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

phng án ti uca bài toán D.
2
3

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:
Cho bài toán P nh sau:
a) Gii bài toán P.
b) Vit BTDN D tng ng và tìm nghimcaD davào
nghimcaP.
c) Gii BTDN D tng ng bng PPH và nhnxét.


















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


















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
4

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

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





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


















8,10
10532
923
9342
ma
x
23)(
84321
6321
754321
874321
ix
xxxxx

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

754321
874321
ix
xxxxx
xxxx
xxxxxx
MxMxxxxxxf
i

















8,10
10532
923
9342
ma

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


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
Tibclpth 5, ta có ttc các HSUL cacácnca
BT “M” đu không âm cho nên BT “M” có PATU là






 0,0,0,0,0,
7
2
,
7
22
,
7
27
*M
x
vitr s HMT đt đclàf(x*
M
) = 9 và do các ngiđu
nhngiátr 0 cho nên BT gc P có PATU là







 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
yyyyg





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

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

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

21
31
321
321
321
321
yy
yy
yyy
yyy
yyy
yyyyg
5
9

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ác cp ràng buc đingu:
923
9342
0
0
0
0
321
4321
4
3
2

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

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

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

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

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

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

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

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

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

9342
0
0
0
0
321
4321
4
3
2
1






xxx
xxxx
x
x
x
x
&
&
&
&
&
&
0

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

0
321
4321
4
3
2
1






xxx
xxxx
x
x
x
x
&
&
&
&
&
&
0
0
153
2324
12

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

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

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

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

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

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

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

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

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

yyyx









0
1
0
3
2
1
y
y
y
23240
7
2
120
7
22
3230
7
27
3213
3212

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

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

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

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

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

yyyx









0
1
0
3
2
1
y
y
y
23240
7
2
120
7
22
3230
7
27
3213
3212

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

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

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'

min10109'9)(
731
96321
5321
84321
98321
3
3
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
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
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
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
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
3
iy
yyyy
yyyyyy
yyyyy
yyyyyy
MyMyyyyyyg
i
ba
ba

ba
ba
ba
12

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:
Các nph:
7654331
,,,,,,' yyyyyyy
ba
98
, yy

















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

Các ngi:
















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

















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

















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
















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

















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
















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
7
13

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:
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

Ý NGHA VÀ MT SNG DNG CA BTN
2. Cách tìm ligii bài toán (P) t BT (D)
+ Th PATU y
0
ca D 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 đingucanótrongP s
tho mãn chtvàkhiđótalp đcmth phng
trình tuyntínhtheocácnca bài toán P.
+ Giih phng trình tuyn tính trên đ tìm nghim
t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 P. 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 P chính là tpphng án ti uca bài toán P.
16

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:
Vit& gii BTN caBT saubng PPH; tđó
suy ra ligiica BT sau:


















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


















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

















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
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
i

















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

i
















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
i
18

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nCB:
PACB XP:
7654
,,, yyyy
)1,4,3,1,0,0,0(
0
y

















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
yyy
yyyyg
i

















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
yyy
yyyyg
i
















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
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):







 0,0,
2
5
,
2
11
,2,0,
2
3
*y
PATU caBT g(y):






 2,0,
2
3
*y
26*)(

yg
Thay y
1
= 3/2, 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

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

xyyy
xyy
xxxxy
xxxy
11
21

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ih phng trình:
Vy, PATU ca BT (P) là: x* = (0, 0, 6, 2)
Tr s HMT đt đc là f(x*) = 26.


















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
























2
6
0
0
0
0
1023

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

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

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

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

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

x
x
x
x
x
x
xxxx
xxx
22

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
3. Chng t tính ti ucamtPA:
Gi s, có vector x
0
(n chiu) và ta cnchng minh x
0
có
là PATU ca BT P hay không?
12
23

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 1:
Cho BT QHTT (P) nh sau:
Chng t rng vector x
0

= (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
xxxxxf
i
















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
















4,10
1023
943
422
min43)(
4321
432
421
4321

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

















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

i
















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
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















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















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














0102/2323
09243

1422/3
428
131
34321
2432
3214
323
311
yxxxx
yxxx
yyyx
yyx
yyx
26

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ih PT:
H PT này vô nghim
Ktlun: x
0
không là PATU ca(P)















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















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).

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

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

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

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

252353
212
8223
min422)(
541
5431
5431
54321
54321
ix
xxx
xxxx
xxxx
xxxxx
xxxxxxf
i
28

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 nhnthyrng x
0
là mt PA ca(P).
B2) Lp BTN (D) tng ng nh sau:





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

4321
yy
yyyy
yyyy
yyy
y
yyyy
yyyyyg





















0,0

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

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

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

42
4321
4321
321
1
4321
4321
yy
yyyy
yyyy
yyy
y
yyyy
yyyyyg

















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

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

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
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

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
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:











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

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










1
1
0
1
0
4422
232
253
1
4
3
2
1
2
4321
4321
321
1
y
y
y

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



1
1
0
1
0
4422
232
253
1
4
3
2
1
2
4321
4321
321
1
y
y
y
y
y
yyyy
yyyy
yyy
y


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

4422
232
253
1
4
3
2
1
2
4321
4321
321
1
y
y
y
y
y
yyyy
yyyy
yyy
y









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

1
2
4321
4321
321
1
y
y
y
y
y
yyyy
yyyy
yyy
y
16
31

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:
B4) Ta nhnthyrng là mtPA
ca(D).
)1,1,0,1(
0
y
Do đó, x
0
= (0, 23, 10, 10, 5/2) là PATU ca(P) và

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

















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

















3,10
1423
5)2(2
62
min23)(
321
321
321
321
ix
xxx
xmxx
xxx
xmxxxf
i
17
33

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
B1)  là mt PA ca(P),
x
0

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
















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

0
là PATU ca (P) thì davàođnh lý đ lch
bù yu, ta có:
 Giih PT sau:








10145610)(
12)2(204
3302
321
0
3213
3211
yyyxf
yymyx
yyyx









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

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

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

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

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


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
Bin đih trên, ta có:






0
4/11
0)114(
2
2
y
m
ym
@ Xét m = 11/4: Khi đó, h trên có nghim:












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
RB
Tclàtacóth tìm đc PATU cho (D) khi m = 11/4;
do đó, ng vi m = 11/4, x
0
là PATU ca(P).
38

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
@ Xét y
2
= 0: Khi đó, ta có h nghimtng ng:








8/7
0
8/3
3
2
1
y
y

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



 m