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

В задаче линейного программирования:

заданные величины c_j, a_ij, b_i, d_j, D_j. Часто на практике величины c_j, a_ij, b_j, могут быть случайными. Так, если b_i – ресурс, то он зависит от ряда факторов. Аналогично, c_j – цены – будут зависеть от спроса и предложения, a_ij – расходные коэффициенты – от уровня техники и технологии.

Задачи, в которых c_j, a_ij, b_i – случайные величины, относят к задачам стохастического программирования.

В задачах стохастического программирования случайный характер величин указывают различными способами:

- реализацией случайных величин;

- законом распределения случайных величин.

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

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

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

Задача стохастического программирования предусматривает стохастическую постановку и целевой функции, и ограничений.

Стохастическая постановка целевой функции может быть двух видов: М–постановка и Р–постановка.

При М – постановке случайная величина заменяется ее математическим ожиданием и задача сводится к оптимизации детерминированной целевой функции:

где – математическое ожидание случайной величины c_j.

При Р – постановке целевая функция будет иметь вид:

- при максимизации целевой функции

обозначает максимизацию вероятности того, что случайная величина будет не меньше некоторого значения r;

- при минимизации целевой функции

обозначает максимизацию вероятности того, что случайная величина будет не больше некоторого значения r.

Наиболее распространены СТП–постановки в вероятностных ограничениях вида:

где a_ij, b_i – случайные величины; a _i – заданные уровни вероятности. Так, ограничение (а) означает, что вероятность соблюдения неравенства должна быть не меньше, чем a _i. Аналогичный смысл и других ограничений.

Для случая, когда вероятностные ограничения представлены в виде типа (а), задачу СТП можно записать:

- при М–постановке

- при P –постановке:

- в случае максимизации целевой функции

- в случае минимизации целевой функции

где c_j, a_ij, b_i – случайные величины.

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

Задачи (_*), (_**), (_***) непосредственно решены быть не могут. Одним из возможных методов их решения может быть представление их в виде детерминированного эквивалента.