Описание
8. ОПТИМИЗАЦИОННЫЕ ЗАДАЧИ
Задания
1. Изобразите на плоскости ограничения задачи линейного программирования и решите (графически) эту задачу:
400W1 + 450W2 min
5W1 + 10W2 ≥ 45
20W1 + 15W2 ≥ 80
W1 ≥ 0, W2 ≥ 0
2. Решите задачу линейного программирования:
W1 + 5W2 max
0,1W1 + W2 ≤ 3,8
0,25W1 + 0,25W2 ≤ 4,2
W1 ≥ 0, W2 ≥ 0
3. Решите задачу целочисленного программирования:
10X + 5Y max
8X + 3Y ≤ 40
3X +10Y ≤ 30
X ≥ 0, Y ≥ 0
X и Y — целые числа
4. Решите задачу о ранце:
X1 + X2 + 2X3 + 2X4 + X5 + X6 max
0,5X1 + X2 + 1,5X3 + 2X4 + 2,5X5 + 3X6 ≤ 3
Управляющие параметры Xk, k=1,2,3,4,5,6, принимают значения из множества, содержащего два элемента — 0 и 1.
5. Транспортная сеть (с указанием расстояний) приведена на рис. 8.9. Найдите кратчайший путь из пункта 1 в пункт 4.
6. Как послать максимальное количество грузов из начального пункта 1 в конечный пункт 8, если пропускная способность путей между пунктами транспортной сети (рис. 8.10) ограничена (табл. 8.7)?
Таблица 8.7
Исходные данные к задаче о максимальном потоке
| Пункт отправления |
Пункт назначения |
Пропускная способность |
| 1 | 2 | 1 |
| 1 | 3 | 2 |
| 1 | 4 | 3 |
| 2 | 5 | 2 |
| 3 | 2 | 2 |
| 3 | 4 | 2 |
| 3 | 6 | 1 |
| 4 | 7 | 4 |
| 5 | 8 | 3 |
| 6 | 5 | 2 |
| 6 | 7 | 1 |
| 6 | 8 | 1 |
| 7 | 8 | 3 |
7. Решите задачу коммивояжера для четырех городов (маршрут должен быть замкнутым и не содержать повторных посещений). Затраты на проезд приведены в табл. 8.8.
Таблица 8.8
Исходные данные к задаче коммивояжера
| Город отправления | Город назначения | Затраты на проезд |
| А | Б | 2 |
| А | В | 1 |
| А | Д | 5 |
| Б | А | 3 |
| Б | В | 2 |
| Б | Д | 1 |
| В | А | 4 |
| В | Б | 1 |
| В | Д | 2 |
| Д | Ф | 5 |
| Д | Б | 3 |
| Д | В | 3 |
