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