Исследование операций / ИСО Учебник
.pdfРаздел 2. Нелинейные и специальные модели исследования операций
ТЕМА 2.1. НЕЛИНЕЙНОСТЬ В ЭКОНОМИЧЕСКИХ ПРОЦЕССАХ
Лекция 2.1.1. Постановка задачи и методы решения для моделей нелинейного программирования
Во многих экономических исследованиях операций зависимости между постоянными и переменными факторами при более детальном рассмотрении оказываются нелинейными. Как правило, в теории управления такие показатели, как прибыль, себестоимость, совокупные транспортные затраты, капитальные затраты на производство, зависят от объема производства (расходы ресурсов, объема перевозок и др.) нелинейно. В этом случае возникает задача нелинейного программирования, математическая модель которой в векторной форме может быть представлена как определение максимального (минимального) значения функции f (x1 , x2 ,...xn ) :
max f (x)= max f (x1 , x2 ,...xn ) |
или min f (x)= min f (x1 , x2 ,...xn ) |
(2.1) |
при условии, что её переменные удовлетворяют соотношениям |
|
|
gi (x1, x2 ,...xn ) ≤ bi |
(i =1,...,k) , |
(2.2) |
gi (x1, x2 ,...xn ) = bi |
(i = k +1,..., m), |
(2.3) |
где f и gi — некоторые известные функции n переменных, а bi — заданные числа. Функции f и gi(x) — нелинейные.
Сведение задачи условной оптимизации к безусловной
Данный метод применим для случая, если задача имеет ограничения только типа равенств, т. е. (2.3). Суть этого метода состоит в том, что за счет ограничений-равенств в задачи уменьшается число переменных.
71
Будем считать, что система из m ограничений относительно n перемен-
ных
gi (x)−bi = 0, i =1,2,...,m |
(2.4) |
может быть разрешима относительно части своих переменных. Не нарушая общности, можно считать, что в системе (2.4) переменные x1, x2 ,..., xm — зависимые, а xm , xm+1,..., xn — независимые. В этом случае из системы (2.4) получим выражения для зависимых переменных через независимые:
x j =ϕj (xm+1, xm+2 ,..., xn ), j =1, 2,..., m. |
(2.5) |
Подставляя (2.4) в (2.5), получим новую задачу: |
|
max f (ϕ1(xm+1,..., xn ),...,ϕm (xm+1,..., xn ), xm+1,..., xn ), |
(2.6) |
в которой оптимизируемая функция уже зависит от n – m переменных.
Пример. Найти минимум функции x12 + x22 + x1 − x2 + x3 −2x4 + x5 , если x1 + x2 + x3 = 5,
x1 + 2x2 + x3 + x4 =10,
5x1 +5x2 +3x3 + x4 + x5 = 25, x1,..., x5 ≥ 0.
Решение. В задаче требуется найти минимум функции относительно пяти переменных, определенных на множестве с тремя ограничениями. Следовательно, две переменные будут независимыми, а три — зависимыми. Пусть зависимыми переменными будут x3, x4 и x5. Из ограничений найдем
x |
= 5 − x |
− x |
2 |
≥ 0 |
|||
|
3 |
1 |
|
|
|
||
x4 = 5 − x2 ≥ 0 |
|
|
. |
||||
x |
= 5 +8x |
|
− x |
2 |
≥ 0 |
||
|
5 |
1 |
|
|
|
||
72
Подставив найденные выражения для x3, x4 и x5 в функцию f(x), полу- |
||||||||||||||||||
чим |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
min |
f (x) = min |
x2 |
+ x2 |
+ x − x |
+ |
(5 − x − x |
)− 2(5− x |
)+(5 +8x − x |
) |
) |
= |
|||||||
x , x ≥ 0 |
x , x ≥ 0 ( |
1 |
2 |
|
1 |
2 |
|
|
1 |
2 |
2 |
1 |
2 |
|
|
|||
1 |
2 |
1 |
2 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
= min |
x2 + x2 |
+8x − x |
|
|
|
|
|
||||||
|
|
|
|
|
|
x , x ≥ 0 ( |
1 |
2 |
|
1 |
|
2 ) |
|
|
|
|
|
|
|
|
|
|
|
|
1 |
2 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
при ограничениях |
|
|
|
|
|
||||||
|
|
|
|
|
|
|
5 − x1 − x2 ≥ 0 |
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
5 − x2 |
≥ 0 |
|
≥ 0 . |
|
|
|
|
|
|
||
|
|
|
|
|
|
|
5 + 8x |
− x |
2 |
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
x1 ≥ 0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
x2 ≥ 0 |
|
|
|
|
|
|
|
|
|
|
|
Далее эту задачу можно решить графически (рис. 2.1). |
|
|
|
|
|
|||||||||||||
|
|
|
|
|
|
|
|
x2 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
5 |
|
|
|
x2=5 |
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
x |
|
|
|
|
|
|
|
|
2 |
|
|
|
2 |
|
|
|
|
|
1+ |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
x |
|
|
|
|
|
||
|
|
(x +4) +(x -1/2) =65/4 |
|
|
|
|
2 |
|
|
|
|
|
||||||
|
|
|
|
|
|
= |
|
|
|
|
|
|||||||
|
|
1 |
|
|
2 |
|
|
|
|
|
|
|
5 |
|
|
|
|
|
|
|
|
|
|
8x1-x2=5 |
|
|
|
|
5 |
x1 |
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
Рис. 2.1. Графическое решение задачи |
|
|
|
|
|
|||||||||
73
Т. к. минимизируемая функция после преобразования стала квадратич-
ной относительно двух переменных: f (x |
, x |
|
2 |
|
|
− |
1 |
|
2 |
65 |
, то из |
|
)= (x + 4) |
+ x |
|
2 |
|
− |
4 |
||||
1 |
|
2 |
1 |
|
2 |
|
|
|
|
ее вида следует, что она будет принимать наименьшее значение при x1=0 и x2=1/2. Возвращаясь к исходной задаче, получим ответ:
x* = 0, |
x* |
= |
1 |
, |
x* = 5 − 0 − |
1 |
= |
9 |
, |
x* |
= 5 − |
1 |
= |
9 |
, |
x* = 5 + 0 − |
1 |
= |
9 |
, |
1 |
2 |
|
2 |
|
3 |
2 |
|
2 |
|
4 |
|
2 |
|
2 |
|
5 |
2 |
|
2 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
f * = 654 .
Метод множителей Лагранжа
Рассмотрим частный случай общей задачи нелинейного программирования, предполагая, что система ограничений содержит только уравнения, отсутствуют условия неотрицательности переменных и
f (x1, x2 ,...xn ) → max(min);
gi (x1, x2 ,...xn ) = bi (i =1,...,m).
В курсе математического анализа данную задачу называют задачей на условный экстремум или классической задачей оптимизации. Чтобы найти решение этой задачи, вводят набор переменных λ1 ,λ2 ,...,λm , называемых множителями Лагранжа, и составляют функцию Лагранжа
|
|
|
|
m |
|
F(x1, x2 ,..., xn ,λ1,λ2 ,...,λm ) = f (x1, x2 ,..., xn ) + ∑λi [bi − gi (x1, x2 ,..., xn )]. (2.7) |
|||||
|
|
|
|
i =1 |
|
Далее находят частные производные |
|
|
|||
|
∂F |
( j =1,...,n) и |
∂F |
(i =1,...,m) |
|
|
|
∂λ |
|||
|
∂x |
j |
|
||
|
|
i |
|
||
74
и рассматривают систему n+m уравнений: |
|
|||||
|
∂F |
|
∂f |
m |
∂gi = 0 |
|
|
= |
− ∑λi |
||||
∂x j |
∂x j |
|||||
|
|
i =1 |
∂x j |
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
∂F |
|
|
|
|
|
|
= bi − gi (x1, x2 ,..., xn ) = 0 |
|||||
|
∂λ |
|||||
|
i |
|
|
|
|
|
с n+m неизвестными x1, x2 ,..., xn ,λ1,λ2 ,...,λm . Всякое решение системы урав-
нений определяет точку X Т = (x1, x2 ,..., xn ), в которой может иметь место экстремум функции f (x1, x2 ,..., xn ) . Следовательно, решив данную систему уравнений, получают все точки, в которых указанная функция может иметь экстремальные значения. Дальнейшее исследование найденных точек проводят так же, как и в случае безусловного экстремума.
Таким образом, определение экстремальных точек задачи методом множителей Лагранжа включает следующие этапы:
—составляют функцию Лагранжа;
—находят частные производные от функции Лагранжа по переменным
xj и λi , приравнивают их к нулю;
—решая данную систему уравнений, находят точки, в которых целевая функция задачи может иметь экстремум;
—среди точек, подозрительных на экстремум, находят такие, в которых достигается экстремум, и вычисляют значение функции в этих точках.
75
Лекция 2.1.2. Постановка задачи и методы решения для моделей выпуклого программирования
Теперь рассмотрим задачу нелинейного программирования с условиями неотрицательности переменных:
f (x1, x2 ,..., xn ) → max |
|
gi (x1, x2 ,..., xn ) −bi ≥ 0 (i =1,..., m) |
(2.8) |
x j ≥ 0 ( j =1,..., n) , |
|
где f и gi — некоторые нелинейные функции n переменных x1, x2 ,..., xn .
Для решения сформулированной задачи в такой общей постановке не существует универсальных методов. Однако для отдельных классов задач, в которых сделаны дополнительные ограничения относительно свойств функций f и gi, есть эффективные методы решения. В частности, ряд таких методов имеется для решения задач нелинейного программирования при условии, что f — вогнутая (выпуклая) функция и область допустимых решений, определяемая ограничениями, выпуклая.
Множество U En является выпуклым, если вместе с любыми двумя точками x(1)и x(2) из этого множества U, ему принадлежит и отрезок, их соединяющий:
αx(1) + (1 −α)x(2) U , α [0;1]
x1
x2
Рис. 2.2. Пример выпуклого множества
76
Функция f (x) является выпуклой на выпуклом множестве U E n , если для любых двух точек x(1), x(2) U выполняется неравенство Иенсена:
f (α x(1) +(1−α)x(2))≤ α f (x(1))+(1−α)f (x(2)) |
0 <α <1 |
Для дифференцируемых функций удобней использовать другое определение выпуклой функции.
Функция f (x) является выпуклой в точке x*, если матрица ее вторых частных производных (матрица Гессе)
|
∂2 |
f (x ) |
|
|
|
|
|
∂x1∂x1 |
|||
∂2 |
f (x ) |
||
H (x )= |
|
|
|
∂x |
∂x |
||
|
|
2 |
1 |
|
|
|
|
∂2 |
f (x ) |
||
|
|
|
|
∂x |
∂x |
||
|
|
n |
1 |
∂2 f (x ) |
… |
∂2 f (x ) |
|
||
∂x1∂x2 |
|
||||
|
∂x1∂xn |
||||
∂2 f (x ) |
… |
∂2 f (x ) |
|||
|
|
|
|
|
|
∂x |
∂x |
∂x |
∂x |
||
2 |
2 |
|
2 |
n |
|
|
|
|
|
|
|
∂2 f (x ) |
… |
∂2 f (x ) |
|||
|
|
|
|
|
|
∂x |
∂x |
∂x |
∂x |
||
n |
2 |
|
n |
n |
|
положительно определена.
Для функции одной переменной это означает, что функция f (x) лежит ниже хорды, соединяющей любые две точки ее графика.
Функцией Лагранжа задачи выпуклого программирования называется функция
m
L(x1, x2 ,..., xn , y1, y2 ,..., ym ) = f (x1, x2 ,..., xn ) + ∑yi [bi − gi (x1, x2 ,..., xn )]
i =1
где y1, y2 ,..., ym — множители Лагранжа.
Точка (X 0 ;Y0 )T = (x10 , x20 ,..., xn0 ; y10 , y20 ,..., ym0 ) называется седловой точ-
кой функции Лагранжа, если
L(x ,..., x |
n |
, y0 |
,..., y0 ) ≤ L(x0 |
,..., x0 |
; y0 |
,..., y0 ) ≤ L(x0 |
,..., x0 |
; y ,..., y |
m |
) |
(2.9) |
|||
1 |
1 |
|
m |
1 |
n |
1 |
m |
1 |
n |
1 |
|
|
||
для всех x j |
≥ 0 |
( j =1,..., n) |
и yi ≥ 0 (i =1,..., m) . |
|
|
|
|
|||||||
77
Говорят, что выполняется условие регулярности, если существует, по крайней мере, одна точка X0T = (x10 , x20 ,..., xn0 ) , для которой gi( X0T )>0 для всех i.
ТЕОРЕМА (теорема Куна — Таккера). Для задачи выпуклого программирования, множество допустимых решений которой обладает свой-
ством регулярности, X 0 = (x10 , x20 ,..., xn0 ) является оптимальным планом для
(3.8) тогда и только тогда, когда существует такой вектор
Y = ( y0 |
, y0 |
,..., y0 ), |
( y0 |
≥ 0,i =1,..., m) , что |
(X |
0 |
;Y )T |
— седловая точка функ- |
|
0 |
1 |
2 |
m |
i |
|
|
0 |
|
|
ции Лагранжа.
Если предположить, что целевая функция f и функции gi непрерывно дифференцируемы, то теорема Куна — Таккера может быть дополнена аналитическими выражениями, определяющими необходимые и достаточные условия того, чтобы точка (X 0 ;Y0 ) была седловой точкой функции Лагранжа,
т. е. являлась решением задачи выпуклого программирования. Эти выраже-
ния имеют следующий вид (условия для задачи на максимум): |
|
∂L0 ≤ 0 |
( j =1,..., n), |
∂x j |
|
x0j T ∂L0 = 0 |
( j =1,...,n), |
∂x j |
|
x0j ≥ 0 |
( j =1,...,n), |
|
|
∂L0 |
≥ 0 |
(i =1,..., m), |
(2.10) |
|
|||
∂yi |
|
||
|
|
||
78
|
|
|
yi0 T |
∂L0 |
= 0 (i =1,..., m), |
|
|
|
|
∂yi |
|||
|
|
|
|
|
|
|
|
|
|
y0 |
≥ 0 |
(i =1,..., m), |
|
|
|
|
i |
|
|
|
где |
∂L0 |
и |
∂L0 — значения соответствующих частных производных функций |
|||
|
∂x j |
|
∂yi |
|
|
|
Лагранжа, вычисленных в седловой точке.
Итак, процесс нахождения решения задачи выпуклого программирования включает следующие этапы:
—проверка на принадлежность задачи выпуклому программированию;
—составляют функцию Лагранжа;
—записывают необходимые и достаточные условия существования седловой точки для функции Лагранжа;
—находят координаты седловой точки функции Лагранжа (проверяя, будет ли найденная точка являться точкой максимума), либо устанавливают ее отсутствие;
—записывают оптимальное решение и находят значение целевой функции.
Пример. Найти min(x12 − x2 )при ограничениях
x ≥1, |
x2 |
+ x2 |
≤10, x |
2 |
≥ 0 (рис. 2.3). |
1 |
1 |
2 |
|
|
Решение. Графическое решение задачи представлено на рис. 2.3.
Рассмотрим теперь аналитическое решение. Составим функцию Лагранжа.
g1(x)=1− x1,
g2 (x)= −10 + x12 + x22 ,
g3 (x)= −x2 ,
L(x,λ)= x12 − x2 + λ1(1− x1 )+ λ2 (−10 + x12 + x22 )−λ3 x2.
79
|
|
|
|
f(x)=x1 |
2+C, C=-2 |
|
|
||||
x2 |
|
|
|
f(x)=x1 |
2+C, C=-1 |
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
4 |
x1=1 |
|
|
f(x)=x1 |
2+C, C=0 |
|
|
||||
3 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
2 |
|
|
|
|
|
|
|
|
|
|
|
1 |
|
|
|
|
|
|
x1 |
2+x2 |
2=10 |
|
|
A |
|
|
|
|
|
|
|
|
|
|
|
0 |
1 |
2 |
|
|
3 |
|
4 |
5 x1 |
|
||
Рис. 2.3. Графическое решение задачи
Выписываем систему необходимых и достаточных условий существования седловой точки для функции Лагранжа.
∂L |
2x1 + 2λ2 x1 |
− λ1 |
≥ 0 |
|
||
0 |
≥ 0 : |
+ 2λ2 x2 |
− λ3 ≥ 0 |
, |
||
∂x j |
||||||
−1 |
|
|||||
|
|
∂L0 |
|
1− x1 ≤ 0 |
|
|
|
|
||||||
|
|
≤ 0 : −10 + x2 + x2 ≤ 0 |
, |
|
|
|||||||||
|
|
|
|
|
|
|||||||||
|
|
∂λi |
|
|
|
|
|
1 |
2 |
|
|
|||
|
|
|
|
− x ≤ 0 |
|
|
|
|
||||||
|
|
|
|
|
|
|
|
2 |
|
|
|
|
|
|
x0j |
∂L |
= 0 : |
x1(2x1 + |
2λ2 x1 −λ1 )= 0 |
, |
|||||||||
0 |
|
|
|
|
|
|
|
|
||||||
|
∂x j |
|
|
x2 (−1+ 2λ2 x2 −λ3 )= 0 |
|
|||||||||
|
|
|
|
|
|
λ1(1 − x1 )= 0 |
|
|
|
|||||
λ0 |
∂L0 |
|
= 0 : |
λ |
2 |
(−10 |
+ x2 |
+ x2 ) |
= 0 |
, |
||||
∂λ |
||||||||||||||
i |
|
|
|
|
1 |
2 |
|
|||||||
|
|
i |
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
λ3x2 = 0 |
|
|
|
|
||||
|
|
|
|
|
|
x |
0 |
≥ 0 , |
λ0 |
≥ 0. |
|
|
|
|
|
|
|
|
|
|
|
j |
|
i |
|
|
|
|
|
80