Симплекс-метод решения задачи линейного программирования
. В новой таблице прежде всего выписываем слева новые базисные неизвестные.
. Далее в новой таблице заполняем и выделяем ключевую строку. Она получается делением всех элементов соответствующей строки исходной таблицы на ключевой элемент.
. Остальные элементы новой таблицы подсчитываем по правилу двух перпендикуляров: каждый элемент новой таблицы, за исключением элементов ключевой строки, равен разности между соответствующим элементом исходной таблицы и произведением элементов, оказавшихся в основаниях перпендикуляров, опущенных из "старого" элемента на ключевой столбец и ключевую строку.
Заметим, что при выборе ключевого столбца не обязательно среди отрицательных элементов индексной строки выбирать наибольший по абсолютной величине, можно брать любой из них. Это связано с тем, что существуют лишь вероятностные оценки минимального количества симплексных таблиц, необходимых для решения задачи. Заметим также, что ключевой элемент всегда положителен.
Симплекс-метод относится к числу конечных и монотонных методов, а именно: через конечное число шагов либо мы получим оптимальный план, либо убедимся в неограниченности целевой функции на множестве планов задачи, причем последовательность симплексных таблиц строится так, что значения целевой функции монотонно возрастают (в задаче максимизации) или монотонно убывают (в задаче минимизации).
Пример 1. Решить симплекс-методом следующую задачу ЛП:
Задача - основная, но не каноническая, так как система уравнений не является канонической (свободный член первого уравнения отрицателен и ни в одном из уравнений нет базисного неизвестного).
Применим метод искусственного базиса. С этой целью составим вспомогательную задачу, так чтобы система уравнений оказалась канонической. Умножив обе части первого уравнения на -1, и прибавив к левым частям обоих уравнений искусственные неизвестные z1 и z2, получим так называемую расширенную систему. Составим вспомогательную функцию, равную сумме искусственных неизвестных, и поставим своей целью минимизировать вспомогательную функцию на множестве планов расширенной системы.
Первый этап. Вспомогательная задача.
Вспомогательная задача является "почти канонической", поэтому решим ее при помощи стандартного алгоритма симплекс-метода. В результате получим последовательность симплексных таблиц вида
Все элементы индексной строки табл. 3 неположительны, следовательно, вспомогательная задача решена и получен ее оптимальный план, причем минимальное значение вспомогательной функции jmin=0. Отсюда следует, что существует каноническая система, равносильная исходной системе, которая содержится в завершающей симплексной таблице вспомогательной задачи. Выписав ее из табл. 3, и присоединив к ней заданную целевую функцию, получим задачу, равносильную исходной основной задаче, которая, как и вспомогательная задача, будет "почти канонической".
Второй этап. Задача, равносильная основной.
Решим эту задачу симплекс-методом.