Відмінності між версіями «Одноетапна М-модель з імовірнісними обмеженнями. Розв’язувальні правила. Узагальнення для скінченнозначних обмежень (без доведення).»

Матеріал з Вікі ЦДУ
Перейти до: навігація, пошук
(видалення частини тексту, уточнення, форматування)
 
(не показані 2 проміжні версії цього учасника)
Рядок 1: Рядок 1:
−
<font size=3> Побудуємо розв’язувальне правило для наступної задачі стохастичного програмування. Обчислити максимум функціоналу <math>M\varphi_0(w,x(w))</math>  серед всіх вимірних функцій <math>x(w)</math>, приймають значення в множині <math>X</math>, і таких, що <math>P{x(w)\in G(w)\geq\alpha}</math>.
+
<font size=3> Побудуємо розв’язувальне правило для наступної задачі стохастичного програмування. Обчислити максимум функціоналу <math>M\varphi_0(w,x(w))</math>  серед всіх визначених функцій <math>x(w)</math>, що визначені на множині <math>X</math>, і таких, що <math>P{x(w)\in G(w)\geq\alpha}</math>.
  
 
<font size=3> Тут <math>0\leq\alpha\leq1</math>, а випадкова область <math>G(w)</math> така, що множина <math>{x,w|x\in G(w)}</math> - борелівська множина у <math>X\times\Omega</math>.
 
<font size=3> Тут <math>0\leq\alpha\leq1</math>, а випадкова область <math>G(w)</math> така, що множина <math>{x,w|x\in G(w)}</math> - борелівська множина у <math>X\times\Omega</math>.
  
−
<font size=3> Нехай <math>\varphi(w,x)</math> - характеристична функція множини <math>G(w)</math>, тобто
+
<font size=3> <math>\ M(cx) \rightarrow max </math>, (1.1) </font>
  
−
<math>\varphi(w,x)=\begin{cases}
+
<font size=3> <math>\ P \left \{ \sum^{n}_{j=1} a_{ij}x_j \leq b_i \right \} \geq p_{i}, i=1,...,m </math>. (1.2) </font>
−
1, x\in G(w)\\
+
−
0, x\in G(w)
+
−
\end{cases}</math>
+
  
−
Розглянута задача може бути переписана в наступній еквівалентній формі
+
<font size=3> Умови <math>\ x \geq 0 </math> припускаються включеними у систему нерівностей (1.2) з <math>\ p_{i}=1 </math>. </font>
  
−
<math>\int\limits_{\Omega}\varphi_0(w,x(w))\,dp\rightarrow sup</math>, (1)
+
<font size=3> Будемо вважати матрицю <math>\ A=||a_{ij}|| </math> детермінованою, а вектори <math> b </math> і <math> c </math> незалежними випадковими векторами. Компоненти кожного з цих векторів можуть бути корельованими між собою. Наступні обчислення будемо вести, припускаючи, що складові вектора обмежень <math> b </math> розподілені нормально. </font>
  
−
<math>\int\limits_{\Omega}\varphi(w,x(w))\,dp\rightarrow \alpha</math>, (2)
+
<font size=3> Задамо розв'язувальне правило у вигляді </font>
  
−
Де <math>p</math> - ймовірнісна міра, що визначає ймовірнісний простір <math>(\Omega,\Sigma,p)</math>. Будемо припускати, що міра <math>p</math> неперервна і регулярна щодо топології <math>\Omega</math>.
+
<font size=3> <math>\ x=Db </math>, (1.3) </font>
−
Розв’язувальне правило (критерій оптимальності) для задач (1), (2)
+
  
−
Для того, щоб <math>x(w)</math> було розв’язком задач (1), (2), необхідно і достатньо існування такого  <math>\lambda\geq 0</math>,що <math>x(w)\in G(w)</math> і <math>\psi_0 (w,x(w))=\alpha(w)</math>, якщо <math>\alpha(w)+\lambda<b(w)</math> або <math>w\in M(\lambda),\psi_0 (w,x(w))=b(w)</math>, якщо <math>\alpha(w)+\lambda<b(w)</math> або <math>w\in N(\lambda)</math>.
+
<font size=3> де <math> D </math> - невідома детермінована матриця розміру <math>\ n \times m </math>. </font>
  
−
Тут <math>M(\lambda)\cup N(\lambda)={W|\alpha(W)+\lambda=b(w)}</math> і <math>PM(\lambda)+r(\lambda)=\alpha_0</math>.  
+
<font size=3> Знайти розв'язки задачі (1.1)-(1.3) - означає очбислити елементи <math>\ d_{ij} </math> матриці <math> D </math>. </font>
 +
 
 +
<font size=3> Перетворимо запис задачі (1.1)-(1.3). Підставимо (1.3) у вираз для показника якості (1.1) розв'язку задачі. Враховуючи статистичну незалежність векторів <math> c </math> і <math> b </math>, маємо </font>
 +
 
 +
<font size=3> <math> M(cx)=\overline{cx}=\overline{cDb}=\sum^m_{i=1} \sum^n_{j=1}d_{ij}\bar{b_i}\bar{c_i} </math>, </font>
 +
 
 +
<font size=3> де <math> \bar{c} </math> і <math>\bar{b} </math> - математичні сподівання векторів <math> c </math> і <math> b </math>. </font>
 +
 
 +
<font size=3> Зведемо тепер умови (1.2) до еквівалентного детермінованого вигляду. Позначимо через <math>\ a_i=(a_{i1},...,a_{in}) </math> ''i''-ий вектор-рядок матриці <math> A </math> і введемо випадкову змінну <math>\ \zeta_i </math>: </font>
 +
 
 +
<font size=3> <math>\ \zeta_i=\frac{(b_i-\bar{b}_i)-a_iD(b-\bar{b})}{\sqrt{M[(b_i-\bar{b}_i)-a_iD(b-\bar{b})]^2}} </math>. </font>
 +
 
 +
<font size=3> Легко бачити, що </font>
 +
 
 +
<font size=3> <math>\ \bar{\zeta}_i=M \zeta_i=0  </math> та <math>\ \sigma^2_{\zeta_i}=M(\zeta_i-\bar{\zeta}_i)^2=1  </math>, </font>
 +
 
 +
<font size=3> тобто випадкові величини <math>\ \zeta_i </math> мають нульові математичні сподівання та одиничні дисперсії. </font>
 +
 
 +
<font size=3> Неважко впевнитися безпосередніми обчисленнями, що умови  <math>\ \sum^n_{j=1}a_{ij}x_j \le b_i </math>, або, що є те ж саме у припущенні (1.3),  </font>
 +
 
 +
<font size=3> <math>\ a_iDb \le b_i </math> еквівалентні співвідношенням </font>
 +
 
 +
<font size=3> <math>\ \zeta_i \ge \zeta^0_i=\frac{-\bar{b}_i+a_iD\bar{b}}{\sqrt{M[(b_i-\bar{b}_i)-a_iD(b-\bar{b})]^2}} </math>. (1.4) </font>
 +
 
 +
<font size=3> Тому умови (1.2) можуть бути замінені нерівностями вигляду </font>
 +
 
 +
<font size=3> <math> P( \zeta_i \ge \zeta^0_i) \ge p_i, i=1,2,...,m </math>. (1.5) </font>
 +
 
 +
<font size=3> Випадкові величини <math> \zeta_i </math> як лінійні комбінації нормально розподілених випадкових величин розподілені нормально. Тому співвідношення (1.5) еквівалентні нерівностям </font>
 +
 
 +
<font size=3> <math>\ \frac{1}{\sqrt{2 \pi}} \int\limits_{\zeta^0_i}^\infty e^{-\frac{t^2}{2}}dt \ge p_i </math>, або <math>\ 1-\Phi (\zeta^0_i) \ge p_i </math>, </font>
 +
 
 +
<font size=3> де <math>\ \Phi(z)=\frac{1}{\sqrt{2 \pi}} \int\limits_{\zeta^0_i}^\infty e^{-\frac{t^2}{2}}dt </math> - [https://ru.wikipedia.org/wiki/Функция_ошибок функція Лапласа]. </font>
 +
 
 +
<font size=3> Останню нерівність можна переписати у вигляді </font>
 +
 
 +
<font size=3> <math> \zeta^0_i \le \Phi^{-1}(1-p_i)=-k_i </math>.  (1.6) </font>
 +
 
 +
<font size=3> При <math> p_i>\frac{1}{2} </math> (а тільки цей випадок і становить інтерес у практичних задачах) <math>\ k_i>0 </math>. </font>
 +
 
 +
<font size=3> За прийнятих припущень числа <math>\ k_i </math> залежать тільки від заданих ймовірностей <math>\ p_i </math> і не залежать від елементів шуканої матриці <math> D </math>. </font>
 +
 
 +
<font size=3> Підставимо вираз для <math>\ \zeta^0_i </math> з (1.4) у нерівність (1.6). Отримаємо наступний запис обмежень вихідної задачі: </font>
 +
 
 +
<font size=3> <math>\ \bar{b}_i-a_iD\bar{b} \ge k_i \sqrt{M[(b_i-\bar{b}_i)-a_iD(b-\bar{b})]^2} </math>. </font>
 +
 
 +
<font size=3> Введемо додаткові змінні <math>\ z_i </math>, такі, що </font>
 +
 
 +
<font size=3> <math>\ \bar{b}_i-a_iD\bar{b} \ge z_i \ge k_i \sqrt{M[(b_i-\bar{b}_i)-a_iD(b-\bar{b})]^2} </math>. </font>
 +
 
 +
<font size=3> Останнє співвідношення еквівалентне системі нерівностей </font>
 +
 
 +
<font size=3> <math>\ a_iD\bar{b}+z_i \le \bar{b}_i </math>,  (1.7) </font>
 +
 
 +
<font size=3> <math>\ -k_i^2M[(b_i-\bar{b}_i)-a_iD(b-\bar{b})]^2+z_i^2 \ge 0</math>, (1.8) </font>
 +
 
 +
<font size=3> <math>\ z_i \ge 0 </math>, (1.9) </font>
 +
 
 +
<font size=3> <math>\ i=1,2,...,m </math>. </font>
 +
 
 +
<font size=3> Кожна з умов вигляду (1.7) визначає півпростір у просторі змінних <math>\ d_{ij} </math> і <math>\ z_i (i=1,2,...,m, j=1,2,...,n)</math>. Перетин цих півпросторів для <math>\ i=1,2,...,m </math> відповідає опуклій багатогранній множині. Можна довести, що про кожному <math>\ i </math> пара умов вигляду (1.8), (1.9) висікає у просторі змінних <math>\ d_{ij} </math> і <math>\ z_i</math> опуклу множину. Ця множина являє собою "верхню" (у сенсі осі <math>\ z_i</math>) порожнину двополосного гіперболоїда. Таким чином, умови (1.7)-(1.9) висікають у просторі змінних <math>\ d_{ij} </math> і <math>\ z_i </math> опуклу множину. Ми прийшли до задачі опуклого програмування. Перепишемо її у більш компактному вигляді. Введемо позначення </font>
 +
 
 +
<font size=3> <math>\ \mu_i(D)=M(b_i-a_iDb) </math> , (1.10) </font>
 +
 
 +
<font size=3> <math>\ \sigma_i^2(D)=M(b_i-a_iDb)^2 </math>, (1.11) </font>
 +
 
 +
<font size=3> <math>\ i=1,2,...,m </math>. </font>
 +
 
 +
<font size=3> У цих позначеннях задача опуклого програмування - детермінований еквівалент задачі (1.1) - (1.3) - приймає вигляд </font>
 +
 
 +
<font size=3> <math>\ \bar{c}D\bar{b} \rightarrow max </math>, (1.12) </font>
 +
 
 +
<font size=3> <math>\ \mu_i(D)-z_i\ge0 </math>, (1.13) </font>
 +
 
 +
<font size=3> <math>\ k_i^2[\mu_i^2(D)-\sigma_i^2(D)]+z_i^2 \ge 0 </math>, (1.14) </font>
 +
 
 +
<font size=3> <math>\ z_i\ge0, i=1,2,...,m </math>. (1.15) </font>
 +
 
 +
<font size=3> Задача, розглянута вище, являє собою ''M''-модель. </font>
  
−
При цьому шукане <math>\lambda</math> визначається формулою <math>\lambda_0 = \lambda(\alpha_0) = inf(\lambda\geq 0 | q (\lambda) \geq \alpha_0)</math>. (3)
 
  
 
Виконала: [[Користувач:Боженко Альбіна|Боженко Альбіна]]
 
Виконала: [[Користувач:Боженко Альбіна|Боженко Альбіна]]
  
 
Редагувала: [[Користувач:Yana230896|Латій Яна]]
 
Редагувала: [[Користувач:Yana230896|Латій Яна]]
 +
 +
Редагувала: [[Користувач:9190373|Мамонтова Галина]]

Поточна версія на 20:56, 20 грудня 2020

Побудуємо розв’язувальне правило для наступної задачі стохастичного програмування. Обчислити максимум функціоналу Неможливо розібрати вираз (невідома помилка): M\varphi_0(w,x(w)) 

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

, що визначені на множині Неможливо розібрати вираз (невідома помилка): X , і таких, що Неможливо розібрати вираз (невідома помилка): P{x(w)\in G(w)\geq\alpha} .

Тут Неможливо розібрати вираз (невідома помилка): 0\leq\alpha\leq1 , а випадкова область Неможливо розібрати вираз (невідома помилка): G(w) 

така, що множина Неможливо розібрати вираз (невідома помилка): {x,w|x\in G(w)}
- борелівська множина у Неможливо розібрати вираз (невідома помилка): X\times\Omega

.

Неможливо розібрати вираз (невідома помилка): \ M(cx) \rightarrow max , (1.1)

Неможливо розібрати вираз (невідома помилка): \ P \left \{ \sum^{n}_{j=1} a_{ij}x_j \leq b_i \right \} \geq p_{i}, i=1,...,m . (1.2)

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

припускаються включеними у систему нерівностей (1.2) з Неможливо розібрати вираз (невідома помилка): \ p_{i}=1

.

Будемо вважати матрицю Неможливо розібрати вираз (невідома помилка): \ A=||a_{ij}|| 

детермінованою, а вектори Неможливо розібрати вираз (невідома помилка):  b 
і Неможливо розібрати вираз (невідома помилка):  c 
незалежними випадковими векторами. Компоненти кожного з цих векторів можуть бути корельованими між собою. Наступні обчислення будемо вести, припускаючи, що складові вектора обмежень Неможливо розібрати вираз (невідома помилка):  b 
розподілені нормально.

Задамо розв'язувальне правило у вигляді

Неможливо розібрати вираз (невідома помилка): \ x=Db , (1.3)

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

- невідома детермінована матриця розміру Неможливо розібрати вираз (невідома помилка): \ n \times m

.

Знайти розв'язки задачі (1.1)-(1.3) - означає очбислити елементи Неможливо розібрати вираз (невідома помилка): \ d_{ij} 

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

.

Перетворимо запис задачі (1.1)-(1.3). Підставимо (1.3) у вираз для показника якості (1.1) розв'язку задачі. Враховуючи статистичну незалежність векторів Неможливо розібрати вираз (невідома помилка): c 

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

, маємо

Неможливо розібрати вираз (невідома помилка): M(cx)=\overline{cx}=\overline{cDb}=\sum^m_{i=1} \sum^n_{j=1}d_{ij}\bar{b_i}\bar{c_i} ,

де Неможливо розібрати вираз (невідома помилка): \bar{c} 

і Неможливо розібрати вираз (невідома помилка): \bar{b} 
- математичні сподівання векторів Неможливо розібрати вираз (невідома помилка):  c 
і Неможливо розібрати вираз (невідома помилка):  b

.

Зведемо тепер умови (1.2) до еквівалентного детермінованого вигляду. Позначимо через Неможливо розібрати вираз (невідома помилка): \ a_i=(a_{i1},...,a_{in}) 

i-ий вектор-рядок матриці Неможливо розібрати вираз (невідома помилка):  A 
і введемо випадкову змінну Неможливо розібрати вираз (невідома помилка): \ \zeta_i

Неможливо розібрати вираз (невідома помилка): \ \zeta_i=\frac{(b_i-\bar{b}_i)-a_iD(b-\bar{b})}{\sqrt{M[(b_i-\bar{b}_i)-a_iD(b-\bar{b})]^2}} .

Легко бачити, що

Неможливо розібрати вираз (невідома помилка): \ \bar{\zeta}_i=M \zeta_i=0 

та Неможливо розібрати вираз (невідома помилка): \ \sigma^2_{\zeta_i}=M(\zeta_i-\bar{\zeta}_i)^2=1

,

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

мають нульові математичні сподівання та одиничні дисперсії.

Неважко впевнитися безпосередніми обчисленнями, що умови Неможливо розібрати вираз (невідома помилка): \ \sum^n_{j=1}a_{ij}x_j \le b_i , або, що є те ж саме у припущенні (1.3),

Неможливо розібрати вираз (невідома помилка): \ a_iDb \le b_i 

еквівалентні співвідношенням

Неможливо розібрати вираз (невідома помилка): \ \zeta_i \ge \zeta^0_i=\frac{-\bar{b}_i+a_iD\bar{b}}{\sqrt{M[(b_i-\bar{b}_i)-a_iD(b-\bar{b})]^2}} . (1.4)

Тому умови (1.2) можуть бути замінені нерівностями вигляду

Неможливо розібрати вираз (невідома помилка): P( \zeta_i \ge \zeta^0_i) \ge p_i, i=1,2,...,m . (1.5)

Випадкові величини Неможливо розібрати вираз (невідома помилка): \zeta_i 

як лінійні комбінації нормально розподілених випадкових величин розподілені нормально. Тому співвідношення (1.5) еквівалентні нерівностям

Неможливо розібрати вираз (невідома помилка): \ \frac{1}{\sqrt{2 \pi}} \int\limits_{\zeta^0_i}^\infty e^{-\frac{t^2}{2}}dt \ge p_i , або Неможливо розібрати вираз (невідома помилка): \ 1-\Phi (\zeta^0_i) \ge p_i ,

де Неможливо розібрати вираз (невідома помилка): \ \Phi(z)=\frac{1}{\sqrt{2 \pi}} \int\limits_{\zeta^0_i}^\infty e^{-\frac{t^2}{2}}dt 

- функція Лапласа.

Останню нерівність можна переписати у вигляді

Неможливо розібрати вираз (невідома помилка): \zeta^0_i \le \Phi^{-1}(1-p_i)=-k_i . (1.6)

При Неможливо розібрати вираз (невідома помилка): p_i>\frac{1}{2} 

(а тільки цей випадок і становить інтерес у практичних задачах) Неможливо розібрати вираз (невідома помилка): \ k_i>0

.

За прийнятих припущень числа Неможливо розібрати вираз (невідома помилка): \ k_i 

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

.

Підставимо вираз для Неможливо розібрати вираз (невідома помилка): \ \zeta^0_i 

з (1.4) у нерівність (1.6). Отримаємо наступний запис обмежень вихідної задачі:

Неможливо розібрати вираз (невідома помилка): \ \bar{b}_i-a_iD\bar{b} \ge k_i \sqrt{M[(b_i-\bar{b}_i)-a_iD(b-\bar{b})]^2} .

Введемо додаткові змінні Неможливо розібрати вираз (невідома помилка): \ z_i , такі, що

Неможливо розібрати вираз (невідома помилка): \ \bar{b}_i-a_iD\bar{b} \ge z_i \ge k_i \sqrt{M[(b_i-\bar{b}_i)-a_iD(b-\bar{b})]^2} .

Останнє співвідношення еквівалентне системі нерівностей

Неможливо розібрати вираз (невідома помилка): \ a_iD\bar{b}+z_i \le \bar{b}_i , (1.7)

Неможливо розібрати вираз (невідома помилка): \ -k_i^2M[(b_i-\bar{b}_i)-a_iD(b-\bar{b})]^2+z_i^2 \ge 0 , (1.8)

Неможливо розібрати вираз (невідома помилка): \ z_i \ge 0 , (1.9)

Неможливо розібрати вираз (невідома помилка): \ i=1,2,...,m .

Кожна з умов вигляду (1.7) визначає півпростір у просторі змінних Неможливо розібрати вираз (невідома помилка): \ d_{ij} 

і Неможливо розібрати вираз (невідома помилка): \ z_i (i=1,2,...,m, j=1,2,...,n)

. Перетин цих півпросторів для Неможливо розібрати вираз (невідома помилка): \ i=1,2,...,m 

відповідає опуклій багатогранній множині. Можна довести, що про кожному Неможливо розібрати вираз (невідома помилка): \ i 
пара умов вигляду (1.8), (1.9) висікає у просторі змінних Неможливо розібрати вираз (невідома помилка): \ d_{ij} 
і Неможливо розібрати вираз (невідома помилка): \ z_i
опуклу множину. Ця множина являє собою "верхню" (у сенсі осі Неможливо розібрати вираз (невідома помилка): \ z_i

) порожнину двополосного гіперболоїда. Таким чином, умови (1.7)-(1.9) висікають у просторі змінних Неможливо розібрати вираз (невідома помилка): \ d_{ij} 

і Неможливо розібрати вираз (невідома помилка): \ z_i 
опуклу множину. Ми прийшли до задачі опуклого програмування. Перепишемо її у більш компактному вигляді. Введемо позначення

Неможливо розібрати вираз (невідома помилка): \ \mu_i(D)=M(b_i-a_iDb) 

, (1.10)

Неможливо розібрати вираз (невідома помилка): \ \sigma_i^2(D)=M(b_i-a_iDb)^2 , (1.11)

Неможливо розібрати вираз (невідома помилка): \ i=1,2,...,m .

У цих позначеннях задача опуклого програмування - детермінований еквівалент задачі (1.1) - (1.3) - приймає вигляд

Неможливо розібрати вираз (невідома помилка): \ \bar{c}D\bar{b} \rightarrow max , (1.12)

Неможливо розібрати вираз (невідома помилка): \ \mu_i(D)-z_i\ge0 , (1.13)

Неможливо розібрати вираз (невідома помилка): \ k_i^2[\mu_i^2(D)-\sigma_i^2(D)]+z_i^2 \ge 0 , (1.14)

Неможливо розібрати вираз (невідома помилка): \ z_i\ge0, i=1,2,...,m . (1.15)

Задача, розглянута вище, являє собою M-модель.


Виконала: Боженко Альбіна

Редагувала: Латій Яна

Редагувала: Мамонтова Галина

Отримано з https://wiki.cusu.edu.ua/index.php?title=Одноетапна_М-модель_з_імовірнісними_обмеженнями._Розв’язувальні_правила._Узагальнення_для_скінченнозначних_обмежень_(без_доведення).&oldid=371745