Экономические методы и модели

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

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

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

     Так, в решении задач НП могут быть испльзованы:

     а) прямые методы, состоящие в нахождении оптимального решения в направлении  наиболее быстрого его достижения, которые относятся к группе градиентных  методов (например, метод наискорейшего  спуска);

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

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

     Рассмотрим  принципиальную суть некоторых нелинейных методов оптимизации. 

     Метод множителей Лагранжа 

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

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

      (2.8)

при ограничениях-равенствах на переменные

        (2.9)

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

(2.10)

где , - дифференцируемые функции;

- не определенные пока еще  множители Лагранжа.

      Находятся частные производные функции L по всем переменным и приравниваются нулю:

 

  (2.11)

      После чего формируется нелинейная система  уравнений:

(2.12)

      Из  решения этой системы находятся  вектор переменных X=( x₁, x₂, …x_n) и стационарные точки . Эти величины  определяются из условий экстремума, поэтому в них возможен максимум или минимум функции. Иногда стационарная точка является точкой перегиба.

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

Выпуклое  программирование 

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

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

     В выпуклом программировании целевая  функция является выпуклой (вогнутой) и гладкой.

     Функция f(x) называется выпуклой, если для любых х₁ и х₂ отрезок АВ, содержащий точки на кривой, лежит ниже графика функции и имеет место условие

(2.13)

для любых х₁ и х₂ и любого действующего числа .

      Если  в условии (2.13) изменить знак неравенства ≤ на ≥, то получим определения вогнутой функции. Если же в условии (2.13) неравенства выполняются как строгие, то функция называется строго выпуклой (или строго вогнутой).

      Гладкость функции означает непрерывность  ее первых производных.

      Задача  выпуклого программирования формулируется  следующим образом: найти минимум  целевой функции  (2.14)

при наличии ограничений на переменные

  (2.15)

и условий неотрицательности  переменных

  (2.16)

      Для вогнутой функции Z достигает максимального значения.

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

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

     К методам решения задач выпуклого  программирования относятся: градиентные  методы, в том числе метод наискорейшего  спуска; метод секущих плоскостей; метод кусочно-линейной аппроксимации целевой функции и функции ограничений; графический метод при наличии двух переменных. 

Динамическое  программирование 

     Разновидностью  подхода оптимизации в задачах  математического программирования является динамическое программирование.

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

     Начало  развития динамического программирования относится к 50-м годам 20 века и  связано с именем Р. Беллмана. Ему  принадлежит разработка основного  функционального уравнения, которое  является математическим выражением сформулированного  им же одного из важных принципов динамического программирования – принципа оптимальности. Этот принцип состоит в следующем: оптимальное поведение обладает тем свойством, что, каковы бы ни были первоначальное состояние и решение в начальным момент, последующие решения должны составлять оптимальное поведение относительно состояния, получающегося в результате первого решения.

     Особенность модели динамического программирования является то, что увеличение количества переменных в задачах вызывает рост возможных вариантов решения. Возникает так называемая проблема размерности (или «проклятие размерности», по выражению Р. Беллмана), которая является серьезным препятствием при решениях задач динамического программирования средней и большой размерности даже на ПК (из-за ограниченности объема оперативной памяти).

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