МАТЕМАТИЧЕСКОЕ ПРОГРАММИРОВАНИЕ

6. ЗАДАЧИ И МЕТОДЫ СТОХАСТИЧЕСКОГО ПРОГРАММИРОВАНИЯ

Детерминированные модели математического программирования часто оказываются неадекватными реальным процессам в экономике. Это объясняется прежде всего неточностью и вероятностным характером тех показаний и ограничений, которые вкладываются в модели. Планирование на основе наиболее оптимистических прогнозов, факторов, обусловливающих производство и потребление, зачастую оказывается несостоятельным из-за отсутствия резервов для коррекции неувязок, которые возникают, если какое-либо звено в цепи производства дает меньше, чем ожидалось по оптимистичному прогнозу. Намного целесообразнее планировать по усредненным показателям, если их разброс достаточно велик. И в этом случае реальные значения показателей могут значительно отличаться от средних значений, и предложенный план окажется непригодным.

Для решения задач планирования в условиях неопределенности разработаны специальные математические модели и методы — стохастическое программирование.

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

78

1) допускается дополнительная закупка покупных изделий по высоким ценам;

2) допускается отказ от части заявленных закупок, связанный с определенным штрафом;

3) спрос потребителей может быть удовлетворен не полностью, но при этом предприятие также несет дополнительные потери в виде штрафов.

Пусть (щ — норма расхода изделия (материала) j-ro типа на производство единицы продукции г-го вида; Xj — количество заявленного (ресурса, материала) j-ro типа; Cj — его цена; %jj — количество дополнительно покупаемого ресурса; dj — его цена; Zj — величина части ресурса j-ro типа, от которой отказываются; fj — штраф за отказ от единицы ресурса; ш, — планируемый выпуск продукции г-го типа; і — случайный вектор спроса на продукцию, производимую предприятием; bj — доход от реализации единицы продукции г-го типа; gi — штраф за недопоставку единицы ресурса г-го типа.

Подобная задача решается в два этапа. На первом этапе выбирается вектор {Жу}"=1 — заявки на необходимые производству ресурсы, на втором этапе при известном {Сі}™ і выбираются переменные {t/j}"=1; {zj}"=1; {ш,}™1 — определяющие способы использования заказанных материалов и план производства.

Такие задачи оптимального планирования называются двухэтап-ными задачами стохастического программирования. Чтобы построить адекватную описанной задаче математическую модель, рассматривают сначала задачу второго этапа при фиксированном плане первого этапа {Жу}"=1. Построенная здесь модель зависит не только от {xj}, но и от случайного вектора {£j(w)}. В этом случае необходимо рассматривать математическое ожидание (Мш) функции-критерия, т. е.

Ф({Жі}) = ммш, {Ш})Задача первого этапа состоит в том, чтобы выбрать план х = {xj}, позволяющий максимизировать Ф(ж). Хотя подобная задача и является ЗВП, однако неявный вид функции Ф(ж) (как математического ожидания) создает значительные трудности в вычислении. Только если множество значений случайного вектора конечно, та двухэтап-ная линейная задача стохастического программирования сводится к ЗЛП специального вида.

В общем случае линейная стохастическая двухэтапная задача формулируется следующим образом.

79

Заданы матрица А размера тпхгц, семейство матриц размера п X ri2, зависящих от случайного параметра (. вектор с и семейства векторов с|, размерности соответственно щ,П2 и т. Для каждого фиксированного £ рассматривается задача

min(e|, у)

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

/Л у >     — Лт.

Пусть оптимальное решение этой задачи у|(ж) существует при любом СТребуется определить

тііі[(с,ж)МсЦ,у|(ж))],

где С — случайный параметр; М$ — символ математического ожидания.

Пусть М^(с^, у|(ж)) = F(x). Доказано, что функция F(x) является выпуклой при ж > 0. Таким образом, линейная стохастическая двухэтапная задача сводится к задаче минимизации выпуклой функции

/(ж) = (c,x) + F(x)

при ограничении ж > 0.

Если количество реализаций случайного вектора £ конечно, то получаем ЗЛП блочной структуры.

К ЗНЛП сводятся также задачи стохастического программирования, в которых решение принимается за один этап без учета конкретной реализации случайного параметра ("состояния природы"), как правило, в таких задачах целевая функция и ограничения понимают в некотором усредненном по случайному параметру смысле. Основная трудность при решении таких задач состоит в том, что целевую функцию и функцию ограничений в явном виде можно получить лишь в исключительных случаях, а можно только непосредственно вычислить значения этих функций и их градиентов при фиксированных ж и ш.

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

80

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

 

 ...  9



Обратная связь

По любым вопросам и предложениям

Имя и фамилия*

Е-меил

Сообщение*

↑ наверх