Івченко І.Ю. Математичне програмування
Подождите немного. Документ загружается.
181
20
83.
1.
48 3
= $ n 7
1
, 7
2
, …, 7
n
. ' =
:
¸
¸
¸
¸
¹
·
¨
¨
¨
¨
©
§
f
f
f
...
............
...
...
21
1121
112
nn
n
cc
cc
cc
C
(20.1)
? c
ij
c
ji
.
= $ = -
. A !, # =
. " $ = -
$- . * =
, . C$ $ ",
# -
"< =. «^»
%, " , > $
= = , $ $ -
.
; t " # = -
i
1
, i
2
, …, i
n
, ":
t = (i
1
, i
2
, …, i
n
)
t = {(i
1
, i
2
), (i
1
, i
2
), …, (i
n – 1
, i
n
), (i
n
, i
1
)}
@= " t l:
l(t) = l(i
1
, i
2
, …, i
n
) =
¦
ij
c ( (i, j) ! t).
2. 48( 23 8:
& " 7
1
":
c
12
, c
13
, …, c
1n
...
182
'$ :
h
1
= min (c
12
, c
13
, …, c
1n
)...
; h
1
= , # , -
= , " 7
1
(, 7
1
). * = " -
= h
i
.
% " ! = ,
' =
¦
n
i
i
h
1
(20.2)
! => > = ", $ " !<
= , $ " $.
' = «!» h
i
(!
). % ) " «-
#» -$ h
i
-
( ) $- "
( ).
n
nn
n
h
h
h
cc
cC
cc
n
C
n
"
"
"
2
1
21
1121
112
...''
............
'...'
'...'
2
1
'
21
¸
¸
¸
¸
¹
·
¨
¨
¨
¨
©
§
f
f
f
(20.3)
%
c'
ij
= c
ij
– h
i
c
ij
= c'
ij
+h
i
i = 1, n, j = 1,n.
? , = << ’ -
$ .
' (20.2) = =
. * = , $ < -
= " < =.
" = " $ (90):
l(t) = l(i
1
, i
2
, …, i
n
) =
¦
tji
ij
c
),(
=
¦
tji
ij
i
hc
),(
)
'(
=
=
¦
tji
ij
c
),(
'
+
¦
n
i
i
h
1
=
¦
tji
ij
c
),(
'
+
0
, (20.4)
(i, j) ! t ( , # "),
0
=
¦
n
i
i
h
1
.
183
& 1- %'. J !,
# ? ? % —
7
1
. * , #
, . *, -
, '
21
— , $ -
h
2
, #$, "" 7
2
, 7
1
.
*-
'
31
— , $
h
3
, #$, "" 7
3
, 7
1
. . J#
c'
i1
$
H
1
= min ('
12
, '
13
, …, c'
1n
), (20.5)
, # #$ 7
1
( $-
"),
=
$
0
$
" " = H
1
. * " . =, -
0
= $
¦
n
j
Hj
1
. ?
=
0
+
¦
n
j
Hj
1
=
¦
n
i
i
h
1
+
¦
n
j
Hj
1
. (20.6)
3. 48( 23 42:
) > " H
j
:
¸
¸
¸
¸
¹
·
¨
¨
¨
¨
©
§
f
f
f
cc
...''''
............
''...''
''...''
21
1121
112
nn
n
cc
cc
cc
C
(20.7)
%
c"
ij
= c’
ij
– H
j
= c
ij
– h
i
– H
j
c
ij
= c"
ij
+ h
i
+ H
i
i = 1, n, j = 1, n. (20.8)
? = << -
’ $ .
* = " t = $
l(t) = l (i
1
, i
2
, …, i
n
)=
¦
tji
ij
c
),(
" + ... (20.9)
(20.8) !, # " $ >
, #$
¦
tji
ij
c
),(
" $ $ >. %
184
= = ". '
— ! > > %
= . J$ $ -
= = ,
$ $ " => . *
!
-
. ? ’ $ $ ".
4.
E3 34
C # $ ’ -
, $> %", $ -
> " (i, j), c"
ij
= 0.
* , n ? @
«» «$» "
(i, j).
C c"
pq
= 0. ( 7
7
q
,
«», 7
7
q
,
" k- ,
«$». @ =< (p, q), < c"
pq
= 0,
= :
(p
,
q) =
iq
p
pj
cc
zz
iqj
minmin . (20.10)
@ > " $ , <
c"
k, m
= 0
(
k, m
) = max (p, q). (20.11)
% , # > >, -
, $ ! " -
7
k
7
.
&$’! = " (n!) = 8
N. ? 8 ", # 7
k
7
m
, > = (k, m), N — ", #
7
k
7
m
, (k, m).
% = ' = ,
(N) = + (
k, m
), (20.12)
$- ", # " 7
7
,
( ? "), " $-
" (
k, m
).
185
5. E 238 ( . C3
;$! = " 8. @
"
m, k
= ^, # ! 7
k
7
m
, 7
m
7
k
$-
!. % 7
k
> " ( = $-
" $), $ > -
, $ k-> . * >-
! m- ( 7
m
> " , -
=, $" $, , -
= # $ ). ; $
> . ; ,
= (
).
-
= ( $ -
= = $ , "
> (k, m), < h'
i
. ; -
> — = i-
h'
i
. ; = j- -
h'
i
. K'
j
! -
. '
’=
¦
n
i
i
h
1
'+
¦
n
j
Hj
1
, (20.13)
= , # =, ’ >
" (k, m), $
$ " # ', $ =
", # = 8, >!
(8) = + '. (20.14)
6.
E 33
% , $ -
(.
10):
G
0
8
=(
k
, m)
N
=(
k
, m)
(
N
)
(
8
)(G
0
) =
&. 10. ’
186
? ", $ , < "
. C " , , , # $
" => 8 = (k, m). @ ! -
= $< = =, < # -
$ (20.10)—(20.11) =
. ;, $
$’ $ -
= = $ " ". A $
> , "
, # " $ ".
; $ $ = =-
, #$ $
.
C, " > (-
):
(4,3), (5,4) (6,5), " (3,5)
,
(5,4), (4,3) (3,5), > (4,6) — (6,5),
(5,4) (4,6).
@ #$ > =, $
" ! ^
"
3, 5
= ^ "
4, 6
= ^.
; $ " = =
, # !< " $ "
$ #, = < ". %
< " = <<. %> "> -
=, , " 8, -
N. J# > " 8,
= !< " . J# = -
> "> " = (e, f), -
, $ $ (e, f), $-
("
e, f
= ^) !< ,
.
= $ n 7
1
, 7
2
, …, 7
n
, =
:
¸
¸
¸
¸
¹
·
¨
¨
¨
¨
©
§
f
f
f
...
............
...
...
21
1121
112
nn
n
cc
cc
cc
C
187
= $ = .
A !, # =
. C$ $ ", # -
"< =.
":
1. ) > .
2. ) > .
3. @= " $ ">, =
=
0
+
¦
n
j
Hj
1
=
¦
n
i
i
h
1
+
¦
n
j
Hj
1
.
4. =
(p, q)=
iq
p
pj
cc
zz
iqj
minmin .
5. @ > " $ , <
c"
k, m
= 0
(k, m)
= max (p, q).
6. ;$! = " N 8.
(N) = +
(k, m)
,
(
8) = + '.
7. ? $ ", < " .
8. ; . 1.
1.
& . C ! :
123456h
i
1 ^ 26 43 16 30 26 16
2 7 ^16130251
32013^355 0 0
4 21 16 25 ^ 18 18 16
5 12462748 ^ 5 5
6235 5 9 5 ^ 5
C =
188
) > :
123456h
i
1 ^ 10 27 0 14 10
2 6 ^ 15 0 29 24
32013^355 0
4509^22
5 7 41 22 43 ^ 0
6180 0 4 0 ^
K
j
5
) > :
123456h
i
1 ^ 10 27 010 14 10
2 1 ^ 15012924
31513^35505
4010
0
9^22
5 2 41 22 43 ^ 0
2
6130
0
0
9
40
2
^
= (16 + 1 + 0 + 16 + 5 + 5) + 5 = 48
=, = " $ ", = 48.
= (20.10):
(1
,
4) = min (10, 27, 14, 10) + min (0, 35, 43, 4) = 10;
(2
,
4) = min (1, 15, 29, 24) + min (0, 35, 43, 4) = 1;
(3, 6) = min (15, 13, 35, 5) + min (10, 24, 2, 0) = 5;
(4, 1) = min (0, 9, 2, 2) + min (1, 15, 2, 13) = 1;
(4, 2) = min (0, 9, 2, 2) + min (10, 13, 41, 0) = 0;
(5, 6) = min (2, 41, 22, 43) + min (10, 24, 0, 2) = 2;
(6, 2) = min (13, 0, 4, 0) + min (10, 13, 0, 41) = 0;
(6, 3) = min (13, 0, 4, 0) + min (27, 15, 9, 22) = 9;
(6, 5) = min (13, 0, 4, 0) + min (14, 29, 5, 2) = 2.
" = %''.
; (20.11):
(k, m)
= max (10,1, 5, 1, 0, 2,0, 9, 2) =10 =
(1, 4)
.
% , "> >, # >! ", $-
(1,4). $! (4, 1) >! 1->
4- :
C =
C =
189
2356h
i
2356h
i
2 1 ^ 152924 1 2 0 ^ 142823
31513^50031513^50
4^092204^0922
5 2 41 22 ^ 0 0 5 2 41 22 ^ 0
6130 0 0 ^ 0 6130 0 0 ^
) > :
20
16
^142823
31513^ 50
5
4^0292 2
5 2 41 22 ^ 0
2
6130
0
0
9
0
2
^
' = 1.
% = $ ’ (. 11)
G
0
8 = (1, 4)
N
= (1, 4)
(?) = 48 + 10 = 58
(G
0
) = 48 (8) = 48 + 1
&. 11. ’
@ > " < -
< , > < .
C> > $ (2,1), # < -
! $"> >, > 16.
(1, 2) , #$ $ $. '-
>! "
2:
2356h
i
2356h
i
313^ 5 0 313^ 50
4^9222 4^700
5 41 22 ^ 0 5 41 22 ^ 0
6000^ 6000^
190
) > . C !
4 ( ! ). , #
, h
2
= 2. '! 2 =! -
>, . * = !< =
! , $ .
? " 8 = (2,1): (8) =
= 49 + 2 = 51. * " Y = (2, 1) : (Y) = 49 + 16 = 65.
/ ’ $! :
(2, 1) =
=49 + 2 = 51
(2, 1) =
= 49 + 16 = 65
G
0
F = (1, 4)
? = (1, 4)
F = (2, 1)
F = (2, 1)
(G
0
) = 48 (1, 4) = 49
(1, 4) = 58
&. 12. / ’
'$ " , -
! < :
min ((1, 4), (2, 1), (2, 1)) = min (58, 51, 65) = 51.
%. ., > ! " (2, 1). ( >
". ! :
2356h
i
313^ 505 2 3 5 h
i
235h
i
4^70
0
0
0
313^5538^0
54122^0
22
4^70
0
4^70
60
13
0
7
0
0
^60
13
0
7
^ 600^
? " >! (5,6). * (6,5) $!
$. ; : (1,4), (2,1) (5,6) =
$ (4,2) "
4, 2
= ^. ' 5 -
6 > :
= . % ’-
$! :
G
0
(2, 1)
(2, 1)
(5, 6)
(5, 6)
= 48 = 49 = 51
(1, 4)
(1, 4)
= 51 +
+ 5 = 56
= 58 = 65
= 51 +
+ 22 = 73
&. 13. / ’