Відмінності між версіями «Прийняття рішень за результатами моделювання»

Матеріал з Вікі ЦДУ
Перейти до: навігація, пошук
 
(не показано 28 проміжних версій цього учасника)
Рядок 1: Рядок 1:
−
'''Моделювання''' (рос. моделирование, англ. modelling, simulation, нім. Modellieren n, Modellierung f, Simulation f) — це метод дослідження явищ і процесів, що ґрунтується на заміні конкретного об'єкта досліджень (оригіналу) іншим, подібним до нього ('''моделлю''').
+
== Поняття моделі та моделювання ==
  
−
'''Модель''' — це уявлення про об'єкт, системи або ідеї в певній формі, що відрізняється від власне цілісності.
+
Усяка цілеспрямована діяльність, у тому числі розробка і прийняття рішень пов'язані з моделюванням.
 +
 
 +
'''Моделюванням''' називається створення деякого образу об'єкта-оригіналу, названого моделлю, що у визначених умовах може заміняти сам об'єкт-оригінал, відтворюючи цікавлячі дослідника властивості і характеристики оригіналу й одночасно забезпечуючи наочність, видимість, приступність іспиту, легкість оперування й інші переваги.
 +
 
 +
З визначення випливає, що модель має цільовий характер, тобто вона відображає не сам по собі об'єкт-оригінал, а формується, виходячи з поставленої мети відображення цілком конкретних властивостей об'єкта моделювання.
 +
 
 +
Використання моделей дозволяє приймати рішення, при обґрунтуванні яких враховуються всі фактори і альтернативи, що виникають у складних умовах виробничо-господарської діяльності. Тому моделювання розглядається як найефективніший спосіб оптимізації управлінських рішень.
 +
 
 +
'''Модель''' – це відображення в схемі, формулі, взірці тощо характерних ознак об’єкту, який досліджується. Вона є спрощеною конкретною життєвою (управлінською) ситуацією, іншими словами в моделях певним чином відображаються реальні події, обставини тощо.
 +
 
 +
Головною характеристикою моделі вважається спрощення реальної життєвої ситуації, до якої вона застосовується. Оскільки форма моделі менш складна, а дані, що не стосуються справи й ускладнюють розуміння проблеми, вилучаються, модель часто збільшує здатність керівника розуміти й розв'язувати проблему, що стоїть перед ним. Модель також допомагає керівникові поєднати свій досвід і здатність міркувати з досвідом та думками експертів.
  
−
Головною характеристикою моделі вважається спрощення реальної життєвої ситуації, до якої вона застосовується. Оскільки форма моделі менш складна, а дані, що не стосуються справи й ускладнюють розуміння проблеми, вилучаються, модель часто збільшує здатність користувача розуміти й розв'язувати проблему, що стоїть перед ним. Модель також допомагає користувачеві поєднати свій досвід і здатність міркувати з досвідом та думками експертів.
 
 
Є низка причин, що зумовлюють використання моделі замість спроб безпосередньої взаємодії з реальністю. До них належать:
 
Є низка причин, що зумовлюють використання моделі замість спроб безпосередньої взаємодії з реальністю. До них належать:
 
* природна складність багатьох організаційних ситуацій  
 
* природна складність багатьох організаційних ситуацій  
−
* неможливість здійснення експериментів у реальному житті, навіть якщо вони потрібні, й орієнтація керівництва на майбутнє.
+
* неможливість здійснення експериментів у реальному житті, навіть якщо вони потрібні, й орієнтація керівництва на майбутнє.  
 +
* наявністю багатофакторних залежностей у процесі розв’язання управлінських завдань;
 +
* необхідністю експериментальної перевірки альтернативних управлінських рішень;
 +
* доцільністю орієнтувати управління на майбутнє.
 +
Моделювання направлене на синтез результатів аналітичного пізнання, внаслідок чого описуються загальні закони і закономірності, стабільні властивості елементів і зв'язків у процесі функціонування або розвитку досліджуваного явища. Моделювання є основною і неодмінною умовою розвитку аналізу.
 +
 
 +
Модельний опис закономірностей змісту робіт по окремих етапах процесу ухвалення рішень, а також зв'язків між даними етапами є важливою передумовою подальшого розвитку аналізу господарської діяльності. З другого боку, результати аналізу дозволяють удосконалювати розробку моделей і наблизити їх до реальної ситуації управління господарською діяльністю.
 +
Моделі ухвалення рішень підтримують у першу чергу кількісний аналіз господарських процесів. Моделі дозволяють легше пройти етапи рутинного аналізу – аж до їх автоматизації. Якісний аналіз просувається углиб і вшир, залишаючи пізнані області процесу для модельних описів.
 +
Модель ухвалення рішень є формалізованою частиною рішення управлінської задачі. Одержане на її основі рішення оптимальне лише з погляду формалізованих умов задачі. Суб'єкт управління доповнює одержане «модельне рішення» необхідним якісним аналізом, враховує свій досвід та інтуїцію і формулює рішення.
 +
 
 +
Моделі «навчають» враховувати всі формалізовані умови керованого процесу. Творчістю кожного конкретного керівника є облік всієї решти (специфічних з погляду моделі) умов рішення управлінської задачі.
 +
 
 +
Так само як моделі ухвалення рішень не знижують значущості інтуїції керівника, вони при правильному застосуванні сприяють розвитку ініціативи працівників, покликаних виконувати дані рішення. Модельне рішення враховує всі чинники, відомі керівнику у момент ухвалення рішення, і примушує виконавців повністю використовувати ці чинники. Але в процесі реалізації ухваленого рішення часто виявляються нові можливості і шляхи застосування конкретних умов. Використовування цих прихованих резервів залежить не від моделі, а від дієвості системи стимулювання всього господарського механізму. Моделі прийняття рішень можуть бути основою розробки обґрунтованих систем стимулювання розвитку ініціативи працівників.
 +
 
 +
== Формування вимог і адекватність моделей ==
 +
[[Файл:Model.png|thumb|right|Формування вимог і адекватності моделей]]
 +
Багато непорозумінь та помилок в результатах застосування моделей виникають через використовування не відповідної для даної задачі моделі або застосування моделі для вирішення задачі, яка не відповідає її можливостям. Адекватність управлінських моделей необхідно оцінювати принаймні з трьох точок зору:
 +
* за відповідністю структурі і властивостям об'єкта управління (керованого процесу);
 +
* за відповідністю властивостям і можливостям методів складання даних моделей і експериментування з ними;
 +
* за відповідністю вимогам вирішуваної управлінської задачі.
 +
При складанні моделей необхідно, поза сумнівом, враховувати вживаність моделей із суб'єктивної точки зору.
 +
 
 +
== Порядок розробки та використання моделей ==
 +
Світова практика виробила певний порядок розробки моделей. Найдоцільніше застосовувати такий процес їх побудови:
 +
* постановка завдання;
 +
* формування моделі;
 +
* перевірка моделі на достовірність;
 +
* використання моделі;
 +
* відновлення моделі.
 +
'''Постановка задачі.'''
 +
 +
Перший і найважливіший етап побудови моделі, здатний забезпечити правильне рішення управлінської проблеми, полягає в постановці задачі. Правильне використовування математики або комп'ютера не принесе ніякої користі, якщо саму проблему не буде точно діагностовано.
 +
 
 +
'''Побудова моделі.'''
 +
 
 +
Після правильної постановки задачі наступним етапом процесу передбачена побудова моделі. Розробник повинен визначити головну мету моделі, які вихідні нормативи або інформацію передбачається одержати, використовуючи модель, щоб допомогти керівництву вирішити проблему, що стоїть перед ним. На додаток до встановлення головних цілей, фахівець з науки управління повинен визначити – яка інформація потрібна для побудови моделі, що задовольняє цим цілям і видає на виході потрібні відомості.
 +
 +
'''Перевірка моделі на достовірність.'''
 +
 
 +
Після побудови моделі її слід перевірити на достовірність. Один з аспектів перевірки полягає у визначенні ступеня відповідності моделі реальному світу. Фахівець з науки управління повинен встановити – чи всі істотні компоненти реальної ситуації вбудовані в модель. Це, звичайно, може виявитися непростою справою, якщо задача складна. Перевірка багатьох моделей управління показала, що вони недосконалі, оскільки не охоплюють всіх релевантних змінних. Природно, чим краще модель відображає реальний світ, тим вище її потенціал як засобу надання допомоги керівнику в прийнятті хорошого рішення, якщо припустити, що модель не дуже складна у використовуванні.
 +
Другий аспект перевірки моделі пов'язаний зі встановленням ступеня, в якому інформація, одержувана з її допомогою, дійсно допомагає керівництву співволодіти з проблемою.
 +
 
 +
'''Використання моделі.'''
 +
 
 +
Після перевірки на достовірність модель готова до використовування. Якщо моделі науки управління створюються фахівцями штабних служб (а так звично і буває), лінійні керівники, для яких вони призначені, повинні брати участь у постановці задачі і встановленні вимог за інформацією, одержуваною з моделі. Згідно дослідженням, коли це має місце, застосування моделей збільшується на 50%. Крім того, таких керівників слід навчити використовувати моделі, пояснивши серед іншого, як модель функціонує, які її потенційні можливості і обмеження.
 +
 
 +
'''Оновлення моделі.'''
 +
 
 +
Навіть якщо використання моделі виявилося успішним, майже напевно вона зажадає оновлення. Керівництво може знайти, що форма вихідних даних не ясна або бажані додаткові дані. Якщо цілі організації змінюються таким чином, що це впливає на критерії прийняття рішень, модель необхідно відповідним чином модифікувати. Аналогічним чином, зміна в зовнішньому оточенні – наприклад, поява нових споживачів, постачальників або технології – може знецінити допущення і початкову інформацію, на яких ґрунтувалася модель при побудові.
 +
 
 +
== Класифікація моделей прийняття управлінських рішень ==
 
Розрізняють три базові типи моделей:
 
Розрізняють три базові типи моделей:
−
# фізична —те, що досліджується за допомогою збільшеного або зменшеного опису об'єкта або системи;
+
* фізична —те, що досліджується за допомогою збільшеного або зменшеного опису об'єкта або системи;
−
# аналогова — досліджуваний об'єкт, котрий поводиться як реальний, але насправді не є таким;
+
* аналогова — досліджуваний об'єкт, котрий поводиться як реальний, але насправді не є таким;
−
# математична — модель, яка також називається символічною. У ній використовуються символи для характеристики властивостей або ознак об'єкта чи події.
+
* математична модель економічного об’єкта (системи) — це його спрощений образ, поданий у вигляді сукупності математич-них співвідношень (рівнянь, нерівностей, логічних співвідношень, графіків тощо).
−
Як і всі засоби та методи, у процесі функціонування моделі науки управління м'''ожуть призвести до помилок'''. Ефективність моделі зменшиться у зв'язку із впливом потенційних погрішностей. Найчастіше трапляються недостовірні вихідні дані, обмежені можливості отримання потрібної інформації, страх користувача, недостатнє практичне використання, надмірно висока вартість.
+
Відповідно до того, що мета моделювання в загальному випадку може бути теоретичною і практичною, моделі також розділяються на два види:
−
Розглянемо найпоширеніші типи математичних моделей, за допомогою яких приймаються рішення:
+
* пізнавальні,
 +
* прагматичні.  
 +
'''Пізнавальні моделі''' є формою організації і представлення знань, засобом з'єднання нових знань з наявними. Тому при виявленні розбіжностей між моделлю і реальністю стає завдання усунення цієї розбіжності за допомогою зміни моделі.
 +
 +
'''Прагматичні моделі''' є засобом керування, організації практичних дій, способом представлення зразково правильних дій, тобто еталонів чи їхніх результатів. Фактично вони є робочим представленням цілей.  
 +
 
 +
Призначення прагматичних моделей полягає в тому, щоб, при виявленні розбіжностей між моделлю і реальністю, розробити способи і засоби для зміни реальності так, щоб наблизити реальність до моделі. Можна сказати, що прагматичні моделі як би відіграють роль деякого стандарту чи зразка, під яким підбудовується як сама діяльність, так і її результат.
 +
 
 +
Прикладами прагматичних моделей можуть бути плани і програми дій, статути організацій і кодекси законів, нормативна база, технологічні схеми різних організаційних операцій, алгоритми, робочі креслення і шаблони, параметри добору і технологічні допуски і т.д.
 +
Як всі засоби і методи, моделі науки управління можуть призвести до помилок. Ефективність моделі може бути понижена дією ряду потенційних погрішностей. Щонайчастіше зустрічаються – недостовірні початкові допущення, обмежені можливості отримання потрібної інформації, страхи користувача, слабке використовування на практиці, надмірно висока вартість.
 +
 +
'''Недостовірні початкові допущення'''. Будь-яка модель спирається на деякі початкові допущення або передумови. Це можуть бути передумови, що піддаються оцінці, наприклад, що витрати на робочу силу в наступні шість місяців складуть 100 тисяч гривень. Такі припущення можна об'єктивно перевірити і підрахувати. Вірогідність того, що вони точні, буде висока. Деякі передумови не піддаються оцінці і не можуть бути об'єктивно перевірені. Припущення про зростання збуту наступного року на 10% — приклад допущення, непіддатливого перевірці. Ніхто не знає напевно, чи відбудеться це дійсно. Оскільки такі передумови є основою моделі, точність останньої залежить від точності передумов. Модель не можна використовувати для прогнозування, наприклад, потреби в запасах, якщо неточні прогнози збуту на майбутній період.
 +
 +
'''Інформаційні обмеження'''. Основна причина невірогідності передумов і інших утруднень – це обмежені можливості в отриманні потрібної інформації, які впливають і на побудову, і на використовування моделей. Точність моделі визначається точністю інформації з проблеми. Якщо ситуація виключно складна, фахівець з науки управління може бути не в змозі одержати інформацію по всіх релевантних чинниках або вбудувати її в модель. Якщо зовнішнє середовище рухоме, інформацію про неї слід обновляти швидко, але це може бути непрактичним.
 +
Побудова моделі найбільш скрутна в умовах невизначеності. Коли необхідна інформація настільки невизначена, що її важко одержати, виходячи з критерію об'єктивності, керівнику, можливо, краще покластися на свій досвід, здібність до думки, інтуїцію і допомогу консультантів.
 +
Страх користувачів. Модель не можна вважати ефективною, якщо нею не користуються. Основна причина невикористовування моделі полягає у тому, що керівники, яким вона призначена, можуть не цілком розуміти одержувані за допомогою моделі результати і тому бояться її застосовувати.
 +
 
 +
'''Слабке використовування на практиці'''. Згідно ряду досліджень рівень методів моделювання в рамках науки управління перевершує рівень використовування моделей. Як наголошувалося вище, одна з причин такої ситуації – страх. Інші причини – це брак знань і опір змінам. Дана проблема підкріплює бажаність того, щоб на стадії побудови моделі штабні фахівці привертали до цієї справи користувачів. Коли люди мають нагоду обговорити і краще зрозуміти питання, метод або передбачувану зміну, їх опір звичайно знижується.
 +
 
 +
'''Надмірна вартість'''. Вигоди від використовування моделі, як і інших методів управління, повинні з лишком виправдовувати її вартість. При встановленні витрат на моделювання керівництву слід враховувати витрати часу керівників вищого і нижчого рівнів на побудову моделі і збір інформації, витрати і час на навчання, вартість обробки і зберігання інформації.
 +
 
 +
== Поняття програми, програмованих та непрограмованих рішень ==
 +
'''Програмовані рішення''' – це ті, що повторюються багатократно і мають напрацьовані правила й процедури прийняття.
 +
 +
'''Непрограмовані рішення''' – це ті, що виниклу проблему мають вирішувати вперше, отже, всі етапи підготовки рішення треба розробляти спеціально.
 +
 +
'''Програма''' - це деталізована послідовність дій, що має деяку мету або завдання і відповідає на реакцію системи та зовнішнього середовища.
 +
 +
Відповідно, '''програмовані рішення''' - це гранично деталізована послідовність дій в суворо певних ситуаціях.
 +
 +
Переваги такого підходу очевидні: знижується вірогідність помилки, зменшується час на ухвалення рішення, з виконавця знімається відповідальність.
 +
 +
Проте зрозуміло, що подібний точний алгоритм годиться лише для суворо певної ситуації. Отже, її невірна ідентифікація може призвести до великих втрат. Крім того, в деяких ситуаціях, з часом така схема може стати неефективною або навіть помилковою. Крім всього іншого жорстка регламентація діяльності робить роботу виконавців нецікавою, позбавляє їх ініціативи і знижує увагу. Як правило, чим вищий рівень управління, на якому приймається рішення, і чим більше їх важливість, тим менше частка програмованих рішень.
 +
 
 +
Непрограмовані рішення використовуються в якісно нових, нестандартних, складних ситуаціях, пов'язаних з дією невідомих чинників.
 +
== Моделі математичного програмування ==
 +
'''Математичне програмування''' — це один із напрямків прикладної математики, предметом якого є задачі на знаходження екстремуму деякої функції за певних заданих умов.
 +
 
 +
Одні з найпоширеніших задач математичного програмування є:
 
* '''модель лінійного програмування''' - використовується, щоб визначити оптимальний спосіб поділу дефіцитних ресурсів за наявності потреб конкурування (планування асортименту виробів, розподіл працівників тощо);
 
* '''модель лінійного програмування''' - використовується, щоб визначити оптимальний спосіб поділу дефіцитних ресурсів за наявності потреб конкурування (планування асортименту виробів, розподіл працівників тощо);
 
* '''модель цілочисельного програмування''' - може використовуватися в різних задачах математичного програмування. Найчастіше є розширенням моделі лінійного програмування, в разі якщо необхідно отримати цілочисельні розвязки.
 
* '''модель цілочисельного програмування''' - може використовуватися в різних задачах математичного програмування. Найчастіше є розширенням моделі лінійного програмування, в разі якщо необхідно отримати цілочисельні розвязки.
 
* '''модель динамічного програмування''' - являє собою математичний апарат, що дає змогу здійснювати планування багатокрокових керованих процесів, а також процесів, які розвиваються у часі.
 
* '''модель динамічного програмування''' - являє собою математичний апарат, що дає змогу здійснювати планування багатокрокових керованих процесів, а також процесів, які розвиваються у часі.
 
* '''теорія ігор''' — метод моделювання оцінки впливу прийнятого рішення на конкурентів. Наприклад, прогнозування реакції конкурентів на зміну цін;
 
* '''теорія ігор''' — метод моделювання оцінки впливу прийнятого рішення на конкурентів. Наприклад, прогнозування реакції конкурентів на зміну цін;
 +
Також математичне моделювання використовується у:
 
* '''модель теорії черг, або модель оптимального обслуговування''' - використовується з метою визначення оптимальної кількості каналів обслуговування стосовно потреби в них. Принциповою проблемою вважається урівноваження витрат на додаткові канали обслуговування та втрат від обслуговування на рівні нижчому, ніж оптимальний;
 
* '''модель теорії черг, або модель оптимального обслуговування''' - використовується з метою визначення оптимальної кількості каналів обслуговування стосовно потреби в них. Принциповою проблемою вважається урівноваження витрат на додаткові канали обслуговування та втрат від обслуговування на рівні нижчому, ніж оптимальний;
 
* '''модель управління запасами''' - застосовується для визначення часу розміщення замовлень на ресурси та їх кількість, а також маси готової продукції на складах. Мета цієї моделі полягає у зведенні до мінімуму негативних наслідків накопичення запасів, що виражається у певних витратах;
 
* '''модель управління запасами''' - застосовується для визначення часу розміщення замовлень на ресурси та їх кількість, а також маси готової продукції на складах. Мета цієї моделі полягає у зведенні до мінімуму негативних наслідків накопичення запасів, що виражається у певних витратах;
 
* '''імітація''' - передбачає процес створення моделі та її експериментальне застосування з метою визначення змін реальної ситуації;
 
* '''імітація''' - передбачає процес створення моделі та її експериментальне застосування з метою визначення змін реальної ситуації;
 +
 +
Розглянемо зазначені задачі математичного програмування та їх можливе застосування біль детально.
 +
 +
=== Модель лінійного програмування. ===
 +
'''Зада́ча ліні́йного програмува́ння''' — задача оптимізації з лінійною цільовою функцією та допустимою множиною обмеженою лінійними рівностями або нерівностями.
 +
 +
Тобто, необхідно мінімізувати
 +
: <math> \sum_{j=1}^n c_j x_j \to \min </math> (1)
 +
при обмеженнях
 +
: <math> \sum_{j=1}^n a_{ij} x_j \leq b_i,\; i = 1, \dots, m_1</math>, (2)
 +
: <math> \sum_{j=1}^n a_{ij} x_j = b_i, \; i = m_1+1, \dots, m</math>, (3)
 +
: <math> x_j \geq 0, \; j = 1, \dots, n_1</math>, (4)
 +
де ''c''<sub>j</sub> (''j'' = 1, …, ''n''), ''a''<sub>ij</sub>(''i'' = 1, …, ''m'')&nbsp;— задані числа.
 +
 +
Задача максимізації функції (1) зводиться до задачі мінімізації шляхом заміни знаків всіх коефіціентів ''c''<sub>j</sub> на протилежні.
 +
Існують наступні методи розвязання задач лінійного програмування:
 +
* Метод потенціалів &mdash; розроблений в 1940 радянськими вченими Л.В. Канторовичем та Гавуріним М. К. в застосуванні до транспортної задачі;
 +
* Симплекс-метод &mdash; цей метод є узагальненням методу потенціалів для випадку загальної задачі лінійного програмування. Розроблений американським вченим Данциґом Дж.-Б. в 1949 році.
 +
* Двоїстий симплекс-метод розроблений згодом після прямого симплекс-методу, і який є, за сутністю, симплекс-методом розв'язання двоїстої задачі лінійного програмування, але сформульованої в термінах вихідної задачі.
 +
Усі ці методи скінченні. Крім того, існують, також, ітеративні методи розв'язання, які дають можливість обчислювати розв'язки задачі із наперед заданою точністю.
 +
 +
=== Модель цілочисельного програмування ===
 +
'''Цілочисельне програмування'''&nbsp;— різновид математичного програмування, що припускає, що шукані значення повинні бути цілими числами.
 +
 +
Розділ математичного програмування, у якому вивчаються методи знаходження екстремумів функцій у просторі параметрів, де всі або деякі змінні є цілими числами.
 +
 +
Найпростіший метод розв'язання задачі цілочисельного програмування&nbsp;— зведення її до задачі лінійного програмування з перевіркою результату на цілочисельність.
 +
 +
==== Булівське програмування ====
 +
 +
До часткового випадку задачі цілочисельного лінійного програмування відносяться задачі, де змінні X можуть приймати всього лише два значення&nbsp;— 0 і 1. Відповідні задачі часто називають задачами '''булівського програмування'''. Найбільш відомі із цих задач&nbsp;— задачі про призначення (якого працівника на яку роботу поставити), задачі вибору маршруту (задача комівояжера, задача листоноші) тощо.
 +
 +
Для розв'язання задач цього типу розробляються специфічні алгоритми, засновані на комбінаториці, графах тощо.
 +
 +
Існують наступні методи розвязання задач цілочисельного програмування:
 +
* Методи відтинання. Метод Гоморі
 +
* Комбінаторні методи. Метод гілок та меж
 +
 +
=== Динамічне програмування ===
 +
 +
'''Динамічне програмування''' - розділ математики, який присвячено теорії і методам розв’язання багатокрокових задач оптимального управління.
 +
 +
У динамічному програмуванні для керованого процесу серед множини усіх допустимих управлінь шукають оптимальне у сенсі деякого критерію тобто таке яке призводить до екстремального (найбільшого або найменшого) значення цільової функції - деякої числової характеристики процесу. Під багатоступеневістю розуміють або багатоступеневу структуру процесу, або розподілення управління на ряд послідовних етапів (ступенів, кроків), що відповідають, як правило, різним моментам часу. Таким чином, в назві "Динамічне програмування" під "програмуванням" розуміють "прийняття рішень", "планування", а слово "динамічне" вказує на суттєве значення часу та порядку виконання операцій в процесах і методах, що розглядаються.
 +
 +
Методи динамічного програмування є складовою частиною методів, які використовуються при дослідженні операцій, і використовуються як у задачах оптимального планування, так і при розв’язанні різних технічних проблем (наприклад, у задачах визначення оптимальних розмірів ступенів багатоступеневих ракет, у задачах оптимального проектування прокладення доріг та ін.)
 +
 +
Методи динамічного програмування використовуються не лише в дискретних, але і в неперервних керованих процесах, наприклад, в таких процесах, коли в кожен момент певного інтервалу часу необхідно приймати рішення. Динамічне програмування також дало новий підхід до задач варіаційного числення.
 +
 +
Хоча метод динамічного програмування суттєво спрощує вихідні задачі, та безпосереднє його використання, як правило, пов’язане з громіздкими обчисленнями. Для подолання цих труднощів розробляються наближені методи динамічного програмування.
 +
 +
=== Теорія ігор ===
 +
'''Тео́рія і́гор'''&nbsp;— теорія математичних моделей прийняття оптимальних рішень в умовах конфлікту. Оскільки сторони, що беруть участь в більшості конфліктів, зацікавлені в тому, щоб приховати від супротивника власні наміри, прийняття рішень в умовах конфлікту, зазвичай, відбувається в умовах невизначеності. Навпаки, фактор невизначеності можна інтерпретувати як противника суб'єкта, який приймає рішення (тим самим прийняття рішень в умовах невизначеності можна розуміти як прийняття рішень в умовах конфлікту). Зокрема, багато тверджень математичної статистики природнім чином формулюються як теоретико-ігрові.
 +
 +
Теорія ігор&nbsp;— розділ прикладної математики, який використовується в соціальних науках (найбільше в економіці), біології, політичних науках, комп'ютерних науках (головним чином для штучного інтелекту) і філософії. Теорія ігор намагається математично зафіксувати поведінку в '''стратегічних ситуаціях''', в яких успіх суб'єкта, що робить вибір залежить від вибору інших учасників. Якщо спочатку розвивався аналіз ігор, в яких один із супротивників виграє за рахунок інших (ігри з нульовою сумою), то згодом почали розглядати широкий клас взаємодій, які були класифіковані за певними критеріями. На сьогоднішній день «теорія ігор щось на кшталт парасольки чи універсальної теорії для раціональної сторони соціальних наук, де соціальні можемо розуміти широко, включаючи як людських так не-людських гравців (комп'ютери, тварини, рослини)» (Роберт Ауманн, 1987)
 +
 +
== Приклад ==
 +
 +
Приклад побудови моделі динамічного програмування та прийняття рішення за результатами проведення тестів над побудованою моделю.
 +
 +
В якості прикладу була взята программа PathFinder. Припустимо, що ми програмуємо деяку комп'ютерну гру. Ігрове поле гри буде у вигляді графа. У грі будуть використовуватися алгоритми пошуку шляху. Існує велика кількість алгоритмів пошуку шляху, і не можна визначити який алгоритм буде кращим в тій чи іншій ситуації.
 +
У грі буде щонайменше 3 типових ситуації:
 +
* Пошук шляху між двома вершинами графа в лабіринті - в даному випадку ігрове поле побудоване у вигляді лабіринту. Нам потрібно знайти найкоротший шлях між двома вершинами графа, які лежать на різних кінцях лабіринту.
 +
* Пошук шляху між двома вершинами графа на відкритому полі - в ігровому полі незначна кількість перешкод.
 +
* Пошук найближчих ресурсів - фінішна вершина не відома. Відомо лише, що вона знаходиться в деякому околі стартової вершини.
 +
Дослідимо 4 алгоритми пошуку шляху:
 +
# алгоритм Дійкстри
 +
# алгоритм А*
 +
# хвильовий алгоритм
 +
# хвильовий* алгоритм
 +
 +
Середовище програми PathFinder дозволяє змоделювати кожну з цих типових ситуацій.
 +
 +
Для початку будуємо граф у вигляді лабіринту з використанням діагональних шляхів. Шлях по діагоналі вважаеться біль дорогим, ніж по прямій. Порівняємо як поводять себе алгоритми при пошуку шляху між двома вершинами графа, що знаходяться у різних кінцях лабіринту[[Файл:PathFinder_Labirint.gif|thumb|right|Лабіринт побудований у середовищі програми PathFinder]].
 +
Результати наведені у таблиці:
 +
{| class="wikitable"
 +
|-
 +
! Алгоритм !! Знайдений шлях !! Витрачений час
 +
|-
 +
| Алгоритм Дійкстри || Вірний || 432 ум. одиниць часу
 +
|-
 +
| Алгоритм А* || Вірний || 570 ум. одиниць часу
 +
|-
 +
| Хвильовий алгоритм || Не вірний || 147 ум. одиниці часу
 +
|-
 +
| Хвильовий* Алгоритм || Вірний || 370 ум. одиниць часу
 +
|}
 +
Якщо побудувати граф без діагональних шляхів, в якому вартість проходження по всіх ребрах фіксована та однакова, то отримаємо наступні результати:
 +
 +
{| class="wikitable"
 +
|-
 +
! Алгоритм !! Знайдений шлях !! Витрачений час
 +
|-
 +
| Алгоритм Дійкстри || Вірний || 426 ум. одиниць часу
 +
|-
 +
| Алгоритм А* || Вірний || 553 ум. одиниць часу
 +
|-
 +
| Хвильовий алгоритм || Вірний || 145 ум. одиниці часу
 +
|-
 +
| Хвильовий* Алгоритм || Вірний || 266 ум. одиниць часу
 +
|}
 +
Якщо побудувати поле без перешкод з ребрами фіксованої довжини, то отримаємо наступні результати:
 +
{| class="wikitable"
 +
|-
 +
! Алгоритм !! Знайдений шлях !! Витрачений час
 +
|-
 +
| Алгоритм Дійкстри || Вірний || 787 ум. одиниць часу
 +
|-
 +
| Алгоритм А* || Вірний || 139 ум. одиниць часу
 +
|-
 +
| Хвильовий алгоритм || Вірний || 161 ум. одиниці часу
 +
|-
 +
| Хвильовий* Алгоритм || Вірний || 440 ум. одиниць часу
 +
|}
 +
В разі використання діагональних відстаней отримаємо наступні результати:
 +
{| class="wikitable"
 +
|-
 +
! Алгоритм !! Знайдений шлях !! Витрачений час
 +
|-
 +
| Алгоритм Дійкстри || Вірний || 788 ум. одиниць часу
 +
|-
 +
| Алгоритм А* || Вірний || 114 ум. одиниць часу
 +
|-
 +
| Хвильовий алгоритм || Не вірний || 163 ум. одиниці часу
 +
|-
 +
| Хвильовий* Алгоритм || Вірний || 779 ум. одиниць часу
 +
|}
 +
 +
За результатами тестування моделі можна зробити наступні висновки:
 +
 +
Алгоритм А* має найкращий результат - завжди знаходить вірний шлях, знаходить шлях швидше за інші алгоритми. Проте зі зростанням кількості перешкод між стартовою та фінішною вершиною, час, котрий алгоритм А* використовує для пошуку шляху зростає. І коли ми маємо справу з лабіринтом, то показники алгоритму А* найгірші. Алгоритм Дійкстри завжди знаходить вірний шлях, проте витрачає багато часу. Кількість витраченого часу не змінюється від кількості перешкод на шляху між стартовою та фінішною вершинами. Хвильовий алгоритм дуже швидкий, проте знаходить вірний шлях лише на графах з фіксованою довжиною ребра. Хвильовий* алгоритм працює швидше ніж алгоритм Дійкстри, якщо у графі переважна кількість ребер фіксованої одиничної довжини. Чим більше ребер різної довжини, тим довше буде шукати шлях алгоритм. І при великій кількості таких ребер він буде найгіршим.
 +
 +
Тому можна винести наступні рішення, котрі надалі використовувати при програмуванні гри:
 +
 +
1. На ігрових полях без великої кількості перешкод використовувати алгоритм А*.
 +
 +
2. У лабіринті, в залежності від типу ребер графа:
 +
* Якщо ребра одиничної довжини - хвильовий алгоритм;
 +
* Якщо переважна кількість ребер одиничної довжини, але є ребра не одиничної довжини - хвильовий* алгоритм;
 +
* Якщо ребра довільної довжини - алгоритм Дійкстри.
 +
 +
3. Для пошуку ресурсів, в залежності від типу ребер графа:
 +
* Якщо ребра одиничної довжини - хвильовий алгоритм;
 +
* Якщо переважна кількість ребер одиничної довжини, але є ребра не одиничної довжини - хвильовий* алгоритм;
 +
* Якщо ребра довільної довжини - алгоритм Дійкстри.
 +
 +
Потрібно зазначити, що тестувати поведінку алгоритмів пошуку шляху у справжній грі буде важче, і краще за все скористатися моделлю.

Поточна версія на 05:46, 23 червня 2011

Поняття моделі та моделювання

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

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

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

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

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

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

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

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

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

Модельний опис закономірностей змісту робіт по окремих етапах процесу ухвалення рішень, а також зв'язків між даними етапами є важливою передумовою подальшого розвитку аналізу господарської діяльності. З другого боку, результати аналізу дозволяють удосконалювати розробку моделей і наблизити їх до реальної ситуації управління господарською діяльністю. Моделі ухвалення рішень підтримують у першу чергу кількісний аналіз господарських процесів. Моделі дозволяють легше пройти етапи рутинного аналізу – аж до їх автоматизації. Якісний аналіз просувається углиб і вшир, залишаючи пізнані області процесу для модельних описів. Модель ухвалення рішень є формалізованою частиною рішення управлінської задачі. Одержане на її основі рішення оптимальне лише з погляду формалізованих умов задачі. Суб'єкт управління доповнює одержане «модельне рішення» необхідним якісним аналізом, враховує свій досвід та інтуїцію і формулює рішення.

Моделі «навчають» враховувати всі формалізовані умови керованого процесу. Творчістю кожного конкретного керівника є облік всієї решти (специфічних з погляду моделі) умов рішення управлінської задачі.

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

Формування вимог і адекватність моделей

Формування вимог і адекватності моделей

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

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

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

Порядок розробки та використання моделей

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

  • постановка завдання;
  • формування моделі;
  • перевірка моделі на достовірність;
  • використання моделі;
  • відновлення моделі.

Постановка задачі.

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

Побудова моделі.

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

Перевірка моделі на достовірність.

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

Використання моделі.

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

Оновлення моделі.

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

Класифікація моделей прийняття управлінських рішень

Розрізняють три базові типи моделей:

  • фізична —те, що досліджується за допомогою збільшеного або зменшеного опису об'єкта або системи;
  • аналогова — досліджуваний об'єкт, котрий поводиться як реальний, але насправді не є таким;
  • математична модель економічного об’єкта (системи) — це його спрощений образ, поданий у вигляді сукупності математич-них співвідношень (рівнянь, нерівностей, логічних співвідношень, графіків тощо).

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

  • пізнавальні,
  • прагматичні.

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

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

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

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

Недостовірні початкові допущення. Будь-яка модель спирається на деякі початкові допущення або передумови. Це можуть бути передумови, що піддаються оцінці, наприклад, що витрати на робочу силу в наступні шість місяців складуть 100 тисяч гривень. Такі припущення можна об'єктивно перевірити і підрахувати. Вірогідність того, що вони точні, буде висока. Деякі передумови не піддаються оцінці і не можуть бути об'єктивно перевірені. Припущення про зростання збуту наступного року на 10% — приклад допущення, непіддатливого перевірці. Ніхто не знає напевно, чи відбудеться це дійсно. Оскільки такі передумови є основою моделі, точність останньої залежить від точності передумов. Модель не можна використовувати для прогнозування, наприклад, потреби в запасах, якщо неточні прогнози збуту на майбутній період.

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

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

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

Поняття програми, програмованих та непрограмованих рішень

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

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

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

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

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

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

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

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

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

Одні з найпоширеніших задач математичного програмування є:

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

Також математичне моделювання використовується у:

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

Розглянемо зазначені задачі математичного програмування та їх можливе застосування біль детально.

Модель лінійного програмування.

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

Тобто, необхідно мінімізувати

Неможливо розібрати вираз (невідома помилка): \sum_{j=1}^n c_j x_j \to \min 
(1)

при обмеженнях

Неможливо розібрати вираз (невідома помилка): \sum_{j=1}^n a_{ij} x_j \leq b_i,\; i = 1, \dots, m_1

, (2)

Неможливо розібрати вираз (невідома помилка): \sum_{j=1}^n a_{ij} x_j = b_i, \; i = m_1+1, \dots, m

, (3)

Неможливо розібрати вираз (невідома помилка): x_j \geq 0, \; j = 1, \dots, n_1

, (4) де cj (j = 1, …, n), aij(i = 1, …, m) — задані числа.

Задача максимізації функції (1) зводиться до задачі мінімізації шляхом заміни знаків всіх коефіціентів cj на протилежні. Існують наступні методи розвязання задач лінійного програмування:

  • Метод потенціалів — розроблений в 1940 радянськими вченими Л.В. Канторовичем та Гавуріним М. К. в застосуванні до транспортної задачі;
  • Симплекс-метод — цей метод є узагальненням методу потенціалів для випадку загальної задачі лінійного програмування. Розроблений американським вченим Данциґом Дж.-Б. в 1949 році.
  • Двоїстий симплекс-метод розроблений згодом після прямого симплекс-методу, і який є, за сутністю, симплекс-методом розв'язання двоїстої задачі лінійного програмування, але сформульованої в термінах вихідної задачі.

Усі ці методи скінченні. Крім того, існують, також, ітеративні методи розв'язання, які дають можливість обчислювати розв'язки задачі із наперед заданою точністю.

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

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

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

Найпростіший метод розв'язання задачі цілочисельного програмування — зведення її до задачі лінійного програмування з перевіркою результату на цілочисельність.

Булівське програмування

До часткового випадку задачі цілочисельного лінійного програмування відносяться задачі, де змінні X можуть приймати всього лише два значення — 0 і 1. Відповідні задачі часто називають задачами булівського програмування. Найбільш відомі із цих задач — задачі про призначення (якого працівника на яку роботу поставити), задачі вибору маршруту (задача комівояжера, задача листоноші) тощо.

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

Існують наступні методи розвязання задач цілочисельного програмування:

  • Методи відтинання. Метод Гоморі
  • Комбінаторні методи. Метод гілок та меж

Динамічне програмування

Динамічне програмування - розділ математики, який присвячено теорії і методам розв’язання багатокрокових задач оптимального управління.

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

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

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

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

Теорія ігор

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

Теорія ігор — розділ прикладної математики, який використовується в соціальних науках (найбільше в економіці), біології, політичних науках, комп'ютерних науках (головним чином для штучного інтелекту) і філософії. Теорія ігор намагається математично зафіксувати поведінку в стратегічних ситуаціях, в яких успіх суб'єкта, що робить вибір залежить від вибору інших учасників. Якщо спочатку розвивався аналіз ігор, в яких один із супротивників виграє за рахунок інших (ігри з нульовою сумою), то згодом почали розглядати широкий клас взаємодій, які були класифіковані за певними критеріями. На сьогоднішній день «теорія ігор щось на кшталт парасольки чи універсальної теорії для раціональної сторони соціальних наук, де соціальні можемо розуміти широко, включаючи як людських так не-людських гравців (комп'ютери, тварини, рослини)» (Роберт Ауманн, 1987)

Приклад

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

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

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

Дослідимо 4 алгоритми пошуку шляху:

  1. алгоритм Дійкстри
  2. алгоритм А*
  3. хвильовий алгоритм
  4. хвильовий* алгоритм

Середовище програми PathFinder дозволяє змоделювати кожну з цих типових ситуацій.

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

Результати наведені у таблиці:

Алгоритм Знайдений шлях Витрачений час
Алгоритм Дійкстри Вірний 432 ум. одиниць часу
Алгоритм А* Вірний 570 ум. одиниць часу
Хвильовий алгоритм Не вірний 147 ум. одиниці часу
Хвильовий* Алгоритм Вірний 370 ум. одиниць часу

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

Алгоритм Знайдений шлях Витрачений час
Алгоритм Дійкстри Вірний 426 ум. одиниць часу
Алгоритм А* Вірний 553 ум. одиниць часу
Хвильовий алгоритм Вірний 145 ум. одиниці часу
Хвильовий* Алгоритм Вірний 266 ум. одиниць часу

Якщо побудувати поле без перешкод з ребрами фіксованої довжини, то отримаємо наступні результати:

Алгоритм Знайдений шлях Витрачений час
Алгоритм Дійкстри Вірний 787 ум. одиниць часу
Алгоритм А* Вірний 139 ум. одиниць часу
Хвильовий алгоритм Вірний 161 ум. одиниці часу
Хвильовий* Алгоритм Вірний 440 ум. одиниць часу

В разі використання діагональних відстаней отримаємо наступні результати:

Алгоритм Знайдений шлях Витрачений час
Алгоритм Дійкстри Вірний 788 ум. одиниць часу
Алгоритм А* Вірний 114 ум. одиниць часу
Хвильовий алгоритм Не вірний 163 ум. одиниці часу
Хвильовий* Алгоритм Вірний 779 ум. одиниць часу

За результатами тестування моделі можна зробити наступні висновки:

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

Тому можна винести наступні рішення, котрі надалі використовувати при програмуванні гри:

1. На ігрових полях без великої кількості перешкод використовувати алгоритм А*.

2. У лабіринті, в залежності від типу ребер графа:

  • Якщо ребра одиничної довжини - хвильовий алгоритм;
  • Якщо переважна кількість ребер одиничної довжини, але є ребра не одиничної довжини - хвильовий* алгоритм;
  • Якщо ребра довільної довжини - алгоритм Дійкстри.

3. Для пошуку ресурсів, в залежності від типу ребер графа:

  • Якщо ребра одиничної довжини - хвильовий алгоритм;
  • Якщо переважна кількість ребер одиничної довжини, але є ребра не одиничної довжини - хвильовий* алгоритм;
  • Якщо ребра довільної довжини - алгоритм Дійкстри.

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

Отримано з https://wiki.cusu.edu.ua/index.php?title=Прийняття_рішень_за_результатами_моделювання&oldid=49532