Лабораторна робота №6
Оптимізаційні задачі
Особливості задач оптимізації
Якщо графік цільової функції паралельний графіку одного з обмежень, для ЦФ буде існувати велика кількість оптимальних рішень. Але розхід ресурсів при максимумі ЦФ в різних точках є різним.
Нехай дано цільову функцію (ЦФ) Z=7x1+21x2, а також обмеження
x1+3x2?12
2x1+x2?11,5
x1?0, x2?0
Потрібно максимізувати ЦФ.
Результат графічного розв’язання наведено на рис.1

Рис.1
У цьому випадку при переміщенні графіка ЦФ у напряму вектору зростання ЦФ до границі полігона дозвільних рішень, пряма ЦФ співпаде з графіком першого обмеження. Таким чином, оптимальним рішенням є всі точки відрізку АВ.
Для аналітичного находження оптимуму дослідимо границі знайденого відрізку – точки А та В. Точка А знаходиться на перетині прямих x1+3x2=12 та 2x1+x2=11,5. Обчислимо координати точки А методом підстановок, у результаті отримаємо: х1=4,5; х2=2,5.
Точка В знаходиться на перетині прямої x1+3x2=12 та прямої x1=0. Її координати х1=0, х2=4.
Значення ЦФ, тобто, наприклад, прибуток у точках А та В однаковий, але розхід ресурсів може бути різним.
Підставимо координати точки А у ліві частини обмежень на ресурси (перше та друге обмеження):
x1+3x2= 4,5 + 3*2,5 = 12.
Можливий розхід ресурсу не більший за 12 одиниць, а при підстановці отримали також 12, тобто цей ресурс вичерпано повністю.
Друге обмеження виглядає так: 2x1+x2?11,5. Розрахунок використання ресурсу дає: 2x1+x2 = 2*4,5 + 2,5 = 11,5. Бачимо, що другій ресурс також вичерпано повністю.
Тепер підставимо координати точки В у ліві частини обмежень.
x1+3x2= 0 + 3*4 = 12. Перший ресурс також використано повністю.
2x1+x2 = 2*0 + 4 = 4. Вийшло 4 < 11,5, тобто другій ресурс в точці В можна зекономити (а саме на 11,5 – 4 = 7,5 одиниць).
Кількість одиниць зекономленого ресурсу необхідно вказати у звіті.
Висновок: оптимальними є значення х1=0, х2=4, ЦФ=84.
Якщо розв’язувати цю задачу за допомогою Excel, то не завжди буде вибрано точку оптимуму. Це відбувається тому, що Excel не враховує економію ресурсів, а тільки максимізує ЦФ. На всьому відрізку АВ цільова функція приймає максимальне значення. Тому Excel у якості відповіді запише будь-яку точку, що належить відрізку АВ (це залежить від початкових значень х1 та х2). Треба зауважити, що ця особливість є недоліком Excel.
Варіант
Цільова ф.
Обмеження
Варіант
Цільова ф.
Обмеження

1
Z=6x1+2x2
x1?0, x2?0
x1+10x2?35
3x1+x2?18
12
Z=1,5x1+6x2
x1?0, x2?0
x1+4x2?18
8x1+5x2?36

2
Z=0,6x1+x2
x1?0, x2?0
3x1+5x2?25
7x1+x2?21
13
Z=x1+0,8x2
x1?0, x2?0
4x1+9x2?40,5
5x1+4x2?32,5

3
Z=2,5x1+x2
x1?0, x2?0
x1+3x2?10,5
5x1+2x2?33
14
Z=5x1+15x2
x1?0, x2?0
x1+3x2?10,5
8x1+3x2?42

4
Z=18x1+14x2
x1?0, x2?0
9x1+7x2?49
3x1+x2?13
15
Z=2x1+0,4x2
x1?0, x2?0
5x1+6x2?25
5x1+x2?12,5

5
Z=6x1+2x2
x1?0, x2?0
5x1+6x2?33
3x1+x2?12
16
Z=1,5x1+12x2
x1?0, x2?0
x1+8x2?56
3x1+x2?18,5

6
Z=0,5x1+2x2
x1?0, x2?0
x1+4x2?12
6x1+7x2?38
17
Z=3x1+4,5x2
x1?0, x2?0
3,5x1+2x2?18
1,5x1+2x2?10

7
Z=6x1+2x2
x1?0, x2?0
x1+9x2?56,5
3x1+x2?13,5
18
Z=2x1+2,5x2
x1?0, x2?0
2,5x1+2x2?22
1,5x1+2x2?16

8
Z=3,5x1+7x2
x1?0, x2?0
1x1+2x2?12
8x1+7x2?60
19
Z=2,8x1+3,2x2
x1?0, x2?0
5,5x1+2,5x2?19
3x1+2x2?15

9
Z=4x1+1,5x2
x1?0, x2?0
4x1+5x2?30
8x1+3x2?32
20
Z=3x1+3,5x2
x1?0, x2?0
2,6x1+2,2x2?14
x1+3x2?11

10
Z=1x1+1,6x2
x1?0, x2?0
5x1+8x2?52
5x1+2x2?28
21
Z=3,4x1+3x2
x1?0, x2?0
4x1+3x2?15
2x1+3x2?10

11
Z=7,4x1+3,7x2
x1?0, x2?0
2x1+3x2?9
2x1+x2?7
22
Z=1,5x1+2x2
x1?0, x2?0
x1+2x2?10
2x1+4x2?18


Особливості задач оптимізації для кількох ЦФ
Якщо задано наприклад три ЦФ, то завдання потрібно виконати з кожною з них окремо, тобто спочатку знайти максимум ЦФ Z1, після цього –максимум ЦФ Z2, зрештою – максимум ЦФ Z3. Можливо побудувати три ЦФ на одному графіку.
Це показує, що оптимальний розв’язок змінюється зі зміною цільової функції. В реальних випадках ЦФ змінюється, наприклад, зі зміною ринкових цін виробляємої продукції.
Графіки деяких ЦФ можуть бути паралельні графіку якогось із значень. В такому випадку точка оптмума знаходиться з врахуванням економії ресурсів. Тоді у звіт слід записати кількість одиниць зекономленого ресурсу.
У звіті потрибно надати три значення ЦФ, а також координати кожної знайденої точки.

Варіант
Цільова ф.
Обмеження
Варіант
Цільова ф.
Обмеження

1
Z1=0,2x1+1,6x2
x1?0, x2?0
x1+10x2?35
3x1+x2?18
12
Z1=1,5x1+6x2
x1?0, x2?0
x1+4x2?18
8x1+5x2?36


Z2=x1+1,5x2


Z2=1,5x1+6x2



Z3=x1+3x2


Z3=1,5x1+6x2


2
Z1=6x1+22x2
x1?0, x2?0
3x1+5x2?25
7x1+x2?21
13
Z1=x1+0,8x2
x1?0, x2?0
4x1+9x2?40,5
5x1+4x2?32,5


Z2=x1+1,2x2


Z2=x1+0,8x2



Z3=4x1+7x2


Z3=x1+0,8x2


3
Z1=1,2x1+2x2
x1?0, x2?0
x1+3x2?10,5
5x1+2x2?33
14
Z1=5x1+15x2
x1?0, x2?0
x1+3x2?10,5
8x1+3x2?42


Z2=6x1+3x2


Z2=5x1+15x2



Z3=18x1+13,5x2


Z3=5x1+15x2


4
Z1=1,5x1+2x2
x1?0, x2?0
9x1+7x2?49
3x1+x2?13
15
Z1=2x1+0,4x2
x1?0, x2?0
5x1+6x2?25
5x1+x2?12,5


Z2=22x1+6x2


Z2=2x1+0,4x2



Z3=3x1+2x2


Z3=2x1+0,4x2


5
Z1=4x1+12x2
x1?0, x2?0
5x1+6x2?33
3x1+x2?12
16
Z1=1,5x1+12x2
x1?0, x2?0
x1+8x2?56
3x1+x2?18,5


Z2=51x1+17x2


Z2=1,5x1+12x2



Z3=12x1+10x2


Z3=1,5x1+12x2


6
Z1=0,6x1+x2
x1?0, x2?0
x1+4x2?12
6x1+7x2?38
17
Z=3x1+4,5x2
x1?0, x2?0
3,5x1+2x2?18
1,5x1+2x2?10


Z2=22x1+4x2






Z3=8x1+5x2





7
Z1=5,5x1+11x2
x1?0, x2?0
x1+9x2?56,5
3x1+x2?13,5
18
Z=2x1+2,5x2
x1?0, x2?0
2,5x1+2x2?22
1,5x1+2x2?16


Z2=4x1+2,5x2






Z3=5x1+7x2





8
Z1=3,5x1+7x2
x1?0, x2?0
1x1+2x2?12
8x1+7x2?60
19
Z=2,8x1+3,2x2
x1?0, x2?0
5,5x1+2,5x2?19
3x1+2x2?15


Z2=3,5x1+7x2






Z3=3,5x1+7x2





9
Z1=4x1+1,5x2
x1?0, x2?0
4x1+5x2?30
8x1+3x2?32
20
Z=3x1+3,5x2
x1?0, x2?0
2,6x1+2,2x2?14
x1+3x2?11


Z2=4x1+1,5x2






Z3=4x1+1,5x2





10
Z1=1x1+1,6x2
x1?0, x2?0
5x1+8x2?52
5x1+2x2?28
21
Z=3,4x1+3x2
x1?0, x2?0
4x1+3x2?15
2x1+3x2?10


Z2=1x1+1,6x2






Z3=1x1+1,6x2





11
Z1=7,4x1+3,7x2
x1?0, x2?0
2x1+3x2?9
2x1+x2?7
22
Z=1,5x1+2x2
x1?0, x2?0
x1+2x2?10
2x1+4x2?18


Z2=7,4x1+3,7x2






Z3=7,4x1+3,7x2