Лабораторная работа №2 по "Основам теории систем" (Решение задач линейного программирования симплекс-методом. Варианты разрешимости задач линейного программирования)Данное решение является оптимальным.
Изобразим это решение на графике: Видим, что единственное и достигается в угловой точке области допустимых решений. 2 вариант.
Отмечая успешно сданную сессию, вышеупомянутые студенты взяли столько же пива и в таких же пропорциях, за исключением того, что вместо пива «Премьер» было куплено пиво «Окское», крепость которого 6,4 % (дешевое и разбавленное). Определить план распития напитков для получения максимального суммарного опьянения (в Функция цели: Приводим ограничения к каноническому виду: = > Решаем симплекс-методом: | 16 | 6,4 | 0 | 0 | 0 | 0 | | С в | Б.П. | X 1 | X 2 | X 3 | X 4 | X 5 | X 6 | В | 0 | X 3 | 2 | 2 | 1 | 0 | 0 | 0 | 1,5 | 0 | X 4 | 3,5 | 1 | 0 | 1 | 0 | 0 | 1,5 | 0 | X 5 | 10 | 4 | 0 | 0 | 1 | 0 | 4,5 | 0 | X 6 | 0 | 1 | 0 | 0 | 0 | 1 | 0,7 | | F | -16 | -10 | 0 | 0 | 0 | 0 | 0 | | 16 | 6,4 | 0 | 0 | 0 | 0 | | С в | Б.П. | X 1 | X 2 | X 3 | X 4 | X 5 | X 6 | В | 0 | X 3 | 0 | 1,428 | 1 | -0,571 | 0 | 0 | 0,642 | 16 | X 1 | 1 | 1,286 | 0 | 0,286 | 0 | 0 | 0,428 | 0 | X 5 | 0 | 1,142 | 0 | -2,85 | 1 | 0 | 0,214 | 0 | X 6 | 0 | 1 | 0 | 0 | 0 | 1 | 0,7 | | F | 0 | -1,82 | 0 | 4,571 | 0 | 0 | 6,857 | | 16 | 6,4 | 0 | 0 | 0 | 0 | | С в | Б.П. | X 1 | X 2 | X 3 | X 4 | X 5 | X 6 | В | 0 | X 3 | 0 | 0 | 1 | 3 | -1,25 | 0 | 0,375 | 16 | X 1 | 1 | 0 | 0 | 1 | -0,25 | 0 | 0,375 | 6,4 | X 2 | 0 | 1 | 0 | -2,5 | 0,875 | 0 | 0,1875 | 0 | X 6 | 0 | 0 | 0 | 2,5 | -0,875 | 1 | 0,5125 | | F | 0 | 0 | 0 | 0 | 1,6 | 0 | 7,2 | Видим, что все оценки положительны, значит оптимальное решение достигнуто. Но одна из свободных переменных ( | 16 | 10 | 0 | 0 | 0 | 0 | | С в | Б.П. | X 1 | X 2 | X 3 | X 4 | X 5 | X 6 | в | 0 | X 4 | 0 | 0 | 0,333 | 1 | -0,416 | 0 | 0,125 | 16 | X 1 | 1 | 0 | -0,333 | 0 | 0,166 | 0 | 0,25 | 10 | X 2 | 0 | 1 | 1,833 | 0 | -0,166 | 0 | 0,5 | 0 | X 6 | 0 | 0 | -0,833 | 0 | 0,166 | 1 | 0,2 | | F | 0 | 0 | 0 | 0 | 1 | 0 | 7,2 | Если оптимальное решение достигнуто в 2-х точках, то оно достигается и на отрезке между ними. Можно составить уравнение данного отрезка по формуле: ; На графике видно, что оптимальное решение достигается на отрезке, значит является альтернативным.
Вектор градиента целевой функции ( F) параллелен радиус-вектору ограничения ( 3 ). Это ограничение образует все множество оптимальных решений. Можно сделать вывод, что альтернативные решения имеются, когда все оценки свободных переменных больше 0, а среди коэффициентов целевой функции оценка одной из свободных переменных равна 0. 3 вариант.
Студент Петров, решив догнать по количеству выпитого студента Сидорова, выпил 4 доли пива «Русич» вместо запланированных 3,5. Решим задачу с учетом изменившихся данных.
Функция цели: Приводим ограничения к каноническому виду: = > Решим задачу симплекс-методом. | 16 | 10 | 0 | 0 | 0 | 0 | | С в | Б.П. | X 1 | X 2 | X 3 | X 4 | X 5 | X 6 | в | 0 | X 3 | 2 | 2 | 1 | 0 | 0 | 0 | 1,5 | 0 | X 4 | 4 | 1 | 0 | 1 | 0 | 0 | 1,5 | 0 | X 5 | 10 | 4 | 0 | 0 | 1 | 0 | 4,5 | 0 | X 6 | 0 | 1 | 0 | 0 | 0 | 1 | 0,7 | | F | -16 | -10 | 0 | 0 | 0 | 0 | 0 | . | 16 | 10 | 0 | 0 | 0 | 0 | | С в | Б.П. | X 1 | X 2 | X 3 | X 4 | X 5 | X 6 | В | 0 | X 3 | 0 | 1,5 | 1 | -0,5 | 0 | 0 | 0,75 | 16 | X 1 | 1 | 0,25 | 0 | 0,25 | 0 | 0 | 0,375 | 0 | X 5 | 0 | 1,5 | 0 | -2,5 | 1 | 0 | 0,75 | 0 | X 6 | 0 | 1 | 0 | 0 | 0 | 1 | 0,7 | | F | 0 | -6 | 0 | 4 | 0 | 0 | 6 | . | 16 | 10 | 0 | 0 | 0 | 0 | | С в | Б.П. | X 1 | X 2 | X 3 | X 4 | X 5 | X 6 | в | 10 | X 2 | 0 | 1 | 1,666 | -0,333 | 0 | 0 | 0,5 | 16 | X 1 | 1 | 0 | -0,166 | 0,333 | 0 | 0 | 0,25 | 0 | X 5 | 0 | 0 | -1 | -2 | 1 | 0 | 0 | 0 | X 6 | 0 | 0 | -0,666 | 0,333 | 0 | 1 | 0,2 | | F | 0 | 0 | 4 | 2 | 0 | 0 | 9 | Данное оптимальное решение является вырожденным, т.к. положительных компонентов меньше числа ограничений. На существование вырожденного оптимального решения указывает наличие в симплекс-таблице нулевого свободного члена при найденном оптимальном решении. В случае вырожденного решения симплекс-таблица может зацикливаться.
Существует 2 способа предупреждения зацикливания: а) – изменение хода ограничения на некоторые величины б) Если минимальное отношение свободных коэффициентов к положительным членам разрешающего столбца определяется неоднозначно, то выбирается отношение любого другого столбца к положительным коэффициентам данного столбца, пока строка не определится однозначно. 4 вариант. В связи с неожиданно полученной стипендией, запасы пива резко увеличились.
Функция цели: Приводим ограничения к каноническому виду: = > В матрице условий нет единичной подматрицы, поэтому используем метод искусственного базиса.
Построим вспомогательную задачу. Решаем вспомогательную задачу симплекс-методом: | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | | С в | Б.П. | X 1 | X 2 | X 3 | X 4 | X 5 | X 6 | X 7 | X 8 | X 9 | X 10 | в | 1 | X 7 | 2 | 2 | -1 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 1,5 | 1 | X 8 | 3.5 | 1 | 0 | -1 | 0 | 0 | 0 | 1 | 0 | 0 | 1,5 | 1 | X 9 | 10 | 4 | 0 | 0 | -1 | 0 | 0 | 0 | 1 | 0 | 4,5 | 1 | X 10 | 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 | | С в | Б.П. | X 1 | X 2 | X 3 | X 4 | X 5 | X 6 | X 7 | X 8 | X 9 | X 10 | в | 1 | X 7 | 0 | 1,428 | -1 | 0,571 | 0 | 0 | 1 | -0,571 | 0 | 0 | 0,642 | 0 | X 1 | 1 | 0,285 | 0 | -0,285 | 0 | 0 | 0 | 0,285 | 0 | 0 | 0,428 | 1 | X 9 | 0 | 1,142 | 0 | 2,857 | -1 | 0 | 0 | -2,85 | 1 | 0 | 0,214 | 1 | X 10 | 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 | | С в | Б.П. | X 1 | X 2 | X 3 | X 4 | X 5 | X 6 | X 7 | X 8 | X 9 | X 10 | в | 1 | X 7 | 0 | 0 | -1 | -3 | 1,25 | 0 | 1 | 3 | -1,25 | 0 | 0,375 | 0 | X 1 | 1 | 0 | 0 | -1 | 0,25 | 0 | 0 | 1 | -0,25 | 0 | 0,375 | 0 | X 2 | 0 | 1 | 0 | 2,5 | -0,875 | 0 | 0 | -2,5 | 0,875 | 0 | 0,187 | 1 | X 10 | 0 | 0 | 0 | -2,5 | 0,875 | -1 | 0 | 2,5 | -0,875 | 1 | 0,512 | | 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 | | С в | Б.П. | X 1 | X 2 | X 3 | X 4 | X 5 | X 6 | X 7 | X 8 | X 9 | X 10 | в | 1 | X 8 | 0 | 0 | -0,333 | -1 | 0,416 | 0 | 0,333 | 1 | -0,416 | 0 | 0,125 | 0 | X 1 | 1 | 0 | 0,333 | 0 | -0,166 | 0 | -,333 | 0 | 0,166 | 0 | 0,25 | 0 | X 2 | 0 | 1 | -0,833 | 0 | 0,166 | 0 | 0,833 | 0 | -0,166 | 0 | 0,5 | 1 | X 10 | 0 | 0 | 0,833 | 0 | -0,166 | -1 | -0,833 | 0 | 0,166 | 1 | 0,2 | | 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 | | С в | Б.П. | X 1 | X 2 | X 3 | X 4 | X 5 | X 6 | X 7 | X 8 | X 9 | X 10 | в | 1 | X 8 | 0 | 0 | 0 | -1 | 0,35 | -0,4 | 0 | 1 | -0,35 | 0,4 | 0,205 | 0 | X 1 | 1 | 0 | 0 | 0 | -0,1 | 0,4 | 0 | 0 | 0,1 | -0,4 | 0,17 | 0 | X 2 | 0 | 1 | 0 | 0 | 0 | -1 | 0 | 0 | 0 | 1 | 0,7 | 0 | X 3 | 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 | | С в | Б.П. | X 1 | X 2 | X 3 | X 4 | X 5 | X 6 | X 7 | X 8 | X 9 | X 10 | в | 0 | X 5 | 0 | 0 | 0 | -2,85 | 1 | -1,14 | 0 | 2,857 | -1 | -1,142 | 0,585 | 0 | X 1 | 1 | 0 | 0 | -0,285 | 0 | 0,285 | 0 | 0,285 | 0 | -0,285 | 0,228 | 0 | X 2 | 0 | 1 | 0 | 0 | 0 | -1 | 0 | 0 | 0 | 1 | 0,7 | 0 | X 3 | 0 | 0 | 1 | -0,571 | 0 | -1,42 | -1 | -1,571 | 0 | 1,428 | 0,357 | | F | 0 | 0 | 0 | 0 | 0 | 0 | -1 | -1 | -1 | -1 | 0 | оптимальное решение вспомогательной задачи.
Искусственные переменные являются свободными и равны нулю. Т.о. это решение является опорным планом исходной задачи. Решим исходную задачу: | 16 | 10 | 0 | 0 | 0 | 0 | | С в | Б.П. | X 1 | X 2 | X 3 | X 4 | X 5 | X 6 | в | 0 | X 5 | 0 | 0 | 0 | -2,85 | 1 | -1,14 | 0,585 | 16 | X 1 | 1 | 0 | 0 | -0,285 | 0 | 0,285 | 0,228 | 10 | X 2 | 0 | 1 | 0 | 0 | 0 | -1 | 0,7 | 0 | X 3 | 0 | 0 | 1 | -0,571 | 0 | -1,42 | 0,357 | | F | 0 | 0 | 0 | -4,576 | 0 | -5,424 | 3,648 | 5 вариант. После отмеченного таким образом праздника обязательно наступает похмелье. Решим задачу из предыдущего варианта, минимизируя этот неприятный фактор, т.е. функция цели: Приводим ограничения к каноническому виду: = > Эта задача решается методом искусственного базиса, т.к. в ней нет единичной подматрицы.
|