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

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

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

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

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

(4.45)

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

(4.46)

(4.47)

В качестве исходных данных необходимо задавать значения параметров 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.48)

, (4.49)

(4.50)

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

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

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

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

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

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

(4.51)

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

(4.52)

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

(4.53)

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

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

(4.54)

(4.55)

(4.56)

(4.57)

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

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

Обозначим:

(4.58)

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

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

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

4.59)

(4.60)

(4.61)

(4.62)

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

(4.63)

(4.64)

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

(4.65)

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

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

Подставив в (7) значения Y_i и _i  из формулы (6) получим:

(4.66)

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

(4.67)

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

(4.68)

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

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

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

(4.69)

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

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

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

(4.70)

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

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