: , , . , , , . :
1. .
2. , , , . 1 i. fi , i- .
3. j i-
. , .
- , 0 1 . i j, :
(27)
dj- j- .
(28)
(29)
:
yi = 1, i. yi = 0, xij = 0 j, . y = (y1, , ym) , (30)-(33) . 2 (30)-(33), :
(34)-(36) , (35) (36), 2 :
(37) 2. 2 Y. (30)-(33) (34)-(36), , y y0. . , , :
(40)
, y ≠ 0 , I . (30)-(33) :
(41)
(42)
ij ≥ 0, (42) , . - , (42) , , xij = 1 ij , ..
(43)
(44)
j. , , :
(45)
:
(46)
(47)
(45) (34), , , . , , (34), uij , (46)-(47). :
|
|
(48)
(49)
d0 - , z0 - , 2.
(50)
; - , ,
(51)
2, 2, , .
.
, /3/ .293, (30)-(33) () , fi = 7 i,
(52)
1. 2 . y0 = (0, 1, 0, 0) z = -∞. (30)-(33), (34)-(36),
(53)
2 :
(54)
(54) y0 = (1, 0, 1, 0), z0 = 18. y0 (30)-(32), (34)-(36).
, (55)
(50) , d0 = 14, d0 ≠ , , , 2, (34)-(36):
(56)
2 (56) y0 = (1, 0, 0, 0), z0 = 21.
y0 (30)-(32) (34)-(36). :
(57)
(50) y0 z0 , , 2, (57) (34)-(36):
(58)
2 (58) y0 = (0, 0, 1, 0), z0 = 25.
y0 (30)-(32) (34)-(36), :
(59)
(50) , 2, (58) (34)-(36) (59):
(60)
(60) y0 = (1, 0, 0, 1), z0 = 26.
y0 (30)-(32) (34)-(36), :
(61)
, , y0 = (1, 0, 0, 1) .
, . , , .
a
1.0 0.0 0.0 0.0
0.0 0.0 0.0 0.0
0.0 0.0 0.0 0.0
0.0 1.0 1.0 1.0
= 26.000
|
|
1.0 0.0 0.0 1.0
: , , . , , , . :
4. .
5. , , , . 1 i. fi , i- .
6. j i-
f = (30 n, 1 + n, 6, 7);
.
1 J.F. Benders Partitioning Procedures for solving mixed variables programming problems. Numerische Mathematik, 4, 1962, p.p. 238-252.
2 .. . .:, , 1975, -432.