1
1

CHNG I- BÀI TOÁN QUY HOCH TUYN TÍNH
BÀI 2. CÁC KHÁI NIM C BN
1. nh nghaBTQHTT
)1((min)max)(
1



n
i
ii
xcxf

















x
mjbxa
i
j
n
i
iij
)1((min)max)(
1



n
i
ii
xcxf















ni
ytuy
x
mjbxa
i
j
n
i
iij
)1((min)max)(
1



n
i
ii
xcxf













)2(),1(
1
ni
ytuy
x
mjbxa
i
j
n
i
iij
)1((min)max)(
1



n
i
ii
xcxf











)3(),1(0
0
)2(),1(
1
ni
ytuy
x
mjbxa
i
j
n
i
iij
)1((min)max)(
1



n
i
ii
xcxf











)3(),1(0
0
)2(),1(
1
ni
ytuy
x
mjbxa
i
j
n
i
iij
)1((min)max)(
1



n
i
ii
xcxf











)3(),1(0
0
)2(),1(
1
ni
ytuy
x
mjbxa
i
j
n
i
iij
)1((min)max)(
1



n
i
ii
xcxf











)3(),1(0
0
)2(),1(
1
ni
ytuy
x
mjbxa
i
j
n
i
iij
)1((min)max)(
1



n
i
ii
xcxf











)3(),1(0
0
)2(),1(
1
ni
ytuy
x
mjbxa
i
j
n
i
iij
2

CHNG I- BÀI TOÁN QUY HOCH TUYN TÍNH
BÀI 2. CÁC KHÁI NIM C BN
2. Các khái nim liên quan
@ Phng án cabàitoán
@ Tpphng án
@ Tho mãn cht
@ Tho mãn lng






0,,,
12
432
42
4321
432
421
321
xxxx
xxx
xxx
xxx
max32)(
4321




 xxxxxf












0,,,
12
432
42
4321
432
421
321
xxxx
xxx
xxx
xxx
3
5

CHNG I- BÀI TOÁN QUY HOCH TUYN TÍNH
BÀI 2. CÁC KHÁI NIM C BN
2. Các khái nim liên quan
Giih ràng bucca bài toán, ta có tpphng án:
LÀ PACB & LÀ PACB
KHÔNG SUY BN





,
6
7
12
29


X
0







 0,
12
1
,
6
5
,
12
29
0
x
2















14
29
,0,
612
1
,
3
2
6
5
,
6
7
12
29


X

,
6
13
,
12
1
*
x























1
,
6
5
,
12
29
0
x
2







 2,
12
5
,
6
13
,
12
1
*
x



6
5
,
6
7
12
29


X
0







 0,
12
1
,
6
5
,
12
29
0
x
2

0
xf















14
29
,0max
6
7
12
65
)(


xf







14
29
,0max
6
7
12
65
)(


xf







14
29
,0)(
12
65
6
7
12


xf







14
29
,0)(
12
65
6
7
12
65
)(
0


xfxf








65
6
7
12
65
)(
0


xfxf















14
29
,0max
6
7













14
29
,0max
6
7
12
65
)(


xf








29
,0max
6
7
12
65
)(


xf







14
29
,0)(
12
65
6
7
12
65
)(
0







14
29
,0)(
12
65
6
7
12
65
)(
0


xfxf













)(
0


xfxf















14
29
,0max
6
7
12
65
)(










14
29
,0max
6
7
12
65
)(


xf







14
29
,0)(
12
65

65
)(


xf







14
29
,0)(
12
65
6
7
12
65
)(
0


xfxf
4
7

CHNG I- BÀI TOÁN QUY HOCH TUYN TÍNH
















,
612
1
,
3
2
6
5
,
6
7
12
29
X
max


,
612
1
,
3
2
6
5
,
6
7
12
29
X
max
6
7
12
65
)( 

xf




)(xf



12
65
)( 

xf




)(xf















,
612
1
,
3

@ Nu f(x)mincóPA & f(x) b chndi thì có PATU.
Tính cht1:
NucóPA thìs có PACB & s PACB là huhn.
Tính cht3:
Nu có PATU thì có PACBTU
Tính cht4:
Nucóhn1 PATU thìcóvôs PATU.




1,0;)1(
*0


xxx




1,0;)1(
*0


xxx




1,0;)1(