Двойственный симплекс метод - как? Примеры решения

На днях столкнулась с задачей, которая вызвала затруднения, поскольку некогда полученные знания уже утеряны, а пополнить базу новыми, как то удалось не сразу. Насколько помнится из студенческой и преподавательской жизни, данная задача никаких особых подводных камней в себе не таила. Но найти доступную информацию в широком интернет пространстве не удалось. Возможно, плохо искала... Неприятным моментом явилась путаница во многих материалах понятий двойственной задачи и двойственного симплекс метода. Насколько я понимаю, это не одно и тоже. Наличие примеров, как оказалось, является вообще чем то сверх фантастическим.

Вся эта ситуация побудила на написание статьи, дабы упростить задачу себе в будущем и с надеждой помочь еще кому нибудь, ищущему. Итак, попробуем разобраться с решением задач линейного программирования двойственным симплекс методом.

В ходе решения задач симплекс методом встречаемся с понятиями допустимого плана и оптимального плана.

Целью задачи линейного программирования является нахождения оптимального плана с учетом того, что переменные могут принимать допустимые (не отрицательные) значения.  Итак, найти оптимальный план - значит решить задачу. 

Рассмотрим задачу, которую необходимо решить двойственным симплекс методом. При составлении симплекс таблицы убеждаемся, что исходный план и не оптимален и не допустим - самая общая ситуация.

Интересно, что все найденные мной примеры рассматривали не общий, а частный случай задачи. Условие ставили таким образом, что план уже был оптимальный, и не требовал каких либо преобразований. Описывали алгоритм двойственного метода и все..дело в шляпе...А что делать, если вы столкнулись с общим случаем задачи?

Все это разговоры, перейдем к решению!