На кожному кроці управління вибирається так, щоб воно в сукупності з усіма оптимальними управліннями на всіх наступних кроках приводило до найкращого сумарним показником ефективності. Тобто управління повинне вибиратися виходячи з оптимальності управління в цілому, а не тільки на якомусь конкретному етапі. В основу цього принципу покладено особливості моделі ДП. На основі цього принципу були сформульовані рекурентні формули Беллмана. Застосування даних формул можливо на базі зворотного або прямий схеми Беллмана. В обох випадках є показником ефективності k -ого кроку. На кожному кроці оптимальне управління вибирається з безлічі можливих управлінь.
Зворотній схема Беллмана.
При зворотній схемі оптимізація здійснюється в результаті зворотного руху від останнього кроку до першого. Спочатку визначається оптимальна стратегія управління на n-му кроці, потім на двох останніх кроках, потім на трьох останніх кроках і т.д. до першого кроку.
n-й крок. стан системи, залежне від стану. - управління на n-му кроці, - цільова функція n -го кроку.
Оптимальний показник ефективності n -го кроку. рівний сумарному показнику ефективності всіх попередніх кроків на безлічі всіляких управлінь всіляких станів системи.
Таким чином, в результаті проходження всіх кроків від останнього до першого визначається оптимальне значення цільової функції. Щоб знайти оптимальну стратегію управління, тобто визначити рішення задачі -. необхідно знову пройти всю послідовність кроків, тільки від початку до кінця.
На першому кроці в якості оптимального управління вибирається знайдене умовно оптимальне управління. характеризується показником ефективності. Знаючи і. на другому кроці знаходиться і управління і т.д.
Процес рішення можна представити у вигляді схеми:
Пряма схема Беллмана
При прямий схемою процес пошуку рішення виконується в напрямку від першого кроку до останнього. Спочатку визначають оптимальну стратегію управління на першому кроці, потім на двох перших кроках, потім на трьох перших кроках і т.д. до останнього кроку.
На даному етапі стан системи -. попередній стан -. - безліч управлінь на першому кроці. Показник ефективності 1-го кроку -.
В результаті проходження всіх кроків від першого до останнього визначається оптимальне значення цільової функції, яке прирівнюється оптимальному показнику ефективності n -го кроку. Щоб знайти оптимальну стратегію управління, тобто визначити рішення задачі -. необхідно знову пройти всю послідовність кроків - від останнього до першого.
Пошук оптимальної стратегії можна представити у вигляді схеми:
Загальна схема застосування методу ДП
1. Вибирається спосіб поділу процесу управління на кроки.
2. Визначаються параметри стану і змінні управління на кожному кроці.
3. Записуються рівняння станів.
4. Вводиться цільова функція.
5. Вводиться в розгляд умовні максимуми (мінімуми) і умовне оптимальне керування на k-му кроці: (в разі зворотного схеми Беллмана), (при прямій схемою Беллмана).
6. Записуються основні рівняння для обраної схеми Беллмана.
7. Послідовно вирішуються записані рівняння Беллмана і виходять дві послідовності функцій: і.
8. Після виконання умовної оптимізації визначається оптимальне рішення поставленої задачі і.
Завдання розподілу коштів між підприємствами
Завдання розподілу ресурсів між підприємствами є завданням динамічного програмування.
Нехай є деяка сума коштів, яку необхідно вкласти в одне або кілька підприємств, щоб отримати максимальний прибуток від інвестування. Передбачається, що в кожне з розглянутих підприємств може бути вкладена як вся сума інвестицій, так і частково, або в підприємство може бути нічого не вкладено, якщо інвестиції в нього не ефективні. Для кожного підприємства повинен бути розрахований показник ефективності інвестицій, який визначається в результаті рішення задачі ЛП про планування виробництва.
Математична модель для кожного виду підприємства має вигляд:
Цільова функція при обмеженнях:
У моделі використані наступні позначення:
- ціна на j- ий вид товару для k -ого підприємства;
- оптимальний обсяг закупівлі i -ого виду ресурсу k-им підприємством;
- рівень запасу i -ого виду ресурсу на k -му підприємстві;
- оптимальний план виробництва j -ого виду продукції на k -му підприємстві;
- норма витрати i -ого виду ресурсу для виробництва одиниці продукції j -ого виду на k -му підприємстві;
- ринкова ціна i -ого виду ресурсу для k -ого підприємства;
- обсяг фінансових коштів, виділених k -ому підприємству;
- мінімальний обсяг замовлень j -ого виду продукції на k -му підприємстві;
- гранична місткість ринку по j-ому виду продукції для k -ого підприємства.
В результаті рішення даної задачі буде отримана величина додаткового доходу від роботи підприємства, яка являє собою різницю прибутку при виділенні інвестицій і прибутку, якщо інвестиції не виробляються.
Обчислені методами лінійного програмування показники ефективності діяльності кожного підприємства в залежності від обсягу одержуваних фінансових коштів в подальшому використовуються для знаходження оптимального розподілу коштів між підприємствами методами динамічного програмування.
1. додатковий дохід кожного підприємства не залежить від обсягів вкладення коштів в інші підприємства;
2. додатковий дохід кожного підприємства виражається в одних і тих же одиницях;
3. сукупний додатковий дохід дорівнює сумі додаткових доходів, отриманих кожним підприємством.
Для визначення оптимальних засобів інвестування необхідно пройти наступні етапи:
1. інтервал зміни виділених коштів розбивається на елементарні відрізки;
2. для заданих значень виділених коштів визначаються показники ефективності для всіх підприємств;
3. по зворотній (прямий) схемою використовуються рівняння Беллмана;
4. в зворотному (прямий) послідовності, починаючи від знаходяться оптимальні значення виділених коштів.
Приклад. Планується діяльність 4 промислових підприємств на черговий рік. Необхідно між ними розподілити 400 одиниць обмеженого ресурсу Q. Кожне підприємство i в залежності від обсягу виділених коштів x отримує додатковий дохід fi (x). Розподіл ресурсів проводиться з точністю 80 одиниць. Необхідно визначити оптимальний розподіл коштів між підприємствами, що забезпечує максимальну ефективність діяльності всіх підприємств.
Обсяги отриманих додаткових доходів в залежності від виділених ресурсів x представлені в таблиці 1.
Обсяг виділених ресурсів, x
Додатковий дохід підприємства в залежності від обсягу виділених коштів, fi (x)
Розглянемо зворотну схему Беллмана.
Згідно зворотного схемою Беллмана починаємо з визначення умовно оптимальних капіталовкладень, що виділяються для останнього четвертого (n -ого) підприємства. Для цього знаходимо значення для кожного x. приймає значення 0, 80, 160, 240, 320, 400.
Показник ефективності 4-го підприємства, що дорівнює сумарним показником ефективності на всіх етапах визначається як.
Знаходимо - сумарний показник ефективності діяльності 3 і 4 підприємств.
Обчислимо об'єднаний показник ефективності діяльності 2, 3 і 4 підприємств -.
Об'єднаний показник ефективності діяльності 4-х підприємств -.
Обсяг виділених ресурсів, x
Показники ефективності підприємств в залежності від обсягу виділених коштів, Z i (x)
Щоб знайти оптимальну стратегію управління, необхідно розглянути всю послідовність кроків від останнього до першого.
В результаті рішення задачі розподілу коштів між підприємствами отримали, що для забезпечення максимальної ефективності діяльності 4-х підприємств, що дорівнює 203 у.о. 1-го і 2-го підприємствам слід не виділяти ресурсів, 3 підприємству необхідно виділити 240 одиниць ресурсу, 4-му - 160 одиниць.
Приріст випуску продукції i - ого підприємства, fi (x)
Частина коштів, що виділяються підприємствам, млн руб, x
Приріст випуску продукції i - ого підприємства, fi (x)
Частина коштів, що виділяються підприємствам, млн руб, x
Приріст випуску продукції i - ого підприємства, fi (x)
Частина коштів, що виділяються підприємствам, млн руб, xi
Приріст випуску продукції i - ого підприємства, fi (x)
Частина коштів, що виділяються підприємствам, млн руб, xi