Постановка двохетапної задачі СП.

Розглянемо задачу лінійного програмування:

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

(21.1)

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

(21.2)

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

тут

Неможливо розібрати вираз (невідома помилка): c=\left \{ c_j \right \} , Неможливо розібрати вираз (невідома помилка): \ j = 1,...n,

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

Неможливо розібрати вираз (невідома помилка): b^{(1)} =\left \{ b^{(1)}_k \right \} , Неможливо розібрати вираз (невідома помилка): \ k = 1,...m_1,

Неможливо розібрати вираз (невідома помилка): A =\left \| \ a_ij^{(1)} \right \| , Неможливо розібрати вираз (невідома помилка): \ i = 1,...m,

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

Неможливо розібрати вираз (невідома помилка): A^{(1)} =\left \| \ a_kj^{(1)} \right \|

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

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

В випадку, коли елементи матриці Неможливо розібрати вираз (невідома помилка): \ A = A(\omega)

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

Уявімо собі процес вирішення задачі (21.1) - (21.4) в такий спосіб. Виберемо спочатку (на першому етапі) вектор, що задовольняє умови (21.3) - (21.4). Потім зафіксуємо реалізацію Неможливо розібрати вираз (невідома помилка): \widehat\omega

випадкової події і відповідні йому значення елементів Неможливо розібрати вираз (невідома помилка): \   A(\widehat\omega)
i Неможливо розібрати вираз (невідома помилка): \   b(\widehat\omega)

, оцінимо невязку Неможливо розібрати вираз (невідома помилка): \ b(\widehat\omega)- A(\widehat\omega)*(\widehat x)

в умовах (21,2) задачі і обчислимо вектор Неможливо розібрати вираз (невідома помилка):  y\geqslant  0 
компенсуючий невязки у відмінності із співвідношенням 

Неможливо розібрати вираз (невідома помилка): \ By= b(\widehat\omega)- A(\widehat\omega) *(\widehat x)

Неможливо розібрати вираз (невідома помилка): B =\left \| \ b_{il} \right \| , Неможливо розібрати вираз (невідома помилка): \ i = 1,...m,

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

- матриця компенсації. У загальному випадку елементи В випадкові. Якщо задача (21.1)-(21.4) інтерпритується в термінах планування виробництва. а А - матриця основних технологічних способів, то В - матриця аварійних технологічних способів, що визначають можливі шляхи компенсації виявлених відхилів. Передбачається, що реалізація Неможливо розібрати вираз (невідома помилка): \ \omega

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

. За порушення умов задачі встановлюється штраф, який залежить від величин складових вектора Неможливо розібрати вираз (невідома помилка): y , компенсуючого невязки. Природно характеризувати штраф величиною Неможливо розібрати вираз (невідома помилка): qy , де Неможливо розібрати вираз (невідома помилка): q\geqslant 0 , взагалі кажучи, випадковий Неможливо розібрати вираз (невідома помилка): n_1

- мірний вектор.

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

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

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

(21.5)

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

  (21.6)

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

 (21.7)

Обидва етапи розв'язка задачі можуть бути зведені в один. Отримаємо постановку, яка носить назву двохетапної задачі лінійного стохастичного програмування: Неможливо розібрати вираз (невідома помилка): \min_x M_\omega\{c(\omega)x+\min_y[q(\omega)y|B(\omega)y=b(\omega)-A(\omega)x, y\geqslant0]\}

Таким чином, рішення двоетапної стохастичної задачі складається з двох векторів: детермінованого Неможливо розібрати вираз (невідома помилка): n

- мірного вектора х, що визначає попередній план, і випадкового Неможливо розібрати вираз (невідома помилка):  n 
- мірного вектора Неможливо розібрати вираз (невідома помилка): \ y = y(\omega)
, визнавчального план компенсації невязок .

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

оптимального плану - компенсації обчислюється як рішення задачі лінійного програмування (21.5) - (21.7).

Виконала: Татьяненко Марина Олександрівна. Редагував: Білобабченко Анатолій Сергійович