2631761_42.1412840525.10196
.pdfставленной единицы товара равна 2 ден. ед., за каждую неудовлетворенную единицу заказанного товара взимается штраф в размере 10 ден. ед. Сравните минимальные суммарные транспортные издержки по доставке товара в случае, когда никаких дополнительных ограничений не накладывается, и в случае, когда второму потребителю должно быть поставлено не менее восьми единиц товара от третьего поставщика, а поставки от второго поставщика первому потребителю запрещены. Векторы a, b и матрица C таковы:
|
|
|
40 |
|
|
|
|
|
|
|
|
7 |
2 |
1 |
6 |
|
|
|
||||
а) a = |
|
30 |
|
|
, b = (20 35 25 50), |
C = |
|
1 |
4 3 5 |
|
; |
|
||||||||||
|
|
|
|
|
|
|||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
8 |
2 |
|
|
|
|
||
|
|
75 |
|
|
|
|
|
|
|
3 |
1 |
|
|
|||||||||
|
80 |
|
|
|
|
|
|
12 |
7 |
2 |
3 |
|
||||||||||
|
20 |
|
, b = (20 10 90 10), |
C = |
|
1 |
|
|
|
|
|
; |
||||||||||
б) a = |
|
|
4 10 11 |
|||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
3 |
13 |
|
|
|
||||
|
15 |
|
|
|
|
|
8 |
9 |
|
|||||||||||||
|
|
|
|
|
|
|
|
25 |
|
|
|
|
6 |
5 |
1 |
|
|
|
|
|
||
|
|
|
|
|
|
|
|
10 |
|
|
|
|
1 |
3 2 |
|
|
|
|
|
|||
в) a = |
|
|
, b = (70 20 15), |
C = |
|
; |
|
|
|
|||||||||||||
|
|
|
|
|
|
|
|
30 |
|
|
|
|
7 |
8 |
9 |
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
7 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
40 |
|
|
4 |
3 |
|
|
|
|
||||||
|
|
|
|
|
70 |
|
|
|
|
8 |
|
10 |
11 |
|
|
|
|
|||||
|
|
|
|
|
60 |
|
|
|
|
1 |
|
9 12 |
|
|
|
|
||||||
г) a = |
, b = (55 45 80), |
C = |
|
|
; |
|
|
|
||||||||||||||
|
|
|
|
|
50 |
|
|
|
10 |
7 |
9 |
|
|
|
|
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
4 |
|
|
|
|
|
|
|
|
|
|
|
|
40 |
|
|
5 |
|
15 |
|
|
|
|||||||||
|
40 |
|
|
|
|
|
|
|
1 |
4 |
1 |
9 |
|
|
||||||||
|
30 |
|
, b = (35 55 40 15), |
|
|
2 |
3 1 10 |
|
|
|||||||||||||
д) a = |
|
C = |
|
; |
||||||||||||||||||
|
80 |
|
|
|
|
|
|
12 |
7 |
8 |
4 |
|
|
|||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
11 |
2 |
|
|
|
|
|||
|
10 |
|
|
|
|
|
5 |
3 |
|
|||||||||||||
|
15 |
|
|
|
|
|
|
|
15 |
12 |
11 |
|
9 |
|
||||||||
|
35 |
|
|
|
|
|
|
|
|
9 |
|
10 7 6 |
|
|||||||||
е) a = |
, b = (70 30 25 70), |
C = |
|
|
. |
|||||||||||||||||
|
50 |
|
|
|
|
|
|
|
|
4 |
|
3 |
13 |
|
7 |
|
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
8 |
6 |
|
|
|
|||
60 |
|
|
|
|
|
|
10 |
10 |
151
ГЛАВА 5. МЕТОДЫНЕЛИНЕЙНОГОПРОГРАММИРОВАНИЯ
§ 5.1. ПОСТАНОВКА ЗАДАЧИ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ
Задача математического программирования в общей постановке формулируется следующим образом: требуется найти вектор X Rn , доставляющий функции
f (x) = f (x1, x2 ,…, xn ) |
(5.1.1) |
максимум на множестве д о п у с т и м ы х р е ш е н и й, заданных ограничениями
ϕi (x) bi , i =1, 2, …, m . |
(5.1.2) |
Если в задаче математического программирования (5.1.1)—(5.1.2) целевая функция f (x) является дифференцируемой и выпуклой вверх, а
левые части всех ограничений ϕi (x) (i =1, 2, …, m) — дифференцируемыми и выпуклыми вниз, то задача (5.1.1)—(5.1.2) называется задачей выпуклого
программирования.
Напомним, что функция f (X ) называется выпуклой в в е р х (вогнутой) на множестве X, если для любых x1, x2 X и любых λ[0;1] выполняется неравенство
f (λx1 + (1−λ)x2 ) λf (x1) + (1−λ) f (x2 ) .
Функция f (x) называется выпуклой в н и з (выпуклой) на множестве
X, если для любых X1, X2 X и любых λ [0; 1] выполняется неравенство
f (λx1 + (1−λ)x2 ) λf (x1) + (1−λ) f (x2 ) .
Если для задач математического программирования в общем случае пока не существует стройной теории, то для задач выпуклого программирования такая теория есть, этой теории и посвящена данная глава.
152
§ 5.2. УСЛОВИЯ КАРУША —КУНА —ТАККЕРА
Функцией Лагранжа задачи выпуклого программирования (3.1.1)— (3.1.2) называется функция
|
|
|
|
|
m |
−ϕi (x)), |
|
L(x, y) = f (x) +(y, b −ϕ(x))= f (x) + ∑yi (bi |
(5.2.1) |
||||||
|
|
|
|
|
i=1 |
|
|
x Rn , y Rm |
, |
|
|
||||
|
|
|
+ |
|
|
|
|
при этом координаты y1, y1,…, |
ym неотрицательного вектора |
|
|||||
y = (y |
y |
2 |
… y |
m |
) Rm |
|
|
1 |
|
|
+ |
|
|
называется множителями Лагранжа для задачи выпуклого программиро-
вания (3.1.1)—(3.1.2).
Если в задаче (3.1.1)—(3.1.2) f (x) выпукла вверх, а все ϕi (x) выпуклы вниз (i = 1, 2, …, m), то, очевидно, функция Лагранжа (5.2.1) выпукла
вверх по x , а по y она является и выпуклой вверх, |
и выпуклой вниз. Дей- |
||||||||
ствительно, пусть x1 , x2 Rn , |
λ [0; 1] . Тогда |
|
|
|
|
||||
L(λx1 + (1 − λ)x2 , y) = f (λx1 |
+ (1 − λ)x2 )+ |
m |
|
|
|
|
|||
∑yi bi − ϕi (λx1 + (1 − λ)x2 ) |
|
||||||||
|
|
i=1 |
|
|
|
|
|||
|
λf (x1 )+(1−λ) f (x2 ) |
|
|
λϕi (x1 )+(1−λ)ϕi (x2 ) |
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
yi (bi −λϕi (x1 )−(1−λ)ϕi (x2 )) |
|
|
|
|
m |
|
|
|
|
|
|
|
|
λf (x1 ) + (1 − λ) f (x2 ) + ∑yi |
|
[λ + (1 − λ)]bi − λϕi (x1 ) − (1 − λ)ϕi (x2 ) = |
|||||||
|
i=1 |
|
|
|
|
|
|
|
|
|
|
|
=1 |
|
|
|
|
|
|
m |
|
|
|
|
|
|
m |
|
|
= λf (x1 ) + λ∑yi |
(bi − ϕi (x1 ))+ (1 − λ) f (x2 ) + (1 − λ)∑yi (bi − ϕi (x2 ))= |
|
|||||||
i=1 |
|
|
|
|
|
|
i=1 |
|
|
|
= λL(x1, y) + (1 − λ)L(x2 , y) |
|
|
|
|||||
Если теперь y1, y2 Rm , λ[0;1], то |
|
|
|
|
|
||||
|
|
|
|
m |
|
|
|
|
|
L(x, λy1 + (1 − λ)y2 ) = f (x) + ∑(λy1i + (1 − λ) yi2 )(bi − ϕi (x1 ))= |
|
|
|||||||
|
|
|
|
i=1 |
|
|
|
|
|
|
m |
|
(bi − ϕi (x1 ))+ |
m |
|
|
|
||
= (λ + (1 − λ)) f (x) + ∑λy1i |
∑(1 − λ) yi2 (bi − ϕi (x1 ))= |
|
|||||||
|
i=1 |
|
|
|
|
i=1 |
|
|
|
=1 |
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
m |
|
|
|
|
|
|
m |
|
|
= λf (x) + λ∑y1i |
(bi − ϕi (x1 ))+ (1 − λ) f (x) + (1 − λ)∑yi2 (bi − ϕi (x1 ))= |
|
|||||||
i=1 |
|
|
|
|
|
|
i=1 |
|
|
= λL(x, y1 ) + (1 − λ)L(x, y2 )
Говорят, что задача выпуклого программирования (3.1.1)—(3.1.2) удовлетворяет условию регулярности, если существует хотя бы одна внутренняя точка множества допустимых решений, определяемого неравен-
ствами (3.1.2) [т. е. такая точка X Rn , что ϕ (x) < b |
(i = 1, 2, …, m)]. |
|
i |
i |
|
153
Точка (x , y |
) Rn+m ( X Rn , Y Rm ) называется седловой точкой |
|
|
+ |
|
функции L(x, y) , если для всех x Rn , y Rm |
|
|
|
+ |
|
|
L(x, y ) L(x , y ) L(x , y) . |
(5.2.2) |
ТЕОРЕМА КУНА — ТАККЕРА. Если задача выпуклого программирования (3.1.1)—(3.1.2) удовлетворяет условию регулярности, то точка X Rn является оптимальным решением этой задачи тогда и только тогда, когда существует такой вектор
y = (y1 y2 … ym ) Rm+
с неотрицательными координатами, что точка (X , Y ) Rn +m является седловой точкой функции Лагранжа данной задачи.
УСЛОВИЯ КАРУША — КУНА — ТАККЕРА В ДИФФЕРЕНЦИАЛЬНОЙ ФОРМЕ. Если
функция Лагранжа L(X, Y) является выпуклой вверх по x, выпуклой вниз по y и непрерывно дифференцируемой по всем xj (j = 1, 2, …, n) и yi (i = 1, 2,
…, m), то для того чтобы пара x Rn , y Rm была седловой точкой |
||||||||||||
функции Лагранжа L(x, y) , |
|
|
|
|
|
|
|
|
|
+ |
|
|
необходимо и достаточно, |
чтобы выполня- |
|||||||||||
лись следующие условия: |
|
|
|
|
|
|
|
|
|
|
|
|
∂L(x, y) |
|
|
|
|
= 0, |
|
j =1, 2, …, n , |
(5.2.3) |
||||
|
|
|
||||||||||
|
∂x j |
|
|
|
|
|
|
|||||
|
|
|
|
|
x=x |
|
|
|
|
|||
∂L(x, y) |
|
|
y=y |
i =1, 2, …, m , |
(5.2.4) |
|||||||
|
|
0, |
||||||||||
|
||||||||||||
|
∂yi |
|
|
|
|
x=x |
|
|
|
|
||
|
|
|
|
|
|
y =y |
|
|
|
|
||
y ∂L(x, y) |
|
= 0, i =1, 2, …, m , |
(5.2.5) |
|||||||||
|
||||||||||||
i |
∂yi |
|
x=x |
|
|
|
|
|||||
|
|
|
|
|
|
|||||||
y |
0, |
|
|
|
|
|
|
y =y |
i =1, 2, …, m . |
(5.2.6) |
||
|
|
|
|
|
|
|
||||||
i |
|
|
|
|
|
|
|
|
|
|
|
|
ПРИМЕР 5.2.1 (ЗАДАЧА КВАДРАТИЧНОГО ПРОГРАММИРОВАНИЯ). Для задачи |
||||||||||||
f (x) = −(x − 8)2 − (x |
2 |
− 8)2 → max , |
(5.2.7) |
|||||||||
|
|
1 |
|
|
|
|
|
|||||
|
|
|
|
|
|
3x1 + x2 15, |
(5.2.8) |
|||||
|
|
|
|
|
|
|
|
x1 + x2 10, |
||||
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
x1 0, |
x2 0 |
(5.2.9) |
проверить выполнение условия регулярности, и если оно выполняется, составить функцию Лагранжа, записать условия Каруша — Куна — Таккера в дифференциальной форме и найти оптимальное решение задачи как точку, удовлетворяющую условиям Каруша — Куна — Таккера.
154
Решение. Такая задача, в которой целевая функция квадратичная, а ограничения — линейные, носит название задачи квадратичного програм-
мирования.
Очевидно, условие регулярности выполняется, поскольку, например, точка
x(0) 1
= 8
является внутренней точкой множества допустимых решений — все ограничения в этой точке выполняются как строгие неравенства:
3 ×1 |
+ 8 |
<15, |
|
|
1 |
+ 8 |
<10, |
|
|||
|
|
1 > 0, |
|
|
|
||
|
|
8 |
> 0. |
|
|
Составим функцию Лагранжа (5.2.1):
L(x, y) = -(x1 - 8)2 - (x2 - 8)2 + y1 (15 - 3x1 - x2 ) + y2 (10 - x1 - x2 ) + y3 x1 + y4 x2 .
Здесь мы учли, в том числе, и ограничения (5.2.9), которые преобразовали к такому виду: −x1 0, − x2 0 .
Производные функции Лагранжа равны
∂L(x, y) = −2(x − 8) − 3y − y + y , |
|||
∂x1 |
1 |
2 |
3 |
1 |
∂L(x, y) = −2(x − 8) − y − y + y , |
|||
∂x2 |
1 |
2 |
4 |
2 |
∂L(x, y) |
=15 − 3x − x , |
∂L(x, y) |
=10 − x − x , |
∂L(x, y) |
= x , |
∂L(x, y) = x . |
|||
|
|
|
|||||||
∂y1 |
2 |
|
∂y2 |
2 |
∂y3 |
∂y4 |
|||
1 |
|
1 |
1 |
2 |
|||||
Условия Каруша — |
Куна — Таккера |
в |
дифференциальной форме |
(5.2.3)—(5.2.6) запишутся в виде (5.2.3')—(5.2.6'):
−2(x1 − 8) − 3y1 − y2 + y3 = 0,−2(x2 − 8) − y1 − y2 + y4 = 0,
15 - 3x1 - x2 0, |
|||
|
- x1 |
- x2 |
0, |
10 |
|||
|
x1 |
|
0, |
|
|
||
|
|
x2 |
0, |
|
|
y (15 - 3x - x ) = 0, |
|
1 |
1 2 |
y2 (10 - x1 - x2 ) = 0, |
|
|
= 0, |
y3 x1 |
|
|
= 0, |
y4 x2 |
(5.2.3')
(5.2.4')
(5.2.5')
155
y1 0, |
|
|
0, |
y2 |
|
|
(5.2.6') |
y3 |
0, |
|
0. |
y4 |
Если ввести обозначения
p1 = y1, p2 = y2 , q1 = y3 , q2 = y4 , r1 = 15 − 3x1 − x2 , r2 =10 − x1 − x2 ,
раскрыть скобки и перенести все переменные в левые части ограничений (5.2.3')—(5.2.6'), а все константы — в правые части, то условия Каруша — Куна — Таккера примут следующий вид:
2x1 |
|
+3 p1 + p2 − q1 |
|
|
|
= 16, |
|
||||||
|
|
2x2 |
+ p1 |
+ p2 |
−q2 |
|
|
= 16, |
|
||||
|
|
|
|
|
|||||||||
3x + x |
2 |
|
|
|
|
+ r |
|
= 15, |
|
||||
|
|
1 |
|
|
|
|
|
1 |
|
|
|
|
|
|
+ x2 |
|
|
|
|
|
+ r2 |
= 10, |
(5.2.10) |
||||
x1 |
|
|
|
|
|
||||||||
p r = 0, p r = 0, q x = 0, q |
x |
|
= 0, |
|
|||||||||
|
1 1 |
|
|
2 |
2 |
1 |
1 |
2 |
|
2 |
|
|
|
x |
0, |
x |
|
0, |
p |
0, |
p |
|
0, |
|
|||
|
1 |
|
|
|
2 |
|
1 |
|
|
2 |
|
|
|
q1 0, |
q2 0, |
r1 0, |
r2 0. |
|
|||||||||
Решение этой системы, если оно существует, можно найти с помо- |
|||||||||||||
щью метода искусственного базиса. |
|
|
|
|
|
|
|||||||
Введем неотрицательные переменные s1 0, |
s2 0 |
и поставим та- |
|||||||||||
кую задачу линейного программирования: |
|
|
|
|
|
||||||||
|
|
|
|
|
t = −s1 − s2 → max , |
|
|
|
|
||||
2x1 |
|
+3 p1 + p2 −q1 |
|
|
|
+s1 |
= 16, |
|
|||||
|
|
2x2 |
+ p1 + p2 |
−q2 |
|
|
+s2 = 16, |
|
|||||
|
|
|
|
|
|||||||||
|
|
+ x2 |
|
|
|
|
|
+r1 |
|
|
|
= 15, |
|
3x1 |
|
|
|
|
|
|
|
|
|
|
|||
x |
|
+ x |
|
|
|
|
|
|
+r |
|
|
= 10, |
|
1 |
|
2 |
|
|
|
|
|
|
2 |
|
|
|
|
p1r1 = 0, p2r2 = 0, q1x1 = 0, q2 x2 = 0,
x1 0, x2 0, p1 0, p2 0, q1 0, q2 0, r1 0, r2 0, s1 0, s2 0.
Если в оптимальном решении этой задачи s1 = s2 = 0 , то набор чи-
сел x1 , x2 , p1 , p2 , q1 , q2 , r1 , r2 будет удовлетворять условиям Каруша — Куна — Таккера (5.2.10), значит, вектор
x1x2
будет являться оптимальным решением задачи (5.2.7)—(5.2.9).
156
|
|
Чтобы решить данную задачу, можно воспользоваться симплексным |
||||||||||||||
|
методом, при этом для учета условий p1r1 = 0, |
p2r2 = 0, |
q1x1 = 0, q2 x2 = 0 |
|||||||||||||
|
при вычислительной реализации симплексного метода необходимо следить |
|||||||||||||||
|
за тем, чтобы не вводить в базис одновременно переменные pi и ri с одним и |
|||||||||||||||
|
тем же индексом i и переменные qj и xj с одним и тем же индексом j. |
|
||||||||||||||
|
|
Соответствующая симплексная таблица представлена в табл. 5.2.1. |
||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Т а б л и ц а |
5.2.1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
cɶ |
Базис |
h |
0 |
0 |
0 |
0 |
0 |
|
0 |
|
0 |
0 |
–1 |
–1 |
Примечания |
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
x1 |
x2 |
p1 |
p2 |
q1 |
|
q2 |
r1 |
r2 |
s1 |
s2 |
||||||
|
|
|
|
|
|
|||||||||||
–1 |
s1 |
16 |
2 |
0 |
3 |
1 |
–1 |
|
0 |
|
0 |
0 |
1 |
0 |
Нельзя вводить в |
|
–1 |
s2 |
16 |
0 |
2 |
1 |
1 |
0 |
|
–1 |
0 |
0 |
0 |
1 |
базис p1, p2 без |
||
0 |
r1 |
15 |
3 |
1 |
0 |
0 |
0 |
|
0 |
|
1 |
0 |
0 |
0 |
вывода из базиса |
|
0 |
r2 |
10 |
1 |
1 |
0 |
0 |
0 |
|
0 |
|
0 |
1 |
0 |
0 |
r1, r2 соответ- |
|
|
t0 – t |
–32 – t |
–2 |
–2 |
–4 |
–2 |
1 |
|
1 |
|
0 |
0 |
0 |
0 |
ственно. |
|
–1 |
s1 |
6 |
0 |
–2/3 |
3 |
1 |
–1 |
|
0 |
|
–2/3 |
0 |
1 |
0 |
Нельзя вводить в |
|
–1 |
s2 |
16 |
0 |
2 |
1 |
1 |
0 |
|
–1 |
0 |
0 |
0 |
1 |
базис p2, q1 без |
||
0 |
x1 |
5 |
1 |
1/3 |
0 |
0 |
0 |
|
0 |
|
1/3 |
0 |
0 |
0 |
вывода из базиса |
|
0 |
r2 |
5 |
0 |
2/3 |
0 |
0 |
0 |
|
0 |
|
–1/3 |
1 |
0 |
0 |
r2, x1 |
соответ- |
|
t0 – t |
–22 – t |
0 |
–4/3 |
–4 |
–2 |
1 |
|
1 |
|
2/3 |
0 |
0 |
0 |
ственно. |
|
0 |
p1 |
2 |
0 |
–2/9 |
1 |
1/3 |
–1/3 |
|
0 |
|
–2/9 |
0 |
1/3 |
0 |
Нельзя вводить в |
|
–1 |
s2 |
14 |
0 |
20/9 |
0 |
2/3 |
1/3 |
|
–1 |
2/9 |
0 |
–1/3 |
1 |
базис p2, q1, r1 без |
||
0 |
x1 |
5 |
1 |
1/3 |
0 |
0 |
0 |
|
0 |
|
1/3 |
0 |
0 |
0 |
вывода из базиса |
|
0 |
r2 |
5 |
0 |
2/3 |
0 |
0 |
0 |
|
0 |
|
–1/3 |
1 |
0 |
0 |
r2, x1, p1 соответ- |
|
|
t0 – t |
–14 – t |
0 |
–20/9 |
0 |
–2/3 |
–1/3 |
|
1 |
|
–2/9 |
0 |
4/3 |
0 |
ственно. |
|
0 |
p1 |
17/5 |
0 |
0 |
1 |
2/5 |
–3/10 –1/10 |
–1/5 |
0 |
3/10 |
1/10 |
|
|
|||
0 |
x2 |
63/10 |
0 |
1 |
0 |
3/10 |
3/20 |
|
–9/20 |
1/10 |
0 |
–3/20 |
9/20 |
|
|
|
0 |
x1 |
29/10 |
1 |
0 |
0 |
–1/10 –1/20 |
3/20 |
3/10 |
0 |
1/20 |
–3/20 |
|
|
|||
0 |
r2 |
4/5 |
0 |
0 |
0 |
–1/5 |
–1/10 |
3/10 |
–4/10 |
1 |
1/10 |
–3/10 |
|
|
||
|
t0 – t |
0 – t |
0 |
0 |
0 |
0 |
0 |
|
0 |
|
0 |
0 |
1 |
1 |
|
|
|
|
На первом шаге симплексного метода наименьший из отрицатель- |
||||||||||||||
|
ных оценочных коэффициентов p |
= −4 , |
однако переменную p1 можно |
|||||||||||||
|
|
|
|
|
|
|
1 |
|
|
|
|
|
|
|
|
|
|
ввести в базис только одновременно с выводом из базиса переменной r1. |
|||||||||||||||
|
Это невозможно, поскольку коэффициент при свободной переменной p1 в |
|||||||||||||||
|
третьем уравнении, соответствующем базисной переменной r1, равен нулю |
|||||||||||||||
|
и не может быть выбран в качестве разрешающего. |
|
|
|
|
|||||||||||
|
|
Поэтому на первом шаге в базис вводится переменная x1 (соответ- |
||||||||||||||
|
ствующий оценочный коэффициент |
|
x |
= −2 ). Итак, |
x = 29 / 10 = 2,9, |
x = , |
||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
1 |
|
|
2 |
|
|
|
|
|
|
|
|
|
|
1 |
|
|
|
|
|
|
|
|
= 63 / 10 = 6,3, y |
=17 / 5 = 3, 4, y |
= y |
= y = 0 . |
|
|
|
|
|
|||||||
|
|
|
1 |
|
|
2 |
3 |
|
4 |
|
|
|
|
|
|
В общем случае система условий Каруша — Куна — Таккера в дифференциальной форме представляет собой систему н е л и н е й н ы х уравнений, отыскание точных решений которой не всегда возможно, следовательно, невозможно найти точные решения задачи выпуклого программирования.
157
Поэтому для приближенного решения большинства задач выпуклого программирования необходимо использовать численные методы. В следующих параграфах мы рассмотрим несколько таких методов.
Существенность условий регулярности иллюстрируется следующим примером.
ПРИМЕР 5.2.2. Требуется решить задачу
f(x) = x →max , x2 0 .
Решение. Решение этой задачи очевидно: это точка x = 0 . При этом очевидно, что условие регулярности не выполняется, поскольку множество допустимых решений состоит из единственной точки x = 0 .
Составим для этой задачи функцию Лагранжа
L(x, y) = x − x2 y ,
и попытаемся записать условия Каруша — |
Куна — Таккера: |
||
∂L =1− 2xy = 0, |
∂L = −x2 0, y |
∂L = −x2 y = 0. |
|
∂x |
∂y |
|
∂y |
Очевидно, данная система противоречива!
§ 5.3. МЕТОД ВОЗМОЖНЫХ НАПРАВЛЕНИЙ
Основная идея метода возможных направлений такова. В каче-
стве начального приближения к оптимальному решению задачи выпуклого программирования (3.1.1)—(3.1.2) выбирается некоторая внутренняя точка X(0) множества допустимых решений [т. е. все ограничения (3.1.2) в этой точке должны выполняться как строгие неравенства].
Далее строится последовательность
x( k +1) = x( k ) + h( k )e( k ) , k =1, 2, 3, … |
(5.3.1) |
приближений к точке максимума целевой функции f (X ) |
на множестве до- |
пустимых решений. |
|
Вектор e(k ) , определяющий направление перемещения из точки x( k ) в точку x( k +1) (на k-м шаге метода) должен удовлетворять двум т р е б о - в а н и я м:
1)при достаточно малых h(k ) точка x( k +1) , определяемая формулой (5.3.1), должна принадлежать множеству допустимых решений (т. е.
вектор e( k ) должен задавать в о з м о ж н о е н а п р а в л е н и е); в
158
частности, если точка x( k ) является граничной точкой множества допустимых решений, то вектор e(k ) должен быть направлен внутрь этого множества;
2)при достаточно малых h( k ) точка x( k +1) , определяемая формулой (5.3.1), должна принадлежать множеству допустимых решений [т. е.
вектор e( k ) |
должен |
задавать н а п р а в л е н и е в о з р а с т а н и я |
целевой функции f (x) ]. |
||
Величина |
h(k ) шага |
смещения в (5.3.1) выбирается из условия |
наибольшего роста целевой функции f (X ) при перемещении из точки x( k ) в точку x( k +1) с учетом того, что новое приближение x( k +1) , определяемое формулой (5.3.1), должно оставаться во множестве допустимых решений.
Если очередное приближение x( k ) является в н у т р е н н е й точкой множества допустимых решений [т. е. в этой точке все ограничения (3.1.2) выполняются как строгие неравенства], то вектор e(k ) можно выбрать совпадающим с градиентом
∂f (x1, x2 , …, xn ) |
|
|
||||
|
||||||
|
∂x1 |
|
|
|
|
|
|
|
|
|
|
||
∂f (x1, x2 , …, xn ) |
|
|
||||
|
|
|
|
|||
grad f (x(k ) ) = |
|
|
|
|
|
|
∂x2 |
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
∂f (x , x , …, x ) |
|
|
||||
|
1 |
2 |
n |
|
|
|
|
∂xn |
|
|
|
|
|
|
|
|
|
x=x( k ) |
||
|
|
|
|
|||
целевой функции f (x) [тогда e(k ) |
= grad f (x( k ) ) будет указывать направле- |
|||||
ние наискорейшего возрастания функции |
f (x) |
в точке x( k ) ]. |
Если же x( k ) является г р а н и ч н о й точкой множества допустимых решений, то некоторые из неравенств (3.1.2) в точке x( k ) обращаются в равенства. В этом случае движение в направлении градиента может вывести за пределы множества допустимых решений.
В этом случае возможное направление
e(k ) |
||
|
1(k ) |
|
e(k ) = e2 |
|
|
|
|
|
|
|
|
e(k ) |
||
|
n |
|
возрастания целевой функции f (x) в точке x( k ) выбирается так, чтобы выполнялись следующие у с л о в и я.
1)угол между вектором e( k ) и вектором grad f (x(k ) ) должен быть как можно меньшим;
159
2) для каждого из ограничений i = i1, i2 , …, iq , активных в точке x( k )
(т. е. обращающихся в точке x( k ) в строгие равенства), угол между вектором e(k ) и внешней нормалью к гиперплоскости
|
n |
|
n |
∂ϕ |
i |
|
|
|
|
|
|
||||||
|
|
∑ |
|
x j |
|
, |
||
πi = x R |
|
|
∂x j |
= bi |
||||
|
|
|
j =1 |
|
|
|
||
|
|
|
|
|
|
|
|
|
касательной к границе множества допустимых решений в точке x( k ) , должен быть не меньше π / 2 (т. е. вектор e(k ) должен быть направлен внутрь множества допустимых решений задачи);
3)вектор E (1) должен быть ограниченным — поскольку направление определяется с точностью до положительного множителя, данное условие обеспечивает однозначность выбора e(1) .
Эти условия приводят к постановке следующей задачи:
|
|
|
|
|
|
|
n |
(x |
(k ) |
) e(jk ) → max, |
|
|
|
|
z = (grad f (x(k ) ),e(k ) ) = ∑ ∂f |
|
|||||||
|
|
|
|
|
|
|
j=1 |
∂x j |
|
|
|
(grad ϕ (x(k ) ),e(k ) ) = |
n |
∂ϕi (x(k ) ) |
e(k ) 0, i = i , i |
, …, i , |
|||||||
∑ |
|
||||||||||
|
|
|
|
|
i |
∂x j |
j |
|
1 2 |
q |
|
|
|
|
|
|
|
j=1 |
|
|
|
|
|
|
n |
|
|
|
|
|
|
||||
∑ |
|
e(jk ) |
|
1. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
j=1 |
|
|
|
|
|
|
|
|
|
|
(5.3.2)
(5.3.3)
Данную задачу можно свести к задаче линейного программирования, для этого нужно представить переменные e(jk ) (которые по смыслу за-
дачи (5.3.2)—(5.3.3) могут принимать значения произвольного знака) как разности e(jk ) = e(jk+) − e(jk−) новых н е о т р и ц а т е л ь н ы х переменных e(jk+) 0 , e(jk−) 0 и добавить условия e(jk+)e(jk−) = 0 (j = 1, 2, …, n).
При этом
|
|
e(1) |
= e(1) + e(1) |
, |
|
|
e(1) |
= e(1) |
+ e(1) , |
||
|
|
1 |
|
1+ |
1− |
|
|
|
2 |
2+ |
2− |
и задача (5.3.2)—(5.3.3) |
примет вид |
|
|
|
|
|
|
||||
|
|
|
|
n ∂f |
(x(k ) ) |
(e(jk+) − e(jk−) ) → max, |
|||||
|
z = ∑ |
∂x j |
|
||||||||
|
|
|
|
j=1 |
|
|
|
|
|
|
|
n |
∂ϕi (x(k ) ) |
(k ) |
|
(k ) |
|
|
|
|
|||
∑ |
|
|
|
|
(ej+ − ej− |
) 0, i = i1, i2 , …, iq , |
|||||
|
|
∂x j |
|||||||||
j=1 |
|
|
|
|
|
|
|
|
|
||
n |
|
|
|
n |
|
|
|
|
|
|
|
∑e(jk+) + ∑e(jk−) 1, |
|
|
|
|
|||||||
j=1 |
|
|
|
j=1 |
|
|
|
|
|
|
|
(5.3.4)
(5.3.5)
160