close

Вход

Забыли?

вход по аккаунту

?

К вопросу о точности эвристических алгоритмов при решении оптимизационных задач в эксплуатации.

код для вставкиСкачать
НАУЧНЫЙ ВЕСТНИК МГТУ ГА
2012
№ 179
УДК 658.66.0146629.73
К ВОПРОСУ О ТОЧНОСТИ ЭВРИСТИЧЕСКИХ АЛГОРИТМОВ
ПРИ РЕШЕНИИ ОПТИМИЗАЦИОННЫХ ЗАДАЧ В ЭКСПЛУАТАЦИИ
Л.Н. ЕЛИСОВ
В статье рассматривается оригинальный подход автора к проблеме решения одного класса оптимизационных
задач в области эксплуатации воздушного транспорта с применением эвристических процедур.
Ключевые слова: оптимизация, критерии, эвристика.
В большинстве своих работ, опубликованных за последние десять лет, автор показывает
универсальные возможности использования понятия «качество» как некоторого критерия при
решении определенного класса оптимизационных задач в области эксплуатации воздушного
транспорта.
К указанному классу можно отнести задачи, связанные с оптимизацией управленческих
процедур в социально-экономических системах, с оптимизацией структуры эксплуатационных
комплексов гражданской авиации, в том числе образовательных учреждений, с оптимальным
управлением авиационным персоналом. Кроме того, практически все задачи, связанные с проблемами безопасности полетов и авиационной безопасности, относятся к этому классу.
Все эти задачи объединяются в один класс прежде всего по отношению к объекту исследования: интересующие нас объекты относятся к категории сложных систем в терминах системотехники [1]. Управление и оптимизация в таких системах принципиально отличаются от классических представлений, поскольку и та, и другая процедуры здесь основаны на ситуационном
подходе. С другой стороны, сложные системы при их исследовании требуют чрезвычайно
большого числа анализируемых параметров и критериев оптимизации, что переводит проблему
в класс NP – сложных задач, которые даже сегодня не имеют численного решения.
В таком случае требуются новые подходы и методы, в качестве которых автор предлагает
использовать квалиметрию, включающую эвристические алгоритмы.
Рассмотрим задачу оптимизации управления образовательными комплексами гражданской
авиации.
Любая оптимизация предполагает некоторую формализацию. С этой целью в работе [1] было получено выражение для целевой функции образовательного комплекса в виде «математического уравнения обучения», под которым понимается зависимость между уровнем знаний
обучаемого, временем обучения и стоимостью обучения. Уравнение имеет вид
1
H=
N
∑ γ i (1 − e −λsi )(1 − e −µti ).
N
(1)
i =1
В работе [1] представлены результаты аналитического решения уравнения (1) в форме трех
оптимизационных задач: за заданное время Т и выделенные на обучение денежные средства S
обеспечить максимальный уровень знаний обучающихся Н; за заданное время Т и при заданном
уровне подготовки обучающихся Н обеспечить минимум средств S; за выделенные средства S и
при заданном уровне подготовки обучающихся Н обеспечить минимум необходимого для этого
времени Т.
Первая задача не имеет замкнутого аналитического решения.
Аналитическое решение второй задачи получено в виде
124
Л.Н. Елисов
∑ [γ i (1 − e − µti )− NH ]
N
N
λ S min = − ln i =1
N
N
∏ γ i (1 − e
N
− µti
i =1
)
,
(2)
где минимальное значение для S рассматривается как функция распределенного временного ресурса T =
N
∑ ti .
i =1
Для третьей задачи минимальное значение для Т рассматривается как функция распределенного денежного ресурса S =
N
∑ si
i =1
∑ [γ i (1 − e − λsi )− NH ]
N
N
µTmin = − ln i =1
N
N
∏ γ i (1 − e
N
i =1
− λsi
)
.
(3)
Выражения (1), (2), (3) получены в результате достаточно сложных логических и математических преобразований. В работе (1) представлена качественная оценка этих зависимостей в виде
графической интерпретации. Важно отметить, что коэффициенты µ, γ, λ, используемые в (1), (2),
(3), являются комплексными, т.е. каждый из них включает достаточно объемную совокупность
характеристик образовательного комплекса. Более того, сам подход к формулировке оптимизационных задач вполне эмпирический, поскольку совокупность анализируемых параметров описывает анализируемый объект весьма приблизительно. Напрашивается однозначный вывод о невозможности аналитического решения рассматриваемых оптимизационных задач.
В работах [1; 2] представлены результаты решения аналогичных задач: оптимизация структуры авиационного предприятия, оптимизация процедур управления авиационным персоналом,
организация системы авиационной безопасности аэропорта, прогнозирование уровня авиационной безопасности аэропорта, оптимальное решение производственного конфликта. Вывод один
- для решения задач подобного класса необходимы новые подходы и методы.
Идея предлагаемого автором подхода состоит в следующем: всю совокупность анализируемых параметров и критериев оптимизации предлагается «спрятать» внутри единого критерия – «качество», воспользовавшись определением этого понятия. В соответствии со стандартами ИСО качество есть степень соответствия присущих характеристик требованиям. Тогда
практически для всех прикладных задач исследуемого класса вполне допустимой является процедура последовательного перехода от реальных параметров объекта оптимизации к параметру
качества объекта по этому параметру.
Процедура вполне согласуется с известной процедурой упорядочивания критериев оптимизации, за одним исключением: сложная математическая операция допустимой трансформации
критериев заменяется эвристической процедурой перехода к параметру качество. Указанный
подход назван квалиметрической оптимизацией. Рассмотрим процедуру квалиметрической оптимизации, последовательно усложняя исследуемые критерии от скалярного до многовекторного
представления.
Скалярная квалиметрическая оптимизация. В том случае, когда критерии оптимизации выражены через скалярные величины, вопрос о переходе к качеству решается достаточно просто:
в этом случае мы имеем право поставить в соответствие значение критерия и уровень качества,
приняв единую шкалу измерения критериев и определив шкалу оценки уровня качества. Тогда
125
К вопросу о точности эвристических алгоритмов при решении оптимизационных задач …
квалиметрическая оптимизация состоит в процедуре вычисления минимального, максимального
и среднего значений качества.
Линейная, векторная квалиметрическая оптимизация. Предположим, что у нас имеется
один критерий оптимизации, но он отображается векторной величиной, а параметры этого критерия есть скалярные величины. Задача состоит в трансформации векторного критерия в параметр качества.
Для перехода от этих параметров к качеству необходимо сформулировать совокупность
требований к каждому параметру, причем выполнимость этих требований в полном объеме однозначно определяет скалярное значение этого параметра в выбранной шкале. Для перехода к
качеству необходимо оценить степень соответствия реальных характеристик указанным требованиям, выставив соответствующие оценки в выбранной шкале. Для реализации описанной
процедуры предлагается использовать линейную квалиметрическую матрицу (рис. 1).
А1
А2
В1
КС11
КС12
КС1х
КСm1
В2
КС21
КС22
КС2х
КСm2
……
Ах
.
.
.
.
.
.
Ву
КСn1
КСу1
КСу2
КСn2
……
КСух
КСnх
КСnm
КСnm
Обобщенное
качество
Рис. 1. Линейная квалиметрическая матрица
Если количество критериев больше двух или векторизация более глубокая, т.е. вектор (критерий) имеет параметры в форме векторных величин, параметры которых, в свою очередь, тоже
векторные величины и т.д., плоская матрица превращается в кубическую и т.д.
В заключение важно отметить следующее:
1. Все вышеизложенное можно рассматривать как классическую процедуру упорядочивания критериев оптимизации на основе квалиметрических представлений. Подобный подход
рассматривается только в приложении к оптимизационным задачам указанного класса и не претендует на расширение области применения.
2. Завершающий этап оптимизации включает процедуры принятия решений компетентным
лицом (ЛПР), т.е. в значительной степени представляет собой эвристический алгоритм независимо от сущности предыдущих этапов оптимизации.
3. Точность оптимизационных процедур и алгоритмов в данном случае представляет собой
степень соответствия принятого решения целевой функции исследуемого объекта. Отсюда точность как один из важнейших параметров оптимизации находится внутри выбранного критерия
оптимизации – качество.
4. Применение эвристических алгоритмов на завершающем этапе оптимизации исключает
использование точных оптимизационных процедур на предыдущих этапах.
5. Опора на «человеческий фактор» (ЛПР) при реализации процедур оптимизации позволяет включить в контур оптимизации интуицию и опыт ЛПР, что при решении поставленной задачи в большинстве случаев более важно, чем математическая доказательность.
126
Л.Н. Елисов
ЛИТЕРАТУРА
1. Елисеев Б.П., Елисов Л.Н. Системотехническое управление образовательными комплексами: монография.
- М.: МГТУ ГА, 2012.
2. Елисов Л.Н. Качество профессиональной подготовки авиационного персонала и безопасность воздушного
транспорта: монография. - М.: ИЦПКПС, 2006.
TO A QUESTION OF ACCURACY OF HEURISTIC ALGORITHMS
AT THE SOLUTION OF OPTIMIZING TASKS IN OPERATION
Elisov L.N.
In the article the authors original approach to the problem of solving a class of optimization problems in the field of
air transport with the use of heuristics.
Key words: optimization, criterions, heuristic.
Сведения об авторах
Елисов Лев Николаевич, 1945 г.р., окончил Пензенский политехнический институт (1967), профессор, доктор технических наук, профессор кафедры безопасности полетов и жизнедеятельности
МГТУ ГА, автор более 200 научных работ, область научных интересов – безопасность воздушного
транспорта, человеческий фактор, квалиметрия, социальные и экономические системы.
Документ
Категория
Без категории
Просмотров
5
Размер файла
106 Кб
Теги
оптимизационными, решение, точности, вопрос, алгоритм, эксплуатации, задачи, эвристических
1/--страниц
Пожаловаться на содержимое документа