VII Международная студенческая научная конференция Студенческий научный форум - 2015

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

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

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

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

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

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

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

1. Характер решений;

2. Выбор показателя качества решения (критерия);

3. Способ декомпозиции ограничений задачи.

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

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

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

минимизировать при условии .

Существуют следующие формы ограничений:

а)

б)

в)

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

Исходные данные этой задачи приводятся в табл.1. Пусть фермер установил, что комбикорм для свиней должен удовлетворять некоторым минимальным требованиям с точки зрения питательности. Они приведены в табл.1. Пусть удельные затраты на закупку единицы веса зерна видов 1, 2 и 3 составляют соответственно 41, 35 и 96 услов.денеж.ед. на 1 кг зерна. Требуется определить, какая из всех возможных смесей, удовлетворяющих требованиям на питательность, является самой дешевой. Обозначим через искомое количество зерна каждого вида.

Таблица 1.

Ингредиенты в составе смеси	Содержание ингредиента в единице зерна вида			Минимальные потребности на период
	1	2	3
А	2	3	7	³1250
	1	1	0	³250
C	5	3	6	³900
D	0,6	0,25	1	³232,5

Тогда требуется найти такие для которых

(1) при условиях:

, (ингредиент А);

, (ингредиент В);

(ингредиент С); (2)

(ингредиент D).

Допустим, что минимальные суммарные потребности в компонентах , , , являются случайными величинами , распределенными равномерно в интервалах [1000, 1500], [200, 300], [500, 1000], [150, 250] соответственно.

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

(3)

где – соответствующее значение случайной величины , удовлетворяющее условию =0.80, откуда =1400. Аналогично находят значения . Далее решают детерминированную эквивалентную задачу ЛП (1), (3). Ее оптимальное решение: = 162.5, = 177.5, = 103.5, а соответствующие минимальные расходы равны 20.693.

Использованные источники:

1. Юдин Д.Б. «Математические методы управления в условиях неполной информации: Задачи и методы стохастического программирования.» Изд.2 2010

2. Юдин Д.Б. «Задачи и методы стохастического программирования.» Изд.22010.

Код для цитирования: Скопировать