Відмінності між версіями «Стохастична транспортна задача. Неперервний розподіл попиту.»
4696268 (обговорення • внесок) |
4696268 (обговорення • внесок) |
||
| Рядок 1: | Рядок 1: | ||
| − | Класичній транспортної задачі і різним її модифікаціям і узагальненям присвячена велика кількість літератури (наприклад, див. [1]). | + | '''Класичній транспортної задачі''' і різним її модифікаціям і узагальненям присвячена велика кількість літератури (наприклад, див. [1]). |
| − | Стохастична транспортна задача обговорювалася в таких виданнях - [2, 3, 4, 5, 6, 7, 8]. | + | Стохастична транспортна задача обговорювалася в таких виданнях - [2, 3, 4, 5, 6, 7, 8, 9]. |
| − | У додатках значний інтерес представляє стохастична постановка транспортної задачі, в якій | + | |
| − | Нехай <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>\ b_j=b_j(w) </math> в j-му пункті споживані - випадкова величина. |
| − | <math>\ q^{(-)}_j[b_j(w)-y_j] </math>, де <math>\ q^{(-)}_j </math> - збиток (штраф за дефіцит), пов’язаний з нестачею одиниці продукту. | + | Припустимо спочатку, що попит <math>\ b_j </math> ''неперервно розподілений'' з щільністю <math>\ \varphi_j(b_j) </math> [3, 8]. |
| − | Математичне сподівання сумарних втрат, пов’язаних з перевезенням продукту, збитком від незадовільного попиту і витрат на зберігання надлишкового продукту, | + | Нехай <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> ‒ витрати на зберігання одиниці продукту. | ||
| + | Математичне сподівання сумарних втрат, пов’язаних з перевезенням продукту, збитком від незадовільного попиту і витрат на зберігання надлишкового продукту, дорівнює | ||
<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>\ 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>\ f_j(y_j) </math> по <math>\ y_j </math> отримаємо <math>\ f^{''}_j(y_j)=(q^{(-)}_j+q^{(+)}_j) \varphi_j(b_j) </math> | + | Продиференціюємо двічі <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>\ 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>\ 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>\ 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>, <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> \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> x_{ij} \geq 0 </math>, <math> y_{ij} \geq 0 </math>, <math> i=1,...,m; </math>, <math> j=1,...,n </math>, | ||
| + | Для вирішення цього завдання в роботі [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. | ||
Виконала: [[Користувач:Корнієнко Олександра|Корнієнко Олександра ]] | Виконала: [[Користувач:Корнієнко Олександра|Корнієнко Олександра ]] | ||
| + | Редагувала: [[Користувач:Федорова Анастасія|Федорова Анастасія]] | ||
Версія за 17:47, 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.
Виконала: Корнієнко Олександра Редагувала: Федорова Анастасія
