: , .
: 150 90 . 1, 2, 3 60, 70, 110 . 1 1, 2, 3 60, 10, 40 . . 1 , 1, 2, 3 120, 20, 80 . . 1 . , .
, .
- :
Xij- i- j- .
j | 1 | 2 | 3 | . | |||
Ai | |||||||
1 | X11 | X12 | X13 | ||||
2 | X21 | X22 | X23 | ||||
. |
Xij.
11 + 12 + 13 = 150
21 + 22 + 23 = 90
(1) 11 + 21 = 60
12 + 22 = 70
13 + 23 = 110
:
(2) Z = 60X11 + 10X12 + 40X13 + 120 X21 + 20X22 + 80X23 → min
, , (1)
11 12 13
= 21 22 23 ,
(2) .
:
Ui | j | 1 | 2 | 3 | . | |||
Ai | ||||||||
U1= | 1 | |||||||
U2= | 2 | |||||||
. | ||||||||
Vj | V1= | V2= | V3= |
. . . (1, 2). 12 = 10. . 12 = min (150, 70) = 70. (2, 1) ( ), .. . . (1, 3), 13 = 40. . 13 = min (150 70, 110) = 80. (1, 1) ( ), .. ( ) . . (2, 3), 23 = 80. . 23 = min (110 80, 90) = 30. (2, 1) 60.
|
|
( ).
.. . , .. . : r = m + n 1, m , n .
r = 2 + 3 1 =4, = 4.
1 = 0 70 80
60 0 30
Z1 = 70*10 + 80*40 + 60*120 + 30*80 = 13500 .
, . . Ui, Vj. Ui + Vj = i j, i j .
U1 + V2 = 10 .
U1 + V3 = 40 . U1 = 0. V2 = 10,
U2 + V1 = 120 V3 = 40, U2 = 40, V1 = 80.
U2 + V3 = 80
Ui | j | 1 | 2 | 3 | . | |||
Ai | ||||||||
U1=0 | 1 | |||||||
U2=40 | 2 | |||||||
. | ||||||||
Vj | V1=80 | V2=10 | V3=40 |
, : Di j = i j (Ui + Vj), i j .
D11 = 60 (0 + 80) = - 20 ≤ 0, D22 = 20 (40 + 10) = - 30 ≤ 0
. , . ( ). (1, 1) ( ). .
, , , .
, , .
, + −, , +, −.
70 + | 120 ‒ | |||
+ * | 20 ‒ | |||
60 ‒ | 50 + | |||
* | 120 | |||
60 | ||||
(1, 1) :
+ −
* 80
λ = min (60, 80) = 60.
− 60 30 +
. , .
Ui | 1 | 2 | 3 | . | ||||
U1= | 1 | |||||||
U2= | 2 | |||||||
. | ||||||||
Vj | V1= | V2= | V3= |
, .. .
|
|
1 = 60 70 20
0 0 90
Z1 = 60*60 + 70*10 + 20*40 + 90*80 = 12300 .
, . .
Ui + Vj = i j, i j .
U1 + V1 = 60 .
U1 + V2 = 10 . U1 = 0. V1 = 60,
U1 + V3 = 40 V2 = 10, V3 = 40, U2 = 40,.
U2 + V3 = 80
Ui | 1 | 2 | 3 | . | ||||
U1=0 | 1 | |||||||
U2=40 | 2 | |||||||
. | ||||||||
Vj | V1=60 | V2=10 | V3=40 |
, : Di j = i j (Ui + Vj), i j .
D21 = 120 (40 + 60) = 20 ≥ 0, D22 = 20 (40 + 10) = - 30 ≤ 0
. , . ( ). (2, 2) ( ).
(2, 2) :
− +
70 20
λ = min (70, 90) = 70.
+ * 90 −
. , .
Ui | 1 | 2 | 3 | . | ||||
U1=0 | 1 | |||||||
U2=40 | 2 | |||||||
. | ||||||||
Vj | V1=60 | V2= - 20 | V3=40 |
, .. .
1 = 60 0 90
0 70 20
Z1 = 60*60 + 90*40 + 70*20 + 20*80 = 10200 .
, . .
Ui + Vj = i j, i j .
U1 + V1 = 60 .
U1 + V3 = 40 . U1 = 0. V1 = 60,
U2 + V2 = 20 V2 = - 20, V3 = 40, U2 = 40,.
U2 + V3 = 80
, : Di j = i j (Ui + Vj), i j .
D21 = 120 (40 + 60) = 20 ≥ 0, D12 = 10 (0 + (- 20)) = 30 ≥ 0.
. . , .
= 60 0 90
0 70 20
Z = 60*60 + 90*40 + 70*20 + 20*80 = 10200 .
. 10200 ., : 1- 60 , 3 90 ; 2- 70 , 3 20 . 1, 2 3 .