Xreferat.com » Рефераты по экономико-математическому моделированию » Теоретические основы математических и инструментальных методов экономики

Теоретические основы математических и инструментальных методов экономики

Теоретические основы специальности.

Оптимизационные методы решения экономических задач. Классическая постановка задачи оптимизации. Оптимизация функций. Оптимизация функционалов. Общая постановка задачи.

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

 Возможны два подхода к  постановке оптимизационных задач: при первом подходе требуется получить максимальные  конечные результаты при заданных условиях производства; при втором подходе требуется получить заданные конечные результаты при минимальных затратах ресурсов.

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

 На практике наибольшее распространение получило линейное программирование.

Методы линейного программирования в математике известны под названием общей задачи линейного программирования.

 Аналитическая формулировка общей задачи линейного программирования

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

Найти решение {Х1,Х2,….Хn}, позволяющее максимизировать или минимизировать  целевую функцию

F = C1X1+C2X2+…+ CnXn

при условиях

Х1≥0; Х2≥0; …; Хn≥0.

Это развернутая запись общей задачи линейного программирования.

Сокращенная запись этой модели имеет вид:

Найти решение {Xj}, позволяющее максимизировать (минимизировать) функцию  

при условиях

 , i  = 1,2,…,n;

Xj ≥ 0, j = 1,2,…,n.

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

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


Матричная форма записи общей задачи линейного программирования

при ограничениях AX≤B

                              X≥0,

где С = (с1, с2,…, сn);

                  

где С – матрица-строка

 А – матрица системы

 Х – матрица-столбец переменных

 В – матрица-столбец свободных членов

Векторная форма записи общей задачи линейного программирования

F = CX → max (min)

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

Х≥0,

где СХ – скалярное произведение векторов

С = (С1, С2, …, Сn) и Х = (х1, х2, …, хn),

векторы


состоят соответственно из коэффициентов при переменных и свободных членов.

(про функционал)

В общем случае задача оптимизации формулируется как задача отыскания max или min значения I(v) для Теоретические основы математических и инструментальных методов экономики.

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

При этом:

v – некоторая функция

I(v) – функционал вида Теоретические основы математических и инструментальных методов экономики

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

Многокритериальная оптимизация представляет собой минимизацию некого вектора целей F(x), на которой могут быть наложены дополнительные ограничения или предельные значения:

Теоретические основы математических и инструментальных методов экономики

(3-47)

Отметим, что поскольку F(x) является неким вектором, то любые компоненты F(x) являюся конкурирующими и отсутсвует некое единое решение поставленной задачи. Взамен этого, для описания характеристик целей вводится концепция множества точек неулучшаемых решений [41] (так называемая оптимальность по Паретто [4],[6]). Неухудшаемое решение есть такое решение, в котором улучшение в одной из целей приводит к некому ослаблению другой. Для более точной формулировки данной концепции рассмотрим некую область допустимых решений Теоретические основы математических и инструментальных методов экономикив параметрическом пространстве Теоретические основы математических и инструментальных методов экономики, которое удовлетворяет всем принятым ограничениям, т.е.

Теоретические основы математических и инструментальных методов экономики

(3-48)

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

Теоретические основы математических и инструментальных методов экономики

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

Теоретические основы математических и инструментальных методов экономики, где Теоретические основы математических и инструментальных методов экономикипри условии Теоретические основы математических и инструментальных методов экономики

(3-49)

Точка неулучшаемого решения может быть определена как:

Определение. Точка Теоретические основы математических и инструментальных методов экономикиявляется неулучшаемым решением, если для некоторой окрестности Теоретические основы математических и инструментальных методов экономикинет некого Теоретические основы математических и инструментальных методов экономикитакого, что Теоретические основы математических и инструментальных методов экономикии

Теоретические основы математических и инструментальных методов экономики


Стратегия взвешенных сумм

Данная стратегия взвешенных сумм преобразует многокритериальную задачу минимизации вектора Теоретические основы математических и инструментальных методов экономикив некую скалярную задачу путем построения неких взвешенных сумм для всех выбранных объектов.

Теоретические основы математических и инструментальных методов экономики

(3-51)

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

Метод Теоретические основы математических и инструментальных методов экономики-ограничений

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

Теоретические основы математических и инструментальных методов экономики

(3-52)

при выполнении условия

Теоретические основы математических и инструментальных методов экономики

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

Метод достижения цели.

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

Теоретические основы математических и инструментальных методов экономики

(3-53)

При условии, что

Теоретические основы математических и инструментальных методов экономики

Член Теоретические основы математических и инструментальных методов экономикивносит в данную задачу элемент ослабления, что, иначе говоря, обозначает жесткость заданного намерения. Весовой вектор w дает исследователю возможность достаточно точно выразить меру взаимосвязи между двумя целями. Например, установка весового вектора w как равного исходному намерению указывает на то, что достигнут тот же самый процент недо- или передостижимости цели Теоретические основы математических и инструментальных методов экономики. Посредством установки в ноль отдельного весового коэффициента (т.е. Теоретические основы математических и инструментальных методов экономики) можно внести жесткие ограничения в поставленную задачу. Метод достижения цели обеспечивает подходящую интуитивную интерпретацию поставленной исследовательской задачи и которая, в свою очередь, является вполне разрешимой с помощью стандартных процедур оптимизации.

Гладкая оптимизация. Седловая точка. Условие Куна-Таккера. Двойственные задачи оптимизации.

Метод множителей Лагранжа позволяет отыскивать максимум или минимум функции при ограничениях-равенствах. Основная идея метода состоит в переходе от задачи на условный экстремум к задаче отыскания безусловного экстремума некоторой построенной функции Лагранжа. Пусть задана задача НП при ограничениях-равенствах вида

минимизировать Теоретические основы математических и инструментальных методов экономики                    (5.2.1)

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

Теоретические основы математических и инструментальных методов экономики                            (5.2.2)

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

Теоретические основы математических и инструментальных методов экономики              (5.2.3)

Справедливо такое утверждение [18]: для того чтобы вектор Теоретические основы математических и инструментальных методов экономики являлся решением задачи (5.2.1) при ограничениях (5.2.2), необходимо, чтобы существовал такой вектор Теоретические основы математических и инструментальных методов экономики, что пара векторов удовлетворяла бы системе уравнений

Теоретические основы математических и инструментальных методов экономики                          (5.2.4)

Теоретические основы математических и инструментальных методов экономики                       (5.2.5)

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

Составляют функцию Лагранжа      Теоретические основы математических и инструментальных методов экономики

Находят частные производные        Теоретические основы математических и инструментальных методов экономики

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

Теоретические основы математических и инструментальных методов экономики                  (5.2.16)

и отыскивают точки Теоретические основы математических и инструментальных методов экономики, удовлетворяющие системе (5.2.16).

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


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

Рассмотрим функцию Лагранжа Теоретические основы математических и инструментальных методов экономики 

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

Теоретические основы математических и инструментальных методов экономики                        (5.3.28)

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

Теоретические основы математических и инструментальных методов экономики            (5.3.29)

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

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

Теоретические основы математических и инструментальных методов экономики                   (5.3.30)

и

Теоретические основы математических и инструментальных методов экономики                          (5.3.31)

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

Теоретические основы математических и инструментальных методов экономики                            (5.3.15)

Теоретические основы математических и инструментальных методов экономики                    (5.3.16)

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

Теоретические основы математических и инструментальных методов экономики                          (5.3.17)

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

Теоретические основы математических и инструментальных методов экономики                                (5.3.18)

Теоретические основы математических и инструментальных методов экономики                             (5.3.19)

Теоретические основы математических и инструментальных методов экономики              (5.3.20)

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

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

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

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

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

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

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

Градиентные методы гладкой оптимизации. Общая идея градиентного спуска (подъема). Пропорциональный градиентный метод. Полношаговый градиентный метод. Метод сопряженных градиентов.

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

Градиентом дифференцируемой функции f(x) в точке х[0] называется n-мерный вектор f(x[0]), компоненты которого являются частными производными функции f(х), вычисленными в точке х[0], т. е.

f'(x[0]) = (дf(х[0])/дх1, …, дf(х[0])/дхn)T.

Этот вектор перпендикулярен к плоскости, проведенной через точку х[0] , и касательной к поверхности уровня функции f(x), проходящей через точку х[0] .В каждой точке такой поверхности функция f(x) принимает одинаковое значение. Приравнивая функцию различным постоянным величинам С0, С1, ... , получим серию поверхностей, характеризующих ее топологию

Вектор-градиент направлен в сторону наискорейшего возрастания функции в данной точке. Вектор, противоположный градиенту (-f’(х[0])), называется антиградиентом и направлен в сторону наискорейшего убывания функции. В точке минимума градиент функции равен нулю. На свойствах градиента основаны методы первого порядка, называемые также градиентным и методами минимизации. Использование этих методов в общем случае позволяет определить точку локального минимума функции.

Очевидно, что если нет дополнительной информации, то из начальной точки х[0] разумно перейти в точку х [1], лежащую в направлении антиградиента - наискорейшего убывания функции. Выбирая в качестве направления спуска р[k] антиградиент -f’(х[k]) в точке х[k], получаем итерационный процесс вида

х[k+1] = x[k]-akf'(x[k]), аk > 0; k=0, 1, 2, ...

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

xi[k+1]=хi[k] - akТеоретические основы математических и инструментальных методов экономикиf(x[k])/Теоретические основы математических и инструментальных методов экономикиxi

i = 1, ..., n; k= 0, 1, 2,...

В качестве критерия останова итерационного процесса используют либо выполнение условия малости приращения аргумента || x[k+l] - x[k] || <= e, либо выполнение условия малости градиента

|| f’(x[k+l]) || <= g,

Здесь e и g - заданные малые величины.

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

При методе с постоянным шагом для всех итераций выбирается некоторая постоянная величина шага. Достаточно малый шаг аk обеспечит убывание функции, т. е. выполнение неравенства

f(х[k+1]) = f(x[k] – akf’(x[k])) < f(x[k]).

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

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

Метод наискорейшего спуска

При использовании метода наискорейшего спуска на каждой итерации величина шага аk выбирается из условия минимума функции f(x) в направлении спуска, т. е.
f(x[k] –akf’(x[k])) = Теоретические основы математических и инструментальных методов экономикиf(x[k] – af'(x[k])).

Это условие означает, что движение вдоль антиградиента происходит до тех пор, пока значение функции f(x) убывает. С математической точки зрения на каждой итерации необходимо решать задачу одномерной минимизации по а функции
j(a) = f(x[k] - af'(x[k])) .

Алгоритм метода наискорейшего спуска состоит в следующем.

1. Задаются координаты начальной точки х[0].

2. В точке х[k], k = 0, 1, 2, ... вычисляется значение градиента f’(x[k]).

3. Определяется величина шага ak, путем одномерной минимизации по а функции j(a) = f(x[k] - af'(x[k])).

4. Определяются координаты точки х[k+1]:

хi[k+1] = xi[k] – аkf’i(х[k]), i = 1 ,..., п.

5. Проверяются условия останова стерационного процесса. Если они выполняются, то вычисления прекращаются. В противном случае осуществляется переход к п. 1.

В рассматриваемом методе направление движения из точки х[k] касается линии уровня в точке x[k+1] (Рис. 2.9). Траектория спуска зигзагообразная, причем соседние звенья зигзага ортогональны друг другу. Действительно, шаг ak выбирается путем минимизации по а

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту

Похожие рефераты: