Реферати

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

Життя Р.-Л. Стивенсона. Капітан "Испаньоли".. Біографічний нарис.

Вимирання українського села - національна небезпека. Характеристика реформування національної економіки і соціально-економічних відносин українського суспільства. Визначення життєвого потенціалу сільського населення України за 1979-2008 роки. Опису економічної трансформації в аграрному виробництві.

Технологія організації укладання трубопроводу. Прокладка напірного поліетиленового водопровідного трубопроводу. Складність виготовлення і монтажу технологічних трубопроводів. Методи виробництва грабарств. Ущільнення ґрунту при обсипанні труби. Калькуляція витрат праці і машинного часу.

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

Концепція тритомного видання до 55-річчю З РАНЕЙ. Підготовка матеріалу для видання книги до 55-річчю З РАНЕЙ, її редагування й оформлення. Вивчення діяльності Академії наук, її внесок у розвиток науково-освітніх і соціально-економічних процесів, упровадження новітніх інноваційних технологій.

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

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

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

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

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

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

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

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

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

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

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

- вектор, що описує стан системи наk-м кроці.

- початковий стан, т. е. стан на 1-м кроці.

- кінцевий стан, т. е. стан на останньому кроці.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Принцип оптимальності. По-якому б не було допустимий стан системи

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

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

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

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

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

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

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

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

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

Передбачимо, що ця процедура виконана, тобто для кожного виходу

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Початкові дані для прикладу

i

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-ой операції.

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

т. е.

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

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

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

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

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

S1() - максимальний виграш, що отримується заNшагов при переході системи з початкового стану в кінцеве при реалізації оптимальної стратегії управління. Очевидно, що S = 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

при =

т. е.

П

рямой прохід

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

i=1

i=2

i

=3

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

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

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

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

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

13

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

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

Контактні відомості: dimarik@chel.ru

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

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

Побажання: -