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

Версія за 22:46, 3 червня 2017

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

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

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

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

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

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

Згідно раніше розглянутої теореми (2.2), для загальної двохетапної задачі множина Неможливо розібрати вираз (невідома помилка): K

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

.

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

Як відомо, опуклий багатогранний Конус Неможливо розібрати вираз (невідома помилка): C

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

Еквівалентність двох визначень опуклого багатогранного конуса Неможливо розібрати вираз (невідома помилка): C

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

.

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

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

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

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

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

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

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

– області визначення попередніх планів двохетапної задачі. 

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

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

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

може бути представлена у вигляді: 

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

Лема 1.3. Множина Неможливо розібрати вираз (невідома помилка): N

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

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

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

– порожня. 

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

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

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

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

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

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

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

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

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

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

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

(1.6) 

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

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

.

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

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

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

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

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

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

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

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

Теорема 1.2. Кожна розв’язна задача вигляду (1.1)-(1.4) має розв’язок Неможливо розібрати вираз (невідома помилка): x^* , в якому додатні (базисні) складові вектора Неможливо розібрати вираз (невідома помилка): x^*

відповідають лінійно незалежним стовпчикам матриці: 

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

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

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

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

.

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

відповідають лінійно незалежні стовбці матриці 

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

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

– розв’язок задачі (1.1)-(1.4). 

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

Наслідок 1.1. Кожна розв’язна задача вигляду (1.1)-(1.4) має розв’язок Неможливо розібрати вираз (невідома помилка): x^* , в якому базисні складові вектора Неможливо розібрати вираз (невідома помилка): x^*

відповідають лінійно незалежним стовпчикам матриці: 

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

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

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

і задача (1.1)-(1.4) розв’язна. Тоді ця задача має розв’язок Неможливо розібрати вираз (невідома помилка):  x^* 

складових вектора Неможливо розібрати вираз (невідома помилка):  x^* 
є додатними.  

Це твердження слідує з наслідку 1.1 [1, c. 168-171].

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

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

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

Доповнювала: Іванченко Дар’я