Студопедия.Орг Главная | Случайная страница | Контакты | Мы поможем в написании вашей работы!  
 

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



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

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

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

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

(5.45)

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

(5.46)

(5.47)

В качестве исходных данных необходимо задавать значения параметров cj, aij, bi, dj, Dj, входящих в ЭВМ. В практических расчетах принимают, что эти значения являются детерминированными, т.е. не зависят от случайных факторов.

Однако на самом деле только параметры dj и Dj, устанавливающие предельно допустимые значения xj, по смыслу будут детерминированными, остальные параметры сi, аij, bj- случайные величины. Например, если ресурсом являются машины, то его величина зависит от надежности работы машин, их технического состояния. Аналогичное утверждение относится к сj и аij. Таким образом, в общем случае cj,aij и bi являются случайными величинами.

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

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

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

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

(5.48)

, (5.49)

(5.50)

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

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

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

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

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

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

(5.51)

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

(5.52)

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

(5.53)

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

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

(5.54)

(6.55)

(5.56)

(5.57)

где аij и bi - случайные величины, di - заданные уровни вероятности.

Обозначим:

(5.58)

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

Обычно принимают, что случайные величины cj,aij,bi,yi подчиняются закону нормального распределения с известным математическим ожиданием и дисперсией.

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

(5.59)

(5.60)

(5.61)

(5.62)

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

(5.63)

(5.64)

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

(5.65)

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

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

(5.66)

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

(5.67)

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

(5.68)

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

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

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

(5.69)

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

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

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

(5.70)

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

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

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

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

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

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

(5.71)

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

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

(5.72)

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

(5.73)

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

(5.74)

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

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

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

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

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

(5.75)

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

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.

По результатам расчета можно сделать следующие выводы. Поскольку x15=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 тонн.





Дата публикования: 2014-11-02; Прочитано: 1040 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!



studopedia.org - Студопедия.Орг - 2014-2024 год. Студопедия не является автором материалов, которые размещены. Но предоставляет возможность бесплатного использования (0.013 с)...