Відмінності між версіями «Область визначення двохетапної задачі з випадковим вектором обмежень.»

Матеріал з Вікі ЦДУ
Перейти до: навігація, пошук
 
(не показані 3 проміжні версії цього учасника)
Рядок 1: Рядок 1:
−
Розглянемо двоетапну задачу стохастичного програмування:
+
<font size=3> Розглянемо двохетапну задачу стохастичного програмування: </font>
  
−
<math> \min_x m_{\infty}\{cx+P(x,A,b)\} </math>
+
<font size=3> <math> \min_x m_{\omega}\{cx+P(x,A,b)\} </math>, </font>
  
−
<math> A^{(1)}x=b^{(1)} </math>
+
<font size=3> <math> A^{(1)}x=b^{(1)} </math>, </font>
  
−
<math> x \geqslant 0 </math>
+
<font size=3> <math> x \geqslant 0 </math>. </font>
  
−
Нехай випадковими є тільки складові вектора обмежень b. Всі інші параметри умов задачі – детерміновані.  
+
<font size=3> Нехай випадковими є тільки складові вектора обмежень <math> b </math>. Всі інші параметри умов задачі – детерміновані. </font>
  
−
Єдине припущення, з яким ми пов’язуємо вибір випадкового вектора <math>b(\omega)</math>, заключається в тому, що його розподіл не повинен залежати від вибору попереднього плану x.  
+
<font size=3> Єдине припущення, з яким ми пов’язуємо вибір випадкового вектора <math>b(\omega)</math>, полягає в тому, що його розподіл не повинен залежати від вибору попереднього плану <math> x </math>. </font>
  
−
Згідно раніше розглянутої теореми, для загальної двоетапної задачі множина K попередніх планів – опукла. Для розглянутого часткового випадку можна довести більш сильне твердження. Виявляється, що в цьому випадку множина K не тільки опукла, але й багатогранна. Більше того, можна явно записати систему лінійних нерівностей, що визначають множину К.
+
<font size=3> Згідно раніше розглянутої теореми [[Область визначення планів першого етапу.|(2.2)]], для загальної двохетапної задачі множина <math> K </math> попередніх планів – опукла. Для розглянутого часткового випадку можна довести більш сильне твердження. Виявляється, що в цьому випадку множина <math> K </math> не тільки опукла, але й багатогранна. Більше того, можна явно записати систему лінійних нерівностей, що визначають множину <math> K </math>. </font>
  
−
Нагадаємо деякі поняття, що необхідні для наступних побудов.
+
<font size=3> Нагадаємо деякі поняття, що необхідні для наступних побудов. </font>
  
−
Як відомо, опуклий багатогранний Конус С може бути представлений або як невід’ємна комбінація скінченного числа векторів, або як перетин скінченного числа півпросторів.
+
<font size=3> Як відомо, опуклий багатогранний Конус <math> C </math> може бути представлений або як невід’ємна комбінація скінченного числа векторів, або як перетин скінченного числа півпросторів. </font>
  
−
Еквівалентність двох визначень опуклого багатогранного конуса С використовується для приведення у відповідність кожній матриці В так звану полярну матрицю <math> B^*</math>.
+
<font size=3> Еквівалентність двох визначень опуклого багатогранного конуса <math> C </math> використовується для приведення у відповідність кожній матриці <math> B </math> так звану полярну матрицю <math> B^*</math>. </font>
  
−
Матриця <math> B^*</math> (розмірності <math>l x m</math>) називається полярною до матриці В (розмірності <math>m x n_1</math>), якщо <math> B^*</math> — матриця з мінімальним числом рядків, що задовольняють умові:
+
<font size=3> Матриця <math> B^*</math> (розмірності <math>l \times m</math>) називається ''полярною'' до матриці <math> B </math> (розмірності <math>m \times n_1</math>), якщо <math> B^*</math> — матриця з мінімальним числом рядків, що задовольняють умові: </font>
  
−
<math> C=\{t|\exist y\geqslant 0, t=By\}=\{t|B^* t\geqslant 0\} </math>
+
<font size=3> <math> C=\{t|\exist y\geqslant 0, t=By\}=\{t|B^* t\geqslant 0\} </math>. </font>
  
−
Введемо множини:
+
<font size=3> Введемо множини: </font>
  
−
<math> N=\{\chi|\forall (\omega \in \Omega) \exist y \geqslant 0, By=b(\omega)-\chi\} </math>
+
<font size=3> <math> N=\{\chi|\forall (\omega \in \Omega) \exist y \geqslant 0, By=b(\omega)-\chi\} </math>, </font>
  
−
<math> N(\omega)=\{\chi| \exist y \geqslant 0, By=b(\omega)-\chi\} </math>
+
<font size=3> <math> N(\omega)=\{\chi| \exist y \geqslant 0, By=b(\omega)-\chi\} </math>. </font>
  
−
Зрозуміло, що  <math> N=\cap_{\omega \in \Omega}N(\omega) </math>
+
<font size=3> Зрозуміло, що  <math> N=\cap_{\omega \in \Omega}N(\omega) </math>. </font>
  
−
Раніше були введені множини:
+
<font size=3> Раніше (у попередніх пунктах) були введені множини: </font>
  
−
<math> K_2 =\{x|\forall (\omega \in \Omega) \exist y \geqslant 0, By=b(\omega)-A(\omega)x\} </math>
+
<font size=3> <math> K_2 =\{x|\forall (\omega \in \Omega) \exist y \geqslant 0, By=b(\omega)-A(\omega)x\} </math>, </font>
  
−
<math> K_2(\omega) =\{x| \exist y \geqslant 0, By=b(\omega)-A(\omega)x\} </math>
+
<font size=3> <math> K_2(\omega) =\{x| \exist y \geqslant 0, By=b(\omega)-A(\omega)x\} </math>. </font>
  
−
Ці множини пов'язані з множинами <math> N </math> і <math> N(\omega) </math> співвідношеннями:
+
<font size=3> Ці множини пов'язані з множинами <math> N </math> і <math> N(\omega) </math> співвідношеннями: </font>
  
−
<math> K_2=\{x|A(\omega)=\chi , \chi \in N\} </math>
+
<font size=3> <math> K_2=\{x|Ax=\chi , \chi \in N\} </math>, </font>
  
−
<math> K_2(\omega)=\{x|A(\omega)=\chi , \chi \in N(\omega)\} </math>
+
<font size=3> <math> K_2(\omega)=\{x|Ax=\chi , \chi \in N(\omega)\} </math>. </font>
  
−
В наступних трьох лемах сформульовані властивості введених множин, які будуть використані для доведення твердження про багатогранність опуклої множини K – області визначення попередніх планів двоетапної задачі.
+
<font size=3> В наступних трьох лемах сформульовані властивості введених множин, які будуть використані для доведення твердження про багатогранність опуклої множини <math> K </math> – області визначення попередніх планів двохетапної задачі. </font>
  
−
Лема 1. Якщо <math>N(\omega)</math> – опукла, багатогранна множина, то <math>K_2 (\omega) </math>– теж опукла багатогранна множина. Якщо <math>N</math> – опукла, багатогранна множина, то <math>K_2</math> – теж опукла багатогранна множина.
+
<font size=3> '''Лема 1.1.''' Якщо <math>N(\omega)</math> – опукла багатогранна множина, то <math>K_2 (\omega) </math> – теж опукла багатогранна множина. Якщо <math>N</math> – опукла, багатогранна множина, то <math>K_2</math> – теж опукла багатогранна множина. </font>
  
−
Лема 2. Множина <math>N(\omega) </math>може бути представлена у вигляді:
+
<font size=3> '''Лема 1.2.''' Множина <math>N(\omega) </math> може бути представлена у вигляді: </font>
  
−
<math>N(\omega)=\{\chi|B^* \chi \leqslant B^* b(\omega)\} </math>
+
<font size=3> <math>N(\omega)=\{\chi|B^* \chi \leqslant B^* b(\omega)\} </math>. </font>
  
−
Лема 3. Множина N є опуклою багатогранною множиною, що визначається системою лінійних нерівностей:
+
<font size=3> '''Лема 1.3.''' Множина <math>N</math> є опуклою багатогранною множиною, що визначається системою лінійних нерівностей: </font>
  
−
<math> B^* b(\omega) \leqslant\alpha_i^*,i=1,...,l </math>
+
<font size=3> <math> B_i^* \chi(\omega) \leqslant\alpha_i^*,i=1,...,l </math>. </font>
  
−
якщо для деякого <math> i,\alpha_i^*=-\infty </math>, множина N – порожня.
+
<font size=3> якщо для деякого <math> i,\alpha_i^*=-\infty </math>, множина <math>N</math> – порожня. </font>
  
−
Теорема 1. Множина K планів детермінованої задачі, що еквівалентна двоетапній задачі стохастичного програмування, в якій випадковим є тільки вектор обмежень b, є опуклою багатогранною множиною.  
+
<font size=3> '''Теорема 1.1.''' Множина <math>K</math>  планів детермінованої задачі, що еквівалентна двоетапній задачі стохастичного програмування, в якій випадковим є тільки вектор обмежень <math>b</math> , є опуклою багатогранною множиною. </font>
  
−
Доведення: Множина <math> K=K_1\cap K_2</math>
+
<font size=3> ''Доведення:'' Множина <math> K=K_1\cap K_2</math>. </font>
  
−
<math> K_1=\{x|A^{(1)}x=b^{(1)},x \geqslant 0\}</math> – випукла многогранна множина. Відповідно до лем 1 і 3 <math> K_2=\{x|B^* Ax\leqslant \alpha^*\} </math> – теж є випуклою многогранною множиною.  
+
<font size=3> <math> K_1=\{x|A^{(1)}x=b^{(1)},x \geqslant 0\}</math> – опукла багатогранна множина. Відповідно до лем 1.1 і 1.3 <math> K_2=\{x|B^* Ax\leqslant \alpha^*\} </math> – теж є опуклою багатогранною множиною. </font>
  
−
Звідси випливає, що K – випукла многогранна множина.
+
<font size=3> Відповідно, <math>K</math> – опукла багатогранна множина виду  </font>
  
−
Значить, K – випукла многогранна множина виду
+
<font size=3> <math>A^{(1)}x=b^{(1)}, Sx\leqslant \alpha^*, x\geqslant 0</math>, де <math>S=B^* A</math> </font>
  
−
<math>A^{(1)}x=b^{(1)}, Sx\leqslant \alpha^*, x\geqslant 0, S=B^* A</math>.
+
<font size=3> ''Теорема доведена.''  </font>
  
−
Теорема доведена.  
+
<font size=3> Дана теорема має в основному теоретичний інтерес, оскільки немає відносно простих способів побудови матриці <math>B^*</math>, полярної до матриці <math>B</math>. </font>
  
−
Дана теорема має в основному теоретичний інтерес, оскільки немає відносно простих способів побудови матриці B*, полярної до матриці B.
 
  
  
 +
<font size=3> Розглянемо тепер деякі властивості двоетапної задачі, в якій випадковим є вектор <math>b=b(\omega)</math>.  </font>
  
−
Розглянемо тепер деякі властивості двоетапної задачі, в якій випадковим є вектор <math>b=b(\omega)</math>.
+
<font size=3> Згідно з вищерозглянутими твердженнями, задача, що розглядається, може бути записана у вигляді: </font>
  
−
Згідно з вищерозглянутими твердженнями, задача, що розглядається, може бути записана у вигляді:
+
<font size=3> <math> \min_x Q(x)=\min_x \{cx+MP(x,b)\}</math>    (1.1)</font>
  
−
<math> \min_x Q(x)=\min+x \{cx+MP(x,b)\}   (1)</math>
+
<font size=3> <math>A^{(1)}x=b^{(1)}</math>, (1.2)</font>
  
−
<math>A^{(1)}=b^{(1)}</math>
+
<font size=3> <math>Sx\leqslant \alpha^*</math>, (1.3) </font>
  
−
<math>Sx\leqslant \alpha^*</math>
+
<font size=3> <math> x\geqslant 0  </math>, (1.4) </font>
  
−
<math> x\geqslant 0  </math>
+
<font size=3> де <math> P(x,b)=\min_{y\in Y(x,b)} qy </math>, (1.5) </font>
  
−
де <math> P(x,b)=\min_{y\in Y(x,b)} qy </math>
+
<font size=3> <math> Y(x,b)=\{y|By=b-Ax, y\geqslant 0\}</math> (1.6) </font>
  
−
<math> Y(x,b)=\{y|By=b-Ax, y\geqslant 0\}</math>
+
<font size=3> для заданих <math>x</math> і <math>b</math>.  </font>
  
−
для заданих х і b.
+
<font size=3> Має місце наступна лема: </font>
  
−
Має місце наступна лема:
+
<font size=3> '''Лема 1.4.''' Нехай <math>x^0</math> – розв’язок задачі опуклого програмування (1.1)-(1.4). Тоді <math>x^0</math> є також розв’язком наступної задачі лінійного програмування: </font>
  
−
Лема 4. Нехай <math>x^0</math> – розв’язок задачі опуклого програмування (1)-(4). Тоді <math>x^0</math> є розв’язком наступної задачі лінійного програмування:
+
<font size=3> <math> cx\rightarrow \min  </math>, (1.7) </font>
  
−
<math> cx\rightarrow \min </math>
+
<font size=3> <math> A^{(1)}x=b^{(1)} </math>, (1.8) </font>
  
−
<math> A^{(1)}x=b^{(1)}  </math>
+
<font size=3> <math> Sx\leqslant \alpha^*  </math>, (1.9) </font>
  
−
<math> Sx\leqslant \alpha^* </math>
+
<font size=3> <math> Ax=Ax^0 </math>, (1.10) </font>
  
−
<math> Ax=Ax^0  </math>
+
<font size=3> <math> x\geqslant 0  </math>. (1.11) </font>
  
−
<math> x\geqslant 0  </math>
+
<font size=3> '''Теорема 1.2.''' Кожна розв’язна задача вигляду (1.1)-(1.4) має розв’язок <math>x^*</math>, в якому додатні (базисні) складові вектора <math>x^*</math> відповідають лінійно незалежним стовпчикам матриці: </font>
  
−
Теорема 2. Кожна розв’язна задача вигляду (1)-(4) має розв’язок x*, в якому додатні (базисні) складові вектора x* відповідають лінійно незалежним стовпчикам матриці:
+
<font size=3> <math>\begin{pmatrix} A^{(1)} \\ S \\ A \end{pmatrix} </math> </font>
  
−
<math>\begin{pmatrix} A^{(1)} \\ S \\ A \end{pmatrix} </math>
+
<font size=3> ''Доведення:'' Нехай <math> x^0 </math> – розв’язок задачі (1.1)-(1.4). Згідно з лемою 1.4, вектор <math> x^0 </math> також є розв’язком задачі (1.7)-(1.11). Також легко бачити, що оптимальний план <math> \tilde{x} </math> задачі (1.7)-(1.11) є також оптимальним планом задачі (1.1)-(1.4). Дійсно, з того, що <math> A\tilde{x}=Ax^0 </math> випливає, що <math> P(\tilde{x},b(\omega))=P(x^0,b(\omega))</math> для всіх <math> \omega\in\Omega </math>. А за цих умов мінімум <math>Q(x)</math> досягіється при <math> c\tilde{x}=cx^0 </math>.  </font>
  
−
Доведення: Нехай <math> x^0 </math> – розв’язок задачі (1)-(4). Згідно з лемою 4, вектор <math> x^0 </math> є розв’язком задачі (7)-(11). Також легко бачити, що оптимальний план <math> \tilde{x} </math> задачі (7)-(11) є оптимальним планом задачі (1)-(4). Дійсно, з того, що <math> A\tilde{x}=Ax^0 </math> випливає, що <math> P(\tilde{x},b(\omega))=P(x^0,b(\omega))</math> для всіх <math> \omega\in\Omega </math>. А за цих умов мінімум <math>Q(x)</math> досягіється при <math> c\tilde{x}=cx^0 </math>.
+
<font size=3> Оскільки задача лінійного програмування (1.7)-(1.11) має оптимальний план <math> x^0 </math>, вона повинна мати і опорний оптимальний план. Позначимо його через <math> x^* </math>. Тоді базисним компонентам вектора <math> x^* </math> відповідають лінійно незалежні стовбці матриці </font>
  
−
Оскільки задача лінійного програмування (7)-(11) має оптимальний план x^0, вона повинна мати і опорний оптимальний план. Позначимо його через x*. Тоді базисним компонентам вектора x* відповідають лінійно незалежні стовбці матриці
+
<font size=3> <math>\begin{pmatrix} A^{(1)} \\ S \\ A \end{pmatrix} </math> </font>
  
−
<math>\begin{pmatrix} A^{(1)} \\ S \\ A \end{pmatrix} </math>
+
<font size=3> і <math> x^* </math> – розв’язок задачі (1.1)-(1.4). </font>
  
−
і x* – розв’язок задачі (1)-(4).
+
<font size=3> ''Теорема доведена.'' </font>
  
−
Теорема доведена.
+
<font size=3> '''Наслідок 1.1.''' Кожна розв’язна задача вигляду (1.1)-(1.4) має розв’язок <math> x^* </math>, в якому базисні складові вектора <math> x^* </math> відповідають лінійно незалежним стовпчикам матриці: </font>
  
−
Наслідок 1. Кожна розв’язна задача вигляду (1)-(4) має розв’язок x*, в якому базисні складові вектора x* відповідають лінійно незалежним стовпчикам матриці:
+
<font size=3> <math>\begin{pmatrix} A^{(1)} \\ A \end{pmatrix} </math> </font>
  
−
<math>\begin{pmatrix} A^{(1)} \\ A \end{pmatrix} </math>
+
<font size=3> Це твердження слідує з теореми 2, а також через те, що <math> S=B^* A</math>.  </font>
  
−
Це твердження слідує з теореми 2 через те, що <math> S=B^* A</math>.  
+
<font size=3> '''Наслідок 1.2.''' Нехай ранг матриці А дорівнює <math> r (\leqslant m)</math> і задача (1.1)-(1.4) розв’язна. Тоді ця задача має розв’язок <math> x^* </math>, в якому не більше, <math> m+r </math> складових вектора <math> x^* </math> є додатними. </font>
  
−
Наслідок 2. Нехай ранг матриці А дорівнює <math> r (\leqslant m)</math> і задача (1)-(4) розв’язна. Тоді ця задача має розв’язок x*, в якому не більше, m+r складових вектора x* додатні.  
+
<font size=3> Це твердження слідує з наслідку 1.1 [1, c. 168-171]. </font>
  
−
Це твердження слідує з наслідку 1.
+
 
 +
 
 +
==Список використаних джерел==
 +
1. Юдин Д. Б. Математические методы управления в условиях неполной информации. / Юдин Д. Б. М: «Сов. радио», 1974. – 400 с.
  
  
  
 
Виконав: [[Користувач:Олійник_Артем|Олійник Артем Олександрович]]
 
Виконав: [[Користувач:Олійник_Артем|Олійник Артем Олександрович]]
 +
 +
Доповнювала: [[Користувач:Іванченко Дар’я|Іванченко Дар’я]]

Поточна версія на 22:47, 3 червня 2017

Розглянемо двохетапну задачу стохастичного програмування:

Неможливо розібрати вираз (невідома помилка): \min_x m_{\omega}\{cx+P(x,A,b)\} ,

Неможливо розібрати вираз (невідома помилка): A^{(1)}x=b^{(1)} ,

Неможливо розібрати вираз (невідома помилка): x \geqslant 0 .

Нехай випадковими є тільки складові вектора обмежень Неможливо розібрати вираз (невідома помилка): b . Всі інші параметри умов задачі – детерміновані.

Єдине припущення, з яким ми пов’язуємо вибір випадкового вектора Неможливо розібрати вираз (невідома помилка): b(\omega) , полягає в тому, що його розподіл не повинен залежати від вибору попереднього плану Неможливо розібрати вираз (невідома помилка): x .

Згідно раніше розглянутої теореми (2.2), для загальної двохетапної задачі множина Неможливо розібрати вираз (невідома помилка): K 

попередніх планів – опукла. Для розглянутого часткового випадку можна довести більш сильне твердження. Виявляється, що в цьому випадку множина Неможливо розібрати вираз (невідома помилка):  K 
не тільки опукла, але й багатогранна. Більше того, можна явно записати систему лінійних нерівностей, що визначають множину Неможливо розібрати вираз (невідома помилка):  K

.

Нагадаємо деякі поняття, що необхідні для наступних побудов.

Як відомо, опуклий багатогранний Конус Неможливо розібрати вираз (невідома помилка): C 

може бути представлений або як невід’ємна комбінація скінченного числа векторів, або як перетин скінченного числа півпросторів.

Еквівалентність двох визначень опуклого багатогранного конуса Неможливо розібрати вираз (невідома помилка): C 

використовується для приведення у відповідність кожній матриці Неможливо розібрати вираз (невідома помилка):  B 
так звану полярну матрицю Неможливо розібрати вираз (невідома помилка):  B^*

.

Матриця Неможливо розібрати вираз (невідома помилка): B^* 

(розмірності Неможливо розібрати вираз (невідома помилка): l \times m

) називається полярною до матриці Неможливо розібрати вираз (невідома помилка): B 

(розмірності Неможливо розібрати вираз (невідома помилка): m \times 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|Ax=\chi , \chi \in N\} ,

Неможливо розібрати вираз (невідома помилка): K_2(\omega)=\{x|Ax=\chi , \chi \in N(\omega)\} .

В наступних трьох лемах сформульовані властивості введених множин, які будуть використані для доведення твердження про багатогранність опуклої множини Неможливо розібрати вираз (невідома помилка): K 

– області визначення попередніх планів двохетапної задачі.

Лема 1.1. Якщо Неможливо розібрати вираз (невідома помилка): N(\omega) 

– опукла багатогранна множина, то Неможливо розібрати вираз (невідома помилка): K_2 (\omega) 
– теж опукла багатогранна множина. Якщо Неможливо розібрати вираз (невідома помилка): N
– опукла, багатогранна множина, то Неможливо розібрати вираз (невідома помилка): K_2
– теж опукла багатогранна множина.

Лема 1.2. Множина Неможливо розібрати вираз (невідома помилка): N(\omega) 

може бути представлена у вигляді:

Неможливо розібрати вираз (невідома помилка): N(\omega)=\{\chi|B^* \chi \leqslant B^* b(\omega)\} .

Лема 1.3. Множина Неможливо розібрати вираз (невідома помилка): N 

є опуклою багатогранною множиною, що визначається системою лінійних нерівностей:

Неможливо розібрати вираз (невідома помилка): B_i^* \chi(\omega) \leqslant\alpha_i^*,i=1,...,l .

якщо для деякого Неможливо розібрати вираз (невідома помилка): i,\alpha_i^*=-\infty , множина Неможливо розібрати вираз (невідома помилка): N 

– порожня.

Теорема 1.1. Множина Неможливо розібрати вираз (невідома помилка): K 

 планів детермінованої задачі, що еквівалентна двоетапній задачі стохастичного програмування, в якій випадковим є тільки вектор обмежень Неможливо розібрати вираз (невідома помилка): b
, є опуклою багатогранною множиною.

Доведення: Множина Неможливо розібрати вираз (невідома помилка): K=K_1\cap K_2 .

Неможливо розібрати вираз (невідома помилка): K_1=\{x|A^{(1)}x=b^{(1)},x \geqslant 0\} 

– опукла багатогранна множина. Відповідно до лем 1.1 і 1.3 Неможливо розібрати вираз (невідома помилка):  K_2=\{x|B^* Ax\leqslant \alpha^*\} 
– теж є опуклою багатогранною множиною.

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

– опукла багатогранна множина виду

Неможливо розібрати вираз (невідома помилка): A^{(1)}x=b^{(1)}, Sx\leqslant \alpha^*, x\geqslant 0 , де Неможливо розібрати вираз (невідома помилка): S=B^* A

Теорема доведена.

Дана теорема має в основному теоретичний інтерес, оскільки немає відносно простих способів побудови матриці Неможливо розібрати вираз (невідома помилка): B^* , полярної до матриці Неможливо розібрати вираз (невідома помилка): B .


Розглянемо тепер деякі властивості двоетапної задачі, в якій випадковим є вектор Неможливо розібрати вираз (невідома помилка): b=b(\omega) .

Згідно з вищерозглянутими твердженнями, задача, що розглядається, може бути записана у вигляді:

Неможливо розібрати вираз (невідома помилка): \min_x Q(x)=\min_x \{cx+MP(x,b)\} 

   (1.1)

Неможливо розібрати вираз (невідома помилка): A^{(1)}x=b^{(1)} , (1.2)

Неможливо розібрати вираз (невідома помилка): Sx\leqslant \alpha^* , (1.3)

Неможливо розібрати вираз (невідома помилка): x\geqslant 0 , (1.4)

де Неможливо розібрати вираз (невідома помилка): P(x,b)=\min_{y\in Y(x,b)} qy , (1.5)

Неможливо розібрати вираз (невідома помилка): Y(x,b)=\{y|By=b-Ax, y\geqslant 0\} 

(1.6)

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

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

.

Має місце наступна лема:

Лема 1.4. Нехай Неможливо розібрати вираз (невідома помилка): x^0 

– розв’язок задачі опуклого програмування (1.1)-(1.4). Тоді Неможливо розібрати вираз (невідома помилка): x^0
є також розв’язком наступної задачі лінійного програмування:

Неможливо розібрати вираз (невідома помилка): cx\rightarrow \min , (1.7)

Неможливо розібрати вираз (невідома помилка): A^{(1)}x=b^{(1)} , (1.8)

Неможливо розібрати вираз (невідома помилка): Sx\leqslant \alpha^* , (1.9)

Неможливо розібрати вираз (невідома помилка): Ax=Ax^0 , (1.10)

Неможливо розібрати вираз (невідома помилка): x\geqslant 0 . (1.11)

Теорема 1.2. Кожна розв’язна задача вигляду (1.1)-(1.4) має розв’язок Неможливо розібрати вираз (невідома помилка): x^* , в якому додатні (базисні) складові вектора Неможливо розібрати вираз (невідома помилка): x^* 

відповідають лінійно незалежним стовпчикам матриці:

Неможливо розібрати вираз (невідома помилка): \begin{pmatrix} A^{(1)} \\ S \\ A \end{pmatrix}

Доведення: Нехай Неможливо розібрати вираз (невідома помилка): x^0 

– розв’язок задачі (1.1)-(1.4). Згідно з лемою 1.4, вектор Неможливо розібрати вираз (невідома помилка):  x^0 
також є розв’язком задачі (1.7)-(1.11). Також легко бачити, що оптимальний план Неможливо розібрати вираз (невідома помилка):  \tilde{x} 
задачі (1.7)-(1.11) є також оптимальним планом задачі (1.1)-(1.4). Дійсно, з того, що Неможливо розібрати вираз (невідома помилка):  A\tilde{x}=Ax^0 
випливає, що Неможливо розібрати вираз (невідома помилка):  P(\tilde{x},b(\omega))=P(x^0,b(\omega))
для всіх Неможливо розібрати вираз (невідома помилка):  \omega\in\Omega

. А за цих умов мінімум Неможливо розібрати вираз (невідома помилка): Q(x) 

досягіється при Неможливо розібрати вираз (невідома помилка):  c\tilde{x}=cx^0

.

Оскільки задача лінійного програмування (1.7)-(1.11) має оптимальний план Неможливо розібрати вираз (невідома помилка): x^0 , вона повинна мати і опорний оптимальний план. Позначимо його через Неможливо розібрати вираз (невідома помилка): x^* . Тоді базисним компонентам вектора Неможливо розібрати вираз (невідома помилка): x^* 

відповідають лінійно незалежні стовбці матриці

Неможливо розібрати вираз (невідома помилка): \begin{pmatrix} A^{(1)} \\ S \\ A \end{pmatrix}

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

– розв’язок задачі (1.1)-(1.4).

Теорема доведена.

Наслідок 1.1. Кожна розв’язна задача вигляду (1.1)-(1.4) має розв’язок Неможливо розібрати вираз (невідома помилка): x^* , в якому базисні складові вектора Неможливо розібрати вираз (невідома помилка): x^* 

відповідають лінійно незалежним стовпчикам матриці:

Неможливо розібрати вираз (невідома помилка): \begin{pmatrix} A^{(1)} \\ A \end{pmatrix}

Це твердження слідує з теореми 2, а також через те, що Неможливо розібрати вираз (невідома помилка): S=B^* A .

Наслідок 1.2. Нехай ранг матриці А дорівнює Неможливо розібрати вираз (невідома помилка): r (\leqslant m) 

і задача (1.1)-(1.4) розв’язна. Тоді ця задача має розв’язок Неможливо розібрати вираз (невідома помилка):  x^*

, в якому не більше, Неможливо розібрати вираз (невідома помилка): m+r 

складових вектора Неможливо розібрати вираз (невідома помилка):  x^* 
є додатними.

Це твердження слідує з наслідку 1.1 [1, c. 168-171].


Список використаних джерел

1. Юдин Д. Б. Математические методы управления в условиях неполной информации. / Юдин Д. Б. М: «Сов. радио», 1974. – 400 с.


Виконав: Олійник Артем Олександрович

Доповнювала: Іванченко Дар’я

Отримано з https://wiki.cusu.edu.ua/index.php?title=Область_визначення_двохетапної_задачі_з_випадковим_вектором_обмежень.&oldid=284501