. :
max{F(x) = CT x| Ax≤B, xi≥0, i =1,n} (1)
min{F(y) = BT y| AT y≥C, yj ≥0, j = 1,m}. (2)
(1) , (2) . . . , B C , A , . F(x) F(y). (1) (2) , .. (2), (1). ( ) : (1) (2) , , , .. max F(x) = min F(y).
, , :
:
1. xi , i- .
2. xi , i- .
3. , .
- . , , , .
.
b1,b2,...,bm, n . j- i- aij, i- ci (i = 1, n; j = 1,m). x*i, F(x) = ∑cixi, .
max{F(x)=∑cixi|∑ajixi≤bj, j=1,m; xi≥0, i=1,n} (3)
, . :
max{F(x)=∑cixi|∑ajixi=bj, j=1,m; xi≥0}.
|
|
. , :
) , F;
) , F;
) ;
) ;
) , .
, , , . , , . , . . , .
, . bj, . y*j (j = 1,m) , . , .
min{F(y)=∑bjyj|∑aijyj≥ci, i=1,n; yj0, j=1,m} (4)
( 3) ( 4), . , , .. max F(x) = min F(y).
1. , :
F(x) = 3x1 + 2x2 (min);
x1 + x2 ≤ 5
2x1 - x2 ≤ 3
x1 + 0.5x2 ≥2
x1,2 ≥ 0
(2). , ≥. (-1),
3 , .
ATy≤C :
- y1 - 2y2 + y3 ≤ 3
- y1 + y2 + 0.5y3 ≤ 2
y1≥0, y2≥0, y3≥0.
- (. 1 2).
1
x1 | x2 | ||
x3 | |||
x4 | -1 | ||
x5 | -2 | -1 | 0.5 |
F |
2
y1 | y2 | y3 | ||
y4 | -1 | -2 | ||
y5 | -1 | 0.5 | ||
F | -2 |
F(x) - . 3 4.
F(x), - . 5 6.
|
|
: , , .
:
; , .
.
:
, : ; , . . , . ; .
( ):
, . , , , :
, , .
:
:
.
, , .
. , , , ( ) . , .. . , .
18) () . , . , -. , , ‑ , .
() , . , , . , , .
, . :
- ;
- ;
- - ;
- ..
, , . . , , . , , , , . . . .
|
|
, . .
19) .
1 : . , .
- | . |
.
, = .
. |