1 . . , .
2 . (, ).
3 . . (i,j) , .
4 . 2-4.
5 . .
1 . (1,3) () 25 , 3 (. 3.1.6). .
3.1.6
1 | 2 | 3 | 4 | 5 | ||
1 | 25 | 30 (25) | ||||
2 | ||||||
3 | ||||||
25 (25) |
(2,1), (3,5) () . (3,5) , 20 (. 3.1.7) . .
3.1.7
1 | 2 | 3 | 4 | 5 | ||
1 | 1 | 4 | 30 (25) | |||
2 | ||||||
3 | 50 (20) | |||||
25 (25) | 20 (20) |
(2,1), 15 (. 3.1.8), . .
3.1.8
1 | 2 | 3 | 4 | 5 | ||
1 | 25 | 4 | 30 (25) | |||
2 | 20 (15) | |||||
3 | 50 (20) | |||||
15 (15) | 25 (25) | 20 (20) |
(1,4) 5 (. 3.1.9), . .
3.1.9
1 | 2 | 3 | 4 | 5 | ||
1 | 4 | 25 | 4 | 30 (30) | ||
2 | 20 (15) | |||||
3 | 50 (20) | |||||
15 (15) | 25 (25) | 30 (5) | 20 (20) |
|
|
(3,2) () 10 (. 3.1.10), . .
3.1.10
1 | 2 | 3 | 4 | 5 | ||
1 | 4 | 5 | 25 | 4 | 30 (30) | |
2 | 20 (15) | |||||
3 | 50 (30) | |||||
15 (15) | 10 (10) | 25 (25) | 30 (5) | 20 (20) |
(. 3.1.11) , .
3.1.11
1 | 2 | 3 | 4 | 5 | ||
1 | 30 (30) | |||||
2 | 20 (20) | |||||
3 | 50 (50) | |||||
15 (15) | 10 (10) | 25 (25) | 30 (30) | 20 (20) |
7, (m + n 1).
100 . :
Z = 25*1 + 5*3 + 15*2 + 5*7 + 10*4 + 20*5 + 20*2 = 285 ..
.
1 . ( ).
2 . . , . , . . .
3 . .
4 . , .
5 . . (i.j) , .
6 . 15.
7 . , .
1. (. 3.1.12).
3.1.12
1 | 2 | 3 | 4 | 5 | |||
1 | 3 1 = 2 | ||||||
2 | 4 2 = 2 | ||||||
3 | 2 2 = 0 | ||||||
3 2 = 1 | 5 4 = 1 | 2 1 = 1 | 5 3 = 2 | 4 2 = 2 | |||
|
|
, . .
: 2 + 2 + 0 = 4
: 1 + 1 + 1 + 2 + 2 = 7
. , (3,5).
3.1.13
1 | 2 | 3 | 4 | 5 | ||||
1 | 4 | 3 1 = 2 | 3 1 = 2 | |||||
2 | 4 2 = 2 | 4 2 = 2 | ||||||
3 | 2 2 = 0 | 3 2 = 1 | 50 (20) | |||||
3 2 = 1 | 5 4 = 1 | 2 1 = 1 | 5 3 = 2 | 4 2 = 2 | ||||
20 (20) |
, . (. 3.1.13).
, .
: 2 + 2 + 1 = 5
: 1 + 1 + 1 + 2 = 5
, . , (. 3.1.14). .
3.1.14
1 | 2 | 3 | 4 | 5 | ||||
1 | 4 | 4 | 3 1 = 2 | 3 1 = 2 | 30 (30) | |||
2 | 4 2 = 2 | 4 2 = 2 | ||||||
3 | 2 2 = 0 | 3 2 = 1 | 50 (20) | |||||
3 2 = 1 | 5 4 = 1 | 2 1 = 1 | 5 3 = 2 | 4 2 = 2 | ||||
3 2 = 1 | 6 4 = 2 | 4 2 = 2 | 7 5 = 2 | |||||
30 (30) | 20 (20) |
: 2 + 1 = 3
: 1 + 2 + 2 + 2 = 7
3.1.15
1 | 2 | 3 | 4 | 5 | |||||
1 | 4 | 1 | 4 | 3 1 = 2 | 3 1 = 2 | 30 (30) | |||
2 | 4 2 = 2 | 4 2 = 2 | 6 2 = 4 | ||||||
3 | 2 2 = 0 | 3 2 = 1 | 4 3 = 1 | 50 (45) | |||||
3 2 = 1 | 5 4 = 1 | 2 1 = 1 | 5 3 = 2 | 4 2 = 2 | |||||
3 2 = 1 | 6 4 = 2 | 4 2 = 2 | 7 5 = 2 | ||||||
3 2 = 1 | 6 4 = 2 | ||||||||
25 (25) | 30 (30) | 20 (20) |
, , .
, (. 3.1.15), . .
. (2,1) , (. 3.1.16).
|
|
3.1.16
1 | 2 | 3 | 4 | 5 | |||||
1 | 4 | 4 | 3 1 = 2 | 3 1 = 2 | 30 (30) | ||||
2 | 4 2 = 2 | 4 2 = 2 | 6 2 = 4 | 20 (15) | |||||
3 | 2 2 = 0 | 3 2 = 1 | 4 3 = 1 | 50 (45) | |||||
3 2 = 1 | 5 4 = 1 | 2 1 = 1 | 5 3 = 2 | 4 2 = 2 | |||||
3 2 = 1 | 6 4 = 2 | 4 2 = 2 | 7 5 = 2 | ||||||
3 2 = 1 | 6 4 = 2 | ||||||||
15 (15) | 25 (25) | 30 (30) | 20 (20) |
, .
3.1.17
1 | 2 | 3 | 4 | 5 | |||||
1 | 3 1 = 2 | 3 1 = 2 | 30 (30) | ||||||
2 | 4 2 = 2 | 4 2 = 2 | 6 2 = 4 | 20 (20) | |||||
3 | 2 2 = 0 | 3 2 = 1 | 4 3 = 1 | 50 (50) | |||||
3 2 = 1 | 5 4 = 1 | 2 1 = 1 | 5 3 = 2 | 4 2 = 2 | |||||
3 2 = 1 | 6 4 = 2 | 4 2 = 2 | 7 5 = 2 | ||||||
3 2 = 1 | 6 4 = 2 | ||||||||
15 (15) | 10 (10) | 25 (25) | 30 (30) | 20 (20) |
, () (. 3.1.17).
100 :
Z = 30*3 + 15*2 + 5*6 + 5*4 + 25*2 + 20*2 = 260 ..
- , , .
, .
, , , ( m + n 1). .
.
1 . .
2 . , , -, , . - - ( ). ( !) .
3 . () (+), (-) (+).
4 . , , , .
|
|
5 . , 24.
6 . , , , , (-).
7 . : , (+), ; , (-), . ( ), , , (-), (). ( ). , , , , .
8 . 6 7 , m + n 1. .
9 . 28.
10 . , 4 .
1, , (. 3.1.18).
3.1.18
1 | 2 | 3 | 4 | 5 | ||
1 | ||||||
2 | ||||||
3 | ||||||
(1,1) , , (. 3.1.19). (1,1). , . , ..
, . (1,1) (2,1). , 2. , . (2,4). (1,4). , (1,1). (+), (-) (+).
3.1.19
1 | 2 | 3 | 4 | 5 | ||
1 | (+) | 5 (-) | ||||
2 | 15 (-) | 5 (+) | ||||
3 | ||||||
:
D1,1 = 4 2 + 7 3 = 6 > 0
, (1,1), .
(1,2). (. 3.1.20) .
3.1.20
1 | 2 | 3 | 4 | 5 | ||
1 | 5 (+) | 5 (-) | ||||
2 | ||||||
3 | 10 (-) | 20 (+) | ||||
:
D1,2 = 5 - 4 + 5 3 = 3 > 0
(1,5). (. 3.1.21). .
:
|
|
D1,5 = 4 2 + 5 3 = 4 > 0
3.1.21
1 | 2 | 3 | 4 | 5 | ||
( 1) | 5 (-) | (+) | ||||
( 2) | ||||||
( 3) | 20 (+) | 20 (-) | ||||
(2,2) (. 3.1.22) .
3.1.22
1 | 2 | 3 | 4 | 5 | ||
1 | ||||||
2 | 6 (+) | 5 (-) | ||||
3 | 10 (-) | 20 (+) | ||||
:
D2,2 = 6 - 4 + 5 7 = 0
, 100 .
(2,3). (. 3.1.23) .
3.1.23
1 | 2 | 3 | 4 | 5 | ||
1 | 1 25 (-) | 3 5 (+) | ||||
2 | 4 (+) | 5 (-) | ||||
3 | ||||||
:
D2,3 = 4 7 + 3 1 = 1 < 0
, .
(-) 5. (2,3) 2,3 = 5 (.3.1.24) .
3.1.24
1 | 2 | 3 | 4 | 5 | ||
1 | 1 25 - 5 | 5 + 5 | ||||
2 | + 5 | 5 - 5 | ||||
3 | ||||||
(. 3.1.25).
3.1.25
1 | 2 | 3 | 4 | 5 | ||
1 | ||||||
2 | ||||||
3 | ||||||
100 :
Z = 20 * 1 + 10 * 3 + 15 * 2 + 5 * 4 + 10 * 4 + 20 * 5 + 20 * 2 = 280 ..
(2,5). (. 3.1.26) .
3.1.26
1 | 2 | 3 | 4 | 5 | ||
1 | 1 20 (+) | 3 10 (-) | ||||
2 | 4 5(-) | 5 (+) | ||||
3 | 5 20 (+) | 20 (-) | ||||
:
D2,5 = 5 2 + 5 3 + 1 4 = 2 > 0
(3,1), (. 3.1.27) .
3.1.27
1 | 2 | 3 | 4 | 5 | ||
1 | 1 20 (-) | 3 10 (+) | ||||
2 | 2 15(-) | 5(+) | ||||
3 | (+) | 20 (-) | ||||
:
D3,1 = 3 - 5 + 3 - 1 + 4 2 = 2 > 0
(3,3). (. 3.1.28) .
3.1.28
1 | 2 | 3 | 4 | 5 | ||
1 | 1 20 (-) | 3 10 (+) | ||||
2 | ||||||
3 | 2 (+) | 20 (-) | ||||
:
D3,3 = 2 5 + 3 1 = - 1 < 0
20. (3,3) , 20, (.3.1.29). (. 3.1.30).
3.1.29
1 | 2 | 3 | 4 | 5 | ||
1 | 1 20 - 20 | 3 10 + 20 | ||||
2 | ||||||
3 | 2 + 20 | 20 - 20 | ||||
7 ( ), .
3.1.30
1 | 2 | 3 | 4 | 5 | ||
1 | ||||||
2 | ||||||
3 | ||||||
100 260 ..:
Z = 30*3 + 15*2 + 5*4 + 10*4 + 20*2 + 20*2 = 260 ..
, . 3.1.30, , . 100 260 ..
.
1 . Ui Vj .
2 . . (i, j), ( ), Ui + Vj = Ci,j. , , m + n 1. , U1 = 0.
3 . (i, j), , :
Si,j = Ui + Vj Ci,j
4 . Si,j £ 0 , , . - (i, j) Si,j > 0 (, , . . ), .
5 . Si,j . q.
6 . , . (+) (-) ( , ).
7 . q, , -.
8 . q, ( +) ( -).
9 . , ( , ).
10 . Ui Vj 3 10.
11 . , Si,j £ 0.
1, , (. 3.1.31).
Ui Vj.
3.1.31
1 V1 | 2 V2 | 3 V3 | 4 V4 | 5 V5 | ||
1 U1 | ||||||
2 U2 | ||||||
3 U3 | ||||||
Ui + Vj = Ci,j:
U1 + V3 = 1,
U1 + V4 = 3,
U2 + V1 = 2,
U2 + V4 = 7,
U3 + V2 = 4,
U3 + V4 = 5,
U3 + V5 = 2.
U1 = 0, . (.3.1.32).
3.1.32
1 V1 = 2 | 2 V2 = 2 | 3 V3 = 1 | 4 V4 = 3 | 5 V5 = 0 | |
1 U1 = 0 | |||||
2 U2 = 4 | |||||
3 U3 = 2 |
, Si,j . 3.1.33.
3.1.33
Si,j = Ui + Vj Ci,j | |
(1,1) | S1,1 = U1 + V1 C1,1 = 0 2 4 = 6 |
(1,2) | S1,2 = U1 + V2 C1,2 = 0 + 2 5 = 3 |
(1,5) | S1,5 = U1 + V5 C1,5 = 0 + 0 4 = 4 |
(2,2) | S2,2 = U2 + V2 C2,2 = 4 + 2 6 = 0 |
(2,3) | S2,3 = U2 + V3 C2,3 = 4 + 1 4 = 1 |
(2,5) | S2,5 = U2 + V5 C2,5 = 4 + 0 5 = 1 |
(3,1) | S3,1 = U3 + V1 C3,1 = 2 2 3 = 3 |
(3,3) | S3,3 = U3 + V3 C3,3 = 2 + 1 2 = 1 |
Si,j, 1, (2,3) (3,3). 4 2 . q (3,3). , (3,3) , (2,3), .
, (. 3.1.34). : (3,3) (+), , , (-) (+). , (+), q, , (-), q.
3.1.34
1 | 2 | 3 | 4 | 5 | |
1 | 1 25 - q(-) | 5 + q(+) | |||
2 | |||||
3 | + q(+) | 20 - q(-) |
q. , (-):
q = min (25, 20) = 20.
(. 3.1.35). (3,4) , ( ) .
3.1.35
1 | 2 | 3 | 4 | 5 | |
1 | |||||
2 | |||||
3 |
100 .
Z = 5*1 + 25*3 + 15*2 + 5*7 + 10*4 + 20*2 + 20*2 = 265 ..
20 .. (285 265) .
Ui Vj , U1 = 0.
U1 + V3 = 1,
U1 + V4 = 3,
U2 + V1 = 2,
U2 + V4 = 7,
U3 + V2 = 4,
U3 + V3 = 2,
U3 + V5 = 2.
. (.3.1.36).
3.1.36
1 V1 = 2 | 2 V2 = 3 | 3 V3 = 1 | 4 V4 = 3 | 5 V5 = 1 | |
1 U1 = 0 | |||||
2 U2 = 4 | |||||
3 U3 = 1 |
. Si,j . . 3.1.37.
3.1.37
Si,j = Ui + Vj Ci,j | |
(1,1) | S1,1 = U1 + V1 C1,1 = 0 2 4 = 6 |
(1,2) | S1,2 = U1 + V2 C1,2 = 0 + 3 5 = 2 |
(1,5) | S1,5 = U1 + V5 C1,5 = 0 + 1 4 = 3 |
(2,2) | S2,2 = U2 + V2 C2,2 = 4 + 3 6 = 1 |
(2,3) | S2,3 = U2 + V3 C2,3 = 4 + 1 4 = 1 |
(2,5) | S2,5 = U2 + V5 C2,5 = 4 + 1 5 = 0 |
(3,1) | S3,1 = U3 + V1 C3,1 = 1 2 3 = 4 |
(3,4) | S3,4 = U3 + V4 C3,4 = 1 + 3 5 = 1 |
Si,j, 1, (2,2) (2,3). 6 4 . q (2,3), , (2,2), .
, (. 3.1.38). : (2,3) (+), , , (-) (+). , (+), q, , (-), q.
3.1.38
1 | 2 | 3 | 4 | 5 | |
1 | 1 5 - q(-) | 25 + q(+) | |||
2 | + q(+) | 5 - q(-) | |||
3 |
q. , (-):
q = min (5, 5) = 5.
(. 3.1.39). (1,3) (2,4) .
(1,3) (2,4) . (2,4), (7 1 (1,3)).
(3,4).
3.1.39
1 | 2 | 3 | 4 | 5 | |
1 | |||||
2 | |||||
3 |
.
Z = 30*3 + 15*2 + 5*4 + 10*4 + 20*2 +20*2 = 260 ..
5 .. (265 260).
, .
U1 = 0.
U1 + V3 = 1,
U1 + V4 = 3,
U2 + V1 = 2,
U2 + V3 = 4,
U3 + V2 = 4,
U3 + V3 = 2,
U3 + V5 = 2.
(.3.1.40).
3.1.36
1 V1 = 1 | 2 V2 = 3 | 3 V3 = 1 | 4 V4 = 3 | 5 V5 = 1 | |
1 U1 = 0 | |||||
2 U2 = 3 | |||||
3 U3 = 1 |
. Si,j . . 3.1.41.
3.1.41
Si,j = Ui + Vj Ci,j | |
(1,1) | S1,1 = U1 + V1 C1,1 = 0 1 4 = 5 |
(1,2) | S1,2 = U1 + V2 C1,2 = 0 + 3 5 = 2 |
(1,5) | S1,5 = U1 + V5 C15 = 0 + 1 4 = 3 |
(2,2) | S2,2 = U2 + V2 C2,2 = 3 + 3 6 = 0 |
(2,4) | S2,4 = U2 + V4 C2,4 = 3 + 3 7 = 1 |
(2,5) | S2,5 = U2 + V5 C2,5 = 3 + 1 5 = 1 |
(3,1) | S3,1 = U3 + V1 C3,1 = 1 1 3 = 3 |
(3,4) | S3,4 = U3 + V4 C3,4 = 1 + 3 5 = 1 |
Si,j £ 0 , (. 3.1.39) . 100 260 ..
, 100 . 260 ..
3.1.3.
, , . .
:
1. .
2. .
.
1 . .
2 . .
3 . , , .
4 . .
1
S . 1,5 . . 3.1.1, 3.1.42.
. 3.1.1. .
3.1.42
, . | 0,33 | 0,25 | 0,35 | 0,45 | 0,25 | 0,5 | 0,47 | 0,31 |
:
, .;
Q , .
.
. () (5) .