1
1

CHNG 2- BÀI TOÁN I NGU
BÀI 1: CÁC KHÁI NIM & NH LÝ C BN
1.1 BTDN (D) caBT gc(P) dng chính tc:
2

CHNG 2- BÀI TOÁN I NGU
BÀI 1: CÁC KHÁI NIM & NH LÝ C BN
1. nh ngha bài toán đingu
Ví d: Vit BTDN D ca BTQHTT (P) sau:

















4,10
223

4,10
223
5542
97342
min523)(
321
4321
4321
4321
ix
xxx
xxxx
xxxx
xxxxxf
i




















4,10
223
5542
97342
min523)(
321
4321
4321
4321
ix
xxx
xxxx
xxxx
xxxxxf
i

























4,10
223
5542
97342
min523)(
321
4321
4321
4321
ix
xxx
xxxx
xxxx
xxxxxf
i
















4,10
223
5542
97342
min523)(
321
4321
4321
4321
ix
xxx
xxxx
xxxx
xxxxxf
i
















4,10
223
5542
97342
min523)(
321
4321
4321
4321
ix
xxx
xxxx
xxxx
xxxxxf
i
















157
5243
224
332
max259)(
21
321
321
321
321
yy
yyy
yyy
yyy
yyyyg
















157
5243
224
332
max259)(
21
321
321
321
321
yy
yyy
yyy
yyy
yyyyg



CHNG 2- BÀI TOÁN I NGU
BÀI 1: CÁC KHÁI NIM & NH LÝ C BN
1. nh ngha bài toán đingu
Bài toán D đcvitnh sau:















157
5243
224
332
max259)(
21
321
321
321
321
yy

yyy
yyy
yyy
yyyyg















157
5243
224
332
max259)(
21
321
321
321
321
yy

yyy
yyy
yyy
yyyyg















157
5243
224
332
max259)(
21
321
321
321
321
yy

97342
min37122)(
431
321
4321
4321
4321
xxx
xxx
xxxx
xxxx
xxxxxf
















0;0,
223

223
5542
97342
min37122)(
431
321
4321
4321
4321
xxx
xxx
xxxx
xxxx
xxxxxf


















0;0,
223
5542
97342
min37122)(
431
321
4321
4321
4321
xxx
xxx
xxxx
xxxx
xxxxxf
6

CHNG 2- BÀI TOÁN I NGU
BÀI 1: CÁC KHÁI NIM & NH LÝ C BN
1.2 BTDN (D) caBT gc(P)  dng tng quát btk:








0,,








0,,
*
422
*
44
222
xxx
xx
xxx
ba
ba








0,,
*
422
*

55422
973442
mi
n
.0.03712122)(
*
42
321
6
*
321
5
*
321
65
*
321
2
2
42
42
42
xxxix
xxxx
xxxxxx
xxxxxx
xxxxxxxxf
ba
i
ba

321
5
*
321
65
*
321
2
2
42
42
42
xxxix
xxxx
xxxxxx
xxxxxx
xxxxxxxxf
ba
i
ba
ba
ba
ba








42
42
xxxix
xxxx
xxxxxx
xxxxxx
xxxxxxxxf
ba
i
ba
ba
ba
ba















0,,;6,5,3,10
223

ba
ba
ba
8

CHNG 2- BÀI TOÁN I NGU
BÀI 1: CÁC KHÁI NIM & NH LÝ C BN
1.2 BTDN (D) caBT gc(P)  dng tng quát btk:



















0
0
357













0
0
357
7243
1224
232
max259)(
2
1
21
321
321
321
321
y
y
yy
yyy

2
1
21
321
321
321
321
321
y
y
yy
yyy
yyy
yyy
yyy
yyyyg
































0
0
357
7243
1224
1224
232
max259)(
2
1
21
321
321



0
0
357
7243
1224
232
max259)(
2
1
21
321
321
321
321
y
y
yy
yyy
yyy
yyy
yyyyg








yy
yyy
yyy
yyy
yyy
yyyyg





















0
0
357








0
0
357
7243
1224
1224
232
max259)(
2
1
21
321
321
321
321
321
y
y
yy
yyy
yyy
yyy
yyy

1
21
321
321
321
321
y
y
yy
yyy
yyy
yyy
yyyyg



































0
0
357
7243
1224
232
max259)(
2
1
21
321
321
321

7243
1224
1224
232
max259)(
2
1
21
321
321
321
321
321
y
y
yy
yyy
yyy
yyy
yyy
yyyyg










yyy
yyy
yyyyg



















0
0
357
7243
1224
1224
232
max259)(








0
0
357
7243
1224
232
max259)(
2
1
21
321
321
321
321
y
y
yy
yyy
yyy
yyy
yyyyg
5
9

















5,10
6534
525
832
max34)(
5432
5432
4321
532
ix
xxxx
xxxx
xxxx
xxxxf

xxxxf
i
















5,10
6534
525
832
max34)(
5432
5432
4321
532
ix
xxxx
xxxx

xxxx
xxxx
xxxxf
i
7
13

CHNG 2- BÀI TOÁN I NGU
BÀI 1: CÁC KHÁI NIM & NH LÝ C BN
2. Cách lp bài toán đingu
Cách 1: a bài toán trên v dng chính tc:


















6,10



6,10
6534
525
832
max00340)(
65432
5432
4321
654321
ix
xxxxx
xxxx
xxxx
xxxxxxxf
i






















6,10
6534
525
832
max00340)(
65432
5432
4321
654321
ix
xxxxx
xxxx
xxxx
xxxxxxxf
i
14

CHNG 2- BÀI TOÁN I NGU
BÀI 1: CÁC KHÁI NIM & NH LÝ C BN
2. Cách lp bài toán đingu



y
yy
yyy
yyy
yyy
y
yyyyg


















0,0
15
032
34
453




0
15
032
34
453
02
min658)(
3
32
321
321
321
1
321
y
yy
yyy
yyy
yyy
y
yyyyg







yyy
yyyyg


















0
15
032
34
453
02
min658)(
3
32
321

15
032
34
453
mi
n
658)(
31
32
321
321
321
321
yy
yy
yyy
yyy
yyy
yyyyg




























0,0
15
032
34
453
mi
n
658)(
31
32
321
321
321
321

min658)(
3
32
321
321
321
1
321
y
yy
yyy
yyy
yyy
y
yyyyg



























0
15
032
34
453
02
min658)(
3
32
321
321
321
1
321
y
yy
yyy
yyy
yyy

321
321
321
321
yy
yy
yyy
yyy
yyy
yyyyg


















0
15








0,0
15
032
34
453
mi
n
658)(
31
32
321
321
321
321
yy
yy
yyy
yyy
yyy
yyyyg




yy
yyy
yyy
yyy
y
yyyyg


















0,0
15
032
34
453
mi



0
15
032
34
453
02
min658)(
3
32
321
321
321
1
321
y
yy
yyy
yyy
yyy
y
yyyyg








yyyyg
8
15

CHNG 2- BÀI TOÁN I NGU
BÀI 1: CÁC KHÁI NIM & NH LÝ C BN
2. Cách lp bài toán đingu
Cách 2:


















))3(.(0
))2(&)1(.(,
)0(15
)0(032









))3(.(0
))2(&)1(.(,
)0(15
)0(032
)0(34
)0(453
)0(02
min658)(
3
21
532
4321
3321
2321
11
321
thucdangbatbrdoy
thucdangbrdoytuyyy
xdoyy
xdoyyy
xdoyyy
xdoyyy

532
4321
3321
2321
11
321
thucdangbatbrdoy
thucdangbrdoytuyyy
xdoyy
xdoyyy
xdoyyy
xdoyyy
xdoy
yyyyg































))3(.(0
))2(&)1(.(,
)0(15
)0(032
)0(34
)0(453
)0(02
min658)(
3
21
532
4321
3321
2321
11
321



0,0
15
032
34
453
min658)(
31
32
321
321
321
321
yy
yy
yyy
yyy
yyy
yyyyg

























0,0
15
032
34
453
min658)(
31
32
321
321
321
321
yy
yy
yyy
yyy

321
321
yy
yy
yyy
yyy
yyy
yyyyg


















0,0
15
032
34



0,0
15
032
34
453
min658)(
31
32
321
321
321
321
yy
yy
yyy
yyy
yyy
yyyyg
9
17

CHNG 2- BÀI TOÁN I NGU
BÀI 1: CÁC KHÁI NIM & NH LÝ C BN
2. Cách lp bài toán đingu
Trong ví d này, ta có các cpràngbuc đingu sau:
6534&0
15&0
032&0

3213
3212
11






xxxxy
yyx
yyyx
yyyx
yyyx
yx
6534&0
15&0
032&0
34&0
453&0
0&0
54323
325
3214
3213
3212
11




yyyx
yyyx
yx
6534&0
15&0
032&0
34&0
453&0
0&0
54323
325
3214
3213
3212
11






xxxxy
yyx
yyyx
yyyx
yyyx
yx
18

CHNG 2- BÀI TOÁN I NGU

phicóítnhtmt PA.
2) K cn& đ đ cp PA x
0
& y
0
cacp BTDN ti ulà
f(x
0
) = g(y
0
).
20

CHNG 2- BÀI TOÁN I NGU
BÀI 1: CÁC KHÁI NIM & NH LÝ C BN
3. Các đnh lý c bn
3.2 nh lý 2 ( lch bù yu): iukincn& đ đ
phng án x
0
ca P và phng án y
0
caD ti ulà:
Tc là: Trong các cpràngbuc đingucacpbài
toán P & D, numtràngbuctho mãn lng (> hoc<)
thì ràng buccònliphitho mãn cht(đng thc, =).






jiij
m
j
ijii
j
j
,10
,10
1
00
1
00



































































mjbxay
nicyax
n
i
jiij
m
j
ijii
j
j
,10
,10
1





mjbxay
nicyax
n
i
jiij
m
j
ijii
j
j
,10
,10
1
00
1
00