- •Методичнi вказiвки до самостійної роботи з дисциплiни «Математичні методи дослідження операцій»
- •Методичнi вказiвки до самостійної роботи з дисциплiни «Математичні методи дослідження операцій»
- •1. Двоїстий симплекс-метод
- •1.1. Схема двоїстого симплекс-методу для задачі максимізації цф
- •1.2. Сфера застосування двоїстого симплекс-методу
- •1.3. Приклад застосування двоїстого симплекс-методу
- •1.4. Додавання нового обмеження
- •1.6. Контрольні завдання
- •1.5. Завдання до самостійної роботи
- •Варіанти завдань
- •2. Алгоритм Гоморі
- •Проблемы, возникающие при округлении решения злп
- •2.1. Загальна характеристика методів відсікання
- •2.2. Метод відсікання Гоморі
- •2.3. Схема алгоритму Гоморі
- •2.4. Эффективность отсечения Гомори
- •2.5. Приклади застосування алгоритму Гоморі Приклад 5. Max ; (25)
- •2.6. Вправи
- •2.7. Контрольні запитання
- •2.8. Завдання для контрольної роботи
- •Список літератури
- •1. Двоїстий симплекс-метод 3
- •2. Алгоритм Гоморі 17
1.5. Завдання до самостійної роботи
Додати до оптимальної симплекс-таблиці додаткове обмеження, згідно зі своїм варіантом (див. табл. 10).
Таблиця 10
Базисні змінні |
|
|
|
|
|
Розв’язок |
Z |
0 |
0 |
-3/5 |
-4/5 |
0 |
5 |
|
1 |
0 |
1/5 |
-2/5 |
0 |
1 |
|
0 |
1 |
-2/5 |
-1/5 |
0 |
2 |
|
0 |
0 |
2/5 |
11/5 |
1 |
14 |
Варіанти завдань
№ 1 -x1 + 2x2 8 . № 2 x1 - x2 1 .
№ 3 x1 + x2 6 . № 4 4x1 - x2 -4 .
№ 5 3x1 + 2x2 6 . № 6 4x1 - 3x2 3 .
№7 x1 x2 . № 8 x1 + 3x2 3 .
№ 9 3x1 - x2 9 . № 10 5x1 + 4 x2 20 .
№ 11 x2 5 . № 12 4x1 + x2 2 .
№ 13 x1 + 3x2 12 . № 14 x1 4 .
№ 15 -6x1 + x2 6 . № 16 x1 3 .
1.6. Контрольні завдання
Розв’язати ЗЛП. Додати (незалежно одне від іншого) до неї додаткові обмеження та розв’язати розширені задачі. Дати графічну ілюстрацію розв’язання задач.
№ 1 min z= x1 + 2x2 ; 3x1 + x2 5 ; x1 4 ; x2 10 ; x1 ,x2 0, Додаткові обмеження : 1) x1 3 ; 2) x1 + x2 1. |
№ 2 min z= x1 + x2 ; x1 + 2x2 6 ; 2x1 + x2 4 ; x1 ,x2 0, Додаткові обмеження : 1) x1 3 ; 2) x1 + x2 1. |
№ 3 min z= x1 + x2 ;
x1 3 ; x2 6 ; x1 ,x2 0, Додаткові обмеження : 1) x2 4 ; 2) x1 + x2 4. |
№ 4 min z= 3x1 + 2x2 ; 2x1 + 3x2 10 ; x1 - x2 3 ; x1 ,x2 0, Додаткові обмеження : 1) x1 + x2 10 ; 2) x1 + x2 2. |
№ 5 min z= 2x1 + 3x2 ; 5x1 + 2x2 10 ; x1 + 3x2 12 ; x1 ,x2 0, Додаткові обмеження : 1) x1 1 ; 2) x1 + x2 15. |
№ 6 min z= 3x1 + 2x2 ;
x1 + x2 4 ; x1 + x2 8 ; x1 ,x2 0, Додаткові обмеження : 1) x1 + x2 6 ; 2) x1 + x2 10. |
№ 7 min z= x1 + x2 ; 2x1 + 4x2 8 ; x1 2 ; x1 ,x2 0, Додаткові обмеження : 1) x1 + x2 1 ; 2) x1 3. |
№ 8 min z= x1 + 2x2 ; 3x1 + x2 3 ; x1 + 2x2 6 ; x1 ,x2 0, Додаткові обмеження : 1) x1 3 ; 2) x1+ x2 8. |
№ 9 min z= x1 + x2 ; 2x1 + x2 4 ; x1 + 2x2 6 ; x1 ,x2 0, Додаткові обмеження : x2 1 ; 2) x1 7. |
№ 10 min z= 6x1 + 4x2 ; 2x1 + x2 3 ; x1 – x2 1 ; –x1 + 2x2 1 ; x1 ,x2 0, Додаткові обмеження : 1) x2 7 ; 2) x1 1. |
№ 11 min z= 2x1 + 3x2 ; 4x1 – x2 7 ; 3x1 + x2 7 ; x1 – 2x2 –7; x1 ,x2 0, Додаткові обмеження : 1) x1 + x2 4 ; 2) x1 + x2 12. |
№ 12 max z= –3x1 – 2x2 ; x1 – x2 0 ; x1 + x2 16 ; x2 6 ; x1 ,x2 0, Додаткові обмеження : 1) x1 + x2 13 ; 2) x1 9. |
№ 13 max z= –2 x1 – x2 ; 2x1 + 6x2 12 ; 6x1 + 4x2 24 ; x1 5 ; x1 ,x2 0, Додаткові обмеження : 1) x1 + x2 1 ; 2) x2 4. |
№ 14 max z= –2x1 – 3x2 ; x1 1 ; x2 2 ; x1 ,x2 0, Додаткові обмеження : 1) x1 + x2 2 ; 2) x1 + x2 4. |
№ 15 min z= 2x1 + x2 ; x1 + x2 15 ; x1 – x2 0 ; x2 5 ; x1 ,x2 0, Додаткові обмеження : 1) 3x1 + 2x2 6 ; 2) x2 6. |
№ 16 –2x1 + x2 2 ; 3x1 + 7x2 21 ; x1 4 ; x1 ,x2 0, Додаткові обмеження : 1) x2 2 ; 2) x1 + x2 2. |
№ 17 max z= –3x1 – x2 ; 5x1 + x2 5 ; x1 + 5x2 5 ; x1 + x2 3 ; x1 ,x2 0, Додаткові обмеження : 1) x2 1 ; 2) x2 3. |
№ 18 max z= –2 x1 – x2 ; 3x1 + x2 5 ; x1 4 ; x2 10 ; x1 ,x2 0, Додаткові обмеження : 1) 3x1 + x2 9 ; 2) x1 5. |
№ 19 max z= – x1 – 2x2 ; x1 + 2x2 20 ; x1 5 ; x2 3 ; x1 ,x2 0, Додаткові обмеження : 1) x1 + x2 1 ; 2) x1 + x2 7. |
№ 20 min z= x1 + 2x2 ; x1 + x2 1 ; x2 2 ; x1 + x2 5 ; x1 ,x2 0, Додаткові обмеження : 1) x1 + x2 4 ; 2) x1 6. |
№ 21 min z= x1 + 3x2 ; x1 + x2 4 ; x1 - x2 0 ; x2 4 ; x1 ,x2 0, Додаткові обмеження : 1) x1 3 ; 2) x1+ 2x2 2. |
№ 22 min z= x1 + 2x2 ; 3x1 + 2x2 6 ; x1 - x2 0 ; x1 ,x2 0, Додаткові обмеження : 1) x1 2 ; 2) x1 + x2 1. |
№ 23 min z= 5x1 + x2 ; 4x1 + 3x2 12 ; x1 3 ; x2 3 ; x1 ,x2 0, Додаткові обмеження : 1) x1 + x2 1 ; 2) x1 2. |
№ 24 min z= x1 + 2x2 ; x1 + x2 2 ; 4x1 + 7x2 28 ; x2 1 ; x1 ,x2 0, Додаткові обмеження : 1) x1 + x2 8 ; 2) 2x1 + 3x2 6. |
№ 25 max z= -3x1 - x2 ; x2 1 ; x2 3 ; x1 + x2 4 ; x1 ,x2 0, Додаткові обмеження : 1) x1 + x2 1 ; 2) 2x1 + 3x2 12. |
№ 26 max z= -x1 - 3x2 ; 2x1 + 3x2 6 ; x1 2 ; x1 ,x2 0, Додаткові обмеження : 1) x2 3 ; 2) x1 + x2 1. |
