Главная Прочие дисциплины Книги Математичне програмування - Наконечний С.І.

Математичне програмування - Наконечний С.І.

10.5. Двохетапні задачі стохастичного програмування

Недоліком розглянутих одноетапних задач стохастичного програмування є те, що в них лише фіксується факт можливих відхилень значень випадкових параметрів і усереднені розв’язки вибирають за умови, що відхилення значень від середнього рівня в будь-який бік небажане (зменшується величина дисперсії параметрів у обмеженнях або цільова функція — дисперсія мінімізується). У більшості реальних економічних задач має значення не лише величина відхилення, але також і його напрямок. Двохетапні задачі стохастичного програмування позбавлені зазначеного недоліку.

Розглянемо задачу стохастичного програмування в такій постановці:

, (10.10)

; (10.11)

. (10.12)

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

.

За виконання обмежень залежно від значень випадкових параметрів та вектора Х у вигляді виникає дефіцит. Позначимо його через :

.

Отже, якщо, то , а якщо , то .

Інакше кажучи,

,

.

Очевидно, що система обмежень (10.11) задачі може бути подана в еквівалентній формі:

Допустимо також, що відомі величини — питомі витрати на збереження надлишків та — питомі витрати, що пов’язані з дефіцитом . Отже, можна визначити штрафну функцію для і-го обмеження за результатом його виконання. Позначимо її через S, тоді:

Тоді доцільно розв’язувати задачу (10.10)—(10.12) у такій постановці:

, (10.13)

; (10.14)

. (10.15)

Змінні та можна розглядати як такі, що забезпечують виконання обмежень (10.11) як рівностей.

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

.

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

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

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

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

1. ймовірнісний характер початкової інформації,
2. вибір попереднього плану з урахуванням його майбутнього коректування,
3. коректування попередньо вибраного плану по мірі уточнення інформації.

Модель (10.13)—(10.15) — найпростіша двохетапна модель стохастичного програмування. У загальному випадку план-корекція вводиться в систему обмежень з допомогою матриці корекції загального вигляду, елементи якої можуть залежати від ω, тобто розглядається система нерівностей:

,

, ; ,

або у векторно-матричній формі:

; (10.16)

, . (10.17)

Попередній план Х вибирається до спостережень над ω. Коли ω стає відомим, то визначають план-корекцію Y у такий спосіб, щоб виконувались співвідношення (10.16), (10.17). При цьому ефект від плану-корекції дорівнює:

. (10.18)

Оскільки з кожним планом-корекцією Y пов’язаний певний ефект, то при певному Х і спостереженому ω його краще за все вибирати з умови максимізації (10.18) за обмежень (10.16), (10.17). Позначимо такий план через і назвемо його оптимальною корекцією плану Х за зовнішніх умов ω. Можна допустити, що існує при кожному Х і ω, у протилежному разі в (10.16) можна ввести штучні змінні Y– і одночасно — в (10.17) з досить великим штрафом (прийом введення штучних змінних детально описано в розділі 2).

Сподіваний ефект від плану-корекції дорівнює:

.

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

(10.19)

за умов:

; (10.20)

, . (10.21)

Іноді нелінійну задачу (10.19)—(10.21) зручно формулювати дещо в іншому вигляді, а саме: знайти такий детермінований вектор Х і такий Y(ω), щоб

(10.22)

за обмежень:

; (10.23)

, . (10.24)

У такій постановці двохетапна задача зводиться до одноетапної. Одночасно знаходиться оптимальний план Х і його оптимальна корекція . Задача (10.22)—(10.24) на відміну від (10.19)—(10.21) лінійна, однак, якщо в задачі (10.19)—(10.21) розв’язком є n-вимірний вектор Х, для пошуку якого можна застосувати чисельні методи, то в задачі (10.22)—(10.24) невідомими є і застосувати для розв’язування задачі чисельні методи можна лише за умови, якщо Ω — скінченна множина з невеликою кількістю елементів.

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

Необхідно спланувати виробництво однорідної продукції, попит на яку випадковий.

Розв’язання. Позначимо через Х обсяги виробництва продукції, через ω — попит на неї, а через С — витрати на виробництво одиниці продукції.

Оскільки попит на продукцію випадковий, то за будь-яких значень Х можливе або її перевиробництво, або дефіцит. Позначимо надлишок продукції через , дефіцит — через , а питомі витрати, що пов’язані зі зберіганням надлишку продукції та компенсацією дефіциту, — відповідно через та . Завдання полягає в знаходженні Х, що мінімізує математичне сподівання витрат, які пов’язані з виробництвом, надлишком та дефіцитом продукції.

Математична модель задачі матиме вигляд:

,

де

,

, .

Очевидно, що коли розв’язок вибрати за середнім значенням попиту , то при та (що, як правило, виконується) отримуємо тривіальну відповідь: .

Потрібно перевезти однорідну продукцію від двох постачальників трьом споживачам. Обсяг продукції першого постачальника a1 = 340 од., а другого — a2 = 560 од. Попит кожного споживача на продукцію є випадковим і відомий з відповідними ймовірностями, які наведені в табл. 10.6—10.8.

Таблиця 10.6

Попит першого споживача на продукцію, од. (b1)	Ймовірність
100	0,05
175	0,2
200	0,6
300	0,1
340	0,05

Таблиця 10.7

Попит другого споживача на продукцію, од. (b2)	Ймовірність
250	0,05
290	0,25
300	0,4
320	0,2
360	0,1

Таблиця 10.8

Попит третього споживача на продукцію, од. (b3)	Ймовірність
290	0,1
300	0,3
400	0,3
590	0,2
600	0,1

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

Таблиця 10.9

Постачальник	Споживач
	перший	другий	третій
Перший	30	37	28
Другий	32	26	30

Якщо попит на продукцію буде більшим, ніж її наявність, то необхідно буде сплатити штраф за недопостачання кожної одиниці продукції першому, другому та третьому споживачам обсягом відповідно 105, 169 і 86 ум. од., а якщо попит буде меншим, то необхідно буде зберігати надлишки, що потребуватиме додаткових витрат на одиницю продукції обсягом відповідно 40, 45 та 30 ум. од.

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

Розв’язання.

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

;

;

.

Загальний обсяг попиту на продукцію становитиме:

,

а пропозиція дорівнює:

Зіставимо обсяг продукції у постачальників і сподіваний загальний попит:

.

Отже, виникає незадоволений попит:

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

,

.

Тоді математична модель двохетапної задачі стохастичного програмування, зведена до задачі лінійного програмування, відповідно до моделі (10.22)—(10.24) має вигляд:

, , , .

Розв’язуючи цю задачу, отримаємо оптимальний план:

,

причому план-корекція , . Мінімальні витрати дорівнюють: F = 35 744 ум. од.