5.3 Лексикографический двойственный симплекс-метод (ЬИ-метод)

Описание метода начнем с симплекс-таблицы, форма которой в данном случае будет отличаться от использовавшейся ранее

 (см. раздел 2).

Пусть для рассматриваемого базиса В множество номеров не­базисных переменных есть Б1 = {т(1),..., т(/)}, / = га —то; множе­ство номеров базисных переменных — 5* = {1,..., га} \ 5". Пред­ставление целевой функции (обозначаемой посредством жо) и ба­зисных переменных через небазисные (по существу, речь идет о системе (2.1"), (2.2") из раздела 2) будем записывать следующим образом:

I

х% = гг0 + Е г1](-хТ(3))1   ieSU{0}. (5.12)

3 = 1

К этим уравнениям добавим также тождественные соотношения вида Х{ = Х{ для небазисных переменных

жг = (-1)(-жг),  1^8'. (5.13)

Симплекс-таблица будет представлять собой матрицу коэф­фициентов правых частей уравнений системы (5.12)—(5.13). В этой таблице количество строк равно га + 1, по одной строке для каждой переменной, включая и целевую функцию жо- Число столбцов равно / + 1, из которых 0-й содержит свободные члены уравнений, а остальные находятся во взаимно однозначном со­ответствии с небазисными переменными, так что ]-шу столбцу соответствует переменная хт^ (со знаком минус). Например, в случае т(]) = то + ]\ ]' = 1,..., /, симплекс-таблица имеет вид

 

1

Хт-\-1

Хп

ж0

^00

%01

■ г0!

Х{

 

%г\

■ 2ц

т + 1

0

-1

. 0

Хп

0

0

. -1

Посредством (33- обозначим ]-ъ столбец симплекс-таблицы, т.е. Рз — • • • > %п]) 1 3 — 0,1,...,/.

Тогда система уравнений (5.12),(5.13) может быть представлена одним векторным уравнением

I

(ж0, жь ..., хп)т = /30 + ^Рз(-Хт(з))- (5-14)

3 = 1

Если гГ8 ф 0, г 6 Б, в > 1, то может быть выполнено элемен­тарное преобразование базиса, при котором базисная переменная хг и небазисная переменная хт^ поменяются ролями. При этом правая часть уравнения (5.14) должна быть преобразована и вы­ражена через новый набор небазисных переменных. Для этого выразим переменную хт^ из г-го уравнения системы

'т(е) —        (^гО ~Ь ^ ] ^гз (    Хт(з)) %г) Зф$

и исключим ее из правой части в (5.14). После подстановки и приведения подобных получаем

(ж0, х1}..., хп)т = (р0 - — Ра) + - Щ*){-хЛ])) + (— Ра)(-хг).

Зф$

Таким образом, элементарное преобразование базиса, которо­му соответствует замена небазисной переменной хт^ на жг, т.е. г(в) := г, (или, что то же самое, замена базисной переменной жг на жт(5)) влечет преобразование симплекс-таблицы, описываемое схемой:

Рз <— Рз - — Р*-> 3 Ф

л 2x5 (5.15) Ра   <— (—

Симплекс-таблицу будем называть нормальной, если каждый ее столбец /3^-, ]' = 1,..., / лексикографически больше нуля.