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

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

Размещено на

Размещено на

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

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

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

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

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

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

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

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

Студент

Веселяка В.В.

м. Львів - 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)

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

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

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

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

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

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

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

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