Відмінності між версіями «Користувач:Таня Запорожчук»

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

Версія за 20:05, 14 травня 2018

2012 рік

Про себе

Студентка 17 групи фізико-математичного факультету Кіровоградського педагогічного університету імені В. Винниченка

Мої інтереси

Я займаюся спортом, а також хочу навчитися вишивати та професійно кататися на ковзанах.

Проекти в яких беру участь

Інформатика та програмування (27 група)



Мої роботи

Проект з інформатики: "Екологія" - №17 групи ФМФ, 2014.

Example.jpg

CТОХАСТИЧНА ТРАНСПОРТНА ЗАДАЧА. ДИСКРЕТНИЙ РОЗПОДІЛ ПОПИТУ. 1 модуль Транспортна задача — задача про оптимальний план перевезення продуктів із пунктів відправлення до пунктів споживання за умови, що витрати на перевезення будуть мінімальними. Стохастична транспортна задача – задача про оптимальний план перевезення продуктів із пунктів відправлення до пунктів споживання за умови, що витрати на перевезення будуть мінімальними та попит на продукцію буде випадковим. Розглянемо тепер попит Неможливо розібрати вираз (невідома помилка): b_j (w) 

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

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

в j-му пункті споживані приймає значення Неможливо розібрати вираз (невідома помилка): b_jk
з ймовірностями Неможливо розібрати вираз (невідома помилка): p_jk
(k=1,…,s_j)</math>. Нехай Неможливо розібрати вираз (невідома помилка): q_j^((-))
 і Неможливо розібрати вираз (невідома помилка): q_j^((+))
- штраф за дефіцит і витрати зберігання одиниці продукту.

Введемо допоміжні зміні Неможливо розібрати вираз (невідома помилка): u_jk 

 і  Неможливо розібрати вираз (невідома помилка): ϑ_jk

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

.
Example.jpg
Отримано з https://wiki.cusu.edu.ua/index.php?title=Користувач:Таня_Запорожчук&oldid=317127