1
1

CHNG I- BÀI TOÁN QUY HOCH TUYN TÍNH
BÀI 3. CÁC DNG C BIT CA BTQHTT
1. BTQHTT dng chính tc (đy đ)
(min)max )(
2211

nn
xcxcxcxf













),1(0

2211
22222121

2211
22222121
11212111
nix
bxaxaxa
bxaxaxa
bxaxaxa
i
mnmnmm
nn
nn
(min)max )(
2211

nn
xcxcxcxf












ii
xcxf









),1(0
),1(
1
nix
mjbxa
i
j
n
i
iji
(II)
(min)max)(
1



n
i
ii









),1(0
),1(
1
nix
mjbxa
i
j
n
i
iji
2
3

CHNG I- BÀI TOÁN QUY HOCH TUYN TÍNH
BÀI 3. CÁC DNG C BIT CA BTQHTT
1. BTQHTT dng chính tc
@ Ma trn điukin & Vector điukin











mi
i
i
i
a
a
a
A

2
1













mnmm

a
a
a
A

2
1













mnmm
n
n
aaa
aaa
aaa
A

CHNG I- BÀI TOÁN QUY HOCH TUYN TÍNH
BÀI 3. CÁC DNG C BIT CA BTQHTT
1. BTQHTT dng chính tc
@ nh lý:
Cho BTQHTT dng chính tcnh dng
(I) hocdng (II), điukincn& đ đ
PA là 1 PACB ca
bài toán là h vector điukin
đclptuyn tính.
), ,,(
**
2
*
1
*
n
xxxx 


0
*

ii
xA
3
5

CHNG I- BÀI TOÁN QUY HOCH TUYN TÍNH
BÀI 3. CÁC DNG C BIT CA BTQHTT
1. BTQHTT dng chính tc

n
i
iji
bxxa 



1
j
n
i
iji
bxa 

1
j
n
i
iji
bxa 

1
jkn
n
i
iji
bxxa 






1
jkn
n
i
iji
bxxa 



1
j
n
i
iji
bxa 

1
j
n
i
iji
bxa 

1
jkn
n
i
iji

xx 
)0(
'

i
x
i
x
'''
iii
xxx 










0
0
''
'
i
i
x
x


'
i
i
x
x
)0(
'

i
x
'''
iii
xxx 
'
ii
xx 
4
7

CHNG I- BÀI TOÁN QUY HOCH TUYN TÍNH
BÀI 3. CÁC DNG C BIT CA BTQHTT
1. BTQHTT dng chính tc
*** CHÚ Ý:
- Bài toán đãchođcgilàBT gc; BT mi
bin đi(cónph) đcgilàiBT ph.
- BT ph có hay không có PATU thì BT gc
cng có hay không có PATU.
- Nu BT ph có PATU thì PATU caBT gcs
đcrútrabng cách bđiphn nph và
đi các tr s cabinmiv các binc theo



0
0,
202
1032
12
722
4
51
4321
543
432
54321
x
xx
xxxx
xxx
xxx
xxxxx
min222)(
54321




 xxxxxxf




xxx
xxxxx
min222)(
54321




 xxxxxxf

















0
0,
202
1032









0
0,
202
1032
12
722
4
51
4321
543
432
54321
x
xx
xxxx
xxx
xxx
xxxxx
5
9

CHNG I- BÀI TOÁN QUY HOCH TUYN TÍNH

''
2
'
22
'
44
xxxxx
xxx
xxx
xx











0,,,,
'
4
''
3
'
3
''
2

''
3
'
3
''
2
'
2
''
3
'
33
''
2
'
22
'
44
xxxxx
xxx
xxx
xx










CHNG I- BÀI TOÁN QUY HOCH TUYN TÍNH
BÀI 3. CÁC DNG C BIT CA BTQHTT
1. BTQHTT dng chính tc
Vd1:
Bin điBT sauv dng chính tc:















0,,,,,,,,,
20)(2)(
103)(2
1)(2)(
72)()(2
mi
n
2)(2)(2)(
8765

''
3
'
3
''
2
'
2
65
'
4
''
3
'
3
''
2
'
21
5
'
4
''
3
'
3
''
2
'
21

8765
'
4
''
3
'
3
''
2
'
21
'
4
''
3
'
3
''
2
'
21
85
'
4
''
3
'
3
7
'

21
xxxxxxxxxx
xxxxxx
xxxxx
xxxxxx
xxxxxxxx
xxxxxxxxf















0,,,,,,,,,
20)(2
)(
103)(2
1)(2)(
72)()(2
mi
n

'
4
''
3
'
3
''
2
'
2
65
'
4
''
3
'
3
''
2
'
21
5
'
4
''
3
'
3
''
2

n
2)(2)(2)(
8765
'
4
''
3
'
3
''
2
'
21
'
4
''
3
'
3
''
2
'
21
85
'
4
''
3
'
3

2
'
21
xxxxxxxxxx
xxxxxx
xxxxx
xxxxxx
xxxxxxxx
xxxxxxxxf
6
11

CHNG I- BÀI TOÁN QUY HOCH TUYN TÍNH
BÀI 3. CÁC DNG C BIT CA BTQHTT
1. BTQHTT dng chính tc
Vd2:
Bin đi BT sau v dng chính tc:


















0,
232
952
4232
max832)(
31
432
321
4321
4321
xx
xxx
xxx
xxxx
xxxxxf





















),1(0
),1;,1(
(min)max)(
1
1
nix
mnjmkbxax
xcxf
i
k
mn
j
jmjkmk
n
i
ii















),1(0
),1;,1(
(min)max)(
1
1
nix
mnjmkbxax
xcxf
i
k
mn
j
jmjkmk
n
i
ii















),1(0
),1;,1(
(min)max)(
1
1
nix
mnjmkbxax
xcxf
i
k
mn
j
jmjkmk
n
i
ii
k
x
k
x
k





mnmmmm
nmm
nmm
aaa
aaa
aaa
A
1 00
0 10
0 01
21
22212
12111


















mnmmmm
nmm
nmm
aaa
aaa
aaa
A
1 00
0 10
0 01
21
22212
12111


















mnmmmm
nmm
nmm
aaa
aaa
aaa
A
1 00
0 10
0 01
21
22212
12111

A chamtma trn đnv cpm
@ Ma trn điukin:
14

CHNG I- BÀI TOÁN QUY HOCH TUYN TÍNH
BÀI 3. CÁC DNG C BIT CA BTQHTT
2. BTQHTT dng chuntc
Vd: Xét BTQHTT sau:
max425)(
4321







xxxxxf











)5,1(0
332
53
72
542
432
421
ix
xxx
xxx
xxx
i
max425)(
4321

4321





xxxxxf











)5,1(0
332
53
72
542
432
421
ix
xxx
xxx
xxx
i


13020
01130
01021
A














13020
01130
01021
A








Vd1: Bin đibàitoánv dng chun
max32)(
4321




 xxxxxf











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

7432
6421
5321
ix
xxxx
xxxx
xxxx
i
max)(32)(
7654321





 xxxMxxxxxf











)7,1(0
12
432

432
42
7432
6421
5321
ix
xxxx
xxxx
xxxx
i
10
19

CHNG I- BÀI TOÁN QUY HOCH TUYN TÍNH
BÀI 3. CÁC DNG C BIT CA BTQHTT
2. BTQHTT dng chuntc
Vd2: Bin đibàitoánv dng chun
min32)(
4321




 xxxxxf







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




)7,1(0
12
432
42
7432
6421
5321
ix
xxxx
xxxx
xxxx
i











)7,1(0
12
432
42

i
11
21

CHNG I- BÀI TOÁN QUY HOCH TUYN TÍNH
BÀI 3. CÁC DNG C BIT CA BTQHTT
2. BTQHTT dng chuntc
Bài toán có dng chunnh sau:
min32)(
84321






Mxxxxxxf











)8,1(0
12

)8,1(0
12
432
42
7432
6421
85321
ix
xxxx
xxxx
xxxxx
i
min32)(
84321






Mxxxxxxf








