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

Версія за 20:30, 23 березня 2014

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

Неможливо розібрати вираз (невідома помилка): \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 }.