Відмінності між версіями «Задача СП з розв’язувальним розподілом за умови детермінованих параметрів умов обмежень. Дискретний розв’язувальний розподіл.»

Матеріал з Вікі ЦДУ
Перейти до: навігація, пошук
Рядок 45: Рядок 45:
 
Зафіксуємо довільним чином  <math>\ m+1 </math> точку <math>\ x_{k}\in X,  \  k = 0,1,...m,</math> , і розв'яжемо отриману при цьому задачу лінійного програмування (19.8) - (19.10).
 
Зафіксуємо довільним чином  <math>\ m+1 </math> точку <math>\ x_{k}\in X,  \  k = 0,1,...m,</math> , і розв'яжемо отриману при цьому задачу лінійного програмування (19.8) - (19.10).
  
Нехай <math>\ p ^{(1)}=(p_{0} ^{(1)},...,p_{m} ^{(1)}) </math>, i
+
Нехай <math>\ p ^{(1)}=(p_{0} ^{(1)},...,p_{m} ^{(1)}) </math>, i
 +
<math>\ \lambda^{(1)}=(\lambda_{0} ^{(1)},...,\lambda_{m+1} ^{(1)}) </math>, - розвязок прямої і двоїстої задачі.

Версія за 14:15, 9 березня 2013

Відображення (19.4) переводить множину Неможливо розібрати вираз (невідома помилка): \ X \subset R ^n , в Неможливо розібрати вираз (невідома помилка): \ X \subset R^{(m+1)} . В цьому випадку Неможливо розібрати вираз (невідома помилка): \ Y - не викупла і незамкнута множина. Позначемо через Неможливо розібрати вираз (невідома помилка): \ co Y

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

.

Задача (19.1) - (19.3) може бути записана в вигляді:

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

Неможливо розібрати вираз (невідома помилка): \ y_i \le 0, i = 1,...m, , (19.6)

Неможливо розібрати вираз (невідома помилка): \ y = (y_0, y_1, ... , y_m)\in co Y , (19.6)


Згідно теореми Каретеодорі для побудови випуклої оболонти множини Неможливо розібрати вираз (невідома помилка): \ Y

із  Неможливо розібрати вираз (невідома помилка): \ m+1 
- вимірного простору потрібно загалом не більш Неможливо розібрати вираз (невідома помилка): \ m+2 
точок Неможливо розібрати вираз (невідома помилка): \ y \in  Y 

. Це значить, що Неможливо розібрати вираз (невідома помилка): \ co Y

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

Неможливо розібрати вираз (невідома помилка): \ co Y= {\sum^{m+1}_{k=0}\phi_{i}(x_{k})p_{k}}

Неможливо розібрати вираз (невідома помилка): \ i = 1,...m, ,

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

Неможливо розібрати вираз (невідома помилка): \sum^{m+1}_{k=0} p_{k}=1 ,

Неможливо розібрати вираз (невідома помилка): \ x_{k}\in X . Нас цікавлять тільки точки Неможливо розібрати вираз (невідома помилка): \ y \in Y \subset R^{(m+1)} ,одна з координат яких Неможливо розібрати вираз (невідома помилка): \ (y_0)

досягає свого екстремального значення. Такі точки відповідно з наслідком теореми Каратеодорі можуть бути представлені як випуклі комбінації не більш ніж Неможливо розібрати вираз (невідома помилка): \ m+1 
векторів Неможливо розібрати вираз (невідома помилка): \ x_{k}\in X 
і  Неможливо розібрати вираз (невідома помилка): \ m+1 
чисел Неможливо розібрати вираз (невідома помилка): \ p_{k} 
Неможливо розібрати вираз (невідома помилка): \  (k = 1,...m),  

, Неможливо розібрати вираз (невідома помилка): \ p_{k}\ge 0


Неможливо розібрати вираз (невідома помилка): \sum^{m}_{k=0} p_{k}=1 .

Задача (19.1) - (19.3) еквівалентна, таким чином , наступній скінченномірній задачі.

Потрібно обчислити вектори Неможливо розібрати вираз (невідома помилка): \ x_{k}

і числа Неможливо розібрати вираз (невідома помилка):  \ p_{k} 

, які визначають нижню межу функціонала

Неможливо розібрати вираз (невідома помилка): \ {\sum^{m}_{k=0}\phi_{0}(x_{k})p_{k}}

(19.8)

За умови

Неможливо розібрати вираз (невідома помилка): \ {\sum^{m}_{k=0}\phi_{i}(x_{k})p_{k}\le 0 \ i = 1,...m}

(19.9)


Неможливо розібрати вираз (невідома помилка): \ x_{k}\in X, \ p_{k}\ge 0 , \ k = 0,1,...m, \sum^{m}_{k=0} p_{k}=1 ,(19.10)


Вектори Неможливо розібрати вираз (невідома помилка): \ x\ast_{k}

і числа Неможливо розібрати вираз (невідома помилка):  \ p\ast_{k} 

, що становить оптимальний план задачі (19.8) - (19.10), визначають дискретний розв'язувальний розподіл вихідної задачі (19.1) - (19.3).

Для розв'язку задачі (19.8) - (19.10) використаємо ітеративний метод. Зафіксуємо довільним чином Неможливо розібрати вираз (невідома помилка): \ m+1

точку Неможливо розібрати вираз (невідома помилка): \ x_{k}\in X,  \  k = 0,1,...m,
, і розв'яжемо отриману при цьому задачу лінійного програмування (19.8) - (19.10).

Нехай Неможливо розібрати вираз (невідома помилка): \ p ^{(1)}=(p_{0} ^{(1)},...,p_{m} ^{(1)}) , i Неможливо розібрати вираз (невідома помилка): \ \lambda^{(1)}=(\lambda_{0} ^{(1)},...,\lambda_{m+1} ^{(1)}) , - розвязок прямої і двоїстої задачі.