Відмінності між версіями «Детермінована задача, еквівалентна до двохетапної задачі СП.»
| Рядок 12: | Рядок 12: | ||
<math> P(x, A, b)=\min_{\ y}q(y) (3.4)</math> | <math> P(x, A, b)=\min_{\ y}q(y) (3.4)</math> | ||
| − | <math> By=b-Ax | + | <math> By=b-Ax (3.5)</math>, |
<math> y \geqslant 0 (3.6)</math> | <math> y \geqslant 0 (3.6)</math> | ||
| Рядок 28: | Рядок 28: | ||
За теоремою двоїстості для лінійного програмування | За теоремою двоїстості для лінійного програмування | ||
| − | <math> P(x, A, b)=Q(x, A, b)=z*(A, b, x)(b-Ax) </math>, | + | <math> P(x, A, b)= Q(x, A, b)= z*(A, b, x)(b-Ax) </math>, |
де ''z*(A, b, x)'' - розв'язок задачі (3.8)-(3.9). | де ''z*(A, b, x)'' - розв'язок задачі (3.8)-(3.9). | ||
| Рядок 45: | Рядок 45: | ||
Теорема 4.1. Нехай матриця ''B'' задовольняє умовам теореми 3.3 і множина планів задачі (3.8)-(3.90) не порожня. Тоді цільова функція (4.1) еквівалентної детермінованої задачі скінченна для будь-якого <math> x \in K_2</math>. | Теорема 4.1. Нехай матриця ''B'' задовольняє умовам теореми 3.3 і множина планів задачі (3.8)-(3.90) не порожня. Тоді цільова функція (4.1) еквівалентної детермінованої задачі скінченна для будь-якого <math> x \in K_2</math>. | ||
| + | |||
| + | Наступне твердження є теоретичною основою для побудови чисельних методів розв'язання двохетапної задачі. | ||
| + | |||
| + | Теорема 4.2. Детермінована задача (4.1)-(4.2), еквівалентна двохетапній задачі (1.8)-(1.10), є задачею опуклого програмування. | ||
| + | |||
| + | Зауважимо, що з опуклості функції ''Q(x)'' випливає її неперервність у всіх внутрішніх точках опуклої множини ''К''. | ||
| + | |||
| + | Для побудови методів розв'язання двохетапної задачі доцільно знайти вираз для опорного функціоналу до ''Q(x)'' і встановити умови диференційованості ''Q(x)''. | ||
| + | |||
| + | Нагадаємо, що лінійний функціонал ''l'' називається опорним для опуклого вниз функціоналу <math> \phi (\lambda)</math> (субградієнтом до <math> \phi (\lambda)</math>) у точці <math> \lambda_0 \in \Lambda</math> | ||
Версія за 19:22, 13 квітня 2013
Побудуємо детерміновану задачу, еквівалентну до двохетапної задачі стохастичного програмування. Розв'язко еквівалентної задачі є попередній план х. По складовим оптимального попереднього плану і реалізаціям ппараметрів умов будується задача другого етапу - задача лінійного програмування, розв'язок якої визначає необхідну компенсацію плану.
Еквівалентна детермінована задача має вигляд Неможливо розібрати вираз (невідома помилка): \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) випливає її неперервність у всіх внутрішніх точках опуклої множини К.
Для побудови методів розв'язання двохетапної задачі доцільно знайти вираз для опорного функціоналу до Q(x) і встановити умови диференційованості Q(x).
Нагадаємо, що лінійний функціонал l називається опорним для опуклого вниз функціоналу Неможливо розібрати вираз (невідома помилка): \phi (\lambda)
(субградієнтом до Неможливо розібрати вираз (невідома помилка): \phi (\lambda)
) у точці Неможливо розібрати вираз (невідома помилка): \lambda_0 \in \Lambda
