,
R(x)=R(x1,x2,xn)=Enj=1cjxj (1)
Eaijxj<bi i=1,m (2)
Xj=>0, i=1,n (3)
xj-, i=1,p, p<=n (4)
(4) p=n->
p<n ->
, .
(4) (1-3) . , - (1-4), - (1-3).
:
1) 2,3 ,
2)
3) (
R(x)=R(x1,x2)=21x1+11x2->max (5)
7x1+4x2<=13 (6)
X1=>0, x2=>0 (7)
X1,x2- (8)
(5-7) .
, .
TO(0,0)=R0=0
TA(0,3(1/4))=R
TB(13/7,0),Rb=
Ra=21*0+11*3(1/4)=35,75
Rb=21*13/7+11*0=139
(1-3) .
(5-7) (1*,2*)=(13/7,0)
R(x1*,x2*)=39
1* 2 , , , 1 1.
1*=1
2*=0
R(x1*,x2*)=21*1+11*0=21
(5-8) .
R(x) .
(0,0)=R=0
(1,0)=21
(0,1)=11
(0,2)=22
(0,3)=33
(1,1)=32
(1-8) (0,3).
, , .
, n m.
2 :
1)
2)
.
(4) (1-3). , , (2-3) , , . . . .
( ).
|
|
, Rx .
n.
()
( ) . , . .
.
. . , .
, , , .
, .
.
Ui, Pi, I Pi+1(i=1,n). ,
P2=T(P1,U1)...
P3=T(P2,U2)
(1)
Pn=T(Pn-1, Un-1)
Pn+1=T(Pn,Un)
. , U1,U2Un F(P1,P2Pn,U1,U2Un)=G(P1,U1,U2Un).
P1=const
F(P1,P2Pn,U1,U2Un)=G(P1,U1,U2Un).- (2)
(2) 1, .
n , U1,U2,Un. :
) G , . ( ).
) , .
, G P1, gi, 1 n, , .
g1(P1,U1)+g2(P2,U2)+gn(Pn,Un) , .
.
P1 n, 1 n, .
, .
|
|
Fn(P1)=max[g1(P1,U1)+f(T(P1,U1))]
fn(p2) n P1.
Fn-1(T(P1U1)) n-1 . fn, fn-1.
. .
.
g.
:
1) , .
, , :
1)
2) ..
, .
.
u1*, , un*
.
F2(Pn)=max gn(Pn, Un)
F2(Pn-1)=max [gn(Pn-1, Un-1)+f1(T(Pn-1,Un-1))]
Fn(P1)=max[g1(P1,U1)+fn-1(T(P2,U2))]
.
, , , . .
:
N , n .
.
.
r1(qi-1,qn)
i-1 i- .
1 n .
RN=sum ri(qi-1,qn)->max
()
, .
N , 1,2,3 n-1 .
n-1 3 , .
q1N=3
q2N=1
q3N=3
9 , 3 .
n-1 .
3 1,2,3. 1 N-2 .
q1N-2=1
q2N-2=1
q3N-2=2
N-2. , N*n2
.
N=20
n=3
M=20*32=180
:
( )
1 6 . .
2 2 | 1,2,5,6 1,2,5,6 1,2,3,5,6 1,2,4,5 | 4 4 4 4 | 1,2,3,4,5,6 1,2,3,4,6 1,3,4,5,6 1,3,4,6 |