Методы оптимизации в экономике

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ московский АвиАционный инстит~т (гоеударствеиный техиичеекий уииверентет) Кафедра "Математичеекая кибернетика" Т,Б. Волкова, Л.с. Диканова, Н.Э. Журина, Т.И. Короткова, И.И. Топчеева МЕТОДЫ ОПТИМИЗАЦИИ 8 ЭКОНОМИКЕ Река иендовано в качестве учебного нособия Рбт)икчионным советом фокультетй Приклидния л1ппюмотикй и физико Московского йвищионБОГО институто МОСКВА 2аба 1. БЕЗУСЛОВНАЯ ОПТИМИЗАЦИЯ Безусловной оптимизацией называют задачу отыскания экстремума (наибольшего или наименьшего значения) скалярной функции 1".(х) и-мерного векторного аргумента при отсутствии ограничений ,1'(х) — ех1г, х Е Е" .

(1.1) В тех случаях, когда известен аналитический вид зависимости оптимизируемой функции~(х) от независимых переменных х, (1 = Г,л ) для отыскания экстремума функций применяются методы исследования функций классического анализа. Это позволяет найти также в аналитическом виде производные оптимизируемых функций, с помощью которых и формулируют необходимые и достаточные условия существования экстремума 111. Использование необходимых условий приводит к необходимости решения системы п уравнений с л неизвестными. Такая система является в общем случае нелинеинои и ее решение представляет значительные трудности.

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

Задача отыскания безусловного экстремума представляет не только самостоятельный интерес, но и является одним из этапов решения более сложных оптимизационных задач, например задач с ограничениями. При решении задачи (1.1) прямыми методами строят последовательности ~х ~ по алгоритму, сходящемуся к стационарной точке функции ~(х ) при выполнении некоторых условий 111. 1.1. Методы градиентного и наискорейшего спуска Градиентный метод является одним из самых распространенных и самых простых методов поиска безусловного экстремума. Он основан на свойстве градиента функции, согласна которому направление градиента совпадает с направлением наискорейшего возрастания функции, а направление антиграднента — с направлением наискорейп|его уб~~ани~ функции.

1 радиентные ~с~од~ ~~еют итерационную формулу вида х +' =ха+ й у~(х"), где Ь вЂ” скаляр, называемый величиной шага; 7 1'(х " ) — градиент функции 1". ( х ) в точке х "; х — начальная точка, задаваемая пользователем. Знак «-» в формуле используется при решении задачи минимизации, «+» — при решении задачи максимизации.

Б градиентном методе шаг Ь выбирается постоянным исходя из ус- ЛОВИМ 1'(х" + Ь 7 1".(х )) Я(х ), Если это условие не выполняется, то величина шага уменьшается до тех пор, пока условие (1,3) не будет выполнено. Алгоритм метода градиентного спуска: 1. Записывается градиент 17,1".(Х) исследуемой функции Г" (х): 2. Задается начальная точка х = (х~1,х~~,...х,",)*, шаг Ь, допу- стимая погрешность вычисления Е > О. 3. Полагается к=О. 4. Вычисляются ~ (х ") и 7 ~(х") . 5. Проверяется условие окончания итерационного процесса < Е, 1=1,2,...,л .

д Х. к=х Если это условие выполняется, то итерационный процесс заканчивается: найденная точка х" с точностью до Я является стационарной точкой 11,21, Если это условие не выполнено, переходят к п.6. 6. Находится новое приближениех"+' = х" + 6 Ъ'~(х'), 7. Вычисляется ~ (х "' ) и проверяется условие )'(х" ~) ~~~(х") Если это условие не выполняется,то шаг дробится (например, пополам) и с новым значением шага повторяется п.б.

3. Полагается к=к+1 и осуществляется переход к п.4. П р и м е р. Определить градиентным методом шах функции 4х~ + 2х~ — х~~ — х~~ — 5 . За начальную точку взять х (4,5);У(х ) = — 10 . о Решаем задачу методом градиентного спуска: 1. Записываем частные производные и градиент функции ~(х ): О 4 — 2х~ — 4 — 2х; 2 — 2х~ , '~7~ = а~, 2. Определяем градиент функции в т. х: ~? ~(х ) = О . ( — 4; — 8)~ . 1 о 3. Находим значениях = х + Л ~7~(х ), х = 5 + Ь 4.

Принимаем 6=0,5, тогда " — ~' ) Л ~- ~ — ~ '~ 5. Вычисляем значение функции ~(х ): ~(х ) = О. 1 . 1 6. Вычисляем градиент в т. х: 1. ~7~(х ) = Таким образом, т. х~ является стационарной и дальнейшее продвижение вдоль градиента невозможно.

В методе наискорейшего спуска шаг Ь„выбирается для каждого значения к из условия аппп~(х" — Л„~7 ~(х" ) ), Ь > О х Это условие может быть записано как ф~ (х" — Ь„~7 ~ (х ) ) — О ОЬ или в виде ( ~7 ~ (х " ), ~7 У ( х " ' ) ) = О . 1. Находится ~? ~ (х ) . 2.

ЗадаЕРСя НачаЛЬНОЕ Пзчнб'ззижснйзс Х И ПОГРЕШНОСТЬ ВЫ'зиСЛЕ ний Е > О . 3. Полагается к=О. 4. Находятся~ (х"), ~7~ (х"). 5. Проверяется условие окончания итерационного процесса я Е, г 1,п . Если это условие не выполняется, то переходят к п.б. 6. Вычиелиеееи л, - еенти~ (кз'') и нааиеннее значение А, а„ подставляется в итерационную формулу ~+1 7. Проверяется условием (х"' ) ~~ ~ (х ) . 8. Полагается к=к+1 и осуществляется переход к п.4. 8 этом методе, в Отличие От метода обычного градиентного спуска, направление дВижения из точки х касается линии урОВня в точке х"'1. Последовательность точек х,х1, ...,х" зигзагообразно приближается к точке экстремума функции, причем звенья этой ломаной ортогональны между собой.

Метод наискорейшего спуска обеспечивает движение к экстремуму с самым выгодным шагом. К методам, называемым методами первого порядка, в которых используются только значения первых производных Оптимизируемых функций, относятся метод покоординатного спуска, метод релаксаций, метод Гаусса — Зейделя и др. (1, 2, 31. 1.2. Градиентные методы 2-го порядка ) б ~)х) =~~х )+ Е ~х; — х;)+ ) ~х ) Эх, Введем обозначения: О, ~~( О) (дХ 3х~ 3„~ 1 =~э~, э~, *" а~„~ )')х) -У1х')+ Х ~х, — х,')- хо) Ах~ $К(х ) = То~да ~У( ") + И~(х")~" = О, где ~" = х"+' — х", Отсюда следует ~" = — В' (х") ~) У (х") к+1 к И)- 1( к))~',)у ( к) или Алгоритм метода Ньютона: 1.

Вычисляются 7~(х) и И'(х) * 2. Задаются начальная точка х и погрешность вычислений Е>О,к=О. 3. Вычисляются ~(х") и )"(х"). Лх) =у 1х') - ~у(х') 1+ —, ()')) ~хх)~). Найдем минимум функции )~(х ), используя необходимые условия экстремума функции: )'— — = 0 =~ ~7~(х ) + И~(хО)Р = О И~ или для любой точки х" можно записать 4х1+х — 3 4 1 1. ~7,~ й'(х) 1, де1$Р'= 23 ° 0 . х1 + бх~ 2.хо - ,', Е = 10- ' О) — 3 1~,( О) 4 1 Ц~т( О) б — 1 23 23 1 4 23 23 4, ХР'- '(х')- 5Х1 О ~7.~ (х ) = =~ х —, — — — точка ш1п 0 1 18 3 0 23 ' 23 1.3* Варианты заданий Задана функция вида ~(х ) = Я11х1 + п1зх 1 х2+ И~2х ~+ Ь1х1+ Ь2х~ 2 з 1. Найти экстремум и определить его тип (шак или ш1п) для заданной функции )". (х ) классическим методом, используя необходимые и достаточные условия существования экстремума (11.

4. Находится Б' (х ) 5, вычисляется приближение х =х — й' (х ) ЧУ(х ) и т д. Таким образом, на каждо~ шпаге Итерации помимо градиента долл~на Вычисляться матрица вторых производнык. Градиентные методы второго порядка оказываются эффективными для строго выпуклых функций и позволяют определить точку экстремума с высокой степенью точности. Обычно и окрестности точки экстремума функция Г(х) является выпуклой и поэтому метод особенно эффективен на заключительном этапе вычислений. П р и и е р. У (х) - 2х1 + Зх2 + х1 х2 — Зх1 - ш1п . г Г 1 В настоящее время транспортная задача линейного программирования широко применяется как в теоретических разработках, так н в практике планирования различных экономических процессов, 2.1.

Постановка задачи и ее математическая модель Некоторый однородный продукт, сосредоточенный у т поставщиков Таблица 21 '11 1,2,...,т) единиц соответственно, необходим и потребителям В в количестве п~~ етй О и Ь (1 = 1,2, ...,и) единиц. Известна стоимость С пере- 1/ Ж1 ейй пйп возки единицы груза от 1-го поставщика у -му потребителю. Необходимо составить ° 4 В $ $ ° Ф ° план перевозок, имеющий ми- мальную стон ос ь5 хм~ Хщй ... хвяь Аи ляющий вывезти все грузы и В1 полностью удовлетворить потребности потребителей.

Обозначим через х; количество единиц груза, запланированных к перевозке от 1-го поставщика к 1'-му потребителю; тогда условие задачи можно записать в виде матрицы планирования (табл.2.1). Совокупность чисел (х; ) будем называть планом перевозок, а сами числа х; — перевозками. Составим математическую модель задачи. Так как от 1-го поставщика к 1-му потребителю запланировано к перевозке х; единиц груза, то стоимость перевозки составит С; х; . Стоимость всего плана выразится двойной суммой: ПЗ Р$ У=Х Х С;х; 1=11 =1 Систему ограничений получаем из следующих условий задачи: а) все грузы должны быть вывезены, т.е. Х х; = а„.

1=1 (1 = 1, 2,, т ) (эти уравнения получаются из строк табл, 2.1); 1О б) все потребности должны быть удовлетворены, т.е. Хх; =Ь. (у'= 1,2,...,л) 1-1 (уравнения получаются из столбцов табл. 2.1). 7 ««м«»»»»«»»»» ъ~»««««« ° ««««« ° «««««, »»«««»««ыт««г«« '«'т»й««Г«»«»т~ч'ъло««чсдп»«««н 7лъяР »«««««««««~«««« ~н «г « "а «»««» ««м -д. - «»- « ет следующий вид. Найти наименьшее значение линеЙной функции Ш П У = Х Х С~~х~,.

~-1 ~-1 при ограничениях « у-1 П$ Хх; =Ь~,~ = 1,2,...,п; г 1 х; ~ О (1 = 1,2,...,т; у = 1,2,...,л). (2.1) В рассмотренной модели предполагается, что суммарные равны суммарным потребностям, т.е. модель закрытая и 'чаФ'тя~ «.3 ФИ и Ха = Х Ь. / ~-! у-1 В противном случае модель должна быть сведена к закрытой путем введения фиктивного поставщика или фиктивного потребителя Будем называть любой план перевозок допустимым, если он удовлетворяет условиям (2.1) — (2.2), Допустимый план будем называть опорным, если в нем отличны от нуля не более т + л — 1 базисных перевозок, а остальные перевозки равны нулю.