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

Стохастическое программирование

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

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

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

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

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

Стохастическое программирование используется для решения задач двух типов.

1. В задачах первого типа прогнозируются статистические характеристики множества одинаковых экстремальных систем. Это задачи пассивного СП.

2. В задачах второго типа строятся алгоритмы планирования и управления в условиях неполной информации. Это задачи активного СП.

В зависимости от постановки задачи стохастического программирования её решения или планы могут вычисляться в двух видах:

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

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

При построении моделей управления в условиях неполной информации существует два подхода к использованию информации:

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

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

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

 

 

Постановка задач СП

Большое число военных, экономических, технических задач записывается в виде задачи ЛП:

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

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

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

Задачи СП могут формулироваться в трех видах

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

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

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

Если в конкретной задаче требуется только чтобы вероятность попадания решения в допустимую область превышала некоторое заранее заданное число a >0 (обычно a >1/2), то такая постановка задач СП называется моделью с вероятностными ограничениями.

Если коэффициент c_j детерминирован, то целевая функция задачи с вероятностными ограничениями не изменяется. Если с_j случайно, то в качестве целевой функции задачи с вероятностными ограничениями берут математическое ожидание целевой функции

(10.1)

или вероятность превышения целевой функции некоторого фиксированного порога F₀ :

P(F>F₀).

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

 

 

(10.2)

 

 

(10.3)

 

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

(10.4)

такая постановка задач СП называется моделью со статистическими условиями.

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

Если в задачах присутствуют как вероятностные, так и статистические и жесткие условия, такие модели называются моделями со смешанными условиями.

 

Модели задач СП

Задачи СП различаются по трем признакам.

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

2. По выбору показателя качества, т. е. целевой функции. Еслинаходится:

а) математическое ожидание от целевой функции, т.е.

, то такие задачи называются М-моделями;

б) если минимизируется дисперсия целевой функции

то такие задачи называются V-моделями;

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

3. По способу расчленения ограничений задачи могут быть:

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

где a_i - вероятность соблюдения условий,

a_0i = 1 – a_i ¾ вероятность несоблюдения условий. (от 0 до 1)

б) С общими вероятностными ограничениями Р[АХ ≥ В] ≥ a, когда могут быть коррелированы параметры не только строки, но и между строками. В такой модели не учитывается сравнительная важность отдельных ограничений.

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

Задача планирования добычи угля в априорных решающих правилах

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

- мощность и угол падения пластов,

- обводнённость участков,

- склонность к выбрасыванию газов,

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

- надежность оборудования, эксплуатационные расходы.

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

Для простоты допускается:

- показатель плана определяется средним значением суммарных затрат,

- область определения плана задается спросом на добываемый уголь (требуемый объем добычи) и фондом заработной платы.

Задача планирования угледобычи следующая.

Для i шахты заранее разрабатывается несколько вариантов развития. Требуется установить наиболее рациональный, с точки зрения объединения шахт, вариант развития каждой шахты.

Пусть , если для i -й шахты принят j- й вариант, иначе По каждой шахте реализуется только один вариант, т. е. .

- годовые затраты на добычу угля в i- й шахте по j -му варианту при реализации w случайных параметров, зависящих от природных факторов.

- годовой объем добычи угля в i -й шахте по j -му варианту при реализации w случайных природных факторов.

- годовой фонд зарплаты i -й шахты по j -му варианту развития при реализации w случайных природных факторов.

d — требуемая в соответствии с планом более высокого уровня годовая добыча угля по объединению в целом.

k - общий фонд зарплаты по объединению.

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

. (10.5)

Ограничения имеют характер построчных вероятностных ограничений по соблюдению спроса и фонда заработной платы

(10.6)

 

 

(10.7)

 

В целом это типичная модель задачи стохастического программирования.