Область визначення двохетапної задачі з випадковим вектором обмежень.

Матеріал з Вікі ЦДУ
Версія від 22:09, 11 квітня 2013; Олійник Артем (обговореннявнесок)

(різн.) ← Попередня версія • Поточна версія (різн.) • Новіша версія → (різн.)
Перейти до: навігація, пошук

Розглянемо двоетапну задачу стохастичного програмування:

Неможливо розібрати вираз (невідома помилка): \min_x m_{\infty}\{cx+P(x,A,b)\}


Неможливо розібрати вираз (невідома помилка): A^{(1)}x=b^{(1)}


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


Нехай випадковими є тільки складові вектора обмежень b. Всі інші параметри умов задачі – детерміновані.

Єдине припущення, з яким ми пов’язуємо вибір випадкового вектора Неможливо розібрати вираз (невідома помилка): b(\omega) , заключається в тому, що його розподіл не повинен залежати від вибору попереднього плану x.

Згідно раніше розглянутої теореми, для загальної двоетапної задачі множина K попередніх планів – опукла. Для розглянутого часткового випадку можна довести більш сильне твердження. Виявляється, що в цьому випадку множина K не тільки опукла, але й багатогранна. Більше того, можна явно записати систему лінійних нерівностей, що визначають множину К.

Нагадаємо деякі поняття, що необхідні для наступних побудов.

Як відомо, опуклий багатогранний Конус С може бути представлений або як невід’ємна комбінація скінченного числа векторів, або як перетин скінченного числа півпросторів.

Еквівалентність двох визначень опуклого багатогранного конуса С використовується для приведення у відповідність кожній матриці В так звану полярну матрицю Неможливо розібрати вираз (невідома помилка): B^* .

Матриця Неможливо розібрати вираз (невідома помилка): B^*

(розмірності Неможливо розібрати вираз (невідома помилка): l x m

) називається полярною до матриці В (розмірності Неможливо розібрати вираз (невідома помилка): m x n_1 ), якщо Неможливо розібрати вираз (невідома помилка): B^*

— матриця з мінімальним числом рядків, що задовольняють умові:




Виконав: Олійник Артем Олександрович