Відмінності між версіями «Стохастична транспортна задача. Неперервний розподіл попиту.»
4696268 (обговорення • внесок) |
2559956 (обговорення • внесок) |
||
| (не показані 7 проміжних версій ще одного учасника) | |||
| Рядок 1: | Рядок 1: | ||
| − | '''Класичній транспортної задачі''' і різним її модифікаціям і узагальненям присвячена велика кількість літератури (наприклад, див. [1]). | + | '''Класичній транспортної задачі''' і різним її модифікаціям і узагальненям присвячена велика кількість літератури (наприклад, див. [1]).<br /> |
| − | + | ||
| − | У додатках значний інтерес представляє стохастична постановка транспортної задачі, в якій передбачається, що попит <math>\ b_j=b_j(w) </math> в j-му пункті споживані - випадкова величина. | + | Стохастична транспортна задача обговорювалася в таких виданнях - [2, 3, 4, 5, 6, 7, 8, 9]. <br /> |
| − | Припустимо спочатку, що попит <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=b_j(w) </math> в j-му пункті споживані - випадкова величина. <br /> |
| − | Якщо після встановлення попиту <math>\ b_j(w) </math> з’ясується, що <math>\ y_j<b_j(w) </math> попит не буде задоволений. Збиток, який при цьому буде завдано системі, природно прийняти пропорційним об’єму незадовільного попиту | + | Припустимо спочатку, що попит <math>\ b_j </math> ''неперервно розподілений'' з щільністю <math>\ \varphi_j(b_j) </math> [3, 8].<br /> |
| − | <math>\ q^{(-)}_j[b_j(w)-y_j] </math>, де <math>\ q^{(-)}_j </math> - збиток (штраф за дефіцит), пов’язаний з нестачею одиниці продукту. | + | Нехай <math>\ y_j=\sum^{m}_{i=1} {x_{ij}} </math> - загальний об’єм продукту, призначеного відповідно до плану, складеного до реалізації <math>\ b_j(w) </math>, для i-го пункту споживання. <br /> |
| − | У випадку, коли <math>\ y_j>b_j(w) </math> виникає необхідність в зберіганні надлишкового продукту. | + | Якщо після встановлення попиту <math>\ b_j(w) </math> з’ясується, що <math>\ y_j<b_j(w) </math> попит не буде задоволений. <br /> |
| − | Нехай при цьому допоміжні витрати системи пропорційні об’єму надлишкового продукту <math>\ q^{(+)}_j[y_j-b_j(w)] </math>, де <math>\ q^{(+)}_j </math> ‒ витрати на зберігання одиниці продукту. | + | Збиток, який при цьому буде завдано системі, природно прийняти пропорційним об’єму незадовільного попиту |
| − | Математичне сподівання сумарних втрат, пов’язаних з перевезенням продукту, збитком від незадовільного попиту і витрат на зберігання надлишкового продукту, дорівнює | + | <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> \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), | |
| − | + | ||
| − | + | ||
| − | <math> x_{ij} \geq 0 </math>, <math> y_{ij} \geq 0 </math>, <math> i=1,...,m; </math>, <math> j=1,...,n </math>, | + | |
| − | Для вирішення цього завдання в роботі [3] розроблено спеціальний алгоритм. | + | Для вирішення цього завдання в роботі [3] розроблено спеціальний алгоритм.<br /> |
== Список літератури == | == Список літератури == | ||
| − | 1. Гольштейн Е. Г., Юдин Д. Б. Задачи линейного программирования транспортного типа. М., «Наука», 1969. | + | 1. Гольштейн Е. Г., Юдин Д. Б. Задачи линейного программирования транспортного типа. М., «Наука», 1969.<br /> |
| − | 2. Беряну (Bereanu В.). Stochastic transportation problem: I, II Randomcosts. «Comunicariie Acad. R. P. R.», 1963, № 13, № 4. | + | 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. | + | 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. | + | 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. | + | 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. | + | 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. | + | 7. Шахиди А. А. Постановки и решение некоторых стохастических транспортных задач. ДАН Тадж. ССР, 1968, т. II, № 3.<br /> |
| − | 8. Шварц (Szwarc W.). The transportation problem with stochastic demand. «Manag. Sci», 1966, v. 11, № 1, p. 33—50. | + | 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. | + | 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.
Виконала: Корнієнко Олександра
Редагувала: Федорова Анастасія
