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

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

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

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

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

(5.45)

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

(5.46)

(5.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. Известны законы распределения случайных величин. Такие задачи называют задачами планирования в условиях риска.

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

(5.48)

, (5.49)

(5.50)

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

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

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

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

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

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

(5.51)

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

(5.52)

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

(5.53)

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

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

(5.54)

(6.55)

(5.56)

(5.57)

где а_ij и b_i - случайные величины, d_i - заданные уровни вероятности.

Обозначим:

(5.58)

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

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

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

(5.59)

(5.60)

(5.61)

(5.62)

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

(5.63)

(5.64)

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

(5.65)

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

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

(5.66)

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

(5.67)

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

(5.68)

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

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

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

(5.69)

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

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

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

(5.70)

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

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

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

Если требуется решение вопросов о выборе схемы прикрепления поставщиков и потребителей продукции, используются модели транспортного типа. Классическая транспортная задача заключается в планировании прикрепления поставщиков к потребителям продукции и формулируется следующим образом: однородный продукт, находящийся в m пунктах производства в количестве Р₁,Р₂,...Р_m, требуется доставить в n пунктов потребления. Потребность продукции в этих пунктах равна S₁,S₂,...S_n.

Экономико-математическая модель задач транспортного типа:

целевая функция - затраты на перевозку продукта должны быть минимальными:

(5.71)

Ограничения:

1. Вся продукция от предприятий-поставщиков отправляется потребителям:

(5.72)

2.Все потребители обеспечены продукцией:

(5.73)

3. Мощность поставщиков равна потребности в продукции (условие закрытости):

(5.74)

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

1. Запрет каких-либо перевозок.

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

2. Ограниченность пропускных способностей коммуникаций.

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

(5.75)

где d_ij - пропускная способность транспортной линии.

3. Нарушение условия равенства производства и потребления (открытая транспортная задача).

Если не вся продукция нужна потребителям, т.е. то ограничение на продукцию, отправляемую из пунктов производства, принимает вид

(5.76)

Транспортная задача сводится к классическому виду путем введения фиктивного потребителя S _n+1 с потребностью

(5.77)

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

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

(5.78)

и ограничения на продукцию, поступающую в каждый пункт потребления, будут

(5.79)

Этот случай также сводится к классической транспортной задаче путем введения фиктивного поставщика с объемом производства

(5.80)

Решение задач по планированию перевозок

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

Исходные данные представлены в табл. 5.12.

Таблица 5.12

Исходные данные для расчета

Потребители	Поставщики	Потребность в материалах
База №1	База №2	База №3
Объект № 1
Объект № 2
Объект № 3
Объект № 4
Мощности поставщиков, т

В соответствующих клетках таблицы задана стоимость перевозок 1 тонны груза от поставщиков к потребителям - с_ij, тыс.р. за 1 тонну. Потери, связанные с хранением продукции у поставщиков, составляют: 5, 7, и 4 тыс. р. за 1 тонну для базы N 1, 2 и 3 соответственно.

Решим задачу с использованием программы симплекс-метода. С учетом переменных, определяющих объем грузов, остающихся на базах, размерность задачи составляет переменных.

Симплекс-матрица представлена в табл. 5.13.

Таблица 5.13

Симплекс-матрица для решения транспортной задачи

Номер строки

Х1

Х2

Х3

Х4

Х5

Х6

Х7

X8

Х9

Х10

Х11

Х12

Х13

Х14

Х15

Вид связи

Правая часть ограничения

F

→

min

=

=

=

=

=

=

=

Решение задачи в системе электронных таблиц EXCEL осуществляется с помощью пункта меню «Сервис», «Анализ данных». Необходимо представить симплекс-матрицу в виде формул.

Результаты решения представлены в табл. 5.14.

Таблица 5.14

Результаты решения

Индексы базисных переменных	Оптимальные значения базисных переменых

Оптимальное значение функции цели 6210.0.

По результатам расчета можно сделать следующие выводы. Поскольку x₁₅=0, вся продукция базы N 3 направляется потребителям. На базе N 1 остается 50 тонн продукции, на базе N 2 - 120 тонн. С учетом того, что потери, связанные с хранением нереализованной продукции учтены в целевой функции, оптимальная стоимость перевозок составит

6210 - 50 5 - 120 7 = 5120 тыс.р.

При этом на объект N 1 продукция доставляется с базы N 1 в объеме 100 тонн; на объект N 2 - с базы N 2 в объеме 120 тонн; на объект N 3 - с базы N 2 в объеме 100 тонн и с базы N 3 в объеме 100 тонн; на объект N 4 - с базы N 1 в объеме 160 тонн.