2.7 Лексикографический симплекс-метод

Пусть а = (ао, а\,..., ап) £ Ка+1 — вектор-строка. Будем го­ворить, что вектор а лексикографически больше нуля и писать а У 0, если первая отличная от нуля компонента положительна: ар > 0, где р = тш{г | аг- ф 0}. Если а', а" £ Ка+1, то счита­ем, что вектор а' лексикографически больше вектора а", а' У а", если а1 —а" У 0. Тем самым на Ка+1 определено отношение линей­ного порядка, так что в любой конечной совокупности векторов {аг} имеется лексикографически минимальный вектор, обознача­емый 1ехтгп{аг}.

Симплекс-таблицу (2.5) будем называть нормальной, если ее строки 01{,1 = 1,...,то, лексикографически положительны. Оче­видно, нормальная симплекс-таблица является прямо допусти­мой и, наоборот, прямо допустимая симплекс-таблица, в которой столбцы с номерами от 1 до т соответствуют базисным пере­менным, является нормальной. Таким образом, любую прямо до­пустимую симплекс-таблицу можно преобразовать в нормальную путем перенумерации переменных (с соответствующей переста­новкой столбцов).

Отличие лексикографического симплекс-метода от обычного касается 0-го и 3-го шагов (шаги 1-й, 2-й и 4-й остаются без из- менений).

О') Начать с нормальной симплекс-таблицы.

3') Если {г | х{8 > 0} ф 0, то выбрать ведущую строку г:

иначе КОНЕЦ (задача неразрешима).

Чтобы доказать конечность данного варианта симплекс-метода, прежде всего покажем, что преобразование симплекс-таблицы на шаге 4 сохраняет ее нормальность. В самом деле, строка г оста­ется лексикографически положительной, так как она получает­ся путем умножения лексикографически положительного вектора аг на положительное число 1/ггз. Для доказательства лексико­графической положительности остальных строк а[ [г ф г, г > 1) рассмотрим два случая:

а) если 2{в < 0, то а' = аг- — (^ы-)аг У аг У 0;

б) если 2{в > 0, то согласно правила выбора ведущей строки

7~аг ^ 7Г«а'г и' слеД°вательно1 а\ = ^18[{^-)аг - (^)аг] У 0.

Из нормальности симплекс-таблиц следует, что на каждой ите­рации ведущая строка аг лексикографически положительна, что с учетом неравенств      < 0 и гГ8 > 0 влечет

т.е. лексикографическое возрастание нулевой строки. Следова­тельно, в ходе работы алгоритма симплекс-таблицы, а значит и базисы, не повторяются, что гарантирует конечность лексикогра­фического симплекс-метода.

Несмотря на столь важное свойство, на практике данный ал­горитм не применяется из-за относительно более сложного пра­вила выбора ведущей строки. Нам же установленное свойство лексикографического симплекс-метода позволяет теперь вернуть­ся к оставленному без ответа вопросу о существовании прямо и

—аг = 1ехтгп{—о.і \ х{8 > 0}

 

«о — (—)01г У а0

двойственно допустимого базиса.

Утверждение 2.4 Если задача ЛП (2.1)-(2.3) разрешима, то у нее существует прямо и двойственно допустимый базис.

Доказательство. Из разрешимости задачи следует существо­вание допустимых решений, т.е. <5 ф 0) что согласно Следствию (Леммы 1) влечет существование базисного допустимого реше­ния. Симплекс-таблица, соответствующая этому б.д.р., будучи прямо допустимой, в случае необходимости (т.е. если она не явля­ется нормальной) может быть посредством перенумерации пере­менных (с соответствующей перестановкой столбцов) преобразо­вана в нормальную. Начав вычисления с этой симплекс-таблицы, лексикографический симплекс-метод через конечное число итера­ций завершит работу, обнаружив на шаге 1 заключительной ите­рации, что текущая симплекс-таблица является двойственно до­пустимой. В силу разрешимости задачи окончание работы на шаге 3 невозможно. Базис, которому соответствует полученная симплекс-таблица, и будет являться прямо и двойственно допу­стимым.

Теперь остается рассмотреть последний существенный вопрос, касающийся работы симплекс-алгоритма — это нахождение на­чальной прямо допустимой симплекс-таблицы.