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

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

<math> \min_x m_{\infty}\{cx+P(x,A,b)\} </math>

<math> A^{(1)}x=b^{(1)} </math>

<math> x \geqslant 0 </math>

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

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

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

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

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

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

Матриця <math> B^*</math> (розмірності <math>l x m</math>) називається полярною до матриці В (розмірності <math>m x n_1</math>), якщо <math> B^*</math> — матриця з мінімальним числом рядків, що задовольняють умові:

<math> C=\{t|\exist y\geqslant 0, t=By\}=\{t|B^* t\geqslant 0\} </math>

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

<math> N=\{\chi|\forall (\omega \in \Omega) \exist y \geqslant 0, By=b(\omega)-\chi\} </math>

<math> N(\omega)=\{\chi| \exist y \geqslant 0, By=b(\omega)-\chi\} </math>

Зрозуміло, що  <math> N=\cap_{\omega \in \Omega}N(\omega) </math>

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

<math> K_2 =\{x|\forall (\omega \in \Omega) \exist y \geqslant 0, By=b(\omega)-A(\omega)x\} </math>

<math> K_2(\omega) =\{x| \exist y \geqslant 0, By=b(\omega)-A(\omega)x\} </math>

Ці множини пов'язані з множинами <math> N </math> і <math> N(\omega) </math> співвідношеннями:

<math> K_2=\{x|A(\omega)=\chi , \chi \in N\} </math>

<math> K_2(\omega)=\{x|A(\omega)=\chi , \chi \in N(\omega)\} </math>

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

Лема 1. Якщо <math>N(\omega)</math> – опукла, багатогранна множина, то <math>K_2 (\omega) </math>– теж опукла багатогранна множина. Якщо <math>N</math> – опукла, багатогранна множина, то <math>K_2</math> – теж опукла багатогранна множина.

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

<math>N(\omega)=\{\chi|B^* \chi \leqslant B^* b(\omega)\} </math>

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

<math> B^* b(\omega) \leqslant\alpha_i^*,i=1,...,l </math>

якщо для деякого <math> i,\alpha_i^*=-\infty </math>, множина N – порожня.

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

Доведення: Множина <math> K=K_1\cap K_2</math>

<math> K_1=\{x|A^{(1)}x=b^{(1)},x \geqslant 0\}</math> – випукла многогранна множина. Відповідно до лем 1 і 3 <math> K_2=\{x|B^* Ax\leqslant \alpha^*|] </math> – теж є випуклою многогранною множиною. 

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

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

<math>A^{(1)}x=b^{(1)}, Sx\leqslant \alpha^*, x\geqslant 0, S=B^* A</math>.

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

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



Розглянемо тепер деякі властивості двоетапної задачі, в якій випадковим є вектор <math>b=b(\omega)</math>. 

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



Виконав: [[Користувач:Олійник_Артем|Олійник Артем Олександрович]]