Лабораторная работа № 2

Телешовой Елизаветы, гр. 726,
Цель работы: Решение задач линейного программирования симплекс-методом.
Варианты разрешимости задач линейного программирования.

1 вариант.
1. Четыре студента: Иванов, Петров, Сидоров и Васильев пошли на концерт группы «Чайф», захватив пиво 2 сортов: «Русич» и «Премьер». Определить план распития напитков для получения максимального суммарного опьянения (в
[pic]). Исходные данные даны в таблице:

|Студент |Норма выпитого |Запасы |
| | |(в |
| | |литрах) |
| |«Русич» |«Премьер» | |
|Иванов |2 |2 |1.5 |
|Петров |3,5 |1 |1,5 |
|Сидоров |10 |4 |4,5 |
|Васильев|– |1 |0,7 |
|Крепость|16 % |10 % | |
|напитка | | | |

2. Математическая модель.
2.1 Управляемые параметры x1[л] – количество выпитого пива «Русич». x2[л] – количество выпитого пива «Премьер».
[pic] – решение.
2.2 Ограничения
[pic] – количество пива «Русич», выпитого Ивановым.
[pic] – количество пива «Премьер», выпитого Ивановым.
[pic]– общее количество пива, выпитого Ивановым.
Общее количество пива, выпитого Ивановым, не превосходит имеющихся у него запасов пива, поэтому:
[pic](л).
Аналогично строим другие ограничения:
[pic](л).
[pic](л).
[pic](л).

3. Постановка задачи.
Найти [pic]*, где достигается максимальное значение функции цели:
[pic]
4. Решение.
[pic] при:
[pic] [pic]
Приведем задачу к каноническому виду:
[pic] [pic]
Определим начальный опорный план: [pic].
Это решение является опорным, т.к. вектора условий при положительных компонентах решения линейно независимы, также [pic], где [pic], но не все оценки положительны ([pic], где [pic] [pic])
Опорный план является оптимальным, если для задачи максимизации все его оценки неотрицательны. [pic] не является оптимальным, значит критерий можно улучшить, если увеличить одну их отрицательных свободных переменных. Будем увеличивать [pic], т.к. ее увеличение вызовет большее увеличение функции цели.
Предположим, что [pic], тогда:
[pic]
Запишем новый опорный план: [pic]. Все оценки опорного плана должны быть неотрицательны, а значит должны выполняться условия:
[pic]=> [pic]
При увеличении [pic], первой перестает выполнять условие неотрицательности переменная [pic], т.к. она первая обращается в ноль. Значит выведем из базиса [pic]. Теперь базисными переменными являются [pic], а свободными
[pic]. Для анализа этого плана выразим функцию цели через новые переменные.
Из ограничения (2) имеем: [pic].
Подставляя в функцию цели: [pic] получаем:
[pic]
Оформим данный этап задачи в виде симплекс-таблицы:
Начальная симплекс-таблица:
| |16 |10 |0 |0 |0 |0 | |
|Св |Б.П. |X1 |X2 |X3 |X4 |X5 |X6 |в |
|0 |X3 |2 |2 |1 |0 |0 |0 |1,5 |
|0 |X4 |3,5 |1 |0 |1 |0 |0 |1,5 |
|0 |X5 |10 |4 |0 |0 |1 |0 |4,5 |
|0 |X6 |0 |1 |0 |0 |0 |1 |0,7 |
| |F |-16 |-10 |0 |0 |0 |0 |0 |

[pic];
Пересчитаем элементы исходной таблицы по правилу четырехугольника:
| |16 |10 |0 |0 |0 |0 | |
|Св |Б.П. |X1 |X2 |X3 |X4 |X5 |X6 |В |
|0 |X3 |0 |1,428|1 |-0,57|0 |0 |0,642 |
| | | | | |2 | | | |
|16 |X1 |1 |0,286|0 |0,286|0 |0 |0,428 |
|0 |X5 |0 |1,14 |0 |-2,86|1 |0 |0,214 |
|0 |X6 |0 |1 |0 |0 |0 |1 |0,7 |
| |F |0 |-5,42|0 |4,576|0 |0 |6,857 |
| | | |4 | | | | | |

[pic];
Пересчитав все оценки, видим, что [pic], значит критерий можно улучшить.
Будем увеличивать [pic]. Пусть [pic], тогда:
[pic] откуда получаем:
[pic];
Все оценки опорного плана должны быть неотрицательны, а значит должны выполняться условия:
[pic] => [pic]
Выведем из базиса [pic]. Теперь базисными переменными являются [pic], а свободными [pic]. Выразим функцию цели через новые переменные:
[pic], а из ограничений (2) и (3): [pic]. Тогда: [pic];
| |16 |10 |0 |0 |0 |0 | |
|Св |Б.П. |X1 |X2 |X3 |X4 |X5 |X6 |В |
|0 |X3 |0 |0 |1 |3 |-1,25|0 |0,375 |
|16 |X1 |1 |0 |0 |1 |-0,25|0 |0,375 |
|10 |X2 |0 |1 |0 |-2,5 |0,875|0 |0,1875|
|0 |X6 |0 |0 |0 |2,5 |-0,87|1 |0,5125|
| | | | | | |5 | | |
| |F |0 |0 |0 |-9 |4,75 |0 |7,875 |

[pic]
Пересчитав все оценки, видим, что [pic], значит критерий можно улучшить.
Будем увеличивать [pic]. Пусть [pic], тогда:
[pic] откуда получаем:
[pic];
Все оценки опорного плана должны быть неотрицательны, а значит должны выполняться условия:
[pic] => [pic]
Выведем из базиса [pic]. Теперь базисными переменными являются [pic], а свободными [pic]. Выразим функцию цели через новые переменные:
[pic], а из ограничений (1) и (2): [pic]. Тогда: [pic];
| |16 |10 |0 |0 |0 |0 | |
|Св |Б.П. |X1 |X2 |X3 |X4 |X5 |X6 |в |
|0 |X4 |0 |0 |0,333|1 |-0,41|0 |0,125 |
| | | | | | |6 | | |
|16 |X1 |1 |0 |-0,33|0 |0,166|0 |0,25 |
| | | | |3 | | | | |
|10 |X2 |0 |1 |1,833|0 |-0,16|0 |0,5 |
| | | | | | |6 | | |
|0 |X6 |0 |0 |-0,83|0 |0,166|1 |0,2 |
| | | | |3 | | | | |
| |F |0 |0 |3 |0 |1 |0 |9 |

[pic]
Видим, что все оценки положительны, значит любое увеличение какой-либо свободной переменной уменьшит критерий. Данное решение является оптимальным. Изобразим это решение на графике:

Видим, что [pic] единственное и достигается в угловой точке области допустимых решений.

2 вариант.
Отмечая успешно сданную сессию, вышеупомянутые студенты взяли столько же пива и в таких же пропорциях, за исключением того, что вместо пива
«Премьер» было куплено пиво «Окское», крепость которого 6,4 % (дешевое и разбавленное). Определить план распития напитков для получения максимального суммарного опьянения (в [pic]).
Функция цели: [pic].
Приводим ограничения к каноническому виду:
[pic] [pic] => [pic] [pic]
Решаем симплекс-методом:
| |16 |6,4 |0 |0 |0 |0 | |
|Св |Б.П. |X1 |X2 |X3 |X4 |X5 |X6 |В |
|0 |X3 |2 |2 |1 |0 |0 |0 |1,5 |
|0 |X4 |3,5 |1 |0 |1 |0 |0 |1,5 |
|0 |X5 |10 |4 |0 |0 |1 |0 |4,5 |
|0 |X6 |0 |1 |0 |0 |0 |1 |0,7 |
| |F |-16 |-10 |0 |0 |0 |0 |0 |

[pic], [pic]
| |16 |6,4 |0 |0 |0 |0 | |
|Св |Б.П. |X1 |X2 |X3 |X4 |X5 |X6 |В |
|0 |X3 |0 |1,428|1 |-0,57|0 |0 |0,642 |
| | | | | |1 | | | |
|16 |X1 |1 |1,286|0 |0,286|0 |0 |0,428 |
|0 |X5 |0 |1,142|0 |-2,85|1 |0 |0,214 |
|0 |X6 |0 |1 |0 |0 |0 |1 |0,7 |
| |F |0 |-1,82|0 |4,571|0 |0 |6,857 |

[pic]; [pic]
| |16 |6,4 |0 |0 |0 |0 | |
|Св |Б.П. |X1 |X2 |X3 |X4 |X5 |X6 |В |
|0 |X3 |0 |0 |1 |3 |-1,25|0 |0,375 |
|16 |X1 |1 |0 |0 |1 |-0,25|0 |0,375 |
|6,4 |X2 |0 |1 |0 |-2,5 |0,875|0 |0,1875|
|0 |X6 |0 |0 |0 |2,5 |-0,87|1 |0,5125|
| | | | | | |5 | | |
| |F |0 |0 |0 |0 |1,6 |0 |7,2 |

[pic]; [pic]
Видим, что все оценки положительны, значит оптимальное решение достигнуто.
Но одна из свободных переменных ([pic]) обратилась в ноль, и если мы ее будем увеличивать, то функция цели не изменится, а решение будет другим, т.е. получим еще одно оптимальное решение, которое будет называться альтернативным.

| |16 |10 |0 |0 |0 |0 | |
|Св |Б.П. |X1 |X2 |X3 |X4 |X5 |X6 |в |
|0 |X4 |0 |0 |0,333|1 |-0,41|0 |0,125 |
| | | | | | |6 | | |
|16 |X1 |1 |0 |-0,33|0 |0,166|0 |0,25 |
| | | | |3 | | | | |
|10 |X2 |0 |1 |1,833|0 |-0,16|0 |0,5 |
| | | | | | |6 | | |
|0 |X6 |0 |0 |-0,83|0 |0,166|1 |0,2 |
| | | | |3 | | | | |
| |F |0 |0 |0 |0 |1 |0 |7,2 |

[pic]
Если оптимальное решение достигнуто в 2-х точках, то оно достигается и на отрезке между ними. Можно составить уравнение данного отрезка по формуле:
[pic];
[pic];

На графике видно, что оптимальное решение достигается на отрезке, значит является альтернативным. Вектор градиента целевой функции (F) параллелен радиус-вектору ограничения (3). Это ограничение образует все множество оптимальных решений.
Можно сделать вывод, что альтернативные решения имеются, когда все оценки свободных переменных больше 0, а среди коэффициентов целевой функции оценка одной из свободных переменных равна 0.

3 вариант.
Студент Петров, решив догнать по количеству выпитого студента Сидорова, выпил 4 доли пива «Русич» вместо запланированных 3,5. Решим задачу с учетом изменившихся данных.
Функция цели:[pic].
Приводим ограничения к каноническому виду:
[pic] [pic] => [pic] [pic]
Решим задачу симплекс-методом.
| |16 |10 |0 |0 |0 |0 | |
|Св |Б.П. |X1 |X2 |X3 |X4 |X5 |X6 |в |
|0 |X3 |2 |2 |1 |0 |0 |0 |1,5 |
|0 |X4 |4 |1 |0 |1 |0 |0 |1,5 |
|0 |X5 |10 |4 |0 |0 |1 |0 |4,5 |
|0 |X6 |0 |1 |0 |0 |0 |1 |0,7 |
| |F |-16 |-10 |0 |0 |0 |0 |0 |

[pic], [pic].
| |16 |10 |0 |0 |0 |0 | |
|Св |Б.П. |X1 |X2 |X3 |X4 |X5 |X6 |В |
|0 |X3 |0 |1,5 |1 |-0,5 |0 |0 |0,75 |
|16 |X1 |1 |0,25 |0 |0,25 |0 |0 |0,375 |
|0 |X5 |0 |1,5 |0 |-2,5 |1 |0 |0,75 |
|0 |X6 |0 |1 |0 |0 |0 |1 |0,7 |
| |F |0 |-6 |0 |4 |0 |0 |6 |

[pic], [pic].
| |16 |10 |0 |0 |0 |0 | |
|Св |Б.П. |X1 |X2 |X3 |X4 |X5 |X6 |в |
|10 |X2 |0 |1 |1,666|-0,33|0 |0 |0,5 |
| | | | | |3 | | | |
|16 |X1 |1 |0 |-0,16|0,333|0 |0 |0,25 |
| | | | |6 | | | | |
|0 |X5 |0 |0 |-1 |-2 |1 |0 |0 |
|0 |X6 |0 |0 |-0,66|0,333|0 |1 |0,2 |
| | | | |6 | | | | |
| |F |0 |0 |4 |2 |0 |0 |9 |

[pic], [pic]
Данное оптимальное решение является вырожденным, т.к. положительных компонентов меньше числа ограничений. На существование вырожденного оптимального решения указывает наличие в симплекс-таблице нулевого свободного члена при найденном оптимальном решении.
В случае вырожденного решения симплекс-таблица может зацикливаться.
Существует 2 способа предупреждения зацикливания: а) [pic] – изменение хода ограничения на некоторые величины [pic]. Они должны быть малы, чтобы изменения были несущественны. б) Если минимальное отношение свободных коэффициентов к положительным членам разрешающего столбца определяется неоднозначно, то выбирается отношение любого другого столбца к положительным коэффициентам данного столбца, пока строка не определится однозначно.

4 вариант.
В связи с неожиданно полученной стипендией, запасы пива резко увеличились.
Функция цели: [pic].
Приводим ограничения к каноническому виду:
[pic] [pic] => [pic] [pic]
В матрице условий нет единичной подматрицы, поэтому используем метод искусственного базиса. Построим вспомогательную задачу.
[pic]
[pic], при этом [pic].
Решаем вспомогательную задачу симплекс-методом:

| |0 |0 |0 |0 |0 |0 |1 |1 |1 |1 | |
|Св |Б.П.|X1 |X2 |X3 |X4 |X5 |X6 |X7 |X8 |X9 |X10 |в |
|1 |X7 |2 |2 |-1 |0 |0 |0 |1 |0 |0 |0 |1,5 |
|1 |X8 |3.5 |1 |0 |-1 |0 |0 |0 |1 |0 |0 |1,5 |
|1 |X9 |10 |4 |0 |0 |-1 |0 |0 |0 |1 |0 |4,5 |
|1 |X10 |0 |1 |0 |0 |0 |-1 |0 |0 |0 |1 |0,7 |
| |F |15,5 |8 |-1 |-1 |-1 |-1 |0 |0 |0 |0 |0 |

| |0 |0 |0 |0 |0 |0 |1 |1 |1 |1 | |
|Св |Б.П.|X1 |X2 |X3 |X4 |X5 |X6 |X7 |X8 |X9 |X10 |в |
|1 |X7 |0 |1,428|-1 |0,571|0 |0 |1 |-0,57|0 |0 |0,642|
| | | | | | | | | |1 | | | |
|0 |X1 |1 |0,285|0 |-0,28|0 |0 |0 |0,285|0 |0 |0,428|
| | | | | |5 | | | | | | | |
|1 |X9 |0 |1,142|0 |2,857|-1 |0 |0 |-2,85|1 |0 |0,214|
|1 |X10 |0 |1 |0 |0 |0 |-1 |0 |0 |0 |1 |0,7 |
| |F |0 |3.571|-1 |3,428|-1 |-1 |0 |-4,42|0 |0 |1,557|

| |0 |0 |0 |0 |0 |0 |1 |1 |1 |1 | |
|Св |Б.П.|X1 |X2 |X3 |X4 |X5 |X6 |X7 |X8 |X9 |X10 |в |
|1 |X7 |0 |0 |-1 |-3 |1,25 |0 |1 |3 |-1,25|0 |0,375|
|0 |X1 |1 |0 |0 |-1 |0,25 |0 |0 |1 |-0,25|0 |0,375|
|0 |X2 |0 |1 |0 |2,5 |-0,87|0 |0 |-2,5 |0,875|0 |0,187|
| | | | | | |5 | | | | | | |
|1 |X10 |0 |0 |0 |-2,5 |0,875|-1 |0 |2,5 |-0,87|1 |0,512|
| | | | | | | | | | |5 | | |
| |F |0 |0 |-1 |-5,5 |2,125|-1 |0 |4,5 |-3,12|0 |0,887|

| |0 |0 |0 |0 |0 |0 |1 |1 |1 |1 | |
|Св |Б.П.|X1 |X2 |X3 |X4 |X5 |X6 |X7 |X8 |X9 |X10 |в |
|1 |X8 |0 |0 |-0,33|-1 |0,416|0 |0,333|1 |-0,41|0 |0,125|
| | | | |3 | | | | | |6 | | |
|0 |X1 |1 |0 |0,333|0 |-0,16|0 |-,333|0 |0,166|0 |0,25 |
| | | | | | |6 | | | | | | |
|0 |X2 |0 |1 |-0,83|0 |0,166|0 |0,833|0 |-0,16|0 |0,5 |
| | | | |3 | | | | | |6 | | |
|1 |X10 |0 |0 |0,833|0 |-0,16|-1 |-0,83|0 |0,166|1 |0,2 |
| | | | | | |6 | |3 | | | | |
| |F |0 |0 |0,5 |-1 |0,25 |-1 |-1,5 |0 |-1,25|0 |0,325|

| |0 |0 |0 |0 |0 |0 |1 |1 |1 |1 | |
|Св |Б.П.|X1 |X2 |X3 |X4 |X5 |X6 |X7 |X8 |X9 |X10 |в |
|1 |X8 |0 |0 |0 |-1 |0,35 |-0,4 |0 |1 |-0,35|0,4 |0,205|
|0 |X1 |1 |0 |0 |0 |-0,1 |0,4 |0 |0 |0,1 |-0,4 |0,17 |
|0 |X2 |0 |1 |0 |0 |0 |-1 |0 |0 |0 |1 |0,7 |
|0 |X3 |0 |0 |1 |0 |-0,2 |-1,2 |-1 |0 |0,2 |1,2 |0,24 |
| |F |0 |0 |0 |-1 |0,35 |-0,4 |-1 |0 |-1,35|-0,6 |0,205|

| |0 |0 |0 |0 |0 |0 |1 |1 |1 |1 | |
|Св |Б.П.|X1 |X2 |X3 |X4 |X5 |X6 |X7 |X8 |X9 |X10 |в |
|0 |X5 |0 |0 |0 |-2,85|1 |-1,14|0 |2,857|-1 |-1,14|0,585|
| | | | | | | | | | | |2 | |
|0 |X1 |1 |0 |0 |-0,28|0 |0,285|0 |0,285|0 |-0,28|0,228|
| | | | | |5 | | | | | |5 | |
|0 |X2 |0 |1 |0 |0 |0 |-1 |0 |0 |0 |1 |0,7 |
|0 |X3 |0 |0 |1 |-0,57|0 |-1,42|-1 |-1,57|0 |1,428|0,357|
| | | | | |1 | | | |1 | | | |
| |F |0 |0 |0 |0 |0 |0 |-1 |-1 |-1 |-1 |0 |

[pic]– оптимальное решение вспомогательной задачи. Искусственные переменные являются свободными и равны нулю. Т.о. это решение является опорным планом исходной задачи.
Решим исходную задачу:
| |16 |10 |0 |0 |0 |0 | |
|Св |Б.П.|X1 |X2 |X3 |X4 |X5 |X6 |в |
|0 |X5 |0 |0 |0 |-2,85|1 |-1,14|0,585|
|16 |X1 |1 |0 |0 |-0,28|0 |0,285|0,228|
| | | | | |5 | | | |
|10 |X2 |0 |1 |0 |0 |0 |-1 |0,7 |
|0 |X3 |0 |0 |1 |-0,57|0 |-1,42|0,357|
| | | | | |1 | | | |
| |F |0 |0 |0 |-4,57|0 |-5,42|3,648|
| | | | | |6 | |4 | |

Критерий можно улучшить, т.к. [pic], [pic], но нельзя найти такое [pic], при котором базисные переменные обращаются в 0. Значит задача неразрешима из-за неограниченности критерия.

5 вариант.
После отмеченного таким образом праздника обязательно наступает похмелье.
Решим задачу из предыдущего варианта, минимизируя этот неприятный фактор, т.е. функция цели: [pic].
Приводим ограничения к каноническому виду:
[pic] [pic] => [pic] [pic]
Эта задача решается методом искусственного базиса, т.к. в ней нет единичной подматрицы. Вспомогательная задача получается точно такой же, как и в предыдущем варианте, поэтому просто возьмем опорный план из предыдущей задачи.
[pic];
| |16 |10 |0 |0 |0 |0 | |
|Св |Б.П.|X1 |X2 |X3 |X4 |X5 |X6 |в |
|0 |X5 |0 |0 |0 |-2,85|1 |-1,14|0,585|
|16 |X1 |1 |0 |0 |-0,28|0 |0,285|0,228|
| | | | | |5 | | | |
|10 |X2 |0 |1 |0 |0 |0 |-1 |0,7 |
|0 |X3 |0 |0 |1 |-0,57|0 |-1,42|0,357|
| | | | | |1 | | | |
| |F |0 |0 |0 |-4,57|0 |-5,42|3,648|
| | | | | |6 | |4 | |

Видим, что оценки свободных переменных меньше нуля, значит решение оптимальное.
[pic]; F = 3,648.
Делаем вывод: оптимальное решение может существовать и при неограниченности области.

Область не ограничена, но существует оптимальное решение [pic], причем единственное, которое достигается в угловой точке.
-----------------------
X(3)

X(2)

X(оп)

X(3)

(3)

(1)

(4)

(2)

[pic]

X(2)

X(4)

F

X(оп)

[pic]

(1)

(4)

F,(3)

[pic]

X(4)

(2)

(1)

X(1)

F

X(оп)

F

(3)

(2)

(4)

(1)

[pic]

(4)

(2)

(3)

F

X(оп)

X(1)

X(2)

(3)

(2)

(4)

(1)

[pic]