2. Основная (расчетная) часть. Задача 1

Условие задачи: Из аэропорта должны вылететь пять воздушных судов (далее ВС) для доставки груза в пять городов. Затраты на полет каждого из самолетов в каждый город представлены в табл. 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

Начнем со сравнения разности коэффициентов целевой функции основной и базовых строк.

1. Разности коэффициентов первой строки со второй:

1 столбец: 414 – 241 = 173

2 столбец: 504 – 485 = 19

3 столбец: 142 – 431 = -289

4 столбец: 161 – 373 = -212

5 столбец: 306 – 765 = -459

Наибольшая разность равна 173 – в первом столбце, а значит элемент х_11, не входит в оптимальный план, т.е. х₁₁ = 0. Следующая по величине разность равна 19 (во втором столбце). Тогда с₁₁ = 241 + 19 = 260.

Новое значение коэффициента вписываю в туже клетку (Таблица 2) и выделяю жирным шрифтом. Аналогично будут занесены и другие новые значения коэффициентов.

Таблица 2.

Столбцы Строки	1	2	3	4	5
1	414 260	504 291	142	161 75	306 237
2	241	485	431	373	765
3	370	690	445	766	347
4	691	218	164	399	771
5	563	411	264	195	822

2. Разность коэффициентов первой строки с третьей:

1 столбец: 260 – 370 = -110

2 столбец: 504 – 690 = -186

3 столбец: 142 – 445 = -303

4 столбец: 161 – 766 = -605

5 столбец: 306 – 347 = -41

Наибольшая разность равна -41 – в пятом столбце, а значит элемент х₁₅, не входит в оптимальный план, т.е. х₁₅ = 0. Следующая по величине разность равна - 110 (в первом столбце). Тогда с₁₅ = 347 + (-110) = 237.

3. Разность коэффициентов первой и четвертой строк:

1 столбец: 260 – 691 = -431

2 столбец: 504 – 218 = 286

3 столбец: 237 – 164 = 73

4 столбец: 161 – 399 = -238

5 столбец: 306 – 771 = -465

Наибольшая разность равна 286 – во втором столбце, а значит элемент х₁₂, не входит в оптимальный план, т.е. х₁₂ = 0. Следующая по величине разность равна 73 (в третьем столбце). Тогда с₁₂ = 218 + 73 = 291.

4. Разность коэффициентов первой и пятой строк:

1 столбец: 260 – 563 = -303

2 столбец: 291 – 411 = -120

3 столбец: 142 – 264 = -122

4 столбец: 161 – 195 = -34

5 столбец: 237 – 822 = -585

Наибольшая разность равна -34 – в четвертом столбце, а значит элемент х₁₄, не входит в оптимальный план, т.е. х₁₄ = 0. Следующая по величине разность равна -120 (во втором столбце). Тогда с₁₄ = 195 + (-120) = 75.

По итогам расчетов и заполнения Таблицы 2 (стр. 6) видно, что в первой строке все элементы, кроме х₁₃, равны 0. Поэтому х₁₃ = 1, строка 1 и столбец 3 исключаются из дальнейшего рассмотрения. А Таблица 2 переходит в Таблицу 3.

Таблица 3.

Столбцы Строки	1	2	4	5
2	241	485 192	373 -24	765 218
3	370	690	766	347
4	691	218	399	771
5	563	411	195	822

Используя Таблицу 3 сравним вторую строку с остальными.

1. Разность коэффициентов 2 строки с 3:

1 столбец: 241 – 370 = -129

2 столбец: 485 – 690 = -205

4 столбец: 373 – 766 = -393

5 столбец: 765 – 347 = 418

Наибольшая разность равна 418 – в пятом столбце, а элемент х₂₅ не входит в оптимальный план, т.е. х₂₅ = 0. Следующая по величине разность равна -129 (в первом столбце). Тогда с₂₅ = 347 + (-129) = 218.

2. Разность коэффициентов 2 строки с 4:

1 столбец: 241 – 691 = -450

2 столбец: 485 – 218 = 267

4 столбец: 373 – 399 = -26

5 столбец: 218 – 771 = -553

Наибольшая разность равна 267 – во втором столбце, а элемент х₂₂ не входит в оптимальный план, т.е. х₂₂ = 0. Следующая по величине разность равна -26 (в четвертом столбце). Тогда с₂₂ = 218 + (-26) = 192.

3. Разность коэффициентов 2 строки с 5:

1 столбец: 241 – 563 = -322

2 столбец: 192 – 411 = -219

4 столбец: 373 – 195 = 178

5 столбец: 218 – 822 = -604

Наибольшая разность равна 178 – в четвертом столбце, а элемент х₂₄ не входит в оптимальный план, т.е. х₂₄ = 0. Следующая по величине разность равна -219 (во втором столбце). Тогда с₂₄ = 195 + (-219) = -24.

По итогам расчетов и заполнения Таблицы 3 (стр. 7) видно, что во второй строке все элементы, кроме х₂₁, равны 0. Поэтому х₂₁ = 1, строка 2 и столбец 1 исключаются из дальнейшего рассмотрения. А Таблица 3 переходит в Таблицу 4.

Таблица 4.

Столбцы Строки	2	4	5
3	690 585	766 369	347
4	218	399	771
5	411	195	822

Используя Таблицу 4 сравним третью строку с остальными.

1. Разность коэффициентов 3 строки с 4:

2 столбец: 690 – 218 = 472

4 столбец: 766 – 399 = 367

5 столбец: 347 – 771 = -424

Наибольшая разность равна 472 – во втором столбце, а элемент х₃₂ не входит в оптимальный план, т.е. х₃₂ = 0. Следующая по величине разность равна 367 (в четвертом столбце). Тогда с₃₂ = 218 + 367 = 585.

2. Разность коэффициентов 3 строки с 5:

2 столбец: 585 – 411 = 174

4 столбец: 766 – 195 = 571

5 столбец: 347 – 822 = -475

Наибольшая разность равна 571 – в четвертом столбце, а элемент х₃₄ не входит в оптимальный план, т.е. х₃₄ = 0. Следующая по величине разность равна 174 (во втором столбце). Тогда с₃₄ = 195 + 174 = 369.

По итогам расчетов и заполнения Таблицы 4 (стр. 8) видно, что в третьей строке все элементы, кроме х₃₅, равны 0. Поэтому х₃₅ = 1, строка 3 и столбец 5 исключаются из дальнейшего рассмотрения. А Таблица 4 переходит в Таблицу 5.

Таблица 5.

Столбцы Строки	2	4
4	218	399 2
5	411	195

Используя Таблицу 5 сравним четвертую строку с остальными.

1. Разность коэффициентов 4 строки с 5:

2 столбец: 218 – 411 = -193

4 столбец: 399 – 195 = 204

Наибольшая разность равна 204 – в четвертом столбце, а значит элемент х₄₄ не входит в оптимальный план, т.е. х₄₄ = 0, а значит (с₄₄ = 195 + (-193) = 2 (и согласно Таблицы 5) элементы х₄₂ = 1 и х₅₄ = 1.

Итого получаю следующие отличные от нуля элементы: х₁₃ = 1; х₂₁ = 1; х₃₅ = 1; х₄₂ = 1; х₅₄ = 1

А значение целевой функции: С = 142 + 241 + 347 + 218 + 195 = 1 143

Т.е. это и есть минимальные суммарные затраты на транспортировку грузов равные 1 143 тыс. руб.

Решение данной задачи имеет следующий вид:

Таблица 6.

№Города № ВС	1	2	3	4	5
1			1
2	1
3					1
4		1
5				1

Вывод: Для того чтобы суммарные затраты на транспортировку грузов били минимальными, необходимо назначить ВС на рейсы следующим образом:

• ВС1 в Город3

• ВС2 в Город1

• ВС3 в Город5

• ВС4 в Город2

• ВС5 в Город4

При таком назначении ВС на рейсы минимальные суммарные затраты на транспортировку грузов равны 1 143 тыс. руб.