Гарантований синтез скалярного критерію для розв’язку задачі багатокритеріальної оптимізації

A generalized criterion for the multicriteria optimization problem has been constructed with interval estimations of weighting coefficients. The most unfavorable point estimation for choice of guaranteed solution has been found. The geometric structure of indifference surface in the criteria space i...

Full description

Saved in:
Bibliographic Details
Date:2019
Main Authors: Smirnov, S. A., Gontarenko, I. S.
Format: Article
Language:Russian
Published: The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute" 2019
Online Access:https://journal.iasa.kpi.ua/article/view/165229
Tags: Add Tag
No Tags, Be the first to tag this record!
Journal Title:System research and information technologies
Download file: Pdf

Institution

System research and information technologies
_version_ 1866302331240316928
author Smirnov, S. A.
Gontarenko, I. S.
author_facet Smirnov, S. A.
Gontarenko, I. S.
author_sort Smirnov, S. A.
baseUrl_str http://journal.iasa.kpi.ua/oai
collection OJS
datestamp_date 2019-04-24T15:47:42Z
description A generalized criterion for the multicriteria optimization problem has been constructed with interval estimations of weighting coefficients. The most unfavorable point estimation for choice of guaranteed solution has been found. The geometric structure of indifference surface in the criteria space is described.
first_indexed 2025-07-17T10:24:45Z
format Article
fulltext © С.А. Смирнов, И.С. Гонтаренко, 2006 Системні дослідження та інформаційні технології, 2006, № 2 99 УДК 519.6:658.5 ГАРАНТИРОВАННЫЙ СИНТЕЗ СКАЛЯРНОГО КРИТЕРИЯ ДЛЯ РЕШЕНИЯ ЗАДАЧИ МНОГОКРИТЕРИАЛЬНОЙ ОПТИМИЗАЦИИ С.А. СМИРНОВ, И.С. ГОНТАРЕНКО Построен обобщенный критерий для задачи многокритериальной оптимизации при интервальном оценивании весовых коэффициентов частных критериев. Найдена наиболее неблагоприятная точечная оценка, необходимая для выбора гарантированного решения. Описана геометрическая структура поверхности безразличия в критериальном пространстве. Основным способом решения задач многокритериальной оптимизации яв- ляется метод агрегирования [1]. Это справедливо и для паретовского анали- за: каждый критерий естественным образом определяет бинарное отноше- ние предпочтения, а затем как результат агрегирования построенных бинарных отношений определяется понятие доминирования по Парето. Среди других важных приложений метода агрегирования предпочтений от- метим задачи коллективного выбора [2]. В простейшем (и наиболее распространенном) варианте агрегирования критериев при векторной оптимизации — методе линейной свертки — ис- пользуются весовые коэффициенты, происхождение которых не вполне формализуемо [3]. Их значения получаются в результате специальных экс- пертных процедур, либо процедур типа «data mining» с участием ЛПР. С этим связаны как достоинства, так и недостатки метода. Конечно, подоб- ные процедуры содержат элемент произвола, но они результативны и не- редко помогают найти вполне удовлетворительные решения многокритери- альных задач, недоопределенных с математической точки зрения. Рассмотрим два обстоятельства, ограничивающих возможности кор- ректного использования метода линейной свертки. А именно, мы не имеем права утверждать априори, что глобальная функция полезности (представ- ляемая агрегированным критерием) задает именно линейную зависимость от исходных критериев. Однако результаты теории полезности [4] позволя- ют построить из исходного множества критериев «локальные функции по- лезности» и обосновать линейную зависимость от них глобальной функции полезности. Таким образом, несмотря на определенные ограничения, метод линейной свертки является достаточно универсальным, результативным и, как следствие, широко распространенным. Второе ограничение правомерности использования этого метода связа- но с отмеченным выше эвристическим характером процедур оценивания весовых коэффициентов. Назначение этих процедур — как можно более точно численно выразить неформальные, качественные представления экс- пертов (либо ЛПР). Понятно, что такие процедуры принципиально не могут быть полностью алгоритмизированы и всегда будут иметь человеко- С.А. Смирнов, И.С. Гонтаренко ISSN 1681–6048 System Research & Information Technologies, 2006, № 2 100 машинный характер. Нередко они имеют форму диалога, итеративного про- цесса между аналитиком и ЛПР [5], структурно напоминающего беседу терапевта с пациентом. Методика организации и проведения такого рода процедур специально разрабатывалась и считается вполне надежной. Про- ведено множество психологических экспериментов, в которых сравнивались различные методы (не только чисто эвристические, но и с аксиоматическим обоснованием) назначения весов критериев. К сожалению, они показывают различные результаты [6], что непосредственно сказывается на качестве ре- шения и доверии к нему. Использование в известных процедурах точечных оценок, на наш взгляд, и приводит к указанной несогласованности. Кроме того, оно не всегда в полной мере отвечает как субъективным возможностям ЛПР, так и объективным особенностям предметной области. В данной работе развивается интервальный подход, использование ко- торого позволяет уменьшить жесткость (повысить адаптивность) процедуры оценивания весовых коэффициентов. Интервальные оценки представляются более адекватными сути дела, поскольку резкое уменьшение степени неоп- ределенности при решении подобных задач трудно удовлетворительно мо- тивировать, а последствия его могут быть весьма значительными. В то же время для эксперта (ЛПР) интервальное оценивание психологически более приемлемо — снижается риск возникновения почти неизбежных ошибок при субъективном точечном оценивании. Однако при этом вместо одного агрегированного критерия возникает класс критериев, и решение задачи выбора наилучшей альтернативы состо- ит из двух этапов. На первом — решается задача выбора значений весовых коэффициентов из интервала, указанного экспертом, т.е. выбора одного из множества обобщенных критериев. На втором — происходит собственно принятие решения путем максимизации полученного критерия. Выбор од- ного из множества критериев предполагает учет дополнительных соображе- ний, позволяющих зафиксировать значения весов. Различия в способах ре- шения этой задачи связаны, как правило, со спецификой требований, предъявляемых к результату. Так использование рассматриваемого в данной работе гарантированного подхода оправдано в случае, когда допускается (или неустранима) неточность оценок, даваемых экспертом, и при этом тре- буется минимизировать риск ошибки в принятии решения. Заметим, что в случае доверия к интервальному оцениванию и принятия рискованной стра- тегии «азартного игрока» имеет смысл вместо минимаксного подхода ис- пользовать макси-максный, т.е. на каждом из двух этапов решать задачу максимизации критерия. ПОСТАНОВКА ЗАДАЧИ Рассматривается критериальное пространство размерности n, в котором веса каждого из критериев )(,),(),( 21 ωωω nfff … , где Ω∈ω — альтернативы, представлены интервальными оценками nxxx ,,, 21 … . Требуется построить обобщенный критерий, минимизирующий риск ошибки, связанный с неточ- ностью оценивания экспертом или ЛПР весовых коэффициентов критериев. Этап 1. Выбор весовых коэффициентов обобщенного критерия. Гарантированный синтез скалярного критерия для решения задачи … Системні дослідження та інформаційні технології, 2006, № 2 101 Построим разбиение критериального пространства на n! конусов, каж- дый из которых задается упорядочением вида )()()( 21 ωωω jnjj fff <<< … . Для каждой из внутренних точек произвольного конуса будет, очевидно, выполняться neee <<…21, , где )(ω ij fe j = . Рассмотрим для заданного упорядочения решение задачи ∑ = → n i ii xe 1 min , где 10 ≤≤ ie , (1) 10 ≤≤≤≤ iii xxx . (2) Требуется отыскать такое решение ∗x задачи (1), (2) , для которого ∑ = ∗ = n i ix 1 1. (3) Последнее условие означает, что решением могут быть точки сечения прямоугольного гипер- параллелепипеда, задаваемого ограничениями (2), гиперпло- скостью (3). В силу выпуклости области, задаваемой ограниче- ниями, ее сечение гиперплоско- стью — выпуклый многогранник (рис. 1). Каждая вершина много- гранного сечения задается как точка пересечения гиперплоско- сти с ребром параллелепипеда (вершиной сечения не может быть внутренняя точка грани). Предложенная характеризация вершин инвариантна, т.е. не зави- сит от размерности критериаль- ного пространства. Требуется отыскать такую вершину сечения, в которой линейная функ- ция ∑ = n i ii xe 1 принимает минимальное значение (вообще говоря, решение не единственно). Вершины сечения, как было отмечено выше, либо лежат на ребрах параллелепипеда, либо совпадают с его вершинами. В первом случае координаты вершины — набор из 1−n следующих в некотором порядке верхних и нижних значений и одной компоненты xk вида kkk xxx ≤≤ ~ : nkkkk xxxxxxx ...,,,~,,...,, 11221 +−− , а во втором — подобная компонента отсутствует: nkk xxxxx ...,,,...,, 121 + . Таким образом, задача сводится к следующему: x1 x3 x2 Рис. 1. Общий вид сечения, задаваемого ограничениями (2), (3) при 3=n С.А. Смирнов, И.С. Гонтаренко ISSN 1681–6048 System Research & Information Technologies, 2006, № 2 102 а) отысканию единственной свободной компоненты (если решением является точка на ребре); б) установлению порядка следования верхних и нижних ограничений для остальных компонент. В том случае, когда искомым решением оказывается вершина паралле- лепипеда, достаточно выполнить подзадачу б). Для некоторого упорядочения коэффициентов neee <<< …21 вы- полняется Утверждение. Линейная комбинация ∑ = n i ii xe 1 , где neee <<< …21,0 , 10 ≤≤≤≤ iii xxx , принимает максимальное значение ∗x : ∑ = = n i ix 1 * 1 в точке сечения с коорди- натами ( )nkkk xxxxxx ...,,,~,...,,, 1121 +− и минимальное значение в точке вида ( )nkkk xxxxxx ...,,,~,...,,, 1121 +− . Доказательство. Предположим (для задачи нахождения минимального значения), что существует точка сечения с меньшим, чем у ∗x значением критерия. Рассмотрим сначала пары вершин сечения ∗∗∗ → xx , все координаты которых, кроме двух, одинаковы (рис. 2). Для рис. 2, а ( ) ( ) ( )=+−+=−∆ ++++ 1111 ****** ˆ~)()( kkkkkkkk xexexexexxfxxf ( ) ( )111 ˆ~ +++ −+−= kkkkkk xxexxe . ∗ + ),~( 1kk xx ),( 1+kk xx ∗∗ + )ˆ,( 1kk xx ∗∗ − ),ˆ( 1 kk xx ( )*1 ~, kk xx − ),( 1 kk xx − ),( 1+kk xx),( 1+kk xx ( )kk xx ,~ 1− ( )kk xx ,ˆ 1− a б в Рис. 2. Возможные переходы ∗∗∗ → xx Гарантированный синтез скалярного критерия для решения задачи … Системні дослідження та інформаційні технології, 2006, № 2 103 Для сохранения равенства ∑ ∑ = = == n i n i ii xx 1 1 *** 1 необходимо, чтобы вы- полнялось ( )11 ˆ~ ++ −−=− kkkk xxxx . Тогда ( ) ( )( ) 0ˆ)()( 111 ****** >−−=−∆ +++ kkkk eexxxxfxxf . Следовательно, при переходе *** xx → значение критерия возрастает. Для рис. 2, б ( ) ( ) ( )=+−+=−∆ −−−− kkkkkkkk xexexexexx 1111 *** ˆ~ ( ) ( )kkkkkk xxexxe −+−= −−− ~ˆ 111 , ∑ ∑ == = = n i n i ii xx 1 1 *** 1, поэтому kkkk xxxx −=− −− ~ˆ 11 . ( ) ( )( ) 0ˆ)()( 111 ****** >+−=−∆ −−− kkkk eexxxxfxxf . Следовательно, при переходе ∗∗∗ → xx значение критерия возрастает. Для рис. 2, в ( ) ( ) ( ) ( ) ( )kkkkkkkkkkkkkk xxexxexexexexe −+−=+−+=↓∆ −−−−−−− 1111111 ˆ~ˆ~ , kkkk xxxx −=− −− 11 ˆ~ . Следовательно, при переходе ∗∗∗ → xx значение критерия возрастает. Итак, при переходе из точки предполагаемого минимума x* в любую из соседних таких, что удовлетворяли бы ограничениям (2), (3), значение целе- вой функции (1) возрастает. Следовательно, ни одна из точек локальной ок- рестности x* не улучшает решения, ∑ = n i ii xe 1 * . Необходимо также учитывать, что в силу ограничений iii xxx ≤≤ рас- сматриваемые равенства разностей kkkk xxxx ~ˆ 11 −=− −− , =− −− 11 ˆkk xx kk xx −= ~ , kkkk xxxx −=− −− 11 ˆ~ могут и не выполняться. Это означает, что в сечении отсутствует соответствующая вершина. Хотя точка с рассматрива- емыми координатами и принадлежит параллелепипеду, сумма ее координат из-за накладываемых ограничений не равна нулю. Таким образом, точка ∗x является точкой локального минимума. На основании выпуклости многогранника (2), (3) и линейности целевой функции (1) можно также утверждать, что ∗x является и точкой глобально- го минимума. Отметим, что при рассмотрении строгого упорядочения <)(1 ωjf )()(2 ωω jnj ff <<< … для разбиения критериального пространства на кону- сы было найдено решение для произвольных внутренних точек каждого из них. В случае равенства )()( 21 ωω jj ff = получаем границы конусов, и зна- чения критерия определяем по непрерывности. При этом, поскольку внутри С.А. Смирнов, И.С. Гонтаренко ISSN 1681–6048 System Research & Information Technologies, 2006, № 2 104 каждого конуса веса определяются однозначно, обобщенный критерий в целом имеет кусочно-линейный характер, а соответствующая поверхность безразличия многокритериальной задачи является многогранной поверхнос- тью. Однако для продолжения решения по непрерывности в точках границы рассматриваются внутренние точки двух конусов, в которых найденные ре- шения различны. Убедимся в корректности определения обобщенного кри- терия в смысле его однозначности. Рассмотрим границу двух конусов 1+= kk ee , а также две возможные формы записи коэффициентов. 1. Внутренним точкам одного из двух граничащих конусов соответст- вует порядок коэффициентов ( )nkkiii xxxxxxx ,...,,,...,,~,,..., 1111 ++− , а точ- кам другого — ( )nkkiii xxxxxxx ,...,,,...,,~,,..., 1111 ++− , т.е. индекс i весового коэффициента ix~ не совпадает ни с k ни с 1+k . В этом случае значения обеих линейных сверток в точках границы совпадают, поскольку коэффици- енты отличаются лишь одной транспозицией, а соответствующие ей компо- ненты вектора критериальных оценок равны ( 1+= kk ee ). Проведенное для ki < рассуждение очевидным образом переносится на случай ki > . 2. Индекс i весового коэффициента ix~ совпадает с k или с 1+k . Рас- смотрим для определенности kx~ . При переходе из первого конуса с упоря- дочением ( )nkkk xxxxx ,...,,~,,..., 111 +− во второй, граничный с ним, единст- венно возможным будет упорядочение ( )nkkkk xxxxxx ,...,,~,,,..., 2111 ++− . Переходы вида ( )nkkiii xxxxxxx ,...,,,,...,~,,..., 1111 ++− или ( ...,,,..., 11 +kk xxx )niii xxxx ,,...,~,,... 11 +− нереализуемы. Таким образом, при переходе границы конусов сумма пары указанных весовых коэффициентов остается неизмен- ной. Значит, предельные значения при переходе в точки границы из внут- ренних точек каждого из конусов совпадают. Случай границ, разделяющих более чем два конуса, очевидно, сводится к рассмотренному. Таким образом, при переходе от одного конуса к другому, что отвечает соответствующему изменению упорядочения компонент векторной оценки (например, от 321 eee << к 123 eee << , как показано на рис. 3), естествен- ным образом обеспечивается непрерывность обобщенного критерия. Процедура построения решения. 1. Начинаем с вершины nxxxx ...,,, 21 0 = . Для нее проверяем 1...21 =+++ nxxx . Если условие выполнено, то 0x и есть решение. Если равенство не выполнено, составляем сумму nxxS ++= ...2 1 , для которой проверяем 1 1 1 1 xSx ≤−≤ . В случае выполнения неравенства существует 1 1 1~ Sx −= такое, что 1...~ 21 =+++ nxxx , и полученная точка …,,~ 21 1 xxx = nx,… является решением. В противном случае переходим в точку nxxxxx ...,,,~, 321 2 = , для которой повторяем процедуру. . . . Гарантированный синтез скалярного критерия для решения задачи … Системні дослідження та інформаційні технології, 2006, № 2 105 i. Для вершины niii i xxxxxxx ...,,,~,,...,, 1121 +−= строим сумму nii i xxxxxS ++++++= +− ...... 1121 . Если i ii i i SxxSx −=∃⇒≤−≤ 1~,1 : +++++++ +− ...~... 1121 iii xxxxx 1=+ nx , то вершина ix является решением. Иначе выполняем шаг 1+i . Этап 2. Решение задачи оптимизации построенного критерия. Построенный на первом этапе критерий представляет собой непрерыв- ную, определенную в любой точке критериального пространства функцию вида nnkkkkkk exexexexexexL +++++++= ++−− ...~...)( 11112211e , где номер и значение компоненты kx~ определяются для внутренних то- чек каждого из конусов, задаваемых упорядочением …<< )()( 21 ωω jj ff )(ωjnf<… , согласно описанной процедуре. Таким образом, задача приня- тия решений на множестве альтернатив с векторными оценками и заданны- Рис. 3. Структура решения задачи для упорядочения 321 eee << , которому соот- ветствует конус 321 xxx >> x2 x1 x3 ( 321 ,~, xxx ) ( 321 ~,, xxx ) ( 321 ~,, xxx ) С.А. Смирнов, И.С. Гонтаренко ISSN 1681–6048 System Research & Information Technologies, 2006, № 2 106 ми интервально весовыми коэффициентами критериев сводится к отыска- нию максимума линейной свертки ))((max: ** e e LLL = в критериальном пространстве. ЗАКЛЮЧЕНИЕ Описанная процедура построения весовых коэффициентов, очевидно, не является оптимальной с точки зрения вычислительной сложности. Для на- хождения решения требуется совершить последовательный просмотр в среднем 2/n компонент вектора оценок. Улучшить этот показатель до ло- гарифмического можно путем организации прохода по методу двоичного поиска. При этом количество шагов улучшенной процедуры составляет в среднем ( ))(logO n . Следует отметить, что предлагаемый метод решения рассматриваемой задачи не является единственным, поскольку кроме наиболее популярного симплекс-метода существуют достаточно эффективные градиентные проце- дуры. Однако все известные для класса задач линейного программирования с ограничениями вида (2), (3) методы решения — численные и, как следст- вие, не дают никакой информации об общей структуре решения. В отличие от них предлагаемый метод учитывает специфику рассматриваемой поста- новки, заключающуюся в том, что задача (1) – (3) является вспомогатель- ной, и ее решение для дальнейшего использования должно быть получено в аналитической форме, поскольку далее необходимо решать задачу оптими- зации построенного обобщенного критерия. Отметим также, что использование интервальных оценок и гарантиро- ванного подхода позволяет надеяться на минимизацию влияния ошибок оценивания субъективного характера и на существенное улучшение надеж- ности результатов принятия решения. ЛИТЕРАТУРА 1. Перегудов Ф.И., Тарасенко Ф.П. Введение в системный анализ.: Учеб. пособие для вузов. — М.: Высш. шк. — 1989. — 367 с. 2. Мулен Э. Кооперативное принятие решений: Аксиомы и модели. — М.: Мир. — 1991. — 464 с. 3. Подиновский В.В. Количественная важность критериев // Автоматика и телемеханика. — 2000. — № 5. — С. 110–123. 4. Фишберн П.С. Теория полезности для принятия решений. — М.: Наука, 1978. — 358 с. 5. Кини Р.Л. Размещение энергетических объектов: выбор решений. — М.: Энергоиздат, 1983. — 504 с. 6. Ларичев О.И. Теория и методы принятия решений, а также Хроника событий в Волшебных Странах: Учебник. — М.: Логос, 2000. — 296 с. 7. Мушик Э., Мюллер П. Методы принятия технических решений. — М.: Мир. — 1990. — 208 с. 8. Самойленко Ю.И., Хорозов О.А., Cмирнов С.А. Алгебраические методы оп- тимизации терминальных функционалов квантово-механических систем / Ин-т кибернетики им. В.М. Глушкова АН Украины. — Препр. — Киев, 1988. — 16 с. Постутила 15.04.2005
id journaliasakpiua-article-165229
institution System research and information technologies
keywords_txt_mv keywords
language Russian
last_indexed 2025-07-17T10:24:45Z
publishDate 2019
publisher The National Technical University of Ukraine &quot;Igor Sikorsky Kyiv Polytechnic Institute&quot;
record_format ojs
resource_txt_mv journaliasakpiua/b1/686f2d55b8805b474f4f2ba7cb6589b1.pdf
spelling journaliasakpiua-article-1652292019-04-24T15:47:42Z Guaranteed synthesis of scalar criterion for multicriteria optimization problem Гарантированный синтез скалярного критерия для решения задачи многокритериальной оптимизации Гарантований синтез скалярного критерію для розв’язку задачі багатокритеріальної оптимізації Smirnov, S. A. Gontarenko, I. S. A generalized criterion for the multicriteria optimization problem has been constructed with interval estimations of weighting coefficients. The most unfavorable point estimation for choice of guaranteed solution has been found. The geometric structure of indifference surface in the criteria space is described. Построен обобщенный критерий для задачи многокритериальной оптимизации при интервальном оценивании весовых коэффициентов частных критериев. Найдена наиболее неблагоприятная точечная оценка, необходимая для выбора гарантированного решения. Описана геометрическая структура поверхности безразличия в критериальном пространстве. Побудовано узагальнений критерій для задачі багатокритеріальної оптимізації при інтервальному оцінюванні вагових коефіцієнтів. Знайдено найбільш несприятливу точкову оцінку, необхідну для вибору гарантованого рішення. Описано геометричну структуру поверхні байдужості у критеріальному просторі. The National Technical University of Ukraine &quot;Igor Sikorsky Kyiv Polytechnic Institute&quot; 2019-04-24 Article Article application/pdf https://journal.iasa.kpi.ua/article/view/165229 System research and information technologies; No. 2 (2006); 99-106 Системные исследования и информационные технологии; № 2 (2006); 99-106 Системні дослідження та інформаційні технології; № 2 (2006); 99-106 2308-8893 1681-6048 ru https://journal.iasa.kpi.ua/article/view/165229/164355 Copyright (c) 2021 System research and information technologies
spellingShingle Smirnov, S. A.
Gontarenko, I. S.
Гарантований синтез скалярного критерію для розв’язку задачі багатокритеріальної оптимізації
title Гарантований синтез скалярного критерію для розв’язку задачі багатокритеріальної оптимізації
title_alt Guaranteed synthesis of scalar criterion for multicriteria optimization problem
Гарантированный синтез скалярного критерия для решения задачи многокритериальной оптимизации
title_full Гарантований синтез скалярного критерію для розв’язку задачі багатокритеріальної оптимізації
title_fullStr Гарантований синтез скалярного критерію для розв’язку задачі багатокритеріальної оптимізації
title_full_unstemmed Гарантований синтез скалярного критерію для розв’язку задачі багатокритеріальної оптимізації
title_short Гарантований синтез скалярного критерію для розв’язку задачі багатокритеріальної оптимізації
title_sort гарантований синтез скалярного критерію для розв’язку задачі багатокритеріальної оптимізації
url https://journal.iasa.kpi.ua/article/view/165229
work_keys_str_mv AT smirnovsa guaranteedsynthesisofscalarcriterionformulticriteriaoptimizationproblem
AT gontarenkois guaranteedsynthesisofscalarcriterionformulticriteriaoptimizationproblem
AT smirnovsa garantirovannyjsintezskalârnogokriteriâdlârešeniâzadačimnogokriterialʹnojoptimizacii
AT gontarenkois garantirovannyjsintezskalârnogokriteriâdlârešeniâzadačimnogokriterialʹnojoptimizacii
AT smirnovsa garantovanijsintezskalârnogokriteríûdlârozvâzkuzadačíbagatokriteríalʹnoíoptimízacíí
AT gontarenkois garantovanijsintezskalârnogokriteríûdlârozvâzkuzadačíbagatokriteríalʹnoíoptimízacíí