Двухэтапный метод

Исторически первым появился М-метод, но он имеет существенный недостаток: возможность появления ошибок в вычислениях, обусловленных очень боль­шой величиной коэффициента М.

Например: М=100000. Тогда коэффициенты в z-уравнении примера 2: (-4+700000) и (-1+400000). Из-за большой величины М вклад исходных ко­эффициентов (4 и 1) оказывается ничтожным. Вследствие ошибок округления, свойственных всем ЭВМ, процесс вычислений может стать нечувствительным к значению исходных коэф­фициентов при x1 и x2. При этом возникает опасность того, что эти переменные будут ин­терпретироваться как переменные, фигурирующие в целевой функции с нулевыми коэффи­циен­тами.

Двухэтапный метод позволяет избежать этих затруднений. При использовании этого метода искусственные переменные вводятся таким же образом, как и в М-методе, однако коэффициент М при этом не фигурирует, что достигается расчленением задачи на два этапа.

Введение искусственных переменных может интерпретироваться как введение в модель полезных для нас изменений (невязок). При этом полупространство, которое соответствует ограничению “³”, “поворачивается” в противоположном направлении, а гиперплоскость превращается в полупространство. Полученная модель отличается от исходной в той мере, в какой искусственные переменные отличаются от ноля, поэтому на первом этапе выполняется минимизация этих отличий от исходной модели. При этом сумма искусственных переменных рассматривается как сумма невязок, которую нужно минимизировать.

Пусть имеем ЗЛП:

 
 


(26)

 

Сформулируем такую вспомагательную задачу:

(27)

 

Двухэтапный метод базируется на следующих утверждениях:

1. Если исходная задача (26) имеет допустимое решение, то в оптимальном решении задачи (27) компоненты вектора R равны нолю.

 

2. Если в оптимальном решении задачи (27) некоторые искусственные переменные больше чем ноль, то исходная задача (26) не имеет решений.

 

Этап 1.

1. Вводятся искусственные переменные, необходимые для получения начальной (стартовой) точки.

2. Записывается новая целевая функция, предусматривающая минимизацию суммы ис­кусственных переменных при исходных ограничениях, видоизмененных за счет введения ис­кусственных переменных.

3. Решается задача линейного программирования.

Если минимальное значение новой целевой функции равно нулю (то есть все искусст­венные переменные имеют в оптимуме нулевые значения), исходная задача имеет допустимое решение. Переход к этапу 2.

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

Если минимальное значение новой целевой функции не равно нулю, то исходная задача не имеет допустимых решений, закончить вычисления, иначе, исходная задача имеет допустимое решение. Возможны следующее случаи:

а) Если все искусственные переменные есть небазисными, то перейти к этапу 2. В текущей точке избыточных ограничений нет.

б) Если среди искусственных переменных есть базисная, то это означает, что в текущей точке есть избыточное ограничение. Если при этом в строке і, что соответствует искусственной переменной, есть коэффициент aij¹0, где j- столбец небазисной неискусственной переменной (), то мы можем вывести из базиса эту искусственную переменную и ввести в него переменную, которой соответствует индекс j.

б.1) Если такой процесс выводит из базиса все искусственные переменные, то получаем вырожденное допустимое решение исходной задачи (в текущей точке есть избыточные ограничения, и при этом среди них нет линейно- зависимых). Перейти к этапу 2.

б.2) Если такой процесс не выведет все искусственные переменные из базиса, тогда каждая строка и соответственная искусственная переменная, в которой aij=0 для всех неискусственных переменных (), соответствует избыточному ограничению, которое является линейной комбинацией одного или нескольких других ограничений. Удаляем эти ограничения и переходим к этапу 2.

 

Этап 2.

Оптимальное базисное решение, полученное на этапе 1, используется в качестве началь­ного решения исходной задачи.

 

 

Реализацию этого метода проиллюстрируем на ЗЛП из примера 11.1.

Этап 1.

Так как необходимо ввести искусственные переменные R1 и R2 в первое и второе ог­раничения соответственно, этап 1 сводится к решению задачи (при этом c -строкой поступаем так же, как и с остальными ограничениями):

Так как R1 и R2 фигурируют в начальном решении, следует подставить в целевую функ­цию их выражения, полученные из соответствующих ограничений

 


Итерация 0 (начало вычислений).

Таблица 15

БП x1 x2 x3 R1 R2 x4 Решение
r -1
z -4 -1
R1
R2 -1
x4


Согласно условию оптимальности переменная x1 вводится в базис. Согласно условию допустимости переменная R1 выводится из базиса.

Итерация 1.

Таблица 16

БП x1 x2 x3 R1 R2 x4 Решение
r 5/3 -1 -7/3
z 1/3 0 4/3 0
x1 1/3 1/3
R2 5/3 -1 -4/3
x4 5/3 -1/3

Согласно условию оптимальности переменная x2 вводится в базис. Согласно условию допустимости переменная R2 выводится из базиса.

Итерация 2.

Таблица 17

БП x1 x2 x3 R1 R2 x4 Решение
r -1 -1
z 1/5 8/5 -1/5 18/5
x1 1/5 3/5 -1/5 3/5
x2 -3/5 -4/5 3/5 6/5
x4 -1

 

Поскольку оптимальное значение функции r равно нулю, начальная задача имеет допустимое решение и можна перейти к этапу 2.

 

Этап 2.

В начале этого этапа исключаются искусственные переменные (удаляются соответствующие столбцы последней таблицы этапа 1) и -строка. Получаем:

Таблица 18

БП x1 x2 x3 x4 Решение
z 1/5 18/5
x1 1/5 3/5
x2 -3/5 6/5
x4

 

. Согласно теории симплекс метода строка z содержит компоненты вектора относительных оценок небазисных переменных соответствующего ДБР. Полученная таблица совпадает с таблицей 10. Дальнейшие результаты вычислений совпадают с результатами вычислений М-метода.

 

Отметим, что элементы -строки могут быть получены и другим способом. Для этого из последней симплекс-таблицы этапа 1 (в нашем примере - из таблицы 17) базисные переменные (x1, x2, x4) должны быть выражены через небазисные (x3):

Потом их выражения подставляются в начальную целевую функцию:

Заполняется симплекс-таблица, которая соответствует ДБР, найденному на этапе 1.

 

Пример 11.2.

Пусть имеем ЗЛП:

min z=3x1+x2 (11.1)

2x1+x2 ³2 (11.2)

x1+2x2 ³2 (11.3)

x1,x2 ³0 (11.4)

Привидем задачу к канонической форме:

min z=3x1+ x2 +0s1 +0s2 (11.5)

2x1+ x2 -1s1 =2 (11.6)

x1+2x2 -1s2 =2 (11.7)

x1,x2 ,s1,s2³0 (11.8)

               
 
x2
 
   
x1
   
(11.3)
     
(11.2)
 
 


Рис 11. 1.

 

Этап 1.

1. Введем искусственные переменные в ограничения типа “³” и “=”. В нашей задаче это ограничения (11.2) и (11.3). Назовем искусственные переменные R1 и R2 соответственно. Тогда модели (11.5)-(11.8) будет соответствовать такая задача:

min z=3x1+ x2 +0s1 +0s2 +0R1 +0R2 (11.9)

2x1+ x2 -1s1 +R1 =2 (11.10)

x1+2x2 -1s2 +R2 =2 (11.11)

x1,x2 ,s1,s2³0 (11.12)

2. На первом этапе двухэтапного симплекс-метода необходимо минимизировать отличия от исходной математической модели. Сформулируем вспомогательную задачу:

Новая целевая функция в общем случае определяется выражением

r = ,

где – количество искуственных переменных.

В нашем случае : r = R1 + R2 .

Выразим R1 и R2 из уравнений (11.10), (11.11) соответственно:

R1 = 2 - 2x1- x2 +1s1

R2= 2 - x1 -2x2 +1s2

После подстановки получим такое выражение длс целевой функции:

r = R1 + R2 =4 - 3x1 -3x2 +1s1 +1s2

Перепишем целевую функцию в виде:

r + 3x1 +3x2 -1s1 -1s2 = 4

 

3. Построим начальную таблицу двухэтапного симплекс-метода.

Строку r заполняем в соответствии с выражением новой целевой функцией , которое было найдено на предыдущем шаге.

Строка z заполняется исходя из целевой функции (11.9) исходной задачи :

z -3x1 - x2 - 0s1 - 0s2 - 0R1 - 0R2=0.

В качестве базисных переменных выбираем те, которые в математической модели встречаются с коэффициентом 1 в одном уравнении, и 0 – в остальных. В нашем случае это будут переменные R1 и R2 .

 

Базисные переменные X1 x2 s1 s2 R1 R2 Решение  
r(min) -1 -1  
z -3 -1  
R1 -1
R2 2 -1

 

 

 

 

 


Теперь решим задачу табличным симплекс-методом, принимая строку r – строкой целевой функции, а над строкой z будем выполнять те же преобразования, что и над обычными ограничениями, это позволит нам при окончании этапа 1 получить полное начальное ДБР для этапа 2.

Согласно условию оптимальности в базис можно ввести как переменную так и , Введём в базис переменную , тогда согласно условию допустимости из базиса будет выведена переменная R2.. После выполнения операции замещения получим таблицу:

 

Базисные переменные x1 ↓ x2 s1 s2 R1 R2 Решение  
r(min) 3/2 -1 1/2 -3/2  
z -5/2 -1/2 ½  
←R1 3/2 -1 1/2 -1/2 2/3
x2 1/2 -1/2 1/2

s

Поскольку не все коэффициенты целевой функции r отрицательны, то продолжаем выполнять итерации симплекс-метода. Согласно условию оптимальности вводим в базис переменную x1 и, согласно условию допустимости, из базиса выводим переменную R1. Получаем таблицу:

 

Базисные переменные x1 x2 s1 s2 R1 R2 Решение
r(min) -1 -1
z -5/3 1/3 5/3 -1/3 8/3
x1 -2/3 1/3 2/3 -1/3 2/3
x2 1/3 -2/3 -1/3 1/3 2/3

 

 

В полученной таблице выполняется условие оптимальности для целевой функции r, то есть, мы получили решение, в котором эта функция достигает минимума. Поскольку оптимальное значение функции r равно нулю, начальная задача имеет допустимое решение и можна перейти к этапу 2. Согласно теории симплекс метода строка z содержит компоненты вектора относительных оценок небазисных переменных соответствующего ДБР. На этом первый этап метода заканчивается, столбцы R1 и R2 а также строка r удаляются из текущей таблицы и продолжаем решать задачу табличным симплекс-методом, для целевой функции z.

 

Этап 2

После выполнения первого этапа симплекс-метода получаем таблицу:

 

Базисные переменные x1 x2 s1 s2 ↓ Решение  
z(min) -5/3 1/3 8/3  
←x1 -2/3 1/3 2/3
x2 1/3 -2/3 2/3  

 

 

Согласно условию оптимальности вводим в базис переменную s2 и согласно условию допустимости выводим из базиса переменную x1. Получаем таблицу:

 

Базисные переменные x1 x2 s1 s2 Решение
z(min) -1 -1
s2 -2
x2 -1

 

 

Данная таблица - оптимальная, потому что в строке z коэффициенты при небазисных переменных – отрицательные (условие оптимальности для задачи на минимум). Задача решена.

Ответ: x1=0, x2 =2, z = 2