- •Решение злп симплекс методом
- •1)Злп нужно привести к канонической форме
- •3) Сводят все данные в симплекс таблицу.
- •1)Все индексные оценки «хорошие», следовательно, получен оптимальный план. Если при этом решали м-задачу и все , то получен и оптимальный план исходной задачи.
- •3)Если есть «плохие» оценки, но в соответствующих столбцах нет ни одного положительного элемента, то целевая функция неограниченна.
1)Все индексные оценки «хорошие», следовательно, получен оптимальный план. Если при этом решали м-задачу и все , то получен и оптимальный план исходной задачи.
Если хотя бы одна из искусственных базисных переменных не равна нулю, то исходная задача решения не имеет. Ее ограничения противоречивы и ОДЗ пусто.
2)Если получен оптимальный план и при этом хотя бы одна нулевая индексная оценка соответствует свободной переменной, то задача имеет бесконечное множество оптимальных планов. Тогда соответствующую свободную переменную вводят в базис и получают еще один оптимальный план.
3)Если есть «плохие» оценки, но в соответствующих столбцах нет ни одного положительного элемента, то целевая функция неограниченна.
При применении симплекс метода переходят от вершины к вершине ОДЗ, двигаясь в направлении градиента по ребру.
Пример
|
|
1 |
2 |
0 |
0 |
М |
B |
|
|
|
|
|
|
||||
|
0 |
2 |
4 |
1 |
0 |
0 |
10 |
|
|
М |
1 |
1 |
0 |
-1 |
1 |
2 |
|
|
М |
М |
0 |
-М |
0 |
2М |
|
|
-1 |
-2 |
0 |
0 |
0 |
0 |
|
.
.
Оценка (М-1) определяет разрешающий столбец.
, где - коэффициент столбца В, - соответствующие положительные коэффициенты разрешающего столбца. , . Минимальное значение определяет разрешающую строку. На пересечении разрешающего столбца и разрешающей строки стоит разрешающий элемент 1.
|
|
1 |
2 |
0 |
0 |
М |
|
|
|
|
|
|
|
||||
|
0 |
2 |
4 |
1 |
0 |
0 |
10 |
10:2=5 |
|
М |
1 |
1 |
0 |
-1 |
1 |
2 |
2:1=2-min |
|
М |
М |
0 |
-М |
0 |
2М |
|
|
-1 |
-2 |
0 |
0 |
0 |
0 |
|
Верхняя строка индексных оценок :
.
Нижняя строка :
.
Проверим индексные оценки
.
|
|
1 |
2 |
0 |
0 |
М |
|
|
|
|
|
|
|
||||
|
0 |
2 |
4 |
1 |
0 |
0 |
10 |
10:2=5 |
|
М |
1 |
1 |
0 |
-1 |
1 |
2 |
2:1=2-min |
|
М |
М |
0 |
-М |
0 |
2М |
|
|
-1 |
-2 |
0 |
0 |
0 |
0 |
|
||
|
0 |
0 |
2 |
1 |
2 |
-2 |
6 |
|
|
1 |
1 |
1 |
0 |
-1 |
1 |
2 |
|
|
0 |
0 |
0 |
0 |
-М |
0 |
|
|
0 |
-1 |
0 |
-1 |
1 |
2 |
|
Так как нет положительных оценок, то получено оптимальное решение М-задачи. Свободные переменные, не являющиеся базисными, полагаем равными нулю. Т.е. , , . Базисные переменные равны соответствующим значениям , т.е. . Минимальное значение равно . Итак, . Так как искусственная базисная переменная , то получено и решение первоначальной задачи .
В случае единственного решения число нулевых индексных оценок должно равняться числу базисных переменных. Так как данное равенство выполняется, то полученное решение является единственным.
Пример
|
|
1 |
2 |
0 |
0 |
-М |
|
|
|
|
|
|
|
||||
|
0 |
2 |
4 |
1 |
0 |
0 |
10 |
10:4=2,5 |
|
-М |
1 |
1 |
0 |
-1 |
1 |
2 |
2:1=2-min |
|
-М |
-М |
0 |
М |
0 |
-2М |
|
|
-1 |
-2 |
0 |
0 |
0 |
0 |
|
.
.
Нижняя строка
.
|
|
1 |
2 |
0 |
0 |
-М |
|
|
|
|
|
|
|
||||
|
0 |
2 |
4 |
1 |
0 |
0 |
10 |
10:4=2,5 |
|
-М |
1 |
1 |
0 |
-1 |
1 |
2 |
2:1=2-min |
|
-М |
-М |
0 |
М |
0 |
-2М |
|
|
-1 |
-2 |
0 |
0 |
0 |
0 |
|
||
|
0 |
-2 |
0 |
1 |
.4. |
-4 |
2 |
2 : 4 = 1/2 |
|
2 |
1 |
1 |
0 |
-1 |
1 |
2 |
|
|
0 |
0 |
0 |
0 |
М |
0 |
|
|
1 |
0 |
0 |
-2 |
2 |
4 |
|
Проверим индексные оценки
.
|
|
1 |
2 |
0 |
0 |
-М |
|
|
|
|
|
|
|
||||
|
0 |
2 |
4 |
1 |
0 |
0 |
10 |
10:4=2,5 |
|
-М |
1 |
1 |
0 |
-1 |
1 |
2 |
2:1=2-min |
|
-М |
-М |
0 |
М |
0 |
-2М |
|
|
-1 |
-2 |
0 |
0 |
0 |
0 |
|
||
|
0 |
-2 |
0 |
1 |
.4. |
-4 |
2 |
2 : 4 = 1/2 |
|
2 |
1 |
1 |
0 |
-1 |
1 |
2 |
|
|
0 |
0 |
0 |
0 |
М |
0 |
|
|
1 |
0 |
0 |
-2 |
2 |
4 |
|
||
|
0 |
-1/2 |
0 |
1/4 |
1 |
-1 |
1/2 |
|
|
2 |
1/2 |
1 |
1/4 |
0 |
0 |
5/2 |
5/2 : 1/2= 5 |
|
0 |
0 |
0 |
0 |
М |
0 |
|
|
0 |
0 |
1/2 |
0 |
0 |
5 |
|
Так как все индексные оценки неотрицательны, то найдено оптимальное решение задачи. При этом все свободные переменные (отсутствующие в столбце последней симплекс таблицы) равны 0. Базисные переменные . Значение целевой функции равно .
То есть, Так как , то получено и решение первоначальной задачи . Оптимальный план . Проверим, является ли он единственным.
В случае единственного решения число нулевых индексных оценок должно равняться числу базисных переменных. В данном случае число базисных переменных ( и ) равно 2, а нулевых индексных оценок три: . Следовательно, задача имеет бесконечное множество решений. Т.к. одна свободная переменная имеет нулевую индексную оценку, то существует еще одно оптимальное решение, линейно независимое с полученным решением. Вводя (свободную переменную с нулевой индексной оценкой) в базис, перейдем к следующей симплекс таблице. Т.е. разрешающий столбец . В нем только один положительный элемент 1/2, который является разрешающим. Симплекс таблица приобретет следующий вид.
|
|
1 |
2 |
0 |
0 |
-М |
|
|
|
|
|
|
|
||||
|
0 |
2 |
4 |
1 |
0 |
0 |
10 |
10:4=2,5 |
|
-М |
1 |
1 |
0 |
-1 |
1 |
2 |
2:1=2-min |
|
-М |
-М |
0 |
М |
0 |
-2М |
|
|
-1 |
-2 |
0 |
0 |
0 |
0 |
|
||
|
0 |
-2 |
0 |
1 |
.4. |
-4 |
2 |
2: 4 = 1/2 |
|
2 |
1 |
1 |
0 |
-1 |
1 |
2 |
|
|
0 |
0 |
0 |
0 |
М |
0 |
|
|
1 |
0 |
0 |
-2 |
2 |
4 |
|
||
|
0 |
-1/2 |
0 |
1/4 |
1 |
-1 |
1/2 |
|
|
2 |
1/2 |
1 |
1/4 |
0 |
0 |
5/2 |
5/2: 1/2= 5 |
|
0 |
0 |
0 |
0 |
М |
0 |
|
|
0 |
0 |
1/2 |
0 |
0 |
5 |
|
||
|
0 |
0 |
1 |
1/2 |
1 |
-1 |
3 |
|
|
1 |
1 |
2 |
1/2 |
0 |
0 |
5 |
|
|
0 |
0 |
0 |
0 |
М |
0 |
|
|
0 |
0 |
1/2 |
0 |
0 |
5 |
|
Выпишем полученное решение М-задачи и решение первоначальной задачи . Оптимальный план .
Итак, максимальное значение достигается в двух вершинах многоугольника, а, следовательно, и на отрезке прямой соединяющей эти вершины (на стороне многоугольника). Общий оптимальный план (любая точка этой стороны многоугольника) имеет вид: , где .
Если обозначить , то ответ можно записать так: задача имеет бесконечное множество решений.
.
Пример
Приведем задачу к каноническому виду, заменяя неравенства равенствами.
В первом уравнении нет базисной переменной, поэтому вводим искусственную базисную переменную и, так как решается задача на max, то в целевую функцию войдет с коэффициентом (-М).
|
|
2 |
3 |
0 |
0 |
-М |
|
|
|
|
|
|
|
||||
|
-M |
2 |
1 |
-1 |
0 |
1 |
2 |
2:2=1 |
|
0 |
1 |
-1 |
0 |
1 |
0 |
0 |
0:1=0-min |
|
-2М |
-М |
M |
0 |
0 |
-2М |
|
|
-2 |
-3 |
0 |
0 |
0 |
0 |
|
Строка индексных оценок
.
Верхняя строка
.
Нижняя строка
.
|
|
2 |
3 |
0 |
0 |
-М |
|
|
|
|
|
|
|
||||
|
-M |
2 |
1 |
-1 |
0 |
1 |
2 |
2:2=1 |
|
0 |
1 |
-1 |
0 |
1 |
0 |
0 |
0:1=0-min |
|
-2М |
-М |
M |
0 |
0 |
-2М |
|
|
-2 |
-3 |
0 |
0 |
0 |
0 |
|
||
|
-M |
0 |
3 |
-1 |
.-2 |
1 |
2 |
2:3=2/3 |
|
2 |
1 |
-1 |
0 |
1 |
0 |
0 |
|
|
0 |
-3M |
M |
2M |
0 |
-2M |
|
|
0 |
-5 |
0 |
2 |
0 |
0 |
|
Проверим индексные оценки
.
|
|
2 |
3 |
0 |
0 |
-М |
|
|
|||||||
|
|
|
|
|
|||||||||||
|
-M |
2 |
1 |
-1 |
0 |
1 |
2 |
2:2=1 |
|||||||
|
0 |
1 |
-1 |
0 |
1 |
0 |
0 |
0:1=0-min |
|||||||
|
-2М |
-М |
M |
0 |
0 |
-2М |
|
||||||||
-2 |
-3 |
0 |
0 |
0 |
0 |
|
|||||||||
|
-M |
0 |
3 |
-1 |
.-2 |
1 |
2 |
2:3=2/3 |
|||||||
|
2 |
1 |
-1 |
0 |
1 |
0 |
0 |
|
|||||||
|
0 |
-3M |
M |
2M |
0 |
-2M |
|
||||||||
0 |
-5 |
0 |
2 |
0 |
0 |
|
|||||||||
|
3 |
0 |
1 |
-1/3 |
.-2/3 |
1/3 |
2/3 |
|
|||||||
|
2 |
1 |
0 |
-1/3 |
1/3 |
1/3 |
2/3 |
|
|||||||
|
0 |
0 |
0 |
0 |
M |
0 |
|
||||||||
0 |
0 |
-5/3 |
-4/3 |
5/3 |
10/3 |
|
«Самая плохая» оценка равна (-5/3). Но в этом столбце нет ни одного положительного элемента. Такая ситуация и соответствует неограниченности целевой функции. Итак, .
Пример
|
|
1 |
2 |
0 |
0 |
М |
|
|
|||||||
|
|
|
|
|
|||||||||||
|
М |
2 |
1 |
-1 |
0 |
1 |
8 |
8:2=4 |
|||||||
|
0 |
1 |
2 |
0 |
1 |
0 |
2 |
2:1=2-min |
|||||||
|
2М |
М |
-М |
0 |
0 |
8М |
|
||||||||
-1 |
-2 |
0 |
0 |
0 |
0 |
|
|||||||||
|
М |
0 |
-3 |
-1 |
-2-2. |
1 |
4 |
|
|||||||
|
1 |
1 |
2 |
0 |
1 |
0 |
2 |
|
|||||||
|
0 |
-3М |
-М |
-2М |
0 |
4М |
|
||||||||
0 |
0 |
0 |
1 |
0 |
2 |
|
Все оценки неположительные, следовательно, получено оптимальное решение М-задачи. Но т.к. то исходная задача решений не имеет