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

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

 

2.4 Методи багатокритеріальної  оптимізації

 

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

Але яку, однак, ефективну альтернативу вибирати? Звичайно, якщо множина абсолютно-оптимальних  альтернатив не є порожньою, то будь-яка  з них (слід нагадати, що всі абсолютно-оптимальні альтернативи рівноцінні між собою) може вважатися розв'язком багатокритеріальної  задачі. Як було з'ясовано вище, на практиці такі задачі зустрічаються досить рідко. Таким чином, потрібно вирішити, що робити у випадку, коли множина абсолютно-оптимальних  альтернатив є порожньою. Оскільки ефективні альтернативи є непорівнянними між собою за перевагою, яка задається  критеріями задачі, а якимось чином  їх необхідно порівняти, то для цього  потрібна додаткова інформація окрім  тієї, яка є при порівнянні альтернатив  за кожним критерієм окремо. Точніше, для порівняння ефективних альтернатив, потрібна додаткова інформація про  перевагу не на множині альтернатив, а на множині критеріїв, тобто  інформація такого типу: скількома  одиницями виграшу за одними критеріями можна компенсувати програшем за іншими критеріями. Джерелом такої  інформації може бути як ОПР, так і  специфіка предметної області, в  якій розв'язується задача прийняття  рішення.

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

Нехай – множина альтернатив багатокритеріальної задачі:

,

яка задовольняє  правилу вибору R. Сформулюємо умови, яким це правило повинно задовольняти у загальному випадку (так звані умови раціональності, сформульовані Вільгельмом [1]).

1. Вибір повинен бути  зробленим завжди, тобто  .

2. Вибирається ефективна  альтернатива, тобто .

3. Єдиність вибору потрібно  розуміти не буквально, що обов'язково  вибрати тільки одну альтернативу. Будемо вважати, що правило  вибору R однозначно визначає розв'язок багатокритеріальної задачі, якщо всі альтернативи, що задовольняють цьому правилу є рівноцінними, тобто якщо , то ~ .

4. Більше того, якщо ми вибираємо  якусь альтернативу, для якої  у множині альтернатив є рівноцінна, то і вона повинна вибиратися  цим же правилом вибору, тобто  якщо  ~ , то .

5. Якщо розглядати дві  ситуації прийняття рішення за  одним і тим же вектором  критеріїв f, але на множинах альтернатив таких, що одна з множин X' є підмножиною іншої X, то вибір з "більш широкої" множини альтернатив X, якщо він належить "більш вузькій" множині альтернатив , повинен бути вибором з цієї множини. Тобто якщо , то .

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

1. Правила вибору, які безпосередньо визначені на множині ефективних альтернатив, тобто . Перевагою таких правил є їх простота, а суттєвим недоліком – необхідність побудови усієї множини ефективних альтернатив.
2. Правила вибору, які є суперпозицією двох правил вибору: правила вибору , що є визначеним на множині альтернатив і вибирає деяку підмножину альтернатив, яка містить як ефективні, так і неефективні альтернативи, і правила вибору , що є визначеним на множині вже попередньо вибраних альтернатив і вибирає тільки ефективну альтернативу. Такий розподіл правила вибору на два правила в деяких практичних ситуаціях дозволяє реалізувати досить ефективний вибір.
3. Діалогові процедури вибору. Цей клас правил вибору враховує той факт, що формалізація правила вибору в багатьох практичних ситуаціях прийняття рішень ускладнюється наявністю "людського" фактору. Справа в тому, що навіть припускаючи наявність у ОПР якоїсь системи переваг, може статися так, що ОПР не завжди її усвідомлює і ця система переваг може усвідомлюватися (формуватися) ОПР тільки у процесі прийняття рішення, змінюючись з часом змінюватися. Тому, якщо вибрано якусь альтернативу, її вже після вибору потрібно перевірити на відповідність перевагам ОПР (які вже можуть змінитися) і при необхідності підкоректувати правило вибору.

Ці міркування приводять  до необхідності створення правил вибору у вигляді діалогової процедури, яка являє собою ітеративний  процес взаємодії між ОПР і  комп'ютером. Кожна ітерація i, i=1,2,…, складається з двох етапів [11]:

1. Обчислювальний етап. На цьому етапі комп'ютер використовує отриману від ОПР інформацію для побудови (корекції) правила вибору, визначає ефективну альтернативу і формує допоміжну інформацію для визначення переваг ОПР.
2. Етап прийняття рішення. ОПР аналізує отриману від комп'ютера ефективну альтернативу та допоміжну інформацію. Якщо ця інформація задовольняє ОПР, то ОПР приймає рішення про вибір , у протилежному випадку дає нову інформацію для комп'ютера, завдяки якій буде робитися інший вибір і т.д.

Методи  багатокритеріальної оптимізації  являють собою чисельну реалізацію певного правила вибору ефективної (слабко-ефективної, власно-ефективної) альтернативи, тому цілком природньо  класифікувати їх за типами інформації, яку дає ОПР для формування правила вибору. Розглянемо наступну класифікацію [12]:

Методи багатокритеріальної оптимізації.

Методи, які не використовують інформацію про перевагу на множині критеріїв.

Методи, які використовують один тип  інформації про перевагу на множині  критеріїв.

Методи, які використовують різні  типи інформації про перевагу на множині  критеріїв.

Спеціальні методи.

 

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

 

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

0-й крок. Розраховуються "найкращі" і "найгірші" значення критеріїв: , здійснюється монотонне перетворення критеріїв до нормованого безрозмірного вигляду:

.

k-й крок (k=1,2,…). ОПР аналізує отриманий на попередньому кроці розв'язок та його оцінку у порівнянні з "найкращими" і "найгіршими" значеннями критеріїв і вказує бажані значення критеріїв

Здійснюється перетворення бажаних значень цільових функцій  до нормованого безрозмірного вигляду  [2].

Обчислюються  вагові коефіцієнти критеріїв:

.

Ефективна альтернатива знаходиться як розв'язок однокритеріальної задачі: . Обчислюється оцінка . Якщо отримані значення цільових функцій задовольняють ОПР, то процедура закінчується, у протилежному випадку – переходимо на наступний крок. Цей метод використовує тільки один тип інформації від ОПР про бажані значення критеріїв [13].

Приклад 2.1. Розв'язати методом бажаної точки наступну задачу:

На рисунку  1.3 зображена множина альтернатив X; лінії рівнів першого й другого критеріїв, відповідно (1), (2); – найкращі, відповідно за першим і другим критерієм задачі, альтернативи.

0 –й крок. Обчислюємо "найкращі" і "найгірші" значення критеріїв: і здійснимо монотонне перетворення критеріїв до нормованого безрозмірного вигляду:

 

 

 

 

 

 

 

Рис. 1.3

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

Обчислюються вагові коефіцієнти критеріїв:

.

Ефективну альтернативу знаходимо як розв'язок задачі:

На рисунку 1.4 можна побачити лінії рівнів і цієї функції, які утворюють кути вершини яких x i x* знаходяться на прямій , що визначається умовою рівності аргументів функції , а бокові сторони паралельні лініям рівня відповідних критеріїв початкової двохкритеріальної задачі. Рівень буде максимальним значенням функції, а точка буде оптимальним розв'язком цієї задачі. Обчислюємо оцінку . Якщо отримані значення критеріїв задовольняють ОПР, то процедура закінчується, у протилежному випадку – переходимо на наступний крок.

 

 

 

 

 

 

 

Рис. 1.4

Далі цей метод реалізовано  програмно. Для знаходження мінімумів  однонокритеріальних задач використовується градієнтний метод, а для знаходження  максимумів та максиміна – метод  Монте-Карло.

 

РОЗДІЛ 3. ПРАКТИЧНА РЕАЛІЗАЦІЯ

 

3.1 Блок-схема алгоритму

 

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

 

Рис. 2.1 – Блок-схема алгоритму методу бажаної точки

 

 

Рис.2.2 – Продовження блок-схеми алгоритму методу бажаної точки

 

Рис. 2.3 – Продовження блок-схеми алгоритму методу бажаної точки

 

3.2 Опис програми 

 

Для розв’язування поставленої  задачі була створена програма на мові Object Pascal в середовищі Delphi 6.

В якості прикладу було взято  задачу:

,

,

.

Критерії  і були задані в програмі (див. підпрограми function f (x1, x2 ,x3:real):real і function t (x1, x2, x3:real):real в модулі Unit3).

Мінімальне значення , критеріїв шукається за допомогою градієнтного методу (див. процедуру GradientMethod в модулі Unit2).

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

Для розв’язування задачі градієнтним методом необхідно  знати перші похідні по всім змінним  для кожного критерію.

Для нашого прикладу:

 

;

 

;

 

;

 

;

 

;

 

.

 

Значення похідних були задані функціями (див. модуль Unit3):

• function df_dx1 (x1,x2,x3:real):real  для ;
• function df_dx2 (x1,x2,x3:real):real  для ;
• function df_dx3 (x1,x2,x3:real):real  для ;
• function dt_dx1 (x1,x2,x3:real):real для ;
• function dt_dx2 (x1,x2,x3:real):real для ;
• function dt_dx3 (x1,x2,x3:real):real для .

Точність знаходження  оптимального розв’язку задається  в програмі значенням константи epsilon=0.001.

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

В програмі є обмеження  на кількість ітерацій. Оскільки, кількість  ітерацій наперед невідома, то вона була задана фіксованим числом, достатньо  великим для того, щоб метод  працював, а саме: константою SIZE=10000. Якщо ітерацій буде більше, то програма видасть повідомлення про це і  завершить роботу. В цьому випадку  слід взяти іншу початкову точку  і знову запустити програму.

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

Знаходження максимальних значень  , критеріїв було реалізовано в процедурі MethodBaganTochki (див. модуль Unit2). Змінна max_f буде зберігати максимальне значення критерію . Змінна max_t –– , максимальне значення  критерію .

Розв’язування однокритеріальної  задачі  було здійснено наближеним методом, а саме: методом Монте-Карло.

В програмі метод Монте-Карло  реалізовано процедурою MethodMonteKarlo (див. модуль Unit2) наступним чином.

10001 раз випадково генеруються точки в діапазоні . Генеруються за допомогою датчика випадкових чисел за нормальним законом розподілу (це досягається вбудованими в Delphi підпрограмами Randomize і Random). Кожен раз, коли  були згенеровані нові точки , обчислювалось і . З них вибирався мінімум. А після, програма знайшла найбільше значення з 10001 знайдених, і точку , яка дала цей максимум.

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