Реферат на тему:

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

План.

1. Загальна характеристика задач динамічного програмування.

2. Геометрична та економічна сутність.

3. Деякі основні типи задач та моделі динамічного програмування (ДП).

4. Принципи оптимальності Белламана.

5. Література

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

В розглянутих вище задачах лінійного та нелінійного програмування ми
знаходили їх розв(язок ніби в один етап чи в один крок. Такі задачі
отримали назву одноетапних чи однокрокових.

На відміну від цих задач задачі ДП є багатоетапними чи
багатокроковими. Іншими словами, знаходження розв(язку конкретних задач
методами ДП включають декілька етапів чи кроків, на кожному з яких
визначається розв(язок деякої окремої задачі, обумовленою початковою.
Тому термін “динамічне програмування” не стільки визначає собою тип
задач, скільки характеризує методи знаходження розв(язку окремих класів
задач математичного програмування, які можуть відноситися до задач як
лінійного, так і нелінійного програмування. Не дивлячись на це, доцільно
дати загальну постановку задачі ДП і визначити єдиний підхід до її
розв(язку.

Припустимо, що дана фізична система S знаходиться в деякому
початковому стані S0 (( S0 та є направляючою. Таким чином, завдяки
здійсненню деякого управління U вказана система переходить з початкового
стану S0 в кінцевий стан Sкін ( SR. При цьому якість кожного з
реалізуючих управлінь U характеризується відповідним значенням функції
W(U). Задача полягає в тому, щоб з більшості можливих управлінь U знайти
таке U* , при якому функція W(U) приймає екстремальне значення W(U*).
Сформульована задача і є загальною задачею ДП.

Дамо геометричну інтерпретацію цієї задачі. Припустимо, що стан
системи характеризується деякою точкою S на площині x1Ox2 (мал.1) і ця
точка завдяки здійснюваному управлінню її рухом переміщується удовж
лінії, яка зображена на мал.1, з області можливих початкових станів S0 в
область допустимих кінцевих станів SR . Кожному управлінню U рухом
точки, а саме кожній траєкторії руху точки, поставимо у відповідність
значення деякої функції W(U) (наприклад, довжину відстані, пройденої
точкою під впливом даного управління). Тоді задача полягає в тому, щоб з
усіх допустимих траекторій руху точки S знайти таку, яка виходить в
результаті реалізації управління U*, що забезпечує екстремальне значення
функції W(U*). До означення такої “траекторії” зводиться і задача ДП у
випадку, коли допустимі стани системи S визначаються точками
n-вимірного простору.

мал.1

Економічну інтерпретацію загальної задачі ДП розглянемо на конкретних
прикладах.

У розпорядження міністерства, у підпорядкуванні якого знаходиться k
підприємств, виділено кошти в розмірі К тис. грн. для використання їх на
розвиток підприємств протягом m років. Ці кошти на початку кожного
господарського року, тобто в моменти t1, t2, …, tm , розприділяються між
підприємствами. Одночасно з цим між підприємствами розподіляється
отриманий ними за минулий рік прибуток. Таким чином, на початок кожного
і-го року періоду, який нас цікавить j-те підприємство отримує в своє
розпорядження хi( j ) тис.грн. Задача полягає у визначенні таких значень
xi( j ) , тобто в знаходженні таких розподілів виділених коштів між
підприємствами і прибутку що ними отримується, при яких за m років
забезпечується отримання максимального прибутку всіма підприємствами.

Сформулювати поставлену задачу в термінах загальної задачі ДП.

Розв(язок. Припускаючи, що j-му підприємству на і-ий рік виділяється
xi(j) тис. грн., будемо розглядати даний розподіл коштів як реалізацію
деякого управління ui . Таким чином, управління ui полягає в тому, що на
і-му кроці першому підприємству виділяється xi(1) тис. грн., другому —
xi(2) тощо. Сукупність чисел xi(1), xi(2), …, xi(k) визначає всю
сукупність управлінь u1, u2, …, um на m кроках розподілу коштів як m
точок в k-вимірному просторі.

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

W= W (u1, u2, …, um).

Отже, задача полягає у виборі таких управлінь ui*, тобто в такому
розподілі коштів, при якому функція W приймає максимальне значення.

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

2. Для збільшення об(ємів випуску продукції, яка користується більшим
попитом, що її випускають підприємства, виділені капіталовкладення в
розмірі S тис. грн. Використання і-тим підприємством xi тис. грн. з
вказаних коштів забезпечує приріст випуску продукції, що визначається
значенням нелінійної функції fi (xi).

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

Розв(язок. Математична постановка задачі полягає в визначені
найбільшого значення функції

n

F = ( fi (xi) (1)

i=1

при умовах

n

( xi = S (2)

i=1

хі ( (і = 1, n) (3)

Сформульована задача є задачею нелінійного програмування. В тому
випадку, коли fi (xi) – опуклі функції, її розв(язок можна знайти,
наприклад, методом множників Лагранжа. Якщо ж функції fi (xi) не є
такими, то відомі методи знаходження розв(язку задач нелінійного
програмування дозволяють визначити глобальний максимум функції (1). Тоді
розв(язок задачі (1) –(3) можна знайти за допомогою ДП. Для цього
початкову задачу потрібно розглянути як багатоетапну. Замість того щоб
розглядати допустимі варіанти розподілу капіталовкладень між n
підприємствами та оцінювати їх ефективність, будемо розглядати
ефективність вкладення коштів на одному підприємстві, на двох
підприємствах, на n підприємствах. Таким чином, отримаємо n етапів, на
кожному з яких стан системи, в якості якої виступають підприємства,
описується об(ємом коштів, які належать освоєнню k підприємствами
(k=1,n). Розв(язки про об(єми капіталовкладень, що виділяються k-му
підприємству (k = 1, n) і є управліннями. Задача полягає у виборі таких
управлінь, при яких функція (1) приймає найбільше значення.

Сформулюйте задачі 3 – 8 в термінах загальної задачі ДП.

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

Рахуючи, що на розвиток і-го підприємства на початок k-го року
виділяється ai(k) тис. грн., знайти такий варіант розподілу коштів між
підприємствами протягом N років, при якому забезпечується отримання за
даний період часу максимального прибутку.

4. У виробничому об(єднанні на початку кожного року повністю
розподіляється між m підприємствами, що входять до його складу,
створений в об(єднанні централізований фонд розвитку виробництва. При
цьому завдяки виділенню з цього фонду і-му підприємству xi тис. грн.
забезпечується отримання додаткового прибутку, що дорівнює fi (xi) тис.
грн. До початку планового періоду, який складається з N років,
централізованому фонду розвитку виробництва виділено A тис. грн. В
кожний наступний рік цей фонд формується за рахунок відрахування в нього
від отриманого прибутку. Ці відрахування для і-го підприємства складають
(I (xi) тис. грн.

Знайти такий варіант розподілу централізованого фонду розвитку
виробництва між підприємствами об(єднання, при якому загальний прибуток,
отриманий за N років, є максимальним.

5. Для здійснення своєї ефективної діяльності виробничі об(єднання і
підприємства мають періодично проводити заміну обладнання, що
використовується. При цій заміні враховуються продуктивність цього
обладнання, затрати, пов(язані з утриманням і ремонтом обладнання, ціна
замінного обладнання і обладнання, що купується. Припустимо, що на
початок запланованого періоду на підприємстві встановлено нове
обладнання, яке дозволяє за r-ий рік випустити готової продукції на суму
R (r) грн., а щорічні витрати, пов(язані з утриманням та ремонтом
обладнання дорівнюють Z (r) грн. В r-ий рік обладнання може бути
продано за S (r) грн. та закуплено нове за Pr грн. З урахуванням всіх
цих факторів знайти оптимальний план заміни обладнання, тобто план, який
забезпечує максимальний прибуток від заміни обладнання протягом N років.

6. Деталі n вигляду можуть оброблятись на двох станках. Час обробки і-ої
деталі (i = 1, n) на першому станку дорівнює ai хвилин, а час обробки
тої ж самої деталі на другому станку дорівнює bi хвилин. Черговість
обробки деталей однакова: спочатку деталь обробляється на першому
станку, а потім на другому. Потрібно вибрати таку послідовність обробки
деталей, при якій час виготовлення всіх деталей буде мінімальним.

7. На склад ємністю W м3 потрібно вмістити n різноманітних типів
обладнання. Об(єм однієї одиниці і-го типу обладнання (і = 1, n)
дорівнює Vi м3 , ціна одиниці даного типу обладнання дорівнює Сі грн.
Визначити, скільки обладнання кожного типу слід помістити на склад так,
щоб загальна ціна обладнання на складі була максимальною.

8. Виробничі об’єднання, які випускають товари народного призначення,
виготовляють їх окремими партіями. Чим більший розмір цих партій, тим це
більше вигідно для виробничих об(єднань. Тому кожне об’єднання
зацікавлене в окремі місяці випускати більше виробів, чим це потрібно
для задоволення попиту, а залишок зберігати на складі для їх реалізації
в наступні місяці. Однак зберігання виробів на складі супроводжується
відповідними затратами.

Будемо рахувати, що підприємство намагається знайти оптимальний план
виробництва продукції протягом N місяців, в кожному з яких необхідно ai
(i = 1, N) одиниць продукції. Запаси на початок запланованого періоду
дорівнюють b виробам, а в кожному з запланованих місяців підприємство
може виготовити не більше di одиниць продукції. Одночасно на складі
може зберігатись не більше ніж A виробів. Витрати, пов(язані з
виробництвом ai (j = 1, k) виробів, складають cj грн., а витрати,
пов(язані зі зберіганням протягом місяця одного виробу, складають ( грн.
Визначити такий план випуску продукції, при якому загальна сума витрат
на виробництво і зберігання її була б мінімальна, а попит на необхідні
вироби був би задоволений повністю і своєчасно.

Розв’язування задач динамічного програмування.

наведені в таблиці 1.

Таблиця 1.

в залежності від об’єму капіталовкладень (тис. грн.)

Підприємство1 Підприємство2 Підприємство3

0 0 0 0

100 30 50 40

200 50 80 50

300 90 90 110

400 110 150 120

500 170 190 180

600 180 210 220

700 210 220 240

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

………………………………….

, так як об’єм капіталовкладень, виділяючих для всіх n підприємств,
дорівнює S тис. грн.

Використовуючи тепер рекурентне співвідношення і вихідні дані
табл.1, приступаємо до знаходження розв’язку задачі, тобто до визначення
спочатку умовно оптимальних, а потім і оптимальних розподілів
капіталовкладень між підприємствами.

для кожного Х, приймаючого значення 0, 100, 200, 300, 400, 500, 600 і
700.

. Тоді, використовуючи табл.1, дістанемо

.

.

:

;

;

;

;

;

Результати обчислень і одержані відповідні умовно оптимальні
розв’язки записуємо в табл.2.

Таблиця 2.

, виділених першому підприємству (тис. грн.)

0 0 0

100 30 100

200 50 200

300 90 300

400 110 400

500 170 500

600 180 600

700 210 700

Використовуючи тепер дані табл.2 і 1, визначимо умовно оптимальні
об’єми капіталовкладень, виділених другому підприємству. Знайдемо

для кожного із допустимих значень Х, рівних 0, 100, 200, 300, 400, 500,
600 і 700:

;

;

;

;

;

;

;

.

Одержані результати і найдені умовно оптимальні об’єми
капіталовкладень, виділених другому підприємству, записуємо в табл.3.

Таблиця 3.

,виділених другому підприємству (тис.грн.)

0 0 0

100 50 100

200 80 100

300 110 200

400 150 400

500 190 500

600 220 100

700 250 200

Переходимо до знаходження значень

,

використовуючи для цього відповідні дані табл.3 і 1.

:

.

Відповідно, максимальний приріст випуску продукції складає 270
тис.грн. Це має місце тоді, коли третьому підприємству виділяється 600
тис.грн., а першому і другому підприємствам – 100 тис.грн. Тоді, як
бачимо з табл.3, другому підприємству необхідно виділити 100 тис. грн.

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

Література.

Наконечний С.І., Савіна С.С. Математичне програмування: Навч. посіб. –
К.:КНЕУ, 2003.- 452 с.

Барвінський А.Ф та ін. Математичне програмування: Навчальний посібник
А.Ф. Барвінський, І.Я. Олексів, З.І. Крупка, І.О. Бобик, І.І. Демків,
Р.І. Квіт, В.В. Кісілевич – Львів: Національний університет “Львівська
політехніка” (Інформаційно-видавничий центр “Інтелект+” Інститут
післядипломної освіти) “Інтелект — Захід”, 2004. – 448 с.

Акулич М.Л. Математичиское програмирование в примерах и задачах: Учебное
пособие для студентов экономических специальних вузов. – Вища школа,
1985-319с.,ст.292-296-300.

Вітлінський В.В., Наконечний С.І., Терещенко Т.О. Математичне
програмування: Навч. – метод. посібник для самост. вивч. дисц. – К.:
КНЕУ, 2001. – 248 с.

Математичне програмування (методичний посібник для студентів економічних
спеціальностей)/Укладачі: Лавренчук В.П., Веренич І.І., Готинчан Т.І.,
Дронь В.С., Кондур О.С., — Чернівці: „Рута”, 1998.-168 с.

PAGE

PAGE 13

Похожие записи