Зенкевич Н.А. Практикум по исследованию операций
Подождите немного. Документ загружается.
1.3. ПРЯМОЙ СИМПЛЕКС-МЕТОД ДЛЯ ЗАДАЧИ МАКСИМИЗАЦИИ 21
1.3.2 Примеры
Если исходное ограничение записано в виде такого неравенства
x
1
+ 2x
2
≤ 6,
добавляя слабую переменную к левой части ограничения, получаем
x
1
+ 2x
2
+ s
1
= 6, s
1
≥ 0.
Если же ограничения представлены неравенствами такого типа:
3x
1
− 5x
2
+ 2x
3
≥ 5,
вычитая из левой части неравенства слабую переменную
3x
1
− 5x
2
+ 2x
3
− s
2
= 5, s
2
≥ 0.
Если правая часть равенства отрицательна, ее всегда можно сделать неотрицатель-
ной, умножая обе части на (-1).
Если какая-то переменная x
i
не имеет ограничения в знаке, ее можно представить
как разность 2-х неотрицательных переменных
x
i
= x
′
i
− x
′′
i
, x
′
i
, x
′′
i
≥ 0.
1.3.3 Вспомогательные построения симплекс-метода
Рассмотрим каноническую задачу максимизации:
max z = max(c
1
x
1
+ c
2
x
2
+ . . . + c
n
x
n
);
(1.3.1)
a
i1
x
1
+ a
i2
x
2
+ . . . + a
in
x
n
= b
i
, i = 1, m;
x
j
≥ 0, j = 1, n.
(1.3.2)
Предполагается, что система ограничений совместна и неизбыточна, то есть система
линейных уравнений имеет хотя бы одно решение
Составим систему линейных уравнений, соответствующую задаче ЛП. Для этого от-
бросим в задаче (1.3.1), (1.3.2) оператор максимума и условие неотрицательности пере-
менных:
22 Глава 1. ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ
z − (c
1
x
1
+ c
2
x
2
+ . . . + c
n
x
n
) = 0; (1.3.3)
a
i1
x
1
+ a
i2
x
2
+ . . . + a
in
x
n
= b
i
, i = 1, m; (1.3.4)
Приведем полученную систему линейных уравнений к диагональной форме по пере-
менным z, x
1
, . . . , x
m
, рассматривая целевую функцию как линейное ограничение:
z + . . . + c
m+1
x
m+1
+ . . . + c
s
x
s
+ . . . + c
n
x
n
= z
0
x
1
+ . . . + a
1,m+1
x
1,m+1
+ . . . + a
1,s
x
1,s
+ . . . + a
1,n
x
1,n
= b
1
;
. . . . . . . . .
x
r
+ . . . + a
r,m+1
x
r,m+1
+ . . . + a
r,s
x
r,s
+ . . . + a
r,n
x
r,n
= b
r
;
. . . . . . . . .
x
m
+ . . . + a
m,m+1
x
m,m+1
+ . . . + a
m,s
x
m,s
+ . . . + a
m,n
x
m,n
= b
m
.
(1.3.5)
Составим из коэффициентов диагональной формы симплексную таблицу (сокра-
щенно С-Т).
z x
1
. . . x
r
. . . x
m
x
m+1
. . . x
s
. . . x
n
z z
0
1 . . . 0 . . . 0 c
m+1
. . . c
s
. . . c
n
x
1
b
1
0 . . . 1 . . . 0 a
1,m+1
. . . a
1,s
. . . a
1,n
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
x
r
b
r
0 . . . 0 . . . 0 a
r,m+1
. . . a
r,s
. . . a
r,n
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
x
m
b
m
0 . . . 0 . . . 1 a
m,m+1
. . . a
m,s
. . . a
m,n
Условия допустимости и оптимальности симплексной таблицы (С-Т)
Симплексная таблица называется прямо-допустимой, если b
i
≥ 0, i = 1, m. Она
соответствует допустимому базисному решению системы линейных уравнений:
x
j
= b
j
, j =
1, m;
x
j
= 0, j = m + 1, n;
z = z
0
.
Симплексная таблица называется двойственно-допустимой, если c
j
≥ 0, j =
1, n.
Симплексная таблица называется оптимальной, если она одновременно и прямо-
допустима, и двойственно-допустима. Такая таблица соответствует оптимальному реше-
нию задачи ЛП.
1.3. ПРЯМОЙ СИМПЛЕКС-МЕТОД ДЛЯ ЗАДАЧИ МАКСИМИЗАЦИИ 23
1.3.4 Алгоритм прямого симплекс-метода
0. Начать вычисления с прямо-допустимой симплексной табли цы (b
i
≥ 0, i = 1, m).
Вычисления по алгоритму состоят в выполнении следующих однотипных элементов.
Каждая из итераций состоит из нескольких последовательно выполняемых шагов.
ИТЕРАЦИЯ
1. Проверка оптимальности или нахождение ведущего столбца симплекс-
ной таблицы.
• Условие оптимальности. Если все коэффициенты c
j
в нулевой строке сим-
плексной таблицы, соответствующей целевой функции неотрицательны, то те-
кущее базисное решение оптимально.
• Если же существуют коэффициенты c
j
< 0, то текущее базисное решение не
оптимально и его можно улучшить за счет введения в базис переменную x
s
,
которая выбирается из условия:
c
s
= min
c
j
<0
c
j
.
Столбец s называется ведущим столбцом симплексной таблицы.
2. Проверка условия неограниченности решения задачи ЛП и нахождение
ведущей строки (ведущего элемента) симплексной таблицы.
• Условие неограниченности задачи ЛП. Если в ведущем столбце s нет поло-
жительных коэффициентов, то значение задачи ЛП не ограничено (нет опти-
мального решения).
• В противном случае, в задаче ЛП в качестве выводимой из базиса переменной
x
r
выбирается та переменная, для которой:
b
r
a
rs
= min
a
is
>0
b
i
a
is
.
Строка r называется ведущей строкой таблицы, а элемент a
rs
– ведущий
элемент симплексной таблицы.
3. Преобразование симплекс-таблицы.
24 Глава 1. ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ
С помощью эквивалентных преобразований (метод Гаусса) добиться того, чтобы
ведущий элемент таблицы стал равен 1, а остальные элементы в ведущем столбце
равны 0. Базисная переменная x
r
заменяется на x
s
и переходим к исследованию
новой симплексной таблицы (новая итерация).
Пример.
max z = max(x
1
+ 3x
2
);
3x
1
+ 2x
2
≤ 12,
x
1
+ 2x
2
≤ 6,
−x
1
+ x
2
≤ 1,
x
2
≤ 2,
x
1
≥ 0,
x
2
≥ 0;
Приведем к канонической форме
z − x
1
− 3x
2
= 0;
3x
1
+ 2x
2
+ s
1
= 12,
x
1
+ 2x
2
+ s
2
= 6,
−x
1
+ x
2
+ s
3
= 1,
x
2
+ s
4
= 2,
x
1
, x
2
, s
i
≥ 0, i = 1, 2, 3, 4.
Дигональная форма образуется по переменным s
1
, s
2
, s
3
, s
4
, следовательно в качестве
начального допустимого базисного решения можем использовать переменные
s
1
= 12, s
2
= 5, s
3
= 1, s
4
= 2, x
2
= x
1
= 0.
Запишем начальную симплексную таблицу:
Переменные задачи
Базисные переменные x
1
x
2
s
1
s
2
s
3
s
4
Базисное решение
z -1 -3 0 0 0 0 0
s
1
3 2 1 0 0 0 12
s
2
2 1 0 1 0 0 6
s
3
-1 1 0 0 1 0 1
s
4
0 1 0 0 0 1 2
1.3. ПРЯМОЙ СИМПЛЕКС-МЕТОД ДЛЯ ЗАДАЧИ МАКСИМИЗАЦИИ 25
В качестве переменной, вводимой в число базисных, мы выбираем x
2
. Соответствую-
щий этой переменной столбец под номером 2 – ведущий столбец.
Теперь из совокупности базисных переменных s
1
, s
2
, s
3
, s
4
необходимо выбрать ис-
ключаемую из базиса переменную.
В нашем случае исключаемой базисной переменной будет s
3
. Строка, соответствую-
щая исключаемой переменной – ведущая строкой, а элемент таб лицы a
32
, находящийся
на пересечении ведущей строки и ведущего столбца – ведущий элемент. Проводим пре-
образования таблицы по методу Гаусса.
Переменные задачи
Базисные переменные x
1
x
2
s
1
s
2
s
3
s
4
Базисное решение
z -4 0 0 0 3 0 3
s
1
5 0 1 0 -2 0 10
s
2
3 0 0 1 -2 0 4
x
2
-1 1 0 0 1 0 1
s
4
1 0 0 0 -1 1 1
В строке, соответствующей целевой функции присутствуют отрицательные коэффи-
циенты, значит симплексная таблица не двойственно-допустима, продолжаем процесс: в
базис вводится переменная x
1
, выводится из базиса переменная s
4
, получаем следующую
таблицу:
Переменные задачи
Базисные переменные x
1
x
2
s
1
s
2
s
3
s
4
Базисное решение
z 0 0 0 0 -1 4 7
s
1
0 0 1 0 3 -5 5
s
2
0 0 0 1 1 -3 1
x
2
0 1 0 0 0 1 2
x
1
1 0 0 0 -1 1 1
По-прежнему в строке, соответствующей целевой функции присутствуют отрицатель-
ные коэффициенты, значит симплексная таблица не двойственно-допустима, на этой
итерации в базис вводится переменная s
3
, выводится из базиса переменная s
2
, получаем
следующую таблицу:
26 Глава 1. ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ
Переменные задачи
Базисные переменные x
1
x
2
s
1
s
2
s
3
s
4
Базисное решение
z 0 0 0 1 0 1 8
s
1
0 0 1 -3 0 4 2
s
3
0 0 0 1 1 -3 1
x
2
0 1 0 0 0 1 2
x
1
1 0 0 1 0 -2 2
Это оптимальное решение задачи, так как выполняются условия прямой допустимо-
сти и двойственной допустимости. Оптимальное решение задачи z
∗
= 8, x
∗
1
= 2, x
∗
2
= 2.
Заметим, что оно совпадает с решением, полученным ранее графическим способом.
1.3.5 Задачи для самостоятельного решения
1.3.1 1.3.2
max z = max(3x
1
+ x
2
+ 2x
3
);
12x
1
+ 3x
2
+ 6x
3
+ 3x
4
= 46;
8x
1
+ x
2
− 4x
3
+ 2x
5
= 8;
3x
1
− x
6
= 0
x
i
≥ 0, i = 1, 2, 3.
max z = max(2x
1
+ 6x
2
+ 3x
3
− 2x
4
);
x
1
+ 7x
2
+ x
3
+ 7x
4
≤ 46;
3x
1
− x
2
+ x
3
+ 2x
4
≤ 8;
2x
1
+ 3x
2
− x
3
+ x
4
≤ 10;
x
i
≥ 0, i = 1, 2, 3, 4.
1.3.3 1.3.4
min z = min(3x
1
− 6x
2
− 2x
3
+ 4x
4
);
x
1
+ 7x
2
+ x
3
+ 7x
4
≤ 46;
3x
1
− x
2
+ x
3
+ 2x
4
≤ 8;
2x
1
+ 3x
2
− x
3
+ x
4
≤ 10;
x
i
≥ 0, i = 1, 2, 3, 4.
max z = max(5x
1
− 6x
2
+ 3x
3
− 5x
4
+ 12x
5
);
x
1
+ 3x
2
+ 5x
3
+ 6x
4
+ 3x
5
≤ 90;
x
i
≥ 0, i = 1, 2, 3, 4, 5.
1.3. ПРЯМОЙ СИМПЛЕКС-МЕТОД ДЛЯ ЗАДАЧИ МАКСИМИЗАЦИИ 27
1.3.5 1.3.6
max z = max(x
1
+ x
2
);
5x
1
− 2x
2
≤ 7;
−x
1
+ x
2
≤ 5;
x
1
+ x
2
≤ 6;
x
1
≥ 0, x
2
≥ 0.
max z = max(8x
1
− 5x
2
);
2x
1
− x
2
− x
3
≤ 4,
4x
1
+ 3x
2
≤ 2,
−3x
1
+ 2x
2
≤ 3;
x
1
, x
2
, x
3
≥ 0.
1.3.7 1.3.8
max z = max(3x
1
+ 2x
2
);
2x
1
+ x
2
≤ 14,
−3x
1
+ 2x
2
≤ 9,
3x
1
+ 4x
2
≤ 27;
x
1
, x
2
≥ 0.
max z = max(8x
1
+ x
2
+ 2x
3
);
5x
1
− x
2
+ x
3
≤ 2,
x
1
+ 2x
2
+ 2x
3
≤ 4;
x
1
, x
2
, x
3
≥ 0.
1.3.9 1.3.10
max z = max(x
1
+ x
2
);
2x
1
+ 11x
2
≤ 38,
x
1
+ x
2
≤ 7,
4x
1
− 5x
2
≤ 5;
x
1
, x
2
≥ 0.
max z = max(x
1
+ 2x
2
+ 3x
3
− x
4
);
x
1
+ 2x
2
+ 3x
3
= 15,
2x
1
+ x
2
+ 5x
3
= 20,
x
1
+ 2x
2
+ x
4
= 10,
x
1
, x
2
, x
3
, x
4
≥ 0.
28 Глава 1. ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ
1.4 Двухфазный симплекс-метод
Для реализации симплекс-метода осталась проблема нахождения начального базисного
решения. Вспомогательные построения гарантируют нахождение базисного (но не обя-
зательно допустимого) решения.
Рассмотрим каноническую задачу максимизации.
max z = max(c
1
x
1
+ c
2
x
2
+ . . . + c
n
x
n
); (1.4.1)
a
1
x
1
+ a
2
x
2
+ . . . + a
n
x
n
= b
i
, i = 1, m;
x
ij
≥ 0, j = 1, n.
(1.4.2)
Предполагаем, что b
i
≥ 0, i =
1, m, (если это не так, то умножим соответствующее
ограничение на -1).
Искусственные переменные.
Добавим в каждое уравнение искуственную переменную R
i
, которые должны быть
равны нулю в оптимальном решении. Получим начальное базисное допустимое решение
R
i
= b
i
≥ 0, i =
1, m, x
j
= 0, j = 1, n.
Используя искусственные переменные, строим новую целевую функцию
r =
m
P
i=1
R
i
. Рассмотрим задачу минимизации функции r, используя исходную целевую
функцию как одно из ограничений (первая фаза).
min r = min
m
P
i=1
R
i
;
z −
n
P
j=1
c
j
x
j
= 0;
R
i
+
n
P
j=1
a
ij
x
j
= 0, i =
1, m;
R
i
≥ 0, i =
1, m, j = 1, n;
(1.4.3)
Если исходная задача имеет допустимое решение, то в конце первой фазы все искус-
ственные переменные должны стать равными нулю. На второй фазе находится максимум
основной функции z.
1.4.1 Алгоритм двухфазного симплекс-метода.
1. Двухфазный симплекс-метод реализуется с помощью обычных симплекс-таблиц.
1.4. ДВУХФАЗНЫЙ СИМПЛЕКС-МЕТОД 29
2. На первой фазе находится допустимое базисное решение задачи (1.4.1), а затем
продолжаются вычисления с исходной целевой функцией (второй этап).
3. Если r
min
< 0, то в исходной задаче (1.4.1) нет допустимого решения.
4. Если r
min
= 0, но в базисе присутствует искусственная переменная, которую нельзя
вывести из базиса с помощью эквивалентных преобразований, то система ограни-
чений избыточна.
Пример. В прямом симплекс-методе, который мы использовали ранее, для получе-
ния начального базисного решения использовались слабые переменные. Однако когда ис-
ходное ограничение записано в виде равенства или имеет знак ≤, нельзя сразу получить
допустимое базисное начальное решение. Это можно увидеть н а следующем примере:
min z = min(4x
1
+ x
2
);
6x
1
+ 2x
2
= 5,
8x
1
+ 6x
2
≥ 7,
2x
1
+ 4x
2
≤ 3,
x
1
, x
2
≥ 0.
Приводим задачу к канонической форме, введя слабую переменную x
3
во второе огра-
ничение, и x
4
в третье ограничение и перейдя от задачи минимума к задачи максимума.
Получим следующую эквивалентную формулировку задачи:
max(−z) = max(−4x
1
− x
2
);
6x
1
+ 2x
2
= 5,
8x
1
+ 6x
2
− x
3
= 7,
2x
1
+ 4x
2
+ x
4
= 3,
x
1
, x
2
, x
3
, x
4
≥ 0.
Фаза 1. Введем в первые два ограничения искусственные переменные R
i
. В резуль-
тате получим диагональную форму относительно переменных R
1
, R
2
, x
4
:
max(−z) = max(−4x
1
− x
2
);
6x
1
+ 2x
2
+ R
1
= 5,
8x
1
+ 6x
2
− x
3
+ R
2
= 7,
2x
1
+ 4x
2
+ x
4
= 3,
x
1
, x
2
, x
3
, x
4
≥ 0,
R
1
, R
2
≥ 0.
30 Глава 1. ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ
Рассмотрим новую целевую функцию r, при этом функцию z будем рассматривать
как одно из ограничений новой задачи:
max(−r) = −R
1
− R
2
;
−z + 4x
1
+ x
2
= 0;
6x
1
+ 2x
2
+ R
1
= 5,
8x
1
+ 6x
2
− x
3
+ R
2
= 7,
2x
1
+ 4x
2
+ x
4
= 3,
x
1
, x
2
, x
3
, x
4
, R
1
, R
2
≥ 0.
−r − 14x
1
− 8x
2
+ x
3
= −12;
−z + 4x
1
+ x
2
= 0;
6x
1
+ 2x
2
+ R
1
= 5,
8x
1
+ 3x
2
− x
3
+ R
2
= 7,
2x
1
+ 4x
2
+ x
4
= 3,
x
1
, x
2
, x
3
, x
4
, R
1
, R
2
≥ 0.
Начальная симплексная таблица примет вид:
Переменные задачи
Базисные переменные x
1
x
2
x
3
R
1
R
2
x
4
Базисное решение
−r -14 -8 1 0 0 0 −12
−z 4 -1 0 0 0 0 0
R
1
6 2 0 1 0 0 5
R
2
8 6 -1 0 1 0 7
x
4
2 4 0 0 0 1 3
Симплексная таблица для второй итерации на первой фазе.
Переменные задачи
Базисные переменные x
1
x
2
x
3
R
1
R
2
x
4
Базисное решение
−r 0 −3
1
3
1 2
1
3
0 0 −
1
3
−z 0 −
1
3
0 −
2
3
0 0 −3
1
3
x
1
1
1
3
0
1
6
0 0
5
6
R
2
0 3
1
3
-1 −1
1
3
1 0
1
3
x
4
0 3
1
3
0 −
1
3
0 1 1
1
3
Оптимальная симплексная таблица для первой фазы метода.
Переменные задачи
Базисные переменные x
1
x
2
x
3
R
1
R
2
x
4
Базисное решение
−r 0 0 0 1 1 0 0
−z 0 0 −
1
10
−
4
5
1
10
0 3
3
10
x
1
1 0
1
10
1
10
−
1
10
0
4
5
x
2
0 1 −
3
10
−
2
5
3
10
0
1
10
x
4
0 0 1 1 -1 1 1