ІНФОРМАЦІЙНІ ТЕХНОЛОГІЇ РІШЕННЯ ЗАДАЧ ВЕКТОРНОЇ ОПТИМІЗАЦІЇ
План:
Введення
Принцип оптимальності Парето. Неулучшаемие (оптимальні за Парето) рішення
Принцип рівноваги по Нешу
Конфлікти, переговори та компроміси
Короткий огляд методів рішення задачі векторної оптимізації
Введення
На відміну від задач обгрунтування рішень по скалярному критерієм, результатом яких є оптимальна (з точністю до передумов і припущень моделі) стратегія, в задачах з векторним критерієм виявляється неможливо з абсолютною впевненістю стверджувати, що те чи інше рішення, дійсно (об'єктивно) оптимально. Одне з рішень може перевершувати інше по одних критеріях і поступатися йому по іншим. Сказати, яке з двох рішень в зазначених умовах об'єктивно краще іншого, не представляється можливим. Тільки з часом буде ясно, наскільки вірним було прийняте рішення; поки ж, до реалізації рішення, особисті переваги ОПР, його досвід і інтуїція є тією основою, яка визначає здатність ОПР передбачати наслідки прийнятого ним компромісу.
Таким чином, складність проблеми прийняття рішень по векторному критерію навіть в умовах визначеності пов'язана не стільки з обчислювальними труднощами, скільки з концептуальної обгрунтованістю вибору оптимального рішення. Неможливо строго математично довести, що вбрання рішення найкраще, - будь-яке рішення з числа недомініруемих, тобто неулучшаемих одночасно по всім приватним критеріям, може виявитися найкращим для конкретного ОПР в конкретних умовах. З тієї ж точки зору не має сенсу говорити про найкращому рішенні взагалі. Це може вважатися аксіомою обгрунтування рішень за кількома критеріями.
Порівняння альтернатив за векторному критерію здійснюються за наступним правилом: всяка альтернатива не гірше будь-якої іншої, якщо для неї значення векторного критерію не менше переважно, ніж значення критерію іншої альтернативи, тобто:
де - альтернативи; - векторний критерій; - символ відносини нестрогого переваги.
Припустимо, що множинність критеріїв пов'язана з наявністю декількох сторін, зацікавлених у вирішенні проблемної ситуації. Кожна сторона прагне знайти і прийняти рішення, при якому її показник ефективності (цільова функція) був би найбільшим. Очевидно, величина показника ефективності кожної сторони залежить від рішень всіх інших сторін. Тому найбільш ефективні для однієї сторони рішення не є такими для інших. У зв'язку з цим, прагнення кожної сторони домагатися найбільшої ефективності прийнятих нею рішень носить конфліктний характер і саме формулювання того, яке рішення є прийнятним, хорошим або найкращим (оптимальним), проблематична.
Розгляд складних економічних об'єктів, що характеризуються цілим спектром характеристик, призводить до необхідності введення понять локального та глобального критеріїв оптимальності. При цьому математично глобальний критерій формулюється у вигляді скалярною цільової функції, яка узагальнено виражає розмаїття цілей, або в вигляді векторної функції, що представляє собою набір несвідомих один до одного приватних цільових функцій (локальних критеріїв).
Слід зазначити, що множинність цілей розвитку економічних систем суттєво ускладнює планування, особливо якщо цілі різноспрямовані, і наближення до одним цілям видаляє систему від досягнення інших. В результаті виникає завдання їх узгодження. Метою багатокритеріальної або векторної оптимізації і є відшукання найкращих рішень за кількома критеріями.
Серед безлічі багатокритеріальних задач можна виділити завдання чотирьох типів:
Завдання оптимізації на безлічі цілей, кожна з яких повинна бути врахована при виборі оптимального рішення. Прикладом може служити завдання складання плану роботи підприємства, в якої критеріями служить ряд економічних показників;
Завдання оптимізації на множині об'єктів, якість функціонування кожного з яких оцінюється самостійним критерієм. Якщо якість функціонування кожного об'єкта оцінюється декількома критеріями (векторним критерієм), то така задача називається багатовекторною. Прикладом може служити задача розподілу дефіцитного ресурсу між декількома підприємствами. Для кожного підприємства критерієм оптимальності є ступінь задоволення його потреби в ресурсі або інший показник, наприклад, величина прибутку. Для плануючого органу критерієм виступає вектор локальних пріоритетів підприємств;
Задача оптимізації на безлічі умов функціонування. В задачах такого типу заданий спектр умов, в яких належить працювати об'єкту, і стосовно до кожного умові якість функціонування оцінюється деяким приватним критерієм;
Завдання оптимізації на безлічі етапів функціонування. Розглядається функціонування об'єктів на деякому інтервалі часу, розбитому на кілька етапів. Якість управління на кожному етапі оцінюється приватним критерієм, а на безлічі етапів - загальним векторним критерієм. Прикладом може служити розподіл квартального плану цеху по декадах. У кожній декаді необхідно забезпечити максимальне завантаження. В результаті вийде критерій максимізації завантаження в кожній декаді кварталу.
Багатокритеріальні задачі можна також класифікувати за іншими ознаками, наприклад, за варіантами оптимізації, по числу або типам критеріїв, за співвідношенням між критеріями, за рівню структуризації, наявності фактора невизначеності і т.п.
При розробці методів рішення векторних задач доводиться вирішувати ряд специфічних проблем.
Проблема нормалізації виникає у зв'язку з тим, що локальні критерії мають, як правило, різні одиниці і масштаби виміру, і це робить неможливим їх безпосереднє порівняння. Операція приведення критеріїв до єдиного масштабу і безрозмірного увазі називається нормуванням. Найбільш поширеним способом нормування є заміна абсолютних значень критеріїв їх відносними величинами.
Проблема вибору принципу оптимальності пов'язана з визначенням властивостей оптимального рішення і рішенням питання - в якому сенсі оптимальне рішення перевершує всі інші.
Проблема обліку пріоритету критеріїв виникає, якщо локальні критерії мають різну значимість. Необхідно знайти математичне визначення пріоритету і ступінь його впливу на рішення задачі.
Проблема обчислення оптимуму виникає, якщо традиційні обчислювальні схеми та алгоритми непридатні для вирішення завдання векторної оптимізації.
Якісна інформація про відносну важливість критеріїв найчастіше являє собою повідомлення про те, що якісь критерії "рівноцінні" або ж "один критерій важливіше інших". Така інформація може бути отримана в ході контрольного пред'явлення ОПР спеціально формованих векторних оцінок і з'ясування, які з них він воліє при порівнянні з іншими. При цьому пред'являються ОПР оцінки повинні задовольняти двом спеціальним вимогам. По-перше, всі приватні компоненти таких спеціальних оцінок повинні мати загальну шкалу, тобто бути однорідними. По-друге, в пропонованих оцінках всі компоненти, крім тих, чия відносна важливість з'ясовується, повинні бути однаковими.
Для того щоб забезпечити однорідність приватних критеріїв, які, взагалі кажучи, мають різні шкали, в практиці часто використовують прості прийоми еквівалентного перетворення неоднорідних приватних критеріїв до єдиного, безрозмірного вигляду. Використовуються наступні формули перетворень (в якості стандарту вибрано перетворення в шкалу із значеннями з відрізка [0; 1]:
Якщо відомі еталонні значення показників (наприклад, міжнародний стандарт), то використовується перетворення наступного виду:
;
Якщо відомі максимально можливі значення показників, то
;
Якщо відомі діапазони зміни показників, то
або.
Перш ніж приступити до розгляду алгоритмів розв'язання задач векторної оптимізації, має сенс коротко зупинитися на деяких фундаментальних поняттях теорії при...
