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

Матеріал з Вікі ЦДУ
Версія від 12:39, 13 травня 2020; 4625918 (обговореннявнесок)

(різн.) ← Попередня версія • Поточна версія (різн.) • Новіша версія → (різн.)
Перейти до: навігація, пошук

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

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

Розглянемо тепер попит Неможливо розібрати вираз (невідома помилка): \ 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 підприємства в м. Кропивницький, які потребують поставки товару: «Епіцентр», «Агрохімресурс», «Креатив», «Червона Зірка». Матриця цін перевезень цегли від постачальників до споживачів така: Рис1.png Попит у кожного споживача стохастичний. Також вводяться значення штрафів за надлишок а також недостачу товару Рис2.png та Рис3.png відповідно. Ми маємо статистичні дані по кожному з підприємств споживачів по замовленню цегли за останні три роки. Запишемо таблицю попиту для першого підприємства «Епіцентр»: Таблиця попиту для першого підприємства Table1.png

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

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

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

Відмітимо, що 𝑥ij – обсяг перевезень з Аi-го пункта в Bj-ому споживачу.
Введемо допоміжні змінні ujk та vjk – обсяг дефіциту та надлишку.
Запишемо цільову функцію Рис4.jpg
Доцільна рівність Рис5.png
Виразивши vjk з останньої рівності та підставивши цей вираз у цільову функцію отримаємо: Рис6.png

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

Та маємо обмеження
Рис8.png

Обмеження для 1-го замовника
Рис9.png

Обмеження для 2-го замовника
Рис10.png

Обмеження для 3-го замовника
Рис11.png

Обмеження для 4-го замовника
Рис12.png

xij≥0, ujk≥0, i = 1, ..., 5; k = 1, ..., sj; j = 1, ..., 4.

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


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

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