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

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

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

Визначити вектор Неможливо розібрати вираз (невідома помилка): 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}

.

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

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