() . , , . , , . .
, , :
;
;
;
;
;
;
;
.
: , , . , ..
:
;
(, , , );
ij i- j - ;
j j- ;
bi i - ;
j j - .
:
(1)
(2)
(3)
(1) ( );
(2) (constraint) ;
(3) ( );
j (variable).
(1)(3) .
(4)
(5)
(6)
= (x 1, x 2,..., xn), j (2) (3) ( (5) (6) ), .
.
, (1) ( (3) ) () , .
, .
(1)(3)
, (7)(9) (1)(3). ( ) () . , , .
|
|
(7)(9) (Dual Value) .
j = max (), j (1)(3).
:
bi (RHS) .
, * . (Lower Bound) .
, y* . (Upper Bound) .
j .
, x * . .
, * . .
2.
3.
.
, .
2 2002 . , - , , , . , .
, , . 20% , 3 .
, , . , , . , .
:
, , , .
, , , , , , , . , , .
|
|
( .) ,:
, 0,6 . 1 .
( ), , :
- , , , , . , . 1 10, . 9 , 5 .
, 8 1 6 1 . . , 800 . .
- , . 80 . A 0,85 . 1 . , -, . , , : , , . , , .
( .) :
, 2 B . 400 . . , 480 . .
. z 1 , 1 .
: z = 0,932 ., = 0,518 .
1. . .
2. .
3. , 80 . .
2. ( 3)
. 1 . . .
, , :
;
;
;
.
. . , , . , . , , .
|
|
(, , , , ). , ..
.
:
;
;
j j - , ;
ij i - j - ;
j j - ;
bi i - .
:
(1) ( );
(2) , ;
(3) .
. , (2) , 1.
:
;
;
w , j - ;
j j- , ;
ij j - j - ;
bi i - ;
j j - ;
drj , r - j - .
:
(4) ( );
(5) , ;
(6) ;
(7) ;
(8) .
(5) (6) . , . * , , .
, . xkj, j, k. .
:
;
;
w , j - ;
s ;
kj j - , k - ;
ij i - j - ;
bik i - k- ;
j j - ;
k k- ;
drkj , r - j - k- ;
j j - .
:
(9) ( );
(10) , ;
(11) ;
(12) ;
(13) .
|
|
3.
4.
.
, , . 1000 5000 . , , , .
, . , , , , . , , , . , . .
, . 300 , . . , . , . 150 . . , . . , . , , : ( ), ( ) ( ). , . . . , , .
200 , , 300 . 10 ., , , 50 . 100 , . , , , . 30 ., 5 ., 10 .
, , . 100 . , 100 . 20 ., 30 . , . 5 . , . , , . . , 40 .
. 100 . 150 . . 40 . , 10 . . , , 60 . . 30 35 . .
|
|
, , . 100 , , . 15 . , 25 . , , . , 2 . 150 , 50 . . 35 ., 40 .
, , . , . , , , .
: , . , , . , , , . , , , .
: , , . , . , , .
: , , , , - . , . , . , .
: , , . , . 2 . , .
: . , 1 . .
: . , , . .
: , . . .
1. , . ?
2. , , .
3. . .
5.
.
. , . ( ) ( ):
. , , , .
0,12 . 1 . 20 . 1 . , 1 , 5,63 . ( ). , 1 , 15,73 . ( ). ( ) 1900 . , 100 , 250 . , , 8 . 1 , . 2 . 1 , (.. 10 . 1 , ).
73 . , 1900 .
. , .
3.( 4, 5)
, . . , . , .
, , :
;
;
;
;
;
.
:
i i (i = 1,..., n);
bj j (j = 1,..., );
cij i j;
xij , i j.
:
(1) ( );
(2) ;
(3) ;
(4) .
1. . :
(1)(4).
.
)
. bm +1 , .. - , i; i , i.
) .
. n +1 , .. - , j; j , .
3. . (ij), , i j . .
̗ ,
{ } (2)(4) xij = 0, (i,j) Ï .
4. . i j , (1)(4) : xij = vij, vij .
5. . i j wij, (1)(4) : xij £ wij.
6. . , i = + 1,..., k di.
zi = 1, i (i = + 1,..., k) di zi = 0, i . d, i (i = n + 1,..., k) i.
:
(5) ( );
(6) ;
(7) ;
(8) ;
(9) .
xij zi,. (5)(9) .
. , -.
( ) , .
:
4. .
6.
.
. . .
1973 . . : (6 ), (12 ) (12 ). .
: . , . , .
. IPA. , . .
, . , , . , , .
, , . , .
IPA. , , .
. 12 . , , 12 . , , . .
, , , , 12- . . IPA. , , .
, . , , , , . .
, IPA :
, , (52 ). , .
, , , , .
. , , . , . 5 .
:
(3 );
(10 );
D (6 );
(3 ).
F (4 ) D.
, . G 4 .
, :
(8 );
I (6 ).
H ( J, 6 ). I ( , 3 ).
, L . , 16 .
. ( , 16 ) ( N, 2 ). , .
. , , 12 , :
, , .
1. . . , ?
2. . . ?
3. . . ?
4. , , : D , J . . , ?
4. ( 6)
(Critical Path Method ) . , , , ..
. , . , . , .
, .
:
1. ?
2. ?
3. , ?
4. , ?
, , :
;
;
;
;
.
. : .
, :
. : , , , D. , . . . , , . D : . , D , . . (. 1).
. 1
. 1 1,2, 3, 4 , , , D. . 1 . s (start). 4 . f(finish). . , (1, 3)(. . 1). D (3,4). , , . , 3 , .
, :
, , , . 2.
.2
, , , (3, 4) (5, 6). . , . , .
:
, . , { A, D, G } { , , , } , 1 7 (. . 2).
.
, .
, , , . , , . , . , .
, , . . .
i j , , , (i,j) , s (start), f (finish), .
:
t(i,j) (i, j);
ES(i,j) (i,j);
EF(i,j) (i,j);
LS(i,j) (i,j),
LF(i,j) (i,j),
Ei i;
Li i;
R(i,j) (i,j) (, (i,j) );
r(i,j) (i,j) (, (i,j) i j).
(i,j) , :
j ES(i,j) = i;
i LF(i,j) = Lj.
, (i,j) (ES(i,j) EF(i,j)) (LS(i,j) LF(i,j)).
:
(1)
(s,j), s ;
(2)
.. (i,j) ( i) ;
(3)
.. (q, j) ;
(4)
.. ;
(5)
.. , , ;
(6)
.. ( ) ;
(7)
.. (/, q) ;
(8)
.. ;
(9)
.. .
:
1. .
2. R(i,j) = 0, (i,j) ;
R (i,j) > 0, (i,j) .
3. (i,j), , , r(i,j), .
4. (i,j), , , R(i,j), , , .
5.
7.
.
() . (). .
. 3 ( , , ).
.3
:
, A, D G. 12 . 61 . .
. 9 . 80 . . , ( ) ( . .):
PERT/COST .
1. , 9 . , ? ?
2. , 7 . , ?
8.
.
SBPA. SBPA , , .
. . . .
, , ( , . .):
:
1. .
2. , D .
3. . , , F G .
4. H .
5. I , , , .
6. J . ( ) SBPA.
SBPA , . , 25 . . . 25 . . .
, . . 22,5% . . 1500 . . , 10 15 . .
10% . , .
1. , .
2. , . ?
3. , .
4. , .
5. ( 7, 8)
, . , , , , , . , . . , , .
, PERT/COST. PERT/COST , , . ( ). , , , .
PERT/COST :
1. ?
2. ?
3. ?
4.