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

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

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

Пример решения ЗЛП симплекс-методом. Рассмотрим на конкретном примере процесс решения КЗЛП табличным симплекс-методом. Пусть дана каноническая задача ЛП:

Как видно, столбцы матрицы с номерами {5, 2, 3} являются линейно независимыми. И можно получить разложение по данным столбцам вектора ограничений с положительными коэффициентами. Последнее означает, что столбцы {5, 2, 3} образуют допустимый базис, с которого можно начать решение задачи. Из столбцов, входящих в базис, с учетом нулевых элементов формируется матрица Δ(β(1)) и обратная по отношению к ней Δ-1(1)):

Используя их, по формуле (1.26) получаем

-84 0 0 -88 0
1/3 0 0 1/3 1
= 2 1 0 3 0 ;
-2/3 0 1 -4/3 0


Используя полученные значения A(1)) и b(1)), заполняем симплекс-таблицу T(1), соответствующую первой итерации (q=1).

Поскольку строка оценок a0(1)) в первом и четвертом столбцах содержит отрицательные элементы (a0,1(1)) = -84, a0,4(1)) = -88), план х(1)) = (0,14,17/3,0,4) не является оптимальным, и значение целевой функции f(x(1))) = -226 может быть улучшено. Следуя рекомендации п.1˝ алгоритма симплекс-метода, полагаем номер вводимого в очередной базис столбца l = 4 (т.к. |-88| > |-84|). Рассматриваем ведущий столбец (выделен пунктирной рамкой)

Он содержит два положительных элемента. Применяя рекомендацию п. 2" алгоритма, получаем λ1= 4/(1/3) =12, λ2=14/3, и, стало быть r = 2. Следовательно, столбец с номером N2(1)) = 2 должен быть выведен из базиса. Таким образом, получаем очередной допустимый базис задачи N(2)) = {5, 4, 3}. Элемент a2,3(1)) является ведущим (обведен кружком). Применив формулы (1.28)-(1.31), переходим к симплекс-таблице, соответствующей второй итерации T(2), и полагаем индекс текущей итерации q = 2.

В ходе выполнения второй итерации опять-таки определяются вводимый столбец а1, выводимый а4 и ведущий элемент a2,1(2)). Перейдя к итерации q = 3, имеем таблицу T(3).

Как видно из T(3), строка оценок содержит только неотрицательные значения, поэтому достигнутый базис N(3)) = {5, 1, 3} является оптимальным. В итоге мы получаем, что вектор х* = (7, 0, 31/3, 0, 5/3) является оптимальным планом (точкой максимума) задачи (1.34)-(1.35), максимальное значение целевой функции равно f* =f(х*)=362, а решение КЗЛП имеет вид ((7, 0, 31/3, 0, 5/3); 362).