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

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

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

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

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

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

В задаче линейного программирования

заданы величины cj, aij, bi, Dj. Часто на практике величины cj, aij bj, могут быть случайными. Так, если bi — ресурс, то он зависит от ряда факторов. Аналогично, сj — цены — будут зависеть от спроса и предложения, aij — расходные коэффициенты — от уровня техники и технологии.

Задачи, в которых сj, аij, bi — случайные величины, относят к задачам стохастического программирования. Переход от чистых стратегий к смешанным расширяет область определения задачи. Вычисление оптимальной смешанной стратегии иногда называют определением решающего распределения стохастической задачи.

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

где ćj – математическое ожидание случайной величины cj .

При P-постановке целевая функция будет иметь вид:

при минимизации целевой функции

обозначает максимизацию вероятности того, что случайная величина будет не больше некоторого значения r;

при максимизации целевой функции

обозначает максимизацию вероятности того, что случайная величина будет не меньше некоторого значения r;

15. Генерация альтернатив решений: понятие генетического алгоритма.

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

В процессе анализа и решения сложной проблемы мы часто интуитивно комбинируем известные частичные решения, пытаясь найти решение общей задачи как комбинацию частных решений, предполагая при этом, что комбинация, состоящая из лучших вариантов, даст лучшее решение. Аналогия не вполне точная, но полезная для понимания идеи генетического алгоритма. Таким образом, в методе генетических алгоритмов сразу встает вопрос, какие параметры или характеристики при анализе ситуации следует варьировать, а какие сохранить без изменения. От этого, конечно, зависят и результаты анализа. Чаще всего используется два генетических оператора: crossover (перекрестный обмен) — обмен секциями хромосом родителей и mutation (мутация) — случайная модификация хромосом.

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

1111010

1* 1* 0* *

Тогда схема для этого примера показано под чертой. В схеме символ * может быть заменен любым символом из используемого алфавита. В нашем случае нулем или единицей. Схема может рассматриваться как определение подмножеств подобных хромосом или гиперповерхностей в n-мерном пространстве. Легко представить, что каждая из хромосом может принадлежать и некоторым другим схемам. Некоторые из этих схем будут включать обе хромосомы, другие только одну. Каждый раз когда определяется годность данной хромосомы, собирается информация о возможной годности каждой схемы, которой принадлежит хромосома. Конечно, возникает вопрос сколько схем следует проанализировать. Перебор может оказаться достаточно большим. Один из путей сокращения перебора – ужесточение произвола в схемах, т.е. уменьшение в них символов * и сокращение числа самих схем. Характеристиками схем являются длина и порядок. Длина определяется числом позиций между первой и последней (т.е. не *) позициями в схеме, а порядок числом определенных (не *) позиций. Другой характеристикой является отношение годности, т.е. присутствие схемы в популяции схемы.

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

15. Генерация альтернатив решений: Дерево решений

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