Відмінності між версіями «Детермінована задача, еквівалентна до двохетапної задачі СП.»
| Рядок 1: | Рядок 1: | ||
<font size=3> Побудуємо детерміновану задачу, еквівалентну до двохетапної задачі стохастичного програмування. </font> | <font size=3> Побудуємо детерміновану задачу, еквівалентну до двохетапної задачі стохастичного програмування. </font> | ||
| + | |||
<font size=3> Розв'язком еквівалентної задачі є попередній план <math>\ x </math>. По складовим оптимального попереднього плану і реалізаціям параметрів умов будується задача другого етапу - задача лінійного програмування, розв'язок якої визначає необхідну компенсацію плану. </font> | <font size=3> Розв'язком еквівалентної задачі є попередній план <math>\ x </math>. По складовим оптимального попереднього плану і реалізаціям параметрів умов будується задача другого етапу - задача лінійного програмування, розв'язок якої визначає необхідну компенсацію плану. </font> | ||
<font size=3> Еквівалентна детермінована задача має вигляд </font> | <font size=3> Еквівалентна детермінована задача має вигляд </font> | ||
| Рядок 7: | Рядок 8: | ||
<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> | ||
Версія за 20:59, 22 березня 2014
Побудуємо детерміновану задачу, еквівалентну до двохетапної задачі стохастичного програмування.
Розв'язком еквівалентної задачі є попередній план Неможливо розібрати вираз (невідома помилка): \ 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.90) не порожня. Тоді цільова функція (4.1) еквівалентної детермінованої задачі скінченна для будь-якого Неможливо розібрати вираз (невідома помилка): x \in K_2
.
Наступне твердження є теоретичною основою для побудови чисельних методів розв'язання двохетапної задачі.
Теорема 4.2. Детермінована задача (4.1)-(4.2), еквівалентна двохетапній задачі (1.8)-(1.10), є задачею опуклого програмування.
Зауважимо, що з опуклості функції Неможливо розібрати вираз (невідома помилка): \ Q(x)
випливає її неперервність у всіх внутрішніх точках опуклої множини Неможливо розібрати вираз (невідома помилка): \ К
.
