Задача динамічного программирования

Курсовая робота з теорії оптимального управління економічними системами.

Тема: Завдання динамічного программирования.

I.Основные поняття і обозначения.

Динамічний програмування — це математичний метод пошуку оптимального управління, спеціально пристосований до многошаговым процесам. Розглянемо приклад такої процесса.

Нехай планується діяльність групи підприємств на N років. Тут кроком є рік. На початку 1-го року в розвиток підприємств виділяються кошти, що їх якось розподілені між тими підприємствами. У процесі функціонування виділених коштів частково витрачаються. Кожне підприємство протягом року приносить певний дохід, залежить від вкладених коштів. На початку року наявні кошти можуть перерозподілятися між підприємствами: кожному їх виділяється певна частка средств.

Ставиться питання: як на початку кожного року розподіляти наявні кошти між підприємствами, щоб сумарний прибуток від всіх підприємств за N років було максимальным?

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

УВ кожному кроці має вибиратися з урахуванням інтересів усіх його наслідки у майбутньому. УВ має бути далекоглядним, з урахуванням перспективи. Немає сенсу вибирати на аналізованому кроці найкраще УВ, якщо це завадить отримати найкращі результати інших кроків. УВ кожному кроці треба обирати «з заглядыванием у майбутнє», інакше можливі серйозні ошибки.

Справді, припустимо, що у розглянутим групі підприємств одні зайняті випуском предметів споживання, інші виробляють при цьому машини. Причому метою є одержання N років максимального обсягу випуску предметів споживання. Нехай плануються капіталовкладення перший рік. Виходячи із вузьких інтересів даного кроку (року), ми мала б усі засоби вкласти у виробництво предметів споживання, пустити наявні машини на повну міць і домогтися під кінець року максимального обсягу продукції. Але правильним буде таке рішення, у цілому? Вочевидь ні. З огляду на майбутнє, необхідно виділити якусь крихту засобів і виробництва машин. У цьому обсяг продукції протягом першого року, природно, знизиться, зате буде створено умови, дозволяють збільшувати його виробництво наступні годы.

У формалізмі вирішення завдань методом динамічного програмування використовуватимуться такі обозначения:

N — число шагов.

— вектор, описывающий стан системи на k-м шаге.

— початкова стан, т. е. cостояние на 1-му шаге.

— кінцеве стан, т. е. cостояние на останньому шаге.

Xk — область допустимих станів на k-ом шаге.

— вектор УВ на k-ом кроці, який би перехід системи зі стану xk-1 до стану xk.

Uk -область допустимих УВ на k-ом шаге.

Wk — величина виграшу, отриманого у результаті k-го шага.

P.S — загальний виграш за N шагов.

— вектор оптимальної стратегії управління чи ОУВ за N шагов.

Sk+1() — максимальний виграш, отримуваний під час переходу із будь-якої стану в кінцеве состояниепри оптимальної стратегії управління, починаючи з (k+1)-го шага.

S1() — максимальний виграш, отримуваний за N кроків під час переходу системи з початкового состоянияв конечноепри реалізації оптимальної стратегії управління. Вочевидь, що P. S = S1(), если-фиксировано.

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

Умова відсутності післядії. Стан, у якому перейшла система за k-й крок, залежить від состоянияи обраного УВи залежить від того, як система прийшла б у стан, то есть.

Аналогічно, величина виграшу Wk залежить від состоянияи обраного УВ, тобто.

Умова аддитивности цільової функції. Загальний виграш за N кроків обчислюється за такою формулою.

Визначення. Оптимальною стратегією управленияназывается сукупність УВ, тобто, у результаті яких система за N кроків переходить з початкового состоянияв конечноеи у своїй загальний виграш P. S приймає найбільше значение.

Умова відсутності післядії дозволяє сформулювати принцип оптимальності Белмана.

Принцип оптимальності. Яке було дозволене стан системыперед черговим 1-му кроком, треба вибрати дозволене УВна цьому кроці те щоб виграш Wi на 1-му кроці плюс оптимальний виграш усім наступні кроки був максимальным.

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

Управління може слугувати гарним чи поганим, ефективним чи неефективним. Ефективність управління оцінюється показником P. S. Постає питання: як вибрати відчутні управління, щоб величина P. S звернулася до максимум ?

Завдання, поставлене є саме оптимального управління, а управління, у якому показник P. S сягає максимуму, називається оптимальним. Оптимальний управлениемногошаговым процесом складається з сукупності оптимальних шаговых управлений:

Отже, маємо поставлено завдання: визначити оптимальне управління кожному шаге (i=1,2,…N) і, отже, оптимальне управління всім процесом .

II. Ідеї методу динамічного программирования.

Ми зазначили, що плануючи многошаговый процес, необхідно вибирати УВ кожному кроці з урахуванням її майбутніх наслідків ще на майбутніх кроках. Проте, від цього правила є виняток. Серед усіх кроків існує один, котрі можуть плануватися без «заглядыва-ния у майбутнє «. Який це крок? Вочевидь, останній — після нього інших кроків немає. Цей крок пояснюють, єдиний із усіх, можна планувати те щоб як такою приніс найбільший зиск. Спланувавши оптимально цей останній крок, можна щодо нього пристроювати передостанній, до передостанньому — предпредпоследний і т.д.

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

N-й крок. Але як його спланувати, коли ми не знаємо, ніж скінчився передостанній? Вочевидь, потрібно докласти всіх зусиль можливі припущення, ніж скінчився передостанній, (N — 1)-й крок, й у кожного їх знайти таке управління, у якому виграш (дохід) на останньому кроці було б максимальний. Розв’язавши цю завдання, знайдемо умовно оптимальне управління (УОУ) на N-ою кроці, тобто. управління, які потрібно застосувати, якщо (N — 1)-й крок закінчився певним образом.

Припустимо, що цю процедуру виконано, тобто кожному за результату.

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

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

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

Справді, нехай ми знаємо початкова стан процесу. Тепер вже знаємо, що робити за перший крок: треба застосувати УОУ, знайдене на першому кроку та початкового сосюяния. Внаслідок цього управління після перший крок система піде на інше стан; але при цьому стану знаємо УОУ і 2002 р буд. Отже, знайдемо оптимальне управління процесом, що веде до максимально можливого выигрышу.

Отже, у процесі оптимізації управління методом динамічного програмування многошаговый процес «минається «дважды:

— вперше — від кінця до початку, у результаті перебувають УОУ| кожному кроці і оптимальний виграш (теж умовний) усім шагах, начиная з даного й під кінець процесса;

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

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

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

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

III.Пример завдання динамічного программирования.

Вибір складу устаткування технологічної линии.

Є технологічна лінія, тобто ланцюжок, послідовність операций.

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

Вихідні дані для примера.

i.

j.

Вартість сировини.

Витрати, пов’язані з допомогою одиниці устаткування j-го типу на i-ой операции.

Продуктивності, відповідно, щодо виходу й входуидляj-готипа устаткування, претендує на i-ую операцию.

Решение:

А, щоб вирішити це завдання методом динамічного програмування введемо такі обозначения:

N = 3 — число шагов.

— Технологічна лінія.

=(0,0,0).

= ().

— вибір устаткування i-ой операции.

Ui — область допустимих УВ на 1-му шаге.

т.е.

Wi — оцінка мінімальної собівартості, отримана у результаті i-го шага.

P.S — функція загального выигрышат. е. мінімальна собівартість .

— вектор — функція, яка описувала перехід системи зі стану в состояниепод дією УВ.

— вектор УВ на i кроці, який би перехід системи зі стану xi-1 до стану xi, тобто. оптимальний вибір устаткування за Nшагов.

Si+1() — максимальний виграш (у разі мінімальна собівартість), отримуваний під час переходу із будь-якої стану в кінцеве состояниепри оптимальної стратегії управління, починаючи з (k+1)-го шага.

S1() — максимальний виграш, отримуваний за N кроків під час переходу системи з початкового состоянияв конечноепри реалізації оптимальної стратегії управління. Вочевидь, що P. S = S1(), якщо = 0.

Запишемо вектора допустимих значений.

Запишемо вектора допустимих управляючих воздействий.

Запишемо вектор — функцію, описує перехід системи зі стану в состояниепод дією УВ.

Запишемо основне функціональне уравнение.

1) Зворотний проход.

Дляi=3.

Враховуючи те, що зазначений крок ми останній і такий операции.

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

візьмемо ціна на сировину.

при=.

при=.

т. е.

Для i=2.

при =.

при =.

при =.

при=.

т. е.

Дляi=1.

при =.

при =.

при =.

при ==.

при =.

при =.

при=.

при =.

т. е.

2) Прямий проход.

Враховуючи те, чтои = (0,0,0)имеем.

i=1.

i=2.

i=3.

Отже оптимальний вибір составаоборудования технологічної лінії передбачає следующее:

На1-ую операцію призначимо устаткування 2-го вида.

На2-ую операцію призначимо устаткування 1-го вида.

На3-ью операцію призначимо устаткування 2-го вида.

Оцінка мінімальної собівартості становитиме 105,5.