К сожалению, соотношение двойственности справедливо далеко не всегда. Среди широких классов задач математического программирования в этом плане можно выделить линейное программирование (при условии непустоты множеств допустимых планов) и выпуклое программирование (также при некоторых условиях регулярности, среди которых наиболее известным является условие Слейтера, требующее существования внутренней точки для множества, задаваемого ограничениями (2)).
Теорема Куна-Таккера. Если задача (4) является задачей выпуклого программирования, удовлетворяющей условию Слейтера, то необходимым и достаточным условием оптимальности плана x0 k X является существование такого y0 k Y, что пара (x0, у0) является седловой точкой функции Лагранжа, то есть удовлетворяет (8).
В соответствии с теоремами двойственности решение задач математического программирования можно сводить к нахождению седловых точек, причем на множествах более простой структуры (без ограничений вида неравенств (2)).
Градиентные методы.
Рассмотрим сначала задачу максимизации функции f (x) без ограничений, то есть в случае, когда Х совпадает со всем пространством R n. Градиент функции f (x) обозначим f 1(х). Условие оптимальности в этом случае имеет вид, однако непосредственное решение системы уравнений (9) может оказаться чересчур сложным.
1(х) = 0
Поэтому на практике поступают следующим образом. Выбирая произвольную начальную точку х1 , строят итеративный процесс
+ 1 = xk + ak f 1(xk), k = 1, 2, _
Число ak называют длиной шага или просто шагом. Если все ak равны между собой, то имеем процесс с постоянным шагом.
Процесс (10), лежащий в основе градиентных методов, представляет собой движение в сторону возрастания функции f (x), так как если f 1(хk) ? 0, то всегда можно выбрать ak так, что f (xk + 1) > f (xk). Существуют разные способы выбора ak . Вообще говоря, наилучшим является выбор такого ak , при котором обеспечивается максимальный рост функции f (x). Такое ak находится из условия
Градиентный метод поиска экстремума (10) с выбором шага по способу (11) называется методом скорейшего подъема (или спуска для задачи на минимум). Такой метод требует наименьшего числа итераций, но зато на каждом шаге приходится решать дополнительную задачу поиска экстремума (11) (правда, в одномерном случае). На практике часто довольствуются нахождением любого ak , обеспечивающего рост функции. Для этого берут произвольное ak и проверяют условие роста. Если оно не выполняется, то дробят ak до тех пор, пока это условие не будет выполнено (такое достаточно малое ak при f 1(хk) ? 0 существует всегда).
Процесс (10), очевидно, останавливается, когда выполнено условие (9). При этом если функция f (x) вогнута, то найденная стационарная точка будет решением задачи максимизации. В противном случае необходимо провести дополнительно исследование функции f (x) в окрестности найденной точки. Однако, даже если она будет точкой максимума, в невыпуклом случае трудно определить, локальный это максимум или глобальный. Поэтому градиентные методы обеспечивают нахождение глобального экстремума только для вогнутых (выпуклых) функций, а в общем случае дают лишь локальные экстремумы (при этом можно попытаться найти глобальный экстремум, применяя итеративный процесс многократно с разными начальными точками).
Если рассматривается задача максимизации f (x)
при ограничениях, то есть когда Х не совпадает с R n, то непосредственное
применение процесса (10) может привести к нарушению ограничений, даже если
начальная точка x1 k X. Однако эту трудность можно преодолеть, например, если
получаемую по формуле (10) очередную точку проектировать на множество Х. Если
обозначить операцию проектирования х на множество Х через Рх(х), то
соответствующий итеративный процесс имеет вид
хk + 1 = Рх(хk + ak f 1(хk))
Полученный метод носит название метода проекции градиента. Шаг ak в методе (12) может выбираться различными способами (например, как в методе скорейшего подъема). Стационарная точка этого процесса является решением задачи (4) в случае вогнутой функции f (x), а в общем случае требуется дополнительное исследование.
Недостатком метода проекции градиента является необходимость проведения операции проектирования, которая в общем случае эквивалентна некоторой задаче поиска экстремума. Однако, когда Х является шаром, параллелепипедом, гиперплоскостью, полупространством или ортантом, задача проектирования решается просто и в явном виде.
Еще одной разновидностью градиентных методов является метод условного градиента, который также предназначен для решения экстремальных задач с ограничениями. Суть его состоит в решении вспомогательной задачи максимизации на множестве Х линейной функции б f 1(xk), x - xk с, представляющей собой главную часть приращения функции f (x) в точке хk . Эта вспомогательная задача может быть непростой, но если Х задается линейными ограничениями, то она представляет собой задачу линейного программирования, которая решается за конечное число шагов стандартными методами (например, симплекс-методом). Если решение вспомогательной задачи найдено, то следующее приближение для исходной задачи строится по формуле
Если множество Х выпуклое, то хk + 1 k Х. Шаг ak выбирается из условия максимального роста функции f (x) или любым другим способом, обеспечивающим рост f (x). На практике обычно решают вспомогательную задачу не точно, а приближенно. В процессе (13) направление движения не совпадает с градиентом функции f (x) в точке хk , но определяется им, так как его компоненты берутся в качестве коэффициентов линейной целевой функции вспомогательной задачи.
Методы возможных направлений
Рассмотрим вариант метода возможных направлений
применительно к задаче максимизации f (x) на множестве (3), где R = R n. Пусть
мы имеем k-е приближение хk к решению этой задачи, и для построения следующего
приближения поставим вспомогательную задачу: максимизировать u при ограничениях
б f 1(xk), aс $ u, бg1(xk), aс $ u,k Ik | a j | # 1, j = 1, 2, _, n,
где= {i | 1 # i # m, gi(xk) = 0}, a = (a1, _,
an).
Эта задача представляет собой задачу линейного программирования в (n + 1)-мерном пространстве векторов (a, u). Множество планов замкнуто, ограничено и непусто, так как a = 0, u = 0 является допустимым планом. Значит, вспомогательная задача имеет решение (ak, uk), причем uk $ 0. Если uk > 0, то нетрудно показать, что направление ak является возможным направлением возрастания функции f (x), то есть точка xk + 1 = xk + akak при достаточно малом ak принадлежит множеству Х и обеспечивает большее значение функции f (x), чем хk . Выбор пары (аk, uk) с возможно большим значением uk при этом означает выбор допустимого направления, наиболее близкого к градиенту функции, то есть возможного направления с наибольшим ростом функции. Если uk = 0, то получается стационарная точка процесса, которая для задачи выпуклого программирования дает решение, а в общем случае требует дополнительного исследования.
Методы множителей Лагранжа
Эта группа методов основана на сведении решения задачи математического программирования к нахождению седловой точки функции Лагранжа. Методы множителей Лагранжа представляют собой различные процедуры поиска седловой точки. В качестве такой процедуры можно взять, например, итеративный процесс как в методе проекции градиента, применив его для подъема по переменной х и спуска по переменной y. Получим процесс
(x) = (g1(x), _, gm(x)), Y = {y | y $ 0}.
Проекция на множество Y определяется весьма просто:
(y) = (Z1 , _, Zm), Zi = max (yi , 0), i = 1, 2,
_, m.
Если R - неотрицательный ортант, то проекция на него определяется аналогичным образом.
Методы второго порядка
До сих пор мы рассматривали методы первого порядка, то есть методы поиска экстремума, использующие первые производные. Фактически в этих методах производится линеаризация, связанная с заменой максимизируемой функции f (x) линейным членом разложения ее в ряд Тейлора. Но если функция дважды непрерывно дифференцируема, то можно использовать для ее аппроксимизации два члена ряда Тейлора. Использование такой аппроксимизации в итеративном процессе может повысить скорость сходимости.
Наиболее известным из методов второго порядка является метод Ньютона, который состоит в следующем. На k-й итерации, имея приближение хk , ставим вспомогательную задачу максимизации функции
(x) = б f 1(xk), x - xk с + 0,5 б f "(xk)(x
- xk), x - xk с
на множестве Х. Пусть тогда следующее приближение строится по формуле Шаг ak можно выбирать разными способами, в частности можно положить ak = 1, тогда в качестве следующего приближения принимается просто решение вспомогательной задачи, то есть .
Для задачи без ограничений, когда Х = R n, метод Ньютона существенно упрощается. Действительно, в этом случае то есть
Значит, для нахождения надо решить систему линейных уравнений (14). Если матрица f "(xk) не вырождена, то имеем просто (при ak = 1)
Достоинством метода Ньютона является высокая скорость сходимости, которая с лихвой компенсирует усложнение вычислений на каждой итерации. Недостатком метода является то, что он сходится при весьма жестких предположениях.
Методы штрафных функций
Как видно из предыдущих рассмотрений, наличие ограничений существенно усложняет задачу поиска экстремума функции. Почти все изложенные методы решения экстремальных задач включали специальные сложные процедуры, учитывающие наличие ограничений (например, проектирование). В этом смысле в особую группу выделялись методы множителей Лагранжа, которые состоят в сведении задачи поиска экстремума с ограничениями к задаче поиска экстремума (точнее, седловой точки, что примерно то же самое) без ограничений или с ограничениями простого вида, учет которых не составляет труда (это видно на примере операции проектирования на неотрицательный ортант). Однако эти методы применимы практически только в выпуклом случае. От этого недостатка избавлены методы штрафных функций, которые позволяют в весьма общем случае сводить экстремальные задачи со сложными ограничениями к задачам без ограничений или с простыми ограничениями, а в сочетании с методами поиска безусловного экстремума служат универсальным средством решения задач математического программирования (конечно, не лишенным недостатков).
Рассмотрим общую задачу математического программирования (4). Методы штрафных функций основаны на описании множества Х с помощью функций со специальными свойствами. Одна группа методов использует функции вида F(х, с), которые обладают следующими свойствами:
В качестве такой функции можно взять, например, квадратичную функцию штрафа которая является дифференцируемой, если дифференцируемы функции ограничений gi(x). Можно показать, что если f (x) и gi(x), i = 1, 2, _, m, непрерывны на замкнутом, ограниченном множестве R и Х ? , то
При этом если х0(сn) реализует максимум в правой части (15), то любая предельная точка последовательности {x0(сn)} есть решение задачи (4).
Таким образом, с помощью метода штрафных функций общую задачу математического программирования можно свести приближенно (при достаточно большом сn) к задаче без ограничений или с простыми ограничениями (на простом множестве R).
Недостатком методов штрафных функций является ухудшение свойств вспомогательных задач (в правой части (15)) при больших значениях сn , в частности чувствительность к ошибкам вычислений. Эти недостатки преодолены в некоторых вариантах штрафных функций, в которых можно ограничиться конечными значениями штрафных констант сn , а также в близких к ним методах модифицированной функции Лагранжа [2].
Более подробно с задачами и методами нелинейного программирования можно познакомиться в [3-5].
Если говорить о практической реализации методов решения задач математического программирования, то надо иметь в виду, что ни один из них не обладает универсальностью, позволяющей применять его эффективно к разным классам задач. Поэтому методы следует выбирать в зависимости от вида максимизируемой функции и функций ограничений. Еще более эффективными являются использование комбинаций методов и применение их в определенной последовательности, если брать полученное одним методом приближенное решение в качестве начального приближения для следующего метода. Такая идея реализуется в существующих пакетах и системах оптимизации, и для практического решения задач главное - научиться грамотно пользоваться ими (по этому вопросу см., например, [6]).
В современной теории оптимизации рассматриваются
и более сложные, чем (4), классы экстремальных задач, которые возникают в
процессах принятия решений в условиях многокритериальности (векторная
оптимизация), неопределенности (стохастическое программирование, минимаксные
задачи и т.д.), конфликта (теория игр). Эти разделы оптимизации вместе с
математическим программированием составляют новую научную дисциплину - теорию
исследования операций (см., например, [7]). Вместе с тем математический аппарат
исследования операций широко использует рассмотренные выше подходы, которые
составляют основу современных методов оптимизации.
Заключение
математика равновесие богатство маркс
Характерной особенностью научно-технического прогресса в развитых странах является возрастание роли экономической науки.
Экономика выдвигается на первый план именно потому, что она в решающей степени определяет эффективность и приоритетность направлений научно-технического прогресса раскрывает широкие пути реализации экономически выгодных достижений.
Применение математики в экономической науке, дало толчок в развитии как самой экономической науке, так и прикладной математике, в части методов экономико-математической модели. Пословица говорит: «Семь раз отмерь - Один раз отрежь». Использование моделей есть время, силы, материальные средства. Кроме того, расчёты по моделям противостоят волевым решениям, поскольку позволяют заранее оценить последствия каждого решения, отбросить недопустимые варианты и рекомендовать наиболее удачные.
На всех уровнях управления, во всех отраслях используются методы экономико-математического моделирования. Выделим условно следующие направления их практического применения, по которым получен уже большой экономический эффект.
Первое направление - прогнозирование и ᴨȇрсᴨȇктивное планирование. Прогнозируются темпы и пропорции развития экономики, на их основе определяются темпы и факторы роста национального дохода, его распределение на потребление и накопление и т.д. Важным моментом является использование экономико-математических методов не только при составлении планов, но и в деле оᴨȇративного руководства по их реализации.
Второе направление - разработка моделей, которые используются как инструмент согласования и оптимизации плановых решений, в частности это межотраслевые и межрегиональные балансы производства и распределения продукции. По экономическому содержанию и характеру информации выделяют балансы стоимостные и натурально-продуктовые, каждый из которыҳ может быть отчетным и плановым.
Третье направление - использование экономико-математических моделей на отраслевом уровне (выполнение расчетов оптимальных планов отрасли, анализ с помощью производственных функций, прогнозирование основных производственных пропорций развития отрасли). Для решения задачи размещения оптимального прикрепления к поставщикам или потребителям и др. используются модели оптимизаций двух типов: в одних для заданного объёма производства продукции требуется найти вариант реализации плана с наименьшими затратами», в других требуется определить масштабы производства и структуру продукции с целью получения максимального эффекта. В продолжение расчетов осуществляется переход от статистических моделей к динамическим и от статистических моделей к динамическим и от моделирования отдельных отраслей к оптимизации многоотраслевых комплексов. Если раньше были попытки создать единую модель отрасли, то теперь наиболее использование комплексов моделей, взаимоувязанных как по вертикали, так и по горизонтали.
Четвертое направление - экономико-математическое моделирование текущего и оперативного планирования промышленных, строительных, транспортных и других объединений, предприятий и фирм. Область практического применения моделей включает также подразделения сельского хозяйства, торговли, связи, здравоохранения, охрану природы и т.д. В машиностроении используется большое количество разнообразных моделей, наиболее «отлаженными» из которыҳ являются оптимизационные, позволяющие определить производственные программы и наиболее рациональные варианты использования ресурсов, распределить производственную программу во времени и эффективно организовать работу внутризаводского транспорта, существенно улучшить загрузку оборудования и разумно организовать контроль продукции и др.