Зміст
Зміст. 1
1. Постановка завдання. 2
2. Короткі теоретичні відомості. 3
3. Реалізація програмного кошти. 7
3.1 Проектування. 7
3.2 Алгоритм пошуку Парето-оптимальних рішень. 7
3.3 Лістинг програмного коду. 10
4. Приклад роботи програми .. 24
4.1 Багатокритеріальна задача. 24
4.2 Двухкрітеріальная завдання. 25
3. Аналітичне завдання критеріїв. 27
Висновки .. 28
Використовувана література. 29
Використовувані програмні засоби. 29
1. Постановка завдання
математична модель Парето оптимальність
Необхідно розробити програмний засіб для пошуку Парето-оптимальних рішень для наступних видів завдань:
1) багатокритеріальна завдання
вхідні дані: кількість критеріїв і рішень; вагові значення, задані безпосередньо, або в параметричному вигляді.
вихідні дані: рішення, входять до безліч Парето; номери Парето-оптимальних рішень з безлічі вихідних рішень
2) двухкрітеріальная завдання
вхідні дані: кількість критеріїв і рішень; вагові значення, задані безпосередньо, або в параметричному вигляді.
вихідні дані: рішення, входять до безліч Парето; номери Парето-оптимальних рішень з безлічі вихідних рішень; графічне представлення Парето-оптимальних рішень.
2. Короткі теоретичні відомості
Нехай заданий набір числових функцій, визначених на множині можливих рішень X. Залежно від змісту завдання вибору ці функції іменують критеріями оптимальності, критеріями ефективності або цільовими функціями.
Зазначені вище числові функції утворюють векторний критерій, який приймає значення в просторі m-мірних векторів. Це простір називають критеріальним простором або простором оцінок, а всяке значення іменують векторної оцінкою можливого рішення x. Всі можливі векторні оцінки утворюють безліч можливих оцінок (можливих або допустимих векторів)
Як правило, між множинами можливих рішень X і відповідним безліччю векторів Y можна встановити взаємно однозначну відповідність, тобто кожному можливому рішенню поставити у відповідність певний можливий вектор, і назад - кожному можливому вектору зіставити певне можливе рішення. У таких випадках вибір у безлічі рішень з математичної точки зору рівносильний вибору під безлічі векторів і всі визначення і результати можна формулювати як в термінах рішень, так і в термінах векторів, причому при бажанні завжди можна без праці здійснити перехід від однієї форми викладу до іншого.
Завдання вибору, яка включає безліч допустимих рішень X і векторний критерій f, зазвичай називають багатокритеріальної завданням або завданням багатокритеріальної оптимізації.
Необхідно зазначити, що формування математичної моделі прийняття рішень (тобто побудова безлічі X і векторного критерію f ) нерідко являє собою складний процес, в якому тісно взаємодіють фахівці двох сторін. А саме, представники конкретній галузі знань, до якої відноситься досліджувана проблема, і фахівці з прийняття рішень (математики). З одного боку, слід врахувати всі найважливіші риси і деталі реальної задачі, а з іншого, - побудована модель не повинна виявитися надмірно складною з тим, щоб для її дослідження і рішення можна було успішно застосувати розроблений до теперішнього часу відповідний математичний апарат. Саме тому етап побудови математичної моделі в значній мірі залежить від досвіду, інтуїції і мистецтва дослідників обох сторін. Його неможливо ототожнити з простим формальним застосуванням вже відомих, добре описаних алгоритмів.
Тут слід ще додати, що будь-яка задача вибору (в тому числі і багатокритеріальна) тісно пов'язана з конкретним ОПР (особа, що приймає рішення). Вже на стадії формування математичної моделі при побудові безлічі можливих рішень і векторного критерію справа не обходиться без порад, рекомендацій і вказівок ОПР, тим більше що векторний критерій як раз і служить. Прийняття рішення при багатьох критеріях для вираження цілей ОПР. При цьому ясно, що побудувати модель в точності відповідає всім реальним обставинам неможливо. Модель завжди є спрощенням дійсності. Важливо домогтися, щоб вона містила ті риси і деталі, які найбільшою мірою впливають на остаточний вибір найкращого рішення.
Розглянемо два довільних можливих рішення і. Для них має місце один і тільки один з наступних трьох випадків:
1) справедливо співвідношення (ОПР перше рішення воліє другого),
2) справедливо співвідношення (ОПР друге рішення воліє першому),
3) не виконується ні співвідношення, ні співвідношення (ОПР не може віддати перевагу жодному з вказаних двох рішень).
Зауважимо, що четвертий випадок, коли обидва беруть участь тут співвідношення і виконуються, неможливий завдяки асиметричності відносини переваги
В першому з зазначених вище випадків, тобто при виконанні співвідношення, говорять, що рішення домінує рішення.
Якщо ж реалізується третій випадок, то говорять, що рішення і не порівняні по відношенню уподобання.
Аксіома Парето.
Для всіх пар допустимих рішень, для яких має місце нерівність, виконується співвідношення
Рішення називається оптимальним по Парето (Парето-оптимальний), якщо не існує такого можливого рішення, для якого має місце нерівність. Всі Парето-оптимальні рішення утворюють безліч Парето, позначуване
Парето-оптимальний рішення - це таке допустиме рішення, яке не може бути покращено (Збільшено) ні по одному з наявних критеріїв без погіршення (зменшення) по якогось хоча б одному іншому критерію.
Інакше кажучи, воліючи одному Парето-оптимального вирішення інше Парето-оптимальне рішення, ЛПР (особа, приймає рішення) змушене йти на певний компроміс, погоджуючись на деяку втрату хоча б за одним критерієм (отримуючи, зрозуміло, визначений виграш, принаймні, по якомусь іншому критерію). З цієї причини безліч Парето нерідко називають безліччю компромісів.
Поняття оптимальності по Парето відіграє важливу роль у математичній економіці. Саме в цій області часто замість Парето-оптимальності використовують найменування ефективне рішення та безліч ефективних рішень. Тим самим, Парето-оптимальність і ефективність в математичній економіці нерідко виявляються синонімами.
3. Реалізація програмного засобу.
середу розробки: Visual Studio 2010
Мова програмування: C #
3.1 Проектування
При проектуванні програмного засобу будемо використовувати об'єктно-орієнтований підхід.
Список класів з коротким описом:
1) MainView.cs - це головне вікно, служить для введення даних та запуску роботи алгоритму пошуку Парето-оптимальних рішень.
2) SolutionsView.cs - це вікно, яке містить знайдені Парето-оптимальні рішення, представлені в табличній формі
3) GraphView.cs - вікно, на якому буде відображатися графічне уявлення множини Парето для двухкрітеріальних завдань
4) Pareto.cs - це основний клас. Містить 2 алгоритму пошуку безлічі Парето.
5) Graph.cs - клас, що містить методи для побудови графіків (в даному випадку будемо використовувати сторонню бібліотеку ZedGgraph.dll)
6) File.cs-методи для збереження і завантаження даних в/з файл (а).
3.2 Алгоритм пошуку Парето-оптимальних рішень
Крок 1. Покласти P (Y) = Y, i = 1, j = 2. Тим самим утворюється так зване поточне безліч Парето-оптимальних векторів, яке на початку роботи алгоритму збігається з безліччю Y, а в кінці складе шукане безліч Парето-оптимальних векторів. Алгоритм влаштований таким чином, що шукане безліч Парето-оптимальних векторів виходить з Y послідовним видаленням свідомо неоптимальних векторів.
Крок 2. Перевірити виконання нерівності. Якщо воно виявилося істинним, то перейти до Кроку 3. В іншому випадку перейт...
