Транспорт: история и современность

Единая транспортная система

Страница 1

Из аэропорта должны вылететь пять воздушных судов (ВС) для доставки груза в пять городов. Затраты на полёт каждого из самолётов в каждый город представлены в табл. 1. Необходимо назначит ВС на рейсы таким образом, чтобы суммарные затраты на транспортировку грузов были минимальными.

Для создания математической модели обозначим назначение i-го самолёта для полёта в j-й город через хij. Так как количество самолётов равно количеству городов, и каждый самолёт может быть направлен только в один город, то хij принимает только два значения: единицу, если i-й самолёт направлен в j-й город, или нулю, в других случаях. Поэтому и . Суммарная стоимость полётов можно представить в виде суммы .

Итак, задачу можно сформулировать таким образом: найти минимальную суммарную стоимость транспортировки грузов при следующих ограничениях:

, , .

Такие задачи транспортного типа носят название задач о назначениях. В настоящей работе для их решения предлагается так называемый метод ПС, предложенный Петруниным С.В. Применение метода к задаче о назначении состоит из 2 этапов: 1) нахождение элемента, не входящего в оптимальный план (т.е., равного нулю); 2) изменения коэффициента этого элемента в целевой функции.

Введём некоторые определения. Нулевым элементом назовём переменную, которая равна нулю в оптимальном (или в оптимальных) решении. Основной строкой (столбцом) назовём строку (столбец), в которой определяется нулевой элемент. Базовой строкой (столбцом) назовём строку (столбец), с элементами которой сравниваются элементы основной строки при поиске нулевого элемента.

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

Сущность второго этапа заключается в том, что находят новое значение коэффициента целевой функции для найденного элемента. Оно будет равно сумме соответствующего коэффициента базовой строки и следующей по величине значению разности.

Более детально применение метода приведём на следующем примере. Представим условие задачи в виде таблицы с коэффициентами целевой функции (табл. 1).

Таблица 1. Затраты на полёт каждого из самолётов (тыс. руб.) в каждый из пяти городов

Будем рассматривать разности коэффициентов первой строки со второй.

131–511=-380

530–355=175

439–329=110

252–162=90

655–715=-60

В соответствии со сказанным выше, элемент х12 не входит в оптимальный план, т.е. х12=0. следующая по величине разность равна 110. Поэтому с12=355+110=465. (Договоримся новые значения сij вписывать в ту же клеточку, но выделять их жирным шрифтом) (табл. 2)

Таблица 2

План формирования поездов
Поезда формируются по назначениям плана формирования, который задается станции. План формирования для станции С приведен в табл. 1. Согласно этому плану станция формирует на три направления (А, Е, И) поезда 12 назначений. При среднем составе поезда 68 вагонов имеем 33 поездов в сутки, причем 27 пое ...

Таблицы кодирования ТУ
В таблице 3 приведены команды ТУ для данной станции. Станция оборудована системой ЭЦК-2003 и перегон с автоблокировкой КЭБ1. Приняты следующие обозначения команд: Н, Ч, Н№, Ч№, М№ – выбор светофора начала маршрута (№ - номер пути отправления или светофора); ДП, ДМ – выбор категории маршрута (поездн ...

Расчет показателей экономической эффективности
Для определения экономической целесообразности введения светофорного регулирования находится коэффициент экономической эффективности Е, срок окупаемости затрат Т, годовой экономический эффект Эгод. Суммарные текущие затраты до осуществления мероприятий, то есть на нерегулируемом перекрестке, опреде ...