Из аэропорта должны вылететь пять воздушных судов (ВС) для доставки груза в пять городов

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

, , .

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

Таблица 1. Затраты на полёт каждого из самолётов (тыс. руб.) в каждый из пяти городов
ГОРОДА САМОЛЁТЫ 1 2 3 4 5
1 262 481 502 337 406
2 341 505 208 452 755
3 123 279 345 136 717
4 421 258 324 843 231
5 367 611 514 511 303

Будем рассматривать разности коэффициентов первой строки со второй.
262–341=-79
481–505=-24
502–208=294
337–452=-115
406–755=-349
В соответствии со сказанным выше, элемент х13 не входит в оптимальный план, т.е. х13=0. следующая по величине разность равна -24. Поэтому с13=502+(-24)=478. (Договоримся новые значения с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

Сравним первую строку с третьей.
262–123=139
481–279=202
502–345=157
337–136=201
406–717=-311
Элемент х12 не входит в оптимальный план, т.е. х12=0. следующая по величине разность равна 201. Поэтому с12=279+201=480.
Теперь сравним первую строку с четвёртой.
262–421=-159
480–258=221
502–324=154
337–843=-506
406–231=175
Элемент х12 не входит в оптимальный план, т.е. х12=0. следующая по величине разность равна 175. Поэтому с12=175+258=433.
Сравним первую строку с пятой.
262–367=-105
433–611=-178
502–514=-36
337–511=-174
406–303=103

Элемент х15 не входит в оптимальный план, т.е. х15=0. следующая по величине разность равна -36. Поэтому с15=303+(-36)=267.
Перейдём ко 2 строке. Сравним её с 1.
341–262=79
505–433=72
208–478=-270
452–337=115
755–267=488
Элемент х25 не входит в оптимальный план, т.е. х25=0. следующая по величине разность равна 115. Поэтому с25=755+115=870.
Сравним 2 строку с 3.
341–123=218
505–279=226
208–345=-137
452–136=316
870–717=153
Элемент х24 не входит в оптимальный план, т.е. х24=0. следующая по величине разность равна 226. Поэтому с24=226+136=362.
Сравним 2 строку с 4.
341–421=-80
505–258=247
208–324=-116
362–843=-481
870–231=639
Элемент х25 не входит в оптимальный план, т.е. х25=0. следующая по величине разность равна 247. Поэтому с25=231+247=478.
Сравним 2 строку с 5.
341–421=-26
505–258=-106
208–324=-306
362–843=-149
478–231=175
Элемент х25 не входит в оптимальный план, т.е. х25=0. следующая по величине разность равна -26. Поэтому с25=303+(-26)=277.
Теперь сравним 3 строку с остальными строками.
123–262=-139
279–433=-154
345–478=-133
136–337=-201
717–267=450
Элемент х35 не входит в оптимальный план, т.е. х35=0. следующая по величине разность равна -139. Поэтому с35=267+(-58)=134.
Сравним 3 строку со 2.
123–341=-218
279–505=-226
345–208=137
136–362=-226
134–277=-143
Элемент х33 не входит в оптимальный план, т.е. х33=0. следующая по величине разность равна -143. Поэтому с33=478+(-143)=335.
Сравним 3 строку с 4.
123–421=-298
279–258=21
335–324=11
136–843=-707
134–231=-97
Элемент х32 не входит в оптимальный план, т.е. х32=0. следующая по величине разность равна 11. Поэтому с32=258+11=269.
Сравним 3 строку с 5.
123–367=-244
269–611=-342
335–514=-179
136–511=-375
134–303=-169
Элемент х35 не входит в оптимальный план, т.е. х35=0. следующая по величине разность равна -179. Поэтому с35=134+(-179)=-45.
Перейдём к 4 строке. Сравним её с 1 строкой.
421–262=159
258–433=-175
342–478=-154
843–337=506
231–267=-36
Элемент х44 не входит в оптимальный план, т.е. х44=0. следующая по величине разность равна 159. Поэтому с44=843+159=1002.
Сравним 4 строку с 2 строкой
421–341=80
258–505=-247
342–208=116
1002–362=640
231–277=-46
Наибольшая разность в 4 столбце 195, следовательно Х44=0. Следующая по величине разность 116. Поэтому
С44= 362+116=478
Сравним 4 строку с 3 строкой
421–123=298
258–269=-11
342–335=-11
478–136=342
231–134=97
Наибольшая разность в 4 столбце 342, следовательно Х44=0. Следующая по величине разность в 1 столбце равна 298. Поэтому
С44= 136+298=434
Сравним 4 строку с 5 строкой
421–367=54
258–611=-353
342–514=-190
434–511=-77
231–303=-72
Наибольшая разность 54, следовательно Х41=0. Следующая по величине разность равна -72. Поэтому
С41= 367+(-72)=295

Теперь сравним 5 строку с остальными строками.
367–262=105
611–433=178
514–478=36
511–337=174
303–267=36
Элемент х52 не входит в оптимальный план, т.е. х52=0. следующая по величине разность равна 174. Поэтому с52=174+433=607.
Сравним 5 строку со 2.
367–341=26
607–505=102
514–208=306
511–362=149
303–277=26
Элемент х53 не входит в оптимальный план, т.е. х53=0. следующая по величине разность равна 149. Поэтому с53=208+149=357.
Сравним 5 строку с 3.
367–123=244
607–269=338
357–335=22
511–136=375
303–134=169
Элемент х52 не входит в оптимальный план, т.е. х54=0. следующая по величине разность равна 338. Поэтому с54=338+136=474.
Сравним 5 строку с 4.
367–295=72
607–258=349
357–324=33
474–434=40
303–231=72
Элемент х52 не входит в оптимальный план, т.е. х52=0. следующая по величине разность равна 72. Поэтому с52=258+72=330.
Таблица 2 перерождается в Таблицу 3
Таблица 3
ГОРОДА САМОЛЁТЫ 2 3 5
2 505 208 755, 870,478, 277
4 258 324 231
5 611, 607,330 514, 357 303

Сравним 5 строку со 4.
330–258=72
357–324=33
303–231=72
Так как максимальная разность отмечается в нескольких столбцах,
никакого вывода сделать нельзя
Сравним 5 строку с 2.
330–505=-175
357–208=149
303–277=26
Элемент х23 не входит в оптимальный план, т.е. х23=0. следующая по величине разность равна 26. Поэтому с42=26+208=234. Отсюда вторая строка и третий столбец уходят. Табл. 3 вырождается в табл. 4.

Таблица 4
ГОРОДА САМОЛЁТЫ 2 5
4 258 231
5 611, 607,330 303

Перейдём к столбцам. Сравним 2 столбец с 5
258–231=27
330–303=27
Нельзя сделать вывод

2.

Рейтинг
( Пока оценок нет )
Понравилась статья? Поделиться с друзьями:
Добавить комментарий

;-) :| :x :twisted: :smile: :shock: :sad: :roll: :razz: :oops: :o :mrgreen: :lol: :idea: :grin: :evil: :cry: :cool: :arrow: :???: :?: :!:

19 + 11 =

Этот сайт использует Akismet для борьбы со спамом. Узнайте как обрабатываются ваши данные комментариев.

Adblock detector