Особые случаи, возникающие при применении двухэтапного мтода
Рассмотрим примеры особых случаев, которые встречаются при решении задачи двухэтапным симплекс-методом.
Пример 12.3 (Вырожденность).
Пусть имеем математическую модель:
min z=x1+x2 (12.1)
-x1 + x2 ³ 1 (12.2)
2x1 + x2 £ 4 (12.3)
x2 ³ 1 (12.4)
x1,x2 ³0 (12.5)
Приведем задачу к канонической форме:
min z= x1 + x2 +0s1 +0s2 +0s3 (12.6)
-x1 + x2 -1s1 = 1 (12.7)
2x1+ x2 +1s2 = 4 (12.8)
x2 -1s3 =1 (12.9)
x1,x2 ,s1,s2,s3³0 (12.10)
|
|
|
|
|
|
|
|
|
|
|
Этап 1
1. Введем искусственные переменные в ограничения типа “³” и “=”. В нашей задаче это ограничения (12.2) и (12.4). Назовем искусственные переменные R1 и R2 соответственно. Тогда модель (12.6)-(12.10) будет иметь такой вид:
min z= x1+ x2 +0s1 +0s2 +0s3 +0R1 +0R2 (12.11)
-x1+ x2 -1s1 +R1 = 1 (12.12)
2x1+ x2 +1s2 = 4 (12.13)
x2 -1s3 +R2 = 1 (12.14)
x1,x2 ,s1,s2,s3³0 (12.15)
2. R1 и R2 выражазим из соответствующих уравнений (12.12), (12.14):
R1 = 1 + x1- x2 +1s1
R2= 1 - x2 +1s3
Получим такую целевую функцию:
r = R1 + R2 = 2 + x1 -2x2 +1s1 +1s3
Перепишем целевую функцию в виде:
r - 1x1 + 2x2 -1s1 -1s3 = 2
3. Построим начальную таблицу двухэтапного симплекс-метода.
| Базисные переменные | x1 |  x2
| s1 | s2 | s3 | R1 | R2 | Решение | |
| r(min) | -1 | -1 | -1 | ||||||
| z | -1 | -1 | |||||||
| R1 | -1 |  1
| -1 | ||||||
| R2 | -1 | ||||||||
| s2 |
Согласно условию оптимальности вводим в базис переменную x2 . На данном этапе невозможно однозначно определить переменную, которою необходимо выводить из базиса согласно условию допустимости.
Мы можем вывести из базиса как переменную R1, так и переменную R2, потому что отношения коэффициентов столбца решений к положительным коэффициентам рабочего столбца одинаковы, и равны единице. Остановим свой выбор на переменной R1. В результате операции замещения получачим таблицу:
| Базисные переменные | x1 | x2 | s1 | s2 | s3 | R1 | R2 | Решение | |
| r(min) | -1 | -2 | |||||||
| z | -2 | -1 | |||||||
| x2 | -1 | -1 | |||||||
| R2 |  1
| -1 | -1 | ||||||
| s2 | -1 |
Одна из базисных переменных (R2) равна нулю. Это означает, что соответствующее решение является вырожденным. С практической точки зрения ситуация полностью объясняется присутствием в модели одного избыточного ограничения. Продолжаем решение задачи по алгоритму симплекс- метода.
Поскольку не все коэффициенты целевой функции отрицательные, то продолжаем выполнять итерации симплекс-метода. Согласно условию оптимальности вводим в базис переменную x1 и, согласно условию допустимости, выводим из базиса переменную R2. Получим таблицу:
| Базисные переменные | x1 | x2 | s1 | s2 | s3 | R1 | R2 | Решение |
| r(min) | -1 | -1 | ||||||
| z | -2 | -1 | ||||||
| x2 | -1 | |||||||
| x1 | -1 | -1 | ||||||
| s2 | -2 | -3 |
Поскольку из базиса выведены все искусственные переменные, то мы получили вырожденное допустимое решение исходной задачи. То есть в текущей точке присутствуют избыточные ограничения, и при этом среди них нет линейно-зависимых.
Итак, если в результате минимизации целевой функции r из базиса выводятся все искусственные переменные, и хотя бы одна из базисных переменных равна 0, то в текущей точке есть избыточное ограничение, и при этом среди них нет линейно-зависимых.
Этап 2
Выполним последнюю итерацию:
| Базисные переменные | x1 | x2 | s1 | s2 | s3 | Решение |
| z(min) |  1
| -2 | ||||
| x2 | -1 | |||||
 x1
|  1
| -1 | ||||
| s2 | -2 |
Согласно условию оптимальности вводим в базис переменную s1 и согласно условию допустимости выводим из базиса переменную x1. Получаем таблицу:
| Базисные переменные | x1 | x2 | s1 | s2 | s3 | Решение |
| z(min) | -1 | -1 | ||||
| x2 | -1 | |||||
| s1 | -1 | |||||
| s2 |
Данная таблица - оптимальная, потому что в строке z коэффициенты при небазисных переменных – отрицательные (условие оптимальности для задачи на минимум). Задача решена.
Ответ: x1=0, x2 =1, z = 1.
Пример 12.4 (Наличие избыточных ограничений, которые есть линейной комбинацией других ограничений.)
Пусть имеем математическую модель:
max z=x1+x2 (12.16)
x1 + x2 = 4 (12.17)
x2 =2 (12.18)
x1 + 2x2 = 6 (12.19)
x1,x2 ³0 (12.20)
|
|
|
|
|
|
Очевидно, что задача уже имеет каноническую форму.
Этап 1
1. Введем искусственные переменные в ограничения типа “³” и “=”. В нашей задачи это ограничения (12.17), (12.18) и (12.19). Назовем искуственные переменные R1 ,R2 и R3 соответственно. Тогда модель (12.16)-(12.20) будет иметь такой вид:
max z= x1+ x2 +0R1 +0R2 +0R3 (12.21)
x1+ x2 +R1 = 4 (12.22)
x2 + R2 = 2 (12.23)
x1+ 2x2 +R3 = 6 (12.24)
x1,x2 ³0 (12.25)
2. Переменные R1 ,R2 и R3 выразим из уравнений (12.22), (12.23), (12.24) соответствено:
R1 = 4 - x1- x2
R2= 2 - x2
R3 = 6 - x1- 2x2
Получаем такую целевую функцию:
r = R1 + R2 + R3 = 12 - 2x1 - 4x2
Перепишем целевую функцию в виде:
r + 2x1 + 4x2 = 12
3. Построим начальную таблицу двухэтапного симплекс-метода.
| Базисные переменные | x1 | x2
| R1 | R2 | R3 | Решение | |
| R(min) | |||||||
| z | -1 | -1 | |||||
| R1 | |||||||
| R2 |  1
| ||||||
| R3 |
Согласно условия оптимальности вводим в базис переменную x2, и, согласно условия допустимости, выводим из базиса переменную R2.
Получим таблицу:
| Базисные переменные |  x1
| x2 | R1 | R2 | R3 | Решение | |
| r(min) | -4 | ||||||
| z | -1 | ||||||
 R1
|  1
| -1 | |||||
| x2 | |||||||
| R3 | -2 |
Поскольку не все коэффициенты целевой функции отрицательные, то продолжаем выполнять итерации симплекс-метода. Согласно условия оптимальности вводим в базис переменную x1, а согласно условия допустимости можно вывести из базиса как переменную R1 так и переменную R3, остановимся на переменной R1. Получим таблицу:
| Базисные переменные | x1 | x2 | R1 | R2 | R3 | Решение | |
| r(min) | -2 | -2 | |||||
| z | |||||||
| x1 | -1 | ||||||
| x2 | |||||||
| R3 | -1 | -1 |
Поскольку не выведены все искусственные переменные из базиса, а минимум функции r равен нолю, и при этом переменная R3 не может быть выведена из базиса, то R3-строка соответствует избыточному ограничению, которое является линейной комбинацией одного или нескольких других ограничений (в нашем случае двух других ограничений). Удаляем это ограничение и переходим к этапу 2.
Итак, если в результате минимизации целевой функции r из базиса не выводятся все искусственные переменные, и хотя бы одна из базисных переменных равна нолю, то в текущей точке есть избыточные ограничения, которые являютсялинейной комбинацией одного или несколькихкох других ограничений.
Этап 2
В результате удаления избыточного ограничения и столбиков, отвечающих исскуственным переменным, получили такую таблицу:
| Базисные переменные | x1 | x2 | Решение | |
| z(max) | ||||
| x1 | ||||
| x2 |
Очевидно, что данная таблица - оптимальна. Задача решена.
Ответ: x1=2, x2 =2, z = 4.