183571 (743598), страница 2

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

минимизировать

при ограничениях

Предположим, что все функции – дифференцируемы. Введем набор переменных (число которых равняется числу ограничений), которые называются множителями Лагранжа, и составим функцию Лагранжа такого вида:

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

множителей Лагранжа, который состоит из следующих шагов.

Составляют функцию Лагранжа

Находят частные производные

Решают систему уравнений

и отыскивают точки , удовлетворяющие системе.

Найденные точки дальше исследуют на максимум (или минимум).

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

Рассмотрим функцию Лагранжа

Определение Пара векторов называется седловой точкой функции Лагранжа , если при всех выполняется условие

Неравенство называют неравенством для седловой точки. Очевидно, что в седловой точке выполняется условие

Между понятием седловой точки функции Лагранжа и решением задачи НП существует взаимосвязь, которая устанавливается в следующей теореме.

Теорема. Пусть и все выпуклы и функции удовлетворяют условию регулярности Слейтера. Вектор является решением задачи НП тогда и только тогда, когда существует такой вектор , что

Теорема Куна-Таккера. Пусть функции , имеют непрерывные частные производные на некотором открытом множестве , содержащем точку . Если является точкой минимума функции при ограничениях , удовлетворяющих условию регулярности в виде линейной независимости векторов , то существуют такие неотрицательные множители Лагранжа , что

Определим функцию Лагранжа следующим образом:

Тогда теорему Куна-Таккера можно записать в виде

Заметим, что множители Лагранжа в задаче НП с ограничениями-равенствами являются знаконеопределенными, тогда как в теореме Куна-Таккера они должны быть положительными.

Каждой задаче линейного программирования соответствует двойственная задача. Двойственная задача по отношению к исходной задаче строится по следующим правилам:

• Если исходная задача ставится на максимум, то двойственная ставится на минимум и наоборот.

• Коэффициенты целевой функции исходной задачи становятся правыми частями ограничений двойственной задачи. Правые части ограничений исходной задачи становятся коэффициентами целевой функции двойственной задачи.

• Если A-матрица коэффициентов исходной задачи, то транспонированная матрица T A будет матрицей коэффициентов двойственной задачи.

• В задаче на максимум все ограничения имеют знак ≤ (=), а в задаче на минимум все ограничения имеют знак ≥ .

• Число переменных в двойственной задаче равно числу ограничений в исходной задаче. Каждому ограничению исходной задачи соответствует переменная двойственной задачи. Если ограничение исходной задач имеет знак (≥ ), то соответствующая переменная двойственной задачи неотрицательна. Если ограничение имеет знак (=), то соответствующая переменная двойственной задачи может принимать положительные и отрицательные значения и наоборот.

1. Выпуклая оптимизация. Условие выпуклости

Основная задача выпуклого программирования

Пусть задано выпуклое и замкнутое множество . Рассмотрим множество

={ }, =( ,…, ), .

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

Формальная постановка задачи выпуклого программирования

Задачу

,

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

0 означает, что ставится задача:

Если существует минимальное значение функции на множестве , то среди всех допустимых планов найти оптимальный план , для которого

= =

при этом число называют значением задачи.

Если оптимального плана не существует, то требуется

• либо найти значение задачи как точную нижнюю грань значений функции на множестве :

=

• либо убедиться, что неограничена снизу на множестве ;

• либо убедиться в том, что множество допустимых планов пусто.

Для решения предложенной оптимизационной задачи следует выполнить следующие действия:

• Определить множество .

• Определить вектор-функцию =( ,…, ) и вектор .

• Определить множество допустимых планов ={ }.

• Привести задачу к стандартной форме основной задачи выпуклого программирования и определить оптимизируемую функцию .

• Проверить, является ли полученная оптимизационная задача ЗВП, для этого

• проверить на выпуклость множество ;

• проверить на выпуклость функцию .

В случае успеха п. 

• Построить функцию Лагранжа полученной ЗВП.

• С помощью дифференциальных условий Куна-Таккера найти седловые точки построенной функции Лагранжа.

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

Методы субградиентной оптимизации. Эти итеративные процедуры формируют последовательность векторов {l^k}.

Фундаментальный теоретический результат заключается в том, что

.

Размер шага на практике обычно выбирают, следуя ,

где q ^k — скаляр, 0 < q ^k 2 и z* — верхняя граница для n(D). Обычно z* получают эвристикой для P. В методе ветвей и границ z* — текущий рекорд. Последовательность q ^k, как правило, начинается с q ⁰=2 и затем q ^k делится пополам, через фиксированное число итераций, зависящее от размерности задачи.

1. Экономико-математическая модель реструктуризации угольной промышленности. Критерий оптимизационной задачи

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

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

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

Полученная модель основана на одной из существующих математических моделей на уровне отраслей промышленности. Эта модель - «Модель распределения капитальных вложений на переходящие и вновь начинаемые объекты строительства». При использовании этой модели можно получить значения капитальных вложений по годам планового периода для переходящих и вновь начинаемых объектов строительства. В данном случае решается задача оптимального распределения лимита капитальных вложений по объектам строительства таким образом, чтобы повысить экономическую эффективность плана капитального строительства и вовремя ввести необходимые мощности.

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

Постановка оптимизационной задачи в нашем случае делается на основе следующих условий:

1) При ликвидации шахты возникают различные затраты, осуществляемые за счет государственного финансирования, их можно укрупнено разделить по нескольким направлениям;

2) Отчетность о проведении работ по ликвидации предприятий компания«Укруглереструктуризация» предоставляет за определенные периоды времени, следовательно, финансирование осуществляется через равномерные периоды времени;

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

4) Расходы по различным направлениям ликвидации шахт проектируются на основании сметной стоимости производства определенных работ по закрытию шахт; эта сметная стоимость рассчитывается по существующим нормативным документам;

5) Необходимо учесть, что бюджетное финансирование лимитировано в каждом периоде;

6) Затраты по каждому направлению ликвидации горного предприятия недолжны превышать суммарную сметную стоимость;

7) Отдельно необходимо учесть обеспечение социальной защиты, высвобождаемых работников.

Целевая функция полученной математической модели с учетом критерии экономической эффективности ликвидации горного предприятия сформулирована следующим образом:

F=ΣΣ(1+E)^t-1Q_i→max

Характеристики

Список файлов реферата