Задача транспортировки груза по сети дорог.

 

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

На рисунке 10 изображена сеть дорог, по которой должен перемещаться транспорт с грузом. Над ребрами сети указаны тарифы.

 

 

 

Рис. 10. Схема дорожной сети.

 

В рассматриваемой задаче используется хронологический принцип выделения шагов, что объясняется физическим смыслом ситуации. Для выделения щагов воспользуемся следующим подходом. Разобьем все пункты сети на группы. К группе 0 отнесем п.1; к группе 1 – пункты, в которые можно попасть непосредственно из п.1; к группе 2 – пункты, в которые можно попасть непосредственно из любого пункта группы 1 и т. д. (см. таблицу 10).

Табл. 10. Группировка пунктов дорожной сети.

Группа 0	Группа 1	Группа 2	Группа 3	Группа 4
п.1	п.2 п.3	п.4 п.5 п.6	п.7 п.8 п.9	п.10

 

Шагом процесса будем считать перевод транспорта из пунктов предшествующей группы в пункты последующей группы. В результате в данной задаче можно выделить 4 шага, которые показаны на рисунке 10.

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

Поиск решения начинается с условной оптимизации, в ходе которой процесс анализируется в обратном порядке – от 4-го шага к 1-му. Решение удобно оформлять с помощью таблиц. Каждая таблица отражает элементы обозначенных ранее множеств и завершается выбором условно-оптимальных значений целевой функции.

Таблица 11 содержит анализ 4-го шага.

 

 

Табл. 11. Анализ 4-го шага.

п.7 п.8 п.9	(7,10) (8,10) (9,10)	п.10 п.10 п.10

 

 

Перейдем к анализу третьего шага. Из рисунка видно, что множество включает нахождение груза либо в п.4, либо в п.5, либо в п.6. Множество включает выбор дорог, ведущих из п.п.4, 5, 6 в п.п. 7, 8, 9. Для п.4 это дороги (4,7) или (4,8); для п.5 – (5,7) или (5,8) или (5,9); для п.6 – (6,8). Множество значений состоит из тарифов на перевозку единицы груза по соответствующей дороге.

Условно-оптимальное управление на третьем шаге для каждого из возможных состояний найдем следующим образом. Рассмотрим любое из состояний множества . Для перевода системы в состояние множества существуют следующие возможности:

- из п.4 - (4,7) или (4,8);

- из п.5 - (5;7) или (5,8) или (5,9);

- из п.6 - (6,8).

Используя результаты условной оптимизации 4-го шага, получаем:

F₃ (x₂, u₃) = min (7+3; 5+9) = 10,

^{(4,7) (4,8)}

F₃(x_2, u₃) = min (2+3; 4+9; 8+6) = 5,

^{(5,7) (5,8)(5,9)}

F₃(x_2, u₃) = min (2+9) =11.

^(6,8)

Оформим данные рассуждения в виде таблицы анализа 3-го шага (табл. 12).

Таблица 12. Анализ 3-го шага.

п.4	(4,7) (4,8)	п.7 п.8				-
п.5	(5,7) (5,8) (5,9)	п.7 п.8 п.9				- -
п.6	(6,8)	п.8

 

 

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

Таблица 13. Анализ 2-го шага.

п.2	(2,4) (2,5)	п.4 п.5				-
п.3	(3,4) (3,5) (3,6)	п.4 п.5 п.6				- -

 

 

Заключительный этап условной оптимизации - анализ 1-го шага отражен в таблице 14. Итог условной оптимизации – экстремальное значение целевой функции. В данном случае это минимальная стоимость транспортировки груза, которая составляет 11 денежных единиц.

 

 

Таблица 14. Анализ 1-го шага.

 

п.1	(1,2) (1,3)	п.2 п.3				-

 

 

Итак, минимальная стоимость транспортировки определена. Теперь с помощью безусловной оптимизации пройдем процесс в прямом направлении – от 1-го шага к 4-му, путем рассмотрения тех же самых таблиц в обозначенном порядке. Это позволит нам определить вектор оптимальных управлений, или оптимальный маршрут. В выборе компонентов вектора оптимальных управлений следует ориентироваться на условно- оптимальное значение целевой функции и решение, принятое на предшествующем шаге. Так, в таблице 14 определяется по минимальному значению В таблице 13 выбирается на основе управления на 1-ом шаге и условно-оптимального значения целевой функции. В последующих таблицах – аналогично. Таким образом, .