: , m + n ui vj, ui + vj = cij ui + vj cij £ 0 .
ui vj . vj ui.
ui vj ui + vj = cij, . , , u1 = 0, . , ui, vj = cij - ui, vj, ui, = cij - vj.
D ij = ui + vj - cij, . D ij £ 0, . D ij ≥ 0, , .
, ui vj.
bj ai | ui | ||||
- | - | ||||
- | 2 | ||||
- | |||||
vj |
u1 = 0, .
, (1, 1), u1 + v1 = 2. u1 = 0, v1 = 2, . , .
(3, 1): u3 + v1 = 3, v1 = 2, u3 =1.
(3, 3): u3 + v3 = 8, u3 = 1, v3 =7.
(2, 3): u2 + v3 = 5, v3 = 7, u2 = 2.
(2, 2): u2 + v2 = 1, u2 = 2, v2 = 3.
.
:
D 12 = u1 + v2 - c12 = 0 + 3 5 = 2 < 0,
D 13 = u1 + v3 - c13 = 0 + 7 2 = 5 > 0,
D 21 = u2 + v1 - c21 = -2 + 2 4 = 4 < 0,
D 32 = u3 + v2 - c32 = 1 + 3 6 = 2 < 0.
D 13 = 5 > 0, , .
(D ij ≥ 0) , , . , . , .
, D ij ≥ 0, (, ), , , , , . (+), () (+). () , , (+), (). . , .. , .
|
|
.
(1, 3), D 13 = 5 > 0. (+) () .
(-) , 60. , , , . :
:
.
. , .
bj ai | ui | ||||
- | |||||
- | |||||
- | - | ||||
vj | -2 |
D 12 = 7, D 21 = 1 > 0, D 32 = 7, D 33 = 5.
D 12 = 1:
:
, . .
bj ai | ui | ||||
- | - | ||||
- | - | ||||
vj | -2 |
D 11 = 1, D 12 = 7, D 32 = 6, D 33 = 4.
, , .
: .
:
L(X)min = 90×2 + 30×4 + 300×1 + 70×5 + 110×3 = 1280 . .
1610 1280 = 330 . .
. , , (i, j) :
.
, :
.