Оптимізаційні методи та моделі. Симплекс-метод розв'язання задач лінійної оптимізації. (Тема 4)

1. Оптимізаційні методи та моделі

Університет митної справи та фінансів
Оптимізаційні
методи
та моделі
доц. Лебідь О.Ю.
Дніпропетровськ
2016

2. Тема 4: Симплекс-метод розв'язання задач лінійної оптимізації

Тема 4: Симплекс-метод
розв'язання
задач
1.Канонічна
форма загальної
задачілінійної
ЛО.
2.Правила
переходу
План
від загальної задачі лінійної
оптимізації
оптимізації до канонічної.
3.Приклад зведення задачі ЛО до канонічної
форми.
4.Основні властивості розв'язків задач ЛО.
5.Симплекс-метод розв'язання задач ЛО.
6.Алгоритм симплекс-методу розв'язання задач
ЛО.
7.Правила перебудови симплекс-таблиці за
методом Жордана-Гаусса.
8.Правило
прямокутника
перебудови
симплексної таблиці.
9.Варіанти розв'язку задачі ЛО симплексметодом.
2
10.Приклад розв'язання задачі ЛО симплекс-

3. Канонічна форма загальної задачі лінійної оптимізації

z c1x1 c2 x2 ... cn xn max
(1)
a11 x1 a12 x2 ... a1n xn b1
a x a x ... a x b
21 1
22 2
2n n
2
..............................................
a m1 x1 a m 2 x2 ... amn xn bm
x1 0, x2 0,..., xn 0.
(2)
за умов
(3)
3

4. Правила переходу від загальної задачі лінійної оптимізації до канонічної

1. Цільову
функцію
максимізувати.
необхідно
2. В системі обмежень всі праві частини
невід’ємні.
3. Всі обмеження в системі є рівняннями
(явні).
4. Всі змінні мають невід’ємний характер.
4

5. Правила переходу від загальної задачі лінійної оптимізації до канонічної

Залишкова змінна. Нерівності типу
“≤” зазвичай можна інтерпретувати як
обмеження на використання деяких
ресурсів. В нерівність вона входить зі
знаком “+”.
Надлишкова змінна. Нерівність типу
“≥” показує на те, що “щось” повинно
бути не менш за деяку величину. В
нерівність вона входить зі знаком “–”.
5

6. Правила переходу від загальної задачі лінійної оптимізації до канонічної

Вільна змінна. Можливі ситуації, коли змінні
можуть приймати будь-які дійсні значення. Таким
чином на неї на накладена умова невід’ємності. Для
виконання п. 4 побудови канонічної форми кожну
вільну за знаком змінну xt необхідно замінити на
xt xt xt , де xt , xt 0 .
6

7. Приклад зведення задачі ЛО до канонічної форми

z 2 x1 5 x2 7 x3 min (4)
за умов
x1 4 x2 6 x3 3,
3 x1 7 x2 9 x3 4,
7 x 3 x x 5,
2
3
1
x1 0, x3 0.
(5)
(6)
7

8. Приклад зведення задачі ЛО до канонічної форми

Канонічна форма задачі (4)-(6):
z 2 x1 5 x2 x 2 7 x3 max
(7)
за умов
x1 4 x2 x2 6 x3 3,
3 x1 7 x2 x2 9 x3 x4 4,
7 x 3 x x x x 5,
2
2
3
5
1
x1 , x2 , x 2 , x3 , x4 , x5 0.
(8)
(9)
8

9. Основні властивості розв’язків задач лінійної оптимізації

Теорема 1. Множина всіх планів задачі
лінійної оптимізації опукла.
Теорема 2. Якщо задача лінійної
оптимізації має оптимальний план, то
екстремального значення цільова функція
набуває в одній із вершин її багатогранника
розв’язків. Якщо ж цільова функція набуває
екстремального значення більш як в одній
вершині цього багатогранника, то вона
досягає його і в будь-якій точці, що є
лінійною комбінацією таких вершин.
9

10. Основні властивості розв’язків задач лінійної оптимізації

Теорема 3. Якщо відомо, що система векторів A 1,
A 2, …, A k (k n) у розкладі A 1x1+A 2x2 + … + A nxn = A 0,
X 0 лінійно незалежна і така, що
A 1x1 +A 2x2 +… +A kxk =A 0,
де всі xj 0, то точка X = (x1, x2, …, xk, 0, …, 0) є
кутовою точкою багатогранника розв’язків.
Теорема 4. Якщо X = (x1, x2, …, xn) – кутова точка
багатогранника розв’язків, то вектори в розкладі
A 1x1 + A 2x2 + … + A nxn = A 0, X 0, що відповідають
додатним xj, є лінійно незалежними.
10

11. Основні властивості розв’язків задач лінійної оптимізації

Наслідок 1. Оскільки вектори A1 , A2 ,..., An мають
розмірність m, то кутова точка багатокутника
розв’язків має не більше, ніж m додатних
компонентів xi 0 (i 1, m) .
Наслідок 2. Кожній кутовій точці багатокутника
розв’язків відповідає k m лінійно незалежних
векторів системи A1 , A2 ,..., An .
Висновок: якщо функціонал задачі лінійної
оптимізації обмежений на багатограннику розв’язків, то:
існує така кутова точка багатогранника розв’язків, в якій
лінійний функціонал досягає свого оптимального значення; 11
кожний опорний план відповідає кутовій точці

12. Основні властивості розв’язків задач лінійної оптимізації

розв’язків має не більше, ніж m додатних
Основні
розв’язків
компонентів xвластивості
i 0 (i 1, m) .
Наслідок
Кожній кутовій
точці багатокутника
задач2.лінійної
оптимізації
розв’язків відповідає k m лінійно незалежних
векторів системи A1 , A2 ,..., An .
Висновок: якщо функціонал задачі лінійної
оптимізації обмежений на багатограннику розв’язків, то:
існує така кутова точка багатогранника розв’язків, в якій
лінійний функціонал досягає свого оптимального значення;
кожний опорний план відповідає кутовій точці
багатогранника розв’язків.
12

13. Симплекс-метод розв'язання задач лінійної оптимізації

Симплекс-метод
–
це
поетапна
обчислювальна
процедура,
в
основу
якої
покладено принцип послідовного покращення
значень цільової функції переходом від одного
опорного плану задачі лінійної оптимізації до
іншого.
Алгоритм
симплекс-методу
завжди
починається з деякого опорного розв’язку (плану)
і потім намагається знайти інший опорний план,
який покращує значення цільової функції.
13

14. Алгоритм симплекс-методу розв'язання задач ЛО

1. Визначення
початкового опорного плану
задачі ЛО.
2. Побудова симплексної таблиці.
3. Перевірка
опорного
плану
на
оптимальність за допомогою оцінок. Якщо
план не оптимальний, то переходять до
нового опорного плану або встановлюють,
що оптимального плану не існує.
4. Перехід до нового опорного плану задачі,
тобто розрахунок нової симплексної таблиці.
5. Повторення дій, починаючи з п. 3.
14

15. Алгоритм симплекс-методу розв'язання задач ЛО

На етапі визначення початкового опорного
плану задачі ЛО, після її зведення до
канонічної форми, шукаємо m одиничних
лінійно незалежних векторів, які становлять
базис m-вимірного простору. Можливі такі
випадки:
•є необхідна кількість одиничних векторів,
тоді початковий опорний план визначається
безпосередньо без додаткових дій;
•у системі обмежень немає необхідної
кількості одиничних незалежних векторів.
Тоді для побудови першого опорного плану
застосовують метод штучного базису.
15

16. Алгоритм симплекс-методу розв'язання задач ЛО

Визначені одиничні лінійно незалежні
вектори утворюють базис, і змінні
задачі, що відповідають їм, називають
базисними, а всі інші змінні –
вільними.
16

17. Алгоритм симплекс-методу розв'язання задач ЛО

Теорема (ознака оптимальності опорного плану).
Опорний план X * x1* , x2* ,..., xn* задачі ЛО є оптимальним,
якщо для всіх j , j 1, n виконується умова
j 0 (для задачі на максимум),
m
де j Z j c j ci aij c j ,
i 1
j 1, n .
Оцінку j можна знайти з симплексної таблиці як
скалярний добуток векторів-стовпчиків “Сбаз” та x j
мінус відповідний коефіцієнт c j .
17

18. Алгоритм симплекс-методу розв'язання задач ЛО

У процесі перевірки умови оптимальності
можливі такі випадки:
усі j , j 1, n задовольняють умову оптимальності, і тоді визначений опорний план є
оптимальним;
не всі j задовольняють умову оптимальності, і
тоді потрібно виконати перехід до наступного,
нового опорного плану задачі.
18

19. Алгоритм симплекс-методу розв'язання задач ЛО

Перехід від одного опорного плану до іншого
виконується зміною базису, тобто виключенням з
нього деякої змінної та введенням замість неї нової з
числа вільних змінних задачі.
Змінна, яка включається до нового базису,
відповідає тій оцінці j , що не задовольняє умову
оптимальності. Якщо таких оцінок кілька, серед них
вибирають найбільшу за абсолютною величиною і
відповідну їй
змінну вводять до базису.
Припустимо, що індекс зазначеної змінної j k .
Відповідний
стовпчик
симплексної
таблиці
називають напрямним.
19

20. Алгоритм симплекс-методу розв'язання задач ЛО

Для визначення змінної, що має бути виключена з
базису, знаходять для всіх додатних aik напрямного
стовпчика величину bi aik . Вибирають найменше
значення , яке вказує на змінну, що виводиться з
базису. Припустимо, що це виконується для i r .
Відповідний
рядок
симплексної
таблиці
називатиметься напрямним.
Перетином напрямного стовпчика та напрямного
рядка визначається число симплексної таблиці a rk ,
яке називають розв’язувальним елементом. За
допомогою елемента a rk й методу Жордана-Гаусса
розраховують нову симплексну таблицю.
20

21. Правила перебудови симплекс- таблиці за методом Жордана-Гаусса

Правила перебудови симплекстаблиці за методом ЖорданаГаусса
1. Розв’язувальний (напрямний) рядок необхідно
поділити на розв’язувальний елемент і здобуті числа
записати у відповідний рядок симплексної таблиці.
2. Розв’язувальний стовпчик у новій таблиці
записують як одиничний з одиницею замість
розв’язувального елемента.
3. Якщо в напрямному рядку є нульовий елемент,
то відповідний стовпчик переписують у нову
симплексну таблицю без змін.
4. Якщо в напрямному стовпчику є нульовий
елемент, то відповідний рядок переписують у нову
таблицю без змін.
5. Усі інші елементи наступної симплекс-таблиці
розраховують за правилом прямокутника.
21

22. Правило прямокутника перебудови симплекс-таблиці

В симплексній таблиці складаємо умовний прямокутник,
вершини якого утворюються такими числами:
1 – розв’язувальний елемент;
2 – число, що стоїть на місці елемента нової симплексної
таблиці, який ми маємо розрахувати;
3 та 4 – елементи, що розміщуються в двох інших
протилежних вершинах умовного прямокутника.
Необхідний елемент нової симплекс-таблиці визначають:
Число 1 Число 2 - Число 3 Число 4
Розв' язувальний елемент
,
де умовний прямокутник виглядатиме
22

23. Варіанти розв'язку задачі ЛО симплекс-методом

Якщо в оцінковому рядку останньої симплексної
таблиці оцінка j =0 відповідає вільній (небазисній)
змінній, то задача ЛО має альтернативний
оптимальний план. Отримати його можна,
вибравши розв’язувальний елемент у зазначеному
стовпчику таблиці та здійснивши один крок
симплекс-методом.
Якщо при переході у симплекс-методі від одного
опорного плану задачі до іншого в напрямному
стовпчику немає додатних елементів aik , тобто
23

24. Варіанти розв'язку задачі ЛО симплекс-методом

таблиці оцінка j =0 відповідає вільній (небазисній)
змінній, то задача ЛО має альтернативний
Варіанти
задачі
ЛО
оптимальний розв'язку
план. Отримати
його можна,
вибравшисимплекс-методом
розв’язувальний елемент у зазначеному
стовпчику таблиці та здійснивши один крок
симплекс-методом.
Якщо при переході у симплекс-методі від одного
опорного плану задачі до іншого в напрямному
стовпчику немає додатних елементів aik , тобто
неможливо вибрати змінну, яка має бути виведена з
базису, то це означає, що цільова функція задачі ЛО
є необмеженою й оптимальних планів не існує.
24

25. Приклад розв'язання задачі ЛО симплекс-методом

z 5 x1 4 x2 max
6 x1 4 x2 24,
x 2 x 6,
1
2
x1 x2 1,
x2 2,
x1 , x2 0
Приведемо нашу задачу до канонічної форми.
z 5 x1 4 x2 0 x3 0 x4 0 x5 0 x6 max
6 x1 4 x2 x3 24,
x 2 x x 6,
1
2
4
x1 x2 x5 1,
x2 x6 2,
xi 0, i 1,6
25

26. Приклад розв'язання задачі ЛО симплекс-методом

Система обмежень у векторній формі:
A1x1 A2 x2 A3 x3 A4 x4 A5 x5 A6 x6 B ,
де
24
6
4
1
0
0
0
6
1
2
0
1
0
0
A1 A 2 A3 A 4 A5 A6 B
1 .
1 ,
1 ,
0 ,
0 ,
1 ,
0 ,
0
1
0
0
0
1
2
Базис: A3 , A4 , A5 , A6 .
Початковий опорний план має вигляд
Х =(0; 0; 0; 0; 450;
Х =380).
(0; 0; 24; 6; 1; 2).
26

27. Приклад розв'язання задачі ЛО симплекс-методом

2
j Z j c j ci aij c j
i 1
,
j 1,6 .
27

28. Приклад розв'язання задачі ЛО симплекс-методом

Отримали новий опорний план
х=(4; 0; 0; 2; 5; 2).
28

29. Приклад розв'язання задачі ЛО симплекс-методом

29

30. Приклад розв'язання задачі ЛО симплекс-методом

Оптимальний план задачі:
X* =(3; 3/ 2; 0; 0; 5/ 2; 1/ 2),
zmax =5*3 +4*3/ 2 =21.
Відповідь: X* =(3; 3/ 2), zmax =21.
30

31. Список літератури

Основна:
1. Зайченко Ю. П. Дослідження операцій :
підручник / Ю. П. Зайченко. – К. : ВІПОЛ, 2000.
2. Таха Х. Введение в исследование операций /
Х. Таха. – М. : Вильямс, 2001.
3. Ульянченко О. В. Досліждення операцій в
економіці / О. В. Ульянченко. – Х. : Гриф, 2003.
Додаткова:
1.
Вітлінський В. В.
Математичне
програмування
/
В. В. Вітлінський,
С. І. Наконечний, Т. О. Терещенко. – К., 2001.
2.
Кузнецов А. В.
Математическое
программирование / А. В. Кузнецов и др. – М.:
Высшая школа, 1994.
31