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

У розглянутих раніше задачах нелінійного програмування ми знаходили їхній розв'язок, так би мовити в один етап або за один крок. Такі задачі мають назву одноетапних або однокрокових.

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

Припустимо, що деяка фізична система 5 перебуває в деякому

початковому стані З1,, е     і є керованою. Таким чином, завдяки

здійсненню деякого керування Е/ зазначена система переходить із

початкового стану 50 у кінцевий стан 5И(1 е 5Д. При цьому якість

кожного з реалізованих керувань І/ характеризується відповідним значенням функції IV (V). Задача полягає в тому, щоб з безлічі можливих керувань V знайти таке V; при якому функція №(Ц) приймає екстремальне (максимальне або мінімальне) значення IV (£/•). Сформульована задача і є загальною задачею динамічного програмування.

Дамо геометричну інтерпретацію цієї задачі. Припустимо, що стан системи характеризується деякою крапкою 5 на площині ХіОх2

 (рис. 6.1) і ця крапка завдяки здійснюваному керуванню її рухом переміщається уздовж лінії, зображеної на рис. 6.1, з області

можливих початкових станів 5^ в область припустимих кінцевих

станів 5Й. Кожному керуванню І/ рухом крапки, тобто кожної траєкторії руху крапки, поставимо у відповідність значення деякої функції і¥(1/) (наприклад, довжину шляху, пройденого крапкою під впливом даного керування). Тоді задача полягає в тому, щоб з усіх припустимих траєкторій руху крапки 5 знайти таку, яка одержується в результаті реалізації керування ЕЛ, яке забезпечує екстремальне значення функції Щи*). До визначення такої «траєкторії» зводиться й завдання динамічного програмування у випадку, коли припустимі стани системи Б визначаються крапками п-мірного простору.

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

Приклад 1. У розпорядження міністерства, у підпорядкуванні якого перебувають к підприємств, виділені кошти в розмірі К млн. грн. для використання їх на розвиток підприємств протягом т років. Ці кошти на початку кожного господарського року ( тобто в моменти іі, І2, ї») розподіляються між підприємствами. Одночасно із цим між підприємствами розподіляється отриманий ними за минулий рік прибуток. Таким чином, на початку кожного і'-го року розглянутого періоду у'-е підприємство одержує у своє розпорядження хР млн. грн. Задача полягає у визначенні таких значень хР, тобто в знаходженні таких розподілів виділених коштів між підприємствами та прибутків, що одержуються ними, при яких за т років забезпечується одержання максимального прибутку всіма підприємствами.

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

Розв 'язання. Припускаючи, що _/-му підприємству на і'-й рік виділяється хР млн. грн., будемо розглядати даний розподіл коштів як реалізацію деякого керування «,. Таким чином, керування іі| полягає в тому, що на і-м кроці першому підприємству виділяється Хі11) млн. грн., другому х/2> млн. грн. і т.д. Сукупність чисел х/!>, хРК .... Хр1 визначає всю сукупність керувань и3, и2, .... ит на т кроках розподілу коштів як т крапок в А-мірному просторі.

В якості критерію оцінки якості обраного розподілу коштів, тобто реалізованих керувань, сумарний прибуток за т років, що залежить від всієї сукупності керувань: ТР=1У(иі,и2, ...,ит).

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

Як видно, сформульована задача є багатоетапною. Ця багатоетапність визначається її умовами, якими передбачене прийняття певних рішень на початку кожного року розглянутого періоду часу. Разом з тим у цілому ряді інших задач динамічного програмування така багатоетапність безпосередньо не випливає з їхніх умов. Однак з метою знаходження розв'язку таких задач доцільно розглядати їх як багатоетапні. Наведемо приклад подібної задачі та дамо її формулювання в термінах загальної задачі динамічного програмування.

Приклад 2. Для збільшення обсягів випуску продукції, що користується підвищеним попитом, виготовленої підприємствами, виділені капіталовкладення в обсязі 8 млн. грн. Використання і-м підприємством Хі млн. грн. із зазначених засобів забезпечує приріст

ВИПуСКу ПрОДуКЦІЇ, ОбуМОВЛеНИЙ ЗНачеННЯМ НелІНІЙНОЇ фуНКЦІЇ Іі(Хі).

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

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

 (6.1)

за умов

 

(6.2)

х,. >0,   (і = 1, я).

(6.3)

Сформульована задача є задачею нелінійного програмування. У тому випадку, коли Я(х$) - опуклі (або ввігнуті) функції, її розв'язок можна знайти, наприклад, методом множників Лагранжа. Якщо жфункції і"[(Х[) не є такими, то відомі методи знаходження рішення завдань нелінійного програмування не дозволяють визначити глобальний максимум функції (6.1). Тоді розв'язання задачі (6.1) -(6.3) можна знайти за допомогою динамічного програмування. Для цього вихідну задачу потрібно розглянути як багатоетапну або багатокрокову. Замість того щоб розглядати припустимі варіанти розподілу капіталовкладень між п підприємствами й оцінювати їх ефективність, будемо досліджувати ефективність вкладення засобів на одному підприємстві, на двох підприємствах і т.д., нарешті, на п підприємствах. Таким чином, одержимо п етапів, на кожному з яких стан системи (у якості якої виступають підприємства) описується

обсягом засобів, що підлягають освоєнню £ підприємствами (к = 1,п). Рішення про обсяги капіталовкладень, що виділяються 4-му підприємству (£ = 1,п), і є керуваннями. Задача полягає у виборі таких керувань, при яких функція (6.1) приймає найбільше значення.