Л Колєчкіна - Багатокритеріальні комбінаторні задачі на поліперестановках та методи їх розв'язування - страница 1

Страницы:
1  2  3 

ВІСНИК ЛЬВІВ. УН-ТУ Серія прикл. матем. інформ. 2010. Вип. 16. C. 28-39

VISNYK LVIVUNIV. Ser. Appl. Math. Inform. 2010. Is. 16. P. 28-39

УДК 517.85

БАГАТОКРИТЕРІАЛЬНІ КОМБІНАТОРНІ ЗАДАЧІ НА ПОЛІПЕРЕСТАНОВКАХ ТА МЕТОДИ ЇХ РОЗВ'ЯЗУВАННЯ

Л. Колєчкіна*, О. Родіонова**

Інститут кібернетики ім. В.М. Глушкова НАН України, пер. Хорольський,8, кв.15, Полтава 36034, e-mail: ludapl@ukr.net Полтавський університет споживчої кооперації України, вул. Фрунзе, 146, кв. 13, Полтава, 36008, e-mail: rodionovaoa@mail.ru

Складність проблем сьогодення зумовлює до пошуку нових класів задач і підходів до їхнього розв'язування. Значне місце займають питання багатокритеріальної оптимізації на комбінаторних множинах, де вони відображають властивості множин допустимих розв'язків. У зв'язку з можливістю побудови математичних моделей прикладних задач питання оптимізації не втрачають своєї значущості та актуальності.

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

Ключові слова: багатокритеріальні комбінаторні задачі, методи розв'язування багатокритеріальних задач, моделі багатокритеріальних задач на полікомбінаторних множинах, множина поліперестановок, ефективний розв' язок.

1. ВСТУП

Питання багатокритеріальної дискретної оптимізації не втрачають своєї значущості [1-8]. Особливо актуальними вони є у світлі комбінаторної оптимізації, оскільки накладання відповідних умов на розв'язок задачі зумовлене властивостями та структурою множин допустимих значень. Поряд з множинами перестановок, розміщень, сполучень виділяються складніші структури - полікомбінаторні множини. Причиною цього є зручність використання зазначених структур для опису значної кількості задач [2, 3, 9-11]. Інтерес до полікомбінаторних множин зумовлений тим, що з їхнім використанням будують математичні моделі практичних задач багатокритеріальної оптимізації.

Для ефективного використання апарату полікомбінаторних множин необхідно вивчити властивості опуклих оболонок для багатокритеріальних задач. Тісний зв' язок комбінаторної оптимізації з комбінаторною теорією многогранників пояснюється тим, що комбінаторні многогранники є опуклими оболонками евклідових комбінаторних множин [15].

Наша стаття є продовженням досліджень в області багатокритеріальної оптимізації на полікомбінаторних множинах [1-11] та присвячена розгляду методів розв'язування багатокритеріальних задач, множин їхніх розв'язків і підходу до розв'язування багатокритеріальних задач на множині поліперестановок.

2. ФОРМУЛЮВАННЯ ЗАДАЧІ

Розглянемо безумовну багатокритеріальну задачу на полікомбінаторній множині  перестановок.  Критерії, що оптимізуються, подають таким набором

© Колєчкіна Л., Родіонова О., 2010функцій:

f (x) = max < cjxj >, i є Ns, j є Nk (1) Такий набір функцій можна подати у вигляді векторного критерію

F (x) = (fi(x),.., fm (x)), (2)

максимум якого треба знайти.

З додаткових умов може виникати умова належності розв'язку деякій комбінаторній чи полікомбінаторній множині. Розглянемо поняття поліпереставної множини: нехай k = г\. Множину перших m натуральних чисел позначимо через Nm відповідно Nm = {1,...,m}. Зобразимо цю множину у вигляді впорядкованого розбиття на s непорожніх підмножин N1,...,Ns, для яких виконуються умови: Nl n Nj = 0 , Nl Ф0, Nj Ф0 , Vi, j єNs. Нехай H - множина всіх елементів вигляду

де пі - довільна перестановка елементів множини Nt ViєNs. Позначимо через AN підмножину пронумерованої мультимножини A [2, 3], що складається з тих елементів A , номери яких належать множині Nl

A   і  = a2i,..., ап, І

де  ki = \N і |;   [ANi ] = (п1, л!-,..., aN <        Vj єNtil_l,   ViєNs, тоді множина

РкП(A,H) = |(ап(1),...,ап(к))апЄ) є A Viє Nk,Vпє HJ є загальною множиною поліперестановок.

Умову належності розв'язку множині поліперестановок запишемо у вигляді

x = (x1,...,xk) є Pk(A,H), (3) де Pksn (A, H ) - множина поліперестановок елементів мультимножини, що містить k елементів, серед яких n різних, і утворена розбиттям мультимножини A на s підмножин [2].

Множина поліперестановок збігається з множиною вершин многогранника поліперестановок: Pj^(A,H) = VertMslm(A,H), опукла оболонка якого описується системою [1]

=£aNiViє Ns, Xxj > Eє Ni,V Ns. (4)

jєN" j=1 jєюi j=1

Враховуючи зазначені умови, задачу сформулюємо так: знайти множину значень (3), що є оптимальною для функції (2)

Z(F,(A,H):max{F(x)xєР^(A,H)}.

Таку задачу назвемо багатокритеріальною безумовною задачею на множині поліперестановок. Під час розв'язування практичних задач виникає необхідність накладання додаткових умов. Математично такі умови D можуть бути подані у вигляді

Ajxj < bj, де іє Nm, j є Nk. (5).

Тоді задача (2), (3), (5) є комбінаторною багатокритеріальною задачею на множині поліперестановок з додатковими обмеженнями Z(F, X): max{F(x)x єХ} .

Враховуючи, що при відображенні в евклідовий простір [15] РП (A, H) = VertMln (A, H), отримаємо

X = D nMl (A, H). (6)

Велика кількість прикладних задач моделюється задачами багатокритеріальної оптимізації з урахуванням комбінаторних властивостей множини допустимих розв'язків, тобто задачами вигляду Z(F, Pksn (A, H) . Розглянемо такі моделі.

3. МОДЕЛЬ ПРИКЛАДНОЇ ЗАДАЧІ НА МНОЖИНІ ПОЛІПЕРЕСТАНОВОК Модель задачі визначення ефективності вкладів у нерухомість. Нехай підприємство має k активів для вкладень у нерухомість A = (а1,...,ak) . Причому

частина цих сум може бути використана лише для здійснення вкладів а1 на період до n1 років, а2 - на n2 років і так далі, as на період до ns; x = (x1,...,xk) -шуканий план вкладів у нерухомість, який треба знайти, де xt - сума вкладу у i -й вид нерухомості. Підприємству доступна інформація про ризики від вкладу у нерухомість i -го виду - c),iє Nt, дохід від нерухомості i -го виду - cf,iє Nt, а також сума витрат на утримання i -го виду нерухомості - с3,іє Nk. Отже, для отримання оптимального плану вкладів у нерухомість потрібно оптимізувати такі критерії.

• Сума ризиків від вкладу f1(x) = min < c1,x >,іє Nk.

• Прибуток від вкладу f2(x) = max < c2, x >,iє Nk.

• Витрати на утримання (експлуатацію) нерухомості f3(x) = min < c3, x >,iє Nk.

Оскільки вклад у нерухомість пов'язаний з необхідністю подальших витрат на утримання, то виникають додаткові обмеження пов'язані з ресурсами підприємства Ajjxj < bj, де і є Nm, j є Nk, де Atj - затрати ресурсів j -го виду на утримання і -го

виду нерухомості, b j - наявність ресурсів j -го виду.

Математична модель задачі. x = (x1,...,xk) - план вкладень у нерухомість, який треба знайти. Описана вище побудова множини x = (x1,...,xk) відповідає множині поліперестановок РП (A, H). Отже, маємо задачу:

знайти таке значення x = (x1,...,xk) є Pk'n(A,H) , яке оптимальне для функцій: f1 ( x) = min < c1 , x >, є Nk , f 2 (x) = max < c2, x >, і є Nk , f 3 (x) = min < c], x >, і є Nk та задовольняє обмеження Ajjxj < bj.

4. ОПИС РОЗВ'ЯЗКІВ БАГАТОКРИТЕРІАЛЬНИХ КОМБІНАТОРНИХ

ЗАДАЧ

При розв' язуванні багатокритеріальних оптимізаційних задач користуються поняттям ефективного розв'язку. Це означає, що жоден із допустимих розв'язків задачі не може поліпшити значення деякої цільової функції, не погіршуючи значення хоча б одного з критеріїв, що залишились. Ефективну альтернативу називають також оптимальною за Парето [13]. Усі такі альтернативи утворюють множину Парето-оптимальних розв'язків - Р(F, X) [7, 8]. Крім Парето-оптимальних (ефективних) розв'язків, визначають також й інші множини розв'язків задач комбінаторної багатокритеріальної оптимізації, такі як Sl(F, X) - множина оптимальних за Слейтером (слабоефективних) розв'язків, Sm(F, X) - множина оптимальних за Смейлом (строго ефективних) розв'язків.

При розв'язуванні задачі знаходять ефективний розв'язок (оптимальний за Парето).

Для задач евклідової комбінаторної оптимізації на множині поліперестановок правильним є твердження, що елементи множин P(F, X) - Парето-оптимальних (ефективних), Sl(F, X) - слабо ефективних та Sm(F,X) - строго ефективних розв'язків задачі розташовані у вершинах многогранника поліперестановок [8]. Це твердження випливає з того, що X = РЩ,(A,H) = VertMsb(A,H) с      (A,H).

5. ВИБІР МЕТОДУ РОЗВ'ЯЗУВАННЯ БАГАТОКРИТЕРІАЛЬНОЇ ЗАДАЧІ

НА ПОЛІПЕРЕСТАНОВКАХ

Багатокритеріальна оптимізація зводиться до вибору серед множини можливих альтернатив, проте виконати цей вибір - складне завдання, оскільки на практиці буває неможливо досягти найліпшого значення для усіх критеріїв одночасно. Питання про переваги на множині допустимих значень досить важливе, оскільки така інформація значно полегшує вибір. Теорія багатокритеріальної оптимізації розглядає різні групи методів, серед яких є такі, що не використовують інформацію про перевагу на множині критеріїв, або використовують один тип інформації про перевагу на множині критеріїв, або використовують різні типи інформації про перевагу на множині критеріїв і спеціальні методи.

Найбільш відомі такі методи: метод ідеальної точки, метод послідовних поступок, метод послідовного введення обмежень, метод бажаної точки, метод задоволення вимог і метод векторної релаксації.

Метод ідеальної точки не використовує допоміжну інформацію про перевагу на множині критеріїв. При розв'язуванні задач цим методом робиться припущення про наявність так званого оптимального розв' язку задачі багатокритеріальної оптимізації, який може бути знайдено шляхом перетворення багатокритеріальної задачі у відповідну однокритеріальну задачу.

На відміну від методу ідеальної точки у методах послідовних поступок, послідовного введення обмежень і задоволених вимог використовують два типи інформації: інформації про впорядкування критеріїв та інформації про діапазони значень критеріїв, проте кожен з цих методів має свої особливості. Наприклад, особливістю методу послідовних поступок є те, що критерії багатокритеріальної задачі повинні бути попередньо впорядковані за зменшенням їхньої важливості, після чого   вибір   розв'язку  задачі   відбувається  шляхом  виконання багатокроковоїдіалогової процедури. Характерною відмінністю методу послідовного введення обмежень є послідовне (на кожному кроці) введення обмежень на альтернативи, які мають незадовільні значення критеріїв, а метод задоволених вимог передбачає визначення переваги на множині критеріїв шляхом виділення так званого головного критерію. Особливістю діалогової процедури методу бажаної точки є необхідність задання бажаних значень критеріїв для визначення переваги на множині критеріїв.

Звичайно, кожен з методів має також певні недоліки. Наприклад, серед недоліків діалогової процедури методу послідовних поступок варто відмітити, що тільки на першому кроці методу величина поступки відповідає її фактичній величині, оскільки вона визначена на всій множині альтернатив. На наступних кроках величина поступки може бути значно меншою за її фактичну величину, оскільки вона визначається на "уточненій" множині альтернатив. Недоліком методу є також зростання обчислювальної складності задач оптимізації з кількістю зроблених кроків, оскільки на кожному кроці додається нове обмеження. Недолік методу векторної релаксації: він призначений для пошуку ефективних альтернатив лише в задачах багатокритеріальної безумовної оптимізації. Припускається, що критерії задачі неперервно-диференційовані вгнуті функції. Варто також зауважити, що альтернативи, які генеруються цією процедурою, тільки в граничному випадку будуть ефективними.

Ці методи не комбінаторні, але ідеї цих методів можуть бути використані як підходи до розв'язування задач багатокритеріальної комбінаторної оптимізації. Розглядаючи комбінаторні методи, треба наголосити на їхній гнучкості та можливості застосування до різних задач комбінаторної оптимізації. Суть комбінаторних методів у скороченому переборі скінченої множини можливих розв'язків задачі. Серед найпоширеніших методів комбінаторної оптимізації можна назвати метод гілок і меж, метод побудови послідовності розв'язків, метод послідовного аналізу варіантів, метод локальної оптимізації, метод динамічного програмування та апроксимаційно-комбінаторний метод. При розв'язуванні комбінаторних задач застосовують евристичні алгоритми, які досить швидко дають розв'язок, але недоліком їхнього використання є той факт, що оптимальності вони гарантувати не можуть.

Страницы:
1  2  3 


Похожие статьи

Л Колєчкіна - Багатокритеріальні комбінаторні задачі на поліперестановках та методи їх розв'язування