span align="justify">) необхідно доставити по підприємствах - вантажоодержувачам (А 2 , А 3 , А 4 , Б 1 , ... Б7) пакетований вантаж (кріплення, mбр = 100 кг.). Вантажомісткість використовуваних автомобілів 1000 кг (10 пакетів).
Необхідно:
Використовуючи модель транспортної мережі і найкоротші відстані між вершинами транспортної мережі (з частини 1), сформувати за критерієм мінімуму сумарного пробігу систему развозочних маршрутів при доставці вантажу з товарного складу (вершина А 1 ) вантажоодержувачам. Потреби у вантажі наводяться в таблиці 1.
лінійне програмування грузоперевозка
1. Визначення найкоротшого відстані між ГО і ДП
Метод потенціалів.
Метод заснований на приписуванні вершин тимчасових позначок, які дають верхню межу довжини від початкової вершини до цієї вершини.
Алгоритм визначення найкоротших відстаней методом потенціалів:
. Початковій точці мережі, за яку може бути прийнята будь-яка з вершин, привласнюють потенціал, рівний нулю ( v i = 0 ).
. Визначають потенціали сусідніх з початковою точкою вершин мережі за формулою
v j = v i < span align = "justify"> + l ij ,
де:
v i - потенціал попередньої (сусідній) вершини;
l ij - довжина ланки, що з'єднує вершини i і j.
З них вибирають найменший потенціал і привласнюють його відповідної вершині. Обраний потенціал визначає найкоротша відстань від початкової точки до даної, на мережі цей зв'язок відзначають стрілкою. p align="justify">. Визначають потенціали вершин, сусідніх з обраної вершиною, і з усієї сукупності потенціалів вибирають найменший, який проставляють у відповідній вершини і т.д.
Повне рішення задачі включає стільки етапів, скільки вершин включає транспортна мережа, оскільки щоразу визначають найкоротші відстані від початкової точки до інших.
Найкоротші відстані від точки А1.
