Сведение двухэтапной задачи стохастического линейного программирования с квантильным критерием к одноэтапной

В предыдущем разделе показано, что в частном случае постоянных цен исходную задачу (4) можно записать в форме двухэтапной задачи стохастического линейного программирования с квантильным критерием. Исследуем полученную задачу (12).

Рассмотрим задачу второго этапа (19). Заметим, что из ограничений (15), (16), (18) при неотрицательности параметров , , , следует ограниченность множества допустимых стратегий в задаче (19). При тех же значениях параметров , , и неотрицательном нулевой вектор переменных удовлетворяет ограничениям задачи (19), поэтому множество допустимых стратегий в задаче (19) непусто. Значит, при указанных ограничениях на параметры решение задачи (19) существует при любой допустимой стратегии первого этапа и любой реализации вектора случайного спроса.

Из теории двойственности задач линейного программирования известно, что в случае существования решения задачи линейного программирования (19) оптимальные значения критериев задачи (19) и двойственной к ней совпадают. Таким образом,

где — вектор двойственных переменных, — множество допустимых значений двойственных переменных.

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

Найдём множество , состоящее из всех вершин множества . Рассмотрим матрицу . Пусть — базисная подматрица (невырожденная квадратная подматрица размерности матрицы ). — подматрица матрицы , составленная из строк , которые не вошли в соответствующую базисную подматрицу .

Рассмотрим вектор . Пусть — подвектор вектора , составленный из тех элементов , номера которых совпадают с номерами строк матрицы , вошедшими в матрицу . Пусть — соответствующий подвектор вектора , составленный из элементов , которые не вошли в .

Тогда множество представимо в виде

(23)

где — число базисных подматриц матрицы .

Таким образом, для нахождения всех вершин множества необходимо перебрать , где — биномиальный коэффициент, невырожденных квадратных подматриц матрицы , последовательно решая системы

Пусть множество состоит из точек. Тогда функцию оптимального значения критерия задачи второго этапа можно записать в виде

Подставим полученную функцию в задачу (12):

где ,

Таким образом, двухэтапная задача (12) сводится к одноэтапной задаче (26) стохастического линейного программирования с квантильным критерием [11], в которой целевая функция потерь имеет вид (27).

В [12] доказана следующая теорема.

Теорема 1[12]. Если , и множество состоит только из нулевого вектора, то решение задачи (26) существует и .

Заметим, что теорема сформулирована в отсутствие каких-либо предположений о виде закона распределения вектора случайных параметров .

Справедливо следствие из теоремы 1.

Следствие. Если , , , , и выполнено условие

то решение задачи (12) существует и .

Доказательство. Выше была доказана эквивалентность задач (26) и (12) при выполнении условий , , , . Значит, решения данных задач либо совпадают, либо не существуют. В силу структуры матрицы множество состоит только из нулевого вектора. Кроме того, при выполнении условий (28) гарантируется непустота множества допустимых стратегий первого этапа. Таким образом, все условия теоремы 1 выполнены. Следствие доказано. ■

С экономической точки зрения ограничение (28) означает, что максимальный объём инвестирования превосходит суммарный объём инвестирования, необходимый для поддержания производства на прежнем уровне.