close

Вход

Забыли?

вход по аккаунту

?

danil-ti

код для вставкиСкачать
МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ
Санкт-Петербургский
государственный университет аэрокосмического приборостроения
?. ?. ???????????, ?. ?. ?????????,
?. ?. ???????
?????? ???.
???????? ???????
????? ??????
Санкт-Петербург
2003
??? 519.8
??? 22.18
?18
??????????? ?. ?., ????????? ?. ?., ??????? ?. ?.
?18 ?????? ???. ???????? ???????: ????? ??????/ ???????. ???., 2003,
36 ?.: ??.
? ?????? ?????? ?????????? ???????? ??????? ?????? ???. ????????
??????????? ?????? ????????????????? ???. ????????? ??????? ??????? ????????? ???.
????? ?????? ???????????? ??? ?????????, ??????????? ?? ????????????? ??????????????? ?????? ? ??????????.
??????????:
??????? ?????? ??????????
?????-?????????????? ???????????????? ????????????
???????????????? ???????????????;
?????? ?. ?. ???????
??????????
???????????-???????????? ??????? ????????????
? ???????? ?????? ??????
© ???????, 2003
??????? ???????
??????????? ????? ??????????
????????? ?????? ??????????
??????? ?????? ??????????
?????? ???.
???????? ???????
????? ??????
???????? ?. ?. ??????????
???????????? ??????? ?. ?. ?????????
????????? ? ?????? 26.09.03. ?????? 60Ч84 1/16. ?????? ????????. ?????? ????????. ???. ???. ?. 2,32. ??. -???. ?. 2,13.
????? 100 ???. ????? ?
???????????-???????????? ?????
????? ??????????? ?????????? ? ???????????? ??????????
????? ??????????? ??????????
???????
190000, ?????-?????????, ??. ?. ???????, 67
2
1. ???????? ? ??????? ???????????? ?????? ???
? ??????? ? ???????? ????? ??????????? ???????, ? ??????? ?? ???
???? ????????? ????? ????????????? ???????? ? ??????????? ?????????? ?????? ??? ?????????? ????? ?????. ????? ??????? ??????????
???????????. ????????? ???????? ????????? ???????????? ?????? ???.
??? ?????????? ????? ???????? ?????? ???????, ????????????? ?
???????? ????? ????????:
??? ? ??? ? ???? ??????? ?????????;
?????? ????????? ?????? ????? ???????;
??? ? ???? ??????? ????????????? ? ? ??? ??? ?????????????????? ???????.
?????????? ????????? ??????? ????????????? ??????????.
???? ?? ??????????? ???? ??????? ?????????????, ?????????-?????????????? ??????? ??????? ? ???????????????, ????????????????
????????? ? ? ??????? ??????, ?????????? ??? ????????. ????????:
???????? ? ??????????, ??????? ??????????????? ????????;
????????? ??????????????, ???????????? ?? ????? ? ??????????
??????????? ????? ??????????? ?? ???? ??????, ??????? ? ????? ? ????
??? ???????????????, ??? ? ??????????? ????????;
??????????? ??? ???????? ???, ??????????? ? ???????????? ?????????, ??? ? ??????? ??????????? ?????? ?????????? ????? ???????
??? ????????????? ??????? ? ????????????????, ??????????? ? ?????????? ? ?. ?.
???????? ????? ????????? ????? ?? ???????? ?????, ??????? ???????? ?? ?????? ????????????? ????????, ?? ?????????????? ???????? ?????? ? ???? ?? ????. ????????:
??????????? ????????? ?????????????? ???????-????????????? ?????????? ? ???????? ??????????????? ???????: ??????????? ?????????, ??????????? ?????????, ???????????? ??????????, ???????? ? ?????????;
???????????? ????????????? ???????? ????????? ??????????????
??????????, ????????????? ? ????????: ???? ??????? ????????????,
????????? ???????, ???????? ????????????? ???????? ? ?. ?.;
???????? ????? ?????????? ?? ?????? ? ?????????? ????????????
???????? ????????? ??????????, ?? ? ??? ????????? ???????? ??? ???
???? «????????? ???» (?????? ??? ?????????? «??? ? ????????»).
????? ??????????????? ???????? ????????? ?????? ???? ??????????? ? ???????????????? ??????: ???????, ???????????????, ?????????????, ??????????.
3
???????, ????????? ??????????? ???????? ???????? ??????? ????:
????????, ?????????, ?????????, ??????? ??? ? ?. ?.
??? ????????? ?????????? ?????????:
?? ???? ?? ??? ?????????? ??????? ?? ????? ???????, ???????????
?????????? ???????????, ?. ?. ???????? ??????????? ? ???????? ????????????????;
??? ??????? ? ????????? ??????? ?? ???????, ??????????? ??????
?? ??????, ??????? ????????? ?????? ????????? ?????????, ???? ???
???????, ?????? ???????????? ? ?????? ?????????? ????????? ???? ???
??????????.
??????? ???? ??????????, ???????, ??? ?????, ???????????? ??? ?????????, ?????????? ?? ?? ?????????? ? ?????????? ???????, ????????:
1) ???????????? ????????? ?????????? (???? ??? ?????) ??????, ?
??? ????? ???????????? ???????????? ??? ???????;
2) ????????????? ????????? ????????? ?????;
3) ??????? ??????? ??????????? ??? ?????????? ???? ?????, ?????? ?? ??????? ???????? ? ?????? (??? ? ?????? ?? ??????????) ????????? ???????.
2. ??????? ????. ????????????? ???.
?????????? ????????????? ???
????? ?????????? ?????????????? ?????? ?????????. ?????????????? ?????? ????????? ?????? ???????? ???????? ??? ?????, ? ??????, ?????? ?????????:
????????? ???????????????? ?????? (???????);
????????? ???????? ?????? ?? ?????? (????????? ? ????);
???????? ??????, ?????????????? ????????? ???????? ( ???????)
??? ??????? ?? ???????.
? ?????? ??? ??????????????, ??? ??????? ???????? ? ?????????
?????????, ????????? ??????? ?? ??????? ????????????, ?. ?. ??????
?? ??????? ????? ???? ??????? ???????? ? ????? ????????? ? ???
???????????? ?????????, ? ??? ?? ??????? ???????? ? ????????? ????
????????? ???????. ? ???????????? ? ???? ??????????? ?????? ?? ??????? ?????????? ???? ?????????.
????????? ???? ??? ????? ???????????????? ????????? ???????:
?? ????? ???????;
?? ????? ?????????;
4
?? ????????? ??????? ????????;
?? ??????????? ??????????????? ??????????? ? ??????????????
????? ???????? ? ???? ????.
?? ????? ??????? ????????? ???? ? ?????, ????? ? ????? ???????????. ? ???????? ???????? ??? ?? ???? ? ??????????? ?????? ???????.
?? ????? ????????? ????????? ???????? ? ??????????? ????. ? ???????? ????? ?????? ??????????? ???????? ?????? ????????? ?????????. ????????, ? ???? ? ??????? ? ??????? ?? ??? ????????? ? «????»
??? «?????». ? ??????????? ????? ?????? ????? ??????????? ?????
????????? ?????????. ????????, ??? ?????????????? ???????? ? ?????????? ?????? ?? ??????? ????? ??????? ????? ???? ? ????? ?????????? ???????????? (???????????) ??????.
?? ????????? ??????? ???????? ????????? ????:
? ??????? ??????, ????? ??????? ?????? ?????? ????? ?????????
???????, ?. ?. ?????? ?????? ???????? ????? ????????;
? ?????????? ?????????, ? ??????? ?????? ? ??????????, ? ??????????? ????????????, ??? ??? ?? ??????? ??????????? ??????;
? ????????? ??????, ??? ???? ? ?????????, ? ????????????? ???????? ???????.
?? ??????????? ??????????????? ??????????? ? ??????????????
????? ???????? ? ???? ???? ????????? ????????????? ? ??????????????? ????. ???? ?????????? ?????????????, ???? ?? ?????? ???? ?????? ???????? ???????? ? ????????? ????????????????? ?????????? ? ????? ?????????? (????????, ??????????? ???????? ? ??????????
????? ???????????? ?? ????????? ????????).
????, ? ??????? ?????? ?? ????? ?????????????? ???? ????????? ???????? ???????, ?????????? ??????????????? (????????, ??? ???? ?
??????? ??????).
?????????? ??????? ??????????? ????????????? ???.
????????? ????? I ????????? ???? ???????, ????? Si ? ?????????
????????? ???????? ?????? i (i?I), ?????????? ?????????? ?????????.
????????:
?) ???? ? ???????
I = {1, 2}, Si = {????, ?????};
?) ??????????? ? ??????????
I = {1, 2, ?, n}, ??? n ? ????? ??????????, Si = {??, ??????, ???????????};
?) ?????????????? ?? ????? ???? ?????????
5
I = {1, 2} Si = {Pi: Pi > 0}, ??? Pi ? ???? ???????????? ??????.
? ?????? ?????? ???????? ?????? ???? ????????? si ? Si, ? ?????????? ???? ???????????? ????? ????????? s = (s1, s2,?,sn), ??????????
?????????.
? ????????????? ???? ???????? ???????? ????????? ????????:
?) (????, ????), (????, ?????), (?????, ????), (?????, ?????);
?) (??, ??, ??????, ??, ???????????, ?, ??????);
?) (5 ??????, 3 ?????), (5 ??????, 7 ??????).
?????????????????? ??????? ? ?????????? ????????? ??????????? ?
???, ??? ??????? ?????? i ? ?????? ???????? s ????????????? ?????,
?????????? ??????? ?????????????? ??? ????????? ? ?????? ????????. ??? ????? ?????????? ????????? ?????? i ? ???????????? H i(s).
???????? ? ????????? ???? ????????.
? ???? ? ???????:
H1(????, ????) = H1(?????, ?????) = 1,
H1(????, ????? ) = H1(?????, ???? ) = ?1,
H2(????, ????) = H2(?????, ?????) = ?1,
H2(????, ?????) = H2(?????, ????) = 1.
?????, ??? ? ????? ???????? H1 + H2 = 0.
??????? ??? ? ???? ??????? ?????????, ??? ?????? ????? ??????????????? ?????????? 1-?? ??????, ??????? ? ?????????? 2-?? ??????.
1?
? 1 ?1 ?
? ?1
H1 = ?
, H2 = ?
?
?.
1?
? ?1
? 1 ?1 ?
??? ???? ??? H1 + H2 = 0.
????? ???????, ??????? ???????? ???????? ???? ? ??????? ??????.
??? ??????????? ? ??????????:
???? ??????????????? ???? ??????, ??? ?????????????10,
??? ???????? (?????? ??????),
?
?
???? ??????????????? ???? ??????, ??? ????????????Hi = ?
7,
?
??? ???????? (?????? ?? ??????),
?
??
??? ?????????? ??????????? i = 1, 2, ?, k (?????? ????? ????????);
6
???? ??????????????? ???? ??????, ??? ???????????????
???????? (?????? ??????),
???? ??????????????? ???? ??????, ??? ???????????????
???????? (?????? ?? ??????),
??? ?????????? ??????????? i = k + 1, ?, n (?????? ??????
????????).
? ?????? ?????????????? ?? ????? ???? ????????? ???????????, ??? ??????????? ?????????? ????? ? ?????, ?????????? ??????? ????, ??? ??????????? ???? ????? ??????? ????? ??????? ? ??????, ???? ???? ?????.
???? d(p) ? ??????? ?????? ? ??????????? ?? ???? ?? ?????, ??
??????? ????????:
?10,
?
?
Hi = ?
? 5,
??
p1 < p2 ,
? p1 Ч d ( p1 ),
?
1-? ????? H1 ( p1 , p2 ) = ?1/ 2 Ч p1 Ч d ( p1 ), p1 = p2 ,
?0,
p1 > p2 ;
?
p1 < p2 ,
?0,
?
2-? ????? H 2 ( p1 , p2 ) = ?1/ 2 Ч p1 Ч d ( p1 ), p1 = p2 ,
? p Ч d ( p ),
p1 > p2 .
2
? 2
3. ??????????? ??????????????? ????
??????????????? ????? ????? ???????? ????? ????, ? ??????? ????? ??????? ?????? ???????? ????????? ?? ??????????? ???????? ??????????????? ????????.
?????????:
I ? ????????? ???? ???????. ????? ????? ??????? I ????????. ?????? ??????? ????????? ??????? ?? ???????, ?. ?. ??????? I = {1, 2, ?, n};
Si ? ????????? ????????? ?????? i ? I, ?. ?. ????????? ?????????
????????, ????????? ? ???????????? ?????? i. ?????????, ??? Si ???????? ?? ????? ???? ????????? ?????????, ????? ??? ???????? ???????
??????????.
??????? ???? ??????? ? ?????? ?????? ?? ??????? ????? ????? ????????? si ? S. ????? ???????, ? ?????????? ?????? ?????? ???? ???????????? ??????? ????????? s = (s1, s2,?,sn), ??????? ?????????? ?????????.
????????? ???? ???????? S = S1 Ч S2 Ч ... Ч Sn , ?. ?. S ???????? ?????????? ????????????? ???????? ????????? ???? ???????. ?????????: Hi(s)
7
? ??????? ?????? i ? ???????? s. ??????? Hi , ???????????? ?? ????????? ???? ????????, ?????????? ???????? ???????? ?????? i.
Hi: S ? R, ?. ?. ?????? ???????? s ? S Hi ? ???????????? ???????????? ?????.
??????????? 1. ??????????????? ????? ?????????? ???????
? = < I , {Si }i? , {H i }i?I >, ? ??????? I ? Si (i ? I) ???????? ?????I
??????, ? Hi ? ??????? ?? ????????? S = S1 Ч S2 Ч ... Ч Sn , , ??????????? ???????????? ????????.
??????????? 2. ??????????????? ???? ? = < I , {Si } , {H i } >,
i?I
i?I
?????????? ????? ? ?????????? ??????, ???? ?????????? ????? ?????????? ????? C, ???
? Hi ( s) =
C ? s ? S , ?. ?. ????? ????????? ????-
i?I
??? ????????? ? ????? ????????.
4. ?????????? ???????? ? ???????? ??????????
???????? s ? ???? ? ??????????? ??????? ?????????? ??? ?????? i,
???? ???? ?????, ??????? ? ???????? s ???? ????????? ?? ?????-????
??????, ?? ????? ????????? ???? ?????? ????????.
????? s = ( s1 , s2 , ..., si ?1 , si , si +1 , ..., sn ) ? ???????????? ???????? ?
???? , ? si ? ????????? ????????? ?????? i.
?????????? ????? ???????? s si? = ( s1 , s2 , ..., si ?1 , si?, si +1 ,..., sn ) , ???????????? ?? ???????? s ??????? ????????? si ?????? i ?? si? . ????????,
??? s si? = s, ???? si? ????????? ? si ( si? = si ).
??????????? 3. ???????? s ? ???? ? ?????????? ?????????? ???
?????? i, ???? H i ( s si? ) ? H i ( s ) , ?si? ? Si .
????? ???????? «??????????» ??????? ? ???, ???, ???? ? ?????????
???????? s ??? ?????? i ???????? ????? ????????? si?, ???
H i ( s si? ) > H i ( s ) , ?? ????? i ? ?????? ?????????????? ???????? s
????? ???????? ??????? ???????, ??????? si?, ?????? si. ? ???? ??????
???????? s ??? ?????? ????? ????????? ????????????.
??????????? 4. ???????? s ?????????? ????????? ?????????? (???
??????????? ?????????), ???? ??? ????????? ??? ???? ???????, ?. ?.
H i ( s si? ) ? H i ( s ) , ?i, ?si? ? Si .
8
?? ??????????? ?????, ??? ? ????????? ?????????? ? ?????? ? ???
?? ???? ????? ?? ????????????? ? ?????????? ?? ????? ?????????.
??????????? 5. ??????????? ?????????? ?????? ? ???????????????
???? ?????????? ????? ??? ?????????, ??????? ?????? ???? ?? ? ???? ??
??????????? ???????? ????.
??????? ?????????? ???????? ?????????? ? ??????????????? ????
?????????? ???????? ????.
5. ?????? «??????? ???????????»
???????????, ???????? 1 ? 2 ???????? ???????????, ??????????? ?
??????????????? ?????????? ?? ?????????? ? ?????? ????????????.
?????? ???? ?????? ??? ???, ? ??????????? ?? ????????? ? ???????????? ???? ??????? ?? ????, ????????? ?? ??????????? ????.
????? I = {1, 2}, Si = {??????????, ?? ??????????}.
????????? ?????????????????? ??????? ? ????????? ?????????.
???? ??? ??????????, ?? ????? ???????? ?? ?????????? ????, ?? ?
?????? ??????????? ?????????????? (????????????? ?????????) ?????? ??????? ???? 5 ??? (??????? (??????) ??????? ?????? ? ?5).
???? ??? ?? ?????????, ?? ?? ??????????? ???? ????????? ? ??????
???????????? ????? ?????, ?? ????????? ?????? ???????? ??????????
??????? ? ????? ?????? ????????????, ? ?????????? ???? ??? ???????
???? ? 1 ??? (??????? (??????) ??????? ?????? ? ?1).
???? ? ??????? ? ???????????? ????????? ???? ?? ???????, ?? ???
??????? ??????? ??? ???? ?? ???????. ? ?????????? ??????????? ??????? ?? ??????? (??????? (??????) 0), ? ??? ???????????? ?????????? ??????? ?????? ???? ????????? ? ???? 10 ??? (??????? (??????) ?10).
??????? ??????? ????????? (??????) ??????? ? ????????????? ????.
????? ? ? ?????????, ? ? ???????????, H1 ? ??????? 1-?? ??????,
H2 ? ??????? 2-?? ??????.
H1 (?, ?) = H 2 (?, ?) = ?5 ,
H1 (?, ?) = H 2 (?, ?) = ?1,
H1 (?, ?) = H 2 (H, ?) = 0,
H1 (H, ?) = H 2 (?, ?) = ?10.
? ????????? ??????, ??? ?????? ????????????? ?????????? 1-??, ?
??????? ?????????? 2-?? ??????, ?????
9
? ?5 0?
? ?5 ?10 ?
H1 = ?
, H2 = ?
?
?.
? ?10 ?1 ?
? 0 ?1 ?
????????? ?????????? ? ?????? ???? ??????????? ???????? (?, ?), ?
??????? ?????? ?? ??????? ?????? ??????????. ? ???? ???????? ??????
?? ??????? ?????? 5, ?. ?. ??????????? ?????????? ?? 5 ???. ? ????????
?? (?, ?), ????? ?? ???? ?? ?????????, ?????? ??????? ????? 1 (??????
??????? ?? 1 ???). ?????? ?????? ???????? ???? ???????????, ??? ???
?????? ?? ??????? ????????????? ??????????? ?? ????????? ?????????
? ??????????, ??????????? ??????? ???? ?? ??????? ? ???????? ?????????, ????? ???? ?????? ? 0 (??? ???? ?????? ???????? ???????? 10).
????? ??????? ???????? ?????????? ??? ??????? ?????? ????????
?????????, ??? ??? ??? ??????????? ?????? ??????????? ????????????? ????? ? 10 ???. ???? ????? «????????» ??????? ??????? ???????????, ?????? ??????????? ????????? ??????????????? ????????? (????
? 1 ???), ?????? ???????? ?????????????? ? ???? ????????????? ?????
? 10 ??? ? ?????? ????????? ?? ??????? ???????????.
6. ?????????????? ??????????????? ???
???????????? ??????????????? ??? ?????? ??????????? ??????????? ?? ? ????? ??????, ?????? ??????? ???? ???????? ?????? ? ????
?? ??????????. ? ???????? ????? ??????? ????? ????? ?????? ????????????? ????????????? ???.
??????????? 6. ????? ???? ??? ??????????????? ???? ?? ? ??? ?
?????? ? ???? ?? ??????????? ??????? ? ?? ?????????, ????????????
???? ????????? ????????:
?? = < I , {Si }i?I , {H i?}i?I >
??? = < I , {Si }i?I , {H i??}i?I >
,
? ????? ?????????? k > 0, ? ??? ??????? ?????? ?????????? ???????????? Ci ?????, ??? ? ????? ???????? s
? i?( s ) = k ? H i??( s ) + ci .
????? ???? ?? ? ??? ?????????? ????????????? ??????????????.
?????????????? ??????????????? ???? ?? ???? ??? ????????????
?
? ~ ???.
10
??????????? ??? ???????? ?????????????? ??????????????? ? ??????????????, ????????? ? ??????????????.
1. ??????????????. ?????? ???? ? ????????????? ???????????? ????? ????: ? ~ ? .
? ? ? ? ? ? ? ? ? ? ? ? ? ?. ??????? k = 1 ? Ci = 0, ??? ???? i ? ?????
???????? s ????? H i ( s ) = 1 ? H i ( s ) + 0, ??? ? ??????????? ????????.
2. ?????????. ???? ?~ ?? , ?? ??~ ?.
? ? ? ? ? ? ? ? ? ? ? ? ? ?. ????? ?~ ?? , ????? ??? ???? ????? ???? ?
?? ?? ????????? ??????? ? ?? ?????????, ? ??????? ???????? ???????
????????? ???????:
H i ( s ) = k ? H i?( s ) + ci , k > 0, ci ? R
? H i?( s ) = 1/ k ? H i ( s ) ? ci / k ,
1
> 0, ci / k ? R
k
? ??~ ?,
??? ? ??????????? ????????.
3. ??????????????. ???? ? ~ ? ? ? ??~ ???, ?? ?~ ???.
? ? ? ? ? ? ? ? ? ? ? ? ? ?. ????? ? ~ ? ? ? ??~ ??? , ????? ?, ??, ???
????? ???? ? ?? ?? ????????? ??????? ? ?? ?????????, ? ???????
???????? ??????? ????????? ???????:
H i ( s ) = k ? H i?( s ) + ci ,
H i?( s ) = p ? H i??( s ) + bi , k > 0, p > 0, ci ? R, bi ? R.
????? H i ? H i?? ??????? ????????????
H i ( s ) = kpH i??( s ) + (kbi + ci ) , kp > 0, (kbi + ci ) ? R,
??? ?? ??????????? 6 ???????? ??????????????? ?~ ???.
????? ???????, ????????? ?????????????? ??????????????? ????????????? ???????? ????? ?????????? ?????????????? ?????????, ?, ??????, ????????? ????????? ???? ??????????????? ??? ?? ??????? ?? ?????????????? ?????? ????????????? ???? ????? ???. ??????
?????????????? ????????? ??????? ???????? ??? ?????? ?????? ??????????????? ?? ??????? ????? ???? ?? ????? ??????.
???????? ????? ????? ????????????? ?????????????? ?????? ?? ????
??????? ???? ? ???????? ????????? ????????? ??????? ci ? ??????
????????? ?????????, ???????????? ????????????? k.
11
??????? ???????????, ??? ???????? ????????? ??????? ? ????????????? ????????????? ????? ?????? ???? ??????????.
??????? 1. ????????????? ????????????? ???? ????? ???? ? ?? ??
???????? ??????????.
? ? ? ? ? ? ? ? ? ? ? ? ? ?. ????? ?~ ??, ? s* ? ???????? ?????????? ?
???? ?. ???????, ??? s* ? ???????? ?????????? ? ???? ?? . ?? ??????????? ???????? ?????????? s* ? ???? ? ???????, ??? ??? ???? i ? I ? si ? Si
????? ?????????:
H i ( s * si ) ? H i ( s*).
(6.1)
? ?????????????? ??????????????? ? ? ?? ????????
H i ( s*) = kH i?( s*) + ci ,
H i ( s * si ) = kH i?( s * si ) + ci ;
(6.2)
(6.3)
?? (6.1), (6.2), (6.3) ????????
kH i? ( s* si ) + ci ? kH i? ( s* ) + ci ,
?????? (? ?????? k > 0) ????????
H i?( s * si ) ? H i?( s*) ? i ? I ? si ? Si ,
??? ? ???????? ????????????? ????????? s* ? ???? ??.
??????????? 7. ??????????????? ???? ? = < I , {Si }i?I , {H i }i?I > ?????, ??? ? ????? ???????? s ? S ????????? ??????? ??????? ?????
????, ?????????? ????? ? ??????? ??????.
??????? 2. ?????? ??????????????? ???? ? ?????????? ?????? ????????????? ???????????? ????????? ???? ? ??????? ??????.
? ? ? ? ? ? ? ? ? ? ? ? ? ?. ????? ? = {I , {Si }i?I , {H i }i?I } ? ???? ? ??????????
? H i ( s) = c, c = const.
i?I
??????? ???????????? ci (i ? I ), , ??? ??????? ? c = c, ? ???????-
??????, ?. ?. ??? ???? ???????? s ? S ?????
i
i?I
??? ???? ?? = {I ,{Si }i?I , {H i?}i?I } ? ????????? ?????????
? i?( s ) = H i ( s ) ? ci . ?????, ???, ? ????? ???????, ? ? ?? ????????????, ?, ? ?????? ???????, ?? ? ???????? ????? ? ??????? ??????, ??? ???
? H i?( s) = ? H i ( s) ? ? ci = c ? c = 0
i?I
12
i?I
i?I
? s ? S.
7. ????????????????? ????
????????????????? ???? ???????? ??????? ??????? ??????????????? ????.
??????????? 8. ???? ? = < I , {Si }i?I , {H i }i?I > ?????????? ?????????????????, ???? ????? ??????? ? ??? ????? ????, ? ???????? ??????? ???????? ???? ??????? ? ?????? ???????? ????? ?? ???????? ?
(7.1)
?????????????? ?? ?????, ?. ?. H1 ( s ) = ? H 2 ( s ), ?s ? S .
?? ??????????? ???????, ??? ? ????? ???????? ?????????????????
???? H 1 ( s ) + H 2 ( s ) = 0 . ????? ??????, ????????????????? ???? ? ???
???? ???? ??? ? ??????? ??????.
????, ??? ??? ??????? ????????????????? ???? ?????????? ??????
?????? ???? ??????? ????????, ?????? ?????????? ???????????? ??
????????? (7.1).
??????? ??? ????????????????? ????? ?????? ???????? ??????:
? = < A, B, H >, ??? ? ? ? ? ????????? ????????? ??????? 1 ? 2, ? ? ?
??????? ???????? ?????? 1, ???????? ?? S = {(a , b): a ? A, b ? B}.
?? ??????? 2 ???????, ??? ??????????????? ???? ???? ??? ? ??????????
?????? ????????????? ???????????? ????????? ????????????????? ????.
8. ???????? ?????
????? ? = < A, B, H > ? ????????????????? ????. ??? ???????? ?????????? (a, b) ?????? ???? ?????
(8.1)
H1 ( a , b) ? H1 ( a ?, b), a ? ? A;
H 2 ( a, b) ? H 2 ( a , b?), b? ? B.
(8.2)
????????, ??? H 2 ( a , b) = ? H1 ( a , b), ??????? ????????? (8.2) ???
? H1 ( a , b) ? ? H1 ( a , b?), b? ? B ??? H1 ( a , b) ? H1 ( a , b?), b? ? B.
?????? ? (8.1) ??????? ??? ? ???? ???????? ??????????? (???????? ??
??????????? H 1 ? ??????????? ? ??? ??????? ???????? 1-?? ??????)
H ( a ?, b) ? H ( a , b) ? H ( a , b?), a ? ? A, b? ? B.
??? ??????????? ???????? ????????? ???????? ??????? ? ? ?????
(a, b): ??? ????? ????????? ?????????? a ???????? ? ????? ??????
???????????, ? ??? ????????? ???????? ?????????? b ? ?????? ???????????, ?. ?. ?? ?????????? a ??????? ? ??????????????, ? ?? ?????????? b ? ???????????. ????? ???????, ?? ???????????, ????????13
??? ???????? ?, ? ??????????? a ? b ????????? ?????????? ????? ??????????????? ????????????? ????? ???????????.
?????????. ??????? ????? ? ????, ??? ??????? ???????? ????? ? ?????? ??? ?????????? ?? ???????????? ??????? ? ?????????.
?????? ??????? ??????? ? ???, ??? ? ?????? ??? ??? ?????????????
????? ??????????, ????? ? ??? ?????????? ???????? ?????? ?? ??????
??????????, ? ??????? ? ?? ??????. ? ????????? ?? ?? ??????? ?????????? ??????????????? ????? ?? ???????.
?????? ??????? ? ???, ??? ? ????????? ??????????????? ????? ??????? ? ?????????????? ??????? ? ?????????? ? ???? ???????????????
???????????. ? ?????? ??? ????????????? ??????????? ?? ???????????. ????? ????, ???????? ????? ??????? ??????????? ?? ??????? ???????
??????? ???????.
9. ??????????? ? ?????? ???????
??????????? 9. ????? f ? ???????, ???????? ?? ????????? D. ??
?????????? ?? ???? ????????? ?????????? ?????????? ?? ???? ????? p
?????, ??? f ( x ) ? p ??? ????? x ? D.
??????????? ?????????: sup f ( x ) ??? sup f ( x ), ???? ???? ???????
x?D
???????????? ??????? ??????? f(x).
??????????? 10. ????????? ??????? f ?? D ?????????? ?????????? ?? ????? p ?????, ??? p ? f ( x ), ?x ? D.
???????????: inf f ( x ) ??? inf f ( x ).
x?D
??????????? 11. ???? ???????? ??????? f ?? D ???????????, ?. ?.
???? ?????????? x? ? D, ????? ??? f ( x )? = sup f ( x ), ?? ?? ??????????
??????????.
???????????: max f ( x ).
??????????? 12. ???? ??????? ??????? f ?? D ???????????, ?. ?.
???? ?????????? x? ? D ????? ??? f ( x*) = inf f ( x ), ?? ?? ??????????
?????????.
???????????: min f ( x ).
??????????? 1. ???? ?????????? ????????? ?????????? c ?????, ???
f ( x ) ? c, ?x ? D, ?? ? sup f ( x ) ? c;
x?D
14
???? ????????? ?????????? d ??????, ??? f ( x ) ? d , ?x ? D, ?? ?
inf f ( x ) ? d .
x?D
?????? ??????????? ??????? ??????????????? ?? ??????????? 9 ? 10.
??????????? 2. ???? f ( x ) ? g ( x ) ?????? ?? D ? ??? ????? x ? D
????? f ( x ) ? g ( x ) , ?? ????? ? sup f ( x ) ? sup g ( x ) , inf f ( x ) ? inf g ( x ).
? ? ? ? ? ? ? ? ? ? ? ? ? ?. ?? ??????? ? ??????????? ????????? ????? f ( x ) ? g ( x ) ? sup g ( x ) = const ? ? ?????? ??????????? 1 sup f ( x ) ?
? sup g ( x ).
?????????? ???????????? ??????????? ??? ?????????.
??????? 3. ???? x ?????????? ? ??????? D , y ?????????? ? ??????? E , f (x, y ) ?????????? ?? D Ч E , ??
supinf f ( x, y ) ? inf sup f ( x, y ).
x
y
y
(9.1)
x
? ? ? ? ? ? ? ? ? ? ? ? ? ?. ????? ??? ????? x ? y f ( x, y ) ? sup f ( x, y ).
x
???????? ??????????? 2, ???????: inf f ( x, y ) ? inf sup f ( x, y ) = const.
y
y
x
?????? ????? ????? ??????????. ??????? ? ???????????? ? ???????????? 1 ?????: supinf f ( x, y ) ? inf sup f ( x, y ).
x
y
y
x
????????? (??????????? 3): ???? ? ????????? (9.1) ??????????
???????????, ??
max inf f ( x, y ) ? min sup f ( x, y ).
x
y
y
(9.2)
x
????, ????? ????, ??????????? ? ??? ?????????? ??????????, ?. ?.
???? ? x ? min f ( x, y ) ? ?y ? max f ( x, y ) , ??
x
y
max min f ( x, y ) ? min max f ( x, y ).
x
y
y
(9.3)
x
??????????? (9.1), (9.2), (9.3) ???????? ?????? ????????????? ??????????. ??? ????? ??????? ???????? ? ?????? ???.
15
10. ????????? ?????????? ? ???????? ?????
??????? 4. ??? ???? ????? ??????? f ( x, y ) , ???????? ?? ?????????
D Ч E , ????? ???????? ?????, ?????????? ? ??????????, ????? ???????????? (?. ?. ???????????) ?????????
max inf f ( x, y ) , min sup f ( x, y )
y
y
x
(10.1)
x
? ??????????? ?????????
max inf f ( x, y ) = min sup f ( x, y ).
y
x
y
(10.2)
x
?????????. ??????????????? ??????????????? ????? ? ?????? ?????? ???.
? ? ? ? ? ? ? ? ? ? ? ? ? ?. 1. ?????????????. ????? f(x, y) ?????
???????? ????? ? (x*, y*) ? ???? ?? ???. ??? ????????, ???
(
) (
) (
)
f x, y * ? f x* , y * ? f x* , y .
(10.3)
???????? ? ????? ????? ????????? (10.3) ??????????? 1 ?. 9, ???????
(
) (
)
sup f x, y * ? f x* , y* .
x
(10.4)
?????, ????????? ??????????? ???????? ????????????? ? ???????
g ( y ) = sup f ( x, y ) , ????????
x
( )
(
) (
)
inf sup f ( x, y ) = inf g ( y ) ? g y * = sup f x, y * ? f x* , y* . (10.5)
y
y
x
x
??????????, ???????? ? ?????? ????? ????????? (10.3) ??????????? 1 ?. 9 ? ????????? ??????????? ????????? ????????????? ? ??????? z ( x ) = inf f ( x, y ) , ???????
y
( )
(
) (
)
supinf f ( x, y ) = sup z ( x ) ? z x* = inf f x* , y ? f x* , y * . 10.6)
y
x
x
y
????????? ????????? (10.5) ? (10.6), ?????:
inf sup f ( x, y ) ? sup f ( x, y* ) ? f ( x* , y* ) ? inf f ( x* , y ) ? supinf f ( x, y ) (10.7)
y
x
y
x
? inf sup f ( x, y ) ? sup inf f ( x, y ).
y
16
x
x
y
x
y
??, ???????? ??????? 3, ??????????? ? ??????????????? ??????????? supinf f ( x, y ) ? inf sup f ( x, y ).
x
y
y
x
???????
inf sup f ( x, y ) = supinf f ( x, y ).
y
x
x
(10.8)
y
??????, ? ????????? (10.7) ??????? ????? ?????. ?????????????,
????? ???? ????? ??? ????? ????? ???????????. ? ?????????,
inf sup f ( x , y ) = sup f ( x , y * ).
y
x
x
????? ??????? ? ????????? inf sup f ( x, y ) ??????? ???????????
y
x
(?????? ??? y = y*) ? ??? ????? ???? ???????? ??? min sup f ( x, y ).
y
x
????? ??? ?? ?? ????????? ???? ?????? ? ????????? (10.7) ????????,
??? inf f ( x* , y ) = supinf f ( x, y ), ?. ?. ???????? ??????????? ? ????? x*
y
y
x
? ??????? ?????? sup inf f ( x, y ) ?? ????? ?????? max inf f ( x, y ).
y
x
y
x
? ????? ????????? (10.8) ????? ???? ?????????? ????????? ??????? max inf f ( x, y ) = min sup f ( x, y ), ??? ? ??????????? ????????.
x
y
y
x
2. ?????????????. ??????????? ??????, ??? ????????? (10.1) ?????????? ? ?????, ? ??????? ?????????? ?? ??? ??????????? ?????????????? ? ?????? x* ? y*
??? ??????, ??? max inf f ( x, y ) = inf f ( x* , y ).
x
y
y
??, ????? ????, ?? ??????????? ???????? inf f ( x* , y ) ? f ( x* , y ),
y
??? ??? max inf f ( x, y ) = inf f ( x , y ) ? f ( x , y ).
*
x
y
*
*
y
(10.9)
?????????? ?????????, ????????
f ( x* , y * ) ? sup f ( x, y * ) = min sup f ( x, y ).
x
y
(10.10)
x
?? ????????????? ????????? (10.1) ?????, ? ?????? ????? ????
????? ? ??? ???????????? ? ???????????? (10.9) ? (10.10) ?????????. ?
?????????, sup f ( x, y * ) = f ( x* , y * ).
x
17
????????, ??? f ( x, y * ) ? sup f ( x, y * ) ?x, ???????
x
(10.11)
f ( x, y* ) ? f ( x* , y * ), ?x.
????? ??? ?? ?? ????????? ?????? ????????? (10.9) ?????
inf f ( x* , y ) = f ( x* , y * ).
y
? ?????? inf f ( x* , y ) ? f ( x* , y ) ?y ????????
y
f ( x * , y * ) ? f ( x * , y ) ?y .
(10.12)
????????? (10.1) ? (10.2) ?????? ???? f ( x, y* ) ? f ( x* , y * ) ? f ( x* , y ),
?. ?. (x*, y*) ? ???????? ????? ??????? f(x, y).
????????? 1. ? ???? ?????????????? ???? ??????? (?????????????)
???? ???????????, ??? ? ???????? ????????? ???????? ????? ????? ????
?????????? ???? ?? ????? ????? ????? x ? y, ?? ??????? ???????????
??????? ?????????? ? ?????????? (10.1). ???????, ???? (a, b) ? (c, d) ?
???????? ????? ??????? f(x, y), ?? ????? (a, d) ? (c, b) ??? ?? ?????
????????? ??? ???? ???????. ??? ???????? ????????? ???? ????????
????? ??????? ?????????? ?????? ???????????????? ?????????.
????????? 2. ?? ????????? (10.9), (10.10), (10.2) ????????, ??? ???????? ??????? ? ???????? ????? ????? ?????? ???????? ??????????
(10.1), ??????????? ????? ??????????.
?????????????, ???????? ??????? ?? ???? ?? ???????? ?????? ?????
???? ?????.
11. ????????? ????
??????????? 13. ????????????????? ????, ? ??????? ?????? ?????
????? ???????? ????????? ?????????, ?????????? ?????????? ??????.
????? ???? ????????? ???????????? ????????? ????????, ? ???????
?????? ????????????? ?????????? ??????? ??????, ??????? ? ?????????? ??????? ??????, ? ?? ?? ??????????? ????? ??????? ??????? ??????
? ??????????????? ???????? H (i, j ) = aij . ??? ??????? ??????????
???????? ????, ??? ???????? ?????????.
??????? ????????? ???????????.
????? A ? ??????? ????????? ????.
18
? a11 a12
?
A = ? a21 a22
? ...
...
??
? am1 am 2
... a1n ?
... a2 n ??
.
... ... ?
?
... amn ??
????? ???? ?????????? m Ч n ??????.
????????? ??????? ?????? ? ?????? ??????????????? ?????, ????????? ??????? ?????? ? ?????? ??????????????? ????????.
Ai . ? i-? ?????? ??????? A .
A. j ? j-? ??????? ??????? A .
(i, j) ? ????????, ??? i ? ????? ??????, j ? ????? ???????.
???????? (i, j) ? ????????? ???? ???????? ???????????, ????
aij* ? ai* j* ? ai* j
? i = 1,..., m, ? j = 1, ..., n.
? ???????????? ? ???????? 4 ??? ????????????? ? ????????? ????
???????? ????? (???????? ??????????) ?????????? ? ??????????, ????? ???? ????? ?????????: max min aij = min max aij .
j
j
i
i
????????????? ???? ?????????? ????????, ??? ??? ????????? ????????? ??????? ?????? ???????, ? ?????? ?????????? ?? ??? ???????????.
????? ?????????? ???????? ????? ??????? A :
? a11
?a
? 21
? ...
??
? am1
?
max ai1
i
? min a1 j ?
j
?
? min a 2 j ??
j
? ? max min aij
j
i
? ...
?
?
? min a mj ?
j
?
a12
a22
...
am 2
...
...
...
...
a1n ?
a2n ??
... ?
?
amn ??
?
?
?
...
max ain
max ai 2
i
i
min max aij
j
i
??????????? 14. ????????? i
?
j , ?? ??????? ???????????
max min aij ? min max aij ; ?????????? ?????????????? ??????????? ?
j
i
j
i
???????????.
19
???? ???????? ? ???????? ????? ???? ?????, ?? ?? ????? ????????
?????????? ????????? ????????? ???? ? ???????? ????????? A ? ???????????? V ( A ).
? ? ? ? ? ? 1. ????? ?????? ??????? ?????????
?3
5
3
?1
A = ?? 0
?2
?
?2
4
2
? min a1 j
j
?
? ? min a
2j
?
j
?
? ? min a
ij
j
?
max ai1
?
max ai 2
i
=2
?
?
= 0 ? ? max min aij = 2
j
i
?
?
= 2
?
max ai 3
i
i
=5
min max aij = 2
j
= ?3
=4
i
???????? ? ???????? ????? ? V ( A ) = 2. ???????? ?????? ????????
???????? (3, 1), ???????????? 3-? ?????????? ??????? ?????? ? 1-? ?????????? ??????? ??????.
?????????. ???? ??????? ? ???????? (3,3) ???? ????? 2, ?? ???
????? ?? ???????? ????????, ??? ??? ??? ??????? ?????? ?????? ???????? ????????? (???????? ????????? ????? ?????????? ??????? ??????), ? ??? ??? ??????? ?????? ? ?? ????????? (??????? ?? ????????
???????????? ????? ????????? ???????? ???????).
? ? ? ? ? ? 2. ????? ?????? ??????? ?????????
= ? 10 30 ? ? 10 ?? ? max min a = 20.
A
ij
? 40 20 ? ? 20
j
i
?
?
?
? ?
40
30
?
min max aij = 30
j
i
???????? ????? 20 ? ??????????? ??? i = 2, ? ???????? ????? 30 ?
??????????? ??? j = 2. ?????? ???? ?? ????? ???????? ?????????? ?
?????? ??????????.
20
????? ?????? ????? ?????? ???? ??????????? ????????? i = 2 ,
????? ??????? ??????? ??????? ???? ????????? j = 2 ? ????????? 20.
?? ? ???? ?????? ??????? ???????? ??????????? ?? ????? ???????????
????????? ? ??????? i = 1 , ????????? ??? ???? 30. ????? ??????? ??????? ??????? j = 1 ? ????????? ????? 10. ?? ? ???? ?????? ??????
??????? i = 2 ? ???????? 40, ?? ??? ?????? ??????? ??????? j = 2 ?
?????????? 20 ? ?.?. ?????, ??? ?? ???? ?? ???????? ?? ???????? ?????????? ???????????? ??? ????? ???????.
12. ????????? ?????????
???? ? ???? ? ???????? A ???????? ? ???????? ?? ????? ???? ?????,
?? ?? ??????? 4, ???? ? ????? ???????? ?? ????? ???????? ??????????.
? ???? ?????? ????? 1 ????? ?????????? ???? ??????? max min aij
j
i
(????? ??????????????? ???????), ? ????? 2 ????? ?? ???? ??? ??????, ??? min max aij (????? ??????????????? ????????). ?????? ? ?????j
i
?? ????? ???????? ???????? (??? ???????? ?????? ??????????????) ???????? ????????. ??????? ??????????? ??????? ??????? ????????
?????????????? ?????????????? ??????????? ??? ?????????? ????????? ? ???? ?????? ???????? ??????? ???? ???? ????????.
???????????, ??????? ????????????? ???????? ???? ????????? ????????, ?. ?. ?????????? ????????????? ???????????? ?? ????????? ?????? (??????????????) ?????????, ? ????? ???????????? ????? ?????????? ?????? ????????? ?????????? ?????????.
????? ???????? ????? ?????? ????????? ? ?????????? ??????? ????????? ????????????? ? ?? ???????? ???? ?? ?????? ?????????? ????
?, ????? ???????, ???? ???????? ????????? ??????????. ? ??????? ??
????????????? ???????? (??????) ?????????, ????? ????????? ?????????? ??????????.
??????????? 15. ????????????? ???????????? ?? ????????? ??????
????????? ?????? ?????????? ??? ????????? ??????????.
????????? ????????? ?????? ????? ??????????? ? ???? ???????
X = ( x1 , x2 , ..., xn ) ,
(12.1)
??? x1 ? 0, x2 ? 0, ..., xn ? 0,
(12.2)
n
? xi = 1,
i =1
(12.3)
21
????? xi ? ??????????? ?????? ??????? ??? i-? ?????????.
????? ???????, ??????? ????????? ????????? ?????? ??????? ? ???????? ??? ????????????, ? ???????? ?????????? ??? ??????????????
?????????. ????? ??????? ????? ?????????????? (??????) ?????????
?????????? ??????? ????????? ?????????, ? ??????? ????????? ?????? ????????? ????? ??????????? 1, ? ??? ????????? ? 0. ??????? ??????
?????????????? ????????? ????? ????? ??????????????? ??? ?????????. ??? ?????? ????????? ?????? ???????? ?????? ? n -?????? ?????????? ???????????? ???????? ???? (12.1):
l1 = (1, 0, ..., 0 ) ,
l2 = (0, 1, ..., 0 ) ,
.....................
ln = (0, 0, ..., 1).
(12.4)
????????? ???? ???????? (12.1), ??????????? ???????? (12.2) ?
(12.3), ?????????? (n ? 1) -?????? ????????, ????????? ?? ???? l1, l2,
?, ln ?????? ?????????.
???? ???????? ????? ???????? ??????????????? ? ?????????? ????? S n .
? ?????? n = 2 ???????? ???????? ????????, ? ?????? n = 3 ? ?????????????, ? ?????? n = 4 ? ??????????. (???. 1).
x3
x2
n=2
e2
e3
n =3
S2
S3
e1
x1
e2
e1
x1
???. 1
22
x2
13. ????????? ?????????? ????????? ????
????? ? ???? ? ???????? ?????????
? a11 a12 ... a1n ?
?a
a22 ... a2 n ??
A = ? 21
? ...
... ... ... ?
?? a
??
? m1 am 2 ... amn ?
?????? 1 ? 2 ?????????? ???????? ???? ????????? ?????????
X = ( x1 , ..., xm ) , Y = ( y1 , ..., yn ).
??????????? 16. ???? (X, Y) ????????? ????????? ??????? ? ????????? ???? ?????????? ????????? ? ????????? ?????????? ? ???? ????.
? ???????? ???????? ? ????????? ?????????? ?????? ??????? ???????? (i, j) (? ?????? ??????????) ??????????? ? ???????????? xi yj.
????? ???????, ?????? ????? ???????? ??????? aij ? ????????????
xiyj, ? ?????????????? ???????? ??? ???????? ?????
m n
? ? aij xi y j .
i =1 j =1
??? ????? ??????????? ?? ??????? ?????? 1 ? ???????? (X, Y)
? ????????? ?????????? ? ???????????? ????? H ( X , Y ).
??????????? 17. ????????? ??????????? ????????? ???? ?????????? ????????????????? ???? < Sm , Sn , ? >, ? ??????? ??????????? ??????? ???????? ?? ????????? ????????? ? ???????? ????, ? ???????
???????? ?????? 1 ???????????? ???
m
n
H ( X , Y ) = ? ? aij xi y j .
i =1 j =1
(13.1)
? ???????????? ????????? ???????????? (13.1) ????? ??????????
m
n
m
i =1
j =1
i =1
T,
H ( X , Y ) = ? xi ? aij y j = ? xi Ai ?Y T = XAY
(13.2)
??? ???????????? ???????????:
W T = ( w1 , w2 ,..., wn )
T
? w1 ?
?w ?
= ? 2 ? ? ??????-???????,
? ... ?
?? w ??
? n?
23
? w1 ?
n
Z W = ( z1 , ..., zn ) ?? ... ?? = ? zi wi ? ????????? ???????????? ?????? w ? i =1
? n?
??? Z ? W.
????? ???????,
T
T.
H ( X , Y ) = X AY
(13.3)
????????? ??????????? ???????? ????? ????????????????? ????,
????????, ??? ? ????????? ?????????? ????????? ???? ????????
(X
*
, Y*
)
???????? ???????? ?????? (????????? ??????????), ???? ??????????? ??????? ???????????
*T ? X * AY
*T ? X * AY
T
X AY
(
)
(
?X ? S m , ?Y ? S n ,
)
(
)
H X , Y * ? H X *, Y * ? H X *, Y .
(13.4)
????? 1 (? ???????? ? ????????? ??????????).
????? Y ? ???????????? ????????? ?????? 2, a ? ????????? ?????:
T
AY
? a , i = 1, ..., m,
i
(13.5)
????? ??? ????? ????????? ????????? X = ( x1 , ..., xn ), X ? Sm ?????
T ?a.
XAY
? ? ? ? ? ? ? ? ? ? ? ? ? ?. ??????? ?????? ?? ?????????? (13.5) ?? xi
(???? ??????????? ?? ?????????, ??? ??? xi ? 0 ). ???????
T
xi AY
? xi a , i = 1, ..., m.
i
?????? ??? ?????????? ???????????:
m
m
m
i =1
i =1
i =1
T = ? x AY T ? ? x a = a ? x = a ? 1 = a ,
XAY
i i
i
i
??? ? ??????????? ????????.
?????????. ????? ??? ?? ?????????????? ???????? ? ?????????
?????????? ? ???????????? ????
T
T ? a ?X ? S ,
AY
? a i = 1, ..., m ? XAY
i
m
T
XA j ? a j = 1, ..., n ? XAY ? a ?Y ? Sn ,
XA j ? a
24
j = 1, ..., n ? XAY T ? a ?Y ? Sn .
??????? 5. ??? ???? ????? ????????
( X *, Y * ) ???? ???????????,
?????????? ? ??????????, ????? ??? ???? i = 1, ..., m ? j = 1, ..., n
??????????? ???????????
*T
*T ? X * A .
? X * AY
AY
i
j
? ? ? ? ? ? ? ? ? ? ? ? ? ?. 1. ?????????????. ?????
(13.6)
( X *, Y * )
?
???????? ??????????. ? ????? ??????????? (13.4) ??? ???? X ? Sn ?
Y ? Sn ? ????? ??????????? (13.6), ??? ??? ??? ?????????? ?? ?????????? (13.4) ??? ??????? ?????? ??? X = li , Y T = l j T .
2. ?????????????. ????? ????? ??????????? (13.6) ??? ????
i = 1, ..., m ? j = 1, ..., n. ???????? ? ????? ???????? ??????????
(13.6) ????? ? ???????? ? ????????? ??????????. ??? ???? ??? ??????????? (13.4).
(
)
*
*
??????? 6. ???? ???????? i , j ? ?????? ?????????? ???????? ???-
???????? ??? ????????? ???? ? ???????? A , ?? ??? ???????? ??????????? ? ??? ?? ?????????? ??????????.
? ? ? ? ? ? ? ? ? ? ? ? ? ?.
??? ???? ? ???????? A ,
(i , j ) ? ??????????? ???????? ? ??????*
? aij* ? ai* j* ? ai* j
*
?i = 1, ..., m, ?i = 1, ..., n.
(13.7)
?? ??????????? (13.6) ???????????? ? (13.7), ???? ??????????
X = i* , Y * = j*. ??????, ??????????? (13.6) ??????????? ??? ?????
*
X * , Y * ? ???????? ( X * = i* , Y * = j* ) ? ??????????? ???????? ??? ?????????? ?????????? ????. ???????????, ??? ???????? ?????????? ?
????????? ?????????? ?????????? ??? ????? ????????? ????.
?????????. ????? ?????? ?????????? ????????? ?????????, ??????????????? ?????? ????????? i , ??? ?? ???????? i. ?????,
i ? A = Ai? , A ? j T = A? j .
(13.8)
25
14. ????????????? ??????????
? ????????? ??????????. ????????? ??????????
T.
????? 2. 1. ??? ????? Y0 ? Sn ?????????? ???????? max XAY
0
X
T.
2. ??? ????? X 0 ? Sm ?????????? ??????? min X 0 AY
Y
? ? ? ? ? ? ? ? ? ? ? ? ? ?.
1. ?????????? ???????
T = ? x AY T . ??? ??????? ??????? ?? x , ..., x ,
F ( x1 , ..., xm ) = XAY
0
i i 0
1
m
i
? ?????? ???????? ??????????? ???????? ?? x1 , ..., xm .
????????? Sm ? ?????????, ????????????. ? ??????? F ( x1 , ..., xm )
????????? ?? Sm (? ???? ?????????????) ?????? ?????????.
2. ?????? ??????????? ????? ???????????? ??????????.
T ? ??????????? ??????? Y.
????? 3. 1. max XAY
X
T ? ??????????? ??????? X.
2. min XAY
Y
?????? ????? ?????????? ??? ?????????????.
T ? min max XAY
T ??????????.
??????? 7. ????????? max min XAY
X
Y
Y
X
? ? ? ? ? ? ? ? ? ? ? ? ? ?. 1. Sn ? ????????? ???????????? ?????????
T ?????????? ?? S (? ???? ?????????????) ???? ??????? max XAY
n
X
T
max XAY
??? ????????, ?. ?. min
??????????.
Y
X
T.
?????????? ???????????? ????????????? max min XAY
X
Y
??????? 8. (??????? ? ??????????)
?????? ?? ?? ???? ??????? A :
T = min max XAY
T.
max min XAY
X
Y
Y
X
(14.1)
???, ??????? ???????, ??????????? ????????? ????????? ???????
??????????.
??? ??????????????.
26
??????????? 18. ????? ???????? ?????????? (14.1) ?????????? ????????? ????????? ???? ? ???????? ????????? A . ??? ???????? ????
???????????? V ( A ).
???????????? ????? ????????? ????? ? ?? ????????? ????? ???????? ??? ???????, ???????? ?? ????????? ???? ????????? ??? (???,
??? ?? ?? ?????, ?? ????????? ???? ??????).
????? ??????? 1 ????????? X 0 , ?? ??????? ??????????? ???????
???????? ? (14.1) ? ????????? ?? ????? ????, ??? ?? ????? ???????????, ??? ??? ???? ???????? ????? ??????? ??, ??? ?? ?? ????????????
??????????????.
????? ??????? 2 ????????? Y0 , ?? ??????? ??????????? ???????
??????? ? (14.1) ? ???????? ?????????????? ?? ??? ????????, ??? ???
??? ???? ?? ?? ???? ?????? 1 ?????? ????? ?????????, ??? ?? ?? ???????????? ??????????????.
????? ???????, ?????? 1 ? 2 ?????? ???????? ????? ???? ?????????, ??????? ? ???? ?????????? ???????? ?????.
??????????? 19. ??????????? ????????? ??????? ? ????????????????? ???? ?????????? ?? ???????????? ???????????.
??????????? ???????? ????? ( X * , Y * ) ????? ?????????? ?????? ? ????
*T ? V ? X * AY
T ??? ???? X ? Sm , Y ? Sn .
XAY
(14.2)
?? ?????, ??? ????? ??????? 1 ??????????? ????????? ???? ???
??????? ?? ???????, ??? ???????? ????, ??? ?? ?? ????? ??? ????
????? 2. ????? ??????? 2 ??? ??????????? ????????? ?????? ????????? ??? ????? ?? ???????, ??? ???????? ????, ??? ?? ?? ????? ???
???? ????? 1. ?????????????, ????? ?????? ?? ??????? ????? ??????????? ????????? ?? ????? ?????? ???????? ?? ??????????. ???
???? ????????? ???????? ????????? ???? ?????? ????????????. ?????????????? ???? ?????????? ? ??? ??????, ??? ? ???????? ?????????? ???????? ????????? ????????? ?????????? ???????????????
?????????????? ???????? ???????? ?????? 1. ??????????? ?? ???????? ???????? ?????? 1 ? ????????? ??????? ????? ???? ??????????.
27
15. ??? ???????? ???????? ????
??????? 9. ? ????????? ???? ? ???????? ????????? A
V ( A ) = max min XA? j = min max Ai?Y T ,
j
X
Y
(15.1)
i
?????? ??????? ?????????? ??????????? ?? ??????????? ??????????
???????.
?????????? ??? ??????????????.
??????? 10. ??? ????? ??????? A ?????
max min aij ? V ( A ) ? min max aij ,
i
j
j
(15.2)
i
? ? ? ? ? ? ? ? ? ? ? ? ? ?. 1. ??????? ????? ???????????.
?? ????????? (15.1) ???????, ??? V ( A ) = max min XA? j .
X
j
?? max min XA? j ? max min iA? j = max min aij , ??? ??? ??????? ?? ???X
j
j
i
j
i
????????? ????????? ????????? ? ??????? ???? ?????? ??????? ???????????? ? ????? ???? ????????? ??????? ????????.
? V ( A ) ? max min aij , ??? ? ??????????? ????????.
j
i
2. ?????? ????? ??????????? ???????????? ??????????.
??????? 11. 1. ???? ????? 1 ????? ?????? ??????????? ????????? i0, ??
V = max min aij = min a i0 j .
j
i
(15.3)
j
2. ???? ????? 2 ????? ?????? ??????????? ????????? j0, ??
V = min max aij = max aij0 .
j
i
(15.4)
i
? ? ? ? ? ? ? ? ? ? ? ? ? ?. 1. ???????? (15.1) V = max min XA? j . ??
X
??????? ??????? ???????? ??????????? ??
j
X = i0 ,
max min XA? j = min i0 A? j = min a i0 j , ??? ? ??????????? ????????.
X
j
j
j
2. ???????????? ??????????.
28
?. ?.
16. ????????????? ?????????
??????????? 20. 1. ????????? X ? ?????? 1 ?????? ?????????? ????????? X ??, ( X ?? ? ?????? ???????????? X ? ), ???? X ?A? j > X ??A? j ???
????? j = 1, ..., n.
2. ????????? Y ? ?????? 2 ?????? ?????????? ????????? Y ?? , ( Y ??
?????? ???????????? ?????????? Y ? ), ???? Ai?Y ?T < Ai?Y ??T ??? ?????
i = 1, ..., m.
??????????? 21. 1. ????????? X ? ?????? 1 ?????????? ?????????
X ??, ( X ?? ???????????? X ? ), ???? X ?A? j ? X ??A? j ??? ?????
j = 1, ..., n. 2. ????????? Y ? ?????? 2 ?????????? ????????? Y ??, ( Y ??
???????????? Y ? ), ???? Ai?Y ?T ? Ai?Y ??T ??? ????? i = 1, ..., m.
? ?????????: 1. ?????? ????????? i ? ?????? 1 ?????? ?????????? (??????????) ?????? ????????? i ?? , ???? ai?j > ai??j ??? ???? j, ( ai?j ? ai??j
??? ???? j ). 2. ?????? ????????? j ? ?????? 2 ?????? ?????????? (??????????) ?????? ????????? j ??, ???? aij? < aij?? ??? ???? i , ( aij? ? aij?? ???
???? i ).
??????????? 22. ???????? ????????? ????????? ?????? ??????????
????????? ???? ??? ?????? ?????????, ??????????? ?????????? ??????? ???????? ???? ????????? ????????????.
?????? ?????????, ???????? ? ?????? ?????? ????????? ?????????,
?????????? ????????????? ??? ???.
??????? 12. ???? ?????? ????????? ?????? ?? ??????? ?????????? ? ??????? ????????? ??? ??????????? ?????????, ?? ???????
????? ?????? ? ????????, ???????????? ?????? ?????? ??????????
? ????? ??????????? ?????????? ??????? ??????, ????? ????????
????.
*
? ? ? ? ? ? ? ? ? ? ? ? ? ?. ????? i0 ?????????? ? ??????? X ?
??????????? ????????? ?????? 1. ????? ??????????? ?????????? i0 ?
????????? ????????? X * ???????????? xi0 > 0 .
*
(
)
????? Y ? ??????????? ????????? ?????? 2. X * ,Y * ? ????????
??????????, ? ??????
*
*T = V ( A )
X * AY
(16.1)
29
????? ?? ??????? 5 ??? ?????? i ?????
Ai 0Y *T < V .
(16.2)
???????????, ??? ??????????? ??????? 12 ???????. ??? ??????, ???
Ai 0?Y *T < V .
(16.3)
???????? ?? i ??????????? (16.2), ?????????? ?????? ?? xi , ?
*
???????? ??????????? (16.3), ???????
*T = ? x A Y *T < ? x V = V ? x = V .
X * AY
i
i?
i
i
*
i
*
i
*
i
*T < V , ??? ???????????? ??????? ???????, ???????? X * AY
??????? (16.1).
??????, ???? ????????????? ??????? ? ??????????? ??????? 12
*T
???????????, ?. ?. Ai0 Y = V . ??? ? ??????????? ????????.
??????????? ??????? 12 ????? ???????? ????????? ???????: ????
*
X , Y * ? ??????????? ????????? ??????? 1 ? 2, ??
n
Ai0 ?Y *T = ? ai0 j y j = V , ??? i ?????, ??? xi * > 0,
0
0
*
j =1
m
X * A? j0 = ? aij0 xi = V , ??? j ?????, ???
0
*
i =1
y j0 > 0.
*
(16.4)
(16.5)
??????? 13. ?? ???? ?????? ???????????? ?????? ????????? ??????
?? ?????????? ? ??????? ??? ??????????? ?????????.
? ? ? ? ? ? ? ? ? ? ? ? ? ?. ????? Y 0 ?????? ?????????? ?????? j0,
? X* ? ????????? ??????????? ????????? ?????? 1. ????? Ai? j0 > Ai?Y 0
??? ???? i. ???????? ??? ??????????? ?? xi * ?????? ? ???????? ??
i, ???????
0.
(16.6)
X * Ai? j0 > X * AY
???????????, j0 ?????????? ? ??????? ????????? ??????????? ????????? ?????? 2. ????? ?? ??????? 12
X * Ai? j0 = X * A? j0 = V .
(16.7)
< V , ? ??? ???????????? ????????? (16.6) ? (16.7), ????? X AY
*
????????? ????????????? ????????? X (??. (14.2)).
30
*
0
????? ???????, ???? ????????????? ???????, ? j0 ?? ????? ??????????? ? ??????? ??????????? ????????? ?????? 2.
??????????? 23. ????? ? = < A, B, H >, ?? =< A0 , B0 , H ? >, ??? A, B ?
????????? ?????? ????????? ??????? 1 ? 2; A0 ? A, B0 ? B, H ? ? ??????? H ?? A0 Ч B0 . ????? ?? ???????? ???????? ?.
?? ??????????? ???????, ??? ????????? ????????? ????????? ? ????????? ?????????? ?? ?????????? ? ????????? ????????? ????????? ???? ?.
??????? 14. 1. ? = < A, B, H > ? ???????? ????????????????? ????.
?? =< A \ i0 , B, H > ? ??????? ???? ?.
2. i0 ? ?????? ????????? ?????? 1 ? ???? ?, ???????????? ?????????
X 0 , ? ??????? ??????? ??? ?? ??????????. ????? ?????? ???????
( X * , Y * , V ) ???? ?? ???????? ???????? ?.
??? ??????????????.
??????? 15. 1. ? = < A, B, H > ?? =< A, B \ j0 , H > ? ??????? ???? ?.
2. j0 ? ?????? ????????? ?????? 2, ???????????? ????????? Y0 , ?
??????? ??????? ??? ?? ??????????. ????? ?????? ??????? ?? ????????
???????? ?.
??? ??????????????.
??????? 16. 1. i0? ?????? ????????? ?????? 1 ? ???? ?, ????????????
????????? ????????? ?????????? X0, ?? ?????????? i0 ? ????? ???????.
2. j0? ?????? ????????? ?????? 2 ? ???? ?, ???????????? ?????????
????????? ?????????? Y0, ?? ?????????? j0 ? ????? ???????.
3. ??? =< A \ i0 , B \ j0 , H > ? ??????? ?. ????? ?????? ??????? ??? ???????? ???????? ?.
??? ??????????????.
??????? 17 (??????? ?? ??????? ???????????????).
????? ( X * , Y * , V ) ? ??????? ???? ? =< A, B, H > . ?????
( X * , Y * , kV + C ) ? ??????? ???? ?? =< A, B, kH + C >, ??? k > 0, C ? R .
( )
(
)
(
)
(16.8)
? ? ? ? ? ? ? ? ? ? ? ? ? ?. H i, Y * ? H X * , Y * ? H X * , j
??? ???? i ? A, j ? B .
*
??? ??????? ????????????? X ? Y * (??. ??????? 5) ? ???? ?.
??????? ??????????? (16.8) ??????????? ???????? ???????????
( )
(
)
(
)
kH i, Y * + C ? kH X * , Y * + C ? kH X * , j + C
(16.9)
??? ???? i ? A, j ? B .
31
? ??? ??????????? ???????? ???????? ????????????? X* ? Y* ????
?? . ????? ???? ?? ????????? (16.8) ? (16.9) ?????, ??? ????
(
)
(
)
V = H X * ,Y * ? ???????? ???? ?, ?? V ? = kH X * , Y * + C = kV + C ?
???????? ???? .
17. ????????? ??????????? ????????? ???????
? ????????? ?????
????? T1 (A) ? ????????? ???? ??????????? ????????? ?????? 1 ?
????????? ???? ? ???????? ????????? A . T (A) ? ????????? ????
2
??????????? ????????? ?????? 2.
??????? 19. ?? ?????? ????????? ???? ? ???????? ????????? A
?????? ?? ????????, ????????:
1) ????????;
2) ????????;
3) ?????????;
4) ????????????.
? ? ? ? ? ? ? ? ? ? ? ? ? ?. ???????? ?????? ??? T1 (A) .
1. ????????? ??????? ?? ????????????? ??????????? ?????????,
?????????????? ? ?. 14.
2. ??? ?????????????? ?????????? T1 (A) ??????? ??? ???????????
????????? ?????? 1: X ? ? X ?? .
????? ??? ???? j = 1, ?, n X ?A? j ? V , X ??A? j ? V .
???????? ????????? X = ? X ? + (1 ? ? ) X ??, ??? ? ? [0; 1].
????? ??? ????? j = 1, ?, n XA? j = (? X ? + (1 ? ? ) X ??) A? j = ?
X ?A? j + (1 ? ? ) X ??A? j ? ? V + (1 ? ? )V = V ,
?. ?. XA? j ? V ??? ???? j, ? ??? ???? ??????? ????????????? ????????? X.
3. ???????????. ????? X1, X2, ?, Xe ? ?????????????????? ??????????? ????????? ?????? 1, ?????????? ? X0.
?? ????????????? ???? ????????? ?????
V ? X e A? j ??? ???? j = 1, ?, n, e = 1, 2, ?
32
(17.1)
?????, ???????? ? ??????? ? ??????????? (17.1), ???????
V ? lim X e A? j .
e ??
???????? ????????????? ??????? XA? j , ?? X (??? ??? ??? ????????),
(
)
????? V ? lim X e A? j = X 0 A? j , ? ??? ???? ??????? ????????????? X0.
e??
????? ???????, ?????? ?????????????????? ????? ?????????? ? ????????? T1 (A) .
4. ??????????????. T (A) ? S m , S m ? ??????????????? ????????
????????? ?????? 1, ?????????? ???????????? ?????????? ? T1 (A) ?
???????????? ?????????.
18. ??????????????? ???? (????? ??????). ?????????
?????????? ??????????????? ???. ??????? ????
????? ? = < I , {Si }i?I , {H i }i?I > ? ???????????? ???????????????
????. ? ????? ? ???? ????????, ?. ?. ????????? Si ?????? ?????????
??????? ?????? ???????.
????? ?i ? ???????????? ????????? ????????? ?????? i, ?. ?. ????????? ????????????? ????????????? ?? ????????? ?????? ?????????
Si; ?i ( si ) ? ??????????? ?????????? ?????? ????????? si ? ?????????
????????? ?i ;
?
i
? ????????? ???? ????????? ????????? ?????? i.
????? ?????? ?? ??????? ????????? ???? ????????? ?i , ?. ?. ???????? ???? ?????? ????????? ? ???????????? ?i ( si ) .
????? ????????? ????????? ???? ??????? i = 1, 2, ?, n ??? ????????????? ????????????? ?????????? ? ????????????, ?. ?. ??????????? ????????? ???????? s = (s1 , s2 , ..., sn ) ????? ?
(s1 )? ? 2(s2 )? ....... ? ? n (sn ) .
1
????? ???????, ????? ????????????? ????????????? ? ?? ?????????
???? ???????? ? ( s ) = ? ( s1 , s2 , ..., sn ) = ?1 ( s1 ) ? ?2 ( s2 ) ? ... ? ?n ( sn ).
??????????? 24. ????? ????????????? ????????????? ? ??????????
????????? ???? ? ? ????????? ??????????.
???????? ??????? ???????? ??????? ?? ??????? ? ???????? ? ??????????? ????????? ?????????.
33
??????????? 25. ???????? ??????? ???????? Hi ?? ???????? ? ?
????????? ?????????? ???? ?????????????? ???????? ???? ????????? ????????
H i (? ) = ? H i ( s ) ? ( s ) =
s?S
n
? .... ? H ( s , ..., s ) ? ? ? ( s ) .
i
s1?S1
??????????? 26. ???? ?* = < I ,
n
1
i =1
sn ?Sn
{? }
i i?I
i
i
(25.1)
, {H i }i?I > , ? ??????? ???-
?????? ???? ??????? ???? I, ????????? ????????? ??????? ?????? i ????
? i , ? ??????? ???????? Hi ???????????? ?????????? (25.1), ?????????? ????????? ??????????? ???? ?.
*
????????, ??? ? ??????????????? ???? ? = < I , {Si }i?I , {H i }i?I > s
(
)
*
*
???????? ????????? ??????????, ???? H i s si ? H i ( s ) ??? ????
i ? I ? si ? Si .
??????????? 27. ???????? ?????????? ?????????? ?????????? ?*
???? ? ?????????? ?????????? ?????????? ???? ? ? ????????? ??????????.
*
????? ???????, ? ???????? ?????????? ? ?, ???? ??? ???? i ? ?i
???????????
(
)
H i ?* ?i ? H i (?* ).
(25.2)
??????? 20. ??? ???? ????? ???????? ?* ? ???? ? ???? ?????????
?????????? ???? ???? (? ????????? ??????????), ?????????? ? ??????????, ????? ??? ?????? ?????? i ? ????? ??? ?????? ????????? si
???????????
H i (?* || si ) ? H i (?* ) .
(25.3)
? ? ? ? ? ? ? ? ? ? ? ? ? ?. 1. ????????????? ????? ???????? ?? (25.2), ???
??? si ? ??????? ?????? ?i .
2. ??? ?????????????? ????????????? ??????? ???????????? ????????? ????????? ?i ?????? i, ??????? ????????? (25.3) ?? ?i ( si ) ?
???????????? ?? si ? Si .
34
???????
? H (?
*
i
si ?Si
|| si ) ? ?i ( si ) ?
? ? ( s ) ? H (? ) =
*
i
i
i
si ?Si
= H i ( ? ) ? ? ?i ( si ) = H i (?* ) ? 1 = H i (?* ) ,
*
si ?Si
? ????? ????? ??????????? ????? H i (?* || ?i ).
????? ???????, H i (?* || ?i ) ? H i (?* ) , ??? ? ??????????? ????????.
???????????, ??? ???????? ?????????? ? ????????? ?????????? ?????????? ? ????? ???????? ??????????????? ????.
??????? 21 (??????? ????):
? ?????? ??????????????? ???? ? = < I , {Si }i?I , {H i }i?I > ?????????? ???? ?? ???? ???????? ?????????? ? ????????? ??????????.
?????????? ??? ??????????????.
????????????????? ??????
1. ???????? ?. ?. ?????? ???. ?????? ??? ???????????-????????????. ?., 1974.
2. ??????? ?. ?., ?????? ?. ?., ???????? ?. ?. ?????? ????????????
???????? ? ????????????? ??????????????-????????????? ?????: ????.
???????. ?., 1992.
3. ????? ?. ?., ??????? ?. ?. ???????? ? ?????????? ?????? ???.
?., 1981.
4. ?????? ?. ?. ?????????????? ?????? ??? ???????????. ?????????, 1995.
5. ???????? ?. ?., ???????? ?. ?., ?????? ?. ?. ?????? ???. ?.,
1998.
35
??????????
1. ???????? ? ??????? ???????????? ?????? ??? ................................
2. ??????? ????. ????????????? ???. ?????????? ?????????????
??? .........................................................................................................
3. ??????????? ??????????????? ???? ................................................
4. ?????????? ???????? ? ???????? ?????????? ...............................
5. ?????? «??????? ???????????» ......................................................
7. ????????????????? ???? .....................................................................
8. ???????? ????? ....................................................................................
9. ??????????? ? ?????? ??????? ........................................................
10. ????????? ?????????? ? ???????? ????? ......................................
11. ????????? ???? .................................................................................
12. ????????? ????????? .......................................................................
13. ????????? ?????????? ????????? ???? .......................................
14. ????????????? ?????????? ? ????????? ??????????. ????????? ?????????? ....................................................................................
15. ??? ???????? ???????? ???? .............................................................
16. ????????????? ????????? ................................................................
17. ????????? ??????????? ????????? ??????? ? ????????? ?????
18. ??????????????? ???? (????? ??????). ????????? ?????????? ??????????????? ???. ??????? ???? ......................................
????????????????? ?????? ....................................................................
36
3
4
7
8
9
13
13
14
15
18
21
23
26
28
29
32
33
35
???? ?? 1 ???). ?????? ?????? ???????? ???? ???????????, ??? ???
?????? ?? ??????? ????????????? ??????????? ?? ????????? ?????????
? ??????????, ??????????? ??????? ???? ?? ??????? ? ???????? ?????????, ????? ???? ?????? ? 0 (??? ???? ?????? ???????? ???????? 10).
????? ??????? ???????? ?????????? ??? ??????? ?????? ????????
?????????, ??? ??? ??? ??????????? ?????? ??????????? ????????????? ????? ? 10 ???. ???? ????? «????????» ??????? ??????? ???????????, ?????? ??????????? ????????? ??????????????? ????????? (????
? 1 ???), ?????? ???????? ?????????????? ? ???? ????????????? ?????
? 10 ??? ? ?????? ????????? ?? ??????? ???????????.
6. ?????????????? ??????????????? ???
???????????? ??????????????? ??? ?????? ??????????? ??????????? ?? ? ????? ??????, ?????? ??????? ???? ???????? ?????? ? ????
?? ??????????. ? ???????? ????? ??????? ????? ????? ?????? ????????????? ????????????? ???.
??????????? 6. ????? ???? ??? ??????????????? ???? ?? ? ??? ?
?????? ? ???? ?? ??????????? ??????? ? ?? ?????????, ????????????
???? ????????? ????????:
?? = < I , {Si }i?I , {H i?}i?I >
??? = < I , {Si }i?I , {H i??}i?I >
,
? ????? ?????????? k > 0, ? ??? ??????? ?????? ?????????? ???????????? Ci ?????, ??? ? ????? ???????? s
? i?( s ) = k ? H i??( s ) + ci .
????? ???? ?? ? ??? ?????????? ????????????? ??????????????.
?????????????? ??????????????? ???? ?? ???? ??? ????????????
?
? ~ ???.
10
??????????? ??? ???????? ?????????????? ??????????????? ? ??????????????, ????????? ? ??????????????.
1. ??????????????. ?????? ???? ? ????????????? ???????????? ????? ????: ? ~ ? .
? ? ? ? ? ? ? ? ? ? ? ? ? ?. ??????? k = 1 ? Ci = 0, ??? ???? i ? ?????
???????? s ????? H i ( s ) = 1 ? H i ( s ) + 0, ??? ? ??????????? ????????.
2. ?????????. ???? ?~ ?? , ?? ??~ ?.
? ? ? ? ? ? ? ? ? ? ? ? ? ?. ????? ?~ ?? , ????? ??? ???? ????? ???? ?
?? ?? ????????? ??????? ? ?? ?????????, ? ??????? ???????? ???????
????????? ???????:
H i ( s ) = k ? H i?( s ) + ci , k > 0, ci ? R
? H i?( s ) = 1/ k ? H i ( s ) ? ci / k ,
1
> 0, ci / k ? R
k
? ??~ ?,
??? ? ??????????? ????????.
3. ??????????????. ???? ? ~ ? ? ? ??~ ???, ?? ?~ ???.
? ? ? ? ? ? ? ? ? ? ? ? ? ?. ????? ? ~ ? ? ? ??~ ??? , ????? ?, ??, ???
????? ???? ? ?? ?? ????????? ??????? ? ?? ?????????, ? ???????
???????? ??????? ????????? ???????:
H i ( s ) = k ? H i?( s ) + ci ,
H i?( s ) = p ? H i??( s ) + bi , k > 0, p > 0, ci ? R, bi ? R.
????? H i ? H i?? ??????? ????????????
H i ( s ) = kpH i??( s ) + (kbi + ci ) , kp > 0, (kbi + ci ) ? R,
??? ?? ??????????? 6 ???????? ??????????????? ?~ ???.
????? ???????, ????????? ?????????????? ??????????????? ????????????? ???????? ????? ?????????? ?????????????? ?????????, ?, ??????, ????????? ????????? ???? ??????????????? ??? ?? ??????? ?? ?????????????? ?????? ????????????? ???? ????? ???. ??????
?????????????? ????????? ??????? ???????? ??? ?????? ?????? ??????????????? ?? ??????? ????? ???? ?? ????? ??????.
???????? ????? ????? ????????????? ?????????????? ?????? ?? ????
??????? ???? ? ???????? ????????? ????????? ??????? ci ? ??????
????????? ?????????, ???????????? ????????????? k.
11
??????? ???????????, ??? ???????? ????????? ??????? ? ????????????? ????????????? ????? ?????? ???? ??????????.
??????? 1. ????????????? ????????????? ???? ????? ???? ? ?? ??
???????? ??????????.
? ? ? ? ? ? ? ? ? ? ? ? ? ?. ????? ?~ ??, ? s* ? ???????? ?????????? ?
???? ?. ???????, ??? s* ? ???????? ?????????? ? ???? ?? . ?? ??????????? ???????? ?????????? s* ? ???? ? ???????, ??? ??? ???? i ? I ? si ? Si
????? ?????????:
H i ( s * si ) ? H i ( s*).
(6.1)
? ?????????????? ??????????????? ? ? ?? ????????
H i ( s*) = kH i?( s*) + ci ,
H i ( s * si ) = kH i?( s * si ) + ci ;
(6.2)
(6.3)
?? (6.1), (6.2), (6.3) ????????
kH i? ( s* si ) + ci ? kH i? ( s* ) + ci ,
?????? (? ?????? k > 0) ????????
H i?( s * si ) ? H i?( s*) ? i ? I ? si ? Si ,
??? ? ???????? ????????????? ????????? s* ? ???? ??.
??????????? 7. ??????????????? ???? ? = < I , {Si }i?I , {H i }i?I > ?????, ??? ? ????? ???????? s ? S ????????? ??????? ??????? ?????
????, ?????????? ????? ? ??????? ??????.
??????? 2. ?????? ??????????????? ???? ? ?????????? ?????? ????????????? ???????????? ????????? ???? ? ??????? ??????.
? ? ? ? ? ? ? ? ? ? ? ? ? ?. ????? ? = {I , {Si }i?I , {H i }i?I } ? ???? ? ??????????
? H i ( s) = c, c = const.
i?I
??????? ???????????? ci (i ? I ), , ??? ??????? ? c = c, ? ???????-
??????, ?. ?. ??? ???? ???????? s ? S ?????
i
i?I
??? ???? ?? = {I ,{Si }i?I , {H i?}i?I } ? ????????? ?????????
? i?( s ) = H i ( s ) ? ci . ?????, ???, ? ????? ???????, ? ? ?? ????????????, ?, ? ?????? ???????, ?? ? ???????? ????? ? ??????? ??????, ??? ???
? H i?( s) = ? H i ( s) ? ? ci = c ? c = 0
i?I
12
i?I
i?I
? s ? S.
7. ????????????????? ????
????????????????? ???? ???????? ??????? ??????? ??????????????? ????.
??????????? 8. ???? ? = < I , {Si }i?I , {H i }i?I > ?????????? ?????????????????, ???? ????? ??????? ? ??? ????? ????, ? ???????? ??????? ???????? ???? ??????? ? ?????? ???????? ????? ?? ???????? ?
(7.1)
?????????????? ?? ?????, ?. ?. H1 ( s ) = ? H 2 ( s ), ?s ? S .
?? ??????????? ???????, ??? ? ????? ???????? ?????????????????
???? H 1 ( s ) + H 2 ( s ) = 0 . ????? ??????, ????????????????? ???? ? ???
???? ???? ??? ? ??????? ??????.
????, ??? ??? ??????? ????????????????? ???? ?????????? ??????
?????? ???? ??????? ????????, ?????? ?????????? ???????????? ??
????????? (7.1).
??????? ??? ????????????????? ????? ?????? ???????? ??????:
? = < A, B, H >, ??? ? ? ? ? ????????? ????????? ??????? 1 ? 2, ? ? ?
??????? ???????? ?????? 1, ???????? ?? S = {(a , b): a ? A, b ? B}.
?? ??????? 2 ???????, ??? ??????????????? ???? ???? ??? ? ??????????
?????? ????????????? ???????????? ????????? ????????????????? ????.
8. ???????? ?????
????? ? = < A, B, H > ? ????????????????? ????. ??? ???????? ?????????? (a, b) ?????? ???? ?????
(8.1)
H1 ( a , b) ? H1 ( a ?, b), a ? ? A;
H 2 ( a, b) ? H 2 ( a , b?), b? ? B.
(8.2)
????????, ??? H 2 ( a , b) = ? H1 ( a , b), ??????? ????????? (8.2) ???
? H1 ( a , b) ? ? H1 ( a , b?), b? ? B ??? H1 ( a , b) ? H1 ( a , b?), b? ? B.
?????? ? (8.1) ??????? ??? ? ???? ???????? ??????????? (???????? ??
??????????? H 1 ? ??????????? ? ??? ??????? ???????? 1-?? ??????)
H ( a ?, b) ? H ( a , b) ? H ( a , b?), a ? ? A, b? ? B.
??? ??????????? ???????? ????????? ???????? ??????? ? ? ?????
(a, b): ??? ????? ????????? ?????????? a ???????? ? ????? ??????
???????????, ? ??? ????????? ???????? ?????????? b ? ?????? ???????????, ?. ?. ?? ?????????? a ??????? ? ??????????????, ? ?? ?????????? b ? ???????????. ????? ???????, ?? ???????????, ????????13
??? ???????? ?, ? ??????????? a ? b ????????? ?????????? ????? ??????????????? ????????????? ????? ???????????.
?????????. ??????? ????? ? ????, ??? ??????? ???????? ????? ? ?????? ??? ?????????? ?? ???????????? ??????? ? ?????????.
?????? ??????? ??????? ? ???, ??? ? ?????? ??? ??? ?????????????
????? ??????????, ????? ? ??? ?????????? ???????? ?????? ?? ??????
??????????, ? ??????? ? ?? ??????. ? ????????? ?? ?? ??????? ?????????? ??????????????? ????? ?? ???????.
?????? ??????? ? ???, ??? ? ????????? ??????????????? ????? ??????? ? ?????????????? ??????? ? ?????????? ? ???? ???????????????
???????????. ? ?????? ??? ????????????? ??????????? ?? ???????????. ????? ????, ???????? ????? ??????? ??????????? ?? ??????? ???????
??????? ???????.
9. ??????????? ? ?????? ???????
??????????? 9. ????? f ? ???????, ???????? ?? ????????? D. ??
?????????? ?? ???? ????????? ?????????? ?????????? ?? ???? ????? p
?????, ??? f ( x ) ? p ??? ????? x ? D.
??????????? ?????????: sup f ( x ) ??? sup f ( x ), ???? ???? ???????
x?D
???????????? ??????? ??????? f(x).
??????????? 10. ????????? ??????? f ?? D ?????????? ?????????? ?? ????? p ?????, ??? p ? f ( x ), ?x ? D.
???????????: inf f ( x ) ??? inf f ( x ).
x?D
??????????? 11. ???? ???????? ??????? f ?? D ???????????, ?. ?.
???? ?????????? x? ? D, ????? ??? f ( x )? = sup f ( x ), ?? ?? ??????????
??????????.
???????????: max f ( x ).
??????????? 12. ???? ??????? ??????? f ?? D ???????????, ?. ?.
???? ?????????? x? ? D ????? ??? f ( x*) = inf f ( x ), ?? ?? ??????????
?????????.
???????????: min f ( x ).
??????????? 1. ???? ?????????? ????????? ?????????? c ?????, ???
f ( x ) ? c, ?x ? D, ?? ? sup f ( x ) ? c;
x?D
14
???? ????????? ?????????? d ??????, ??? f ( x ) ? d , ?x ? D, ?? ?
inf f ( x ) ? d .
x?D
?????? ??????????? ??????? ??????????????? ?? ??????????? 9 ? 10.
??????????? 2. ???? f ( x ) ? g ( x ) ?????? ?? D ? ??? ????? x ? D
????? f ( x ) ? g ( x ) , ?? ????? ? sup f ( x ) ? sup g ( x ) , inf f ( x ) ? inf g ( x ).
? ? ? ? ? ? ? ? ? ? ? ? ? ?. ?? ??????? ? ??????????? ????????? ????? f ( x ) ? g ( x ) ? sup g ( x ) = const ? ? ?????? ??????????? 1 sup f ( x ) ?
? sup g ( x ).
?????????? ???????????? ??????????? ??? ?????????.
??????? 3. ???? x ?????????? ? ??????? D , y ?????????? ? ??????? E , f (x, y ) ?????????? ?? D Ч E , ??
supinf f ( x, y ) ? inf sup f ( x, y ).
x
y
y
(9.1)
x
? ? ? ? ? ? ? ? ? ? ? ? ? ?. ????? ??? ????? x ? y f ( x, y ) ? sup f ( x, y ).
x
???????? ??????????? 2, ???????: inf f ( x, y ) ? inf sup f ( x, y ) = const.
y
y
x
?????? ????? ????? ??????????. ??????? ? ???????????? ? ???????????? 1 ?????: supinf f ( x, y ) ? inf sup f ( x, y ).
x
y
y
x
????????? (??????????? 3): ???? ? ????????? (9.1) ??????????
???????????, ??
max inf f ( x, y ) ? min sup f ( x, y ).
x
y
y
(9.2)
x
????, ????? ????, ??????????? ? ??? ?????????? ??????????, ?. ?.
???? ? x ? min f ( x, y ) ? ?y ? max f ( x, y ) , ??
x
y
max min f ( x, y ) ? min max f ( x, y ).
x
y
y
(9.3)
x
??????????? (9.1), (9.2), (9.3) ???????? ?????? ????????????? ??????????. ??? ????? ??????? ???????? ? ?????? ???.
15
10. ????????? ?????????? ? ???????? ?????
??????? 4. ??? ???? ????? ??????? f ( x, y ) , ???????? ?? ?????????
D Ч E , ????? ???????? ?????, ?????????? ? ??????????, ????? ???????????? (?. ?. ???????????) ?????????
max inf f ( x, y ) , min sup f ( x, y )
y
y
x
(10.1)
x
? ??????????? ?????????
max inf f ( x, y ) = min sup f ( x, y ).
y
x
y
(10.2)
x
?????????. ??????????????? ??????????????? ????? ? ?????? ?????? ???.
? ? ? ? ? ? ? ? ? ? ? ? ? ?. 1. ?????????????. ????? f(x, y) ?????
???????? ????? ? (x*, y*) ? ???? ?? ???. ??? ????????, ???
(
) (
) (
)
f x, y * ? f x* , y * ? f x* , y .
(10.3)
???????? ? ????? ????? ????????? (10.3) ??????????? 1 ?. 9, ???????
(
) (
)
sup f x, y * ? f x* , y* .
x
(10.4)
?????, ????????? ??????????? ???????? ????????????? ? ???????
g ( y ) = sup f ( x, y ) , ????????
x
( )
(
) (
)
inf sup f ( x, y ) = inf g ( y ) ? g y * = sup f x, y * ? f x* , y* . (10.5)
y
y
x
x
??????????, ???????? ? ?????? ????? ????????? (10.3) ??????????? 1 ?. 9 ? ????????? ??????????? ????????? ????????????? ? ??????? z ( x ) = inf f ( x, y ) , ???????
y
( )
(
) (
)
supinf f ( x, y ) = sup z ( x ) ? z x* = inf f x* , y ? f x* , y * . 10.6)
y
x
x
y
????????? ????????? (10.5) ? (10.6), ?????:
inf sup f ( x, y ) ? sup f ( x, y* ) ? f ( x* , y* ) ? inf f ( x* , y ) ? supinf f ( x, y ) (10.7)
y
x
y
x
? inf sup f ( x, y ) ? sup inf f ( x, y ).
y
16
x
x
y
x
y
??, ???????? ??????? 3, ??????????? ? ??????????????? ??????????? supinf f ( x, y ) ? inf sup f ( x, y ).
x
y
y
x
???????
inf sup f ( x, y ) = supinf f ( x, y ).
y
x
x
(10.8)
y
??????, ? ????????? (10.7) ??????? ????? ?????. ?????????????,
????? ???? ????? ??? ????? ????? ???????????. ? ?????????,
inf sup f ( x , y ) = sup f ( x , y * ).
y
x
x
????? ??????? ? ????????? inf sup f ( x, y ) ??????? ???????????
y
x
(?????? ??? y = y*) ? ??? ????? ???? ???????? ??? min sup f ( x, y ).
y
x
????? ??? ?? ?? ????????? ???? ?????? ? ????????? (10.7) ????????,
??? inf f ( x* , y ) = supinf f ( x, y ), ?. ?. ???????? ??????????? ? ????? x*
y
y
x
? ??????? ?????? sup inf f ( x, y ) ?? ????? ?????? max inf f ( x, y ).
y
x
y
x
? ????? ????????? (10.8) ????? ???? ?????????? ????????? ??????? max inf f ( x, y ) = min sup f ( x, y ), ??? ? ??????????? ????????.
x
y
y
x
2. ?????????????. ??????????? ??????, ??? ????????? (10.1) ?????????? ? ?????, ? ??????? ?????????? ?? ??? ??????????? ?????????????? ? ?????? x* ? y*
??? ??????, ??? max inf f ( x, y ) = inf f ( x* , y ).
x
y
y
??, ????? ????, ?? ??????????? ???????? inf f ( x* , y ) ? f ( x* , y ),
y
??? ??? max inf f ( x, y ) = inf f ( x , y ) ? f ( x , y ).
*
x
y
*
*
y
(10.9)
?????????? ?????????, ????????
f ( x* , y * ) ? sup f ( x, y * ) = min sup f ( x, y ).
x
y
(10.10)
x
?? ????????????? ????????? (10.1) ?????, ? ?????? ????? ????
????? ? ??? ???????????? ? ???????????? (10.9) ? (10.10) ?????????. ?
?????????, sup f ( x, y * ) = f ( x* , y * ).
x
17
????????, ??? f ( x, y * ) ? sup f ( x, y * ) ?x, ???????
x
(10.11)
f ( x, y* ) ? f ( x* , y * ), ?x.
????? ??? ?? ?? ????????? ?????? ????????? (10.9) ?????
inf f ( x* , y ) = f ( x* , y * ).
y
? ?????? inf f ( x* , y ) ? f ( x* , y ) ?y ????????
y
f ( x * , y * ) ? f ( x * , y ) ?y .
(10.12)
????????? (10.1) ? (10.2) ?????? ???? f ( x, y* ) ? f ( x* , y * ) ? f ( x* , y ),
?. ?. (x*, y*) ? ???????? ????? ??????? f(x, y).
????????? 1. ? ???? ?????????????? ???? ??????? (?????????????)
???? ???????????, ??? ? ???????? ????????? ???????? ????? ????? ????
?????????? ???? ?? ????? ????? ????? x ? y, ?? ??????? ???????????
??????? ?????????? ? ?????????? (10.1). ???????, ???? (a, b) ? (c, d) ?
???????? ????? ??????? f(x, y), ?? ????? (a, d) ? (c, b) ??? ?? ?????
????????? ??? ???? ???????. ??? ???????? ????????? ???? ????????
????? ??????? ?????????? ?????? ???????????????? ?????????.
????????? 2. ?? ????????? (10.9), (10.10), (10.2) ????????, ??? ???????? ??????? ? ???????? ????? ????? ?????? ???????? ??????????
(10.1), ??????????? ????? ??????????.
?????????????, ???????? ??????? ?? ???? ?? ???????? ?????? ?????
???? ?????.
11. ????????? ????
??????????? 13. ????????????????? ????, ? ??????? ?????? ?????
????? ???????? ????????? ?????????, ?????????? ?????????? ??????.
????? ???? ????????? ???????????? ????????? ????????, ? ???????
?????? ????????????? ?????????? ??????? ??????, ??????? ? ?????????? ??????? ??????, ? ?? ?? ??????????? ????? ??????? ??????? ??????
? ??????????????? ???????? H (i, j ) = aij . ??? ??????? ??????????
???????? ????, ??? ???????? ?????????.
??????? ????????? ???????????.
????? A ? ??????? ????????? ????.
18
? a11 a12
?
A = ? a21 a22
? ...
...
??
? am1 am 2
... a1n ?
... a2 n ??
.
... ... ?
?
... amn ??
????? ???? ?????????? m Ч n ??????.
????????? ??????? ?????? ? ?????? ??????????????? ?????, ????????? ??????? ?????? ? ?????? ??????????????? ????????.
Ai . ? i-? ?????? ??????? A .
A. j ? j-? ??????? ??????? A .
(i, j) ? ????????, ??? i ? ????? ??????, j ? ????? ???????.
???????? (i, j) ? ????????? ???? ???????? ???????????, ????
aij* ? ai* j* ? ai* j
? i = 1,..., m, ? j = 1, ..., n.
? ???????????? ? ???????? 4 ??? ????????????? ? ????????? ????
???????? ????? (???????? ??????????) ?????????? ? ??????????, ????? ???? ????? ?????????: max min aij = min max aij .
j
j
i
i
????????????? ???? ?????????? ????????, ??? ??? ????????? ????????? ??????? ?????? ???????, ? ?????? ?????????? ?? ??? ???????????.
????? ?????????? ???????? ????? ??????? A :
? a11
?a
? 21
? ...
??
? am1
?
max ai1
i
? min a1 j ?
j
?
? min a 2 j ??
j
? ? max min aij
j
i
? ...
?
?
? min a mj ?
j
?
a12
a22
...
am 2
...
...
...
...
a1n ?
a2n ??
... ?
?
amn ??
?
?
?
...
max ain
max ai 2
i
i
min max aij
j
i
??????????? 14. ????????? i
?
j , ?? ??????? ???????????
max min aij ? min max aij ; ?????????? ?????????????? ??????????? ?
j
i
j
i
???????????.
19
???? ???????? ? ???????? ????? ???? ?????, ?? ?? ????? ????????
?????????? ????????? ????????? ???? ? ???????? ????????? A ? ???????????? V ( A ).
? ? ? ? ? ? 1. ????? ?????? ??????? ?????????
?3
5
3
?1
A = ?? 0
?2
?
?2
4
2
? min a1 j
j
?
? ? min a
2j
?
j
?
? ? min a
ij
j
?
max ai1
?
max ai 2
i
=2
?
?
= 0 ? ? max min aij = 2
j
i
?
?
= 2
?
max ai 3
i
i
=5
min max aij = 2
j
= ?3
=4
i
???????? ? ???????? ????? ? V ( A ) = 2. ???????? ?????? ????????
???????? (3, 1), ???????????? 3-? ?????????? ??????? ?????? ? 1-? ?????????? ??????? ??????.
?????????. ???? ??????? ? ???????? (3,3) ???? ????? 2, ?? ???
????? ?? ???????? ????????, ??? ??? ??? ??????? ?????? ?????? ???????? ????????? (???????? ????????? ????? ?????????? ??????? ??????), ? ??? ??? ??????? ?????? ? ?? ????????? (??????? ?? ????????
???????????? ????? ????????? ???????? ???????).
? ? ? ? ? ? 2. ????? ?????? ??????? ?????????
= ? 10 30 ? ? 10 ?? ? max min a = 20.
A
ij
? 40 20 ? ? 20
j
i
?
?
?
? ?
40
30
?
min max aij = 30
j
i
???????? ????? 20 ? ??????????? ??? i = 2, ? ???????? ????? 30 ?
??????????? ??? j = 2. ?????? ???? ?? ????? ???????? ?????????? ?
?????? ??????????.
20
????? ?????? ????? ?????? ???? ??????????? ????????? i = 2 ,
????? ??????? ??????? ??????? ???? ????????? j = 2 ? ????????? 20.
?? ? ???? ?????? ??????? ???????? ??????????? ?? ????? ???????????
????????? ? ??????? i = 1 , ????????? ??? ???? 30. ????? ??????? ??????? ??????? j = 1 ? ????????? ????? 10. ?? ? ???? ?????? ??????
??????? i = 2 ? ???????? 40, ?? ??? ?????? ??????? ??????? j = 2 ?
?????????? 20 ? ?.?. ?????, ??? ?? ???? ?? ???????? ?? ???????? ?????????? ???????????? ??? ????? ???????.
12. ????????? ?????????
???? ? ???? ? ???????? A ???????? ? ???????? ?? ????? ???? ?????,
?? ?? ??????? 4, ???? ? ????? ???????? ?? ????? ???????? ??????????.
? ???? ?????? ????? 1 ????? ?????????? ???? ??????? max min aij
j
i
(????? ??????????????? ???????), ? ????? 2 ????? ?? ???? ??? ??????, ??? min max aij (????? ??????????????? ????????). ?????? ? ?????j
i
?? ????? ???????? ???????? (??? ???????? ?????? ??????????????) ???????? ????????. ??????? ??????????? ??????? ??????? ????????
?????????????? ?????????????? ??????????? ??? ?????????? ????????? ? ???? ?????? ???????? ??????? ???? ???? ????????.
???????????, ??????? ????????????? ???????? ???? ????????? ????????, ?. ?. ?????????? ????????????? ???????????? ?? ????????? ?????? (??????????????) ?????????, ? ????? ???????????? ????? ?????????? ?????? ????????? ?????????? ?????????.
????? ???????? ????? ?????? ????????? ? ?????????? ??????? ????????? ????????????? ? ?? ???????? ???? ?? ?????? ?????????? ????
?, ????? ???????, ???? ???????? ????????? ??????????. ? ??????? ??
????????????? ???????? (??????) ?????????, ????? ????????? ?????????? ??????????.
??????????? 15. ????????????? ???????????? ?? ????????? ??????
????????? ?????? ?????????? ??? ????????? ??????????.
????????? ????????? ?????? ????? ??????????? ? ???? ???????
X = ( x1 , x2 , ..., xn ) ,
(12.1)
??? x1 ? 0, x2 ? 0, ..., xn ? 0,
(12.2)
n
? xi = 1,
i =1
(12.3)
21
????? xi ? ??????????? ?????? ??????? ??? i-? ?????????.
????? ???????, ??????? ????????? ????????? ?????? ??????? ? ???????? ??? ????????????, ? ???????? ?????????? ??? ??????????????
?????????. ????? ??????? ????? ?????????????? (??????) ?????????
?????????? ??????? ????????? ?????????, ? ??????? ????????? ?????? ????????? ????? ??????????? 1, ? ??? ????????? ? 0. ??????? ??????
?????????????? ????????? ????? ????? ??????????????? ??? ?????????. ??? ?????? ????????? ?????? ???????? ?????? ? n -?????? ?????????? ???????????? ???????? ???? (12.1):
l1 = (1, 0, ..., 0 ) ,
l2 = (0, 1, ..., 0 ) ,
.....................
ln = (0, 0, ..., 1).
(12.4)
????????? ???? ???????? (12.1), ??????????? ???????? (12.2) ?
(12.3), ?????????? (n ? 1) -?????? ????????, ????????? ?? ???? l1, l2,
?, ln ?????? ?????????.
???? ???????? ????? ???????? ??????????????? ? ?????????? ????? S n .
? ?????? n = 2 ???????? ???????? ????????, ? ?????? n = 3 ? ?????????????, ? ?????? n = 4 ? ??????????. (???. 1).
x3
x2
n=2
e2
e3
n =3
S2
S3
e1
x1
e2
e1
x1
???. 1
22
x2
13. ????????? ?????????? ????????? ????
????? ? ???? ? ???????? ?????????
? a11 a12 ... a1n ?
?a
a22 ... a2 n ??
A = ? 21
? ...
... ... ... ?
?? a
??
? m1 am 2 ... amn ?
?????? 1 ? 2 ?????????? ???????? ???? ????????? ?????????
X = ( x1 , ..., xm ) , Y = ( y1 , ..., yn ).
??????????? 16. ???? (X, Y) ????????? ????????? ??????? ? ????????? ???? ?????????? ????????? ? ????????? ?????????? ? ???? ????.
? ???????? ???????? ? ????????? ?????????? ?????? ??????? ???????? (i, j) (? ?????? ??????????) ??????????? ? ???????????? xi yj.
????? ???????, ?????? ????? ???????? ??????? aij ? ????????????
xiyj, ? ?????????????? ???????? ??? ???????? ?????
m n
? ? aij xi y j .
i =1 j =1
??? ????? ??????????? ?? ??????? ?????? 1 ? ???????? (X, Y)
? ????????? ?????????? ? ???????????? ????? H ( X , Y ).
??????????? 17. ????????? ??????????? ????????? ???? ?????????? ????????????????? ???? < Sm , Sn , ? >, ? ??????? ??????????? ??????? ???????? ?? ????????? ????????? ? ???????? ????, ? ???????
???????? ?????? 1 ???????????? ???
m
n
H ( X , Y ) = ? ? aij xi y j .
i =1 j =1
(13.1)
? ???????????? ????????? ???????????? (13.1) ????? ??????????
m
n
m
i =1
j =1
i =1
T,
H ( X , Y ) = ? xi ? aij y j = ? xi Ai ?Y T = XAY
(13.2)
??? ???????????? ???????????:
W T = ( w1 , w2 ,..., wn )
T
? w1 ?
?w ?
= ? 2 ? ? ??????-???????,
? ... ?
?? w ??
? n?
23
? w1 ?
n
Z W = ( z1 , ..., zn ) ?? ... ?? = ? zi wi ? ????????? ???????????? ?????? w ? i =1
? n?
??? Z ? W.
????? ???????,
T
T.
H ( X , Y ) = X AY
(13.3)
????????? ??????????? ???????? ????? ????????????????? ????,
????????, ??? ? ????????? ?????????? ????????? ???? ????????
(X
*
, Y*
)
???????? ???????? ?????? (????????? ??????????), ???? ??????????? ??????? ???????????
*T ? X * AY
*T ? X * AY
T
X AY
(
)
(
?X ? S m , ?Y ? S n ,
)
(
)
H X , Y * ? H X *, Y * ? H X *, Y .
(13.4)
????? 1 (? ???????? ? ????????? ??????????).
????? Y ? ???????????? ????????? ?????? 2, a ? ????????? ?????:
T
AY
? a , i = 1, ..., m,
i
(13.5)
????? ??? ????? ????????? ????????? X = ( x1 , ..., xn ), X ? Sm ?????
T ?a.
XAY
? ? ? ? ? ? ? ? ? ? ? ? ? ?. ??????? ?????? ?? ?????????? (13.5) ?? xi
(???? ??????????? ?? ?????????, ??? ??? xi ? 0 ). ???????
T
xi AY
? xi a , i = 1, ..., m.
i
?????? ??? ?????????? ???????????:
m
m
m
i =1
i =1
i =1
T = ? x AY T ? ? x a = a ? x = a ? 1 = a ,
XAY
i i
i
i
??? ? ??????????? ????????.
?????????. ????? ??? ?? ?????????????? ???????? ? ?????????
?????????? ? ???????????? ????
T
T ? a ?X ? S ,
AY
? a i = 1, ..., m ? XAY
i
m
T
XA j ? a j = 1, ..., n ? XAY ? a ?Y ? Sn ,
XA j ? a
24
j = 1, ..., n ? XAY T ? a ?Y ? Sn .
??????? 5. ??? ???? ????? ????????
( X *, Y * ) ???? ???????????,
?????????? ? ??????????, ????? ??? ???? i = 1, ..., m ? j = 1, ..., n
??????????? ???????????
*T
*T ? X * A .
? X * AY
AY
i
j
? ? ? ? ? ? ? ? ? ? ? ? ? ?. 1. ?????????????. ?????
(13.6)
( X *, Y * )
?
???????? ??????????. ? ????? ??????????? (13.4) ??? ???? X ? Sn ?
Y ? Sn ? ????? ??????????? (13.6), ??? ??? ??? ?????????? ?? ?????????? (13.4) ??? ??????? ?????? ??? X = li , Y T = l j T .
2. ?????????????. ????? ????? ??????????? (13.6) ??? ????
i = 1, ..., m ? j = 1, ..., n. ???????? ? ????? ???????? ??????????
(13.6) ????? ? ???????? ? ????????? ??????????. ??? ???? ??? ??????????? (13.4).
(
)
*
*
??????? 6. ???? ???????? i , j ? ?????? ?????????? ???????? ???-
???????? ??? ????????? ???? ? ???????? A , ?? ??? ???????? ??????????? ? ??? ?? ?????????? ??????????.
? ? ? ? ? ? ? ? ? ? ? ? ? ?.
??? ???? ? ???????? A ,
(i , j ) ? ??????????? ???????? ? ??????*
? aij* ? ai* j* ? ai* j
*
?i = 1, ..., m, ?i = 1, ..., n.
(13.7)
?? ??????????? (13.6) ???????????? ? (13.7), ???? ??????????
X = i* , Y * = j*. ??????, ??????????? (13.6) ??????????? ??? ?????
*
X * , Y * ? ???????? ( X * = i* , Y * = j* ) ? ??????????? ???????? ??? ?????????? ?????????? ????. ???????????, ??? ???????? ?????????? ?
????????? ?????????? ?????????? ??? ????? ????????? ????.
?????????. ????? ?????? ?????????? ????????? ?????????, ??????????????? ?????? ????????? i , ??? ?? ???????? i. ?????,
i ? A = Ai? , A ? j T = A? j .
(13.8)
25
14. ????????????? ??????????
? ????????? ??????????. ????????? ??????????
T.
????? 2. 1. ??? ????? Y0 ? Sn ?????????? ???????? max XAY
0
X
T.
2. ??? ????? X 0 ? Sm ?????????? ??????? min X 0 AY
Y
? ? ? ? ? ? ? ? ? ? ? ? ? ?.
1. ?????????? ???????
T = ? x AY T . ??? ??????? ??????? ?? x , ..., x ,
F ( x1 , ..., xm ) = XAY
0
i i 0
1
m
i
? ?????? ???????? ??????????? ???????? ?? x1 , ..., xm .
????????? Sm ? ?????????, ????????????. ? ??????? F ( x1 , ..., xm )
????????? ?? Sm (? ???? ?????????????) ?????? ?????????.
2. ?????? ??????????? ????? ???????????? ??????????.
T ? ??????????? ??????? Y.
????? 3. 1. max XAY
X
T ? ??????????? ??????? X.
2. min XAY
Y
?????? ????? ?????????? ??? ?????????????.
T ? min max XAY
T ??????????.
??????? 7. ????????? max min XAY
X
Y
Y
X
? ? ? ? ? ? ? ? ? ? ? ? ? ?. 1. Sn ? ????????? ???????????? ?????????
T ????????
Документ
Категория
Без категории
Просмотров
0
Размер файла
316 Кб
Теги
danil
1/--страниц
Пожаловаться на содержимое документа