Відмінності між версіями «Детермінована задача, еквівалентна до двохетапної задачі СП.»

Матеріал з Вікі ЦДУ
Перейти до: навігація, пошук
Рядок 1: Рядок 1:
Побудуємо детерміновану задачу, еквівалентну до двохетапної задачі стохастичного програмування. Розв'язком еквівалентної задачі є попередній план ''х''. По складовим оптимального попереднього плану і реалізаціям ппараметрів умов будується задача другого етапу - задача лінійного програмування, розв'язок якої визначає необхідну компенсацію плану.  
+
<font size=3> Побудуємо детерміновану задачу, еквівалентну до двохетапної задачі стохастичного програмування. Розв'язком еквівалентної задачі є попередній план ''х''. По складовим оптимального попереднього плану і реалізаціям ппараметрів умов будується задача другого етапу - задача лінійного програмування, розв'язок якої визначає необхідну компенсацію плану.</font>
  
Еквівалентна детермінована задача має вигляд
+
<font size=3> Еквівалентна детермінована задача має вигляд </font>
 
<math> \min_{x\in K}Q(x) </math>.
 
<math> \min_{x\in K}Q(x) </math>.
  
Дотепер ми вивчали область визначення ''K'' попередніх планів двохетапної задачі. Дослідимо тепер цільовий функціонал ''Q(x)'' - показник якості попереднього плану.
+
<font size=3> Дотепер ми вивчали область визначення ''K'' попередніх планів двохетапної задачі. Дослідимо тепер цільовий функціонал ''Q(x)'' - показник якості попереднього плану.</font>
  
Виразимо ''Q(x)'' через статистичні характеристики параметрів умов задачі і доведемо, що детермінована задача, еквівалентна задачі СП, є задачею опуклого програмуваня.
+
<font size=3> Виразимо ''Q(x)'' через статистичні характеристики параметрів умов задачі і доведемо, що детермінована задача, еквівалентна задачі СП, є задачею опуклого програмуваня.</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>
Рядок 16: Рядок 16:
 
<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: Рядок 22:
 
<math> zB \leqslant q</math> (3.9)
 
<math> zB \leqslant q</math> (3.9)
  
для кожного ''x, A, b''.
+
<font size=3> для кожного ''x, A, b''. </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>,
  
де ''z*(A, b, x)'' - розв'язок задачі (3.8)-(3.9).
+
<font size=3> де ''z*(A, b, x)'' - розв'язок задачі (3.8)-(3.9).</font>
  
Враховуючи введені позначення, можна тепер двохетапну задачу (1.8)-(1.10) переписати наступним чином:
+
<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: Рядок 42:
 
<math> x \in K</math>
 
<math> x \in K</math>
  
Має місце твердження.  
+
<font size=3> Має місце твердження.</font>
  
'''Теорема 4.1.''' Нехай матриця ''B'' задовольняє умовам теореми 3.3 і множина планів задачі (3.8)-(3.90) не порожня. Тоді цільова функція (4.1) еквівалентної детермінованої задачі скінченна для будь-якого <math> x \in K_2</math>.
+
<font size=3> '''Теорема 4.1.''' Нехай матриця ''B'' задовольняє умовам теореми 3.3 і множина планів задачі (3.8)-(3.90) не порожня. Тоді цільова функція (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>
  
Зауважимо, що з опуклості функції ''Q(x)'' випливає її неперервність у всіх внутрішніх точках опуклої множини ''К''.
+
<font size=3> Зауважимо, що з опуклості функції ''Q(x)'' випливає її неперервність у всіх внутрішніх точках опуклої множини ''К''. </font>
  
Для побудови методів розв'язання двохетапної задачі доцільно знайти вираз для опорного функціоналу до ''Q(x)'' і встановити умови диференційованості ''Q(x)''.
+
<font size=3> Для побудови методів розв'язання двохетапної задачі доцільно знайти вираз для опорного функціоналу до ''Q(x)'' і встановити умови диференційованості ''Q(x)''. </font>
  
Нагадаємо, що лінійний функціонал ''l'' називається опорним для опуклого вниз функціоналу <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 size=3> Нагадаємо, що лінійний функціонал ''l'' називається опорним для опуклого вниз функціоналу <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>
 
+
'''Теорема 4.3.''' Функціонал
+
<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>
 
<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>
  
є опорним до цільового функціоналу (4.1) еквівалентної детермінованої задачі у точці <math> x_0 \in K </math>.
+
<font size=3> є опорним до цільового функціоналу (4.1) еквівалентної детермінованої задачі у точці <math> x_0 \in K </math>. </font>
  
'''Доведення'''. Функція ''z^*(A, b, x)'' за означенням є розв'язком задачі (3.8)-(3.9) для заданого <math> x \in K</math> і фіксованого ''A'' i ''b''. Звідси,
+
<font size=3> '''Доведення'''. Функція ''z^*(A, b, x)'' за означенням є розв'язком задачі (3.8)-(3.9) для заданого <math> x \in K</math> і фіксованого ''A'' i ''b''. Звідси, </font>
  
 
<math> cx+z^*(A, b, x)(b-Ax) \geq cx+z^*(a, b, x_0)(b-Ax) </math>,
 
<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>.
 
<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>.
 
<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>.
 
<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>.
 
<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)
 
<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>
  
Якщо виконуються умови теореми 4.1 і ймовірнісна міра у просторі ''A'', ''b'' абсолютно неперервні відносно міри Лебега у просторі ''A'', ''b'', (тобто ймовірність попасти у шар достатньо малого радіуса скільки завгодно мала), то цільова функція ''Q(x)'' еквівалентної детермінованої задачі всюди на ''K'' неперервно диференційована.
+
<font size=3> Якщо виконуються умови теореми 4.1 і ймовірнісна міра у просторі ''A'', ''b'' абсолютно неперервні відносно міри Лебега у просторі ''A'', ''b'', (тобто ймовірність попасти у шар достатньо малого радіуса скільки завгодно мала), то цільова функція ''Q(x)'' еквівалентної детермінованої задачі всюди на ''K'' неперервно диференційована. </font>

Версія за 19:58, 22 березня 2014

Побудуємо детерміновану задачу, еквівалентну до двохетапної задачі стохастичного програмування. Розв'язком еквівалентної задачі є попередній план х. По складовим оптимального попереднього плану і реалізаціям ппараметрів умов будується задача другого етапу - задача лінійного програмування, розв'язок якої визначає необхідну компенсацію плану.

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