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

     До  сих пор нет достаточно конструктивного метода решения общей (даже линейной) двухэтапной задачи стохастического программирования. Стандартные методы выпуклого программирования в общем случае неприменимы для вычисления предварительного плана — решения выпуклой задачи первого этапа.

     Это подсказывает путь алгоритмизации решения  сложных задач в автоматизированных системах управления—замену трудоемких процедур, которые отвечают обоснованным (точным или приближенным) методам решения детерминированных экстремальных задач, относительно простыми «законами управления»—решающими правилами или решающими распределениями стохастического расширения соответствующих задач. 
Платой за упрощение задачи и за переход от громоздких алгоритмов к относительно простым решающим механизмам служат трудоемкая предварительная работа по построению «законов управления» и некоторая потеря эффективности решения задачи в каждом отдельном случае. 
В литературе по стохастическому программированию описаны многочисленные модели выбора решений, сформулированные в терминах стохастического программирования. Разнообразные задачи управления запасами—классические примеры стохастических моделей. Синтез систем массового обслуживания, удовлетворяющих заданным требованиям и оптимизирующих пропускную способность системы или определяемый ею доход, сводится к решению экстремальных стохастических задач.

      2.3. Пути решения задач

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

     Для каждого из трех путей присуща  своя  модель.      

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

     Доказательство  этого факта  приводится  на условном примере. Действительное оптимальное назначение транспорта по маршрутам при условии случайного спроса на маршруты и оптимальное  назначение, основанное на математическом ожидании спроса, почти никогда не совпадают. В данной работе не приводится алгоритма решения таких задач с большой размерностью. Разновидностью модели, используемой в [1], является модель из работы [2], имеющая отличие в экономической постановке. Если в [1] рассматривается транспортная  задача с неопределенным  спросом, то в [2] изучается  производственно-транспортная  задача с неопределенным спросом, что позволяет расширить класс  решаемых задач.       

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

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

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

     Точное  же решение задачи нахождения оптимального плана в двухэтапной задаче стохастического  линейного программирования наталкивается  на большую размерность задачи, что  ведет к большим затратам на получение результата. При условии, что случайная величина спроса на изделие предприятия имеет конечное число реализаций, решение задач такого объема затруднительно обычными линейными методами. В этом случае используют метод решения, предложенный работе [2].       

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

      2.4. Формальная постановка стохастической задачи

      
Приведем формальную постановку многоэтапной стохастической задачи. Пусть wi—набор случайных параметров i-го этапа, a xi—решение, принимаемое на i-м этапе. Обозначим

wk=(w1, … ,wk)

xk= (x1, … ,xn)  
k = 1,…,n . 
Общая модель многоэтапной задачи стохастического программирования имеет вид: 
Mwn y0(wn, xn)àmin, 
Mwk{yk(wk, xk)Ѕwk-1}іbk(wk-1) 
xkО Gk,k=1,…,n. 
Здесь y0 (wn, xn) —случайная функция от решений всех этапов, 
{yk(wk, xk) -случайная вектор-функция, определяющая ограничения k-го этапа;

bk(wk-1)—случайный  вектор;

Gk—некоторое  множество, определяющее жесткие  ограничения k-го этапа;

Mwk{ykЅwk-1}—условное  математическое ожидание yk в предположении,  что на этапах, предшествующих k-му, реализован набор 
wk-1=(w1, … ,wk-1).

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

     Для того чтобы постановка задачи была полной, необходимо еще указать, среди  какого класса функций (решающих правил x=x(w)ОХ от реализаций случайных исходных данных следует разыскивать решение. 
К моменту, когда должно быть принято решение k-го этапа, можно успеть обработать результаты наблюдения реализаций случая на этапах 1, ...,s; sЈk. 
В задачах решение на 1-м этапе принимается после реализации случайных параметров условий на предыдущем (i—1)-м этапе. Решающие правила имеют вид xi=xi(wi-1) , i = 1,…,n .

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

      Заключение 

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

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

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

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

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

      Список литературы 

     1.http://ru.wikipedia.org/wiki/%D0%A1%D1%82%D0%BE%D1%85%D0%B0%D1%81%D1%82%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%BE%D0%B5_%D0%BF%D1%80%D0%BE%D0%B3%D1%80%D0%B0%D0%BC%D0%BC%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5

     2. http://matmetod-popova.narod.ru/BB.htm

     3. Журнал «Государство и право», февраль 2005, №2 Н.М. Добрынин

     4. С.А. Минюк, Е.А. Ровба, К.К. Кузьмич «Математические методы и модели», ТетраСистемс 2002

     5. Меладзе В.Э. Стохастические методы в оценке бизнеса.// Вопросы оценки, №2, 2002