Область визначення двохетапної задачі з випадковим вектором обмежень.

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

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

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

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

Нехай випадковими є тільки складові вектора обмежень b. Всі інші параметри умов задачі – детерміновані.

Єдине припущення, з яким ми пов’язуємо вибір випадкового вектора Неможливо розібрати вираз (невідома помилка): b(\omega) , заключається в тому, що його розподіл не повинен залежати від вибору попереднього плану x.

Згідно раніше розглянутої теореми, для загальної двоетапної задачі множина K попередніх планів – опукла. Для розглянутого часткового випадку можна довести більш сильне твердження. Виявляється, що в цьому випадку множина K не тільки опукла, але й багатогранна. Більше того, можна явно записати систему лінійних нерівностей, що визначають множину К.

Нагадаємо деякі поняття, що необхідні для наступних побудов.

Як відомо, опуклий багатогранний Конус С може бути представлений або як невід’ємна комбінація скінченного числа векторів, або як перетин скінченного числа півпросторів.

Еквівалентність двох визначень опуклого багатогранного конуса С використовується для приведення у відповідність кожній матриці В так звану полярну матрицю Неможливо розібрати вираз (невідома помилка): B^* .

Матриця Неможливо розібрати вираз (невідома помилка): B^*

(розмірності Неможливо розібрати вираз (невідома помилка): l x m

) називається полярною до матриці В (розмірності Неможливо розібрати вираз (невідома помилка): m x n_1 ), якщо Неможливо розібрати вираз (невідома помилка): B^*

— матриця з мінімальним числом рядків, що задовольняють умові:

Неможливо розібрати вираз (невідома помилка): C=\{t|\exist y\geqslant 0, t=By\}=\{t|B^* t\geqslant 0\}

Введемо множини:

Неможливо розібрати вираз (невідома помилка): N=\{\chi|\forall (\omega \in \Omega) \exist y \geqslant 0, By=b(\omega)-\chi\}

Неможливо розібрати вираз (невідома помилка): N(\omega)=\{\chi| \exist y \geqslant 0, By=b(\omega)-\chi\}

Зрозуміло, що Неможливо розібрати вираз (невідома помилка): N=\cap_{\omega \in \Omega}N(\omega)

Раніше були введені множини:

Неможливо розібрати вираз (невідома помилка): K_2 =\{x|\forall (\omega \in \Omega) \exist y \geqslant 0, By=b(\omega)-A(\omega)x\}

Неможливо розібрати вираз (невідома помилка): K_2(\omega) =\{x| \exist y \geqslant 0, By=b(\omega)-A(\omega)x\}

Ці множини пов'язані з множинами Неможливо розібрати вираз (невідома помилка): N

і Неможливо розібрати вираз (невідома помилка):  N(\omega) 
співвідношеннями:

Неможливо розібрати вираз (невідома помилка): K_2=\{x|A(\omega)=\chi , \chi \in N\}

Неможливо розібрати вираз (невідома помилка): K_2(\omega)=\{x|A(\omega)=\chi , \chi \in N(\omega)\}

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

Лема 1. Якщо Неможливо розібрати вираз (невідома помилка): N(\omega)

– опукла, багатогранна множина, то Неможливо розібрати вираз (невідома помилка): K_2 (\omega) 

– теж опукла багатогранна множина. Якщо Неможливо розібрати вираз (невідома помилка): N

– опукла, багатогранна множина, то Неможливо розібрати вираз (невідома помилка): K_2
– теж опукла багатогранна множина.

Лема 2. Множина Неможливо розібрати вираз (невідома помилка): N(\omega) може бути представлена у вигляді:

Неможливо розібрати вираз (невідома помилка): N(\omega)=\{\chi|B^* \chi \leqslant B^* b(\omega)\}

Лема 3. Множина N є опуклою багатогранною множиною, що визначається системою лінійних нерівностей:

Неможливо розібрати вираз (невідома помилка): B^* b(\omega) \leqslant\alpha_i^*,i=1,...,l

якщо для деякого Неможливо розібрати вираз (невідома помилка): i,\alpha_i^*=-\infty , множина N – порожня.

Теорема 1. Множина K планів детермінованої задачі, що еквівалентна двоетапній задачі стохастичного програмування, в якій випадковим є тільки вектор обмежень b, є опуклою багатогранною множиною.

Доведення: Множина Неможливо розібрати вираз (невідома помилка): K=K_1\cap K_2

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

– випукла многогранна множина. Відповідно до лем 1 і 3 Неможливо розібрати вираз (невідома помилка):  K_2=\{x|B^* Ax\leqslant \alpha^*\} 
– теж є випуклою многогранною множиною. 

Звідси випливає, що K – випукла многогранна множина.

Значить, K – випукла многогранна множина виду

Неможливо розібрати вираз (невідома помилка): A^{(1)}x=b^{(1)}, Sx\leqslant \alpha^*, x\geqslant 0, S=B^* A .

Теорема доведена.

Дана теорема має в основному теоретичний інтерес, оскільки немає відносно простих способів побудови матриці B*, полярної до матриці B.

Розглянемо тепер деякі властивості двоетапної задачі, в якій випадковим є вектор Неможливо розібрати вираз (невідома помилка): b=b(\omega) .

Згідно з вищерозглянутими твердженнями, задача, що розглядається, може бути записана у вигляді:

Неможливо розібрати вираз (невідома помилка): \min_x Q(x)=\min+x \{cx+MP(x,b)\} (1)

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

Неможливо розібрати вираз (невідома помилка): Sx\leqslant \alpha^*

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

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

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

для заданих х і b.

Має місце наступна лема:

Лема 4. Нехай Неможливо розібрати вираз (невідома помилка): x^0

– розв’язок задачі опуклого програмування (1)-(4). Тоді Неможливо розібрати вираз (невідома помилка): x^0
є розв’язком наступної задачі лінійного програмування:

Неможливо розібрати вираз (невідома помилка): cx\rightarrow \min

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

Неможливо розібрати вираз (невідома помилка): Sx\leqslant \alpha^*

Неможливо розібрати вираз (невідома помилка): Ax=Ax^0

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

Теорема 2. Кожна розв’язна задача вигляду (1)-(4) має розв’язок x*, в якому додатні (базисні) складові вектора x* відповідають лінійно незалежним стовпчикам матриці:

Неможливо розібрати вираз (невідома помилка): \begin{pmatrix} A^{(1)} \\ S \\ A \end{pmatrix}

Доведення: Нехай Неможливо розібрати вираз (невідома помилка): x^0

– розв’язок задачі (1)-(4). Згідно з лемою 4, вектор Неможливо розібрати вираз (невідома помилка):  x^0 
є розв’язком задачі (7)-(11). Також легко бачити, що оптимальний план Неможливо розібрати вираз (невідома помилка):  \tilde{x} 
задачі (7)-(11) є оптимальним планом задачі (1)-(4). Дійсно, з того, що Неможливо розібрати вираз (невідома помилка):  A\tilde{x}=Ax^0 
випливає, що Неможливо розібрати вираз (невідома помилка):  P(\tilde{x},b(\omega))=P(x^0,b(\omega))
для всіх Неможливо розібрати вираз (невідома помилка):  \omega\in\Omega 

. А за цих умов мінімум Неможливо розібрати вираз (невідома помилка): Q(x)

досягіється при Неможливо розібрати вираз (невідома помилка):  c\tilde{x}=cx^0 

.

Оскільки задача лінійного програмування (7)-(11) має оптимальний план x^0, вона повинна мати і опорний оптимальний план. Позначимо його через x*. Тоді базисним компонентам вектора x* відповідають лінійно незалежні стовбці матриці

Неможливо розібрати вираз (невідома помилка): \begin{pmatrix} A^{(1)} \\ S \\ A \end{pmatrix}

і x* – розв’язок задачі (1)-(4).

Теорема доведена.

Наслідок 1. Кожна розв’язна задача вигляду (1)-(4) має розв’язок x*, в якому базисні складові вектора x* відповідають лінійно незалежним стовпчикам матриці:

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

Це твердження слідує з теореми 2 через те, що Неможливо розібрати вираз (невідома помилка): S=B^* A .

Наслідок 2. Нехай ранг матриці А дорівнює Неможливо розібрати вираз (невідома помилка): r (\leqslant m)

і задача (1)-(4) розв’язна. Тоді ця задача має розв’язок x*, в якому не більше, m+r складових вектора x* додатні. 

Це твердження слідує з наслідку 1.

Виконав: Олійник Артем Олександрович