Стохастическое программирование

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

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

. (6.17)

Исходя из цели, сформулированной в задаче, нужно найти такое решение (то есть, строку матрицы (6.17.)), которое будет оптимальным (например, позволяет минимизировать средние затраты ). Для определения оптимального решения используют различные критерии. Остановимся на двух из них.

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

Таблица 6.12.

Матрица целевых функций, иллюстрирующая применение минимаксного критерия

i j
	0,2	0,3	0,25	0,4
	0,1	0,2	0,15	0,3
	0,4	0,1	0,25	0,15

, , , .

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

Другим критерием является критерий минимаксного риска (критерий Сэвиджа).

Вводится понятие риска: . Критерий заключается в определении такой строки , для которой величина минимальна.

Поэтапное решение задачи

Решение той или иной задачи стохастического программирования часто проводится поэтапно: решение уточняется с ученом проведенных наблюдений . Таким образом, получение постепенно уточняемого решения можно представить в виде цепочек двух типов: (1 тип), (2 тип). Цепочка –этапная, если встречается в ней раз.

Цепочка 1 типа соответствует задаче перспективного этапного стохастического программирования (например, принятие плана экономического развития до 2050 года), а цепочка 2 типа соответствует задаче оперативного этапного стохастического программирования (например, решение той или иной производственной задачи). Обозначим через — состояния, от которых зависит решение задачи. Тогда задачу стохастического программирования можно сформулировать следующим образом:

(6.18.)

,

Из (6.18.) следует, что оптимальное решение будет зависеть от состояний . Если в результате наблюдений становится известным, то задача (6.18.) будет представлять собой задачу нелинейного программирования. Как отмечалась выше, уточнение и оптимального решения проводится поэтапно. Остановимся в этой связи подробнее на задаче стратегического двухэтапного стохастического программирования.

Двухэтапная задача

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

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

, (6.19)

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

Эквивалентная задача нелинейного программирования

Как уже отмечалось, при фиксированном задача стохастического программирования трансформируется в задачу нелинейного программирования. Существуют задачи стохастического программирования, которые можно заменить на эквивалентные задачи нелинейного программирования. Рассмотрим такую задачу. Пусть требуется минимизировать линейную функцию при условиях: , где — элементарное событие вероятностного пространства , , — алгебра событий. Такие условия называются жесткими ограничениями. Иначе их можно записать просто в виде неравенств: , (эти неравенства реализуются с вероятностью единица). Будем предполагать, что ограничения выполняются для всех возможных . Тогда получим задачу нелинейного программирования с конечным или бесконечным числом ограничений. Рассмотрим частный случай такой задачи, а именно случай линейных ограничений:

, , , (6.20)

,

где — случайные величины, . Нужно найти такие , которые удовлетворяли бы этим ограничениям при любых . Если и независимы, то, определив максимальный из возможных коэффициентов (обозначим его ) и минимальный элемент из всех возможных, , вместо ограничений (6.20.) получим следующие:

, , , . (6.21)

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