Реферати українською » Экономико-математическое моделирование » Інформаційні технології вирішення завдань векторної оптимізації


Реферат Інформаційні технології вирішення завдань векторної оптимізації

Страница 1 из 2 | Следующая страница

ІНФОРМАЦІЙНІ ТЕХНОЛОГІЇ РІШЕННЯЗАДАЧВЕКТОРНОЙОПТИМИЗАЦИИ


План:

Запровадження

Принцип оптимальності Парето.Неулучшаемие (оптимальні по Парето) рішення

Принцип рівноваги поНешу

Конфлікти, переговори, і компроміси

Короткий огляд методів виконання завдання векторної оптимізації


Запровадження

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

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

Порівняння альтернатив по векторному критерію здійснюються за наступному правилу: всяка альтернатива буде не гірший будь-який інший, для неї значення векторного критерію щонайменше переважно, ніж значення критерію інший альтернативи, тобто:


де - альтернативи; - векторний критерій; - символ відносини несуворого переваги.

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

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

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

Серед сили-силенноїмногокритериальних завдань можна назвати завдання чотирьох типів:

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

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

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

Завдання оптимізації на безлічі етапів функціонування. Розглядається функціонування об'єктів на деякому інтервалі часу, розбитому сталася на кілька етапів. Якість управління кожному етапі оцінюється приватним критерієм, але в безлічі етапів – загальнимвекторним критерієм. Прикладом може бути розподіл квартального плану цехи здекадам. У кожній декаді необхідно забезпечити максимальне завантаження. Через війну вийде критерій максимізації завантаження у кожному декаді кварталу.

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

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

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

Проблема вибору принципу оптимальності пов'язані з визначенням властивостей оптимального рішення і рішення питання – у сенсі оптимальне рішення переважає всі інші.

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

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

Якісна інформація про відносну важливості критеріїв найчастіше є повідомлення у тому, якісь критерії “рівноцінні” або ж “один критерій важливіше інших”. Такої інформації може бути отримана під час контрольного пред'явленняЛПР спеціально формованих векторних оцінок і з'ясування, які їх вона віддає перевагу при порівнянні коїться з іншими. У цьому запропонованіЛПР оцінки повинні задовольняти двом спеціальним вимогам. По-перше, всі приватні компоненти таких спеціальних оцінок повинен мати загальну шкалу, тобто однорідними. По-друге, в пропонованих оцінках все компоненти, крім, чия відносна важливість з'ясовується, повинні бути однаковими.

Щоб забезпечити однорідність приватних критеріїв, які, власне кажучи, мають різні шкали, на практиці часто використовують прості прийоми еквівалентного перетворення неоднорідних приватних критеріїв до єдиного, безрозмірному виду. Використовуються такі формули перетворень (як стандарт вибрано перетворення на шкалу зі значеннями з відрізка [0;1]:

Якщо відомі еталонні значення показників (наприклад, міжнародний стандарт), то використовується перетворення наступного виду:

 ;

Якщо відомі максимально можливі значення показників, то

 ;

Якщо відомі діапазони зміни показників, то

 

чи .

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


Принцип оптимальності Парето.Неулучшаемие (оптимальні по Парето) рішення

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

Рішення боку краще її вирішення , якщо:

.

З вищесказаного (на наявність сторін, самостійно вибирають свої рішення), можна сформулювати принцип одноголосності, відомого як принцип оптимальності Парето):

Якщо усіх сторін допустимі рішення краще рішень , то останні ні прийнято (одноголосно відкинуті).

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

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

 

Принцип рівноваги поНешу

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

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

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

.

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

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

Ситуація рівноваги може бути не єдиною.

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

Ситуації рівноваги можуть збігатися або збігатися з ситуаціями оптимальними по Парето.

 

Конфлікти, переговори, і компроміси

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

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

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

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

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

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

 

Короткий огляд методів виконання завдання векторної оптимізації

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

Методи, засновані на згортання системи показників ефективності;

Методи, використовують обмеження на критерії;

Методи цільового програмування;

Методи, засновані на знаходженні компромісного рішення;

Методи, основу яких вмостилися людино-машинні процедура прийняття рішень (інтерактивне програмування).

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

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

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

.

І тут функція переваги вибирається як:

(5.1)

і

Страница 1 из 2 | Следующая страница

Схожі реферати:

Навігація