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

Матеріал з Вікі ЦДПУ
Перейти до: навігація, пошук
 
Рядок 22: Рядок 22:
 
При природному припущені <math>\ q^{(-)}_j+q^{(+)}_j \geq 0  </math> маємо <math>\ f^{''}_j(y_j) \geq 0 </math>.<br /> А це означає, що <math>\ f_j(y_j) </math>, а разом з нею і <math>\ Q(x,y) </math> - опуклі вниз функції  <math>\ y_j </math>.<br />
 
При природному припущені <math>\ q^{(-)}_j+q^{(+)}_j \geq 0  </math> маємо <math>\ f^{''}_j(y_j) \geq 0 </math>.<br /> А це означає, що <math>\ f_j(y_j) </math>, а разом з нею і <math>\ Q(x,y) </math> - опуклі вниз функції  <math>\ y_j </math>.<br />
  
Таким чином, детермінований еквівалент стохастичної транспортної задачі являє собою '''задачу опуклого програмування''': <br />
+
Таким чином, детермінований еквівалент стохастичної транспортної задачі являє собою '''задачу опуклого програмування''', яка має такий вигляд: <br />
<math>\ Q(x,y) \rightarrow min </math>, <math> \sum^{n}_{j=1} {x_{ij}=a_i} </math>, <math>  \sum^{m}_{i=1} {x_{ij}=y_j}</math>,  
+
<math>\ Q(x,y) \rightarrow min </math> (1.1),  
<math>  \sum^{n}_{j=1} {y_j} = \sum^{m}_{i=1} {a_i} </math>,
+
 
<math> x_{ij} \geq 0  </math>, <math> y_{ij} \geq 0  </math>, <math> i=1,...,m; </math>, <math> j=1,...,n </math>,
+
<math> \sum^{n}_{j=1} {x_{ij}=a_i} </math> (1.2),  
 +
 
 +
<math>  \sum^{m}_{i=1} {x_{ij}=y_j}</math> (1.3),  
 +
 
 +
<math>  \sum^{n}_{j=1} {y_j} = \sum^{m}_{i=1} {a_i} </math> (1.4),
 +
 
 +
<math> x_{ij} \geq 0  </math>, <math> y_{ij} \geq 0  </math>, <math> i=1,...,m; </math>, <math> j=1,...,n </math> (1.5),
  
 
Для вирішення цього завдання в роботі [3] розроблено спеціальний алгоритм.<br />
 
Для вирішення цього завдання в роботі [3] розроблено спеціальний алгоритм.<br />

Поточна версія на 23:19, 6 квітня 2021

Класичній транспортної задачі і різним її модифікаціям і узагальненям присвячена велика кількість літератури (наприклад, див. [1]).

Стохастична транспортна задача обговорювалася в таких виданнях - [2, 3, 4, 5, 6, 7, 8, 9].

У додатках значний інтерес представляє стохастична постановка транспортної задачі, в якій передбачається, що попит \ b_j=b_j(w) в j-му пункті споживані - випадкова величина.
Припустимо спочатку, що попит \ b_j неперервно розподілений з щільністю \ \varphi_j(b_j) [3, 8].
Нехай \ y_j=\sum^{m}_{i=1} {x_{ij}} - загальний об’єм продукту, призначеного відповідно до плану, складеного до реалізації \ b_j(w) , для i-го пункту споживання.
Якщо після встановлення попиту \ b_j(w) з’ясується, що \ y_j<b_j(w) попит не буде задоволений.
Збиток, який при цьому буде завдано системі, природно прийняти пропорційним об’єму незадовільного попиту \ q^{(-)}_j[b_j(w)-y_j] , де \ q^{(-)}_j - збиток (штраф за дефіцит), пов’язаний з нестачею одиниці продукту.
У випадку, коли \ y_j>b_j(w) виникає необхідність в зберіганні надлишкового продукту.
Нехай при цьому допоміжні витрати системи пропорційні об’єму надлишкового продукту \ q^{(+)}_j[y_j-b_j(w)] , де \ q^{(+)}_j ‒ витрати на зберігання одиниці продукту.
Математичне сподівання сумарних втрат, пов’язаних з перевезенням продукту, збитком від незадовільного попиту і витрат на зберігання надлишкового продукту, дорівнює
\ Q(x,y)= \sum^{n}_{j=1} \left \{\sum^{m}_{i=1} {c_{ij}x_{ij}} + q^{(+)}_j \int\limits_{0}^{y_j} (y_j-b_j(w)) \varphi_j(b_j) db_j  +   q^{(-)}_j \int\limits_{y_j}^{\infty} (b_j(w)-y_j) \varphi_j(b_j) db_j  \right \}

Цільова функція \ Q(x,y) стохастичної транспортної задачі – опукла вниз функція змінних \ y_j .
Дійсно \ Q(x,y)= \sum^{n}_{j=1} \left \{ \sum^{m}_{i=1} {c_{ij}x_{ij}} + f_j(y_j)  \right \}

де \ f_j(y_j)=q^{(+)}_j  \int\limits_{0}^{y_j} (y_j-b_j) \varphi_j(b_j) db_j + q^{(-)}_j \int\limits_{y_j}^{\infty} (b_j-y_j) \varphi_j(b_j) db_j

Продиференціюємо двічі \ f_j(y_j) по \ y_j , отримаємо
\ f^{''}_j(y_j)=(q^{(-)}_j+q^{(+)}_j) \varphi_j(b_j)

При природному припущені \ q^{(-)}_j+q^{(+)}_j \geq 0  маємо \ f^{''}_j(y_j) \geq 0 .
А це означає, що \ f_j(y_j) , а разом з нею і \ Q(x,y) - опуклі вниз функції \ y_j .

Таким чином, детермінований еквівалент стохастичної транспортної задачі являє собою задачу опуклого програмування, яка має такий вигляд:
\ Q(x,y) \rightarrow min (1.1),

 \sum^{n}_{j=1} {x_{ij}=a_i} (1.2),

  \sum^{m}_{i=1} {x_{ij}=y_j} (1.3),

  \sum^{n}_{j=1} {y_j} = \sum^{m}_{i=1} {a_i} (1.4),

 x_{ij} \geq 0  ,  y_{ij} \geq 0  ,  i=1,...,m; ,  j=1,...,n (1.5),

Для вирішення цього завдання в роботі [3] розроблено спеціальний алгоритм.

Список літератури

1. Гольштейн Е. Г., Юдин Д. Б. Задачи линейного программирования транспортного типа. М., «Наука», 1969.
2. Беряну (Bereanu В.). Stochastic transportation problem: I, II Randomcosts. «Comunicariie Acad. R. P. R.», 1963, № 13, № 4.
3. Вильямс (Williams A. C.). A stochastic transportation problem. «Operations Research», 1963, v. 11, № 5, p. 759—770.
4. Михок, Илеана (Mihoc G., Ilean^a Nadejde). Programarea mathematica. Programarea stochastica. Editura stiintifica, Bucuresti, 1967, p. 407.
5. Чарнс, Кирби, Рэйк (Charnes A., Kirby M., Raike W.). Chanceconstrained generalized networks. «Oper. Res.», 1966, v. 14, p. 1113—1120.
6. Chance-constrained model on transport prices and scheduling under competition. Transportation Sci., 1968, № 1. Aut: Charnes A., Littlechiled, Kirby M., Raike W.
7. Шахиди А. А. Постановки и решение некоторых стохастических транспортных задач. ДАН Тадж. ССР, 1968, т. II, № 3.
8. Шварц (Szwarc W.). The transportation problem with stochastic demand. «Manag. Sci», 1966, v. 11, № 1, p. 33—50.
9. Эль-Агизи (El-Agizy M.). Two-stage programming under uncertainty with discrete distribution function. «Oper. Res.», 1967, v. 15, № 1, p. 55—70.

Виконала: Корнієнко Олександра
Редагувала: Федорова Анастасія