 |
 |
 |
 |
|
 |
 |
21
Отдельно следует обсудить тот случай, когда столбец a
l
(?
(q)
), претендующий на ввод в базис, не
содержит положительных компонентов
a
l
(?
(q)
)
? 0).
Это означает, что целевая функция в задаче не
ограничена на множестве допустимых значений, т. е. может достигать сколь угодно большого значения.
Последнее, очевидно, означает завершение процесса вычислений ввиду отсутствия оптимального
плана. Геометрически ситуация, когда a
l
(?
(q)
)
? 0
, соответствует тому, что ось ординат оказывается
внутри конуса, натянутого на систему расширенных столбцов а
j
, а значит, прямая, проведенная через
конец вектора b параллельно оси аппликат, однажды «войдя» в этот конус, более никогда из него «не
выходит».
Вообще говоря, после перехода от базиса ?
(q)
к базису ?
(q+1)
мы можем заново сформировать матрицы
? (?
(q+1)
), ?
-1
(?
(q+1)
) и, вычислив А(?
(q+1)
) = ?
-1
(?
(q+1)
)A, делать выводы о его оптимальности. Однако,
учитывая, что ?
(q+1)
отличается от ?
(q)
всего лишь одним столбцом, с точки зрения техники вычислений
представляется рациональным непосредственно переходить от A (?
(q)
) и b (?
(q)
) к A (?
(q+1)
) и b (?
(q+1)
) .
Дело в том, что у матриц типа A (?
(q)
) столбцы, соответствующие базисным векторам, состоят из нулей,
за исключением одного элемента, равного единице. Позиция этого ненулевого элемента определяется
порядковым номером базисного столбца в N(?
(q)
). Поэтому для получения матрицы A (?
(q+1)
) достаточно
с помощью линейных операций над строками матрицы A (?
(q)
) привести ее столбец, соответствующий
вводимому в базис вектору, к «базисному» виду.
Для это применяется преобразование Жордана—Гаусса
(так называемый метод полного
исключения). В данном случае оно состоит в том, что мы должны «заработать» единицу на месте
элемента a
r,l
(?
(q)
) (он обычно называется ведущим)* и нули на месте остальных элементов столбца
a
l
(?
(q)
). Первое достигается посредством деления r-й строки на ведущий элемент, второе — путем
прибавления вновь полученной r-й строки, умноженной на подходящий коэффициент, к остальным
строкам матрицы A(?
(q)
).
* Напомним, что l — номер столбца, вводимого в базис, а r
— номер строки в симплекс-таблице, определяющей номер
столбца, выводимого из базиса.
Формально результат выполнения данного преобразования над элементами A(?
(q)
) и b(?
(q)
) может
быть выражен в следующем виде
Следует особо отметить смысл элементов вектора b(?
(q)
). Его нулевой компонент b
0
(?
(q)
) в
соответствии с построением содержит значение целевой функции, достигаемое ею на текущем плане
а остальные элементы — ненулевые компоненты этого плана: