Відмінності між версіями «Детермінована задача, еквівалентна до двохетапної задачі СП.»
9190313 (обговорення • внесок) |
|||
| (не показані 37 проміжних версій 5 учасників) | |||
| Рядок 1: | Рядок 1: | ||
| − | Побудуємо детерміновану задачу, еквівалентну до двохетапної задачі стохастичного програмування. | + | <font size=3> Побудуємо детерміновану задачу, еквівалентну до двохетапної задачі стохастичного програмування. </font> |
| − | Еквівалентна детермінована задача має вигляд | + | <font size=3> Розв'язком еквівалентної задачі є попередній план <math>\ x </math>. По складовим оптимального попереднього плану і реалізаціям параметрів умов будується задача другого етапу - задача лінійного програмування, розв'язок якої визначає необхідну компенсацію плану. </font> |
| − | <math> \min_{x\in K}Q(x) </math> | + | <font size=3> Еквівалентна детермінована задача має вигляд </font> |
| + | <math> \min_{x\in K}Q(x) </math> | ||
| − | + | <font size=3> До цього ми вивчали область визначення <math>\ K </math> попередніх планів двохетапної задачі. Далі дослідимо цільовий функціонал <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> P(x, A, b)=\min_{\ y}q(y) (3.4) </math> |
| − | <math> By=b-Ax (3.5)</math>, | + | <math>\ {By=b-Ax} (3.5) </math>, |
| − | <math> y \geqslant 0 (3.6)</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> Q(x, A, b)=\max_{\ z}z(b-Ax) (3.8)</math> | ||
| Рядок 22: | Рядок 23: | ||
<math> zB \leqslant q</math> (3.9) | <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>, | + | <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> | <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> \bar{c}x+M[z*(A, b, x)(b-Ax)]\rightarrow min, </math> (4.1) | ||
| Рядок 42: | Рядок 43: | ||
<math> x \in K</math> | <math> x \in K</math> | ||
| − | Має місце твердження. | + | <font size=3> Має місце твердження. </font> |
| − | Теорема 4.1. | + | <font size=3> '''Теорема 4.1.''' Нехай матриця <math>\ B </math> задовольняє умовам теореми 3.3 і множина планів задачі (3.8)-(3.9) не порожня. Тоді цільова функція (4.1) еквівалентної детермінованої задачі скінченна для будь-якого <math> x \in K_2</math>. </font> |
| − | Наступне твердження є теоретичною основою для побудови чисельних методів розв'язання двохетапної задачі. | + | <font size=3> Наступне твердження є ''теоретичною основою'' для побудови чисельних методів розв'язання двохетапної задачі. </font> |
| − | Теорема 4.2. Детермінована задача (4.1)-(4.2), еквівалентна двохетапній задачі (1.8)-(1.10), є задачею опуклого програмування. | + | <font size=3> '''Теорема 4.2.''' Детермінована задача (4.1)-(4.2), еквівалентна двохетапній задачі (1.8)-(1.10), є задачею опуклого програмування. </font> |
| − | + | <font size=3> '''Доведення.''' Відповідно теоремі 2.2. множина <math>K</math> попередніх планів опукла. Залишається довести, що <math>Q(x)</math> опукла вниз по <math>x</math>. Для цього достатньо показати, що <math>Q(x,A,b)</math> опукла по <math>x</math> для всіх <math>A</math> і <math>b</math>. | |
| − | + | <font size=3> '''Опукла функція''' – функція, яка визначена на опуклій множині лінійного простору, і задовольняє нерівності | |
| − | Нагадаємо, що лінійний функціонал | + | <math> f(\lambda x+(1-\lambda)y) \leq \lambda f+(1-\lambda) </math>, при всіх <math>\lambda\in[0,1]</math>. |
| + | |||
| + | <font size=3> Нехай <math>x_1,x_2\in K</math> а <math>z^*(A,b,x_1)</math> та <math>z^*(A,b,x_2)</math> - відповідні розв’язки задачі (3.8)-(3.9). Тоді | ||
| + | |||
| + | <math>z^*(A,b,x_1 )(b-Ax_1 )\geq z*(A,b,\lambda x_1+(1-\lambda) x_2 )(b-Ax_1 )</math> | ||
| + | |||
| + | <math>z^*(A,b,x_2 )(b-Ax_2 )\geq z*(A,b,\lambda x_1+(1-\lambda) x_2 )(b-Ax_2 )</math> | ||
| + | |||
| + | <font size=3> Помноживши першу нерівність на <math>\lambda</math>, а другу на <math>(1-\lambda)</math> і додавши їх, отримаємо: | ||
| + | |||
| + | <math>\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 ))</math> | ||
| + | |||
| + | Отже, <math>Q(x,A,b)</math> опукла пo <math>x</math> при всіх <math>A</math> і <math>b</math>. | ||
| + | |||
| + | Тоді і <math>Q(x)=c\bar{x}+\int\limits_{\Omega} Q(x,A,b)\,dp </math> також опукла по <math>x</math>. '''Теорема доведена.''' | ||
| + | |||
| + | <font size=3>Зауважимо, що з опуклості функції <math>\ Q(x)</math> випливає її неперервність у всіх внутрішніх точках опуклої множини <math>\ K </math>. </font> | ||
| + | |||
| + | <font size=3> Для побудови методів розв'язання двохетапної задачі доцільно знайти вираз для опорного функціоналу до <math>\ Q(x) </math> і встановити умови диференційованості <math>\ Q(x) </math>. </font> | ||
| + | |||
| + | <font size=3> Нагадаємо, що лінійний функціонал <math>\ l </math> називається опорним для опуклого вниз функціоналу <math>\ \phi (\lambda) </math> (/субградієнтом до <math>\ \phi (\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> неперервно диференційована. | ||
| + | |||
| + | Виконала: [[Користувач:Кухаренко Настя|Кухаренко Анастасія]] | ||
| + | |||
| + | Редагувала: [[Користувач:9190313|Хачатрян Ліліт]] | ||
Поточна версія на 08:10, 24 травня 2021
Побудуємо детерміновану задачу, еквівалентну до двохетапної задачі стохастичного програмування.
Розв'язком еквівалентної задачі є попередній план Неможливо розібрати вираз (невідома помилка): \ 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 неперервно диференційована.
Виконала: Кухаренко Анастасія
Редагувала: Хачатрян Ліліт
