Оптимизация обобщенных многоцелевых систем

Тип работы:
Реферат
Предмет:
Физико-математические науки


Узнать стоимость

Детальная информация о работе

Выдержка из работы

УДК 519.5 doi: 10. 18 287/2223−9537−2015−5-4−411−428
ОПТИМИЗАЦИЯ ОБОБЩЕННЫХ МНОГОЦЕЛЕВЫХ СИСТЕМ
С.А. Пиявский
Самарский государственный архитектурно-строительный университет, Самара, Россия spiyav@mail. ru
Аннотация
В статье расширяется ранее введенное автором понятие многоцелевой системы. Многоцелевая система рассматривалась как множество элементов, в совокупности реагирующих на множество внешних воздействий путем оптимального распределения этих воздействий между собой. При этом полагалось, что в многоцелевой системе критерий оптимальности скалярен, любой элемент системы может реагировать на любое отдельное внешнее воздействие, причем исключительно автономно, то есть не в кооперации с другими элементами системы. В статье рассматривается модель обобщенной многоцелевой системы, где эти ограничения снимаются. Предусматриваются ограниченная возможность реагирования элементов системы на внешние воздействия, возможность совместного реагирования ее элементов на отдельные внешние воздействия и многокрите-риальность оценки эффективности функционирования системы. Предложены точные алгоритмы оптимизации интегральных и гарантирующих систем, основанные на модели смешанного линейного программирования. Учитывая их высокую размерность, предлагаются точные и эвристические методы снижения размерности численно решаемых при этом оптимизационных задач. В терминах оптимизации обобщенных многоцелевых систем могут успешно решаться задачи проектирования технических объектов и систем технических объектов, стандартизации и унификации, размещения и обслуживания и др.
Ключевые слова: многоцелевая система, оптимизация, проектирование, принятие решений, многокритериалъностъ, внешние факторы.
Введение
Понятие многоцелевой системы (МС) было введено в 70-х годах прошлого столетия при оптимизации параметров различных летательных аппаратов как обобщение так называемой «задачи об оптимальном покрытии» [1]. Характерной особенностью этого понятия является, наряду с рассмотрением множества допустимых решений (альтернатив), из которого предполагается выбрать оптимальное решение, ещё и так называемого «внешнего множества», которое отражает многообразие целей, критериев эффективности, условий функционирования, неопределённость исходных данных и прогнозных характеристик, органически присущее любой задаче проектирования. Так, проектирование самолета под так называемую «расчётную задачу», то есть под заданную дальность и величину целевой нагрузки либо объём пассажиропотока уже заранее обесценивает оптимальный характер решения, поскольку в реальности спроектированный самолет будет эксплуатироваться для различных целей: перевозить различные грузы на различные дальности в непредсказуемой на момент проектирования экономической среде. Отсюда следует, во-первых, необходимость ориентации искомого оптимального решения на весь диапазон внешних факторов, а во-вторых, возможно, многоэлементный характер этого решения, при котором отдельные его элементы «распределяют между собой» этот диапазон. Таким образом, под многоцелевой системой понималась система, которая состоит из одного или нескольких элементов множества допустимых решений, оптимально, в смысле некоторого скалярного критерия, реагирующих на совокупность внешних факторов (так называемое внешнее множество), распределяя его между собой.
Понятие М С получило ряд практических применений при исследовании сетей искусственных спутников Земли, универсальных космических аппаратов, структуры самолетного парка, типоразмерных параметрических рядов технических объектов и т. п., использовалось при разработке группы методов принятия многокритериальных решений ПРИНН [2−10]. В настоящей статье даётся его обобщение.
1 Математическая модель оптимальной простой многоцелевой системы
Сформулируем модель простой МС, для простоты считая множество допустимых решений и внешнее множество дискретными.
Обозначим через X = (х,},= п множество элементов, представляющих многообразие
внешних факторов, через У = (уу}J=1 т — множество элементов, из которых конструируется искомое оптимальное решение, через f (х, у), хе X, уе У — функцию, определяющую эффективность использования элемента решения уе У при реализации внешних факторов хе X. Будем называть X внешним множеством, У — множеством элементов решений, f (х, у) — локальными потерями. Будем полагать, что допустимым решением (многоэлементной стратегией1) А является любое непустое подмножество множества элементов решений, А с У.
Пусть 1 (х) = тт f (х, у), хе X — оптимальное (минимальное) возможное значение
уе У
локальных потерь в условиях реализации внешних факторов хе X. Примем для определённости 1 (х, у) & gt- 0, хе X, уе У и перейдём от функции локальных потерь к функции относительных потерь
(1) р (х, у) = 1 (х, у& gt- - 1 (х), хе X, уе У.
1 (х)
Она характеризует величину проигрыша из-за использования при внешних факторах хе X элемента решения уе У вместо элемента решения, оптимального для данных внешних факторов.
Примем, что при фиксированной многоэлементной стратегии, А е У каждому элементу внешнего множества сопоставляется тот из элементов стратегии, А е У, которому отвечает наименьшее по сравнению с остальными элементами стратегии значение относительного проигрыша. Его номер задаётся целочисленной так называемой распределяющей функцией Е (х). Тогда значение относительного проигрыша при реализации внешних факторов
х может быть записано как р (х, уЕ (х)), хе X, уЕ (х) е, А или
Ру = Р (х, Уу), гДе х, = х У = Е (х,).
Эффективность Г (X, А, Е (х)) использования многоэлементной стратегии Ае У и распределяющей функции Е (х) для «обслуживания» всего внешнего множества X будем
1 В процессе обсуждении статьи в редакции не по всем вопросам был достигнут консенсус с автором. В частности, насколько оправдано тождество между допустимым решением и многоэлементной стратегией. Ведь допустимое решение — это то, что возможно, а стратегия — то, к чему стремятся и что не всегда достижимо. Насколько оправдано использование самого понятия «многоцелевая» система, если фактически рассматривается неопределённость (многообразие) внешних условий, а не целей? А также к чему следует относить многообразие внешних факторов — к данности или к неуправляемому прогнозу? Редакция вновь обращается к нашим читателям и будущим авторам высказаться по затронутым вопросам. Прим. ред.
характеризовать максимальным (гарантирующим) или средним проигрышем на всей совокупности элементов множества X.
В первом случае будем говорить о гарантирующей многоцелевой системе (ГМС):
F = тахр (х, уе (,)).
1=1…п '-
Во втором случае будем говорить об интегральной многоцелевой системе (ИМС):
п
F = Хр (Хп УЕ (X)Ь
1=1
или, если известна функция «важности» различных элементов внешнего множества п (х) = п, 1 = 1,…, п,
п
^ п (х)р (X, Уе (х))
F = --п-.
?п (х)
1=1
Оптимальной будем называть пару (А, Е (х)), минимизирующую гарантирующий или средний проигрыш МС при заданном числе элементов стратегии р.
Представляется целесообразным расширение описанной модели в нескольких направлениях:
1) учёт областей достижимости — элементы решения могут использоваться не при всех внешних факторах (самолеты не могут летать на любые расстояния) —
2) учёт возможности комплексного использования не одного, а нескольких вариантов решения при реагировании на конкретные внешние факторы (совместное использование нескольких типов транспортных средств при выполнении одной операции, например, добираться до пункта назначения вначале поездом, а потом автомобилем) —
3) использование многокритериальной оценки эффективности решений, приводящее к векторной функции локальных потерь.
Построим математическую модель МС, учитывающую первые два направления.
2 Математическая модель
оптимальной комплексируемой многоцелевой системы
Назовём возможной реакцией системы на внешний фактор х нуль-единичный т -мерный вектор, а Гг = {аг }, номера единичных компонентов которого отвечают номерам
элементов решения, задействованных в обслуживании этого внешнего фактора. Таким образом, в модели отражается возможность не автономного, а комплексного (несколькими элементами множества решений) реагирования на отдельную реализацию внешнего фактора. Это даёт основания назвать подобную МС комплексируемой (К_МС). Обозначим через [ 1 количество таких допустимых реакций. Тогда исходное описание оптимизируемой МС включает множество реализаций внешних факторов X = {х1=1 п}, множество элементов
решений У = {уз=1 т}, множество допустимых реакций на внешние факторы, характеризуемое векторами, а, г1 = 1,…, 1= 1,…, п и скалярную функцию локальных потерь х, У, а) & gt- 0, оценивающую эффективность реакции, а на реализацию внешних факторов х. Аналогично (1), перейдём от неё к функции относительных потерь, обозначая её далее тем же символом:
(2) р (л-., Y, airl) = -1, r'- = 1… R, i = 1… n.
min ф (x, К, a ,)
q1 =1… r, '-
i=1… n
Обратим внимание, что, если в (1) нормирование производилось к минимальному значению локальных потерь при любых элементах решения, то в (2) участвуют минимальные значения локальных потерь при различных реакциях системы на отдельно взятую реализацию внешних факторов.
Таким образом, решение задачи оптимизации К_МС включает оптимальный набор элементов решений, задаваемый многоэлементной стратегией A, и оптимальную распределяющую функцию, характеризуемую включёнными в решение реакциями системы на внешние факторы.
Опишем произвольную стратегию A нуль-единичным вектором u = {uj}J=1 m, номера
единичных компонентов которого отвечают номерам элементов решения, вошедших в эту стратегию.
Условие ограниченности числа элементов стратегии. Число элементов стратегии p полагаем заданным или ограниченным сверху:
mm
X u = p или X u & lt- p.
i=1 i=1
Условия допустимости реакций системы. Конкретная стратегия определяет набор реакций системы, которые являются допустимыми в её рамках: все элементы решений, входящие в реакцию системы, должны быть включены в стратегию A. Допустимость реакции (i, r'-) при конкретной стратегии будем характеризовать нуль-единичным признаком допустимости v ,. Тогда указанное условие порождает следующие соотношения:
¦uj
X Ф
(3) vr, — J=m-, r'- = 1… R, i = 1… n.
Xj
J=1
Действительно, если какие-либо ненулевые компоненты вектора, определяющего реакцию, не входят в стратегию, числитель (3) будет меньше знаменателя, что повлечет нулевое значение булевого признака v'-. В противном же случае признак vr может
принимать как нулевое, так и единичное значения. Соотношение (3) удобнее рассматривать в эквивалентном виде
m m
VXaJ -Xa-Ju & lt- 0, r'- =1… R, '- =1…n.
j=1 J=1
Условия допустимости стратегий. При фиксированной стратегии для каждого варианта внешних факторов должна существовать хотя бы одна допустимая реакция
R,
системы: X vir- -1, '- = 1,…, n.
r'- =1
Введём булевый признак z^, / = 1,…, n, отражающий включение реакции системы (/, r'-) в
оптимальное решение. Тогда очевидны следующие соотношения. Условия допустимости оптимальной реакции.
z, & lt-, r'- = 1,…, R, '- = 1,…, n.
Условия однозначности оптимального решения.
я
, п.

г1 =1
(4)? = 1, '- = 1…
Обозначим через С) относительные потери при оптимальной реакции МС на реализацию внешних факторов х, 1 = 1,…, п. С учётом (4)
С = ?р (х, У, а^)^г, / = 1,…, п.
г =1
Критерий оптимальности при оптимизации комплексируемой ГМС (К_ГМС) примет вид
(5) F = йдаГ — тт
при условиях
С1 — С9аг, 1 =1… п,
а при оптимизации комплексируемой интегральной МС (К_ИМС)
п
? п (х)с1
F = ---& gt- т1п.
п (х)
=1
Предложенная математическая модель принадлежит к классу задач смешанного линейного программирования. Управлениями в ней являются переменные
п
V ., и, г ., с/, с!^. Их общее количество не более 2? [ + п + т+1, из них не более п + 1
Г и Г 1 даг Лш^ 1
=1
вещественн^1х, остальные булевы, а количество ограничений типа равенств и неравенств не
п
более 2? [ + 4п +1. Для решения такого рода задач существуют достаточно эффективные
=1
стандартные программы для ЭВМ.
3 Математическая модель
многокритериальной комплексируемой многоцелевой системы
Перейдем к рассмотрению МС, в которых функция локальных потерьДх1,У, а),
оценивающая эффективность реакции а. г1 системы на реализацию внешних факторов х
является не скалярной, а векторной:
Щ (х, y, а п) = {& lt-р, 4(х, У, а1Г,)}^=1…у.
Казалось бы, лишний индекс в символе функции р призван подчеркнуть, что для
различных элементов внешнего множества локальные потери могут измеряться различными критериями, число которых также может быть различно.
Как известно, переход от скалярного критерия к векторному порождает проблему неоднозначности при сравнении различных вариантов решения. В строгом смысле, само понятие оптимальности заменяется при этом более слабым понятием эффективности по Парето и, как правило, ряд вариантов решения оказываются несравнимыми по эффективности. Причина состоит в том, что непонятно, как соразмерить между собой значения различных критериев, если сами критерии по сути своей различны (например,
уровень комфорта пассажиров и взлетный вес самолета) и/или имеют различную строго неформализуемую важность, определяемую просто терминами «обычный», «важный», «более важный» (например, «увеличение комфорта пассажиров важнее, чем уменьшение взлетного веса самолета»).
В предлагаемой модели многокритериальной комплексируемой MC (МК_МС) первая
проблема решается переходом от исходных локальных потерь рq (x, Y, a), q = 1,…, Q, к соответствующим относительным потерям рр (Y, a. ,) r'- = 1,…, R, q = 1,…, Q'-, '- = 1,…, n аналогично (2)
Pq (Y, a,)
P (Y, ar'-) = q, —, -1, r'- = 1… R'-, q = 1… Q'-, '- = 1… n.
'-r min pq (Y, a '-)
q =1… r,'- '-q
'-=1… n
Эти потери имеют одинаковую шкалу (отвлечённые числа), что даёт возможность их сопоставления. Если нет оснований разделять критерии р (по относительной важности, то естественно принять для гарантирующей МК_МС скалярные относительные потери
р'-(Y, a) = max р ((Y, a), '- = 1,…, n,
'-r q=1… Q, '-r
а для интегральной MK_MC —
1 Q'-
Р. (Y, a, r,) = - X (P (Y, air.), '- = 1… n,
Q'- q=1
и далее решать задачу оптимизации для исходной МК_МС как для К_МС со скалярным вектором относительных потерь.
Если есть основания учитывать различную важность критериев р (, q = 1,…, Q, следует
использовать один из многочисленных существующих методов их «скаляризации» (см. например, [11]). Наиболее предпочтительным, по нашему мнению, являются методы ПРИНН [7, 10] и «шансов» [12, 13], поскольку они ориентированы на минимальное использование субъективной информации как по числу базовых постулатов, так и по объёму дополнительной информации от лица, принимающего решение, и хорошо алгоритмически проработаны.
Оба метода позволяют лицу, принимающему решение, просто отнести различные критерии к нескольким группам важности. Они учитывают математическим путём всё многообразие «разумных» способов свёртывания значений частных критериев в скалярное значение комплексного критерия. Метод ПРИНН для этого заменяет бесконечное множество «разумных способов» оптимальной? -сетью «типовых способов учёта неопределённости (в данном случае многокритериальности)» (ТСУН). Затем осуществляется итеративная процедура «согласования» оценок, полученных с помощью различных ТСУН, аналогичная процедуре ДЕЛФИ. Согласованные с заданной точностью значения оценок и являются значениями комплексного критерия. Приближённое значение этого критерия f может быть получено по формуле:
X -1
f = s=L-.
X 3я
s=1
Здесь 5 — количество частных критериев,, 5 = 1,…, 5 — их значения, к5 = 1,2…, — номера групп важности, к которым отнесены частные критерии. Например, если одни критерии
полагаются «обычной важности», другие — «более важными», а третьи — «самыми существенными», то для каждого критерия, входящего в первую группу к5 = 1, во вторую
группу — к5 = 2, в третью группу — к5 = 3. Это значение следует принять в качестве
скалярных локальных потерь.
Метод «шансов» даже отказывается от использования хотя и оптимального, но сравнительно небольшого набора типовых способов учёта неопределённости, и взамен методом Монте-Карло зондирует всё множество способов учёта неопределённости практически бесконечным числом испытаний, рассчитывая при каждом из них комплексную оценку эффективности каждого из сравниваемых вариантов решений. В результате рассчитывается жёсткий и мягкий рейтинг каждого варианта решения. Жёсткий рейтинг решения есть доля способов учёта неопределённости, при которых это решение является наилучшим по сравнению с остальными (в случае, если при каком-то способе учёта
неопределённости лучшими оказываются несколько (например, р=) решений, в жёстком
1
рейтинге каждого из них в сумме в числителе добавляется не 1, а -). Мягкий рейтинг
Р=
решения отражает среднюю по совокупности испытаний сравнительную эффективность этого решения по сравнению с решениями, оказавшимися наилучшими в соответствующих испытаниях. При использовании метода «шансов» в гарантирующих МК_МС в качестве скалярных локальных потерь естественно принимать жесткий рейтинг, а в интегральных МК_МС — мягкий.
Используя методы ПРИНН и «шансов», надо иметь в виду, что в них результирующая эффективность рассчитывается по шкале от нуля до единицы или 100-балльной шкале, причём единице или 100 баллам соответствует наилучший результат, поэтому, говоря о потерях, нужно вычитать результат, полученный этими методами, соответственно из единицы или 100 баллов.
Таким образом, задача многокритериальной оптимизации МС решается в два этапа. На первом этапе в рамках каждого элемента внешнего множества осуществляется переход от векторной оценки различных вариантов реакции системы на этот элемент к скалярным относительным потерям. Заметим, что если элементу внешнего множества отвечает единственная реакция системы, то этот элемент, как и варианты решения, порождающие эту реакцию, могут быть исключены из дальнейшей оптимизации, поскольку уже изначально должны войти в искомое оптимальное решение задачи. На втором этапе решается получившаяся задача оптимизации скалярной К_МС, как это описано в предыдущем разделе.
4 Уменьшение размерности решаемых оптимизационных задач
Размерность задач оптимизации К_МС может быть очень большой. Если в реакции на каждый вариант внешних факторов может использоваться каждый элемент множества решений У, то есть ^ = т, 1 = 1,…, п, то, как указывалось выше, число оптимизируемых переменных составит 2пт + п + т + 1, а число ограничений — 2тп + 4п + 1. Если допустимыми будут хотя бы парные реакции на внешние факторы всех элементов управления, то число переменных и ограничений будет около 2пт2. В этом случае, если множества X и У содержат хотя бы по сто элементов, задача оптимизации будет включать около двух миллионов оптимизируемых переменных и ограничений. Поэтому желательно предложить пути уменьшения размерности решаемых задач.
Для гарантирующей К_МС предлагается следующий экономный алгоритм.
Вначале определим для каждого элемента внешнего множества элементы множества решений, входящие в состав его реакции, имеющей нулевой относительный проигрыш (напомним, что в задачу оптимизации входят лишь элементы внешнего множества, на которые система отвечает не менее чем двумя возможными реакциями). Совокупность таких элементов определит многоэлементное решение «идеальной» гарантирующей К_МС, обозначим число элементов в нем через ртах. Такому решению отвечают нулевые
относительные потери. При меньшем количестве элементов решения относительные потери будут возрастать (точнее, не убывать).
Обратим задачу оптимизации: вместо поиска оптимального по критерию (5) решения, содержащего заданное количество р элементов, будем искать минимальную по количеству входящих в неё элементов стратегию, при которой критерий (5) принимает значение, не большее некоторого заданного значения 1.
Назовём реакцию системы односвязной, если она определяется единственным элементом решения, и многосвязной — если несколькими. Рассмотрим вначале К_МС, в которой в числе реакций системы на каждый вариант внешних факторов присутствует не более одной многосвязной реакции. Назовем такие К_МС слабосвязными.
Пусть рассматриваемая К_МС — слабосвязная. Зададимся некоторым числом 1 как значением критерия оптимальности, под которое ищется стратегия, включающая минимально возможное число элементов множества решений. Сохраним в рассмотрении лишь реакции, для которых
р (X,, У, 81У) & lt- 1, Г- = 1,…, Я,'- = 1,…, п.
Если при этом для какого-либо варианта внешних факторов оказались отброшены все реакции, это означает, что гарантирующая К_МС со столь низким значением критерия (5) не существует и следует задаться более высоким значением 1. Варианты внешних факторов, для которых сохранилась лишь одна реакция, можно исключить из дальнейшего рассмотрения вместе с элементами решения, входящими в эту реакцию, так как они уже обязаны быть включены в искомую оптимальную стратегию. Оставшаяся в рассмотрении К_МС также будет слабосвязной.
Для того чтобы реакция любой МС на конкретный элемент внешнего множества могла быть реализована оптимальным решением, необходимо и достаточно, чтобы в него были включены все элементы решения, определяющие эту реакцию. Соответственно необходимое и достаточное условие реализуемости отдельной реакции Г Для любой, не только слабосвязной, К_МС можно записать в виде
1 т
(6) -тт- ХэГЛ г 1.
К-& quot-
4=1
Для того чтобы система «отреагировала» на элемент внешнего множества х1, необходимо и достаточно выполнения хотя бы одного из условий (6). Но для слабосвязной К_МС все их
можно заменить единственным условием
Я, 1 т
^^ (т ^^ ^'-Г '- ^) ~ 1.
Г =1 У а4,
4=1
Преобразуем левую часть этого соотношения:
К, 1 т К, т ^ ц т К, ^ ц т К, ^
^^ (т ^^ аг/Ц)
=1 У г/ =1 ≠1 У 89, ≠1 г/ =1 У 89, ≠1 г& gt- =1 У 89,
?-I 1Г/ ?-I 1Г/ ?-I 1Г/ ?-I 1Г/
д=1 д=1 д=1 9=1
Окончательно получим
т К о!
(7) У (Х^-ц * 1-
. =1 у^
9=1
Ясно, что если хотя бы одно из условий (6) выполнено, то выполнение (6) очевидно даже не для слабосвязных К_МС. А вот выполнение хотя бы одного из условий (6) при выполнении условия (7) справедливо лишь для слабосвязных К_МС. Действительно, в (7) выражение, стоящее в круглых скобках для односвязных реакций, может быть равно либо нулю, либо единице- для многосвязной же реакции оно может быть и ненулевым, но меньшим единицы, если в оптимальное решение входят лишь некоторые элементы решения, определяющие эту реакцию. Поскольку К_МС слабосвязна, из выполнения (7) следует, что как минимум одна из круглых скобок равна единице, тогда как в случае не слабосвязной К_МС выполнение (7) могло бы быть достигнуто за счёт суммирования нескольких не равных единице круглых скобок, отвечающих многосвязным реакциям.
Замена условий (6) на (7) позволяет существенно снизить размерность решаемой оптимизационной задачи. Проводя аналогию с оценкой, приведённой в начале раздела 4, если в реакции на каждый вариант внешних факторов может использоваться каждый элемент множества решений У, то для слабосвязной К_МС с учётом (7) число оптимизируемых переменных составит 3п + т + 1, а число ограничений — 7п + 1. В этом случае, если множества X и У содержат по сто элементов, задача оптимизации будет включать около тысячи оптимизируемых переменных и ограничений.
Любую К_МС можно редуцировать до слабосвязной, введя дополнительные фиктивные элементы в множество решений, чтобы преобразовать «лишние» многосвязные реакции в односвязные. Например, если многосвязная реакция порождается тремя элементами решения у1, у2, у3, её можно сделать односвязной, порождаемой фиктивным элементом решения I. При этом в систему соотношений потребуется включить дополнительное соотношение
31 = У1 + У2 + Уз.
Итак, сформулируем задачу оптимизации слабосвязной К_ГМС с реакциями, которым отвечают относительные потери по сравнению с оптимальным реагированием на каждую отдельную реализацию внешних факторов, не превышающие заданного значения & lt-1.
Задача 1. Задано. Требуется найти стратегию, включающую минимальное количество элементов множества решений У и обеспечивающую реакции системы на любые внешние факторы из внешнего множества X.
Оптимизационная модель решения задачи 1.
Для Г: Р (Х1, У, Г) ^: = 1…
п
У ^ т1п
≠1
т К о!
(8) У (УЬт^-Ц & gt- 1,/=1…п.
^ г/ =1*9,
9=1
uj е {0,1}, j = 1,…, m.
Это задача булева линейного программирования с m переменными и n ограничениями типа неравенств, которая легко решается существующими стандартными программами для ЭВМ.
Решив задачу 1 для dmax = max р (xnY, a ir), можно найти минимальное количество
г,=1… R
элементов решений pmin, при котором К_МС обеспечивает реагирование на весь диапазон внешних факторов, представленный внешним множеством X. После этого рядом последовательных решений задачи 1 для различных значений параметра d в пределах от 0 до dmax можно получить зависимость минимально необходимого количества элементов
стратегии от параметра d (рисунок 1). Эта же зависимость (показана на рисунке 1 звёздочками) определяет оптимальные К_ГМС, которые при заданном числе элементов обеспечивают реагирование на любые реализации внешних факторов с минимальными гарантированными потерями.
В отличие от К_ГМС для В интегральных К_МС не удаётся
предложить алгоритм получения точного решения, который Ейш.г оперировал бы задачами
оптимизации существенно меньшей размерности, чем модель, представленная в разделе 2.
С целью уменьшения
вычислительной сложности решения задачи оптимизации, для К_ИМС -Aj. можно предложить лишь следующий
алгоритм улучшения. Он позволяет,
_^ ^ отталкиваясь от некоторой опорной
многоэлементной стратегии, А а Y, улучшить её и/или проверить её относительную оптимальность.
Рекомендуем в качестве опорной принимать стратегию,
оптимизирующую соответствующую гарантирующую К_МС. Пусть yj е A с Y — какой-либо элемент решения, входящий в стратегию A. Вычислим
его потенциал исключения F-j как суммарное увеличение значения критерия оптимальности
ИМС при переходе к стратегии A y. Затем для каждого варианта решения yk, не
входящего в A, рассчитаем его потенциал включения F+Jk как уменьшение возросшего
значения критерия оптимальности ИМС благодаря включению в стратегию A взамен исключённого элемента y элемента yk. Отметим, что расчёт потенциалов включения и
исключения не требует полного расчёта критерия оптимальности ИМС — достаточно внести изменения относительно лишь тех элементов внешнего множества, в которых деактивируются и активируются соответствующие элементам yj, yk реакции. Если
оказывается, что
Рисунок 1 — Зависимость числа элементов оптимальной К_ГМС от гарантированных потерь по сравнению с оптимальным реагированием на каждую отдельную реализацию внешних факторов
(9) F-J & lt- ,
то переходим от стратегии, А к более эффективной стратегии, А у и Ук и повторяем
процесс. Если же при переборе всех элементов множества У, А не нашлось элемента, для которого выполняется (9), делаем вывод, что стратегия, А обеспечивает относительный оптимум в задаче оптимизации ИМС.
Пример. Рассмотрим М С, внешнее множество которой включает 10 независимых внешних факторов, а множество стратегий — 5 элементов. Структура реакций системы на различные внешние факторы представлена в таблице 1. Среди реакций имеются многосвязные (они выделены) — таким образом, МС является комплексной (К_МС). Каждому внешнему фактору отвечает не более одной многосвязной реакции, следовательно, К_МС слабосвязная.
Внешние факторы разнокачественны, поэтому эффективность реагирования системы на каждый из них описывается своей системой критериев. Их количество для различных внешних факторов изменяется от 2 до 6. Значения критериев для каждой реакции приведены в таблице 2. Для определённости полагается, что желательным является минимизация каждого критерия.
Перейдём от исходных значений критериев эффективности реакций к оценке относительных потерь в эффективности по каждому критерию, связанных с тем, что соответствующая реакция реализуется системой взамен наиболее эффективной по данному критерию из-за того, что оптимальное решение не содержит всех элементов решения, необходимых для реализации наиболее эффективной реакции. Результаты показаны в таблице 3.
Предположим, что для каждого внешнего фактора различные критерии могут иметь различную значимость. В таблице 4 показана группа значимости каждого критерия. Напомним, что номер группы значимости не означает числовой величины, а указывает лишь, что, в рамках данного внешнего фактора, критерий с большим номером «важнее» критерия с меньшим номером.
Перейдём от векторной оценки относительных потерь по частным критериям, представленным в таблицах 3 и 4, к комплексной оценке. Для этого используем общедоступный метод ПРИНН. В таблице 5 приведены результаты расчётов.
Результаты, приведённые в таблице 5, являются исходными данными для оптимизации рассматриваемой МС.
Исследуем оптимальную гарантирующую МС, используя математическую модель (9). Из таблицы 5 видно, что минимальное значение комплексных относительных потерь равно 0,23. Лимитирующим при этом является внешний фактор 9.
При б = 0,23 матрица коэффициентов модели (9) имеет вид, показанный в таблице 6, а
оптимальное решение таково: и1 = 1, и2 = 1, и3 = 1, и4 = 1, и5 = 1, то есть включает все
элементы множества элементов решений.
Максимальное значение комплексных относительных потерь по всем реакциям системы, как следует из таблицы 5, равно 0,95. Соответствующая матрица коэффициентов модели приведена в таблице 7, ей соответствует оптимальное решение и1 = 1, и2 = 0, и3 = 1, и4 = 1, и5 = 1. Таким образом, установлено, что для того, чтобы с
некоторыми гарантированными потерями реагировать на все внешние факторы, МС должна содержать не менее четырёх из пяти возможных элементов решения.
Но при четырёх элементах решения гарантированные потери могут быть уменьшены. Направленным перебором б (методом дихотомии) можно установить, что минимальные
гарантированные потери при четырёх элементах оптимальной гарантирующей стратегии составляют величину 0,41.
Таблица 1 — Структура реакций М С Таблица 2 — Значения критериев эффективности
на внешние факторы реакций на внешние факторы
о и & lt-и и — Э 1 «» и Номера элементов решения 7
Номер вне фактора и, а п, а '- & lt-и я о К 1 2 3 4 5
1 0 0 1 1 1
1 2 0 1 0 0 1
3 1 0 0 0 0
2 1 0 0 0 1 0
2 1 0 1 1 1
1 0 1 0 0 0
3 2 0 0 1 1 1
3 1 0 0 0 0
4 0 0 0 1 0
1 1 0 0 0 0
4 2 0 0 0 0 1
3 1 1 1 0 0
5 1 0 0 1 0 0
2 0 1 0 0 0
6 1 1 0 1 0 1
2 0 1 0 0 0
1 0 0 0 1 0
7 2 1 0 0 1 1
3 0 0 1 0 0
8 1 1 0 1 1 1
2 0 0 0 1 0
1 0 0 1 0 0
9 2 1 0 1 0 0
3 0 1 1 1 1
10 1 1 0 0 0 0
2 1 1 1 1 1
Номер внешнего фактора, Номер реакции п Номера критериев эффективности реакции МС на внешний фактор
1 2 3 4 5 6
1 1 82 37 20
2 32 20 55
3 59 19 6
2 1 60 19 55 33
2 94 65 40 54
3 1 80 67 5
2 13 86 89
3 40 9 91
4 24 45 25
4 1 43 45 71
2 55 96 73
3 44 79 59
5 1 56 59 62 40 16
2 58 25 38 98 91
6 1 11 7
2 44 56
7 1 54 6 16 66 64 2
2 9 23 76 26 47 80
3 84 19 19 42 79 1
8 1 15 52
2 28 43
9 1 34 29 28
2 41 59 64
3 19 1 24
10 1 31 21
2 17 65
Таблица 3 — Относительные потери в эффективности частных критериев реакций на внешние факторы
Номер внешнего фактора Номер реакции Номера критериев эффек! реакции МС на внешний факто ивности р
1 2 3 4 5 6
1 1 1,56 0,95 2,33
2 0,00 0,05 8,17
3 0,84 0,00 0,00
2 1 0,00 0,00 0,38 0,00
2 0,57 2,42 0,00 0,64
3 1 5,15 6,44 0,00
2 0,00 8,56 16,80
3 2,08 0,00 17,20
4 0,85 4,00 4,00
4 1 0,00 0,00 0,20
2 0,28 1,13 0,24
3 0,02 0,76 0,00
5 1 0,00 1,36 0,63 0,00 0,00
2 0,04 0,00 0,00 1,45 4,69
6 1 0,00 0,00
2 3,00 7,00
7 1 5,00 0,00 0,00 1,54 0,36 1,00
2 0,00 2,83 3,75 0,00 0,00 79,00
3 8,33 2,17 0,19 0,62 0,68 0,00
8 1 0,00 0,21
2 0,87 0,00
9 1 0,79 28,00 0,17
2 1,16 58,00 1,67
3 0,00 0,00 0,00
10 1 0,82 0,00
2 0,00 2,10
Таблица 4 — Группы значимости критериев Таблица 5 — Комплексные относительные потери
эффективности реакций в эффективности реакций
на внешние факторы на внешние факторы
Номер внешнего фактора /'- Номера критериев эффективности реакций МС на внешний фактор
1 2 3 4 5 6
1 3 1 2
2 3 1 2 2
3 1 1 2
4 1 2 2
5 1 2 3 1 2
6 2 1
7 3 2 1 2 2 3
8 1 1
9 3 1 2
10 1 2
Номер внешнего фактора /'- Номер реакции Г Комплексные относительные потери р (, а. г,)
1 1 0,87
2 0
3 0,23
2 1 0
2 0,06
3 1 0,95
2 0,24
3 0,08
4 0,56
4 1 0
2 0,43
3 0
5 1 0,41
2 0
6 1 0
2 1
7 1 0,55
2 0,21
3 0,89
8 1 0
2 0
9 1 0,27
2 0,77
3 0,23
10 1 0
2 0,75
Таблица 6 — Коэффициенты оптимизационной модели при б = 0,23
Номер внешнего фактора / Номера элементов решения
1 2 3 4 5
1 1,00 0,50 0,00 0,00 0,50
2 0,25 0,00 0,25 1,25 0,25
3 1,00 0,00 0,00 0,00 0,00
4 1,33 0,33 0,33 0,00 0,00
5 0,00 1,00 0,00 0,00 0,00
6 0,33 0,00 0,33 0,00 0,33
7 0,33 0,00 0,00 0,33 0,33
8 0,25 0,00 0,25 1,25 0,25
9 0,00 0,25 0,25 0,25 0,25
10 1,00 0,00 0,00 0,00 0,00
Таблица 7 — Коэффициенты оптимизационной модели при б = 0,95
Номер внешнего фактора /'- Номера элементов решения
1 2 3 4 5
1 1,00 0,50 0,33 0,33 0,83
2 0,25 0,00 0,25 1,25 0,25
3 1,00 1,00 0,33 1,33 0,33
4 1,33 0,33 0,33 0,00 1,00
5 0,00 1,00 1,00 0,00 0,00
6 0,33 0,00 0,33 0,00 0,33
7 0,33 0,00 1,00 1,33 0,33
8 0,25 0,00 0,25 1,25 0,25
9 0,50 0,25 1,75 0,25 0,25
10 1,20 0,20 0,20 0,20 0,20
Окончательные результаты оптимизации исходной гарантирующей МС приведены в таблице 8, в которой выделены оптимальные реакции МС и показаны их относительные потери.
Таблица 8 — Результаты оптимизации гарантирующей МС
Номер внешнего фактора /'- Номер реакции Г Оптимальные реакции при оптимальной 4-элементной стратегии ц = 1, и2 = 0, иъ = 1, Ц, = 1, и15 = 1 проигрыш не более 0,41 Оптимальные реакции при оптимальной 5-элементной стратегии Ц = 1, и2 = 1, Ц = 1, и, = 1, Ц15 = 1 проигрыш не более 0,23
1 2 0
3 0,23
2 1 0 0
3 3 0,08 0,08
4 1 0 0
3 0 0
5 1 0,41
2 0
6 1 0 0
7 2 0,21 0,21
8 1 0 0
2 0 0
9 1 0,27
3 0,23
10 1 0 0
Заключение
В статье существенно расширена модель простой МС. Появилась возможность учитывать взаимодействие нескольких элементов многоэлементной стратегии МС при реагировании на разнообразные внешние факторы. Это привело к понятиям односвязной и многосвязной реакции и соответственно к рассмотрению своеобразных классов МС — слабосвязных и многосвязных. Указан метод преобразования многосвязной МС в слабосвязную. Предложены методы учёта многокритериальности в оценке эффективности реагирования МС на различные внешние факторы с помощью методов ПРИНН и «шансов». В результате рассматривается общая задача оптимизации многокритериальной многосвязной комплексируемой МС. Для краткости считаем целесообразным называть такую систему обобщенной многоцелевой системой (ОМС). Для ОМС в статье разработаны методы её оптимизации, основанные на аппарате смешанного линейного программирования. Это позволяет при решении конкретных прикладных задач существенно пополнять модель, вводя структурные связи между элементами стратегий и различными внешними факторами.
Список источников
[1] Пиявский, CA. Об оптимизации сетей / С. А. Пиявский // Известия А Н СССР. Техническая кибернетика. -1968. — № 1. — С. 68−80.
[2] Пиявский, CA. Оптимизация параметров многоцелевых летательных аппаратов / С. А. Пиявский, B.C. Брусов, Е. А. Хвилон. — М.: Машиностроение, 1974. — 106 с.
[3] Брусов, B.C. Комбинированная двигательная система, универсальная для диапазона маневров //
B.C. Брусов, В. В. Салмин // Космические исследования. — 1974. — Т. 12, № 3. — С. 368.
[4] Смирнов, ОЛ. САПР: формирование и функционирование проектных модулей. / О. Л. Смирнов,
C.А. Падалко, С. А. Пиявский — М.: Машиностроение, 1987. — 272 с.
[5] Галиев, Ш. И. Некоторые экстремальные многократные покрытия квадрата кругами / Ш. И. Галиев,
A.B. Хорьков // Вестник Казанского государственного технического университета им. А. Н. Туполева. -2014. — № 2. — С. 154−159.
[6] Galiev, S.I. Optimization of multiple covering of a bounded set with circles / S.I. Galiev, M.A. Karpova // Computational Mathematics and Mathematical Physics. — 2010. — Vol. 50., No. 4. — P. 721−732.
[7] Брусов, B.C. Синтез оптимального ансамбля нейроконтроллеров для многорежимного летательного аппарата / B.C. Брусов, Ю. В. Тюменцев // Вестник Московского авиационного института. — 2006. — Т. 13, № 2. -С. 67−78.
[8] Брусов, B.C. Применение теоретико-множественного подхода к учету неопределенностей при решении задач векторной оптимизации / B.C. Брусов, А. Л. Суздальцев // Автоматика и телемеханика. — 2008. — № 4. -С. 94−100.
[9] Брусов, B.C. Пример оценки решений в условиях нескольких критериев эффективности / B.C. Брусов, Ю. В. Одноволик // Научный вестник Московского государственного технического университета гражданской авиации. — 2013. — № 188. — С. 15−18.
[10] Брусов, B.C. Метод оценки решений при эксплуатации технических систем в условиях неоднозначности оценки эффективности / B.C. Брусов, Ю. В. Одноволик // Научный вестник Московского государственного технического университета гражданской авиации. — 2012. — № 175. — С. 78−83.
[11] Малышев, В .В. Метод принятия решений в условиях многообразия способов учёта неопределённости /
B.В. Малышев, Б. С. Пиявский, С. А. Пиявский // Известия РАН. Теория и системы управления. — 2010. — № 1. — С. 46−61.
[12] Ларичев, О. И. Теория и методы принятия решении, а также Хроника событий в Волшебных странах / О. И. Ларичев. — М.: Логос, 2002 — 392 с.
[13] Пиявский, CA. Два новых понятия верхнего уровня в онтологии многокритериальной оптимизации /
C. А. Пиявский // Онтология проектирования. — 2013. — № 1(7). — С. 65−85.
[14] Пиявский, CA. Прогрессивность многокритериальных альтернатив / С. А. Пиявский // Онтология проектирования. — 2013. — № 4(10). — С. 60−71.
OPTIMIZATION OF GENERALIZED MULTI-PURPOSE SYSTEMS S. A. Piyavsky
Samara State University of Architecture and Civil Building, Samara, Russia spiyav@mail. ru
Abstract
The article expands the definition of multi-purpose system that was previously implemented by the author. Multipurpose system is defined as a collection of elements that react to external impacts by reassigning parts of the impact between the members of the collection in an optimal way. It is assumed that the vector of the impact is always scalar, every element of the system is able to react to any kind of separate impact autonomously, without any interaction with other elements of the system. The article considers the model of the generalized multi-purpose system, where these restrictions are removed. The model described in the article allows for limited impact reaction of the system'-s elements. The possibility ofjoint response for impact for the elements of the system is considered. A multi-criteria methods of evaluation the system'-s performance is proposed. Accurate algorithms of optimization of integrated and guaranteeing systems based on the model of a mixed linear programming are proposed. Given the high dimensionality of the numerically solved tasks for the optimization problems, precise and heuristic methods for the dimensionality reduction are proposed. A variety of tasks, such as designing of objects and systems of objects, standardization and unification, arrangement of items, services and others can be solved by means of optimization of the generalized multi-purpose systems.
Keywords: multi-purpose systems, optimization, planning, decision making, multicriteriality, external factors.
Referents
[1] Piyavsky, S.A. Ob optimizatsii setej [About the networks optimization] / S.A. Piyavsky // Izvestiya RAS USSR. Tekhnicheskaya kibernetika. — 1968. — No.1. — P. 68−80. (In Russian).
[2] Piyavsky, S.A. Optimizatsiya parametrov mnogotselevykh letatel'-nykh apparatov [Parameter optimization of multipurpose aircrafts] / S.A. Piyavsky, V.S. Brusov, E.A. Hvilon. — Moscow: Mashinostroenie, 1974. — 106 p. (In Russian).
[3] Brusov, V.A. Kombinirovannaya dvigatel'-naya sistema, universal'-naya dlya diapazona manevrov [Combined propulsion system, universal for a range of maneuvers], V.S. Brusov, V.V. Salmin // Kosmicheskie issledovaniya. -1974. — Vol. 12, No. 3. — P. 368. (In Russian).
[4] Smirnov, O.L. SAPR: formirovanie i funktsionirovanie proektnykh modulej [CAD: the formation and operation of the project modules.]. / O.L. Smirnov, S.A. Padalko, S.A. Piyavskij — Moscow: Mashinostroenie, 1987. — 272 p. (In Russian).
[5] Galiev, S.I. Nekotorye ehkstremal'-nye mnogokratnye pokrytiya kvadrata krugami [Some extreme multiple coverings of a square with circles] / S.I. Galiev, A.V. Khor'-kov // Vestnik Kazanskogo gosudarstvennogo tekhnicheskogo universiteta im. A.N. Tupoleva. — 2014. — No.2. — P. 154−159. (In Russian).
[6] Galiev, S.I. Optimization of multiple covering of a bounded set with circles / S.I. Galiev, M.A. Karpova // Computational Mathematics and Mathematical Physics. — 2010. — Vol. 50, No. 4. — P. 721−732.
[7] Brusov, V.S. Sintez optimal'-nogo ansamblya nejrokontrollerov dlya mnogorezhimnogo letatel'-nogo apparata [Synthesis of optimal ensemble neyrokontrollerov for multi-mode aircraft]/ V.S. Brusov, Y.V. Tyumentsev // Vestnik Moskovskogo aviatsionnogo instituta. — 2006. — Vol. 13, No. 2. — P. 67−78. (In Russian).
[8] Brusov, V.S. Primenenie teoretiko-mnozhestvennogo podkhoda k uchetu neopredelennostej pri reshenii zadach vektornoj optimizatsii [Use of set theory approach to accounting for uncertainty in solving problems of vector optimization] / V.S. Brusov, A.L. Suzdal'-tsev // Avtomatika i telemekhanika. — 2008. — No. 4. — P. 94−100. (In Russian).
[9] Brusov, V.S. Primer otsenki reshenij v usloviyakh neskol'-kikh kriteriev ehffektivnosti [An example of assessment decisions under a number of performance criteria] / V.S. Brusov, Y.V. Odnovolik // Nauchnyj vestnik Moskovskogo gosudarstvennogo tekhnicheskogo universiteta grazhdanskoj aviatsii. — 2013. — No. 188. — P. 15−18. (In Russian).
[10] Brusov, V.S. Metod otsenki reshenij pri ehkspluatatsii tekhnicheskikh sistem v usloviyakh neodnoznachnosti otsenki ehffektivnosti [The method of assessment solutions in the operation of technical systems in a mixed as-
sessment of the effectiveness] / V.S. Brusov, Y.V. Odnovolik // Nauchnyj vestnik Moskovskogo gosudarstvennogo tekhnicheskogo universiteta grazhdanskoj aviatsii. — 2012. — No. 175. — P. 78−83. (In Russian).
[11] Malyshev, V.V. Metod prinyatiya reshenij v usloviyakh mnogoobraziya sposobov ucheta neopredelennosti [The method of decision-making in a variety of ways to deal with uncertainty] / V.V. Malyshev, B.S. Piyavskij, S.A. Piyavskij // Izvestiya RAN. Teoriya i sistemy upravleniya. — 2010. — No 1. — P. 46−61. (In Russian).
[12] Larichev, O.I. Teoriya i metody prinyatiya reshenii, a takzhe Khronika sobytij v Volshebnykh stranakh [Theory and methods of decision making, as well as the Chronicles of the Magic country] / O.I. Larichev. — Moscow: Logos, 2002. — 392 p. (In Russian).
[13] Piyavsky, S.A. Dva novykh ponyatiya verkhnego urovnya v ontologii mnogokriterial'-noj optimizatsii [Two new concepts of top-level ontology of multi-criteria optimization] / S.A. Piyavskij // Ontology of designing. — 2013. -No. 1(7). — P. 65−85. (In Russian).
[14] Piyavsky, S.A. Progressivnost'- mnogokriterial'-nykh al'-ternativ [The progressiveness of multicriteria alternatives] / S.A. Piyavskij // Ontology of designing. — 2013. — No. 4(10). — P. 60−71. (In Russian).
Сведения об авторе
Пиявский Семён Авраамович. Окончил Куйбышевский авиационный институт в 1964 году, аспирантуру при кафедре динамики полета Московского авиационного института в 1967 году. Доктор технических наук, профессор, заведующий кафедрой прикладной математики и вычислительной техники Самарского государственного архитектурно-строительного университета. Почетный работник высшей школы РФ, академик Академии наук о Земле и Академии нелинейных наук. Опубликовал более 350 научных работ в области системного анализа, методов оптимизации и принятия решений, математического моделирования, образовательных систем и технологий. Основные научные результаты: онтологии образовательного процесса, методы многоэкстремальной оптимизации, решения краевых задач для систем обыкновенных дифференциальных уравнений, принятия решений в условиях неустранимой неопределенности, оптимизации сетей ИСЗ, оптимизации многоцелевых систем летательных аппаратов- теория многоцелевых систем, компьютерная технология технического творчества, теория оптимального управления развитием научных способностей молодежи, новые формы организации образовательного процесса в высшей школе в условиях развитой инфокоммуникационной среды и др.
Semen Avraamovich Piyavsky. Graduated from Kuibyshev Aviation Institute in 1964 and the graduate school at the Flight Dynamics Department at the Moscow Aviation Institute in 1967. Doctor of Technical Sciences, Professor, Head of the Department of Applied Mathematics and Computer Science at Samara State University of Architecture and Civil Engineering. Honored Worker of Higher School of Russia, Academician of the Academy of Earth Sciences and Academy of Nonlinear Sciences. He has published over 350 scientific papers in field of system analysis, optimization techniques and decision-making, mathematical modeling, education systems and technologies. Basic scientific results: education ontologies, Multiple-optimization techniques, solution of boundary value problems for systems of ordinary differential equations, decision making under fatal uncertainty, computer technology of engineering creation, the optimal control theory of young people'- academic abilities development, new forms of organization of educational process in higher education in advanced info-communications environment, etc.
m

ПоказатьСвернуть
Заполнить форму текущей работой