трусики женские украина

На головну

 Динамічне програмування - Економіко-математичне моделювання

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

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

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

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

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

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

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

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

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

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

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

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

- Початковий стан, т. Е. Cостояние на 1-му кроці.

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

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 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

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

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

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

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

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

13

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

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

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

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

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

Побажання

Авіація і космонавтика
Автоматизація та управління
Архітектура
Астрологія
Астрономія
Банківська справа
Безпека життєдіяльності
Біографії
Біологія
Біологія і хімія
Біржова справа
Ботаніка та сільське господарство
Валютні відносини
Ветеринарія
Військова кафедра
Географія
Геодезія
Геологія
Діловодство
Гроші та кредит
Природознавство
Журналістика
Зарубіжна література
Зоологія
Видавнича справа та поліграфія
Інвестиції
Інформатика
Історія
Історія техніки
Комунікації і зв'язок
Косметологія
Короткий зміст творів
Криміналістика
Кримінологія
Криптологія
Кулінарія
Культура і мистецтво
Культурологія
Логіка
Логістика
Маркетинг
Математика
Медицина, здоров'я
Медичні науки
Менеджмент
Металургія
Музика
Наука і техніка
Нарисна геометрія
Фільми онлайн
Педагогіка
Підприємництво
Промисловість, виробництво
Психологія
Психологія, педагогіка
Радіоелектроніка
Реклама
Релігія і міфологія
Риторика
Різне
Сексологія
Соціологія
Статистика
Страхування
Будівельні науки
Будівництво
Схемотехніка
Теорія організації
Теплотехніка
Технологія
Товарознавство
Транспорт
Туризм
Управління
Керуючі науки
Фізика
Фізкультура і спорт
Філософія
Фінансові науки
Фінанси
Фотографія
Хімія
Цифрові пристрої
Екологія
Економіка
Економіко-математичне моделювання
Економічна географія
Економічна теорія
Етика

8ref.com

© 8ref.com - українські реферати


енциклопедія  бефстроганов  рагу  оселедець  солянка