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

Стохастическое программирование - это метод решения задач на оптимум в условиях неопределенности, случайности. В любом случае решение экономических задач - на максимум прибыли или минимум затрат, показатели прибыли или затрат, строго говоря, являются величинами случайными. Предполагая, что эти величины детерминированные (наперед заданные), мы делаем известные допущения.

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

Пример постановки задачи в детерминированной форме.

Целевая функция:

(4.33)

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

(4.34)

(4.35)

В качестве исходных данных необходимо задавать значения параметров c_j, a_ij, b_i, d_j, D_j, входящих в ЭВМ. В практических расчетах принимают, что эти значения являются детерминированными, т.е. не зависят о случайны факторов.

Однако, на самом деле только параметры d_j и D_j, устанавливающие предельно допустимые значения x_j, по смыслу будут детерминированными, остальные параметры с_i, а_ij, b_j- случайные величины. Например, если ресурсом являются машины, то его величина зависит от надежности работы машин, их технического состояния. Аналогичное утверждение относится к с_j и а_ij. Таким образом, в общем случае c_j, a_ij и b_i являются случайными величинами.

Задачу со случайными параметрами обычно называют задачей стохастического программирования (СТП). С точки зрения полноты описания случайной величины рассмотрим два случая:

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

2. Известны законы распределения случайных величин. Такие задачи называют задачами планирования в условиях риска.

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

(4.36)

, (4.37)

(4.38)

Рассчитаем план для 2-х разных случаев. Худшим (пессимистическим) будет такой план, в котором ресурсы, принимаем наименьшими min b_i, а их расход наибольшим - max a_ij. Ожидаемая прибыль будет находиться на нижнем пределе min c_j. Подставив эти значения, получим обычную задачу линейного программирования. Если она имеет решение, получим пессимистический план производства min x_j (j=1, n), выполнение которого гарантировано, но этот план дает низкий экономический эффект.

Лучшим (оптимистическим) будет такой план, в котором ресурсы, располагаемые предприятием, принимаем наибольшими max b_i, прибыль с каждого изделия наибольшая max c_i.

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

Задача в пессимистической постановке очень часть может оказаться несовместной.

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

Если в целевой функции задачи ЛП

(4.39)

где С_j - случайные величины, то обычно принимается максимизация (минимизация) математического ожидания целевой функции:

(4.40)

что можно записать так:

(4.41)

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

Ограничения. В задаче СТП возможны следующие варианты ограничений:

(4.42)

(4.43)

(4.44)

(4.45)

где а_ij и b_i - случайные величины,

d_i - заданные уровни вероятности.

Обозначим:

(4.46)

где Y_i - случайная величина.

Обычно принимают, что случайные величины c_j, a_ij, b_i, y_i подчиняются нормальному закону распределения с известным математическим ожиданием и дисперсией.

Подставив (4.46) в неравенства получим:

(4.47)

(4.48)

(4.49)

(4.50)

Случайная величина y_i при независимых d_i и Q_i будет иметь математическое ожидание и дисперсию:

(4.51)

(4.52)

где - дисперсия случайной величины bi. Для первого варианта ограничения (4.47 – 4.50) можно записать:

(4.53)

где t_di - коэффициент, учитывающий закон распределения случайной величины, определяемый аналитически или таблично в зависимости от значения вероятности d_i;

y_i - среднеквадратическое отклонение случайной величины y_i.

Подставив в (4.52) значения Y_i и _i получим:

(4.54)

После преобразований получим:

(4.55)

Если сравнить выражение (4.55) с аналогичным ограничением в детерминированной постановке

(4.56)

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

1. Выполнен переход от детерминированных значений к математическим ожиданиям случайных величин Q_ij и b_i.

2.Появился дополнительный член:

(4.57)

который учитывает все вероятностные характеристики задачи:

- закон распределения с помощью t_di;

- заданный уровень вероятности d_i, дисперсии случайных величин Q_ij, равные и дисперсию случайных величин b_i, равные . Таким образом, получим

(4.58)

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

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

Вопросы для самопроверки:

1. Что такое критерий оптимальности, целевая функция, ограничения?

2. Приведите пример задачи оптимизации, составьте целевую функцию и систему ограничений задачи.

3. Охарактеризуйте область применения и специфику моделей стохастического программирования.

Модели оптимального планирования транспортного типа