Лабораторная работа № 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]