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

 

 

 

 

 

Тема: «Параметрическое и стохастическое программирование. Постановка задачи и методы её решения»

 

 

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

 

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

В общем виде задача Параметрического программирования заключается в максимизации целевой функции по всем х=(x₁,...,х _п) , удовлетворяющим ограничениям

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

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

Если при любом фиксированном  задача Параметрического программирования представляет собой задачу линейного программирования( выпуклого программирования и т. п.), то говорят о задаче линейного (соответственно выпуклого и т. <п.) параметрического программирования. В общем виде проблематику Параметрического программирования можно охарактеризовать следующим образом. 1) Нахождение и выяснение свойств множеств разрешимости 2) Нахождение областей устойчивости решений, характеризация их строения; анализ поведения неустойчивых задач. 3) Характеризация зависимости оптимального значения целевой функции от вектора параметров.

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

при условиях

где . Тогда существует такое разбиение на конечное число открытых слева интервалов: = (где интервал неограничен слева, неограничен справа, причем возможен случай совпадения одного из них с ), что при всех соответствующая задача линейного Параметрического программирования разрешима, причем на каждом интервале , она имеет один и тот же базис. Исключение могут составлять лишь интервалы и , на которых целевая функция (2) может быть неограниченна. Таким образом, в данной задаче множество разрешимости представляет собой объединение всех за возможным исключением и (или) . Далее, оптимальное значение целевой функции на каждом , является выпуклой кусочно линейной функцией параметра . Численные методы решения однопараметрических задач линейного Параметрического программирования представляют собой модификации симплексного метода; в случае многомерного пространства параметров приходится привлекать более сложные соображения.

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

 

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

В задачах прикладной математики можно различать детерминированные  и стохастические задачи. В процессе решения последних развилась  обширная в настоящее время математическая дисциплина — теория вероятностей.

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

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

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

   1.1

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

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

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

При М-постановке случайная  величина заменяется ее математическим ожиданием и задача сводится к оптимизации детерминированной целевой функции:

     1.2

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

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

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

    1.3

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

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

    1.4

 

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

Наиболее распространены СТП-постановки в вероятностных ограничениях вида:

 

    1.5

 

где аi j , bi — случайные величины; ai — заданные уровни вероятности.

Так, ограничение (а) означает, что вероятность соблюдения неравенства

      1.6

должна быть не меньше, чем  ai. Аналогичный смысл и других ограничений.

Для случая, когда вероятностные  ограничения представлены в виде типа (а), задачу СТП можно записать при М-постановке:

        1.7

 

При Р-постановке:

• в случае максимизации целевой функции

 

         1.8

 

• в случае минимизации целевой функции

 

          1.9

 

где cj , ai j , bi — случайные величины.

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

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