Задача о кратчайшем маршруте




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

Замечание. Вместо расстояний между населенными пунктами могут быть известны стоимости доставки единицы груза из пункта в пункт, время, затрачиваемое на переезд из пункта в пункт.

В терминах теории графов задачу можно сформулировать следующим образом: между двумя заданными вершинами графа найти цепь с минимальной длиной ребер.

Данная задача может быть решена методом динамического программирования (тема 35, п. 35.2) с минимизируемой целевой функцией, выражающей стоимость затрат на перевозку единицы груза из начального пункта в пункт назначения.

Пример 36.10. Найти наиболее экономный маршрут перевозки груза из города в город и стоимость перевозки для сети дорог, показанной на рис. 36.14. Над ребрами сети указаны стоимости перевозки единицы груза из одного города в другой (в ден. ед.).

Решение. Математическая модель задачи. Система S: транспорт с грузом, который нужно переместить из пункта в пункт , и сеть дорог, соединяющая эти пункты.

Представим процесс перевозки груза как многошаговый процесс. Для этого сгруппируем населенные пункты следующим образом. К группе отнесем пункт , к группе все пункты, в которые можно попасть из , то есть и . К группе – все пункты, куда можно попасть из и , то есть , , . В группу – все, куда можно попасть из , , , то есть , , . К группе – пункт . Результат группировки удобно представить в виде таблицы:

   
     

Тогда движение транспорта с грузом из пункта в пункт можно представить как -шаговый процесс: на первом шаге груз перемещают из пункта группы в пункт группы ; на втором шаге – из пункта группы в пункт группы ; на третьем шаге – из пункта группы в пункт группы ; на четвертом шаге – из пункта группы в пункт группы . Таким образом, формирование наиболее экономного маршрута может быть реализовано за шага.

Составленная таблица содержит сведения о множестве состояний – множестве местонахождений транспорта с грузом в некотором пункте группы с номером . Множество начальных состояний . Множество конечных состояний . Множество состояний в начале -го шага: – множество пунктов группы с номером (откуда выезжает транспорт с грузом). Управление на -м шаге: выбор дороги , по которой следует направить груз из данного населенного пункта в соседний в общем направлении к пункту . Множество состояний в конце -го шага: – множество пунктов группы с номером (куда прибывает транспорт с грузом в результате принятого управления). Целевая функция на -м шаге – затраты на перевозку единицы груза из данного пункта в выбранный соседний пункт. Рекуррентные соотношения Р. Беллмана имеют вид

Воспользуемся алгоритмом метода динамического программирования.

Условная оптимизация

1) На четвертом шаге требуется найти условно оптимальные значения целевой функции при транспортировке груза из пунктов группы в . Тогда управление – выбор дороги для доставки. Условно оптимальные значения целевой функции равны затратам при передвижении по этим дорогам. Целевая функция однозначна на каждом шаге. Вычисления проведем в виде таблицы:

Таблица 36.1

 
 
 

2) На третьем шаге требуется найти условно оптимальные значения целевой функции при транспортировке груза из пунктов группы в , причем путь из пунктов группы в уже оптимизирован и представлен в последнем столбце табл. 36.1. Вычисления проведем в виде таблицы:

Таблица 36.2

       
       
       
       
       
       

3) На втором шаге требуется найти условно оптимальные значения целевой функции при транспортировке груза из пунктов группы в , причем путь из пунктов группы через пункты группы в уже оптимизирован и представлен в последнем столбце табл. 36.2. Вычисления проведем в виде таблицы:

Таблица 36.3

       
       
       
       
       

На первом шаге требуется найти условно оптимальные значения целевой функции при транспортировке груза из пункта в пункт , причем путь из пунктов группы через пункты групп и в уже оптимизирован и представлен в последнем столбце табл. 36.3. Вычисления проведем в виде таблицы:

Таблица 36.4

       
       

Этап условной оптимизации завершен.

Безусловная оптимизация

Проанализируем результаты вычислений. Согласно табл. 36.4 получаем, что минимальная стоимость перевозки груза из пункта в пункт равна ден. ед. Этой стоимости соответствует дорога . В табл. 36.3, в строке , находим минимальную стоимость перевозки на оставшемся пути ден. ед., ей соответствует дорога . В табл. 36.2, в строке , минимальной стоимости оставшегося пути ден. ед. соответствует две дороги или . В табл. 36.1 строке соответствует минимальная стоимость оставшегося пути ден. ед. и дорога , а строке – минимальная стоимость ден. ед. и дорога .

Ответ. Минимальная стоимость перевозки груза из пункта в пункт 14 ден. ед. Наиболее экономные маршруты: и .

 

Теоретический материал: [2, гл. 30], [10, гл. 4], [12, гл. 30], [22, гл. 4], [24, гл. 2], [26, гл. 3], [28].

 



Поделиться:




Поиск по сайту

©2015-2024 poisk-ru.ru
Все права принадлежать их авторам. Данный сайт не претендует на авторства, а предоставляет бесплатное использование.
Дата создания страницы: 2019-04-14 Нарушение авторских прав и Нарушение персональных данных


Поиск по сайту: