Нелинейное программирование системный анализ

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

Нелинейное программирование используется для решения однокритериальных задач оптимизации с детерминированной целевой функцией при накладываемых ограничениях в виде равенств или неравенств. Для данного класса задач снимается условие линейности функций или ограничений.

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

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

Универсальных алгоритмов решения нелинейных задач не существует из-за большого разнообразия вида нелинейности.

Разработанные ныне методы решения задач нелинейного программирования могут быть разделены на ряд больших групп:

¨ методы линеаризации целевой функции и ограничений, основанные на их разложении в ряд, логарифмирование и т.д., с последующим применением методов линейного программирования для решения задачи;

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

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

Методы решения задач дискретного (целочисленного) программирования

Дискретное программирование используется для решения задач с детерминированной целевой функцией при ограничениях на значения переменных.

Примерами таких задач являются: определение очередности выполнения работ, назначение ресурсов по объектам использования, выбор маршрута на сети «задача о коммивояжере».

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

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

Различают два класса методов решения задач дискретного программирования: методы отсечения и комбинаторные методы.

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

Процесс повторяется до выполнения требований по целочисленности. Для решения целочисленных задач используется алгоритм Гомори и алгоритм Дальтона и Ллевелина (см. [6.57]).

Комбинаторные методы используются для решения нелинейных задач с булевыми переменными. Для таких задач используется так называемый аддитивный алгоритм, вычислительные операции в котором осуществляют вычитанием. Идея аддитивного алгоритма заключается в переборе 2 N возможных решений (где N — число булевых переменных) и выбор лучшего из них (см. [6.45; 6.55]).

Источник

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

Как известно, общая задача математического программирования формулируется следующим образом: найти вектор , удовлетворяющий системе ограничений

b_i, i=1,…,m,

(система иногда представляется через знак » /html/597/308/html_4ssnywccmf.tFzE/img-eXAwNI.png» name=»Object419″ align=»absmiddle» width=»113″ height=»22″>. При этом предполагается, что известны функциии. Обычно на некоторые переменные из наборанакладывается условие неотрицательности. Если и , гдеи – известные константы, то при условии неотрицательности решения получаем задачу линейного программирования. Любую другую задачу математического программирования, не удовлетворяющую таким условиям, будем считать нелинейной.

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

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

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

Процесс нахождения решения задачи нелинейного программирования с использованием её геометрической интерпретации включает следующие этапы:

1. Находят область допустимых решений задачи, определяемых соотношениями (если она пуста, то задачане имеет решения).
2. Строят гиперповерхность .
3. Определяют гиперповерхность наивысшего (наинизшего) уровня или устанавливают неразрешимость задачи из-за неограниченности функции сверху (снизу) намножестве допустимых решений.
4. Находят точку области допустимых решений, через которую проходит гиперповерхность наивысшего (наинизшего) уровня, и определяют в ней значение функции .

Пример 7.1. Найти максимальное значение функции при условиях Так как целевая функция нелинейная, то это задача нелинейного программирования. Областью допустимых решений данной задачи является многоугольник . Следовательно, для нахождения её решения нужно определить такую точку многоугольника, в которой функцияпринимает максимальное значение. Построим линию уровня , где– некоторая постоянная, и исследуем её поведение при различных значениях. При каждом значенииполучаем параболу, которая тем выше отдалена от оси, чем больше значение(рис. 7.1). Значит, функцияпринимает максимальное значение в точке касания одной из парабол с границей многоугольника. В данном случае это точка, в которой гиперповерхностькасается сторонымногоугольника. Координаты точкиможно найти из системы уравнений: Решив эту систему, получаем: Итак,при Как видим, в задаче нелинейного программирования точка максимального значения целевой функции не является в данном случае вершиной многоугольника решений. Рассмотрим частный случай общей задачи нелинейного программирования, предполагая, что система ограничений содержит только уравнения, отсутствуют условия отрицательности переменных и и – функции, непрерывные вместе со своими частными производными (по крайней мере, вторая частная производная должна быть непрерывной. (7.1) (7.2) Рис. 7.1. Геометрическое решение задачинелинейного программирования примера 7.1 В курсе математического анализа задачу (7.1)-(7.2) называют задачей на условный экстремум или классической задачей оптимизации. Чтобы вспомнить необходимые и достаточные условия существования экстремума такой задачи, введём набор переменных , называемыхмножителями Лагранжа, составим функцию Лагранжа , находим частные производные ии рассматриваем системууравнений (здесь привлечём необходимое условие экстремума, заключающееся в том, что первая производная должна быть равна): (7.3) с неизвестными. Всякое решение системы уравнений (7.3) определяет точку, в которой может иметь место экстремум функции. Следовательно, решив систему (7.3), получают все точки, в которых функцияможет иметь экстремальные значения. Дальнейшее исследование найденных точек проводят так же, как и в случае безусловного экстремума (здесь привлекается достаточное условие экстремума – если вторая производная меньше нуля, то имеет место максимум, если больше нуля – минимум). Таким образом, определение экстремальных точек задачи нелинейного программирования (7.1)-(7.2) методом множителей Лагранжа включает следующие этапы:

1. Составляют функцию Лагранжа.
2. Находят частные производные от функции Лагранжа по переменным ии приравнивают их 0.
3. Решая систему уравнений (7.3), находят точки, в которых целевая функция может иметь экстремум.
4. Среди точек, подозрительных на экстремум, находят точки, в которых достигается экстремум, и вычисляют значения целевой функции в этих точках.

Рассмотрим пример. Пример 7.2. Предприятию необходимо изготовить 180 деталей. Эти изделия могут быть изготовлены двумя технологическими способами. При производстве изделийI способом затраты равны (руб.), а при изготовленииизделийII способом они составляют (руб.). Определить, сколько изделий каждым из способов следует изготовить так, чтобы общие затраты на производство продукции были минимальными. Решение. Математическая модель задачи нелинейного программирования состоит в следующем: найти минимум функции при условияхи. Решим задачу, используя метод множителей Лагранжа. Найдём минимальное значение функции при условии , т.е. без учёта требования неотрицательности переменных. Для этого составим функцию Лагранжа . Вычислим её частные производные по , , и приравняем их : Перенесём в правые части первых двух уравнений и, приравнивая их левые части, получимили. Решаем совместно систему, т.е. получаем координаты точки, удовлетворяющие условиям неотрицательности. Эта точка является подозрительной на экстремум. Используя вторые частные производные, выясняем, что в этой точке функция имеет условный минимум. То же получим, если исследование на условный экстремум функциисведём к исследованию на безусловный экстремум функции, полученной изв результате её преобразований: из уравнения связи найдеми подставим в целевую функцию, получим функцию одной переменной: . ; ; ; , т.е. в этой точке имеем минимум. Метод множителей Лагранжа можно применять и в том случае, когда условия связи представляют собой неравенства. Так, если требуется найти экстремум функции при условии, то сначала следует найти точки безусловного экстремума функциииз уравнений , затем среди этих точек отобрать те, координаты которых удовлетворяют условию связи , и, наконец, определить точки,удовлетворяющие системе уравнений: . Tочки, найденные в результате решения этой системы, вместе с точками, определёнными на первом этапе и удовлетворяющими условию, подлежат дальнейшему исследованию, как и при нахождении безусловного экстремума. В заключение рассмотрения метода Лагранжа для решения задач нелинейного программирования скажем, что функцию Лагранжа можно трактовать и в определённом экономическом смысле. Если максимизируемую функцию интерпретировать как прибыль, а правые части неравенств как величину отпущенных ресурсов, то множительy можно рассматривать как стоимость единицы ресурсов. Тогда определит экономию ресурсов в денежном выражении, а функция Лагранжа будет являться величиной общего дохода. Для общей задачи нелинейного программирования (7.4) (7.5) (7.6) Как уже упоминалось, для отдельных классов задач, в которых сделаны дополнительные ограничения относительно свойств функции иразработаны эффективные методы их решения. В частности, ряд таких методов имеется для решения задач нелинейного программирования (7.4)–(7.6) при условии, что– вогнутая (выпуклая) функция и область допустимых решений, определяемая ограничениями (7.5)–(7.6), – выпуклая. Определение 7.1. Функция , заданная на выпуклом множестве X, называется выпуклой, если для любых двух точек и из X и любого выполняется соотношение . Определение 7.2. Функция , заданная на выпуклом множествеX, называется вогнутой, если для любых двух точек и из X и любого выполняется соотношение . Определение 7.3. Говорят, что множество допустимых решений задачи (7.4)–(7.6) удовлетворяет условию регулярности, если существует, по крайней мере, одна точка , принадлежащая области допустимых решений, такая, что . Определение 7.4. Задача (7.4)–(7.6) называется задачей выпуклого программирования, если функция является вогнутой (выпуклой), а функции– выпуклыми. Теорема 7.1. Любой локальный максимум (минимум) задачи выпуклого программирования является глобальным максимумом (минимумом). Что называется функцией Лагранжа, уже было пояснено, седловой же точкой функции Лагранжа называется точка если для всех и .

Источник