<< Пред. стр. 6 (из 13) След. >>
Список литературы по разделу
ГЛАВА 2. НЕЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ
2.1. МЕТОДЫ РЕШЕНИЯ ЗАДАЧ НЕЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
2.1.1. Постановка задачи. Как уже упоминалось во введении, предположение о возможности описать зависимости между управляемыми переменными с помощью линейных функций далеко не всегда адекватно природе моделируемого объекта. Например, в рассмотренных в главе 1 моделях цена товара считается независимой от количества произведенного продукта, однако в повседневной жизни мы постоянно сталкиваемся с тем, что она может зависеть от объема партии товара. Аналогичные замечания могут быть сделаны и по поводу технологических ограничений: расход определенных видов сырья и ресурсов происходит не линейно, а скачкообразно (в зависимости от объема производства). Попытки учесть эти факторы приводят к формулировке более общих и сложных оптимизационных задач. Изучение методов их решения составляет предмет научной области, получившей названия нелинейного программирования.
Общая задача нелинейного программирования (ОЗНП) определяется как задача нахождения максимума (или минимума) целевой функции f(x{, х2,..., хп) на множестве D, определяемом системой ограничений
(2.1)
где хотя бы одна из функций f или gi является нелинейной.
По аналогии с линейным программированием ЗНП однозначно определяется парой (D,f) и кратко может быть записана в следующем виде
(2.2)
Также очевидно, что вопрос о типе оптимизации не является принципиальным. Поэтому мы, для определенности, в дальнейшем по умолчанию будем рассматривать задачи максимизации.
Как и в ЗЛП, вектор называется допустимым планом, а если для любого x?D выполняется неравенство , то х* называют оптимальным планом. В этом случае х* является точкой глобального максимума.
С точки зрения экономической интерпретации f(x) может рассматриваться как доход, который получает фирма (предприятие) при плане выпуска х, а как технологические ограничения на возможности выпуска продукции. В данном случае они являются обобщением ресурсных ограничений в ЗЛП
Задача (2.2) является весьма общей, т. к. допускает запись логических условий, например:
или запись условий дискретности множеств:
Набор ограничений, определяющих множество D, при необходимости всегда можно свести либо к системе, состоящей из одних неравенств:
либо, добавив фиктивные переменные у, к системе уравнений:
Перечислим свойства ЗИП, которые существенно усложняют процесс их решения по сравнению с задачами линейного программирования:
1. Множество допустимых планов D может иметь очень сложную структуру (например, быть невыпуклым или несвязным).
2. Глобальный максимум (минимум) может достигаться как внутри множества D, так и на его границах (где он, вообще говоря, будет не совпадать ни с одним из локальных экстремумов).
3. Целевая функция f может быть недифференцируемой, что затрудняет применение классических методов математического анализа.
В силу названных факторов задачи нелинейного программирования настолько разнообразны, что для них не существует общего метода решения.
2.1.2. Решение задач условной оптимизации методом Лагранжа. Одним из наиболее общих подходов к решению задачи поиска экстремума (локального максимума или минимума) функции при наличии связующих ограничений на ее переменные (или, как еще говорят, задачи условной оптимизации) является метод Лагранжа. Многим читателям он должен быть известен из курса дифференциального исчисления. Идея данного метода состоит в сведении задачи поиска условного экстремума целевой функции
(2.3)
на множестве допустимых значения D, описываемом системой уравнений
(2.4)
к задаче безусловной оптимизации функции
Ф(x,u) = f(x1,x2,...,xn)+ulgl(xi,x2,...,xn)+...+ungm(xl,x2,...,xn), (2.5)
где - вектор дополнительных переменных, называемых множителями Лагранжа. Функцию Ф(х,и), где , , называют функцией Лагранжа. В случае дифференцируемое(tm) функций f и gi справедлива теорема, определяющая необходимое условие существования точки условного экстремума в задаче (2.3)-(2.4). Поскольку она непосредственно относится к предмету математического анализа, приведем ее без доказательства.
Теорема 2.1. Если х* является точкой условного экстремума функции (2.3) при ограничениях (2.4) и ранг матрицы первых частных производных функций
равен т, то существуют такие, не равные одновременно нулю, при которых
(2.6)
Из теоремы (2.1) вытекает метод поиска условного экстремума, получивший название метода множителей Лагранжа, или просто метода Лагранжа. Он состоит из следующих этапов.
1. Составление функции Лагранжа Ф(х,и).
2. Нахождение частных производных
и
3. Решение системы уравнений
(2.7)
относительно переменных х и и.
4. Исследование точек, удовлетворяющих системе (2.7), на максимум (минимум) с помощью достаточного признака экстремума.
Присутствие последнего (четвертого) этапа объясняется тем, что теорема (2.1) дает необходимое, но не достаточное условие экстремума. Положение дел с достаточными признаками условного экстремума обстоит гораздо сложнее. Вообще говоря, они существуют, но справедливы для гораздо более частных ситуаций (при весьма жестких предпосылках относительно функций f и gi) и, как правило, трудноприменимы на практике. Еще раз подчеркнем, что основное практическое значение метода Лагранжа заключается в том, что он позволяет перейти от условной оптимизации к безусловной и, соответственно, расширить арсенал доступных средств решения проблемы. Однако нетрудно заметить, что задача решения системы уравнений (2.7), к которой сводится данный метод, в общем случае не проще исходной проблемы поиска экстремума (2.3)-(2.4). Методы, подразумевающие такое решение, называются непрямыми. Они могут быть применены для весьма узкого класса задач, для которых удается получить линейную или сводящуюся к линейной систему уравнений (2.7). Их применение объясняется необходимостью получить решение экстремальной задачи в аналитической форме (допустим, для тех или иных теоретических выкладок). При решении конкретных практических задач обычно используются прямые методы, основанные на итеративных процессах вычисления и сравнения значений оптимизируемых функций.
2.1.3. Градиентные методы решения задач безусловной оптимизации. Ведущее место среди прямых методов решения экстремальных задач занимает градиентный метод (точнее, семейство градиентных методов) поиска стационарных точек дифференцируемой функции. Напомним, что стационарной называется точка, в которой и которая в соответствии с необходимым условием оптимальности является "подозрительной" на наличие локального экстремума. Таким образом, применяя градиентный метод, находят множество точек локальных максимумов (или минимумов), среди которых определяется максимум (или минимум) глобальный.
Идея данного метода основана на том, что градиент функции указывает направление ее наиболее быстрого возрастания в окрестности той точки, в которой он вычислен. Поэтому, если из некоторой текущей точки х(1) перемещаться в направлении вектора , то функция f будет возрастать, по крайней мере, в некоторой окрестности х(1). Следовательно, для точки , , лежащей в такой окрестности, справедливо неравенство . Продолжая этот процесс, мы постепенно будем приближаться к точке некоторого локального максимума (см. рис. 2.1).
Однако как только определяется направление движения, сразу же встает вопрос о том, как далеко следует двигаться в этом направлении или, другими словами, возникает проблема выбора шага ?, в рекуррентной формуле
(2.8)
задающей последовательность точек, стремящихся к точке максимума.
В зависимости от способа ее решения различают различные варианты градиентного метода. Остановимся на наиболее известных из них.
Метод наискорейшего спуска
Название метода можно было бы понимать буквально, если бы речь шла о минимизации целевой функции. Тем не менее, по традиции такое название используется и при решении задачи на максимум.
Пусть f(x) = f(xl,xl,...xn) - дифференцируемая функция, заданная на Rn, а - некоторая текущая точка. Оговоримся, что каких-либо общих рекомендаций, касающихся выбора исходной точки (или, как еще говорят, начального приближения) x(0), не существует, однако по возможности она должна находиться близко от искомого оптимального плана х*. Как уже говорилось выше, если x(q) - нестационарная точка (т. е. ), то при движении в направлении функция f(x) на некотором промежутке обязательно будет возрастать. Отсюда возникает естественная идея такого выбора шага, чтобы движение в указанном направлении продолжалось до тех пор, пока возрастание не прекратится. Для этого выразим зависимость значения f(x) от шагового множителя ? > 0 , полагая
(2.9)
или, в координатной форме,
(2.10)
Чтобы добиться наибольшего из возможных значений f при движении по направлению , нужно выбрать такое значение , которое максимизирует функцию . Для вычисления , используется необходимое условие экстремума . Заметим, что если для любого ? >0 , то функция f(x) не ограничена сверху (т. е. не имеет максимума). В противном случае, на основе (2.10) получаем
(2.11)
что, в свою очередь, дает
(2.12)
Если считать, что следующая точка соответствует оптимальному значению , то в ней должно выполняться условие , и следует находить из условия или
(2.13)
Условие (2.13) означает равенство нулю скалярного произведения градиентов функции f точках х(q+1) и х(q) Геометрически оно может быть интерпретировано как перпендикулярность векторов градиентов функции f в указанных точках, что и показано на рис. 2.2. Продолжая геометрическую интерпретацию метода наискорейшего спуска, отметим, что в точке х(q+1) вектор , будучи градиентом, перпендикулярен линии уровня, проходящей через данную точку. Стало быть, вектор является касательным к этой линии. Итак, движение в направлении градиента следует продолжать до тех пор, пока он пересекает линии уровня оптимизируемой функции.
После того как точка х(q+1) найдена, она становится текущей для очередной итерации. На практике признаком достижения стационарной точки служит достаточно малое изменение координат точек, рассматриваемых на последовательных итерациях. Одновременно с этим координаты вектора должны быть близки к нулю.
Метод дробления шага
Для нахождения шага ?, в методе наискорейшего спуска требуется решить уравнение (2.13), которое может оказаться достаточно сложным. Поэтому часто ограничиваются "подбором" такого значения ?, что . Для этого задаются некоторым начальным значением ?1 (например, ?1 =1) и проверяют условие . Если оно не выполняется, то полагают
и т. д. до тех пор, пока не удается найти подходящий шаг, с которым переходят к следующей точке х(q+1). Критерий завершения алгоритма, очевидно, будет таким же, как и в методе наискорейшего спуска.
2.1.4. Оптимизационные задачи для выпуклых функций. Общим недостатком рассмотренных выше методов безусловной оптимизации было, с одной стороны, то, что они позволяют отыскивать только точки, подозрительные на локальный экстремум, а с другой - то, что найденные решения могут существенно зависеть от начального приближения. Поиск глобального оптимума подразумевает перебор найденных точек, который, в случае градиентных методов, может быть осуществлен за счет подбора соответствующих начальных приближений х(0).
Рис. 2.1
Рис. 2.2
Однако существует один класс функций, для которых градиентные методы приводят к нахождению глобального оптимума. Это выпуклые функции.
>Функция называется выпуклой в области D, если для любых двух точек и любого выполняется неравенство
(2.14)
если же
(2.15)
то функция называется вогнутой.
Геометрический смысл понятий выпуклости и вогнутости для случая функции одной переменной представлен на рис. 2.3. Из него, в частности, видно, что график выпуклой функции лежит ниже отрезка, соединяющего точки и , а график вогнутой - выше.
Рис. 2.3
Можно доказать, что достаточным условием выпуклости функции является положительная определенность матрицы
называемой также матрицей Гессе, во всех точках x?D. Соответственно, достаточным условием вогнутости является отрицательная определенность матрицы Гессе. В частности, для функций одной переменной достаточным условием выпуклости (вогнутости) является выполнение неравенства .
Как следует из геометрической интерпретации, для выпуклой функции локальный экстремум, если он существует, совпадает с глобальным. Справедлива теорема.
Теорема 2.2. Если f(x) выпуклая (вогнутая) на Rn функция и , то х* - точка глобального минимума (максимума).
Доказательство.
Доказательство достаточно провести для случая вогнутой функции, т. к. для противоположного случая оно будет абсолютно аналогичным с точностью до знака.
Пусть х - произвольная точка, отличная от точки х*. Тогда, для любого , в силу вогнутости функции f(x) будет выполняться
из чего следует
Если ввести вектор l = х - х* и обозначить , то длина вектора будет равна . Следовательно,
Устремив и учитывая, что вектор l сонаправлен с , получим
По условию теоремы . Это означает, что для любого вектора l (а, стало быть, для любой точки х) согласно формуле, выражающей производную по направлению через градиент,
Следовательно, для любой точки х, не равной х*, справедливо неравенство , т.е. х* - точка глобального максимума. ^
Поскольку выпуклые функции обладают столь "полезными" оптимизационными качествами, они занимают исключительно важное место в теории исследования операций. Соответствующий раздел получил название выпуклого программирования, а общая задача выпуклого программирования формулируется как проблема поиска максимума вогнутой (минимума выпуклой) функции на выпуклом множестве.
2.1.5. Метод допустимых направлений. Данный метод также называется методом возможных направлений или же по имени автора - методом Зойтендейка, см. [16]. Его основную идею будет удобно продемонстрировать на примере ЗИП с ограничениями в форме неравенств:
(2.16)
В указанном методе так же, как и в градиентных методах, находится последовательность точек таких, что 7. При этом переход от точки х(q) к точке происходит по некоторому выбранному направлению s(q) с шаговым множителем :
(2.17)
По отношению к векторам, задающим направления перемещения, вводятся два фундаментальных понятия.
>Направление s называется допустимым (возможным) в точке , если существует такое , что .
>Направление s называется прогрессивным в точке , если существует такое , что f(x(q) +?s) > f(x(q)) для задачи максимцзации и f(x(q) +?s) < f(x(q)) для задачи минимизации.
На основе данных определений достаточно просто сформулировать критерий проверки оптимальности точки (так называемый критерий оптимальности в терминах допустимых и прогрессивных направлений):
> точка х* является оптимальным планом задачи (2.16), если в ней ни одно допустимое направление не является прогрессивным.
В алгоритме метода допустимых направлений правила выбора точки к которой происходит очередной переход, различаются в зависимости от того, где находится текущая точка . Принципиально возможны две ситуации.
1°. Точка лежит внутри области D, т. е. для всех i ? 1 : т (см. рис. 2.4). Очевидно, что для внутренней точки любое направление будет допустимым (при выборе достаточно малого шага), поэтому естественным представляется движение в сторону "гарантированного" возрастания значения функции, а именно в направлении градиента. Значит, для внутренней точки целесообразно выбрать .
Шаговый множитель выбирается так, чтобы, с одной стороны, новая точка принадлежала D, а с другой - значение целевой функции в ней было как можно большим.
Рис. 2.4
Рис. 2.5
C этой целью сначала найдем промежуток из условия , для чего необходимо решить систему неравенств:
(2.18)
Зная промежуток , определяем значение шагового множителя из условия максимизации значения функции в направлении :
(2.19)
Вновь найденная точка может находиться или внутри области D, или на ее границе. В первом случае (на рис. 2.4 ему соответствует точка ) переходим к началу данного пункта и повторяем вышеописанные действия, а во втором (точка на рис. 2.4) - действуем по рассматриваемой далее схеме.
2°. Точка х(q) находится на границе области (см. рис. 2.5). Это означает, что одно или несколько неравенств из системы ограничений задачи (2.16) выполняются как строгие равенства: . Например, на рис. 2.5 и .
Ограничение, которое в текущей точке выполняется как равенство, называют активным. Множество номеров активных ограничений в точке будем обозначать как . В примере, изображенном на рис. 2.5, I(x(q)) = {l, 3}. Также из рисунка видно, что все допустимые направления, исходящие из точки x^q\ должны образовывать тупые углы с векторами градиентов функций, задающих активные ограничения в данной точке. Последнее условие может быть выражено через задание ограничений на значения скалярных произведений вектора направления s на градиенты функции ограничений:
(2.20)
(2.21)
где Iл - множество номеров индексов линейных ограничений, Iн - множество номеров индексов нелинейных ограничений. Соответственно, - номера линейных активных ограничений, a - номера нелинейных активных ограничений. Отличие условий (2.20) от условий (2.21) заключается в том, что в случае линейного ограничения направление, образующее прямой угол с градиентом ограничивающей функции (т. е. их скалярное произведение равно нулю), будет заведомо допустимым, а в случае нелинейного ограничения - возможно, нет.
Все возможные направления в точке образуют так называемый конус допустимых направлений, и из них для следующего перехода, очевидно, нужно выбрать прогрессивное. Если такового не существует, то согласно сформулированному выше критерию точка является оптимальной! Для ускорения максимизации функции желательно, чтобы угол между искомым допустимым прогрессивным направлением и градиентом целевой функции был как можно меньше или, что то же самое, как можно большей была бы проекция s на (при условиях нормировки вектора ). Иными словами, желательно, чтобы неравенство выполнялось при минимально возможном . Тогда задачу отыскания наилучшего допустимого прогрессивного направления можно свести к задаче минимизации параметра :
(2.22)
при условиях
(2.23)
где - условие нормировки, обеспечивающее ограниченность решения;
- некоторое достаточно малое число, характеризующее "строгость" выполнения неравенств.
В отличие от всех остальных, последнее условие в системе (2.23) является нелинейным, что существенно усложняет процесс решения задачи (2.22)-(2.23). Поэтому на практике для определения направления (возможно, не лучшего) переходят от данной задачи к задаче линейного программирования путем замены указанных выше условий нормировки на ограничения вида :
(2.24)
(2.25)
где , .
После того как прогрессивное направление s(q) найдено, шаговый множитель определяется по методу, описанному в п. 1?.
В заключение отметим, что при практических расчетах алгоритм завершается при достижении такой точки х*, в которой , где ? - достаточно малое число.
Представляется полезным обратить внимание читателя и на | то, что применяемый для решения задач линейного программирования симплекс-метод может быть рассмотрен как частный случай метода допустимых направлений. В частности, этап выбора столбца, вводимого в очередной базис, соответствует определению допустимого прогрессивного направления. Более подробно о такой концепции симплекс-метода можно прочесть в [1].
2.1.6. Пример решения ЗНП методом допустимых направлений. Рассмотрим процесс применения метода допустимых направлений на конкретном примере. Пусть дана ЗНП:
(2.26)
(2.27)
Итерация 1. В качестве начального приближения возьмем точку х(1) = (0,0). Нетрудно заметить, что она удовлетворяет системе неравенств (2.27), т. е. . Для х(1) все неравенства выполняются как строгие, т. е. множество индексов активных ограничений ?. Следовательно, в х(1) любое направление является допустимым, и нам остается определить, с каким шагом , можно двигаться вдоль градиента целевой функции . Система неравенств типа (2.18), из решения которых определяется интервал допустимых значений для , для данной задачи примет вид:
<< Пред. стр. 6 (из 13) След. >>
Список литературы по разделу