Лабораторна робота №15, Потік мінімальної вартості

« Назад

Теоретична довідка

Це класична потокова задача, де дуги сітки характеризуються питомими витратами на перевезення і пропускною здатністю.

Нормовані вартості нульових ділянок вказують на збільшення загальних витрат при примусовому включенні їх у маршрут. Нормовані вартості не нульових ділянок вказують на зменшення загальних витрат, оскільки вони обмежені пропускною здатністю.

Тіньові ціни для потенціалів вузлів вказують на збільшення або зменшення загальних витрат за умови розміщення джерела у відповідному вузлі.

Задача 1. Потік мінімальної вартості

Завдання

Необхідно визначити оптимальні маршрути доставки заданого обсягу з вузла-джерела в вузол-сток мінімальної загальної вартості. Всі проміжні вузли мають нульові потенціали і є суто транзитними.

Постановка:

Транспортна мережа задана змішано-орієнтованою сіткою,

Початкові дані мають відомості про мережу, що складається з 12 вузлів і 22 спрямованих дуг.

Для першого вузла задано пропозиція (100), для останнього - попит (- 100), потенціали всіх інших - нуль (вони транзитні).

Для дуг задані питомі витрати на перевезення ними вантажу і їх пропускну здатність.

Знайти потік перевезення вантажу, щоб

1. Загальні витрати = Потік*Витрати → min

2. При обмеженні:

- Вихід - Вхід (Сума) = Попит / Пропозиція;

- Потоки <= Пропускна здатність;

- Потоки> = 0.

Хід роботи

1. Витрати на перевезення кожної із дуг задаються довільно.

2. Для обчислення потоку в вузлах використовують функцію обчислення суми величин, координати яких задовольняють певні умови (тобто, якщо певна величина належить відповідній множині). (суммесли).

Рис. 1 – Задача про потік мінімальної вартості, Excel

Контрольні запитання

1. Які способи розв’язування мережних задач вам відомі?

2. Що таке вузол?

3. Який граф ми називаємо орієнтованим?

4. Що таке петля?

5. Які параметри дуг можливі?

6. Що таке потенціал вузла?

7. В чому полягає суть задачі про Кенігзберські мости?