Основные понятия теории оптимизации

Оглавление
Введение 31.Основные понятия теории оптимизации 42. Условия Куна-Таккера 63. Теоремы Куна–Таккера 10Заключение  15Список реферируемой литературы 16
Введение
 Актуальность темы, на мой взгляд, не вызывает никаких сомнений. Действительно, ведь объектом нелинейного программирования считается оптимизация разнообразных производственных процессов, основной целью которых всегда является максимизация прибыли, минимизация издержек. Эффективное применение ресурсов выступает одним из основных компонентов успешного функционирования любого экономического субъекта.
Теорема Куна-Таккера выступает обобщением методов решения оптимизационных задач в двух назначениях:
- линейного программирования на нелинейный случай, получивший по аналогии неудачное название «нелинейного программирования»;
- нелинейных ограничений равенств на ограничения неравенства.
Метод и условия Каруша-Куна-Таккера (Karush-Kuhn- Tucker conditions, KKT) формально являются нужными требованиями оптимальности задачи нелинейного программирования. Кроме этого, необходимые требования содержат, так называемые требования регулярности стационарных точек – невырожденность множества градиентов ограничений. Метод считается обобщением метода множителей Лагранжа на случай ограничений неравенств. Но в различие от него, ограничения, которые накладываются на переменные, представляют собой не уравнения, а неравенства.
Цель данной работы заключается в изучении теоремы Куна-Таккера.
Для того, чтобы достичь поставленную цель необходимо:
- охарактеризовать основные понятия теории оптимизации;
- рассмотреть условия Куна-Таккера;
- показать теорему Куна–Таккера.
 Основные понятия теории оптимизации
На практике часто встречаются такие обстоятельства, когда какой-то результат можно достичь не одним, а различными методами. В такие обстоятельства может попасть и отдельно взятый человек, к примеру, когда он решает проблему о распределении личных расходов, и целая организация или даже отрасль, если необходимо установить, как применять существующие в их распоряжении ресурсы, чтобы достичь наибольшего выхода продукции, и, в конце концов, народное хозяйство в общем. Конечно, при разнообразии решений должно быть найдено наилучшее.
Успешный исход решения большинства экономических задач имеет зависимость от наилучшего, наивыгоднейшего способа применения ресурсов. И от того, как будут разделены эти, как правило, ограниченные ресурсы, будет зависеть конечный итог работы экономического субъекта. [1]
Сущность методов оптимизации (оптимального программирования) содержится в том, чтобы, отталкиваясь из присутствия обусловленных ресурсов, выбрать такой способ их применения (распределения), при котором будет обеспечиваться минимум или максимум интересующего нас показателя.
Необходимым требованием употребления оптимального подхода к планированию (принципа оптимальности) выступают гибкость, альтернативность производственно-хозяйственных обстановок, в условиях которых придется получать планово-управленческие решения. Именно подобные ситуации, как правило образуют повседневную практику предприятия (прикрепление к поставщикам, маршрутизация, выбор производственной программы, раскрой материалов).
Таким образом, оптимальное программирование осуществляет благополучное решение огромного ряда экстремальных задач производственного планирования. В сфере же макроэкономического анализа, планирования и прогнозирования оптимальное программирование разрешает выбирать вариант народнохозяйственного плана (программы формирования), которые характеризуются наилучшим соотношением потребления и сбережений (накоплений), наилучшей долей производственных капиталовложений в национальном доходе, наилучшим соотношением коэффициента рентабельности и коэффициента роста национальной экономики и др.
Оптимальное программирование осуществляет приобретение практически ценных результатов, так как по своей сути оно вполне отвечает характеру изучаемых технико-экономических явлений и процессов. С математической и статистической точек зрения данный метод используем только к тем процессам, которые формулируются положительными величинами и в своей общности формируют объединение взаимозависимых, но качественно разнообразных величин. Данным требованиям, как правило, соответствуют величины, которыми охарактеризуются экономические процессы. Перед исследователем экономики всегда есть – некоторое масса различного рода положительных величин. Экономист, решая задачи оптимизации, всегда встречается не с одной, а с несколькими взаимозависимыми факторами или величинами.
Оптимальное программирование можно использовать только к таким задачам, при разрешении которых оптимальный итог получается лишь в форме точно формулированных целей и при вполне обусловленных ограничениях, обычно выливающихся из наличных ресурсов (сырья, трудовых ресурсов, производственных мощностей и пр.). В требования задачи обычно включается некоторая математически выраженная система взаимозависимых факторов, средства и условия, ограничивающие характер их применения.
Задача делается разрешимой при введении в нее установленных оценок, как для взаимозависимых факторов, так и для ожидаемых итогов. Следственно, оптимальность итога задачи программирования обладает относительным характером. Подобный итог считается оптимальным только с точки зрения тех критериев, которыми он оценивается, и ограничений, включенных в задачу.
Исходя из вышесказанного, для каждой задачи оптимального программирования свойственны три таких момента, как:
1) присутствие системы взаимозависимых факторов;
2) строго установленный критерий оценки оптимальности;
3) правильная формулировка условий, которые ограничивают применение наличных средств или факторов. [2]
Существуют различные виды математического программирования в зависимости от целевой функции и характера функций-ограничений:
1. линейное программирование – функции линейны;
2. нелинейного программирования – хотя бы одна из данных является функцией нелинейной;
3. квадратичного программирования – f(х) считается квадратичной функцией, где ограничения линейны;
4. сепарабельное программирование – f(х) является суммой функций, многообразных для любой переменной, требования – ограничения, быть может, как нелинейными, так и линейными;
5. целочисленное (линейное или нелинейное) программирование – координаты искомой точки х лишь целые числа;
6. выпуклое программирование – целевая функция – выпуклая, функции – ограничения – выпуклые, т.е выпуклые функции рассматриваются на выпуклых множествах и пр. [6]
Методы решения задач нелинейного программирования подразделяются на несколько классов:
- градиентные методы;
- методы линейного программирования;
- методы штрафных функций.
Каждая группа методов применяется при определенных требованиях, которые накладываются на целевую функцию и ограничения. Но в классе выпуклых функций вероятно, определение оптимального решения задачи нелинейного программирования опираясь на отыскании стационарной точки. Подобное решение предоставляют условия Куна-Таккера.
Условия Куна-ТаккераМножители Лагранжа можно употреблять при определении критериев оптимальности для задач оптимизации с ограничениями в форме равенств. Г.У. Кун и А.У. Таккер обобщили данный подход на вариант общей задачи нелинейного программирования с ограничениями, как в форме равенств, так и в форме неравенств.
Рассмотрим такую общую задачу нелинейного программирования, как:
минимизировать (0)
при ограничениях (1)
(2)
Определение:
Ограничение в форме неравенства получает название активное, или связывающее, в точке , когда , и неактивное, или несвязывающее, когда
Если имеется вероятность выявить ограничения, которые являются неактивными в точке оптимума, до прямого решения задачи, то данные ограничения можно пропустить из модели и тем самым снизить ее размеры. Главное препятствие при этом в идентификации неактивных ограничений, предшествующей решению задачи.[3]
Г.У. Кун и А.У. Таккер создали нужные и достаточные требования оптимальности для задач нелинейного программирования, истекая из гипотезы о дифференцируемости функций . Данные условия оптимальности, всем знакомые как условия Куна–Таккера, можно выразить в форме задачи определения решения некоторой системы нелинейных уравнений и неравенств, или, как иногда отмечают, задачи Куна–Таккера. [3]Отыскать векторы , удовлетворяющие таким условиям, как:
(3)
(4)
(5)
(6)
(7)
Главным образом, проиллюстрируем условия Куна – Таккера на примере.
Пример 1.
Минимизировать
при ограничениях
Решение.
Предоставив данную задачу в форме задачи нелинейного программирования (0) – (2), мы получим:
Уравнение (3), которое входит в состав условий Куна–Таккера, принимает такой вид, как:
откуда Неравенства (4) и уравнения (5) задачи Куна – Таккера в подобном варианте записываются так:
Уравнения, широко известные как условие дополняющей нежесткости, получают вид:
Отметим, что на переменные и налагается условие неотрицательности, тогда как ограничение на знак не имеется.
И, таким образом, в данной задаче условия Куна–Танкера записываются в таком виде, как:
Для того, чтобы истолковать условия Куна – Таккера, проанализируем задачу нелинейного программирования с ограничениями в форме равенств:
минимизировать
при ограничениях
Записываем условия Куна–Таккера (8)
(9)
Затем проанализируем функцию Лагранжа именно для задачи нелинейного программирования с ограничениями в форме равенств:
Для данной функции условия оптимальности первого порядка заносятся в виде:
Сложно не увидеть, что условия Куна-Таккера (8) и (9) сходятся с условиями оптимальности первого порядка для задач Лагранжа.
Проанализируем задачу нелинейного программирования с ограничениями в форме неравенств:
минимизировать
при ограничениях
Записываем условия Куна–Таккера:
Соответственная функция Лагранжа имеет следующий вид:
Условия оптимальности первого порядка записываются как:
Надо отметить, что - множитель Лагранжа, соответственный ограничению . В одном варианте было сказано, что представляет неявную цену, ассоциированную с ограничением ; иными словами, величина отображает видоизменение наименьшего значения целевой функции , порождаемое единичным приращением правой части - го ограничения.
Если представить, что - е ограничение выступает неактивным (то есть . С другой стороны, когда -е ограничение активное (то есть ), то соответственная неявная цена не должно быть обязательно равна нулю, но , так как . И, таким образом, для всех значений .
Для того, чтобы найти знак (неявной цены, ассоциированной с ограничением ), надлежит повысить правую часть ограничения от 0 до 1. Понятно, что при этом область допустимых решений идет к сужению, так как каждое решение, удовлетворяющее ограничению , автоматически удовлетворит неравенству . Таким образом, размеры допустимой области идут к уменьшению, и наименьшее значение усовершенствовать не получится (так как вообще оно может лишь повышаться). Иными словами, неявная цена , ассоциированная с -м ограничением, должна являться неотрицательной, что отвечает условиям Куна–Таккера.
Теоремы Куна–ТаккераИтак, мы построили условия Куна–Таккера для задач условной оптимизации. При помощи метода множителей Лагранжа принято интуитивное представление о том, что условия Куна – Танкера очень близко соединены с нужными условиями оптимальности. Сейчас мы рассмотрим строгие формулировки нужных и достаточных условий оптимальности решения задачи нелинейного программирования.
Теорема 1. Необходимость условий Куна–ТаккераПроанализируем задачу нелинейного программирования (0) – (2). Пусть - дифференцируемые функции, а х* – это допустимое решение данной задачи. Предположим . Затем пусть линейно независимы. Если х* – это оптимальное решение задачи нелинейного программирования, то имеется такая пара векторов , что выступает решением задачи Куна–Таккера (3) – (7).
Условие, по которому должны являться линейно независимыми, знакомо как условие линейной независимости и по сути выступают некоторым условием регулярности вероятной среды, которое почти каждый раз выполняется для встречающихся на практике задач оптимизации. Но, вообще контроль выполнения условия линейной независимости очень трудна, так как необходимо заранее известное оптимальное решение задачи. Вместе с этим условие линейной независимости каждый раз выполняется для задач нелинейного программирования, имеющих такие условия, как:
1. Все ограничения в форме равенств и неравенств включают линейные функции.
2. Все ограничения в форме неравенств включают вогнутые функции, все ограничения-равенства – линейные функции, а также есть, по крайней мере, одна допустимая точка х, которая располагается во внутренней части области, назначаемой ограничениями-неравенствами. Иными словами, имеется такая точка х, что
Когда условие линейной независимости в точке оптимума не исполняется, то задача Куна–Таккера может не располагать решением.
Пример 2
Минимизировать
при ограничениях
Решение.
На рисунке 1 изображается область допустимых решений выраженной ранее нелинейной задачи. Понятно, что оптимальное решение данной задачи - это . Изобразим, что условие линейной независимости не осуществляется в точке оптимума.
457200-457200
Рис. 1. Допустимая область в примере 2
Так как Несложно увидеть, что векторы являются линейно зависимыми, то есть условие линейной независимости в точке не исполняется.
Записываем условия Куна–Таккера и проверяем, выполняются ли они в точке (1, 0). Условия (3), (6) и (7) принимают такой вид;
При из уравнения (11) вытекает, что , тогда как уравнение (14) дает . Таким образом, точка оптимума не выступает точкой Куна – Таккера.
Надо отметить, что нарушение условия линейной независимости не каждый раз говорит, что точки Куна–Таккера нет. Для того, чтобы удостоверить это, сменим целевую функцию из данного примера функцией. При этом оптимум как и прежде достигается в точке (1,0), в которой условие линейной независимости не осуществляется. Условия Куна–Таккера (12) – (16) остаются такими же, а уравнение (11) принимает вид
Легко испытать, что точка выступает точкой Куна–Таккера, то есть удовлетворяет условиям Куна–Таккера.
Теорема о необходимости условий Куна–Таккера разрешает идентифицировать неоптимальные точки. Иными словами, теорему 1 можно применять для подтверждения того, что заданная допустимая точка, которая удовлетворяет условию линейной независимости, не выступает оптимальной, если она не отвечает условиям Куна–Таккера. С иной стороны, если в данной точке условия Куна–Таккера выполняются, то не существует гарантии, что отыскано оптимальное решение нелинейной задачи. В форме примера проанализируем следующую задачу нелинейного программирования.
Следующая теорема определяет условия, при осуществлении которых точка Куна–Таккера автоматически отвечает оптимальному решению задачи нелинейного программирования.
Теорема 2. Достаточность условий Куна–ТаккераПроанализируем задачу нелинейного программирования (0) – (2). Пускай целевая функция является выпуклой, все ограничения в форме неравенств включают вогнутые функции , а ограничения в форме равенств включают линейные функции . В таком варианте, когда есть решение , удовлетворяющее условиям Куна–Таккера (3) – (7), то х* – оптимальное решение задачи нелинейного программирования.
Когда условия теоремы 2 выполняются, то определение точки Куна–Таккера обеспечивает приобретение оптимального решения задачи нелинейного программирования.
Теорему 2 можно также применять для доказательства оптимальности данного решения задачи нелинейного программирования. В форме иллюстрации покажем пример:
Минимизировать
при ограничениях
С помощью теоремы 2 доказываем, что решение выступает оптимальным. Имеем
Поскольку матрица положительно полуопределена при всех х, функция оказывается выпуклой. Первое ограничение в форме неравенства включает линейную функцию , которая в то же время считается как выпуклой, так и вогнутой. Для того, чтобы показать, что функция считается вогнутой, подсчитаем
Положив , получим и. Следовательно, решение х*=(1, 5), удовлетворяет условиям Куна–Таккера. Так как условия теоремы 2 реализованы, то оптимальное решение задачи из примера 3. Надо отметить, что имеются также и прочие значения и , которые удовлетворяют системе (17) – (24).
Существуют следующие замечания:
1. Для имеющихся на практике задач условие линейной независимости, как обычно, выполняется. Когда в задаче все функции дифференцируемы, то точку Куна–Таккера необходимо рассматривать как вероятную точку оптимума. Следовательно, многие из методов нелинейного программирования встречают к точке Куна–Таккера.
2. Если условия теоремы 2 выполнены, точка Куна–Таккера в это же время является точкой глобального минимума. К сожалению, контроль достаточных условий очень затруднительна, и, кроме этого, прикладные задачи нередко не располагают требуемыми свойствами. Надо отметить, что присутствие хотя бы одного нелинейного ограничения в форме равенства приведет к нарушению предположений теоремы 2.
3. Достаточные условия, определенные теоремой 2, можно обобщать на случай задач с невыпуклыми функциями, входящими в ограничения в форме неравенств, невыпуклыми целевыми функциями и нелинейными ограничениями-равенствами. При этом применяются такие обобщения выпуклых функций, как квазивыпуклые и псевдовыпуклые функции. [5]
Заключение
Успешный исход решения большинства экономических задач имеет зависимость от наилучшего, наивыгоднейшего способа применения ресурсов. И от того, как будут разделены эти, как правило, ограниченные ресурсы, будет зависеть конечный итог работы экономического субъекта.
Сущность методов оптимизации (оптимального программирования) содержится в том, чтобы, отталкиваясь из присутствия обусловленных ресурсов, выбрать такой способ их применения (распределения), при котором будет обеспечиваться минимум или максимум интересующего нас показателя.
Оптимальное программирование осуществляет благополучное решение огромного ряда экстремальных задач производственного планирования. В сфере же макроэкономического анализа, планирования и прогнозирования оптимальное программирование разрешает выбирать вариант народнохозяйственного плана (программы формирования), которые характеризуются наилучшим соотношением потребления и сбережений (накоплений), наилучшей долей производственных капиталовложений в национальном доходе, наилучшим соотношением коэффициента рентабельности и коэффициента роста национальной экономики и др.
Каждая группа методов решения задач нелинейного программирования применяется при определенных требованиях, которые накладываются на целевую функцию и ограничения. Но в классе выпуклых функций вероятно, определение оптимального решения задачи нелинейного программирования опираясь на отыскании стационарной точки. Подобное решение предоставляют условия Куна-Таккера.
В теории оптимизации условия Каруша — Куна — Таккера— необходимые условия решения задачи нелинейного программирования. Чтобы решение было оптимальным, должны быть выполнены некоторые условия регулярности. Метод является обобщением метода множителей Лагранжа. В отличие от него, ограничения, накладываемые на переменные, представляют собой не уравнения, а неравенства.
Список реферируемой литературы
Волошин Г.Я., Методы оптимизации в экономике: Учебное пособие. – М.: «Издательство «Дело и Сервис», 2004. – 320 с.
Данилов Н.Н. Курс математической экономики. – М.: Высшая школа, 2006.
Замков О.О., Толстопятенко А.В., Чермных Ю.Н. Математические методы в экономике: учеб. пособие. Изд-во «ДИС», Москва. – 1998 г.
Колемаев В.А. Математическая экономика: Учебник для вузов. – 2-е изд., перераб. и доп. – М.: ЮНИТИ-ДАНА, 2002. – 399 с.
Коршунов Н.И., Плясунов В.С., Математика в экономике. – М.: Изд-во «Вита-Пресс», 2006. – 345 с.
Кундышева Е.С. Математическое моделирование в экономике: Учебное пособие/ Под науч. ред. Проф. Б.А. Суслакова. – М.: Издательско-торговая корпорация «Дашков и Кο», 2004. – 352 с.