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

Матеріал з Вікі ЦДУ
Перейти до: навігація, пошук
(доповнення)
 
(не показані 97 проміжних версій 2 учасників)
Рядок 1: Рядок 1:
−
<font size=3>Розглянемо, двоетапну задачу, в якій випадковим є тільки вектор обмежень, а матриця компенсації ''В''  
+
<font size=3> Недоліком розглянутих одноетапних задач стохастичного програмування є те, що в
 +
них лише фіксується факт можливих відхилень значень випадкових параметрів і
 +
усереднені розв’язки вибирають за умови, що відхилення значень від середнього рівня в
 +
будь-який бік небажане (зменшується величина дисперсії параметрів у обмеженнях або
 +
цільова функція — дисперсія мінімізується). У більшості реальних економічних задач
 +
має значення не лише величина відхилення, але також і його напрямок. Двохетапні задачі
 +
стохастичного програмування позбавлені зазначеного недоліку. <Br>
 +
<font size=3> Розглянемо, двоетапну задачу, в якій випадковим є тільки вектор обмежень, а матриця компенсації ''В''  
 
(після відповідної перестановки рядків і стовпців) може бути представлена ​​у вигляді ''В = (Е, -Е)'', де ''Е'' - одинична матриця розміру ''mxm''. Розіб'ємо вектори ''у'' і ''q'' на дві частини, відповідні підматриці ''Е, -Е'' матриці ''B''. Задача  в цьому випадку приймає вид  
 
(після відповідної перестановки рядків і стовпців) може бути представлена ​​у вигляді ''В = (Е, -Е)'', де ''Е'' - одинична матриця розміру ''mxm''. Розіб'ємо вектори ''у'' і ''q'' на дві частини, відповідні підматриці ''Е, -Е'' матриці ''B''. Задача  в цьому випадку приймає вид  
  
Рядок 12: Рядок 19:
 
<math>P(x,b)=\{min(q^{+}y^{+}+q^{-}y^{-}|y^{+}-y^{-}=b(\omega)-Ax;y^{+}\ge0, y^{-}\ge0\}.</math>  (4)
 
<math>P(x,b)=\{min(q^{+}y^{+}+q^{-}y^{-}|y^{+}-y^{-}=b(\omega)-Ax;y^{+}\ge0, y^{-}\ge0\}.</math>  (4)
  
−
Тут <math>q^{+},q^{-},y^{+},y^{-}</math>- m-мірні вектори.
+
Тут <math>q^{+},q^{-},y^{+},y^{-}</math>- m-мірні вектори.<br>
−
+
<font size=3> У моделях двохетапного стохастичного програмування відображаються
 +
найхарактерніші особливості планування за умов невизначеності:
 +
# ймовірнісний характер початкової інформації,
 +
# вибір попереднього плану з урахуванням його майбутнього коректування,
 +
# коректування попередньо вибраного плану по мірі уточнення інформації.
 
Будемо називати модель (1)-(3) ''найпростішою постановкою  
 
Будемо називати модель (1)-(3) ''найпростішою постановкою  
 
двохетапної задачі лінійного стохастичного програмування''.  
 
двохетапної задачі лінійного стохастичного програмування''.  
Рядок 50: Рядок 61:
  
 
<math> \Q_i(x,b_{i})=\begin{cases}
 
<math> \Q_i(x,b_{i})=\begin{cases}
−
[b_{i}-(Ax)_{i}] q^{+}_{i},b_{i}-(Ax)_{i}\geqslant 0 \\
+
[b_{i}-(Ax)_{i}] q^{+}_{i}, b_{i}-(Ax)_{i}\geqslant 0 \\
−
-[b_{i}-(Ax)_{i}] q^{-}_{i},  
+
-[b_{i}-(Ax)_{i}] q^{-}_{i},
 
b_{i}-(Ax)_{i}\le 0  
 
b_{i}-(Ax)_{i}\le 0  
 
\end{cases}</math>.  (7)
 
\end{cases}</math>.  (7)
Рядок 70: Рядок 81:
 
Введемо вектори
 
Введемо вектори
  
−
<math> \tilde {q} = \frac{1}{2} (q^{+} + q^{-}),  \tilde {c} = c - 1/2 (q^{+} - q^{-}) A. </math>
+
<math> \tilde {q} = \frac{1}{2} (q^{+} + q^{-}),  \tilde {c} = c - \frac{1}{2} (q^{+} - q^{-}) A. </math>
  
 
Маємо
 
Маємо
Рядок 80: Рядок 91:
 
<math> (y^{+} - y^{-}) = b - Ax. </math>     
 
<math> (y^{+} - y^{-}) = b - Ax. </math>     
  
−
Виключаючи тривіальний практично нецікавий випадок, можна вважати що <math>  q^{+}>0,  q^{-}>0. </math> Тому на оптимальному плані <math> (y^{+} + y^{-}) = |b - Ax|.  </math> Із (11) видно, що при цьому розв'язанні задачі задовольняє рівнянню  
+
Виключаючи тривіальний практично нецікавий випадок, можна вважати що <math>  q^{+}>0,  q^{-}>0. </math> Тому на оптимальному плані <math> y^{+} y^{-} = 0 </math> і <math> y^{+} + y^{-} = |b - Ax|.  </math> Із (11) видно, що при цьому розв'язанні задачі задовольняє рівнянню  
  
 +
<math> \tilde {c} x + \tilde {q} M |b - Ax| + \frac{1}{2} (q^{+} - q^{-}) Mb = cx + M(q^{+} y^{+} + q^{-} y^{-}). </math>
  
 +
Тому еквівалентна детермінована задача дя двохетапної задачі в найпростішій постановці може бути переписана у вигляді
 +
 +
<font size=3><math>\tilde {c}x+\tilde {q}M|b - Ax|\to min,</math>  (12)<font>
 +
 +
<font size=3><math>A^{(1)}x=b^{(1)},</math>  (13) <font>
 +
 +
<font size=3><math>x\ge0.</math>  (14) <font>
 +
 +
Наведемо ще одну форму записи цієї ж завдання. Введемо позначення
 +
 +
<math> Ax=\varkappa</math>,  <math>(Ax)_{i} = \varkappa_{i}, </math>
 +
 +
<math> Q(\varkappa) = Q(x) = M {\sum\limits_{i=1}^m \Q_{i}(x,b_{i})}={\sum\limits_{i=1}^m M \Q_{i}(\varkappa_{i},b_{i})}= {\sum\limits_{i=1}^m \Q_{i}(\varkappa_{i})}. </math>
 +
 +
Функції <math> Q_{i}(\varkappa_{i},b_{i}), </math> так як і <math> Q_{i}(\varkappa_{i}), </math> - опуклі функції по <math> \varkappa_{i}. </math>
 +
 +
Двохетапна стохастична задача в найпростішій постановці зведена, таким чином, до наступної задачі опуклого сепарабельного програмування:
 +
 +
<font size=3><math> cx+{\sum\limits_{i=1}^m \Q_{i}(\varkappa_{i})}\to min,</math>  (15)<font>
 +
 +
<font size=3><math>A^{(1)}x=b^{(1)},</math>  (16) <font>
 +
 +
<font size=3><math>Ax=\varkappa,</math>  (17) <font>
 +
 +
<font size=3><math>x\ge0.</math>  (18) <font>
 +
 +
Вивчимо функції <math> Q_{i}(\varkappa_{i}). </math>
 +
 +
Позначимо через <math>\delta_{i} </math> і <math>\gamma_{i} </math> відповідно точну верхню і точну нижню грані випадкової величини <math> b_{i}(\omega), </math> через <math> \overline{b}=(\overline{b}_{1},...,\overline{b}_{m})=Mb </math> - математичне сподівання вектора обмежене і через <math> F_{i} b_{i} </math> - функцію розподілу компонентів <math> b_{i}(\omega). </math>
 +
 +
Розділимо множину значень <math> \varkappa_{i} </math> на три області:  <math> (-\infty, \gamma_{i}), [\gamma_{i}, \delta_{i}], (\delta_{i}, \infty). </math> Якщо <math> b_{i}(\omega) </math> не має нижньої (відповідно верхньої) грані, покладем <math> \gamma_{i}=-\infty </math> (відповідно <math> \delta_{i}=\infty). </math>
 +
 +
Обчислимо значення <math> Q_{i}(\varkappa_{i}) </math> в кожній із цих областей. Маємо
 +
 +
 +
<math> Q_{i}(\varkappa_{i})= MQ_{i}(\varkappa_{i}, b_{i})=-q^{-}_{i}\int \limits_{b_{i}\leqslant\varkappa_{i}} (b_{i}-\varkappa_{i})dF_{i}(b_{i})+q^{+}_{i}\int \limits_{b_{i}>\varkappa_{i}} (b_{i}-\varkappa_{i})dF_{i}(b_{i})=q^{+}_{i}\int \limits_{\Omega}[b_{i}(\omega)-\varkappa_{i}]dp-(q^{+}_{i}+q^{-}_{i})\int \limits_{b_{i}\leqslant\varkappa_{i}} (b_{i}-\varkappa_{i})dF_{i}(b_{i}), </math>
 +
 +
або
 +
 +
<math> Q_{i}(\varkappa_{i})=q^{+}_{i}\overline{b}_{i}-q^{+}_{i}\varkappa_{i}-(q^{+}_{i}+q^{-}_{i})\int \limits_{b_{i}\leqslant\varkappa_{i}} (b_{i}-\varkappa_{i})dF_{i}(b_{i}). </math>  (19)
 +
 +
Розглянемо три випадки.
 +
 +
1. Нехай <math> \varkappa_{i}<\gamma_{i}. </math> В цьому випадку
 +
 +
<math> \{b_{i}|b_{i}\leqslant\varkappa_{i}\}\neq\varnothing. </math>
 +
 +
Із (19) отримаємо
 +
 +
<math> Q_{i}(\varkappa_{i})=q^{+}_{i}\overline{b}_{i}-q^{+}_{i}\varkappa_{i}. </math>
 +
 +
Тобто функція <math> Q_{i}(\varkappa_{i}) </math> лінійна на проміжку <math> (-\infty, \gamma_{i}). </math>
 +
 +
2. <math> \varkappa_{i}\in [\gamma_{i},\delta_{i}].</math> В цьому випадку
 +
 +
<math> \{b_{i}|b_{i}\leqslant\varkappa_{i}\}=\{b_{i}|\gamma_{i}\leqslant b_{i} \leqslant \varkappa_{i}\}. </math>
 +
 +
Функція <math> Q_{i}(\varkappa_{i}) </math> на цьому відрізку виражається співвідношенням
 +
 +
<math> Q_{i}(\varkappa_{i})=q^{+}_{i}\overline{b}_{i}-q^{+}_{i}\varkappa_{i}-(q^{+}_{i}+q^{-}_{i})\int \limits^{\varkappa_{i}}_{\gamma_{i}}(b_{i}-\varkappa_{i})dF_{i}(b_{i}). </math>
 +
 +
Конкретний вид опуклої функції <math> Q_{i}(\varkappa_{i}) </math> залежить від функції розподілу <math> F_{i}(b_{i}). </math>
 +
 +
3. <math> \varkappa_{i}>\delta_{i}. </math> В цьому випадку множина <math> \{b_{i}|b_{i}\leqslant\varkappa_{i}\} </math> збігається з усією областю змінної <math> b_{i}(\omega) </math> і
 +
 +
<math> \int \limits_{b_{i}\leqslant\varkappa_{i}} [b_{i}(\omega)-\varkappa_{i}]dF_{i}(b_{i})=\int \limits_{\Omega}[b_{i}(\omega)-\varkappa_{i}]dp=\overline{b}_{i}-\varkappa_{i}. </math> 
 +
 +
Отже, функція <math> Q_{i}(\varkappa_{i}) </math> на проміжку <math> (\delta_{i}, \infty) </math> лінійна
 +
 +
<math> Q_{i}(\varkappa_{i})=-q^{-}_{i}\overline{b}_{i}+q^{-}_{i}\varkappa_{i}. </math>
 +
 +
Опукла функція <math> Q_{i}(\varkappa_{i}) </math> неперервна на всій числовій прямій.
 +
 +
Характер функції <math> Q_{i}(\varkappa_{i}) </math> дозволяє спростити запис задачі (15)-(18) і зробити її більш зручною для якісного і кількісного аналізу.
 +
 +
Введемо змінні <math> \varkappa^{(1)}_{i}, \varkappa^{(2)}_{i}, \varkappa^{(3)}_{i}, </math> задовольняють умовам
 +
 +
<math> \begin{cases}
 +
\varkappa^{(1)}_{i}-\varkappa^{(2)}_{i}-\varkappa^{(3)}_{i}=\overline{b}_{i}-\varkappa_{i}, \\
 +
\varkappa^{(1)}_{i}\geqslant\overline{b}_{i}-\gamma_{i}\geqslant0, \\
 +
\delta_{i}-\gamma_{i}\geqslant\varkappa^{(2)}_{i}\geqslant0,  \\
 +
\varkappa^{(3)}_{i}\geqslant0
 +
\end{cases}</math>.    (20)
 +
 +
Для стислості обмежимося випадком <math> \gamma_{i}>-\infty. </math>
 +
 +
Враховуючи отримані вище вираження для <math> Q_{i}(\varkappa_{i}) </math> на різних ділянках, можна переписати завдачу (15)-(18)  в наступному вигляді:
 +
 +
<math> {\sum\limits_{j=1}^n c_{j}x_{j}+\sum\limits_{i=1}^m (q^{+}_{i}\varkappa^{(1)}_{i}+q^{-}_{i}\varkappa^{(3)}_{i})+\sum\limits_{i=1}^m Q_{i}(\varkappa^{(2)}_{i}) \to min},</math>  (21)
 +
 +
<math>{\sum\limits_{j=1}^n a^{(1)}_{ij}x_{j}=b^{(1)}_{i}}, </math>                      <math> i=1,...,m_{1}, </math>    (22)
 +
 +
<math>{\sum\limits_{j=1}^n a_{ij}x_{j}+\varkappa^{(1)}_{i}-\varkappa^{(2)}_{i}-\varkappa^{(3)}_{i}=\overline{b}_{i}}, </math>    <math> i=1,...,m, </math>    (23)
 +
 +
<math> \varkappa^{(1)}_{i}\geqslant \overline{b}_{i}-\gamma_{i},  \delta_{i}-\gamma_{i}\geqslant\varkappa^{(2)}_{i}\geqslant0,    \varkappa^{(3)}_{i}\geqslant0 , </math>    <math> i=1,...,m, </math>    (24)
 +
 +
<math> x_{j}\geqslant0,  j=1,...,n, </math>    (25)
 +
 +
де
 +
 +
<math> Q_{i}(\varkappa^{(2)}_{i})=-q^{+}_{i}\varkappa^{(2)}_{i}+(q^{+}_{i}+q^{-}_{i})\int \limits^{\varkappa^{(2)}_{i}}_{0}(\varkappa^{(2)}_{i}-b_{i})dF_{i}(b_{i}+\gamma_{i}). </math>          (26)
 +
 +
Перехід до нових змінних збільшив число змінних і обмежень, але спростив структуру задачі.
 +
 +
Еквівалентна детермінована задача для двохетапної стохастичної задачі в найпростішій постановці у формі (21)-(25) лінійна щодо змінних <math> x_{j},\varkappa^{(1)}_{i},\varkappa^{(3)}_{i}</math> і опукла і сепарабельна по змінним <math>\varkappa^{(2)}_{i}.</math>
 +
 +
Задачу можна також подати у векторно-матричній формі:<br>
 +
<i> A(ω)X + D(ω)Y + b(ω) ≥ 0  ; </i> (27)<br>
 +
<i>  X ≥ 0 , Y ≥ 0 . </i> (28)<br>
 +
Попередній план Х вибирається до спостережень над ω. Коли ω стає відомим, то
 +
визначають план-корекцію Y у такий спосіб, щоб виконувались співвідношення (27),
 +
(28). При цьому ефект від плану-корекції дорівнює:
  
  
 
==Список використаних джерел==
 
==Список використаних джерел==
 
1. Юдин Д. Б. Математические методы управления в условиях неполной информации. / Юдин Д. Б. М: «Сов. радио», 1974. – 400 с.
 
1. Юдин Д. Б. Математические методы управления в условиях неполной информации. / Юдин Д. Б. М: «Сов. радио», 1974. – 400 с.
 +
 +
Доповнювала: [[Користувач:Поветкіна Олена|Повєткіна Олена]]
 +
 +
Доповнювала: [[Користувач:Мамонтова Галина|Мамонтова Галина]]

Поточна версія на 08:24, 12 квітня 2021

Недоліком розглянутих одноетапних задач стохастичного програмування є те, що в них лише фіксується факт можливих відхилень значень випадкових параметрів і усереднені розв’язки вибирають за умови, що відхилення значень від середнього рівня в будь-який бік небажане (зменшується величина дисперсії параметрів у обмеженнях або цільова функція — дисперсія мінімізується). У більшості реальних економічних задач має значення не лише величина відхилення, але також і його напрямок. Двохетапні задачі стохастичного програмування позбавлені зазначеного недоліку.
Розглянемо, двоетапну задачу, в якій випадковим є тільки вектор обмежень, а матриця компенсації В (після відповідної перестановки рядків і стовпців) може бути представлена ​​у вигляді В = (Е, -Е), де Е - одинична матриця розміру mxm. Розіб'ємо вектори у і q на дві частини, відповідні підматриці Е, -Е матриці B. Задача в цьому випадку приймає вид

Неможливо розібрати вираз (невідома помилка): Q(x)=cx+MP(x,b)\to min, 

 (1)

Неможливо розібрати вираз (невідома помилка): A^{(1)}x=b^{(1)}, 

  (2)

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

  (3)

де

Неможливо розібрати вираз (невідома помилка): P(x,b)=\{min(q^{+}y^{+}+q^{-}y^{-}|y^{+}-y^{-}=b(\omega)-Ax;y^{+}\ge0, y^{-}\ge0\}. 

 (4)

Тут Неможливо розібрати вираз (невідома помилка): q^{+},q^{-},y^{+},y^{-} - m-мірні вектори.
У моделях двохетапного стохастичного програмування відображаються найхарактерніші особливості планування за умов невизначеності:

  1. ймовірнісний характер початкової інформації,
  2. вибір попереднього плану з урахуванням його майбутнього коректування,
  3. коректування попередньо вибраного плану по мірі уточнення інформації.

Будемо називати модель (1)-(3) найпростішою постановкою двохетапної задачі лінійного стохастичного програмування. Очевидно, що завдання (4) другого етапу має плани при довільної реалізації Неможливо розібрати вираз (невідома помилка): (\omega) 

і будь-якому вибраному попередньому плані х.

Тобто Неможливо розібрати вираз (невідома помилка): K_{2}=R^{n} 

і Неможливо розібрати вираз (невідома помилка):  K=K_{1}=\{x|A^{(1)}x=b^{(1)}, x\ge0\}

.

Необхідна і достатня умова існування кінцевого розв'язку задачі другого етапу при найпростішій постановці двохетапної задачі набуває досить простий вигляд. У загальному випадку ця умова має вигляд

Неможливо розібрати вираз (невідома помилка): \{z|zB\le q\}\neq\varnothing .

У розглянутому випадку

Неможливо розібрати вираз (невідома помилка): \{z|zB\le q\}=\{z|z(E, -E)\le q\}=\{z|-q^{-}\le z\le q^{+}\} \neq\varnothing .

Таким чином, для розв'язання задачі другого етапу в найпростішій постановці двохетапної задачі необхідно і достатньо, щоб Неможливо розібрати вираз (невідома помилка): -q^{-}\le q^{+} 

тобто

Неможливо розібрати вираз (невідома помилка): q^{+}+q^{-}\ge 0. 

 (5)

У практичних задачах умова (5) завжди виконується, оскільки штрафи Неможливо розібрати вираз (невідома помилка): -q^{-} 

і  Неможливо розібрати вираз (невідома помилка): q^{+}

, як правило, невід'ємні.

Задача, двоїста до задачі (4) другого етапу, має вигляд

Неможливо розібрати вираз (невідома помилка): Q(x,b)=\{max z(b-Ax)|-q^{-}\le z\le q^{+} \} . (6)

Задача (6) легко вирішується. Розв'язок цієї задачі записується формулою

Неможливо розібрати вираз (невідома помилка): Q(x,b)={\sum\limits_{i=1}^m \Q_{i}(x,b_{i})},


де

Неможливо розібрати вираз (невідома помилка): \Q_i(x,b_{i})=\begin{cases} [b_{i}-(Ax)_{i}] q^{+}_{i}, b_{i}-(Ax)_{i}\geqslant 0 \\ -[b_{i}-(Ax)_{i}] q^{-}_{i}, b_{i}-(Ax)_{i}\le 0 \end{cases} . (7)

Тому еквівалентна опукла задача для двохетапної стохастичної задачі у найпростішій постановці має вигляд

Неможливо розібрати вираз (невідома помилка): cx+M{\sum\limits_{i=1}^m \Q_{i}(x,b_{i})\to min}, 

 (8)

Неможливо розібрати вираз (невідома помилка): A^{(1)}x=b^{(1)}, 

  (9)

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

  (10)

де Неможливо розібрати вираз (невідома помилка): Q_{i}(x,b_{i}) 

визначаються з співвідношень (7).

Розглянемо кілька інших форм запису еквівалентної детермінованої задачі для найпростішої постановки двохетапної задачі. При різних умовах різні форми запису можуть виявитися більш зручними для аналізу.

Введемо вектори

Неможливо розібрати вираз (невідома помилка): \tilde {q} = \frac{1}{2} (q^{+} + q^{-}), \tilde {c} = c - \frac{1}{2} (q^{+} - q^{-}) A.


Маємо

Неможливо розібрати вираз (невідома помилка): \tilde {c} x + \tilde {q} M (q^{+} + q^{-}) + \frac{1}{2} (q^{+} - q^{-}) Mb = cx + \frac{1}{2} (q^{+} - q^{-}) M [(b - Ax) - (y^{+} - y^{-})] + M (q^{+} y^{+} - q^{-} y^{-}). 

    (11)

На планах двохетапної задачі

Неможливо розібрати вираз (невідома помилка): (y^{+} - y^{-}) = b - Ax.


Виключаючи тривіальний практично нецікавий випадок, можна вважати що Неможливо розібрати вираз (невідома помилка): q^{+}>0, q^{-}>0. 

Тому на оптимальному плані Неможливо розібрати вираз (невідома помилка):  y^{+} y^{-} = 0 
і Неможливо розібрати вираз (невідома помилка):  y^{+} + y^{-} = |b - Ax|.  
Із (11) видно, що при цьому розв'язанні задачі задовольняє рівнянню

Неможливо розібрати вираз (невідома помилка): \tilde {c} x + \tilde {q} M |b - Ax| + \frac{1}{2} (q^{+} - q^{-}) Mb = cx + M(q^{+} y^{+} + q^{-} y^{-}).


Тому еквівалентна детермінована задача дя двохетапної задачі в найпростішій постановці може бути переписана у вигляді

Неможливо розібрати вираз (невідома помилка): \tilde {c}x+\tilde {q}M|b - Ax|\to min, 

 (12)

Неможливо розібрати вираз (невідома помилка): A^{(1)}x=b^{(1)}, 

  (13)

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

  (14)

Наведемо ще одну форму записи цієї ж завдання. Введемо позначення

Неможливо розібрати вираз (невідома помилка): Ax=\varkappa , Неможливо розібрати вираз (невідома помилка): (Ax)_{i} = \varkappa_{i},


Неможливо розібрати вираз (невідома помилка): Q(\varkappa) = Q(x) = M {\sum\limits_{i=1}^m \Q_{i}(x,b_{i})}={\sum\limits_{i=1}^m M \Q_{i}(\varkappa_{i},b_{i})}= {\sum\limits_{i=1}^m \Q_{i}(\varkappa_{i})}.


Функції Неможливо розібрати вираз (невідома помилка): Q_{i}(\varkappa_{i},b_{i}), 

так як і Неможливо розібрати вираз (невідома помилка):  Q_{i}(\varkappa_{i}), 
- опуклі функції по Неможливо розібрати вираз (невідома помилка):  \varkappa_{i}.


Двохетапна стохастична задача в найпростішій постановці зведена, таким чином, до наступної задачі опуклого сепарабельного програмування:

Неможливо розібрати вираз (невідома помилка): cx+{\sum\limits_{i=1}^m \Q_{i}(\varkappa_{i})}\to min, 

 (15)

Неможливо розібрати вираз (невідома помилка): A^{(1)}x=b^{(1)}, 

  (16)

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

  (17)

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

  (18)

Вивчимо функції Неможливо розібрати вираз (невідома помилка): Q_{i}(\varkappa_{i}).


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

і Неможливо розібрати вираз (невідома помилка): \gamma_{i} 
відповідно точну верхню і точну нижню грані випадкової величини Неможливо розібрати вираз (невідома помилка):  b_{i}(\omega), 
через Неможливо розібрати вираз (невідома помилка):  \overline{b}=(\overline{b}_{1},...,\overline{b}_{m})=Mb 
- математичне сподівання вектора обмежене і через Неможливо розібрати вираз (невідома помилка):  F_{i} b_{i} 
- функцію розподілу компонентів Неможливо розібрати вираз (невідома помилка):  b_{i}(\omega).


Розділимо множину значень Неможливо розібрати вираз (невідома помилка): \varkappa_{i} 

на три області:  Неможливо розібрати вираз (невідома помилка):  (-\infty, \gamma_{i}), [\gamma_{i}, \delta_{i}], (\delta_{i}, \infty). 
Якщо Неможливо розібрати вираз (невідома помилка):  b_{i}(\omega) 
не має нижньої (відповідно верхньої) грані, покладем Неможливо розібрати вираз (невідома помилка):  \gamma_{i}=-\infty 
(відповідно Неможливо розібрати вираз (невідома помилка):  \delta_{i}=\infty).


Обчислимо значення Неможливо розібрати вираз (невідома помилка): Q_{i}(\varkappa_{i}) 

в кожній із цих областей. Маємо


Неможливо розібрати вираз (невідома помилка): Q_{i}(\varkappa_{i})= MQ_{i}(\varkappa_{i}, b_{i})=-q^{-}_{i}\int \limits_{b_{i}\leqslant\varkappa_{i}} (b_{i}-\varkappa_{i})dF_{i}(b_{i})+q^{+}_{i}\int \limits_{b_{i}>\varkappa_{i}} (b_{i}-\varkappa_{i})dF_{i}(b_{i})=q^{+}_{i}\int \limits_{\Omega}[b_{i}(\omega)-\varkappa_{i}]dp-(q^{+}_{i}+q^{-}_{i})\int \limits_{b_{i}\leqslant\varkappa_{i}} (b_{i}-\varkappa_{i})dF_{i}(b_{i}),


або

Неможливо розібрати вираз (невідома помилка): Q_{i}(\varkappa_{i})=q^{+}_{i}\overline{b}_{i}-q^{+}_{i}\varkappa_{i}-(q^{+}_{i}+q^{-}_{i})\int \limits_{b_{i}\leqslant\varkappa_{i}} (b_{i}-\varkappa_{i})dF_{i}(b_{i}). 

  (19)

Розглянемо три випадки.

1. Нехай Неможливо розібрати вираз (невідома помилка): \varkappa_{i}<\gamma_{i}. 

В цьому випадку

Неможливо розібрати вираз (невідома помилка): \{b_{i}|b_{i}\leqslant\varkappa_{i}\}\neq\varnothing.


Із (19) отримаємо

Неможливо розібрати вираз (невідома помилка): Q_{i}(\varkappa_{i})=q^{+}_{i}\overline{b}_{i}-q^{+}_{i}\varkappa_{i}.


Тобто функція Неможливо розібрати вираз (невідома помилка): Q_{i}(\varkappa_{i}) 

лінійна на проміжку Неможливо розібрати вираз (невідома помилка):  (-\infty, \gamma_{i}).


2. Неможливо розібрати вираз (невідома помилка): \varkappa_{i}\in [\gamma_{i},\delta_{i}]. 

В цьому випадку

Неможливо розібрати вираз (невідома помилка): \{b_{i}|b_{i}\leqslant\varkappa_{i}\}=\{b_{i}|\gamma_{i}\leqslant b_{i} \leqslant \varkappa_{i}\}.


Функція Неможливо розібрати вираз (невідома помилка): Q_{i}(\varkappa_{i}) 

на цьому відрізку виражається співвідношенням

Неможливо розібрати вираз (невідома помилка): Q_{i}(\varkappa_{i})=q^{+}_{i}\overline{b}_{i}-q^{+}_{i}\varkappa_{i}-(q^{+}_{i}+q^{-}_{i})\int \limits^{\varkappa_{i}}_{\gamma_{i}}(b_{i}-\varkappa_{i})dF_{i}(b_{i}).


Конкретний вид опуклої функції Неможливо розібрати вираз (невідома помилка): Q_{i}(\varkappa_{i}) 

залежить від функції розподілу Неможливо розібрати вираз (невідома помилка):  F_{i}(b_{i}).


3. Неможливо розібрати вираз (невідома помилка): \varkappa_{i}>\delta_{i}. 

В цьому випадку множина Неможливо розібрати вираз (невідома помилка):  \{b_{i}|b_{i}\leqslant\varkappa_{i}\} 
збігається з усією областю змінної Неможливо розібрати вираз (невідома помилка):  b_{i}(\omega) 
і

Неможливо розібрати вираз (невідома помилка): \int \limits_{b_{i}\leqslant\varkappa_{i}} [b_{i}(\omega)-\varkappa_{i}]dF_{i}(b_{i})=\int \limits_{\Omega}[b_{i}(\omega)-\varkappa_{i}]dp=\overline{b}_{i}-\varkappa_{i}.


Отже, функція Неможливо розібрати вираз (невідома помилка): Q_{i}(\varkappa_{i}) 

на проміжку Неможливо розібрати вираз (невідома помилка):  (\delta_{i}, \infty) 
лінійна

Неможливо розібрати вираз (невідома помилка): Q_{i}(\varkappa_{i})=-q^{-}_{i}\overline{b}_{i}+q^{-}_{i}\varkappa_{i}.


Опукла функція Неможливо розібрати вираз (невідома помилка): Q_{i}(\varkappa_{i}) 

неперервна на всій числовій прямій.

Характер функції Неможливо розібрати вираз (невідома помилка): Q_{i}(\varkappa_{i}) 

дозволяє спростити запис задачі (15)-(18) і зробити її більш зручною для якісного і кількісного аналізу.

Введемо змінні Неможливо розібрати вираз (невідома помилка): \varkappa^{(1)}_{i}, \varkappa^{(2)}_{i}, \varkappa^{(3)}_{i}, 

задовольняють умовам

Неможливо розібрати вираз (невідома помилка): \begin{cases} \varkappa^{(1)}_{i}-\varkappa^{(2)}_{i}-\varkappa^{(3)}_{i}=\overline{b}_{i}-\varkappa_{i}, \\ \varkappa^{(1)}_{i}\geqslant\overline{b}_{i}-\gamma_{i}\geqslant0, \\ \delta_{i}-\gamma_{i}\geqslant\varkappa^{(2)}_{i}\geqslant0, \\ \varkappa^{(3)}_{i}\geqslant0 \end{cases} . (20)

Для стислості обмежимося випадком Неможливо розібрати вираз (невідома помилка): \gamma_{i}>-\infty.


Враховуючи отримані вище вираження для Неможливо розібрати вираз (невідома помилка): Q_{i}(\varkappa_{i}) 

на різних ділянках, можна переписати завдачу (15)-(18)  в наступному вигляді:

Неможливо розібрати вираз (невідома помилка): {\sum\limits_{j=1}^n c_{j}x_{j}+\sum\limits_{i=1}^m (q^{+}_{i}\varkappa^{(1)}_{i}+q^{-}_{i}\varkappa^{(3)}_{i})+\sum\limits_{i=1}^m Q_{i}(\varkappa^{(2)}_{i}) \to min}, 

 (21)

Неможливо розібрати вираз (невідома помилка): {\sum\limits_{j=1}^n a^{(1)}_{ij}x_{j}=b^{(1)}_{i}}, 

                      Неможливо розібрати вираз (невідома помилка):  i=1,...,m_{1}, 
   (22)

Неможливо розібрати вираз (невідома помилка): {\sum\limits_{j=1}^n a_{ij}x_{j}+\varkappa^{(1)}_{i}-\varkappa^{(2)}_{i}-\varkappa^{(3)}_{i}=\overline{b}_{i}}, 

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

Неможливо розібрати вираз (невідома помилка): \varkappa^{(1)}_{i}\geqslant \overline{b}_{i}-\gamma_{i}, \delta_{i}-\gamma_{i}\geqslant\varkappa^{(2)}_{i}\geqslant0, \varkappa^{(3)}_{i}\geqslant0 , 

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

Неможливо розібрати вираз (невідома помилка): x_{j}\geqslant0, j=1,...,n, 

   (25)

де

Неможливо розібрати вираз (невідома помилка): Q_{i}(\varkappa^{(2)}_{i})=-q^{+}_{i}\varkappa^{(2)}_{i}+(q^{+}_{i}+q^{-}_{i})\int \limits^{\varkappa^{(2)}_{i}}_{0}(\varkappa^{(2)}_{i}-b_{i})dF_{i}(b_{i}+\gamma_{i}). 

         (26)

Перехід до нових змінних збільшив число змінних і обмежень, але спростив структуру задачі.

Еквівалентна детермінована задача для двохетапної стохастичної задачі в найпростішій постановці у формі (21)-(25) лінійна щодо змінних Неможливо розібрати вираз (невідома помилка): x_{j},\varkappa^{(1)}_{i},\varkappa^{(3)}_{i} 

і опукла і сепарабельна по змінним Неможливо розібрати вираз (невідома помилка): \varkappa^{(2)}_{i}.


Задачу можна також подати у векторно-матричній формі:
A(ω)X + D(ω)Y + b(ω) ≥ 0  ; (27)
X ≥ 0 , Y ≥ 0 . (28)
Попередній план Х вибирається до спостережень над ω. Коли ω стає відомим, то визначають план-корекцію Y у такий спосіб, щоб виконувались співвідношення (27), (28). При цьому ефект від плану-корекції дорівнює:


Список використаних джерел

1. Юдин Д. Б. Математические методы управления в условиях неполной информации. / Юдин Д. Б. М: «Сов. радио», 1974. – 400 с.

Доповнювала: Повєткіна Олена

Доповнювала: Мамонтова Галина

Отримано з https://wiki.cusu.edu.ua/index.php?title=Найпростіша_постановка_двохетапної_задачі_СП.&oldid=373808