1
1

CHNG 2- BÀI TOÁN I NGU
BÀI 2: CÁCH GII BÀI TOÁN I NGU
Ý NGHA VÀ MT SNG DNG CA BTN
1. Cách tìm ligii bài toán đingu(D) t BT (P)
Davàocácđnh lý và h qu nêu  bài 1, ta có:
@ Nu P có hay không có PATU thì D cng có hay không
có PATU và ngcli.
@ Nu có PATU thì giá tr HMT ti uca2 BT bng nhau.
+ Th PATU x
0
ca P vào các ràng bucbt
đng thc trong các cp ràng buc đingu. Nu
ràng buc nào tho mãn lng thì ràng buc đi
ngucanótrongD s tho mãn chtvàkhiđó
ta lp đcmth phng trình tuyntínhtheo
các nca bài toán D.
2

CHNG 2- BÀI TOÁN I NGU
BÀI 2: CÁCH GII BÀI TOÁN I NGU
Ý NGHA VÀ MT SNG DNG CA BTN
1. Cách tìm ligii bài toán đingu(D) t BT (P)
+ Giih phng trình tuyn tính trên đ tìm
nghimtng ng.
+ Thay nghimcah phng trình trên vào các
ràng buccònlica bài toán D. Khi đó, nhng
nghimcah phng trình ti utho mãn các
ràng buccònlica bài toán D chính là tp

5,10
10532
923
9342
max23)(
4321
321
4321
4321
ix
xxxx
xxx
xxxx
xxxxxf
i




















5,10
10532
923
9342
max23)(
4321
321
4321
4321
ix
xxxx
xxx
xxxx
xxxxxf
i




















5,10
10532
923
9342
max23)(
4321
321
4321
4321
ix
xxxx
xxx
xxxx
xxxxxf
i








a) a bài toán P v BT “M” dng chunvi2 nph x
5
và x
6
; 2 ngi x
7
và x
8
nh sau:
HnCB: x
6
, x
7
và x
8
.


10,7,9,0,0,0,0,0
M
x
PACB XP caBT “M”:






















8,10
10532
923
9342
ma
x
23)(
84321
6321
754321
874321
ix
xxxxx
xxxx
xxxxxx
MxMxxxxxxf
i

xxxx
xxxxxx
MxMxxxxxxf
i

















8,10
10532
923
9342
ma
x
23)(
84321
6321

x
23)(
84321
6321
754321
874321
ix
xxxxx
xxxx
xxxxxx
MxMxxxxxxf
i


10,7,9,0,0,0,0,0
M
x
3
5

CHNG 2- BÀI TOÁN I NGU
BÀI 2: CÁCH GII BÀI TOÁN I NGU
Ý NGHA VÀ MT SNG DNG CA BTN
6

CHNG 2- BÀI TOÁN I NGU
BÀI 2: CÁCH GII BÀI TOÁN I NGU
Ý NGHA VÀ MT SNG DNG CA BTN
4
7




 0,
7
2
,
7
22
,
7
27
*x
vitr s HMT đt đc
là f(x*) = 9.
8

CHNG 2- BÀI TOÁN I NGU
BÀI 2: CÁCH GII BÀI TOÁN I NGU
Ý NGHA VÀ MT SNG DNG CA BTN
b) Bài toán đinguD caP đcvitnh sau:























0,0
153
2324
12
323
min1099)(
21
31
321
321
321
321
yy
yy
yyy
yyy
yyy

yy
yy
yyy
yyy
yyy
yyyyg


















0,0
153
2324
12
323
min1099)(

1






xxx
xxxx
x
x
x
x
&
&
&
&
&
&
0
0
153
2324
12
323
2
1
31
321
321




xxx
xxxx
x
x
x
x
&
&
&
&
&
&
0
0
153
2324
12
323
2
1
31
321
321
321




xxxx
x
x
x
x
&
&
&
&
&
&
0
0
153
2324
12
323
2
1
31
321
321
321








x
&
&
&
&
&
&
0
0
153
2324
12
323
2
1
31
321
321
321








y
y
yy

&
&
&
0
0
153
2324
12
323
2
1
31
321
321
321








y
y
yy
yyy
yyy
yyy
923

0
153
2324
12
323
2
1
31
321
321
321








y
y
yy
yyy
yyy
yyy
923
9342
0
0
0

323
2
1
31
321
321
321








y
y
yy
yyy
yyy
yyy
923
9342
0
0
0
0
321
4321
4

321
321
321








y
y
yy
yyy
yyy
yyy
923
9342
0
0
0
0
321
4321
4
3
2
1









y
y
yy
yyy
yyy
yyy
923
9342
0
0
0
0
321
4321
4
3
2
1









y
y
yy
yyy
yyy
yyy
923
9342
0
0
0
0
321
4321
4
3
2
1






xxx
xxxx
x

y
yy
yyy
yyy
yyy
10

CHNG 2- BÀI TOÁN I NGU
BÀI 2: CÁCH GII BÀI TOÁN I NGU
Ý NGHA VÀ MT SNG DNG CA BTN
Davàođnh lý đ lch bù yu:
Vy, PATU ca BTN D là y* = (0, 1, 0) vitr
s hàm mctiêuđt đc là g(y*) = 9.
23240
7
2
120
7
22
3230
7
27
3213
3212
3211



yyyx
yyyx

3211



yyyx
yyyx
yyyx









0
1
0
3
2
1
y
y
y
23240
7
2
120
7

y
23240
7
2
120
7
22
3230
7
27
3213
3212
3211



yyyx
yyyx
yyyx









0
1





0
1
0
3
2
1
y
y
y
23240
7
2
120
7
22
3230
7
27
3213
3212
3211



yyyx
yyyx

3211



yyyx
yyyx
yyyx









0
1
0
3
2
1
y
y
y
23240
7
2
120
7

y
6
11

CHNG 2- BÀI TOÁN I NGU
BÀI 2: CÁCH GII BÀI TOÁN I NGU
Ý NGHA VÀ MT SNG DNG CA BTN
c) Gii bài toán D bng phng pháp đnhình:
a bài toán D v bài toán “M” dng chunnh sau:
















9,10
155'3
2332'4
1'2
3223'










9,10
155'3
2332'4
1'2
3223'
min10109'9)(
731
96321
5321
84321
98321
3
3
3
3
3
iy
yyyy
yyyyyy
yyyyy
yyyyyy

96321
5321
84321
98321
3
3
3
3
3
iy
yyyy
yyyyyy
yyyyy
yyyyyy
MyMyyyyyyg
i
ba
ba
ba
ba
ba










ba
ba
ba
ba
ba
















9,10
155'3
2332'4
1'2
3223'
min10109'9)(
731
96321
5321






9,10
155'3
2332'4
1'2
3223'
min10109'9)(
731
96321
5321
84321
98321
3
3
3
3
3
iy
yyyy
yyyyyy
yyyyy
yyyyyy
MyMyyyyyyg
i
ba
ba



9,10
155'3
2332'4
1'2
3223'
min10109'9)(
731
96321
5321
84321
98321
3
3
3
3
3
iy
yyyy
yyyyyy
yyyyy
yyyyyy
MyMyyyyyyg
i
ba
ba
ba
ba
ba

3
3
3
iy
yyyy
yyyyyy
yyyyy
yyyyyy
MyMyyyyyyg
i
ba
ba
ba
ba
ba































9,10
155'3
2332'4
1'2
3223'
min10109'9)(
731
96321
5321
84321
98321
3
3
3
3

155'3
2332'4
1'2
3223'
min10109'9)(
731
96321
5321
84321
98321
3
3
3
3
3
iy
yyyy
yyyyyy
yyyyy
yyyyyy
MyMyyyyyyg
i
ba
ba
ba
ba
ba




yyyy
yyyyyy
yyyyy
yyyyyy
MyMyyyyyyg
i
ba
ba
ba
ba
ba
















9,10
155'3
2332'4

Ý NGHA VÀ MT SNG DNG CA BTN
c) Gii bài toán D bng phng pháp đnhình:
Hnc bn:
9875
,,, yyyy
y
M
= (0,0,0,0,0,1,0,1,3,2)
14

CHNG 2- BÀI TOÁN I NGU
BÀI 2: CÁCH GII BÀI TOÁN I NGU
Ý NGHA VÀ MT SNG DNG CA BTN
c) Gii bài toán D bng phng pháp đnhình:
Tibclpth 4, ta thyrng ttc các HSUL cacác
n đu không dng; vy, PATU caBT “M”là
y*
M
= (0, 1, 0, 0, 0, 0, 0, 1, 0, 0) và tr s ca HMT đt
đclàg(y*
M
) = 9. ng thi, ta nhnthyrng, các n
gi caBT “M”đunhngiátr 0; cho nên BT D có PATU
là y* = (0, 1, 0) vitr HMT đt đclàg(y*) = 9.
Nhn xét: PA này ging nh PA nhn đct câu b.
8
15

CHNG 2- BÀI TOÁN I NGU
BÀI 2: CÁCH GII BÀI TOÁN I NGU











4,10
1023
943
422
min43)(
4321
432
421
4321
ix
xxxx
xxx
xxx
xxxxxf
i




















4,10
1023
943
422
min43)(
4321
432
421
4321
ix
xxxx
xxx
xxx
xxxxxf
i


i

















4,10
1023
943
422
min43)(
4321
432
421
4321
ix
xxxx
xxx

xxxx
xxx
xxx
xxxxxf
i
9
17

CHNG 2- BÀI TOÁN I NGU
BÀI 2: CÁCH GII BÀI TOÁN I NGU
Ý NGHA VÀ MT SNG DNG CA BTN
BTN tng ng:

Gii BT này bng
PPH nh sau:





















3,10
142
42
332
13
max1094)(
321
32
321
31
321
iy
yyy
yy
yyy
yy
yyyyg
i





















3,10
142
42
332
13
max1094)(
321
32
321
31
321
iy
yyy
yy
yyy
yy
yyyyg

yy
yyy
yy
yyyyg
i
















3,10
142
42
332
13
max1094)(
321
32
321








7,10
142
42
332
13
max1094)(
7321
632
5321
431
321
iy
yyyy
yyy
yyyy
yyy
yyyyg
i





















7,10
142
42
332
13
max1094)(
7321
632
5321
431
321
iy
yyyy
yyy
yyyy

iy
yyyy
yyy
yyyy
yyy
yyyyg
i
















7,10
142
42
332
13
max1094)(
7321

332
13
max1094)(
7321
632
5321
431
321
iy
yyyy
yyy
yyyy
yyy
yyyyg
i
10
19

CHNG 2- BÀI TOÁN I NGU
BÀI 2: CÁCH GII BÀI TOÁN I NGU
Ý NGHA VÀ MT SNG DNG CA BTN
20

CHNG 2- BÀI TOÁN I NGU
BÀI 2: CÁCH GII BÀI TOÁN I NGU
Ý NGHA VÀ MT SNG DNG CA BTN
PATU caBT ph ca g(y):




2
= 0, y
3
= 2 vào HRB ca g(y), ta có:













03132
01
2
9
3
102302
4220
2
3
2321
131
43213
4211

xyyy
xyy
xxxxy
xxxy













03132
01
2
9
3
102302
4220
2
3
2321
131
43213
4211

xyyy
xyy
xxxxy
xxxy













03132
01
2
9
3
102302
4220
2
3
2321
131
43213
4211







2
6
0
0
0
0
1023
422
4
3
2
1
2
1
4321
421
x
x
x
x
x
x
xxxx
xxx

422
4
3
2
1
2
1
4321
421
x
x
x
x
x
x
xxxx
xxx














x
x
xxxx
xxx























2
6
0















2
6
0
0
0
0
1023
422
4
3
2
1
2
1
4321
421

= (1, 0, 8, 3/2) là mt PA nhng
không phi là PATU ca(P).
















4,10
1023
943
422
min43)(
4321
432
421
4321
ix
xxxx
xxx

xxx
xxx
xxxxxf
i
















4,10
1023
943
422
min43)(
4321
432
421
4321
ix

ix
xxxx
xxx
xxx
xxxxxf
i
24

CHNG 2- BÀI TOÁN I NGU
BÀI 2: CÁCH GII BÀI TOÁN I NGU
Ý NGHA VÀ MT SNG DNG CA BTN
Gii:
B1: Ta thy x
0
= (1, 0, 8, 3/2) tho mãn ttc các RB ca
(P)  x
0
là mtPA ca(P).
B2: Lp BTN (D) tng ng nh sau:





















3,10
142
42
332
13
max1094)(
321
32
321
31
321
iy
yyy
yy
yyy
yy
yyyyg
i




i
















3,10
142
42
332
13
max1094)(
321
32
321
31
321
iy
yyy

31
321
iy
yyy
yy
yyy
yy
yyyyg
i
13
25

CHNG 2- BÀI TOÁN I NGU
BÀI 2: CÁCH GII BÀI TOÁN I NGU
Ý NGHA VÀ MT SNG DNG CA BTN
Gii:
B3: Gi s x
0
là PATU ca (P); khi đó, theo đnh lý đ lch
bù yu, ta có:














0102/2323
09243
1422/3
428
131
34321
2432
3214
323
311
yxxxx
yxxx
yyyx
yyx
yyx














0102/2323
09243
1422/3
428
131
34321
2432
3214
323
311
yxxxx
yxxx
yyyx
yyx
yyx















09243
1422/3
428
131
34321
2432
3214
323
311
yxxxx
yxxx
yyyx
yyx
yyx














0102/2323
09243









0
0
142
42
13
3
2
321
32
31
y
y
yyy
yy
yy














0
0
142
42
13
3
2
321
32
31
y
y
yyy
yy
yy














0
0
142
42
13
3
2
321
32
31
y
y
yyy
yy
yy
14
27

CHNG 2- BÀI TOÁN I NGU
BÀI 2: CÁCH GII BÀI TOÁN I NGU
Ý NGHA VÀ MT SNG DNG CA BTN
Ví d 2:
Cho BT QHTT (P) nh sau:
Chng t rng x
0
= (0,23,10,10,5/2) là mt PATU ca(P).

xxxx
xxxxx
xxxxxxf
i
















5,10
2042
252353
212
8223
min422)(
541
5431
5431
54321

541
5431
5431
54321
54321
ix
xxx
xxxx
xxxx
xxxxx
xxxxxxf
i
















5,10
2042


















0,0
4422
232
253
1
1232
min2025218)(
42
4321
4321
321
1
4321

4422
232
253
1
1232
min2025218)(
42
4321
4321
321
1
4321
4321
yy
yyyy
yyyy
yyy
y
yyyy
yyyyyg











yyyy
yyyyyg





















0,0
4422
232
253
1
1232
min2025218)(






0,0
4422
232
253
1
1232
min2025218)(
42
4321
4321
321
1
4321
4321
yy
yyyy
yyyy
yyy
y
yyyy
yyyyyg





4321
yy
yyyy
yyyy
yyy
y
yyyy
yyyyyg
15
29

CHNG 2- BÀI TOÁN I NGU
BÀI 2: CÁCH GII BÀI TOÁN I NGU
Ý NGHA VÀ MT SNG DNG CA BTN
Gii:
B3) Gi s, x
0
là PATU ca(P), davàođnh lý đ lch
bù yu, ta có:














0212/52
442202/5
232010
253010
1023
25431
43215
43214
3213
12
yxxxx
yyyyx
yyyyx
yyyx
yx














0212/52
442202/5
232010
253010
1023
25431
43215
43214
3213
12
yxxxx
yyyyx
yyyyx
yyyx
yx














0212/52

232010
253010
1023
25431
43215
43214
3213
12
yxxxx
yyyyx
yyyyx
yyyx
yx
30

CHNG 2- BÀI TOÁN I NGU
BÀI 2: CÁCH GII BÀI TOÁN I NGU
Ý NGHA VÀ MT SNG DNG CA BTN
Gii:
B3) Ta giih PT sau:











4321
4321
321
1
y
y
y
y
y
yyyy
yyyy
yyy
y


















y
y
yyyy
yyyy
yyy
y


















































1
1
0
1
0



















1
1
0
1
0
4422
232
253
1
4
3
2

y
0
= (1, 0, 1, -1) là PATU ca(D)
32

CHNG 2- BÀI TOÁN I NGU
BÀI 2: CÁCH GII BÀI TOÁN I NGU
Ý NGHA VÀ MT SNG DNG CA BTN
Ví d 3: Cho BTQHTT (P) nh sau:
Tìm các giá tr cam đ vector là PATU
ca BT (P).


4,0,2
0
x


















3,10
1423
5)2(2
62
min23)(
321
321
321
321
ix
xxx
xmxx
xxx
xmxxxf
i


















3,10
1423
5)2(2
62
min23)(
321
321
321
321
ix
xxx
xmxx
xxx
xmxxxf
i











phitho mãn h ràng bucca(P). Ta
nhnthyrng x
0
đãtho mãn 5 trong 6
ràng bucca BT; do đó, đ tho mãn c 6
ràng buc, x
0
phitho mãn ràng buc2:

4,0,2
0
x
4/115)2(42



 mm
34

CHNG 2- BÀI TOÁN I NGU
BÀI 2: CÁCH GII BÀI TOÁN I NGU
Ý NGHA VÀ MT SNG DNG CA BTN
B2) Lp BTN (D) tng ng:
















0
12)2(2
22
33
max1456)(
2
321
321
321
321
y
yymy
myyy
yyy
yyyyg
















0
12)2(2
22
33
max1456)(
2
321
321
321
321
y
yymy
myyy
yyy
yyyyg
18
35

CHNG 2- BÀI TOÁN I NGU
BÀI 2: CÁCH GII BÀI TOÁN I NGU
Ý NGHA VÀ MT SNG DNG CA BTN
B3) Nu x

10145610)(
12)2(204
3302
321
0
3213
3211
yyyxf
yymyx
yyyx








10145610)(
12)2(204
3302
321
0
3213
3211
yyyxf
yymyx
yyyx



3211
yyyxf
yymyx
yyyx








101456
12)2(2
33
321
321
321
yyy
yymy
yyy








101456




101456
12)2(2
33
321
321
321
yyy
yymy
yyy








101456
12)2(2
33
321
321
321
yyy
yymy
yyy
36


3
2
1
11/)3228(
11/)5(
y
y
y
19
37

CHNG 2- BÀI TOÁN I NGU
BÀI 2: CÁCH GII BÀI TOÁN I NGU
Ý NGHA VÀ MT SNG DNG CA BTN
 h nghim trên là PATU ca (D) thì h nghimtrên
phitho h ràng bucca g(y); khi đó:
8/7
8/70
152/1)2(
2










y
 h nghim này là PA ca(D), h nghim này
phitho mãn HRB ca(D); tclà:
8/5)2(



mRB
20
39

CHNG 2- BÀI TOÁN I NGU
BÀI 2: CÁCH GII BÀI TOÁN I NGU
Ý NGHA VÀ MT SNG DNG CA BTN
Vyvi thì ta có th tìm đc
PATU ca(D); tclàvi,
x
0
là PATU ca(P).
8/5m
4/118/5



m
Ktlun: x
0
= (2, 0, 4) là PATU ca(P) khi:
4/118/5
