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

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

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

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

Рис. 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.

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

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

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

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

Задача транспортировки груза по сети дорог. - student2.ru Задача транспортировки груза по сети дорог. - student2.ru Задача транспортировки груза по сети дорог. - student2.ru Задача транспортировки груза по сети дорог. - student2.ru
п.7 п.8 п.9 (7,10) (8,10) (9,10) п.10 п.10 п.10

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

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

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

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

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

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

F3 (x2, u3) = min (7+3; 5+9) = 10,

(4,7) (4,8)

F3(x2, u3) = min (2+3; 4+9; 8+6) = 5,

(5,7) (5,8)(5,9)

F3(x2, u3) = min (2+9) =11.

(6,8)

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

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

Задача транспортировки груза по сети дорог. - student2.ru Задача транспортировки груза по сети дорог. - student2.ru Задача транспортировки груза по сети дорог. - student2.ru Задача транспортировки груза по сети дорог. - student2.ru Задача транспортировки груза по сети дорог. - student2.ru Задача транспортировки груза по сети дорог. - student2.ru Задача транспортировки груза по сети дорог. - student2.ru
п.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-го шага.

Задача транспортировки груза по сети дорог. - student2.ru Задача транспортировки груза по сети дорог. - student2.ru Задача транспортировки груза по сети дорог. - student2.ru Задача транспортировки груза по сети дорог. - student2.ru Задача транспортировки груза по сети дорог. - student2.ru Задача транспортировки груза по сети дорог. - student2.ru Задача транспортировки груза по сети дорог. - student2.ru
п.2 (2,4) (2,5) п.4 п.5 -
  п.3 (3,4) (3,5) (3,6) п.4 п.5 п.6 - -

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

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

Задача транспортировки груза по сети дорог. - student2.ru Задача транспортировки груза по сети дорог. - student2.ru Задача транспортировки груза по сети дорог. - student2.ru Задача транспортировки груза по сети дорог. - student2.ru Задача транспортировки груза по сети дорог. - student2.ru Задача транспортировки груза по сети дорог. - student2.ru Задача транспортировки груза по сети дорог. - student2.ru
п.1 (1,2) (1,3) п.2 п.3 -

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



Наши рекомендации