Модель А

Распределить по рейсам в два аэропорта назначения имеющиеся в наличии ВС трех типов, обеспечив заданную потребность в пассажирских перевозках при минимальной суммарной себестоимости всех транспортных операций.

Осуществим проверку условия совершения транспортной операции при максимальном пассажиропотоке име­ю­щимся парком ВС:

P_j N_j ³ Q_i / M_i,

214·2 + 78·6 + 164·4 = 1552 ³ 6655 / 12 + 3652 / 12 = 858.92

– условие выполняется.

Целевая функция записывается следующим образом:

С = C_ij X_ij = 767.247 X₁₁ + 476.508 X₁₂ + 771.786 X₁₃ +

+ 1461.055 X₂₁ + 907.352 X₂₂ + 1462.137 X₂₃ ® min.

 

Ограничения на максимальное количество используемых ВС j-го типа:

X_i1 / M_i1 £ N₁, X_i2 / M_i2 £ N₂, X_i3 / M_i3 £ N₃;

X₁₁ / 12 + X₂₁ / 12 £ 2,

X₁₂ / 18 + X₂₂ / 12 £ 5,

X₁₃ / 12 + X₂₃ / 12 £ 3.

 

Ограничения на требуемое общее количество перевозимых пассажиров:

X_1j P_j g ³ Q₁, X_2j P_j g ³ Q₂.

Задача целочисленного линейного программирования решается методом ветвей и границ для различных вариантов распределения пассажиропотока и различных значений коэффициента занятости кресел g.

Варианты 1 и 2.

Ограничения на требуемое общее количество перевозимых пассажиров записывается следующим образом:

g = 1.0 214 X₁₁ + 78 X₁₂ + 164 X₁₃ ³ 6655,

214 X₂₁ + 78 X₂₂ + 164 X₂₃ ³ 3652;

g = 0.8 171 X₁₁ + 62 X₁₂ + 131 X₁₃ ³ 6655,

171 X₂₁ + 62 X₂₂ + 131 X₂₃ ³ 3652;

g = 0.6 128 X₁₁ + 47 X₁₂ + 98 X₁₃ ³ 6655,

128 X₂₁ + 47 X₂₂ + 98 X₂₃ ³ 3652.

Вариант 3.

Ограничения на требуемое общее количество перевозимых пассажиров записывается следующим образом:

g = 1.0 214 X₁₁ + 78 X₁₂ + 164 X₁₃ ³ 3328,

214 X₂₁ + 78 X₂₂ + 164 X₂₃ ³ 1826;

g = 0.8 171 X₁₁ + 62 X₁₂ + 131 X₁₃ ³ 3328,

171 X₂₁ + 62 X₂₂ + 131 X₂₃ ³ 1826;

g = 0.6 128 X₁₁ + 47 X₁₂ + 98 X₁₃ ³ 3328,

128 X₂₁ + 47 X₂₂ + 98 X₂₃ ³ 1826.

На рисунке 1 представлен вид таблицы MS Excel. Полученные результаты приведены в таблицах 17 и 18.

 

Таблица 17 – Распределение ВС по авиалиниям
Вариант	Аэропорт назначения	Коэффициент занятости кресел
1.0	0.8	0.6
Ту-204	Ту-134А	Ту-154М	Ту-204	Ту-134А	Ту-154М	Ту-204	Ту-134А	Ту-154М
1 и 2								-
						-		-
Использовано	1.000	0.028	0.861	1.000	0.272	1.000	1.000	0.889	1.000
			-	-					-
		-			-				-
Использовано	1.000	0.000	0.028	1.000	0.011	0.222	1.000	0.017	0.583

Таблица 18 – Суммарные затраты, тыс.руб.
Вари-ант	Коэффициент занятости кресел	Затраты на обслуживание пассажиров
1.0	0.8	0.6
Целевая функция
	55 514.433	72 635.228	105 112.362	1 939.905
	2 917.024
	25 426.529	32 693.155	45 242.098	2 428.452
Суммарные затраты
	57 454.338	74 575.133	107 052.267
	58 431.457	75 552.252	108 029.386
	27 854.981	35 121.607	47 670.550

 

Распределение ВС по рейсам в вариантах 1 и 2 не отличаются друг от друга, поскольку максимальные значения пассажиропотоков одинаковы. Суммарная себестоимость отличается из-за разницы в затратах на обслуживание пассажиров на рейсах «туда» и рейсах «обратно».

 

Рисунок 1 – Вид таблицы MS Excel решения задачи (модель А)
Модель Б

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

Целевая функция (суммарная прибыль) записывается следующим образом:

П = [Y_i¢ (Т_i - С_i¢) + Y_i¢¢ (Т_i - С_i¢¢)] - C_ij X_ij =

Y₁¢ (3.911 - 0.179) + Y₂¢ (7.492 - 0.205) + Y₁¢¢ (3.911 - 0.204) + Y₂¢¢ (7.492 - 0.427) -

- (767.247 X₁₁ + 476.508 X₁₂ + 771.786 X₁₃ + 1461.055 X₂₁ + 907.352 X₂₂ +

+ 1462.137 X₂₃) =

= 3.732 Y₁¢ + 7.287 Y₂¢ + 3.707 Y₁¢¢ + 7.065 Y₂¢¢ -

- (767.247 X₁₁ + 476.508 X₁₂ + 771.786 X₁₃ + 1461.055 X₂₁ + 907.352 X₂₂ +

+ 1462.137 X₂₃) ® max.

 

Ограничения на максимальное количество используемых ВС j-го типа:

X_i1 / M_i1 £ N₁, X_i2 / M_i2 £ N₂, X_i3 / M_i3 £ N₃;

X₁₁ / 12 + X₂₁ / 12 £ 2,

X₁₂ / 18 + X₂₂ / 12 £ 5,

X₁₃ / 12 + X₂₃ / 12 £ 3.

Ограничения на возможное общее количество перевозимых пассажиров:

Y₁¢ £ Q₁¢, Y₁¢¢ £ Q₁¢¢, Y₂¢ £ Q₂¢, Y₂¢¢ £ Q₂¢¢.

Ограничения на пассажировместимость ВС:

Y₁¢ £ X_1j P_j g, Y₁¢¢ £ X_1j P_j g, Y₂¢ £ X_2j P_j g, Y₂¢¢ £ X_2j P_j g.

Задача целочисленного линейного программирования решается методом ветвей и границ для различных вариантов пассажиропотока и различных значений коэффициента занятости кресел g.

Ограничение на пассажировместимость ВС записываются следующим образом:

g = 1.0 Y₁¢ £ 214 X₁₁ + 78 X₁₂ + 164 X₁₃,

Y₁¢¢ £ 214 X₁₁ + 78 X₁₂ + 164 X₁₃,

Y₂¢ £ 214 X₂₁ + 78 X₂₂ + 164 X₂₃,

Y₂¢¢ £ 214 X₂₁ + 78 X₂₂ + 164 X₂₃;

g = 0.8 Y₁¢ £ 171 X₁₁ + 62 X₁₂ + 131 X₁₃,

Y₁¢¢ £ 171 X₁₁ + 62 X₁₂ + 131 X₁₃,

Y₂¢ £ 171 X₂₁ + 62 X₂₂ + 131 X₂₃,

Y₂¢¢ £ 171 X₂₁ + 62 X₂₂ + 131 X₂₃;

g = 0.6 Y₁¢ £ 128 X₁₁ + 47 X₁₂ + 98 X₁₃,

Y₁¢¢ £ 128 X₁₁ + 47 X₁₂ + 98 X₁₃,

Y₂¢ £ 128 X₂₁ + 47 X₂₂ + 98 X₂₃,

Y₂¢¢ £ 128 X₂₁ + 47 X₂₂ + 98 X₂₃.

Ограничения на возможное общее количество перевозимых пассажиров записываются следующим образом:

Вариант 1:

Y₁¢ £ 6655, Y₁¢¢ £ 0, Y₂¢ £ 3652, Y₂¢¢ £ 0;

Вариант 2:

Y₁¢ £ 0, Y₁¢¢ £ 6655, Y₂¢ £ 0, Y₂¢¢ £ 3652;

Вариант 3:

Y₁¢ £ 3328, Y₁¢¢ £ 3328, Y₂¢ £ 1826, Y₂¢¢ £ 1826.

Полученные результаты приведены в таблицах 19 и 20. На рисунке 2 представлен вид таблицы MS Excel.

 

 

Рисунок 2 – Вид таблицы MS Excel решения задачи (модель Б)

 

 

Таблица 19 – Распределение ВС по авиалиниям и пассажиропотоки
Вариант	Аэропорт назначения	Коэффициент занятости кресел

1.0

0.8

0.6

Рейсы

Пассажиры

Рейсы

Пассажиры

Рейсы

Пассажиры

Ту-204

Ту-134А

Ту-154М

Туда

Обратно

Ту-204

Ту-134А

Ту-154М

Туда

Обратно

Ту-204

Ту-134А

Ту-154М

Туда

Обратно

-

-

-

-

-

-

-

-

-

-

						-	-	-	-	-	-	-	-	-	-
Использов.	1.000	0.000	0.000	5 136	0.000	0.000	0.000	-	0.00	0.000	0.00	-

-

-

-

-

-

-

-

-

-

-

						-	-	-	-	-	-	-	-	-	-
Использов.	1.000	0.000	0.000	5 136		0.000	0.000	0.000		0.000	0.000	0.000

Использов.	1.000	0.014	0.000	10 326	1.000	0.000	0.167	10 282	1.000	0.000	0.000	6 162

\

Таблица 20 – Суммарные прибыль и затраты, тыс.руб.
Вариант	Коэффициент занятости кресел
1.0	0.8	0.6
Суммарная прибыль
	1 890.223	-	-
	25 572.565	18 647.603	7 213.029
Суммарные затраты
	30 208.664	-	-
	30 208.664
	24 871.744	32 216.647	28 127.240