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

Версія за 19:02, 22 червня 2011

Моделювання (рос. моделирование, англ. modelling, simulation, нім. Modellieren n, Modellierung f, Simulation f) — це метод дослідження явищ і процесів, що ґрунтується на заміні конкретного об'єкта досліджень (оригіналу) іншим, подібним до нього (моделлю).

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

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

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

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

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

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

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

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

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

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

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

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

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

Неможливо розібрати вираз (невідома помилка): \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) де c_j (j = 1, …, n), a_ij(i = 1, …, m) — задані числа.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Приклад

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

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

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

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

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

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

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

Лабіринт побудований у середовищі програми PathFinder

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

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