Транспортна задача у сітьовій постановці
Транспортну задачу можна зобразити графом, на якому кожна дуга має значення Транспортна задача у сітьовій постановці відображається такою математичною моделлю: де Напрямок переміщування вантажу вказується дугою. До графу також входять вершини, які не відображують постачальника чи споживача; такі вершини є проміжними з нульовими запасами чи потребами (так звані перевалочні бази). Для знаходження оптимального варіанта згідно з графом транспортної задачі будується який-небудь перший розв’язок цієї задачі з урахуванням ребер неорієнтовного графа та значень
Якщо для усіх ребер графа Розміщення значень Якщо план довільний
Приклад. Нехай є транспортна задача у сітьовій постановці (рис. 8.11).
Рис.8.11 Перший базисний розв’язок має вигляд (рис. 8.12).
20 20 Рис.8.12 Перевірка:
Для ребра (14) будується дуга(14), потім для неї знаходиться цикл (1, 4, 2, 5, 3) та обчислюється Дузі (14) надається значення Будується новий план розподілу ресурсів (рис. 8.13).
Рис.8.13
Висновки
1. Теорія графів в частиною загальної теорії дискретної математики. 2. Для ряду прикладних задач ефективно використовувати спеціальні методи теорії графів, які враховують особливості структури сітьових постановок. Математичний апарат теорії графів дозволяє розв’язувати задачі, які пов’язані з питаннями максимізації обсягів перевезення вантажу, знаходженням найкоротшої відстані постачання вантажу, оптимізацією структур, взаємозв’язків між елементами та ін. 3. Методи розв’язування задач у сітьовій постановці мають форму рекурсивних обчислювань, що легко піддається процесу алгоритмізації та реалізації розв’язування таких задач на ЕОМ.
Контрольні запитання 1. Які зустрічаються типи графів? 2. Що таке ізоморфність графів? 3. Які існують відображення графів? 4. Що таке зважений граф? 5. Що таке розріз мережі? 6. Яка основна ідея методи Форда-Фалкерсона? 7. Що таке максимальний потік мережі?
8. На чому базується метод розв’язування задачі про найкоротшу відстань?
РОЗДІЛ 9
Читайте также: IV. Четвертый вопрос – типовая задача. Воспользуйтесь поиском по сайту: ![]() ©2015 - 2025 megalektsii.ru Все авторские права принадлежат авторам лекционных материалов. Обратная связь с нами...
|