Відмінності між версіями «Постановка двохетапної задачі СП.»
9167465 (обговорення • внесок) |
|||
| (не показано 23 проміжні версії 4 учасників) | |||
| Рядок 1: | Рядок 1: | ||
| + | <big>У практичних додатках стохастичного програмування частіше за інших зустрічаються так звані двохетапні задачі, або стохастичні задачі з компенсацією нев’язок. Цій задачі присвячено набагато більше публікацій, ніж будь-який інший моделі стохастичного програмування. | ||
| + | |||
| + | В даній статті наведені постановка і якісний аналіз двохетапної стохастичної задачі. | ||
| + | |||
| + | При дослідженні багатьох задач планування і управління в умовах неповної інформації доцільно уявляти собі процес рішення розділеним на два етапи. На першому етапі вибирається попередній план, що дозволяє провести необхідні підготовчі роботи. На другому етапі проводиться компенсація нев’язок, виявлених після спостереження реалізованих значень випадкових параметрів умов задачі. Зрозуміло, що попередній план і план-компенсація повинні бути узгоджені таким чином, щоб забезпечити мінімум середнього значення сумарних витрат, що виникають на обох етапах виконання задачі. У вирішуваній задачі вибір попереднього плану повинен, звичайно, гарантувати існування плану-компенсації. | ||
| + | |||
Розглянемо задачу лінійного програмування: | Розглянемо задачу лінійного програмування: | ||
| − | <math> cx\rightarrow min </math> ( | + | <math> cx\rightarrow min </math> (1.1) |
| − | <math>\ Ax = b </math> ( | + | <math>\ Ax = b </math> (1.2) |
| − | <math> x\geqslant 0 </math>( | + | <math>\ A^{(1)}x = b^{(1)} </math> (1.3) |
| + | |||
| + | <math> x\geqslant 0 </math> (1.4) | ||
тут | тут | ||
<math> c=\left \{ c_j \right \}</math>, <math>\ j = 1,...n, </math>; | <math> c=\left \{ c_j \right \}</math>, <math>\ j = 1,...n, </math>; | ||
| − | |||
<math> b=\left \{ b_i \right \}</math>, <math>\ i = 1,...m, </math>; | <math> b=\left \{ b_i \right \}</math>, <math>\ i = 1,...m, </math>; | ||
| − | |||
<math> b^{(1)} =\left \{ b^{(1)}_k \right \}</math>, <math>\ k = 1,...m_1, </math>; | <math> b^{(1)} =\left \{ b^{(1)}_k \right \}</math>, <math>\ k = 1,...m_1, </math>; | ||
| + | <math> A =\left \| \ a_ij^{(1)} \right \| </math>, <math>\ i = 1,...m, </math>; <math>\ j = 1,...n, </math>;<math> A^{(1)} =\left \| \ a_kj^{(1)} \right \| </math>, <math>\ k = 1,...m_1, </math>; <math>\ j = 1,...n, </math>; | ||
| + | |||
| + | |||
| + | В випадку, коли елементи матриці <math>\ A = A(\omega)</math> і векторів <math>\ b = b(\omega)</math> і <math>\ c = c(\omega)</math> - випадкові величини і рішення <math>\ x </math> слід прийняти спостереження реалізації випадкових параметрів умов, постановка і порядок рішення задачі повинні бути уточнені. | ||
| + | Уявімо собі процес вирішення задачі (1.1) - (1.4) в такий спосіб. Виберемо спочатку (на першому етапі) вектор, що задовольняє умови (1.3) - (1.4). Потім зафіксуємо реалізацію <math>\widehat\omega </math> випадкової події і відповідні йому значення елементів <math>\ A(\widehat\omega)</math> i <math>\ b(\widehat\omega)</math>, оцінимо невязку <math>\ b(\widehat\omega)- A(\widehat\omega)*(\widehat x) </math> в умовах (1.2) задачі і обчислимо вектор <math> y\geqslant 0 </math> компенсуючий невязки у відмінності із співвідношенням | ||
| + | |||
| + | <math>\ By= b(\widehat\omega)- A(\widehat\omega) *(\widehat x) </math> | ||
| + | |||
| + | <math> B =\left \| \ b_{il} \right \| </math>, <math>\ i = 1,...m, </math>; <math>\ l = 1,...n_1, </math>; - матриця компенсації. У загальному випадку елементи В випадкові. Якщо задача (21.1)-(21.4) інтерпритується в термінах планування виробництва. а А - матриця основних технологічних способів, то В - матриця аварійних технологічних способів, що визначають можливі шляхи компенсації виявлених відхилів. Передбачається, що реалізація <math>\ \omega</math> не залежить від вибору <math>\ (\widehat x) </math>. | ||
| + | За порушення умов задачі встановлюється штраф, який залежить від величин складових вектора <math> y </math>, компенсуючого невязки. Природно характеризувати штраф величиною <math> qy </math>, де <math> q\geqslant 0 </math>, взагалі кажучи, випадковий <math> n_1</math> - мірний вектор. | ||
| + | Вектор <math> y </math> компенсуючий невязки, може бути вибраний багатьма способами. Підпорядкуємо вибір у наступній додатковій вимозі. Будемо вибирати складові <math> y </math> таким чином, щоб забезпечити мінімальний штраф за компенсацію невязок умов задачі, що визначаються попереднім планом. Іншими словами на другому етапі завдання | ||
| + | |||
| + | <math> qy\rightarrow min </math> (1.5) | ||
| + | |||
| + | <math>\ By=b-Ax </math> (1.6) | ||
| + | |||
| + | <math> y\geqslant 0 </math> (1.7) | ||
| + | |||
| + | Обидва етапи розв'язка задачі можуть бути зведені в один. Отримаємо постановку, яка носить назву двохетапної задачі лінійного стохастичного програмування: | ||
| + | |||
| + | <math> \min_x M_\omega\{c(\omega)x+\min_y[q(\omega)y|B(\omega)y=b(\omega)-A(\omega)x, y\geqslant0]\}</math>, (1.8) | ||
| + | |||
| + | <math>\ A^{(1)}x = b^{(1)} </math>, (1.9) | ||
| + | |||
| + | <math>x\geqslant0</math>. (1.10) | ||
| + | |||
| + | Таким чином, рішення двоетапної стохастичної задачі складається з двох векторів: детермінованого <math> n </math> - мірного вектора х, що визначає попередній план, і випадкового <math> n </math> - мірного вектора <math>\ y = y(\omega)</math> , визнавчального план компенсації невязок . | ||
| + | Для вирішення завдання досить обчислити оптимальний попередній план <math>\ x </math>. Після реалізації випадкової події <math>\omega</math>, тобто після реалізації випадкових параметрів умов задачі, відповідна реалізація <math>\ y </math> оптимального плану - компенсації обчислюється як рішення задачі лінійного програмування (1.5) - (1.7). | ||
| + | |||
| + | При перспективному плануванні слід враховувати можливість випадкових збурень системи. | ||
| + | |||
| + | Перспективний план повинен володіти свого роду стійкістю по відношенню до зміни вихідних даних, які можуть відбуватися у міру його впровадження. | ||
| + | |||
| + | Затрати на корекцію плану повинні бути якомога меншими. Звідси доцільність використання для перспективного плунвання схем двохетапного (або багатоетапного) стохастичного програмування, малочутливих до зміни параметрів умов задачі. | ||
| + | |||
| + | |||
| + | Виконала: [[Користувач: 65890|Татьяненко Марина Олександрівна]]. Редагував: [[Користувач:9167465|Білобабченко Анатолій Сергійович]] | ||
| + | </big> | ||
Поточна версія на 17:28, 25 червня 2021
У практичних додатках стохастичного програмування частіше за інших зустрічаються так звані двохетапні задачі, або стохастичні задачі з компенсацією нев’язок. Цій задачі присвячено набагато більше публікацій, ніж будь-який інший моделі стохастичного програмування.
В даній статті наведені постановка і якісний аналіз двохетапної стохастичної задачі.
При дослідженні багатьох задач планування і управління в умовах неповної інформації доцільно уявляти собі процес рішення розділеним на два етапи. На першому етапі вибирається попередній план, що дозволяє провести необхідні підготовчі роботи. На другому етапі проводиться компенсація нев’язок, виявлених після спостереження реалізованих значень випадкових параметрів умов задачі. Зрозуміло, що попередній план і план-компенсація повинні бути узгоджені таким чином, щоб забезпечити мінімум середнього значення сумарних витрат, що виникають на обох етапах виконання задачі. У вирішуваній задачі вибір попереднього плану повинен, звичайно, гарантувати існування плану-компенсації.
Розглянемо задачу лінійного програмування:
Неможливо розібрати вираз (невідома помилка): cx\rightarrow min
(1.1)
Неможливо розібрати вираз (невідома помилка): \ Ax = b
(1.2)
Неможливо розібрати вираз (невідома помилка): \ A^{(1)}x = b^{(1)}
(1.3)
Неможливо розібрати вираз (невідома помилка): x\geqslant 0
(1.4)
тут
Неможливо розібрати вираз (невідома помилка): c=\left \{ c_j \right \} , Неможливо розібрати вираз (невідома помилка): \ j = 1,...n,
Неможливо розібрати вираз (невідома помилка): b=\left \{ b_i \right \} , Неможливо розібрати вираз (невідома помилка): \ i = 1,...m,
Неможливо розібрати вираз (невідома помилка): b^{(1)} =\left \{ b^{(1)}_k \right \} , Неможливо розібрати вираз (невідома помилка): \ k = 1,...m_1,
Неможливо розібрати вираз (невідома помилка): A =\left \| \ a_ij^{(1)} \right \| , Неможливо розібрати вираз (невідома помилка): \ i = 1,...m,
- Неможливо розібрати вираз (невідома помилка): \ j = 1,...n,
- Неможливо розібрати вираз (невідома помилка): A^{(1)} =\left \| \ a_kj^{(1)} \right \|
, Неможливо розібрати вираз (невідома помилка): \ k = 1,...m_1,
- Неможливо розібрати вираз (невідома помилка): \ j = 1,...n,
В випадку, коли елементи матриці Неможливо розібрати вираз (невідома помилка): \ A = A(\omega)
і векторів Неможливо розібрати вираз (невідома помилка): \ b = b(\omega) і Неможливо розібрати вираз (невідома помилка): \ c = c(\omega) - випадкові величини і рішення Неможливо розібрати вираз (невідома помилка): \ x слід прийняти спостереження реалізації випадкових параметрів умов, постановка і порядок рішення задачі повинні бути уточнені.
Уявімо собі процес вирішення задачі (1.1) - (1.4) в такий спосіб. Виберемо спочатку (на першому етапі) вектор, що задовольняє умови (1.3) - (1.4). Потім зафіксуємо реалізацію Неможливо розібрати вираз (невідома помилка): \widehat\omega
випадкової події і відповідні йому значення елементів Неможливо розібрати вираз (невідома помилка): \ A(\widehat\omega) i Неможливо розібрати вираз (невідома помилка): \ b(\widehat\omega)
, оцінимо невязку Неможливо розібрати вираз (невідома помилка): \ b(\widehat\omega)- A(\widehat\omega)*(\widehat x)
в умовах (1.2) задачі і обчислимо вектор Неможливо розібрати вираз (невідома помилка): y\geqslant 0 компенсуючий невязки у відмінності із співвідношенням
Неможливо розібрати вираз (невідома помилка): \ By= b(\widehat\omega)- A(\widehat\omega) *(\widehat x)
Неможливо розібрати вираз (невідома помилка): B =\left \| \ b_{il} \right \|
, Неможливо розібрати вираз (невідома помилка): \ i = 1,...m,
- Неможливо розібрати вираз (невідома помилка): \ l = 1,...n_1,
- - матриця компенсації. У загальному випадку елементи В випадкові. Якщо задача (21.1)-(21.4) інтерпритується в термінах планування виробництва. а А - матриця основних технологічних способів, то В - матриця аварійних технологічних способів, що визначають можливі шляхи компенсації виявлених відхилів. Передбачається, що реалізація Неможливо розібрати вираз (невідома помилка): \ \omega
не залежить від вибору Неможливо розібрати вираз (невідома помилка): \ (\widehat x)
. За порушення умов задачі встановлюється штраф, який залежить від величин складових вектора Неможливо розібрати вираз (невідома помилка): y , компенсуючого невязки. Природно характеризувати штраф величиною Неможливо розібрати вираз (невідома помилка): qy , де Неможливо розібрати вираз (невідома помилка): q\geqslant 0 , взагалі кажучи, випадковий Неможливо розібрати вираз (невідома помилка): n_1
- мірний вектор.
Вектор Неможливо розібрати вираз (невідома помилка): y
компенсуючий невязки, може бути вибраний багатьма способами. Підпорядкуємо вибір у наступній додатковій вимозі. Будемо вибирати складові Неможливо розібрати вираз (невідома помилка): y таким чином, щоб забезпечити мінімальний штраф за компенсацію невязок умов задачі, що визначаються попереднім планом. Іншими словами на другому етапі завдання
Неможливо розібрати вираз (невідома помилка): qy\rightarrow min
(1.5)
Неможливо розібрати вираз (невідома помилка): \ By=b-Ax
(1.6)
Неможливо розібрати вираз (невідома помилка): y\geqslant 0
(1.7)
Обидва етапи розв'язка задачі можуть бути зведені в один. Отримаємо постановку, яка носить назву двохетапної задачі лінійного стохастичного програмування:
Неможливо розібрати вираз (невідома помилка): \min_x M_\omega\{c(\omega)x+\min_y[q(\omega)y|B(\omega)y=b(\omega)-A(\omega)x, y\geqslant0]\} , (1.8)
Неможливо розібрати вираз (невідома помилка): \ A^{(1)}x = b^{(1)} , (1.9)
Неможливо розібрати вираз (невідома помилка): x\geqslant0 . (1.10)
Таким чином, рішення двоетапної стохастичної задачі складається з двох векторів: детермінованого Неможливо розібрати вираз (невідома помилка): n
- мірного вектора х, що визначає попередній план, і випадкового Неможливо розібрати вираз (невідома помилка): n - мірного вектора Неможливо розібрати вираз (невідома помилка): \ y = y(\omega) , визнавчального план компенсації невязок .
Для вирішення завдання досить обчислити оптимальний попередній план Неможливо розібрати вираз (невідома помилка): \ x . Після реалізації випадкової події Неможливо розібрати вираз (невідома помилка): \omega , тобто після реалізації випадкових параметрів умов задачі, відповідна реалізація Неможливо розібрати вираз (невідома помилка): \ y
оптимального плану - компенсації обчислюється як рішення задачі лінійного програмування (1.5) - (1.7).
При перспективному плануванні слід враховувати можливість випадкових збурень системи.
Перспективний план повинен володіти свого роду стійкістю по відношенню до зміни вихідних даних, які можуть відбуватися у міру його впровадження.
Затрати на корекцію плану повинні бути якомога меншими. Звідси доцільність використання для перспективного плунвання схем двохетапного (або багатоетапного) стохастичного програмування, малочутливих до зміни параметрів умов задачі.
Виконала: Татьяненко Марина Олександрівна. Редагував: Білобабченко Анатолій Сергійович
