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

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

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

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

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

где Сведение двухэтапной задачи стохастического линейного программирования с квантильным критерием к одноэтапной - student2.ru — вектор двойственных переменных, Сведение двухэтапной задачи стохастического линейного программирования с квантильным критерием к одноэтапной - student2.ru — множество допустимых значений двойственных переменных.

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

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

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

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

Сведение двухэтапной задачи стохастического линейного программирования с квантильным критерием к одноэтапной - student2.ru (23)

где Сведение двухэтапной задачи стохастического линейного программирования с квантильным критерием к одноэтапной - student2.ru — число базисных подматриц матрицы Сведение двухэтапной задачи стохастического линейного программирования с квантильным критерием к одноэтапной - student2.ru .

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

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

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

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

Подставим полученную функцию Сведение двухэтапной задачи стохастического линейного программирования с квантильным критерием к одноэтапной - student2.ru в задачу (12):

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

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

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

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

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

Теорема 1[12].Если Сведение двухэтапной задачи стохастического линейного программирования с квантильным критерием к одноэтапной - student2.ru , Сведение двухэтапной задачи стохастического линейного программирования с квантильным критерием к одноэтапной - student2.ru и множество Сведение двухэтапной задачи стохастического линейного программирования с квантильным критерием к одноэтапной - student2.ru состоит только из нулевого вектора, то решение задачи (26) существует и Сведение двухэтапной задачи стохастического линейного программирования с квантильным критерием к одноэтапной - student2.ru .

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

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

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

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

то решение задачи (12) существует и Сведение двухэтапной задачи стохастического линейного программирования с квантильным критерием к одноэтапной - student2.ru .

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

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

Наши рекомендации