Відмінності між версіями «Умови оптимальності плану першого етапу задачі стохастичного програмування.»

Матеріал з Вікі ЦДУ
Перейти до: навігація, пошук
м
 
(не показані 11 проміжних версій 3 учасників)
Рядок 1: Рядок 1:
<font size=3> Сформулюємо необхідні умови оптимальності попереднього плану x двохетапної задачі. </font>
+
<font size=3> Сформулюємо необхідні умови оптимальності попереднього плану <math>x</math> двохетапної задачі. </font>
  
 
<font size=3> Введемо вектор </font>
 
<font size=3> Введемо вектор </font>
 
<math>~c_x=M[c-z^*(A,b,x)A]</math>
 
<math>~c_x=M[c-z^*(A,b,x)A]</math>
<font size=3> та лінійну форму <math>L_{x_1}=(c_1,x)=M[c-z^*(A,b,x_1)A]x</math> </font>
+
<font size=3> та лінійну форму <math>L_{x_{1}}=(c_{x_1},x)=M[c-z^*(A,b,x_1)A]x</math>. </font>
  
<font size=3> '''Теорема 1 (необхідна умова оптимальності плану двохетапної задачі):''' </font>
 
  
<font size=3> Якщо <math>\ x* </math> - розв’язок двохетапної задачі, то для будь-якого <math>x \in K</math> </font>
 
  
<math>L_x(x^*)\leq{L_x(x)}</math> (1)
+
<font size=3> '''Теорема 1 (Необхідна умова оптимальності плану двохетапної задачі.):''' </font>
 +
 
 +
<font size=3> Якщо <math>\ x^* </math> - розв’язок двохетапної задачі, то для будь-якого <math>x \in K</math> </font>
 +
 
 +
<font size=3> <math>L_x(x^*)\leq{L_x(x)}</math> (1) </font>
  
 
<font size=3> '''Доведення:''' </font>
 
<font size=3> '''Доведення:''' </font>
  
<font size=3> Оскільки <math>\ x* </math> - оптимальний план, а x – план двохетапної задачі, то <math>Q(x^*)\leq{Q(x)}</math>, тобто
+
<font size=3> Оскільки <math>\ x^* </math> - оптимальний план, а <math>\ x </math> – план двохетапної задачі, то <math>Q(x^*)\leq{Q(x)}</math>, тобто </font>
 +
 
 
<math>M\{cx^*+z^*(A,b,x^*)(b-Ax^*)\}\leq{M\{cx+z^*(A,b,x)(b-Ax)\}}</math> (2) </font>
 
<math>M\{cx^*+z^*(A,b,x^*)(b-Ax^*)\}\leq{M\{cx+z^*(A,b,x)(b-Ax)\}}</math> (2) </font>
  
<font size=3> Крім того </font>
+
<font size=3> Крім того, </font>
  
<math>M\{z^*(A,b,x^*)(b-Ax^*)\}\geq{M\{z^*(A,b,x)(b-Ax)\}}</math> (3)
+
<font size=3> <math>M\{z^*(A,b,x^*)(b-Ax^*)\}\geq{M\{z^*(A,b,x)(b-Ax^*)\}}</math> (3) </font>
  
<font size=3> так як <math>\ z*(A,b,x*) </math>- оптимальний план задачі, двоїстої до задачі другого етапу при <math>\ x=x*. </font>
+
<font size=3> так як <math>\ z^*(A,b,x^*) </math>- оптимальний план [[Умови розв’язуваності задачі другого етапу.|задачі (3.8)-(3.9)]], двоїстої до задачі другого етапу при <math>\ x=x^*. </math> </font>
  
<font size=3> Віднімаючи від (2) (3) приходимо до твердження (1): </font>
+
<font size=3> Віднімаючи (3) від  (2) приходимо до твердження (1): </font>
  
 
<math>M(cx^*)+M(z^*(A,b,x^*)b)-M(z^*(A,b,x^*)Ax^*)-M(z^*(A,b,x)Ax^*)+M(z^*(A,b,x)b)\leq{M(cx)+M(z^*(A,b,x)b)-M(z^*(A,b,x)Ax)-M(z^*(A,b,x^*)Ax^*)+M(z^*(A,b,x^*)b)}</math>
 
<math>M(cx^*)+M(z^*(A,b,x^*)b)-M(z^*(A,b,x^*)Ax^*)-M(z^*(A,b,x)Ax^*)+M(z^*(A,b,x)b)\leq{M(cx)+M(z^*(A,b,x)b)-M(z^*(A,b,x)Ax)-M(z^*(A,b,x^*)Ax^*)+M(z^*(A,b,x^*)b)}</math>
Рядок 34: Рядок 37:
 
<font size=3> '''Теорема доведена.''' </font>
 
<font size=3> '''Теорема доведена.''' </font>
  
<font size=3> Теорема 1 містить ідею аналізу двохетапної задачі. Теорема стверджує, що розв’язок <math>\ x* двохетапної задачі надає лінійній формі <math>L_{x_1}(x)=M[c-z^*(A,b,x_1)A]x</math> значення, що не перевищує значення форми в точці <math>x_1 \in K</math>. </font>
+
 
 +
 
 +
<font size=3> Теорема 1 містить ідею аналізу двохетапної задачі. Теорема стверджує, що розв’язок <math>\ x^* </math> двохетапної задачі надає лінійній формі <math>L_{x_1}(x)=M[c-z^*(A,b,x_1)A]x</math> значення, що не перевищує значення форми в точці <math>x_1 \in K</math>. </font>
  
 
<font size=3> Звідси випливає наступний метод аналізу двохетапної задачі. </font>
 
<font size=3> Звідси випливає наступний метод аналізу двохетапної задачі. </font>
  
<font size=3> Вибираємо деяку кількість точок <math>x_1 \in K</math> і обчислюємо для них розв’язки <math>~z^*(A,b,x_1)</math> задачі лінійного програмування (3.8)-(3.9), двоїстої до задачі другого етапу. </font>
+
<font size=3> Обираємо деяку кількість точок <math>x_1 \in K</math> та обчислюємо для них розв’язки <math>~z^*(A,b,x_1)</math> задачі лінійного програмування [[Умови розв’язуваності задачі другого етапу.|(3.8)-(3.9)]], двоїстої до задачі другого етапу. </font>
  
<font size=3> Для кожного вибраного <math>~x_1</math> будуємо нерівність типу (1): <math>L_{x_1}(x)\leq{L_{x_1}(x_1)}</math>
+
<font size=3> Для кожного обраного <math>~x_1</math> будуємо нерівність типу (1): <math>L_{x_1}(x)\leq{L_{x_1}(x_1)}</math>. </font>
  
 
<font size=3> Отримана таким чином послідовність нерівностей представляє собою систему обмежень, що звужують множину, в якій міститься оптимум, і, відповідно, тих, що скорочують діапазон зміни показника якості розв’язку двохетапної задачі. </font>
 
<font size=3> Отримана таким чином послідовність нерівностей представляє собою систему обмежень, що звужують множину, в якій міститься оптимум, і, відповідно, тих, що скорочують діапазон зміни показника якості розв’язку двохетапної задачі. </font>
 +
 +
  
 
<font size=3> '''Наведемо економічну інтерпретацію умови''' (1). </font>
 
<font size=3> '''Наведемо економічну інтерпретацію умови''' (1). </font>
  
<font size=3> Вектор <math>\ z*(A,b,x) </math> – розв’язок задачі, двоїстої до задачі другого етапу, представляє собою вектор оцінок продуктів. що виявилися дефіцитними або надлишковими при інтенсивностях x технологічних способів після того, як були реалізовані технологічна матриця A та вектор попиту b. Ці оцінки визначають вплив величини нев’язки на витрати, пов’язані з найбільш економною ліквідацією нев’язок. Величина  </font>
+
<font size=3> Вектор <math>\ z^*(A,b,x) </math> – розв’язок [[Умови розв’язуваності задачі другого етапу.|задачі (3.8)-(3.9)]], двоїстої до задачі другого етапу, представляє собою вектор оцінок продуктів, що виявилися дефіцитними або надлишковими при інтенсивностях <math>\ x </math> технологічних способів після того, як були реалізовані технологічна матриця <math>\ A </math> та вектор попиту <math>\ b </math>. Ці оцінки визначають вплив величини нев’язки на витрати, пов’язані з найбільш економною ліквідацією нев’язок. Величина  </font>
  
 
<math>\sum^{m}_{i=1}{a_{ij}z^{*}_i(A,b,x)}-c_j</math>
 
<math>\sum^{m}_{i=1}{a_{ij}z^{*}_i(A,b,x)}-c_j</math>
  
<font size=3> вказує на прибутковість експлуатації j-ого технологічного способу з одиничною інтенсивністю у припущенні, що параметри умов задачі реалізувалися як елементи матриці <math>\ A </math> та складові векторів <math>\ b </math>, <math>\ c </math>, а оцінки продуктів пораховані для випадку, коли експлуатація технологічних способів відбувається з інтенсивністю <math>\ x.
+
<font size=3> вказує на прибутковість експлуатації ''j''-ого технологічного способу з одиничною інтенсивністю у припущенні, що параметри умов задачі реалізувалися як елементи матриці <math>\ A </math> та складові векторів <math>\ b </math> та <math>\ c </math>, а оцінки продуктів пораховані для випадку, коли експлуатація технологічних способів відбувається з інтенсивністю <math>\ x </math>. </font>
Якщо вектор <math>\ x* </math> визначає оптимальний попередній план двохетапної задачі, то сумарний середній прибуток при інтенсивностях <math>\ x* </math> використання технологічних способів виробництва, підрахована в оптимальних оцінках (ті, що відповідають <math>\ x* </math>), не менше сумарного середнього прибутку, порахованого в оптимальних оцінках для будь-якого іншого допустимого плану <math>\ x. </math> </font>
+
  
<font size=3> '''Теорема 2 (необхідна і достатня умова оптимальності плану двохетапної задачі):''' </font>
 
  
<font size=3> Нехай <math>\ x* </math>- внутрішня точка множини <math>\ K </math>, а цільова функція <math>\ Q(x) </math> детермінованої задачі, еквівалентної двохетапній задачі, диференційована в околі <math>\ x*. Тоді задача, двоїста до задачі другого етапу, має розв’язок <math>\ z*(A,b,x*)</math> такий, що  </font>
+
<font size=3> Якщо вектор <math>\ x^* </math> визначає оптимальний попередній план двохетапної задачі, то сумарний середній прибуток при інтенсивностях <math>\ x^* </math> використання технологічних способів виробництва, підрахований в оптимальних оцінках (ті, що відповідають <math>\ x^* </math>), не менший сумарного середнього прибутку, порахованого в оптимальних оцінках для будь-якого іншого допустимого плану <math>\ x. </math> </font>
 +
 
 +
 
 +
 
 +
<font size=3> '''Теорема 2 (Необхідна і достатня умова оптимальності плану двохетапної задачі.):''' </font>
 +
 
 +
<font size=3> Нехай <math>\ x^* </math>- внутрішня точка множини <math>\ K </math>, а цільова функція <math>\ Q(x) </math> детермінованої задачі, еквівалентної двохетапній задачі, диференційована в околі <math>\ x^* </math>. Тоді [[Умови розв’язуваності задачі другого етапу.|задача (3.8)-(3.9)]], двоїста до задачі другого етапу, має розв’язок <math>\ z^*(A,b,x^*)</math> такий, що  </font>
  
 
<math>c_{x^*}=M[c-z^*(A,b,x^*)A]=0</math> (4)
 
<math>c_{x^*}=M[c-z^*(A,b,x^*)A]=0</math> (4)
  
<font size=3> тоді і тільки тоді, коли <math>\ x* </math> - розв’язок двохетапної задачі. </font>
+
<font size=3> тоді і тільки тоді, коли <math>\ x^* </math> - розв’язок двохетапної задачі. </font>
  
 
<font size=3> '''Доведення:''' </font>
 
<font size=3> '''Доведення:''' </font>
  
<font size=3> Згідно з теоремою, що визначає опорний функціонал до <math>\ Q(x) </math>, стверджуємо, що гіперплощина </font>
+
<font size=3> Згідно з [[Детермінована задача, еквівалентна до двохетапної задачі СП.|теоремою 4.3]], що визначає опорний функціонал до <math>\ Q(x) </math>, стверджуємо, що гіперплощина </font>
  
 
<math>~u=M[c-z^*(A,b,x_0)A]x+Mz^*(A,b,x_0)b</math>
 
<math>~u=M[c-z^*(A,b,x_0)A]x+Mz^*(A,b,x_0)b</math>
  
<font size=3> є опорною гіперплощиною до множини <math>u\geq{Q(x)}</math>в точці <math>~x=x_0</math>.
+
<font size=3> є опорною гіперплощиною до множини <math>u\geq{Q(x)}</math> в точці <math>~x=x_0</math>.
  
<font size=3> За умовою опукла функція Q(x) диференційована в точці <math>\ x=x* </math>. Відповідно опорна гіперплощина </font>
+
<font size=3> За умовою опукла функція <math>\ Q(x) </math> диференційована в точці <math>\ x=x^* </math>. Відповідно, опорна гіперплощина </font>
  
 
<math>~u=M[c-z^*(A,b,x^*)A]x+Mz^*(A,b,x^*)b</math>
 
<math>~u=M[c-z^*(A,b,x^*)A]x+Mz^*(A,b,x^*)b</math>
  
<font size=3> дотикається до гіперповерхні <math>\ u=Q(x)</math> в точці <math>\ x=x* </math>. </font>
+
<font size=3> дотикається до гіперповерхні <math>\ u=Q(x)</math> в точці <math>\ x=x^* </math>. </font>
 
    
 
    
<font size=3> Враховуючи, що <math>\ x* </math> - внутрішня точка множини K отримаємо, що рівність </font>
+
<font size=3> Враховуючи, що <math>\ x^* </math> - внутрішня точка множини <math>\ K </math> отримаємо, що рівність </font>
  
 
<math>\frac{\partial Q}{\partial x}=\frac{\partial u}{\partial x}=M[c-z^*(A,b,x^*)A]=0</math>
 
<math>\frac{\partial Q}{\partial x}=\frac{\partial u}{\partial x}=M[c-z^*(A,b,x^*)A]=0</math>
<font size=3> є необхідною умовою оптимальності вектора <math>\ x* </math>.  </font>
+
<font size=3> є необхідною умовою оптимальності вектора <math>\ x^* </math>.  </font>
  
<font size=3> Рівність (4) є також і достатньою умовою, оскільки функція <math>\ Q(x)</math> опукла вниз. </font>  
+
<font size=3> Рівність (4) є також і достатньою умовою, оскільки функція <math>\ Q(x)</math> опукла до низу. </font>  
  
 
<font size=3> '''Теорема доведена.''' </font>
 
<font size=3> '''Теорема доведена.''' </font>
 +
 +
<font size=3> [1, c. 161-163]. </font>
 +
 +
 +
 +
==Список використаних джерел==
 +
<font size=2> 1. Юдин Д. Б. Математические методы управления в условиях неполной информации. / Юдин Д. Б. М: «Сов. радио», 1974. – 400 с.
 +
 +
 +
 +
<font size=2> Виконала: [[Користувач:Гонтаренко Марія Олександрівна|Гонтаренко Марія]]
 +
 +
<font size=2> Доповнювала: [[Користувач:9190285|Петрикова Ірина]]

Поточна версія на 08:10, 24 травня 2021

Сформулюємо необхідні умови оптимальності попереднього плану Неможливо розібрати вираз (невідома помилка): x

двохетапної задачі. 

Введемо вектор Неможливо розібрати вираз (невідома помилка): ~c_x=M[c-z^*(A,b,x)A]

та лінійну форму Неможливо розібрати вираз (невідома помилка): L_{x_{1}}=(c_{x_1},x)=M[c-z^*(A,b,x_1)A]x .


Теорема 1 (Необхідна умова оптимальності плану двохетапної задачі.):

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

- розв’язок двохетапної задачі, то для будь-якого Неможливо розібрати вираз (невідома помилка): x \in K

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

(1) 

Доведення:

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

- оптимальний план, а  Неможливо розібрати вираз (невідома помилка): \ x 
– план двохетапної задачі, то Неможливо розібрати вираз (невідома помилка): Q(x^*)\leq{Q(x)}

, тобто

Неможливо розібрати вираз (невідома помилка): M\{cx^*+z^*(A,b,x^*)(b-Ax^*)\}\leq{M\{cx+z^*(A,b,x)(b-Ax)\}}

(2) </font>

Крім того,

Неможливо розібрати вираз (невідома помилка): M\{z^*(A,b,x^*)(b-Ax^*)\}\geq{M\{z^*(A,b,x)(b-Ax^*)\}}

(3) 

так як Неможливо розібрати вираз (невідома помилка): \ z^*(A,b,x^*) - оптимальний план задачі (3.8)-(3.9), двоїстої до задачі другого етапу при Неможливо розібрати вираз (невідома помилка): \ x=x^*.


Віднімаючи (3) від (2) приходимо до твердження (1):

Неможливо розібрати вираз (невідома помилка): M(cx^*)+M(z^*(A,b,x^*)b)-M(z^*(A,b,x^*)Ax^*)-M(z^*(A,b,x)Ax^*)+M(z^*(A,b,x)b)\leq{M(cx)+M(z^*(A,b,x)b)-M(z^*(A,b,x)Ax)-M(z^*(A,b,x^*)Ax^*)+M(z^*(A,b,x^*)b)}


Неможливо розібрати вираз (невідома помилка): M(cx^*)-M(z^*(A,b,x)Ax^*)\leq{M(cx)-M(z^*(A,b,x)Ax)}


Неможливо розібрати вираз (невідома помилка): M[c-z^*(A,b,x)A]x^*\leq{M[c-z^*(A,b,x)A]x}


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


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


Теорема 1 містить ідею аналізу двохетапної задачі. Теорема стверджує, що розв’язок Неможливо розібрати вираз (невідома помилка): \ x^*

двохетапної задачі надає лінійній формі Неможливо розібрати вираз (невідома помилка): L_{x_1}(x)=M[c-z^*(A,b,x_1)A]x
значення, що не перевищує значення форми в точці Неможливо розібрати вираз (невідома помилка): x_1 \in K

.

Звідси випливає наступний метод аналізу двохетапної задачі.

Обираємо деяку кількість точок Неможливо розібрати вираз (невідома помилка): x_1 \in K

та обчислюємо для них розв’язки Неможливо розібрати вираз (невідома помилка): ~z^*(A,b,x_1)
задачі лінійного програмування (3.8)-(3.9), двоїстої до задачі другого етапу. 

Для кожного обраного Неможливо розібрати вираз (невідома помилка): ~x_1

будуємо нерівність типу (1): Неможливо розібрати вираз (невідома помилка): L_{x_1}(x)\leq{L_{x_1}(x_1)}

.

Отримана таким чином послідовність нерівностей представляє собою систему обмежень, що звужують множину, в якій міститься оптимум, і, відповідно, тих, що скорочують діапазон зміни показника якості розв’язку двохетапної задачі.


Наведемо економічну інтерпретацію умови (1).

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

– розв’язок задачі (3.8)-(3.9), двоїстої до задачі другого етапу, представляє собою вектор оцінок продуктів, що виявилися дефіцитними або надлишковими при інтенсивностях Неможливо розібрати вираз (невідома помилка): \ x 
технологічних способів після того, як були реалізовані технологічна матриця Неможливо розібрати вираз (невідома помилка): \ A 
та вектор попиту Неможливо розібрати вираз (невідома помилка): \ b 

. Ці оцінки визначають вплив величини нев’язки на витрати, пов’язані з найбільш економною ліквідацією нев’язок. Величина

Неможливо розібрати вираз (невідома помилка): \sum^{m}_{i=1}{a_{ij}z^{*}_i(A,b,x)}-c_j


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

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

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


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

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

), не менший сумарного середнього прибутку, порахованого в оптимальних оцінках для будь-якого іншого допустимого плану Неможливо розібрати вираз (невідома помилка): \ x.



Теорема 2 (Необхідна і достатня умова оптимальності плану двохетапної задачі.):

Нехай Неможливо розібрати вираз (невідома помилка): \ x^* - внутрішня точка множини Неможливо розібрати вираз (невідома помилка): \ K , а цільова функція Неможливо розібрати вираз (невідома помилка): \ Q(x)

детермінованої задачі, еквівалентної двохетапній задачі, диференційована в околі Неможливо розібрати вираз (невідома помилка): \ x^* 

. Тоді задача (3.8)-(3.9), двоїста до задачі другого етапу, має розв’язок Неможливо розібрати вираз (невідома помилка): \ z^*(A,b,x^*)

такий, що  

Неможливо розібрати вираз (невідома помилка): c_{x^*}=M[c-z^*(A,b,x^*)A]=0

(4)

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

- розв’язок двохетапної задачі. 

Доведення:

Згідно з теоремою 4.3, що визначає опорний функціонал до Неможливо розібрати вираз (невідома помилка): \ Q(x) , стверджуємо, що гіперплощина

Неможливо розібрати вираз (невідома помилка): ~u=M[c-z^*(A,b,x_0)A]x+Mz^*(A,b,x_0)b


є опорною гіперплощиною до множини Неможливо розібрати вираз (невідома помилка): u\geq{Q(x)}

в точці Неможливо розібрати вираз (невідома помилка): ~x=x_0

.

За умовою опукла функція Неможливо розібрати вираз (невідома помилка): \ Q(x)

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

. Відповідно, опорна гіперплощина

Неможливо розібрати вираз (невідома помилка): ~u=M[c-z^*(A,b,x^*)A]x+Mz^*(A,b,x^*)b


дотикається до гіперповерхні Неможливо розібрати вираз (невідома помилка): \ u=Q(x)

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

.

Враховуючи, що Неможливо розібрати вираз (невідома помилка): \ x^*

- внутрішня точка множини Неможливо розібрати вираз (невідома помилка): \ K 
отримаємо, що рівність 

Неможливо розібрати вираз (невідома помилка): \frac{\partial Q}{\partial x}=\frac{\partial u}{\partial x}=M[c-z^*(A,b,x^*)A]=0

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

Рівність (4) є також і достатньою умовою, оскільки функція Неможливо розібрати вираз (невідома помилка): \ Q(x)

опукла до низу.  

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

[1, c. 161-163].


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

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


Виконала: Гонтаренко Марія

Доповнювала: Петрикова Ірина