Задачі багатокритеріальної оптимізації в дослідженні операцій

МІНІСТЕРСТВО ОСВІТИ І НАУКИ, МОЛОДІ ТА СПОРТУ УКРАЇНИ

ЛЬВІВСЬКИЙ ІНСТИТУТ БАНКІВСЬКОЇ СПРАВИ

УНІВЕРСИТЕТУ БАНКІВСЬКОЇ СПРАВИ

НАЦІОНАЛЬНОГО БАНКУ УКРАЇНИ(м.Київ)

Кафедра економічної кібернетики

КОМПЛЕКСНА КУРСОВА РОБОТА

З дисципліни «Системи керування та адміністрування баз даних та сховищ даних»

на тему: «Задачі багатокритеріальної оптимізації в дослідженні операцій»

Студент Веселяка В.В.

м. Львів — 2013 рік

Зміст

Вступ

1. Сутність задачі багатокритеріальної оптимізації

1.1 Постановка задачі та математична модель задач багатокритеріальної оптимізації

1.2 Оптимальність за Парето

2. Проблеми і класифікація методів вирішення задач багатокритеріальної оптимальності

2.1 Інтерактивні методи вирішення задач багатокритеріальної оптимальності

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

2.3 Метод послідовних поступок

3. Приклад розв’язування багатокритеріальної задачі

4. Користувацька база даних Висновки Спиcок використаної літератури

Вступ

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

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

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

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

1. Сутність задачі багатокритеріальної оптимізації

1.1 Постановка задачі та математична модель задач багатокритеріальної оптимізації

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

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

. (1)

Знайти розв’язок, який одночасно був би найкращим за всіма критеріями, неможливо, тому що в загальному випадку покращення значення одного з критеріїв приводить до погіршення значення іншого[3].

Проілюструємо геометрично задачу оптимізації за двома критеріями. При цьому вважатимемо (як і всюди надалі, окрім окремих випадків), що критерії якості максимізуються.

Розглянемо загальну задачу оптимізації за двома критеріями з двома змінними:

(2)

Зобразимо область припустимих розв’язків у просторі змінних. Значення критеріїв відображатимемо у просторі критеріїв

Кожній конкретній точці множини припустимих рішень відповідатиме одне і лише одне значення кожного з критеріїв, хоча обернене твердження не завжди буде відповідати дійсності (декілька розв’язків можуть бути рівноцінними з точки зору значень критеріїв), тобто відповідне відображення буде гомоморфним[1].

Здійснивши таку операцію для всіх точок припустимої області в просторі змінних, отримаємо її образ в просторі критеріїв:

Рис. 1.1. Відображення припустимої області з простору змінних в простір критеріїв[4]

На рис. 1 розв’язки 4 та 5 відображаються в одну й ту ж саму точку в просторі критеріїв, тобто є ідентичними з точки зору їх якості. Крім того, вони є гіршими, ніж розв’язки 2 та 3, у яких значення кожного з критеріїв є більші, ніж у 4 та 5. Розв’язки 1, 2, та 3 є непорівняльними, тобто без додаткової інформації неможливо визначити, який із них є кращийзначення за одним з критеріїв для них є більші, а за іншим — менші.

В той же час, аналізуючи розв’язки, що знаходяться на кривій А-В-С, можна зробити висновок, що вони є множиною «найкращих» розв’язків: для будь-якого іншого розв’язку з множини припустимих завжди знайдеться хоча б один із розв’язків, що знаходяться на А-В-С та кращий за нього (тобто такий, що його домінує). Таким чином, розв’язки, що лежать на А-В-С, не домінуються ніякими іншими розв’язками, що належать до припустимої області.

Множина недомінованих розв’язків багатокритерійної задачі називається множиною Паретооптимальних розв’язків (саме Вільфредо Парето одним із перших досліджував задачі такого типу) і є, таким чином, у загальному випадку розв’язком багатокритерійної задачі. В свою чергу розв’язок належить до множини Парето-оптимальних, якщо він не домінується ніяким іншим[12].

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

У теорії багатокритеріальної оптимізації(БКО) вирішуються завдання прийняття рішень одночасно за кількома критеріями. Завдання БКО ставиться таким чином: потрібно знайти числа, які задовольняють систему обмежень

, (1.1) для яких функції

, (1.2) досягають максимального значення.

Безліч точок, що задовольняють систему (1.1), утворюють допустиму область. Елементи множини називаються припустимими рішеннями або альтернативами, а числові функції , — цільовими функціями або критеріями, заданими на множині D. У формулюванні задачі (1.1) — (1.2) наявні цільових функцій. Ці функції відображають множину в множині, яка називається множиною досяжності[8].

У векторній формі математичну модель БКО (1.1) — (1.2) можна записати таким чином:

при. (1.3)

Тут — вектор-функція аргументу.

Вперше проблема БКО виникла у італійського економіста В. Парето в 1904 р. при математичному дослідженні товарного обміну. Надалі інтерес до проблеми БКО посилився у зв’язку з розробкою і використанням обчислювальної техніки, і вже пізніше стало зрозуміло, що багатокритеріальні задачі виникають також і в техніці, наприклад, при проектуванні складних технічних систем .

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

Зважаючи на це в теорії БКО поняття оптимальності отримує різні тлумачення, і тому сама теорія містить три основні напрямки:

1. Розробка концепції оптимальності .

2. Доказ існування рішення, оптимального у відповідному сенсі.

3. Розробка методів знаходження оптимального рішення[3].

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

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

(1.4),

де — додатні чи від'ємні коефіцієнти. Додатні коефіцієнти відповідають тим критеріям, які потрібно максимізувати, а від'ємні — тим, які мінімізуються. Абсолютні значення коефіцієнтів відповідають пріоритету (важливості) того чи іншого показника[5].

Наприклад, якщо розв’язується виробнича задача, то з додатними коефіцієнтами ввійдуть такі величини, як обсяг прибутку, отриманого від реалізації товарів та послуг, з від'ємними — витрати ресурсів (часу, праці), собівартість одиниці продукції[15].

Узагальнений критерій може подаватись у вигляді дробу, де в чисельнику знаходиться добуток показників, які необхідно максимізувати, припустимо, а в знаменнику — добуток тих, які потрібно мінімізувати :

(1.5)

Загальним недоліком критеріїв (1.4), (1.5) є те, що існує можливість недостатню ефективність одного критерію компенсувати іншим. Наприклад, зниження значення виконання попередніх замовлень (в (1.5) буде в чисельнику) може компенсуватися зменшенням використання ресурсів (знаменник дробу (1.5)). Оскільки окремі величини в чисельнику та знаменнику пропорційно зменшилися, то значення дробу не змінюється, проте складені на основі таких розрахунків плани можуть призвести до негативних наслідків[11].

Такі критерії порівнюють із запропонованим Львом Толстим жартома «критерієм оцінки людини» у вигляді дробу, де в чисельнику зазначають справжні достоїнства людини, а у знаменнику — її думку про себе. Отже, якщо людина майже немає достоїнств (чисельник дробу буде малим числом) і водночас у неї зовсім відсутня зарозумілість (в знаменнику — майже нуль), то вона буде мати нескінченно велику цінність (оскільки будь-яке число, поділене на нескінченно малу величину, дає нескінченність)[].

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

1.2 Оптимальність за Парето

Якщо функції досягають максимум в одній і тій же точці, то говорять, що завдання (1.3) має ідеальне рішення.

Випадки існування ідеального рішення в багатокритеріальної задачі вкрай рідкісні. Тому основна проблема при розгляді завдання (1.3) — формалізація принципу оптимальності, тобто визначення того, в якому сенсі «оптимальне «рішення краще за інших. У разі відсутності «ідеального рішення «в задачі (1.3) шукається компромісне рішення.

Для всякої альтернативи вектор із значень цільових функцій є векторної оцінкою альтернативи. Векторна оцінка альтернативи містить повну інформацію про цінність (корисність) цієї альтернативи для головного конструктора системи, або, як прийнято говорити в системному аналізі, особи, що приймає рішення. Порівняння будь-яких двох фіналів замінюється порівнянням їх векторних оцінок[9].

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

У задачі БКО точка називається оптимальною по Парето, якщо не існує іншої точки, яка б переважала над. Точки, оптимальні за Парето, утворюють безліч точок, оптимальних за Парето (множину ефективних точок) .

Оптимальні рішення багатокритеріальної задачі слід шукати лише серед елементів множини альтернатив. У цій області жоден критерій не може бути поліпшений без погіршення хоча б одного з інших. Важливою властивістю множини Парето є можливість «вибраковувати «з множини альтернатив заздалегідь невдалі, які поступаються іншим за всіма критеріями. Зазвичай рішення багатокритеріальної задачі має починатися з виділення множини. При відсутності додаткової інформації про систему переваг головний конструктор повинен приймати рішення сам з множини Парето[12].

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

Часто рішення багатокритеріальної задачі полягає в побудові множини Парето — оптимальних точок і надалі виборі однієї з них на основі «здорового глузду» або з допомогою будь-якого іншого критерію .

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

Цільові функції відображають множину точок, оптимальних за Парето в множині, яка називається множиною Парето[13].

2. Проблеми і класифікація методів вирішення задач багатокритеріальної оптимальності

При вирішенні задач БКО доводиться вирішувати специфічні питання, пов’язані з невизначеністю цілей і критеріїв. Якщо перелічити основні проблеми, що виникають при розробці методів БКО, бачимо:

1. Проблема нормалізації критеріїв, тобто приведення критеріїв до єдиного (безрозмірного) масштабом виміру .

2. Проблема вибору принципу оптимальності, тобто встановлення, в якому сенсі оптимальне рішення краще за всіх інших рішень .

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

4. Проблема обчислення оптимуму завдання БКО. Мова йде про те, як використовувати методи лінійної, нелінійної, дискретної оптимізації для обчислення оптимуму завдань з певною специфікою[7].

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

Найбільш часто використовується заміна критеріїв їх безрозмірними відносними величинами:

де .

Нормалізовані критерії володіють двома важливими властивостями: по-перше, вони є безрозмірними величинами, і, по-друге, вони задовольняють нерівність для будь-кого. Ці властивості дозволяють порівнювати критерії між собою[10].

Основні методи, що застосовуються при вирішенні завдань БКО, представлені на рис. 2.1.

Рис .2.1. Класифікація методів вирішення багатокритеріальних завдань[3]

2.1 Інтерактивні методи вирішення задач багатокритеріальної оптимальності

В даний час набули поширення інтерактивні методи вирішення багатокритеріальних завдань, коли інформація про важливість і перевагах приходить як від інженерарозробника, так і від ЕОМ. Уточнення узагальнених критеріїв та упорядкування критеріїв за важливістю виробляється на основі діалогу конструктора з ЕОМ. Часто для визначення найкращого рішення конструктору доводиться вирішувати завдання структурної та параметричної оптимізації. При цьому модель прийняття рішення описується як завдання багатокритеріальної оптимізації. У цьому випадку використовують інтерактивний режим оптимізації або діалогової оптимізації. Розробник може змінити процес вирішення завдання на будь-якому етапі, параметри, метод вирішення, математичний опис завдання. Проблемами тут є розробка ефективних пакетів прикладних програм, сценаріїв діалогу, евристичних і точних алгоритмів проектування з урахуванням розпливчастості і невизначеності інтелектуальної діяльності інженерарозробника[7].

Метод аналізу ієрархії

Метод аналізу ієрархій (МАІ) — математичний інструмент системного підходу до складних проблем прийняття рішень.

МАІ не наказує особі, що приймає рішення, будь-якого «правильного» рішення, а дозволяє йому в інтерактивному режимі знайти такий варіант (альтернативу), який найкращим чином узгоджується з його розумінням суті проблеми та вимогами до її вирішення.

Цей метод розроблений американським математиком Томасом Сааті.

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

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

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

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

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

Порядок застосування методу аналізу ієрархій:

1) Побудова якісної моделі проблеми у вигляді ієрархії, що включає мету, альтернативні варіанти досягнення цілі і критерії для оцінки якості альтернатив.

2) Визначення пріоритетів всіх елементів ієрархії з використанням методу парних порівнянь.

3) Синтез глобальних пріоритетів альтернатив шляхом лінійної згортки пріоритетів елементів на ієрархії.

4) Перевірка суджень на узгодженість.

5) Прийняття рішення на основі отриманих результатів[5].

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

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

Ієрархічні структури, використовувані в МАІ, являє собою інструмент для якісного моделювання складних проблем.

Вершиною ієрархії є головна мета; елементи нижнього рівня представляють безліч варіантів досягнення мети (альтернатив); елементи проміжних рівнів відповідають критеріям або факторів, які пов’язують ціль з альтернативами.

Після побудови ієрархії учасники процесу використовують МАІ для визначення пріоритетів всіх вузлів структури. Інформація для розстановки пріоритетів збирається з усіх учасників і математично обробляється[14].

Рис.2.2.Найпростіша ієрархія МАІ

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

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

Розглянемо коротко деякі способи побудови ефективних множин. Для лінійних багатокритеріальних задач ефективне безліч векторів критеріїв повністю визначається вхідними в нього вершинами безлічі досяжності G (для безлічі ефективних рішень — ефективними вершинами D). Застосовуючи один з методів згортки з вагами і вирішуючи завдання з різними ненульовими значеннями ваг (побудувавши сітку ваг або параметрично), можна знайти багато (рідше — все) ефективні вершини. Зауважимо, що лінійна згортка дає тільки вершини, інші способи згортки можуть давати ефективні точки на ребрі або грані. Щоб отримати уявлення про всім ефективному безлічі, слід після знаходження чергового оптимального (ефективного) рішення знайти всі альтернативні оптимальні рішення, які існують, якщо серед оцінок небазисних змінних є нульові (вводячи по черзі ці змінні в базисне рішення, можна отримає всі вершини ефективної грані). Докладно і наочно ці питання розглянуті в книзі Р. Штойера. При відтворенні ефективної множини по вершинах потрібно пам’ятати, що через її неопуклість не всяка опукла комбінація ефективних вершин дає ефективну точку. Опукла комбінація ефективних вершин породжує трикутник ABC, хоча ефективними є тільки його сторони AB і BC. Для наочності подання ефективне безліч лінійної задачі можна проектувати на площину — воно буде мати вигляд одного або декількох багатокутників із загальними ребрами і вершинами (як розгортка тривимірної фігури). У кожної вершини може бути виведений відповідний критерійний вектор. Вибір найкращого рішення полегшиться, якщо ОПР, переміщаючи покажчик по представленому ефективному безлічі, отримуватиме значення критеріального вектора в точці покажчика або інше уявлення, приміром, у вигляді графіків, про поведінку вектора[10] .

Рис. 2.3.Опукла комбінація ефективних вершин

задача багатокритеріальна оптимізація На відміну від описаного способу метод обмежень можезастосовуватися як для лінійних, так і нелінійних багатокритеріальних задач. У критеріальному просторі будується сітка, значення критеріїв у вузлах якої виступають в якості обмежень на відповідні критерії. Для цього спочатку вирішується m однокритеріальних завдань (на максимум кожного приватного критерію), які дають діапазони зміни кожного критерію [] на ефективному множині. Сітка, що накладається на цей інтервал, включає S +1 вузол:

(2.1)

Потім для кожного критерію вирішуються завдання:

(2.2)

для всіх можливих поєднань з (2.4.). Чим дрібніше сітка, тим точніше можна представити ефективну множину. Основним недоліком даного методу є велике число розв’язуваних завдань. При цьому частина з них може виявитися нерозв’язною, а частина може дати лише слабо ефективні точки .

Рис. 2.4.Пошук ефективної множини

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

У завданнях з опуклою множиною D допустимих рішень і лінійними критеріями множина досяжності G опукла. У таких випадках легше побудувати усю множину G, ніж неопуклу ефективну множину. Водночас G дає повне уявлення про структуру останнього. Ця перевага особливо проявляється в лінійних багатокритеріальних задачах, так як багатогранну опуклу множину G можна описати у вигляді зручному для його побудови.

(2.3)

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

Для побудови множини G у вигляді (2.3) застосовують теорію лінійних нерівностей. Якщо розглянути нерівність

(2.4)

в якому v і w — k і l — мірні вектори змінних. Очевидно, що система (2.4) породжує в (k + l) — вимірному просторі деяку багатогранну множину M. Побудуємо на ньому множину Mw таких точок w'E¹, що для кожної знайдеться хоча б одна точка v' E^k, що утворює пару { v ', w '}, що задовольняє (2.4). Можна розглянути побудову М_w на прикладі простої системи з k = l = 1 :

1), 2), 3) ,

4), 5), 6) .

Множину Mw отримаємо, якщо виключимо змінну v, для чого слід скласти пари нерівностей з протилежними знаками при v (попередньо нерівність ділиться на коефіцієнт при v). B результаті цих перетворень маємо:

1) +2): , 1) +5):, 2) +4):, 2) +6): ,

3), 4) +5):, 5) +6): .

Спільне рішення нерівностей і дає множину Mw :

яке являє собою відрізок осі w, тобто ортогональну проекцію M на простір E¹. Цей метод може бути поліпшений шляхом використання процедури фільтрації несуттєвих обмежень в описі M_w .

Рис. 2.5. Спільне рішення нерівностей

Стосовно до лінійної задачі з n змінними і m критеріями багатогранне безліч в просторі E^n+m представляється у вигляді

(2.5)

Очевидно, що цікавить нас безліч G (аналог M_w) є ортогональною проекцією Z на критеріальний простір Е^m і може бути побудований розглянутим методом. Як зазначалося вище, у складних випадках замість точної множини G легше уявити її апроксимацію, але при цьому спрощена множина повинна мати ту ж ефективну множину, що і G.

Рис. 2.6. Двовимірні перетини (проекції) множини G

В якості ілюстрації на рис. 2.6. показані двовимірні перетини (проекції) множини G для задачі з 4 критеріями.

Інший спосіб побудови перетинів пов’язаний з поняттям оболонки Еджворта — Парето (ОЕП). Під ОЕП розуміється множина досяжності G разом з усіма домінуючими нею точками критериального простору. З визначення випливає, що множини Парето на G і ОЕП збігаються. Приклад ОЕП для задачі ЛП з двома критеріями наведено на рис. 2.7. ОПР пред’являються перетинине множини G, а оболонки Еджворта — Парето. В показано, що при цьому спрощується побудова перетинів і, що особливо важливо, на таких перетинах легше аналізувати підмножини Парето .

Рис. 2.7. Аналіз множини Парето

У практичних додатках методів вирішення багатокритеріальних завдань рідко використовується який-небудь один підхід в чистому вигляді, а комбінація підходів дозволяє краще пристосуватися до особливостей конкретної проблеми і ОПР. При цьому може виявитися особливо плідним поєднання інтерактивних процедур і методів подання досяжної (ефективної) множини з використанням засобів мультимедіа[17].

2.3 Метод послідовних поступок

Наступний спосіб носить назву методу послідовних поступок. Процедура вирішення багатокритеріальної задачі методом послідовних поступок полягає в тому, що всі приватні критерії розташовують і нумерують у порядку їх відносної важливості; максимізують перший, найважливіший критерій; потім призначають величину припустимого зниження значення цього критерію і максимізують другий за важливістю приватний критерій при умові, що значення першого критерію не повинно відрізнятися від максимального більш ніж на величину встановленого зниження (поступки); знову призначають величину поступки, але вже за другим критерієм і знаходять максимум третього за важливістю критерію за умови, щоб значення перших двох критеріїв не відрізнялися від раніше знайдених максимальних значень більше ніж на величини відповідних поступок; далі подібним же чином по черзі використовуються всі інші приватні критерії; оптимальної зазвичай вважають будь-яку стратегію, яка отримана при вирішенні задачі відшукання умовного максимуму останнього за важливістю критерію.. У цьому методі критерії нумеруються в порядку убування важливості. Нехай критерії записані в порядку зменшення їх важливості. Тоді повинні бути виконані наступні дії[13].

1 -й крок. Вирішується однокритеріальних завдання по 1 — му критерію

.

2 -й крок. Призначається розумна з інженерної точки зору поступка, складається і вирішується нова задача оптимізації за 2 — му критерію

.

3-й крок. Призначається поступка для 2 -го критерію, складається і вирішується завдання оптимізації за 3 — му критерію :

.

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

— й крок. Призначається поступка для — го критерію, складається і вирішується завдання оптимізації за останнім — му критерію

.

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

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

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

Як бачимо, в методі поступок передбачається, що різниця у важливості критеріїв не надто велика. Можна припустити, що величина поступок якось пов’язана з нашим відчуттям цієї різниці[8].

3. Приклад розв’язування багатокритеріальної задачі

Розв’язати задачу багатокритеріальної оптимізації

при обмеженнях Будується допустиму множину значень у вигляді многокутника. Графічно оптимальний розв’язок отримано за критерієм, який знаходиться в точці С (6;7). Йому відповідає. За другим критерієм оптимальний розв’язок буде в точці B (1;4). Йому відповідає значення. Тобто відрізок ВС є оптимальним ефективним планом.

Рис. 3.1. Допустима множина значень

Але якщо критерії рівноцінні (), то шукають компромісний розв’язок, який також забезпечує мінімальні витрати. Тоді функції витрат будуть:

Надалі записується еквівалентна задача мінімізувати при обмеженнях Після елементарних перетворень задача зводиться до задачі мінімізувати

Ця задача має 3 змінних і 7 обмежень, тому для спрощенння розв’язку переходять до двоїстої задачі, яка буде спряженою з даною.

при обмеженнях

Така задача розв’язується симплексним методом послідовними ітераціями, допоки усірізниці не будуть більшими або рівними 0.

В результаті розв’язування цієї задачі симплексним методом ми отримуємо розв’язок:

Цьому розв’язку відповідає точка F на відрізку BC. Йому відповідають мінімальні витрати і відхилення від оптимального значення для обох критеріїв:

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

Тому складається система рівнянь:

При вирішенні цієї системи .

Розв`язком є. Розв’язок співпадає з розв’язком симплексним методом, тобто задача розв’язана правильно.

Висновок

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

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

Багатокритеріальний підхід є методичним підґрунтям подолання певної міри неточності і неповноти початкових даних, які використовуються для вирішення оптимізаційних планових завдань діяльності підприємств.

Список використаної літератури

1. Ногин В. Д. Принятие решений в многокритериальной среде: количественный подход./ В. Д. Ногин — М.: «ФИЗМАТЛИТ», 2002.-176 с.

2. Лотов А. В., Поспелова И. И. Конспект лекций по теории и методам многокритериальной оптимизации/ А. В. Лотов, И. И. Поспелова — М: ВМиК МГУ, 2006 г. — 130 с.

3. Вагнер Г. Основы исследования операций./Г.Вагнер — М.: Мир, 1973.

4. Стернин М. Ю. Интерактивный поиск решений многокритериальной задачи о назначениях // Системы и методы поддержки принятия решений: Сб. тр./ М. Ю. Стернин — М.:ВНИИСИ., 1988.

5. Ларичев О. И., Стернин М. Ю. Человеко-машинные методы решения многокритериальной задачи о назначениях // Автоматика и телемеханика./О.И.Ларичев, М. Ю. Стернин — М.:Институт системного анализа РАН,1998. № 7- 135−156с.

6. Штойер Р. Многокритериальная оптимизация: теория, вычисления, приложения./Р.Штойер — М.: Наука, 1982.

7. Исаев С. А. Десертация «Решение многокритериальных задач». /С.А.Исаев — Н. Новгород, 2000.

8. Трифонов А. Г. Многокритериальная оптимизация./А.Г.Трифонов // Інтернет ресурс: http://matlab.exponenta.ru/optimiz/book₁/16.php

9. Вентцель Е. С. Исследование операцій. Задачи, принципы, методология./Е.С. Вентцель — М.:Наука, 1988.-206с.

10. Оспіщев В.І., Бурко Д. Л. Дослідження операцій, Навчальний посібник/В.І.Осріщев, Д. Л. Бурко — Харків.:ХНАМГ, 2008.-117с.

11. Катренко А. В. Дослідження операцій: Підручник./А.В.Катренко — Львів: Магнолія Плюс, 2004.

12. Волков И. К., Загоруйко Е. А. Исследование операций: Учебник./И.К.Волков, Е. А. Загоруйко — М.: МГТУ им. Н. Э. Баумана, 2002.

13. Зайченко Ю. П. Дослідження операцій./Ю.П.Зайченко — Київ:Видавничий Дім «Слово», 2006. — 816 с.

14. Ржевський С. В., Александрова В. М. Дослідження операцій, Акадевидав/С.В.Ржевський, В. М. Александрова — Київ, 2006 — 362с.

15. Соболь И. М., Статников Р. Б. «Выбор оптимальных параметров в задачах со многими критериями"/И.М.Соболь, Р. Б. Статников — М., 1985, 112с.

16. КутковецькийВ.Я. Методи розв’язання задач дослідження операцій: Монографія./В.Я. Кутковецький — Миколаїв: Вид-во ЧДУімені ПетраМогили, 2010. — 164 с.

17. Семенова Н. В., Колєчкiна Л. М., Нагiрна А. М., Доповідь НАН Багатокритерiальнi задачi/ Н. В. Семенова, Л. М. Колєчкiна, А. М. Нагiрна, 2010.