Методы оптимизации в экономике (1014358)
Текст из файла
ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ московский АвиАционный инстит~т (гоеударствеиный техиичеекий уииверентет) Кафедра "Математичеекая кибернетика" Т,Б. Волкова, Л.с. Диканова, Н.Э. Журина, Т.И. Короткова, И.И. Топчеева МЕТОДЫ ОПТИМИЗАЦИИ 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 базисных перевозок, а остальные перевозки равны нулю.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
