Сформулированный выше алгоритм Симплекс-метода можно применять лишь в том случае, если выделено первое допустимое решение, т.е. исходная задача линейного программирования приведена к виду
При этом , тогда, положив свободные неизвестные равными нулю, получаем опорное решение .
Рассмотрю метод нахождения опорного решения, основанный на введении искусственных переменных. Для этого запишем задачу линейного программирования в общем виде. Будем рассматривать задачу с числом неизвестных и ограничениями:
(5.1)
Перепишем систему (5.1) в другом виде. Для этого введём искусственные переменные так, чтобы был выделен базис. Тогда система примет вид
(5.2)
Системы (5.1) и (5.2) будут эквивалентны в том случае, если все , для будут равны 0. Кроме того, считаю, что все для . В противном случае соответствующие ограничения из системы (5.1) умножим на – 1. Для того чтобы были равны 0, мы должны преобразовать задачу таким образом, чтобы все искусственные переменные перешли в свободные неизвестные.
В этом случае система (5.2) после преобразования примет вид:
(5.3)
От системы (5.2) к системе (5.3) всегда можно перейти шагами симплекс-метода. При таком переходе в качестве линейной формы рассматривают функцию
, (5.4)
равную сумме искусственных переменных. Переход заканчивают, когда и все искусственные переменные переведены в свободные неизвестные.
Анализ вариантов решений
1. Если , а все переведены в свободные переменные, то задача не имеет положительного решения.
2. Если , а часть осталась в базисе, то для перевода их в свободные необходимо применять специальные приёмы.
В симплекс-таблице, соответствующей системе (5.3), после того как , а все - свободные, вычёркивают строку для и столбцы для и решают задачу для исходной линейной формы .
Рекомендуется вводить минимум искусственных переменных.
5.2. Второй алгоритм отыскания опорного плана.
Пусть задача линейного программирования записана в каноническом виде:
(5.5)
(5.6)
, , , .
Построим первую таблицу Жордана-Гаусса для задач (5.5) и (5.6). Для единообразия вычислительной процедуры к исходной таблице приписываем строку целевой функции:
(5.7)
После приведения системы ограничений к единичному базису целевая функция, как и базисные переменные, будет выражена через свободные переменные. Аналогичным приёмом я пользовался, когда решали задачи графическим методом с числом переменных более двух.