Компромиссный метод решения задач условной оптимизации

Розглянуто можливість компромісного розв’язку в задачах умовної оптимізації. Проблема полягає в тому, щоб отриманий розв’язок відображав компроміс між суперечливими вимогами екстремізації цільової функції і виконання обмежень. Для розв’язання розглянутої проблеми використовується підхід багатокритер...

Повний опис

Збережено в:

Бібліографічні деталі
Дата:	2012
Автор:	Воронин, А.Н
Формат:	Стаття
Мова:	Russian
Опубліковано:	Інститут кібернетики ім. В.М. Глушкова НАН України 2012
Назва видання:	Проблемы управления и информатики
Теми:	Оптимальное управление и методы оптимизации
Онлайн доступ:	https://nasplib.isofts.kiev.ua/handle/123456789/207529
Теги:	Додати тег Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Цитувати:	Компромиссный метод решения задач условной оптимизации / А.Н. Воронин // Проблемы управления и информатики. — 2012. — № 5. — С. 64–70. — Бібліогр.: 3 назви. - рос.

Репозитарії

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	irk-123456789-207529
record_format	dspace
spelling	irk-123456789-2075292025-10-12T00:05:53Z Компромиссный метод решения задач условной оптимизации Компромісний метод розв’язання задач умовної оптимізації A Compromise Method of Constrained Optimization Problems Solution Воронин, А.Н Оптимальное управление и методы оптимизации Розглянуто можливість компромісного розв’язку в задачах умовної оптимізації. Проблема полягає в тому, щоб отриманий розв’язок відображав компроміс між суперечливими вимогами екстремізації цільової функції і виконання обмежень. Для розв’язання розглянутої проблеми використовується підхід багатокритеріальної оптимізації з застосуванням нелінійної схеми компромісів. Наведено модельний приклад. The possibility of obtaining a compromise solution to the problems of constrained optimization is investigated. The problem is that the resulting decision should reflect a compromise between the conflicting requirements of objective function extremalization and performance of limitations. For the decision of a considered problem, the approach of multicriteria optimization with use of the nonlinear trade-off scheme is undertaken. An illustrative example is given. 2012 Article Компромиссный метод решения задач условной оптимизации / А.Н. Воронин // Проблемы управления и информатики. — 2012. — № 5. — С. 64–70. — Бібліогр.: 3 назви. - рос. 0572-2691 https://nasplib.isofts.kiev.ua/handle/123456789/207529 519.9 10.1615/JAutomatInfScien.v44.i9.60 ru Проблемы управления и информатики application/pdf Інститут кібернетики ім. В.М. Глушкова НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Russian
topic	Оптимальное управление и методы оптимизации Оптимальное управление и методы оптимизации
spellingShingle	Оптимальное управление и методы оптимизации Оптимальное управление и методы оптимизации Воронин, А.Н Компромиссный метод решения задач условной оптимизации Проблемы управления и информатики
description	Розглянуто можливість компромісного розв’язку в задачах умовної оптимізації. Проблема полягає в тому, щоб отриманий розв’язок відображав компроміс між суперечливими вимогами екстремізації цільової функції і виконання обмежень. Для розв’язання розглянутої проблеми використовується підхід багатокритеріальної оптимізації з застосуванням нелінійної схеми компромісів. Наведено модельний приклад.
format	Article
author	Воронин, А.Н
author_facet	Воронин, А.Н
author_sort	Воронин, А.Н
title	Компромиссный метод решения задач условной оптимизации
title_short	Компромиссный метод решения задач условной оптимизации
title_full	Компромиссный метод решения задач условной оптимизации
title_fullStr	Компромиссный метод решения задач условной оптимизации
title_full_unstemmed	Компромиссный метод решения задач условной оптимизации
title_sort	компромиссный метод решения задач условной оптимизации
publisher	Інститут кібернетики ім. В.М. Глушкова НАН України
publishDate	2012
topic_facet	Оптимальное управление и методы оптимизации
url	https://nasplib.isofts.kiev.ua/handle/123456789/207529
citation_txt	Компромиссный метод решения задач условной оптимизации / А.Н. Воронин // Проблемы управления и информатики. — 2012. — № 5. — С. 64–70. — Бібліогр.: 3 назви. - рос.
series	Проблемы управления и информатики
work_keys_str_mv	AT voroninan kompromissnyjmetodrešeniâzadačuslovnojoptimizacii AT voroninan kompromísnijmetodrozvâzannâzadačumovnoíoptimízacíí AT voroninan acompromisemethodofconstrainedoptimizationproblemssolution
first_indexed	2025-10-12T01:08:27Z
last_indexed	2025-10-13T01:08:48Z
_version_	1845826922282483712
fulltext	© А.Н. ВОРОНИН, 2012 64 ISSN 0572-2691 УДК 519.9 А.Н. Воронин КОМПРОМИССНЫЙ МЕТОД РЕШЕНИЯ ЗАДАЧ УСЛОВНОЙ ОПТИМИЗАЦИИ Введение Задачи оптимизации в различных предметных областях обычно сводятся к поиску экстремума целевой функции, ограниченной условиями, наложенными на аргументы оптимизации. Для решения таких задач привлекается аппарат матема- тического программирования. Изложим кратко некоторые основные понятия из этой области. Математическое программирование используется для разрабатывания мето- дов отыскания экстремальных значений целевой функции )(xf среди множества ее возможных значений, определяемых ограничениями ).(x Достаточно общая задача математического программирования формулирует- ся так: найти оптимальное сочетание аргументов оптимизации, доставляющее экстремум целевой функции при заданных ограничениях: ),(extrarg* xfx Xx  при ]}.,1[,0)(],,1[,0{ mjxnixxX ji  Допускаются ,mn  ,mn  .mn  Функции )(xf и )(xj произвольные. В зависимости от свойств целевой функции и функций ограничений все зада- чи математического программирования делятся на два основных класса:  задачи линейного программирования,  задачи нелинейного программирования. Если целевая функция и функции ограничений — линейные функции, то со- ответствующая задача поиска экстремума является задачей линейного програм- мирования. Если хотя бы одна из указанных функций нелинейная, то соответ- ствующая задача поиска экстремума является задачей нелинейного программиро- вания. В настоящей работе ограничимся рассмотрением задач нелинейного программирования. Для конструктивного решения задачи делаются дополнительные частные предположения. В наиболее простом случае рассматривается задача без ограни- чений (оптимизация в открытой области, безусловная оптимизация). Обычно ис- пользуется необходимое условие экстремума функции как следствие из теоремы Ферма: ,0/)(  ixxf ],,1[ ni имея в виду, что достаточное условие (минимум или максимум) вытекает из фи- зического смысла задачи. При необходимости достаточное условие определяется по знаку второй производной в точке экстремума (знак плюс означает минимум функции, а минус — максимум). Решая эту систему уравнений, получаем требуе- мый набор 0xx  из n аргументов оптимизации. Наличие ограничений принципиально отличает задачи математического про- граммирования от обычных задач математического анализа по отысканию экс- тремальных значений функции. В этом случае имеет место условная оптимизация. Международный научно-технический журнал «Проблемы управления и информатики», 2012, № 5 65 В классической постановке рассматри- вается случай строгого равенства ограниче- ний некоторым константам: jj bx  )( ],,1[ mj это так называемая изоперимет- рическая задача («задача Дидоны»). На рис. 1 показана двумерная по аргу- ментам и с одним ограничением изоперимет- рическая задача. Поверхность функции )(xf представляется линиями равного уровня const)( xf (как на топографических кар- тах), а ограничение — проекцией пространственной кривой bx  )( на координат- ную плоскость. Для решения изопериметрических задач пользуются методом множителей Лагранжа. Составляется функция Лагранжа )],([)(),( 1 xbxfx jjj m j    где ,j ],,1[ mj — неопределенные множители Лагранжа, которая исследуется на безусловный экстремум. Для этого используется необходимое условие экстре- мума функции и решается система уравнений ,0/  ix ];,1[ ni ,0/  jjj b ].,1[ mj Получается n значений вектора x (точка А на рис. 1) и, как побочный результат, m значений вектора  множителей Лагранжа, при котором уравнения связей вы- полняются строго. Из анализа физического смысла множителей Лагранжа следует, что по вели- чине l-го множителя ,l ],,1[ ml можно судить о мере несоответствия l-го усло- вия связи и требования экстремизации целевой функции. Действительно, пусть кривая bx  )( на рис. 1 такова, что проходит через точку )0(x экстремума функции ).(xf В этом случае процедура множителей Лагранжа дает результат 0xx  и ,0 т.е. здесь требования выполнения ограничения и экстремизации целевой функции не противоречат друг другу. И наоборот, чем дальше точка x от ,)0(x тем больше значение коэффициента . Следовательно, множители Ла- гранжа  в данной задаче являются векторной мерой того, насколько строгие уравнения ограничений «мешают» достичь экстремума функции ).(xf Если ограничения заданы как неравенства ,0)(  x а функции )(xf и )(x выпуклые, то для решения задачи привлекается теорема Куна–Таккера, которая обобщает теорему Лагранжа для неклассических задач. Приведем краткую фор- мулировку теоремы Куна–Таккера: для того, чтобы целевая функция )(xf дости- гала в точке x глобального условного экстремума, необходимо и достаточно, чтобы ,x  являлась глобальной седловой точкой функции Лагранжа. Это зна- чит, что ),(),(),( **  xxx для всех х, λ из области определения задачи. f const ψb A x 1x 2x 0x Рис. 1 66 ISSN 0572-2691 В соответствии с этой теоремой при заданных предположениях поверхность функции Лагранжа в пространстве ),( x имеет оптимальную точку ,x , кото- рая является седловой и определяется как ).,(maxminarg,   xx x Алгоритм решения задач поиска экстремумов в случае функций с седловыми точ- ками обычно сводится к решению системы уравнений ,0            ixi i x x ];,1[ ni ,0              j j j ].,1[ mj Из анализа задачи условной оптимизации следует, что требования, предъяв- ляемые к экстремизации целевой функции, и выполнения ограничений противо- речивы. При этом в изопериметрической задаче приоритет полностью отдается выполнению ограничений, а целевая функция экстремизируется при условии их строгого выполнения. В задаче Куна–Таккера эти противоречивые требования удовлетворяются строго в одинаковой мере. Между тем само понятие противоречивости требований предполагает воз- можность компромисса. Результатом этого вывода может быть методика реше- ния, при которой условия связи выполняются не точно, а компромиссно. Если принять это допущение, то решения, полученные с помощью множителей Ла- гранжа, представляются всего лишь точками в континууме возможных компро- миссных решений. Проблема состоит в том, чтобы полученное при этом допущении решение отражало компромисс между противоречивыми требованиями экстремизации це- левой функции и выполнения ограничений. Если указанные противоречивые тре- бования облечь в форму частных критериев, то такая ситуация дает основание для привлечения к решению задачи условной оптимизации подхода многокритери- альной (в данном случае двухкритериальной) оптимизации. Субъективность в методике решения задачи По своей сути компромисс является прерогативой человека, лица, принима- ющего решение (ЛПР). Получая компромиссное решение, мы намеренно вводим в методику решения задачи субъективный фактор в виде предпочтений ЛПР. Оста- новимся на этом подробнее. В настоящее время в науке все чаще проявляются черты смены парадигмы, перехода от стиля классицизма к концепциям постклассической науки. Характер- ной чертой стиля современной науки является включение в методику решения за- дач человека (эксперт, ЛПР), в отличие от классической науки, возводившей фор- мализацию в абсолют и ставившей целью исключать при описании действитель- ности все сколько-нибудь субъективные суждения. Считалось, что познание следует освобождать от случайностей, пристрастий и слабостей индивидуального человеческого исполнения. Наука строится по стро- гим правилам логики, и поэтому часто кажется, что личностное, человеческое — наши идеи, пристрастия, общее представление о мире — никакой роли не играет. Но любая логика начинает развиваться от постулатов, от аксиом, которые сами по себе никак логически не обоснованы. Бесспорно, естественные науки изучают объективный мир природы, находящейся вне нас и от нас не зависимый. Но ис- следователь рассматривает этот мир глазами человека определенной эпохи, опре- деленной культуры, наконец, определенного психического и интеллектуального склада, — и все это накладывает отпечаток на его деятельность и результаты этой деятельности. Международный научно-технический журнал «Проблемы управления и информатики», 2012, № 5 67 Создание и выбор моделей, конкретизация целевого функционала и выбор метода исследования несут отпечаток личности исследователя, а в области изуче- ния сложных систем незаменим его личный опыт и интуиция [1]. Наука включает в свой предмет человека, допуская элементы субъективности в объективно истин- ном знании. Наблюдатель осознает себя частью исследуемого мира, активно вза- имодействующей с наблюдаемым объектом. Возвращаясь к понятию компромисса, заметим, что вся теория многокрите- риальной оптимизации построена на идеях компромисса и все ее проблемы сво- дятся к способам формализации субъективных предпочтений ЛПР. Постановка задачи Логика компромисса требует, чтобы при решении задачи на условный экс- тремум назначались границы допустимых, с точки зрения ЛПР, отступлений от строгих равенств по ограничениям, а также определялась предельно допустимая для него величина ухудшения целевой функции. Эти назначенные величины об- разуют пространство компромисса, в котором ищется приемлемое для данного ЛПР компромиссно-оптимальное решение. Пусть выражения ,0)(  xj ],1[ mj таковы, что по физическим сообра- жениям могут быть допущены отступления от строгих равенств в некоторых назначенных пределах: jj Ax  )( ].,1[ mj Положим для определенности, что целевая функция )(xf является минимизиру- емой. Определена некоторая предельная величина, выше которой минимизируе- мая целевая функция, с точки зрения ЛПР, не может (или не должна) поднимать- ся: .)( Bxf  Ставится задача: определить компромиссно-оптимальное решение .x Метод решения В данной задаче выражения для ограничений )(xj и целевая функция )(xf могут рассматриваться как своего рода минимизируемые, неотрицательные и ограниченные критерии. Возникают все предпосылки для применения к задаче условной оптимизации подхода многокритериальной оптимизации. Суть понятия «компромисс» заключается в ответе на вопрос: сколькими еди- ницами выигрыша по одному критерию можно, по мнению ЛПР, компенсировать неизбежный проигрыш единицы по другому критерию (другим) в заданной ситу- ации? На основании этой информации формулируется конкретная схема компро- миссов для данной многокритериальной задачи и в итоге находится искомое ре- шение. Таким образом, определение многокритериального решения по своей приро- де компромиссно и основано на использовании субъективной информации. Имея эту информацию и выбрав схему компромиссов, можно перейти от общего век- торного выражения к скалярной свертке частных критериев, что является основой для построения конструктивного аппарата решения многокритериальных задач. Возможность решения проблемы основана на гипотезе существования некоторой функции полезности, возникающей в сознании ЛПР при решении конкретной многокритериальной задачи. Можно утверждать, что практически все подходы к определению скалярной свертки критериев сводятся к построению той или иной математической модели функции полезности ЛПР. 68 ISSN 0572-2691 Предполагается, что существуют некоторые инварианты, правила, обычно являющиеся общими для всех ЛПР независимо от их индивидуальных склонно- стей, которых они одинаково придерживаются в той или иной ситуации. Соглас- но [2] субъективность ЛПР имеет свои границы. В деловых решениях человек обязан быть рациональным, чтобы иметь возможность аргументировать мотивы своего выбора, логику своей субъективной модели. Поэтому любые предпочтения ЛПР должны находиться в рамках определенной рациональной системы. Это и делает возможной формализацию. В данном случае предметом исследования является такая тонкая субстанция, как воображаемая функция полезности, возникающая в сознании ЛПР при реше- нии конкретной многокритериальной задачи. У каждого ЛПР своя функция по- лезности. Тем не менее можно получить сведения для задания вида содержатель- ной модели критериальной функции, если выявить и проанализировать некоторые общие закономерности, наблюдаемые в процессе принятия многокритериальных решений различными ЛПР в разных ситуациях. При этом напряженность ситуа- ции характеризуется близостью критериев к своим предельно допустимым значе- ниям. Такой анализ [2, 3] позволил сформулировать универсальную скалярную свертку частных критериев, которая выражает схему компромиссов, адаптирую- щуюся к ситуации принятия многокритериальных решений (нелинейная схема компромиссов). Тогда может быть предложена следующая процедура условной оптимизации, основанная на концепции нелинейной схемы компромиссов: .)]([)]([minarg 11 1 *            xfBBxAAx jjj m jXx Из этого выражения видно, что полученное решение является результатом ком- промисса между стремлением удовлетворить строгие ограничения ,0)(  xj ],1[ mj и тенденцией минимизировать целевую функцию ).(xf При этом ре- шение осуществляется по нелинейной схеме компромиссов, основанной на прин- ципе «подальше от предельно допустимых значений ,jA ],,1[ mj и В». Скалярная свертка уравнений связи и целевой функции по нелинейной схеме в данной формуле приведена в унифицированной форме [2]. При необходимости дополнительные индивидуальные предпочтения ЛПР могут быть учтены введени- ем весовых коэффициентов: ,)]([)1()]([minarg 11 1 *            xfBBxAAx jjjj m jXx ,0 j ,1 1   j m j где ,ja ],,1[ mj — весовые коэффициенты, отражающие относительную важ- ность выполнения соответствующих ограничений;  — весовой коэффициент, устанавливающий относительную важность для ЛПР противоречивых тенденций: выполнения ограничений и минимизации целевой функции. Пример. Задана целевая функция в виде эллиптического параболоида (рис. 2): 4 )5( 2 )6( )( 2 2 2 1     xx xf с минимумом в точке ).5;6(0 x В пространстве ),( 21 xx заданы уравнения связи (их пересечение дает начало координат) в виде ограничений 0)( 11  xx и ,0)( 22  xx которые желательно выполнять строго, но ЛПР допускает откло- нения в пределах 4111  Ax и .3222  Ax Международный научно-технический журнал «Проблемы управления и информатики», 2012, № 5 69 Максимальная величина минимизируемой целевой функции достигается при строгом выполнении ограничений (в нашем примере в начале координат )0, 21 xx и составляет .2525,24)(  Bxf ЛПР считает эту величи- ну предельно допустимой. Ставится задача: найти такие значения аргу- ментов оптимизации ,, 21  xx при которых требо- вания минимизации целевой функции и выполне- ния ограничений удовлетворяются компромиссно. Подставляем численные значения в выражение для компромиссной условной оптимизации в унифицированной форме (без весовых коэффициентов): . 4 )5( 2 )6( 25 25 3 3 4 4 minarg 2 2 2 121 *                         xxxx x Xx Решить эту задачу можно и аналитически, выполнив безусловную минимизацию скалярной свертки. Однако в практических случаях аналитический расчет может оказаться громоздким. Обычно пользуются численными методами экстремизации функций, но гораздо удобней применить компьютерную программу. Для решения широкого спектра оптимизационных задач разработана и изло- жена в работе [2] программа векторной оптимизации TURBO-OPTIM. Программа выполнена на языке Borland C++3.1 с использованием библиотеки Turbo Vision, что обеспечивает эффективное использование ресурсов ЭВМ, стандартизованную и удобную среду для пользователя, простоту модификации и отладки. Для работы с программой необходимо выполнить следующее: — выделить набор частных критериев так, чтобы все они принимали неотри- цательные значения и требовали минимизации; — определить допустимое предельное значение для каждого критерия; — выделить набор параметров (независимых переменных), от которых зави- сят частные критерии; — определить диапазон изменения каждого параметра (минимальное, стар- товое и максимальное значения); — задать ограничения для параметров, имеющие вид неравенств ,0)( rg j ],,1[ kj где k — количество ограничений; — определить вид зависимости частных критериев от параметров. Программа позволяет решать задачи оптимизации для следующих случаев связи частных критериев с аргументами оптимизации (параметрами):  критерии выражаются через параметры явно, известны аналитические зави- симости;  критерии являются некоторыми функционалами, и для расчета их значений требуется решение системы дифференциальных уравнений;  зависимости критериев от параметров неизвестны, и для определения зна- чений параметров необходимо проведение экспериментов;  значения критериев можно получить, выполнив написанную пользователем программу;  есть таблица зависимости частных критериев от параметров. В каждом из перечисленных случаев программа представляет пользователю средства нахождения минимума обобщенного критерия, построенного по нели- нейной схеме компромиссов, одним из методов оптимизации: 1) метод симплекс- планирования в модификации Нелдера–Мида и 2) нелокальный метод нелинейно- го программирования (дуальный метод оптимизации [2]). x 1x 2x 0x f (x) 2A 1A Рис. 2 70 ISSN 0572-2691 В соответствии с этапами работы с программой устанавливаем: режим «Ана- литика», метод оптимизации «Симплекс-планирование» (по умолчанию) и далее вводим числовые данные: ;0min1 x ;2start1 x ;41max1  Ax ;0min2 x ;2start2 x ;32max2  Ax ;41max1max1  Ay ;32max2max2  Ay .25maxmax3  Bfy После этого задаем команду «Выполнить», и программа определяет искомые зна- чения аргументов оптимизации: ,82,11 x 45,02 x и компромиссно-оптималь- ное значение целевой функции .89,13)( * xf Заключение Предложенный компромиссный метод позволяет обойтись без вспомогатель- ной категории неопределенных множителей Лагранжа, используемой как при ре- шении изопериметрических задач, так и в процедуре седловых точек Куна– Таккера. Обычно множители Лагранжа играют лишь вспомогательную, техниче- скую роль и представляют собой побочный результат решения задачи условной оптимизации. Иногда даже незначительный отход от строгого выполнения огра- ничений (или от седловой точки) позволяет существенно улучшить целевую функцию. Возможность назначения допустимых пределов для изменения ограни- чений и целевой функции по физическим соображениям дает ЛПР дополнитель- ные степени свободы при решении практических оптимизационных задач. А.М. Воронін КОМПРОМІСНИЙ МЕТОД РОЗВ’ЯЗАННЯ ЗАДАЧ УМОВНОЇ ОПТИМІЗАЦІЇ Розглянуто можливість компромісного розв’язку в задачах умовної оптимізації. Проблема полягає в тому, щоб отриманий розв’язок відображав компроміс між суперечливими вимогами екстремізації цільової функції і виконання обмежень. Для розв’язання розглянутої проблеми використовується підхід багатокритері- альної оптимізації з застосуванням нелінійної схеми компромісів. Наведено модельний приклад. A.N. Voronin A COMPROMISE METHOD OF CONSTRAINED OPTIMIZATION PROBLEMS SOLUTION The possibility of obtaining a compromise solution to the problems of constrained optimization is investigated. The problem is that the resulting decision should reflect a compromise between the conflicting requirements of objective function ex- tremalization and performance of limitations. For the decision of a considered prob- lem the approach of multicriteria optimization with use of the nonlinear trade-off scheme is undertaken. The illustrating example is given. 1. Воронин А.Н. Экспертные модели многокритериальной оптимизации // Information Tech- nologies & Knowledge. — 2011. — 5, N 3. — P. 217–223. 2. Воронин А.Н., Зиатдинов Ю.К., Козлов А.И. Векторная оптимизация динамических систем. — Киев : Техніка, 1999. — 284 с. 3. Воронин А.Н. Нелинейная схема компромиссов в многокритериальных задачах оценивания и оптимизации // Кибернетика и системный анализ. — 2009. — № 4. — С. 106–114. Получено 02.02.2012

Компромиссный метод решения задач условной оптимизации

Репозитарії

Схожі ресурси