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

Версія за 05:13, 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 пунктів постачальників морозива зі своїми обсягами товару відповідно (160;140;145;130;120).

Ми маємо 4 підприємства які потребують поставки товару: «Світанок», «Ескімо», «Мак», «Вікторія». Матриця цін перевезень морозива від постачальників до споживачів така задана: c_ij.

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

Ми маємо статистичні дані по кожному з підприємств споживачів по замовленню морозива за останні три роки. Запишемо таблиці попиту для кожного підприємства і порахуємо ймовірності замовлень за 36 місяців.

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

Таблиця попиту для першого підприємства Табл. 2.5 K b_1 (k) К-сть замовлень за 3 роки (міс.). p_1k 1 60 4 4/36 2 110 10 10/36 3 130 7 7/36 4 160 9 9/36 5 170 6 6/36 Запишемо таблицю попиту для другого підприємства «Ескімо»: Таблиця попиту для другого підприємства Табл. 2.6 K b_2 (k) К-сть замовлень за 3 роки (міс.). p_2k 1 70 20 20/36 2 130 10 10/36 3 180 6 6/36 Запишемо таблицю попиту для третього підприємства: «Мак» Таблиця попиту для третього підприємства Табл. 2.7 K b_3 (k) К-сть замовлень за 3 роки (міс.). p_3k 1 80 12 12/36 2 145 8 8/36 3 175 13 13/36 4 187 3 3/36 Запишемо таблицю попиту для четвертого підприємства «Вікторія»: Таблиця попиту для четвертого підприємства Табл. 2.8 K b_4 (k) К-сть замовлень за 3 роки (міс.). p_4k 1 80 22 22/36 2 100 14 14/36 Потрібно здійснити оптимальний план перевезення товарів із пунктів відправлення до пунктів споживання за умови, що витрати на перевезення будуть мінімальними. Розвязання: Відмітимо, що x_ij – обсяг перевезень з А_i-го пункта в B_j-ому споживачу. Введемо допоміжні змінні u_jk та v_jk – обсяг дефіциту та надлишку. Запишемо цільову функцію ∑_(j=1)^4▒{∑_(i=1)^5▒〖c_ij x_ij 〗+q_j^- ∑_(k=1)^(S_j)▒〖p_jk u_jk 〖+q〗_j^+ ∑_(k=1)^(S_j)▒〖p_jk v_jk 〗〗} . Доцільна рівність ∑_(i=1)^5▒x_ij +u_jk-v_jk=b_jk , k=1,…,s_j; j=1,…,4. Виразивши v_jk з останньої рівності та підставивши цей вираз у цільову функцію отримаємо: ∑_(j=1)^4▒〖{∑_(i=1)^5▒〖〖(c〗_ij 〖+q〗_j^+)x_ij 〗+〖(q〗_j^- 〖+q〗_j^+)∑_(k=1)^(S_j)▒〖p_jk u_jk 〗}.〗 Розпишемо її детальніше ∑_(j=1)^4▒〖{∑_(i=1)^5▒〖〖(c〗_ij 〖+q〗_j^+)x_ij 〗+〖(q〗_j^- 〖+q〗_j^+)∑_(k=1)^(S_j)▒〖p_jk u_jk 〗}=(4x_11+5x_21+3x_31+7x_41+〗 +4x_51+3∙(4/36∙u_11+10/36∙u_12+7/36∙u_13+9/36∙u_14+6/36∙u_15))+(2x_12+ +5x_22+7x_32+3x_42+4x_52+4∙(20/36∙u_21+10/36∙u_22+6/36∙u_23))+(4x_13+ +2x_23+4x_33+8x_43+2x_53+3∙(12/36∙u_31+8/36∙u_32+13/36∙u_33+3/36∙u_34))+ +(8x_14+5x_24+4x_34+6x_44+7x_54+4∙(22/36∙u_41+14/36∙u_42))→min Та маємо обмеження ∑_(j=1)^4▒〖x_ij=a_i, i=1,..,5〗, x_11+x_12+x_13+x_14=160; x_21+x_22+x_23+x_24=140; x_31+x_32+x_33+x_34=145; x_41+x_42+x_43+x_44=130; x_51+x_52+x_53+x_54=120; ∑_(i=1)^5▒x_ij +u_jk-v_jk=b_jk , k=1,…,s_j; j=1,…,4, Обмеження для 1-го замовника x_11+x_21+x_31+x_41+x_51+u_11-v_11=60; x_11+x_21+x_31+x_41+x_51+u_12-v_12=110; x_11+x_21+x_31+x_41+x_51+u_13-v_13=130; x_11+x_21+x_31+x_41+x_51+u_14-v_14=160; x_11+x_21+x_31+x_41+x_51+u_15-v_15=170; Обмеження для 2-го замовника x_12+x_22+x_32+x_42+x_52+u_21-v_21=70; x_12+x_22+x_32+x_42+x_52+u_22-v_22=130; x_12+x_22+x_32+x_42+x_52+u_23-v_23=180; Обмеження для 3-го замовника x_13+x_23+x_33+x_43+x_53+u_31-v_31=80; x_13+x_23+x_33+x_43+x_53+u_32-v_32=145; x_13+x_23+x_33+x_43+x_53+u_33-v_33=175; x_13+x_23+x_33+x_43+x_53+u_34-v_34=187; Обмеження для 4-го замовника x_14+x_24+x_34+x_44+x_54+u_41-v_41=80; x_14+x_24+x_34+x_44+x_54+u_42-v_42=100;

x_ij≥0,u_jk≥0,v_jk≥0, i=1,…,5; k=1,…,s_j; j=1,…,4. Отже ми отримали модель лінійного програмування, яка містить 48 змінних. Розв’яжемо задачу лінійного програмування за допомогою Excel отримаємо: Мінімальна сума за транспортування становить: 3462,31 грн.

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