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

Версія за 05:56, 2 червня 2017

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

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

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

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

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

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

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

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

де

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

a) має ранг m,

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

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

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

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

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

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

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

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

Із (1.12) і (1.13) отримуємо (1.10).

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

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

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

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

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

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

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

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

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

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

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

Теорема 1.3. Теорема 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 }.

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