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

 

Модель є образним представленням якогось об’єкту чи процесу і використовується для аналізу або вивчення цього об’єкту чи процесу.

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

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

Можна виділити наступні основні етапи операційного дослідження:

- спостереження явища й збір вихідних даних;

- постановка задачі;

- побудова математичної моделі;

- розрахунок моделі;

- тестування моделі й аналіз вихідних даних. Якщо отримані результати не задовольняють дослідника, то треба або повернутися на етап побудови математичної моделі, тобто запропонувати для рішення задачі іншу математичну модель; або повернутися на етап постановки задачі, тобто поставити задачу більш коректно;

- застосування результатів досліджень.

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

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

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

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

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

б) Визначення параметрів моделі, тобто заздалегідь відомих фіксованих факторів, на значення яких дослідник не впливає.

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

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

д) Виявлення невідомих факторів, тобто величин, які можуть змінюватись випадковим або невизначеним чином.

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

Вводяться наступні умовні позначки:  – параметри моделі;  – керуючі змінні або рішення; – область припустимих рішень;  – випадкові або невизначені фактори;  – цільова функція або критерій ефективності (критерій оптимальності).

 

.                                                                                     (1.1)

 

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

 

,                                                            (1.2)

 

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

 

.                                               (1.3)

 

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

Основні принципи побудови математичної моделі динамічного програмування.

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

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

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

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

На рисунку 1.4 зображена класифікація математичних моделей і місце динамічних моделей у загальній структурі [1].

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

По обліку невідомих факторів математичні моделі діляться на детерміновані, стохастичні й моделі з елементами невизначеності.

У стохастичних моделях невідомі фактори – це випадкові величини, для яких відомі функції розподілу й різні статистичні характеристики (математичне очікування, дисперсія, середньоквадратичне відхилення й т.д.). Серед стохастичних можна виділити:

- моделі стохастичного програмування, у яких в цільову функцію (1.2) входять випадкові величини;

- моделі теорії випадкових процесів, призначені для вивчення процесів, стан яких у кожен момент часу є випадковою величиною;

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

 

Рисунок 1.4 – Класифікація математичних моделей

 

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

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

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

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

У динамічних моделях на відміну від статичних лінійних і нелінійних моделей враховується фактор часу. Критерій оптимальності в динамічних моделях може бути самого загального виду (і навіть взагалі не бути функцією), однак для нього повинні виконуватися певні властивості. Розрахунок динамічних моделей складний, і для кожної конкретної задачі необхідно розробляти спеціальний алгоритм рішення [4].

Графічні моделі використаються тоді, коли завдання зручно представити у вигляді графічної структури.