Оптимизационные методы решения экономических задач
Теорема Куна-Таккера. Пусть функции , имеют непрерывные частные производные на некотором открытом множестве
, содержащем точку
. Ес
ли является точкой минимума функции
при ограничениях
, удовлетворяющих условию регулярности в виде линейной независимости векторов
, то существуют такие неотрицательные множители Лагранжа
, что
Определим функцию Лагранжа следующим образом:
Тогда теорему Куна-Таккера можно записать в виде
Заметим, что множители Лагранжа в задаче НП с ограничениями-равенствами являются знаконеопределенными, тогда как в теореме Куна-Таккера они должны быть положительными.
Каждой задаче линейного программирования соответствует двойственная задача. Двойственная задача по отношению к исходной задаче строится по следующим правилам:
· Если исходная задача ставится на максимум, то двойственная ставится на минимум и наоборот.
· Коэффициенты целевой функции исходной задачи становятся правыми частями ограничений двойственной задачи. Правые части ограничений исходной задачи становятся коэффициентами целевой функции двойственной задачи.
· Если A-матрица коэффициентов исходной задачи, то транспонированная матрица T A будет матрицей коэффициентов двойственной задачи.
· В задаче на максимум все ограничения имеют знак ≤ (=), а в задаче на минимум все ограничения имеют знак ≥ .
· Число переменных в двойственной задаче равно числу ограничений в исходной задаче. Каждому ограничению исходной задачи соответствует переменная двойственной задачи. Если ограничение исходной задач имеет знак (≥ ), то соответствующая переменная двойственной задачи неотрицательна. Если ограничение имеет знак (=), то соответствующая переменная двойственной задачи может принимать положительные и отрицательные значения и наоборот.
4 Выпуклая оптимизация. Условие выпуклости
Основная задача выпуклого программирования
Пусть задано выпуклое и замкнутое множество . Рассмотрим множество
={
},
=(
,…,
),
Î
.
где (
) — вогнутые (выпуклые вверх) непрерывные на
скалярные функции. В теории математического программирования каждый элемент
Î
принято называть допустимым планом, а само множество
— множеством допустимых планов.
Формальная постановка задачи выпуклого программирования
Задачу
,
где выпукла, а
определяется вышеприведенными условиями, называется основной задачей выпуклого программирования.
0 означает, что ставится задача:
Если существует минимальное значение функции на множестве
, то среди всех допустимых планов найти оптимальный план
, для которого
=
=
при этом число называют значением задачи.
Если оптимального плана не существует, то требуется
· либо найти значение задачи как точную нижнюю грань значений функции на множестве
:
=
· либо убедиться, что неограничена снизу на множестве
;
· либо убедиться в том, что множество допустимых планов пусто.
Для решения предложенной оптимизационной задачи следует выполнить следующие действия:
· Определить множество .
· Определить вектор-функцию =(
,…,
) и вектор
Î
.
· Определить множество допустимых планов ={
}.
· Привести задачу к стандартной форме основной задачи выпуклого программирования и определить оптимизируемую функцию .
· Проверить, является ли полученная оптимизационная задача ЗВП, для этого
Другие рефераты на тему «Экономико-математическое моделирование»:
- Исследование модели развития покупательского спроса для предприятия, выпускающего определенный товар
- Решения задачи планирования производства симплекс методом
- Поиск кратчайшего пути передвижения слона по шахматному полю
- Определение зависимости цены товара
- Оптимизация сетевой модели комплекса производственных работ
Поиск рефератов
Последние рефераты раздела
- Выборочные исследования в эконометрике
- Временные характеристики и функция времени. Графическое представление частотных характеристик
- Автоматизированный априорный анализ статистической совокупности в среде MS Excel
- Биматричные игры. Поиск равновесных ситуаций
- Анализ рядов распределения
- Анализ состояния финансовых рынков на основе методов нелинейной динамики
- Безработица - основные определения и измерение. Потоки, запасы, утечки, инъекции в модели