Оптимальные решения многокритериальных комбинаторных задач на размещениях
The problem of multicriterion combinatorial optimization on placing is examined. It is grounded, that the effective decisions of task are in the tops of polyhedron of placing. The algorithm of finding of Pareto-optimum estimations is represented for combinatorial multicriterion problems.
Saved in:
| Published in: | Теорія оптимальних рішень |
|---|---|
| Date: | 2007 |
| Main Author: | |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2007
|
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/84995 |
| 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: | Оптимальные решения многокритериальных комбинаторных задач на размещениях / Л.Н. Колечкина // Теорія оптимальних рішень: Зб. наук. пр. — 2007. — № 6. — С. 67-73. — Бібліогр.: 7 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1860063020313477120 |
|---|---|
| author | Колечкина, Л.Н. |
| author_facet | Колечкина, Л.Н. |
| citation_txt | Оптимальные решения многокритериальных комбинаторных задач на размещениях / Л.Н. Колечкина // Теорія оптимальних рішень: Зб. наук. пр. — 2007. — № 6. — С. 67-73. — Бібліогр.: 7 назв. — рос. |
| collection | DSpace DC |
| container_title | Теорія оптимальних рішень |
| description | The problem of multicriterion combinatorial optimization on placing is examined. It is grounded, that the effective decisions of task are in the tops of polyhedron of placing. The algorithm of finding of Pareto-optimum estimations is represented for combinatorial multicriterion problems.
|
| first_indexed | 2025-12-07T17:05:20Z |
| format | Article |
| fulltext |
Теорія оптимальних рішень. 2007, № 6 67
ÒÅÎвß
ÎÏÒÈÌÀËÜÍÈÕ
вØÅÍÜ
Рассматривается задача много-
критериальной комбинаторной
оптимизации на размещениях.
Обосновано, что эффективные
решения задачи находятся в вер-
шинах многогранника размеще-
ний. Представлено алгоритм на-
хождения парето-оптимальных
оценок для комбинаторных мно-
гокритериальных задач.
_____________________________
Л.Н. Колечкина, 2007
ÓÄÊ 519.85
Ë.Í. ÊÎËÅ×ÊÈÍÀ
ÎÏÒÈÌÀËÜÍÛÅ ÐÅØÅÍÈß
ÌÍÎÃÎÊÐÈÒÅÐÈÀËÜÍÛÕ
ÊÎÌÁÈÍÀÒÎÐÍÛÕ ÇÀÄÀ×
ÍÀ ÐÀÇÌÅÙÅÍÈßÕ
Введение. При решении почти каждой слож-
ной практической задачи возникает необхо-
димость в рассмотрении ее модели со мно-
гими критериями. Учитывая эти данные в
настоящее время бурно развивается теория
дискретных оптимизационных многокрите-
риальных задач. При этом не всегда учиты-
ваются имеющиеся комбинаторные свойства
допустимой области. Многокритериальность
в прикладном аспекте позволяет учесть од-
новременно несколько факторов, показате-
лей, характеристик и дает возможность адек-
ватно моделировать реальные процессы и
системы. Сочетание таких проблем приводит
к исследованию многокритериальных задач
на комбинаторных множествах. Эти пробле-
мы являются сложными каждая сама по себе,
а в совокупности они практически не иссле-
довались, т. е. их изучение и решение явля-
ется достаточно важным и актуальным.
Многокритериальные задачи рассматри-
ваются в [1–5], задачи комбинаторной опти-
мизации на разных комбинаторных множе-
ствах в [6, 7].
Как известно, одним из основных, фунда-
ментальных понятий теории многокритери-
альности является понятия оптимального по
Парето, т. е. эффективного решения.
В настоящей работе рассматриваются за-
дачи оптимизации с несколькими целевыми
функциями на комбинаторном множестве
размещений и поиск парето-оптимальных
решений.
Л.Н. КОЛЕЧКИНА
68 Теорія оптимальних рішень. 2007, № 6
На практике такие задачи возникают, когда необходимо сформулировать и
формализовать в виде критериев ряд отдельных требований, которые предъяв-
ляются к оптимальному решению. Объединить эти критерии в один, обобщен-
ный, не всегда целесообразно и возможно.
1. Постановка задачи. Для дальнейшего изложения материалы используем
понятие мультимножество, что определяется основой и кратностью элементов
[6]. Пусть задано мультимножество { }η= gggА ,...,, 21 , а { }neeeАS ,...,,)( 21= его
основание, кратность элементов η=η++η+η∈η= nnjj Njek ...,,)( 21 , где
je 1R∈ , nNj ∈∀ . Возьмем произвольное η∈ Nk , kj ≤η .
Упорядоченной k -выборкой мультимножества А называется набор
( )
kiii ggge ,,,
21
K= , (1)
где Аg
ji ∈ ,kj Ni ∈∀ ,kNj ∈∀ ,ts ii ≠ если ts ≠ ,kNs ∈∀ kNt ∈∀ .
Определение 1 [6]. Множество )(AР , элементами которого являются
k -выборки вида (1) мультимножества A , называется евклидовым комбина-
торным множеством, если для произвольных его элементов ),...,,( 21 kaaae =′ ,
),...,,( 21 kbbbe =′′ выполняются условия: ):()( jjk baJjee ≠∈∃⇔′′≠′ , т. е. мно-
жество )(AР имеет такие свойства: два элемента множества )(AР отличаются
друг от друга, если они независимо от других отличий отличаются порядком
размещения символов, что их образуют.
Совокупность всех упорядоченных k -выборок вида (1) мультимножества
А будем называть общим множеством k -размещений и обозначим его ( )AP
k
nη .
Интерес к евклидовым комбинаторным множествам связан с возможностью
рассматривать их как точки k
R , т. е. с возможностью погружения их в арифме-
тическое евклидово пространство k
R .
Пусть )(AР − эвклидово комбинаторное множество, а e вида (1) − элемент
)(AР . Отображение k
f RAРAРf ⊂→ )()(: называется погружением множества
)(AР в арифметическое эвклидово пространство, если f ставит множеству
)(AР во взаимнооднозначное соответствие множеству k
f RAР ⊂)( по правилу:
для ( )
kii gge , ,
1
K= )(AР∈ , )(efx = , )()...,( 1 AРxxx fk ∈= , имеем
jij gx =
kNj ∈∀ .
Рассмотрим комбинаторную многокритериальную задачу на множестве
размещений.
ОПТИМАЛЬНЫЕ РЕШЕНИЯ МНОГОКРИТЕРИАЛЬНЫХ КОМБИНАТОРНЫХ ЗАДАЧ …
Теорія оптимальних рішень. 2007, № 6 69
Пусть линейная вектор-функция f имеет вид
),,...,,,,()( 21
xcxcxcxf
m= , (2)
а множество допустимых решений задачи определяется пересечением двух
множеств )(APXD
k
nη∩= , где множества Х задано конечной системой линей-
ных неравенств
},,{ kj
jn
NjbxaRxХ ∈≤∈= ,
где kj
nj
NjRbRa ∈∈∈ ,, , (3)
а множества размещений
)( APx
k
nη∈ . (4)
Под решением комбинаторной задачи (2 – 4), будем понимать нахождение
элементов ( )xfP , – множество парето-оптимальных (эффективных решений).
Согласно [5] для произвольного Xx ∈ истинно утверждение:
( ) ( ) ( ) ( ) ( ){ }=≠≥∈⇔∈ xfyfxfyfXyxfPx ,|, Ø. (5)
В работе [6], рассмотрено решение задач с линейной функцией цели на
множестве размещений. Как известно )()( AconvPАП k
n
k
n ηη = и называется общим
многогранником размещений. Пусть элементы мультимножества А упорядоче-
ны таким образом:
η≤≤ gg ...1 , (6)
то общий многогранник размещений )(GП k
nη задается системой неравенств
∑ ∑ ∑
ω
= ω∈
ω
=
+−η≤≤
1 1
1
j i j
iij gxg , kN⊂ω∀ . (7)
Если k≥η1 , то левая часть неравенств в системе (7) может быть заменена
неравенствами 11 xg < ki N∈∀ . Если kn ≥η , то правая часть неравенств в си-
стеме (7) может быть заменена неравенствами η≤ gxi , ki N∈∀ . Если условия
k≥1η , kn ≥η выполняются вместе, то многогранник )(A
k
nηΠ преобразуется в
куб: η≤≤ gxg i1 , ki N∈∀ .
Известно из [6], что для задачи нахождения минимума функции
∑
=
=
k
j
jj xcxf
1
)( , (8)
Л.Н. КОЛЕЧКИНА
70 Теорія оптимальних рішень. 2007, № 6
где α≥≥≥α≥α +α
kss
c...cc...c
11
, kNs ∈ , kN∈α , на общем множестве размеще-
ний ( )AP
k
nη минимум достигается в точке )(),...,( 1 GPxxx
k
nk η
∗∗∗ ∈= , которая
удовлетворяет условиям
si Nigx
i
∈∀=∗
α ; rir Nigx
is
∈∀= +−η
∗
α +
, (9)
если элементы мультимножества А упорядочены согласно (6), где r , s кон-
станты, удовлетворяющие условия ksr =+ , kNsr ∈, .
Учитывая вышеописанное, можно определить условия нахождения реше-
ния многокритериальной задачи (2), (4) без дополнительных условий (3). Такую
многокритериальную задачу назовем многокритериальной безусловной задачей
с линейными критериями на множестве размещений. В некоторых случаях мо-
жет быть полезным
Утверждение 1. Если iB – множество перестановок ),...,( 1
i
k
ii αα=α эле-
ментов множества первых натуральных чисел kN , что удовлетворяют условию
iiiii
i
k
i
s
i
s
ii C...CC...CC
ααααα
≥≥≥≥≥≥
+121
, (10)
то множество эффективных решений задачи (2), (4) не пусто, если не пусто
множество, которое является пересечением множеств решений iR , найденных
для каждого критерия mi Ni,x,c ∈ отдельно:
∅≠=
=
RR
m
i
iI
1
. (11)
Для любой перестановки Β∈αα=α ),...,( 1 k , точка )()...( **
1
*
APxxx
k
nk η∈= , в
виде (9) при условии (6), принадлежит множеству эффективных решений.
Доказательство. Понятно, что если Β∈α , то mі Nі∈∀Β∈α , а поэтому
точка *x в виде (9) при условии (6) определяет точку, которая принадлежит
одновременно множествам решений для каждого из критериев отдельно (2).
Поэтому, точка *x – оптимальное решение задачи (2), (4).
Вышерассмотренное утверждение не дает ответа на вопрос: какие решения
найдены: эффективные, слабо эффективные или строго эффективные.
Но одним из основных понятий многокритериальных задач, как определено
выше, является понятия парето-оптимального решения. Для комбинаторных
многокритериальных задач оно представляет обобщенное понятие точки мак-
симума числовой функции, т. е. решение парето-оптимально, если значения лю-
бого из критериев можно улучшить лишь за счет ухудшения значений осталь-
ных критериев.
Свойствам и методам отыскания парето-оптимальных решений посвящена
достаточно обширная литература, но для выше сформулированной задачи ком-
ОПТИМАЛЬНЫЕ РЕШЕНИЯ МНОГОКРИТЕРИАЛЬНЫХ КОМБИНАТОРНЫХ ЗАДАЧ …
Теорія оптимальних рішень. 2007, № 6 71
бинаторной оптимизации (2 – 4) необходимо учесть специфику и комбинатор-
ные свойства области допустимых решений.
Утверждение 2. Парето-оптимальные решения многокритериальных ком-
бинаторных задач на размещениях находятся в вершинах многогранника раз-
мещений )(GП k
nη .
Доказательство. Если рассматривать многокритериальную комбинаторную
безусловную задачу (2), (4), то согласно утверждению 1 оптимальные решения –
точки множества размещений )( AP
k
nη . Как известно vert )(A
k
nηΠ = )( AP
k
nη , то
при наложении дополнительных условий (3), эффективные решения также бу-
дут в вершинах, поскольку условия (3) только усекают область, которая описы-
вается системой неравенств (7). Понятно, что случай ∅=D не рассматривается.
Теорема доказана.
Наряду с множеством парето-оптимальных решений комбинаторной много-
критериальной задачи целесообразно рассмотреть множество парето-
оптимальных оценок [3]. Вектор ( )*
xf при парето-оптимальном решении ∗
x
называют парето-оптимальным вектором оценок, а множество всех таких век-
торов – множеством парето-оптимальных оценок. Обозначим
( ) ( )( )== XPfYP f { ( ) |*
Yxf ∈ при некотором ( )XPx f∈* }, (12)
где Y означает множество возможных векторов, т. е. ( )xfY = .
Благодаря наличию вышеуказанной прямой связи (12) между множествами
эффективных решений и парето-оптимальных векторов можно применить алго-
ритм нахождения множества парето-оптимальных оценок для задачи комбина-
торной оптимизации (2 – 4), аналогичный [3].
Алгоритм
Шаг 1. Для всех точек )(),...,( 1 APxxx
k
nk η∈= определить множество
возможных оценок { }N
yyyY ,...,, 21= .
Шаг 2. Образовать множество парето-оптимальных оценок, вы-
брав 2,1,)( === jiYYP , которые совпадают с множеством решений Y .
Шаг 3. Проверить выполнение неравенства ji
yy ≥ , если оно выполняется,
то перейти к шагу 4, иначе перейти к шагу 6.
Шаг 4. Удалить из текущего множества векторов )(YP вектор j
y , перейти
к шагу 5.
Шаг 5. Проверить выполнение неравенства Nj < , если оно выполняется,
то положить 1+= jj и вернуться к шагу 3. В другом случае необходимо перей-
ти к шагу 8.
Л.Н. КОЛЕЧКИНА
72 Теорія оптимальних рішень. 2007, № 6
Шаг 6. Проверить справедливость неравенства ji
yy ≥ , если оно выполня-
ется, перейти к шагу 7, иначе вернуться к шагу 5.
Шаг 7. Удалить из текущего множества векторов )(YP вектор i
y и перей-
ти к шагу 8.
Шаг 8. Проверить выполнение неравенства 1−< Ni , если оно выполняет-
ся, то положить 1+= ii , а затем 1+= ij . После этого необходимо вернуться к
шагу 3, иначе расчеты закончить. Множество парето-оптимальных оценок по-
строено полностью.
Суть алгоритма состоит в том, что искомое множество парето-оптимальных
оценок образуется с последовательным удалением заблаговременно известных
неоптимальных векторов.
Задача усложняется, если область возможных решений определяется не
только комбинаторными условиями, которые описывают комбинаторный мно-
гогранник размещения, а накладываются еще дополнительные ограничения.
Заключение. Исследованы решения комбинаторной многокритериальной
задачи. Обоснован подход к нахождению эффективных оценок.
Дальнейшее развитие данной работы будет направлено на разработку алго-
ритма и исследования множества эффективных решений.
Будет исследована эффективность алгоритма при решении конкретных
практических задач.
Л.М. Колєчкіна
ОПТИМАЛЬНІ РОЗВ’ЯЗКИ БАГАТОКРИТЕРІАЛЬНИХ КОМБІНАТОРНИХ ЗАДАЧ НА
РОЗМІЩЕННЯХ
Розглядається задача багатокритеріальної комбінаторної оптимізації на розміщеннях. Пока-
зано, що ефективні розв'язки задачі знаходяться у вершинах багатогранника розміщень.
Представлено алгоритм знаходження парето-оптимальних оцінок для комбінаторних багато-
критеріальних задач.
L.N. Kolechkina
OPTIMUM DECISIONS OF MULTICRITERION COMBINATORIAL PROBLEMS ON
PLACING
The problem of multicriterion combinatorial optimization on placing is examined. It is grounded,
that the effective decisions of task are in the tops of polyhedron of placing. The algorithm of find-
ing of Pareto-optimum estimations is represented for combinatorial multicriterion problems.
1. Сергиенко И.В. Математические модели и методы решения задач дискрет-
ной оптимизации. – Киев: Наук. думка, 1988. – 472 с.
2. Козерацкая Л.Н. Множество строго эффективных точек задачи частично це-
лочисленной векторной оптимизации – как характеристика ее устойчивости
ОПТИМАЛЬНЫЕ РЕШЕНИЯ МНОГОКРИТЕРИАЛЬНЫХ КОМБИНАТОРНЫХ ЗАДАЧ …
Теорія оптимальних рішень. 2007, № 6 73
// Кибернетика и системный анализ. – 1997. – № 6. – С. 181 – 184.
3. Подиновский В.В., Ногин В.Д. Парето-оптимальные решения многокритери-
альных задач. – М.: Наука, 1982. – 256 с.
4. Сергиенко И.В., Козерацкая Л.Н., Лебедева Т.Т. Исследование устойчиво-
сти и параметрический анализ дискретных оптимизационных задач. – Киев:
Наук. думка, 1995. – 171 с.
5. Лебедева Т.Т., Семенова Н.В., Сергиенко Т.И. Устойчивость векторных задач
целочисленной оптимизации: взаимосвязь с устойчивостью множеств опти-
мальных и неоптимальных решений // Кибернетика и системный анализ. –
2005. – № 4 – С. 90 – 100 .
6. Стоян Ю.Г., Ємець О.О. Теорія і методи евклідової комбінаторної оптимі-
зації. – К.: Ін-т системн. досліджень освіти, 1993. – 188 с.
7. Ємець О.О., Колєчкіна Л.М. Задачі комбінаторної оптимізації з дробово-
лінійними цільовими функціями. – К.: Наук. думка, 2005. – 118 с.
Получено 17.04.2007
|
| id | nasplib_isofts_kiev_ua-123456789-84995 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | XXXX-0013 |
| language | Russian |
| last_indexed | 2025-12-07T17:05:20Z |
| publishDate | 2007 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Колечкина, Л.Н. 2015-07-18T06:12:05Z 2015-07-18T06:12:05Z 2007 Оптимальные решения многокритериальных комбинаторных задач на размещениях / Л.Н. Колечкина // Теорія оптимальних рішень: Зб. наук. пр. — 2007. — № 6. — С. 67-73. — Бібліогр.: 7 назв. — рос. XXXX-0013 https://nasplib.isofts.kiev.ua/handle/123456789/84995 519.85 The problem of multicriterion combinatorial optimization on placing is examined. It is grounded, that the effective decisions of task are in the tops of polyhedron of placing. The algorithm of finding of Pareto-optimum estimations is represented for combinatorial multicriterion problems. ru Інститут кібернетики ім. В.М. Глушкова НАН України Теорія оптимальних рішень Оптимальные решения многокритериальных комбинаторных задач на размещениях Optimum decisions of multicriterion combinatorial problems on placing Article published earlier |
| spellingShingle | Оптимальные решения многокритериальных комбинаторных задач на размещениях Колечкина, Л.Н. |
| title | Оптимальные решения многокритериальных комбинаторных задач на размещениях |
| title_alt | Optimum decisions of multicriterion combinatorial problems on placing |
| title_full | Оптимальные решения многокритериальных комбинаторных задач на размещениях |
| title_fullStr | Оптимальные решения многокритериальных комбинаторных задач на размещениях |
| title_full_unstemmed | Оптимальные решения многокритериальных комбинаторных задач на размещениях |
| title_short | Оптимальные решения многокритериальных комбинаторных задач на размещениях |
| title_sort | оптимальные решения многокритериальных комбинаторных задач на размещениях |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/84995 |
| work_keys_str_mv | AT kolečkinaln optimalʹnyerešeniâmnogokriterialʹnyhkombinatornyhzadačnarazmeŝeniâh AT kolečkinaln optimumdecisionsofmulticriterioncombinatorialproblemsonplacing |