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

Версія за 05:19, 2 червня 2017

Транспортна задача — задача про оптимальний план перевезення продуктів із пунктів відправлення до пунктів споживання за умови, що витрати на перевезення будуть мінімальними.

Стохастична транспортна задача – задача про оптимальний план перевезення продуктів із пунктів відправлення до пунктів споживання за умови, що витрати на перевезення будуть мінімальними та попит на продукцію буде випадковим.

Розглянемо тепер попит Неможливо розібрати вираз (невідома помилка): \ b_j(w)

розподілений дискретно. В цьому випадку детермінований еквівалент стохастичної транспортної задачі виявляється задачею лінійного програмування. 

Припустимо, що попит Неможливо розібрати вираз (невідома помилка): \ b_j

в j-му пункті споживані приймає значення Неможливо розібрати вираз (невідома помилка): \ b_{jk} 
з ймовірностями Неможливо розібрати вираз (невідома помилка): \ p_{jk} 
Неможливо розібрати вираз (невідома помилка): \ (k=1,...,s_j) 

. Нехай Неможливо розібрати вираз (невідома помилка): \ q^{(-)}_j

 і Неможливо розібрати вираз (невідома помилка): \ q^{(+)}_j 
- штраф за дефіцит і витрати зберігання одиниці продукту. 

Введемо допоміжні зміні Неможливо розібрати вираз (невідома помилка): \ u_{jk}

і Неможливо розібрати вираз (невідома помилка): \ v_{jk} 

, рівні відповідні величини дефіциту (і надлишкового продукту) в j-м пункті споживання при реалізації k-го варіанту попиту, тобто при Неможливо розібрати вираз (невідома помилка): \ b_j=b_{jk} .

Цільова функція стохастичної транспортної задачі – математичне сподівання сумарних витрат – записується у вигляді Неможливо розібрати вираз (невідома помилка): \ \sum^{n}_{j=1} \left \{\sum^{m}_{i=1} {c_{ij}x_{ij}} + q^{(-)}_j \sum^{s_j}_{k=1} {p_{jk}u_{jk}} + q^{(+)}_j \sum^{s_j}_{k=1} {p_{jk}v_{jk}} \right \}

Завжди має місце рівність Неможливо розібрати вираз (невідома помилка): \sum^{m}_{i=1} {x_{ij}+u_{jk}-v_{jk}} = b_{jk} , Неможливо розібрати вираз (невідома помилка): \ k=1,...,s_{j}

; Неможливо розібрати вираз (невідома помилка): \ j=1,...,n 

. Обчислюючи Неможливо розібрати вираз (невідома помилка): \ v_{jk}

із останньої рівності, перепишемо вираз для цільового функціонала задачі 

Неможливо розібрати вираз (невідома помилка): \ \sum^{n}_{j=1} \left \{\sum^{m}_{i=1} {(c_{ij} + q^{(+)}_j)x_{ij}} +(q^{(-)}_j+q^{(+)}_j) \sum^{s_j}_{k=1} {p_{jk}u_{jk}} \right \} - \sum^{n}_{j=1} {q^{(+)}_j \bar{b}_j}

Де Неможливо розібрати вираз (невідома помилка): \bar{b}_j = Mb_j(w)= \sum^{s_j}_{k=1} {p_{jk}b_{jk}} . Останній член в виразі для критерію якості розв’язку стохастичної транспортної задачі не містить параметрів управління. Тому в формальній моделі задачі його можна опустити. Таким чином, детермінований еквівалент стохастичної транспортної задачі з дискретним розподілом попиту може бути представлений наступною моделлю лінійного програмування:

Неможливо розібрати вираз (невідома помилка): \ \sum^{n}_{j=1} \left \{\sum^{m}_{i=1} {(c_{ij} + q^{(+)}_{ij})x_{j}} +(q^{(-)}_{ij}+q^{(+)}_{ij}) \sum^{s_j}_{k=1} {p_{jk}u_{jk}} \right \} \rightarrow min

,

Неможливо розібрати вираз (невідома помилка): \sum^{n}_{j=1} {x_{ij}=a_i} , Неможливо розібрати вираз (невідома помилка): \ i=1,...,m

Неможливо розібрати вираз (невідома помилка): \sum^{m}_{i=1} {x_{ij}+u_{jk}-v_{jk}} = b_{jk}

,  Неможливо розібрати вираз (невідома помилка): \ k=1,...,s_j 

Неможливо розібрати вираз (невідома помилка): \ j=1,...,n

Неможливо розібрати вираз (невідома помилка): \sum^{n}_{j=1} \sum^{s_j}_{k=1} {(v_{jk}-u_{jk})} = \sum^{m}_{i=1} {a_i} - \sum^{n}_{j=1} \sum^{s_j}_{k=1} {b_jk}

Неможливо розібрати вираз (невідома помилка): \ x_{ij} \geq 0 , Неможливо розібрати вираз (невідома помилка): \ u_{jk} \geq 0 , Неможливо розібрати вираз (невідома помилка): \ v_{jk} \geq 0 , Неможливо розібрати вираз (невідома помилка): \ i=1,...,m , Неможливо розібрати вираз (невідома помилка): \ k=1,...,s_j , Неможливо розібрати вираз (невідома помилка): \ j=1,...,n .

Приклад постановки транспортної задачі стохатичного програмування:

5 студенток, що закінчили курс художньої праці виготовлять прикраси вдома у кількості відповідно (151;116;143;142;167).

Ми маємо 4 магазина які потребують поставки художніх прикрас: «Світанок», «Аура», «Лісова пісня», «Вікторія».

Матриця цін перевезень прикрас від студентів до магазинів задана c_ij. Попит у кожного споживача (магазину) стохастичний. Також вводяться значення штрафів за надлишок а також недостачу товару q_j^+=(2;1;3;4) та q_j^-=(4;2;3;1) відповідно.

М и маємо статистичні дані по кожному магазину споживачів по замовленню прикрас за останні 35 місяців.

Потрібно здійснити оптимальний план перевезення товарів із пунктів відправлення до пунктів споживання за умови, що витрати на перевезення будуть мінімальними.

Виконала: Лисенко Наталія Дмитрівна