Нелинейное программирование

Для того чтобы определить знак (неявной цены, ассоциированной с ограничением ), следует увеличить правую часть ограничения от 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. Прикладное применение нелинейной оптимизации

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

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

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

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

ІІІ. Задачи нелинейного программирования общего вида, где достигается локальный оптимум, среди которых ищут глобальный оптимум.

Для примера рассмотрим некоторые задачи относящиеся к управлению и принятию решений, которые можно решить, используя теорию и методы нелинейного программирования

Задача управления запасами

Для выполнения компенсаторной функции и регулирования цен на продовольственные продукты в регионе муниципальные власти создают запасы для удовлетворения будущего спроса. Основным вопросом при этом зачастую становится определение того, как часто и в каком объеме создавать эти запасы.

Слишком частые пополнения запасов приводят к нерациональным потерям времени и средств, связанных с их непрерывным пополнением. С другой стороны, очевидно, что пополнение запасов через длительные промежутки времени приводит к образованию чрезмерно больших запасов и значительно повышает стоимость хранения запасов, в некоторых случаях (продукты с ограниченным сроком хранения) это вообще невозможно Определение оптимального объема запасов в этих условиях представляет собой классическую задачу оптимизации.

В рамках рассматриваемой задачи спрос предполагается постоянным и равным λ единиц товара в год. Чересчур частое пополнение запасов нецелесообразно, так как стоимость выполнения одного заказа составляет K руб. независимо от его размера. Первоначальная стоимость единицы товара равна c руб. Хранение излишних запасов также нецелесообразно, поскольку стоимость хранения единицы товара отлична от нуля и составляет h руб. в год. Для того чтобы упростить задачу, предположим, что спрос удовлетворяется немедленно (т.е. задолженные запросы отсутствуют), а пополнение осуществляется сразу же, как только запасы иссякают.

Рисунок 2 - Циклы управления запасами.

Рисунок 2 иллюстрирует изменение объема запасов с течением времени. В точке A объем запасов равен B; затем объем запасов начинает уменьшаться со скоростью λ единиц товара в единицу времени и достигает нулевого значения в точке C. В это время поступает новая партия товара, и объем запасов восстанавливается.

Треугольник ABC представляет один цикл управления запасами, который повторяется во времени. Задача заключается в том, чтобы определить оптимальный размер заказа B и продолжительность интервала времени между заказами C – A. Обозначим соответствующие переменные через Q и T.

Поскольку T есть величина промежутка времени, в течение которого при скорости λ истощается запас Q, имеем T=Q/λ. Таким образом, задача сводится к нахождению оптимального значения Q. Заметим, что когда Q мало, переменная T также имеет малое значение. При этом частота заказов велика, что обуславливается большие затраты на выполнение заказов и относительно малые издержки хранения запасов. С другой стороны, наличие большого объема запасов (Q велико) приводит к увеличению затрат на хранение запасов и одновременно к снижению издержек, связанных с выполнением заказов на товары. Одна из основных задач управления запасами состоит в определении оптимального значения Q, которому соответствует минимум суммы полных годовых затрат.

Получим аналитическое выражение для функции полных годовых затрат (затраты/цикл × количество циклов/год).

 

.

Примечание. Затраты на хранение запасов в течение цикла равны затратам на хранение Q/2 единиц товара в течение интервала времени T.

Таким образом, подлежащая минимизации функция полных затрат есть

,

,

.

отсюда следует, что – выпуклая функция и если существует положительное значение Q*, такое, что , то Q* минимизирует .

Решив уравнение , получим

.

Таким образом, оптимальный размер заказа равен

.

При этом T* – интервал времени между заказами . Величина Q* известна в теории управления запасами как наиболее экономичный размер заказа.

Часто для решения задач нелинейного программирования применяются средства автоматизации, это могут быть как специализированные программные комплексы, так и традиционные представители ПО, например – Excel.

В Excel для поиска оптимуму нелинейной задачи используется улучшенный метод сопряженных градиентов  Флетчера-Ривса итерационного типа, приспособленный известным математиком Л. Лесдоном для программы надстройки Excel Solver (Поиск решений).

Идея градиентного метода поиску экстремума функции (предложена в 1847 году Коши): выбирается начальная (стартовая) точка (начальное приближение у виде набора произвольных значений неизвестных) и вычисляется градиент (начальные производные целевой функции в диапазоне этой точки), который определяет шаг и направление движения в следующую точку для улучшения ЦФ. У следующих точках эта процедура повторяется, пока эти производные не станут нулевыми, что говорит о достижении экстремума.