Поліедральний підхід до розв'язання одного класу векторних задач комбінаторної оптимізації
Розглядаються багатокритерiальнi задачi дискретної оптимiзацiї на допустимiй комбiнаторнiй множинi полiрозмiщень. Дослiджуються структурнi властивостi допустимої областi i рiзних видiв ефективних розв’язкiв. На основi розвитку iдей евклiдової комбiнаторної оптимiзацiї i методу головного критерiю роз...
Збережено в:
| Дата: | 2009 |
|---|---|
| Автори: | , |
| Формат: | Стаття |
| Мова: | Українська |
| Опубліковано: |
Видавничий дім "Академперіодика" НАН України
2009
|
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/8642 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Поліедральний підхід до розв'язання одного класу векторних задач комбінаторної оптимізації / Н.В. Семенова, Л.М. Колєчкiна // Доп. НАН України. — 2009. — № 6. — С. 46-53. — Бібліогр.: 15 назв. — укр. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859640446070816768 |
|---|---|
| author | Семенова, Н.В. Колєчкіна, Л.М. |
| author_facet | Семенова, Н.В. Колєчкіна, Л.М. |
| citation_txt | Поліедральний підхід до розв'язання одного класу векторних задач комбінаторної оптимізації / Н.В. Семенова, Л.М. Колєчкiна // Доп. НАН України. — 2009. — № 6. — С. 46-53. — Бібліогр.: 15 назв. — укр. |
| collection | DSpace DC |
| description | Розглядаються багатокритерiальнi задачi дискретної оптимiзацiї на допустимiй комбiнаторнiй множинi полiрозмiщень. Дослiджуються структурнi властивостi допустимої областi i рiзних видiв ефективних розв’язкiв. На основi розвитку iдей евклiдової комбiнаторної оптимiзацiї i методу головного критерiю розроблений i обгрунтований полiедральний пiдхiд до розв’язання зазначеного класу задач.
Multicriterial problems of discrete optimization on a feasible combinatorial set of polyarrangements are considered. Structural properties of the feasible region and different types of efficient solutions are explored. On the basis of development of the ideas of Euclidean’s combinatorial optimization and the method of main criterion, a polyhedral approach to the solution of multicriterial combinatorial problems on the set of polyarrangements is developed and grounded.
|
| first_indexed | 2025-12-07T13:20:58Z |
| format | Article |
| fulltext |
УДК 519.8
© 2009
Н.В. Семенова, Л. М. Колєчкiна
Полiедральний пiдхiд до розв’язання одного класу
векторних задач комбiнаторної оптимiзацiї
(Представлено академiком НАН України I. В. Сергiєнком)
Розглядаються багатокритерiальнi задачi дискретної оптимiзацiї на допустимiй комбi-
наторнiй множинi полiрозмiщень. Дослiджуються структурнi властивостi допусти-
мої областi i рiзних видiв ефективних розв’язкiв. На основi розвитку iдей евклiдової
комбiнаторної оптимiзацiї i методу головного критерiю розроблений i обгрунтований
полiедральний пiдхiд до розв’язання зазначеного класу задач.
Новим теоретичним пiдходом для розв’язання важливих задач економiки, проектування
складних систем, прийняття рiшень в умовах невизначеностi тощо є застосування моде-
лей i методiв, що об’єднують багатокритерiальнiсть альтернатив i рiзнi комбiнаторнi вла-
стивостi допустимої множини. На сьогоднiшнiй день в областi дослiдження рiзних класiв
дискретних та векторних оптимiзацiйних задач, побудови методiв їх розв’язання отриманi
iстотнi результати [1–15].
Для розв’язання задач комбiнаторної оптимiзацiї розробленi рiзнi обчислювальнi ме-
тоди. Однi з найбiльш перспективних з них видiлилися в окрему область полiедральної
комбiнаторики [4–8, 10–13]. Загальна iдея цих методiв полягає у встановленнi зв’язку екс-
тремальних комбiнаторних задач з методами лiнiйного програмування i виглядає таким
чином: елементи допустимої множини iнтерпретуються як точки евклiдового простору,
функцiї критерiїв i обмежень розглядаються як неперервнi. Отже, розв’язується задача
знаходження екстремуму функцiї на опуклiй оболонцi заданих точок (тобто на опуклому
многограннику). Дiйсно, екстремум лiнiйної функцiї на многограннику досягається в однiй
з вершин, яка включається в множину елементiв, що розглядаються. Задача знаходження
екстремуму лiнiйної функцiї є задачею лiнiйного програмування. Особливiсть розв’язання
комбiнаторних задач при такому зведеннi полягає в тому, що при знаходженнi розв’язкiв
варто обмежитися лише вершинами многогранника.
Останнiм часом в областi дослiдження рiзних класiв комбiнаторних моделей, розробки
нових методiв їх розв’язання велика увага придiляється методам, що грунтуються на вико-
ристаннi структурних властивостей комбiнаторних множин [2, 4–11, 14, 15]. Використання
iнформацiї про структуру опуклої оболонки допустимих розв’язкiв, яка є основою для бага-
тьох методiв, — один iз самих успiшних на сьогоднiшнiй день пiдходiв до розв’язання задач
комбiнаторної оптимiзацiї. Але при розв’язаннi таких задач виникають проблеми, пов’язанi
зi складнiстю математичних моделей, великим обсягом iнформацiї та iн. У данiй роботi
формулюється i дослiджується нова актуальна багатокритерiальна задача на допустимiй
комбiнаторнiй множинi полiрозмiщень. Особливiсть роботи полягає у вивченнi комбiна-
торних властивостей многогранникiв в тiсному зв’язку з задачами векторної оптимiзацiї,
важливими для практичного застосування.
Властивостi евклiдових комбiнаторних множин описанi в багатьох роботах. Поряд з до-
бре вiдомими евклiдовими комбiнаторними множинами перестановок, розмiщень, сполу-
чень, розбиттiв видiляються бiльш складнi структури — полiкомбiнаторнi множинi. Iнтерес
46 ISSN 1025-6415 Reports of the National Academy of Sciences of Ukraine, 2009, №6
до таких множин зумовлений рiзними прикладними задачами, оскiльки значна їх кiлькiсть
добре описується за допомогою полiкомбiнаторних конструкцiй [7, 8, 10].
Дана робота продовжує i розвиває дослiдження багатокритерiальних задач на комбiна-
торних та полiкомбiнаторних множинах, наведених в роботах [4–8, 14, 15]. Для векторних
задач комбiнаторного типу на множинi полiрозмiщень на основi вивчених властивостей
многогранникiв, якi описують опуклу оболонку допустимої множини, запропонований по-
лiедральний пiдхiд до розв’язання, заснований на iдеях методiв головного критерiю, рела-
ксацiї, вiдтинаючих площин.
1. Постановка задачi. Як вiдомо, розмiщенням iз q елементiв по n називається упо-
рядкований набiр a = (ai1 , ai2 , . . . , ain) iз n елементiв, що належать мультимножинi A =
= {a1, a2, . . . , aq}. Нехай A(q, k, n) — загальна комбiнаторна множин n-розмiщень, iндуко-
вана q > n елементами з мультимножини A, серед елементiв якої k рiзних. Образ множини
A(q, k, n) при вiдображеннi в R
n позначимо E(q, k, n). Усяка точка x ∈ E(q, k, n) має таку
властивiсть, що її координати набувають значень з мультимножини A дiйсних чисел, тобто
x = (x1, x2, . . . , xn), де xj = aij , aij ∈ A ∀ i, j ∈ Nn.
Подамо множину Nq у виглядi упорядкованого розбиття на s, де s < q, непорожнiх
пiдмножин J1, . . . , Js, якi попарно не перетинаються, тобто для них виконуються умови:
Ji
⋂
Jj = ∅, Ji 6= ∅, Jj 6= ∅, ∀ i, j ∈ Ns, а також упорядкованого розбиття числа n на s
доданкiв n1, n2, . . . , ns, що задовольняють умову 1 6 ni 6 qi, ∀ i ∈ Ns, |Ji| = qi. Очевидно,
що q1 + q2 + . . . + qs = q, n1 + n2 + · · · + ns = n. Позначимо H множину елементiв вигляду
h = (h(1), . . . , h(n)) = (h1, . . . , hs), де h(j) ∈ Nn, j ∈ Nn, а hi — довiльна перестановка
елементiв множини Ji ∀ i ∈ Ns. Нехай пiдмультимножина Ai мультимножини A складається
з тих елементiв A, номери яких належать множинi Ji: Ai = {ai
1, a
i
2, . . . , a
i
ni
}, |Ji| = ni.
Означення. Множину A(q, k, n, s) = {(ah(1), . . . , ah(n)) | ah(i) ∈ A ∀ i ∈ Nn,∀h ∈ H}
називають загальною множиною полiрозмiщень.
Не втрачаючи загальностi, упорядкуємо елементи мультимножини A за неспаданням:
a1 6 a2 6 · · · 6 an. Очевидно, що це упорядкування зберiгається i для кожної пiдмульти-
множини Ai, i ∈ Ns, з A.
Розглянемо задачу оптимiзацiї на евклiдовiй комбiнаторнiй множинi
Z(Φ, A(q, k, n, s)) : max{Φ(a) | a ∈ A(q, k, n, s)},
що полягає в максимiзацiї векторного критерiю Φ(a) = (Φ1(a), . . . ,Φl(a)) на множинi полi-
розмiщень, де Φi : R
n → R
1, i ∈ Nl.
2. Деякi властивостi евклiдової множини полiрозмiщень. Опуклою оболон-
кою множини полiрозмiщень A(q, k, n, s) є многогранник полiрозмiщень Mns
qk (A) =
= conv A(q, k, n, s), множина вершин якого є пiдмножиною множини полiрозмiщень:
vert Mns
qk (A) ⊆ A(q, k, n, s).
Теорема 1. Многогранник полiрозмiщень Mns
qk (A) визначається сукупнiстю всiх роз-
в’язкiв такої системи нерiвностей:
ni
∑
j=1
xj 6
ni
∑
j=1
ai
j , i ∈ Ns, (1)
mi
∑
j=1
xαj
>
mi
∑
j=1
ai
j , mi ∈ Nqi−1, αj ∈ Ji ∀ i ∈ Ns (2)
ISSN 1025-6415 Доповiдi Нацiональної академiї наук України, 2009, №6 47
αj 6= αt, ∀ j 6= t, ∀ j, t ∈ Ji.
Розглянемо деякi його властивостi i зв’язок iз загальною множиною полiрозмiщень.
Очевидно, що з системи лiнiйних нерiвностей (1), (2) можна видiлити s пiдсистем лiнiй-
них нерiвностей, що описують многогранники розмiщень Mni
qiki
(Ai), якi є опуклими комбi-
нацiями множини розмiщень ahi , i ∈ Ns. Отже,
Mni
qiki
(Ai) =
{
x ∈ R
ni
∣
∣
∣
∣
∣
ni
∑
j=1
xj 6
ni
∑
j=1
ai
qi−j ,
mi
∑
j=1
xαj
>
mi
∑
j=1
ai
j
}
,
mi ∈ Nqi−1, αj ∈ Ji, αj 6= αt, ∀ j 6= t, ∀ j, t ∈ Ji, ∀ i ∈ Ns. Кожний з многогранникiв Mni
qiki
(Ai)
є многогранником розмiщень.
Як вiдомо, пiд добутком многогранникiв M1, . . . ,Ms розумiють множину
s
⊗
i=1
Mi = {x ∈ R
d1+···+ds | x = (x1, . . . , xs), xi ∈ Mi ∀ i ∈ Ns},
де Mi — di-вимiрний многогранник. Вiдповiдно до твердження 3.2 [12, с. 26] справедлива
рiвнiсть
s
⊗
i=1
Mni
qiki
(Ai) = {x ∈ R
d1+···+ds | x = (x1, . . . , xs), xi ∈ Mni
qiki
(Ai)∀ i ∈ Ns},
тобто точка x ∈
s
⊗
i=1
Mni
qiki
(Ai) задовольняє кожну з s пiдсистем системи (1), (2). Отже,
можна стверджувати, що якщо ahi — вершина многогранника Mni
qiki
(Ai), то a(h) =
s
⊗
i=1
ahi ,
a(h) = (ah1 , . . . , ahs), де a(h) ∈ A(q, k, n, s).
Теорема 2. Многогранник полiрозмiщень Mns
qk (A) при ni < qi ∀ i ∈ Ns комбiнаторно
еквiвалентний многограннику полiперестановок M s
nk(A), що має розмiрнiсть n = n1 +
+ n2 + · · · + ns.
Справедливiсть теореми випливає з того, що Mns
qk (A) =
s
⊗
i=1
Mni
qiki
(Ai), теореми 4.8 [12,
с. 193] та означення многогранника полiперестановок [10].
Наслiдок 1. Для числа ri(M
ni
qiki
(Ai)) i-вимiрних граней (0 6 i 6 ni) многогранника
полiрозмiщень Mni
qiki
(Ai) справедлива формула
ri(M
ni
qiki
(Ai)) =
∑ (ni + 1)!
ti1!t
i
2! · · · t
i
ni−i+1!
∀ i ∈ Nni
,
де пiдсумовування проводиться за всiма розв’язками рiвняння ti1 + ti2 + · · · + tini−i+1 = ni
в цiлих додатних числах.
Оскiльки множина полiрозмiщень є пiдмножиною множини розмiщень A(q, k, n, s) ⊂
⊂ A(q, k, n) ∀ s ∈ Nn, то кiлькiсть елементiв полiрозмiщень не перевершує загальну кiлькiсть
елементiв множини розмiщень.
Твердження 1. Загальне число Ans
qk полiрозмiщень дорiвнює
Ans
qk = |A(q, k, n, s)| =
s
∏
i=1
qi!
(qi − ni)!
.
Справедливi такi теореми [10].
48 ISSN 1025-6415 Reports of the National Academy of Sciences of Ukraine, 2009, №6
Теорема 3. Mns
qk (A) =
s
⊗
i=1
Mni
qiki
(Ai).
Теорема 4. Множина вершин многогранника Mns
qk (A) є пiдмножиною множини полi-
розмiщень A(q, k, n, s).
Слiд вiдзначити, що загальне число p лiнiйних нерiвностей, що входять у систему (1), (2)
та описують многогранник полiрозмiщень Mns
qk (A), досить велике. У деяких випадках його
можна зменшити.
Твердження 2. Якщо з n координат xi, i ∈ Nn, точки x ∈ R
n тiльки k рiзних, то
число нерiвностей системи, що описують опуклий многогранник Mns
qk (A), можна змен-
шити, виключивши з системи N =
s
∑
i=1
Ni нерiвностей, де Ni = 1 + ni +
ni
∑
j=i+1
Cj
ni
, i ∈
∈ Ns.
Доведення. Сукупнiсть нерiвностей пiдсистеми для деякої пiдмножини Ji, i ∈ Ns,
системи (1), (2), якi мають однакове значення mi верхньої межi пiдсумовування, будемо
називати mi-ю групою нерiвностей цiєї пiдсистеми, де i ∈ Ns. У кожну mi-ту групу вхо-
дить Cmi
qi
нерiвностей. Отже, загальне число pi нерiвностей, що описують многогранник
Mni
qiki
(Ai), дорiвнює pi =
qi
∑
i=0
Cmi
qi
= 2qi , i ∈ Ns. Оскiльки з qi координат ai
j , j ∈ Ji, ki рiз-
них, то з i-ї пiдсистеми нерiвностей (1), (2) можна виключити деякi нерiвностi. З огляду на
умови a1 6 a2 6 · · · 6 aq для будь-якого j ∈ Nmi−1, mi 6 qi, i 6 Ns, справедлива рiвнiсть
ai
j = ai
j+1. Тому при виконаннi нерiвностей першої групи в пiдсистемi (1), (2) будуть також
справедливi нерiвностi другої, третьої, . . . , mi-ї, i ∈ Ns, груп. Дiйсно, оскiльки xj > ai
1,
j ∈ Ji, i ∈ Ns, то ∀mi ∈ Nn, i ∈ Ns, виконується умова
mi
∑
j=1
xαj
> mia
i
1. Отже, з кожної
пiдсистеми системи (1), (2), що описує многогранник полiрозмiщень Mns
qk (A), можна ви-
ключити нерiвностi другої, третьої, . . . , mi-ї, i ∈ Ns, груп i загальне число нерiвностей у mi
пiдсистемi буде складати Ni = 1 + qi +
qi
∑
j=i+1
Cj
qi
. Аналогiчнi мiркування можна провести,
якщо набiр чисел (ai
1, a
i
2, . . . , a
i
n) має властивiсть ai
j = ai
j+1 ∀ j ∈ Nni−1 \ Nni−mi
, i ∈ Ns,
то в пiдсистемi системи (1), (2) досить залишити тiльки нерiвностi першої, другої, . . . ,
(mi − j)-ї груп. Таким чином, число нерiвностей, яке можна виключити iз системи (1), (2),
дорiвнюватиме N =
s
∑
i=1
Ni.
При вiдображеннi множини полiрозмiщень A(q, k, n, s) в евклiдiв простiр R
n сформулю-
ємо задачу Z(F,X) максимiзацiї векторного критерiю F (x) на допустимiй множинi X:
Z(F,X) : max{F (x) | x ∈ X}.
Кожному елементу a ∈ A(q, k, n, s) вiдповiдає точка x ∈ X, така, що F (x) = Φ(a), де
F (x) = (f1(x), f2(x), . . . , fl(x)), fi : R
n → R
1, i ∈ Nl, X 6= ∅, vert Mns
qk (A) ⊆ X ⊆ Mns
qk (A) =
= conv A(q, k, n, s). Нехай задача Z(F,X) мiстить також опуклi обмеження, що утворю-
ють замкнуту опуклу множину D ⊂ R
n вигляду: D = {x ∈ R
n, gi(x) 6 0, i ∈ Nm}. Тодi
vert Mns
qk (A)
⋂
D ⊆ X ⊂ Mn1
qk
⋂
D.
Традицiйне поняття оптимальностi в задачах багатокритерiальної оптимiзацiї замiнює-
ться на поняття Парето-оптимальностi (ефективностi), слабої ефективностi (оптимальностi
за Слейтером) та строгої ефективностi (оптимальностi за Смейлом). Отже, пiд розв’язками
задачi Z(F,X) будемо розумiти елементи таких множин: P (F,X) — Парето-оптимальних
ISSN 1025-6415 Доповiдi Нацiональної академiї наук України, 2009, №6 49
розв’язкiв, Sl(F,X) — слабо ефективних, Sm(F,X) — строго ефективних розв’язкiв. Згiдно
з [3], для ∀x ∈ X справедливi твердження:
x ∈ Sl(F,X) ⇔ {y ∈ X | F (y) > F (x)} = ∅, (3)
x ∈ P (F,X) ⇔ {y ∈ X | F (y) > F (x), F (y) 6= F (x)} = ∅, (4)
x ∈ Sm(F,X) ⇔ {y ∈ X | y 6= x, F (y) > F (x)} = ∅, (5)
Sm(F,X) ⊂ P (F,X) ⊂ Sl(F,X). (6)
Оскiльки |X| < ∞, то множина P (F,X) 6= ∅ i зовнi стiйка [9].
3. Структурнi властивостi та умови оптимальностi рiзних множин ефектив-
них розв’язкiв.
Теорема 5.
P (F,G)
⋂
vert Mns
qk (A) ⊂ P (F,X),
Sl(F,G)
⋂
vert Mns
qk (A) ⊂ Sl(F,X),
Sm(F,G)
⋂
vert Mns
qk (A) ⊂ Sm(F,X).
Нехай функцiї fi(x), i ∈ Nl, векторного критерiю F (x) є лiнiйними: fi(x) = 〈ci, x〉, ci,
i ∈ Nl, — вектор-рядок матрицi C ∈ R
n×l. Позначимо K = {x ∈ R
n | Cx > 0} — конус
перспективних напрямкiв [3] задачi Z(F,X), int K = {x ∈ R
n | Cx > 0} — внутрiшнiсть
конуса K, K0 = {x ∈ R
n | Cx = 0} — ядро лiнiйного вiдображення C : R
n → R
l. З фор-
мул (3)–(5) випливає справедливiсть тверджень
x ∈ Sl(C,X) ⇔ (x + int K)
⋂
X = ∅, (7)
x ∈ P (C,X) ⇔ (x + (K \ K0))
⋂
X = ∅, (8)
x ∈ Sm(C,X) ⇔ (x + K)
⋂
X \ {x} = ∅. (9)
Твердження 3. При виконаннi умов ni = qi − 1 ∀ i ∈ Ns справедливi включення
Sm(F,X) ⊂ P (F,X) ⊂ Sl(F,X) ⊂ vert Mns
qk (A).
Теорема 6. Якщо допустима множина X задачi Z(F,X) не мiстить обмежень, якi
описують опуклу множину D або Mns
qk (A) ⊆ D та ni = qi − 1 ∀ i ∈ Ns, тобто X =
= vert Mns
qk (A), то справедливi рiвностi
P (F,Mns
qk (A))
⋂
vert Mns
qk (A) = P (F,X),
Sl(F,Mns
qk (A))
⋂
vert Mns
qk (A) = Sl(F,X),
Sm(F,Mns
qk (A))
⋂
vert Mns
qk (A) = Sm(F,X).
Доведення. З теореми 5 та умов даної теореми випливає, що ∀x ∈ R
n справедливе
твердження: x ∈ Sl(F,Mns
qk (A))
⋂
vert Mns
qk (A) ⇒ x ∈ Sl(F,X),
x ∈ P (F,Mns
qk (A))
⋂
vert Mns
qk (A) ⇒ x ∈ P (F,X),
x ∈ Sm(F,Mns
qk (A))
⋂
vert Mns
qk (A) ⇒ x ∈ Sm(F,X).
50 ISSN 1025-6415 Reports of the National Academy of Sciences of Ukraine, 2009, №6
Доведемо зворотнi iмплiкацiї. Нехай x ∈ Sl(F,X), звiдки, вiдповiдно до твердження 3,
випливає, що x ∈ vert Mns
qk (A). Припустимо, вiд супротивного, що x /∈ Sl(F,Mns
qk (A)). З огля-
ду на лiнiйнiсть функцiй fi(x), i ∈ Nl, векторного критерiю F (x) вiдповiдно до теореми 5 [3]
виконується умова (x + intK)
⋂
M(x) 6= ∅, тобто в конусi (x + int],K) лежать деякi точ-
ки границi многогранника Mns
qk (A), отже iснує його вершина, що належить цьому конусу.
Останнє в силу формули (7) означає, що x /∈ Sl(F,X) i приводить до протирiччя з умовою
теореми. Отже, Sl(F,Mns
qk (A))
⋂
vert Mns
qk (A) = Sl(F,X).
Подiбними мiркуваннями доводяться iншi твердження даної теореми.
Наслiдок 2. За умов теореми 6 ∀x ∈ R
n справедливi твердження:
x ∈ Sl(F,X) ⇔ x ∈ Sl(F,Mns
qk (A))
⋂
vert Mns
qk (A),
x ∈ P (F,X) ⇔ x ∈ P (F,Mns
qk (A))
⋂
vert Mns
qk (A),
x ∈ Sm(F,X) ⇔ x ∈ Sm(F,Mns
qk (A))
⋂
vert Mns
qk (A).
Якщо Mns
qk (A)
⋂
D 6= Mns
qk (A), то справедливi лише достатнi умови оптимальностi роз-
в’язкiв.
Теорема 7. P (F,Mns
qk (A))
⋂
D ⊂ P (F,X),
Sl(F,Mns
qk (A))
⋂
D ⊂ Sl(F,X), Sm(F,Mns
qk (A))
⋂
D ⊂ Sm(F,X).
4. Полiедральний пiдхiд до розв’язання векторних задач на комбiнаторнiй
множинi полiрозмiщень. Структурнi властивостi допустимої областi X та множин ефек-
тивних розв’язкiв, а також лiнiйнiсть функцiй векторного критерiю дозволяють звести
розв’язання задачi Z(F,X) до розв’язання задачi Z(F,G), визначеної на неперервнiй допу-
стимiй множинi G = Mns
qk (A)
⋂
D. Розвиваючи результати робiт [3–9, 14,15], в данiй робо-
тi пропонується i обгрунтовується пiдхiд до розв’язання задачi комбiнаторної оптимiзацiї
Z(F,X), який базується на її зведеннi до задачi, визначеної на опуклiй оболонцi множини
полiрозмiщень, застосуваннi методу головного критерiю для розглядуваного класу вектор-
них задач i враховує той факт, що число обмежень досить велике.
Твердження 4. Якщо для елементiв мультимножини A i коефiцiєнтiв cj , j ∈ Nn,
цiльової функцiї задачi extr
{
f(x) =
n
∑
j=1
cjxj | x ∈ vert Mns
qk (A)
}
виконуються вiдповiдно
умови a1 6 a2 6 . . . 6 an i ci1 6 ci2 6 · · · 6 cin , ij , j ∈ Nn, то максимум функцiї
f(x) на допустимiй множинi досягається в точцi x = (xi1 , . . . , xin) ∈ vertMns
qk (A), що
визначається як xij = aj∀ j ∈ Nn, а мiнiмум — вiдповiдно в точцi x = (xi1 , xi2 , . . . , xin),
де xij+1
= an−j ∀ j ∈ Nn−1
⋃
{0}.
Справедливiсть даного твердження очевидна, оскiльки найбiльше значення суми попар-
них добуткiв досягається при зiставленнi зростаючої послiдовностi ci iз зростаючою послi-
довнiстю xi, а найменше значення суми, вiдповiдно, досягається при зiставленнi зростаючої
послiдовностi ci iз спадаючою послiдовнiстю xi.
Пропонується такий пiдхiд розв’язання розглянутого класу векторних задач. Вхiдна
багатокритерiальна задача зводиться до задачi оптимiзацiї за одним критерiєм fr(x), r ∈ Nl,
що вибирається головним, при умовi, що значення всiх iнших критерiїв не менше деяких
встановлених величин (граничних значень) ti, i ∈ Nl \ {r}. Таким чином, маємо задачу
Z(fr,X(ti)) : max{fr(x) | fi(x) > ti, i ∈ Nl \ {r}, x ∈ X}.
Оптимальний розв’язок x0 цiєї задачi завжди є слабо ефективним, а якщо вiн єдиний
(з точнiстю до еквiвалентностi ∼ f ), то i ефективним. Якщо розв’язок x0 ефективний, то вiн
ISSN 1025-6415 Доповiдi Нацiональної академiї наук України, 2009, №6 51
є єдиним (з точнiстю до еквiвалентностi ∼ f ) розв’язком задачi Z(fr,X(ti)) при будь-якому
фiксованому r ∈ Nl i ti = fi(x
0), i ∈ Nl \ {r}. Вибiр одного з критерiїв як головного не
зменшує можливiсть вибору оптимального розв’язку. Для визначення порогових значень
ti, i ∈ Nl \ {r}, можна скористатися твердженням 4, що встановлює верхнi i нижнi границi
значень критерiїв fi(x), i ∈ Nl, на множинi полiрозмiщень. Пропонується два пiдходи до
розв’язання вхiдної задачi Z(F,X). Перший полягає в присвоєннi порогам ti, i ∈ Nl \ {r},
максимально можливих значень критерiїв fi(x), i ∈ Nl, на множинi полiрозмiщень з на-
ступним розширенням допустимої областi задачi Z(fr,X), якщо вхiдна задача виявиться
недопустимою, а у випадку її допустимостi — знаходження ефективного або слабо ефектив-
ного розв’язку. Другий пiдхiд допускає пошук оптимального розв’язку задачi Z(fr,X) при
визначеннi мiнiмальних значень критерiїв fi(x), i ∈ Nl, з наступним звуженням допустимої
областi за допомогою вибору наступних значень порогiв ti, i ∈ Nl \ {r}, упорядкованих за
зростанням, за мiнiмальними значеннями критерiїв. Процедура присвоєння серiї граничних
величин ti обмежень i в першому i в другому пiдходi дуже проста, оскiльки з використанням
твердження 4 вона зводиться пiсля упорядкування коефiцiєнтiв критерiїв до обчислення
скалярного добутку двох векторiв, тобто до визначення значень лiнiйних критерiїв. При
цьому, з огляду на структурнi особливостi множини полiрозмiщень, величини ti можна об-
числювати бiльш ефективно, використовуючи перестановки елементiв кожної i-ї, i ∈ Ns,
пiдмножини мультимножини A.
Очевидно, що запропонований метод у результатi розв’язання скiнченного числа пiдза-
дач вигляду Z(fr,X) приводить до ефективного розв’язку задачi Z(F,X), або до встанов-
лення її нерозв’язностi.
Таким чином, у данiй роботi на основi проведеного аналiзу векторної комбiнаторної
задачi, що базується на використаннi iнформацiї про опуклу оболонку допустимої облас-
тi, вивченнi властивостей многогранникiв, вершини яких визначають пiдмножину зада-
ної комбiнаторної множини полiрозмiщень, розроблено i обгрунтовано метод розв’язання
складних багатокритерiальних задач на комбiнаторнiй множинi полiрозмiщень. Застосу-
вання структурних властивостей комбiнаторних многогранникiв дає можливiсть розробля-
ти ефективнi алгоритми розв’язування векторних оптимiзацiйних задач.
1. Сергиенко И.В. Математические модели и методы решения задач дискретной оптимизации. – Киев:
Наук. думка, 1988. – 472 с.
2. Сергиенко И.В., Каспшицкая М.Ф. Модели и методы решения на ЭВМ комбинаторных задач опти-
мизации. – Киев: Наук. думка, 1981. – 287 с.
3. Лебєдєва Т. Т., Семенова Н.В., Сергiєнко Т. I. Умови оптимальностi та розв’язуваностi в задачах
лiнiйної векторної оптимiзацiї з опуклою допустимою множиною // Доп НАН України. – 2003. –
№ 10. – С. 80–85.
4. Семенова Н.В., Колечкина Л.Н., Нагорная А.Н. Подход к решению векторных задач дискретной
оптимизации на комбинаторном множестве перестановок // Кибернетика и систем. анализ. – 2008. –
№ 3. – С. 158–172.
5. Semenova N.V., Kolechkina L.M., Nagirna A.M. Vector combinatorial problems in a space of combinations
with linear fractional functions of criteria // Intern. J. Inform. Theor. and Appl. – 2008. – 15. – P. 240–245.
6. Семенова Н.В., Колечкина Л.Н., Нагорная А.Н. Решение и исследование векторных задач комбина-
торной оптимизации на множестве полиперестановок // Пробл. управления и информатики. – 2008. –
№ 6. – С. 26–41.
7. Семенова Н. Векторные задачи на комбинаторном множестве полиразмещений: условия оптимально-
сти и подход к решению // Intern. Book Series “Information science and computing”, № 7. – Supplement to
Intern. J. Inform. Theor. and Knowledge. – 2008. – 2. Institute of Inform. Theor. and Appl. FOI ITHEA. –
Sofia, 2008. – P. 187–195.
52 ISSN 1025-6415 Reports of the National Academy of Sciences of Ukraine, 2009, №6
8. Колечкина Л. Многокритериальные задачи на комбинаторном множестве полиразмещений: структур-
ные свойства решений // Ibid. – P. 180–186.
9. Подиновский В.В., Ногин В.Д. Парето-оптимальные решения многокритериальных задач. – Москва:
Наука, 1982. – 256 с.
10. Стоян Ю.Г., Ємець О.О., Ємець Є.М. Оптимiзацiя на полiрозмiщеннях: теорiя та методи. – Пол-
тава: РВЦ ПУСКУ, 2005. – 104 с.
11. Ємець О.О., Колєчкiна Л.М. Задачi комбiнаторної оптимiзацiї з дробово-лiнiйними цiльовими функ-
цiями. – Київ: Наук. думка, 2005. – 118 с.
12. Емеличев В.А., Ковалев М.М., Кравцов М.К. Многогранники, графы, оптимизация. – Москва: Нау-
ка, 1981. – 344 с.
13. Aardal K., Hoesel S. Polyhedral techniques in combinatorial optimization I: Theory // Statist. Neerlandi-
ca. – 1996. – 15. – P. 3–26.
14. Семенова Н.В. Условия оптимальности в векторных задачах комбинаторной оптимизации // Теорiя
оптим. рiшень. – 2008. – № 7. – С. 153–160.
15. Семенова Н.В., Колєчкiна Л.М., Нагiрна А.М. Розв’язання багатокритерiальних задач комбiнатор-
ної оптимiзацiї на множинi полiперестановок // Доп. НАН України. – 2009. – № 2. – С. 41–48.
Надiйшло до редакцiї 30.01.2009Iнститут кiбернетики iм. В.М. Глушкова
НАН України, Київ
N.V. Semenova, L.M. Kolechkina
A polyhedral approach to the solution of a class of vector problems of
combinatorial optimization
Multicriterial problems of discrete optimization on a feasible combinatorial set of polyarrangements
are considered. Structural properties of the feasible region and different types of efficient solutions
are explored. On the basis of development of the ideas of Euclidean’s combinatorial optimization and
the method of main criterion, a polyhedral approach to the solution of multicriterial combinatorial
problems on the set of polyarrangements is developed and grounded.
ISSN 1025-6415 Доповiдi Нацiональної академiї наук України, 2009, №6 53
|
| id | nasplib_isofts_kiev_ua-123456789-8642 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1025-6415 |
| language | Ukrainian |
| last_indexed | 2025-12-07T13:20:58Z |
| publishDate | 2009 |
| publisher | Видавничий дім "Академперіодика" НАН України |
| record_format | dspace |
| spelling | Семенова, Н.В. Колєчкіна, Л.М. 2010-06-14T08:47:24Z 2010-06-14T08:47:24Z 2009 Поліедральний підхід до розв'язання одного класу векторних задач комбінаторної оптимізації / Н.В. Семенова, Л.М. Колєчкiна // Доп. НАН України. — 2009. — № 6. — С. 46-53. — Бібліогр.: 15 назв. — укр. 1025-6415 https://nasplib.isofts.kiev.ua/handle/123456789/8642 519.8 Розглядаються багатокритерiальнi задачi дискретної оптимiзацiї на допустимiй комбiнаторнiй множинi полiрозмiщень. Дослiджуються структурнi властивостi допустимої областi i рiзних видiв ефективних розв’язкiв. На основi розвитку iдей евклiдової комбiнаторної оптимiзацiї i методу головного критерiю розроблений i обгрунтований полiедральний пiдхiд до розв’язання зазначеного класу задач. Multicriterial problems of discrete optimization on a feasible combinatorial set of polyarrangements are considered. Structural properties of the feasible region and different types of efficient solutions are explored. On the basis of development of the ideas of Euclidean’s combinatorial optimization and the method of main criterion, a polyhedral approach to the solution of multicriterial combinatorial problems on the set of polyarrangements is developed and grounded. uk Видавничий дім "Академперіодика" НАН України Інформатика та кібернетика Поліедральний підхід до розв'язання одного класу векторних задач комбінаторної оптимізації A polyhedral approach to the solution of a class of vector problems of combinatorial optimization Article published earlier |
| spellingShingle | Поліедральний підхід до розв'язання одного класу векторних задач комбінаторної оптимізації Семенова, Н.В. Колєчкіна, Л.М. Інформатика та кібернетика |
| title | Поліедральний підхід до розв'язання одного класу векторних задач комбінаторної оптимізації |
| title_alt | A polyhedral approach to the solution of a class of vector problems of combinatorial optimization |
| title_full | Поліедральний підхід до розв'язання одного класу векторних задач комбінаторної оптимізації |
| title_fullStr | Поліедральний підхід до розв'язання одного класу векторних задач комбінаторної оптимізації |
| title_full_unstemmed | Поліедральний підхід до розв'язання одного класу векторних задач комбінаторної оптимізації |
| title_short | Поліедральний підхід до розв'язання одного класу векторних задач комбінаторної оптимізації |
| title_sort | поліедральний підхід до розв'язання одного класу векторних задач комбінаторної оптимізації |
| topic | Інформатика та кібернетика |
| topic_facet | Інформатика та кібернетика |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/8642 |
| work_keys_str_mv | AT semenovanv políedralʹniipídhíddorozvâzannâodnogoklasuvektornihzadačkombínatornoíoptimízacíí AT kolêčkínalm políedralʹniipídhíddorozvâzannâodnogoklasuvektornihzadačkombínatornoíoptimízacíí AT semenovanv apolyhedralapproachtothesolutionofaclassofvectorproblemsofcombinatorialoptimization AT kolêčkínalm apolyhedralapproachtothesolutionofaclassofvectorproblemsofcombinatorialoptimization |