Відмінності між версіями «Постановка двохетапної задачі СП.»

Версія за 20:22, 11 квітня 2013

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

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

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

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

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

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