Задача про вибір найбільш економного маршруту постачання вантажу

На даній мережі доріг є декілька маршрутів, якими можна постачати вантаж з пункту 1 в пункт N . Відомі вартості перевезення одиниці вантажу між окремими проміжними пунктами мережі. Потрібно вибрати в мережі такий маршрут постачання вантажу з пункту 1 в пункт N, якому відповідають найменші витрати.

Для розв'язування задачі методом ДП розіб'ємо всі пункти мережі на групи. До першої групи віднесемо пункт 1; до другої – пункти, в які можна попасти безпосередньо з пункту 1; до третьої – пункти, в які можна попасти безпосередньо з будь-якого пункту другої групи і т.д. В результаті рух транспорту з вантажем з пункту 1 в пункт набуде поетапного характеру: на першому етапі транспорт рухається з пункту 1 в деякий пункт другої групи, на другому етапі – з пункту другої групи в пункт третьої групи і т.д. Разом з тим і процес знаходження найбільш економного маршруту з пункту 1 в пункт розпадається на етапи. На кожному етапі потрібно так вибрати маршрут, щоб затрати на постачання вантажу були мінімальними. Так вибраний підхід до розв'язування задачі враховує особливості мережі.

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

Читайте також:

<== попередня сторінка	\|	наступна сторінка ==>
Задача про збільшення виробничих потужностей за рахунок відрахувань з прибутку	\|	Задача мінімізації витрат пального літаком при набиранні висоти і швидкості

Не знайшли потрібну інформацію? Скористайтесь пошуком google:

Генерація сторінки за: 0.005 сек.