Стохастична транспортна задача. Неперервний розподіл попиту.

Матеріал з Вікі ЦДУ
Перейти до: навігація, пошук

Класичній транспортної задачі і різним її модифікаціям і узагальненям присвячена велика кількість літератури (наприклад, див. [1]). Стохастична транспортна задача обговорювалася в таких виданнях - [2, 3, 4, 5, 6, 7, 8]. У додатках значний інтерес представляє стохастична постановка транспортної задачі, в якій передбачаэться, що попит Неможливо розібрати вираз (невідома помилка): \ b_j=b_j(w)

в j-му пункті споживані - випадкова величина. Припустимо спочатку, що попит Неможливо розібрати вираз (невідома помилка): \ b_j 
  неперервно розподілений з щільністю Неможливо розібрати вираз (невідома помилка): \ \varphi_j(b_j) 
[3, 7].

Нехай Неможливо розібрати вираз (невідома помилка): \ 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 ,


Виконала: Корнієнко Олександра