Відмінності між версіями «Одноетапні стохастичні задачі з лінійними розв’язувальними правилами. М-модель та V-модель.»
Рядок 72: | Рядок 72: | ||
<math>\ i=1,2,...,m </math>. | <math>\ i=1,2,...,m </math>. | ||
+ | |||
+ | Кожна з умов виду (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=1 </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> опуклу множину. Ми прийшли до задачі опуклого програмування. Перепишемо її у більш компактному вигляді. Введемо позначення | ||
+ | |||
+ | <math>\ \mu_i(D)=M(b_i-a_iDb) </math> , (1.10) | ||
+ | |||
+ | <math>\ \sigma_i^2(D)=M(b_i-a_iDb)^2 </math>, (1.11) | ||
+ | |||
+ | <math>\ i=1,2,...,m </math>. | ||
+ | |||
+ | У цих позначеннях задача опуклого програмування - детермінований еквівалент задачі (1.1) - (1.3) - приймає вигляд | ||
+ | |||
+ | <math>\ \bar{c}D\bar{b} \rightarrow max </math>, (1.12) | ||
+ | |||
+ | <math>\ \mu_i(D)-z_i\ge0 </math>, (1.13) | ||
+ | |||
+ | <math>\ k_i^2[\mu_i^2(D)-\sigma_i^2(D)]+z_i^2 \ge 0 </math>, (1.14) | ||
+ | |||
+ | <math>\ z_i\ge0, i=1,2,...,m </math>. (1.15) |
Версія за 18:37, 24 січня 2013
Розглянемо наступну М-модель стохастичного програмування з ймовірнісними обмеженнями:
Неможливо розібрати вираз (невідома помилка): \ M(cx) \rightarrow max , (1.1)
Неможливо розібрати вираз (невідома помилка): \ P \left \{ \sum^{n}_{j=1} a_{ij}x_j \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-ту вектор-строку матриці А і введемо випадкову змінну Неможливо розібрати вираз (невідома помилка): \ \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) \le p_i, i=1,2,...,m . (1/5)
Випадкові величини Неможливо розібрати вираз (невідома помилка): \zeta_i
як лінійні комбінації нормально розподілених випадкових величин розподілені нормально. Тому співвідношення (1.5) еквівалентні нерівностям
Неможливо розібрати вираз (невідома помилка): \ \frac{1}{\sqrt{2 \pi}} \int\limits_{\zeta^0_i}^\infty e^{-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^{-t^2/2}dt
- функція Лапласа.
Останню нерівність можна переписати у вигляді
Неможливо розібрати вираз (невідома помилка): \zeta^0_i \le \Phi^{-1}(1-p_i)=-k_i . (1.6)
При Неможливо розібрати вираз (невідома помилка): p_i>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 пара умов вигляду (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)