Модификация метода скорейшего спуска

Решается задача минимизации функции .

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

Выбираем шаг h, затем переходим в направлении антиградиента в новую точку, выбираем шаг h₁ (используется метод деления отрезка пополам).

Чтобы избежать зацикливания программы, в нее вставлен счетчик циклов Т, когда Т > , счет оканчивается (высвечивается “ Время ”); счет также заканчивается, когда сумма абсолютных величин производных меньше заданного положительного числа . .

Вопросы для самоконтроля

1. Основные свойства вектора-градиента.

2. Основная идея градиентного метода нахождения экстремума целевой функции.

3. Критерии прекращения итерационного процесса при применении градиентных методов.

4. Особенность градиентного метода с постоянным шагом.

5. Градиентный метод наискорейшего спуска.

6. Какова точность экстремальных значений целевой функции в градиентном методе?

7. Какие существуют методы выбора шага в градиентном методе?

8. Какова роль штрафной функции?

9. В чем заключается суть метода Франка-Вулфа?

10. В каких случаях используют метод Лагранжа?

11. Какова точность приближенных методов задач нелинейного программирования?

12. Общая постановка задачи нелинейного программирования.

13. Какой метод используют для обобщенных приближенных решений?

ПРАКТИКУМ

Задание 1. Решение задач нелинейного программирования градиентным методом по критерию модуля разности оптимизируемой функции.

Предприятие выпускает два вида продукции х₁ и х₂ (в тоннах). Затраты (в тысячах рублей), связанные с производством продукции, выражаются целевой функцией

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

Таблица 7.3

Варианты заданий

№ варианта

Задание 2. Решить графическим методом следующие задачи нелинейного программирования:

при

10.

при

11.

при

12.

при

13.

при

14.

при

15.

при

Задание 3. Оптимизация целевой функции градиентным методом с постоянным и оптимальным шагом.

1. Ознакомиться с оптимизацией целевой функции методом градиентного спуска.

2. В соответствии со своим вариантом задания найти оптимум целевой функции с заданной начальной точкой:

а) с постоянным шагом, например, h=0,5 и =0,2;

б) с оптимальным шагом методом наискорейшего спуска.

3. Составить расчетные таблицы.

4. Построить траекторию поиска экстремума.

Варианты заданий

10.

11.

12.

13.

14.

15.

16.

17.

18.

19.

20.

21.

22.

23.

24.

25.

26.

27.

28.

29.

30.

Задание 4. Модификация метода скорейшего спуска на ЭВМ

Найти минимальное значение функции F методом скорейшего спуска на ЭВМ (ППП BTN/GRAD.EXE) . Задать начальные координаты точки, например (1,1,1,1), =0,01, =0,1.

Варианты заданий

1. ;

2. ;

3. ;

4. ;

5. ;

6. ;

7. + 2;

8. ;

9. ;

10. ;

11. ;

12. ;

13. ;

14. ;

15. ;

16. ;

17. ;

18. ;

19. ;

20. ;

21. ;

22. ;

23. ;

24. ;

25. ;

26. ;

27. ;

28. ;

29. ;

30. .

Задание 5.

Предприятие выпускает изделия А и В, при изготовлении которых используется сырье вида I и II. Известны запасы сырья а_i₀(i=1,2 ), нормы его расхода а_ij (j=1,2) на единицу изделия, оптовые цены р_j на изделия и их плановая себестоимость .Как только объем выпускаемой продукции перестает соответствовать оптимальным размерам предприятия, дальнейшее увеличение выпуска Х_j ведет к повышению себестоимости продукции, и в этих условиях фактическая себестоимость с_j в первом приближении описывается функцией , где – некоторая постоянная величина. Составить план выпуска изделий, обеспечивающий предприятию получение максимальной прибыли.

1. В соответствии со своим вариантом задания найти оптимум целевой функции с заданной начальной точкой.

2. Построить траекторию поиска экстремума.

Необходимые числовые данные приведены в таблице 7.4.

Таблица 7.4

Варианты заданий

№ варианта

а₁₀

а₂₀

а₁₁

а₁₂

а₂₁

а₂₂

р₁

р₂

0,2 0,1 0,2 0,1 0,1 0,3 0,2 0,2 0,1 0,1 0,2 0,2 0,1 0,1 0,2 0,3 0,3 0,1 0,2 0,2 0,3 0,2 0,2 0,2 0,2 0,3 0,2 0,1 0,1 0,2

(2;3) (3;1) (4;1) (2;1) (2;2) (3;2) (3;0) (2;1) (2;1) (3;2) (1;3) (1;4) (2;1) (1;2) (3;1) (2;3) (4;2) (2;1) (4;1) (3;2) (2;4) (4;1) (2;1) (1;2) (2;4) (2;2) (4;1) (2;1) (3;1) (2;3)

Рекомендуемая литература

1.Акулич, И. Л. Математическое программирование в примерах и задачах. – М.: Высшая школа, 1986. – 319 с.

2.Берюхова, Т. Н., Кучумов, Р. Я. Банк производственных задач в расчетах на ЭВМ: учебное пособие. – Тюмень: ТюмИИ, 1992. - 124 с.

3.Берюхова, Т. Н., Бабушкина, Н. В. Математические методы и модели в деятельности дорожно-строительного управления//Математические методы и модели в управлении, экономике и социологии: сборник научных трудов. – Тюмень: ТюмГНГУ, 2006. – С. 32-37.

4.Берюхова, Т. Н., Осипенко, А. М. Моделирование оптимальных автобусных маршрутов г. Тюмени// Математические методы и модели в управлении, экономике и социологии: материалы Всероссийской научно-практической конференции. – Тюмень: ТюмГНГУ, 2008. – С. 99-105.

5.Горчаков, А. А., Орлова, И. А. Компьютерные экономико-математические модели. – М.: Компьютер, ЮНИТИ, 1995.

6.Дрогобыцкий, И.Н. Экономико-математическое моделирование. - М: изд. «ЭКЗАМЕН», 2006. - 798 с.

7.Давыдов, Э. Г. Исследование операций. – М.: Высшая школа, 1990.-383 с.

8.Замков, О. О., Толстопятенко, А. В., Черемных, Ю. Н. Математические методы в экономике. – М.: изд. «ДИС», 1997.- 368 с.

9.Исследование операций в экономике: учебное пособие для вузов/ Н. Ш. Кремер, Б. А. Путко, И. М. Тришин и др.; под ред. Н. Ш. Кремера. - М.: Банки и биржи, ЮНИТИ, 1999. – 407 с.

10. Кузнецов, Ю. Н. Высшая математика. Математическое программирование. – Минск: Высшая школа, 1997.

11. Калихман, И. Л. Сборник задач по математическому программированию. – М.: Высшая школа, 1975. – 270 с.

12. Карасев, А. И., Кремер, Н. Ш., Савельева, Т. И. – Математические методы и модели в планировании. – М.: Экономика, 1987.

13. Карданская, Н. Л. Принятие управленческого решения: учебник для вузов. – М.: ЮНИТИ, 1999. – 407 с.

14. Квитковская, В. П., Берюхова, Т. Н. Модель определения рациональных объемов подготовки запасов нефти//Математические методы и модели в экономике и управлении: сборник научных трудов – Тюмень: ТюмГНГУ, 2004. – С. 62-66.

15. Кузнецов, Ю. Н., Кузубов, В. И., Волощенко, А. Б. Математическое программирование. – М.: Высшая школа, 1986.

16. Кузнецов, Б. Т. Математические методы и модели исследования операций: учебное пособие для вузов.- М.: ЮНИТИ-ДАНА, 2005.-390 с.

17. Курицкий, Б. Я. Поиск оптимальных решений средствами EXCEL в примерах. – СПб: ВН, 1997. - 384 с.

18. Мальцева, Т. Л., Берюхова, Т. Н. Разработка оптимального решения о выборе технологического оборудования// Математические методы и модели в экономике и управлении: сборник научных трудов – Тюмень: ТюмГНГУ, 2004. – С. 110-114.

19. Экономико-математические методы и прикладные модели: учеб. пособие для вузов/ В. В. Федосеев, А. Н. Гармаш, Д. М. Дайитбегов и др.; под ред. В. В. Федосеева.- М.: ЮНИТИ, 2000. - 391 с.

20. Таха, Хэмди А. Введение в исследование операций: в 2 кн. - М.: Мир, 1985.

21. Математическое программирование / под ред. Н. Ш. Кремера. - М.: Финстатинформ, 1995.

22. Сборник задач и упражнений по высшей математике: Математическое программирование/ А. В. Кузнецов, В. А. Сакович, Н. И. Холод и др.; под общей ред. А. В. Кузнецова. – Мн.: Выш. шк., 1995. – 382 с.

23. Иванилов, Ю. П., Лотов, А. В. Математические модели в экономике. - М.: Наука, 1979. - 304 с.

24. Бережная, Е. В., Бережной, В. И. Математические методы моделирования экономических систем: учебное пособие. – М.: Финансы и статистика, 2005. - 432 с.

25. Волошин, Г. Я. Методы оптимизации в экономике: учебное пособие. – М.: Дело и сервис, 2004. - 320 с.

26. Миксюк, С. Ф., Комкова, В. М. Экономико-математические методы и модели: учебное пособие. - Минск: БГЭУ, 2006. - 219 с.

27. Орехов, Н.А. Математические методы и модели в экономике. - М.: ЮНИТИ-ДАНА, 2004. - 303 с.

28. Применение исследования операций в экономике/ Т. Д. Березнева (СССР), Христиан Гроссман (ГДР), Дюк Вернер (ГДР) и др.; пер. с венг. М.: Экономика, 1977. - 323 с.

29. Просветов, Г. И. Математические модели в экономике. – М.: РДЛ, 2006. - 160 с.

30. Фомин, Г. П. Математические методы и модели в коммерческой деятельности. - М.: Финансы и статистика, 2005. - 616 с.

31. Хачатрян, С. Р., Пинегина, М. В., Буянов, В. П. Методы и модели решения экономических задач: учебное пособие. - М.: Экзамен, 2005. - 384 с.

32. Хедли, Дж. Нелинейное и динамическое программирование. – М.: Мир, 1967.

33. Шапкин, А. С. Математические методы и модели исследования операций. - М.: Дашков и К., 2004. - 396 с.

34. Шелобаев, С. И. Математические методы и модели в экономике, финансах, бизнесе: учебное пособие для вузов. – М.: ЮНИТИ-ДАНА, 2001. - 367 с.

СОДЕРЖАНИЕ