- 1
- 2
- 3
- . . .
- последняя »
1. Задача 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 |
Будем рассматривать разности коэффициентов первой строки со второй.
-511=-380
-355=175
-329=110
-162=90
-715=-60
В соответствии со сказанным выше, элемент х12 не входит в оптимальный план, т.е. х12=0. следующая по величине разность равна 110. Поэтому с12=355+110=465. (Договоримся новые значения сij вписывать в ту же клеточку, но выделять их жирным шрифтом) (табл. 2) Таблица 2
ГОРОДА САМОЛЁТЫ | 1 | 2 | 3 |
- 1
- 2
- 3
- . . .
- последняя »
Похожие работы
Тема: Единая транспортная система |
Предмет/Тип: География, экономическая география (Реферат) |
Тема: Единая транспортная система и география транспорта |
Предмет/Тип: География, экономическая география (Курсовая работа (п)) |
Тема: Единая транспортная система и география транспорта |
Предмет/Тип: Транспорт, грузоперевозки (Курсовая работа (т)) |
Тема: Единая транспортная система и география транспорта 2 |
Предмет/Тип: Логика (Курсовая работа (т)) |
Тема: Единая транспортная сеть |
Предмет/Тип: Транспорт, грузоперевозки (Курсовая работа (т)) |
Интересная статья: Быстрое написание курсовой работы