Единая транспортная системаСтраница 1
Из аэропорта должны вылететь пять воздушных судов (ВС) для доставки груза в пять городов. Затраты на полёт каждого из самолётов в каждый город представлены в табл. 1. Необходимо назначит ВС на рейсы таким образом, чтобы суммарные затраты на транспортировку грузов были минимальными.
Для создания математической модели обозначим назначение i-го самолёта для полёта в j-й город через хij. Так как количество самолётов равно количеству городов, и каждый самолёт может быть направлен только в один город, то хij принимает только два значения: единицу, если i-й самолёт направлен в j-й город, или нулю, в других случаях. Поэтому и . Суммарная стоимость полётов можно представить в виде суммы .
Итак, задачу можно сформулировать таким образом: найти минимальную суммарную стоимость транспортировки грузов при следующих ограничениях:
, , .
Такие задачи транспортного типа носят название задач о назначениях. В настоящей работе для их решения предлагается так называемый метод ПС, предложенный Петруниным С.В. Применение метода к задаче о назначении состоит из 2 этапов: 1) нахождение элемента, не входящего в оптимальный план (т.е., равного нулю); 2) изменения коэффициента этого элемента в целевой функции.
Введём некоторые определения. Нулевым элементом назовём переменную, которая равна нулю в оптимальном (или в оптимальных) решении. Основной строкой (столбцом) назовём строку (столбец), в которой определяется нулевой элемент. Базовой строкой (столбцом) назовём строку (столбец), с элементами которой сравниваются элементы основной строки при поиске нулевого элемента.
Первый этап состоит в том, что сравниваются разности коэффициентов целевой функции основной и базовой строк во всех столбцах. Тот элемент основной строки, который соответствует наибольшей разности, не войдёт в оптимальный план. Затем то же проводим для столбцов.
Сущность второго этапа заключается в том, что находят новое значение коэффициента целевой функции для найденного элемента. Оно будет равно сумме соответствующего коэффициента базовой строки и следующей по величине значению разности.
Более детально применение метода приведём на следующем примере. Представим условие задачи в виде таблицы с коэффициентами целевой функции (табл. 1).
Таблица 1. Затраты на полёт каждого из самолётов (тыс. руб.) в каждый из пяти городов
ГОРОДА САМОЛЁТЫ |
1 |
2 |
3 |
4 |
5 |
1 |
131 |
530 |
439 |
252 |
655 |
2 |
511 |
355 |
329 |
162 |
715 |
3 |
112 |
143 |
343 |
644 |
670 |
4 |
411 |
236 |
334 |
380 |
671 |
5 |
150 |
335 |
530 |
458 |
800 |
Будем рассматривать разности коэффициентов первой строки со второй.
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 |
2 |
3 |
4 |
5 |
1 |
131 54 |
530 465,239 |
439 337 |
252 |
655 |
2 |
511 170,72 |
355 201 |
329 |
162 |
715 666 |
3 |
112 21 |
143 |
343 333 |
644 310,202 |
670 |
4 |
411 182 |
236 |
334 |
380 |
671 |
5 |
150 |
335 |
530 |
458 |
800 |
Построение линейного графика изменения пропускной способности
Совместное влияние элементов дороги на пропускную способность оценивается перемножением частных коэффициентов снижения пропускной способности на участках подъемов, учитываются все коэффициенты, если продольный уклон не превышает 20‰, при продольных уклонах более 20‰ не учитывают. Каждый элемент дор ...
Оценка ресурсов, необходимых для разработки решения
Сравнительный анализ, выбор наиболее оптимального способа доставки грузов, требует огромных затрат, большой объем информации о каждом виде транспорта. Процесс разработки управленческих решений, помимо временных ресурсов, требует транспортные ресурсы, человеческие ресурсы, и финансовые ресурсы. Тран ...
Определение уравновешивающей силы с помощью теоремы Н. Е. Жуковского о
«жестком рычаге»
Если в соответствующие точки повернутого на 90° плана скоростей перенести все внешние силы, действующие на механизм, силы инерции, уравновешивающую силу, то план скоростей, рассматриваемый как жесткий рычаг относительно полюса p, будет находится в равновесии, т.е. сумма моментов всех сил относитель ...