|
|
| Рядок 1: |
Рядок 1: |
| − | <font size=3> Побудуємо детерміновану задачу, еквівалентну до двохетапної задачі стохастичного програмування. </font> | + | <font size=3> Побудуємо детерміновану задачу, еквівалентну до двохетапної задачі стохастичного програмування. </font> |
| − | <font size=3> Розв'язком еквівалентної задачі є попередній план <math>\ х </math>. По складовим оптимального попереднього плану і реалізаціям ппараметрів умов будується задача другого етапу - задача лінійного програмування, розв'язок якої визначає необхідну компенсацію плану. </font> | + | <font size=3> Розв'язком еквівалентної задачі є попередній план <math>\ x </math>. По складовим оптимального попереднього плану і реалізаціям параметрів умов будується задача другого етапу - задача лінійного програмування, розв'язок якої визначає необхідну компенсацію плану. </font> |
| − | | + | |
| | <font size=3> Еквівалентна детермінована задача має вигляд </font> | | <font size=3> Еквівалентна детермінована задача має вигляд </font> |
| | <math> \min_{x\in K}Q(x) </math> | | <math> \min_{x\in K}Q(x) </math> |
| Рядок 8: |
Рядок 7: |
| | | | |
| | <font size=3> Виразимо <math>\ Q(x) </math> через статистичні характеристики параметрів умов задачі і доведемо, що детермінована задача, еквівалентна задачі СП, є задачею опуклого програмуваня. </font> | | <font size=3> Виразимо <math>\ Q(x) </math> через статистичні характеристики параметрів умов задачі і доведемо, що детермінована задача, еквівалентна задачі СП, є задачею опуклого програмуваня. </font> |
| − |
| |
| − | <font size=3> '''Розглянемо задачу другого етапу''' </font>
| |
| − |
| |
| − | <math> P(x, A, b)=\min_{\ y}q(y) (3.4) </math>
| |
| − |
| |
| − | <math>\ {By=b-Ax} (3.5) </math>,
| |
| − |
| |
| − | <math> y \geqslant 0 (3.6) </math>
| |
| − |
| |
| − | <font size=3> та двоїсту до неї </font>
| |
| − |
| |
| − | <math> Q(x, A, b)=\max_{\ z}z(b-Ax) (3.8)</math>
| |
| − |
| |
| − | <math> zB \leqslant q</math> (3.9)
| |
| − |
| |
| − | <font size=3> для кожного <math>\ x, A, b </math>. </font>
| |
| − |
| |
| − | <font size=3> Будемо вважати, що задача другого етапу, а отже, і двоїста до неї задачі розв'язні.</font>
| |
| − |
| |
| − | <font size=3> За теоремою двоїстості для лінійного програмування </font>
| |
| − |
| |
| − | <math>\ P(x, A, b)= Q(x, A, b)= z*(A, b, x)(b-Ax) </math>,
| |
| − |
| |
| − | <font size=3> де <math>\ z*(A, b, x) </math> - розв'язок задачі (3.8)-(3.9).</font>
| |
| − |
| |
| − | <font size=3> Враховуючи введені позначення, можна тепер двохетапну задачу (1.8)-(1.10) переписати наступним чином: </font>
| |
| − |
| |
| − | <math> \min_{x\in K}Q(x)=\min_{x\in K}{\bar{c}x+MQ(x, A, b)} </math>
| |
| − |
| |
| − | <font size=3> або </font>
| |
| − |
| |
| − | <math> \bar{c}x+M[z*(A, b, x)(b-Ax)]\rightarrow min, </math> (4.1)
| |
| − |
| |
| − | <math> x \in K</math>
| |
| − |
| |
| − | <font size=3> Має місце твердження. </font>
| |
| − |
| |
| − | <font size=3> '''Теорема 4.1.''' Нехай матриця <math>\ B </math> задовольняє умовам теореми 3.3 і множина планів задачі (3.8)-(3.90) не порожня. Тоді цільова функція (4.1) еквівалентної детермінованої задачі скінченна для будь-якого <math> x \in K_2</math>. </font>
| |
| − |
| |
| − | <font size=3> Наступне твердження є ''теоретичною основою'' для побудови чисельних методів розв'язання двохетапної задачі. </font>
| |
| − |
| |
| − | <font size=3> '''Теорема 4.2.''' Детермінована задача (4.1)-(4.2), еквівалентна двохетапній задачі (1.8)-(1.10), є задачею опуклого програмування. </font>
| |
| − |
| |
| − | <font size=3> Зауважимо, що з опуклості функції <math>\ Q(x) </math> випливає її неперервність у всіх внутрішніх точках опуклої множини <math>\ К </math>. </font>
| |
| − |
| |
| − | <font size=3> Для побудови методів розв'язання двохетапної задачі доцільно знайти вираз для опорного функціоналу до <math>\ Q(x) </math> і встановити умови диференційованості <math>\ Q(x) </math>. </font>
| |
| − |
| |
| − | <font size=3> Нагадаємо, що лінійний функціонал <math>\ l </math> називається опорним для опуклого вниз функціоналу <math>\ \phi </math> (\lambda)</math> (субградієнтом до <math>\ \phi </math> (\lambda)</math>) у точці <math> \lambda_0 \in \Lambda</math>, якщо <math> \phi (\lambda)-\phi (\lambda_0) \geq (l, \lambda-\lambda_0)</math> при всіх <math> \lambda \in \Lambda </math>. </font>
| |
| − |
| |
| − | <font size=3> '''Теорема 4.3.''' Функціонал </font>
| |
| − |
| |
| − | <math> M{c-z^*(A, b, x_0)A}=\int\limits_{\Omega}{c(\omega)-z^*[A(\omega), b(\omega), x_0]A(\omega)}dp </math>
| |
| − |
| |
| − | <font size=3> є опорним до цільового функціоналу (4.1) еквівалентної детермінованої задачі у точці <math> x_0 \in K </math>. </font>
| |
| − |
| |
| − | <font size=3> '''Доведення'''. Функція <math>\ z^*(A, b, x) </math> за означенням є розв'язком задачі (3.8)-(3.9) для заданого <math> x \in K</math> і фіксованого <math>\ A </math> i <math>\ b </math>. Звідси, </font>
| |
| − |
| |
| − | <math> cx+z^*(A, b, x)(b-Ax) \geq cx+z^*(a, b, x_0)(b-Ax) </math>,
| |
| − |
| |
| − | <font size=3> або, що те ж саме, </font>
| |
| − |
| |
| − | <math> [c-z^*(A, b, x)A]x+z^*(A, b, x)b \geq [c-z^*(A, b, x)A]x+z^*(A, b, x_0)b </math>.
| |
| − |
| |
| − | <font size=3> За означенням </font>
| |
| − |
| |
| − | <math> Q(x)=\bar{c}x+\int\limits_{\Omega}z^*(A, b, x)(b-Ax)dp </math>.
| |
| − |
| |
| − | <font size=3> Тому з останньої рівності випливає, що </font>
| |
| − |
| |
| − | <math> Q(x) \geq \int\limits_{\Omega}[c-z^*(A, b, x_0)A]xdp+\int\limits_{\Omega}z^*(A, b, x_0)bdp </math>.
| |
| − |
| |
| − | <font size=3> З іншої сторони, </font>
| |
| − |
| |
| − | <math> Q(x_0) = \int\limits_{\Omega}[c-z^*(A, b, x_0)A]x_0dp+\int\limits_{\Omega}z^*(A, b, x_0)bdp </math>.
| |
| − |
| |
| − | <font size=3> Звідси випливає, що </font>
| |
| − |
| |
| − | <math> Q(x)-Q(x_0)\geq \int\limits_{\Omega}[c-z^*(A, b, x_0)A]xdp \cdot (x-x_0) </math>, (4.3)
| |
| − |
| |
| − | <font size=3> що й треба було довести. </font>
| |
| − |
| |
| − | <font size=3> Якщо виконуються умови теореми 4.1 і ймовірнісна міра у просторі <math>\ A </math>, <math>\ b </math> абсолютно неперервні відносно міри Лебега у просторі <math>\ A </math>, <math>\ b </math>, (тобто ймовірність попасти у шар достатньо малого радіуса скільки завгодно мала), то цільова функція <math>\ Q(x)</math> еквівалентної детермінованої задачі всюди на <math>\ K </math> неперервно диференційована. </font>
| |
