Івченко І.Ю. Математичне програмування
Подождите немного. Документ загружается.
191
@ = :
235h
i
38^08 23h
i
23 h
i
4 ^ 7 07 4 ^ 7 7 4 ^ 0 (26)
60807^ 6 0 ^ 60^
% 8, $
3 –5. ' < ,
’ >! " (3, 5), $ -
, >! (6, 3): "
6, 3
= ^.
) > .
G
0
(
1, 4
)
(1, 4)
(
2, 1
)
(2, 1)
(
5, 6
)
(5, 6) (3, 5)
= 48 = 49 = 51
= 58 = 65 = 73
= 56
(3, 5)
(
5, 6
)
= 56 + 7 = 63
= 56 + 8 = 64
&. 14. / ’
) " $! ", !
" :
min ((1, 4), (2, 1), (5, 6), (3, 5)) = min (58, 65, 73,63) = 58.
'!, # #> ! " Y, $
". ;! >, < $ -
=, # ! ". A , $ -
$ (1,4) > ".
$ $ ,
$ $ (1,4) , $
.
=, ! < ( "
1,4
= ^).
123456h
i
1 ^ 26 43 ^ 30 26 26
2 7 ^ 16 1 30 25 1
32013^355 0 0
4 21 16 25 ^ 18 18 16
5 12462748 ^ 5 5
6235 5 9 5 ^ 5
C =
192
) > -
:
123456h
i
1^017^40
2 6 ^ 15 0 29 24
32013^355 0
4509^22
5 7 41 22 43 ^ 0
6180 0 4 0 ^
K
j
5
123456
h
i
1^0
0
17 ^ 4 0
0
21^150
5
29 24
31513^3550
5
40
1
0
0
9^22
5 2 41 22 43 ^ 0
2
6130
0
0
9
40
2
^
= (26 + 1 + 0 + 16 + 5 + 5) + 5 = 58.
@ > ", $! (6, 3),
(3, 6) >! ("
3, 6
= ^). '>! 6 3
>:
123456h
i
123456h
i
1^0^40 1^0^40
2 1 ^ 0 29 24 2 1 ^ 0 29 24
3 151335 5 ^ 5 3 151335 5 ^
400^22 400^22
5 2 41 43 ^ 0 5 2 41 43 ^ 0
%:
= (6, 3) = 58 + 5 = 63 = (6, 3) = 58 + 9 = 67
C =
C =
193
* ’ $! :
(6, 3)(6, 3)
G
0
(1, 4)
(1, 4)
(2, 1)
(2, 1)
(5, 6)
(5, 6)
(3, 5)
(3, 5)
= 48 = 49 = 51 = 56
= 73 = 65
= 58
(6,3) = 63 = (6,3) = 67
= 56 +
+ 7 = 63
= 56 +
+ 8 = 64
&. 15. / "
) " ! " -
(3, 5) = (6, 3) = 63.
J ? , , < !
" ", $ (3,5). ? $ -
" (20.14). ? -
. J# $ ,
" — , # =
". ? ’
, # ! [2,2],
" > $ !< . % -
, . ’ $! :
(6, 3)
(3, 5)
(4, 3),
(6, 2)
G
0
(1, 4)
(1, 4)
(2, 1)
(2, 1)
(5, 6)
(5, 6) (3, 5)
(6, 3)
= 48 = 49 = 51 = 56 = 63
(6, 3) = 63
= (6, 3) = 67
= 58 = 65 = 73 = 64
&. 16. /. ’
'" $, > < -
":
(1,4), (2,1), (5,6), (3,5), (4,3) (6,2) -
: t = {(1,4), (4,3), (3,5), (5,6), (6,2), (2,1)}. (20.15)
194
@= "
l (t) = c
1,4
+ c
4,3
+ c
3,5
+ c
5,6
+ c
6,2
+ c
2,1
=
= 16 + 25 + 5 + 5 + 5 + 7 = 63.
J , = " $!
> $. " $
=. $ = $- ,
(20.15) , "> =-
. &’ .
2.
’(< &%:
123456h
i
1 — 41 60 39 46 10 10
231—5916 1 51 1
3 29 51 — 14 42 50 14
4 32 12 52 — 16 26 12
516391560—5715
61530384736—15
H
j
67
123456h
i
i
1 — 31 50 29 36
0
43
10 29
2 30 — 58 15 0
19
50 1 15
31537—0
30
28 36 14 15
4200
19
40—414124
5 1 24 0
19
45 — 42 15 1
60
16
15 18 32 21 — 15 15
H
j
00000067
j
1151815414
&. 17. @ ’
67 (1, 6)
110
(1, 6)
83
(3, 4)
102
(3, 4)
83
(4, 2)
108
(2, 5)
114
(2, 5)
83
(4, 2)
83
(5, 1)
83
(6, 3)
83
195
12345h
i
i
2 30 — 58 15 0 0
3 1537—0280
4 20040—4 0
5 1 24 0 45 — 0
6 0 15 18 32 21 15
H
j
j
12345h
i
i
2 30 — 58 15 0 0
3 1537—0280
4 20040—4 0
5 1 24 0 45 — 0
6 0 0 3 17 6 15
1000016
j
12345h
i
i
2 29 — 58 15 0
19
15
31437—
0
29
28 14
4290
0
58 — 4 0
50
14
24 0
3
45 — 0
600
3
3176 3
H
j
j
14 0 3 15 4
196
1235h
i
i
229—58
0
31
029
4290
25
58 4 0 25
50
29
24 0
3
—0 0
600
3
3603
H
j
00000
j
29 0 3 4
123h
i
i
425
0
25
58025
50
25
24 0
3
00
600
3
303
H
j
0000
j
25 0 3
13h
i
i
000
6030
H
j
000
j
':
L = 83
: 1—6—3—4—2—5—1
1
6
5 4
3
2
&. 18. /. "
197
1. %&!'
2. $' ?
3. 6 -
, ; 8 N.
4. $ ?
1.
&’= =.
1. 11.
123456 123456
1 — 4 1013 4 8 1 —3645305217
2 2 — 9 7 6 7 2 27 — 49 31 25 27
3 8 5 — 5 5 9 3 4222—481660
4585—710 4164014—4531
56449—4 55591639—41
651483— 62312333031—
2. 12.
123456 123456
1 — 51 21 21 24 59 1 — 53 9 51 5 5
2 43 — 6 10 9 15 2 29 — 31 43 5 24
3 5413—332135 3 5855— 5 3119
4 163715—5543 4 1739 5 —28 9
5 19122660—30 5 5 5 4619—19
6 3 44 42 46 30 — 6 40 12 36 5 37 —
3. 13.
123456 123456
1 — 41 60 39 46 10 1 — 19 15 21 17 13
2 31 — 59 16 1 51 2 15 — 12 10 22 10
3 2951—144250 3 1718—253010
4 321252—1626 4 101537—4212
5 16391560—57 5 13431310—27
6 1530384736— 6 2135451010—
198
5. 15.
123456 123456
1 —48 4 46 0 0 1 —4616261954
2 24 — 26 38 0 19 2 38 — 1 5 44 10
35350—02614 3498—281630
4 1234 0 —23 4 4 113210—5038
5 0 0 4114—14 5 14 7 2155—25
6 35 7 31 0 32 — 6 0 39 37 41 25 —
6. 16.
123456 123456
1 — 20 28 12 39 32 1 — 2 8 11 2 6
2 21—15 9 1727 2 1213—2025 5
3 30 25 — 45 29 47 3 6 3 — 3 3 7
475240—151 4363—58
56046115—34 5 4 2 2 7—2
6 1145142130— 6 163040 5 5 —
7. 17.
123456 123456
1 — 19 40 30 15 9 1 — 15 20 26 32 18
2 56 — 14 57 12 8 2 20 — 17 15 27 15
3 42 4 —283324 3 2223—303515
4 1 12 5 —2116 4 152042—4517
5 21163852—59 5 18481815—32
6 51 1 17 22 29 — 6 26 41 50 15 15 —
199
8. 18.
123456 123456
1—401001304080 112168547
2 20—90706070 2 9 8 7 2211 6
3 80 50 — 50 50 90 3 4 15 12 8 7 8
4 50 80 50 — 70 100 4 9 22 10 13 14 6
5 60404090—40 5 1618 5 141617
6 5010408030— 6 8 5 9 161413
9. 19.
123456 123456
1 — 56 26 66 29 64 1 — 25 46 31 50 25
2 48—11151420 2 16—28312913
3 5918—382640 3 2132—432117
4 214220—6048 4 345132—4538
5 24173165—35 5 17211523—17
6 8 49 47 51 35 — 6 45 34 65 50 34 —
10. 20.
123456 123456
1 — 46 65 44 51 15 1 — 20 34 19 34 25
25 36 — 64 21 6 55 2 45 — 50 34 38 29
3 34 56 — 19 47 55 3 36 7 — 18 23 19
4 371757—2131 4 3512 4 —5020
5 21442065—62 5 43506025—32
6 2035435241— 6 4556786050—
200
21
4 — .4
1.
( ’ 3 .4
C$ $$ n . ? -
= $$: 1, 2 3- . K
$$ = $. 48:
+ 48
>" ,,$ ++? +"
@
'
12…
n W
' 1 a
1
a
2
… a
n
Wa
i
' 2 b
1
b
2
… b
n
Wb
i
' 3 c
1
c
2
… c
n
Wc
i
;$ $$ n
, $ -
$$, < $$
$ ".
A =! ,
:
k
= {i
1
, i
2
, …, i
k
} — k ;
k + 1
= {
k
, i
k + 1
} — k + 1 ;
A(
k
), B(
k
) C(
k
) — $$ -
k
", -
.
@
k + 1
= $
:
A(
k + 1
) = A(
k
) + a
k + 1;
B(
k + 1
) = max(A (
k + 1
), B(
k
)) + b
k + 1
; (21.1)
C(
k + 1
) = max (B(
k + 1
),C (
k
)) + c
k + 1.
Ak
= A(
k
) + Wa
i
+ min (b
i
+ c
i
), i p
k
(
i
k
);
Bk
= B(
k
) + Wb
i
+ min c
i
, i
k
; (21.2)
Ck
= C(
k
) + Wc
i
, i
k.
'
Ak
! $$ !< -
, # " -