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

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

Пусть имеется n различных типов самолетов, которые нужно распределить между m авиалиниями. Пусть месячный объем перевозок самолетом i-го типа на j-й авиалинии равен а_ij единицам, а связанные с этим месячные эксплуатационные расходы составляют c_ij рублей. Определить число x_ij самолетов i-го типа, которое следует закрепить за j-й авиалинией для обеспечения перевозки по этой линии а_ij единиц (i= , j= ) при минимальных суммарных эксплуатационных расходах, если известно, что имеется N_i самолетов i-го типа (i= ).

Математическая модель задачи выглядит следующим образом.

Целевая функция имеет вид:

® min.

ЦФ представляет суммарные эксплуатационные расходы в месяц.

Ограничения имеют вид:

³ a_j, j= , (1)

=N_i, i= , (2)

x_ij³ 0, x_ij- целые числа, i= , j= .

Условия (1) определяют, что самолеты j-й авиалинии должны обеспечивать объем перевозок не меньше заданного.

Условия (2) представляют собой ограничение по количеству имеющихся самолетов i-го типа.

Данная задача является задачей целочисленного линейного программирования.