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

Поточна версія на 12:39, 13 травня 2020

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

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

Розглянемо тепер попит Неможливо розібрати вираз (невідома помилка): \ 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 пунктів постачальників цегли в різних містах: Київ, Донецьк, Харків, Одеса, Вінниця зі своїми обсягами товару відповідно (150;130;135;120;110). Ми маємо 4 підприємства в м. Кропивницький, які потребують поставки товару: «Епіцентр», «Агрохімресурс», «Креатив», «Червона Зірка». Матриця цін перевезень цегли від постачальників до споживачів така: Попит у кожного споживача стохастичний. Також вводяться значення штрафів за надлишок а також недостачу товару та відповідно. Ми маємо статистичні дані по кожному з підприємств споживачів по замовленню цегли за останні три роки. Запишемо таблицю попиту для першого підприємства «Епіцентр»: Таблиця попиту для першого підприємства

Запишемо таблицю попиту для другого підприємства «Агрохімресурс»: Таблиця попиту для другого підприємства

Запишемо таблицю попиту для третього підприємства «Креатив»: Таблиця попиту для третього підприємства

Запишемо таблицю попиту для четвертого підприємства «Червона Зірка»: Таблиця попиту для четвертого підприємства

Відмітимо, що 𝑥_ij – обсяг перевезень з А_i-го пункта в B_j-ому споживачу.
Введемо допоміжні змінні u_jk та v_jk – обсяг дефіциту та надлишку.
Запишемо цільову функцію
Доцільна рівність
Виразивши v_jk з останньої рівності та підставивши цей вираз у цільову функцію отримаємо:

Розпишемо її детальніше

Та маємо обмеження

Обмеження для 1-го замовника

Обмеження для 2-го замовника

Обмеження для 3-го замовника

Обмеження для 4-го замовника

x_ij≥0, u_jk≥0, i = 1, ..., 5; k = 1, ..., s_j; j = 1, ..., 4.

Отже ми отримали модель лінійного програмування, яка містить 48 змінних.

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

Доповнювала: Андреєва Ольга