Условная и безусловная оптимизация. Теорема Куна-Таккера

                Министерство образования и науки Российской Федерации

Государственное образовательное  учреждение

высшего профессионального  образования

«Волгоградский  государственный технический университет»

Факультет экономики  и управления

Кафедра «Мировая экономика и экономическая теория»

 

 

 

 

 

                                          СЕМЕСТРОВАЯ РАБОТА

 

  

 по предмету  «Микроэкономика»

 

на тему:

 

«Условная и  безусловная оптимизация. Теорема Куна-Таккера»

 

 

 

 

 

 

                

 

                  Выполнила:

                 

                  ФЭУ-160

                  Проверила:

 

 

 

 

 

 

 

 

 

 

                                       Волгоград 2012

                                         

                                        Содержание

 

 

 

      Введение………………………………………………………….3

 

1. Основные понятия теории оптимизации………………….….4
2. Теорема Куна-Такера……………………………………….…6
3. Безусловная оптимизация……………………………………..8
4. Условная оптимизация…………..……………………………15

Заключение………………………………………………….….…19

Список литературы…………………………………….................20

        

 

                                                Введение

Под задачей математического программирования принято называть задачу оптимизации.  При наличии нескольких критериев возможны два класса задач оптимизации: задачи условной оптимизации и задачи безусловной оптимизации. При условной оптимизации отыскивается наибольшее или наименьшее значение одного из критериев при условии, что остальные критерии имеют заданные значения. Важным и полезным для исследования задач условной оптимизации является понятие о расширении экстремальной задачи. Оно позволяет подчеркнуть взаимосвязь таких различных подходов, как метод Лагранжа, метод штрафов, переход к осредненной постановке и др. Основное внимание будет уделено изложению и пояснению методики перехода от условий задачи (критерия оптимальности, связей и ограничений) к условиям, выделяющим оптимальные решения. Важно и то обстоятельство, что изменения в постановке задачи легко учесть при составлении условий оптимальности решения. Лагранжа для того и служит, чтобы от задачи условной оптимизации перейти к задаче безусловной оптимизации по расширенному  (за счет множителей Лагранжа) набору аргументов оптимизации. В этом случае на каждом шаге алгоритма удается перейти от задачи условной оптимизации к безусловной и вместо двух условно-оптимальных зависимостей запоминать только одну. Рассмотрим алгоритм динамического программирования применительно к частным формам связи.                          Итак, решение задачи условной оптимизации при нескольких ограничениях сведено к многократному решению задачи условной оптимизации с одним ограничением c применением теоремы Куна-Такера.

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

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

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

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

Необходимым условием использования оптимального подхода к планированию (принципа оптимальности) является гибкость, альтернативность производственно-хозяйственных ситуаций, в условиях которых приходится принимать  планово-управленческие решения. Именно такие ситуации, как правило составляют повседневную практику хозяйствующего субъекта (выбор производственной программы, прикрепление к поставщикам, маршрутизация, раскрой материалов, приготовление  смесей).

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

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

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

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

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

 

 

 

 

 

 

                          Теорема Куна-Таккера.

 

 

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

Мы рассмотрим эти теоремы в дифференциальной форме (т.е. когда

все функции  дифференцируемы).

Пусть даны функции

                                      

                                         

и

                                  

                                    ψr: XR , r=1,...,m,

где X⊆.

Функцию φ(⋅) будем использовать как целевую функцию,

а с помощью  функций ψr(⋅) будем задавать ограничения.  При этом

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

                                 

                                   φ(x)→max

                                ψj(x)>0, j=1,...,m,                                               (1)

                                 x=(x1,...,xn)∈X.

 

Функция Лагранжа (лагранжиан) этой задачи имеет следующий вид:

                     

                        L(x, λ)= φ(x)+ (x),

 

где коэффициенты λj называют множителями Лагранжа.

 

Прямая  теорема Куна — Таккера (необходимое  условие оптимальности)

Пусть функции  φ(⋅λ), ψ1(⋅),...,ψn(⋅) дифференцируемы, и — решение задачи (1), такое что ∈int(X) и выполнены условия регулярности.

Тогда существуют множители Лагранжа λj>0,  j= 1, ...,m,  такие что при =1 выполнены следующие соотношения:

 

                           =0, i=1,...,n

и

                                         =0

 

 

Обратная  теорема Куна–Таккера  (достаточное условие оптимальности)

Пусть функции  φ(⋅), ψ1(⋅),...,(⋅) дифференцируемы и вогнуты,

множество X выпукло и точка допустима в задаче (1), причем

                                            ∈int(X).

Пусть,  кроме того,  существуют множители  Лагранжа

λj>0, j=1,...,m, такие что при = 1 выполнены следующие соотношения:

 

                               =0, i=1,...,n

и

                                     =0

 

 

Тогда — решение задачи (1).

 

 

                          Безусловная оптимизация. 

 

 

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

Решение многих теоретических и практических задач  сводится к отысканию экстремума (наибольшего или наименьшего  значения) скалярной функции f(х) n-мерного векторного аргументах. В дальнейшем под x будем понимать вектор-столбец (точку в n-мерном пространстве):

        

Вектор-строка получается путем применения операции транспонирования:

=( …, ) 

Оптимизируемую  функцию f(x) называют целевой функцией или критерием оптимальности.

В дальнейшем без ограничения общности будем  говорить о поиске минимального значения функции f(x) записывать эту задачу следующим образом:

f(x ) min.

Вектор х*, определяющий минимум целевой функции, называют оптимальным.

Отметим, что  задачу максимизации f(x) можно заменить эквивалентной ей задачей минимизации или наоборот. Если х* - точка минимума функции y = f(x), то для функции y =- f(x) она является точкой максимума, так как графики функций f(x) и - f(x), симметричны относительно оси абсцисс.                                                                                                                            Итак, минимум функции f(x) и максимум функции - f(x) достигаются при одном и том же значении переменной.

 Минимальное  же значение функции f(x), равно максимальному значению функции - f(x), взятому с противоположным знаком, т.е. min f(x) =-max(f(x)).

Рассуждая аналогично, этот вывод нетрудно распространить на случай функции многих переменных. Если требуется заменить задачу минимизации  функции f(x₁, …, x_n) задачей максимизации, то достаточно вместо отыскания минимума этой функции найти максимум функции  f(x₁,…,x_n). Экстремальные значения этих функций достигаются при одних и тех же значениях переменных. Минимальное значение функции                  f(x₁, …, x_n) равно максимальному значению функции - f(x₁, …, x_n), взятому с обратным знаком, т.е. min f(x₁, …, x_n) =max f(x₁, …, x_n). Отмеченный факт позволяет в дальнейшем говорить только о задаче минимизации.

                            

Рисунок 1.  Экстремум

В реальных условиях на переменные x_i, i=1, …. n, и некоторые функции g_i (х), h_i(х), характеризующие качественные свойства объекта, системы, процесса, могут быть наложены ограничения (условия) вида:

g_i (х) = 0, i=1, …. n,

h_i (х) <= 0, i=1, …. n,

a <= x <= b,

 

 

где

 ; 

Такую задачу называют задачей условной оптимизации.

 

 

 При отсутствии ограничений  имеет место задача безусловной оптимизации.

Каждая точка х в n-мерном пространстве переменных х₁, …, х_n, в которой выполняются ограничения, называется допустимой точкой задачи. Множество всех допустимых точек называют допустимой областью G. Решением задачи (оптимальной точкой) называют допустимую точку х*,  в которой целевая функция f(х) достигает своего минимального значения.

Точка х* определяет глобальный минимум функции одной переменной f(x), заданной на числовой прямой Х , если x ^*  X и f(x^*) < f(x) для всех x^*   X (Рис. 2, а). Точка х* называется точкой строгого глобального минимума, если это неравенство выполняется как строгое. Если же в выражении f(х*) <= f(x) равенство возможно при х, не равных  х*, то реализуется нестрогий минимум, а под решением в этом случае понимают множество х* = [x^*   X: f(x) = f(x^*)] (Рис. 2, б).

Рисунок  2. Глобальный минимум. а - строгий, б - нестрогий

Точка х*   Х определяет локальный минимум функции f(x) на множестве Х , если при некотором достаточно малом e > 0 для всех х, не равных  х*, x   X, удовлетворяющих условию ¦х - х*¦<= e, выполняется неравенство f(х*) < f(х). Если неравенство строгое, то х* является точкой строгого локального минимума. Все определения для максимума функции получаются заменой знаков предыдущих неравенств на обратные. На Рис.3 показаны экстремумы функции одной переменной f(х) на отрезке [a, b] . Здесь х₁, х₃, х₆ - точки локального максимума, а х₂, х₄ - локального минимума. В точке х₆ реализуется глобальный максимум, а в точке              х₂ - глобальный минимум.

                                  

Рисунок 3. Экстремумы функции

Классификация методов

Возможны  два подхода к решению задачи отыскания минимума функции многих переменных f(x) = f(x₁, ..., х_n) при отсутствии ограничений на диапазон изменения неизвестных. Первый подход лежит в основе косвенных методов оптимизации и сводит решение задачи оптимизации к решению системы нелинейных уравнений, являющихся следствием условий экстремума функции многих переменных. Как известно, эти условия определяют, что в точке экстремума х* все первые производные функции по независимым переменным равны нулю: