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

Версія за 17:51, 18 травня 2020

Класичній транспортної задачі і різним її модифікаціям і узагальненям присвячена велика кількість літератури (наприклад, див. [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 , Неможливо розібрати вираз (невідома помилка): \sum^{n}_{j=1} {x_{ij}=a_i} , Неможливо розібрати вираз (невідома помилка): \sum^{m}_{i=1} {x_{ij}=y_j} , Неможливо розібрати вираз (невідома помилка): \sum^{n}_{j=1} {y_j} = \sum^{m}_{i=1} {a_i} , Неможливо розібрати вираз (невідома помилка): x_{ij} \geq 0 , Неможливо розібрати вираз (невідома помилка): y_{ij} \geq 0 , Неможливо розібрати вираз (невідома помилка): i=1,...,m; , Неможливо розібрати вираз (невідома помилка): j=1,...,n ,

Для вирішення цього завдання в роботі [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.

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