2.8 Выполнение 0-го шага

Для поиска прямо допустимого базиса задачи (2.1)-(2.3) и со­ответствующей прямо допустимой симплекс-таблицы рассмотрим следующую вспомогательную задачу:

т

 

г = 1

 

Переменные ] = га + 1,..., га + то, принято называть ис­кусственными. Без ограничения общности можно считать, что 6г- > О, г = 1,..., т. В таком случае вектор ж 6 цп+т с компо_ нентами х^ = 0, ] = 1,..., га, и хп+{ = 6г-, г = 1,..., т, является базисным допустимым решением задачи, которое соответствует "искусственному"базису В = I (т.е. <т(г) = га + г, г = 1,...,то). Кроме того, на множестве допустимых решений целевая функ­ция £ ограничена снизу нулем. Следовательно, задача разреши­ма и тш£ > 0. Ее решение может быть получено симплекс-методом (с привлечением, при необходимости, "незацикливаю-щихся"вариантов этого метода), используя в качестве начального прямо допустимый искусственный базис ("метод искусственного базиса").

Возможны два случая:

1) тш£ > 0. Это означает, что исходная задача (2.1)-(2.3) не имеет допустимых решений, т.е. ограничения этой задачи несо­вместны и задача неразрешима;

2) тш£ = 0. В таком случае в полученном оптимальном ре­шении все искусственные переменные равны нулю. При этом не исключается, что некоторые из них остаются в числе базисных. Из полученной на заключительной итерации прямо допустимой симплекс-таблицы может быть получена начальная прямо допу­стимая симплекс-таблица для исходной задачи (2.1)-(2.3).

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

Пусть переменная х^ где ] > га, является базисной и соответ­ствует г-й строке симплекс-таблицы. Тогда гг$ = 0, поскольку в базисном решении = гг$ и все искусственные переменные в оптимальном решении равны 0.

Если 2Г]- = 0 для всех ] = 1,..., га, то мы имеем нулевую стро­ку, которую из таблицы можно просто удалить. Наличие такой строки свидетельствует о линейной зависимости уравнений си­стемы (2.2), что делает возможным удаление части уравнений без ущерба для существа дела. Подобная ситуация по необхо­димости будет возникать, если в совместной исходной системе ограничений (2.2)-(2.3) ранг матрицы А меньше числа уравне­ний, гапдА < то.

Остается рассмотреть случай, когда в г-й строке имеются ненулевые элементы. Пусть гГ8 ф 0, 1 < в < п. Выполним элементарное преобразование таблицы с ведущим элементом ггз, т.е. один шаг метода исключения Гаусса-Жордана. Ввиду того, что гго = 0, при этом преобразовании элементы нулевого столбца не изменяются, в частности, сохраняется их неотрицательность. Роль базисной переменной, соответствующей г-й строке, будет те­перь выполнять переменная основной задачи х3, т.е. <т(г) полага­ется равным в, а искусственная переменная х^ из числа базисных ( и вообще из рассмотрения) оказывается исключенной.

Действия, подобные описанным выше, проделаем в отношении всех искусственных переменных, оставшихся базисными. После этого в нулевой строке таблицы записываем коэффициенты целе­вой функции исходной задачи, выраженной только через небазис­ные переменные. На этом процесс построения начальной прямо допустимой симплекс-таблицы для основной задачи (2.1)-(2.3), а вместе с ним и 0-й шаг симплекс-алгоритма, можно считать за­вершенным.

Вышеописанный способ выполнения 0-го шага обычно назы­вают первым этапом симплекс-метода, а метод в целом — двух-этапным симплекс-методом.