.


:




:

































 

 

 

 





, , . . , , , , , . , , , .


(2.11)
(2.12)
(2.13)


. (2.12), (2.13) . . . , (2.11) (2.13) .
. , .

. . . N . (2.11) F , , ( ).
:


(2.14)
. (2.15)


(2.14) ( (2.15)) ., F . =( . :


(2.16)


. .


=( .
.

1. .

2. =( .

3. .

4. , ( ). .

5. .


2.3.

( ) :

1) ;

2) ;

:
, .
, , , , , - , .

,
. (. , :

,


).


, .



( .

.
, ( ) , 1. , , ) . . -, , . , - , - . -, . .


) , (2.17)
(2.18)
, (2.19)

. - :


) (2.20)
( (2.21)
, (2.22)


(2.20) - (2.22) . Ÿ :


).


(2.18) , .


.


) (2.23)


- (2.20) - (2.22) , (2.17)-(2.19).
, , - ,
).
.
, , n- .

 

( )

, , . , :

1. (, );

2. , ;

3. ;

4. , . .

:

, m ( i). , i=1,2,..,m.

, i - , bi . , n , ( j, j=1,2,,n). i - j - aij. -, m×n aij .

2.1

    n
 
 
m

 

, , cj j - . j - , , xj.

, , :

X = (x1, x2, , xn), :

( (2.24)
(2.25)

.

i , i - , bi . , j - , xi >0, , xi =0.

.. .

 

 

2.5.

. m n , . j ( ) i, ij. , , .. k kij.
, , , ai , i, bj >j. . , , , :

1. , , . "" n +1 0 i.

2. , . , m+1 .


:


(2.34)

,
xij , i j, ij ( i j).

:

. 800, 900 600 . . , 300, 600, 650 750 . . 1 . :

 

 


2.2

 

  1 2 3 4
1        
2        
3        


( , ), .
, 800+900+600=2300 300+600+650+750=2300. :
- , i j .



 


. . , - , , .
, - . :
.


2.3

  1 2 3 4 5 >i
1            
2            
3            
4            
bj            


("- " ). . 1 18 . 48, 1, 18 (1,1). 1 , 1 30 . 2 (27 ), 27 (1,2); 3 1 3. 3 39 . 30 2, , 9 3. 18 3 12 4; 6 5, 20 4 . ; , . , , -. , , . :


2.4

  1 2 3 4 5 i
1            
2            
3            
4            
bj            


, , ij.
- - , Ai Bj, , . , Bj. - . , , , 2.4.
, Cij Cik Ai Bj Bk . , , , . , , 2: C21 = C24, b1 b4, 4 (2,1).


2.5

  1 2 3 4 5 i
1            
2            
3            
4            
bj            


. , Bi Aj Cji.
, , . , F0 =1039, F0 =723.

, , . m+n -1. , , m + n - 1.

. . , , 4
m+n-1 =4+5-1=8,
7, 3 2 0., (3,5).
- Cij, , .
.
, - .,,18 (1,1) (2,1) 18 (2,3) (1,3). . ( 1039) ( 913) , 126 . , 18 :


2.6

  1 2 3 4 5 i
1            
2            
3            
4            
bj            

 


.

, , , 90.


:

1)

 

 

2)

 

 

3)

 


, , (). + ,

, , , . .

- , , , , , ., : , - . , , . : . ., , , ` +`, ` -`.

γ. γ. k kγ. , , . , , kγ. , , , . , , , .
, , , , .

, , , -: () , .

m+n-1.

, . , , , . , , , .

k, , , ( , ).
; .
, , : . , .


.


, .





.


Ai Bj C ij; . xij, .
. Ai ( ) - αi;

Bj ( ) βj. (). ai +bj = č ij (i=1..m; j=1..n) č ij Ai Bj.

, αi βj ; , - .

, (αi βj) .
(αi βj) č ij Cij. . , xij ( m + n -1). xij>0. (αi βj) , :


č ijij= ij, xij>0.
( xij =0), , .
, . : xij>0,
αij= č ij= ij, xij=0,
αij= č ij ij,, . , , . :
č ij= ij ( ) (2.35)
č ij ij ( ) (2.36)

, (αi βj) Ai Bj (i=1,...,m;j=1,...,n). : .
, - .

, , (2.35). , ; , ., . :

(αi βj) (2.35), :

γi,j=i,j - č i,j.
, : .
() .
(, ). m+n-1 , m - , n .

(αi βj), , :


αij= ij (2.37)
(2.37) m+n-1, m+n.

, (, ).

m+n-1

(2.37) αi, βj,

, č i,jij .

2.7

    1   2   3   4   5   αi
  1 č= 7 č= 6     č= 6 α1= 0
  2   č= 5 č= 4 č= 5   α2= -1
  3 č= 8   č= 6 č= 7   α3= 1
  4   č= 6 č= 5   č= 6 α4= 0
  βj   β1= 7   β2= 6   β3= 5   β4= 6   β5= 6  

 


α4 =0,=> β4 =6, α4 + β4 = 44 =6,

=>
α1 =0, α1 + β4 = 14 =6,

=>
β3 =5, α1 + β3 = 13 =5,

=>
β1 =7, α4 + β1 = 41 =7,

=>
α2 =-1, α2 + β1 = 21 =6,

=>
β5 =6, α2 + β5 = 25 =5,

=>
α3 =1, α3 + β5 = 35 =7,

=>
β2 =6, α3 + β2 = 25 =7.


, č ij ij, , . ( ), , . .
6 č ij ij, . , č ij- ij . ( 1),, ,, (4,2):
2.8

 
           
6 + 7     5 - -1
        7 +  
7 - 5 +        
           

 


14, , , -. 14 - +.
αi βj .
, :

1) , m+n-1 ( ).

2) (αi βj) , . , , .

3) č i,jij . , , .

4) , , ( ).

5) , , , , .


2 . : F0=723,F1=709,F2=Fmin=703.
, , Fmin = 703.

 





:


: 2017-02-28; !; : 437 |


:

:

, .
==> ...

790 - | 761 -


© 2015-2024 lektsii.org - -

: 0.11 .