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

Нехай процес оптимізації розбитий на п кроків. На кожному кроці потрібно визначити два типи змінних - змінну стану S та змінну керування х. Змінна стану S визначає, в яких станах може бути система на k- мукроці. Залежно від S на цьому кроці можна використати деякі керування, які характеризуються змінною х. Використання керування х на k- мукроці дає деякий результат f_k(S,x_k) iпереводить систему в деякий новий стан S'(S,x_k). Для кожного можливого стану на k- мукроці (з усіх можливих керувань) вибирається таке керування х_к, щоб результат, якии отримаємо з k- го по п- йкрок був оптимальним. Числова характеристика цього результату називається функцією Белмана F_k(S) та залежить від номера кроку k і стану системи S. Отже, сутність принципу оптимальності Белмана полягає в тому, що яким би не був стан системи в результаті певної кількості кроків, на найближчому кроці керування потрібно вибирати так, щоб воно разом з оптимальним керуванням на всіх наступних кроках приводило до найкращого виграшу.

Весь розв’язок задачі розбивається на два етапи. На першому етапі знаходять функцію Белмана й оптимальне керування для всіх можливих станів на кожному кроці, починаючи з першого. На останньому п- мукроці знайти оптимальне керування і значення функції Белмана F_n(S) нескладно, оскільки F_n(S) = max{f_k(S,x_n)}, де максимум знаходять за всіма можливими значеннями

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

Цей максимум (чи мінімум) знаходиться за всіма можливими для k i S значеннями керованої змінної х_k.

Після того, як функція Белмана і відповідне оптимальне керування знайдені для всіх кроків з першого до п- го(на першому кроці k=1 стан системи рівний її початковому стану

), виконуємо другий етап розв’язання задачі згідно з алгоритмом зворотної прогонки. Знаючи оптимальне керування на n -му кроці х_п, ми можемо шукати оптимальне керування на (п-1) кроці доти, доки не дійдемо до першого.

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

8.3. Прикладні моделі динамічного програмування (модель оптимального розподілу фінансових ресурсів між інвестиційними проектами)

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

Позначимо через x _і - розмір інвестицій, виділених під і -ий проект (

), де і - індекс проекту. Отже, має місце рівність:

На основі попереднього аналізу встановлено, що приріст продукції внаслідок реалізації і- гопроекту задається функцією

. Тоді сумарний приріст продукції фірми становитиме:

Отже, наша задача полягає у заходженні таких значень

які задовольняють (8.5) і забезпечують максимум функції (8.6).

Позначимо максимальний сумарний приріст продукції, одержаний при розподілі інвестицій розміром х для перших k проектів, через F_k(x), причому

Для визначення функцій F_k(x) побудуємо рекурентне рівняння за допомогою кількох етапів.

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

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

приросту продукції, а залишок (х-х₂) виділяється першому проекту, який дає

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

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

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

. Наявний залишок (х-х₃) надамо першому та другому проектам, які при оптимальному розподілі дають приріст F₂(x-x₃) грошових одиниць. Отже, максимальний ефект, який отримаємо від розподілу інвестицій між першими трьома проектами буде:

Розглянемо загальний випадок розподілу інвестицій для перших k проектів. Нехай k- мупроекту виділено х_к одиниць інвестицій, які забезпечать йому приріст продукції розміром f_k(х_k). Залишок інвестицій (х-х_k) віддамо першим (k-1) проектам і вони при оптимальному розподілі принесуть фірмі

приросту продукції. При цьому фірма отримає сумарний приріст продукції рівний:

Отже, ми отримали рекурентне співвідношення (8.7), яке представляє собою рівняння Белмана для задачі (8.5) – (8.6).

Вступ ТЕМА 1. ПРЕДМЕТ, МЕТОД І ЗАДАЧІ КУРСУ 1.5 Основні дефініції математичного моделювання. 1.6 Моделювання в економіці та його використання в розвитку та формалізації економічної теорії. 1.7 Теоретичні основи математичного моделювання та класифікація моделей. 1.8 Математична модель та її основні елементи. 1.9 Принципи та етапи побудови моделей. ТЕМА 2. ФУНКЦІЇ І ГРАФІКИ В ЕКОМІЧНОМУ МОДЕЛЮВАННІ 2.1 Поняття функціональної залежності. 2.2 Способи завдання та дослідження функцій. 2.3. Основні елементарні функції. ТЕМА 3. МОДЕЛІ ЗАДАЧ ЛІНІЙНОГО ПРОГРАМУВАННЯ ТА МЕТОДИ ЇХ РОЗВ'ЯЗУВАННЯ 3.1 Постановка задач лінійного програмування, їх моделі та основні форми. 3.2 Графічний метод розв'язування задач лінійного програмування. 3.3 Симплексний метод розв'язування задач лінійного програмування. ТЕМА 4. ТЕОРІЯ ДВОЇСТОСТІ ТА КІЛЬКІСНИЙ АНАЛІЗ ОПТИМІЗАЦІЙНИХ РОЗРАХУКІВ 4.1 Двоїстість у задачах лінійного програмування. 4.2 Основні теореми двоїстості. 4.3 Двоїстий симплекс-метод. 4.4 Економіко-математичний аналіз оптимальних розрахунків. ТЕМА 5. ТРАНСПОРТНА ЗАДАЧА 5.1 Постановка транспортної задачі та її математична модель. 5.2 Методи побудови початкового опорного плану. 5.3 Метод потенціалів. 5.4 Практичне застосування транспортної задачі. Модель оптимального розподілу фінансових ресурсів банку. Модель оптимізації штатного розпису фірми. ТЕМА 6. ЗАДАЧІ ЦІЛОЧИСЛОВОГО ЛІНІЙНОГО ПРОГРАМУВАННЯ ТА МЕТОДИ ЇХ РОЗВ'ЯЗАННЯ 6.1 Постановка задачі цілочислового лінійного програмування. 6.2 Методи розв'язування задач цілочислового лінійного програмування. 6.3 Прикладні моделі задач цілочислового лінійного програмування. ТЕМА 7. НЕЛІНІЙНІ ОПТИМІЗАЦІЙНІ МОДЕЛІ ЕКОНОМІЧНИХ СИСТЕМ 7.1 Постановка задачі нелінійного програмування та її характерні особливості. 7.2 Основні види задач нелінійного програмування. Прикладне використання методу множників Лагранжа. ТЕМА 8. ДИНАМІЧЕ ПРОГРАМУВАННЯ 8.1 Постановка задачі динамічного програмування. 8.2 Методи розв’язування задач динамічного програмування. 8.3 Прикладні моделі динамічного програмування.