- , - 1, .
, .
10. . ()
(..).
, .
:
1. ;
2. , ;
3. ( ).
1. , , .. :
F(x) = c1x1 + + cnxn → max
a11x1+a12x2++a1nxn=b1
a21x1+a22x2++a2nxn=b2
am1x1+am2x2++amnxn=bn
.
:
x1+ a1m+1xm+1+ a1kxk+ a1nxn=b1
x2+ a2m+1xm+1+ a2kxk+ a2nxn=b2
xm+ amm+1xm+1+ amkxk+ 2mnxn=bm
Ā1= (10...0), Ā2=(01..0), Ām=(00..1)
X1= (x1,x2,x3)
X1= (b1,b2,bm)
, , , .
2. k aek ( )
:
) L aek
b'e = be/ aek,.aek>0
b) 0
b'i = bi be/aek * aik ≥0 => bi/aik ≥be/aek.
, , k
min= bi/aik
k.
1- 2- .
F(X2)= Ʃ cibi be/aek (Ʃ ciaik ck)
Ѳk= be/aek
∆k = Ʃ ciaik ck
. Ak .
F(X2) = F(X1)- Ѳk*∆k
0 (∆k < 0), :
1. ... , !
2. k: max{-Ѳk*∆k}, , .
3. , .
, , , 0.
11. . ()
, :
" " ( , )
|
|
,
,
26.1
:
:
.
- x6 +1. x6 (.. ).
:
. () 1 = 2 = 3 = 0.
1 = (0,0,0,24,30,6) 1 = (4, 5, 6).
:
Δk = CXk ck
:
C = (1, 2,..., m)
Xk = (x1k, x2k,..., xmk)
.
. , :
. "" , . . "" . "" , , .
Δk "0" Z(X1).
, Δ1 = -2, Δ3= -9 1 3 .
, , , .
, .
:
θ01 :
θ01 = 6 l = 1, θ03 = 3 l = 1 ( 26.1).
ΔZ1 = 6*(- 2) = 12, ΔZ3 = 3*(- 9) = 27.
, 3 6, θ03 (l = 1).
13 = 2, 2 = (0,0,3,21,42,0) 2 = (3, 4, 5). ( 26.2)
|
|
, 2 Δ2 = 6. 2 .
, . θ02 , 7 l = 2. , 4. 22 = 3, 3 = (0,7,10,0,63,0) 2 = (3, 2, 5) ( 26.3).
, ,
Δ1 = 7/2, Δ4 = 2, Δ6 = 7/2.
: max Z(X) = 201 = (0,7,10,0,63).
12. . ()
F(x) = c1x1 + + cmxn → max
111 + 122 + + m1n ≤ 1
211 + 222 + + m2n ≤ 2
....
m11 + m22 + + mnn ≤ m
Ζ (Y)= 11 + 22 + + mm → min
111 + 122 + + m1n ≥ 1
211 + 222 + + m2n ≥ 2
.
n11 + n22 + + mnn ≥ m
yj ≥0, j = 1, 2 m
y1, y2ym
, . . (). , , .
, . min, max.
:
Ζ (x) = 6x1 + 72 + 9x3 → min
11 + 22 + 33 ≥ 5
11 + 12 + 13 ≥2
11 + 22 + 63 ≥7
1≥0; 2≥0; 3≥0
F(Y)= 51 + 22 + 43 → max
A =
AT =
11 + 22 + 13 ≤ 6
21 + 12 + + 23 ≤ 7
31 + 12 + 63 ≤ 9
. aij i, qj
aij i, qj; (,Q)
(,Q) = ( )
B(,Q) = ( )
13. . 22. ()
, . . , . . , . , .
2 :
- ()
-
, . - .
()
, . m [1..2m], n [1..2..n].
i, j, ij ij. :
|
|
1 | 2 | n | ||
A1 | A11 | A12 | A1n | |
A2 | A21 | A22 | A2n | |
Am | Am1 | Am2 | Amn |
1 | 2 | n | ||
A1 | B11 | B12 | B1n | |
A2 | B21 | B22 | B2n | |
Am | Bm1 | Bm2 | Bmn |
, , , .. :
1- 1
2- 2
3- 3
= 1.
:
q1- B1
q2- B2
q3- B3
= 1.
, .
ij i x qi
:
Ha (P,Q) =
B (P,Q) =
22
11 | 12 |
21 | 22 |
=
B11 | B12 |
B21 | B22 |
=
1 (1)
1- (2)
q (1)
1- q (2)
(, q); (, q)
1. (, q) = 11*( q) + (1- q) + 21*(1-)q + 22*(1-)(1- q)
= (11-12-21+22) q + (12-22) + (21-22)* q + 22
3. = (11-12-21+22) q + (12-22) + (21-22)* q + 22
:
= 11- 12- 21+22
D = B11- B12- B21+B22
α = A22-A12
β = B22-B21
Ɣ = 21-22
Δ = B12-B22
Ha(p;q) = C*(pq) αp+ Vq +A22
(*)
Hb(p;q) = D*(pq) Δ p + βq + B22
II.
: * q*, 0≤ *≤ 1; 0 ≤ q*≤1.
, 2 ;
1. ()
1.1 (q) < Ha(p*,q*) Ɣ p ϵ [0;1]
1.2 HB(p*q) ≤ HB(p*q*)
, ( 1 )
( 2 )
(1) (p*q*) , , , , , .
1. (.)
, .
2. (1) :
2.
(0,q) ≤ Ha (p*q*)
Ha(1,q) ≤ Ha (p*q*)
3.
B(p*,0) ≤ HB (p*q*)
HB(p*,1) ≤ HB (p*q*)
2 , 1.1 ( =0 =1).
. 3, 1.2 . (2 3) (*) :
Ha(p*,q*) = *q*-2p*+ Ɣq* + a22 (4)
Ha(0,q*) = Ɣq* + a22 (5)
Ha(1,q*) = Cq*- α + Ɣq* + a22 (6)
(2) :
Ha(p*,q*) - (0,q*)≥0
(4) (5)
|
|
*(q*- α) ≥0 (7)
(2) :
Ha(p*,q*) - (1,q*)≥0
(4) (5)
*q* - αp* - (Cq*- α) ≥0
= Cq*-(p*-1) α(p*-1) ≥0 (8)
(8):
(*-1)(q*- α) ≥0
p*(Cq*- α) ≥0 (9)
(3)
(p*q*) = Dp*q*- βq*+ Δ p + βq + B22 (10)
HB(p*q*) = Δ p+ B22 (11)
HB=(p*,1) = Dp*- β+ Δ p* + βq + B22 (12)
(3)
14. (*,0) ≤ (*,q*)
Dp*q*- βq*≥0
q*(Dp*- β)≥0
(3)
HB(p*q*) HB (p*,1) ≥0
(10) (12)
Dp*q* - βp*-(Dp*-β) = p* x D(q*-1)- β(q*-1) ≥0
(q*-1)(Dp*- β) ≥0
q*(Dp*- β) ≥0
15. .( )
, p, 1-p, 0≤p≤1 q, 1-q, 0≤q≤1
: p* q*, 0≤ p* ≤1 0≤ q* ≤1 (), :
(1)
(1) , , , . , .
1: (. )
. ( )
2:
(1) :
(2)
(3)
( )
(2) , (1) , p=0 q=1. . , (3) (1b) .
(1) (3). :
(*)
(*)
H(A) (0, q*) = α × q* + a22 (4)
H(A) (1, q*) = C × q* α + γ × q*+a22 (5)
(2) :
H(A) (p*,q*) H(A) (0,q*) ≥ 0
(*) (4)
p* (C × q* α) ≥ 0 (6)
(2) :
H(A) (p*,q*) H(A) (1,q*) ≥ 0
(*) (4)
C× p*× q* α × p* (C × q* α) ≥ 0
C × q*(p*1) α (p*1) ≥ 0 (7)
(6) (7) :
(8)
(3). H(B)
(9)
(10)
(11)
(3)
H(B) (p*,q*) H(B) (p*,0) ≥ 0
(9) (10)
≥ 0
(12)
(3)
H(B) (p*,q*) H(B) (p*,1) ≥ 0
(9) (12)
(8) (12) 0≤ p*≤1, 0≤ q*≤1 .
:
B =
:
1) : C, α, D, β
C = 14, α= 3, D = 9, β = 2
2) (8) (12) :
(1*)
(2*)
(8) (12) , , p* q*, 4 . : 0 1,
- p*=1, (1b)↔ 14× q* + 3 ≥ 0 ↔ 0≤ q*≤
q*= 0, p*=1, (2). , (2*) .
q*= 0, p*=1 .
- p*=1, 0≤ q*≤ (2*) → .
- q*=0. (1*) . (1*)↔14× q* 3 ≥ 0 ↔ q* ≥
, q* p* (2*) . , 0≤ p*≤1. (1*)
→q*=
p* q* = (2*) :
p*=
, .
: p*= , q*=
:
H(A) = 14 × × +3× + 2 × 1=
H(B) = 9× × 2 × 3 × + 1 =
.
. , .
.
N 4 , .
|
|
N=1,2,3n. SCN
S- S N.
R = Ckn
n= =
:
kn=2n
S . S .
. , S V(S) S .
. :
, ( )
V(A B) V(A)+V(B) (1)
(1) , , . (1) , , .
2 (0 1). V(S)=1, S . V(S)=0, S .
:
1)
2) .
3) , , .
4) .
. ,
V(A B)= V(A)+V(B) (2)
A1B N
A B=
(2) A B= , .
:
, .
(3),
V(i)- i
V(N)- , N .
:
(3) (2).
S L
S L= ,
V (S)+V(L) V(S L)
V(S) (1`)
V(L)(2`)
(3`)
\ 2 , .
V(S L)+V (N \S L) V(N)
V(N)=
(1`)+(2`)+(3`),
V(N)= ) V(S)+ V(L)+V(N\S L) V(N) (4`)
.
.
. , . .
=V(N)
.
. , .
V(N)
.
S . . .
. X= (x1, x2, xn)
17. . ()
: . , , . :
, n- . X=(x1,2n), :
- (1*)
- (2*)
(1*)
(2*)
, , (1*)
. , , .
, N, ≠V , -, .
X=(x1,2n) , :
(1)
(2)
(3)
: 1-3, 2 . , , , 1 3 .
:
V(S)- ,
V(S)- ,
S-
18. . ()
19. . ()
M , M
1) ,
2)
,
-
:
,
, . -.
.
, ?
:
0-1 , .
V(S) /n-|S|+1,
n .
|S|- .
, - .
20. 0-1 . ()
(IV,V) 0-1, , V(i)=0; i=1,2,,n; V(N)=1
, -0, 1.
.
0-1 .
.
(IV,V) (IV/V) ~(IV,V), 0-1 . :
V´(i)= KV(i) + Ci=0 i=1,2,,n
V´(N)=KV(N)+ =1 (n+1)
n+1
n
n+1. :
, []>0 ( )
K Ci= - KV(i)=>
, 0-1 . : V
V(S)-
V(S)- ,
S-
:
V(1)=100 V(1,2)=300 V(1,2,3)= 550
V(2)=150 V(1,3)=350
V(3)=300 V(2,3)=420
V (1) = V (2) = V (3) =0
V(1,2,3)=1
21. . ()
22. . (, )
. , , ()
, .
, , , .
, .
.
,
, .
(1,2,4) , .. .
, .
. .
.
, . , .
.
.
.
: 3 1 4 .
: 1 :
V1=(5,4,3,7)
V2=(6,7,5,4)
V3=(3,8,5,4)
23. 2.
( )
1) 1-
2) .
3)
.
.
.
.
, .
.
1 . , . :
, .
.
3 .
3- , . 3- , :
, 3- .
2.
,1 2- , .
.
1- 3-, 2- 2-, 3- 1-.
.
.
1- , 2- , .
:
1-:
1-
2
2-:
1
2
3 , 1-
4 , 1-
:
1 | 2 | 3 | 4 | |
1 | -2 | -2 | ||
2 | -2 | -2 |
-2
2- 4- .
:
2- , 1- .
2- 2 (1 2)
1 | 2 | |
1 | -2 | |
2 | -2 |
24. . ()
.
.
1 , 2 :
1 ,
2 ., 1 ,
2,
3 ,
2 .
.
, , .
p
V=-2
V=
2 . - .