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

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

Повний опис

Збережено в:

Бібліографічні деталі
Дата:	2014
Автори:	Александрова, В.М., Соболенко, Л.О.
Формат:	Стаття
Мова:	Ukrainian
Опубліковано:	Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України 2014
Назва видання:	Системні дослідження та інформаційні технології
Теми:	Методи оптимізації, оптимальне управління і теорія ігор
Онлайн доступ:	http://dspace.nbuv.gov.ua/handle/123456789/86116
Теги:	Додати тег Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Цитувати:	Деякі методи знаходження ефективних точок багатокритеріальної задачі оптимізації / В.М. Александрова, Л.О. Соболенко // Системні дослідження та інформаційні технології. — 2014. — № 4. — С. 100-110. — Бібліогр.: 9 назв. — укр.

Репозитарії

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	irk-123456789-86116
record_format	dspace
spelling	irk-123456789-861162015-09-09T03:01:59Z Деякі методи знаходження ефективних точок багатокритеріальної задачі оптимізації Александрова, В.М. Соболенко, Л.О. Методи оптимізації, оптимальне управління і теорія ігор Розглянуто чисельні підходи до отримання Парето-оптимальних точок, що базуються на зведенні багатокритеріальних задач оптимізації до «скаляризованих» задач оптимізації зі спеціальними цільовими функціями. Послідовна оптимізація таких функцій при зафіксованих значеннях вагових коефіцієнтів критеріальних функцій дозволяє виділяти серед безлічі ефективних рішень ті, що задовольняють ОПР. На основі задачі дискретного мінімаксу, що будується із застосуванням векторів критеріїв та вагових коефіцієнтів, запропоновано модифікацію методу лінеаризації для розв’язання задачі багатокритеріальної оптимізації. Вихідна задача по знаходженню ефективної точки зводиться до послідовного розв’язання задач квадратичного програмування. Наведено результати чисельного розв’язання багатокритеріальних задач оптимізації різними методами. Проведений в роботі аналіз та порівняння чисельного експерименту підтверджують ефективність запропонованого методу. Рассмотрены наиболее известные численные подходы к получению Парето-оптимальных точек, основанны на сведении многокритериальных задач оптимизации к «скаляризованным» задачам оптимизации со специальными целевыми функциями. Последовательная оптимизация таких функций при зафиксированных значениях весовых коэффициентов критериальных функций позволяет выделять среди множества эффективных решений те, которые удовлетворяют ЛПР. На основе задачи дискретного минимакса, которая строится с использованием векторов критериев и весовых коэффициентов, предложена модификация метода линеаризации для решения задачи многокритериальной оптимизации. Исходная задача по нахождению эффективной точки сводится к последовательному решению задач квадратичного программирования. Приведены результаты численного решения многокритериальных задач оптимизации различными методами. Проведенный в работе анализ и сравнение результатов численного эксперимента подтверждают эффективность предложенного метода. Thе paper describes numerous approaches to obtain Pareto-optimal points, based on the reduction of multi-criteria optimization problems to «scalarized» optimization problems with specific objective functions. The sequential optimization of the functions at the fixed values of criteria functions weights allows to select among the many effective solutions, those that satisfy the decision maker. The modification of the linearization method for solving multi-objective optimization problems was proposed. It is based on the discrete minimax problem, which is constructed using criteria and the weights. The original problem of finding the effective point is reduced to the successive solutions of quadratic programming problems. The results of numerical solutions of multiobjective optimization problems by different methods were presented. The performed analysis and comparison of the results of numerical experiments confirm the effectiveness of the proposed method. 2014 Article Деякі методи знаходження ефективних точок багатокритеріальної задачі оптимізації / В.М. Александрова, Л.О. Соболенко // Системні дослідження та інформаційні технології. — 2014. — № 4. — С. 100-110. — Бібліогр.: 9 назв. — укр. 1681–6048 http://dspace.nbuv.gov.ua/handle/123456789/86116 519.8 uk Системні дослідження та інформаційні технології Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Ukrainian
topic	Методи оптимізації, оптимальне управління і теорія ігор Методи оптимізації, оптимальне управління і теорія ігор
spellingShingle	Методи оптимізації, оптимальне управління і теорія ігор Методи оптимізації, оптимальне управління і теорія ігор Александрова, В.М. Соболенко, Л.О. Деякі методи знаходження ефективних точок багатокритеріальної задачі оптимізації Системні дослідження та інформаційні технології
description	Розглянуто чисельні підходи до отримання Парето-оптимальних точок, що базуються на зведенні багатокритеріальних задач оптимізації до «скаляризованих» задач оптимізації зі спеціальними цільовими функціями. Послідовна оптимізація таких функцій при зафіксованих значеннях вагових коефіцієнтів критеріальних функцій дозволяє виділяти серед безлічі ефективних рішень ті, що задовольняють ОПР. На основі задачі дискретного мінімаксу, що будується із застосуванням векторів критеріїв та вагових коефіцієнтів, запропоновано модифікацію методу лінеаризації для розв’язання задачі багатокритеріальної оптимізації. Вихідна задача по знаходженню ефективної точки зводиться до послідовного розв’язання задач квадратичного програмування. Наведено результати чисельного розв’язання багатокритеріальних задач оптимізації різними методами. Проведений в роботі аналіз та порівняння чисельного експерименту підтверджують ефективність запропонованого методу.
format	Article
author	Александрова, В.М. Соболенко, Л.О.
author_facet	Александрова, В.М. Соболенко, Л.О.
author_sort	Александрова, В.М.
title	Деякі методи знаходження ефективних точок багатокритеріальної задачі оптимізації
title_short	Деякі методи знаходження ефективних точок багатокритеріальної задачі оптимізації
title_full	Деякі методи знаходження ефективних точок багатокритеріальної задачі оптимізації
title_fullStr	Деякі методи знаходження ефективних точок багатокритеріальної задачі оптимізації
title_full_unstemmed	Деякі методи знаходження ефективних точок багатокритеріальної задачі оптимізації
title_sort	деякі методи знаходження ефективних точок багатокритеріальної задачі оптимізації
publisher	Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України
publishDate	2014
topic_facet	Методи оптимізації, оптимальне управління і теорія ігор
url	http://dspace.nbuv.gov.ua/handle/123456789/86116
citation_txt	Деякі методи знаходження ефективних точок багатокритеріальної задачі оптимізації / В.М. Александрова, Л.О. Соболенко // Системні дослідження та інформаційні технології. — 2014. — № 4. — С. 100-110. — Бібліогр.: 9 назв. — укр.
series	Системні дослідження та інформаційні технології
work_keys_str_mv	AT aleksandrovavm deâkímetodiznahodžennâefektivnihtočokbagatokriteríalʹnoízadačíoptimízacíí AT sobolenkolo deâkímetodiznahodžennâefektivnihtočokbagatokriteríalʹnoízadačíoptimízacíí
first_indexed	2025-07-06T13:32:37Z
last_indexed	2025-07-06T13:32:37Z
_version_	1836904619868946432
fulltext	 В.М. Александрова, Л.О. Соболенко, 2014 100 ISSN 1681–6048 System Research & Information Technologies, 2014, № 4 TIДC МЕТОДИ ОПТИМІЗАЦІЇ, ОПТИМАЛЬНЕ УПРАВЛІННЯ І ТЕОРІЯ ІГОР УДК 519.8 ДЕЯКІ МЕТОДИ ЗНАХОДЖЕННЯ ЕФЕКТИВНИХ ТОЧОК БАГАТОКРИТЕРІАЛЬНОЇ ЗАДАЧІ ОПТИМІЗАЦІЇ В.М. АЛЕКСАНДРОВА, Л.О. СОБОЛЕНКО Розглянуто чисельні підходи до отримання Парето-оптимальних точок, що ба- зуються на зведенні багатокритеріальних задач оптимізації до «скаляризова- них» задач оптимізації зі спеціальними цільовими функціями. Послідовна оп- тимізація таких функцій при зафіксованих значеннях вагових коефіцієнтів критеріальних функцій дозволяє виділяти серед безлічі ефективних рішень ті, що задовольняють ОПР. На основі задачі дискретного мінімаксу, що будується із застосуванням векторів критеріїв та вагових коефіцієнтів, запропоновано модифікацію методу лінеаризації для розв’язання задачі багатокритеріальної оптимізації. Вихідна задача по знаходженню ефективної точки зводиться до послідовного розв’язання задач квадратичного програмування. Наведено ре- зультати чисельного розв’язання багатокритеріальних задач оптимізації різними методами. Проведений в роботі аналіз та порівняння чисельного ек- сперименту підтверджують ефективність запропонованого методу. ВСТУП Вивчення питань прийняття рішень під час дослідження й проектування складних систем призводить до необхідності постановок задач оптимізації з урахуванням сукупності критеріальних функцій — багатокритеріальних задач оптимізації. Це пояснюється тим, що лише у виняткових випадках аль- тернативні рішення щодо способів проведення операції можна порівнювати між собою за одним критерієм. Зазвичай для прийняття рішення потрібно здійснити вибір на основі цілої низки критеріїв, які можуть перебувати в суперечності один до одного. Але при цьому кожен із запропонованих критеріїв вважається настільки суттєвим, що не врахування його під час ви- бору рішення було б ризикованим і необачливим з огляду наслідків прове- дення операції. Основним питанням, що виникає, коли порівнюють між со- бою альтернативні рішення за умови кількох критеріїв, є: яке з двох рішень вважати кращим, якщо під час заміни одного із цих рішень на інше значення одного або кількох критеріїв «покращаться», а інших — «погіршаться». Мета роботи — розробка способу прийняття ефективних рішень за умови кількох критеріїв, що базується на зведенні багатокритеріальної задачі оптимізації до задачі дискретного мінімаксу та розв’язанні її методом лінеаризації. Порівняння запропонованого методу з найпоширенішими ме- тодами розв’язання багатокритеріальної задачі оптимізації. Деякі методи знаходження ефективних точок багатокритеріальної задачі оптимізації Системні дослідження та інформаційні технології, 2014, № 4 101 ПАРЕТО–ОПТИМАЛЬНІ ТОЧКИ Нехай X — певним чином визначена множина (альтернативних рішень), а }{ iF — визначені на X m функцій. Припустимо, що значення кожної з цих функцій шляхом підходящого вибору елемента (рішення) x з множи- ни X бажано зробити (для визначеності) найменшим: Xx xF  inf)(  , (1) де            )( )( )( 1 xF xF xF m  — m -компонентна (критеріальна) вектор-функція. Нехай ,1m тобто є принаймні дві критеріальні функції .}{ iF Кожна з цих функ- цій застосовується для порівняння рішень з множини X . За даним i -м кри- терієм iF рішення Xx вважається «кращим» за рішення ,Xy якщо )()( yFxF ii  . Задача (1) називається багатокритеріальною задачею оптимі- зації. Основна проблема, що при цьому виникає, полягає в суперечливості бажання одночасної мінімізації на множині X усіх критеріальних функцій .}{ iF Може статися так, що за будь-якої заміни цього розв’язку Xx на ін- ший розв’язок Xy при зменшенні значень одних критеріальних функцій значення інших критеріальних функцій збільшуються. Отже, для багатокритеріальних задач оптимізації немає абсолютно най- кращих (за всіма критеріями одночасно) рішень. Але це зовсім не означає, що неможливо раціоналізувати вибір рішення на заданій множині альтерна- тивних рішень. Рішення (вектор, елемент, точку) XxP  називають оптимальним за Парето (або Парето-оптимальним, або ефективним) [1–3], якщо не існує рі- шення Xx такого, що ,,,1)()( mixFxF Pii  й )()( Pii xFxF  хоча б для одного },...,1{ mi . Іншими словами, якщо XxP  — Парето- оптимальне, то для будь-якого Xx знайдеться функція ,iF  )(xii },...,1{ m (яка саме функція — залежить від рішення x ), для якої .)()( Pii xFxF  Із цього означення випливає, що заміна Парето-оптимального рішення на Xx якщо й призводить до зменшення значень деяких критеріальних функцій, то вона обов’язково призводить до збільшення інших функцій. Рішення (вектор, елемент, точка) XxSp  називається слабо ефектив- ним, якщо не існує рішення Xx такого, що )()( Spii xFxF  mi ,,1  [1–3]. Тобто заміна слабо ефективного рішення не може призвести до одно- часного покращення значень усіх критеріальних функцій. Якщо позначити PX — множину Парето-оптимальних точок, а SpX — множину слабо ефективних точок, то має місце включення: .XXX PSp  В.М. Александрова, Л.О. Соболенко ISSN 1681–6048 System Research & Information Technologies, 2014, № 4 102 Оптимальне за Парето рішення можна інтерпретувати як економічно прийнятне, раціональне й у певному розумінні добре рішення. Отже, під розв’язанням багатокритеріальної задачі оптимізації (1) бу- демо розуміти знаходження деякої множини ,XD  кожна точка якої на- лежить PX (або SpX ). ЗНАХОДЖЕННЯ ПАРЕТО-ОПТИМАЛЬНИХ ТОЧОК Нехай множина ,X на якій визначені функції ,)(xFi },,1{ mIi  задачі (1), задається системою рівностей та нерівностей: .},0)(;,0)(\|{ 0IjxgIjxgRxXx jj n   (2) При цьому всі функції, що визначають задачу (1), (2), ),(xFi ,Ii ),(xg j ,0IIj  — опуклі та неперервно диференційовані. Більшість з відомих підходів до розв’язання багатокритеріальної задачі оптимізації (1), (2) полягають у тому, що початкова задача зводиться до де- якої однокритеріальної (скалярної) задачі оптимізації шляхом «згортання» векторного критерія )(xF в одну цільову функцію — узагальнений крите- рій. При цьому можливе одержання узагальненого критерія декількома спо- собами. Найбільш розповсюдженим узагальненим критерієм є лінійна згортка: ,)()(    Ii ii xFxF  (3) де }{ i — довільним чином вибрані m чисел такі, що   i ii ,1,0  .Ii Не важко довести, що розв’язок )(pP xx  задачі математичного програмування з цільовою функцією (3)            m i iiXx xFxF 1 )()(min  (4) є оптимальним за Парето рішенням задачі (1). Вагові коефіцієнти }{ i в означенні цільової функції )(xF задачі оп- тимізації (4) мають таку інтерпретацію. По-перше, ці коефіцієнти є коефіці- єнтами зведення до єдиної одиниці виміру різних одиниць виміру значень критеріальних функцій .}{ iF І, по-друге, величина коефіцієнта i є величи- ною «абсолютної значущості» критеріальної функції iF , тобто більш зна- чущій для особи, яка приймає рішення (ОПР), критеріальній функції F має відповідати більший ваговий коефіцієнт . Для різних векторів mR одержуємо різні однокритеріальні задачі (4), тобто перебираючи різні значення }{ i можна отримати різні Парето- оптимальні рішення сформульованої m -критеріальної задачі математичного Деякі методи знаходження ефективних точок багатокритеріальної задачі оптимізації Системні дослідження та інформаційні технології, 2014, № 4 103 програмування (1). На якому саме із цих рішень зупинить свій вибір ОПР, взагалі кажучи, не відомо. Цей вибір залежить як від вже отриманого досві- ду розв’язування відповідного типу задач, так і від заздалегідь не формалі- зованих бажань. Для розв’язання задачі (4) можна застосовувати відомі методи неліній- ної оптимізації, наприклад, метод лінеаризації та його прискорені модифі- кації [4–7]. Інший підхід до розв’язання багатокритеріальної задачі оптимізації по- лягає в тому, що деяку ефективну точку задачі (1) можна охарактеризувати в термінах розв’язку задачі дискретного мінімаксу [5, 8]: )(maxmin xFi IiXx  . (5) Задача (5), у свою чергу, еквівалентна задачі оптимізації: ,},,)(:{min , XxIixFi x    (6) де 1R — допоміжна змінна. Таким чином, задача (5) (або (6)) дозволяє визначити гарантовану верхню оцінку для всіх критеріїв .),( IixFi  Для розв’язання (6) також можна застосувати відомі методи оптимізації. В [8] на основі задач (5), (6) було запропоновано метод лінеаризації знаходження ефективної точки задачі (1), (2). Допоміжна задача цього мето- ду для задачі (5) має вигляд: ,,0)(),(:),(max 2 1min 2      IjxgpxgpxFp jji ip .,0)(),( 0   Ijxgpxg jj (7) Недоліком цього методу з допоміжною задачею (7) є те, що він знахо- дить лише одну Парето-оптимальну точку (як правило, слабо ефективну), яка не завжди є прийнятною для ОПР. Розглянемо «скаляризацію» багатокритеріальної задачі оптимізації (1) із застосуванням задачі дискретного мінімаксу «зважених» критеріїв: .1,0),(maxmin    Ii iiii IiXx xF  (8) Розв’язуючи задачу (8) для різних значень вагових коефіцієнтів ,}{ i можна одержати різні ефективні точки )(* x початкової задачі (1). Не важко показати, що, якщо точка x — розв’язок задачі (8), то x — слабо ефективна точка задачі (1). Припустимо, що Xx * не є слабо ефек- тивною точкою задачі (1). Тоді за означенням знайдеться така точка ,ˆ Xx що IixFxF ii  )()ˆ( * . Отже для будь-якого i справедлива нерівність: )(max)()ˆ( xFxFxF ii i iiii   . (9) В.М. Александрова, Л.О. Соболенко ISSN 1681–6048 System Research & Information Technologies, 2014, № 4 104 Оскільки нерівність (9) виконується для всіх ,i то вона виконується й для такого ,i для якого досягається максимум у лівій її частині, тобто .)(max)()ˆ(max xFxFxF ii i iiii i   Нерівність )(max)ˆ(max xFxF ii i ii i   суперечить тому, що Xx  — розв’язок задачі (8). Побудуємо модифікацію методу лінеаризації [8, 9] знаходження ефек- тивної точки задачі (1), (2), розв’язуючи задачу (8). Основою цього алгоритму є розв’язання наступної допоміжної задачі квадратичного програмування:     ,,0),(:2/1min 2 , IipxFp ii p   ,,0)(),(,,0)(),( 0    IjxgpxgIjxgpxg jjjj (10) де ,0i 1 Ii i — фіксовані. Функція Лагранжа задачі (10) має вигляд:       0 )(),(),( 2 1),,,( 2 IIj jjj Ii iii xgpxgvpxFupvupL   . Необхідними й достатніми умовами, що пов’язують розв’язок )(xp за- дачі (10) з множниками Лагранжа ,}{ iu ,}{ iv є наступна система рівностей та нерівностей:                             .0)()()( ,,0 ,,0 ,1 ,,0)(),( ,,0),( 0 0 0 xgvxFuxp Ijv Iju u IIjxgpxgv IipxFu j IIj jii Ii i j i Ii i jjj iii     (11) Тепер нескладно побудувати двоїсту задачу до задачі (10):            2 , 0 )()( 2 1max Ii IIj jjiii vu xgvxFu   .,0 ,,0 ,1:)( 0            Ijv Iiu uxgv j i Ii i IIj jj  (12) Деякі методи знаходження ефективних точок багатокритеріальної задачі оптимізації Системні дослідження та інформаційні технології, 2014, № 4 105 Розв’язками задачі (12) є вектори )}({ xui та )}({ xv j , а розв’язок )(xp задачі (10), згідно системи (11), визначається рівнянням: .)()()()()( 0 xgxvxFxuxp j IIj jii Ii i      Розв’язок )( kk xpp  задачі (10) для kxx  вважатимемо вектором спуску в ітераційному процесі: .1 k k kk ptxx  Кроковий множник kt вибираємо за таким правилом: знаходимо перше значення ,,1,0 s для якого виконується нерівність: ,)()(})]()([{max 2kk k kk k k i kk ii Ii ptxgNtpxgNxFtpxF     (13) 0,2   st — достатньо мале число. Якщо таке 0ss  знайдено, то ви- бираємо .2 0s kt  В (13) ,},\|)(\|;),(;0{max)( 0IjxgIjxgxg jj      0 \|)(\| IIj kjk xvN  , де )}({ kj xv — розв’язок двоїстої задачі (12) в точці .kxx  Обґрунтування обмеженості знизу величин ,2 st  ,,1,0 s наве- дено в [4]. Критерієм зупинки описаного ітераційного процесу є виконання умови 1)( kxp , 01  — задана точність. Для методу з допоміжною задачею (7) в [8] доведено, що рівність 0)( * xp та виконання умов регулярності в точці ,x є необхідними для то- го, щоб точка x була оптимальною для задачі (6) й слабо ефективною для задачі (1), (2). Для опуклої задачі (1), (2) (множина X та функції ),(xFi Ii — опуклі) за виконання умов регулярності в точці x рівність 0)( xp є також і достатньою. Якщо ж припускається строга опуклість функцій ,)(xFi Ii та виконання умов регулярності, то рівність 0)( * xp є необхідною і достатньою для того, щоб точка x була Парето- оптимальною для задачі (1), (2). Для описаної модифікації методу лінеаризації розв’язання задачі (1), (2) з допоміжною задачею (10) при фіксованих 0i , 1 Ii i справедливі аналогічні властивості, які встановлюють зв’язок між виконанням умов 0)( xp та ефектнивною (слабо-ефективною) точкою x задачі (1), (2). Оскільки зазвичай множина ефективних точок багатокритеріальної за- дачі оптимізації (1) містить багато точок, а запропоновані методи на основі «згортання» критеріїв (задачі (4), (8)) для фіксованого набору вагових коефіцієнтів }{ i знаходять тільки одну ефективну точку ,)(Px то розв’язання багатокритеріальної задачі оптимізації неможливе без діалогу з ОПР. В.М. Александрова, Л.О. Соболенко ISSN 1681–6048 System Research & Information Technologies, 2014, № 4 106 ПОРІВНЯННЯ МЕТОДІВ ЗНАХОДЖЕННЯ ЕФЕКТИВНИХ ТОЧОК НА ПРИКЛАДІ РОЗВ’ЯЗАННЯ МОДЕЛЬНОЇ ЗАДАЧІ Приклад. Знайти ефективні точки багатокритеріальної задачі оптимізації [9]: Xxxx xx xF          max 4 52 )( 21 21  , (14) де множина X визначається нерівностями: ,1021  xx ,02,1 x ,81 x 62 x (рис. 1). Початкова точка — .}0;0{0 Tx  Розв’яжемо задачу (14) декількома способами. 1 спосіб. Побудуємо лінійну «згортку» векторного критерія F й пере- йдемо від задачі (14) до задачі оптимізації:  21212211 :)4()52()({max xxxxxxxF x  .}6,8,0,10 212,1  xxx (15) Значення параметрів ,0}{ 2,1  .121  Для значення параметрів ,5,01  5,02  лінії рівня функції )(xF паралельні прямій ,)10( 21  xx що визначає перше обмеження задачі (15). Тобто у цьому випадку множина Рис. 1. Множини допустимих і Парето-оптимальних точок, лінії рівнів критеріаль- них функцій задачі (14) 6 2x 1x Лінії рівня )(2 xF 0 4 8 Лінії рівня )(1 xF Лінії рівня )(xF для різних  Парето-оптимальна множина Множина альтернативних рішень )(X 2 Деякі методи знаходження ефективних точок багатокритеріальної задачі оптимізації Системні дослідження та інформаційні технології, 2014, № 4 107 розв’язків задачі (15) збігається з множиною Парето-оптимальних точок задачі (14) (рис. 1). Для значень 15,0 1  й відповідних 12 1   розв’язком задачі (15) є єдина точка ,)6;4( Tx  а для значень  10  5,0 — єдина точка .)2;8(* Tx  2 спосіб. Задачу (14) шляхом введення допоміжної змінної  зводимо до оптимізаційної задачі виду (6): ,4,52:{max 2121 ,    xxxx x }.6,8,0,10 212,121  xxxxx (16) У цьому випадку одержуємо лише одну Парето-оптимальну точку за- дачі (14): ,)33,3;66,6(* Tx  ,)30;30()( * TxF  .30*  3 спосіб. Парето-оптимальні точки задачі (14) знаходимо шляхом розв’язання задач, аналогічних (16), для різних значень ,0}{ 2,1  :121  ,)4(,)52(:{max 212211 ,    xxxx x }.6,8,0,10 212,121  xxxxx (17) Однокритеріальні задачі (15)–(17), до яких зводилась початкова багато- критеріальна задача оптимізації (14), розв’язувались за допомогою авторсь- ких реалізацій метода лінеаризації [4], запропонованої модифікації метода [8] та методами пакета Solver, Frontline Systems Inc. Методи пакета Solver для розв’язання оптимізаційних задач можна ви- кликати з MS Excel, попередньо сформувавши у клітинах робочого аркушу математичну модель задачі. Так, наприклад, на рис. 2 показано робочий аркуш MS Excel, в клітинах якого містяться значення початкової точки, вагові кое- фіцієнти та формули для обчислення цільової функції й обмежень задачі (15). Рис. 2. Математична модель задачі (15) для пакета Solver В.М. Александрова, Л.О. Соболенко ISSN 1681–6048 System Research & Information Technologies, 2014, № 4 108 На рис. 3 показано, як потрібно задати параметри у вікні програми Solver, щоб застосувати її для розв’язання цієї задачі. В таблиці наведені Парето-оптимальні точки задачі (14) та способи, за допомогою яких вони одержані. Т а б л и ц я . Результати обчислень № x F  Примітка (задача, метод )       30 30 , 30 – Задача (16) – метод [4], Solver 1       33,3 66,6       15 15 , 15       5,0 5,0 Задача (17) – метод [4], Solver Задача (14) – мод. метода [8] ]5,0;0[1  , 12 1   Задача (15) – метод [4], Solver 2       2 8       34 26 ]1;567,0[1 12 1   Задача (17) – метод [4], Solver Задача (14) – мод. метода [8] [1;5,0]1  , 12 1   Задача (15) – метод [4], Solver 3       6 4       22 38 [367,0;0]1 , 12 1   Задача (17) – метод [4], Solver Задача (14) – мод. метода [8] 4       5 5       25 35       5,0 5,0 Задача (15) – метод [4], Solver 5 Безліч ефек- тивних точок ]38;26[1F , ]34;22[2 F ,[567,0;367,0[1  12 1   Задача (17) – метод [4], Solver Задача (14) – мод. метода [8] Рис. 3. Параметри задачі (15) для пакета Solver Деякі методи знаходження ефективних точок багатокритеріальної задачі оптимізації Системні дослідження та інформаційні технології, 2014, № 4 109 З проведених чисельних експериментів можна зробити висновок, що найбільш «повне покриття» Парето-оптимальної множини задачі (14) можна одержати, якщо розв’язувати її або безпосередньо за допомогою сформу- льованої вище модифікації метода лінеаризації, або розв’язуючи «зведену» задачу (17) методами оптимізації. Оскільки запропонована модифікація метода лінеаризації враховує специфіку оптимізаційної задачі (17), до якої зводиться багатокритеріальна задача, то вона знаходить розв’язок за меншу кількість ітерацій, ніж загальні методи, які не враховують цієї специфіки. Це продемонстровано на рис. 4, де порівнюється збіжність запропонованого метода та метода [4], хоча хара- ктер збіжності однаковий. Відмінність між ітераційними процесами цих двох методів полягає в тому, що перший будує послідовність точок у просторі )( nR вихідної за- дачі, а другий — у просторі більшого виміру .)( 1nR Із застосуванням задач (15) шляхом варіювання вагових коефіцієнтів можна одержати лише деяку підмножину ефективних точок задачі (14), а із застосуванням задачі (16) — взагалі лише одну. ВИСНОВКИ Розглянуто багатокритеріальну задачу оптимізації, в якій критеріальні фун- кції, що складають векторний критерій, та функції, що описують множину допустимих точок, є опуклими та неперервно диференційованими. Описані підходи до отримання Парето-оптимальних точок на основі зведення початкової задачі до задач математичного програмування зі спеці- альними цільовими функціями, побудованими на компонентах векторного критерія та параметрах, що визначають уподобання ОПР. Послідовна опти- мізація таких функцій при зафіксованих значеннях параметрів дозволяє ви- діляти серед Парето-оптимальних рішень ті, що задовольняють ОПР. Рис. 4. Збіжність методів: а — запропонований метод; б — [4] а б В.М. Александрова, Л.О. Соболенко ISSN 1681–6048 System Research & Information Technologies, 2014, № 4 110 Запропоновано модифікацію метода лінеаризації Б.Н. Пшеничного для розв’язання багатокритеріальної задачі оптимізації, яка будується на основі задачі дискретного мінімаксу «зважених» критеріїв. Стосовно цієї задачі доведено, що її розв’язок для фіксованих параметрів є слабо ефективною точкою відповідної багатокритеріальної задачі оптимізації. У роботі наведено розрахунки та чисельні експерименти із застосуван- ням метода лінеаризації, запропонованого метода та методів пакета Solver Frontline Systems Inc. Метод лінеаризації для задач математичного програ- мування, його модифікація для багатокритеріальної задачі оптимізації та алгоритм для розв’язання допоміжної задачі (задачі квадратичного програ- мування) реалізовано авторами у вигляді ієрархії класів C# для платформи NET 3.5. Проведений порівняльний аналіз роботи алгоритмів, наглядно підтвер- джує ефективність роботи запропонованого алгоритму. ЛІТЕРАТУРА 1. Гермейер Ю.Б. Введение в теорию исследования операций. — М.: Наука, 1987. — 384 с. 2. Подиновский В.В., Ногин В.Д. Парето–оптимальные решения много-крите- риальных задач. — М.: Наука, 1982. — 256 с. 3. Ржевський С.В., Александрова В.М. Дослідження операцій. — К.: Академвидав, 2006. — 560 с. 4. Пшеничный Б.Н. Метод линеаризации. — М.: Наука, 1983. — 136 с. 5. Пшеничный Б.Н., Данилин Ю.М. Численные методы в экстремальных зада- чах. — М.: Наука, 1975. — 319 с. 6. Пшеничный Б.Н., Панин В.М., Соболенко Л.А. Методы оптимизации в эконо- мико-математическом моделировании / Под ред. Е.Г. Гольштейна. — М.: Наука, 1991. — 448 с. 7. Химмельблау Д. Прикладное нелинейное программирование. — М.: Мир, 1975. — 534 с. 8. Пшеничный Б.Н., Сосновский А.А. Метод линеаризации для решения много- критериальной задачи оптимизации // Кибернетика. — 1987. — № 6. — С. 107–109. 9. Сосновский А.А., Александрова В.М. Несколько примеров решения мно- гокритериальной задачи оптимизации // Использование методов и ин- формационных технологий в технических и экономических системах. — К.: ИК АН Украины, 1992. — С. 17–23. Надійшла 07.03.2014

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

Репозитарії

Схожі ресурси