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

 

Міністерство освіти і науки, молоді та спорту України

Полтавський національний педагогічний університет імені В.Г.Короленка

 

 

фізико-математичний факультет

кафедра математичного аналізу та інформатики

 

 

 

МЕТОД БАЖАНОЇ ТОЧКИ ПРИ ПРИЙНЯТТІ  РІШЕНЬ В УМОВАХ ВИЗНАЧЕНОСТІ ТА ЙОГО ПРОГРАМНА РЕАЛІЗАЦІЯ

Дипломна  кваліфікаційна робота

зі спеціальності 7.080201 Інформатика

 

Рекомендовано до захисту

«____»___________2011 р.,

Протокол  №____________

Зав. кафедри____________

 

Виконала:

студентка V курсу, групи М-54

Жездріс Анелє  Вітаутасівна

 

Науковий керівник:

доктор фіз.-мат. наук, професор

Ємець Олег Олексійович

 

 

Полтава – 2011

ЗМІСТ

 

ВСТУП………………………………………………………...……………………...3                                                            

РОЗДІЛ 1. ІНФОРМАЦІЙНИЙ  ОГЛЯД…………………………………………...5

1. Огляд задач багатокритеріального програмування,

приклади  багатокритеріальності………...………………………..……5

2. Поняття про багатокритеріальну оптимізацію……………...…………8         

РОЗДІЛ 2. ТЕОРЕТИЧНА  ЧАСТИНА………………………………..………….11

1. Основні поняття та визначення теорії прийняття рішень

в умовах визначеності…………………………..…………………….11

2. Загальні відомості про задачі багатокритеріальної оптимізації..….12
3. Постановка задачі багатокритеріальної оптимізації……..…………18
4. Методи багатокритеріальної оптимізації………..…………………..29
5. Метод бажаної точки при прийнятті рішень в умовах

визначеності…………………………………………………………...32

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

1. Блок-схема  алгоритму …………………….………………………...36        
2. Опис програмної реалізації методу бажаної точки………………....38 

ВИСНОВКИ………………………………………………………………………...45

СПИСОК  ВИКОРИСТАНИХ ДЖЕРЕЛ ………………………………………..46

ДОДАТОК А………………….…………………………………………………….48             

 

 

 

 

 

 

 

 

ВСТУП

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

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

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

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

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

Виходячи з поставленої мети, в роботі розв’язано низку наступних завдань:

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

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

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

Робота складається зі вступу, трьох розділів, висновків, списку використаних джерел та додатків. Обсяг роботи складає 47 сторінок та 4 рисунка. Додаток до дипломної роботи містить 32 сторінки та 3 рисунка. Список використаної літератури містить 13 джерел. Програмна реалізація методу бажаної точки розроблена у середовищі Delphi 6.

 

 

РОЗДІЛ 1. ІНФОРМАЦІЙНИЙ ОГЛЯД

 

1. Огляд задач багатокритеріального програмування, приклади багатокритеріальності

 

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

,

,

   

,

 при  , де - критерії оптимізації,

а – множина допустимих значень змінної,

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

Приклади багатокритеріальності.

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

Планування очищення нафти

{витрати},

{кількість сирої нафти,  що імпортується},

{кількість матеріалу  із високим вмістом сірки},

{відхилення від запланованого  складу},

{горіння газів}.

Планування виробництва

{загальний прибуток},

{мінімальний прибуток  за будь-який період},

{кількість невиконаних  замовлень},

{додатковий час},

{запаси готової продукції}.

Добір набору цінних паперів

{прибуток},

{ризик},

{дивіденди},

{відхилення від бажаного  рівня різноманітності паперів}.

Розрахунок капіталовкладень

{наявність кошт},

{попит на капіталовкладення},

{щорічні витрати на  експлуатацію},

{інвестиції у проекти,  що пов’язані із охороною навколишнього  середовища},

{інвестиції у проекти  у вказаному регіоні},

{інвестиції у проекти  заданої товарної специфіки}.

Керування лісним господарством

{постійний врожай деревини},

{дні відпочинку у  лісі людей},

{дні полювання у лісі  людей},

{площа розповсюдження  диких звірів},

{кількість місяців пасовища  домашньої худоби}

{перевищення бюджету}.

Керування водосховищами

{прибуток від рекреації  на водосховищі №1},

{прибуток від регулювання  стоку нижче водосховища №1},

{кількість енергії,  що виробляється},

{поставки води на  комунальні потреби},

{прибуток від рекреації  на водосховищі №2},

{прибуток від поливу  земель нижче водосховища №2}.

Формування ревізійної служби на фірмі

{прибуток},

{приріст кількості персоналу},

{зменшення кількості  персоналу},

{надлишкові витрати},

{нераціональне використання  кваліфікації кадрів},

{час, що використовується  на професіональний приріст}.

Транспортування

{вартість},

{середній час доставки  вантажу найвпливовішим клієнтам},

{виробництво за заданою  технологією},

{використання палива}.

Виготовлення сировини для  сосисок, копченої ковбаси та салямі

{вартість},

{жирність},

{відхилення від заданого  кольору},

{протеїн},

{відхилення від заданого  рівня вологості},

{відхилення від заданого  відношення свинини та телятини}.

 

1.2 Поняття про багатокритеріальну оптимізацію

 

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

                 (1.1)

за умов

, .

Задача (1.1), найімовірніше, буде нелінійною, але для заданого підходу  це не найголовніші труднощі. Найскладніше те, що для багатьох задач неможливо  отримати деякий математичний опис функції  корисності U. Власне, саме такі задачі нас і цікавлять. Навіть не зважаючи на те, що ми можемо не знати функцію корисності ОПР, такі задачі мають бути розв’язані [2].

Відповідно, коли невідомо явний  вираз функції корисності ОПР, не залишається нічого, окрім вивчення яким-небудь чином «області заміщення» для критеріїв

,

,

…

,

де ,

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

Оптимальні та остаточні розв’язки.

Слід зазначити деякі  зауваження щодо властивостей оптимальних  розв’язків. Точка з множини S є оптимальною, якщо вона максимізує функцію корисності ОПР в (1.1). Але для того, щоб точка була оптимальною, вона повинна бути ефективною. Точка з множини S є ефективною тоді і тільки тоді, коли відповідне їй значення векторного критерію не домінується. Тобто точка ефективна, якщо з неї неможливо рушити в межах допустимої множини зі збільшенням одного з критеріїв, якщо не зменшити при цьому хоча б один із тих, що залишились [3]. Неефективні розв’язки можуть бути кандидатами в оптимальні.

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

Аналіз розв’язку за набором  показників.

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

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

РОЗДІЛ 2. ТЕОРЕТИЧНА ЧАСТИНА

 

2.1 Основні поняття та визначення  теорії прийняття рішень в  умовах визначеності

 

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