Відмінності між версіями «Класифікація задач стохастичного програмування: за виглядом цільової функції та за умовами обмеження.»

Матеріал з Вікі ЦДУ
Перейти до: навігація, пошук
 
(не показано 33 проміжні версії 3 учасників)
Рядок 1: Рядок 1:
В якості цільової функції задачі стохастичного лінійного програмування з імовірнісними обмеженнями зазвичай приниймають такі функціонали, як математичне сподівання або дисперсію лінійної форми або ймовірність перевищення лінійною формою деякого фіксованого порога.
+
<font size=3> В якості цільової функції задачі стохастичного лінійного програмування з імовірнісними обмеженнями зазвичай приймають такі функціонали, як математичне сподівання або дисперсію лінійної форми або ймовірність перевищення лінійною формою деякого фіксованого порога. </font>
  
*за виглядом цільової функції
+
*<font size=3>'''''за виглядом цільової функції''''' </font>
1.Задачі з цільовою функцією <math> \overline{cx}=M(cx) </math> називають М- моделями
+
<font size=3> 1. Задачі з цільовою функцією <math> \overline{cx}=M(cx) </math> називають <font size=3>'''М- моделями'''. </font> </font>
  
2.Задачі, в яких потрібно мінімізувати дисперсію лінійної форми <math>\ M({cx-\overline{cx}})^2 </math>, називають  V-моделями
+
<font size=3> 2. Задачі, в яких потрібно мінімізувати дисперсію лінійної форми <math>\ M \left \{cx-\overline{cx} \right \}^2 </math>, називають  <font size=3>'''V-моделями'''. </font>  </font>
  
3.Стохастичні задачі, в яких оптимізується ймовірність перевищення лінійної формою деякого порога  <math>\ P({cx \geq c^0 x^0}) </math>, називають Р-моделями
+
<font size=3> До V –моделей відносять також стохастичні задачі з показниками якості розв’язання <math>\ M \left \{cx-c^0 x^0 \right \} </math>, де , взагалі кажучи, <math> {c^0 x^0} \ne \overline{cx} </math>.  </font>
  
У цю ж групу моделей включають задачі, де потрібно мінімізувати поріг <math>\ {k} </math>, який не повинен бути перевищений лінійною формою <math>\ {cx} </math> із заданою ймовірністю <math>\ {\alpha} </math>:
+
<font size=3> 3. Стохастичні задачі, в яких оптимізується ймовірність перевищення лінійної формою деякого порога  <math>\ P \left \{cx \geq c^0 x^0  \right \} </math>, називають <font size=3>'''P-моделями'''. </font>  </font>
 +
 
 +
<font size=3> У цю ж групу моделей включають задачі, де потрібно мінімізувати поріг <math>\ {k} </math>, який не повинен бути перевищений лінійною формою <math>\ {cx} </math> із заданою ймовірністю <math>\ {\alpha} </math>: </font>
 
<math>\ {k} \rightarrow min,P({cx} \le {k})={\alpha} </math>.
 
<math>\ {k} \rightarrow min,P({cx} \le {k})={\alpha} </math>.
  
При формалізації стохастичної задачі можна привести у відповідність всій області визначення цільової функції одне або декілька імовірнісних обмежень. Умови задачі (в лінійному випадку) можуть бути представлені у вигляді одного з наступних записів:
+
<font size=3> При формалізації стохастичної задачі можна привести у відповідність всій області визначення цільової функції одне або декілька імовірнісних обмежень. Умови задачі (в лінійному випадку) можуть бути представлені у вигляді одного з наступних записів: </font>
 +
 
 +
*<font size=3>'''''за умовами обмеження''''' </font>
 +
<math>\ a) </math> <math>\ P \left \{ \sum^{n}_{j=1} a_{ij}x_j \geq b_{i} \right \} \geq {\alpha}_{i}, 0 \le {\alpha}_{i} \le 1, i=1,...,m </math>,
 +
 
 +
<math>\ b) </math> <math>\ P \left \{ Ax \geq {b} \right \} \geq {\alpha}, 0 \le {\alpha} \le 1 </math>,
 +
 
 +
<math>\ c) </math> <math>\ P \left \{ \sum^{n}_{j=1} a_{i_kj}x_j \geq b_{i_k}; i_{k}\subset{I_{k}} \right \} \geq {\alpha}_{k}, 0 \le {\alpha}_{k} \le 1, k=1,...,s, \bigcup\limits_{k=1}^s I_k= \left \{ 1,...,m \right \} </math>.
 +
 
 +
<font size=3> Будемо називати задачі з імовірнісними обмеженнями, заданими у формі '''(a)''', <font size=3>'''''задачами з порядковим ймовірносними обмеженнями'''''  </font>, а задачі з обмеженнями у формі '''(b)''' - <font size=3>'''''задачами з імовірністним обмеженням'''''.  </font>  </font>
 +
 
 +
<font size=3> У задачі, в якій обмеження записані у формі '''(b)''', всі випадкові параметри умов можуть бути корельовані. Однак в цьому записі не враховується порівняльна важливість окремих обмежень. У записі '''(а)''' можуть бути враховані тільки стохастичні зв'язку випадкових параметрів умов задачі, що належать одному рядку. Однак при цьому запис '''(а)''' дозволяє відобразити різне відношення до нев'язок, які виникають у різних обмеженнях задачі. У записі '''(а)''' виконання кожного з обмежень - рядків може бути забезпечено різними (для кожного рядка) множинами реалізацій явищ природи <math>\ {\omega} </math>, які визначаються випадковими параметрами умов задачі <math>\ a_{ij} (\omega) </math> і <math>\ b_i (\omega) </math>. Множина <math>\ {\omega} </math>, для якої одночасно виконуються всі обмеження '''(а)''', може виявитися порожньою. Аналогічні зауваження можуть бути зроблені з приводу запису '''(с)'''.  </font>
 +
 
 +
<font size=3> Вибір значень ймовірностей <math>\ {\alpha},{\alpha}_{i},{\alpha}_{k} </math>, є '''''предметом самостійної задачі'''''. Зокрема, ці величини можуть бути обрані в результаті попереднього дослідження і зіставлення витрат, пов'язаних із збільшенням параметрів <math>\ {\alpha},{\alpha}_{i},{\alpha}_{k} </math> і показника якості розв’язання вихідної стохастичної задачі що досягається за рахунок цього ефекту при оптимізації.  </font>
 +
 
 +
<font size=3> У кожному окремому випадку тільки змістовна інтерпретація умов задачі дозволяє вибрати характер розв’язання, вид цільової функції і спосіб розчленовування умов, які найкращим чином відображають істотні аспекти постановки задачі. Нехай, '''наприклад''', умови задачі обмежують вибір параметрів плану виробництва (інтенсивності використання різних технологічних способів), виходячи з вимоги забезпечити з певною ймовірністю задоволення випадкового попиту <math>\ b_{i}</math> на i-й продукт. Запис умов у формі '''(b)''' доцільна в тому випадку, коли один і той же споживач багаторазово замовляє всі <math>\ {m} </math> видів вироблених продуктів. Запис умов у формі '''(а)''' природна в тих випадках, коли різні продукти замовляються різними споживачами. Аналогічним чином визначається область застосування запису '''(с)''' , що включає як крайні окремі випадки записи '''(а)''' і '''(b)'''. У загальному випадку, коли немає необхідності обмежуватися задачами лінійного стохастичного  програмування, імовірнісні обмеження записуються у вигляді  </font>
 +
<math>\ P \left \{ x \in G_{i} (\omega)  \right \} \geq {\alpha}_{i} </math>,
 +
 
 +
<font size=3> де <math>\ G_{i} (\omega) </math>-деяка випадкова область, що задається системою рівностей і нерівностей або будь-яким іншим конструктивним чином [1, c. 64].  </font>
 +
 
 +
==Список використаних джерел==
 +
1. Юдин Д. Б. Математические методы управления в условиях неполной информации. / Юдин Д. Б. М: «Сов. радио», 1974. – 400 с.
  
*за умовами обмеження
+
Виконала: [[Користувач:Самойленко Таня|Самойленко Тетяна ]]
a).<math>\ P \left \{ \sum^{n}_{j=1} a_{ij}x_j \geq b_{i} \right \} \geq {\alpha}_{i}, 0 \le {\alpha}_{i} \le 1, i=1,...,m </math>.
+
  
b).<math>\ P \left \{ \sum^{n}_{j=1} a_{ij}x_j \geq b_{i} \right \} \geq {\alpha}_{i}, 0 \le {\alpha}_{i} \le 1, i=1,...,m </math>.
+
Доповнювала: [[Користувач:Кухаренко Настя|Кухаренко Анастасія]]

Поточна версія на 13:16, 9 квітня 2017

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

  • за виглядом цільової функції

1. Задачі з цільовою функцією Неможливо розібрати вираз (невідома помилка): \overline{cx}=M(cx)

називають М- моделями.  

2. Задачі, в яких потрібно мінімізувати дисперсію лінійної форми Неможливо розібрати вираз (невідома помилка): \ M \left \{cx-\overline{cx} \right \}^2 , називають V-моделями.

До V –моделей відносять також стохастичні задачі з показниками якості розв’язання Неможливо розібрати вираз (невідома помилка): \ M \left \{cx-c^0 x^0 \right \} , де , взагалі кажучи, Неможливо розібрати вираз (невідома помилка): {c^0 x^0} \ne \overline{cx} .

3. Стохастичні задачі, в яких оптимізується ймовірність перевищення лінійної формою деякого порога Неможливо розібрати вираз (невідома помилка): \ P \left \{cx \geq c^0 x^0 \right \} , називають P-моделями.

У цю ж групу моделей включають задачі, де потрібно мінімізувати поріг Неможливо розібрати вираз (невідома помилка): \ {k} , який не повинен бути перевищений лінійною формою Неможливо розібрати вираз (невідома помилка): \ {cx}

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

Неможливо розібрати вираз (невідома помилка): \ {k} \rightarrow min,P({cx} \le {k})={\alpha} .

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

  • за умовами обмеження

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

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

,

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

Неможливо розібрати вираз (невідома помилка): \ P \left \{ Ax \geq {b} \right \} \geq {\alpha}, 0 \le {\alpha} \le 1 

,

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

Неможливо розібрати вираз (невідома помилка): \ P \left \{ \sum^{n}_{j=1} a_{i_kj}x_j \geq b_{i_k}; i_{k}\subset{I_{k}} \right \} \geq {\alpha}_{k}, 0 \le {\alpha}_{k} \le 1, k=1,...,s, \bigcup\limits_{k=1}^s I_k= \left \{ 1,...,m \right \} 

.

Будемо називати задачі з імовірнісними обмеженнями, заданими у формі (a), задачами з порядковим ймовірносними обмеженнями , а задачі з обмеженнями у формі (b) - задачами з імовірністним обмеженням.

У задачі, в якій обмеження записані у формі (b), всі випадкові параметри умов можуть бути корельовані. Однак в цьому записі не враховується порівняльна важливість окремих обмежень. У записі (а) можуть бути враховані тільки стохастичні зв'язку випадкових параметрів умов задачі, що належать одному рядку. Однак при цьому запис (а) дозволяє відобразити різне відношення до нев'язок, які виникають у різних обмеженнях задачі. У записі (а) виконання кожного з обмежень - рядків може бути забезпечено різними (для кожного рядка) множинами реалізацій явищ природи Неможливо розібрати вираз (невідома помилка): \ {\omega} , які визначаються випадковими параметрами умов задачі Неможливо розібрати вираз (невідома помилка): \ a_{ij} (\omega)

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

. Множина Неможливо розібрати вираз (невідома помилка): \ {\omega} , для якої одночасно виконуються всі обмеження (а), може виявитися порожньою. Аналогічні зауваження можуть бути зроблені з приводу запису (с).

Вибір значень ймовірностей Неможливо розібрати вираз (невідома помилка): \ {\alpha},{\alpha}_{i},{\alpha}_{k} , є предметом самостійної задачі. Зокрема, ці величини можуть бути обрані в результаті попереднього дослідження і зіставлення витрат, пов'язаних із збільшенням параметрів Неможливо розібрати вираз (невідома помилка): \ {\alpha},{\alpha}_{i},{\alpha}_{k}

і показника якості розв’язання вихідної стохастичної задачі що досягається за рахунок цього ефекту при оптимізації.  

У кожному окремому випадку тільки змістовна інтерпретація умов задачі дозволяє вибрати характер розв’язання, вид цільової функції і спосіб розчленовування умов, які найкращим чином відображають істотні аспекти постановки задачі. Нехай, наприклад, умови задачі обмежують вибір параметрів плану виробництва (інтенсивності використання різних технологічних способів), виходячи з вимоги забезпечити з певною ймовірністю задоволення випадкового попиту Неможливо розібрати вираз (невідома помилка): \ b_{i}

на i-й продукт. Запис умов у формі (b) доцільна в тому випадку, коли один і той же споживач багаторазово замовляє всі Неможливо розібрати вираз (невідома помилка): \ {m} 
видів вироблених продуктів. Запис умов у формі (а) природна в тих випадках, коли різні продукти замовляються різними споживачами. Аналогічним чином визначається область застосування запису (с) , що включає як крайні окремі випадки записи (а) і (b). У загальному випадку, коли немає необхідності обмежуватися задачами лінійного стохастичного  програмування, імовірнісні обмеження записуються у вигляді  

Неможливо розібрати вираз (невідома помилка): \ P \left \{ x \in G_{i} (\omega) \right \} \geq {\alpha}_{i} ,

де Неможливо розібрати вираз (невідома помилка): \ G_{i} (\omega) -деяка випадкова область, що задається системою рівностей і нерівностей або будь-яким іншим конструктивним чином [1, c. 64].

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

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

Виконала: Самойленко Тетяна

Доповнювала: Кухаренко Анастасія