Відмінності між версіями «Умови розв’язуваності задачі другого етапу.»

Версія за 17:03, 30 травня 2021

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

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

Неможливо розібрати вираз (невідома помилка): \min_{\ x}M_{w}{(cx+P(x,A,b))}

 (1) 

Неможливо розібрати вираз (невідома помилка): \ {A^{(1)}{x}=b^{(1)}}

(2) 

Неможливо розібрати вираз (невідома помилка): x \geqslant 0

(3) 

де

Неможливо розібрати вираз (невідома помилка): P(x, A, b)=\min_{\ y}q(y)

(4) 

Неможливо розібрати вираз (невідома помилка): \ {By=b-Ax}

  (5) 

Неможливо розібрати вираз (невідома помилка): y \geqslant 0

  (6) 

Встановимо умови розв'язності задачі (4)-(6) другого етапу. Має місце наступна умова обмеженості знизу цільового функціоналу.

Теорема 1. Нехай множина Неможливо розібрати вираз (невідома помилка): K_2

непорожня. Для рішення задачі другого етапу при будь-яких реалізаціях А і b і будь-якому попередньому плані x необхідно і достатньо, щоб система нерівностей 

Неможливо розібрати вираз (невідома помилка): zB \leqslant q

                                    (7) 

була розв'язана, тобто щоб

Неможливо розібрати вираз (невідома помилка): \ {(z|zB \leqslant q) \ne \varnothing}.

(Передбачається, що B і q детерміновані).

Доведення: За умовою множина планів задачі (4)-(6) не порожня. Згідно з теоремою двоїстості лінійного програмування функція Неможливо розібрати вираз (невідома помилка): P(x,A,b)

обмежена знизу в тому і тільки в тому випадку, коли область визначення двоїстої задачі для кожного x, A, b 

Неможливо розібрати вираз (невідома помилка): Q(x, A, b)=\max_{\ z}z(b-Ax) (8)

Неможливо розібрати вираз (невідома помилка): zB \leqslant q (9)

непорожня. Оскільки область визначення задачі (8)-(9) не залежить від A, b, x, то при виконанні умови (7) задача другого етапу розв'язна при всіх A, b і x, а при порушенні цієї умови не має розв'язку ні при яких A, b і x. Функція Неможливо розібрати вираз (невідома помилка): P(x,A,b)

в цьому випадку не обмежена знизу для всіх x , і задача (1)-(3) і, отже, двохетапна задача втрачає сенс. 

Якщо накласти на матрицю компенсації B деякі обмеження,можна отримати прості умови, при яких множина планів задачі (8), (9) не порожня.

Теорема 2. Нехай матриця B має m+1 стовпець і задовольняє умовам:

a) має ранг m,

b) Неможливо розібрати вираз (невідома помилка): \ -B_{m+1}={\sum^{m}_{j=1}g_{j}B_{j}}, g_j>0, j=1,...,m

При цих умовах задача другого етапу має кінцеве рішення тоді і тільки тоді, коли

Неможливо розібрати вираз (невідома помилка): {\sum^{m}_{j=1}g_jq_j}+q_{m+1} \geqslant 0.

(10) 

Доведення: Необхідність. Нехай задачу (4)-(6) можна розв'язати. Тоді множина планів двоїстої до неї задачі непорожня. Нехай вектор Неможливо розібрати вираз (невідома помилка): z_0

задовольняє умовам (9) двоїстої задачі, тобто  

Неможливо розібрати вираз (невідома помилка): z_0B_j \leqslant q_j, j=1,...,m+1. (11)

Звідси при Неможливо розібрати вираз (невідома помилка): \ g_j>0

Неможливо розібрати вираз (невідома помилка): {\sum^{m}_{j=1}g_jz_0B_j} \leqslant {\sum^{m}_{j=1}g_jq_j} (12)

Із умови b) і (11) для j=m+1

Неможливо розібрати вираз (невідома помилка): z_0B_{m+1}=-{\sum^{m}_{j=1}z_0g_jB_j \leqslant q_{m+1}} (13)

Із (12) і (13) отримуємо (10).

Достатність. Нехай (10) має місце, а функція Неможливо розібрати вираз (невідома помилка): P(x,A,b)

не обмежена на множині планів задачі. Тоді множина планів задачі, двоїстої до задачі другого етапу, порожня 

Неможливо розібрати вираз (невідома помилка): \ {(z|zB \leqslant q) \ne \varnothing} (14)

З лінійної незалежності векторів Неможливо розібрати вираз (невідома помилка): B_1,...,B_m

слідує, що система 

Неможливо розібрати вираз (невідома помилка): \ zB_j=q_j, j=1,...,m (15)

маємо єдине рішення Неможливо розібрати вираз (невідома помилка): z_0 . В силу співвідношення (14)

Неможливо розібрати вираз (невідома помилка): \ z_0B_{m+1}>q_{m+1} (16)

Із (15), (16) і умови b) теореми отримуємо

Неможливо розібрати вираз (невідома помилка): \ z_0B_{m+1}=-{\sum^{m}_{j=1}z_0g_jB_j }=-{\sum^{m}_{j=1}g_jq_j }>q_m+1

що суперечить умові (10). Теорему доведено.

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

Можна показати [2], що аналогічну умову відсутність прибутку має місце і для випадків, коли Неможливо розібрати вираз (невідома помилка): \ n_1>m+1 . Але тоді ця умова буде тільки необхідною.

Має місце наступне твердження.

Теорема 3. Нехай матриця B має ранг m і існують числа Неможливо розібрати вираз (невідома помилка): g_j>0, j=1,..,m; g_j\geqslant0, j=m+1,..,n_1; (n_1-m>1) , такі що

Неможливо розібрати вираз (невідома помилка): \ {\sum^{n_1}_{j=m+1}g_jB_j }=-{\sum^{m}_{j=1}g_jB_j }.

Для того щоб задача другого етапу мала кінцевий розв'язок Неможливо розібрати вираз (невідома помилка): (K_2 \ne \varnothing)

необхідно щоб виконувалась наступна умова: 

Неможливо розібрати вираз (невідома помилка): \ {\sum^{m}_{j=1}g_jq_j } \leqslant {\sum^{n_1}_{j=m+1}g_jq_j }.

В [2] наводиться приклад, коли умови теореми не є достатніми.

Список використаних джерел

1. Юдин Д. Б. Математические методы управления в условиях неполной информации. / Юдин Д. Б. М: «Сов. радио», 1974. – 400 с.

2. Калль (Kall P.). Qualitative Aussagen zu einigen Problem der stochastischen Programierung. "Z. Wahrschein. und verw. Geb.", 1966, 6, №3, 246-272.

Виконала: Вернигора Анна Редагувала: Лисенко Наталія , Крячко Анастасія