Задачи по методам принятия решений

 

1. Изобразите на плоскости ограничения задачи линейного программирования и решите (графически) эту задачу:

400 W₁ + 450 W₂ → min ,

5 W₁ + 10 W₂ ≥ 45,

20 W₁ + 15 W₂ ≥ 80,

W₁ ≥ 0, W₂ ≥ 0.

2. Решите задачу линейного программирования:

W₁ + 5 W₂ → max ,

0,1 W₁ + W₂ ≤ 3,8 ,

0,25 W₁ + 0,25 W₂ ≤ 4,2 ,

W₁ ≥ 0 , W₂ ≥ 0 .

3. Решите задачу целочисленного программирования:

10 Х + 5 У → max .

8 Х + 3 У ≤ 40,

3 Х + 10 У ≤ 30,

Х ≥ 0 , У ≥ 0 , Х и У - целые числа.

4. Решите задачу о ранце:

Х₁ + Х₂ + 2 Х₃ + 2Х₄ + Х₅ + Х₆ → max ,

0,5 Х₁ + Х₂ + 1,5 Х₃ + 2Х₄ + 2,5Х₅ + 3Х₆ ≤ 3.

Управляющие параметры Х_k, k = 1,2,…, 6 , принимают значения из множества, содержащего два элемента - 0 и 1.

5. Решите задачу коммивояжера для четырех городов (маршрут должен быть замкнутым и не содержать повторных посещений). Затраты на проезд приведены в табл.7.

 

Таблица 7.

Исходные данные к задаче коммивояжера

Город отправления	Город назначения	Затраты на проезд
А	Б
А	В
А	Д
Б	А
Б	В
Б	Д
В	А
В	Б
В	Д
Д	А
Д	Б
Д	В

 

6. Транспортная сеть (с указанием расстояний) приведена на рис.9. Найдите кратчайший путь из пункта 1 в пункт 4.

 

 

 

 

Рис.9. Исходные данные к задаче о кратчайшем пути.

 

7. Как послать максимальное количество грузов из начального пункта 1 в конечный пункт 8, если пропускная способность путей между пунктами транспортной сети (рис.10) ограничена (табл.8)?

 

 

Рис.10. Транспортная сеть к задаче о максимальном потоке.

 

Таблица 8.

Исходные данные к задаче о максимальном потоке

Пункт отправления	Пункт назначения	Пропускная способность