Chương 2: Bài toán đối ngẫu - bài 1 pot

Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (280.83 KB, 10 trang )

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

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
2
3

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:



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

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
3
5

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:
Ví d: Vit bài toán đinguca bài toán sau:
















0;0,
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
















0;0,

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

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

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

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

44
222
xxx
xx
xxx
ba
ba
4
7

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,,;6,5,3,10
223

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

ba
ba
ba















0,,;6,5,3,10
223
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
ba
ba
ba
















0,,;6,5,3,10
223
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
ba
ba
ba















0,,;6,5,3,10
223

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

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

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

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

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

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

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

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

321
321
321
y
y
yy
yyy
yyy
yyy
yyy
yyyyg




















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

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

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

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

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

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

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

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

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

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

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

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

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

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

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


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
10

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
6
11

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âu thn chú”:
Ràng D cùng duhoc“bng” nP;
nD thìtráiràngP hoctu.
Ràng D thì trái hoc“bng” nP;
n D cùng duràngP hoctu.
MinMax  MinMax  MinMax 
MaxMin 
MaxMin 
MaxMin 
12

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
Ví d: Lp bài toán đinguca bài toán sau:

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

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

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

xxxx
xxxxf
i
















5,10
6534
525
832
max34)(
5432
5432
4321
532
ix
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

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

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

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

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

mi
n
658)(
31
32
321
321
321
321
yy
yy
yyy
yyy
yyy
yyyyg
















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

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

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

321
321
1
321
y
yy
yyy
yyy
yyy
y
yyyyg


















0,0

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

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

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

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

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

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

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

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

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

032
34
453
02
min658)(
3
32
321
321
321
1
321
y
yy
yyy
yyy
yyy
y
yyyyg












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

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

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

n
658)(
31
32
321
321
321
321
yy
yy
yyy
yyy
yyy
yyyyg

















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

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

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

)0(34
)0(453
)0(02
min658)(
3
21
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
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
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
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

thucdangbatbrdoy
thucdangbrdoytuyyy
xdoyy
xdoyyy
xdoyyy
xdoyyy
xdoy
yyyyg
16

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:



















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
yyy
yyyyg





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

34&0
453&0
0&0
54323
325
3214
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






xxxxy
yyx
yyyx
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
6534&0
15&0
032&0
34&0
453&0
0&0
54323
325
3214
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






xxxxy
yyx
yyyx
yyyx
yyyx
yx
18

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.1 nh lý 1: Vicp bài toán P & D, ch xyra
mttrongbatrng hp sau:
a) C hai đu không có PA.
b) C hai đu có PA; khi đó, c hai cùng có
PATU và giá tr HMT TU ca2 BT bng nhau.
c) Mt trong hai bài toán không có PA và bài
toán kia có PA; khi đó, bài toán không có PATU
và hàm mctiêuca nó không b chn.
10
19

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.1 nh lý 1 (Phát biukhác): Numt trong hai bài toán
đingucóligii(tc có PATU) thì bài toán kia cng có
ligii(tccng có PATU) và khi đó, vimicp PATU
x
0
& y
0
ca (P) & (D) tng ng, ta có: f(x
0
) = g(y
0
).
H qu
1) iukincn& đ đ cp BTDN gii đclàmiBT

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, =).




