Глава V. Нелинейное программирование
Методы нелинейного программирования – это численные методы отыскания минимума (максимума) функций многих переменных при наличии ограничений типа равенств и неравенств, имеющих нелинейный вид, т.е. требуется найти такой вектор , при котором функция
достигает минимума, при выполнении ограничений
Метод линеаризации. Суть метода линеаризации заключается в следующем. Выполняется линеаризация всех соотношений (5.1) – (5.3). Для этого применяется разложение в ряд Тейлора с удержанием только линейных составляющих. Разложение выполняется в окрестности точки , которой следует задаться. Итак, вместо (5.1) – (5.3) имеем для k-той итерации:
Соотношения (5.4) позволяют решать задачу линейного программирования.
Таким образом, может быть построена последовательность точек , которая, вообще говоря, может привести к точке , являющийся решением задачи (5.1) – (5.3).
Пример. Минимизировать
Пусть . Линеаризованные соотношения
определяют задачу линейного программирования. Решив эту задачу, найдем точку первого приближения , затем находится точка и т.д.
Рассмотрим геометрическую интерпретацию задачи этого примера. На рис. 5.1 приведены графики, соответствующие ограничениям (5.6) и (5.8), (5.9).
З адача (5.5), (5.6) предполагает нахождение на дуге АВ такой точки, в которой целевая функция (5.5) достигает минимума. Решение этой задачи известно, это точка A.
В результате линеаризации геометрическая интерпретация задачи изменилась. Теперь среди точек прямой требуется найти такую точку, в которой функция (5.7) достигает минимума. Как было сказано выше, это задача определяется соотношениями (5.7) – (5.9). Оправдано, однако, добавление к этим соотношениям дополнительных неравенств, которые бы ограничивали область поиска решения. Эти дополнительные ограничения вводятся из следующих соображений. Ошибка линеаризации по мере удаления от точки все больше и больше возрастает, см., например, зависимости и . В таких условиях вполне оправдано введение ограничений
г де и некоторые положительные числа. Полученная при этом новая допустимая область показана на рис. 5.1 и 5.2.
Таким образом, уже среди точек отрезка должна быть найдена точка, в которой целевая функция (5.7) достигает минимума.
Совершенно аналогично следует поступать при любой итерации, причем, числа и от итерации к итерации следует постепенно уменьшать.
Алгоритм нелинейного программирования
Излагаемый ниже алгоритм позволяет решать задачу нелинейного программирования в постановке (5.1) – (5.3).
В качестве начальной точки может быть выбрана любая точка, т.е. как точка, принадлежащая допустимой области D (определяется ограничениями (5.2), (5.3)), так и точки, не принадлежащие ей. Если , то в первую очередь организуется наискорейший спуск «почти в область D», а затем включается в работу метод линеаризации. Если , то сразу применяется метод линеаризации.
Рассмотрим, что входит в понятие «почти в область D» и как организуется наискорейший спуск в эту область. «Почти областью D» называется вся совокупность точек x, для которых имеют место ограничения
где , – некоторые малые положительные числа. Эти числа должны быть такими, что выполнение условий (5.10) может расцениваться как практически удовлетворительное выполнение равенств
(строго говоря, точного выполнения этих равенств практически добиться не возможно вообще). Таким образом, «почти область D» определяется ограничениями (5.10), (5.11).
Наискорейший спуск почти в область D осуществляется в результате минимизации функции
Как только обратится в ноль, решается задача линейного программирования, затем вновь проверяются все ограничения и т.д. Задача (5.5), (5.6) по этому методу решается примерно так, как это показано на рис. 5.3.
Н а этом рисунке , ; , – траектории спуска «почти в область D», , ; , – траектории, соответствующие методу линеаризации.
Методы решения задач нелинейного программирования
Нелинейное программирование используется для решения однокритериальных задач оптимизации с детерминированной целевой функцией при накладываемых ограничениях в виде равенств или неравенств. Для данного класса задач снимается условие линейности функций или ограничений.
Особенности использования данных методов определяются тем, что нелинейность целевой функции f(x) требует исследования условий (необходимых и достаточных) наличия экстремума. Для этого надо уметь получить аналитические выражения по меньшей мере двух производных этой функции.
При наличии линейных ограничений эти производные ищут только в точках, удовлетворяющих данным ограничениям. Нелинейность ограничений может привести к тому, что пространство возможных решений становится невыпуклым, и тогда оптимальному решению не всегда будет соответствовать одна из угловых точек этого пространства.
Универсальных алгоритмов решения нелинейных задач не существует из-за большого разнообразия вида нелинейности.
Разработанные ныне методы решения задач нелинейного программирования могут быть разделены на ряд больших групп:
¨ методы линеаризации целевой функции и ограничений, основанные на их разложении в ряд, логарифмирование и т.д., с последующим применением методов линейного программирования для решения задачи;
¨ аналитические методы нахождения экстремальных значений целевой функции при наличии ограничений. Они могут применяться при условии, что неизвестные величины непрерывны, или на этот счет сделаны соответствующие допущения, а также целевая функция и ограничения имеют частные производные хотя бы до второго порядка включительно;
¨ поисковые методы оптимизации, обеспечивающие решение нелинейной задачи путем последовательного перехода от одного допустимого решения к другому, в направлении экстремума целевой функции, до тех пор, пока дальнейшее ее улучшение станет невозможным или нецелесообразным.
Методы решения задач дискретного (целочисленного) программирования
Дискретное программирование используется для решения задач с детерминированной целевой функцией при ограничениях на значения переменных.
Примерами таких задач являются: определение очередности выполнения работ, назначение ресурсов по объектам использования, выбор маршрута на сети «задача о коммивояжере».
Основной особенностью является то, что все или некоторые переменные должны принимать только целочисленные (дискретные) значения. Обычно это бывает при описании неделимых объектов (людей, машин и т.п.) или при наложении жестких ограничений типа равенств.
При решении задач возникают сложности с выбором специальных дополнительных ограничений для отсечения области решений с нецелочисленными переменными, которые часто приходится выбирать по эвристическим правилам.
Различают два класса методов решения задач дискретного программирования: методы отсечения и комбинаторные методы.
Методы отсечений используются при решении линейных целочисленных задач без булевых переменных. Их идея заключается в ослаблении ограничений (за счет отказа от требований целочисленности) и решении обычной задачи линейного программирования. Затем, если полученное оптимальное решение не удовлетворяет требованию целочисленности, вводят специальные дополнительные требования, тем самым отсекая некоторую область возможных решений, и вновь решают задачу линейного программирования с проверкой результатов на целочисленность переменных.
Процесс повторяется до выполнения требований по целочисленности. Для решения целочисленных задач используется алгоритм Гомори и алгоритм Дальтона и Ллевелина (см. [6.57]).
Комбинаторные методы используются для решения нелинейных задач с булевыми переменными. Для таких задач используется так называемый аддитивный алгоритм, вычислительные операции в котором осуществляют вычитанием. Идея аддитивного алгоритма заключается в переборе 2 N возможных решений (где N — число булевых переменных) и выбор лучшего из них (см. [6.45; 6.55]).