Симплекс-метод решения задач линейного программирования

1.

Симплекс-метод решения
ЗЛП

2. Содержание

1. Определение К-матрицы в КЗЛП
2. Переход от одной К-матрицы КЗЛП к другой К3.
4.
5.
6.
7.
8.
9.
матрице
Симплекс-разность К-матрицы КЗЛП
Способ построения опорного плана, более близкого
к оптимальному
Критерий оптимальности опорного плана
Критерий отсутствия конечного решения
Алгоритм симплекс-метода
Пример 1
Пример 2
АЛГОРИТМ СИМПЛЕКС-МЕТОДА
2

3. Пусть требуется решить задачу (1)

Симплекс-метод решения ЗЛП
n
Пусть требуется
решить задачу
f ( x) c j x j max
j 1
n
a
j 1
ij
x j bi
xj 0
,
i 1, m
j 1, n
,
,
bi 0
(1)
,
i 1, m
Или
f ( x) (c, x ) max
Ax b
x 0
,
(2)
b 0
Симплекс-метод
3

4.

Так как решением задачи (2) является крайняя точка множества
Р ее допустимых решений, или, что то же самое, неотрицательное
базисное решение системы линейных уравнений A x b , то метод
решения задачи (1) должен содержать 4 момента:
1) обоснование способа перехода от одного опорного плана (Кматрицы) к другому;
2) указание признака оптимальности, позволяющего проверить,
является ли данный опорный план оптимальным;
3) указание способа построения нового опорного плана, более
близкого к оптимальному;
4) указание признака отсутствия конечного решения.
Симплекс-метод
4

5. Определение К-матрицы в КЗЛП

Рассмотрим каноническую задачу линейного программирования (КЗЛП):
f ( x) (c, x) max
Ax b
x 0, b 0.
Будем считать, что ранг матрицы А равен m, причем m<n.
Запишем КЗЛП в векторном виде: max(c, x)
n
a
j 1
j
xj b
(*)
x 0, b 0,
где a j – j-й столбец матрицы А.
Дадим одно из определений опорного плана. ОП ЗЛП будемn называть такой
план X ( X 1 , X 2 ,..., X n ) , что векторы a j , входящие в разложение a j x j b
j 1
со строго положительными x j , линейно независимы.
К-матрицей КЗЛП будем называть расширенную матрицу системы линейных
уравнений, равносильной системе (*), содержащую единичную подматрицу на
месте первых n своих столбцов и все элементы (n+1)-го которой
m
C
n
неотрицательны. Число К-матриц конечно и не превышает
. Каждая Кматрица определяет ОП КЗЛП и наоборот.
АЛГОРИТМ СИМПЛЕКС-МЕТОДА
5

6. Переход от одной К-матрицы ЗЛП к другой К-матрице.

Пусть известна К-матрица
K
(S )
a11( S )
(S )
a21
...
a(S )
m1
a12( S )
... a1(nS )
(S )
22
(S )
2n
a
...
am( S2)
... a
... ...
(S )
... amn
(S )
b1( S )
(S )
b2
...
bm( S )
(3)
Обозначим через N N1( S ) ,..., N m( S ) вектор номеров базисных
(единичных) столбцов матрицы K (S ) , X N ( S ) b1( S ) ,..., bm( S ) вектор, компоненты которого есть базисные компоненты опорного
плана, определяемого матрицей
, и могут быть отличны от
K (S )
нуля.
Переход от одной К-матрицы ЗЛП к другой
6

7.

Остальные (n - m) компонент опорного плана,
(S )
(S )
K
определяемого матрицей
, равны нулю. Очевидно, что векторы N
и
полностью задают опорный план,
X N (S)
K (S )
определяемый матрицей Например, пусть:
K (S )
(S )
0 3 1 4 2 0, 1
1 4 0 3 3 0 2
0 5 0 1 8 1 4
(S )
тогда N (3,1,6) ; X N b (1,2,4) и, следовательно,
(S )
опорный план, определяемый K , имеет вид:
(S )
X (2,0,1,0,0,4)
Переход от одной К-матрицы ЗЛП к другой
7

8.

Итак, пусть К-матрица (3) определяет невырожденный опорный
план X N ( S ) b1( S ) ,..., bm( S )
N
(S )
N1( S ) ,..., N m( S )
(S )
k
(S )
Выберем в матрице K
столбец a
, не принадлежащий
(S )
единичной подматрице, т. е. K N i
, i 1, m , и такой, что в этом
столбце есть хотя бы один элемент больше нуля.
Пусть alk 0 . Считая alk направляющим элементом, совершим над
матрицей K (S ) один шаг метода Жордана - Гаусса. В результате получим
новую матрицу
( S 1)
( S 1)
( S 1)
( S 1)
(S )
(S )
K ( S 1)
(S )
k
a11
a12
( S 1)
( S 1)
a22
a21
...
...
a ( S 1) a ( S 1)
m2
m1
... a1n
... a2( Sn 1)
...
...
... a
( S 1)
mn
( S 1)
b2
...
bm( S 1)
b1
,
в которой a
стал единичным, но которая может и не быть К-матрицей, т.к.
1)
bi( Sмогут
среди величин
быть отрицательные.
Переход от одной К-матрицы ЗЛП к другой
8

9.

Теорема 1.
Пусть в каком-либо столбце К-матрицы
один строго положительный элемент (
K
(S )
-
a
(S )
k
есть хотя бы
K N i(S ) , i 1, m ) . Тогда с помощью
одного шага метода Жордана-Гаусса можно построить новую К-матрицу
K ( S 1) , выбрав направляющий элемент
из условия
Переход от одной К-матрицы ЗЛП к другой
9

10. Симплекс-разность К-матриц ЗЛП. Изменение функции при переходе от одной К-матрицы к другой.

Симплекс-разность К-матриц ЗЛП. Изменение
функции f (x) при переходе от одной К-матрицы к
другой.
Определение.
Величину
(S )
j
(C N , a
(S)
(S )
j
) Cj
,
где C N ( S ) - вектор, компонентами которого являются коэффициенты
линейной функции f ( x) (c, x) при базисных ( N
(S )
) переменных
опорного плана, определяемого матрицей K (S ) , назовем j-й
симплекс - разностью матрицы
K (S )
Симплекс-разность К-матриц ЗЛП
.
10

11.

(S )
Пусть X N
и
X N ( S 1) - опорные планы, определяемые матрицами
K (S ) и K ( S 1) соответственно. Тогда очевидно, что
f ( X N ( S 1) ) (C N ( S 1) , X N ( S 1) ) ; f ( X N ( S ) ) (C N ( S ) , X N ( S ) )
и
f ( X N ( S 1) ) f ( X N ( S ) ) ( S ) (kS )
где К-номер столбца a
(S )
k
(S )
b
f ( X N ( S ) ) l( S ) (kS )
alk
,
, вводимого в базис при получении
матрицы K ( S 1) из K (S ) .
Симплекс-разность К-матриц ЗЛП
11

12. Способ построения опорного плана (матрицы ), более близкого к оптимальному, чем

Способ построения опорного плана
более близкого к оптимальному, чем
X N ( S 1)
(матрицы
K ( S 1)
),
X N (S )
Теорема 2.
Пусть в матрице
K (S )
(S )
(S )
есть k 0 , и в столбце a k
( K N i(S ) , i 1, m ) есть хотя бы один строго положительный элемент.
Тогда от матрицы K (S ) можно перейти к матрице K ( S 1) , причем
f ( X N ( S 1) ) f ( X N ( S ) )
.
Способ построения опорного плана
12

13.

Доказательство.
Так как в К-ом столбце К-матрицы
элемент, то согласно теореме 1 от матрицы
K (S )
K (S )
есть строго положительный
можно перейти к новой
(S )
( S 1)
a
K
К-матрице
ЗЛП, выбрав направляющий элемент lk из условия (7).
По условию
(kS ) 0
поэтому из соотношения
следует
,
а по построению ( S ) 0
,
f ( X N ( S 1) ) f ( X N ( S ) ) ( S ) (kS )
f ( X N ( S 1) ) f ( X N ( S ) )
Если все опорные планы ЗЛП невырождены, то
(ч.т.д.)
(S ) 0
и
f ( X N ( S 1) ) f ( X N ( S ) )
Способ построения опорного плана
13

14. Критерий оптимальности опорного плана

X N ( S )
Теорема 3
(S )
Пусть все симплекс - разности матрицы
неотрицательные. Тогда
K
(S )
опорный план
, определяемый
матрицей
, является
X N(S )
K
оптимальным.
Доказательство.
По условиям теоремы
или
(8)
x1
Пусть
j
C
(S )
(S )
CN
,a j
N
x2
X план
Произвольный
ЗЛП.
. . .
x
nи правую
Умножим левую
части (8) на
неотрицательности
(9)
(S )
(S )
C
C
N
(S )
,a j
(S )
j
(S )
,
C
j
0
j 1, n
, тогда в силу
получим
xj
,a j
x
Критерий оптимальности опорного плана
xj
j
Cjxj
,
j 1, n
14

15.

Согласно (9) имеем:
n
n
f X Cjxj CN
n
j 1
m
C N i
j 1 i 1
или
f XN
(S )
j 1
(S )
(S )
aij
f X
(S )
,a j
m
(S )
x
x j C Ni bi
i 1
(S )
j
(S )
f XN
(S )
.
Что и доказывает теорему.
Критерий оптимальности опорного плана
15

16. Критерий отсутствия конечного решения.

Теорема 4
(S )
k
Пусть в матрице K
есть 0 , и в столбце a
( K N i(S )
,i 1, m ) нет ни одного положительного элемента. Тогда ЗЛП
(1) не имеет конечного решения.
(S )
(S )
k
Доказательство.
(S )
K
Пусть К-я симплекс-разность матрицы
(S )
(S )
(S )
K C N , a N CK 0 ,
и все
aik
Матрица
(S )
K
(10)
0 , i 1,2,..., m.
(S )
определяет опорный план
XN
N
(11)
(S )
(S )
(S )
(S )
b1 , b2 ,..., bm
(S )
(S )
(S )
N1 , N 2 ,..., N m
Критерий отсутствия конечного решения
(S )
.
16

17.

Рассмотрим вектор
у которого
/
X .
/
x2
. . ,
/
xn
/
(S )
(S )
x N1( S ) b1 a1k xk ,
x1
/
x / N 2( S ) b2
(S )
a2 k
(S )
xk ,
. . . . . . . . .
x / N m ( S ) bm
(S )
amk
(S )
xk ,
/
(S )
где
-любое положительное число.
x
x
,
k
N
, i 1, m.
k
k нулю.
i
Остальные n-m+1 компонент вектора положим равными
xk условия (11) компоненты вектора неотрицательны. Легко убедиться в
В силу
том, что компоненты вектора
удовлетворяют X
и /функциональным ограничениям
ЗЛП, т.е. вектор
- план ЗЛП при любом положительном / .
X
xk
Критерий отсутствия конечного решения
/
X /
X
17

18.

Имеем:
/
f X C N ( S ) b1
CN
m
1
( S ) bm
(S )
C N1 b1
(S )
(S )
(S )
(S )
amk
a1k
(S )
(S )
(S )
CN2
(S )
(S )
f X x
/
Или окончательно
f X
(12)
(S )
k
N
k
X
2
(S )
... C N m bm
a2 k
(S )
0
xk C N ( S ) b2
(S )
xk C k xk
C N 2 b2
xk (C N1 a1k
(S )
(S )
(S )
k
/
... C N m
(S )
(S )
a2 k
(S )
xk ...
amk
(S )
Ck )
.
/
f X M
,
Т.к.
, то из (12) следует, что для любого числа М >0 всегда можно /
f X
P
найти план
ЗЛП, для которого
т.е. линейная форма
не ограничена сверху на множестве
планов.
Терема доказана.
Критерий отсутствия конечного решения
18

19. Пример 1

• Симплекс-методом решить ЗЛП:
max (1)
f ( X ) 3X1 2 X 2
X 1 2 X 2 6,
2 X 1 X 2 8,
X 1 X 2 1,
(2)
X 2 2,
X 1 0, X 1 0.
ПРИМЕР №1
19

20.

• Приводим систему линейных неравенств (2) к каноническому
виду, вводя в каждое неравенство дополнительную переменную
x j , j 3,6 .
• Получим систему линейных уравнений:
X 1 2 X 2 X 3 6,
2 X 1 X 2 X 4 8,
X 1 X 2 X 5 1,
(3)
X 2 X 6 2,
X j 0, j 1,6.
ПРИМЕР №1
20

21.

• Целевая функция (1) будет иметь вид
F ( X ) 3X1 2 X 2 0 X 3 0 X 4 0 X 5 0 X 6
• Расширенная матрица
K (0)
1
2
1
0
2 1 0 0 0 6
1 0 1 0 0 8
1 0 0 1 0 1
1 0 0 0 1 2
K (0)
системы линейных уравнений (3) является исходной
(0)
(0)
К-матрицей
ЗЛП,
которая
определяет
X N (6,8,1,2)
N (исходный
3,4,5,6)
опорный план:
C N ( 0 ) (0,0,0,0)
ПРИМЕР №1
21

22.

Введём следующие обозначения:
• S-номер итерации
• i-номера строк таблицы
N
-номера столбцов, образующих единичную подматрицу
CN
-коэффициенты целевой функции при столбцах, образующих
единичную подматрицу
ai
-соответствуют переменным задачи
XN b
-сначала содержит правые части системы уравнений , в
конце алгоритма - искомые значения переменных
-для вычисления значений
ПРИМЕР №1
22

23.

Результаты последовательных итераций симплексалгоритма оформим в виде симплекс-таблицы.
23

24.

На второй итерации S=2, все j 0, j 1,6 следовательно,
опорный план
( 2)
( 2)
X N ( 2 ) (4 / 3;10 / 3;3;2 / 3) ; N (2,1,5,6)
( 2)
определяемый К-матрицей K
, оптимальный,
*
X (10 / 3;4 / 3;0;0;3;2 / 3)
• Оптимальное значение линейной формы равно:
*
( 2)
f ( X ) f ( X N ) (C N , b )
(2)
( 2)
C N ( 2 ) b1( 2 ) C N ( 2 ) b2( 2) C N ( 2 ) b3( 2) C N ( 2 ) b4( 2)
1
2
3
4
2
2 4 / 3 3 10 / 3 0 3 0 2 / 3 12
3
ПРИМЕР №1
24

25. Пример 2

• Симплекс-методом решить ЗЛП:
max(2 X 1 X 2 )
X 1 X 2 10
X 1 40
(4)
(5)
X 1, 2 0
Приводим ЗЛП (4-5) к каноническому виду
max(2 X 1 X 2 0 X 3 0 X 4 )
X 1 X 2 X 3 10
X 1 X 4 40
X j 0;
(6)
j 1,4
ПРИМЕР №2
25

26.

Результаты последовательных итераций запишем в
симплекс-таблицу.
ПРИМЕР №2
26

27.

• Из симплекс-таблице при S=2 следует, что согласно шагу 3
симплекс-алгоритма данная ЗЛП не имеет конечного решения,
т.к. отрицательная симплекс-разность (32 ) соответствует
( 2)
столбцу a 3 , все элементы которого неположительны.
• Итак,
max f ( X )
P
ПРИМЕР №2
27