Оглавление:
Задача о закреплении самолетов за воздушными линиями
Эта задача возникает при выборе оптимального варианта плана закрепления самолетов заданными воздушными линиями, обеспечивающего необходимые объемы перевозок при минимальных суммарных эксплуатационных расходах. Она формулируется так.
Пусть имеется 
различных типов самолетов, которые нужно распределить между 
авиалиниями. Пусть месячный объем перевозок самолетом 
-го типа на 
-й авиалинии равен 
единицам, а связанные с этим месячные эксплуатационные расходы составляют 
руб. Определить число 
самолетов -го типа, которое следует закрепить за -й авиалинией для обеспечения перевозки по ней 
единиц 
при минимальных суммарных эксплуатационных расходах, если известно, что имеется 
самолетов -го типа 
.
Так как объем перевозок по -й авиалинии
, а суммарные расходы составляют при этом
то задача состоит в минимизации
при ограничениях
и решается симплекс-методом с учетом целочисленности .
Пример:
Пусть три типа самолетов следует распределить между четырьмя авиалиниями. В приводимой ниже таблице задано число самолетов каждого типа, месячный объем перевозок каждым самолетом на каждой авиалинии и соответствующие эксплуатационные расходы.
Надо распределить самолеты по авиалиниям так, чтобы при минимальных суммарных эксплуатационных расходах перевезти по
каждой из четырех авиалиний соответственно не менее 300, 200, 1000 и 500 единиц груза.
Обозначим через 
число самолетов 
типа, которое планируется закрепить за 
авиалинией. Тогда задача сводится к минимизации
при ограничениях
Перепишем ограничения в виде
Составив таблицу
и освободившись от последних трех уровней, т.е. переведя последние три переменные в свободные и вычеркнув столбцы, соответствующие этим свободным переменным, получим преобразованную таблицу, в которой еще есть отрицательные свободные члены.
Переходим к отысканию опорного решения. Сделав два шага модифицированных жордановых исключений, придем к таблице.
Из таблицы видно, что решение
для которого 
, является не только опорным, но и оптимальным (все коэффиценты 
-строки неположительны!).
Эта теория взята со страницы лекций по предмету «математическое программирование»:
Предмет математическое программирование
Возможно эти страницы вам будут полезны:
