 |
 |
 |
 |
|
 |
 |
24
Поскольку строка оценок a
0
(?
(1)
)
в первом и четвертом столбцах содержит отрицательные элементы
(a
0,1
(?
(1)
) = -84, a
0,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}.
Элемент a
2,3
(?
(1)
) является ведущим (обведен кружком). Применив формулы (1.28)-(1.31), переходим к
симплекс-таблице, соответствующей второй итерации T
(2)
, и полагаем индекс текущей итерации q = 2.
В ходе выполнения второй итерации опять-таки определяются вводимый столбец а¹, выводимый а
4
и
ведущий элемент a
2,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).
1.4.4. Сходимость симплекс-метода. Вырожденность в задачах ЛП. Важнейшим свойством
любого вычислительного, алгоритма является сходимость, т. е. возможность получения в ходе его
применения искомых результатов (с заданной точностью) за конечное число шагов (итераций).
Легко заметить, что проблемы со сходимостью симплекс-метода потенциально могут возникнуть на
этапе выбора значения r (п. 2") в случае, когда одинаковые минимальные значения отношения
будут достигнуты для нескольких строк таблицы Т
(q)
одновременно. Тогда на следующей итерации
столбец b(?
(q+1)
) будет содержать нулевые элементы. Напомним, что
допустимый базисный план канонической задачи ЛП, соответствующий базису
?
(q)
, называется
вырожденным, если некоторые его базисные компоненты равны нулю, т. е. вектор b(?
(q)
)