Оптимальний план випуску продукції

Табл. 2.12

Кількість гарнітурів першого виду , шт.	Кількість гарнітурів другого виду , шт.	Максимальний сумарний прибуток $
8	6	6200

2.5. Прийняття рішення методом динамічного програмування.

Задача розподілення ресурсів

1. Постановка проблеми

У розпорядженні виробничої фірми є запас ресурсів (припустимо =3 умовним одиницям ресурсу), який треба розподілити між (=3) підприємствамиП₁,П₂ ,П_3(m).

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

Функції прибутку підприємств

Таблиця 2.13

х	φ1(х)	φ2(х)	φ3(х)
1	0,5	0,1	0,6
2	1,1	0,5	1,1
3	1,4	1,3	1,2

Вирішити проблему оптимального розподілу ресурсів між підприємствами.

2. Формулювання мети прийняття рішень.

Вибрати такий варіант розподілу ресурсів між підприємствами, щоб сумарний прибуток отриманий фірмою був би максимальним.

3. Визначення множини допустимих альтернатив

Множина альтернатив задачі розподілення ресурсів є не зовсім очевидною. Під альтернативою ОПР в даній задачі розуміється вектор - який подає обсяги ресурсів, що виділяються кожному підприємству.

Допустимість альтернативи визначається ресурсними та логічними обмеженнями.

Ресурсні обмеження

Логічні обмеження

4. Ідентифікація типу задачі прийняття рішення.

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

Задача розподілу ресурсів є однокритеріальною, повністю визначеною задачею прийняття рішень.

5. Порівняння альтернатив та вибір рішення

1. Виключення з розгляду альтернатив, що домінуються.

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

(2.28)

2. Знаходження значення критерію для кожної з альтернатив

В загальному випадку множина допустимих альтернатив є нескінченною, оскільки існує безліч варіантів розподілу ресурсів. Але, у задачі, яка розглядається, кількість альтернатив може бути скінченою, якщо розглядати варіанти розподілу запасу ресурсів S₀=3од, з дискретним кроком ∆=1 од., що принципово дозволяє здійснити повний перебір варіантів.

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

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

Необхідні теоретичні відомості. Метод динамічного програмування

Метод динамічного програмування (ДП) є потужним методом оптимізації управлінських рішень.

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

Критерій W називають адитивним якщо його можна подати як суму значень на окремих кроках

(2.29),

де w_i-значення критерію і-тому кроці.

Мультиплікативність критерію відповідає умові:

(2.30)

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

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

(2.31)

Потрібно знайти таке управління при якому виграш W обертається до максимуму.

(2.32)

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

“багатоетапних” задач.

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

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

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

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

Пересуваючись таким чином до першого кроку знаходяться всі умовно оптимальні управління. Якщо відомо в якому стані була система на початку першого кроку, можна вибрати оптимальне управління на першому кроці та всіх кроках до кінця процесу,,…,.

Саме ці управління забезпечують максимальний виграш

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

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

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

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

Практичні рекомендації