Лекция3_Симплекс_метод_ЛП

1. Свойства задачи ЛП

Свойство 1. Допустимая область задачи ЛП выпукла,
если она не пуста.
Свойство 2. Если допустимая область имеет вершины и
задача ЛП имеет решение, то оно достигается, по
крайней мере, в одной из вершин.
Свойство 3. Множество решений задачи ЛП выпукло.
Свойство 4. Если допустимая область ограничена, то
любая задача ЛП имеет оптимальное решение.
Свойство 5. Необходимым и достаточным условием
существования решения задачи ЛП на максимум
(минимум) является ограниченность целевой функции
сверху (соответственно снизу) в допустимой области.
1

2. Конечные методы решения задачи ЛП. Симплекс метод

Лекция 3
2

3. План лекции

I Канонический вид задачи ЛП
II Обоснование симплекс метода
III Алгоритм симплекс метода
IV Структура симплекс-таблицы
V Пример
VI Вспомогательная задача для определения
начального базиса
3

4. I Канонический вид задачи ЛП

5. Канонический вид задачи ЛП

Пусть имеется задача ЛП в канонической форме:
F( x ) = c1 x1 + c 2 x 2 + .... + c n x n → max (1)
a11x1 + ... + a1n x n = b1
............................
a x + ... + a x = b
mn n
m
m1 1
(2)
x1 0,..., x n 0
Если в исходной задаче ограничения вида «≤» в левую часть добавляется
неотрицательная фиктивная переменная, если ограничения вида «≥» то из
левой части вычитается неотрицательная фиктивная переменная. Если на
переменную не наложено требования не отрицательности проводится замена:
x j = x /j − x //j , x /j , x //j 0 .
5

6. Векторно-матричная запись задачи ЛП

Вводя в рассмотрение векторы
(
)
A j = a1 j , a 2 j ,...,a mj T , j = 1, n .
Мы можем переписать задачу (1-2) в форме:
F = c x → max ,
A1x1+A2x2 +…+Anxn=b,
x 0
(3)
(4)
и трактовать следующим образом: из всех разложений вектора b по
векторам A1 , …, A n , с неотрицательными коэффициентами требуется
выбрать хотя бы одно такое, коэффициенты xi, i = 1, n , которого
доставляют целевой функции F максимальное значение.
Систему (4) можно записать в виде:
A x = n = b
(4’)
6

7. II Обоснование симплекс метода

8. Определения

T
(
)
x
=
x
,...,
x
1
n называется
Ненулевое допустимое решение
опорным, если векторы Aj , соответствующие отличным от
нуля координатам вектора x, линейно-независимы.
Ненулевое опорное решение x назовем невырожденным,
если оно имеет ровно «m» положительных координат.
Если число положительных координат опорного решения
меньше m, то оно называется вырожденным.
Упорядоченный набор из «m» линейно-независимых
векторов Aj, соответствующих положительным
координатам опорного решения назовем базисом.
8

9. Теорема

Вектор x = (x1 ,...,x n ) тогда и только тогда является опорным
решением задачи, когда точка х является вершиной
допустимого множества.
Обозначения
(
)
x б = x i 1 ,..., x i m T – вектор базисных переменных;
(
A б = A i1 ,...,A i m – матрица базисных векторов;
Cб = ci1 ,...,ci m – вектор из коэффициентов целевой функции при базисных неизвестных;
)
(
)
C c = (ci ,...,ci )– вектор из коэффициентов целевой функции при свободных переменных;
x с = x i m +1 ,..., x i n T – вектор свободных переменных;
m +1
n
A c = A i m+1 ,...,Ai n – матрица свободных векторов (векторов, не вошедших в базис).
9

10. Этапы симплекс метода

1. Определяется некоторая вершина области допустимых
решений.
2. По некоторому критерию проверяют, не является ли
рассматриваемая вершина оптимальной.
3. Если критерий не выполнен, проверяют не является ли ЦФ
неограниченной сверху в допустимой области.
4. Если и этот критерий не выполнен, получают новую
вершину, в которой значение ЦФ не меньше чем в
предыдущей. Возврат к шагу 2.
Метод заключается в последовательном обходе
вершин/угловых точек множества допустимых решений.
10

11. III Алгоритм симплекс метода

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

1. Определяется начальный базис. Его составляют вектора Aj которые
образуют единичную матрицу размерности m.
2. Проводится разложение векторов Aj, k = 1, m – компоненты вектора
и b по базису.
3. Рассчитываются оценки для всех векторов (компоненты вектора
оценок):
= сTб A б− 1 A c − cс
m
j = сi k x ij − с j
k
k =1
(5)
Где x ij – компоненты разложения вектора Aj
k
4. Проверятся критерий оптимальности (первая теорема Данцига): все
компоненты вектора оценок неотрицательные ( j 0 ), тогда текущее
решение оптимально. Решение найдено, конец алгоритма.
12

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

5. Проверятся критерий отсутствия решения – неограниченности целевой функции (вторая теорема
Данцига):
r : r 0 : x irk 0 k = 1, m
среди компонент вектора оценок есть отрицательные и при этом, по крайней мере, у одного из свободных
векторов с отрицательной оценкой все компоненты разложения по базису меньше или равны нулю. Если он
выполнен конец алгоритма.
6. Модификация базиса. Существует лучшее опорное решение, которое можно получить, введя в базис
свободный вектор A s , имеющий наименьшую отрицательную оценку S и, выведя из базиса тот вектор A r
исходного базиса, для которого:
x i0k x i0r
(6)
min s = s
k = 1, m
x si 0 x i
x
ir
k
k
где x i0k , k = 1, m – компоненты x б ;
x sik , k = 1, m – компоненты вектора А s , вводимого в базис.
7. Координаты всех векторов в новом базисе могут быть найдены через координаты векторов в старом
базисе по формулам:
x kj
s , при k = r
x
j ik
(7)
xi =
j
s
k
x
x
ik
j
ir
x
−
, j = 0, n, k = 1, m, k r.
ik
s
x
ir
8. Возвращение к шагу 3.
13

14. IV Структура симплекс-таблицы

15. Симплекс таблица

Таблица 1 – общая схема симплекс-таблицы
В столбце «Базис» указываются вектора A L k попавшие в базис; в столбце сбаз записываются коэффициенты
c L k при соответствующих неизвестных из целевой функции. В столбце b (опорное решение) записываются
координаты разложения вектора b по базису, то есть опорный план; в столбцах A1 , A2 ,…, An записывают
координаты разложения этих векторов по базису, то есть столбцы матрицы A б−1 A c .
После этого заполняют строку «Оценки»:
- значение целевой функции для найденного опорного решения:
m
F = сi k x i0k ;
k =1
15
(8)

16. V Пример

17. Математическая модель

Рассмотрим задачу из части I
F( x ) = 47 x1 + 61x 2 → max
0 x1 + x 2 48
x1 + 0 x 2 120
10x + 20x 2000
2
1
x1 0
x2 0
Приведем к каноническому виду
F( x ) = 47 x1 + 61x 2 + 0 x 3 + 0 x 4 + 0 x 5 → max
0 x1 + x 2 + x 3 = 48
x1 + 0 x 2 + x 4 = 120
10x + 20x + x = 2000
2
5
1
x1 0 x 2 0 x 3 0 x 4 0 x 5 0
17

18. Определение начального базиса

Выпишем вектора
0
1
1
0
0
A1 = 1 A 2 = 0 A3 = 0 A 4 = 1 A5 = 0
10
20
0
0
1
Начальный базис образуют векторы
A3 A 4 A5
18

19. Первая симплекс-таблица

Бази
Сбаз bопор
с
А3
А4
А5
Δj
0
0
0
48
120
2000
F(x)=0
47
А1
0
61
А2
1
0
А3
1
0
А4
0
0
А5
0
1
10
-47
0
20
-61
0
0
0
1
0
0
0
1
0
Критерий оптимальности не выполнен.
Критерий неограниченности не выполнен.
Переходим к новой симплекс-таблице.
19
x опор = (0 0 48 120 2000)
θ
48
4
∞
100

20. Вторая симплекс таблица

Расчет элементов
Разрешающая строка
1
0
48
= 48 x12 = = 0 x 32 = = 1
1
1
1
48 20
48 0
x 50 = 2000 −
= 1040
= 120
Остальные элементы x 04 = 120 −
1
1
1 20
1 0
0 0
0 20
x 34 = 0 −
= −20
= 0 x 35 = 0 −
x14 = 1 −
= 1 x15 = 10 −
= 10
1
1
1
1
Базис Сбаз
А2
А4
А5
Δj
61
x 02 =
bопор
48
0
120
1040
0
F(x)=2928
47
61
0
0
0
θ
А1
0
А2
1
А3
1
А4
0
А5
0
∞
1
0
1
0
10
-47
0
0
0
-20
61
0
0
1
0
x опор = (0 48 0 120 1040)
20
4
120
104

21. Третья симплекс таблица

Расчет элементов
Разрешающая строка
1040
− 20
1
= 104 x13 =
= −2 x15 = = 0,1
10
10
10
0 1040
1 1040
= 48
x 04 = 120 −
= 16
Остальные элементы x 02 = 48 −
10
10
− 20 1
− 20 0
1 0
x 34 = 0 −
x 32 = 1 −
x 52 = 0 −
= −2
=0
=1
10
10
10
Базис Сбаз
А2
А4
А1
Δj
61
x10 =
bопор
48
0
16
104
47
F(x)=7816
x 54 = 0 −
47
61
0
0
0
θ
А1
0
А2
1
А3
1
А4
0
А5
0
48
0
0
1
-0,1
1
0
0
0
2
-2
0
0
0,1
4,7
-33
x опор = (104 48 0 16 0 )
21
1 1
= −0,1
10
4
8
∞

22. Четвертая симплекс таблица

Базис
Сбаз
bопор
А2
61
А3
А1
40
8
120
0
47
F(x)=8080
Δj
47
61
0
0
А1
0
0
1
0
А2
1
0
0
0
А3
0
1
0
0
А4
А5
-0,5 0,05
0,5 -0,05
1
0,1
16,5 3,05
Критерий оптимальности выполнен
x*опор = (120 40 8 0 0 )
22
0

23. VI Вспомогательная задача для определения начального базиса

24. Нахождения начального базиса

Если в исходной задаче все ограничения имели вид
“≤”, то в качестве начального базиса можно брать
базис из векторов при дополнительных переменных.
В общем случае для построения начального базиса
используется специальный прием, известный как
метод искусственного базиса.
Дана задача в каноническом виде
F = c x → max (3)
Ax = b
(4)
x 0
24

25. Вспомогательная задача для определения начального базиса

G = − y1 − y 2 − ... − y m → max
(G = y1 + y2 + ... + ym → min )
a11x1 + ... + a1n x n + y1 = b1
a x + ... + a x + 0 y + y = b
21 1
2n n
1
2
2
(9)
............................
a m1x1 + ... + a mn x n + 0 y1 + ... + y m = b m
x j 0, j = 1, n
yi 0, i = 1, m.
Переменные y1, y2, ….,ym называются искусственными переменными.
Вспомогательная задача всегда имеет решение!
Теорема: Если в оптимальном решении вспомогательной задачи, среди
искусственных переменных есть положительные, то исходная задача ЛП не
имеет области допустимых решений, если все yi*=0, i=1,..m, то базис,
соответствующий оптимальному решению вспомогательной задачи, можно
взять в качестве исходного базиса основной задачи.
25

26. Пример

Исходная задача
Канонический вид
F = x 1 + 3x 2 → max
F = x1 + 3x 2 + 0 x 3 + 0 x 4 → max
2 x1 + x 2 10
− 2 x1 + 3x 2 6
x1 0, x 2 0
2x1 + x 2 − x 3 = 10
− 2x1 + 3x 2 + x 4 = 6
x1 0, x 2 0, x 3 0, x 4 0
Вспомогательная задача для нахождения начального базиса
G = − y1 → max
2x 1 + x 2 − x 3 + y1 = 10
− 2x 1 + 3x 2 + x 4 = 6
x 1 0, x 2 0, x 3 0, x 4 0
26

27. Решение вспомогательной задачи

Первая симплекс-таблица. Решение не оптимально, есть отрицательные оценки
0
0
0
0
-1
А1
А2
А3
А4
А5
Базис
Сбаз
bопор
А5
-1
10
2
1
-1
0
1
А4
0
6
-2
3
0
1
0
F(x)=-10
-2
-1
0
0
0
Δj
10
=
2
Вторая симплекс-таблица. Решение оптимально
0
0
0
-1
А1
А2
А3
А4
А5
Базис
Сбаз
bопор
А1
0
5
1
0,5
-0,5
0
0,5
А4
0
16
0
4
-1
1
1
0
0
0
0
1
Δj
27
0
F(x)=0

28. Решение исходной задачи

Целевая функция вспомогательной задачи g(x*,y*)=0 следовательно
получили начальный базис для исходной задачи.
Составим симплекс-таблицу для исходной задачи
1
3
0
0
А1
А2
А3
А4
Базис
Сбаз
bопор
А1
1
5
1
0,5
-0,5
0
А4
0
16
0
4
-1
1
0
-2,5
-0,5
0
Δj
F(x)=0
Целевая функция не ограничена сверху!
Вектор А3 имеет отрицательную оценку и все координаты разложения ≤0
28