Добро пожаловать на наш портал !

Методы компьютерного моделирования экономических процессов

Пример решения ЗЛП двойственным симплекс-методом

Пример решения ЗЛП двойственным симплекс-методом. Рассмотрим на конкретном, примере процесс решения КЗЛП двойственным симплекс-методом. Для этого, опять-таки, вернемся к задаче (1.34)-(1.35), решенной в п. 1.4.3 и п. 1.5.2. Предположим, что произошли изменения в векторе ограничений b в результате которых


Содержание исходной симплекс-таблицы T(1) (за исключением столбца b(1))) будет идентично содержанию таблицы, получающейся на последнем шаге алгоритма, рассмотренного в п. 1.4.3. Для вычисления значений b(1)) в данном случае можно воспользоваться обратной матрицей, полученной на последней итерации в п. 1.5.2:

В результате имеем:

Как видно из таблицы Т(1), в столбце b(1)) содержатся отрицательные элементы b1(1)) = - 1/3<0), то есть базис β(1) ={5, 1, 3} не является оптимальным, но в то же время легко убедиться, что он обладает свойствами сопряженного базиса. Отрицательный элемент в b(1)) является единственным, поэтому номер столбца, выводимого из базиса, определяется однозначно — r = 1 и N1(1))=5. Далее рассматриваем строку a1(1)) = (0, -1/6, 0, -1/6, 1). В ней имеются отрицательные элементы. Вычисляем λ2 =42:(-(-1/6))=252, λ4 =38:(-(-1/6))=228. λ2> λ4, следовательно, номер столбца, вводимого в базис — l = 4. Осуществляем преобразование и получаем симплекс-таблицу T(2).

Поскольку b(2)) >0, то достигнутый базис N(2)) = {4,1,3} является оптимальным. Из Т(2) можно выписать оптимальный план х* = (6, 0, 32/3, 2, 0) и соответствующее ему значение целевой функции f(x*)= 444.