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

Минский институт управления 
 
 
 
 
 
 
 

Управляемая самостоятельная работа

по  дисциплине 
 
 

“ Высшая математика ” 

на  тему «Параметрическое и стохатическое программирование». 
 
 
 
 
 
 
 
 
 
 
 

Минск 2011 г. 

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

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

здесь x-вектор столбец размера n, C- вектор-строка размера 1´n, D - матрица размера n´n, симметричная и неотрицательно определенная (D ³ 0). b - столбец длины m. A - матрица размера m´n, ранг ее равен m (R(A) = m).         

 Имеет  место также условие неотрицательности компонентов вектора x:  

x ³ 0.   

Поскольку наличие  компонента Cx не оказывает существенного влияния на результаты, изложенные в настоящей работе, будем без ограничения общности предполагать вектор C нулевым. В такой поста

новке задача принимает вид:  

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

2. Графическое и аналитическое  решение задач  параметрического программирования

В практических задачах необходимо определить наибольшее и наименьшее значения функции (глобальный экстремум) в некоторой области. Говорят, что функция z = f (X) имеет в точке X⁰ заданной области D глобальный максимум (наибольшее значение) или глобальный минимум (наименьшее значение), если неравенство f(X) ≤ f(X⁰) или соответственно выполняется для любой точки X € D.  
Если область D замкнута и ограничена, то дифференцируемая функция z = f (X) достигает в этой области своих наибольшего и наименьшего значений или в стационарной точке, или в граничной точке области (теорема Вейерштрасса).

Граница области  D аналитически может быть задана системой уравнений (условий) относительно переменных x₁, x₂, ..., x_n. Поэтому, исследуя экстремальные свойства функции на границе, необходимо решить задачу определения условного экстремума.

Условный  экстремум. Пусть необходимо найти экстремум функции z = f (x₁, x₂, ..., x_n ) при условии, что переменные x₁, x₂, ..., x_n удовлетворяют, уравнениям

Предполагается, что функции f и φ_i , имеют непрерывные частные производные по всем переменным. Уравнения (2.32) называют уравнениями связи. Говорят, что в точке удовлетворяющей уравнениям связи (2.32), функция z = f (X) имеет условный максимум (минимум), если неравенство f(X⁰) ≥  f(X) (f(X⁰) ≤  f(X)) имеет место для всех точек X, координаты которых удовлетворяют уравнениям связи.  
Легко заметить, что задача определения условного экстремума совпадает с задачей нелинейного программирования. 
Один из способов определения условного экстремума применяется в том случае, если из уравнений связи (2.32) m переменных, например x₁, x₂, ..., x_n, можно явно выразить через оставшиеся n - m переменных:

Подставив полученные выражения для x_f в функцию z, получи 
мz_i = f(ψ_i (x_{m + 1} , ..., x_n ), ..., ψ_m (x_{m + 1} , ..., x_n ), x_{m + 1} , ..., x_n )

или

Задача сведена  к нахождению локального (глобального) экстремума для функции (2.34) от n - m переменных. Если в точке функция (2.34) имеет экстремум, то в точке функция z = f (x₁, ..., x_n ) имеет условный экстремум.

Пример 2.10.2

Метод множителей Лагранжа

Другой способ определения условного экстремума начинается с построения вспомогательной  функции Лагранжа, которая в области  допустимых решений достигает максимума  для тех же значений переменных x₁, x₂, ..., x_n, что и целевая функция z. 
Пусть решается задача определения условного экстремума функции z = f (X) при ограничениях (2.32)  
Составим функцию

которая называется функцией Лагранжа. X, — постоянные множители (множители Лагранжа). Отметим, что множителям Лагранжа можно придать экономический смысл. Если f (x₁, x₂, ..., x_n ) — доход, соответствующий плану X = (x₁, x₂, ..., x_n ), а функция φ_i (x₁, x₂, ..., x_n ) — издержки i-го ресурса, соответствующие этому плану, то X, — цена (оценка) i-го ресурса, характеризующая изменение экстремального значения целевой функции в зависимости от изменения размера i-го ресурса (маргинальная оценка). L(Х) — функция n + m переменных (x₁, x₂, ..., x_n , λ₁, λ₂, ..., λ_n ). Определение стационарных точек этой функции приводит к решению системы уравнений

Легко заметить, что  , т.е. в (2.48) входят уравнения связи. Таким образом, задача нахождения условного экстремума функции z = f (X) сводится к нахождению локального экстремума функции L(X). Если стационарная точка найдена, то вопрос о существовании экстремума в простейших случаях решается на основании достаточных условий экстремума — исследования знака второго дифференциала d²L(X) в стационарной точке при условии, что переменные приращения Δx_i - связаны соотношениями

полученными путем дифференцирования уравнений связи. Рассмотрим пример.

Пример 2.10.3

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

а целевая  функция иметь вид 

Как и в  случае геометрического решения  задач линейного программирования, сначала необходимо построить область  допустимых решений (ОДР) — множество  точек плоскости, удовлетворяющих  неравенствам (2.41). Но в отличие от задач линейного программирования здесь ОДР не обязательно будет выпуклой и может быть даже разрывной. Экстремум функции может достигаться и внутри области, и на границе. После построения ОДР следует записать уравнения линий уровня целевой функции — множество точек плоскости, в которых целевая функция (2.42) постоянна: f(x₁, x₂ ) = C, и определить направление возрастания (убывания) целевой функции, построив, например, линии уровня для разных значений С.  
Затем, перемещая линию уровня в нужном направлении в ОДР, найти точки области, в которых целевая функция принимает оптимальное значение. 
 

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

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

Для решения  задачи стохастического программирования в Р-постановке и с вероятностными ограничениями переходят к детерминированному эквиваленту.

Для целевой  функции детерминированный эквивалент имеет вид:

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

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

где σ2j — дисперсия  случайной величины сj Решение таких задач затруднительно, поэтому далее рассматриваем целевая функция только в М- постановке. Детерминированный эквивалент вероятностного ограничения типа (а) 

может быть сведен к виду: 

где ai j , bi — математические ожидания; , σ i j 2 , ө i 2 — дисперсии случайных величин aij , bi ; ta = Ф*-1(ai) — обратная функция нормального распределения при функции распределения: 

где ai — заданный уровень вероятности (табл. 2.1).

Обычно решают задачи при ai > 0,5, поэтому даны значения ta только для положительных ta..

Таблица 2.1

Если же ai < 0,5; то t1-a = - ta. Так, для а = 0,4; t0,4 = t(1-0,6) = - t 0, 6 =0,25.

Детерминированный эквивалент задачи СТП в М-по- становке имеет вид 

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

Каждое 1-е ограничение  в детерминированном эквиваленте (2.6) отличается от аналогичного ограничения  задачи линейного программирования следующим: 

от детерминированных  значений aij, bi выполнен переход к математическим ожиданиям случайных величин aij, bi;

появился дополнительный член ( ζ )

который учитывает  все вероятностные факторы: закон  распределения с помощью ta; заданный уровень вероятности ai ; дисперсии случайных величин aij равные σ ij 2; дисперсии случайных величин bi равные ө i 2.

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

3.1 

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

3.2 

где

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

Функция F(x1, х2, хп) называется сепарабельной, если она может быть представлена в виде суммы функций, каждая из которых является функцией одной переменной, т. е. если

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

Пример 1. Рассмотрим задачу распределения двух видов  ресурсов для выпуска двух наименований изделий.

Решение. Ее модель: 

где a i j , bi , cj — случайные.

При М-постановке модель запишется:

где a1, a2 — заданные уровни вероятности соблюдения каждого  ограничения.

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

Исходные данные, необходимые для решения этой задачи, сведены в таблицах 3.3 и 3.4. 

Таблица 3.3

Таблица 3.4

Если задать уровни вероятности a1,2 = 0,6, для которых  ta = 0,25, то получим после подстановки исходных данных детерминированный эквивалент: 

Результаты решения  этой задачи для детерминированного случая ζ i = 0 и при a i = 0,6 (табл. 3.5), где 

Таблица 3.5

Таблица 3.6

Рассмотрим теперь, как повлияют на результат решения  задачи величины, определяющие ее вероятностный  характер. К таким величинам относят  заданный уровень вероятности ai, и дисперсий σij2 и θi2. Начнем с анализа влияния ai (табл. 3.6).

Из анализа  решения этой задачи можно сделать  следующие выводы: для обеспечения  гарантированного (с вероятностью a = 0,6) выполнения плана необходимо иметь дополнительно около 5% каждого вида ресурса. При отсутствии дополнительного ресурса целевой функции может уменьшиться на величину (β = 4% вследствие возможного сокращения выпуска продукции х2 от 5,3 до 5,04.

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

При этом можно  сделать выводы:

в целях повышения заданного уровня вероятности выполнения плана ai требуется увеличить дополнительные ресурсы γi. Так, для выполнения плана с вероятностью, близкой к 1 (а = 0,987), необходим дополнительный ресурс в размере γi = 26, ..., 33% от величины используемого без учета вероятностных характеристик;

отсутствие такого увеличения может привести к ухудшению  целевой функции на величину β = 33,6%;

возрастание a отражается на номенклатуре продукции. При этом в интервале a = 0,5, ..., 0,77 значение х1 сохраняется неизменным, а х2 — уменьшается. При дальнейшем увеличении а = 0,89, ..., 0,987 значение х2 = const, в то время как х1 сначала скачком растет, а затем постепенно уменьшается. Несмотря на то что при а = 0,89 значения x1,2 резко изменяются, целевая функция во всем интервале изменения а уменьшается плавно. Таково влияние заданного уровня вероятности соблюдения ограничений а на результат решения задачи. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Литература:

1. Интернет сайт: http://ru.wikipedia.org/wiki/
2. «Математическое программирование» / Костевич Л.