Відмінності між версіями «Користувач:Таня Запорожчук»
652469 (обговорення • внесок) (→Мої роботи) |
652469 (обговорення • внесок) (→Мої роботи) |
||
| Рядок 22: | Рядок 22: | ||
Стохастична транспортна задача – задача про оптимальний план перевезення продуктів із пунктів відправлення до пунктів споживання за умови, що витрати на перевезення будуть мінімальними та попит на продукцію буде випадковим. | Стохастична транспортна задача – задача про оптимальний план перевезення продуктів із пунктів відправлення до пунктів споживання за умови, що витрати на перевезення будуть мінімальними та попит на продукцію буде випадковим. | ||
Розглянемо тепер попит <math>b_j (w)</math> розподілений дискретно. В цьому випадку детермінований еквівалент стохастичної транспортної задачі виявляється задачею лінійного програмування. | Розглянемо тепер попит <math>b_j (w)</math> розподілений дискретно. В цьому випадку детермінований еквівалент стохастичної транспортної задачі виявляється задачею лінійного програмування. | ||
| − | Припустимо, що попит <math>b_j</math> в j-му пункті споживані приймає значення <math>b_jk</math> з ймовірностями <math><math>p_jk</math> (k=1,…,s_j)</math>. Нехай | + | Припустимо, що попит <math>b_j</math> в j-му пункті споживані приймає значення <math>b_jk</math> з ймовірностями <math><math>p_jk</math> (k=1,…,s_j)</math>. Нехай <math>q_j^((-))</math> і <math>q_j^((+))</math>< - штраф за дефіцит і витрати зберігання одиниці продукту. |
Введемо допоміжні зміні <math>u_jk і ϑ_jk</math>, рівні відповідні величини дефіциту (і надлишкового продукту) в j-м пункті споживання при реалізації k-го варіанту попиту, тобто при <math>b_j=b_jk</math>. | Введемо допоміжні зміні <math>u_jk і ϑ_jk</math>, рівні відповідні величини дефіциту (і надлишкового продукту) в j-м пункті споживання при реалізації k-го варіанту попиту, тобто при <math>b_j=b_jk</math>. | ||
Цільова функція стохастичної транспортної задачі – математичне сподівання сумарних витрат – записується у вигляді | Цільова функція стохастичної транспортної задачі – математичне сподівання сумарних витрат – записується у вигляді | ||
Версія за 19:57, 14 травня 2018
Про себе
Студентка 17 групи фізико-математичного факультету Кіровоградського педагогічного університету імені В. Винниченка
Мої інтереси
Я займаюся спортом, а також хочу навчитися вишивати та професійно кататися на ковзанах.
Проекти в яких беру участь
Інформатика та програмування (27 група)
Мої роботи
Проект з інформатики: "Екологія" - №17 групи ФМФ, 2014.
CТОХАСТИЧНА ТРАНСПОРТНА ЗАДАЧА. ДИСКРЕТНИЙ РОЗПОДІЛ ПОПИТУ. 1 модуль Транспортна задача — задача про оптимальний план перевезення продуктів із пунктів відправлення до пунктів споживання за умови, що витрати на перевезення будуть мінімальними. Стохастична транспортна задача – задача про оптимальний план перевезення продуктів із пунктів відправлення до пунктів споживання за умови, що витрати на перевезення будуть мінімальними та попит на продукцію буде випадковим. Розглянемо тепер попит Неможливо розібрати вираз (невідома помилка): b_j (w)
розподілений дискретно. В цьому випадку детермінований еквівалент стохастичної транспортної задачі виявляється задачею лінійного програмування.
Припустимо, що попит Неможливо розібрати вираз (невідома помилка): b_j
в j-му пункті споживані приймає значення Неможливо розібрати вираз (невідома помилка): b_jk з ймовірностями Неможливо розібрати вираз (невідома помилка): <math>p_jk (k=1,…,s_j)</math>. Нехай Неможливо розібрати вираз (невідома помилка): q_j^((-)) і Неможливо розібрати вираз (невідома помилка): q_j^((+))
< - штраф за дефіцит і витрати зберігання одиниці продукту. Введемо допоміжні зміні Неможливо розібрати вираз (невідома помилка): u_jk і ϑ_jk , рівні відповідні величини дефіциту (і надлишкового продукту) в j-м пункті споживання при реалізації k-го варіанту попиту, тобто при Неможливо розібрати вираз (невідома помилка): b_j=b_jk . Цільова функція стохастичної транспортної задачі – математичне сподівання сумарних витрат – записується у вигляді Неможливо розібрати вираз (невідома помилка): ∑_(j=1)^n▒{∑_(i=1)^m▒c_ij x_ij+q_j^((-)) ∑_(k=1)^(s_j)▒〖 p_jk u_jk 〗+q_j^((+)) ∑_(k=1)^(s_j)▒〖 p_jk ϑ_jk 〗}
Завжди має місце рівність Неможливо розібрати вираз (невідома помилка): ∑_(i=1)^m▒x_ij +u_jk-ϑ_jk=b_jk,k=1,…s_j;j=1,…n
.
Обчислюючи Неможливо розібрати вираз (невідома помилка): ϑ_jk із останньої рівності, перепишемо вираз для цільового функціонала задачі
Неможливо розібрати вираз (невідома помилка): ∑_(j=1)^n▒〖{∑_(i=1)^m▒〖(c〗_ij +q_j^((+)))x_ij+(q_j^((-) )+q_j^((+) ))∑_(k=1)^(s_j)▒〖 p_jk u_jk 〗}-∑_(j=1)^n▒〖q_j^((+) ) (b_j ) ̅ 〗〗 Де (b_j ) ̅=Mb_j (w)=∑_(k=1)^(s_j)▒〖 p_jk b_jk 〗 . Останній член в виразі для критерію якості розв’язку стохастичної транспортної задачі не містить параметрів управління. Тому в формальній моделі задачі його можна опустити. Таким чином, детермінований еквівалент стохастичної транспортної задачі з дискретним розподілом попиту може бути представлений наступною моделлю лінійного програмування:
Неможливо розібрати вираз (невідома помилка): ∑_(j=1)^n▒〖{∑_(i=1)^m▒〖(c〗_ij +q_j^((+)))x_ij+(q_j^((-) )+q_j^((+) ))∑_(k=1)^(s_j)▒〖 p_jk u_jk 〗}→min〗 ∑_(j=1)^n▒x_ij =a_i,i=1,…,m ∑_(i=1)^m▒x_ij +u_jk-ϑ_jk=b_jk,k=1,…,s_j;j=1,…n ∑_(j=1)^n▒〖∑_(k=1)^(s_j)▒〖( ϑ_jk-u_jk 〗)=∑_(i=1)^m▒a_i -∑_(j=1)^n▒∑_(k=1)^(s_j)▒〖 b_j k〗〗 x_ij≥0,u_jk≥0,ϑ_jk≥0,i=1,…,s_j,j=1,…,n.
2 модуль УМОВИ РОЗВЯЗУВАНОСТЫ ЗАДАЧ ДРУГОГО ЕТАПУ Двоетапна задача стохастичного програмування виникає тоді, коли процес прийняття рішення поділяють на два етапи. На першому етапі вибирається попередній план, який задовольняє умови задачі за будь-якої реалізації випадкових параметрів. На другому етапі розраховується величина компенсації відхилень розробленого плану від фактичних значень, щоб були визначені після спостереження за реалізацією випадкових параметрів. Оптимальний план задачі визначають так, щоб забезпечити мінімум середнього значення загальних витрат, які виникають на обох етапах розв’язування задачі. Для існування розв’язку двоетапної задачі вибір плану на першому етапі має гарантувати існування плану-компенсації. Перепишемо двоетапну задачу стохастичного лінійного програмування в такій формі:
Неможливо розібрати вираз (невідома помилка): 〖min〗_x〖M_w 〗 (cx+P(x,A,b)) (1.1) A^((1)) x=b^((1)) (1.2) x≥0
(1.3)
де Неможливо розібрати вираз (невідома помилка): P(x,A,b)=〖min〗_y q(y)
(1.4)
Неможливо розібрати вираз (невідома помилка): By=b-Ax
(1.5)
Встановимо умови розв'язності задачі (1.4)-(1.5) другого етапу. Має місце наступна умова обмеженості знизу цільового функціоналу. Теорема 1.1. Нехай множина K_2 непорожня. Для рішення задачі другого етапу при будь-яких реалізаціях А і b і будь-якому попередньому плані x необхідно і достатньо, щоб система нерівностей
Неможливо розібрати вираз (невідома помилка): zB≤q
(1.6)
була розв'язана, тобто щоб Неможливо розібрати вираз (невідома помилка): (z|zB≤q)≠∅
(передбачається, що B і q детерміновані).
Доведення: За умовою множина планів задачі (1.4)-(1.6) не порожня. Згідно з теоремою двоїстості лінійного програмування функція Неможливо розібрати вираз (невідома помилка): P(x,A,b)
обмежена знизу в тому і тільки в тому випадку, коли область визначення двоїстої задачі для кожного x,A,b
Неможливо розібрати вираз (невідома помилка): P(x,A,b)=〖max〗_z z(b-Ax) (1.7) zB≤q
(1.8)
непорожня. Оскільки область визначення задачі (1.7)-(1.8) не залежить від A,b, x, то при виконанні умови (1.6) задача другого етапу розв'язана при всіх A,b і x. Функція P(x,A,b) в цьому випадку не обмежена знизу для всіх x , і задача (1.1)-(1.3) і, отже, двоетапна задача втрачає сенс. Теорема 1.2. Нехай матриця B має Неможливо розібрати вираз (невідома помилка): m+1
стовпець і задовольняє умовам:
a) має ранг m, (1.9) b) Неможливо розібрати вираз (невідома помилка): -B_(m+1)=∑_(j=1)^m▒〖g_j B_j 〗,g_j>0,j=1,…,m
(1.10)
Доведення: Необхідність. Нехай задачу (1.4)-(1.6) можна розв’язати. Тоді множина планів двоїстої до неї задачі непорожня. Нехай вектор z_0 задовольняє умовам (1.8) двоїстої задачі, тобто
Неможливо розібрати вираз (невідома помилка): z_0 B_j≤g_j,j=1,…,m+1
(1.11)
Звідси при Неможливо розібрати вираз (невідома помилка): g_j>0
Неможливо розібрати вираз (невідома помилка): ∑_(j=1)^m▒g_j z_0 B_j≤∑_(j=1)^m▒g_j q_j
Із умови b) і (1.11) для Неможливо розібрати вираз (невідома помилка): j=m+1
Неможливо розібрати вираз (невідома помилка): z_0 B_(m+1)=-∑_(j=1)^m▒〖〖z_0 g〗_j B_j≤〗 q_(m+1)
(1.12)
Із (1.11) і (1.12) отримуємо (1.10). Достатність. Нехай (1.10) має місце, а функція Неможливо розібрати вираз (невідома помилка): P(x,A,b)
не обмежена на множині планів задачі. Тоді множина планів задачі, двоїстої до задачі другого етапу, порожня
Неможливо розібрати вираз (невідома помилка): (z|zB≤q)≠∅
(1.13)
З лінійної незалежності векторів Неможливо розібрати вираз (невідома помилка): B_1,…,B_m , слідує, що система Неможливо розібрати вираз (невідома помилка): zB_j=q_j,j=1,…,m
(1.14)
маємо єдине рішення Неможливо розібрати вираз (невідома помилка): z_0 . В силу співвідношення (1.14) Неможливо розібрати вираз (невідома помилка): z_0 B_(m+1)>q_(m+1)
Із (1.13), (1.14) і умови b) теореми отримуємо Неможливо розібрати вираз (невідома помилка): z_0 B_(m+1)=-∑_(j=1)^m▒〖〖z_0 g〗_j B_j 〗=-∑_(j=1)^m▒〖g_j q_j 〗>q_m+1
що суперечить умові (1.10). Теорему доведено. Теорема 1.3. Нехай матриця B має ранг m і існують числа Неможливо розібрати вираз (невідома помилка): q_j>0,j=1,…,m; q_j≥0,j=m+1,…,n_1; (n_1-m>1)
, такі що
Неможливо розібрати вираз (невідома помилка): ∑_(j=m+1)^(n_1)▒〖g_j B_j 〗=-∑_(j=1)^m▒〖g_j B_j 〗
