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

Матеріал з Вікі ЦДУ
Перейти до: навігація, пошук
м
 
(не показана одна проміжна версія 3 учасників)
Рядок 1: Рядок 1:
−
Відображення (19.4) переводить множину <math>\ X \subset R ^n </math>, в <math>\ X \subset R^{(m+1)}</math>. В цьому випадку <math>\ Y </math>- не викупла і незамкнута множина. Позначемо через <math>\ co Y </math> випуклу множину <math>\ Y </math>.
+
===Загальна математична постановка задачі математичного програмування===
−
Задача (19.1) - (19.3) може бути записана в вигляді:
+
  
−
<math>\ y_0 \rightarrow inf </math>,          (19.5)
+
Типову задачу математичного програмування в детермінованій постановці можна сформулювати так:
  
−
<math>\ y_i \le 0, i = 1,...m, </math>,       (19.6)
+
Визначити вектор <math>X=(x_1, x_2, x_3, ..., x_n)</math>, для компонент якого:
  
−
<math>\ y = (y_0, y_1, ... , y_m)\in co Y </math>, (19.6)
 
  
 +
<math>max(min)F=f(X)</math>,
  
−
Згідно теореми Каретеодорі для побудови випуклої оболонти множини  <math>\ Y </math> із  <math>\ m+1 </math> - вимірного простору потрібно загалом не більш <math>\ m+2 </math> точок <math>\ y \in  Y </math>. Це значить, що <math>\ co Y </math> може бути представлена в вигляді:
+
<math>q_i(X)\leq0(i=1..m)</math>,
  
−
<math>\ co Y= {\sum^{m+1}_{k=0}\phi_{i}(x_{k})p_{k}}</math>;
+
<math>X\geq0</math>.
  
−
<math>\  i = 1,...m,  </math>,
 
  
−
<math> \in X\in X </math>,  
+
Якщо функції в даній задачі, крім керованих параметрів <math>X</math>, залежать ще й від деяких випадкових величин <math>\omega=(\omega_1, \omega_2, \omega_3, ..., \omega_n)</math>, то матимемо задачу стохастичного програмування:
  
−
<math> \sum^{m+1}_{k=0} p_{k}=1 </math>,
 
  
−
<math>\ x_{k}\in X </math>.
+
<math>max(min)F=f(X, \omega)</math>,
−
Нас цікавлять тільки точки <math>\ y \in Y \subset R^{(m+1)} </math>,одна з координат яких  <math>\ (y_0)</math> досягає свого екстремального значення. Такі точки відповідно з наслідком теореми Каратеодорі можуть бути представлені як випуклі комбінації не більш ніж <math>\ m+1 </math> векторів <math>\ x_{k}\in X </math> і  <math>\ m+1 </math> чисел <math>\ p_{k} </math> <math>\  k = 1,...m,  </math>, <math> \ p_{k}\ge 0 </math>
+
  
−
<math> \sum^{m}_{k=0} p_{k}=1 </math>.
+
<math>q_i(X, \omega)\leq0(i=1..m)</math>,
  
−
Задача (19.1) - (19.3) еквівалентна, таким чином , наступній скінченномірній задачі.
+
<math>X\geq0, \omega\in\Omega</math>.
  
−
Потрыбно обчислити вектори <math>\ x_{k}</math> і числа <math> \ p_{k} </math>, які визначають нижню межу функціонала
 
  
−
<math>\ {\sum^{m}_{k=0}\phi_{0}(x_{k})p_{k}}</math>;  (19.8)
+
Де <math>\omega</math> — простір подій <math>\Omega</math>.
  
−
За умови
+
Залежно від можливості здобути та врахувати інформацію про детермінованості (стохастичності) функцій <math>f(X, \omega), q_i(X, \omega)</math> задачі, постановки задач стохастичного програмування можуть містити:
  
−
<math>\  {\sum^{m}_{k=0}\phi_{i}(x_{k})p_{k}\le 0 \  i = 1,...m}</math>; (19.9)
+
а) стохастичні коефіцієнти цільової функції та детерміновані обмеження;
  
−
<math>\ x_{k}\in X\in X,  \ k = 0,1,...m,  \sum^{m}_{k=0} p_{k}=1  </math>,
+
б) детерміновані коефіцієнти цільової функції та стохастичні вільні члени і коефіцієнти системи обмежень;
 +
 
 +
в) стохастичні коефіцієнти цільової функції, вільні члени і коефіцієнти системи обмежень.
 +
 
 +
 
 +
Конкретні постановки задач стохастичного програмування мають свою специфіку. Перш за все необхідно враховувати таке:
 +
 
 +
1. Вектор <math>X</math> є детермінованим чи випадковим. Якщо вектор <math>X</math> детермінований, то він не залежить від випадкових параметрів моделі. Якщо він випадковий, то тоді <math>X(\omega)</math> залежить від випадкових параметрів.
 +
 
 +
2. Як розуміти максимізацію (мінімізацію) цільової функції — як абсолютну (для всіх значень <math>\omega\in\Omega</math>), чи як максимізацію її математичного сподівання або деякої іншої ймовірнісної характеристики цієї функції (моди, медіани), або мінімізації середньоквадратичного відхилення. Наприклад, що краще, мати платню 500 ± 200 чи 450 ± 50. У першому випадку платня може змінюватись в межах 300 - 700, у другому лише 400 - 500 грн.
 +
 
 +
3. Як виконуються обмеження — абсолютно для всіх <math>\omega\in\Omega</math>, чи в середньому або з допустимими порушеннями, ймовірність яких мала.
 +
 
 +
 
 +
При постановці задач стохастичного програмування слід виходити не тільки з математичних міркувань, а й з економічного змісту та евристичних міркувань. Наприклад, детермінованість чи стохастичність вектора <math>X</math> визначається із сутності економічних, технологічних процесів, тощо. Для сільськогосподарського підприємства вектор, що визначатиме площі посіву рослинницьких культур, обов’язково має бути детермінованим, якщо ж шуканий вектор для того ж підприємства за тих самих  умов визначатиме, наприклад, обсяги кредитів, його компоненти мають бути стохастичними величинами, бо достеменно невідомо, чи будуть вони отримані. Методи розв’язування стохастичних задач ділять на дві групи — прямі та непрямі.
 +
 
 +
Прямі методи використовуються для розв’язування задач стохастичного програмування, коли існують способи побудови функцій <math>f(X,\omega)</math> і <math>g_i(X,\omega)\leq0, i=1..m</math> на базі інформації про параметри <math>\omega</math>. Непрямими є методи зведення стохастичної задачі до задачі лінійного чи нелінійного програмувань, тобто, перехід до детермінованого аналогу задачі стохастичного програмування.
 +
 
 +
 
 +
=====Постановка  задачі:=====
 +
 
 +
У задачах першого класу з детермінованими параметрами умов потрібно обчислити розподіл <math>F_x</math>  вектора <math>X</math> при якому:
 +
 
 +
 
 +
<math>M\phi_0 (x) =\int \phi_0 dF_x \rightarrow \infty</math>,  (1)
 +
 
 +
<math>M\phi_i (x) =\int  \phi_i dF_x \leq  0, i=1,2, ..., m</math>,  (2)
 +
 
 +
<math>x\in X</math>,  (3)
 +
 
 +
 
 +
Де <math>X</math> - задана множина в n-вимірному евклідовому просторі.
 +
 
 +
Введемо нові змінні:
 +
 
 +
 
 +
<math>y = \phi_i (x)</math>,  (4)
 +
 
 +
 
 +
Відображення (4) переводить множину <math>X \subset R^n </math>, в <math>X \subset R^{m+1}</math>.
 +
 
 +
В цьому випадку <math>Y</math> - не випукла і незамкнута множина.
 +
 
 +
Позначемо через <math>coY</math>, випуклу множину <math>Y</math>.
 +
 
 +
Задача (1) - (3) може бути записана в вигляді:
 +
 
 +
 
 +
<math>y_0 \rightarrow \infty</math>,  (5)
 +
 
 +
<math>y_i \le 0, i = 1..m</math>,  (6)
 +
 
 +
<math>y = (y_0, y_1, ... , y_m)\in coY</math>,  (7)
 +
 
 +
 
 +
Згідно теореми Каретеодорі для побудови випуклої оболонки множини  <math>\ Y </math> із  <math>\ m+1 </math> - вимірного простору потрібно загалом не більш <math>\ m+2 </math> точок <math>\ y \in  Y </math>. Це значить, що <math>\ coY </math> може бути представлена в вигляді:
 +
 
 +
 
 +
<math>coY= {\sum^{m+1}_{k=0}\phi_{i}(x_{k})p_{k}}</math>;
 +
 
 +
<math>i = 0, 1, ..., m</math>,
 +
 
 +
<math>p_k \geq 0</math>,
 +
 
 +
<math>\sum^{m+1}_{k=0} p_{k}=1</math>,
 +
 
 +
<math>x_k\in X</math>.
 +
 
 +
 
 +
Нас цікавлять тільки точки <math>y \in Y \subset R^{m+1}</math>, одна з координат яких  <math>y_0</math> досягає свого екстремального значення. Такі точки відповідно з наслідком теореми Каратеодорі можуть бути представлені як випуклі комбінації не більш ніж <math>m+1</math> векторів <math>x_k \in X</math> і  <math>m+1</math> чисел <math>p_k</math>, <math>(k = 1..m)</math>, <math>p_k \geq 0 </math>,
 +
<math>\sum^{m}_{k=0} p_{k}=1</math>.
 +
 
 +
Таким чином, задача (1) - (3) еквівалентна наступній скінченномірній задачі:
 +
 
 +
Потрібно обчислити вектори <math>x_{k}</math> і числа <math>p_{k} </math>, які визначають нижню межу функціонала
 +
 
 +
 
 +
<math>{\sum^{m}_{k=0} \phi_{0}(x_{k})p_{k}}</math>;   (8)
 +
 
 +
 
 +
За умови:
 +
 
 +
 
 +
<math>{\sum^{m}_{k=0} \phi_{i}(x_{k})p_{k} \leq 0, i = 1, ..., m}</math>;   (9)
 +
 
 +
<math>x_{k}\in X, p_{k} \geq 0, k = 0,1, ..., m, \sum^{m}_{k=0} p_{k}=1</math>,  (10)
 +
 
 +
 
 +
Вектори <math>x\ast_{k}</math> і числа <math>p\ast_{k} </math>, що становить оптимальний план задачі (8) - (10), визначають дискретний розв'язувальний розподіл вихідної задачі (1) - (3).
 +
 
 +
Для розв'язку задачі (8) - (10) використаємо ітеративний метод.
 +
Зафіксуємо довільним чином <math>m+1 </math> точку <math>x_{k}\in X, k = 0,1, ..., m</math>, і розв'яжемо отриману при цьому задачу лінійного програмування (8) - (10).
 +
 
 +
Нехай <math>\ p^{(1)}=(p_{0}^{(1)}, ..., p_{m}^{(1)}) </math>, i <math>\lambda^{(1)}=(\lambda_{0}^{(1)}, ..., \lambda_{m+1}^{(1)}) </math>, - розв'язок прямої і двоїстої задачі. Введемо в базис задачі новий розширений вектор умов <math>(\psi_{0}(x), \psi_{1}(x),...,\psi_{m}(x),1)^T</math> так, щоб значення цільового функціоналу (8) при цьому зменшилося.
 +
 
 +
Відповідна точка <math>\ x\in X </math> повинна задовольняти умову:
 +
 
 +
 
 +
<math>\sum^{m}_{k=0}\lambda_{i} ^{(1)}\phi_{i}{x}+\lambda_{m+1} ^{(1)}< -\psi_{0}(x) </math> .
 +
 
 +
 
 +
Нову точку <math>x_{m+1}</math> можна обчислити в результаті розв'язку допоміжної задачі:
 +
 
 +
 
 +
<math>\psi_{0}(x)=\sum^{m}_{k=0}\lambda_{i} ^{(1)}\phi_{x}\longrightarrow min  </math>,
 +
 
 +
<math>x\in X </math>.
 +
 
 +
 
 +
Обчислив <math>x_{m+1}</math>, знаходим новий розв'язок лінійної задачі (8) - (10) і двоїстої до неї і т.д.
 +
 
 +
Зрозуміло, що для реалізації інеративного методу достатньо на кожній ітерації зберігати в пам'яті не більш <math>\ m+2 </math> точок <math>\ x_{k}</math>.
 +
 
 +
Виконала: [[Юрченко Тетяна Сергіївна|Юрченко Тетяна Сергіївна ]]
 +
 
 +
Редагували: [[Лисенко Наталія|Лисенко Наталія ]], [[Токарь Володимир|Токарь Володимир]]

Поточна версія на 04:02, 28 грудня 2020

Загальна математична постановка задачі математичного програмування

Типову задачу математичного програмування в детермінованій постановці можна сформулювати так:

Визначити вектор Неможливо розібрати вираз (невідома помилка): X=(x_1, x_2, x_3, ..., x_n) , для компонент якого:


Неможливо розібрати вираз (невідома помилка): max(min)F=f(X) ,

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

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


Якщо функції в даній задачі, крім керованих параметрів Неможливо розібрати вираз (невідома помилка): X , залежать ще й від деяких випадкових величин Неможливо розібрати вираз (невідома помилка): \omega=(\omega_1, \omega_2, \omega_3, ..., \omega_n) , то матимемо задачу стохастичного програмування:


Неможливо розібрати вираз (невідома помилка): max(min)F=f(X, \omega) ,

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

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


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

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

.

Залежно від можливості здобути та врахувати інформацію про детермінованості (стохастичності) функцій Неможливо розібрати вираз (невідома помилка): f(X, \omega), q_i(X, \omega) 

задачі, постановки задач стохастичного програмування можуть містити:

а) стохастичні коефіцієнти цільової функції та детерміновані обмеження;

б) детерміновані коефіцієнти цільової функції та стохастичні вільні члени і коефіцієнти системи обмежень;

в) стохастичні коефіцієнти цільової функції, вільні члени і коефіцієнти системи обмежень.


Конкретні постановки задач стохастичного програмування мають свою специфіку. Перш за все необхідно враховувати таке:

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

є детермінованим чи випадковим. Якщо вектор Неможливо розібрати вираз (невідома помилка): X
детермінований, то він не залежить від випадкових параметрів моделі. Якщо він випадковий, то тоді Неможливо розібрати вираз (невідома помилка): X(\omega)
залежить від випадкових параметрів.

2. Як розуміти максимізацію (мінімізацію) цільової функції — як абсолютну (для всіх значень Неможливо розібрати вираз (невідома помилка): \omega\in\Omega ), чи як максимізацію її математичного сподівання або деякої іншої ймовірнісної характеристики цієї функції (моди, медіани), або мінімізації середньоквадратичного відхилення. Наприклад, що краще, мати платню 500 ± 200 чи 450 ± 50. У першому випадку платня може змінюватись в межах 300 - 700, у другому лише 400 - 500 грн.

3. Як виконуються обмеження — абсолютно для всіх Неможливо розібрати вираз (невідома помилка): \omega\in\Omega , чи в середньому або з допустимими порушеннями, ймовірність яких мала.


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

визначається із сутності економічних, технологічних процесів, тощо. Для сільськогосподарського підприємства вектор, що визначатиме площі посіву рослинницьких культур, обов’язково має бути детермінованим, якщо ж шуканий вектор для того ж підприємства за тих самих  умов визначатиме, наприклад, обсяги кредитів, його компоненти мають бути стохастичними величинами, бо достеменно невідомо, чи будуть вони отримані. Методи розв’язування стохастичних задач ділять на дві групи — прямі та непрямі.

Прямі методи використовуються для розв’язування задач стохастичного програмування, коли існують способи побудови функцій Неможливо розібрати вираз (невідома помилка): f(X,\omega) 

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

. Непрямими є методи зведення стохастичної задачі до задачі лінійного чи нелінійного програмувань, тобто, перехід до детермінованого аналогу задачі стохастичного програмування.


Постановка задачі:

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

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


Неможливо розібрати вираз (невідома помилка): M\phi_0 (x) =\int \phi_0 dF_x \rightarrow \infty , (1)

Неможливо розібрати вираз (невідома помилка): M\phi_i (x) =\int \phi_i dF_x \leq 0, i=1,2, ..., m , (2)

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


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

- задана множина в n-вимірному евклідовому просторі.

Введемо нові змінні:


Неможливо розібрати вираз (невідома помилка): y = \phi_i (x) , (4)


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

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

- не випукла і незамкнута множина.

Позначемо через Неможливо розібрати вираз (невідома помилка): coY , випуклу множину Неможливо розібрати вираз (невідома помилка): Y .

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


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

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

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


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

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

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

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


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

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

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

Неможливо розібрати вираз (невідома помилка): \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 \geq 0 , Неможливо розібрати вираз (невідома помилка): \sum^{m}_{k=0} p_{k}=1 .

Таким чином, задача (1) - (3) еквівалентна наступній скінченномірній задачі:

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

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

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


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

(8)


За умови:


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

(9)

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


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

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

, що становить оптимальний план задачі (8) - (10), визначають дискретний розв'язувальний розподіл вихідної задачі (1) - (3).

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

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

, і розв'яжемо отриману при цьому задачу лінійного програмування (8) - (10).

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

так, щоб значення цільового функціоналу (8) при цьому зменшилося.

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

повинна задовольняти умову:


Неможливо розібрати вираз (невідома помилка): \sum^{m}_{k=0}\lambda_{i} ^{(1)}\phi_{i}{x}+\lambda_{m+1} ^{(1)}< -\psi_{0}(x) 

.


Нову точку Неможливо розібрати вираз (невідома помилка): x_{m+1} 

можна обчислити в результаті розв'язку допоміжної задачі:


Неможливо розібрати вираз (невідома помилка): \psi_{0}(x)=\sum^{m}_{k=0}\lambda_{i} ^{(1)}\phi_{x}\longrightarrow min ,

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


Обчислив Неможливо розібрати вираз (невідома помилка): x_{m+1} , знаходим новий розв'язок лінійної задачі (8) - (10) і двоїстої до неї і т.д.

Зрозуміло, що для реалізації інеративного методу достатньо на кожній ітерації зберігати в пам'яті не більш Неможливо розібрати вираз (невідома помилка): \ m+2 

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

.

Виконала: Юрченко Тетяна Сергіївна

Редагували: Лисенко Наталія , Токарь Володимир

Отримано з https://wiki.cusu.edu.ua/index.php?title=Задача_СП_з_розв’язувальним_розподілом_за_умови_детермінованих_параметрів_умов_обмежень._Дискретний_розв’язувальний_розподіл.&oldid=371896