Кулик Елементы теории принятия решений 2010

ния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

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

Заметим, что(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а).

Такимобразом

,условиесходной

задачи есть программаА .

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

λk=0=∑δi = ∑

4

δi = ∑δi=δ1+δ2+δ3+δ4=1.

0

{ }

i=1

i J

i 1,2,3,4

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 )

известен.

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 .

найти

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

4δ2 −δ3 = 0,

1

−4δ2 +

δ3

= 0,

(С.1)

δ1

2

=1

δ

1

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