p align="left">Если предположить, что - е ограничение является неактивным (т.е. С другой стороны, если -е ограничение активное (т. е. ), то соответствующая неявная цена не обязательно равна нулю, однако , так как . Таким образом, для всех значений . Для того чтобы определить знак (неявной цены, ассоциирован-ной с ограничением ), следует увеличить правую часть ограничения от 0 до 1. Ясно, что при этом область допустимых решений сужается, поскольку любое решение, удовлетворяющее ограничению , автоматически удовлетворяет неравенству . Следовательно, размеры допустимой области уменьша-ются, и минимальное значение улучшить невозможно (так как вообще оно может только возрастать). Другими словами, неявная цена , ассоциированная с -м ограничением, должна быть неотри-цательной, что соответствует условиям Куна--Таккера. 3.3. Теоремы Куна--ТаккераВ предыдущем разделе построены условия Куна--Таккера для задач условной оптимизации. С помощью метода множителей Лагранжа получено интуитивное представление о том, что условия Куна -- Танкера тесно связаны с необходимыми условиями опти-мальности. В данном разделе рассматриваются строгие формули-ровки необходимых и достаточных условий оптимальности решения задачи нелинейного программирования. Теорема 1. Необходимость условий Куна--Таккера Рассмотрим задачу нелинейного программирования (0)-(2). Пусть - дифференцируемые функции, а х* -- допус-тимое решение данной задачи. Положим . Далее пусть линейно неза-висимы. Если х* -- оптимальное решение задачи нелинейного про-граммирования, то существует такая пара векторов , что является решением задачи Куна--Таккера (3)--(7). Условие, согласно которому должны быть линейно независимыми, известно как ус-ловие линейной независимости и по существу представляет собой некоторое условие регулярности допустимой области, которое поч-ти всегда выполняется для встречающихся на практике задач опти-мизации. Однако вообще проверка выполнения условия линейной независимости весьма затруднительна, так как требуется, чтобы оптимальное решение задачи было известно заранее. Вместе с тем условие линейной независимости всегда выполняется для задач нелинейного программирования, обладающих следующими свой-ствами. 1. Все ограничения в виде равенств и неравенств содержат линейные функции. 2. Все ограничения в виде неравенств содержат вогнутые функ-ции, все ограничения-равенства -- линейные функции, а также существует, по крайней мере, одна допустимая точка х, которая рас-положена во внутренней части области, определяемой ограниче-ниями-неравенствами. Другими словами, существует такая точка х, что Если условие линейной независимости в точке оптимума не вы-полняется, то задача Куна--Таккера может не иметь решения. Пример 4 Минимизировать при ограничениях Решение. На рис.1 изображена область допустимых ре-шений сформулированной выше нелинейной задачи. Ясно, что оптимальное решение этой задачи есть . Пока-жем, что условие линейной независимости не выполняется в точке оптимума. Рис.1 Допустимая область в задаче 4 Так как Легко видеть, что векторы линейно зависимы, т. е. условие линейной независимости в точке не выпол-няется. Запишем условия Куна--Таккера и проверим, выполняются ли они в точке (1, 0). Условия (3), (6) и (7) принимают сле-дующий вид; (11) (12) (13) (14) (15) (16) При из уравнения (11) следует, что , тогда как уравнение (14) дает , Следовательно, точка оптимума не является точкой Куна -- Таккера. Заметим, что нарушение условия линейной независимости не обязательно означает, что точка Куна--Таккера не существует. Для того чтобы подтвердить это, заменим целевую функцию из этого примера функцией. При этом оптимум по-прежнему достигается в точке (1,0), в которой условие линейной независимости не выполняется. Условия Куна--Так-кера (12) - (16) остаются неизменными, а уравнение (11) принимает вид Нетрудно проверить, что точка является точкой Куна--Таккера, т. е. удовлетворяет условиям Куна--Таккера. Теорема о необходимости условий Куна--Таккера позволяет идентифицировать неоптимальные точки. Другими словами, тео-рему 1 можно использовать для доказательства того, что задан-ная допустимая точка, удовлетворяющая условию линейной неза-висимости, не является оптимальной, если она не удовлетворяет условиям Куна--Таккера. С другой стороны, если в этой точке условия Куна--Таккера выполняются, то нет гарантии, что най-дено оптимальное решение нелинейной задачи. В качестве примера рассмотрим следующую задачу нелинейного программирования. Следующая теорема устанавливает условия, при выполнении которых точка Куна--Таккера автоматически соответствует оптимальному решению задачи нелинейного программирования. Теорема.2 Достаточность условий Куна--Таккера Рассмотрим задачу нелинейного программирования (0) -- (2). Пусть целевая функция выпуклая, все ограничения в виде неравенств содержат вогнутые функции , а ограничения в виде равенств содержат линейные функции . Тогда если существует решение , удовлет-воряющее условиям Куна--Таккера (3) -- (7), то х* -- оп-тимальное решение задачи нелинейного программирования. Если условия теоремы 2 выполняются, то нахождение точки Куна--Таккера обеспечивает получение оптимального решения задачи нелинейного программирования. Теорему 2 можно также использовать для доказательства оптимальности данного решения задачи нелинейного программирования. В качестве иллюстрации опять рассмотрим пример: Минимизировать при ограничениях С помощью теоремы 2 докажем, что решение является оптимальным. Имеем Так как матрица положительно полуопределена при всех х, функция оказывается выпуклой. Первое ограничение в виде неравенства содержит линейную функцию , которая одновре-менно является как выпуклой, так и вогнутой. Для того чтобы показать, что функция является вогнутой, вычислим Поскольку матрица отрицательно определена, функция является вогнутой. Функция входит в линейное ограни-чение в вяде равенства. Следовательно, все условия теоремы 2 выполнены; если мы покажем, что - точка Куна-Так-кера, то действительно установим оптимальность решения . Условия Куна-Таккера для примера 2 имеют вид (22) (23) (24) (25) , (26) , (27) (28) (29) Точка удовлетворяет ограничениям (24) -- (26) и, следовательно, является допустимой. Уравнения (22) и (23) принимают следующий вид: Положив ,получим и. Таким образом, реше-ние х*=(1, 5), удовлетворяет условиям Куна--Таккера. Поскольку условия теоремы 2 выполнены, то оптимальное решение задачи из примера 3. Заметим, что существуют также и другие значения и , которые удов-летворяют системе (22) -(29). Замечания 1.Для встречающихся на практике задач условие линейной независимости, как правило, выполняется. Если в задаче все функции дифференцируемы, то точку Куна--Таккера следует рассматривать как возможную точку оптимума. Таким образом, многие из методов нелинейного программирования сходятся к точке Куна--Таккера. (Здесь уместно провести аналогию со случаем безусловной оптимизации, когда соответствующие алгоритмы позволяют определить стационарную точку.) 2. Если условия теоремы 2 выполнены, точка Куна--Таккера в то же время оказывается точкой глобального минимума. К сожа-лению, проверка достаточных условий весьма затруднительна, и, кроме того, прикладные задачи часто не обладают требуемыми свойствами. Следует отметить, что наличие хотя бы одного нелиней-ного ограничения в виде равенства приводит к нарушению предпо-ложений теоремы 2. 3.Достаточные условия, установленные теоремой 2, можно обобщить на случай задач с невыпуклыми функциями, входящими в ограничения в виде неравенств, невыпуклыми целевыми функ-циями и нелинейными ограничениями-равенствами. При этом ис-пользуются такие обобщения выпуклых функций, как квазивыпук-лые и псевдовыпуклые функции. 4. Функции нескольких переменныхОграниченные возможности симплексного метода, заключенные в задачах со сложными видами ограничений и произвольным видом целевой функции, привели к широкому использованию итеративных методов поиска оптимального решения. Сначала рассмотрим вопрос анализа «в статике» с использова-нием положений линейной алгебры и дифференциального исчисле-ния, а также условия, которые (в достаточно общих возможных ситуациях) позволяют идентифицировать точки опти-мума. Такие условия используются для проверки выбранных точек и дают возможность выяснить, являются ли эти точки точками ми-нимума или максимума. При этом задача вы-бора указанных точек остается вне рамок проводимого анализа; основное внимание уделяется решению вопроса о том, соответствуют ли исследуемые точки решениям многомерной задачи безусловной оптимизации, в которой требуется минимизировать f(x) x при отсутствии ограничений на x, где x -- вектор управляемых переменных размерности n, f -- скалярная целевая функция. Обыч-но предполагается, что xi (для всех значений i=1, 2, …, n) могут принимать любые значения, хотя в ряде практических при-ложений область значений x выбирается в виде дискретного мно-жества. Кроме того, часто оказывается удобным предполагать, что функция f и ее производные существуют и непрерывны всюду, хотя известно, что оптимумы могут достигаться в точках разрыва f или ее градиента Градиентом функции f(х) называют вектор, величина которого определяет скорость изменения функции f(x), а направление совпадает с направлением наибольшего возрастания этой функции. Следует помнить, что функция f может принимать минимальное значение в точке x, в которой f или претерпевают разрыв. Кроме того, в этой точке может не существовать. Для того чтобы по-строить систему конструктивных критериев оптимальности, необ-ходимо (по крайней мере на первой стадии исследования) исключить из рассмотрения подобные ситуации, которые весьма усложня-ют анализ. 4.1. Методы прямого поискаНиже рассматривается вопрос анализа «в динамике» для функций нескольких переменных, т. е. исследуются методы и алгоритмы, позволяющие на итерацион-ной основе получать оценки х*-- вектора управляемых переменных, которому соответствует минимальное значение функции f(x). Ука-занные методы применимы также к задачам максимизации, в кото-рых целевую функцию следует заменить на -f(х). Методы, ориен-тированные на решение задач безусловной оптимизации, можно разделить на три широких класса в соответствии с типом используе-мой при реализации того или иного метода информации. 1. Методы прямого поиска, основанные на вычислении только значений целевой функции. 2. Градиентные методы, в которых используются точные значе-ния первых производных f(x). 3. Методы второго порядка, в которых наряду с первыми про-изводными используются также вторые производные функции f(x). Ниже рассматриваются методы, относящиеся к каждому из пере-численных классов, поскольку ни один метод или класс методов не отличается высокой эффективностью при решении оптимизационных задач различных типов. В частности, возможны случаи, когда про-исходит переполнение памяти ЭВМ; в других ситуациях вычисление значений целевой функции требует чрезмерных затрат времени; в некоторых задачах требуется получить решение с очень высокой степенью точности. В ряде приложений либо невозможно, либо весьма затруднительно найти аналитические выражения для произ-водных целевой функции. Поэтому если предполагается использо-вать градиентные методы, следует применить процедуру разностной аппроксимации производных. В свою очередь это приводит к необ-ходимости экспериментального определения длины шагов, позво-ляющего установить надлежащее соответствие между ошибкой округления и ошибкой аппроксимации. Таким образом, инженер вынужден приспосабливать применяемый метод к конкретным ха-рактеристикам решаемой задачи. Методы решения задач безусловной оптимизации отличаются относительно высоким уровнем развития по сравнению с другими методами нелинейного программирования. Ниже речь идет о методах прямого поиска, для реализации которых требуются только значения целевой функции; в следующем разделе рассматриваются градиентные методы и методы второго порядка. Здесь предполагается, что f(x) непрерывна, а может как существовать, так и не существовать, поскольку соответствующие числовые значения не используются. Однако следует отметить, что методы прямого поиска можно приме-нять для решения задач, в которых существует, и они часто используются в тех случаях, когда представляет собой сложную векторную функцию управляемых переменных. Наконец, в этом и последующих разделах предполагается, что функция f(х) унимо-дальна в рассматриваемой области. Если же изучаемые методы применяются для анализа мультимодальных функций, то приходит-ся ограничиваться идентификацией локальных минимумов. Многомерные методы, реализующие процедуру поиска оптиму-ма на основе вычисления значений функции, с общих позиций можно разделить на эвристические и теоретические. Эвристические методы, как это следует из названия, реализуют процедуры поиска с помощью интуитивных геометрических представлений и обеспечи-вают получение частных эмпирических результатов. С другой сто-роны, теоретические методы основаны на фундаментальных математических теоремах и обладают такими операционными свойствами, как сходимость (по крайней мере при выполнении некоторых опре-деленных условий). Ниже подробно рассматриваются три метода прямого поиска:
Страницы: 1, 2, 3
|