- •Учебно-методические материалы к изучению дисциплины «Методы оптимизации» (конспект лекций)
- •1. Классификация задач оптимизации
- •2. Классификация математических методов и моделей в экономике
- •3. Линейное программирование
- •3.1. Постановка задачи линейного программирования
- •3.2. Экономическая интерпретация задач линейного программирования
- •3.3. Требования совместности условий
- •3.4. Графический метод решения задач линейного программирования
- •3.5. Симплекс-метод
- •3.6. Модифицированный симплекс-метод
- •3.7. Построение опорных планов
- •3.8. Условия оптимальности
- •3.9. Метод искусственного базиса
- •3.10. Транспортная задача
- •3.11. Двойственные задачи линейного программирования
- •3.12. Устойчивость оптимизационного решения
- •4. Нелинейное программирование
- •4.1. Классификация и общая постановка задач нелинейного программирования
- •4.2. Метод множителей Лагранжа
- •4.3. Возможные обобщения метода множителей. Седловая точка функции Лагранжа
- •4.4. Оптимальные решения при ограничениях-неравенствах. Теорема Куна - Таккера
- •4.5. Выпуклое программирование. Задача выпуклого программирования
- •4.6. Квадратичное программирование
- •4.7. Градиентные методы
- •5. Оптимизация на графах
- •5.1. Основные понятия теории графов
- •5.2. Связность
- •5.3. Подграфы
- •5.4. Матрица графов
- •5.5. Потоки в сетях
- •5.6. Задача о максимальном потоке сети
- •5.7. Задача о кратчайшем пути
- •5.8. Задача коммивояжера
- •5.9. Оптимизация сетевого графика
- •5.10. Методы оптимизации производственной программы
- •6. Динамическое программирование
- •6.1. Общая постановка задачи динамического программирования
- •6.2. Принцип оптимальности. Уравнение Беллмана
- •6.3. Простейшие экономические задачи, решаемые методом динамического программирования
- •7. Математические модели потребительского поведения и спроса
- •7.1. Отношение предпочтения и функция полезности
- •7.2. Решение задачи об оптимальном выборе потребителя
- •7.3. Функции спроса. Коэффициент эластичности
4.7. Градиентные методы
Используя градиентные методы, можно найти, решение любой задачи нелинейного программирования. Применение этих методов в общем случае позволяет найти точку локального экстремума. Поэтому более целесообразно использовать их для нахождения решения задач выпуклого программирования. Процесс нахождения решения задачи с помощью градиентных методов состоит в том, что начиная с некоторой точки осуществляется последовательный переход к некоторым другим точкам до тех пор, пока не будет найдено приемлемое решение исходной задачи. Градиентные методы могут быть подразделены на две группы.
К первой группе относятся методы, при использовании которых исследуемые точки не выходят за пределы области допустимых решений задачи. В данном случае наиболее распространенным является метод Франка - Вульфа. Ко второй - методы, при использовании которых исследуемые точки могут как принадлежать, так и не принадлежать области допустимых решений. Однако в результате реализации итерационного процесса находится точка области допустимых решений, определяющая приемлемое решение. Наиболее часто используются метод штрафных функций и метод Эрроу - Гурвица. При нахождении решения задачи градиентными методами итерационный процесс продолжается до тех пор, пока градиент функции в очередной точке не станет равным нулю или же пока не выполнится неравенство
, где (точность полученного решения).
Метод Франка - Вульфа. Пусть требуется найти максимальное значение вогнутой функции
(9)
при условиях
(10)
(11)
Ограничения содержат только линейные неравенства. Эта особенность является основой для замены в окрестности исследуемой точки нелинейной целевой функции линейной, в результате чего решение исходной задачи сводится к последовательному решению задач линейного программирования.
Процесс нахождения решения начинают с определения точки, принадлежащей области допустимых решений. Пусть это точка . Вычисляют в этой точке градиент функции (9):
,
строят линейную функцию
. (12)
Находят максимум функции (12) при ограничениях (10) и (11). Пусть решение данной задачи определяется точкой . За новое допустимое решение исходной задачи принимают координаты точки , которые находят по формулам
,
где - некоторое число, называемое шагом вычислений . За принимают наименьший корень уравнения или выбирают произвольно, если он не принадлежит интервалу (0; 1).
Метод штрафных функций. Рассмотрим задачу нелинейного программирования (6) -(8), где - выпуклые функции.
Вместо того, чтобы решать эту задачу, находят максимум функции
,
где определяется системой ограничений и называется штрафной функцией. Последнюю можно построить различными способами. Наиболее часто она имеет вид
,
где
а - некоторые постоянные числа, представляющие собой весовые коэффициенты.
Используя штрафную функцию, последовательно переходят от одной точки к другой до тех пор, пока не получат приемлемое решение. Координаты последующей точки находят по формуле
,
где - шаг вычислений .
Итерационный процесс обычно начинают при сравнительно малых значениях и, продолжая его, эти значения постепенно увеличивают.
Метод Эрроу - Гурвица. При нахождении решения задачи нелинейного программирования методом штрафных функций значения , выбирают произвольно, что приводит к значительным колебаниям удаленности определяемых точек от области допустимых решений. Этот недостаток устраняется при решении задачи методом Эрроу - Гурвица, согласно которому на очередном шаге числа находят по формуле
В качестве начальных значений берут произвольные неотрицательные числа.