1
1

CHNG I- BÀI TOÁN QUY HOCH TUYN TÍNH
BÀI 5. GII BTQHTT BNG PP N HÌNH
Ni dung c bnca PP đnhình
2

CHNG I- BÀI TOÁN QUY HOCH TUYN TÍNH
BÀI 5. GII BTQHTT BNG PP N HÌNH
Xét BT QHTT dng chuntcnh sau:
(min)max)(
1



n
i
ii
xcxf










);,1;,1(0,0

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

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

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

j
jkmjk
2
3

CHNG I- BÀI TOÁN QUY HOCH TUYN TÍNH
BÀI 5. GII BTQHTT BNG PP N HÌNH
1. clng ca n:
PACB XP:
hay
VihnCB:
x
1
, x
2
, …, x
m
)0,,0,,,,(
00
2
0
1
0

m
xxxx 
)0,,0,,,,(
21
0


m
bbbx 
)0,,0,,,,(
00
2
0
1
0

m
xxxx 
)0,,0,,,,(
21
0

m
bbbx 
)0,,0,,,,(
00
2
0
1
0

m
xxxx 
)0,,0,,,,(
21
0




),1(
1
nmlcac
l
m
k
klkl



cgilàh sclng ca nx
l
.
4

CHNG I- BÀI TOÁN QUY HOCH TUYN TÍNH
BÀI 5. GII BTQHTT BNG PP N HÌNH
2. Duhiuti uca bài toán
Có PATU
Có PATU
max)(
1



n
i
ii

1



n
i
ii
xcxf
l


nml
l
,10 

nml
l
,10 
max)(
1



n
i
ii
xcxf
min)(
1


b) Nuvimih sclng mà tntiítnhtmt
thì bài toán có phng án c bnmitthn.
CHNG I- BÀI TOÁN QUY HOCH TUYN TÍNH
BÀI 5. GII BTQHTT BNG PP N HÌNH
3. nh lý c bn
0
l
0
l
0
l
0


l
0


l
0


l
0

kl
a
0

kl

BÀI 5. GII BTQHTT BNG PP N HÌNH
4. Thuttoánđnhìnhgii BTQHTT dng chuntc
A. GiiBT cc đi
a) Bclpth nht
Các thành phnca BDH bao gm:
+ Ct B: Ghi lnlt theo th t các nCB caBT.
+ Ct A: Ghi tng ng các h s cacácnCB trongHMT.
+ Ct C: Ghi các s hng t do tng ng vicácnCB.
+ Ct D: Ghi ma trn điukincah ràng bucchính.
+ Hàng E: Ghi toàn b các nca BT trong HMT.
+ Hàng F: Ghi h s tng ng cacác
n trong HMT.
8

CHNG I- BÀI TOÁN QUY HOCH TUYN TÍNH
BÀI 5. GII BTQHTT BNG PP N HÌNH
4. Thuttoánđnhìnhgii BTQHTT dng chuntc
A. GiiBT cc đi
a) Bclpth nht
Các thành phnca BDH bao gm:
+ Hàng G: Tính tr s cacách sclng (HSUL) các
nvàtr s caHMT:



m
i
jiij
cxc
1

+ Nuttc các HSUL đu không âm thì PACB xut
phát đang xét là PATU ca BT. Và thut toán kt thúc.
+ Nutntiítnht 1 HSUL âm ca n không CB mà
vector điukinca n đócha các thành phn đu
không dng thì bài toán không gii đc. Thut toán
kt thúc viktlun bài toán không có PATU.
+ Nu không xy ra 2 trng hptrênthìtasđixây
dng 1 PACB mitthn. Và ta ti
ptcthut toán vi
bclpth 2.
10

CHNG I- BÀI TOÁN QUY HOCH TUYN TÍNH
BÀI 5. GII BTQHTT BNG PP N HÌNH
4. Thuttoánđnhìnhgii BTQHTT dng chuntc
A. GiiBT cc đi
b) Bclpth hai
6
11

b.1) Tìm n đa vào:
Ta tìm HSUL âm nh nht trong BDH hinti,
gi s là thì n x
m+k
sđcchn đa
vào hnCB mica BDH th hai. Khi đó, ct
điukin A
m+k
= (a
1m+k

trong bng đnhìnhtrênthìnólàa
rm+k
.
CHNG I- BÀI TOÁN QUY HOCH TUYN TÍNH
BÀI 5. GII BTQHTT BNG PP N HÌNH
4. Thuttoánđnhìnhgii BTQHTT dng chuntc
A. GiiBT cc đi
b) Bclpth hai


mi
a
b
kim
i
i
,1




mi
a
b
kim
i
i
,1



đcxácđnh bng (và d nhiên, h s cacác
nc bn khác luôn bng 0).
CHNG I- BÀI TOÁN QUY HOCH TUYN TÍNH
BÀI 5. GII BTQHTT BNG PP N HÌNH
4. Thuttoánđnhìnhgii BTQHTT dng chuntc
A. GiiBT cc đi
b) Bclpth hai
14

b.3) Lpbng đnhìnhth hai:
- ivi dòng i btk, ta tính h s cacácn không
c bnnh sau:
CHNG I- BÀI TOÁN QUY HOCH TUYN TÍNH
BÀI 5. GII BTQHTT BNG PP N HÌNH
4. Thuttoánđnhìnhgii BTQHTT dng chuntc
A. GiiBT cc đi
b) Bclpth hai
krm
r
kimi
d
i
a
b
abb






b
abb




mi
a
a
aaa
krm
jrm
kimjim
d
jim
,1



-Cách sclng và giá tr hàm mctiêuđc
tính nh bclpth nht.
16

b.3) Lpbng đnhìnhth hai: Vd v cách tính
CHNG I- BÀI TOÁN QUY HOCH TUYN TÍNH
BÀI 5. GII BTQHTT BNG PP N HÌNH
4. Thuttoánđnhìnhgii BTQHTT dng chuntc
A. GiiBT cc đi
b) Bclpth hai
d

thchintng t nh bcl
pth hai. Nhng các
h s trong ma trn điukinvàcács hng t do ca
BDH sau đctínhda vào ma trn điukinvàcác
s hng t do cabng đn hình ngay trcnó.
10
19

CHNG I- BÀI TOÁN QUY HOCH TUYN TÍNH
BÀI 5. GII BTQHTT BNG PP N HÌNH
4. Thuttoánđnhìnhgii BTQHTT dng chuntc
A. GiiBT cc đi
***** CHÚ Ý:
+ Nu các HSUL cacácn không CB trong BDH
cui cùng đudng thì BT ch có duy nht 1
PACBTU- đólàPACBTU va tìm đc trong BDH
cui cùng.
+ NucácHSUL cacácn không CB trong
BDH cui cùng đu không âm, và tntiítnht
1 HSUL ca n không CB bng 0 thì BT s có
vô s PATU:




1,0;)1(
*0


xxx

t BT ph bng cách bđiphn nph
và đicáctr s cabinmiv binc
theo các công thc đibin đã dùng.
11
21

CHNG I- BÀI TOÁN QUY HOCH TUYN TÍNH
BÀI 5. GII BTQHTT BNG PP N HÌNH
4. Thuttoánđnhìnhgii BTQHTT dng chuntc
B. GiiBT cctiu
@ BT cctiucng đcgiitng t nh BT
cc đinhng cnchúý đn HSUL trong BT cc
tiunh sau:
+ iukinti ucaBT cctiulà:
+ iukin BT không gii đclàtntiítnht1
HSUL ca n không CB dng và các thành phn
cavector điukintng ng ca n đó đu
không dng; tclà
+ n đcchn đavàolàn ng viHSUL
dng lnnht.
j
j



,0
j
j



theo BT cc đi f(x) vicáchbin điHMT t
cctiu sang cc đi:
)()( xfxg


)()( xfxg


)()( xfxg


12
23

CHNG I- BÀI TOÁN QUY HOCH TUYN TÍNH
BÀI 5. GII BTQHTT BNG PP N HÌNH
5. Các ví d v gii BTQHTT bng PP nhình
5.1) GiiBT saubng PP đn hình:
max34)(
321



 xxxxf











0,,
122
824
1622
321
321
31
321
xxx
xxx
xx
xxx
max34)(
321



 xxxxf











0,,
122
824
1622
321
321
31
321
xxx
xxx
xx
xxx
24

CHNG I- BÀI TOÁN QUY HOCH TUYN TÍNH
BÀI 5. GII BTQHTT BNG PP N HÌNH
5. Các ví d v gii BTQHTT bng PP nhình
GiiBT víd 5.1:
a bài toán trên v dng chunnh sau:
max34)(
321



 xxxxf





CHNG I- BÀI TOÁN QUY HOCH TUYN TÍNH
BÀI 5. GII BTQHTT BNG PP N HÌNH
5. Các ví d v gii BTQHTT bng PP nhình
GiiBT víd 5.1:
26

CHNG I- BÀI TOÁN QUY HOCH TUYN TÍNH
BÀI 5. GII BTQHTT BNG PP N HÌNH
5. Các ví d v gii BTQHTT bng PP nhình
GiiBT víd 5.1:
Sau bclpth ba, ta có HSUL ca nx
1
(là
n không CB) là -7 trong khi vector điukin
ca nnàyđu có thành phnâm; chonênBT
ph không gii đc và do đó, BT gccng
không gii đc(BT khôngcóPATU).
14
27

CHNG I- BÀI TOÁN QUY HOCH TUYN TÍNH
BÀI 5. GII BTQHTT BNG PP N HÌNH
5. Các ví d v gii BTQHTT bng PP nhình
5.2) GiiBT saubng PP đnhình
min325)(
4321








xxxxxf












4,10
2123
38324
14232
31
321
4321
ix
xx
xxx
xxxx
i
min325)(

i
min325)(
4321





xxxxxf












4,10
2123
38324
14232
31
321
4321
ix
xx

2123
38324
14234
731
6321
54321
ix
xxx
xxxx
xxxxx
i
min325)(
4321




 xxxxxf














7,10
2123
38324
14234
731
6321
54321
ix
xxx
xxxx
xxxxx
i
min325)(
4321




 xxxxxf











GiiBT víd 5.2:
30

CHNG I- BÀI TOÁN QUY HOCH TUYN TÍNH
BÀI 5. GII BTQHTT BNG PP N HÌNH
5. Các ví d v gii BTQHTT bng PP nhình
GiiBT víd 5.2:
Tibclpth ba, ta có ttc các HSUL
đu không dng cho nên kt thúc thut toán
đn hình. Khi đó, BT gc có PATU là:
x* = (0, 118/13, 86/13, 0);
Tr s HMT đt đclà: f(x*) = -38.
16
31

CHNG I- BÀI TOÁN QUY HOCH TUYN TÍNH
BÀI 5. GII BTQHTT BNG PP N HÌNH
5. Các ví d v gii BTQHTT bng PP nhình
5.3) GiiBT saubng PP đnhình
max42325)(
4321






xxxxxf








xxxxxf














0
0,,
542
4522
14234
2
431
4321
54321
4321

542
4522
14234
2
431
4321
54321
4321
x
xxx
xxxx
xxxxx
xxxx
max42325)(
4321






xxxxxf























0
0,,
542
4522
14234
2
431
4321
54321
4321
x
xxx
xxxx
xxxxx
xxxx
32

bng cách đt:
max42325)(
4321




 xxxxxf
a















0,,
8,7,6,4,3,10
542
4522
14234
552







0,,
8,7,6,4,3,10
542
4522
14234
552
84321
7554321
64321
baa
i
a
baa
a
xxx
ix
xxxxx
xxxxxxx
xxxxx
max42325)(
4321




baa
a
xxx
ix
xxxxx
xxxxxxx
xxxxx
max42325)(
4321




 xxxxxf
a

















CHNG I- BÀI TOÁN QUY HOCH TUYN TÍNH
BÀI 5. GII BTQHTT BNG PP N HÌNH
5. Các ví d v gii BTQHTT bng PP nhình
GiiBT víd 5.3:
34

CHNG I- BÀI TOÁN QUY HOCH TUYN TÍNH
BÀI 5. GII BTQHTT BNG PP N HÌNH
5. Các ví d v gii BTQHTT bng PP nhình
GiiBT víd 5.3:
Tibclpth hai, ttc các HSUL ca n
đu không âm. Nh vy, BT ph có PACBTU
là x
s
= (0, 0, 0, 5/4, 41/4, 0, 33/2, 0, 0) vitr
s HMT là f(x) = 25 + 5/4 = 105/4. Khi đó, BT
gcs có PATU là: x* = (0, 0, 0, 5/4, 41/4) và
tr s HMT vnlàf(x*) = 105/4.
18
35

CHNG I- BÀI TOÁN QUY HOCH TUYN TÍNH
BÀI 5. GII BTQHTT BNG PP N HÌNH
Kinh nghimgii toán:
@ Nutacó nhiuhn1 n đcchn đa
vào hnCB-tc là có nhiuhn 1 HSUL âm
bé nht(BT cc đi) hocHSUL dng lnnht
(BT cctiu)- thì ta s chn nnàođây???
@ Nutacó nhiuhn1 n đcchn đa

baM


 baM



A. GII BT M RNG- BT “M”
38

CHNG I- BÀI TOÁN QUY HOCH TUYN TÍNH
BÀI 5. GII BTQHTT BNG PP N HÌNH
6. Thuttoánđnhìnhm rng giiBT “M”
@ Do M là mts dng vô cùng ln, cho
nên, trên BDH, duca HSUL ph thuc
vào h s a ca M trong HSUL đó. Vicso
sánh giá tr ca hai HSUL cn tuân theo qui
tc sau:
-H s a caM s quyt đnh chính; tclà
nu a
1
> a
2
thì btk giá tr b.
-Nuh s a bng nhau thì h s b s
quyt đnh; tclànu b
1
< b
2
thì .

@ Khi trong hn CB không còn ngi thì
BT “M” tr thành BTQHTT thông thng.
TÌM LI GII CA BT GC
40

CHNG I- BÀI TOÁN QUY HOCH TUYN TÍNH
BÀI 5. GII BTQHTT BNG PP N HÌNH
6. Thuttoánđnhìnhm rng giiBT “M”
BT “M” và BT gccómi quan h nh sau:
@ Nu BT “M” không gii đc (không có PATU)
thì BT gccng không gii đc.
@ Nu BT “M” có PATU nhng tntiítnht1
ngi có giá tr dng thì BT gc không gii
đc (không có PATU).
@ Nu BT “M” có PATU và các ngiđunhn
giá tr 0 thì BT gcgii đc. PATU caBT “M”
sau khi bđiphn ngi và thay thnph (nu
có) s là PATU caBT gc.
B. TÌM LI GII CA BT GC
21
41

CHNG I- BÀI TOÁN QUY HOCH TUYN TÍNH
BÀI 5. GII BTQHTT BNG PP N HÌNH
7. Các ví d giiBT “M”
7.1) Gii bài toán sau bng phng pháp đnhình
min32)(
4321








xxxxxf












4,10
7
6232
22
4321
4321
4321
ix
xxxx
xxxx
xxxx
i

xxxx
i
min32)(
4321





xxxxxf












4,10
7
6232
22
4321
4321
4321
ix










7,10
7
6232
22
74321
64321
54321
ix
xxxxx
xxxxx
xxxxx
i
min32)(
7654321





 MxMxMxxxxxxf


 MxMxMxxxxxxf












7,10
7
6232
22
74321
64321
54321
ix
xxxxx
xxxxx
xxxxx
i
min32)(
7654321




CHNG I- BÀI TOÁN QUY HOCH TUYN TÍNH
BÀI 5. GII BTQHTT BNG PP N HÌNH
7. Các ví d giiBT “M”
Gii bài toán ví d 7.1:
BT “M” có PACB xut phát là x
0
= (0, 0, 0, 0, 2, 6, 7)
vihnCB làx
5
, x
6
và x
7
.
2
0
44

CHNG I- BÀI TOÁN QUY HOCH TUYN TÍNH
BÀI 5. GII BTQHTT BNG PP N HÌNH
7. Các ví d giiBT “M”
Gii bài toán ví d 7.1:
Tibclpth 4, toàn b HSUL cacácn
đu không dng cho nên bài toán “M” có
PATU là x
M
= (21/10, 0, 8/5, 33/10, 0, 0, 0). Và
các ngiđucógiátr bng 0 cho nên BT gc
có PATU là x* = (21/10, 0, 8/5, 33/10) và HMT
đttr s f(x*) = 27/10.

min3)(
321


 xxxxf









3,10
12
232
321
321
ix
xxx
xxx
i
min3)(
321


 xxxxf



3,10
12
232
321
321
ix
xxx
xxx
i
46

CHNG I- BÀI TOÁN QUY HOCH TUYN TÍNH
BÀI 5. GII BTQHTT BNG PP N HÌNH
7. Các ví d giiBT “M”
Gii bài toán ví d 7.2
H ràng buc chính chacónCB chonêntatin hành
thêm 2 ngi x
4
và x
5
vào h ràng buc chính và ta có
BT “M” nh sau:
min3)(
54321




 MxMxxxxxf





5,10
12
232
5321
4321
ix
xxxx
xxxx
i
min3)(
54321




 MxMxxxxxf









5,10
12

+1/2
+5/2
48

CHNG I- BÀI TOÁN QUY HOCH TUYN TÍNH
BÀI 5. GII BTQHTT BNG PP N HÌNH
7. Các ví d giiBT “M”
7.3) Gii bài toán sau bng phng pháp đnhình:
max42)(
321


 xxxxf












4,10
6
353
5432
421

321
ix
xxx
xxx
xxx
i
max42)(
321


 xxxxf












4,10
6
353
5432
421
321
321

xxx
xxx
xxx
i
max42)(
321


 xxxxf












4,10
6
353
5432
421
321
321
ix
xxx



6,10
6
353
5432
421
6321
5321
ix
xxx
xxxx
xxxx
i
max42)(
321


 xxxxf












6,10
6
353
5432
421
6321
5321
ix
xxx
xxxx
xxxx
i
max42)(
321


 xxxxf












6,10









8,10
6
353
5432
8421
76321
5321
ix
xxxx
xxxxx
xxxx
i
max42)(
87321




 MxMxxxxxf














8,10
6
353
5432
8421
76321
5321
ix
xxxx
xxxxx
xxxx
i
max42)(
87321




 MxMxxxxxf


và x
8
.