Системи прийняття рішень

Міністерство освіти і науки Республіки Казахстан

Павлодарський державний університет ім. С. Торайгирова

Факультет фізики математики та інформаційних технологій

Кафедра обчислювальної техніки і програмування

Курсова робота

За дисциплін е «Теоретичні основи комп'ютерних систем»

Тема:

«Системи прийняття рішень»

2005

1. Теоретичне завдання

1.1 Введення

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

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

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

1.2 Структура процесу прийняття рішення

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

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

Таким чином, процес прийняття рішень можна розбити на наступні етапи:

- Дослідити власне проблему;

- Усвідомити вихідну ситуацію;

- Сформувати можливі варіанти вирішення;

- Описати наслідки цих варіантів рішення;

- Оцінити можливі варіанти рішень і (або) наслідки цих рішень;

- Вибрати оптимальне рішення;

- Узагальнити накопичений досвід прийняття рішення.

Дана структура процесу прийняття рішення наочно зображена на малюнку 1.1.

Малюнок 1.1 - Структура процесу прийняття рішення

1.3 Вихідна ситуація

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

Щоб сформулювати уявлення про вихідної ситуації треба відповісти на наступні запитання.

- Хто повинен і зобов'язаний (або хоче) вирішувати?

- Де, тобто на (в) якому місці, в якому оточенні (середовищі), за яких обставин і граничних умовах належить приймати рішення?

- Коли (до якого терміну, як часто) потрібно прийняти рішення?

- Як (яким чином або в якій формі, ніж) повинно бути виражене рішення?

- Що обумовлює рішення? У чому його мета, задум? Для чого воно служить? Навіщо його треба приймати?

1.4 Можливості прийняття рішення

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

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

Надалі ми будемо дотримуватися двох робочих правил.

1. Всі можливі рішення, які нам відомі, слід наочно зіставити між собою.

2. Перелік можливих рішень треба досліджувати на повноту і при необхідності поповнити.

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

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

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

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

1.5 Наслідки рішень

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

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

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

1.6 критерій рішень.

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

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

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

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

- Технічні критерії;

- Техніко-економічні критерії;

- Соціологічні критерії;

- Психологічні критерії;

- Естетичні критерії;

- Соціальні критерії.

Звернемося тепер до шкали оцінки обраного критерію. Виділяють такі види шкал:

- Точні числа;

- Наближені числа;

- Відносні числа;

- Окуляри, пункти;

- Оцінки, пункти.

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

1.7 Пошук рішення

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

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

1.8 Витяг уроків з прийнятих рішень

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

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

2. Практичне завдання

2.1 Завдання

Фірма рекламує свою продукцію з використанням чотирьох засобів: телевізора, радіо, газет і афіш. З різних рекламних експериментів, які проводилися в минулому, відомо, що ці засоби призводять до збільшення прибутку відповідно на 10, 3, 7 і 4 дол. у розрахунку на 1 дол., витрачений на рекламу. Розподіл рекламного бюджету різними засобами, підпорядковане наступним обмеженням:

а) повний бюджет не повинен перевершувати 500000 дол.;

б) слід витрачати не більше 40% бюджету на телебачення і не більше 20% бюджету на афіші;

в) внаслідок привабливості для підлітків радіо на нього слід витрачати, принаймні, половину того, що планується на телебачення.

Скільки коштів слід направити на кожен вид реклами, щоб прибуток був максимальним.

2.2 Математична модель

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

(2.1)

де x _i - обсяг грошових коштів йдуть на рекламу i - го типу;

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

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

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

На основі даних, отриманих із завдання, можна побудувати цільову функцію відповідно до формули 2.2.

(2.2)

де W - цільова функція - прибуток від;

x ₁ - кошти витрачені на телевізійну рекламу;

x ₂ - кошти витрачені на радіо рекламу;

x ₃ - кошти витрачені на газетну рекламу;

x ₄ - кошти витрачені на афішну рекламу.

У завдання є наступні обмеження: повний бюджет не повинен перевершувати 500 000 дол., Тобто дол.; слід витрачати не більше 40% бюджету на телебачення і не більше 20% бюджету на афіші, тобто і ; Внаслідок привабливості для підлітків радіо на нього слід витрачати, принаймні, половину того, що планується на телебачення, тобто .

Отримана система зображена на формулі (2.3).

(2.3)

Тепер треба позбутися від нерівності і перейти до рівності. Для цього введемо невід'ємні фіктивні змінні, які урівноважать не рівність (2.3).

(2.4)

На основі формул (2.1), (2.2) і (2.4), постоєм математичну модель даної завдання.

(2.5)

2.3 Метод рішення

Існує багато методів розв'язання ЗЛП. Більшість з них призначені для окремих випадків. Графічний метод - дуже наочний, але призначений для завдань, у яких кількість базисних змінних не більше двох. Евристичний метод може впоратися з ЗЛП не традиційного виду, хоча заздалегідь не може гарантувати результат. Транспортний метод також хороший, але застосуємо для задач окремого випадку.

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

Симплекс метод має наступний канонічний вигляд математичної моделі.

Дано:

- N вільних змінних. Їх значення ми можемо вибирати самі. Припустимо їх рівними нулю.

- M базисних змінних. Їх значення визначається за лінійним рівнянням від вільних змінних, але тому що вільні члени дорівнюють нулю, то базисні змінні дорівнюють значенню вільних членів рівнянь.

- Цільова функція виражена через лінійне рівняння від вільних змінних.

Цей метод призначений для знаходження мінімуму, тому щоб знайти максимум, треба в місце використовувати

Наведемо математичну модель нашої задачі у канонічному вигляді.

(2.6)

Математична модель одночасно є початковим опорним рішенням. Воно оформляється у відповідності з таблицею 2.1.

Таблиця 2.1

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

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

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

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

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

2.4.1 Абстрактний клас симплекс таблиці

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

2.4.2 Властивості клас TSimplex

Клас TSimplex має такі властивості:

- N, m: integer - відповідно число вільних і число базисних змінних;

- W, b: array of extended - масиви, що містять відповідно вільні члени і коефіцієнти цільової функції;

- Wb: extended - вільний член цільової функції;

- FTit, BTit: array of string - відповідно назви вільних і базисних мінливих;

- A: array of array of extended - матриця коефіцієнтів лінійних функцій базисних мінливих;

- Result: TNextResult - результат останньої операції;

- Ir, jr: integer - відповідно роздільна рядок і дозволяє стовпець;

- History: TStack - історія про попередні операції, дозволяє повернутися назад.

Для повної ячності треба опісять тип TNextResult і клас TStack.

Тип TNextResult описує результат останньої операції.

TNextResult = (nrFound = 0, nrOporOk, nrOporFail, nrOptimOk, nrOptimFail, nrStackEmputy),

де nrFound - знайдено рішення;

nrOporOk - знайдено спосіб, як замінить базис, щоб наблизитися до опорного вирішенню;

nrOporFail - неможливо знайти опорне рішення, тобто і вся завдання не має рішення;

nrOptimOk - знайдено спосіб, як замінить базис, щоб наблизитися до оптимального рішення;

nrOptimFail - неможливо знайти оптимальне рішення, тобто і вся завдання не має рішення;

nrStackEmputy - стік з історією про попередні ходах порожній, тобто неможливо зробити крок назад.

Клас TStack - стік, що зберігає історію про зроблені кроки, дозволяє відкинути положення обчислення тому.

TIJ = record i, j: integer end;

TStack = class

top: integer;

stackIJ: array [0 .. 1000] of TIJ;

end;

2.4.3 Методи класу TSimplex

Клас TSimplex має наступні методи:

- Procedure newBase - дозволяє перейти до нового базису, причому роздільна рядок і дозволяє стовпець вказується у властивостях ir, jr;

- Function next: TNextResult - знаходить наступний крок до опрорному рішенням або якщо воно знайдено до оптимального рішення, причому зберігає у властивості history пройдений шлях;

- Procedure back - повертається на один крок назад, використовуючи властивість history.

2.5 Рішення

На основі початкових даних математичної моделі нашої задачі (2.6), побудуємо симплекс таблицю відповідно з малюнком 2.1.

Малюнок 2.1 - Опорне рішення

Оскільки вільні члени не негативні, то це опорне рішення, на основі нього ми отримаємо оптимальне рішення.

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

Виберемо дозволяючим стовпцем x ₁ тому коефіцієнтів цільової функції в цьому стовпці більше нуля і більше всіх інших позитивних коефіцієнтів цільової функції, він дорівнює 10.

Виберемо роздільної рядком y ₂ тому що відношення вільного члена до числа у відповідному рядку і вирішуючому стовпці мінімально і не негативно (0 / 0,6 = 0).

Виділимо дозволяє стовпець, рядок і елемент.

Переїдемо до нового базису у відповідності з рисунком 2.2 за правилом, вираховуючи нові коефіцієнти за правилом прямокутника:

Малюнок 2.2 - Перший крок

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

Виберемо дозволяючим стовпцем x ₃ тому коефіцієнтів цільової функції в цьому стовпці більше нуля і більше всіх інших позитивних коефіцієнтів цільової функції, він дорівнює 13,66.

Виберемо роздільної рядком y ₄ тому що відношення вільного члена до числа у відповідному рядку і вирішуючому стовпці мінімально і не негативно (0 / 13,66 = 0).

Виділимо дозволяє стовпець, рядок і елемент.

Переїдемо до нового базису у відповідності з рисунком 2.3 за правилом, вираховуючи нові коефіцієнти за правилом прямокутника:

Малюнок 2.3 - Другий крок

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

Виберемо дозволяючим стовпцем x ₂ тому коефіцієнтів цільової функції в цьому стовпці більше нуля і більше всіх інших позитивних коефіцієнтів цільової функції, він дорівнює 37.

Виберемо роздільної рядком y ₁ тому що відношення вільного члена до числа у відповідному рядку і вирішуючому стовпці мінімально і не негативно (500000 / 5 = 100000).

Виділимо дозволяє стовпець, рядок і елемент.

Переїдемо до нового базису у відповідності з рисунком 2.4 за правилом, вираховуючи нові коефіцієнти за правилом прямокутника:

Малюнок 2.4 - Оптимальне рішення

Оскільки є коефіцієнти в рівнянні цільової функції, які більше нуля, то це рішення оптимальне.

Відповідь:

Висновок

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

Список використаних джерел

1. Кремер Н.Ш., Путко Б.А. та ін Дослідження операцій в економіці. Навчальний посібник. М.: Юніті, 1997

2. Федосєєв В.В., Гармаш О.М. та ін Економіко-математичні методи і прикладні моделі. М.: Юніті, 2001

3. Акулич І.Л. Математичне програмування в прикладах і задачах. - М.: Вища школа, 1986

4. Житніков С.А., Біржанова З.М. та ін Економіко-математичні методи і моделі. Караганда: видавництво КЕУ, 1998

5. Замків О.О., Толстопятенко А.В. Математичні методи в економіці. М.: ДІС, 1997

6. Колеман В.А. Математична економіка. М., 1998

7. Кузнєцов Ю.М., Кузубов В.І., Волощенко А.Б. Математичне програмування. М.: Вища школа, 1998

8. Лопатников Л.І. Економіко-математичний словник. М.: Наука, 1987

9. Малихін В.І. Математичне моделювання економіки. М., 1998

10. Мельник М.М. Економіко-математичні методи в плануванні та управлінні матеріально-технічним постачанням. - М.: Вища школа, 1990

11. Нусупбеков С.І., Устенова О.Ж. Математичні методи моделювання економічних систем. Алмати: Евері, 2002

12. Спірін А.А., Фомін Г.П. Економіко-математичні методи і моделі в торгівлі. - М.: Економіка, 1988