Розв'язання багатокритеріальних задач комбінаторної оптимізації на множині поліперестановок

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

Full description

Saved in:

Bibliographic Details
Date:	2009
Main Authors:	Семенова, Н.В., Колєчкіна, Л.М., Нагірна, А.М.
Format:	Article
Language:	Ukrainian
Published:	Видавничий дім "Академперіодика" НАН України 2009
Subjects:	Інформатика та кібернетика
Online Access:	https://nasplib.isofts.kiev.ua/handle/123456789/7905
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:	Розв'язання багатокритеріальних задач комбінаторної оптимізації на множині поліперестановок / Н.В. Семенова, Л.М. Колєчкiна, А.М. Нагiрна // Доп. НАН України. — 2009. — № 2. — С. 41-48. — Бібліогр.: 15 назв. — укр.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	nasplib_isofts_kiev_ua-123456789-7905
record_format	dspace
spelling	Семенова, Н.В. Колєчкіна, Л.М. Нагірна, А.М. 2010-04-22T13:27:24Z 2010-04-22T13:27:24Z 2009 Розв'язання багатокритеріальних задач комбінаторної оптимізації на множині поліперестановок / Н.В. Семенова, Л.М. Колєчкiна, А.М. Нагiрна // Доп. НАН України. — 2009. — № 2. — С. 41-48. — Бібліогр.: 15 назв. — укр. 1025-6415 https://nasplib.isofts.kiev.ua/handle/123456789/7905 519.8 Дослiджено складнi багатокритерiальнi задачi на комбiнаторнiй множинi полiперестановок. Розглянуто деякi властивостi допустимої областi комбiнаторної багатокритерiальної задачi. Побудовано i обгрунтовано метод розв’язання сформульованих задач. Запропонований пiдхiд може застосовуватися для розв’язування комбiнаторних багатокритерiальних задач на полiперестановках. Complex multicriterial problems on a combinatorial set of polypermutations are studied, and a method to solve such problems is constructed and substantiated. Some properties of the feasible region of a combinatorial multicriterial problem are considered. uk Видавничий дім "Академперіодика" НАН України Інформатика та кібернетика Розв'язання багатокритеріальних задач комбінаторної оптимізації на множині поліперестановок The solution of multicriterial problems of combinatorial optimization on a set of polipermutations 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	2009
language	Ukrainian
publisher	Видавничий дім "Академперіодика" НАН України
format	Article
title_alt	The solution of multicriterial problems of combinatorial optimization on a set of polipermutations
description	Дослiджено складнi багатокритерiальнi задачi на комбiнаторнiй множинi полiперестановок. Розглянуто деякi властивостi допустимої областi комбiнаторної багатокритерiальної задачi. Побудовано i обгрунтовано метод розв’язання сформульованих задач. Запропонований пiдхiд може застосовуватися для розв’язування комбiнаторних багатокритерiальних задач на полiперестановках. Complex multicriterial problems on a combinatorial set of polypermutations are studied, and a method to solve such problems is constructed and substantiated. Some properties of the feasible region of a combinatorial multicriterial problem are considered.
issn	1025-6415
url	https://nasplib.isofts.kiev.ua/handle/123456789/7905
citation_txt	Розв'язання багатокритеріальних задач комбінаторної оптимізації на множині поліперестановок / Н.В. Семенова, Л.М. Колєчкiна, А.М. Нагiрна // Доп. НАН України. — 2009. — № 2. — С. 41-48. — Бібліогр.: 15 назв. — укр.
work_keys_str_mv	AT semenovanv rozvâzannâbagatokriteríalʹnihzadačkombínatornoíoptimízacíínamnožinípolíperestanovok AT kolêčkínalm rozvâzannâbagatokriteríalʹnihzadačkombínatornoíoptimízacíínamnožinípolíperestanovok AT nagírnaam rozvâzannâbagatokriteríalʹnihzadačkombínatornoíoptimízacíínamnožinípolíperestanovok AT semenovanv thesolutionofmulticriterialproblemsofcombinatorialoptimizationonasetofpolipermutations AT kolêčkínalm thesolutionofmulticriterialproblemsofcombinatorialoptimizationonasetofpolipermutations AT nagírnaam thesolutionofmulticriterialproblemsofcombinatorialoptimizationonasetofpolipermutations
first_indexed	2025-11-26T12:47:29Z
last_indexed	2025-11-26T12:47:29Z
_version_	1850621931063083008
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 результати [1–15]. Як вiдомо, бiльшiсть комбiнаторних оптимiзацiйних задач можуть бути зведенi до задач цiлочислового програмування, але це не завжди виправдано, оскiльки при цьому втрача- ється можливiсть врахування комбiнаторних властивостей задач [2]. Систематичне вивчення властивостей евклiдових комбiнаторних множин та їх дослiд- ження описанi в багатьох роботах. Поряд з добре вiдомими евклiдовими комбiнаторни- ми множинами перестановок, розмiщень, сполучень, розбиттiв видiляються бiльш склад- нi структури — полiкомбiнаторнi множини [11, 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зних комбiнаторних множинах, а також розвивати новi оригiнальнi методи їх розв’язання, використовуючи властивостi комбiнаторних множин i їх опуклих оболонок. Дана робота продовжує дослiдження багатокритерiальних задач на комбiнаторних мно- жинах перестановок, сполучень, вiдображенi в роботах [8, 9]. На п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в до їх розв’язання. ISSN 1025-6415 Доповiдi Нацiональної академiї наук України, 2009, №2 41 1. Основнi поняття та означення. Розглянемо основнi поняття та означення, необ- хiднi для постановки задачi та викладу основних результатiв даної роботи [11, 13]. Мультимножина A = {a1, a2, . . . , aq} визначається основою S(A) = {e1, e2, . . . , ek} i крат- нiстю її елементiв k(ej) = rj , j ∈ Nk = {1, 2, . . . , k}, r1 + r2 + · · · + rk = q. Означення 1. Впорядкованою n-вибiркою з мультимножини A називається набiр a = = (ai1 , ai2 , . . . , ain), де aij ∈ A ∀ ij ∈ Nn, ∀ j ∈ Nn, is 6= it, якщо s 6= t ∀ s ∈ Nn, ∀ t ∈ Nn. Означення 2. Множина E(A), елементами якої є n-вибiрки з мультимножини A, на- зивається евклiдовою комбiнаторною множиною, якщо для довiльних її елементiв a′ = = (a′1, a ′ 2, . . . , a ′ n), a′′ = (a′′1 , a ′′ 2, . . . , a ′′ n) виконуються умови (a′ 6= a′′) ⇔ (∃ j : a′j 6= a′′j ), тобто два елементи множини E(A) вiдмiннi один вiд одного, якщо вони, незалежно вiд iнших вiдмiнностей, розрiзняються порядком розмiщення елементiв, що їх утворюють. Наведемо множину Nn у виглядi упорядкованого розбиття на s непорожнiх пiдмножин N1, . . . , Ns, якi не перетинаються, а отже для яких виконуються умови: Ni ⋂ Nj = ∅, Ni 6= ∅, Nj 6= ∅, ∀ i, j ∈ Ns. Позначимо H — множину всiх елементiв вигляду: π = (π(1), . . . , π(n)) = = (π1, . . . , πs), де πi — довiльна перестановка елементiв множини Ni ∀ i ∈ Ns. Нехай пiдмультимножина ANi мультимножини A складається з тих елементiв A, номери яких належать множинi Ni: ANi = {aNi 1 , . . . , aNi ki }, \|Ni\| = ni. Означення 3. Множину P s nk(A,H) = {(aπ(1), . . . , aπ(n)) \| aπ(i) ∈ A ∀ i ∈ Nn, ∀π ∈ H} називають загальною множиною полiперестановок. Не втрачаючи загальностi, упорядкуємо елементи мультимножини A за неспаданням: a1 6 a2 6 · · · 6 an, що буде справедливим i для пiдмультимножин з A. 2. Властивост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дно з [11, 13], елементи множини полiперестановок як точки арифметичного евклiдового простору R n. Нехай вектор a є елементом евклiдової комбiнаторної множини E(A). Вiдображення ϕ : E(A) → Eϕ(A) ⊂ R n називається зану- ренням множини E(A) в арифметичний евклiдовий простiр, якщо ϕ задає взаємно одно- значну вiдповiднiсть Eϕ(A) ⊂ R n за правилом: для a = (ai1 , . . . , ain) ∈ E(A), x = ϕ(a), x = (x1, . . . , xn) ∈ Eϕ(A), xj = aij ∀j ∈ Nn. Тодi образ множини полiперестановок в арифметичному евклiдовому просторi позначають Es nk(A,H). У роботах [11, 13] показа- но, що опуклою оболонкою множини полiперестановок є полiпереставний многогранник Πs nk(A,H) = conv P s nk(A,H), множиною вершин якого є множина P s nk(A,H) полiперестано- вок: vert Πs nk(A,H) = P s nk(A,H). Теорема 1 [13]. Множина Πs nk(A,H) визначається сукупнiстю всiх розв’язкiв системи ∑ j∈N ′ i xj = ki ∑ j=1 aNi j , ∀ i ∈ Ns, (1) ∑ j∈ωi xj > \|ωi\| ∑ j=1 aNi j , ∀ωi ⊂ N ′ i , ∀ i ∈ Ns, (2) де 42 ISSN 1025-6415 Reports of the National Academy of Sciences of Ukraine, 2009, №2 aNi j ∈ ANi , N ′ i = {( i−1 ∑ j=1 kj ) + 1, ( i−1 ∑ j=1 kj ) + 2, . . . , ( i ∑ j=1 kj )} ∀ j ∈ Ns. Многогранник Πs nk(A,H) називатимемо загальним многогранником евклiдової множини полiперестановок. Розглянемо деякi його властивостi та його зв’язок з загальною множиною полiперестановок. Означення 4. Пiд добутком многогранникiв M1, . . . ,Ms розумiють множину s ⊗ i=1 Mi = = {x ∈ R d1+···+ds \| x = (x1, . . . , xs), xi ∈ Mi ∀ i ∈ Ns}, де Mi є di-вимiрним многогранником ∀ i ∈ Ns. Скористаємося такою лемою [14]. Лема 1. 1. Добутком многогранникiв є многогранник. 2. dim ( s ⊗ i=1 Mi ) = s ∑ i=1 dim Mi, де dimA — вимiрнiсть множини A. 3. k-Вимiрнi гранi многогранника s ⊗ i=1 Mi утворюють множину з елементами вигляду s ⊗ i=1 Fi, де F i — ki-вимiрна грань многогранника Mi та k1 + · · · + ks = k. Справедливi такi теореми [13]. Теорема 2. Πs nk(A,H) = s ⊗ i=1 Πniki (ANi). Теорема 3. Множина P s nk(A,H) збiгається з множиною вершин многогранника Πs nk(A,H). Теорема 4. Вершина a(π)∈vert Πs nk(A,H) є сумiжною до вершини a(σ)∈vert Πs nk(A,H) тодi i тiльки тодi, коли a(σ) утворюється з a(π) переставленням двох нерiвних одна однiй компонент — aNi i та aNi i+1, j ∈ Nni−1, i ∈ Ns. 3. Постановка задачi. Розглядаються багатокритерiальнi комбiнаторнi задачi вигляду Z(Φ, P s nk(A,H)) : max{Φ(a)\|a ∈ P s nk(A,H)}, що полягають у максимiзацiї векторного критерiю Φ(a) на евклiдовiй комбiнаторнiй мно- жинi полiперестановок P s nk(A,H), де Φ(a) = (Φ1(a),Φ2(a), . . . ,Φl(a)), Φi : R n → R 1, i ∈ Nl. При вiдображеннi множини полiперестановок P s nk(A,H) в евклiдiв простiр R n сфор- мулюємо задачу Z(F,X) максимiзацiї деякого векторного критерiю F (x) на множинi X, причому кожнiй точцi a ∈ P s nk(A,H) буде вiдповiдати точка x ∈ X, така, що F (x) = Φ(a). Z(F,X) : max{F (x) \| x ∈ X}, де F (x) = (f1(x), f2(x), . . . , fl(x)) вiдповiдає функцiоналу Φi(a), fi : R n → R 1, i ∈ Nl, X — непорожня множина у R n, що визначається таким чином: X = vert Πs nk(A,H), Πs nk(A,H) = = conv P s nk(A,H). Пiд вiдповiднiстю векторної функцiї F вектору функцiоналiв Φ будемо розумiти спiввiдношення Φ(a) = F (ϕ(a)) ∀ a ∈ P s nk(A,H). Задача Z(F,X) може мiстити також додатковi лiнiйнi обмеження, що утворюють опуклу многогранну множину D ⊂ R n вигляду D = {x ∈ R n \| Bx 6 d}, де d ∈ R m, B ∈ R m×n. Отже, допустима множина має вигляд: X = vert Πs nk(A,H) ⋂ D. Розроблено багато рiзних принципiв прийняття рiшень в таких задачах. Нас будуть цiкавити деякi з найбiльш традицiйних, пов’язанi з видiленням iз усiєї множини Y = {y = = F (x) \| x ∈ X} множини непокращуваних або оптимальних за Парето, оптимальних ISSN 1025-6415 Доповiдi Нацiональної академiї наук України, 2009, №2 43 за Слейтером, оптимальних за Смейлом векторiв. Таким чином, пiд розв’язанням задачi Z(F,X) будемо розумiти знаходження елементiв однiєї з таких множин: P (F,X) — множи- ни Парето-оптимальних (ефективних розв’язкiв), Sl(F,X) — оптимальних за Слейтером (слабо ефективних) розв’язкiв, Sm(F,X) — оптимальних за Смейлом (строго ефективних) розв’язкiв. Згiдно з [4, 6, 7], для кожного 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) непорожня i зовнi стiйка [15]: ∀ y ∈ X ∃x ∈ P (F,X) : F (x) > F (y). У випадку нескiнченностi мультимножини A питання про iснування елементiв множини P (F,X) вимагає окремого дослiдження. 4. Умови оптимальностi i властивостi множин ефективних розв’язкiв. Теорема 5. Елементи множин Sm(F,X)-строго ефективних, P (F,X)-Парето-опти- мальних, Sl(F,X)-слабо ефективних розв’язкiв багатокритерiальної комбiнаторної задачi на полiперестановках вигляду Z(F,X) знаходяться у вершинах полiпереставного много- гранника Πs nk(A,H). Доведення. Враховуючи спiввiдношення (6) мiж введеними множинами ефектив- них розв’язкiв, а також, згiдно з теоремою 3 з [13], той факт, що множина допустимих розв’язкiв X є пiдмножиною множини вершин загального полiпереставного многогранника Πs nk(A,H), тобто P s nk(A,H) = vert Πs nk(A,H), приходимо до справедливостi ланцюга вклю- чень: Sm(F,X) ⊂ P (F,X) ⊂ Sl(F,X) ⊂ vert Πs nk(A,H). Теорему доведено. Нехай функцiї fi(x), i ∈ Nl, векторного критерiю F (x) є лiнiйними, тобто fi(x) = 〈ci, x〉, i ∈ Nl. Важливi властивостi допустимої областi X i множин рiзних видiв ефективних розв’язкiв, зазначенi в теоремi 5, а також лiнiйнiсть функцiй векторного критерiю дозво- ляють звести розв’язання задачi Z(F,X) до розв’язання задачi Z(F,G), яка визначена на неперервнiй допустимiй множинi G = Πs nk(A,H) ⋂ D. Нехай C ∈ R n×l — матриця, cj — її вектор-рядок, i ∈ Nl. Многогранник Πs nk(A,H) наведемо у виглядi Πs nk(A,H) = {x ∈ R n \| 〈πi, x〉 6 γi, i ∈ Np}, звiвши всi нерiвностi, що його описують, до одного вигляду (6). Аналiз задачi Z(F,X) проводитимемо з урахуванням властивостей конуса K = {x ∈ R n \| Cx > 0} перспективних напрямкiв [4] задачi Z(F,X) та опуклих замкнутих конусiв 0+Π(y) = {x ∈ R n \| πix 6 0, i ∈ N(y)}, де N(y) = {i ∈ ∈ Nq \| πiy = γi}, що можуть бути побудованi для всiх точок y ∈ vert Πs nk(A,H). Очевидно, що N(y) 6= ∅, X ⊆ y + 0+Π(y). Позначимо K0 = {x ∈ R n \| Cx = 0} — ядро вiдображення C : R n → R l, int K = {x ∈ R n \| Cx > 0} — внутрiшнiсть конуса K. З формул (3)–(5) випливає, що ∀x ∈ X справедливi твердження x ∈ Sl(C,X) ⇔ (x + intK) ⋂ X = ∅, (7) x ∈ P (C,X) ⇔ x + (K \ K0) ⋂ X = ∅, (8) x ∈ Sm(C,X) ⇔ (x + K) ⋂ X \ {x} = ∅. (9) Справедливi такi теореми. 44 ISSN 1025-6415 Reports of the National Academy of Sciences of Ukraine, 2009, №2 Теорема 6. P (F,G) ⋂ vert Πs nk(A,H) ⊂ P (F,X), Sl(F,G) ⋂ vert Πs nk(A,H) ⊂ Sl(F,X), Sm(F,G) ⋂ vert Πs nk(A,H) ⊂ Sm(F,X). Доведення. Оскiльки vert Πs nk(A,H) ⋂ D ⊂ G, то P (F,G) ⋂ vert Πs nk(A,H) ⋂ D ⊂ ⊂ P (F,G ⋂ vertΠs nk(A,H) ⋂ D) = P (F,X). Спiввiдношення Sl(F,X) = Sl(F, vert Πs nk(A,H) ⋂ D) ⊃ Sl(F,G) ⋂ vert Πs nk(A,H) ⋂ D, Sm(F,X) = Sm(F,D ⋂ vert Πs nk(A,H)) ⊃ Sm(F,G) ⋂ vert Πs nk(A,H) доводяться ана- логiчно. Теорема 7. Якщо допустима множина X задачi Z(F,X) не мiстить обмежень, що описують опуклу многогранну множину D, або Πs nk(A,H) ⊆ D, тобто X = vertΠs nk(A,H), то ∀x ∈ R n справедливi твердження: x ∈ Sl(F,X) ⇔ x ∈ Sl(F,Πs nk(A,H)) ⋂ vert Πs nk(A,H), x ∈ P (F,X) ⇔ x ∈ P (F,Πs nk(A,H)) ⋂ vert Πs nk(A,H), x ∈ Sm(F,X) ⇔ x ∈ Sm(F,Πs nk(A,H)) ⋂ vert Πs nk(A,H). Доведення. З теореми 6, з урахуванням умови теореми 7, випливає, що ∀x ∈ R n спра- ведливi висловлення: x ∈ Sl(F,Πs nk(A,H)) ⋂ vert Πs nk(A,H) ⇒ x ∈ Sl(F,X), x ∈ P (F,Πs nk(A,H)) ⋂ vert Πs nk(A,H) ⇒ x ∈ P (F,X), x ∈ Sm(F,Πs nk(A,H)) ⋂ vert Πs nk(A,H) ⇒ x ∈ Sm(F,X). Доведемо зворотнi iмплiкацiї. Нехай x ∈ Sl(F,X), звiдки, за теоремою 5, випливає, що x ∈ vert Πs nk(A,H). Припустимо, вiд супротивного, що x /∈ Sl(F,Πs nk(A,H)). З огляду на лiнiйнiсть функцiй fi(x), i ∈ Nl, векторного критерiю F (x) за теоремою 1 iз [6] виконує- ться умова int K ⋂ (Π(x) − x) 6= ∅, тобто в конусi (x + int K) лежать деякi точки границi многогранника Πs nk(A,H), отже, iснує точка x1 ∈ vert Πs nk(A,H), що належить цьому ко- нусу. Останнє, в силу формули (7), означає, що x /∈ Sl(F,X) i приводить до протирiччя з умовою теореми. Iншi твердження даної теореми доводяться аналогiчно цьому. Доведе- ння завершено. Наслiдок. За умов теореми 7 справедливi рiвностi P (F,Πs nk(A,H)) ⋂ vert Πs nk(A,H) = P (F,X), Sl(F,Πs nk(A,H)) ⋂ vert Πs nk(A,H) = Sl(F,X), Sm(F,Πs nk(A,H)) ⋂ vert Πs nk(A,H) = Sm(F,X). Якщо в задачi Z(F,X) допустима область X = vert Πs nk(A,H), то для будь-якої точки x ∈ vert Πs nk(A,H) задачi P (F,X) справедливi необхiднi i достатнi умови оптимальностi всiх вказаних вище видiв ефективних розв’язкiв, отриманi в [6]. Якщо допустима область X задачi Z(F,X) мiстить додатковi обмеження, що описують опуклий многогранник D, тобто X = vert Πs nk(A,H) ⋂ D i Πs nk(A,H) ⋂ D 6= Πs nk(A,H), то справедливi лише достатнi умови оптимальностi. ISSN 1025-6415 Доповiдi Нацiональної академiї наук України, 2009, №2 45 Теорема 8. ∀x ∈ vert Πs nk(A,H): x ∈ P (F,Πs nk(A,H)) ⋂ D ⇒ x ∈ P (F,X), x ∈ Sl(F,Πs nk(A,H)) ⋂ D ⇒ x ∈ Sl(F,X), x ∈ Sm(F,Πs nk(A,H)) ⋂ D ⇒ x ∈ Sm(F,X). Доведення. Оскiльки G = Πs nk(A,H) ⋂ D, то справедливi iмплiкацiї ∀x ∈ vert Πs nk(A,H) : x ∈ P (F,Πs nk(A,H)) ⋂ D ⇒ ⇒ x ∈ P (F,Πs nk(A,H) ⋂ D) = P (F,G) ⇒ x ∈ P (F,X), x ∈ Sl(F,Πs nk(A,H)) ⋂ D ⇒ x ∈ Sl(F,X), x ∈ Sm(F,Πs nk(A,H)) ⋂ D ⇒ x ∈ Sm(F,X). Таким чином, теореми 5–8 встановлюють взаємозв’язок мiж задачею Z(F,X) i задачею Z(F,G), що визначена на неперервн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 умови. Якщо задача Z(F,X) не мiстить лiнiйних обмежень, що утворюють опуклу многогран- ну множину D ⊂ R n, або Πs nk(A,H) ⊆ D, тобто X = vert Πs nk(A,H), то при викори- станнi необхiдних i достатнiх умов оптимальностi (теорема 7) процес її розв’язання зво- диться до пошуку ефективних розв’язкiв задачi Z(F,G) на неперервнiй допустимiй множи- нi G = Πs nk(A,H) з наступним вибором з них лише тих, якi є вершинами многогранника Πs nk(A,H). Аналiзуючи теореми 6 i 8, приходимо до спiввiдношень, що iснують мiж задача- ми Z(F,X) i Z(F,G): якщо x ∈ R(F,G) ⋂ vert Πs nk(A,H), то x ∈ R(F,X), якщо ж x /∈ R(F,G) ⋂ \| Πs nk(A,H), то з цього не випливає, що x /∈ R(F,X), де R(F,X) визначає множину P (F,X), Sm(F,X) або Sl(F,X). 5. Загальний пiдхiд до розв’язування векторних задач на комбiнаторнiй мно- жинi полiперестановок. Якщо задача Z(F,X) мiстить додатковi лiнiйнi обмеження, то пропонується такий пiдхiд до її розв’язання: 1) знаходимо ефективнi розв’язки задачi Z(F,Πs nk(A,H)); 2) перевiряємо їх на належнiсть множинi D. Якщо x ∈ P (F,Πs nk(A,H)) ⋂ D, то x ∈ ∈ P (F,X); 3) розглянемо допустимi розв’язки x ∈ X задачi Z(F,X), якi є неефективними в зада- чi Z(F,Πs nk(A,H)), тобто x ∈ X \ P (F,Πs nk(A,H)) ⋂ D, i перевiряємо їх на ефективнiсть. Для цього можна скористатися необхiдними i достатнiми умовами, сформульованими в [15, с. 187, 188]. 46 ISSN 1025-6415 Reports of the National Academy of Sciences of Ukraine, 2009, №2 Твердження 1. Допустимий розв’язок x0 ефективний тодi i тiльки тодi, коли вiн є оптимальним розв’язком задачi Z1(F,X) : max { m ∑ i=1 fi(x) \| x ∈ X, fi(x) > fi(x 0), i ∈ Nm } . Якщо розв’язок x0 неефективний, то в результатi розв’язання цiєї задачi знаходимо ефек- тивний розв’язок x∗, тобто такий, що F (x∗) > F (x0). Продовжуючи дослiдження i розвиваючи результати робiт [1, 5, 6, 8–13], автори роз- робили пiдхiд до розв’язання задач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й област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. Сергиенко И.В. Математические модели и методы решения задач дискретной оптимизации. – Киев: Наук. думка, 1988. – 472 с. 2. Сергиенко И.В., Каспшицкая М.Ф. Модели и методы решения на ЭВМ комбинаторных задач опти- мизации. – Киев: Наук. думка, 1981. – 287 с. 3. Сергиенко И.В., Шило В.П. Задачи дискретной оптимизации: проблемы, методы решения, исследо- вания. – Киев: Наук. думка, 2003. – 264 с. 4. Сергиенко И.В., Козерацкая Л.Н., Лебедева Т. Т. Исследование устойчивости и параметрический анализ дискретных оптимизационных задач. – Киев: Наук. думка, 1995. – 170 с. 5. Сергиенко И.В., Лебедева Т. Т., Семенова Н.В. О существовании решений в задачах векторной опти- мизации // Кибернетика и системный анализ. – 2000. – № 6. – С. 39–46. 6. Лебєдєва Т. Т., Семенова Н.В., Сергiєнко Т. I. Умови оптимальностi та розв’язуваностi в задачах лiнiйної векторної оптимiзацiї з опуклою допустимою множиною // Доп. НАН України. – 2003. – № 10. – С. 80–85. 7. Лебедева Т.Т., Семенова Н.В., Сергиенко Т.И. Устойчивость векторных задач целочисленной опти- мизации: взаимосвязь с устойчивостью множеств оптимальных и неоптимальных решений // Кибер- нетика и системный анализ. – 2005. – № 4. – С. 90–100. 8. Семенова Н.В., Колечкина Л.Н., Нагорная А.Н. Подход к решению векторных задач дискретной оптимизации на комбинаторном множестве перестановок // Там же. – 2008. – № 3. – С. 158–172. 9. 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. Information Theories and Applications. – 2008. – 15. – P. 240–245. ISSN 1025-6415 Доповiдi Нацiональної академiї наук України, 2009, №2 47 10. Стоян Ю.Г., Яковлев С. В. Математические модели и оптимизационные методы геометрического проектирования. – Киев: Наук. думка, 1986. – 265 с. 11. Стоян Ю.Г., Ємець О.О. Теорiя i методи евклiдової комбiнаторної оптимiзацiї. – Київ: Iн-т систем. дослiджень освiти, 1993. – 188 с. 12. Ємець О.О., Колєчкiна Л.М. Задачi комбiнаторної оптимiзацiї з дробово-лiнiйними цiльовими функ- цiями. – Київ: Наук. думка, 2005. – 118 с. 13. Ємець О.О., Роскладка О.В. Задачi оптимiзацiї на полiкомбiнаторних множинах: властивостi та розв’язання. – Полтава: РВЦ ПУСКУ, 2006. – 130 с. 14. Емеличев В.А., Ковалев М.М., Кравцов М.К. Многогранники, графы, оптимизация. – Москва: На- ука, 1981. – 344 с. 15. Подиновский В.В., Ногин В.Д. Парето-оптимальные решения многокритериальных задач. – Москва: Наука, 1982. – 256 с. Надiйшло до редакцiї 09.06.2008Iнститут кiбернетики iм. В.М. Глушкова НАН України, Київ N.V. Semenova, L.M. Kolechkina, A. M. Nagirna The solution of multicriterial problems of combinatorial optimization on a set of polipermutations Complex multicriterial problems on a combinatorial set of polypermutations are studied, and a method to solve such problems is constructed and substantiated. Some properties of the feasible region of a combinatorial multicriterial problem are considered. 48 ISSN 1025-6415 Reports of the National Academy of Sciences of Ukraine, 2009, №2

Розв'язання багатокритеріальних задач комбінаторної оптимізації на множині поліперестановок

Institution

Similar Items