8. Двухфазный симплекс-метод.

(1)

Симплекс-метод предполагает наличие начального базисного плана у задачи (1). Значит, его нужно построить. Но существуют задачи, у которых ограничения противоречивы, то есть планов, вообще, нет. Как быть? Прежде всего, можно попытаться выделить в основных ограничениях базисные переменные (то есть входящие лишь в одно уравнение с коэффициентом +1; им будут соответствовать единичные столбцы в матрице ). При этом, однако, надо следить, чтобы вектор оставался неотрицательным. Если удаётся построить в каждом основном ограничении по базисной переменной, то очевиден и базисный план: . В общем случае рекомендуется применить следующий метод.

По параметрам задачи (1) построим вспомогательную задачу: (18-задача 1-й фазы)

– вектор искусственных переменных, – искусственные переменные, а вектор , то есть .

То есть, мы искусственно в каждое основное ограничение прибавили по искусственной неотрицательной переменной и тогда вектор неизвестных в задаче (18) имеет вид: . А основные ограничения можно записать в виде: . Лемма 1. У задачи (18) с помощью симплекс-метода можно всегда построить оптимальный базисный план: ..

Лемма 2. Для того чтобы множество планов задачи (1) было не пусто, необходимо и достаточно, чтобы искусственные компоненты оптимального плана задачи (18) были нулевыми ( ).

Задача (18) называется задачей первой фазы для задачи (1).

Пусть мы решили задачу первой фазы и построили для неё оптимальный базисный план: .

Возможны следующие случаи:

1. , тогда согласно лемме 2 – это и будет для неё ответ;

2. и , то есть искусственные переменные не входят в базис. Тогда очевидно, что вектор будет планом задачи, причём базисным.

Выбирая его в качестве начального базисного плана, приступаем к решению задачи (1). Этот этап называется второй фазой. А вместе первая и вторая фазы образуют двухфазный метод решения канонической задачи.

3. , но в базис входит некоторая искусственная переменная .

Тогда согласно лемме 2 является планом задачи (1), но ещё не базисным, поскольку в базис обязательно должно входить переменных задачи (1).

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

3 а) . Это значит, что в результате симплекс итерации (а при симплекс преобразованиях, на самом деле, при переходе от одного базисного плана к другому, осуществляется преобразование Гаусса основных ограничений ) одно из основных ограничений задачи (1) приняло вид , то есть это ограничение, а точнее, которое является линейной комбинацией остальных. Исключаем его из задачи (вычёркиваем) и тогда размерность уменьшиться на единицу . Если других переменных в базисе нет, то приходим к случаю 2. То есть вектор во множестве будет начальным базисным планом задачи (1) и переходим ко второй фазе.

3 б) , но существует . Тогда совершаем ещё одну симплекс итерацию по элементу и в результате переменная выйдет из базиса, а вместо неё войдет переменная (вместо искусственной переменной в базис войдёт переменная задачи (1)). Сам план не изменится, поскольку Если других искусственных переменных в базисе нет, то снова вектор , будет начальным базисным планом задачи (1). И опять приступаем ко второй фазе.