Задача о закреплении самолетов за воздушными линиями

Эта задача возникает при выборе оптимального варианта закрепления самолетов (или судов) за воздушными линиями, обеспечивающего необходимые объемы перевозок при минимальных суммарных эксплуационных расходах.

Пусть три типа самолетов следует распределить между четырьмя авиалиниями.

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

Тип самолета № авиалинии		...	j	...	n	Минимальный объем перевозок
	A11 = 15 B11 = 15 X11	...	A1j = 30 B1j = 70 X11	...	A1n = 25 B1n = 40 X11
	A21 = 10 B21 = 20 X21	...	A2j = 25 B2j = 28 X2j	...	A2n = 50 B2n = 70 X2n
...	...	...	...	...	...	...
i	Aj1 = 20 Bj1 = 25 Xj1	...	Aij = 10 Bij = 15 Xij	...	Ajn = 30 Bjn = 40 Xjn
...	...	...	...	...	...	...
m	Am1 = 50 Bm1 = 40 Xm1	...	Amj = 17 Bmjn= 45 Xmj	...	Amn = 45 Bmn = 65 Xmn
Число самолетов	N1 = 50		Nj = 20	...	Nn = 30

Надо распределить самолеты по авиалиниям так, чтобы при минимальных суммарных эксплуатационных расходах перевезти по каждой из четырех авиалиний соответственно не менее

300,

200,

1000 и

500 единиц груза.

Обозначим:

Xij – число самолетов j-го типа, которое надо закрепить за i-ой авиалинией для обеспечения перевозки по этой линии Ai единиц груза при минимальных суммарных эксплуатационных расходах

Aij – количество груза перевозимого по i–ой авиалинии самолетом j-го типа.

Bij – суммарные эксплуатационные расходы.

Nj – число самолетов j–го типа. где, i =1,2,…,m и j = 1, 2, …, n

Так как объем перевозок по i –ой авиалинии равен

Ai1Xi1 + … + AinXin i = 1,…, m),

А суммарные расходы составляют при этом

n m

Σ Σ Bij·Xij,

j=1 i=1

то задача состоит в минимизации линейной формы

n m

Z = Σ Σ Bij·Xij, (7)

j=1 i=1

при ограничениях

Ai1Xi1 + AijXij + AinXin ≥ Aij (i=1,2,…,m) (8)

Xij + Xij + Xij = Nj (j=1,2,…,n) (9)

Xij ≥ 0 (i=1,2,…,m и j=1,2,…,n) (10)

или для нашего примера

Z = 15X11 + 20X21 + 25X31 + 40X41 + 70X12 + 28X22 + + 15X32 + 45X42 + 40X13 + 70X23 + 40X33 + 65X43 (7a)

при ограничениях

15X11 + 30X12 + 25X13 ≥ 300,

10X21 + 25X22 + 50X23 ≥ 200, (8a)

20X31 + 10X32 + 30X33 ≥ 1000,

50X41 + 17X42 + 45X43 ≥ 500 и

X11 + X21 + X31 + X41 = 50,

X12 + X22 + X32 + X42 = 20, (9a)

X13 + X23 + X33 + X43 = 30,

Xij ≥ 0 (i=1,2,3,4 и j =1,2,3) (10a)