Методы оптимизации. Алгоритмы. Линейное программирование

Определение 5.3. Ограничение задачи (5.3) называется регулярным, если существует допустимое решение задачи , при котором .

Определение 5.4. Если все ограничения задачи регулярные, то говорят о регулярности самой задачи.

Вторая теорема Куна -Таккера. Для любого оптимального решения x^* регулярной задачи выпуклого программирования (5.3) существует вектор множителей Лагранжа y^* такой, что (x^*, y^*) - седловая точка функции Лагранжа.

Условия седловой точки для гладких функций (условия Куна-Таккера)

Теоремы Куна-Таккера дают метод нахождения оптимального решения задачи (5.3) через поиск седловых точек функции Лагранжа. Поэтому особый интерес вызывают условия, определяющие седловые точки. Получим эти условия для непрерывно дифференцируемых функций.

Предположим, что все функции в задаче (5.3) выпуклые и непрерывно дифференцируемые. Тогда можно сформулировать необходимые и достаточные условия седловой точки функции Лагранжа, называемые условиями Куна-Таккера.

Теорема 5.2. Точка является седловой точкой функции Лагранжа задачи выпуклого программирования тогда и только тогда, когда в ней выполняются условия Куна-Таккера:

, , (5.6)

, .

Доказательство.

Точка седловая и в ней по переменной x достигается минимум в области и максимум по переменной y в области . Следовательно, если , то частная производная в точке либо равна 0, либо положительна. Если , то частная производная в точке равна 0. Это можно записать, используя условие дополняющей нежесткости

, для .

В векторной форме этот результат выглядит так

, .

Аналогично выводится группа условий для переменной y.

В условиях Куна-Таккера , а функция , являясь неотрицательной линейной комбинацией выпуклых функций, - выпуклая функция. Из теоремы об эквивалентных условиях выпуклости из выпуклости функции следует

.

Используя равенство , и неравенство , получаем для всех . И так, доказано неравенство для всех .

Вспомним вид функции Лагранжа:

.

Из условий Куна-Таккера

, .

Следовательно,

для всех .

Или для всех . Доказано, что точка - седловая.

В таблице 5.1 приведены условия Куна-Таккера для общей задачи выпуклого программирования:

(5.7)

где

Таблица 5.1 - Условия Куна-Таккера к задаче (5.7)

Если исходная задача является задачей выпуклого программирования, функции в задаче непрерывно дифференцируемы, а ограничения регулярные, то можно любую данную точку проверить на оптимальность.

Алгоритм проверки точки на оптимальность

1. Преобразовать задачу к виду (5.7), выписав все функции .

2. Проверить выпуклость всех функций, входящих в ограничения-неравенства, и линейность, входящих в ограничения-равенства. Доказать регулярность каждого из нелинейных ограничений.

3. Выписать условия Куна-Таккера, подставив в них координаты точки .

4. Если полученная система имеет решение , то - седловая точка функции Лагранжа, а - оптимальное решение задачи (5.7) по 1-й теореме Куна-Таккера. В противном случае по второй теореме Куна-Таккера не является оптимальным решением. Проверка завершается.

6. МЕТОД ВОЗМОЖНЫХ НАПРАВЛЕНИЙ

Это - численный метод решения регулярной задачи выпуклого программирования. Был предложен Г. Зойтендейком.

Рассмотрим задачу выпуклого программирования в виде

(6.1)

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

Общая схема метода возможных направлений

1. Преобразовать задачу к виду (6.1), выписав все функции .

2. Проверить выпуклость всех функций. Доказать регулярность каждого из нелинейных ограничений.

3. Выбрать произвольно точку , удовлетворяющую ограничениям задачи.

Положить k=0.

4. Построить в точке конус возможных направлений спуска .

5. Если конус - пустое множество, то делаем вывод о том, что точка является оптимальным решением задачи (6.1), и алгоритм завершает работу.

6. Выбрать в точке из конуса возможных направлений спуска направление .

7. Выбрать в точке при выбранном направлении длину шага .

8. Перейти в новую точку .

9. Присвоить k=k+1. Перейти к пункту 4.

Построение конуса возможных направлений спуска в точке .

1. Найти номера тех ограничений, которые в точке выполняются как строгие равенства:

.

Это множество номеров можно разделить на два непересекающихся подмножества: и -линейная функция} и

и -нелинейная функция}.

В построении конуса будут участвовать только ограничения с этими номерами.

2. Конус возможных направлений спуска задается системой неравенств

Выписать систему неравенств, задающую конус в точке .

Выбор направления из конуса возможных направлений спуска

1. Если антиградиент целевой функции принадлежит полученному конусу, то полагаем . Переходим на пункт 4.

2. Если в конусе существует направление, ближайшее к антиградиенту целевой функции, то выбираем его. Переходим на пункт 4.

3. Выбираем любое направление из конуса.

4. Направление выбрано.

Выбор длины шага

Длину шага выбираем после выбора направления путем решения задачи

. (6.2)

В задаче (6.2) минимизация проводится по переменной б .

ЛИТЕРАТУРА

1. Сухарев А.Г., Тимохов А.В., Федоров В.В. Курс методов оптимизации.2-е издание. М.: ФИЗМАТЛИТ, 2005.

2. Вентцель Е.С. Исследование операций. Задачи, принципы, методология. М.: Высш. шк.,2011.

3. Таха Х. Введение в исследование операций.7-е издание. М.: Вильямс,2007.

4. Афанасьев М.Ю., Суворов Б.П. Исследование операций в экономике: модели, задачи, решения: Учеб. Пособие. М.: ИНФА-М, 2013

5. Моисеев Н.Н., Иванилов Ю.П., Столярова Е.М.. Методы оптимизации. М.: Наука, 1978.

6. Васильев Ф.П. Численные методы решения экстремальных задач: Учеб. пособие. М.: Наука, 1981.

7. Зинченко А.Б., Сантылова Л.И. Индивидуальные задания по курсу “Методы оптимизации” (часть 1): Метод.указания для студентов вечернего отделения мех.-мат.фак.-Ростов н/Д: РГУ,2003.

8. Зинченко А.Б., Сантылова Л.И. Индивидуальные задания по курсу “Методы оптимизации” (часть 2): Метод.указания для студентов мех.-мат.фак. Ростов н/Д: РГУ,2003.

9. Зинченко А.Б., Сантылова Л.И. Индивидуальные задания по курсу “Методы оптимизации” (части 3): Метод.указания для студентов мех.-мат.фак. Ростов н/Д: РГУ,2006.

10. Землянухина Л.Н., Сантылова Л.И. Индивидуальные задания по курсу “Методы оптимизации” (части 4): Метод.указания для студентов мех.-мат.фак. Ростов н/Д: РГУ,2006.

11. Землянухина Л.Н., Зинченко А.Б., Сантылова Л.И., Макмак С.М. Линейное программирование и смежные вопросы (часть 1): Метод.указания для студентов мех.-мат.фак. по курсу “Методы оптимизации”. Ростов н/Д: РГУ, 2008.

12. Л.Н. Землянухина, А.Б. Зинченко, Л.И. Сантылова, Макмак С.М. Линейное программирование и смежные вопросы (часть 2): Метод.указания для студентов мех.-мат.фак. по курсу “Методы оптимизации”. Ростов н/Д: РГУ, 2008.

13. Л.Н. Землянухина, А.Б. Зинченко, Л.И. Сантылова. Линейное программирование и смежные вопросы (часть 3): Метод.указания для студентов мех.-мат.фак. по курсу “Методы оптимизации”. Ростов н/Д: РГУ, 1998.

14. Сантылова Л.И. Вариационное исчисление и методы оптимизации. Руководство по решению задач (часть 1): Метод.указания. Ростов н/Д: РГУ, 2006.

Дополнительная литература

15. Волков И.К. и др. Введение в исследование операций. М.:Изд-во МГТУ им. Баумана, 2000.

16. Вагнер Г. Основы исследования операций. Т.1-3.- М.:Мир,1973.

17. Давыдов Э.Г.. Исследование операций. М. 1990.

18. Реклейтис Г. и др. Оптимизация в технике. М. Мир, 1986.

19. Химмельблау Д. Прикладное нелинейное программирование. М.: Мир, 1975.

Размещено на Allbest.ru