Двойственный симплекс метод - как? Примеры решения
![]() |
На днях столкнулась с задачей, которая вызвала затруднения, поскольку некогда полученные знания уже утеряны, а пополнить базу новыми, как то удалось не сразу.Насколько помнится из студенческой и преподавательской жизни, данная задача никаких особых подводных камней в себе не таила. Но найти доступную информацию в широком интернет пространстве не удалось. Возможно, плохо искала... Неприятным моментом явилась путаница во многих материалах понятий двойственной задачи и двойственного симплекс метода. Насколько я понимаю, это не одно и тоже. Наличие примеров, как оказалось, является вообще чем то сверх фантастическим. |
Вся эта ситуация побудила на написание статьи, дабы упростить задачу себе в будущем и с надеждой помочь еще кому нибудь, ищущему. Итак, попробуем разобраться с решением задач линейного программирования двойственным симплекс методом.
В ходе решения задач симплекс методом встречаемся с понятиями допустимого плана и оптимального плана.
Целью задачи линейного программирования является нахождения оптимального плана с учетом того, что переменные могут принимать допустимые (не отрицательные) значения. Итак, найти оптимальный план - значит решить задачу.
Рассмотрим задачу, которую необходимо решить двойственным симплекс методом. При составлении симплекс таблицы убеждаемся, что исходный план и не оптимален и не допустим - самая общая ситуация.
Интересно, что все найденные мной примеры рассматривали не общий, а частный случай задачи. Условие ставили таким образом, что план уже был оптимальный, и не требовал каких либо преобразований. Описывали алгоритм двойственного метода и все..дело в шляпе...А что делать, если вы столкнулись с общим случаем задачи?
Все это разговоры, перейдем к решению!