Chng I
MT S MÔ HÌNH VÀ PHNG PHÁP TI U
1. Mô hình quy hoch tuyn tính
1.1. Các bc cn thit khi áp dng phng pháp mô hình hoá
− Trc ht phi kho sát, phát hin vn đ cn gii quyt.
− Phát biu các điu kin ràng buc, mc tiêu ca bài toán di dng đnh tính.
Sau đó la chn các bin quyt đnh / các n s và xây dng mô hình đnh lng (còn
gi là mô hình toán hc).
− Thu thp s liu, xác đnh phng pháp gii quyt.
− nh ra quy trình gii / thut gii. Có th gii mô hình bng cách tính toán
thông thng. i vi các mô hình ln, gm nhiu bin và nhiu điu kin ràng buc
cn lp trình và gii mô hình trên máy tính.
− ánh giá kt qu. Trong trng hp phát hin thy có kt qu bt thng hoc kt
qu không phù hp vi thc t, cn kim tra và chnh sa li quy trình gii hoc mô hình.
− Trin khai các phng án tìm đc trên thc t.
Các thut ng sau thng gp khi áp dng phng pháp mô hình hoá:
− ng dng toán / Toán ng dng (Mathematical Applications hay Applied
Mathematics).
− Vn trù hc (Operations Research vit tt là OR).
− Khoa hc qun lí (Management Science vit tt là MS)
1.2. Mô hình quy hoch tuyn tính
Phát biu mô hình
Vi mc đích tìm hiu bc đu, xét mô hình toán hc sau đây, còn gi là mô
hình quy hoch tuyn tính hay bài toán quy hoch tuyn tính (BTQHTT), mà trong đó
chúng ta mun ti u hoá (cc đi hoá hay cc tiu hoá) hàm mc tiêu:
z = c
1
x
1
+ c
2

+ a
22
x
2
+... +a
2n
x
n

≤
b
2
...
a
m1
x
1
+ a
m2
x
2
+... +a
mn
x
n

≤
b
m
x

: z = 8x
1
+ 6x
2
→ Max
c ràng buc:
4x
2x
1
+ 4x
2
≤ 48
x
1
, x
2
≥ 0
giá tr ca cá
m mc tiêu đt giá tr ln nht.
Bài toán này có ý ngha kinh t
hm I và II.  sn xut ra mt đn v sn phm I cn có 4 đn v nguyên liu loi
A và 2 đn v nguyên liu loi B, các ch tiêu đó cho mt đn v sn phm loi II là 2
và 4. Lng nguyên liu d tr loi A và B hin có là 60 và 48 (đn v). Hãy xác đnh
phng án sn xut đt li nhun ln nht, bit li nhun trên mi đn v sn phm bán
ra là 8 và 6 (đn v tin t) cho các sn phm loi I và II.
Phng pháp đ th
Phng pháp đ th có
Bc 1: V min ràng buc / min các phng án kh thi, là tp hp các
i (các phng án, nu nói mt cách ngn gn). Mi phng án đc th hin qua
b s (x

1
+ 4x
2
= 48
x
2
6 15
3
24
A
B
C
Hình Ph áp đ t ii bài toán hoch n tính I.1. ng ph h g quy tuy
th (x
1
= 0, x = 12) và (x = 0, x = 24). Sau đó tìm n
2 2 1 1 2
− Lúc này, giao ca hai na mt phng tìm đc trên cho ta tp hp các đim (x
1
, x
2
)
tho mã
ta ch xét các đim nm trong góc phn t th nht. Vy min các phng án kh
thi là min gii hn bi t giác OABC (còn gi là đn hình vì là min to nên bi giao
ca các na mt phng).
Bc 2: Trong min (OABC) ta tìm đim (x , x ) sao cho
z = 8x
1
+ 6x
2
đt giá tr ln nht.
ng đng đng mc. Tùy theo gi
− V đng đng mc: 8x
1
+ 6x
2
= c  mc c = 24, (ta có th chn giá tr c bt
kì, nhng chn c =
o đ thun li hn). D dàng tìm đc hai đim nm trên đng đng mc này là
(x
1
= 0,

đc x
1
= 12, x
2
= 6 bng cách gii h phng trình 4x
1
+ 2x
2
= 60 và 2x
1
+ 4x
2
= 48).
iên ca
đn h
in phng án.
Kt lun: Trong các phng án kh thi thì phng án ti u là (x
1
= 12, x
2
= 6).
Ti phng án này, giá tr hàm mc tiêu là ln nht z = 8 × 12 + 6 × 6 = 132.
max
Nhn xét: Phng án ti u ca bài toán trên (hay các BTQHTT khác, nu có)
luôn đt đc ti mt trong các đnh ca đn hình hay còn gi là các đim cc b
ình (chính xác hn, đim cc biên là đim thuc đn hình, mà không th tìm đc
mt đon thng nào cng thuc đn hình nhn đim đó là đim trong). Nhn xét trên
đây là mt đnh lí toán hc đã đc chng minh mt cách tng quát. Nói mt cách hình
nh, mun đt đc phng án ti u cho các BTQHTT thì cn phi “mo him” đi xét
các đim cc biên ca min phng án.

Tìm đim cc biên
xut phát
Tìm
đim iên cc b
k tt hn
Kim tra
đi u u kin ti 
In và lu tr kt qu
Dng
úng
Sai
Hình I.2. S đ khi gii BTQHTT

= 60
1 2 4
x
1
, x
2
, x , x
4
≥ 0
Cách lp và bin đi các bng đn hình
cn lp mt s bng đn hình nh trình
bày tr
t 1 là ct h s hàm mc tiêu ng vi các bin c s đã chn. Phng án xut
phát c
phng án) cn ghi các giá tr ca
các b
là các ct h s trong các điu kin ràng buc tng ng vi
các b
Q
rong s đ trên, vì mc đích trình bày vn đ đn gin, chúng ta không đ cp ti
các trng hp khi BTQHTT có min phng án là tp rng (lúc đó ta không tìm đc
phng án xut phát) cng nh khi ta không tìm đc đim cc biên k tt hn mc dù
điu kin ti u cha tho mãn (lúc đó tp các giá tr hàm mc tiêu z không b chn).
ây là phng pháp s gi
húng ta cn đa BTQHTT v dng chính tc bng cách thêm vào các bin bù
không âm x
3
và x
4
nh sau:

− Ct 2 là ct các bin c s. Trong ct 3 (ct
in c s đã chn.
− Các ct tip theo
in x
1
, x
2
, x
3
và x
4
ca bài toán đã cho.
Bng I.1. Các bng đn hình gii BTQHTT
c
1
= 8 c
2
= 6 c
3
= 0 c
4
= 0
H s hàm
mc tiêu c
j
Bin c
s
Phng
án
x

3
= 0 z
4
= 0
Hàng ∆
j
= c
j
− z
j

∆
1
= 8 ∆
2
= 6 ∆
3
= 0 ∆
4
= 0
8
0
x
1
x
4
15
18
1
0

= −2 ∆
4
= 0
8
6
x
1
x
2
12
6
1
0
0
1
1/3
−1/6
−1/6
1/3
Hàng z z
0
= 132 8 6 5/3 2/3
Hàng ∆
j
= c
j
− z
j
0 0
−5/3 −2/3

(ct h s ca hàm mc tiêu) × (ct h s ca bin x
1
) = 0×4 + 0×2 = (giá mt đn v
sn phm loi III)×(t l thay th riêng loi I / loi III) + (giá mt đn v sn phm loi
IV) × (t l thay th riêng loi I / loi IV) = tng chi phí phi b ra khi đa thêm mt
đn v sn phm loi I vào phng án sn xut mi = 0. Các giá tr z
j
, vi j = 1, 2, 3, 4,
đc tính tng t và chính là các chi phí khi đa mt thêm mt đn v sn phm loi
x
j
vào phng án sn xut mi. Còn z
0
là giá tr ca hàm mc tiêu đt đc ti phng
án đang xét: z
0
= (ct h s ca hàm mc tiêu)× (ct phng án) = 0×60 + 0×48 = 0.
− Trên hàng ∆
j
cn ghi các giá tr ∆
j,
j = 1, 2, 3, 4, tính theo công thc ∆
j
= c
j
–z
j
= li nhun trên mt đn v sn phm – chi phí trên mt đn v sn phm. Vy ∆
j
là

làm bin c s mi do
x
j
tng kéo theo hàm mc tiêu tng.  đây ta chn đa x
1
vào (đánh du √  ct ∆
1
).
Bc 2: Chn hàng xoay đ xác đnh đa bin nào ra khi s bin c s (vì ti
mi bc s bin c s là không thay đi).  chn hàng xoay, ta thc hin quy tc “t
s dng bé nht" bng cách ly ct phng án (60 48)
T
chia tng ng cho ct xoay (4
2)
T
đ chn t s bé nht. Mt điu cn chú ý là ta ch xét các t s có mu s dng.
Vì Min{60/4, 48/2} = 60/4 đt đc ti hàng đu, nên ta đánh du √ vào hàng
xoay là hàng đu (hàng tng ng vi bin x
3
). Do đó cn đa x
3
ra khi các bin c
s.
Bc 3: Chn phn t xoay nm trên giao ca hàng xoay và ct xoay.
Bc 4: Xoay sang bng đn hình mi, xác đnh các bin c s mi đ đin vào
ct bin c s, đng thi thay các giá tr trong ct h s hàm mc tiêu. Sau đó, tính li
các phn t ca hàng xoay bng cách ly hàng xoay c chia cho phn t xoay đ có
hàng mi tng ng.
Bc 5: Các phn t còn li ca bng đn hình mi đc tính theo quy tc "hình
ch nht": (1)

= phn t xoay = 4, (4)
c
= 2
⇒ (1)
mi
= 4 − 2 ×
4
2
= 3.

Hình I.3. Quy tc hình ch nht

Gii thích: Các bc xoay trên đây ch là phép bin đi tng đng h phng
trình
4x
1
+ 2x
2
+ x
3
= 60 (a)
2x
1
+ 4x
2
+ x
4
= 48 (b)
đ có h
x

Phân tích bng đn hình bc 2
Bng bc 2 có th đc phân tích tng t nh bng bc 1. Cn chú ý rng lúc
này ta đang  v trí ca đim C(15, 0) vì x
1
= 15 còn x
2
= 0; giá tr ca hàm mc tiêu là
z
0
= 120 đã đc ci thin hn so vi bc 1. Ta thy ∆
2
= 2 > 0 nên còn có th ci
thin hàm mc tiêu bng cách chn bin x
2
làm bin c s mi. Thc hin các bc
xoay sang phng án cc biên k tt hn, chúng ta s có bng đn hình bc 3.
Phân tích bng đn hình bc 3
Ti bng đn hình bc 3 ta thy điu kin ti u đã đc tho mãn (
∆
j

≤
0
∀
j=1, 2, 3, 4) nên không còn kh nng ci thin phng án. Phng án ti u đã đt đc
ti x
1
= 12, x
2
= 6, x

ta dùng phn mm Lingo đ gii ví d đã xét  trên.
z = 8x
1
+ 6x
2
→ Max
vi các ràng buc:
4x
1
+ 2x
2
≤
60
2x
1
+ 4x
2
≤
48
x
1
, x
2
≥ 0.
 gii bài toán này, chúng ta cn cài đt Lingo vào trong máy tính. Nhn vào
biu tng Lingo trên màn hình đ vào ca s Lingo. Sau đó thc hin các lnh Lingo:
Menu > New > <Untitle> và gõ vào các d liu ca bài toán nh hình I.4.

Hình I.4. Nhp d liu ca bài toán quy hoch tuyn tính trong Lingo
Tip theo, cn nháy chut vào nút LINGO và gii bài toán đ thu đc kt qu chi

và B
3
. Gi x
ij
là lng đin
nng đc đa t ngun i ti h tiêu th j. Cn phi xác đnh các x
ij
sao cho tng chi
phí là nh nht. Nh vy ta có BTQHTT sau:
z = → Min
23
ij ij
i1 j1
cx
==
∑∑
vi các điu kin ràng buc là:
x
11
+ x
12
+ x
13
≤ A
1
,
x
21
+ x
22

đn hình đã bit hay phng pháp phân phi s đc nghiên cu  mc 1.3, chng II.
Bài toán phân ti cho máy
Mt xí nghip có hai loi máy M
1
và M
2
. Các loi máy này có th sn xut đc ba
loi sn phm P
1
, P
2
và P
3
vi các nng sut là a
ij,
chng hn máy M
1
sn xut sn phm
P
2
vi nng sut a
12
. Mi đn v sn phm mang li lãi sut c
j
vi j = 1, 2, 3. Mi tháng xí
nghip phi sn xut sn phm loi j không ít hn b
j
đn v và không vt quá d
j
đn v,

22
≥ b
2
,
a
13
x
13
+ a
23
x
23
≥ b
3
,
a
11
x
11
+ a
21
x
21
≤ d
1
,
a
12
x
12

22
+ x
23
≤ m
2
,
x
ij
≥ 0, i = 1, 2 và j = 1, 2, 3.
(trong đó m
1
và m
2
là tng thi gian chy máy M
1
và M
2
).
Bài toán trên đây còn có th phát biu mt cách tng quát hn và vn gii đc
bng phng pháp đn hình. Hn na, trong lnh vc quy hoch sn xut hay qun lí
kinh doanh, nói riêng trong ngành c khí và đin lc, BTQHTT đc ng dng rt rng
rãi và mang li hiu qu cn thit.
2. B sung thêm v phng pháp đn hình
2.1. a BTQHTT v dng chính tc
Ví d 1: (Trng hp các ràng buc đu có du ≤)
z = 8x
1
+ 6x
2
→

+ 0x
4
→ Max
123
124
1234
4x 2x x 60
2x 4x x 48
x,x,x,x 0
++=
⎧
⎪
++=
⎨
⎪
≥
⎩

Lúc này, trong h hai điu kin ràng buc đã có đ hai bin đng đc lp trong
tng phng trình vi h s +1, nên đã có th tìm đc phng án cc biên xut phát đ
bt đu quá trình gii bài toán. Mt cách tng quát, BTQHTT dng chính tc là bài toán
vi các bin không âm, các ràng buc vi du “=”, h s v phi ca các ràng buc
không âm. Ngoài ra, mi phng trình bt buc phi có mt bin đng đc lp vi h s
+1.
Ví d 2: (Trng hp có điu kin ràng buc vi du ≥)
z = 8x
1
+ 6x
2
→ Max

⎪
+−=
⎨
⎪
≥
⎩

Phi thêm bin gi x
5
(x
5
gi là lng vi phm ca phng trình th hai) đ đc
h điu kin ràng buc
⎪
⎩
⎪
⎨
⎧
≥
=+−+
=++
0x,x,x,x,x
48xxx4x2
60xx2x4
54321
5421
321

Lúc này, đã có đ hai bin đng đc lp trong tng phng trình vi h s +1,
nên đã có th tìm đc phng án cc biên xut phát đ bt đu quá trình gii bài toán

4x 2x x 60
2x 4x x 48
x 0,x 0,x 0,x 0
++≤
⎧
⎪
+−=
⎨
⎪
≥≤≥≥
⎩

Lúc này mun gii bài toán bng phng pháp đn hình ta phi đi bin x'
2
= −x
2
.
Ta có BTQHTT vi các bin đu không âm.
z = 8x
1
+ 6x'
2
→ Max
vi các ràng buc:
123
124
1234
4x 2x' x 60
2x 4x' x 48
x,x',x,x 0


du tu ý
Lúc này ta vit bin x
2
di dng x
2
= x'
2
− x''
2
vi
2
22
x' max[0,x ]
x'' max[0, x ]
=
⎧
⎨
=−
⎩
2
thì đm bo
2
2
x' 0
x'' 0
≥
⎧
⎨
≥

Kt lun: Bao gi cng đa đc BTQHTT bt kì (các bin có du tu ý, các
ràng buc có th ≤, ≥, =) v dng chính tc.
2.2. Phng pháp đn hình m rng
Phng pháp đn hình m rng còn gi là phng pháp đánh thu M đc áp
dng đ đ gii BTQHTT có bin gi.
Ví d:
z = 8x
1
+ 6x
2
→ Max
vi các ràng buc: