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

Из аэропорта должны вылететь пять воздушных судов(ВС) для доставки груза в пять городов. Затраты на полет каждого из самолетов в каждый город представлены в табл 1. Таблица 1. 1 2 3 4 5 1 414 504 142 161 306 2 241 485 431 373 765 3 370 690 445 766 347 4 691 218 164 399 771 5 563 411 264 195 822 Необходимо назначить ВС на рейсы таким образом, что суммарные затраты на транспортировку грузов были минимальными.

Математическая модель задачи:
Пусть xij- назначение i – го самолета для полета в j -й город.
По условию ixij=1, jxij=1.
Суммарная стоимость полетов : ijxijcij.
Таким образом, найти минимальную стоимость транспортировки грузов z=ijxijcij. при следующих ограничениях: ixij=1, jxij=1, xij≥0.
Это задача о назначениях. Решим ее методом Петрунина С.В.
Будем рассматривать разности коэффициентов первой строки со второй.
414-241=173, 504-485=19, 142-431=-289, 161-373=-212, 306-765=-459.
Наибольшая разность 173 в первом столбце. Значит, элемент x11 не входит в оптимальный план, то есть x11=0. Следующая по величине разность 19 ( 2 столбце). Поэтому с11 =173
Будем рассматривать разности коэффициентов первой строки с третей.
173-370=-197,504-690=-186,142-445=-303,161-766=-605, 306-347=-41
Нельзя сделать вывод.
Будем рассматривать разности коэффициентов первой строки со четвертой.
173-691=-518,504-218=286,142-164=-22,161-399=-560,306-771=-465
Наибольшая разность 286 в втором столбце. Значит, элемент x12 не входит в оптимальный план, то есть x12=0. Поэтому с12 =286
Будем рассматривать разности коэффициентов первой строки с пятой.
173-563=-390,286-411=-125,142-264=-122,-161-195=-34,306-822=-516
Нельзя сделать вывод.
Будем рассматривать разности коэффициентов второй строки со первой.
241-173=68,485-286=199,431-142=289,373-161=212,765-306=459
Наибольшая разность 459 в пятом столбце. Значит, элемент x25 не входит в оптимальный план, то есть x25=0. Следующая по величине разность 289 ( 3 столбце). Поэтому с25 =459
Будем рассматривать разности коэффициентов второй строки с третей.
241-370=-129,485-690=-205,431-445=-14,373-766=-393,459-347=112
Наибольшая разность 112 в пятом столбце

. Значит, элемент x25 не входит в оптимальный план, то есть x25=0. Поэтому с25 =112
Будем рассматривать разности коэффициентов второй строки со четвертой.
241-691=-450,485-218=267,431-164=267,373-399=-26,112-771=-659
Наибольшая разность 267 в 2,3 столбце. Нельзя сделать вывод.
Будем рассматривать разности коэффициентов второй строки со пятой.
241-563=-322,485-411=74,431-264=167,373-195=178,112-822=-710
Наибольшая разность 178 в 4 столбце. Значит, элемент x24 не входит в оптимальный план, то есть x24=0. Следующая по величине разность 167 ( 3 столбце). Поэтому с24 =178
Будем рассматривать разности коэффициентов третей строки с первой.
370-173=197,690-286=404,445-142=303,766-161=605,347-306=40
Наибольшая разность 605 в 4 столбце. Значит, элемент x34 не входит в оптимальный план, то есть x34=0. Следующая по величине разность 404 ( 2 столбце). Поэтому с34 =605
Будем рассматривать разности коэффициентов третей строки с второй.
370-241=129,690-485=205,445-431=14,605-177=428,347-112=235
Наибольшая разность 428 в 4 столбце. Значит, элемент x34 не входит в оптимальный план, то есть x34=0. Следующая по величине разность 235 ( 5 столбце). Поэтому с34 =428
Будем рассматривать разности коэффициентов третей строки с четвертой.
370-691=-321,690-218=472,445-169=276, 428-399=29,347-771=-424
Наибольшая разность 472 в 2 столбце. Значит, элемент x32 не входит в оптимальный план, то есть x32=0. Следующая по величине разность 276 ( 3 столбце). Поэтому с32 =472
Будем рассматривать разности коэффициентов третей строки с пятой.
370-563=-193,472-411=61,445-264=181,428-195=233,347-822=-475
Наибольшая разность 233 в 4столбце