Принятие решений в условиях многокритериальности с комбинаторными свойствами альтернатив
В статье рассматривается задача принятия решений при многих критериях на комбинаторных конфигурациях. Такие задачи являются моделями многих практических задач. Обосновываются свойства области допустимых решений задачи, базирующиеся на свойствах многогранника размещений, вершины которого определ...
Saved in:
| Published in: | Штучний інтелект |
|---|---|
| Date: | 2010 |
| Main Author: | |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут проблем штучного інтелекту МОН України та НАН України
2010
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/56124 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Принятие решений в условиях многокритериальности с комбинаторными свойствами альтернатив / Л.Н. Колечкина // Штучний інтелект. — 2010. — № 1. — С. 61-69. — Бібліогр.: 9 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-56124 |
|---|---|
| record_format |
dspace |
| spelling |
Колечкина, Л.Н. 2014-02-12T00:01:31Z 2014-02-12T00:01:31Z 2010 Принятие решений в условиях многокритериальности с комбинаторными свойствами альтернатив / Л.Н. Колечкина // Штучний інтелект. — 2010. — № 1. — С. 61-69. — Бібліогр.: 9 назв. — рос. 1561-5359 https://nasplib.isofts.kiev.ua/handle/123456789/56124 519.1 В статье рассматривается задача принятия решений при многих критериях на комбинаторных конфигурациях. Такие задачи являются моделями многих практических задач. Обосновываются свойства области допустимых решений задачи, базирующиеся на свойствах многогранника размещений, вершины которого определяют заданное комбинаторное множество точек. Представлено множество альтернатив в виде ориентированного графа многогранника размещений. Описываются свойства графа многогранника размещений, которые используются для разработки нового метода решений предлагаемой задачи на графе. У статті розглядується задача прийняття рішень при багатьох критеріях на комбінаторних конфігураціях. Такі задачі є моделями багатьох практичних задач. Обґрунтовуються властивості області допустимих рішень задачі, що базуються на властивостях многогранника розміщень, вершини якого визначають задану комбінаторну множину точок. Представлено множину альтернатив у вигляді орієнтованого графа многогранника розміщень. Описуються властивості графа многогранника розміщень, які використовуються для розробки нового методу розв’язання пропонованої задачі на графі. In article the decision-making task is considered at many criteria on combinatorial configurations which is models of many practical tasks. Properties of area of admissible solutions the tasks which are based on properties of a polyhedron of allocations which tops define the set combinatorial point set are proved. It is presented sets of alternatives in the form of a graph of a polyhedron of allocations. Properties of a polyhedron graph of allocations which are used for development of a new method of solutions of the offered task on the graph are described. ru Інститут проблем штучного інтелекту МОН України та НАН України Штучний інтелект Моделирование объектов и процессов Принятие решений в условиях многокритериальности с комбинаторными свойствами альтернатив Прийняття рішень в умовах багатокритеріальності з комбінаторними властивостями альтернатив Decision-Making in the Conditions of Multicriterion with Combinatorial Properties of Alternatives Article published earlier |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| title |
Принятие решений в условиях многокритериальности с комбинаторными свойствами альтернатив |
| spellingShingle |
Принятие решений в условиях многокритериальности с комбинаторными свойствами альтернатив Колечкина, Л.Н. Моделирование объектов и процессов |
| title_short |
Принятие решений в условиях многокритериальности с комбинаторными свойствами альтернатив |
| title_full |
Принятие решений в условиях многокритериальности с комбинаторными свойствами альтернатив |
| title_fullStr |
Принятие решений в условиях многокритериальности с комбинаторными свойствами альтернатив |
| title_full_unstemmed |
Принятие решений в условиях многокритериальности с комбинаторными свойствами альтернатив |
| title_sort |
принятие решений в условиях многокритериальности с комбинаторными свойствами альтернатив |
| author |
Колечкина, Л.Н. |
| author_facet |
Колечкина, Л.Н. |
| topic |
Моделирование объектов и процессов |
| topic_facet |
Моделирование объектов и процессов |
| publishDate |
2010 |
| language |
Russian |
| container_title |
Штучний інтелект |
| publisher |
Інститут проблем штучного інтелекту МОН України та НАН України |
| format |
Article |
| title_alt |
Прийняття рішень в умовах багатокритеріальності з комбінаторними властивостями альтернатив Decision-Making in the Conditions of Multicriterion with Combinatorial Properties of Alternatives |
| description |
В статье рассматривается задача принятия решений при многих критериях на комбинаторных конфигурациях. Такие задачи являются моделями многих практических задач. Обосновываются свойства области допустимых решений задачи, базирующиеся на свойствах многогранника размещений, вершины которого определяют заданное комбинаторное множество точек. Представлено множество альтернатив в виде ориентированного графа многогранника размещений. Описываются свойства графа многогранника размещений, которые используются для разработки нового метода решений предлагаемой задачи на графе.
У статті розглядується задача прийняття рішень при багатьох критеріях на комбінаторних конфігураціях. Такі задачі є моделями багатьох практичних задач. Обґрунтовуються властивості області допустимих рішень задачі, що базуються на властивостях многогранника розміщень, вершини якого визначають задану комбінаторну множину точок. Представлено множину альтернатив у вигляді орієнтованого графа многогранника розміщень. Описуються властивості графа многогранника розміщень, які використовуються для розробки нового методу розв’язання пропонованої задачі на графі.
In article the decision-making task is considered at many criteria on combinatorial configurations which is models of many practical tasks. Properties of area of admissible solutions the tasks which are based on properties of a polyhedron of allocations which tops define the set combinatorial point set are proved. It is presented sets of alternatives in the form of a graph of a polyhedron of allocations. Properties of a polyhedron graph of allocations which are used for development of a new method of solutions of the offered task on the graph are described.
|
| issn |
1561-5359 |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/56124 |
| citation_txt |
Принятие решений в условиях многокритериальности с комбинаторными свойствами альтернатив / Л.Н. Колечкина // Штучний інтелект. — 2010. — № 1. — С. 61-69. — Бібліогр.: 9 назв. — рос. |
| work_keys_str_mv |
AT kolečkinaln prinâtierešeniivusloviâhmnogokriterialʹnostiskombinatornymisvoistvamialʹternativ AT kolečkinaln priinâttâríšenʹvumovahbagatokriteríalʹnostízkombínatornimivlastivostâmialʹternativ AT kolečkinaln decisionmakingintheconditionsofmulticriterionwithcombinatorialpropertiesofalternatives |
| first_indexed |
2025-11-24T15:58:00Z |
| last_indexed |
2025-11-24T15:58:00Z |
| _version_ |
1850849734688768000 |
| fulltext |
«Штучний інтелект» 1’2010 61
2К
УДК 519.1
Л.Н. Колечкина
Институт кибернетики им. В.М. Глушкова НАН Украины, г. Киев
ludapl@ukr.net
Принятие решений в условиях
многокритериальности с комбинаторными
свойствами альтернатив
В статье рассматривается задача принятия решений при многих критериях на комбинаторных
конфигурациях. Такие задачи являются моделями многих практических задач. Обосновываются свойства
области допустимых решений задачи, базирующиеся на свойствах многогранника размещений,
вершины которого определяют заданное комбинаторное множество точек. Представлено множество
альтернатив в виде ориентированного графа многогранника размещений. Описываются свойства графа
многогранника размещений, которые используются для разработки нового метода решений предлагаемой
задачи на графе.
Введение
Основой успешного функционирования любого производства является приня-
тие решений, адекватных условиям, в которых функционируют объекты. В принятии
решений компьютер становится ближайшим помощником человека [1]. Но традицион-
ное использование ЭВМ не самое эффективное. Руководитель, кроме информации из
базы данных, кроме некоторых экономических или технологических расчетов, в
своей деятельности встречается с большим количеством задач по управлению системой,
которые решаются в рамках многокритериальной оптимизации при наличии мно-
жества альтернатив. Потребность нахождения множества альтернатив возникает вслед-
ствие того, что всякая реальная задача требует выбора и принятия решений с учетом
многих критериев качества [2-4]. Эти критерии, как правило, противоречивы и разно-
родны в том смысле, что качество сравниваемых альтернатив невозможно адекватно
выразить одним комплексным критерием, представляющим собой некоторую свертку
исходных частных критериев. Иными словами оказываются неприменимыми априор-
ные процедуры многокритериальной оптимизации. В этом случае для осуществления
выбора и принятия решений необходимо использовать адаптивные процедуры, приме-
нение которых предполагает нахождение того или другого множества альтернатив.
В свою очередь множество альтернатив часто имеет специфические, в частнос-
ти комбинаторные свойства, которые необходимо учесть для адекватного описания
математической модели и ее применения для решения прикладных задач. Поэтому
есть целесообразным рассмотреть подход к решению, который основан на особеннос-
тях класса векторных задач на комбинаторных конструкциях. Следует отметить, что
большой интерес ученых вызывают методы анализа некоторых комбинаторных задач,
базирующиеся на свойствах многогранников, вершины которых определяют заданное
комбинаторное множество точек. Комбинаторные многогранники связаны с теорией
графов [5], [6]. Графы многогранников обладают многими интересными свойствами;
при их изучении возникает большое число задач, представляющих интерес не только
для теории графов, комбинаторики, топологии и геометрии, но и для теории многокри-
териальной оптимизации.
Колечкина Л.Н.
«Искусственный интеллект» 1’2010 62
2К
Данная работа является продолжением работ [7-9]. В ней рассматривается ме-
тод решения дискретных многокритериальных задач с применением графов с учетом
комбинаторных свойств множества альтернатив.
1. Определение задачи векторной оптимизации на комбинаторном множест-
ве. Задача векторной оптимизации обычно определяется как вычислительная проб-
лема, в которой задано множество альтернатив { }xΧ = , векторная целевая функция
( ) :F x X R→ , где ( ) ( ) ( ) ( )( )1 ,..., ,...,i lF x f x f x f x= , состоящая из частных критериев
( ) max,i lf x i N→ ∈ , и требуется найти альтернативу 0x X∈ , на которой эта целевая
функция принимает экстремальное значение: ( ) ( )0
x X
F x extr F X
∈
= , { }min, maxextr∈ .
Для задач оптимизации альтернативы x X∈ обычно называют допустимыми реше-
ниями, 0x – оптимальное решение, { }X x= – множеством допустимых решений. Если
множество X дискретное, то соответствующая задача оптимизации называется зада-
чей дискретной оптимизации.
При 1N = , то есть в однокритериальном случае, X% – это множество всех опти-
мумов данной задачи.
В данной работе рассматривается случай, когда X – комбинаторное множество
размещений. ( ) ( ) ( ) ( )( )1 ,..., ,...,i lF x f x f x f x= − векторный критерий, задан на мно-
жестве ( )A B размещений, порождаемых некоторым конечным мультимножеством
{ }1 2, ,..., qB b b b= . Тогда задача имеет вид: ( ),Z F X .
Задача может содержать также дополнительные линейные ограничения, которые
образуют выпуклое многогранное множество nD R⊂ вида: { | }nD x R Gx H= ∈ ≤ ,
где ,m nG R ×∈ mH R∈ . Запишем линейные ограничения в виде линейных неравенств:
( ) , ,ij i m nG x h i N j N≥ ∈ ∈ . (1)
Для решения задачи ( ),Z F X рассмотрим разложение ее на подзадачи, преоб-
разовав каждое из неравенств системы дополнительных ограничений (1) в равенство
( )1
1
, ,
n
ij i i m n
i
G x g x h i N j N
=
= = ∈ ∈∑ , и будем рассматривать нахождение точки x =
= 1 2( , ,..., )nx x x по значению ih целевой функции на множестве размещений.
Как известно, размещением из q элементов по n называется упорядоченный на-
бор из n элементов, которые принадлежат мультимножеству { }1 2, ,..., qB b b b= .
Следует заметить, что в этом случае понятие «оптимум» имеет непротиворечивое
определение: допустимое решение 0x оптимальное, если оно минимизирует (или мак-
симизирует) целевую функцию на ( ) ( )0: , min ,
x X
X F x b F x b
∈
= или ( ) ( )0 0, ,F x b F x b= =
( )max ,
x X
F x b
∈
= , где X содержит элементы множества размещений ( )A B .
Принятие решений в условиях многокритериальности...
«Штучний інтелект» 1’2010 63
2К
Каждый элемент множества ( )A B есть упорядоченным набором q соответст-
вующих действительных чисел. Не теряя общности, упорядочим элементы мульти-
множества B по неубыванию таким образом: 1 2 qb b b≤ ≤ ≤K . Тогда выпуклой оболоч-
кой общего множества размещений ( )A B является общий многогранник размещений
conv ( )M A B= [5]:
{ }1
1 1
1,..., ,n
j i q j n
j i j
M x R b x b N n
ω ω
− +
= ∈ω =
= ∈ ≤ ≤ ∀ω⊂ =
∑ ∑ ∑ а ( ) vertA B M= .
Согласно [5] conv ( )x M A B∈ = является вершиной многогранника размещений
M тогда и только, когда он представляет собой перестановку чисел 1 1,..., , ,s q rb b b − +
, , qbK , где 0 s q≤ ≤ , 0 r n≤ ≤ , s r n+ = .
Как известно [9], для перестановочного многогранника можно построить граф,
с помощью которого можно рассматривать изменение значения целевой функции в
точках – вершинах многогранника размещений. Воспользуемся следующей теоремой.
Теорема 1. Многогранник размещений conv ( )M A B= = ( )n
qM B при n q< и лю-
бом векторе ( )1 2, , , qB b b b= K комбинаторно эквивалентен перестановочному много-
граннику ( )nM B размерности n [5].
Учитывая связь между перестановками и размещениями, для элементов множе-
ства размещений можно построить подобный граф многогранника размещений ( )n
qM B .
Далее ( )n
qM B = M .
2. Построение графа многогранника размещений и его свойства.
Пусть существует граф ( )G B некоторого многогранника размещений M .
Опишем построение графа ( )G B для размещения из 4 элементов по 3. Для удоб-
ства оперирования элементы множества размещения – точки пронумеруем от 1 до 24,
так как их будет как раз 24, и будем их называть вершинами 24, ∈ip i N графа ( )G B ,
которые будут размещаться на четырех подграфах ( )1G B , ( )2G B , ( )3G B , ( )4G B , в
зависимости от выбора элементов из множества В. Тогда для подграфов графа ( )G B вы-
полняются следующие условия: 1 2 3 4, , ,X X X X X X X X⊆ ⊆ ⊆ ⊆ , где 4, ,iX X i N∈ –
множество вершин; 1 2 3 4, , ,U U U U U U U U⊆ ⊆ ⊆ ⊆ , где 4, ,iU U i N∈ – множество
ребер. В подграфе ( )1G B , который расположен в верхней части графа ( )G B , вершины
образованы из максимальных элементов мультимножества { }1 2, ,..., qB b b b= = (2, 3, 4),
которые образовывают элементы множества размещений. Следующий подграф ( )2G B
строится путем замены минимального элемента на еще более минимальный, то есть
выбирается подмножество (1, 3, 4) и генерируются вершины. Аналогичным образом
строятся подграфы: ( )3G B , вершины которого образовываются путем генерации эле-
ментов (1, 2, 4), и ( )4G B – вершины образовываются из (1, 2, 3).
Колечкина Л.Н.
«Искусственный интеллект» 1’2010 64
2К
Далее рассмотрим любой частный критерий ( ) ( )if x f x= , li N∈ вектор-функции
( )F x . Вектор коэффициентов функции
1
( ) ,
n
j
j
f x c x
=
= ∑ обозначим ( )jc c=
r , nj N∈ ,
где 1 2 ... nc c c≤ ≤ ≤ , ni N∈ для функции. Тогда значение функции ( )f x в произвольной
точке (1 24)≤ ≤ip i определяется как скалярное произведение ( ) ( , )j j jf p p c= .
( )1G B
( )2G B
8
( )3G B
( )4G B
Рисунок 1 – Представления графа многогранника размещений Μ
22
3 4 1 1 4 3
3 1 4 4 1 3 4 3 1
2 3 4
3 2 4
2 4 3 3 4 2
4 2 3 4 3 2
1 3 4
1 3
2
5
4 6
7 9 11
10 12
2 3 1 1 3 2
2 1 3 3 1 2 3 2 1
1 2 4
2 1 4
1 4 2 2 4 1
4 1 2 4 2 1
1 2 3
13 15
14
17
16 18
19 21 23
20 24
8
Принятие решений в условиях многокритериальности...
«Штучний інтелект» 1’2010 65
2К
Далее рассмотрим построение вершин в подграфах. Следует заметить, что граф
( )G B можно построить индуктивным способом, начиная с двух первых элементов
размещения, аналогично графу многогранника перестановок [9]. Рассмотрим одно ин-
тересное свойство в виде леммы, которое будем использовать для построения графа.
Лемма 1. Из двух смежных вершин ,i jp p многогранника размещений M функ-
ция ( )f x принимает не меньшее (большее) значение для той вершины, в которой мак-
симальный из двух различающихся элементов находится справа, при условии, что
коэффициенты целевой функции
1
( ) ,
n
j
j
f x c x
=
= ∑ упорядочены следующим образом:
1 2 ... nc c c≤ ≤ ≤ , ni N∈ .
Рассмотрим вершины 1p и 2p , которые размещены на некотором подграфе 1( )G B
графа ( )G B . Пусть имеем вершину ( ) ( )1 12,3, 4p G B= ∈ , тогда вершина 2p образова-
на из 1p путем транспозиции элементов 1 и 2. Согласно лемме 1 получим соотношение
значений целевой функции в этих точках: 1 2( ) ( )f p f p≥ . Если теперь в вершинах 1p ,
2p поменять местами элементы 2 и 3, то получим вершины 3p и 5p , для которых
выполняется соотношение 3 5( ) ( )f p f p≥ . Кроме того, по лемме 1 получаем 1( )f p ≥
3( )f p≥ и 2 5( ) ( )f p f p≥ . Аналогично, путем транспозиции элементов 1 и 3 получим
из 2p вершину 4p , а из 4p транспозицией элементов 2, 3 – вершину 6p . В результате
этих действий получим полный подграф 1( )G B , который содержит все вершины мно-
гогранника размещений M , полученные из элементов ( )2,3, 4 . Очевидно, что в под-
графе 1( )G B функция ( )f x принимает максимальное значение в вершине 1p и ми-
нимальное – в вершине 6p (при упорядочении элементов множества размещений и
коэффициентов целевой функции по возрастанию).
Путь (маршрут) на каждом подграфе графа ( )G B определяется последователь-
ностью вершин и ребер для первого подграфа 1( )G B соответственно: 1 1 2 2 3 3 4 4p u p u p u p u
5 5 6 6p u p u , для второго 2 ( )G B – последовательностью 7 7 8 8 9 9 10 10 11 11 12 12p u p u p u p u p u p u ,
для третьего 3( )G B – последовательностью 13 13 14 14 15 15 16 16 17 17 18 18p u p u p u p u p u p u , для
четвертого 4 ( )G B – 19 19 20 20 21 21 22 22 23 23 24 24p u p u p u p u p u p u , где , ,i ip vert M u U i∈ ∈ ∈
∈ 24N . Ребро iu соединяет вершину ip с вершиной 1,ip + то есть выполняется отноше-
ние инцидентности ( )1, ,i i ip u p +Φ . В каждом подграфе 1( )G B , 2 ( )G B , 3( )G B , 4 ( )G B
определяется гамильтонов цикл, содержащий все вершины подграфа.
Для дальнейшего изложения материала рассмотрим некоторые интересные свой-
ства описанного графа ( )G B многогранника размещений согласно рис. 1.
Говоря о какой-либо задаче на графе ( )G B , ее допустимое решение обозначим
через x , подразумевая, что ( ),x xx X U= – это удовлетворяющий определенным усло-
виям подграф графа ( )G B с множеством вершин xX X⊆ , где X – множество вершин
графа ( )G B и множеством ребер UU x ⊆ – множеством всех допустимых решений этой
задачи. Для рассматриваемой задачи множество всех допустимых решений X vertM= .
Колечкина Л.Н.
«Искусственный интеллект» 1’2010 66
2К
Так как построение подобно графу перестановочного многогранника, который
описан в работе [9], исходя из теоремы 1, то целесообразно утверждать, что граф
( )G B состоит из подграфов, которые конечны и изоморфны между собой (рис. 1).
Граф ( )G B можно рассматривать как конечный граф, который есть объединени-
ем четырех подграфов ( ) ( )1 1 1,G B X U= , ( ) ( )2 2 2,G B X U= , ( ) ( )3 3 3,G B X U= , ( )4G B =
( )4 4,X U= , где 1 2 3 4, , ,X X X X vert M∈ и для ( ), ,=G X U 1 2vert M X X X X= = U U
3 4X XU U , 1 2 3 4.U U U U U= U U U
Определение 1. ( )1 1 1 1, ,= ΦG X U и ( )2 2 2 2, ,= ΦG X U называются изоморфны-
ми ( )1 2≅G G , если существуют два взаимно однозначных соответствия 1 2: X Xϕ →
и ( )1 2 ,U Uψ → сохраняющие отношение инцидентности: ( ) ( ) ( )( )2 1 1 1, ,x u yΦ ϕ ψ ϕ =
( )1 1 1 1, ,x u y= Φ [6].
Следует отметить, что ( ) ( )1 1 1,G B X U= , ( ) ( )2 2 2,G B X U= , ( ) ( )3 3 3,G B X U= ,
( ) ( )4 4 4,G B X U= графы попарно изоморфны, так как между их вершинами и ребра-
ми существует взаимно однозначное соответствие.
Из определения следует, что изоморфные графы можно одинаково изображать
графически и отличаться они будут только метками вершин, что и обозначено на
рис. 1.
Определение 2. Граф называется ориентированным (орграф), если каждое его
ребро ориентировано: ( ) ( ), , , ,x y X u U x u y y u x∀ ≠ ∈ ∀ ∈ Φ ⇒¬Φ [6].
Преобразуем неориентированный граф ( )G B в ориентированный – заменой каж-
дого неориентированного ребра парой ориентированных ребер.
Для этого рассмотрим шестерки точек – вершины подграфов графа ( )G B , ко-
торые можно представить на плоскости в виде плоского (планарного) графа так же,
как и для графа перестановочного многогранника [9]. Причем для каждой шестерки
вершин можно построить гамильтонов путь. Для произвольного n граф ( )G B рас-
кладывается на подграфы, где наименьший состоит из множества вершин и дуг,
соединяющий эти вершины, что снова приводит к рассмотрению подграфов вида
( ) ( )1 1 1,G B X U= , ( ) ( )2 2 2,G B X U= , ( ) ( )3 3 3,G B X U= , ( ) ( )4 4 4,G B X U= .
Учитывая свойства графа ( )G B , рассмотрим алгоритм решения задачи ( ),Z F X
на графе многогранника размещений. В алгоритме используется решение подзадачи,
которая состоит в нахождении множества точек – вершин графа по экстремальным
значениям целевых функций ( )1
1
, ,
m
ij i i m k
i
G x g x h i N j N
=
= = ∈ ∈∑ на основе метода де-
ления отрезка пополам (метода дихотомии), используя свойства графа ( )G B .
3. Алгоритм решения векторной задачи на размещениях.
Рассмотрим метод решения дискретных многокритериальных задач с примене-
нием графов.
Принятие решений в условиях многокритериальности...
«Штучний інтелект» 1’2010 67
2К
Пусть ( ) ( ),G B X U= есть граф, задано также множество подграфов { }1,..., .qG G
Допустимое решение x определяется как подграф ( ), , ,x x x xx X U X X U U= ⊆ ⊆ , в
котором каждая компонента связности изоморфна графу ( )G B , где X – множество
допустимых решений на графе. Учитывая многокритериальность заданной задачи,
заметим, что ее необходимо свести к однокритериальной задаче.
Для этого применим известный алгоритм линейной свертки. Эти алгоритмы ба-
зируются на следующем известном факте: при положительно-определенной вектор-
целевой функции элемент x X∈ , максимизирующий линейную свертку ( )F xλ , явля-
ется Парето-оптимальным. Далее общая идея предложенного метода решения задачи
( , )Z F X состоит в последовательном рассмотрении подзадач, каждая из которых со-
держит функции из вектор-функции и функции-ограничения.
Алгоритм
Начальный шаг. Полагаем 0s = . Сведем многокритериальную задачу ( , )Z F G
на графе ( )G B многогранника размещений к однокритериальной с помощью линейной
свертки: задаем весовые неотрицательные коэффициенты , ,j lj Nλ ∈ которые опреде-
ляют степень важности каждого критерия, и максимизируем линейную комбинацию
целевых функций, то есть решаем задачу
( , )sZ f G , где
1
( ) ,
l
i i
i
f x c x
=
= λ∑ ,
1
0, , 1
l
i l i
i
i N
=
λ ≥ ∈ λ =∑ , s nG R= .
В случае, если какой-либо из коэффициентов 1iλ = , а все другие 0jλ = , i j≠ ,
, li j N∈ , то рассматривается однокритериальная задача с i -й целевой функцией.
Задаем элементы множества B 1 2, ,..., qb b b , которые упорядочены 1 2 ... qb b b≤ ≤ ≤ ,
задаем коэффициенты целевой функции 1 2, ,..., nc c c .
Основная часть.
Шаг 1: Упорядочим коэффициенты iλ ⋅ ic , li N∈ , 1 1 2 2 ... ,n n nc c c i Nλ ≤ λ ≤ ≤ λ ∈ целе-
вой функции
1
( ) ,
l
i i
i
f x c x
=
= λ∑ .
Шаг 2: Определяем минимальные и максимальные значения целевой функции ( )f x =
1
,
l
i i
i
c x
=
= λ∑ , вычисляем значения *
min( )f x , *
max( )f x на общем графе многогран-
ника ( )G B и на каждом из подграфов 1( )G B , …, ( )nG B .
Шаг 3: 0.k = Выбираем одно из дополнительных ограничений
1
,
m
i ij i
i
h g x
=
=∑ ,mi N∈
nj N∈ присваиваем 1k k= + , если k m= , то есть все ограничения выбраны, то на
шаг 10. Иначе, задаем коэффициенты дополнительного ограничения k : , ,ij mg i N j∈
Колечкина Л.Н.
«Искусственный интеллект» 1’2010 68
2К
, 1, :kj N k k i k i∈ = + = − . Строим решетку для преобразования индексов коэффици-
ентов (упорядочиваем коэффициенты):
1 2 3 4 1 2 3 4
1 2 3 4 1 2 3 4
k kU U
′= ⇒ = ′ ′ ′ ′α α α α α α α α
.
Шаг 4: Преобразовываем дополнительное ограничение в ограничения вида: ( )ijg x =%
( )i ij iU g x h= ≥ , в котором коэффициенты упорядочены по возрастанию.
Шаг 5: Определяем * *
max min( ) max, ( ) mink kg x g x= =% % на графе ( )G B .
Шаг 6: Находим значения функции дополнительного ограничения ( )ijg x% в левых
крайних точках
leftip , которые определяют max значений функции ( )kg x% на каждом
подграфе 1( )G B , …, ( )nG B графа (рис. 1).
Шаг 7: Сравниваем выполнение ограничений ( )q qg x b≥% , если условие выполняется,
запоминаем
leftip и переходим на следующий шаг 8. Иначе на шаг 9.
Шаг 8: Находим значения функции – дополнительного ограничения в точках
riteip
(точки, которые определяют min значение ( )kg x% на каждом подграфе). Делим отре-
зок, который определяется точками ( )
rite lefti q ip g x p≤ ≤ на шаге 6, 7, пополам и по-
лучаем точку ( )* 2
left ritei ix p p= − . Переходим на следующий шаг.
Шаг 9: Проверяем выполнения преобразованного дополнительного ограничения ( )kg x ≥
kb≥ , подставив значения точки из множества размещений ( )A B . Если неравенство
выполняется, то запоминаем нужный отрезок * *
min[ , ]x p или * *
max[ , ]p x . Проверя-
ем выполнения условия k m= , если не выполняется, то переходим на шаг 3. Иначе
на следующий шаг.
Шаг 10: Для всех дополнительных ограничений ищем подграф, который определяется
множеством вершин и вычисляем на нем min или max значений целевой функ-
ции ( )f x . Задача решена, если значение целевой функции находится в точках на пере-
сечениях и определяют объединение вершин подграфов 1( )G B , …, ( )nG B . Иначе –
задача неразрешима.
Таким образом, результатом работы алгоритма является подграф ( )0 , ,x X U= Φ
исходного графа ( ) ( ), ,G B X U= Φ . 0x – Парето-оптимальное решение задачи ( ),Z F X .
Поскольку решение задачи ищется на конечном дискретном множестве размещений,
то можно гарантировать нахождение хотя бы одного Парето-оптимального решения
x% задачи ( ),Z F X с вектор-целевой функцией, а соответственно применение ал-
горитма к данному графу ( )G B , у которого сложность нахождения x% составляет
( )2O mn .
Вычислительная сложность всякого алгоритма α измеряется количеством эле-
ментарных операций (арифметических, сравнения и т.п.) и обозначается через ( )α τ .
Принятие решений в условиях многокритериальности...
«Штучний інтелект» 1’2010 69
2К
Выводы
Исследованы сложные задачи на комбинаторном множестве размещений со мно-
гими критериями. Рассмотрены некоторые свойства допустимой области комбинатор-
ной задачи, которая имеет специфические входные данные. Построен и обоснован
метод локализации линейной функции на комбинаторных конфигурациях.
Модель многокритериальной задачи с учетом комбинаторных свойств области
допустимых решений может быть применена для принятия решений в практических
задачах экономики, техники, народного хозяйства.
Дальнейшее развитие данной работы будет направлено на реализацию и адап-
тацию сформулированного метода, а также на разработку новых методов решения
комбинаторных оптимизационных задач с учетом входных данных и других комби-
наторных множеств.
Литература
1. Шевченко А.И. Задачи и вопросы экспериментального поиска алгоритмов интеллектуального твор-
ческого процесса человека как прототипа машинного интеллекта / А.И. Шевченко, И.С. Сальников,
Р.И. Сальников // Искусственный интеллект. – 2008. – № 3. – С. 6-17.
2. Подиновский В.В. Парето-оптимальные решения многокритериальных задач / В.В. Подиновский,
В.Д. Ногин. – М. : Наука, 1982. – 256 с.
3. Штойер Р. Многокритериальная оптимизация / Штойер Р. – М. : Радио и связь, 1992. – 504 с.
4. Семенова Н.В. Подход к решению векторных задач дискретной оптимизации на комбинаторном
множестве перестановок / Н.В. Семенова, Л.Н. Колечкина, А.Н. Нагорная // Кибернетика и
системный анализ. – 2008. – № 3. – С. 158-172.
5. Емеличев В.А. Многогранники, графы, оптимизация / Емеличев В.А., Ковалев М.М., Кравцов М.К. –
М. : Наука, 1981. – 344 c.
6. Уилсон Р. Дж. Введение в теорию графов / Уилсон Р.Дж. – М. : Мир, 1977.
7. Емеличев В.А. О некоторых алгоритмических проблемах многокритериальной оптимизации на гра-
фах / В.А. Емеличев, В.А. Перепелица // Журн. выч. математики и мат. физики. – 1989. – Т. 29, № 2. –
С. 171-183.
8. Донец Г.А. О сложности алгоритмов поиска в глубину на модульных графах / Г.А. Донец, И.Э. Шу-
линок // Теорія оптимальних рішень. – 2002. – № 1. – С. 105-110.
9. Донец Г.А. Метод упорядочения значений линейной функции на множестве перестановок / Г.А. До-
нец, Л.Н. Колечкина // Кибернетика и системный анализ. – 2009. – № 2. – С. 50-61.
Л.М. Колєчкіна
Прийняття рішень в умовах багатокритеріальності
з комбінаторними властивостями альтернатив
У статті розглядується задача прийняття рішень при багатьох критеріях на комбінаторних конфігураціях.
Такі задачі є моделями багатьох практичних задач. Обґрунтовуються властивості області допустимих
рішень задачі, що базуються на властивостях многогранника розміщень, вершини якого визначають
задану комбінаторну множину точок. Представлено множину альтернатив у вигляді орієнтованого
графа многогранника розміщень. Описуються властивості графа многогранника розміщень, які використовуються
для розробки нового методу розв’язання пропонованої задачі на графі.
L.N. Kolechkina
Decision-Making in the Conditions of Multicriterion with Combinatorial Properties of Alternatives
In article the decision-making task is considered at many criteria on combinatorial configurations which is
models of many practical tasks. Properties of area of admissible solutions the tasks which are based on
properties of a polyhedron of allocations which tops define the set combinatorial point set are proved. It is
presented sets of alternatives in the form of a graph of a polyhedron of allocations. Properties of a polyhedron
graph of allocations which are used for development of a new method of solutions of the offered task on the
graph are described.
Статья поступила в редакцию 22.12.2009.
|