1.6.2. Признак отсутствия допустимых планов
Наличие в ЗЛП псевдоплана не гарантирует решение данной задачи. Подтверждением этого факта служит следующая теорема.
Теорема 1.11. Признак неразрешимости злп в двойственном симплекс-методе.
Пусть в ЗЛП (1.67) имеется псевдоплан х* = (x1*, …, xr*, …, xn*) такой, что r-я координата меньше нуля, а все элементы r-й строки симплексной таблицы неотрицательны, тогда ЗЛП неразрешима. Другими словами, область допустимых планов D есть пустое множество.
В более формализованной форме теорема может быть сформулирована следующим образом: Если существует псевдоплан х* = (x1*,…, xr*,…, xn*) такой, что xr * < 0, а элементы аrj 0, j =1, n , то множество D = .
П р и м е р 1.17. Решить следующую злп:
C(х) = 5x1 + x2 min
x1 – x2 4
–x1 + x2 6
xj 0; j = 1,2
Выполнив эквивалентные преобразования (каноническая форма и еди-ничный базис), получаем:
C1(х) = –5x1 – x2 max
–x1 + x2 + x3 = - 4
x1 – x2 + x4 = - 6
xj 0; j = 1,4
Составим симплексную таблицу (табл. 1.11), из которой видно, что базисным планом задачи является вектор х =(0; 0; -4; -6). Так как в строке оценок отрицательных чисел нет, а в столбце А0 есть отрицательные числа, то имеем псевдоплан и можем применить алгоритм двойственного симплекс-метода.
На второй итерации вектор A3 нужно вывести из базиса. При этом отрицательных элементов в соответствующей строке симплексной таблицы нет. Из только что доказанной теоремы 1.11 следует вывод, что задача не разрешима. Область допустимых планов есть пустое множество (D = ).
Это легко можно проиллюстрировать графически (рис.1.14). Прямые линии, являющиеся границами полуплоскостей, соответствующих неравенствам, параллельны. Поэтому данные полуплоскости не пересекаются. Таким образом, область допустимых планов отсутствует, D = .
Таблица 1.11.
Решение примера 1.17
|
|
|
-5 |
-1 |
0 |
0 |
с |
Базис |
A0 = b |
A1 |
A2 |
A3 |
A4 |
0 |
A3 |
- 4 |
- 1 |
1 |
1 |
0 |
0 |
A4 |
- 6 |
1 |
-1 |
0 |
1 |
|
C1(х)/j |
0 |
5 |
1 |
0 |
0 |
0 |
A3 |
- 10 |
0 |
0 |
1 |
1 |
- 1 |
A2 |
6 |
-1 |
1 |
0 |
- 1 |
|
C1(х)/j |
- 6 |
6 |
0 |
0 |
1 |
х2
6 --
4
--
D
=
2 --
1
1
1
1
1
х1
-6 -4 -2 0 2 4
-2
--
-4 --
Рис.1.14. Графическая иллюстрация отсутствия
множества допустимых планов в ЗЛП
1.6.3. Решение ЗЛП с дополнительным активным ограничением
Допустим,
что ЗЛП вида (1.67) имеет оптимальный план
.
При этом известен носитель оптимального
плана
.
Последней итерации симплексной таблицы
соответствует система уравнений (1.78).
(1.78)
Координаты оптимального плана х* соответственно равны:
.
Добавим к исходной ЗЛП (1.67) дополнительное активное или, как еще говорят, существенное ограничение вида:
(1.79)
Ограничение (1.79) не выполняется для плана х*. Введем в неравенство (1.79) дополнительную переменную xn+1 0.
(1.80)
Сгруппируем в уравнении (1.80) базисные и небазисные переменные:
(1.81)
Выразим xk из (1.78) и подставим в уравнение (1.81):
(1.82)
Теперь выделим и сгруппируем свободные переменные, а постоянные члены перенесем в правую часть уравнения (1.82):
(1.83)
Уравнение
(1.83) представляет собой активное
ограничение (1.79), записанное в приведенной
форме. Обозначим
,
тогда дополнительная переменная xn+1
= xm+1,0
.
Запишем уравнение (1.83) в (m+1)-ю строку последней итерации симплексной таблицы. При этом появляется новый единичный базисный вектор An+1, у которого все координаты равны нулю, кроме координаты с номером (m +1), где стоит единица.
Итак,
за счет дополнительного ограничения
(1.83) получили новую ЗЛП, в которой имеется
псевдоплан
.
Действительно, n
новых
двойственных оценок равны прежним
двойственным оценкам, а оценка n+1
= 0, как
оценка базисного вектора An+1.
Кроме того, xm+1,0
0, так
как
в силу предположения, что дополнительное
ограничение активное.
Таким образом, имея псевдоплан, можно продолжать решение ЗЛП двойственным симплекс-методом.
П р и м е р 1.19. Предприятие изготавливает для постоянного заказчика изделие А основной номенклатуры и изделие В второстепенной номенклатуры. Издержки на производство одного изделия А равны 5 ден. ед., а изделия В – 1 ден. ед. Заказчик требует поставлять изделия А как минимум на четыре единицы больше, чем изделия В. Кроме того, производство одного изделия А дает единицу токсичных отходов, а изделия В – две единицы отходов. Согласно экологическим требованиям общее количество токсичных отходов не должно превышать 12 единиц. В связи с тем, что предприятие испытывает финансовые затруднения, необходимо так организовать производство, чтобы минимизировать издержки.
Для построения ЭММ введем переменные х1 – количество производимых изделий вида А, а х2 – количество производимых изделий вида В. Тогда ЭММ данной задачи будет выглядеть следующим образом:
х1 + 2х2 12 (l1)
х1 – х2 4 (l2)
х1, х2 0,
где (l2) и (l2) обозначения прямых линий, ограничивающих соответствующие полуплоскости (они потребуются для геометрической иллюстрации решения данной задачи).
Преобразовав построенную модель к каноническому виду
х1 + 2х2 + х3 = 12
–х1 + х2 + х4 = –4
х1, х2 , х3 , х4 0,
получим псевдоплан (табл. 1.13).
Таблица 1.13.
Решение производственной задачи (пример 1.19)
-
-5
-1
0
0
0
с
Базис
А0 = b
A1
A2
A3
A4
A5
0
0
A3
A4
C1(x)/j
12
-4
0
1
-1
5
2
1
1
1
0
0
0
1
0
0
-5
A3
A1
C1(x)/j
8
4
-20
0
1
0
3
-1
6
1
0
0
1
-1
5
0-5
0
A3
A1
A5
C1(x)/j
8
4
-2
-20
0
1
0
0
3
-1
-1
6
1
0
0
0
1
-1
-1
5
0
0
1
0
0
-5
0
A3
A1
A4
C1(x)/j
6
6
2
-30
0
1
0
0
2
0
1
1
1
0
0
0
0
0
1
0
1
-1
-1
5
На второй итерации получен оптимальный план х* = (4; 0; 8; 0), т.е. предприятие должно выпускать только 4 единицы изделия А. При этом издержки составят С(х*) = 20 ден.ед.
Однако обстоятельства изменились, и заказчик потребовал изготовить не менее 6 штук изделий А. Появляется новое активное ограничение х1 6 (обозначим соответствующую прямую l3). Далее, введя в активное ограничение –х1 – 6 дополнительную переменную х5 0, получим следующую систему ограничений:
3х2
+ х3
+ х4
= 8
х1 – х2 – х4 = 4
–х1 + х5 = – 6
Выразим х1 из второго уравнения и подставим в третье уравнение
х1 = 4 + х2 + х4 ,
– 4 – х2 – х4 + х5 = – 6 ,
– х2 – х4 + х5 = – 2.
Запишем последнее уравнение в дополнительную строку симплексной таблицы (см. третья итерация, табл. 1.13).
Применяя алгоритм двойственного симплекс-метода, получаем оптимальный план х1* = (6; 0; 6; 2; 0), С(х1*) = 30 ден. ед. Геометрическая иллюстрация решения данной задачи показана на рис. 1.15.
х2
6
-
-
-
(l2)
-
-
- х* х1* х1
1 1 1
1 1 1 1 1 1 *1 1 * 1 1 1 1 1
1
-5
0 - 6 12
С(х) - (l3) (l1)
-
-4 -
Рис. 1.15. Иллюстрация решения задачи (пример 1.19)