Оптимизационные методы решения экономических задач (стр. 2 из 4)
При условии, что
Член
вносит в данную задачу элемент ослабления, что, иначе говоря, обозначает жесткость заданного намерения. Весовой вектор w дает исследователю возможность достаточно точно выразить меру взаимосвязи между двумя целями. Например, установка весового вектора w как равного исходному намерению указывает на то, что достигнут тот же самый процент недо- или передостижимости цели 
. Посредством установки в ноль отдельного весового коэффициента (т.е. 
) можно внести жесткие ограничения в поставленную задачу. Метод достижения цели обеспечивает подходящую интуитивную интерпретацию поставленной исследовательской задачи и которая, в свою очередь, является вполне разрешимой с помощью стандартных процедур оптимизации. Метод множителей Лагранжа позволяет отыскивать максимум или минимум функции при ограничениях-равенствах. Основная идея метода состоит в переходе от задачи на условный экстремум к задаче отыскания безусловного экстремума некоторой построенной функции Лагранжа. Пусть задана задача НП при ограничениях-равенствах вида
минимизировать 
при ограничениях
Предположим, что все функции 
– дифференцируемы. Введем набор переменных 
(число которых равняется числу ограничений), которые называются множителями Лагранжа, и составим функцию Лагранжа такого вида:
Справедливо такое утверждение для того чтобы вектор 
являлся решением задачи при ограничениях необходимо, чтобы существовал такой вектор 
, что пара векторов удовлетворяла бы системе уравнений
множителей Лагранжа, который состоит из следующих шагов.
Составляют функцию Лагранжа 
Находят частные производные 
Решают систему уравнений
и отыскивают точки 
, удовлетворяющие системе.
Найденные точки 
дальше исследуют на максимум (или минимум).
Седловая точка и задача нелинейного программирования
Рассмотрим функцию Лагранжа 
Определение Пара векторов 
называется седловой точкой функции Лагранжа 
, если при всех 
выполняется условие
Неравенство называют неравенством для седловой точки. Очевидно, что в седловой точке выполняется условие
Между понятием седловой точки функции Лагранжа 
и решением задачи НП существует взаимосвязь, которая устанавливается в следующей теореме.
Теорема. Пусть 
и все 
выпуклы и функции 
удовлетворяют условию регулярности Слейтера. Вектор 
является решением задачи НП тогда и только тогда, когда существует такой вектор 
, что
Теорема Куна-Таккера. Пусть функции 
, имеют непрерывные частные производные на некотором открытом множестве 
, содержащем точку . Если 
является точкой минимума функции 
при ограничениях 
, удовлетворяющих условию регулярности в виде линейной независимости векторов 
, то существуют такие неотрицательные множители Лагранжа 
, что
Определим функцию Лагранжа следующим образом:
Тогда теорему Куна-Таккера можно записать в виде
Заметим, что множители Лагранжа 
в задаче НП с ограничениями-равенствами являются знаконеопределенными, тогда как в теореме Куна-Таккера они должны быть положительными.
Каждой задаче линейного программирования соответствует двойственная задача. Двойственная задача по отношению к исходной задаче строится по следующим правилам:
· Если исходная задача ставится на максимум, то двойственная ставится на минимум и наоборот.
· Коэффициенты целевой функции исходной задачи становятся правыми частями ограничений двойственной задачи. Правые части ограничений исходной задачи становятся коэффициентами целевой функции двойственной задачи.
· Если A-матрица коэффициентов исходной задачи, то транспонированная матрица T A будет матрицей коэффициентов двойственной задачи.
· В задаче на максимум все ограничения имеют знак ≤ (=), а в задаче на минимум все ограничения имеют знак ≥ .
· Число переменных в двойственной задаче равно числу ограничений в исходной задаче. Каждому ограничению исходной задачи соответствует переменная двойственной задачи. Если ограничение исходной задач имеет знак (≥ ), то соответствующая переменная двойственной задачи неотрицательна. Если ограничение имеет знак (=), то соответствующая переменная двойственной задачи может принимать положительные и отрицательные значения и наоборот.
4 Выпуклая оптимизация. Условие выпуклости
Основная задача выпуклого программирования
Пусть задано выпуклое и замкнутое множество
. Рассмотрим множество 
={ 
}, 
=( 
,…, 
), 
.