 |
 |
 |
 |
|
 |
 |
26
на множестве, определяемом ограничениями
строится вспомогательная задача
Как видно из (1.36)-(1.39), задача (
D
~
,
f
~
) отличается от задачи (D,
f) матрицей, получаемой в
результате добавления к
исходной матрице А единичной матрицы, которой соответствуют
дополнительные (фиктивные) переменные х
n+1
,...,х
n+m
. Данным переменным (собственно говоря, их и
называют невязками) в целевой функции
f
~
отвечают коэффициенты (-1), а переменным х1,...,х
n
,
которые являются общими для обеих задач, — нулевые коэффициенты. Существенной особенностью
(
D
~
,
f
~
) является наличие в ней очевидного исходного базиса, образуемого добавленными столбцами, и
соответствующего плана с базисными компонентами х
n+i
= b
i
? 0,
i
1: m. В силу структуры целевой
функции I? в процесс поиска ее максимума процедурой симплекс-метода фиктивные переменные
(невязки) х
n+i
должны минимизироваться желательно до нуля, что может быть достигнуто за счет
последовательного перевода их в небазисные компоненты плана. Если в оптимальном плане ??,
полученном в результате решения вспомогательной задачи, последние m компонент (т. е. невязки)
равны нулю, то его начальные n компонент удовлетворяют системе ограничений, определяющих
область D, и
x
~
легко (простым отбрасыванием невязок) может быть преобразован в стартовый до-
пустимый план основной задачи (D, f). При этом все строки симплекс-таблицы, полученной на
последней итерации вспомогательной задачи (за исключением нулевой), могут быть перенесены в
первую таблицу основной задачи. Элементы же нулевой строки для вновь формируемой симплекс-
таблицы вычисляются по формулам:
где
?
(*)
— базис, полученный на последней итерации вспомогательной задачи.
В случае, когда оптимальный план вспомогательной задачи ?? все же содержит не равные нулю
фиктивные компоненты (т. е.
f
~
(
x
~
)<0), мы приходим к заключению об отсутствии допустимых
планов у исходной задачи (D, f), т. е. D = O.
1.5. МОДИФИЦИРОВАННЫЙ СИМПЛЕКС-МЕТОД
1.5.1. Вычислительная схема, основанная на преобразовании обратных матриц. Анализируя
вычислительную процедуру симплекс-метода с позиций оценки трудоемкости, нетрудно заметить, что
наиболее критичным в этом плане является этап пересчета значений А и b при переходе от одного
базисного плана к другому (п. 3 алгоритма). Однако в том случае, когда число ограничений задачи m
явно меньше количества переменных n, можно добиться существенной «экономии», выполняя на