Реферат на тему:
Дослідження операцій. Багатокритеріальні задачі в менеджменті
План
Основні поняття та постановка задачі.
Методи згортання критеріїв. Метод ідеальної точки.
Поняття про діалогові методи.
КЛЮЧОВІ ПОНЯТТЯ ТА ТЕРМІНИ
невизначеність мети
багатокритерійна задача ДО
простір критеріїв
згортання критеріїв
метрика простору
множина Парето-оптимальних розв’язків
простір змінних
діалоговий метод
ідеальна точка
поступка за критерієм
контрольний показник
переведення критерію в обмеження
Основні поняття та постановка задачі.
На практиці задачі, що не мають невизначеностей, є скоріше вийнятком,
аніж правилом. Поряд із розглянутими вище існує ще один важливий вид
невизначеності – невизначеність мети, що виявляється у наявності
декількох, в більшості випадків незбіжних аспектів оцінки якості того чи
іншого розв’язку з множини припустимих. У формальному вигляді аспекти
оцінки якості відображаються за допомогою множини критеріїв.
Таким чином виникає багатокритерійна задача дослідження операцій,
загальний вигляд якої наступний:
. (1)
Знайти розв’язок, який одночасно був би найкращим за всіма критеріями,
неможливо, тому що в загальному випадку покращення значення одного з
критеріїв приводить до погіршення значення іншого.
Проілюструємо геометрично задачу оптимізації за двома критеріями. При
цьому вважатимемо (як і всюди надалі, окрім окремих випадків), що
критерії якості максимізуються.
Розглянемо загальну задачу оптимізації за двома критеріями з двома
змінними:
(2)
, хоча обернене твердження не завжди буде відповідати дійсності
(декілька розв’язків можуть бути рівноцінними з точки зору значень
критеріїв), тобто відповідне відображення буде гомоморфним. Здійснивши
таку операцію для всіх точок припустимої області в просторі змінних,
отримаємо її образ в просторі критеріїв:
Рис. 1. Відображення припустимої області з простору змінних в простір
критеріїв
На рис. 1 розв’язки 4 та 5 відображаються в одну й ту ж саму точку в
просторі критеріїв, тобто є ідентичними з точки зору їх якості. Крім
того, вони є гіршими, ніж розв’язки 2 та 3, у яких значення кожного з
критеріїв є більші, ніж у 4 та 5. Розв’язки 1, 2, та 3 є
непорівняльними, тобто без додаткової інформації неможливо визначити,
який із них є кращий -значення за одним з критеріїв для них є більші, а
за іншим – менші.
В той же час, аналізуючи розв’язки, що знаходяться на кривій А-В-С,
можна зробити висновок, що вони є множиною “найкращих” розв’язків: для
будь-якого іншого розв’язку з множини припустимих завжди знайдеться хоча
б один із розв’язків, що знаходяться на А-В-С та кращий за нього (тобто
такий, що його домінує). Таким чином, розв’язки, що лежать на А-В-С, не
домінуються ніякими іншими розв’язками, що належать до припустимої
області.
Множина недомінованих розв’язків багатокритерійної задачі називається
множиною Парето- оптимальних розв’язків (саме Вільфредо Парето одним із
перших досліджував задачі такого типу) і є, таким чином, у загальному
випадку розв’язком багатокритерійної задачі. В свою чергу розв’язок
належить до множини Парето-оптимальних, якщо він не домінується ніяким
іншим.
Побудова множини Парето-оптимальних розв’язків для задач ДО в більшості
випадків є неможливою внаслідок значних обчислювальних труднощів. Крім
того, в більшості випадків завдання полягає в знаходженні одного
розв’язку. Такий розв’язок повинен належати до множини
Парето-оптимальних, а ось яким він повинен бути, може виявитися лише в
процесі його побудови. Тому був розроблений та застосовується на
практиці цілий ряд методів, деякі з них розглядаються нижче.
Методи згортання критеріїв. Метод ідеальної точки.
Одним із найрозповсюдженіших способів є приведення множини критеріїв до
одного глобального та розв’язування класичної однокритерійної задачі.
Однак застосування цього підходу має суттєві вади, і однією з них є те,
що отриманий розв’язок для деяких специфічних задач може навіть не
належати до множини Парето-оптимальних.
Методи згортання критеріїв приводять первісну задачу до однокритерійної
задачі такого вигляду:
.
Найвживанішими є:
лінійне згортання
(3)
лінійне згортання нормованих критеріїв:
(4)
В цих методах сі — вагові коефіцієнти критеріїв, які повинні відображати
їх важливість,
— мінімальне та максимальне значення і-го критерію.
Основною проблемою цих методів є проблема виявлення точних значень
вагових коефіцієнтів – ця процедура в більшості випадків є суб’єктивною.
Окрім того, коефіцієнти в методі лінійного згортання повинні бути
розмірними величинами, тому що критерії в більшості випадків мають різну
розмірність. З метою позбавлення від цього недоліку в згортанні
нормованих критеріїв окремі критерії спочатку нормуються (нормовані
критерії є безрозмірними та змінюються в інтервалі від 0 до 1). Але
внаслідок такого “вдосконалення” з’являються нормовані критерії, які не
мають змістовного навантаження, і тому об’єктивне визначення вагових
коефіцієнтів ще більш ускладнюється. Таким чином довільність (що
викликана багатокритерійністю) переноситься в іншу інстанцію
(визначення числових значень вагових коефіцієнтів).
Інший підхід до розв’язання проблеми багатокритерійності -аксіоматичний
– полягає в формулюванні множини аксіом з наступним формальним
виведенням виду функції корисності (глобального критерію), за допомогою
якого й здійснюватиметься остаточний вибір. У цьому випадку виявляються
всі обмеження, які побічно накладаються при еврістичному застосуванні
того чи іншого методу. Виявляється, що лінійне згортання обгрунтоване
при достатньо жорстких аксіоматичних умовах, які в багатьох випадках не
виконуються.
Окрім того, існують й інші методи згортання – такі, як метод ідеальної
точки. Метод ідеальної точки базується на тому, що постулюється
існування “ідеальної точки” для розв’язку задачі, у якій досягається
екстремум усіх критеріїв (принцип Джофріона). Так, на рис. 1 ідеальною є
точка D в просторі критеріїв, якій не відповідає жоден припустимий
розв’язок простору змінних. Оскільки ідеальна точка в абсолютній
кількості випадків не знаходиться серед припустимих, виникає проблема
знаходження точки, що “найближча” до ідеальної і належить до множини
припустимих. Все було би добре, якщо б існувало єдине об’єктивне поняття
“віддалі”, однак це не так – якщо на площині ми можемо з тим чи іншим
обгрунтуванням застосовувати Евклідову метрику, то, наприклад, на
поверхні кулі (земної також!) найкоротшою віддаллю буде дуга, а не
пряма.
Таким чином, для розв’язання задачі за допомогою методу “ідеальної
точки” необхідно насамперед визначити її координати, і надалі визначити
метрику, за допомогою якої можна було б виміряти віддаль до оптимальної
точки. Для визначення координат “ідеальної точки” розв’язуємо п
однокритерійних задач за кожним з критеріїв оптимізації
Сукупність оптимальних значень критеріїв кожної з однокритерійних задач
і визначить координати ідеальної точки
в просторі критеріїв. Якщо “ідеальна точка” належить до множини
припустимих (що зустрічається вкрай рідко), то розв’язок отриманий.
В іншому випадку визначаємо “віддаль” до ідеальної точки, вводячи
метрику, і розв’язуємо однокритерійну задачу знаходження точки з числа
припустимих, яка найменш віддалена від ідеальної. Таким чином задача
матиме вигляд
Якщо обрана Евклідова метрика, то критерій буде мати вигляд:
(5)
Переведення критеріїв в обмеження.
Контрольні показники. Метод послідовних поступок.
Одним із найзрозуміліших змістовно є метод переведення критеріїв в
обмеження, що полягає у виділенні головного критерію Q1 (x) , за яким
проводитиметься оптимізація, нормативних значень QіN для кожного з
критеріїв, що залишилися (значення критерію не може бути меншим за
нормативне), та розв’язуванні отриманої таким чином однокритерійної
задачі оптимізації:
(6)
Основними проблемами при застосуванні цього методу є складнощі з
визначенням головного критерію та нормативних значень для інших
критеріїв. Якщо нормативні значення обрані недостатньо великими, то не
всі резерви покращення їх значень будуть використані, якщо ж ці значення
будуть завеликими, то задача взагалі не буде мати розв’язків, оскільки
область припустимих рішень виявиться пустою.
Метод контрольних показників дозволяє позбутися деяких проблем,
притаманних методу переведення критеріїв в обмеження. Система нормативів
задається для всіх критеріїв, і критерій якості представляється у
вигляді:
&
&
&
H
l
?
?
ae
??
$
&
F
H
j
l
?
?
?
?
a
ae
$&2|~?,
.
?
TH
a
*ae
? (7)
Але й у цьому випадку залишається проблема обгрунтування значень
нормативів і додається проблема знаходженння розв’язку максимінної
задачі.
Метод послідовних поступок є одним із найобгрунтованіших змістовно, і за
умови відсутності суперечностей в перевагах особи, що приймає рішення,
може дати добрий результат. Насамперед критерії впорядковуються ОПР за
важливістю в порядку її спадання:
і таким
чином на ( і+1 )-му кроці розв’язуватиметься задача:
(8)
Процес розв’язування закінчується у випадках, коли або досягнуто
останнього критерію, або ж призначення поступки недоцільне. У випадку
необхідності процес можна повторити, здійснивши аналіз попередніх
результатів. Таким чином, метод послідовних поступок є достатньо гнучким
і дозволяє уникнути багатьох проблем, властивих іншим методам. Для його
реалізації достатньо мати ефективний метод розв’язування однокритерійної
задачі потрібного типу.
Поняття про діалогові методи.
Діалогові методи належать до групи найгнучкіших методів пошуку розв’язку
багатокритерійних задач. Характерною рисою цих методів є участь у
процесі розв’язування особи, що приймає рішення, а це дозволяє
скорегувати перебіг рішення та врахувати деякі неформальні моменти. У
принципі, момент діалогу присутній уже в методі послідовних поступок –
на кожному кроці алгоритм звертається до ОПР з метою отримання значення
поступки для того чи іншого критерію. Надалі з метою ілюстрації
розглянемо схеми деяких з діалогових методів.
Доводі розповсюдженим є алгоритм розв’язування, запропонований
Джофріоном та модифікований багатьма дослідниками, що використовує ідеї
добре відомого градієнтного методу. Робота алгоритму починається з
будь-якої точки припустимої області. На кожному етапі з залученням ОПР
визначається напрям руху в просторі критеріїв та довжина кроку в цьому
напрямку. Напрямок руху (еквівалент градієнту) визначається шляхом
опитування ОПР щодо значень коефіцієнтів заміщення критеріїв в біжучій
точці (проводиться опитування – яким значенням зміни по одному з
критеріїв можна скомпенсувати зміну іншого критерію). Звичайно, що
напрямок руху залежатиме від координат точки в просторі критеріїв. Після
цього ОПР задає величину кроку в заданому напрямку і здійснюється –
якщо його значення приводить до виходу за межі припустимої і в просторі
змінних, величина кроку зменшується, щоб отримана точка належала до
області припустимих значень. Процедура повторюється, поки ОПР не
зупинить її виконання, або поки не будуть виконані формальні умови
зупинки. Цей метод висуває високі вимоги до ОПР відносно виявлення
значень коефіцієнтів заміщень критеріїв.
Іншу групу методів утворюють методи поступового звуження множини
розв’язків, що належать до множини Парето-оптимальних.
Розглянемо діалоговий алгоритм розв’язування двокритерійної задачі
оптимізації:
(9)
Розв’яжемо пару однокритерійних задач оптймізації по кожному з критеріїв
і підстановкою відповідних оптимальних значень змінних визначимо іншу
координату в просторі критеріїв:
Ці кроки виконуються без втручання ОПР, і ОПР пред’являється графічне
зображення (рис. 2) з координатами трьох точок в області критеріїв, а
також ставиться запитання: В якому напрямку від середньої точки
необхідно рухатися по осі критерію Q1 ? В залежності від відповіді
інтервал пошуку звужується, переіндексовуються крайні точки, шукаються
координати середньої точки і процедура опитування повторюється. Цікаво
відзначити, що в цьому випадку по суті звужується область
Парето-оптимальних розв’язків, але при цьому ОПР не повинен знати її
конфігурацію.
Рис. 2. Послідовність кроків при пошуку оптимального розв’язку
двокритерійної задачі за допомогою діалогового методу
Приклад.
Побудова множини Парето-оптимальних розв’язків, вибір кращої
альтернативи згортанням критеріїв.
Необхідно визначити множину Парето-оптимальних альтернатив, обрати
найкращу з використанням лінійної згортки критеріїв з вагами 0.3 та 0.7
та за методом ідеальної точки, якщо критерії задані наступним чином:
а координати альтернатив в просторі змінних задані наступною таблицею:
№ 1 2 3 4 5 6
x1 1 3 0 -1 6 8
x2 2 1 3 2 1 -2
Розв’язання.
Послідовність розв’язання цієї задачі в загальному є наступною: спочатку
розраховуємо значення двох критеріїв. Для кожної з 6 альтернатив (тобто
будуємо образи кожної з альтернатив в просторі критеріїв); далі – для
побудови множини Парето – оптимальних альтернатив виключаємо з наведеної
множини послідовно доміновані альтернативи – поки не дійдемо до
останньої. Лінійну згортку будуємо, використовуючи образи альтернатив в
просторі критеріїв. Всі необхідні розрахунки зведені в наступну таблицю:
№ альтернативи 1 2 3 4 5 6
Q1 6 7 9 2 13 20
Q2 0 -17 3 0 -71 -130
Парето-оптимальні альтернативи – – + – + +
Q згортки 1,8 -9,8 4,8 0,6 -45,8 -85,0
Парето-оптимальні альтернативи визначаємо, порівнюючи біжучу
альтернативу зі всіма наступними. Якщо зустрічається альтернатива, що
домінується біжучою, то вона виключається з подальшого розгляду. Якщо ж
така альтернатива домінує біжучу, то біжуча виключається з розгляду,
здійснюється перехід до альтернативи, наступної за біжучою і не
виключеної з розгляду. Процес повторюється до моменту, поки біжучу
альтернативу не буде з чим порівнювати.
Починаємо з альтернативи 1. Вона непорівняльна з альтернативою 2.
Порівнюємо 1 з наступною – 3.
3 домінує 1 – тому переходимо до наступної невиключеної за 1
альтернативи -2, а 1 виключаємо з розгляду. Альтернативу 2 порівнюємо з
наступною невиключеною -3, 3 домінує 2, тому виключаємо 2 і переходимо
до 3 як до біжучої альтернативи. З домінує 4 – тому 4 виключаємо. 3
непорівняльна з 5, та 3 непорівняльна з 6 — і отже – оскільки наступні
альтернативи відсутні – 3 належить до множини Парето-опти-мальних.
Наступна біжуча альтернатива – 5, яка непорівняльна з 6. Таким чином,
множину Парето-оптимальних альтернатив складають рішення за номерами
3,5, та 6.
Обчислимо значення критерія-згортки для кожної з 6 альтернатив.
Наприклад, для альтернативи 1:
Обираючи максимальне значення, вважаючи, що аргументом є номер
альтернативи, отримаємо:
тобто за критерієм згорткою кращою є альтернатива 3.
Приклад.
Визначення найкращого розв’язку методом переведення критеріїв в
обмеження.
Q1 Q2 Q3
A1 2 4 8
A2 4 3 14
A3 7 8 2
A4 5 6 6
A5 8 4 4
A6 3 6 12
Розв’язання.
тобто обираємо А4 .
Література
Карлин С. Математические методы в теории игр, программировании и
экономике. -М.: Мир, 1964.
Вентцель Е.С. Введение в исследование операций. Сов. радио, 1964.
Пономаренко О.І., Пономаренко В.О. Системні методи в економіці, бізнесі
й менеджменті. -К.: Либідь, 1995.
Пономаренко О.І., Перестюк М.О., Бурим В.М. Основи математичної
економіки. -К.: Інформтехніка, 1995.
Горелик В.А., Ушаков М.А. Исследование операций. -М.: Машиностроение,
1986.
PAGE
PAGE 12
X2
Q2
Q1
X1
A
D
C
B
4,5
1
2
3
1
2
3
4
5
Простір змінних
Простір критеріїв
Q2
Q1
Q(2)
Q(3)
Q(1)
Q2
Q(2)
Q(3)
Q(1)
Q1
Нашли опечатку? Выделите и нажмите CTRL+Enter
