Принцип оптимальності Беллмана

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

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

· Об’єктом дослідження повинна служити управляєча система (об’єкт) з заданими допустимими станами і допустимим управлінням;

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

· Задача не повинна залежати від кількості кроків і бути визначеною кожному з них;

· Стан системи на кожному кроці повинен описуватись однаковим (по складу) набором параметрів;

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

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

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

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

Рис. 5.1

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

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

(5.14)

де

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

ü Оптимальна стратегія управління повинна задовольняти наступній вимозі: який би не був початковий стан на му кроціі вибране на цьому кроці управління , наступне управління (управлінські рішення) повинні бути оптимальними по відношенню до стану , отриманому в результаті рішення, прийнятого на кроці .

Основне співвідношення (5.14) дозволяє знайти функції тільки в співвідношенні з початковою умовою, таким в нашому випадку є рівняння

.

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

.

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

В той же час, говорячи про динамічне програмування як про метод рішення оптимізаціонних задач, необхідно відмітити і його слабкі сторони. Так, в запропонованій схемі рішення задачі (5.3)-(5.4) суттєвим образом використовується той факт, що система обмежень має тільки одне рівняння, і, як наслідок, її стан задається одним числом – нерозподіленим ресурсом . При наявності деяких обмежень стан управляємого об’єкту на кожному кроці характеризується вже набором параметрів і стабілізувати значення функцій необхідно для багаторазово більшої кількості точок. Остання причина робить застосування метода динамічного програмування явно нераціональним або навіть просто неможливим. Дану проблему його основоположник Р.Беллман ефектно назвав «прокляттям багатомірності». В наш час розроблені окремі шляхи подолання вказаних проблем. Докладну інформацію про них можна знайти в спеціальній літературі [4,5].

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

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

В даній задачі розглядається деякий економічний об’єкт (фірма, магазин, завод….), що функціонує на протязі деякого числа періодів, що позначаються номерами . Кожен період характеризується нормативною потребою в визначеній кількості однотипних працівників . Той же об’єм робіт може бути виконаний іншою кількістю працівників , що, потребує додаткових витрат чи за рахунок нераціонального використання робочої сили, або в разі підвищення оплати за інтенсивну роботу. Розміри цих додаткових витримок описуються функціями , де - відхилення фактичної чисельності робочих від планово необхідної , причому . Управлінське рішення на кроці заключається в виборі величини зміни числа співробітників , що однозначно визначає кількість робочих на протязі наступного періоду: . Затрати по витраті кількості робітників (найму і звільненню) при переході при переході від періоду і до періоду задаються функцією , де також . Тоді сумарні витримки, визвані на кроці рішенням, характеризуються значенням функцій:

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

де (5.15)

На основі сфотрмульованої моделі ставиться задача мінімізації цільової функції (витримок) (5.15). добавимо, що постановка задачі не буде коректною, якщо не задати початкову умову на кількість робітників. Існує дві модифікації задачі, що визначаються типом початкової вимоги: в першому випадку задається початкове значення на першому етапі , а в другому – необхідна кількість в м періоді .

Дата добавления: 2013-12-14