Відмінності між версіями «Область визначення двохетапної задачі з випадковим вектором обмежень.»
(Створена сторінка: Розглянемо двоетапну задачу стохастичного програмування: <math> \min_x m_{\infty}\{cx+P(x,A,b)\} </math> <math...) |
|||
| Рядок 21: | Рядок 21: | ||
Матриця <math> B^*</math> (розмірності <math>l x m</math>) називається полярною до матриці В (розмірності <math>m x n_1</math>), якщо <math> B^*</math> — матриця з мінімальним числом рядків, що задовольняють умові: | Матриця <math> B^*</math> (розмірності <math>l x m</math>) називається полярною до матриці В (розмірності <math>m x n_1</math>), якщо <math> B^*</math> — матриця з мінімальним числом рядків, що задовольняють умові: | ||
| + | <math> C=\{t|\exist y\geqslant 0, t=By\}=\{t|B^* t\geqslant 0\} </math> | ||
| + | Введемо множини: | ||
| + | <math> N=\{\chi|\forall (\omega \in \Omega) \exist y \geqslant 0, By=b(\omega)-\chi\} </math> | ||
| + | |||
| + | <math> N(\omega)=\{\chi| \exist y \geqslant 0, By=b(\omega)-\chi\} </math> | ||
| + | |||
| + | Зрозуміло, що <math> N=\cap_{\omega \in \Omega}N(\omega) </math> | ||
| + | |||
| + | Раніше були введені множини: | ||
| + | |||
| + | <math> K_2 =\{x|\forall (\omega \in \Omega) \exist y \geqslant 0, By=b(\omega)-A(\omega)x\} </math> | ||
| + | |||
| + | <math> K_2(\omega) =\{x| \exist y \geqslant 0, By=b(\omega)-A(\omega)x\} </math> | ||
| + | |||
| + | Ці множини пов'язані з множинами <math> N </math> і <math> N(\omega) </math> співвідношеннями: | ||
| + | |||
| + | <math> K_2=\{x|A(\omega)=\chi , \chi \in N\} </math> | ||
| + | |||
| + | <math> K_2(\omega)=\{x|A(\omega)=\chi , \chi \in N(\omega)\} </math> | ||
| + | |||
| + | В наступних трьох лемах сформульовані властивості введених множин, які будуть використані для доведення твердження про багатогранність опуклої множини K – області визначення попередніх планів двоетапної задачі. | ||
| + | |||
| + | Лема 1. Якщо <math>N(\omega)</math> – опукла, багатогранна множина, то <math>K_2 (\omega) </math>– теж опукла багатогранна множина. Якщо <math>N</math> – опукла, багатогранна множина, то <math>K_2</math> – теж опукла багатогранна множина. | ||
| + | |||
| + | Лема 2. Множина <math>N(\omega) </math>може бути представлена у вигляді: | ||
| + | |||
| + | <math>N(\omega)=\{\chi|B^* \chi \leqslant B^* b(\omega)\} </math> | ||
| + | |||
| + | Лема 3. Множина N є опуклою багатогранною множиною, що визначається системою лінійних нерівностей: | ||
| + | |||
| + | <math> B^* b(\omega) \leqslant\alpha_i^*,i=1,...,l </math> | ||
| + | |||
| + | якщо для деякого <math> i,\alpha_i^*=-\infty </math>, множина N – порожня. | ||
| + | |||
| + | Теорема 1. Множина K планів детермінованої задачі, що еквівалентна двоетапній задачі стохастичного програмування, в якій випадковим є тільки вектор обмежень b, є опуклою багатогранною множиною. | ||
| + | |||
| + | Доведення: Множина <math> K=K_1\cap K_2</math> | ||
| + | |||
| + | <math> K_1=\{x|A^{(1)}x=b^{(1)},x \geqslant 0\}</math> – випукла многогранна множина. Відповідно до лем 1 і 3 <math> K_2=\{x|B^* Ax\leqslant \alpha^*|] </math> – теж є випуклою многогранною множиною. | ||
| + | |||
| + | Звідси випливає, що K – випукла многогранна множина. | ||
| + | |||
| + | Значить, K – випукла многогранна множина виду | ||
| + | |||
| + | <math>A^{(1)}x=b^{(1)}, Sx\leqslant \alpha^*, x\geqslant 0, S=B^* A</math>. | ||
| + | |||
| + | Теорема доведена. | ||
| + | |||
| + | Дана теорема має в основному теоретичний інтерес, оскільки немає відносно простих способів побудови матриці B*, полярної до матриці B. | ||
| + | |||
| + | |||
| + | |||
| + | Розглянемо тепер деякі властивості двоетапної задачі, в якій випадковим є вектор <math>b=b(\omega)</math>. | ||
| + | |||
| + | Згідно з вищерозглянутими твердженнями, задача, що розглядається, може бути записана у вигляді: | ||
Виконав: [[Користувач:Олійник_Артем|Олійник Артем Олександрович]] | Виконав: [[Користувач:Олійник_Артем|Олійник Артем Олександрович]] | ||
Версія за 23:05, 12 квітня 2013
Розглянемо двоетапну задачу стохастичного програмування:
Неможливо розібрати вираз (невідома помилка): \min_x m_{\infty}\{cx+P(x,A,b)\}
Неможливо розібрати вираз (невідома помилка): A^{(1)}x=b^{(1)}
Неможливо розібрати вираз (невідома помилка): x \geqslant 0
Нехай випадковими є тільки складові вектора обмежень b. Всі інші параметри умов задачі – детерміновані.
Єдине припущення, з яким ми пов’язуємо вибір випадкового вектора Неможливо розібрати вираз (невідома помилка): b(\omega) , заключається в тому, що його розподіл не повинен залежати від вибору попереднього плану x.
Згідно раніше розглянутої теореми, для загальної двоетапної задачі множина K попередніх планів – опукла. Для розглянутого часткового випадку можна довести більш сильне твердження. Виявляється, що в цьому випадку множина K не тільки опукла, але й багатогранна. Більше того, можна явно записати систему лінійних нерівностей, що визначають множину К.
Нагадаємо деякі поняття, що необхідні для наступних побудов.
Як відомо, опуклий багатогранний Конус С може бути представлений або як невід’ємна комбінація скінченного числа векторів, або як перетин скінченного числа півпросторів.
Еквівалентність двох визначень опуклого багатогранного конуса С використовується для приведення у відповідність кожній матриці В так звану полярну матрицю Неможливо розібрати вираз (невідома помилка): B^* .
Матриця Неможливо розібрати вираз (невідома помилка): B^*
(розмірності Неможливо розібрати вираз (невідома помилка): l x m
) називається полярною до матриці В (розмірності Неможливо розібрати вираз (невідома помилка): m x n_1 ), якщо Неможливо розібрати вираз (невідома помилка): B^*
— матриця з мінімальним числом рядків, що задовольняють умові:
Неможливо розібрати вираз (невідома помилка): C=\{t|\exist y\geqslant 0, t=By\}=\{t|B^* t\geqslant 0\}
Введемо множини:
Неможливо розібрати вираз (невідома помилка): N=\{\chi|\forall (\omega \in \Omega) \exist y \geqslant 0, By=b(\omega)-\chi\}
Неможливо розібрати вираз (невідома помилка): N(\omega)=\{\chi| \exist y \geqslant 0, By=b(\omega)-\chi\}
Зрозуміло, що Неможливо розібрати вираз (невідома помилка): N=\cap_{\omega \in \Omega}N(\omega)
Раніше були введені множини:
Неможливо розібрати вираз (невідома помилка): K_2 =\{x|\forall (\omega \in \Omega) \exist y \geqslant 0, By=b(\omega)-A(\omega)x\}
Неможливо розібрати вираз (невідома помилка): K_2(\omega) =\{x| \exist y \geqslant 0, By=b(\omega)-A(\omega)x\}
Ці множини пов'язані з множинами Неможливо розібрати вираз (невідома помилка): N
і Неможливо розібрати вираз (невідома помилка): N(\omega) співвідношеннями:
Неможливо розібрати вираз (невідома помилка): K_2=\{x|A(\omega)=\chi , \chi \in N\}
Неможливо розібрати вираз (невідома помилка): K_2(\omega)=\{x|A(\omega)=\chi , \chi \in N(\omega)\}
В наступних трьох лемах сформульовані властивості введених множин, які будуть використані для доведення твердження про багатогранність опуклої множини K – області визначення попередніх планів двоетапної задачі.
Лема 1. Якщо Неможливо розібрати вираз (невідома помилка): N(\omega)
– опукла, багатогранна множина, то Неможливо розібрати вираз (невідома помилка): K_2 (\omega)
– теж опукла багатогранна множина. Якщо Неможливо розібрати вираз (невідома помилка): N
– опукла, багатогранна множина, то Неможливо розібрати вираз (невідома помилка): K_2 – теж опукла багатогранна множина.
Лема 2. Множина Неможливо розібрати вираз (невідома помилка): N(\omega) може бути представлена у вигляді:
Неможливо розібрати вираз (невідома помилка): N(\omega)=\{\chi|B^* \chi \leqslant B^* b(\omega)\}
Лема 3. Множина N є опуклою багатогранною множиною, що визначається системою лінійних нерівностей:
Неможливо розібрати вираз (невідома помилка): B^* b(\omega) \leqslant\alpha_i^*,i=1,...,l
якщо для деякого Неможливо розібрати вираз (невідома помилка): i,\alpha_i^*=-\infty
, множина N – порожня.
Теорема 1. Множина K планів детермінованої задачі, що еквівалентна двоетапній задачі стохастичного програмування, в якій випадковим є тільки вектор обмежень b, є опуклою багатогранною множиною.
Доведення: Множина Неможливо розібрати вираз (невідома помилка): K=K_1\cap K_2
Неможливо розібрати вираз (невідома помилка): K_1=\{x|A^{(1)}x=b^{(1)},x \geqslant 0\}
– випукла многогранна множина. Відповідно до лем 1 і 3 Неможливо розібрати вираз (невідома помилка): K_2=\{x|B^* Ax\leqslant \alpha^*|]
– теж є випуклою многогранною множиною.
Звідси випливає, що K – випукла многогранна множина.
Значить, K – випукла многогранна множина виду
Неможливо розібрати вираз (невідома помилка): A^{(1)}x=b^{(1)}, Sx\leqslant \alpha^*, x\geqslant 0, S=B^* A .
Теорема доведена.
Дана теорема має в основному теоретичний інтерес, оскільки немає відносно простих способів побудови матриці B*, полярної до матриці B.
Розглянемо тепер деякі властивості двоетапної задачі, в якій випадковим є вектор Неможливо розібрати вираз (невідома помилка): b=b(\omega) .
Згідно з вищерозглянутими твердженнями, задача, що розглядається, може бути записана у вигляді:
Виконав: Олійник Артем Олександрович
