Äîêóìåíò âçÿò èç êýøà ïîèñêîâîé ìàøèíû. Àäðåñ îðèãèíàëüíîãî äîêóìåíòà : http://io.cs.msu.ru/PROgames.pdf Äàòà èçìåíåíèÿ: Mon Nov 6 19:52:58 2006 Äàòà èíäåêñèðîâàíèÿ: Mon Oct 1 19:23:46 2012 Êîäèðîâêà: Windows-1251

1

(64 )
2- , " ". 3- . 32 . 32 . 3- . . : .., .. 2006/07 . : .. . . . . . . . . . . . . - . . . . . . . . . . . - . - . . . . . . . . . . . . . . . . . . . . . . .


2 / 1 2 3 4 () 24 12 12 18 64 () 12 6 6 8 32 12 6 6 8 32

[1] .., .. . .: -, 2005. [2] .. . .: -, 2005. [3] .. . .: , 1976. [4] .. . .: , 1990. [5] .., .., .. . .: , 1986. , 1. . . 2. - . 3. . 4. . 5. 2*n m*2 . 6. . 7. p p p . 8. p p p . 9. p . 10. . 11. p . 12. . 13. 1. 14. . 15. . 16. . 17. . 18. 2.


 1. 19. . 20. .

3



1.
F (x, y ) X × Y , X, Y - . . (x0 , y 0 ) X × Y 1 F (x, y ) X × Y , F (x, y 0 ) F (x0 , y 0 ) F (x0 , y ) x X y Y (1.1) , , max F (x, y 0 ) = F (x0 , y 0 ) = min F (x0 , y ).
xX y Y

. . 1 2 ( ). 1 x X, 2 y Y . , , . F (x, y ) , X × Y . F (x, y ) . F (x, y ), - F (x, y ). , = X, Y , F (x, y ) . , . x0 , y 0 , . . . , , F (x, y ) X × Y . (x0 , y 0 ) - F (x, y ). (x0 , y 0 , v = F (x0 , y 0 )) , x0 , y 0 - , v - . . . , : X = {1, ..., m}, Y = {1, ..., n}. i, j, F (i, j ) aij . A = (aij )m×n . i, - j .

1 . , E 3 z + x2 - y 2 = 0 .


4 (i0 , j 0 ) - A, aij
0

ai

0j0

ai0 j , i = 1, ...m, j = 1, ..., n.
0j0

, ai j 0 - . 1.1. A =

i0 - -

00 . 04 (1,1) (2,1) - v . , a12 = v , (1,2) . 1.2. . () (), . , , , - . -1 1 . 1 -1

A=



, . . . , .. F (x, y ) X × Y ? , , ? . x. , , inf F (x, y ). inf F (x, y ) y Y y Y

() , x. v = sup inf F (x, y ) . v.
xX y Y

. x0 , inf F (x0 , y ) =
y Y

. y , sup F (x, y ).
xX

, . v = inf sup F (x, y ) .
y Y xX

. y 0 , sup F (x, y 0 ) =
xX

v. 1.2. v v.

. 1.1. 1) F (x, y ) X × Y ,


 1. , max inf F (x, y ) = min sup F (x, y ).
xX y Y y Y xX

5

(1.3)

2) (1.3). (x0 , y 0 ) , x0 - , y 0 - . . (1.3), X 0 ×Y 0 , X 0 Y 0 - . 1.3. min aij -4 2 2 -3

1j4

1i4

7 -1 -4 1 4 2 3 2 A= 2 2 5 2 4 -3 7 -2 max aij 7 2 7 2





, , , . v = v = 2, X 0 = {2, 3}, Y 0 = {2, 4}. X 0 × Y 0 . , . 1.2. F (x, y ) X × Y , X, Y - 1 . Y (x) = Arg min F (x, y ).
y Y def

1) W (x) = min F (x, y ) X.
y Y

2) , x X Y (x) y (x). y (x) X. . , X, Y - , F (x, y ) X × Y . , X = [a, b], Y = [c, d] . 1.2 , .
1 , , .


6 . . . . Z , z = z Z 0 < < 1 z +(1-)z Z. . h(z ), Z, , z = z Z 0 < < 1 h(z + (1 - )z ) h(z ) + (1 - )h(z ). (1.4) , h(z ) . (1.4) (>), h(z ) ( ).
m

2.6
i=1

2 zi . .

1.3. 1 . 1.3. X E m Y E n - , F (x, y ) X × Y . , y Y F (x, y ) x x X y . F (x, y ) X × Y .

2.
, ( ). . , ( ?). . . X. - x X , . . 1) X = {1, ..., m}, . p = (p1 , ..., pm ),
m

pi = 1 , p
i=1

i

0, i = 1, ..., m.

p, i pi . ,
1

.


 2.

7

p0 = (1/2, 1/2), . 2) X = [a, b], . - [a, b], .. , : (x) = 0, x < a, (x) = 1, x b. x , { x} (x) x. 3) X - . X. , :
m m

(x) =
i=1

pi Ix(i) (x),
i=1

pi = 1 , p

i

0, x(i) X, i = 1, ..., m,

Ix(i) (x) = 1, x = x(i) , 0, x = x(i) .

h(x) :
m

h(x)d(x) =
X i=1

pi h(x(i) ).

{} - X. , X {}. , x Ix . X , i p = (0, ..., 0, 1, 0, ..., 0), i- , X = [a, b] x [a, b] , 1 x. X ( ). = X, Y , F (x, y ) . {} . , { } - , .. Y . F (, ) =
XY

F (x, y )d(x)d (y ).

, . . = {}, { }, F (, )


8 . . (0 , 0 , v = F (0 , 0 )) . 0 , 0 , v - . , . , m × n- A = (aij ). -
m

P = {p = (p1 , ..., pm ) |
i=1

pi = 1, p

i

0, i = 1, ..., m},

-
n

Q = {q = (q1 , ..., qn ) |
j =1

qj = 1, q

j

0, j = 1, ..., n},

-
m n

A(p, q ) =
i=1 j =1

pi aij qj .

, = P, Q, A(p, q ) - . 2.1 ( ). . . , A(p, q ) P × Q. P, Q - , A(p, q ) P × Q, p q . 1.3 A(p, q ) P × Q . , . 1) . , p0 , . 2) , . .

2.2. . ( 1) , : , . , ( 2 - ). H = (hij )3×3 - , bi - i- . A = (bi hij )3×3 - , - . p0 = (1/2, 1/4, 1/4) - . , , - .


 3.

9

: - . . X × Y = [a, b] × [c, d]. - X Y - F (, )
b d

F (, ) =
a c

F (x, y )d(x)d (y ).

, c = {}, { }, F (, ) .

3.
. . 3.1. : 1) inf F (, ) = min F (, y ) {};
{ } {} y Y

2) sup F (, ) = max F (x, ) { }.
xX

, 3.1 . 1. v : v = max min F (, y ) = min max F (x, ).
{} y Y { } xX

2. (0 , 0 , v ) , , F (x, 0 ) v F (0 , y ) x X y Y . ()

3.1 . A : 1) min A(p, q ) = min A(p, j ) p P ;
q Q pP 1jn

2) max A(p, q ) = max A(i, q ) q Q.
1im

1. v A : v = max min A(p, j ) = min max A(i, q ).
pP 1 j n q Q 1 i m

2. (p0 , q 0 , v ) A, , A(i, q 0 ) v A(p0 , j ), i = 1, ...m, j = 1, ..., n. ()


10 3.1 . , () 2 3.1
m

A(p0 , j ) =
i=1

p0 aij i

p0 ,
n

A(i, q 0 ) =
j =1

aij q

0 j

q 0 A v . 3.1. - c1 cn A= ... c2 : c2 c1 ... ...
n

... ... ... cn

cn



cn-1 . ... c1

, p0 = q 0 = (1/n, ..., 1/n), v =

ck /n - k=1

. , () , . , p0 = q 0 = (1/2, 1/2), v = 0 - . (p0 1) p0 > 0 i 0 2) qj > 0 3.2 ( ). , q 0 , v ) - A. A(i, q 0 ) = v ; A(p0 , j ) = v .

. (p0 , q 0 , v ) - A. 1) A(i, q 0 ) < v p0 = 0; i 0 2) A(p0 , j ) > v qj = 0. , . A(i, q 0 ) v 0 (A(p0 , j ) v ) () p0 0 (qj 0) . i ( ), 3.2 ( ). : (p0 , q 0 , v ) A
0 p0 (v - A(i, q 0 )) = qj (A(p0 , j ) - v ) = 0, i = 1, ..., m, j = 1, ..., n. i

3.2. A, ai > 0. , p0 , q 0


 4. . 3.2
n 0 A(i, q 0 ) = ai qi = v , i = 1, ..., n, i=1 0 n + 1 qi , i = 1, ..., n, v , q v /ai , i = 1, ..., n, 1 v= n . k=1 1 ak 0 i 0 qi = 1.

11

=

, p0 = q 0 .

4.
. . I. . i1 A i2 , , i1 . , . . , a = (a1 , ..., al ) b = (b1 , ..., bl ), ai bi , i = 1, ..., l. , >. , a b. . a(i) , i = 1, ..., m, p
m m i

0, i =

1, ..., m, a
i=1 ( i)

pi = 1,
i=1

pi a

( i)



pi .

4.1 ( ). A . . , . . , . . . . 4.1 ( ). A .


12 . , . . 4.1. 3 A = 1 2 1 3 2 5 3 . 1

. . ^ A= 3 1 1 3

(p, q , v ) = ((1/2, 1/2), (1/2, 1/2), 2). ^^ (p0 , q 0 , v ) = ((1/2, 1/2, 0), (1/2, 1/2, 0), 2). II. 2 × n m × 2. 2 × n- A. p = (p1 , 1 - p1 ) p1 [0, 1]. , 3.2 , v = max min A(p, j ) = max
pP 1 j n 0 p1 1 1 j n

min [a1j p1 + a2j (1 - p1 )].

[0,1] lj (p1 ) = a1j p1 + a2j (1 - p1 ) kj = a1j - a2j , j = 1, ..., n, p0 min lj (p1 ) - (. 4.1). 1
1jn

lj1 T v lj2 1 0 p0 1 . 4.1

Ep

1

. .


 4.

13

) 0 < p0 < 1. 1 . 4.1. lj1 lj2 , (p0 , v ) kj1 0, kj2 0. 1 kj1 q + kj2 (1 - q ) = 0. (4.2)

q , [0,1]. (4.2) , lj1 (p1 )q + lj2 (p1 )(1 - q ) . q , j = j1 , 0 0 q : qj = 1 - q , j = j2 , 0, j = j1 , j2 , , p1 [0, 1] A(p, q 0 ) = lj1 (p1 )q + lj2 (p1 )(1 - q ) = v . 0 ) p1 = 0. 2 . . ) p0 = 1. 1 , ), . 4.2. A = (. 4.2) l1 (p1 ) = (-1)p1 + 2(1 - p1 ) = l2 (p1 ) = (-2)p1 + 4(1 - p1 ) = l3 (p1 ) = 3p1 + 1(1 - p1 ) = 1 + , l1 l3 . -1 -2 2 4 3 . 1

2 - 3p1 , 4 - 6p1 , 2 p1 , p0 = 1/5 - 1

4T t t l2 t t ÅÅl3 Å t 2 ÅÅ tÅ ÅÅt v Å t 1Å t t E t l1 1 0 1 0 p1 = 5 t . 4.2

p

1

v = l1 (p0 ) = 7/5 p0 = (1/5, 4/5). j1 = 3, k3 = 2, j2 = 1, k1 = -3. 1 2q + (-3)(1 - q ) = 0 q = 3/5. q 0 = (2/5, 0, 3/5) - . () 2 3.1 (p0 , q 0 , v ).


14 m × 2- A. q = (q1 , 1 - q1 ) q1 [0, 1]. , 3.2 , v = min max A(i, q ) = min
q Q 1 i m 0 q1 1 1 i m

max [ai1 q1 + ai2 (1 - q1 )].

max li (q1 ) li (q1 ) =
1im 0 ai1 q1 + ai2 (1 - q1 ), i = 1, ..., m, [0,1] q1 . . , (4.2).

III. . - , -. , v . 3.2 ,
m

v = max min A(p, j ) = max min
pP 1 j n

pP 1 j n i=1

pi aij .

u v = max u,
(u,p)B m

B = {(u, p) |
i=1 m

pi aij

u, j = 1, ..., n,

pi = 1 , p
i=1

i

0, i = 1, ..., m}.

, p P u (u, p) B min A(p, j ).
1jn

v > 0, , u . zi = pi /u, z = (z1 , ..., zm ). , (u, p) B ,
m m

zi = 1/u,
i=1 i=1

aij z

i

1, j = 1, ..., n, z

i

0, i = 1, ..., m.

v = max u =
(u,p)B

1
m

, z
0 i

i=1 0

z -
m

zi min
i=1


 5.
m

15

aij z
i=1

i

1, j = 1, ..., n, z

i

0, i = 1, ..., m.

(I )

z 0 : v =
m

1/
i=1

0 zi , p 0 = v z 0 .

, v = min max A(i, q ) =
q Q 1 i m

1
n j =1 0 wj

,

w0 -
n

wj max
j =1 n

aij wj
j =1

1, i = 1, ..., m, wj

0, j = 1, ..., n.

(I I )

q 0 = v w0 - . (I ) (I I ) .

5.
. T t = 1, ..., T . t - xt , yt . 1. x1 U1 , , , y1 V1 (x1 ) = V1 (ž). t - 1 x1 , ..., xt-1 , y1 , ..., yt-1 . xt = (x1 , ..., xt ), y t = (y1 , ..., yt ). t. , xt-1 , y t-1 , xt Ut (xt-1 , y t-1 ) = Ut (ž). yt Vt (xt , y t-1 ) = Vt (ž), xt , y t-1 , xt . T (xT , y T ), . - , . (xT , y T ) F (xT , y T ) . . t xt xt : xt = xt (xt-1 , y t-1 ), ~ ~ xt-1 , y t-1 . ~ xt Ut . , x1 = x1 , ~ ~ .
T

~ x = (xt , t = 1, ..., T ) X = ~ ~
t=1

~ Ut .


16 , t yt yt : yt = yt (xt , y t-1 ), ~ ~ ~ xt , y t-1 . yt Vt . ~
T

~ y = (yt , t = 1, ..., T ) Y = ~ ~
t=1

~ Vt .

x, y , - ~~ . (x, y ) : ~~ x1 = x1 , y1 = y1 (x1 ), x2 = x2 (x1 , y1 ) .. ~ ~ ~ ~ F (x, y ) = F (xT , y T ), (xT , y T ) - , x ~~ y . , ~ ~~ = X , Y , F (x, y ) . ~~ : , Ut (ž), Vt (ž) ; , Ut (ž) Ut , Vt (ž) Vt , F (xT , y T ) U1 × ž ž ž × UT × V1 × ž ž ž × VT . x0 = (x0 , t = 1, ..., T ), y 0 = (yt , 1, ..., T ), ~ ~t ~ ~0 . F (xt , y t-1 ) (xt , y t ) . x0 , yt , . ~t ~0 yT . ~0 (xT , y T -1 ) yT (xT , y ~0
T -1 0 ) = yT : def def

F (xT , y

T -1

0 , yT ) =

yT VT (ž)

min

F (xT , y

T -1

, yT ) = F (xT , y

def

T -1

).
-1

x0 . (xT ~T def x0 (xT -1 , y T -1 ) = x0 : ~T T F (xT
-1

,y

T -1

)

, x0 , y T

T -1

)=

xT UT (ž)

max F (xT

-1

, xT , y

T -1

) = F (xT

def

-1

,y

T -1

).

yT , x0 , ..., yt+1 , x0+1 , F (xT , y ~0 ~T ~0 ~t yt , x0 , F (xt , y ~0 ~t T t.
t-1 T -1

), ..., F (xt , y t ).

), F (xt-1 , y

t-1

) -


 5.

17

, x0 , y 0 . , ~~ Ut (ž), Vt (ž) , x0 , y 0 , . ~~ , 1.2 . v = max F (x1 ) ~
x1 U
1

def F (x1 )

=

x1 U1 y1 V1 (ž)

max

min F (x1 , y1 ) = ... F (xT , y T ).

= max

x1 U1 y1 V1 (ž)

min ... max

xT UT (ž) yT VT (ž)

min

5.1 (). ( ) (x0 , y 0 , v ). ~~~ 5.1. , . T , T . , T 1 . . , Ut (xt-1 , y t-1 ) ( ) t- , (xt-1 , y t-1 ). Vt (xt , y t-1 ) t- . 1, , F (xT , y T ) = 0, , 1/2, . . , , . 5.2. 5 2 A= 3 4 3 7 2 0 1 2 3 2 4 0 . 3 5

M1 = {1, 2} M2 = {3, 4}, - N1 = {1, 2} N2 = {3, 4}. . 1. {1, 2} M , A. , ,
1 , , .


18 {1, 2} N , A. 2. i M , , , j N , , , i. aij . , . k 2 2 k k 2 1 d d d2 1 1 d2 d dk k dk k 3 3 1 2 1 t2 3 t4 t t t 1 t2 3 t4 k t2 k k k 3 3 2 tk tk k k 0 2 0 1 ?f ?f ?f ?f ?f ?f ?f ?f ?f ?f ?f ?f ? f 2 1? f2 ?f ?f ?f ?f ? f 4 3 ? f4 1 3 ? f ? f 3 ? f4 ?f ?f 3 ? f 4 1 ? f2 1 ? f2 5 32 7 ? f 32 5 ?f?f ?f3
1

1

4

2

03

2

4

0

. 5.1 () 1 ( ), .. , , F (, , i, j ) = aij . F (, , i) = min F (, , i, j ), -
j N

F (, ) = max F (, , i), - F () = min F (, ),
iM


=1,2

- v = max F () = 2. ~
=1,2

~ x0 = (0 , ~0 (, )), y 0 = ( 0 (), ~0 (, , i)) : ~ i ~ j ~ ~ 0 = 2, ~0 (2, 1) = 3, ~0 (2, 2) = 3, 0 (1) = 2, 0 (2) = 1, i i ~0 (1, 2, 1) = 3, , ~0 (1, 2, 2) = 4, ~0 (2, 1, 3) = ~0 (2, 1, 4) = 2. j j j j , , . , i . , 0 = 2 ~0 (, ) = 2.
1

, .


 6.

19

6.
. . . x X, - y Y . . , . (x, y ) . F (x, y ), - G(x, y ), X × Y . , , . , = X, Y , F (x, y ), G(x, y ) . , , x X, y Y , . ( , ..) . , (, ) () 1 . (), . , F (x, y ) G(x, y ) X × Y . 1 . x X . y Y , x. 2 : xy . , . , - , , . 1 . : () ( ) x . y , x. F1 1 . , , x, y Y (x) = Arg max G(x, y ),
y Y

.. G(x, y ). , , Y (x), y Y (x). W (x) = min F (x, y )
y Y (x)

( ) x.
1

-

(pricipal-agent).


20 , Y (x) - . , min : F1 = sup min F (x, y ).
xX y Y (x)

y Y (x)

. > 0. x - 1 , W (x ) F1 - . , sup . 1 - F1 - x > 0. 2 . x y . f : Y X. 2 1 {f }. 2 : f y x = f (y ). : f (y ) - , y . F2 2 . , , f , y Y (f ) = Arg max G(f (y ), y ).
y Y xX

Y (f ) , Y (f ) , Y (f ), Y (f ) = Y,

f . y Y .1 Y (f ) = , Y (f ) = .

y Y (f ). f W (f ) = inf F (f (y ), y ).
y Y (f )

F2 = sup inf F (f (y ), y ).
f {f } y Y (f )

. > 0. f - 2 , W (f ) F2 - . F2 , {f }. F2 , X Y . F2 . X (y ) = Arg max F (x, y ) - , X (y ) = Arg max G(x, y ) - xX (y ) xX

, . f : y Y f (y ) X (y ).
1 , , , , G(f (y ), y ) .


 6.

21

: G2 = max min G(x, y ) - y Y xX , f : f (y ) Arg min G(x, y ) y Y ;
xX

E = Arg max min G(x, y ) - ;
y Y xX

D = {(x, y ) X × Y | G(x, y ) > G2 }; sup F (x, y ), D = , K = (x,y)D -, D = ; M = min max F (x, y ).
y E xX

6.1 (). 2 F2 = max[K, M ]. 6.2. 1 , 2 : X = Y = [0, 1], F (x, y ) = 3x/4 + y /2, G(x, y ) = (x - y )2 . 1 . F1 = sup min (3x/4 + y /2), 0 x 1 y Y (x) {1}, 0 x < 1/2, 2 Y (x) = Arg max (x - y ) = {0, 1}, x = 1/2, 0y1 {0}, 1/2 < x 1. W (x) = min (3x/4 + y /2) . 6.1.
y Y (x)

W (x)

T b & & & & &

7/8 & 3/4 & & & & Ex 1/2 1 . 6.1

F1 = 7/8, x = 1/2 - 4/3 - - . , F1 . 2 . G2 = max min (x - y )2 = 0, D = {(x, y ) | (x - y )2 > 0}, K = 5/4 = F2 ,
0 y 10 x 1

(x , y ) = (1 - 4/3, 1), f (y ) = - - .

x , y = y , y, y = y ,


22 1 . Y (x) = Arg max F (x, y )
y Y (x)

- , . . (x0 , y 0 ) , x0 Arg max max F (x, y ), y 0 Y (x0 ).
xX y Y (x)

, , x, , . , . g : x Y g (x) Y (x). 6.1 F (x, g (x)) X. , X x0 . y 0 = g (x0 ) (x0 , y 0 ) .

7.
A , . a sa S a . , . s = (sa , a A) S =
aA

Sa,

. a ua (s), S, , , . , = A, S a , ua (s), a A . . . s = (sa , a A) ( ) , a A
sa S

max ua (s||sa ) = ua (s). a

sa , , . s||sa s sa . , , a, s, a sa . , sa , s, a . , , - , .


 7.

23

u2 (s1 , s2 ) -u1 (s1 , s2 ), - . - u1 (s1 , s2 ) S 1 × S 2 . , , : , , . , . , . , . . . . , : S 1 = {1, ..., m}, S 2 = {1, ..., n}. i S 1 , j S 2 - . A = (u1 (i, j ))m×n = (aij )m×n , B = (u2 (i, j ))m×n = (bij )m×n . (i0 , j 0 ) - , aij
0

ai

0j0

, i = 1, ..., m,

b

i0 j

b

i0 j

0

, j = 1, ..., n.

7.1. : A= 1 0 0 , 2 B= 2 0 0 . 1

. ( ) , : ( 1 ) ( 2). , 1 , - 2 . , - 2, - 1. , - . : (1,1) (2,2). , - . , 2, - 1. . . , , . , . , . 7.2. : A= -8 0 , -10 -1 B= -8 0 -10 -1

. ( 1 2), , . (


24 1) ( 2) . ( (1,1)), 8 . ( (2,2)), , - , , , 1 . , , ( (2,1) (1,2)), ( ), - 10 . (1,1): . (2,2), , . , . . s , s, ua (s) ua (s), a A - . 7.2 . (!). , . 205 221 , B= . 223 078 (1,1) - , 1 . , 7.3. A = W (1) = min a1j = 0,
1j3

W (2) = min a2j = 2.
1j3

1 . , . 2, , 0. ? - , , , . , 1.3. . 7.1 (). f : S S - S . s : f (s) = s. , . , S - , . , S - , f - < 2 , f . 7.1. S a , a A, - . , ua (s) S sa sb , b = a. .


 7.

25

S a (sb , b = a) = Arg max ua (s). sa a a
s S

S a (sb , b = a), a f a 7.4.

A. , (. 7.2), f a (sb , b = a) = sa , a A. : 2 3 5 -1 7547 4 -2 3 4 , B = 4 5 5 4 . A= 2 -3 6 6 2 15 4 -1 25 3 8736

A , B - . (3,3) - . 7.5. = X, Y , F (x, y ), G(x, y ) , X, Y F (x, y ), G(x, y ) - . X = Y = [0, 1], F (x, y ) = -3x2 + 2y 2 + 7xy , G(x, y ) = -(x + y - 1)2 . F (x, y ) G(x, y ) x y . - x(y ) = 7y /6, 0 y 6/7, y (x) = 1 - x. 1, 6/7 < y 1,

x(y 0 ) = x0 , y (x0 ) = y 0 , x0 = 7/13, y 0 = 6/13. 7.6. . - . x y - , , 0 < c1 c2 - , .. . p(x + y ) x + y . F (x, y ) = (p(x+y )-c1 )x G(x, y ) = (p(x+y )-c2 )y - , . p(x + y ) = K/(x + y ) , 1 > 0. , X = [0, (K/c1 )1/ ], x > (K/c1 )1/ . Y = [0, (K/c2 )1/ ]. , 7.1 (x0 , y 0 ) . x0 > 0, y 0 > 0. x0 , y 0 Fx (x0 , y 0 ) = Gy (x0 , y 0 ) = K K x0 - c1 - 0 = 0, (x0 + y 0 ) (x + y 0 )+1 (x0 K K y 0 - c2 - 0 = 0. 0 ) +y (x + y 0 )+1


26 , x0 + y 0 = (x0 , y 0 ) = (2 - )K 1 (2 - )K c1 + c2
(+1)/

(2 - )K c1 + c2

1/

,

c2 + ( - 1)c1 , c1 + ( - 1)c2 .

y 0 > 0, c1 + ( - 1)c2 > 0. c1 + ( - 1)c2 0, : (1 - )K 1/ , y 0 = 0. x0 = c1 , A = (aij )m×n , B = (bij )m×n . , : p P, q Q. -
m n m n

A(p, q ) =
i=1 j =1

pi aij qj , B (p, q ) =
i=1 j =1

pi bij qj .

= P, Q, A(p, q ), B (p, q ) . P Q - - , A(p, q ) B (p, q ) . 7.2 (p0 , q 0 ), ( ) . max A(p, q 0 ) = A(p0 , q 0 ); max B (p0 , q ) = B (p0 , q 0 ).
pP q Q

3.1 . 7.1. (p0 , q 0 ) , , A(i, q 0 ) B (p0 , j ) 1) p0 > 0 i 0 2) qj > 0 A(p0 , q 0 ), i = 1, ..., m, B (p0 , q 0 ), j = 1, ..., n. ()

7.3 ( ). (p0 , q 0 ) - . A(i, q 0 ) = A(p0 , q 0 ); B (p0 , j ) = B (p0 , q 0 ).

X = {1, ..., m}, Y = {1, ..., n}.


 7.

27

7.4. (p0 , q 0 ) , , X 0 X, Y 0 Y v1 , v2 , 0 0 aij qj = v1 , i X 0 , aij qj v1 , i X 0 , / 0 0 j Y j Y (7.1) 0 0 qj = 1, qj 0, j Y 0 ,
j Y
0



p0 bij = v2 , j Y 0 , i
0

p0 b i
iX
0

ij

v2 , j Y 0 , / (7.2)

iX

iX

0

p0 = 1, p i

0 i

0, i X 0 .

7.4 . 2 × n : A= a11 a21 žžž žžž a1 a2
n n

,

B=

b b

11 21

žžž žžž

b b

1n 2n

.

X 0 = {1, 2}, Y 0 = {j1 , j2 }. j1 , j2 (7.1) (7.2). p0 b 1
1j1

+ (1 - p0 )b 1

2j1

= v2 ,

p0 b 1

1j2

+ (1 - p0 )b 1

2j2

= v2 .

(7.3)

p0 , v1 0 p0 1. p0 = (p0 , p0 ) 1 1 12 () : p0 b1j + (1 - p0 )b2j v2 j = j1 , j2 . (7.4) 1 1 (7.4) , j1 , j2 . (7.4) . a1j1 q + a1j2 (1 - q ) = v1 , a2j1 q + a2j2 (1 - q ) = v1 . (7.5) q


q , v1 (7.5), 0 11 . j = j1 , q , 0 0 q : qj = 1 - q , j = j2 , 0, j = j1 , j2 ,

() (7.5). , (p0 , q 0 ) - . . 0 p1 1 lj (p1 ) = p1 b1j + (1 - p1 )b2j , j = 1, ..., n. lj j1 , j2 , p0 , v2 1 (7.3), 0 p0 1 (7.4). 1 (7.5) 0 q 1.
1

j1 , j2 .


28 245 , B= 421 3 0 2 2 0 . 3

7.6. A =

T l1 b b l2 2 l3 0 1 2 1 3
3 3

E

p

1

. 7.1 l1 (p1 ) = 3p1 , l2 (p1 ) 2, l3 (p1 ) = 3(1 - p1 ). ( l2 l3 . 7.1) p0 = 1/3. 1 4q + 5(1 - q ) = v1 , 2q + (1 - q ) = v1 . (7.5)

q = 2 > 1. , l1 l2 . p0 = 2/3. 1 2q + 4(1 - q ) = v1 , 4q + 2(1 - q ) = v1 (7.5)

q = 1/2, v1 = 3. (p0 , q 0 ) = ((2/3, 1/3), (1/2, 1/2, 0)) - . 7.7. . 100 . 1.3 . , 1 . , 0.3 . (). ( 1) ( 1), ( 2), . , , 100 ., - 130 . , . 0.12 . , 4/5. , 0.3 ., 0.2 . . ( 2) ( 1), ( 2). , . ,


 8.

29

. 100 100 -12 0 A= , B= . 90 130 40 , , 100(0.8(4/5) + 1.3(1/5)) = 90 ., 100(0.08(4/5) - 0.12(1/5)) = 4 . , . ,

(p0 , q 0 ) = ((1/4, 3/4), (3/4, 1/4)). p0 q 0 : 25 c , 75 . 7.5. A . . 7.5 . B . . i = 1, ..., n, - n , . fi (t) , t i- . x = (x1 , ..., xn ) : i- xi . : , -, , - , A xi - .
n

X= xE -

n i=1

xi = A, xi

0, i = 1, ..., n ,

n

X = xE

n i=1

xi = A, xi

0, xi Z, i = 1, ..., n ,

Z - .

8.
: max min fi (xi ) = min fi (x0 ). i
xX 1 i n 1in

(8.1)


30 min fi (xi ), .. 1in

. : , . x0 . (8.1) , fi (t) [0, A]. , , f1 (0) f2 (0) ... fn (0).

, : , . , . 8.1 (). x0 - (8.1). x0 : k , 1 k n, fi (x0 ) = fk (x0 ) < fk+1 (0), i = 1, ..., k - 1, i k x0 = 0, i = k + 1, .., n. i (8.2)

f1 (0) = f2 (0) = ... = fn (0), k = n. x0 . . , . . k = n, n - 1, ..., 1
k

fi (x0 ) = C, i = 1, ..., k , i
i=1

x0 = A i

C, x0 , ..., x0 . 1 k x0 k < n C < fk+1 (0), x0 = (x0 , ..., x0 , 0, ..., 0) - 1 i k . k . 8.1. . . xi - , i- , ij - j - , j = 1, ..., xi . , ij , mi Vi . mi - -, .. . fi - , .
xi

mi (1 + fi ). i =
j =1

ij - i-


 8. . fi , , {
i 1

31

xi mi (1 + fi )} =

Yi =

def

i - xi mi xi Vi

xi mi fi xi Vi

. xi , Yi . , y1- - 1 - (y ) = ,
y

1 (y ) = 2

e-x
-

2

/2

dx

- . Vi y1- , i = 1, ..., n. fi (xi ) = xi mi A - . x X . xi . min max fi (xi ).
xX 1 i n

, - . :
xX 1 i n

max min fi (xi ) = min fi (x ). i
1in

(8.3)

fi (t) - . I = {1, ..., n} x X I (x) = Arg min fi (x).
iI

|I (x)| I (x). 8.2. x - (8.3), |I (x )| . : x > 0, min fi (x ) j i
1in

fj (x - 1). j

(8.4)

, (8.4) . (8.3). x(1) - . , k -
1

i- .


32 (k 1) x(k) . x(k) (8.4), 8.2 . , (k ) (8.4) . j, xj > 0 fj (xj
(k )

- 1) > min fi (xi ) = fl (xl ).
1in k+1)

(k )

(k )

x(

xi

(k+1)

: (k ) xj - 1, i = j, = x(k) + 1, i = l, l k) ( xi , i = j, l .

: 1) |I (x(k) | = 1. ( min fi (xi
1in

k+1)

) > min fi (xi ).
1in

(k )

2) |I (x(k) )| > 1.
1in

min fi (xi

(k+1)

) = min fi (xi ), |I (x(
1in

(k )

k+1)

)| < |I (x(k) )|.

, , I (x(k) ). , , X . x(1) , . 8.1.
xX 1 i 4

max min ix2 = min i(x )2 , i i
1i4 4

X = xE
4 i=1

xi = 10, xi

0, xi Z, i = 1, 2, 3, 4 .

: max min ix2 = min i(x0 )2 , i i
xX 1 i 4 4 1i4

X= xE
4 i=1

xi = 10, xi

0, i = 1, 2, 3, 4 .

fi (t) = it2 , fi (0) = 0, i = 1, 2, 3, 4. 8.1 x0
4

ix2 i

= C, i = 1, 2, 3, 4,
i=1

xi = 10.


 9. x0 = i C /i, i = 1, 2, 3, 4, C = 10
i=1

33



C :
4 -1

1 i

.

, x0 3.59, x0 2.54, x0 2.07, x0 1.8. 1 2 3 4 x(1) = (4, 3, 2, 1). x0 . i 1 2 3 4 xi 4 3 2 1
(1)

i xi 16 18 12 4

(1) 2

i xi

(1)

-1 9 8 3 0

2

xi 3 3 2 2

(2)

i xi 9 18 12 16

(2) 2

i xi

(2)

-1 4 8 3 4

2

I (x(1) ) = {4} (8.4) x(1) j = 1. , I (x(2) ) = {1} (8.4) . , x(2) - .

9.

n n

max
xX i=1

fi (xi ) =
i=1

fi (x0 ). i

(9.1)

. A n , fi (t) - , t i- . (8.1), fi (t) - . , [0, A]. . 9.1 (). x0 - (9.1). , : fi (x0 ) = , x0 > 0, i i (9.2) fi (x0 ) , x0 = 0. i i fi (t) , (9.2) . , fi (t) f1 (0) f2 (0) ... fn (0), fi (0) < 0, i = 1, ..., n, (9.3)

l, x0 > 0, i = 1, ..., l, x0 = 0, i = l + 1, ..., n. i i 9.1. . (9.4)


34 n i = 1, ..., n. i- t, 1 - e-÷i t , ÷i > 0. pi i- . A - . x = (x1 , ..., xn ) X ,
n

i xi .
i=1

pi (1 - e-÷i xi ) -

, . fi (t) = pi (1 - e-÷i t ) (9.1). , fi (t) = -pi ÷2 e-÷i t < 0. , fi (t) . i fi (0) = pi ÷i : p1 ÷1 p2 ÷2 ... pn ÷n .

(9.4) l, x0 > 0, i = 1, ..., l, x0 = 0, i = l + 1, ..., n. i i (9.2) fi (x0 ) = , i = 1, ..., l, i fi (x0 ) , i = l + 1, ..., n. i x0 = i 1 ln(pi ÷i ) - ln , i = 1, ..., l. ÷i ÷i (9.5)

,
l

A=
k=1

ln(pk ÷k ) - ln ÷k

l

k=1

1 . ÷k

ln (9.5) x0 i ln(pi ÷i ) 1 = - ÷i ÷i
l

k=1

ln(pk ÷k ) -A ÷k

l

k=1

1 ÷k

-1

, i = 1, ..., l.

pi ÷i , x0 , i = 1, ..., l, i , x0 > 0 l
l

A>
k=1

ln(pk ÷k ) - ln(pl ÷l ) ÷k

l

k=1

1 . ÷k

(9.6)

fi (0) = pi ÷i , i = l + 1, ..., n,


 9.

35

pl+1 ÷l+1 , pi ÷i .
l

ln =
k=1

ln(pk ÷k ) -A ÷k

l

k=1

1 ÷k

-1

.


l

ln(p

l+1

÷l

+1

)
k=1

1 ÷k

l

k=1

ln(pk ÷k ) - A. ÷k

ln(pl+1 ÷l+1 )(÷l+1 )-1 l+1 l+1 ln(pk ÷k ) 1 A - ln(pl+1 ÷l+1 ) . (9.7) ÷k ÷k
k=1 k=1

, l (9.6),(9.7), l = n. , (9.6) l = 1. ,
l

k=1

ln(pk ÷k ) - ln(pl ÷l ) ÷k

l

k=1

1 ÷k

l. . (9.1):
n xX n

max
i=1

fi (xi ) =
i=1

fi (x ) i

(9.8)

fi (t) - . , , : xi > 0, fi (xi ) (fi (xi + 1) + fi (xi - 1))/2 fi (xi ) - fi (xi - 1) fi (xi + 1) - fi (xi ). (9.9)

(9.9) , fi . . 9.1. fi (t), (9.9), fi (t) - fi (t0 ) (fi (t0 + 1) - fi (t0 ))(t - t0 ), t > t0 (9.10) fi (t) - fi (t0 ) (fi (t0 ) - fi (t0 - 1))(t - t0 ), t < t0 (9.11)

9.2 (). x - (9.8). x x > 0 fj (x ) - fj (x - 1) max [fi (x + 1) - fi (x )]. (9.12) j j j i i
1in