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

       Методы прямого поиска. Суть этих методов состоит в том, что для поиска экстремального значения используются только значения ЦФ. Большинство методов этой группы основаны на экспериментальных данных и отражают опыт практических исследований, но строго теоретического обоснования не имеют.

К достоинствам этих методов относится:

· Простота алгоритма;

· Возможность вычислить значение ЦФ практически во всех точках.

Недостаток:

· Трудность при обработке Седловых точек.

К этим методам относятся: метод покоординатного спуска, метод Хука-Дживса, метод Розенброка, метод Пауэлла, метод регулярного многогранника, метод деформируемого многогранника, метод скользящего допуска.

Метод покоординатного спуска

Суть метода состоит в том, что поиск решения выполняется по каждой оси (направление изменения переменной x_i). Выбирается первая переменная x₁ (первая ось координат) и выполняется перемещение по этой оси. В каждой точке вычисляется значение ЦФ. Движение вдоль выбранной оси координат прекращается в тот момент, когда очередная точка будет иметь значение ЦФ большее, чем в предыдущей точке.

Фиксируется лучшая достигнутая точка по текущей оси. Затем переходит ко второй оси координат (x2) и т.д., до последней переменной xn и затем процедура поиска повторяется, начиная с первой оси координат. Ели при проходе очередного цикла нельзя указать ни одного перемещения по любой оси координат, то уменьшают размер шага и выполняют ту же процедуру с меньшим шагом. Поиск экстремума прекращается, если размер шага становится меньше некоторой сколь угодно малой величины или, когда значение ЦФ в двух соседних точках становится практически одинаковой.

Для организации поиска метода покоординатного спуска используется соотношение x^k=x^k-1+a_k∙U^k, где x^k – координаты текущей точки поиска, x^k-1 – координаты предыдущей точки поиска, U^k – единичный вектор, определяющий направление спуска на k-м шаге. Может принимать значения +1 и -1, что обеспечивает перемещение по оси в одном из двух направлений. a_k – размер шага. Одна итерация включает в себя проход по каждой оси координат.

Алгоритм метода:

1. Определить координаты стартовой точки;

2. Вычислить значение ЦФ в этой точке;

3. Выбрать очередную ось и прибавить дельта x(шаг итерации)

4. Вычислить значение ЦФ в текущей точке;

5. Если значение ЦФ в текущей точке меньше, чем в предыдущей, то сделать еще один шаг в том же направлении и перейти к пункту 4. Если значение ЦФ в текущей точке больше, чем в предыдущей, то прейти к пункту 6.

6. Определить, был ли сделанный шаг в этом направлении первым, если да, то запомнить, что по текущей оси по текущему направлению сделан первый неудачный шаг. Перейти к пункту 7. Если нет, перейти к пункту 8.

7. Сменить направление движения по текущей оси и прейти к пункту 4.

8. Проверить все ли оси координат просмотрены, если да – перейти к пункту 9, если нет – перейти к пункту 3.

9. Проверить по всем ли осям координат сделано два неудачных первых шага. Если да, то уменьшить дельта x и перейти к пункту 10, если нет – перейти к пункту 3.

10. Проверить, достигнута ли требуемая точность, если да – перейти к шагу 11, если нет, то перейти к шагу 3 и начать просмотр с первой оси координат.

11. Остановить вычисления, вывести значение ЦФ и координаты точки экстремума.

 

       Градиентные методы поиска экстремума при своей работе требуют вычисления не только значения ЦФ на каком-либо множестве точек, но и вычисления первой производной на том же множестве, иногда вычисление второй производной.

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

       Метод градиентного спуска.

       Суть его заключается в том, что в каждой i -той точке алгоритма вычисляется градиент. Определяются направления движения и шаг. Строится последовательность точек, переходя от одной точке к другой, достигается точка минимума. В точке минимума все элементы градиента принимают значение 0. Для определения координат очередной точки используется антиградиент – противоположное направление градиента.

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

       Для случая с фиксированным коэффициентом изменение размера шага координаты точки на k-ом шаге по формуле: x^k=x ^k-1-s_k

       Размер шага s_k определяется по формуле s_k=d_kградf(x^k-1) где d_k – коэффициент изменения шага, d_k<1

       Критерий остановки алгоритма – это выполнение следующего условия |-градf(sk)|<E, E-точность вычисления.

 

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

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

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

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

1. Находят область допустимых решений задачи, определяемых соотношениями  (если она пуста, то задача не имеет решения).

2. Строят гиперповерхность .

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

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

Например, найти максимальное значение функции   при условиях

 

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

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

Решив эту систему, получаем:

Итак,  при

 

 

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

 

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

 

                                       

                                  

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

,

находим частные производные   и  и рассматриваем систему   уравнений (здесь привлечём необходимое условие экстремума, заключающееся в том, что первая производная должна быть равна ):

                            

с m + n неизвестными .

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

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

1. Составляют функцию Лагранжа.

2. Находят частные производные от функции Лагранжа по переменным  и   приравнивают их к нулю.

3. Решая систему уравнений, находят точки, в которых целевая функция может иметь экстремум.

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

 

Пример. Предприятию необходимо изготовить 180 деталей. Эти изделия могут быть изготовлены двумя технологическими способами. При производстве   изделий I способом затраты равны  (руб.), а при изготовлении   изделий II способом они составляют  (руб.). Определить, сколько изделий каждым из способов следует изготовить так, чтобы общие затраты на производство продукции были минимальными.

 

Решение.

Математическая модель задачи нелинейного программирования состоит в следующем: найти минимум функции   при условиях   и .

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

.

Вычислим её частные производные по , ,   и приравняем их к нулю:

Перенесем в правые части первых двух уравнений   и, приравнивая их левые части, получим   или .

Решаем совместно систему, т.е. получаем координаты точки, удовлетворяющие условиям неотрицательности. Эта точка является подозрительной на экстремум. Используя вторые частные производные, выясняем, что в этой точке функция  имеет условный минимум. То же получим, если исследование на условный экстремум функции сведем к исследованию на безусловный экстремум функции , полученной из в результате её преобразований: из уравнения связи найдем   и подставим в целевую функцию, получим функцию одной переменной :

.

; ; ; , т.е. в этой точке имеем минимум.

                  

Метод множителей Лагранжа можно применять и в том случае, когда условия связи представляют собой неравенства.

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

.

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

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