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

Матеріал з Вікі ЦДУ
Перейти до: навігація, пошук
 
(не показані 9 проміжних версій ще одного учасника)
Рядок 1: Рядок 1:
−
Стохастична постановка транспортної задачі, в якій пропонується щоб попит <math>\ b_j=b_j(w) </math> в j-му пункті споживані випадкової величини. Припустимо, що попит <math>\ b_j </math>  неперервно розподілений з щільністю <math>\ \varphi_j(b_j) </math>.
+
'''Класичній транспортної задачі''' і різним її модифікаціям і узагальненям присвячена велика кількість літератури (наприклад, див. [1]).<br />
−
Нехай <math>\ y_j=\sum^{m}_{i=1} {x_{ij}} </math> -  загальний об’єм продукту, призначеного з відповідністю з планом, складеним до реалізації <math>\ b_j(w) </math>, для i-го пункту споживання. Якщо після встановлення попиту <math>\ b_j(w) </math> з’ясується, що <math>\ y_j<b_j(w) </math> попит не буде задоволений. Збиток, який при цьому буде завдано системі, природно прийняти пропорційним об’єму незадовільного попиту  
+
 
−
<math>\ q^{(-)}_j[b_j(w)-y_j] </math>,  де  <math>\ q^{(-)}_j </math> - збиток (штраф за дефіцит), пов’язаний з нестачею одиниці продукту. В випадку, коли <math>\ y_j>b_j(w) </math> виникає необхідність в зберіганні надлишкового продукту. Нехай при цьому допоміжні витрати системи пропорційні об’єму надлишкового продукту <math>\ q^{(+)}_j[y_j-b_j(w)] </math>,  де  <math>\ q^{(+)}_j </math>  ‒ витрати на зберіганні одиниці продукту.  
+
Стохастична транспортна задача обговорювалася в таких виданнях - [2, 3, 4, 5, 6, 7, 8, 9]. <br />
−
Математичне сподівання сумарних втрат, пов’язаних з перевезенням продукту, збитком від незадовільного попиту і витрат на зберігання надлишкового продукту, рівно
+
 
 +
У додатках значний інтерес представляє стохастична постановка транспортної задачі, в якій передбачається, що попит <math>\ b_j=b_j(w) </math> в j-му пункті споживані - випадкова величина. <br />
 +
Припустимо спочатку, що попит <math>\ b_j </math>  ''неперервно розподілений'' з щільністю <math>\ \varphi_j(b_j) </math> [3, 8].<br />
 +
Нехай <math>\ y_j=\sum^{m}_{i=1} {x_{ij}} </math> -  загальний об’єм продукту, призначеного відповідно до плану, складеного до реалізації <math>\ b_j(w) </math>, для i-го пункту споживання. <br />
 +
Якщо після встановлення попиту <math>\ b_j(w) </math> з’ясується, що <math>\ y_j<b_j(w) </math> попит не буде задоволений. <br />
 +
Збиток, який при цьому буде завдано системі, природно прийняти пропорційним об’єму незадовільного попиту  
 +
<math>\ q^{(-)}_j[b_j(w)-y_j] </math>,  де  <math>\ q^{(-)}_j </math> - збиток (штраф за дефіцит), пов’язаний з нестачею одиниці продукту. <br />
 +
У випадку, коли <math>\ y_j>b_j(w) </math> виникає необхідність в зберіганні надлишкового продукту. <br />
 +
Нехай при цьому допоміжні витрати системи пропорційні об’єму надлишкового продукту <math>\ q^{(+)}_j[y_j-b_j(w)] </math>,  де  <math>\ q^{(+)}_j </math>  ‒ витрати на зберігання одиниці продукту. <br />
 +
Математичне сподівання сумарних втрат, пов’язаних з перевезенням продукту, збитком від незадовільного попиту і витрат на зберігання надлишкового продукту, дорівнює<br />
 
<math>\ 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 \}</math>
 
<math>\ 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 \}</math>
  
−
Цільовий функціонал <math>\ Q(x,y) </math> стохастичної транспортної задачі – опукла вниз функція змінних <math>\ y_j </math>. Дійсно <math>\ Q(x,y)= \sum^{n}_{j=1} \left \{ \sum^{m}_{i=1} {c_{ij}x_{ij}} + f_j(y_j)  \right \}</math>
+
'''Цільова функція''' <math>\ Q(x,y) </math> стохастичної транспортної задачі – опукла вниз функція змінних <math>\ y_j </math>.<br /> Дійсно <math>\ Q(x,y)= \sum^{n}_{j=1} \left \{ \sum^{m}_{i=1} {c_{ij}x_{ij}} + f_j(y_j)  \right \}</math>
 +
 
 +
де <math>\ 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</math><br />
 +
 
 +
Продиференціюємо двічі <math>\ f_j(y_j) </math> по <math>\ y_j </math>, отримаємо <br /> <math>\ f^{''}_j(y_j)=(q^{(-)}_j+q^{(+)}_j) \varphi_j(b_j) </math>
 +
 
 +
При природному припущені <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 />
 +
<math>\ Q(x,y) \rightarrow min </math> (1.1),
 +
 
 +
<math> \sum^{n}_{j=1} {x_{ij}=a_i} </math> (1.2),
  
−
Де <math>\ 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</math>
+
<math> \sum^{m}_{i=1} {x_{ij}=y_j}</math> (1.3),
  
−
Продиференціюємо двічі <math>\ f_j(y_j) </math> по <math>\ y_j </math> отримаємо <math>\ f^{''}_j(y_j)=(q^{(-)}_j+q^{(+)}_j) \varphi_j(b_j) </math>
+
<math> \sum^{n}_{j=1} {y_j} = \sum^{m}_{i=1} {a_i} </math> (1.4),
  
−
При природному припущені <math>\ q^{(-)}_j+q^{(+)}_j \geq 0  </math> маємо <math>\ f^{''}_j(y_j) \geq 0 </math>. А це означає, що <math>\ f_j(y_j) </math>, а разом з нею і <math>\ Q(x,y) </math> - опуклі вниз функції  <math>\ y_j </math>.
+
<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 />
−
<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>  \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>,
+
  
 +
== Список літератури ==
 +
1. Гольштейн Е. Г., Юдин Д. Б. Задачи линейного программирования транспортного типа. М., «Наука», 1969.<br />
 +
2. Беряну (Bereanu В.). Stochastic transportation problem: I, II Randomcosts. «Comunicariie Acad. R. P. R.», 1963, № 13, № 4.<br />
 +
3. Вильямс (Williams A. C.). A stochastic transportation problem. «Operations Research», 1963, v. 11, № 5, p. 759—770.<br />
 +
4. Михок, Илеана (Mihoc G., Ilean^a Nadejde). Programarea mathematica. Programarea stochastica. Editura stiintifica, Bucuresti, 1967, p. 407.<br />
 +
5. Чарнс, Кирби, Рэйк (Charnes A., Kirby M., Raike W.). Chanceconstrained generalized networks. «Oper. Res.», 1966, v. 14, p. 1113—1120.<br />
 +
6. Chance-constrained model on transport prices and scheduling under competition. Transportation Sci., 1968, № 1. Aut: Charnes A., Littlechiled, Kirby M., Raike W.<br />
 +
7. Шахиди А. А. Постановки и решение некоторых стохастических транспортных задач. ДАН Тадж. ССР, 1968, т. II, № 3.<br />
 +
8. Шварц (Szwarc W.). The transportation problem with stochastic demand. «Manag. Sci», 1966, v. 11, № 1, p. 33—50.<br />
 +
9. Эль-Агизи (El-Agizy M.). Two-stage programming under uncertainty with discrete distribution function. «Oper. Res.», 1967, v. 15, № 1, p. 55—70.<br />
  
−
Виконала: [[Користувач:Корнієнко Олександра|Корнієнко Олександра ]]
+
Виконала: [[Користувач:Корнієнко Олександра|Корнієнко Олександра ]]<br />
 +
Редагувала: [[Користувач:4696268|Федорова Анастасія]]

Поточна версія на 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.

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

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