|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция |
Градиентный метод
Производной функции F (Х) = F (
Абсолютная величина производной по направлению даёт скорость изменения функции в этом направлении, а знак показывает характер изменения функции (возрастание или убывание). Градиент функции F (Х) = F ( grad F (Х) В каждой точке Х направление наискорейшего возрастания функции F (Х) совпадает с направлением градиента Градиентный метод – метод решения задач математического программирования, основанный на поиске экстремума функции путём последовательного перехода к нему с помощью градиента этой функции. В случае поиска минимума функции говорят о методе наискорейшего спуска, в случае задачи максимизации – о методе наискорейшего подъёма. Общая схема решения задач математического программирования градиентным методом состоит в построении последовательности
если ищется Fmax, или
если ищется Fmin. Число Если Если
Замечания. 1) На практике итерации продолжаются до тех пор, пока не выполнится некоторый критерий счёта, например, | F ( где ε – заданное число (погрешность вычисления). 2) По методу наискорейшего спуска длина шага Необходимое условие экстремума этой функции имеет вид:
- скалярное произведение градиентов целевой функции в точках равно нулю, что равносильно условию ортогональности градиентов. 3) Для упрощения вычислений в формулах (5.23) – (5.25) можно вместо Условие (5.25) даёт геометрическую интерпретацию градиентного метода в случае функции 2-х переменных: луч, идущий от точки
Пример. Решить задачу: F ( Решение. 1) Покажем, что данная задача является задачей выпуклого программирования. Частные производные функции F ( А = Её главные миноры: 2) Решим ЗВП градиентным методом - методом наискорейшего спуска. ОДР задачи – криволинейная область АВС (рис. 46) Найдём градиент целевой функции: В качестве исходной точки выберем точку Х 0 (2; 1), принадлежащую ОДР. Вычислим значение градиента в точке Х 0:
Следующую точку Х 1 найдём по формуле (5.24):
Градиент в точке Х 1:
![]()
Рис.3. Область допустимых решений ЗВП
По условию (5.25) найдём
Подставим это значение в выражения для Х 1 и Х 1 = (1; 2); Так как градиент в точке Х 1 = (1; 2) равен нулю, то в этой точке достигается минимум целевой функции. Fmin (1; 2) = - 2. Экстремум найден за 1 шаг, причём он достигается во внутренней точке ОДР. Вычисления по методу наискорейшего спуска удобно представлять в таблице. Расчёты данной ЗВП занесём в табл. 21.
Таблица 21
В данном примере экстремум достигался внутри ОДР. Если экстремум ЗВП достигается на границе ОДР, то поступают следующим образом. В качестве исходной точки Пусть система ограничений ЗВП линейна, т.е. имеет вид
Пусть методом скорейшего спуска получена последовательность точек Если
где Для того, чтобы остаться в ОДР, нужно вместо Шаг
По формуле (5.27) находят Если прямая на плоскости задана уравнением ax + by + c = 0, то её направление задаётся вектором
Пример. Решить ЗВП градиентным методом: F ( Решение. Область допустимых решений задачи – трапеция ОАВС (рис. 4). Градиент целевой функции
![]()
Рис.4. Область допустимых решений ЗВП
В качестве исходной точки выберем точку Х 0 (1; 1), принадлежащую ОДР. Вычислим значение градиента в точке Х 0:
Следующую точку Х 1 найдём по формуле (23):
Градиент в точке Х 1: По условию (5.25) найдём
Подставим это значение в выражение для Х 1, получим: Х 1 = Точка Х 1 не принадлежит ОДР, причём не выполняются оба неравенства системы ограничений. По формуле (5.27) найдём
Точка Направление прямой Следующую точку Х 2 найдём по формуле:
Градиент в точке Х 2:
По условию (5.25) найдём
Подставим это значение в выражения для Х 2 и Х 2 = (3; 2); Точка Х 2 лежит на границе ОДР, на прямой
Так как проекция градиента на это направление равна нулю, значит, получено оптимальное решение. Максимум целевой функции Fmax (3; 2) = 7. Представим расчёты в табл. 1. Таблица 1
Оптимальное решение ЗВП найдено за 2 шага, причём максимум получен на границе ОДР в точке (3; 2). Пример. Решить ЗВП градиентным методом: F (
Решение. ОДР задачи – треугольник ОАВ (рис. 48). Градиент целевой функции В качестве исходной точки выберем точку Х 0 (2; 2), принадлежащую ОДР. Вычислим значение градиента в точке Х 0:
![]()
Рис.5. Область допустимых решений ЗВП Следующую точку Х 1 найдём по формуле (5.23):
Градиент в точке Х 1: По условию (5.25) найдём
Подставим это значение в выражения для Х 1 и Х 1 = Точка Х 1 принадлежит ОДР. Следующую точку Х 2 найдём по формуле (5.23):
Градиент в точке Х 2: Вычисления с округлениями до 10-2 представим в табл. 23. На 5-м шаге вычисления можно остановить, т.к. значение целевой функции меняется незначительно: | F ( Таким образом, можно считать, что максимум целевой функции (с точностью вычислений ε = 0,01) достигается в точке Fmax (6,66; 7,33) = 24,33. Таблица 2
Контрольные вопросы: 1. Сформулируйте задачу нелинейного программирования. Приведите примеры. 2. Перечислите и охарактеризуйте методы решения задач нелинейного программирования. Литература: 1. Высшая математика для экономистов: Учебник для вузов / Н.Ш. Кремер, Б.А. Путко, И.М. Тришин, М.Н.Фридман. Под ред. Н.Ш. Кремера. – М.: ЮНИТИ, 2005. – 471 с. 2. Общий курс высшей математики для экономистов: Учебник. / Под ред. В.И. Ермакова. –М.: ИНФРА-М, 2006. – 655 с. 3. Сборник задач по высшей математике для экономистов: Учебное пособие / Под ред.В.И. Ермакова. М.: ИНФРА-М, 2006. – 574 с. 4. Гмурман В. Е. Руководство к решению задач по теории вероятностей и магматической статистике. - М.: Высшая школа, 2005. – 400 с. 5. Гмурман. В.Е Теория вероятностей и математическая статистика. - М.: Высшая школа, 2005. 6. Данко П.Е., Попов А.Г., Кожевникова Т.Я. Высшая математика в упражнениях и задачах. Ч. 1, 2. – М.: Оникс 21 век: Мир и образование, 2005. – 304 с. Ч. 1; – 416 с. Ч. 2. 7. Математика в экономике: Учебник: В 2-х ч. / А.С. Солодовников, В.А. Бабайцев, А.В. Браилов, И.Г. Шандара. – М.: Финансы и статистика, 2006. 8. Шипачев В.С. Высшая математика: Учебник для студ. вузов – М.: Высшая школа, 2007. – 479 с.
Поиск по сайту: |
Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.032 сек.) |