Главная Обратная связь

Дисциплины:

Архитектура (936)
Биология (6393)
География (744)
История (25)
Компьютеры (1497)
Кулинария (2184)
Культура (3938)
Литература (5778)
Математика (5918)
Медицина (9278)
Механика (2776)
Образование (13883)
Политика (26404)
Правоведение (321)
Психология (56518)
Религия (1833)
Социология (23400)
Спорт (2350)
Строительство (17942)
Технология (5741)
Транспорт (14634)
Физика (1043)
Философия (440)
Финансы (17336)
Химия (4931)
Экология (6055)
Экономика (9200)
Электроника (7621)






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



 

Без ограничений и не отрицательность переменных

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

Z = f (x1 ,x2 ,…, xn ) max.

 

(3.1)
Необходимое условие экстремума целевой функции f (x1 ,x2 ,…, xn ) заключается в следующем. Пусть f дифференцируема и имеет экстремум в некоторой точке. Тогда в этой точке будут верны такие равенства:

. . . ,

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

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

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

(3.2)
Задача вида

Z = f (x1 ,x2 ,…, xn ) max

xj ≥ 0 ; j=1,2,…,n,

где f (x1 ,x2 ,…, xn ) - выпуклая (вогнутая) функция, называется задачей ВП с неотрицательными переменными.

Сформулируем условия для определения наибольшего значения функции f в задаче(3.3). Внутри области (xj 0) необходимым условием экстремума является равенство нулю частных производных функции f : =0. На границе области (xj = 0) частные производные удовлетворяют условию ≤ 0, если f вогнутая функция.

Примеры возможных решений задачи максимизации функции одной неотрицательной переменной иллюстрируют все возможные решения задачи в одномерном случае(рис.1-3). Если решение внутри области(x0 > 0), то производная =0 .Рассмотрим решение задачи максимизации функции f. Предположим, что ее решение x0 находится внутри области определения. В этом случае производная функции f в точке максимума x0 равна нулю. Данная ситуация отражена на рис. 1

 

 

y y y

fx'(x0)=0 ≤0 < 0

 


 

0 x0>0 x 0 x0=0 x 0 x0=0 x

рис. 1 рис. 2 рис. 3

Возможны также случаи расположения решения x0 на границе области. При нахождении наибольшего значения в этом случае производная функции f в точке x0 может быть неположительной (рис.2). Такая ситуация возникает при выпуклости максимизируемой функции. Производная функции f в точке x0 может быть и отрицательной (рис. 3).Это будет в случае, когда максимизируемая функция будет вогнутой.



Все случаи расположения решения x0 на границе области определения функции f можно обобщить в виде неравенства: ≤0.

Все эти случаи можно отразить в виде равенства нулю произведения x0 на ,то есть в виде равенства x0 = 0.

Следовательно, для одномерной функции необходимое условие экстремума

x0 = 0.

Аналогично рассуждая, можно сформулировать необходимое условие экстремума функции n переменных, оно будет иметь вид xj =0; j=1,2,…,n,

где xj ≥ 0, ≤ 0. Причем, если xj 0, то =0, если, xj = 0, то ≤ 0.

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

 

Ограничения типа равенств.

(3.3)
Задача выпуклого программирования в случае ограничений в виде равенств имеет вид

Z = f (x1 ,x2 ,…, xn ) max,

 

(3.4)
1(x1 ,x2 ,…, xn ) = 1,

2(x1 ,x2 ,…, xn ) = 2,

- - - - - - - - - - - - - - -

m(x1 ,x2 ,…, xn ) = m,

Для ее решения будем использовать метод множителей Лагранжа. Пусть λ1, λ2,…, λm - некоторые числа. Составим функцию Лагранжа :

(x1 ,x2 ,…, xn, λ1, λ2,…, λm ) = f (x1 ,x2 ,…, xn ) + i [b1 - 1(x1 ,x2 ,…, xn )].

 

Задача на нахождение условного экстремума функции f сводится к задаче нахождения безусловного экстремума функции Лагранжа .

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

= - i = 0,

(3.5)


= - i = 0,

- - - - - - - - - - - - - - - - - - - - - - - - -

= - i = 0,

= b1 - 1(x1 ,x2 ,…, xn ) = 0,

= b2 - 2(x1 ,x2 ,…, xn ) = 0,

- - - - - - - - - - - - - - - - - - - - - - - - - - -- - - - - - -



= bm - m(x1 ,x2 ,…, xn ) =0.

 

Получили систему n + m уравнений с n + m неизвестными x1 ,x2 ,…, xn ; λ1, λ2,…, λm. Для выпуклых (вогнутых) функций решение системы уравнений единственное (если конечно, оно вообще существует). Пусть решением системы является следующая совокупность значений переменных: xo 1, xo2,…, xon ; λo1, λo2,…, λom. Это решение, дающее экстремум функции Лагранжа, состоит из двух частей:

оптимальное решение задачи xo=(xo 1,xo2,…, xon) и оптимальный вектор множителей Лагранжа λo=(λo1, λo2,…, λom).

Вообще-то нам необходимо было найти оптимальное решение задачи (3.3), (3.4), то ест решение xo. Но, как увидим далее, значения множителей Лагранжа, соответствующие оптимальному плану xo, не являются излишними. Напротив, с их помощью можно получить дополнительную ценную информацию об оптимальном xo. Остановимся на значении множителей Лагранжа в плановой практике.

Пусть условия (3.3), (3.4) отражают следующую задачу производства x1 ,x2 ,…, xn для некоторого предприятия, который обеспечивал бы ему максимум прибыли f (x1 ,x2 ,…, xn )

и соответствовал бы балансу потребности и лимита по всем видам производственных ресурсов. Если потребность в ресурсе на предприятии составляет i(x1 ,x2 ,…, xn ) единиц, лимит этого ресурса составляет bi единиц, то можно утверждать, что план производства должен удовлетворять равенствам

i (x1 ,x2 ,…, xn ) = bi , i=1,2,…,m.

Очевидно, что оптимальное решение задачи (3.3) и (3.4) зависит от правых частей ограничений (3.4). Это значит, что компоненты оптимального плана xo 1,xo2,…, xon зависят от лимитов ресурсов b1, b2,…, bm. Понятно, что и оптимальное значение целевой функции

Zo= f (xo1,xo2,…, xon) также будет зависеть от b1, b2,…, bm. Найдем числовое выражение зависимости оптимального значения целевой функции Z от лимитов ресурсов b1, b2,…, bm.

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

Докажем, что = λoi , i=1,2,…,m.

Компоненты оптимального плана xoj есть некоторые функции от bi , i=1,2,…,m:

xoj = xoj (b1, b2,…, bm) , j=1,2,…,n.

Поэтому Zo есть сложная функция вида

Zo= Zo(b1, b2,…, bm)= Zo[xo1(b1, b2,…, bm),…, xon(b1, b2,…, bm)].

Используя правило дифференцирования сложной функции, получим

(3.6)
= .

Продифференцируем левую и правую части равенства fk (xo1,xo2,…, xon)=bk по bi, получим

(3.7)
= = = 1, 2, если k = i если k ≠ i.

Умножим на λok и просуммируем по k, получим

λoi - ok = ok .

Отсюда имеем

(3.8)
λoi - ok = 0.

Сложив(3.6) и (3.8), получим

(3.9)
= λoi + - ok .

 

 

Два последних слагаемых в первой части (3.9) вместе равны нулю. Покажем это:

- ok = - ok =

= ( - ok ).

Но согласно необходимому условию экстремума функции Лагранжа

(3.10)
- ok = 0,

(3.11)
поэтому два последних слагаемых в правой части равенства (3.9) в сумме дают ноль. Отсюда следует равенство = λoi , i=1,2,…,m.

Таким образом, метод множителей Лагранжа, помимо того, что дает решение задачи ВП с ограничениями в виде равенств, позволяет также проанализировать, насколько оптимальное значение целевой функции чувствительно к изменениям констант ограничений. Например, если какой-то множитель Лагранжа равен нулю, то небольшие изменения соответствующей константы ограничений не окажут никакого влияния на оптимальное значение целевой функции. Если некоторая константа bi увеличится на одну единицу, то при λoi >0 множитель Лагранжа λoi показывает, что оптимальное значение целевой функции Zo увеличится на λoi единицу (в задаче на максимум). Обратим внимание на то, что при этом нет необходимости решать новую задачу ВП, у которой правая часть ограничения i равна bi + 1.

В целом можно сделать вывод, что практическое значение равенства (3.11) в том, что мы легко можем оценить, как изменится оптимальное значение целевой функции при малом изменении лимитов ресурсов. По-другому говоря, множители Лагранжа λoi являются оценками ресурсов b1, b2,…, bm.

 

 


Эта страница нарушает авторские права

allrefrs.ru - 2019 год. Все права принадлежат их авторам!