Тема 14. Нелинейное программирование в решении задач управления.

 

Основные понятия и математическая модель задачи.

 

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

Выделение класса экстремальных задач, определяемых линейным функционалом на множестве, задаваемом линейными ограничениями, следует отнести к 30-м годам ХХ столетия. Одновременно с развитием линейного программирования большое внимание уделялось задачам нелинейного программирования, в которых либо целевая функция, либо ограничения, либо то и другое нелинейны. В 1951 г. была опубликована работа Куна и Таккера, в которой приведены необходимые и достаточные условия оптимальности для решения задач нелинейного программирования. Эта работа послужила основой для последующих исследований в этой области.

Имеются проблемы, в которых связи заведомо не являются линейными.

Источники нелинейности относятся в основном к одной из двух категорий:

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

2) установленные (постулируемые) руководством правила поведения или задаваемые зависимости, например: формулы или правила расчета с потребителями энергии или других видов услуг; эвристические правила определения страховых уровней запаса продукции; гипотезы о характере вероятностного распределения рассматриваемых в модели случайных величин; различного рода договорные условия взаимодействия между партнерами по бизнесу и др.

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

НЕЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ (НЛП) - раздел математического программирования, посвященный теории и методам решения задач оптимизации нелинейных функций на множествах, задаваемых нелинейными ограничениями (равенствами и неравенствами).

В общем виде задача НЛП описывается с помощью следующей модели нелинейного программирования:

(1)

(2)

(3)

где х = (x₁, х₂,..., х_n) - вектор переменных задачи.

Задача (1) - (3) называется задачей нелинейного программирования в стандартной форме на максимум.

Может быть сформулирована также задача НЛП на минимум.

Вектор х = (x₁, х₂,..., х_n), компоненты х_j которого удовлетворяют ограничениям (2) и (3), называется допустимым решением или допустимым планом задачи НЛП.

Совокупность всех допустимых планов называется множеством допустимых планов.

Допустимое решение задачи НЛП, при котором целевая функция (1) достигает максимального значения, называется оптимальным решением задачи НЛП.

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

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

1. По количеству локальных критериев в целевой функции методы НЛП делятся на:

· однокритериальные,

· многокритериальные.

2. По длине вектора методы делятся на:

· однопараметрические или одномерные (n=1),

· многопараметрические или многомерные (n>1).

3. По наличию ограничений методы НЛП делятся на:

· без ограничений (безусловная оптимизация),

· с ограничениями (условная оптимизация).

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

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

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

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

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

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

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

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

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

· выпуклое программирование,

· квадратичное программирование,

· целочисленное программирование,

· стохастическое программирование,

· динамическое программирование и др.

Задачи выпуклого программирования – это задачи, в которых определяется минимум выпуклой функции (или максимум вогнутой), заданной на выпуклом замкнутом множестве. Эти задачи среди задач нелинейного программирования наиболее изучены.

Среди задач выпуклого программирования более подробно изучены задачи квадратичного программирования. В этих задачах целевая функция – квадратична, а ограничения – линейны.

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

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

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

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

Таблица 1. Классификация моделей по ее элементам.

Исходные данные	Переменные	Зависимости	Задача
Детерминиро-ванные	Непрерывные	Линейные	Линейного программирования
Целочисл. (дискретные)	Линейные	Целочисленного пр.
Непрерывные, целочисл.	Нелинейн.	Нелинейного пр.
Случайные	Непрерывные	Линейные	Стохастического пр.

Графический метод нелинейного программирования

Задачи НЛП обладают свойствами, которые усложняют процесс их решения по сравнению с задачами линейного программирования:

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

2. Глобальный максимум (минимум) может достигаться как внутри множества G, так и на его границах (где он, вообще говоря, будет не совпадать ни с одним из локальных экстремумов).

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

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

Рассмотрим графический метод решения задач НЛП. Его алгоритм такой же, как и для решения задач линейного программирования.

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

Если количество переменных в неравенствах, задающих область допустимых планов задач, равно 2, то ее можно изобразить на координатной плоскости. Каждое неравенство определяет некоторую полуплоскость. Пересечение данных полуплоскостей G является областью допустимых планов задач. Поведение целевой функции в рамках двумерной иллюстрации может быть охарактеризовано с помощью линии уровня.

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

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

Чтобы найти оптимальное решение задачи НЛП, нужно выполнить следующие действия:

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

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

3. При решении задачи на минимум определить направление убывания, а для задачи на максимум - направление возрастания линий уровня ЦФ.

4. Найти точку ОДР, через которую проходит линия уровня с наименьшим в задаче на минимум (соответственно, наибольшим в задачи на максимум) значением параметра С. Эта точка будет оптимальным решением. Если ЦФ не ограничена снизу в задаче на минимум (сверху — в задаче на максимум), то это означает, что задача не имеет оптимального решения.

5. Найти координаты точки оптимума и определить в ней значение ЦФ.

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

Возможен и случай касания линии уровня грани (линии) множества G, соответственно, все точки, лежащие на этой грани, будут являться альтернативными оптимальными планами.

Заметим, что аналогичным образом могут быть построены интерпретации задач нелинейного программирования для случая трехмерного пространства R³, где множеству G будет соответствовать некоторый ограниченный или неограниченный многогранник, а поведение целевой функции будет характеризоваться поверхностями (плоскостями) уровня.

Этот метод может быть применен не только к задачам с двумя или тремя переменными и ограничениями в виде неравенств, но и к задачам, у которых i - k =2 (i - количество ограничений, k - количество неизвестных).

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

Рассмотрим примеры решения задач НЛП графическим методом.

Задача №1. Решить следующий пример графическим методом:

Решение. Область допустимых решений – окружность с центром в точке х₁=13, х₂=-3 и радиусом = 13.

Ответ: ; .

Задача №2. На предприятии имеется два вида ресурсов. Определите оптимальное распределение величин затрачиваемых ресурсов на производство некоторого продукта, если цена ресурса первого вида 3 единицы, второго – 4 единицы, а всего на производство выделено 24 единицы. Известно, что из количества х первого ресурса и у второго ресурса можно получить единиц продукта.

Решение. Пусть х - количество ресурсов первого вида, у - количество ресурсов второго вида. Математическая модель задачи: на множестве ограничений

Если целевой функции придавать фиксированные значения 1, 2, 3,..., то будем получать окружности с центром в начале координат и радиусом 1, 2, 3,… Начертим ряд окружностей (линии уровня целевой функции). Из рисунка будет видно, что функция z = достигает наибольшего значения, равного 8, в точке А (8; 0), т.е. z_max=z (8; 0)=8. Значит, количество первого ресурса должно равняться 8, а использование второго ресурса нерационально.