Определение потребной структуры парка воздушных судов методом линейного программирования

УДК 656.7

ОПРЕДЕЛЕНИЕ ПОТРЕБНОЙ СТРУКТУРЫ ПАРКА ВОЗДУШНЫХ СУДОВ МЕТОДОМ

ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

А.Д. Припадчев

В статье обоснован и сформулирован метод определения потребного типа воздушного судна для конкретного маршрута, основанного на разработанном алгоритме выбора наилучшего варианта с применением симплекс-метода

Ключевые слова: воздушное судно, параметрический ряд, линейное программирование, симплекс-метод, экономическая эффективность

ВВЕДЕНИЕ

Решение задач оптимизации означает поиск и достижение оптимального соотношения параметров авиационной транспортной системы (АТС) и ряда параметров системы, которые влияют на оптимальность и результат функционирования АТС. Оптимальность обозначает наличия в системе приемлемых свойств в соответствии с принятым критерием эффективности. При этом должны быть определены и иметь смысл следующие характеристики или условия задач оптимизации:

- критерии оптимизации в виде показателей эффекта, объединенных в общий критериальный показатель экономической эффективности;

- алгоритмы и методики для оценки единого критериального показателя и проверки

оптимальности;

- определение общего критериального

показателя экономической эффективности

процесса пассажирских перевозок при изменении параметров, влияющих на изменение целевой функции.

1. СОСТОЯНИЕ ВОПРОСА

Авиапредприятия в настоящее время остро нуждаются в современных ВС. Устаревший

парк и изменение требований к летнотехническим характеристикам являются

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

Применительно к ВС, задействованным в АТС пассажирских перевозок, возможно

сформулировать следующие положения:

- технико-экономическая оценка ВС должна

рассматриваться совместно с выполняемыми ими ВС должна рассматриваться совместно с выполняемыми ими задачами;_____________________

Припадчев Алексей Дмитриевич - ОГУ, канд. техн. наук, доцент, e-mail: aleksejj-pripadchev@rambler.ru

- оценку эффективности отдельного типа ВС необходимо вести в соответствии с потребностями в пассажирских перевозках авиапредприятий и всей АТС в целом.

Классический аналитический метод поиска экстремума функций многих переменных предполагает ряд требований к построению целевой функции и уравнений связи (с ограничениями), которые невозможно

полностью выполнить в процессе пассажирских перевозок АТС.

2. ПОСТАНОВКА ЗАДАЧИ

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

параметров. Система получается громоздкой, вычислительные трудности усугубляются. При оптимизации параметров АТС эти требования невыполнимы еще и в силу особенностей задачи поиска оптимальных параметров системы с ВС. Возможно использование следующих численных методов оптимизации: 1) итерационные методы. Различают следующие итерационные методы. Метод невязок. В этом случае минимизируется функция ошибок (невязок), возрастающая

квадратичная или любая другая функция, в соответствии с формулой

п т к

Т0

г=1 }=1 к=1

Метод «случайных возмущений», где вводят для некоторой точки (х,у,г) в п т к-мерном пространстве параметров системы возмущения по таблице случайных чисел Ахг-, Ау , Агк и

исследуют изменения К.

Метод «замороженных» переменных, где фиксируют по статистическим данным все, кроме

одного параметра, и применяют или аналитические или численные методы поиска оптимальных значений, затем исследуют следующий параметр. Применение

вышеперечисленных методов нежелательно, т.к. не «видно» изменение критерия оценки от оптимизируемых параметров, не допускается анализ пологости экстремальных точек.

2) градиентные методы. При больших затратах времени точность поиска не гарантируется, т.к. направление его может быть в стороне от глобального оптимума, часто случаются «зацикливания» при негладких экстремумах.

3) метод сканирования. Различают полный и целенаправленный перебор. Методы не предъявляют особых требований к виду целевой функции и ограничениям. Функции и их производные не обязательно должны быть непрерывными и могут быть заданы как в аналитическом, так и в табличном виде. Допускается исследование влияния отдельных параметров на критерий. Однако при этом требуется много времени на поиск. Проблема выбора рационального шага изменения оптимизируемых параметров успешно решается не только при численных переменных, но и при наличии непрерывных переменных.

3. МЕТОДИКА ИССЛЕДОВАНИЯ

Оптимизация парка ВС проводится на основе математического моделирования. Для построения математической модели необходимо иметь четкое представление о цели функционирования исследуемой системы и располагать информацией об ограничениях, которые определяют область допустимых значений переменных [1].

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

альтернатив решения применительно к исследуемой проблемной ситуации; определение присущих исследуемой АТС ограничений. Второй этап исследования связан с построением модели. На этом этапе учитывая особенности постановки задачи вырабатываем модель наиболее подходящую для адекватного описания исследуемой АТС. При построении такой модели должны быть установлены количественные соотношения для выражения целевой функции и ограничений. На третьем этапе исследования осуществляется решение сформулированной задачи. При использовании математической модели решение получаем с

помощью оптимизационных методов, т.е. приводим модель к оптимальному решению или проводим анализ модели на чувствительность. Четвертый этап исследования заключается в проверке адекватности модели. Модель можно считать адекватной, если некоторые неточности отображения АТС-оригинала способствуют обеспечению достаточно надежного

предсказания поведения системы. Общий метод проверки адекватности модели состоит в сопоставлении получаемых результатов с характеристиками системы, которые при тех же исходных условиях имели место в прошлом. Если при аналогичных входных параметрах модель достаточно точно воспроизводит поведение системы, то она считается адекватной.

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

подходящей модели. Несмотря на слишком большое число переменных, и ограничений, которые необходимо учитывать при анализе реальной ситуации, лишь небольшая их часть оказывается существенной для описания поведения исследуемой АТС. При описании реальной АТС, прежде всего, необходимо идентифицировать доминирующие переменные, параметры и ограничения. В связи с чем, мы предлагаем для оптимизации парка ВС вариант математического моделирования процесса пассажирских перевозок гражданской авиации РФ. При рассмотрении вопроса о выборе оптимального парка ВС необходимо учитывать системный подход к планированию цели, учитывать как перспективу развития цели, так и комплексное решение с использованием большинства взаимосвязей внутри АТС и вне системы. Таким образом, необходимо решить три основных иерархические задачи:

1) определение потребного количества ВС, каждого варианта для каждого маршрута;

2) решение экономико-математической задачи

оптимизации парка ВС при выполнении пассажирских перевозок; 3) достижение

максимальной эффективности ВС в процессе пассажирских перевозок.

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

перечисленных выше требований, возможно, провести лишь при системном подходе к выбору оптимального парка ВС. Системный анализ характеризуется не специфическим научным аппаратом, а упорядоченным, логически обоснованным подходом к исследованию проблем. Он представляет совокупность методов, применяемых при исследовании возможных подходов к решению сложных задач, и применяется для определения наиболее реальных способов решения возникших проблем, обеспечивающих максимальное удовлетворение поставленных требований. Методология системного анализа определяется как совокупность его принципов, т.е. наиболее общих закономерностей проведения конкретных анализов различных систем и процессов, протекающих в них. Определяющими принципами системного анализа является: целенаправленность. АТС существует и развивается в соответствии с целями,

поставленными извне или активно формируемыми самой системой; поиск

нескольких вариантов решения возникших проблем с целью выбора наилучших из них; нахождение оптимальных решений; глубина и полноценность изучения динамического

характера их функционирования и развития АТС.

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

1) постановка задачи. Формулировка цели и вопросов, требующих решения, анализ условий функционирования АТС с учетом заданных ограничений, выбор критериев оптимальности;

2) построение математической модели. Построение целевой функции с системой ограничений-равенств;

3) определение алгоритма поиска оптимального решения с учетом минимального значения целевой функции и с коэффициентами в целевой функции;

4) проверка модели и оценка решения.

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

отыскание наилучшего способа распределения ограниченных ресурсов, по нескольким взаимосвязанным по цели и использованию ресурсов по видам деятельности авиапредприятий. Наглядный графический метод — решение задач линейного

программирования, ограниченного двумя переменными. Однако геометрическая интерпретация модели линейного

программирования позволяет получить важный результат: при решении задачи необходимо

принимать во внимание экстремальные точки пространства решений, т.е. точки пересечения линейных зависимостей с учетом введенных ограничений. Этот результат является главным моментом при построении вычислительной схемы симплекс-метода [2,3].

Процесс решения задачи линейного программирования симплекс-методом носит итерационный характер, т.е. однотипные вычислительные процедуры в определенной последовательности повторяются до тех пор, пока не будет получено оптимальное решение. Для методологического построения решения задачи линейного программирования

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

1) все ограничения записываются в виде равенства с неотрицательной правой частью;

2) значения всех переменных модели неотрицательны;

3) целевая функция подлежит максимизации или минимизации.

В процессе построения математической модели для решения данной задачи необходимо четко представлять:

1) для определения каких величин должна быть построена математическая модель;

2) какие ограничения должны быть

наложены на переменные, чтобы выполнялись условия, характерные для моделирующей АТС;

3) в чем состоит цель, для достижения которой из всех допустимых значений переменных необходимо выбрать те, которые будут соответствовать оптимальному решению задачи.

Трудность построения математической

модели заключается в идентификации

переменных и последующем представлении цели и ограничений в виде математических функций этих переменных. В рассматриваемом случае мы имеем следующее [2]:

1) переменные. В связи с тем, что необходимо из определенного пункта «А» произвести

воздушную перевозку по «п» маршрутам, то переменными в данной модели являются:

а) «п» — количество маршрутов;

б) «т» — тип ВС;

2) целевая функция. Количество рейсов в месяц для рассматриваемых типов ВС на всех маршрутах и с учетом цен одного рейса для каждого типа ВС на рассматриваемых

маршрутах, целевую функцию суммарных расходов на все рейсы всех маршрутов вычисляем по формуле

1=1 ]=1

3) ограничения. При решении

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

авиапассажиров по п-му маршруту, количество рейсов, совершаемых на /-ом маршруте ВС 7-ого типа. Окончательно для всех маршрутов система ограничений-равенств представлена в виде

Ь1 “ а1,1  Х1,1 + а1,2  Х 1,2 + ••• + а1,т  Х 1,т

Ь2 a2,1 'Х2,1 + a2,2 ' X2,2 + "• + a2,m ' X2,m

.

С формальной позиции данная модель является линейной, т.к. все входящие в нее функции (целевая функция и ограничения) линейны. Линейность предполагает наличие двух свойств:

1) пропорциональности.

Пропорциональность означает, что вклад каждой переменной в целевую функцию и общий объем пассажирской перевозки прямо пропорционален уровню этой переменной;

2) аддитивности. Аддитивность заключается в том, что целевая функция представляет собой сумму вкладов от различных переменных.

4. ОБСУЖДЕНИЕ РЕЗУЛЬТАТОВ

Из теоретических положений, лежащих в основе построения симплекс-метода, следует, что узловые точки полностью определяются базисным решением задачи линейного программирования. Условие оптимальности и

допустимости симплекс-алгоритма обеспечивает переход от начальной точки к смежной, соответствующей улучшенному значению целевой функции. Максимальное количество итераций, необходимых для получения оптимума (т.е. количество базисных решений), не превосходит п! /[п - т )т!, где п — число

переменных, а т — число уравнений модели линейного программирования.

Неограниченность целевой функции или пространства решений, а также отсутствие допустимых решений свидетельствуют о неточностях, допущенных при построении исходной математической модели.

ВЫВОДЫ

1. Предложен вариант формирования парка ВС на основе математической модели, построенной на базе линейного программирования, а именно с помощью симплекс-метода.

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

3. Современный оптимальный парк должен состоять из типов ВС с часовым расходом топлива до 3,0 т/ч при средней вместимости 140 пассажиров.

4. Предлагаемая методика позволяет определить оптимальный парк ВС как по отдельным авиапредприятиям, по федеральным округам, так и по стране в целом.

Литература

1. Аоки, М. Введение в методы оптимизации / М. Аоки. - М.: Наука, 1977. - 344 с.

2. Припадчев, А.Д. Определение оптимального парка воздушных судов. Монография / А.Д. Припадчев. - М.: Академия Естествознания, 2009. - 246 с.

3. Хэмди, А. Таха. Введение в исследование операций / Таха А. Хэмди. - М.: СПб.; Киев: Изд. дом «Вильямс», 2001. - 256 с.

Оренбургский государственный университет

DEFINITION OF NEEDFUL FLYING STOCK STRUCTURE BY THE LINEAR

PROGRAMMING METHOD A.D. Pripadсhev

The method of definition of the most effective function of an aircraft based on the developed algorithm of optimal variant choice with use of simplex method is validated and formulated in this article

Key words: aircrafts, parametrical row, linear programming, simplex-method, economic effectiveness