<<
>>

2.2. ДВОЙСТВЕННОСТЬ В НЕЛИНЕЙНОМ ПРОГРАММИРОВАНИИ

2.2.1. Понятие седловой точки. В настоящем параграфе мы кратко остановимся на некоторых фундаментальных моментах теории нелинейного программирования. Отправной точкой для них является распространение метода Лагранжа для решения ЗНП с ограничениями в форме неравенств:

где X — некоторая область в пространстве Rn.

По аналогии с п.

2.1.2 определим для задачи (2.28) функцию Лагранжа:

? Пара векторов (х, u) называется седловой точкой функции Ф(х, и) в некоторой области X x U, если

для любых x ? X и u ? U

Неравенства (2.30) также называют неравенствами седловой точки.

В качестве примера седловой точки может быть приведена точка (0, 0) для функции Ф(х,и) = -х2 + и2, определенной на множестве R х R. В самом деле, Ф(0,0)=0, Ф(х,0)=-х2, Ф(0, и) = и2, а для любых x?R и u?R выполняются неравенства –х2 ? 0 и 0 ? и2.

На рис. 2.7 изображен график функции Ф(х,и) (гиперболический параболоид), и, как видно, в окрестности точки (0,0) он действительно по форме напоминает седло, чем и объясняется происхождение соответствующего термина.

2.2.2. Теорема Куна—Таккера. Центральное место в теории нелинейного программирования занимает теорема Куна— Таккера, которая связывает решение ЗНП с наличием седловой точки у соответствующей функции Лагранжа.

Теорема 2.3. (Достаточное условие экстремума).

Если (х, и) — седловая точка функции Лагранжа, в области x?X?D, и?0,то х является оптимальным планом задачи (2.28), причем справедливо так называемое правило дополняющей нежесткости:

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

По определению седловой точки

при всех x?X, и?0. Из второго неравенства в (2.32) следует, что

Однако (2.33) может иметь место только тогда, когда gi(x)?0 при всех i?1:m.

Действительно, если существует такое k, что gk(x)>0, то, положив иi=0 для всех i ? k и выбрав достаточно большое иk > 0, можно добиться того, что значение

окажется больше постоянного выражения

Из того, что для всех i?1:m выполняются неравенства gi(x)?0, следует, что х является допустимым планом задачи (2.28).

Если в левую часть неравенства (2.33) подставить значения ui = 0, i?1:m, то получим, что

Вместе с тем из того что, gi(x)?0 и ui ?0, следует оценка

Совместное рассмотрение последних двух неравенств приводит к правилу дополняющей нежесткости в точке х:

Тогда на основании левой части неравенства седловой точки (2.32) имеем, что для всех х?Х (в том числе и для х?D)

Но условию ЗНП для любых х?D верны неравенства gi(x)?0, что, в сочетании с условием ui ?0, позволяет записать

Значит,

Окончательно получаем, что для любых х?D справедливо соотношение f(x)?f(x), т. е. х — оптимальный план задачи (2.28). ?

Утверждение, обратное теореме (2.3), т. е. необходимое условие экстремума в ЗНП, оказывается верным только при выполнении дополнительных условий, которым должна удовлетворять задача (2.28). Важнейшим из них является так называемое условие регулярности Слейтера:

*

Говорят, что функция gi (х), задающая ограничение в задаче (2.28), удовлетворяет условию регулярности Слейтера, если существует такая точка , принадлежащая области допустимых планов D, что

т. е. является внутренней точкой относительно ограничения gi(x). Поэтому данное условие также называют условием телесности.

Вообще говоря, существуют разные варианты необходимого условия Куна—Таккера. Приведем один из них.

Теорема 2.4. (Необходимое условие наличия экстремума).

Если (D, f) является задачей выпуклого программирования с решением х, ее целевая функция f(x) и функции ограничений gi(x) — дифференцируемы, нелинейные ограничения в форме неравенств удовлетворяют условию регулярности Слейтера, то существует такой вектор и ? 0, что (х,и) — седловая точка функции Лагранжа Ф(х,и).

Мы не будем здесь приводить доказательство теоремы (2.4), которое является довольно сложным.

Заинтересованный читатель может найти его в таких источниках, как [1, 13].

Значение теоремы Куна—Таккера состоит в том, что она позволяет связать процесс решения оптимизационной задачи с поиском седловых точек функции Лагранжа, т. е., грубо говоря, с максимизацией этой функции по х и минимизацией по и.

Определим F(x) как функцию, ставящую в соответствие каждому значению х минимальное значение функции Ф(х,и) по и:

и по аналогии

Рассмотрим задачу отыскания максимума функции F(x)

и задачу минимизации G(u)

Очевидно, что

Отсюда следует, что максимум F(x) находится в допустимой области D и совпадает с максимумом целевой функции f(x) задачи (2.28):

Таким образом, задача (2.34), в определенном смысле, равносильна (2.28). Аналогичные выводы могут быть получены и для (2.35). Задачи (2.34) и (2.35) образуют двойственную пару. Как нетрудно догадаться, данное отношение является обобщением отношения двойственности для задач линейного программирования. Соответственно, при определенных условиях пара двойственных задач нелинейного программирования обладает свойствами, аналогичными свойствам двойственных линейных задач. В частности, при любых х?Х, и?0

Условие (2.36) находит широкое применение при построении оценок в итеративных методах решения оптимизационных задач. Например, если имеется возможность приблизительно решить прямую и двойственную задачи и получить последовательности приближений {х(q)} и {и(q)}, то с помощью неравенств вида

можно определить момент остановки вычислительной процедуры.

В заключение отметим, что возможен вариант вывода выражений для целевых функций и ограничений пары двойственных задач линейного программирования из общего определения отношения двойственности для нелинейных задач. Также отметим, что в процессе формирования нелинейных двойственных задач существует большая неоднозначность: их вид можно варьировать, включая в множество Х часть ограничений gi(x)?0.

КЛЮЧЕВЫЕ ПОНЯТИЯ

>

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

Условная и безусловная оптимизация. >

Прямые и непрямые методы решения оптимизационных задач. >

Стационарная точка.

>

Градиентные методы. >

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

Выпуклая и вогнутая функции. >

Матрица Гессе. >

Достаточное условие выпуклости (вогнутости). >

Задача выпуклого программирования. >

Допустимое направление. >

Прогрессивное направление. >

Седловая точка. >

Теорема Куна—Таккера. >

Условие регулярности Слейтера.

КОНТРОЛЬНЫЕ ВОПРОСЫ

2.1. При каких условиях оптимизационная задача может быть отнесена к классу нелинейных?

2.2. Приведите пример экономической модели, сводящейся к задаче нелинейного программирования.

2.3. Перечислите основные трудности, возникающие в процессе решения задачи нелинейного

программирования.

2.4. Какой смысл вкладывается в понятие «условная оптимизация»?

2.5. Для чего предназначен метод множителей Лагранжа и в чем он состоит?

2.6. Какая точка называется стационарной?

2.7. Какие принципиальные этапы входят в градиентные методы?

2.8. Для решения каких задач предназначены метод наискорейшего спуска и метод дробления шага?

2.9. Дайте определение выпуклой (вогнутой) функции.

2.10. Сформулируйте достаточное условие выпуклости (вогнутости) функции.

2.11. В чем заключена специфика задач выпуклого программирования?

2.12. Перечислите основные этапы, входящие в метод допустимых направлений.

2.13. Сформулируйте задачу, которая должна быть решена при определении шага в методе

допустимых направлений.

2.14. Исходя из каких соображений определяется допустимое прогрессивное направление?

2.15. Какое условие используется для определения оптимальности текущей точки в методе

допустимых направлений?

2.16. Дайте определение седловой точки. Приведите пример функции, имеющей седловую точку.

2.17. Сформулируйте необходимое и достаточное условия теоремы Куна—Таккера. Какое значение

они имеют для решения задач нелинейного программирования?

2.18. В чем состоит условие регулярности Слейтера? Поясните его содержание.

2.19. Какое условие получило название «правила дополняющей нежесткости»?

2.20. Приведите пример пары двойственных задач нелинейного программирования.

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

<< | >>
Источник: Конюховский П. В.. Математические методы исследования операций в экономике — СПб.: Издательство «Питер». — 208 с. — (Серия «Краткий курс»).. 2000

Еще по теме 2.2. ДВОЙСТВЕННОСТЬ В НЕЛИНЕЙНОМ ПРОГРАММИРОВАНИИ:

  1. 3.5. Нелинейное и динамическое программирование; понятие об имитационном моделировании
  2. 5.2. Предельная полезность и цены 5.2.1. Двойственные оценки в задачах математического программирования
  3. Основные этапы развития технологий программирования Программирование в кодах и ассемблер
  4. • Принцип оптимальности в планировании и управлении, общая задача оптимального программирования • Формы записи задачи линейного программирования и ее экономическая интерпретация • Математический аппарат • Геометрическая интерпретация задачи • Симплексный метод решения задачи 2.1. Принцип оптимальности в планировании и управлении, общая задача оптимального программирования
  5. 3.1. Теория двойственности в анализе оптимальных решений экономических задач
  6. 10.4 Задачи нелинейной оптимизации
  7. 5.2.3. Двойственные оценки и функции цен
  8. 10.2.6 Двойственная задача
  9. Общая характеристика эволюционных (нелинейных) динамических моделей
  10. Нелинейные косвенные налоги и налоговые льготы
  11. Эволюционные (нелинейные) динамические модели в анализе макроэкономических систем
  12. 13.2.2 Дискриминация второго типа (нелинейное ценообразование)
  13. Дискриминация второго типа (нелинейное ценообразование)
- Информатика для экономистов - Антимонопольное право - Бухгалтерский учет и контроль - Бюджетна система України - Бюджетная система России - ВЭД РФ - Господарче право України - Государственное регулирование экономики в России - Державне регулювання економіки в Україні - ЗЕД України - Инновации - Институциональная экономика - История экономических учений - Коммерческая деятельность предприятия - Контроль и ревизия в России - Контроль і ревізія в Україні - Кризисная экономика - Лизинг - Логистика - Математические методы в экономике - Микроэкономика - Мировая экономика - Муніципальне та державне управління в Україні - Налоговое право - Организация производства - Основы экономики - Политическая экономия - Региональная и национальная экономика - Страховое дело - Теория управления экономическими системами - Управление инновациями - Философия экономики - Ценообразование - Экономика и управление народным хозяйством - Экономика отрасли - Экономика предприятия - Экономика природопользования - Экономика труда - Экономическая безопасность - Экономическая география - Экономическая демография - Экономическая статистика - Экономическая теория и история - Экономический анализ -