Детермінована задача, еквівалентна до двохетапної задачі СП.

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

Розв'язком еквівалентної задачі є попередній план Неможливо розібрати вираз (невідома помилка): \ x . По складовим оптимального попереднього плану і реалізаціям параметрів умов будується задача другого етапу - задача лінійного програмування, розв'язок якої визначає необхідну компенсацію плану. Еквівалентна детермінована задача має вигляд Неможливо розібрати вираз (невідома помилка): \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.9) не порожня. Тоді цільова функція (4.1) еквівалентної детермінованої задачі скінченна для будь-якого Неможливо розібрати вираз (невідома помилка):  x \in K_2

.

Наступне твердження є теоретичною основою для побудови чисельних методів розв'язання двохетапної задачі.

Теорема 4.2. Детермінована задача (4.1)-(4.2), еквівалентна двохетапній задачі (1.8)-(1.10), є задачею опуклого програмування.

Доведення. Відповідно теоремі 2.2. множина Неможливо розібрати вираз (невідома помилка): K

попередніх планів опукла. Залишається довести, що Неможливо розібрати вираз (невідома помилка): Q(x)
опукла вниз по Неможливо розібрати вираз (невідома помилка): x

. Для цього достатньо показати, що Неможливо розібрати вираз (невідома помилка): Q(x,A,b)

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

.

Опукла функція – функція, яка визначена на опуклій множині лінійного простору, і задовольняє нерівності

Неможливо розібрати вираз (невідома помилка): f(\lambda x+(1-\lambda)y) \leq \lambda f+(1-\lambda) , при всіх Неможливо розібрати вираз (невідома помилка): \lambda\in[0,1] .

Нехай Неможливо розібрати вираз (невідома помилка): x_1,x_2\in K

а Неможливо розібрати вираз (невідома помилка): z^*(A,b,x_1)
та Неможливо розібрати вираз (невідома помилка): z^*(A,b,x_2)
- відповідні розв’язки задачі (3.8)-(3.9). Тоді 

Неможливо розібрати вираз (невідома помилка): z^*(A,b,x_1 )(b-Ax_1 )\geq z*(A,b,\lambda x_1+(1-\lambda) x_2 )(b-Ax_1 )

Неможливо розібрати вираз (невідома помилка): z^*(A,b,x_2 )(b-Ax_2 )\geq z*(A,b,\lambda x_1+(1-\lambda) x_2 )(b-Ax_2 )

Помноживши першу нерівність на Неможливо розібрати вираз (невідома помилка): \lambda , а другу на Неможливо розібрати вираз (невідома помилка): (1-\lambda)

і додавши їх, отримаємо:

Неможливо розібрати вираз (невідома помилка): \lambda z^*(A,b,x_1 )(b-Ax_1 )+(1-\lambda)z^*(A,b,x_2 )(b-Ax_2 )\geq z^*(A,b,\lambda x_1+(1-\lambda) x_2 )(b-A(\lambda x_1+(1-\lambda) x_2 ))

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

опукла пo Неможливо розібрати вираз (невідома помилка): x
при всіх Неможливо розібрати вираз (невідома помилка): A
і Неможливо розібрати вираз (невідома помилка): b

.

Тоді і Неможливо розібрати вираз (невідома помилка): Q(x)=c\bar{x}+\int\limits_{\Omega} Q(x,A,b)\,dp

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

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

Зауважимо, що з опуклості функції Неможливо розібрати вираз (невідома помилка): \ Q(x)

випливає її неперервність у всіх внутрішніх точках опуклої множини Неможливо розібрати вираз (невідома помилка): \ K 

.

Для побудови методів розв'язання двохетапної задачі доцільно знайти вираз для опорного функціоналу до Неможливо розібрати вираз (невідома помилка): \ Q(x)

і встановити умови диференційованості Неможливо розібрати вираз (невідома помилка): \ Q(x) 

.

Нагадаємо, що лінійний функціонал Неможливо розібрати вираз (невідома помилка): \ l

називається опорним для опуклого вниз функціоналу Неможливо розібрати вираз (невідома помилка): \ \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) для заданого Неможливо розібрати вираз (невідома помилка):  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 
неперервно диференційована.

Виконала: Кухаренко Анастасія

Редагувала: Хачатрян Ліліт