Відмінності між версіями «Область визначення двохетапної задачі з випадковим вектором обмежень.»
| Рядок 1: | Рядок 1: | ||
<font size=3> Розглянемо двоетапну задачу стохастичного програмування: </font> | <font size=3> Розглянемо двоетапну задачу стохастичного програмування: </font> | ||
| − | <font size=3> <math> \min_x m_{\omega}\{cx+P(x,A,b)\} </math> </font> | + | <font size=3> <math> \min_x m_{\omega}\{cx+P(x,A,b)\} </math>, </font> |
| − | <font size=3> <math> A^{(1)}x=b^{(1)} </math> </font> | + | <font size=3> <math> A^{(1)}x=b^{(1)} </math>, </font> |
| − | <font size=3> <math> x \geqslant 0 </math> </font> | + | <font size=3> <math> x \geqslant 0 </math>. </font> |
<font size=3> Нехай випадковими є тільки складові вектора обмежень <math> b </math>. Всі інші параметри умов задачі – детерміновані. </font> | <font size=3> Нехай випадковими є тільки складові вектора обмежень <math> b </math>. Всі інші параметри умов задачі – детерміновані. </font> | ||
| Рядок 55: | Рядок 55: | ||
<font size=3> <math> B_i^* \chi(\omega) \leqslant\alpha_i^*,i=1,...,l </math>. </font> | <font size=3> <math> B_i^* \chi(\omega) \leqslant\alpha_i^*,i=1,...,l </math>. </font> | ||
| − | <font size=3> якщо для деякого <math> i,\alpha_i^*=-\infty </math>, множина N – порожня. </font> | + | <font size=3> якщо для деякого <math> i,\alpha_i^*=-\infty </math>, множина <math>N</math> – порожня. </font> |
| − | <font size=3> Теорема 1. Множина K планів детермінованої задачі, що еквівалентна двоетапній задачі стохастичного програмування, в якій випадковим є тільки вектор обмежень b, є опуклою багатогранною множиною. </font> | + | <font size=3> '''Теорема 1.1.''' Множина <math>K</math> планів детермінованої задачі, що еквівалентна двоетапній задачі стохастичного програмування, в якій випадковим є тільки вектор обмежень <math>b</math> , є опуклою багатогранною множиною. </font> |
| − | <font size=3> Доведення: Множина <math> K=K_1\cap K_2</math> </font> | + | <font size=3> ''Доведення:'' Множина <math> K=K_1\cap K_2</math>. </font> |
| − | <font size=3> <math> K_1=\{x|A^{(1)}x=b^{(1)},x \geqslant 0\}</math> – | + | <font size=3> <math> K_1=\{x|A^{(1)}x=b^{(1)},x \geqslant 0\}</math> – опукла багатогранна множина. Відповідно до лем 1.1 і 1.3 <math> K_2=\{x|B^* Ax\leqslant \alpha^*\} </math> – теж є опуклою багатогранною множиною. </font> |
| − | <font size=3> | + | <font size=3> Відповідно, <math>K</math> – опукла багатогранна множина виду </font> |
| − | <font size=3> | + | <font size=3> <math>A^{(1)}x=b^{(1)}, Sx\leqslant \alpha^*, x\geqslant 0</math>, де <math>S=B^* A</math> </font> |
| − | <font size=3> | + | <font size=3> ''Теорема доведена.'' </font> |
| − | + | <font size=3> Дана теорема має в основному теоретичний інтерес, оскільки немає відносно простих способів побудови матриці <math>B^*</math>, полярної до матриці <math>B</math>. </font> | |
| − | + | ||
| − | <font size=3> Дана теорема має в основному теоретичний інтерес, оскільки немає відносно простих способів побудови матриці B*, полярної до матриці B. </font> | + | |
Версія за 22:28, 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
) називається полярною до матриці Неможливо розібрати вираз (невідома помилка): B
(розмірності Неможливо розібрати вираз (невідома помилка): m \times 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|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)
Неможливо розібрати вираз (невідома помилка): 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.
Виконав: Олійник Артем Олександрович
