Построение алгоритма решения

Постановка задачи

Рассмотрим двухэтапную задачу квантильной оптимизации с критерием в форме математического ожидания следующего вида:

при ограничениях

,

где ,

, причём матрица Т развёрнута определённым образом (по строкам или по столбцам).

Пусть имеет конечное распределение, а именно . Тогда решение исходной задачи может быть сведено к решению задачи линейного программирования

при ограничениях

.

Однако, эта задача, если

, имеет размерность технологической матрицы , что весьма внушительно, поскольку К может быть достаточно большим числом не только потому, что велико количество возможных реализаций случайных факторов в прикладной задачи, но и потому, что может подразумеваться несколько периодов планирования.

Можно попытаться предложить некоторые варианты сведения полученной ЗЛП к ряду ЗЛП меньшей размерности.

Построение алгоритма решения

Предположим, что у нас есть некоторое субоптимальное решение , которому соответствует значение критерия второго этапа . В качестве первичной субоптимальной пары может быть взята , которая является формальным решением задачи . Смысл этого хода в том, что мы временно не используем никакой информации о втором этапе, а предполагаем, что он уже оптимизирован, насколько возможно.

Теперь, если у нас есть некоторая субоптимальная пара , то мы должны убедиться в том, что она удовлетворяет всем ограничениям задачи. Для этой проверки достаточно решить серию из К задач при ограничениях , где и - векторы невязок, I – единичная матрица, . Если для какого-либо , то как сумма невязок, и, используя двойственные переменные, получим . Всегда , так что для выполнения условий допустимости субоптимальной пары () нужно потребовать , то есть

Условия оптимальности можно получить, рассматривая функцию , являющуюся выпуклой по . Тогда , где – субградиент функции в точке . С использованием двойственных переменных можно записать , , тогда , а , тем самым и для должно быть выполнено условие оптимальности .

Из этих соображений и строится алгоритм L-shaped метода.

Дата добавления: 2015-10-23