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

РОССИЙСКАЯ ФЕДЕРАЦИЯ

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ

ФГБОУ ВПО «ТЮМЕНСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ»

ИНСТИТУТ ДИСТАНЦИОННОГО ОБРАЗОВАНИЯ

Специальность «Государственное и муниципальное управление»

 

 

 

К О Н Т Р О Л Ь Н А Я    Р А Б О Т А

 

 

По дисциплине: «Основы математического моделирования социально-экономических процессов»

 

По теме: Нелинейное программирование

 

 

 

 

Выполнил:

студентка 4  курса, 7 семестр,

Немчинова Галина Геннадьевна

 

 

сентябрь, 2014

 

Содержание:

 

Введение

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

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

 

1. Постановка задачи  нелинейного программирования

В задаче нелинейного программирования (НЛП) требуется найти значение многомерной переменной х=( ), минимизирующее целевую функцию f(x) при условиях, когда на переменную х наложены ограничения типа неравенств

 

, i=1,2,…, m        (1)

 

а переменные , т.е. компоненты вектора х, неотрицательны:

 

         (2)

 

Иногда в формулировке задачи ограничения (1) имеют противоположные знаки неравенств. Учитывая, однако, что если , то , всегда можно свести задачу к неравенствам одного знака. Если некоторые ограничения входят в задачу со знаком равенства, например , то их можно представить в виде пары неравенств , , сохранив тем самым типовую формулировку задачи.

 

 

2. Критерии оптимальности  в задачах с ограничениями

Ряд инженерных задач связан с оптимизацией при наличии некоторого количества ограничений на управляемые переменные. Такие ограничения существенно уменьшают размеры области, в которой проводится поиск оптимума. На первый взгляд может показаться, что уменьшение размеров допустимой области должно упростить процедуру поиска оптимума. Между тем, напротив, процесс оптимизации становится более сложным, поскольку установленные выше критерии оптимальности нельзя использовать при наличии ограничений. При этом может нарушаться даже основное условие, в соответствии с которым оптимум должен достигаться в стационарной точке, характеризующейся нулевым градиентом. Например, безусловный минимум функции имеет место в стационарной точке х=2. Но если задача минимизации решается с учетом ограничения , то будет найден условный минимум, которому соответствует точка x=4. Эта точка не является стационарной точкой функции f, так как (4)=4. Далее исследуются необходимые и достаточные условия оптимальности решений задач с ограничениями. Изложение начинается с рассмотрения задач оптимизации, которые содержат только ограничения в виде равенств.

2.1 Задачи с ограничениями в виде  равенств

Рассмотрим общую задачу оптимизации, содержащую несколько ограничений в виде равенств:

Минимизировать

при ограничениях , k=1,…, n

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

Пример 1

Минимизировать

при ограничении

Исключив переменную , с помощью уравнения , получим

оптимизационную задачу с двумя переменными без ограничений

min

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

2.2 Множители Лагранжа

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

Рассмотрим задачу минимизации функции n переменных с учетом одного ограничения в виде равенства:

Минимизировать

      (3)

при ограничениях

      (4)

В соответствии с методом множителей Лагранжа эта задача преобразуется в следующую задачу безусловной оптимизации:

минимизировать

L (x, u)=f(x) – u*h(x)     (5)

Функция L (х; u) называется функцией Лагранжа, u – неизвестная постоянная, которая носит название множителя Лагранжа. На знак u никаких требований не накладывается.

Пусть при заданном значении u=u0 безусловный минимум функции L (x, u) по х достигается в точке и удовлетворяет уравнению . Тогда, как нетрудно видеть, x0 минимизирует (1) с учетом (4), поскольку для всех значений х, удовлетворяющих (4), и L (x, u)=min f(x).

Разумеется, необходимо подобрать значение u=u° таким образом, чтобы координата точки безусловного минимума х° удовлетворяла равенству (4). Это можно сделать, если, рассматривая u как переменную, найти безусловный минимум функции (5) в виде функции u, а затем выбрать значение u, при котором выполняется равенство (4). Проиллюстрируем это на конкретном примере.

Пример 2

Минимизировать

при ограничении =0

Соответствующая задача безусловной оптимизации записывается в следующем виде:

минимизировать L (x, u)= -u

Решение. Приравняв две компоненты градиента L к нулю, получим

Для того чтобы проверить, соответствует ли стационарная точка х° минимуму, вычислим элементы матрицы Гессе функции L (х; u), рассматриваемой как функция х,

,

которая оказывается положительно определенной. Это означает, что L (х, u) – выпуклая функция х. Следовательно, координаты , определяют точку глобального минимума. Оптимальное значение u находится путем подстановки значений и в уравнение =2, откуда 2u+u/2=2 или . Таким образом, условный минимум достигается при и и равен min f(x)=4/5.

При решении задачи из примера 2 мы рассматривали L (х; u) как функцию двух переменных и и, кроме того, предполагали, что значение параметра u выбрано так, чтобы выполнялось ограничение. Если же решение системы

 

, j=1,2,3,…, n

в виде явных функций u получить нельзя, то значения х и u находятся путем решения следующей системы, состоящей из n+1 уравнений с n+1 неизвестными:

 

, j=1,2,3,…, n

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

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

Минимизировать f(x)

при ограничениях =0, k=1, 2,…, К.

Функция Лагранжа принимает следующий вид:

L (x, u)=f(x)-

Здесь –множители Лагранжа, т.е. неизвестные параметры, значения которых необходимо определить. Приравнивая частные производные L по х к нулю, получаем следующую систему n уравнении с n неизвестными:

 

……….

 

Если найти решение приведенной выше системы в виде функций вектора u оказывается затруднительным, то можно расширить систему путем включения в нее ограничений в виде равенств

Решение расширенной системы, состоящей из n+К уравнений с n+К неизвестными, определяет стационарную точку функции L. Затем реализуется процедура проверки на минимум или максимум, которая проводится на основе вычисления элементов матрицы Гессе функции L, рассматриваемой как функция х, подобно тому, как это было проделано в случае задачи с одним ограничением. Для некоторых задач расширенная система n+К уравнений с n+K неизвестными может не иметь решений, и метод множителей Лагранжа оказывается неприменимым. Следует, однако, отметить, что такие задачи на практике встречаются достаточно редко.

 

3. Условия Куна-Таккера

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

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

минимизировать

         (0)

при ограничениях

       (1)

      (2)

Определение:

Ограничение в виде неравенства называется активным, или связывающим, в точке , если , и неактивным, или несвязывающим, если

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

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

3.1 Условия Куна–Таккера и задача Куна–Таккера

Найти векторы , удовлетворяющие следующим условиям

 

    (3)

     (4)

      (5)

     (6)

      (7)

 

Прежде всего проиллюстрируем условия Куна – Таккера на примере.

Пример 3

Минимизировать

при ограничениях

Решение.

Записав данную задачу в виде задачи нелинейного программирования (0) – (2), получим:

 

 

Уравнение (3), входящее в состав условий Куна–Таккера, принимает следующий вид:

 

 

откуда

 

Неравенства (4) и уравнения (5) задачи Куна – Таккера в данном случае записываются в виде

 

Уравнения (5.16), известные как условие дополняющей нежесткости, принимают вид

 

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

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

 

3.2 Интерпретация условий Куна –  Таккера

Для того чтобы интерпретировать условия Куна – Таккера, рассмотрим задачу нелинейного программирования с ограничениями в виде равенств:

минимизировать

при ограничениях

Запишем условия Куна–Таккера

 

     (8)

      (9)

Далее рассмотрим функцию Лагранжа для задачи нелинейного программирования с ограничениями в виде равенств:

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

Нетрудно видеть, что условия Куна-Таккера (8) и (9) совпадают с условиями оптимальности первого порядка для задачи Лагранжа.

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

минимизировать

при ограничениях

Запишем условия Куна–Таккера

 

 

Соответствующая функция Лагранжа имеет вид

 

Условия оптимальности первого порядка записываются как

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

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