Реферат Динамічний програмування

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

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


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


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

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

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

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

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

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

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

N – число кроків.

– вектор,описывающий стан системи на k-м кроці.

– початкова стан, т. е. cостояние на 1-му кроці.

– кінцеве стан, т. е. cостояние на останньому кроці.

Xk – область допустимих станів на k-ом кроці.

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

Uk – область допустимих УВ на k-ом кроці.

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

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

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

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

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

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

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


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


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


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

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

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

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

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

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


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


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

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

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

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

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

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

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

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

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

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

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

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

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

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

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


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

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

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

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

Вихідні дані приміром

і 1 2 3
j 1 2 1 2 1 2


10 8 4 5 8 9

12 8 4 6 9 9


20 18 6 8 10 12


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

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

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


Рішення:

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

N = 3 – число кроків.

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

= (0,0,0)

= ( )

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

Uіобласть допустимих УВ на і-м кроці.

тобто.

Wі – оцінка мінімальної собівартості, отримана у результаті і-го кроку.

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




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


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

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

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


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



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



З

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






З

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




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

Д

ля i=3


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

у

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

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


при =



при =


т. е.


Для i=2



115,2


при =


138,04


при =


102,8


при =


123,1


при =


т. е.


Д

ля i=1



140,2


при =


125,3


при =


п

125,3

ри =


125,3


при ==


125,3


при =


125,3


при =


125,3


при =


125,3


при =


т. е.


  1. П

    рямой прохід

Враховуючи те, як і = (0,0,0) маємо

i=1




i=2




і

=3




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

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

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

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

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


13



Розділ колекції : Экономико-математическое моделювання

Автор : Родіонов Д.А.

Контактні відомості : [email protected]

Найменування роботи : Динамічний програмування

Вигляд роботи : курсова робота

Побажання : -

Схожі реферати:

Навігація