- •Решение задач симплексным методом
- •План решения:
- •2.Привести систему неравенств к каноническому виду.
- •3.Составить симплекс-
- •Индексная строка
- •4.Проверить знаки в индексной строке.
- •5.Найти наименьшее Q.
- •План
- •Правилом
- •Правило прямоугольника на практике.
- •Внимание
- •7. Сформировать следующую часть симплексной таблицы, пользуясь правилом прямоугольника.
- •Разрешающий элемент
- •Новая симплекс таблица.
Решение задач симплексным методом
План решения:
•1.Составить систему неравенств. 2.Привести систему неравенств к каноническому виду.
3.Составить симплекс-таблицу. 4.Проверить знаки в индексной строке. 5.Найти наибольшее Q.
6.Найти разрешающий элемент.
7. Сформировать следующую часть симплексной таблицы, пользуясь правилом прямоугольника.
•Симплекс-пример: Дано: F(x)=3х1+5х2+4х3→Max
0.1х1+0.2х2+0.4х3≤1100 0.05х1+0.02х2+0.02х3≤120 3х1+1х2+2х3≤8000
1.На данном этапе смотрим к чему стремиться функция Max,Min.От этого зависит знак неравенств. 2.Если функция стремится к Max,то знак неравенств ≤.Если функция стремится к Min,то знак неравенств ≥
2.Привести систему неравенств к каноническому виду.
0.1х1+0.2х2+0.4х3 0.05х1+0.02х2+0.02х3 3х1+1х2+2х3
0.1х1+0.2х2+0.4х3+0х4=1100 0.05х1+0.02х2+0.02х3+0х5=120 3х1+1х2+2х3+0х6=8000
1.Уравниваем правую и левую часть неравенства добавляя новый элемент. Элементы не должны повторяться.
3.Составить симплекс-
План |
Баз В |
таблицу. |
х5 |
х6 |
Q |
||||
х1 |
х2 |
х3 |
х4 |
||||||
|
ис |
|
|
|
|
|
|
|
|
1 |
х4 |
110 |
0.1 |
0.2 |
0.4 |
1 |
0 |
0 |
|
|
|
|
|||||||
|
х5 |
0 |
|
|
|
|
|
|
|
|
120 |
0.05 |
0.02 |
0.02 |
0 |
1 |
0 |
|
|
|
х6 |
|
|
|
|
|
|
||
|
800 |
3 |
1 |
2 |
0 |
0 |
1 |
|
|
|
|
|
|||||||
Индексн |
|
0 |
|
|
|
|
|
|
|
F(X1)0 |
|
|
|
|
|
|
|
||
ая |
|
|
|
|
|
|
|
||
строка |
записываем |
|
|
|
|
|
|
|
2.Базис – записываем добавленные элементы(базисные элементы). 3.В-коэффициенты уравнений.
4.Q- это отношение столбца B к столбцу с наименьшим коэффициентом в индексной строке.
5.Индексная строка – коэффициенты функции.
Индексная строка
План |
Баз |
В |
х1 |
х2 |
х3 |
х4 |
х5 |
х6 Q |
|
|
ис |
|
|
|
|
|
|
|
|
1 |
х4 |
110 |
0.1 |
0.2 |
0.4 |
1 |
0 |
0 |
|
|
|
||||||||
|
х5 |
0 |
|
|
|
|
|
|
|
|
120 |
0.05 |
0.02 |
0.02 |
0 |
1 |
0 |
||
|
х6 |
|
|
|
|
|
|||
|
800 |
3 |
1 |
2 |
0 |
0 |
1 |
||
|
|
||||||||
Индексн |
|
0 |
|
|
|
|
|
|
|
F(X1) |
0 |
-3 |
-5 |
-4 |
0 |
0 |
0 |
||
ая |
|||||||||
строка |
|
|
|
|
|
|
|
|
|
В индексной строке записываем |
|
произведение коэффициентов функции на -1.
Коэффициенты в базисных элементах равны 0.
4.Проверить знаки в индексной строке.
Пла |
Бази |
В |
х1 |
х2 |
х3 |
х4 |
х5 |
х6 Q |
н |
с |
|
|
|
|
|
|
|
1 |
х4 |
1100 |
0.1 |
0.2 |
0.4 |
1 |
0 |
0 |
|
х5 |
120 |
0.05 |
0.02 |
0.02 |
0 |
1 |
0 |
|
х6 |
8000 |
3 |
1 |
2 |
0 |
0 |
1 |
Инде |
|
|
|
|
|
|
|
|
ксна |
F(X1) |
0 |
-3 |
-5 |
-4 |
0 |
0 |
0 |
я |
||||||||
стро |
|
|
|
|
|
отрицательные |
||
ка |
|
|
|
необходимо избавиться |
*Выбираем наименьшее отрицательное число. *В столбце с наименьшем отрицательным числом будет находиться разрешающий элемент.
5.Найти наименьшее Q.
Пла |
Бази |
В |
х1 |
х2 |
х3 |
х4 |
х5 |
х6 |
Q |
н |
с |
|
|
|
|
|
|
|
|
1 |
х4 |
1100 |
0.1 |
0.2 |
0.4 |
1 |
0 |
0 |
5500 |
|
х5 |
120 |
0.05 |
0.02 |
0.02 |
0 |
1 |
0 |
6000 |
|
х6 |
8000 |
3 |
1 |
2 |
0 |
0 |
1 |
8000 |
Инде |
|
|
|
|
|
|
|
|
|
ксна |
F(X1) |
0 |
-3 |
-5 |
-4 |
0 |
0 |
0 |
0 |
я |
|||||||||
ка |
|
|
|
|
помогает |
|
|
||
стро |
|
|
|
|
|
|
|
|
|
разрешающий элемент *Q=Элементы столбца В делить на
элементы столбца с наименьшим числом в индексной строке.
*1100/0.2=5500
*Необходимо выбрать наименьшее Q.
План
1
6.Найти разрешающий
Баз В |
х1элемент. |
х5 |
х6 |
|||||
|
х2 |
х3 |
х4 |
|||||
ис |
|
|
|
|
|
|
|
|
х4 |
110 |
0.1 |
0.2 |
0.4 |
1 |
0 |
0 |
|
|
||||||||
х5 |
0 |
|
|
|
|
|
|
|
120 |
0.05 |
0.02 |
0.02 |
0 |
1 |
0 |
||
х6 |
|
|
|
|
|
|
||
800 |
3 |
1 |
2 |
0 |
0 |
1 |
||
|
||||||||
|
0 |
|
|
|
|
|
|
Q
5500
6000
8000
Индексн
ая РазрешающийF(X1) 0 -3 -5 -4 0 0полученный0 0
строка
пересечении столбца наименьшим отрицательным коэффициентом и наименьшим Q. Разрешающий элемент необходим для того, чтобы по правило прямоугольника избавиться от отрицательных элементов в индексной строке.
Правилом
прямоугольника.
•Правило прямоугольника
•Чтобы найти элемент новой симплексной таблицы, нужно воспользоваться правилом прямоугольника. Для этого в исходной таблице выделяют прямоугольник, вершинами которого служат нужные для вычисления элементы. Диагональ, содержащую разрешающий и искомый элементы новой таблицы, называют главной, а другую – побочной. Чтобы получить элемент новой симплексной таблицы, нужно из произведения угловых элементов главной диагонали вычесть произведение угловых элементов побочной диагонали и полученное число разделить на разрешающий элемент, выделенный рамкой.
НЭ = СЭ - (А*В)/РЭ