Кулик Елементы теории принятия решений 2010
.pdf3). Найдём точкуминимума НЕрегулярного позинома.
Согласно Теореме 2.5 точка (xmin ,ymin ,zmin) минимума нерегулярного позинома для n =3 переменных есть решение следующейсистемы из трёхуравнений (2.15б):
x(−1) Aax−1 y−1z−1 +(+1) bxy +(+1) 2cxz +(0) 2cyz=0,
y(−1) Aax−1 y−1z−1 +(+1) bxy +(0) 2cxz +(+1) 2cyz=0,
z(−1) Aax−1 y−1z−1 +(0) bxy +(+1) 2cxz +(+1) 2cyz=0,
или
−Aax−1 y−1z−1 + bxy + 2cxz =0,−Aax−1 y−1z−1 + bxy + 2cyz=0,−Aax−1 y−1z−1 +2cxz +2cyz=0,
которую решим следующим образом. Вычтем из1го уравне-
ния2- е уравнение и сразу находим, что y=x. Далее вычтем из 2- |
|
гоуравнения 3-е уравнение получимследующеевыражение |
: |
|
bxy = 2cxz, т.е. |
z = |
b |
y или z = |
|
b |
x . |
|
||||||||||
|
|
2c |
|
|||||||||||||||
|
|
|
|
|
|
|
|
|
2c |
|
|
|
|
|
||||
Подставивв 1-е уравнениевыражения |
|
для y |
и z, |
получим |
||||||||||||||
|
|
|
−1 |
|
−1 |
b |
−1 |
|
|
|
|
|
b |
|
|
|||
|
|
−Aax |
|
x |
|
|
|
x |
+ bxx |
+ 2cx |
|
|
|
x =0, |
||||
|
|
|
2c |
2c |
||||||||||||||
или |
|
|
|
|
|
|
|
|
|
|
|
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
−2cAa |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1/ 5 |
|
x−3 |
+ 2bx2 |
=0 x5 = cAa2 |
|
x= cAa2 . |
||||||||||||||
|
||||||||||||||||||
b |
|
|
|
|
|
|
|
b |
|
|
|
|
b |
|
Таким образом, эта система уравнений имеет положительное (таккак для позинома x >0, y >0, z >0) решение
cAa 1/ 5 |
|
1 |
|
Aab3 1/ 5 |
|
|
||||
xmin= ymin = |
2 |
; zmin= |
|
|
|
|
|
. |
|
|
2 |
c |
4 |
|
|
|
|||||
b |
|
|
|
|
|
|
|
|
||
4). Найдём минимальноезначение НЕрегулярного позинома: |
|
|||||||||
min f(x,y,z) =f (xmin ,ymin ,zmin) = Aax−2 |
z−1 |
+bx2 |
+4cx |
z . |
||||||
|
|
|
min |
min |
|
min |
min |
min |
x>0, y>0, z>0
5). Итем самым задача решена▄
161
Пример2.10 (см. [2, с. 25])
Скорость распространения в глубокой воде волны, длина кото-
рой равна λ, пропорциональна величине |
λ |
+ |
a |
, где a — неко- |
|
|
|
|
|||
|
|||||
|
a |
|
λ |
|
торая константа. При какой длине волны λmin скорость будет наименьшая?
Решение
0). Введёмобозначения
|
λ |
|
|
|
|
+ |
a |
|
|
g( λ)= b · |
|
|
||
|
a |
|
λ |
|
|
|
|
|
|
2 |
2 |
λ |
+ |
a |
, |
g( λ) = b |
|
· |
|
||
|
|
a |
|
λ |
|
гдеb — коэффициентпропорциональности |
, λ >0; a>0. |
Заметим, что так как b 2 =Const, то можнополагать, что |
f(x)= g(λ)2 b2= |
|
λ |
+ |
a |
|
|
|
||||||||
|
|
|
|
|
|
|
, |
|
|
|
|||||
|
|
|
|
|
|
|
|
||||||||
|
|
a |
|
|
λ |
|
|
|
|||||||
где x =λ и a=A, т .е. f( x) = g(x)2b2 |
= |
1 |
|
x + Ax−1 |
, |
где A>0, и |
|||||||||
A |
|||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|||||
переформулируемисходную задачу следующимобразом |
. |
||||||||||||||
Найти минимум позинома f(x) = |
|
1 |
x + Ax−1, |
|
где A>0 в облас- |
||||||||||
|
|
|
|||||||||||||
|
|
|
A |
|
|
|
|
|
|
|
ти егоопределения (т.е. x>0).
1). Убедимся, чтоисходная функция f (x) являетсяименно позиномом (приэтом отметим,что нет вынужденныхограничений). Заметим,что f( x) —это именно позином (см. Пример2.6).
2). Проверим, что минимизируемый позином f (x) являетсяименно регулярным позиномом. Заметим, что f(x) —это НЕрегулярный позином (см. Пример2.6).
3). Найдём точкуминимума НЕрегулярного позинома.
Точка xmin минимума этого позинома( см. Пример 2.6) уженайдена:
xmin=A λmin = a.
4). Находитьминимальное значение НЕрегулярного позинома (или исходнойфункции) взадаче не требуется.
5). Итем самым задача решена▄
162
Пример2.11 (см. [2, с. 93])
Найти минимум позинома f(x,y,z) =4x−1 y−1z−1+4xz+xy+2yz в
области его определения (необходимо использовать решение двойственной задачи).
Решение
1). Убедимся, чтоисходнаяфункция f(x,y,z) являетсяименнопози- номом(приэтомотметим, чтонетвынужденныхограничений).
Заметим, что(ck>0, aik , |
где k=1, 2, 3, 4; i=1, 2, 3) m=4, n=3 |
|||||||
и |
|
|
|
|
|
|
|
|
c1=4, |
|
c2=4, |
|
c3=1, |
c |
4=2, |
||
x a11= –1, |
|
a12=1, |
a |
13=1, |
|
a14=0, |
||
y a21= –1, |
|
a22=0, |
|
a23=1, |
|
a24=1, |
||
z a31= –1, |
a |
32=1, |
|
a33=0, |
a |
34=1, |
||
тогда (таккак |
x 1=x; x2=y; x3=z) выполненоусловие (2.5а) |
|||||||
m |
n |
|
|
=4x−1 y−1z−1 |
+4xz+ xy +2yz = f(x,y,z), |
|||
∑ ck ∏xiaik |
|
|||||||
k =1 |
i=1 |
|
|
|
|
|
|
|
т.е. f(x,y,z) |
— этоименно позиномв виде (2.5а). |
|||||||
Такимобразом |
,условиесходной |
задачи есть программаА . |
2). Сформулируем далеенеобходимую двойственную функцию и соответствующую ей систему уравнений.
Двойственная функция( для программы В) к данной прямой задаче или программе А формулируется следующимобра -
зом [2, с. 93]:
Ю
Я
v(δ ,δ |
|
,δ |
|
,δ |
|
)= |
|
4 δ1 |
4 δ2 |
1 δ3 2 |
δ4 |
( |
δ +δ |
|
+δ |
+δ |
|
) |
δ1+δ2+δ3+δ4 |
||||||||||||||
2 |
3 |
4 |
|
|
|
|
|
|
|
|
|
|
|
2 |
4 |
|
|||||||||||||||||
1 |
|
|
|
|
|
|
1 |
|
3 |
|
|
|
|
||||||||||||||||||||
|
|
|
|
|
|
|
|
δ1 |
δ2 |
δ3 |
|
δ4 |
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||
или |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
v(δ1,δ2 ,δ3 ,δ4 )= |
4 |
δ1 |
|
4 |
δ2 |
|
1 |
δ3 |
|
2 |
δ4 |
, |
|
|
|
||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
δ1 δ2 |
δ3 δ4 |
|
|
|
|
|
||||||||||||||||
Заметим, чтов данной задаче |
c1=4, c2=4, |
c3=1, c4=2, нотогда |
|||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
163 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
m=4 |
|
ci |
δi |
|
c1 |
δ1 |
|
c2 |
δ2 |
|
c3 |
δ3 |
|
c4 |
δ4 |
||
дляЮ ∏ |
|
= |
|
|
|
|
|
|
|
= |
|||||||
|
|
|
|
|
|||||||||||||
i=1 |
|
δi |
|
δ1 |
|
δ2 |
|
δ3 |
|
δ4 |
|
= δ41 δ1 δ42 δ2 δ13 δ3 δ24 δ4 ,
p=0
дляЯ ∏(λk )λk = (λ0 )λ0 =11 ,
k =0
так как J0 ={1, 2, 3, 4},
λk=0=∑δi = ∑ |
4 |
|
δi = ∑δi=δ1+δ2+δ3+δ4=1. |
||
0 |
{ } |
i=1 |
i J |
i 1,2,3,4 |
Системауравнений будетследующей:
(−1) δ1 +1 δ2 +1 δ3 +0 = 0,
(−1) δ1 +0 +1 δ3 +1 δ4 = 0,
(−1) δ1 +1 δ2 +0 +1 δ4 = 0, (*)
∑4 δi =1.i=1
3). Найдём решениедвойственной задачи [2, с. 93-94].
Заметим, что система (*) линейных уравнений может быть представлена в следующемвиде :
δ2 +δ3 = δ1,δ3 +δ4 = δ1,δ2 +δ4 = δ1,
δ1 +δ2 +δ3 +δ4 =1.
Далее, умножив 2-е уравнение на (–1)и сложив первые три уравнения, можнополучить, что 2δ2 = δ1 , или
164
δ2 = 12 δ1 ,
а значит
δ2 = δ3 = δ4 = 12 δ1 .
Тогда с учётом 4-го уравнения системы (*) окончательно получаем единственное (положительное) решение (η1, η2 , η3 , η4 ) , где
η1 = 52 ; η2 = η3 = η4 = 15 .
Таким образом, множество состоит только източки
(η1, η2 , η3 , η4 ) = 2 , 1 , 1 , 1 .5 5 5 5
Тогдамаксимум двойственнойфункции
v0 = max v(δ1,...,δm ) = v(η1,..., ηm )
определяется следующим выражением:
v0 = v(η1, η2 , η3 , η4 )= |
|
4 2 / 5 |
|
4 1/ 5 |
1 |
1/ 5 |
2 |
|
|
1/ 5 |
||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
= |
||||||||||||||
|
|
|
|
|
|
|
|
|
||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
2 / 5 |
|
1/ 5 |
1/ 5 |
|
1/ 5 |
|
||||||||||||
16 |
|
|
4 |
|
1 |
|
2 |
|
|
1/ 5 |
|
|
|
|
1/ 5 |
|
|
|
5 |
|
1/ 5 |
|
||||||||
= |
|
|
|
|
|
|
|
|
|
|
|
|
|
= |
(100 20 5 10) |
|
= |
(10 |
|
) |
|
=10 . |
||||||||
|
|
1/ 5 |
1/ 5 |
1/ 5 |
|
|
|
|
||||||||||||||||||||||
4 / 25 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||
Вывод. |
Максимум двойственной функции v(δ1,...,δm ) |
|
известен. |
Осталось найти точку t = (t1,t2 ,t3 ) =(xmin ,ymin ,zmin) минимума исходного позинома f(x,y,z).
165
4). Найдём точку |
t минимумаисходного позинома. |
|
Дляопределения |
координатточки |
минимума составим систему |
уравнений (2.33б), котораядля нашей задачибудет иметьвид |
4x−1 y−1z−1 = η1v0 = (2 / 5) 10 = 4, |
|
|||||||
|
|
|
= η2v0 = (1/ 5) 10 = 2, |
|
||||
4xz |
|
|
|
|||||
xy |
|
|
= η v |
= (1/ 5) 10 = 2, |
|
|||
|
|
|
|
|
|
3 0 |
|
|
|
|
|
= η4v0 = (1/ 5) 10 = 2, |
|
||||
2yz |
|
|
|
|||||
или |
|
|
|
|
|
|
|
|
|
|
−1 |
y |
−1 |
z |
−1 |
= 4, |
|
4x |
|
|
|
|
||||
4xz |
|
|
|
|
= 2, |
(**) |
||
|
|
|
|
|
|
|
|
|
xy |
|
|
|
|
|
= 2, |
|
|
|
|
|
|
|
|
|
= 2. |
|
2yz |
|
|
|
|
|
|||
В (**) подставив в 1-е уравнение |
значение xy = 2 из 3-го уравне- |
|||||||
ния сразу получим, что |
zmin = |
1 |
. Из2го уравнения, зная zmin, сразу |
|||||
находим, что xmin =1. Из3- |
|
|
2 |
|
|
|||
го уравнения, зная xmin, сразу определя- |
||||||||
ем,что ymin = 2 . |
|
|
|
|
|
|
|
|
В итоге получается, что система (**) имеет единственное и положительное решение
t= (xmin ,ymin ,zmin) = 1,2, 1 .
2
5). Найдём минимальноезначение исходного позинома. Выполнены условия для Теоремы 2.7в, а значит согласно теоре-
медвойственности
min f(x,y,z) = f(xmin ,ymin ,zmin) = f(1, 2, 1/2) = 10.
x>0, y>0, z>0
6). Итем самым задача решена▄
166
Пример2.12 (см. [2, с. 100])
Среди всех точек (x, y) плоскости с положительными координатами, удовлетворяющими неравенству x4 y−4 + x−1 y ≤1, найти точку, ординатау которой минимальна.
Решение
0). Введёмследующие обозначения:
g0 (x, y) = y ,
g1 (x, y) = x4 y−4 + x−1 y1/ 2 .
Переформулируем исходную задачу в виде следующей прямой задачи —геометрической программы А:
найти |
|
|
|
min g0 (x, y) = min y |
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
(A.1) |
|||||
приограничениях |
|
|
|
x > 0, |
y > 0 , |
|
|
|
|
|
|
(A.2) |
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
g (x, y) = x4 y−4 + x−1 y1/ 2 ≤1. |
(A.3) |
||||||||
|
|
|
|
|
1 |
|
|
|
|
|
|
|
|
1). Убедимся, чтоноваяформулировка |
задачи полностью соответ- |
||||||||||||
ствует (2.16а,б,в). Этодействительно так ( g0 |
и g1 |
— это по- |
|||||||||||
зиномы, см.Пример 2.А.) и |
|
|
|
|
|
|
|
|
|||||
n=2 (в программеА всегодве переменных x и |
y); |
|
|||||||||||
p=1 |
(всегоодно вынужденноеограничение |
|
g1(x, y) ≤1); |
||||||||||
m0 |
=1 (упозинома |
g0 (x, y) один член, т.е. однослагаемое); |
|||||||||||
m1 = 2 (упозинома |
g1 (x, y) двачлена,т.е.два слагаемых); |
||||||||||||
m = m0 +m1 =1+2 = 3 (три переменных |
δ1,δ2 ,δ3 ); |
|
|||||||||||
c1=1 (таккак у |
g0 (x, y) множитель при y есть 1); |
|
|||||||||||
c2=1 (таккак |
у |
g (x, y) множитель при |
x4 y−4 есть 1); |
|
|||||||||
|
|
|
1 |
|
|
|
|
|
|
|
|
|
|
c3=1 (таккак |
у |
g (x, y) множитель при |
x−1 y1/ 2 есть 1); |
||||||||||
|
|
|
1 |
|
|
|
|
|
|
|
x4 y –4 |
||
|
|
|
|
|
|
|
|
|
|
|
|||
|
0 |
, |
A1 = |
|
4 −1 |
, |
|
0 4 −1 |
|
||||
A0 = |
|
|
A = |
|
|
1 |
|
, |
|||||
|
1 |
|
|
|
−4 1/ 2 |
|
|
|
1 −4 |
|
|
|
|
|
|
|
|
|
2 |
|
|||||||
матрица «экспонент» |
|
для задачи |
|
|
|
|
|
||||||
|
|
x0 y1 |
x –1 y1/2 |
||||||||||
|
|
|
|
|
|
|
|
||||||
|
|
|
|
|
167 |
|
|
|
|
|
|
|
|
для g |
0 |
J |
0 |
|
= 1 ; |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
{ } |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
для g |
1 |
J |
1 |
= 1+1,1+2 = 2, 3 . |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||
|
|
|
{ |
|
|
|
} |
|
{ |
|
} |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
2). Поскольку естьвынужденные ограничения, тосформулируем |
|
|||||||||||||||||||||||||||||||||||||||
далеенеобходимуюдвойственную |
|
|
задачу. |
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||||||||||
Двойственная задача (или программа В) к данной прямой за- |
||||||||||||||||||||||||||||||||||||||||
даче или программе А (A.1) ÷ (A.3) формулируется следующим |
||||||||||||||||||||||||||||||||||||||||
образом [2,с. 101]: |
|
|
|
|
|
|
|
|
|
Ю |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||
найти |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Я |
|
|
|
|
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
1 δ1 1 |
|
δ2 1 |
|
δ3 |
|
|
|
|
|
|
|
|
|
|
|||||||||||||
max v(δ ,δ |
|
,δ |
|
) = max |
|
|
|
|
(δ |
|
+δ |
|
) |
δ2 +δ3 |
(B.1) |
|||||||||||||||||||||||||
2 |
3 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2 |
3 |
|
|
|
||||||||||||||||||||
|
|
1 |
|
|
|
|
|
|
|
|
|
δ2 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
δ1 |
|
|
δ3 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||
приограничениях |
δ1 ≥ 0, δ2 ≥ 0, δ3 ≥ 0, |
|
|
|
|
|
|
|
|
|
|
(B.2) |
||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
+4 δ2 +(−1) δ3 = 0, |
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||||
|
|
|
|
|
|
|
|
|
0 δ1 |
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
+(−4) δ2 |
+ |
1 |
δ3 |
= 0, |
|
|
|
|
|
|
|
|
|
(B.3) |
|||||||||||||||
|
|
|
|
|
|
|
|
|
1 δ1 |
|
2 |
|
|
|
|
|
|
|
|
|
||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
m0 =1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
∑δi =δ1 =1. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||
|
|
|
|
|
|
|
|
|
i=1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Заметим, чтов данной задаче |
|
|
c1=c2=c3=1, δ1 =1, нотогда |
|
|
|
|
|
||||||||||||||||||||||||||||||||
|
|
m |
|
|
ci |
|
δi |
|
|
|
|
δ1 |
|
δ2 |
|
|
|
δ3 |
|
|
1 |
|
|
δ1 |
|
|
|
δ2 |
|
1 |
|
δ3 |
||||||||
дляЮ ∏ |
|
= |
c1 |
|
|
|
c2 |
|
|
|
|
c3 |
|
|
= |
|
|
1 |
|
|
|
|
, |
|||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||||||||||||||
|
|
i=1 |
δi |
δ1 δ2 |
|
|
δ3 |
|
|
δ1 δ2 |
|
δ3 |
|
|||||||||||||||||||||||||||
|
|
p=1 |
|
|
|
|
|
= (λ0 )λ0 |
(λ1 )λ1 |
=11 (δ2 +δ3 )δ2 +δ3 , |
|
|
|
|
|
|
|
|||||||||||||||||||||||
дляЯ ∏(λk )λk |
|
|
|
|
|
|
|
|||||||||||||||||||||||||||||||||
|
|
k =0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
так как (см. (2.20)) |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
λk=0 =∑δi =∑δi =∑δi =δ1 =1, |
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
i J |
|
|
|
|
i 1 |
|
i=1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
0 |
|
|
|
|
|
|
{} |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
3 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
λk=1 =∑δi = ∑δi =∑δi =δ2 +δ3. |
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
i J |
|
|
|
i |
2,3 |
|
|
i=2 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
1 |
|
|
|
|
|
{ |
} |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
168 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
3). Найдём решениедвойственной задачи [2, с. 100-109]. Заметим,что система линейных уравнений
4δ2 −δ3 = 0, |
|
|
||||
|
|
|
1 |
|
|
|
|
|
−4δ2 + |
δ3 |
= 0, |
(С.1) |
|
δ1 |
2 |
|||||
|
|
=1 |
|
|
|
|
δ |
|
|
|
|
||
|
1 |
|
|
|
|
|
имеет следующее единственное решение:
δ1 = 1, δ2 =1/2, δ3 = 2 (сложиввсе3 уравнения, получим1–(1/2) δ3 =0 δ3 =2 δ2 =1/2).
Это решение удовлетворяет неравенствам (B.2), значит двойственная программа (B.1) ÷ (B.3) совместна, причём её допустимое мно-
жество D состоит из единственного вектора δ=(1, 1/2, 2). Отсюда
на основании Теоремы 2.8 можно утверждать как о существовании оптимальных векторов у обеих задач, так и о равенстве минимумапрямой программымаксимуму двойственной (см. (2.36)), т.е.
min g0 (x, y) = max v(δ1,δ2 ,δ3 ) = v .
P D
Так как допустимое множество D состоит из единственной точки δ= (1, 1/2, 2), то она и будет точкой η=(1, 1/2, 2) максимума двойственной задачи (или программыВ), азначит
|
|
1 1 1 |
1/ 2 |
1 2 |
|
1 |
|
|
|
1/ 2+2 |
|
25 |
|
|
|
||||
v |
|
= v(η) = |
|
|
2 |
+2 |
= |
16 |
5 |
, |
|
||||||||
|
|
||||||||||||||||||
|
|
1 1/ 2 2 |
|
|
|
|
|
|
|
|
|||||||||
т.е. max v(δ) = v и максимум |
v(δ ,δ |
2 |
,δ |
3 |
) |
известен. |
|
|
|
||||||||||
D |
|
|
|
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Следовательно, в силу (2.36) |
таков жебудет |
|
и минимум исходной |
||||||||||||||||
задачи (т.е. программыА): |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
= 25 |
|
|
|
|
|
|
|||||
|
|
min g0 (x, y) = min y = g0 (t ) |
5 . |
|
|
|
|
||||||||||||
|
|
P |
P |
|
|
|
|
|
|
|
16 |
|
|
|
|
|
|
||
Вывод. |
|
Минимальное значение позинома g0 (x, y) |
известно. Ос- |
||||||||||||||||
талось найти только точку t |
его минимума. |
|
|
|
|
|
|
|
|
||||||||||
|
|
|
|
169 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
4). Найдём точку t |
= (t1,t2 ) минимумапозинома g0 (t ) . |
|
||||||||||||||||||||||||||||||||||||||
Дляопределения |
координатточки |
|
|
минимума составим систему |
||||||||||||||||||||||||||||||||||||
уравнений (2.37), которая длянашей задачи будет иметь вид |
|
|||||||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
25 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
{ } |
|
|
|
|
|||||
|
|
1 |
|
|
|
|
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0 |
|
|
|
|
|
||||||||||||
y |
= η v(η) = η v = |
16 |
|
5, |
|
|
|
|
|
1 J = 1 , |
|
|
|
|
||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
x4 y−4 |
= |
|
|
η2 |
= |
|
1/ 2 |
|
= |
1 |
, |
|
2 J |
1 |
= |
{ |
2,3 , |
1 K = |
1 , |
|||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||||||||||||||||
|
|
|
|
|
η2 +η3 |
|
|
|
(1/ 2)+2 5 |
|
|
|
|
|
|
|
|
|
|
|
|
} |
{ } |
|||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||
|
|
|
|
|
|
|
|
|
η3 |
|
|
|
|
4 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
x−1 y1/ 2 = |
|
|
|
|
|
= |
|
|
|
|
|
|
|
3 J |
|
|
|
= |
|
2,3 , |
1 K = 1 , |
|||||||||||||||||||
|
η |
|
+η |
|
|
5 |
|
|
|
|
|
|
|
|
|
|
||||||||||||||||||||||||
|
|
|
|
|
|
|
2 |
3 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
|
|
{ |
|
|
|
} |
{ } |
||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
где p=1 |
и |
|
|
k = 1, 2, …, p; |
т.е. k =1, причём |
|
λk > 0, |
так как |
|
|||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
3 |
|
|
|
|
|
|
|
|
|
|
|
|
1 |
|
|
|
|
|
|
||
|
λk =∑ηi =∑ |
ηi = ∑ |
ηi =∑ηi =η2+η3 = |
+2>0, K={1}. |
||||||||||||||||||||||||||||||||||||
|
2 |
|||||||||||||||||||||||||||||||||||||||
|
|
i J |
k |
|
|
|
|
1 |
|
|
|
|
{ |
|
} |
|
i=2 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
|
|
|
|
|
|
|
i J |
|
|
|
|
i 2,3 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||
Решая этусистему,находим |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
x = t = 25 4 |
5, y = t |
2 |
= 25 |
|
5 |
|
|
|
|
|||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
|
16 |
|
|
|
|
|
|
|
|
|
|
|
16 |
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
(из1го- |
уравнения следует, что y = |
25 |
|
|
5 , аиз 2-го, что x = 5 |
y ). |
||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
16 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
4 |
|
|
Отметим, |
что 2-е уравнениепри |
|
x = |
25 |
4 |
5, y = |
25 |
|
5 разрешимо. |
|||||||||||||||||||||||||||||||
|
|
|
||||||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
16 |
|
|
|
|
|
|
|
|
|
16 |
|
|
|
|||||
Таким образом , |
известныкоординаты |
|
|
|
|
|
x, |
|
|
y |
точки минимума |
|||||||||||||||||||||||||||||
программыА, т .е. задачи (A.1) ÷ (A.3). |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||||||||||||
5). Уточнениеи проверка (дляиспользуемых при решениизадач |
||||||||||||||||||||||||||||||||||||||||
теорем) важныхпредпосылок и положений. |
|
|
|
|
|
|
|
|||||||||||||||||||||||||||||||||
Заметим, чтопри |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||
|
|
|
|
|
|
|
|
|
|
x = 4, |
y = 5 или x* = (4, 5) |
|
|
|
|
неравенство (A.3),т .е. (2.16в) выполняется строго (т.е. найден
хотя бы один вектор x* с положительным компонентами (2.16б), для которого все вынужденные ограничения (2.16в) выполнены строго), а значитпрограмма А сильносовместна.
170