Методы оптимальных решений. Симплексный метод

1. Дисциплина МЕТОДЫ ОПТИМАЛЬНЫХ РЕШЕНИЙ

Факультет дистанционного обучения,
направление 38.03.01 «Экономика»,
профиль «Финансы и кредит»
Дисциплина
МЕТОДЫ ОПТИМАЛЬНЫХ
РЕШЕНИЙ
Кафедра математических
методов в экономике

2. СИМПЛЕКСНЫЙ МЕТОД РЕШЕНИЯ ЗЛП

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

3.

4.

5.

6.

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

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

8.

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

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

Рассмотрим каноническую задачу линейного программирования (КЗЛП):
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 ( X1 , X 2 ,..., X n ) , что векторы a j , входящие в разложение
a jxj b
со строго положительными x j , линейно независимы.
j 1
К-матрицей КЗЛП будем называть расширенную матрицу системы линейных
уравнений, равносильной системе (*), содержащую единичную подматрицу на
месте первых n своих столбцов и все элементы (n+1)-го которой
неотрицательны. Число К-матриц конечно и не превышает C nm . Каждая Кматрица определяет ОП КЗЛП и наоборот.
АЛГОРИТМ СИМПЛЕКС-МЕТОДА
9

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

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

11.

Остальные (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)
Переход от одной К-матрицы ЗЛП к другой
11

12.

Итак, пусть К-матрица (3) определяет невырожденный опорный
план X N ( S ) b1( S ) ,..., bm( S )
N
(S )
N1( S ) ,..., N m( S )
(S )
k
Выберем в матрице K
столбец a
, не принадлежащий
(S )
единичной подматрице, т. е. K N i
, i 1, m , и такой, что в этом
столбце есть хотя бы один элемент больше нуля.
(S )
Пусть alk 0 . Считая alk направляющим элементом, совершим над
матрицей K (S ) один шаг метода Жордана - Гаусса. В результате получим
новую матрицу
( S 1)
( S 1)
( S 1)
( S 1)
(S )
(S )
K ( S 1)
(S )
k
a11
a
( S 1) 12( 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могут
среди величин
быть отрицательные.
Переход от одной К-матрицы ЗЛП к другой
12

13.

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

14.

Доказательство:
Пусть известна К-матрица
K
(S )
a11( S )
(S )
a
21
...
a(S )
m1
a12( S )
... a1(nS )
(S )
a22
... a2( Sn )
...
am( S2)
...
...
(S )
... amn
b1( S )
(S )
b2
...
bm( S )
задачи линейного программирования, которая определяет невырожденный
опорный план
X N ( S ) b1( S ) ,..., bm( S )
N
(S )
N1( S ) ,..., N m( S )
следовательно,
b1( S ) 0,
,
,
b2( S ) 0,
..., bm( S ) 0
Остальные n-m компонент опорного плана равны нулю.
Переход от одной К-матрицы ЗЛП к другой
14

15.

Возьмем в матрице K (S ) столбец К , не принадлежащий
единичной подматрице ( K N i(S ) , i 1, m ) и такой, что в этом
столбце есть хотя бы один отличный от нуля элемент.
(S )
Пусть alk 0 .
(S )
Считая alk направляющим элементом, совершим над матрицей K (S )
один шаг метода Жордана-Гаусса.
В результате получим новую матрицу
K ( S 1)
a11( S 1)
( S 1)
a
21
...
a ( S 1)
m1
a12( S 1)
... a1(nS 1)
( S 1)
a22
... a2( Sn 1)
...
am( S2 1)
...
...
( S 1)
... amn
b1( S 1)
( S 1)
b2
...
bm( S 1)
элементы которой выражаются через элементы матрицы
следующим формулам:
АЛГОРИТМ СИМПЛЕКС-МЕТОДА
,
K (S )
по
15

16.

alj( S 1)
( S 1)
ij
( S 1)
i
a
b
alj( S )
( S 1)
;
b
l
(S )
alk
(S )
ij
a
(S )
i
b
bl( S )
(S ) ;
blk
j 1, n
(1*)
(S )
lj
a
aik( S )
( S ) ; i 1, m,
alk
(S )
l
b
aik( S )
( S ) ; i 1, m, i l
alk
j 1, n, i l
(2*)
(3*)
Таким образом, в результате одного шага метода ЖорданаГаусса мы получили L-матрицу ЗЛП, причем компоненты вектора
N
( S 1)
N1( S 1) , N 2( S 1) ,..., N m( S 1)
выражаются по следующим формулам:
N i( S 1) N i( S ) , i l
N
( S 1)
l
k
Переход от одной К-матрицы ЗЛП к другой
(4*)
16

17.

( S 1)
Однако матрица K
может и не быть К-матрицей ЗЛП, так
как среди величин bi( S 1) , i 1, m
могут быть отрицательные.
Получим условия, которым должен удовлетворять
направляющий элемент alk( S ) , чтобы ( S 1)
bi
0, i 1, m .
Из alj( S 1)
alj( S )
( S 1)
;
b
l
(S )
alk
bl( S )
(S ) ;
blk
j 1, n
следует, что
bl( S 1) 0
тогда и только тогда, когда
alk( S ) 0
(4)
Это первое условие, которое мы должны наложить на выбор
направляющего элемента.
Переход от одной К-матрицы ЗЛП к другой
17

18.

( S 1)
i
Из b
b
(S )
i
b
(S )
l
aik( S )
( S ) ; i 1, m, i l
alk
следует, что
bi( S 1) 0, i 1,2,..., l 1, l 1,..., m
тогда и только тогда, когда
aik( S )
b b ( S ) 0, i 1,2,..., l 1, l 1,..., m
alk
(S )
Условие (5) выполняется для всех aik 0 ,
(S )
i
(5)
(S )
l
i 1,2,..., l 1, l 1,..., m .
(S )
Перепишем неравенство (5) для строго положительных aik
в виде
bi( S ) bl( S )
( S ) 0,
(S )
aik
alk
i 1,2,..., l 1, l 1,..., m
Переход от одной К-матрицы ЗЛП к другой
(6)
18

19.

(S )
Очевидно, неравенство (6) будет выполняться для всех aik 0
если выбрать l таким, что
bl( S )
(S )
alk
bi( S )
(S )
min
(S )
(S )
aik
0 ,i 1, m a ik
Если минимум в
индекса i, то bi( S 1) 0,
случае план ЗЛП.
Если минимум в
ниях индекса i ,то
(7)
соотношении (7) достигается при одном значении
i 1, m , т. е. матрица K ( S 1) определяет в этом
соотношении (7) достигается при нескольких значе-
(S )
Тогда при
,
l i1
bi(1S )
a
(S )
i1k
bi(2S )
a
(S )
i2 k
...
bi(rS )
ai(rSk )
bi(2S 1) bi(3S 1) ... bi(rS 1) 0
определяет вырожденный опорный план ЗЛП.
, т.е. матрица K ( S 1)
(ч.т.д.)
Переход от одной К-матрицы ЗЛП к другой
19

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

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

21.

Пусть X N ( S )
и
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 ) .
Симплекс-разность К-матриц ЗЛП
21

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

Способ построения опорного плана X N
( S 1)
более близкого к оптимальному, чем X N
)
(матрицы K ( S 1),
(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 ) )
.
Способ построения опорного плана
22

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

X N ( S )
Теорема 3
Пусть все симплекс - разности матрицы K (S ) неотрицательные.
Тогда опорный план X N ( S ) , определяемый матрицей K (S )
,
является оптимальным.
Критерий оптимальности опорного плана
23

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

Теорема 4
(S )
Пусть в матрице K
есть k 0 , и в
(S )
(S )
столбце a k ( K N i , i 1, m ) нет ни
(S )
одного положительного элемента. Тогда ЗЛП
(1) не имеет конечного решения.
Критерий отсутствия конечного решения
24

25. Алгоритм симплекс-метода

Пусть известна исходная К-матрица K ( 0 ) ЗЛП,
определяющая исходный опорный план
X N (b1( 0) , b2( 0) ,..., bm( 0) ),
(0)
N
(0)
( N1( 0) , N 2( 0) ,..., N m( 0) ).
Последовательно строятся К-матрицы K (0) , K (1) ,..., K ( S )
ЗЛП, пока не выполнится критерий оптимальности или
критерий, позволяющий убедиться в отсутствии конечного
решения.
Рассмотрим алгоритм S-ой итерации симплекс-метода. В
( S 1)
начале S-ой итерации имеем К-матрицу K
ЗЛП,
определяющую опорный план
X N (b1( S 1) , b2( S 1) ,..., bm( S 1) ),
( S 1)
N
( S 1)
( N1( S 1) , N 2( S 1) ,..., N m( S 1) ).
Алгоритм симплекс-метода
25

26.

Шаг 1.
( S 1)
( S 1)
( S 1)
(
j
N
, i 1, m)
Вычисляем для столбцов a j матрицы K
,
j
симплекс-разности ( jS 1) и находим номер К из условия
(kS 1) min ( jS 1) , 1 j n
Шаг 2.
( S 1)
( S 1)
( S 1)
Если j 0 , то опорный план X N , N
является
оптимальным, а f ( X N ( S 1) ) (C N ( S 1) , X N ( S 1) ) есть оптимальное
значение линейной формы f ( X ) , иначе переходим к шагу 3
Шаг 3.
Если aik( S 1) 0, i 1, m то ЗЛП не имеет конечного решения.
bi( S 1) bl( S 1)
Иначе находим номер L из условия ( S 1)
min ( S 1) ( S 1)
;
1 i m a
alk
ik
a ( S 1) 0
ik
( S 1)
направляющий элемент на S-ой итерации метода есть элемент alk
Алгоритм симплекс-метода
26

27.

Шаг 4.
(S )
Вычисляем компоненты вектора N
:
N i( S ) N i( S 1) , i L, N L( S ) k .
Шаг 5.
Производим один шаг метода Жордана-Гаусса с направляющим
элементом
aik( S 1)
. Присваиваем переменной S алгоритма
значение S+1 и переходим к шагу 1.
Алгоритм симплекс-метода
27

28. Пример 1

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

29.

• Приводим систему линейных неравенств (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
29

30.

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

31.

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

32.

Результаты последовательных итераций симплексалгоритма оформим в виде симплекс-таблицы.
S i
0 1
2
3
4
5
(S )
N
б.п.
3
4
5
6
CN
XN
(S )
b
(S )
3
2
(S )
0
0
0
0
6
8
1
2
F=0
a1
1
2
-1
0
-3
( 0j )
0
(S )
0
(S )
0
(S )
(S )
0
(S )
(S )
a2
2
1
1
1
-2
a3
1
0
0
0
0
a4
0
1
0
0
0
a5
0
0
1
0
0
a6
0
0
0
1
0
1 1
2
3
4
5
3
1
5
6
(1j )
0
3
0
0
2
4
5
2
F=3*4=12
0
1
0
0
0
3/2
1/2
3/2
1
-1/2
1
0
0
0
0
-1/2
1/2
1/2
0
3/2
0
0
1
0
0
0
0
0
1
0
2 1
2
3
4
5
2
1
5
6
( 2j )
2
3
0
0
4/3
10/3
3
2/3
F=38/3
0
1
0
0
0
1
0
0
0
0
2/3
-1/3
-1
-2/3
1/3
-1/3
2/3
1
1/3
2
0
0
1
0
0
0
0
0
1
0
6
4
k=1
L=2
4/3
8
10/3
2
k=2
L=1
32

33. Пересчёт таблицы

34.

( 2)
• На второй итерации S=2, все j 0, j 1,6 следовательно,
опорный план
( 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)
XN
( 2)
• Оптимальное значение линейной формы равно:
*
( 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
34

35. Пример 2

• Симплекс-методом решить ЗЛП:
max( 2 X 1 X 2 )
(4)
X 1 X 2 10
X 1 40
(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
(6)
X 1 X 4 40
X j 0;
j 1,4
ПРИМЕР №2
35

36.

Результаты последовательных итераций запишем в
симплекс-таблицу.
S i
N
(S )
CN
XN
(S )
b
(S )
2
1
(S )
1
0
(S )
2
(S )
0
(S )
3
(S )
4
0 1
2
3
3
4
( 0j )
0
0
10
40
F=0
a
1
1
-2
1 1
2
3
1
4
(1j )
2
0
10
30
F=2*10=20
1
0
0
-1
1
-3
1
-1
2
0
1
0
30
2 1
2
3
1
2
( 2j )
2
1
40
30
F=2*40+30=
=110
1
0
0
0
1
0
0
-1
-1
1
1
3
-
ПРИМЕР №2
a
-1
0
-1
a
1
0
0
a
0
1
0
10
40
36

37.

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

38. Список литературы

1. Мастяева И.Н., Горемыкина Г.И.,
Семенихина О.Н., Методы оптимизации:
линейные модели. М.: МЭСИ, 2015.
2. Мастяева И.Н., Горемыкина Г.И.,
Семенихина О.Н., Исследование
операций и методы оптимизации. М.:
МЭСИ, 2015.
3. Мастяева И.Н., Горемыкина Г.И.,
Семенихина О.Н., Методы оптимальных
решений. М.: Курс, 2016.