- •1.2. Приклади побудови математичних моделей
- •1.3. Завдання
- •1.4. Завдання до контрольної роботи
- •2. Гpафічний спосіб pозв’язання злп
- •2.1. Загальні положення графічного способу розв’язання злп
- •2.2. Приклади розв’язання злп графічним способом
- •Завдання до самостійної роботи
- •2.3. Завдання до контрольної роботи
- •3. Постоптимальний аналіз моделей
- •3.1. Аналіз моделей після знаходження оптимального розв’язку
- •3.2. Перша задача аналізу на чутливість
- •3.2.1. Гранично допустиме збільшення запасу дефіцитного ресурсу
- •3.2.2. Гранично допустиме зниження запасу недефіцитного ресурсу
- •3.3. Друга задача аналізу на чутливість
- •3.4. Третя задача аналізу на чутливість
- •1 Спосіб визначення інтервалів варіювання коефіцієнтів цф:
- •2 Спосіб визначення інтервалів варіювання коефіцієнтів цф:
- •Перевірка
- •Висновки
- •Приклади проведення постоптимального аналізу
- •3.5.1. Задача 1
- •Перевірка
- •Висновки
- •3.5.2. Задача 2
- •Висновки
- •3.6. Завдання до самостійної роботи
- •3.7. Завдання до контрольної роботи
- •Список літератури
2.2. Приклади розв’язання злп графічним способом
Приклад 5. Розв’яжемо графічно Задачу про фарби [11] (прикл. 1 з розд. 1.2).
Максимізувати |
; |
|
|
при обмеженнях |
; |
(продукт А) |
(4) |
; |
(продукт B) |
(5) | |
; |
(співвідношення попитів) |
(6) | |
; |
(макс. попит на фарбу I) |
(7) | |
; |
|
(8) | |
. |
|
(9) |
Область допустимих розв’язків задачі – багатокутник ABCDEF (рис. 7). Оптимальний розв’язок задачі – точка С. Значення та в цій точці знаходяться за допомогою розв’язання системи двох рівнянь: і. Розв’язавши її, отримаємо:=10/3 (т),= 4/3 (т). Прибутокz, одержаний у цьому випадку, складе 38/3 (тис. грн.).
Рис. 7
Відповідь: =10/3 (т),= 4/3 (т),z = 38/3 (тис. грн.).
На цьому прикладі можна побачити усі головні особливості ЗЛП: у ньому допустима множина розв’язків становить собою опуклий багатокутник, отриманий в результаті перетину півплощин, і найбільше значення цільової функції досягається в його вершині.
Завдання до самостійної роботи
Визначити простір розв’язків і знайти оптимальний розв’язок задачі, вважаючи, що кожна із зазначених нижче умов замінює (а не доповнює) відповідні вихідні дані, причому усі інші задані співвідношення залишаються без змін.
максимальний попит на фарбу I дорівнює 3 т.
попит на фарбу I не менш як 2 т.
попит на фарбу I рівно на одну тону перевищує попит на фарбу Е.
допустимі витрати вихідного продукту В не менш, як 8 тон на добу.
допустимі витрати вихідного продукту В не менш, як 8 тон на добу, а попит на фарбу I перевищує попит на фарбу Е не менш, ніж на одну тону.
Знайти оптимальний розв’язок при таких цільових функціях:
;
;
.
Приклад 6. Розв’язати ЗЛП графічно.
Максимізувати |
z = 2x1 + 2x2, |
|
при обмеженнях |
x1 + x2 ≤ 8; |
(10) |
x1 – 4x2 ≤ 2; |
(11) | |
x2 ≤ 5; |
(12) | |
x1 ≥ 1; |
(13) | |
x1 ≥ 0; |
(14) | |
x2 ≥ 0 |
(15) |
Рис. 8
Область допустимих розв’язків задачі – багатокутник ABCDE (рис. 8). Коефіцієнти цільової функції пропорційні коефіцієнтам обмеження (10): , отже, оптимальний розв’язок задачі – відрізокCD.
Знайдемо координати т. D:
Знайдемо координати т. C:
Відповідь: , 0 ≤ λ ≤ 1; z=16.
Приклад 7. Розв’язати ЗЛП графічно.
Максимізувати |
, |
|
при обмеженнях |
– x1 + x2 ≤ 1; |
(16) |
x1 + x2 ≥ 2; |
(17) | |
x1 – 4x2 ≤ 1; |
(18) | |
x1 ≥ 0; |
(19) | |
x2 ≥ 0. |
(20) |
Рис. 9
Відповідь: Задача не має розв’язку. Область допустимих розв’язків та цільова функція є необмеженими.
Приклад 8. Розв’язати ЗЛП графічно.
Максимізувати |
, |
|
при обмеженнях |
–; |
(21) |
; |
(22) | |
–; |
(23) | |
x1 ≥ 0 ; |
(24) | |
x2 ≥ 0. |
(25) |
Рис. 10
Відповідь: Задача не має розв’язку. Обмеження задачі – несумісні.
2.3. Завдання до контрольної роботи
Розв’язати ЗЛП графічно.
1. max z = 2x1 + 1x2 ; |
2. max z = 6x1 + 10x2; |
3. max z = x1 – 2x2 ; | |||
1x1 – 10x2 10; |
(1) |
–1x1 + 1x2 5; |
(1) |
1x1 – 2x2 4; |
(1) |
2x1 – 2x2 20; |
(2) |
–1x1 + 5x2 40; |
(2) |
5x1 + 2x2 10; |
(2) |
–10x1 + 1x2 10; |
(3) |
3x1 + 5x2 75; |
(3) |
4x1 – 3x2 12; |
(3) |
2x1 – 1x2 50; |
(4) |
5x1 – 1x2 60; |
(4) |
7x1 + 4x2 28; |
(4) |
x1 , x2 0. |
|
2x1 – 5x2 15; |
(5) |
x1 , x2 0. |
|
|
|
x1 , x2 0. |
|
|
|
|
|
|
|
|
|
4. max z = 1x1 + 1x2 ; |
5. max z = 2x1 + 1x2 ; |
6. max z = x1 + 2x2 ; | |||
5x1 – 2x2 10; |
(1) |
1x1 – 1x2 4; |
(1) |
1x1 – 5x2 5; |
(1) |
–1x1 + 1x2 5; |
(2) |
1x1 + 1x2 10; |
(2) |
–3x1 + 1x2 3; |
(2) |
1x1 + 1x2 6; |
(3) |
4x1 – 1x2 12; |
(3) |
–4x1 + 5x2 20; |
(3) |
–1x1 + 1x2 = 1; |
(4) |
7x1 + 1x2 7; |
(4) |
–1x1 + 2x2 10; |
(4) |
x1 , x2 0. |
|
x1 , x2 0. |
|
x1 , x2 0. |
|
|
|
|
|
|
|
7. max z = 10x1 – 4x2 ; |
8. max z = 2x1 – 4x2 ; |
9. max z = 2x1 + 3x2 ; | |||
–2x1 + 1x2 10; |
(1) |
8x1 – 5x2 16; |
(1) |
–2x1 + 1x2 4; |
(1) |
4x1 + 5x2 60; |
(2) |
1x1 + 3x2 2; |
(2) |
3x1 – 8x2 24; |
(2) |
5x1 – 2x2 60; |
(3) |
2x1 + 7x2 9; |
(3) |
x2 3; |
(3) |
2x1 – 5x2 40; |
(4) |
x1 , x2 0. |
|
x1 , x2 0. |
|
x1 , x2 0. |
|
|
|
|
|
|
|
|
|
|
|
10. max z = –2x1 + 1x2 ; |
11. max z = 1x1 + 1x2 ; |
12. max z = –2x1 + 1x2 ; | |||
2x1 + 1x2 8; |
(1) |
1x1 + 1x2 1; |
(1) |
2x1 + 1x2 8; |
(1) |
1x1 + 1x2 6; |
(2) |
–5x1 + 1x2 0; |
(2) |
1x1 + 3x2 6; |
(2) |
–3x1 + 2x2 3; |
(3) |
–1x1 + 5x2 0; |
(3) |
3x1 + 1x2 3; |
(3) |
1x1 1; |
(4) |
1x1 + 1x2 6; |
(4) |
–1x1 + 1x2 = 3; |
(4) |
x1 , x2 0. |
|
x1 , x2 0. |
|
x1 , x2 0. |
|
|
|
|
|
|
|
13. max z = 11x1 + 11x2 ; |
14. max z = 5x1 + 2x2 ; |
15. max z = x1 – 2x2 ; | |||
1x1 + 1x2 4; |
(1) |
2x1 + 1x2 11 ; |
(1) |
–3x1 + 2x2 9 ; |
(1) |
2x1 + 5x2 5; |
(2) |
–3x1 + 2x2 10 ; |
(2) |
3x1 + 4x2 27; |
(2) |
5x1 + 2x2 5; |
(3) |
3x1 + 4x2 12 ; |
(3) |
2x1 + 1x2 12; |
(3) |
1x1 3; |
(4) |
1x1 – 2x2 4 ; |
(4) |
1x2 = 6; |
(4) |
1x2 2; |
(5) |
x1 , x2 0. |
|
x1 , x2 0. |
|
x1 , x2 0. |
|
|
|
|
|
|
|
|
|
|
|
16. max z = 2x1; |
17 max z = 10x1 + 2x2 ; |
18 max z = 2x1 + 3x2 ; | |||
1x1 + 1x2 10; |
(1) |
4x1 – 2x2 5 ; |
(1) |
–2x1 + 1x2 2; |
(1) |
–3x1 + 2x2 6; |
(2) |
–1x1 + 2x2 5 ; |
(2) |
1x1 + 2x2 6; |
(2) |
1x1 + 1x2 3; |
(3) |
1x1 + 1x2 4 ; |
(3) |
1x1 + 2x2 2; |
(3) |
1x1 3; |
(4) |
1x1 + 1x2 2 ; |
(4) |
3x1 + 2x2 6; |
(4) |
1x2 5; |
(5) |
x1 , x2 0. |
|
x1 , x2 0. |
|
x1 , x2 0. |
|
|
|
|
|
|
|
|
|
|
|
19. max z = 2x1 – 1x2 ; |
20. min z = 5x1 + 2x2 ; |
21. max z = 7x1 – 1x2 ; | |||
–1x1 + 1x2 4 ; |
(1) |
1x1 + 7x2 7; |
(1) |
1x1 + 1x2 3; |
(1) |
6x1 + 6x2 36; |
(2) |
–2x1 + 1x2 5; |
(2) |
5x1 + 1x2 5; |
(2) |
2x1 – 3x2 6; |
(3) |
2x1 + 5x2 10; |
(3) |
1x1 + 5x2 5; |
(3) |
1x1 + 1x2 4; |
(4) |
5x1 + 2x2 10 ; |
(4) |
1x1 4; |
(4) |
1x1 + 1x2 = 5; |
(5) |
7x1 + 1x2 7; |
(5) |
1x2 5; |
(5) |
x1 , x2 0. |
|
1x1 5; |
(6) |
x1 , x2 0. |
|
|
|
1x2 5; |
(7) |
|
|
|
|
x1 , x2 0. |
|
|
|
|
|
|
|
|
|
22. min z = 2x1 + 4x2 ; |
23. max z = 2x1 + 2x2 ; |
24. max z = 7x1 + 6x2 ; | |||
3x1 + 1x2 9; |
(1) |
–3x1 + 2x2 6; |
(1) |
1x1 + 1x2 14; |
(1) |
1x1 + 2x2 6; |
(2) |
1x1 + 1x2 3; |
(2) |
3x1 – 5x2 15; |
(2) |
1x1 – 1x2 3; |
(3) |
1x1 3; |
(3) |
6x1 + 3x2 24; |
(3) |
1x2 5; |
(4) |
1x2 5; |
(4) |
1x1 = 15; |
(4) |
x1 , x2 0. |
|
4x1 + 5x2 20; |
(5) |
1x2 10; |
(5) |
|
|
x1 , x2 0. |
|
x1 , x2 0. |
|
Сконструювати дві ЗЛП (записати систему обмежень та розв’язати графічно), у яких поєднання “вид ОДР” – “оптимальний розв’язок” не збігався би із завданнями, отриманими згідно з варіантом. (Кількість обмежень ЗЛП – не менше 3-х).
Сконструювати ЗЛП (записати систему обмежень та розв’язати графічно), в якій ОДР – відрізок, оптимум – точка.
Сконструювати ЗЛП (записати систему обмежень та розв’язати графічно), в якій ОДР – відрізок, оптимум – альтернативний.
Сконструювати ЗЛП (записати систему обмежень та розв’язати графічно), в якій ОДР – промінь, оптимум – точка.
Сконструювати ЗЛП (записати систему обмежень та розв’язати графічно), в якій ОДР – промінь, оптимум – альтернативний.
Сконструювати ЗЛП (записати систему обмежень та розв’язати графічно), в якій ОДР – багатокутник, оптимум – точка.
Сконструювати ЗЛП (записати систему обмежень та розв’язати графічно), в якій ОДР – багатокутник, оптимум – альтернативний.
Навести приклади можливих видів множин допустимих розв’язків ЗЛП та видів множин оптимальних розв’язків у R2 (дати їх графічну ілюстрацію).
Варіанти контрольної роботи подані в табл. 32.
Таблиця 32
Номер варіанта |
Завдання |
Номер варіанта |
Завдання |
1 |
1, 24, 25 |
14 |
11, 14, 25 |
2 |
2, 23, 25 |
15 |
9, 15, 25 |
3 |
3, 22, 25 |
16 |
10, 13, 25 |
4 |
4, 21, 25 |
17 |
8, 16, 25 |
5 |
5, 20, 25 |
18 |
7, 17, 25 |
6 |
6, 19, 25 |
19 |
3, 22, 25 |
7 |
7, 18, 25 |
20 |
4, 18, 25 |
8 |
8, 16, 25 |
21 |
5, 20, 25 |
9 |
9, 17, 25 |
22 |
6, 19, 25 |
10 |
10, 14, 25 |
23 |
2, 11, 25 |
11 |
11, 15, 25 |
24 |
1, 15, 25 |
12 |
12, 13, 25 |
25 |
3, 12, 25 |
13 |
11, 24, 25 |
26 |
1, 21, 25 |
Домашнє завдання. “Основи аналізу на чутливість”. Побудувати математичну модель, розв’язати та виконати постоптимальний аналіз моделі із завдання 1, розд. 1.3.