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

План.
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 грн., а витрати, повязані зі зберіганням протягом місяця одного виробу, складають грн. Визначити такий план випуску продукції, при якому загальна сума витрат на виробництво і зберігання її була б мінімальна, а попит на необхідні вироби був би задоволений повністю і своєчасно.
Розв’язування задач динамічного програмування.
Задача. Знайти розв’язок задачі,якщо S=700 тис.грн. n=3, а значення і наведені в таблиці 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, дістанемо
.
Тут перший рядок відповідає розв’язку , а другий рядок – розв’язку . Так як першому розв’язку приріст випуску продукції не забезпечується, а при другому дорівнює 30 тис. грн., то умовно оптимальним розв’язком являється .
Аналогічно знаходимо умовно оптимальний розв’язок для інших значень :
;
;
;
;

;


Результати обчислень і одержані відповідні умовно оптимальні розв’язки записуємо в табл.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.
Так як в даному випадку число підприємств дорівнює 3 то проводимо обчислення лише для одного значення :

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


Література.
Наконечний С.І., Савіна С.С. Математичне програмування: Навч. посіб. – К.:КНЕУ, 2003.- 452 с.
Барвінський А.Ф та ін. Математичне програмування: Навчальний посібник А.Ф. Барвінський, І.Я. Олексів, З.І. Крупка, І.О. Бобик, І.І. Демків, Р.І. Квіт, В.В. Кісілевич – Львів: Національний університет “Львівська політехніка” (Інформаційно-видавничий центр “Інтелект+” Інститут післядипломної освіти) “Інтелект - Захід”, 2004. – 448 с.
Акулич М.Л. Математичиское програмирование в примерах и задачах: Учебное пособие для студентов экономических специальних вузов. – Вища школа, 1985-319с.,ст.292-296-300.
Вітлінський В.В., Наконечний С.І., Терещенко Т.О. Математичне програмування: Навч. – метод. посібник для самост. вивч. дисц. – К.: КНЕУ, 2001. – 248 с.
Математичне програмування (методичний посібник для студентів економічних спеціальностей)/Укладачі: Лавренчук В.П., Веренич І.І., Готинчан Т.І., Дронь В.С., Кондур О.С., - Чернівці: „Рута”, 1998.-168 с.

Внимание, отключите Adblock

Вы посетили наш сайт со включенным блокировщиком рекламы!
Ссылка для скачивания станет доступной сразу после отключения Adblock!

Скачать