Ví dụ về phương pháp kinh tế I Đại học Vinh

Ví dụ về phương pháp kinh tế của Đại học Vinh, tài liệu gồm 14 trang giúp bạn tham khảo, ôn tập và đạt kết quả cao. Mời bạn đọc đón xem!

Chương I
MT S MÔ HÌNH VÀ PHNG PHÁP TI U
1. Mô hình quy hoch tuyến tính
1.1. Các bước cn thiết khi áp dng phương pháp mô hình hoá
Trước hết phi kho sát, phát hin vn đề cn gii quyết.
Phát biu các điu kin ràng buc, mc tiêu ca bài toán dưới dng định tính.
Sau đó la chn các biến quyết định / các n s và xây dng mô hình định lượng (còn
gi là mô hình toán hc).
Thu thp s liu, xác định phương pháp gii quyết.
Định ra quy trình gii / thut gii. Có th gii mô hình bng cách tính toán
thông thưng. Đối vi các mô hình ln, gm nhiu biến và nhiu điu kin ràng buc
cn lp trình và gii mô hình trên máy tính.
Đánh giá kết qu. Trong trưng hp phát hin thy có kết qu bt thưng hoc kết
qu không phù hp vi thc tế, cn kim tra và chnh sa li quy trình gii hoc mô hình.
Trin khai các phương án tìm được trên thc tế.
Các thut ng sau thưng gp khi áp dng phương pháp mô hình hoá:
ng dng toán / Toán ng dng (Mathematical Applications hay Applied
Mathematics).
Vn trù hc (Operations Research viết tt là OR).
Khoa hc qun lí (Management Science viết tt là MS)
1.2. Mô hình quy hoch tuyến tính
Phát biu mô hình
Vi mc đích tìm hiu bước đầu, xét mô hình toán hc sau đây, còn gi là mô
hình quy hoch tuyến tính hay bài toán quy hoch tuyến tính (BTQHTT), mà trong đó
chúng ta mun ti ưu hoá (cc đại hoá hay cc tiu hoá) hàm mc tiêu:
z = c
1
x
1
+ c
2
x
2
+ c
n
x
n
Max (Min)
vi các điu kin ràng buc:
a
11
x
1
+ a
12
x
2
+... +a
1n
x
n
b
1
a
21
x
1
+ 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
1
, x
2
,..., x
n
0 (điu kin không âm)
Ví d
vi cá
1
+ 2x
2
60
Cn tìm c các biến quyết định x
1
, x
2
để các ràng buc được thon
và hà
ế như sau: Gi s mt xí nghip sn xut hai loi
sn p
ý nghĩa minh ho và giúp hiu bn cht vn đề.
phương án
kh th
Trước hết chúng ta v đồ th 4x
1
+ 2x
2
= 60 bng cách xác định hai đim trên
đồ th
: z = 8x
1
+ 6x
2
Max
c ràng buc:
4x
2x
1
+ 4x
2
48
x
1
, x
2
0
giá tr ca
m mc tiêu đạt giá tr ln nht.
Bài toán này có ý nghĩa kinh t
hm I và II. Để sn xut ra mt đơn v sn phm I cn có 4 đơn v nguyên liu loi
A và 2 đơn v nguyên liu loi B, các ch tiêu đó cho mt đơn v sn phm loi II là 2
và 4. Lượng nguyên liu d tr loi A và B hin có là 60 và 48 (đơn v). Hãy xác định
phương án sn xut đạt li nhun ln nht, biết li nhun trên mi đơn v sn phm bán
ra là 8 và 6 (đơn v tin t) cho các sn phm loi I và II.
Phương pháp đồ th
Phương pháp đồ th
Bước 1: V min ràng buc / min các phương án kh thi, là tp hp các
i (các phương án, nếu nói mt cách ngn gn). Mi phương án được th hin qua
b s (x
1
, x
2
) còn gi là véc tơ nghim, tho mãn tt c các ràng buc đã có (xem hình
I.1).
: (x
1
= 0, x
2
= 30) và (x
2
= 0, x
1
= 15).
30
4x
1
+ 2x
2
= 60
O
4
8
12
x
1
2x
1
+ 4x
2
= 48
x
2
6 15
3
24
A
B
C
Hình Phư áp đồ t ii bài toán hoch ến tính I.1. ơng ph h g quy tuy
Đồ th trên là mt đưng thng chia mt phng làm hai na mt phng: mt phn
gm các đim (x , x ) tho mãn 4x + 2x 60; mt phn tho mãn 4x + 2x 60. Ta
tìm đ
a mt phng tho mãn 2x + 4x
48.
n hai ràng buc đầu tiên. Tuy nhiên, để tho mãn điu kin không âm ca các
biến,
1 2
Cách 1: á tr ca x
1
, x
2
mà z có nhng mc
giá tr khác nhau.
24 là bi s chung ca 6 và 8 để vic tìm to độ các đim ct hai
trc t
= 6). Chúng ta nhn thy, nếu tnh tiến song song đưng đồng
mc l
1 2 1 2 1 2
ược na mt phng tho mãn 4x
1
+ 2x
2
60.
Tương t, có th v đồ th 2x
1
+ 4x
2
= 48 bng cách xác định hai đim thuc đồ
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 ca hai na mt phng tìm được trên cho ta tp hp các đim (x
1
, x
2
)
tho
ta ch xét các đim nm trong góc phn tư th nht. Vy min các phương án kh
thi là min gii hn bi t giác OABC (còn gi là đơn hình vì là min to nên bi giao
ca các na mt phng).
Bước 2: Trong min (OABC) ta tìm đim (x , x ) sao cho
z = 8x
1
+ 6x
2
đạt giá tr ln nht.
ng đường đồng mc. Tùy theo gi
V đưng đồng mc: 8x
1
+ 6x
2
= c mc c = 24, (ta có th chn giá tr c bt
kì, nhưng chn c =
o độ thun li hơn). D dàng tìm được hai đim nm trên đưng đồng mc này là
(x
1
= 0,
x
2
= 4) và (x
2
= 0, x
1
= 3). Các đim nm trên đưng đồng mc này đều cho giá tr hàm
mc tiêu z = 24.
Tương t, có th v đưng đồng mc th hai: 8x
1
+ 6x
2
= 48 đi qua hai đim (x
1
=
0, x
2
= 8) và (x = 0, x
2 1
ên trên theo hướng ca véc tơ pháp tuyến
n
r
(8, 6) thì giá tr ca hàm mc tiêu z = 8x
1
+
6x
2
tăng lên.
Vy giá tr z ln nht đạt được khi đưng đồng mc đi qua đim B(12, 6) (tìm
được x
1
= 12, x
2
= 6 bng cách gii h phương trình 4x
1
+ 2x
2
= 60 và 2x
1
+ 4x
2
= 48).
iên ca
đơn h
in phương án.
Kết lun: Trong các phương án kh thi thì phương án ti ưu là (x
1
= 12, x
2
= 6).
Ti phương án này, giá tr hàm mc tiêu là ln nht z = 8 × 12 + 6 × 6 = 132.
max
Nhn xét: Phương án ti ưu ca bài toán trên (hay các BTQHTT khác, nếu có)
luôn đạt được ti mt trong các đỉnh ca đơn hình hay còn gi là các đim cc b
ình (chính xác hơn, đim cc biên là đim thuc đơn hình, mà không th tìm được
mt đon thng nào cũng thuc đơn hình nhn đim đó là đim trong). Nhn xét trên
đây là mt định lí toán hc đã được chng minh mt cách tng quát. Nói mt cách hình
nh, mun đạt được phương án ti ưu cho các BTQHTT thì cn phi “mo him” đi xét
các đim cc biên ca min phương án.
Cách 2: T nhn xét trên, để tìm phương án ti ưu ta ch cn so sánh giá tr ca
hàm mc tiêu ti các đim cc biên ca m
Tính giá tr z ti O(0, 0): z(0, 0) = 0; ti A(0, 12): z(0, 12) = 72; ti C(15,0): z(15,
0) = 1
c
biên n
i BTQHTT đang xét, quy trình gii được minh ho như sau:
hoc:
O(0, 0) C(15, 0) B(12, 6) dng
Sơ đồ khi
20; ti B(12, 6): z(12, 6) = 132 = Max{z(O), z(A), z(B), z(C)}. Vy z
max
= 132.
Nhn xét: Mun tìm phương án ti ưu ca BTQHTT ta xut phát t mt đim c
ào đó, tìm cách ci thin hàm mc tiêu bng cách đi ti đim cc biên k nó. Tiếp
tc như vy cho ti khi tìm được phương án ti ưu. Trong trưng hp BTQHTT có
phương án ti ưu thì quy trình gii này bao gm hu hn bước (do s đim cc biên là
hu hn).
Đối v
O(0, 0) A(0,12) B(12,6) dng
z = 0 z = 72 z = 132
z = 0 z = 120 z = 132
B
t đ
u
Nhp d liu
Tìm đim cc biên
xut phát
Tìm
đim iên cc b
k tt hơn
Kim tra
đi u u kin ti ư
In và lưu tr k
ế
t
q
u
Dng
Đún
g
Sai
Hình I.2. Sơ đồ khi gii BTQHTT
uy trình gii BTQHTT tng quát có sơ đồ khi gin lược như trình bày trên hình
I.2. T
1.3. Phương pháp đơn hình
i BTQHTT theo sơ đồ trên. Để gii ví d đã cho, trước
hết c
z = 8x
1
+ 6x
2
+ 0x
3
+ 0x
4
Max
vi các ràng buc:
4x
1
+ 2x
2
+ x
3
= 60
1 2 4
x
1
, x
2
, x , x
4
0
Cách lp và biến đổi các bng đơn hình
cn lp mt s bng đơn hình như trình
bày tr
t 1 là ct h s hàm mc tiêu ng vi các biến cơ s đã chn. Phương án xut
phát c
phương án) cn ghi các giá tr ca
các b
là các ct h s trong các điu kin ràng buc tương ng vi
các b
Q
rong sơ đồ trên, vì mc đích trình bày vn đề đơn gin, chúng ta không đề cp ti
các trưng hp khi BTQHTT có min phương án là tp rng (lúc đó ta không tìm được
phương án xut phát) cũng như khi ta không tìm được đim cc biên k tt hơn mc dù
điu kin ti ưu chưa tho mãn (lúc đó tp các giá tr hàm mc tiêu z không b chn).
Đây là phương pháp s gi
húng ta cn đưa BTQHTT v dng chính tc bng cách thêm vào các biến bù
không âm x
3
và x
4
như sau:
2x + 4x + x = 48
3
Để gii BTQHTT dng chính tc trên đây,
ong bng I.1. Trước hết, cn đin s liu ca bài toán đã cho vào bng đơn hình
bước 1:
C
ó th chn là x
1
= x
2
= 0 (đây chính là đim gc to độ O(0, 0)), do đó x
3
= 60, x
4
=
48). Như vy ti bước này chúng ta chưa bước vào sn xut, nên trong phương án chưa
đơn v sn phm loi I hay II được sn xut ra (ch “sn xut” ra các lượng nguyên
liu dư tha, ta cũng nói là các “sn phm” loi III và IV), và giá tr hàm mc tiêu z
tm thi bng 0. Các biến bù có giá tr ln hơn 0 có nghĩa là các nguyên liu loi tương
ng chưa được s dng hết. Ta gi các biến x
3
và x
4
là các biến cơ s vì chúng có giá tr
ln hơn 0 còn x
1
và x
2
là các biến ngoài cơ s vì chúng có giá tr bng 0. Vi bài toán
có hai ràng buc, ti mi bước ch có hai biến cơ s.
Ct 2 là ct các biến cơ s. Trong ct 3 (ct
iến cơ s đã chn.
Các ct tiếp theo
iến x
1
, x
2
, x
3
và x
4
ca bài toán đã cho.
Bng I.1. Các bng đơn hình gii BTQHTT
c
1
= 8 c
2
= 6 c
3
= 0 c
4
= 0
H sm
mc tiêu c
j
Biến cơ
s
Phương
án
x
1
x
2
x
3
x
4
0
0
x
3
x
4
60
48
4
2
2
4
1
0
0
1
Hàng z z
0
= 0 z
1
= 0 z
2
= 0 z
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
1/2
3
1/4
1/2
0
1
Hàng z z
0
= 120 z
1
= 8 z
2
= 4 z
3
= 2 z
4
= 0
Hàng
j
= c
j
z
j
1
= 0
2
= 2
3
= 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
Phân tích bng đơn hình bước 1
H s ng vi biến x
1
trên hàng th nht là a
11
= 4 có nghĩa là t l thay thế
riêng gia mt đơn v sn phm loi I và mt đơn v sn phm loi III là 4 (gii thích:
xét phương trình / ràng buc th nht 4x
1
+ 2x
2
+ x
3
= 60, x
1
tăng mt đơn v thì x
3
phi gim bn đơn v nếu gi nguyên x
2
). Tương t ta có th gii thích được ý nghĩa
ca các h s a
ij
khác cho trên hàng 1 và hàng 2 trong bng đơn hình bước 1.
Chúng ta xét hàng z ca bng đơn hình. Để tính z
1
, cn áp dng công thc z
1
=
(ct h s ca hàm mc tiêu) × (ct h s ca biến x
1
) = 0×4 + 0×2 = (giá mt đơn v
sn phm loi III)×(t l thay thế riêng loi I / loi III) + (giá mt đơn v sn phm loi
IV) × (t l thay thế riêng loi I / loi IV) = tng chi phí phi b ra khi đưa thêm mt
đơn v sn phm loi I vào phương án sn xut mi = 0. Các giá tr z
j
, vi j = 1, 2, 3, 4,
được tính tương t và chính là các chi phí khi đưa mt thêm mt đơn v sn phm loi
x
j
vào phương án sn xut mi. Còn z
0
là giá tr ca hàm mc tiêu đạt được ti phương
án đang xét: z
0
= (ct h s ca hàm mc tiêu)× (ct phương án) = 0×60 + 0×48 = 0.
Trên hàng
j
cn ghi các giá tr
j,
j = 1, 2, 3, 4, tính theo công thc
j
= c
j
–z
j
= li nhun trên mt đơn v sn phm – chi phí trên mt đơn v sn phm. Vy
j
là
"lãi biên"/mt đơn v sn phm khi đưa thêm mt đơn v sn phm loi j vào phương án
sn xut mi. Nếu
j
> 0 thì hàm mc tiêu còn tăng được khi ta đưa thêm các đơn v sn
phm loi j vào phương án sn xut mi. Có th chng minh được
j
chính là đạo hàm
riêng z/x
j
ca hàm mc tiêu z theo biến x
j
. Như vy, x
1
tăng lên 1 thì z tăng lên 8 còn
x
2
tăng lên 1 thì z tăng lên 6.
Do
1
2
đều dương nên vn còn kh năng ci thin hàm mc tiêu khi chuyn
sang (hay “xoay sang”) mt phương án cc biên k tt hơn (quay li nhn xét phn
gii bài toán bng phương pháp đồ th: đim cc biên k ca đim (0, 0) có th là A(0,
12) hay C(15, 0)).
Th tc xoay (pivotal procedure)
Bước 1: Chn ct xoay là ct có
j
> 0 tc là chn biến x
j
làm biến cơ s mi do
x
j
tăng kéo theo hàm mc tiêu tăng. đây ta chn đưa x
1
vào (đánh du ct
1
).
Bước 2: Chn hàng xoay để xác định đưa biến nào ra khi s biến cơ s (vì ti
mi bước s biến cơ s là không thay đổi). Để chn hàng xoay, ta thc hin quy tc “t
s dương bé nht" bng cách ly ct phương án (60 48)
T
chia tương ng cho ct xoay (4
2)
T
để chn t s bé nht. Mt điu cn chú ý là ta ch xét các t s có mu s dương.
Vì Min{60/4, 48/2} = 60/4 đạt được ti hàng đầu, nên ta đánh du vào hàng
xoay là hàng đầu (hàng tương ng vi biến x
3
). Do đó cn đưa x
3
ra khi các biến cơ
s.
Bước 3: Chn phn t xoay nm trên giao ca hàng xoay và ct xoay.
Bước 4: Xoay sang bng đơn hình mi, xác định các biến cơ s mi để đin vào
ct biến cơ s, đồng thi thay các giá tr trong ct h s hàm mc tiêu. Sau đó, tính li
các phn t ca hàng xoay bng cách ly hàng xoay cũ chia cho phn t xoay để
hàng mi tương ng.
Bước 5: Các phn t còn li ca bng đơn hình mi được tính theo quy tc "hình
ch nht": (1)
mi
= (1)
cũ
– (2)
cũ
× (4)
cũ
/(3)
cũ
, trong đó (3) là đỉnh tương ng vi phn t
xoay (xem hình I.3).
(4)
(2) (3)
(1)
Chng hn: (1)
cũ
= 4, 2
(cũ)
= 2
(3)
cũ
= phn t xoay = 4, (4)
cũ
= 2
(1)
mi
= 4 2 ×
4
2
= 3.
Hình I.3. Quy tc hình ch nht
Gii 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
1
+ (1/2)x
2
+ (1/4)x
3
= 15 (a’)
0x
1
+ 3x
2
(1/2)x
3
+ x
4
= 18 (b’)
bng cách ly phương trình (a) chia cho 4 (phn t xoay) để có (a’), ri ly (b) tr bt
2
× (a)/4 để có (b’). Đây chính là ni dung ca bước 4 và bước 5. Còn bước 3 s đảm
bo rng giá tr ca các biến cơ s mi không âm (x
1
= 15, x
4
= 18).
Áp dng th tc xoay cho các phn t nm trên hàng 1 và 2 ca bng đơn hình
bước 1, sau đó tính các giá tr trên hàng z
j
j
tương t như khi lp bng đơn hình
bước 1, chúng ta s nhn được bng đơn hình bước 2.
Phân tích bng đơn hình bước 2
Bng bước 2 có th được phân tích tương t như bng bước 1. Cn chú ý rng lúc
này ta đang v trí ca đim C(15, 0) vì x
1
= 15 còn x
2
= 0; giá tr ca hàm mc tiêu là
z
0
= 120 đã được ci thin hơn so vi bước 1. Ta thy
2
= 2 > 0 nên còn có th ci
thin hàm mc tiêu bng cách chn biến x
2
làm biến cơ s mi. Thc hin các bước
xoay sang phương án cc biên k tt hơn, chúng ta s có bng đơn hình bước 3.
Phân tích bng đơn hình bước 3
Ti bng đơn hình bước 3 ta thy điu kin ti ưu đã được tho mãn (
j
0
j=1, 2, 3, 4) nên không còn kh năng ci thin phương án. Phương án ti ưu đã đạt được
ti x
1
= 12, x
2
= 6, x
3
= 0, x
4
= 0, tc là ti đim cc biên B(12, 6) vi giá tr z
max
= 132.
Mt s chú ý
Điu kin ti ưu cho các BTQHTT dng Max là
j
0 j.
Đối vi các BTQHTT cn cc tiu hoá hàm mc tiêu thì điu kin ti ưu (hay
tiêu chun dng) là
j
0 j (nếu tn ti j mà
j
0 thì cn tiếp tc ci thin hàm mc
tiêu bng cách chn ct j làm ct xoay...).
Trong thc tin gii các BTQHTT dng tng quát có th xy ra trưng hp
không tìm được phương án xut phát (tc là không có phương án kh thi, xem thêm
mc 1.2). Lúc này có th kết lun mô hình đã thiết lp có các điu kin ràng buc quá
cht ch, cn xem xét ni lng các điu kin này.
Trong trưng hp ta tìm được ct xoay mà không tìm được hàng xoay thì kết
lun hàm mc tiêu không b chn trên (đối vi các BTQHTT dng Max) hoc không b
chn dưới (đối vi các BTQHTT dng Min). Khi đó dng quá trình gii và kết lun mô
hình quy hoch tuyến tính đã thiết lp không phù hp vi thc tế.
1.4. Gii mô hình quy hoch tuyến tính bng các phn mm tính toán
Hin nay có nhiu phn mm tính toán gii BTQHTT khá hiu qu như Excel,
Lingo. Nhng phn mm này rt thân thin vi ngưi dùng. Tuy nhiên cn nhn mnh
rng, vic phát biu đưc mô hình bài toán và phân tích, đánh giá được kết qu mi
chính là nhng khâu quan trng nht trong phương pháp mô hình hoá. Sau đây, chúng
ta dùng phn mm Lingo để gii ví d đã xét trên.
z = 8x
1
+ 6x
2
Max
vi các ràng buc:
4x
1
+ 2x
2
60
2x
1
+ 4x
2
48
x
1
, x
2
0.
Để gii bài toán này, chúng ta cn cài đặt Lingo vào trong máy tính. Nhn vào
biu tượng Lingo trên màn hình để vào ca s Lingo. Sau đó thc hin các lnh Lingo:
Menu > New > <Untitle> và gõ vào các d liu ca bài toán như hình I.4.
Hình I.4. Nhp d liu ca bài toán quy hoch tuyến tính trong Lingo
Tiếp theo, cn nháy chut vào nút LINGO và gii bài toán để thu đưc kết qu chi
tiết như trên hình I.5.
Hình I.5. Kết qu gii bài toán quy hoch tuyến tính trong Lingo
Kết qu chi tiết cho ta biết giá tr cc đại ca hàm mc tiêu là 132 vi phương án
ti ưu là: x
1
= 12, x
2
= 6. Các giá tr ti ưu ca các biến đối ngu là y
1
= 5/3 và y
2
= 2/3
(còn gi là các giá ước định hay giá bóng Shadow Prices).
1.5. Mt s ng dng ca phương pháp đơn hình
(Gii các bài toán quy hoch sn xut trong lĩnh vc cơ khí và đin lc)
Bài toán phân phi đin năng
Có ba h ph ti cn được cung cp đin năng t hai ngun đin nm cách xa
nhau. Giá thành truyn ti mt đơn v đin năng t ngun i đến h tiêu th j là c
ij
. Kh
năng cung cp đin năng ca mi ngun b gii hn bi tr lượng hin có ca chúng là
A
1
và A
2
. Nhu cu tiêu dùng ca các h tiêu th là B
1
, B
2
và B
3
. Gi x
ij
là lượng đin
năng được đưa t ngun i ti h tiêu th j. Cn phi xác định các x
ij
sao cho tng chi
phí là nh nht. Như vy ta có BTQHTT sau:
z = Min
23
ij ij
i1 j1
cx
==
∑∑
vi các điu kin ràng buc là:
x
11
+ x
12
+ x
13
A
1
,
x
21
+ x
22
+ x
23
A
2
,
x
11
+ x
21
= B
1
,
x
12
+ x
22
= B
2
,
x
13
+ x
23
= B
3
,
x
ij
0, i = 1, 2 và j = 1, 2, 3.
Bài toán trên đây (hoc dng tng quát hơn) có th gii được bng phương pháp
đơn hình đã biết hay phương pháp phân phi s được nghiên cu mc 1.3, chương II.
Bài toán phân ti cho máy
Mt xí nghip có hai loi máy M
1
và M
2
. Các loi máy này có th sn xut được ba
loi sn phm P
1
, P
2
và P
3
vi các năng sut là a
ij,
chng hn máy M
1
sn xut sn phm
P
2
vi năng sut a
12
. Mi đơn v sn phm mang li lãi sut c
j
vi j = 1, 2, 3. Mi tháng xí
nghip phi sn xut sn phm loi j không ít hơn b
j
đơn v và không vượt quá d
j
đơn v,
j = 1, 2, 3. Hãy lp kế hoch phân ti cho các máy sao cho đạt tng li nhun ln nht.
D thy bài toán này dn ti BTQHTT sau:
z =
32
jij
j1 i1
cax
==
ij
∑∑
Max
vi các điu kin ràng buc:
a
11
x
11
+ a
21
x
21
b
1
,
a
12
x
12
+ a
22
x
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
+ a
22
x
22
d
2
,
a
13
x
13
+ a
23
x
23
d
3
,
x
11
+ x
12
+ x
13
m
1
,
x
21
+ x
22
+ x
23
m
2
,
x
ij
0, i = 1, 2 và j = 1, 2, 3.
(trong đó m
1
và m
2
là tng thi gian chy máy M
1
và M
2
).
Bài toán trên đây còn có th phát biu mt cách tng quát hơn và vn gii được
bng phương pháp đơn hình. Hơn na, trong lĩnh vc quy hoch sn xut hay qun lí
kinh doanh, nói riêng trong ngành cơ khí và đin lc, BTQHTT được ng dng rt rng
rãi và mang li hiu qu cn thiết.
2. B sung thêm v phng pháp đn hình
2.1. Đưa BTQHTT v dng chính tc
Ví d 1: (Trưng hp các ràng buc đều có du )
z = 8x
1
+ 6x
2
Max
vi các ràng buc:
12
12
12
4x 2x 60
2x 4x 48
x,x 0
+≤
+≤
Đưa BTQHTT v dng chính tc như đã biết bng cách thêm hai biến bù (slack
variables) x
3
và x
4
. Ta có BTQHTT dng chính tc là:
z = 8x
1
+ 6x
2
+ 0x
3
+ 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 điu kin ràng buc đã có đ hai biến đng độc lp trong
tng phương trình vi h s +1, nên đã có th tìm được phương án cc biên xut phát để
bt đầu quá trình gii bài toán. Mt cách tng quát, BTQHTT dng chính tc là bài toán
vi các biến không âm, các ràng buc vi du “=”, h s vế phi ca các ràng buc
không âm. Ngoài ra, mi phương trình bt buc phi có mt biến đứng độc lp vi h s
+1.
Ví d 2: (Trưng hp có điu kin ràng buc vi du )
z = 8x
1
+ 6x
2
Max
vi các ràng buc:
12
12
12
4x 2x 60
2x 4x 48
x,x 0
+≤
+≥
Ta thêm các biến bù x
3
(slack variable) mang du “+”, x
4
(surplus variable) mang
du “để có h điu kin ràng buc sau:
123
124
1234
4x 2x x 60
2x 4x x 48
x,x,x,x 0
++=
+−=
Phi thêm biến gi x
5
(x
5
gi là lượng vi phm ca phương trình th hai) để được
h điu kin ràng buc
=++
=++
0x,x,x,x,x
48xxx4x2
60xx2x4
54321
5421
321
Lúc này, đã có đ hai biến đng độc lp trong tng phương trình vi h s +1,
nên đã có th tìm được phương án cc biên xut phát để bt đầu quá trình gii bài toán
bng phương pháp đơn hình vi hàm mc tiêu là z = 8x
1
+ 6x
2
+ 0x
3
+ 0x
4
Mx
5
Max, trong đó M + và biu thc Mx
5
gi là lượng pht (đánh thuế). Bài toán đã
được đưa v dng chính tc. Lượng vi phm x
5
càng ln thì hàm mc tiêu càng gim,
giá tr ca hàm mc tiêu ch có th đạt Max khi x
5
= 0.
Ví d 3: (Trưng hp có biến không dương)
z = 8x
1
6x
2
Max
vi các ràng buc:
123
124
1234
4x 2x x 60
2x 4x x 48
x 0,x 0,x 0,x 0
++
+−=
≥≤≥≥
Lúc này mun gii bài toán bng phương pháp đơn hình ta phi đổi biến x'
2
= x
2
.
Ta có BTQHTT vi các biến đều không âm.
z = 8x
1
+ 6x'
2
Max
vi các ràng buc:
123
124
1234
4x 2x' x 60
2x 4x' x 48
x,x',x,x 0
−+
−−=
Ví d 4: (Trưng hp có biến vi du tu ý)
z = 8x
1
+ 6x
2
Max
vi các ràng buc:
12
12
12
4x 2x 60
2x 4x 48
x0,x
+≤
+≤
d
u tu
ý
Lúc này ta viết biến x
2
dưới dng x
2
= x'
2
x''
2
vi
2
22
x' max[0,x ]
x'' max[0, x ]
=
=−
2
thì đảm bo
2
2
x' 0
x'' 0
Các ràng buc s
1223
1224
1 2 234
4x 2x' 2x'' x 60
2x 4x' 4x' x 48
x ,x' ,x'' ,x ,x 0
+−+=
+−+=
Bài toán vi hàm mc tiêu là: z = 8x
1
+ 6x'
2
6x''
2
+ 0x
3
+ 0x
4
và các điu kin
ràng buc trên là BTQHTT dng chính tc.
Kết lun: Bao gi cũng đưa được BTQHTT bt kì (các biến có du tu ý, các
ràng buc có th , , =) v dng chính tc.
2.2. Phương pháp đơn hình m rng
Phương pháp đơn hình m rng còn gi là phương pháp đánh thuế M được áp
dng để để gii BTQHTT có biến gi.
Ví d:
z = 8x
1
+ 6x
2
Max
vi các ràng buc:
12
12
12
4x 2x 60
(a) 2x 4x 48
x,x 0
+≤
+≥
hay: z = 8x
1
+ 6x
2
+0x
3
+ 0x
4
Max vi các ràng buc
123
124
1234
4x 2x x 60
(b) 2x 4x x 48
x,x,x,x 0
++=
+−=
Ta có th đưa bài toán v dng chính tc sau gi là bài toán M:
Max z = 8x
1
+ 6x
2
+0x
3
+ 0x
4
Mx
5
(trong đó M +) vi các ràng buc
123
1245
12345
4x 2x x 60
(c) 2x 4x x x 48
x,x,x,x,x 0
++=
+−+=
Cách 1: Có th gii BTQHTT vi các điu kin ràng buc (a) bng phương pháp
đồ th để nhn được kết qu: phương án ti ưu là (x
1
= 0, x
2
= 30) và z
max
= 180.
Cách 2: Gii BTQHTT vi các điu kin ràng buc (c) bng cách lp bng đơn
hình như thông thưng nhưng chú ý h s M + (xem bng I.2).
Bng I.2. Các bng đơn hình gii bài toán M
8 6 0 0
M
H s
hàm mc
tiêu
Biến
cơ s
Phương
án
x
1
x
2
x
3
x
4
x
5
0
M
x
3
x
5
60
48
4
2
2
4
1
0
0
1
0
+1
Hàng z
z
0
= 48M z
1
= 2M z
2
= 4M
z
3
= 0 z
4
= M
z
5
= M
Hàng
j
1
= 8+2M
2
= 6+4M
3
= 0
4
= M
5
= 0
0
6
x
3
x
2
36
12
3
1/2
0
1
1
0
1/2
1/4
1/2
1/4
Hàng z 72 3 6 0
3/2
3/2
Hàng
j
5 0 0 3/2
M 3/2
0
6
x
4
x
2
72
30
6
2
0
1
2
1/2
1
0
1
0
Hàng z 180 12 6 3 0 0
Hàng
j
4
0
3
0
M
Ti bng đơn hình cui cùng, ta thy
j
0 j nên phương án ti ưu đã đạt được
vi x
2
= 30, x
4
= 72, các x
j
khác = 0 và z
Max
= 180.
Lưu ý
Khi mt biến gi đã được đưa ra khi cơ s thì không bao gi quay li na. Do
đó ta có th xoá ct biến gi đó khi bng đơn hình.
Nếu du hiu dng xut hin (
j
0 j) nhưng vn còn biến gi vi giá tr
dương trong s các biến cơ s thì điu này chng t bài toán ban đầu không th
phương án kh thi (có th chng minh bng phn chng).
Vi ví d trên (xem bng I.2) ta thy quá trình gii chia làm hai pha: pha 1
nhm gii bài toán M cho ti khi biến gi (x
5
) được đưa ra khi s biến cơ s (lúc này
có phương án cc biên xut phát cho bài toán (b)) và pha 2 nhm tìm phương án ti ưu
cho bài toán (b).
Phn mm tính toán Lingo có th gii được tt c các BTQHTT không đòi hi
ngưi dùng phi đưa chúng v dng chính tc.
3. Mô hình quy hoch tuyến tính đa mc tiêu
3.1. Các khái nim cơ bn
Phát biu mô hình
Trong các bài toán kĩ thut, công ngh, qun lí, kinh tế nông nghip v.v... ny
sinh t thc tế, chúng ta thưng phi xem xét để ti ưu hoá đồng thi mt lúc nhiu
mc tiêu. Các mc tiêu này thưng là khác v th nguyên, tc là chúng được đo bi các
đơn v khác nhau. Nhng tình hung như vy to ra các bài toán ti ưu đa mc tiêu.
Như vy, chúng ta cn phi ti ưu hoá (cc đại hoá hoc c
c tiu hoá tu theo tình
hung thc tế) không phi là ch mt mc tiêu nào đó, màđồng thi tt c các mc
tiêu đã đặt ra.
Bài toán ti ưu đa mc tiêu mà trong đó min ràng buc D là tp li đa din và
các mc tiêu z
i
= f
i
(X), vi i = 1, 2,…, p, là các hàm tuyến tính xác định trên D, được
gi là bài toán quy hoch tuyến tính đa mc tiêu. Khi đó, ta có mô hình toán hc sau
đây được gi là mô hình quy hoch tuyến tính đa mc tiêu :
Max CX vi ràng buc X
D, trong đó:
C là ma trn cp p
×
n
D = {
X
R
n
: AX B}
vi A là ma trn cp m
×
n và B
R
m
.
Ví d: BTQHTT vi hai mc tiêu
f
1
(X) = x
1
+ 2x
2
Min hay z
1
= f’
1
(X) = x
1
2x
2
Max
z
2
= f
2
(X) = 2x
2
, Max
vi các ràng buc
12
12
12
xx
xx 3
x, x 0
−+
+≥
3
Ta có th viết bài toán này dưới dng ma trn như sau: Max CX vi ràng buc
X D
= {X R
2
: AX B}, trong đó X = (x
1
, x
2
)
T
, B = (3, 3, 0, 0)
T
, còn
C = , A =
0
1
2
2
1
1
1
0
1
1
0
1
.
Có th nói, BTQHTT đa mc tiêu là BTQHTT mà trong đó chúng ta phi ti ưu
hoá cùng mt lúc nhiu mc tiêu. Tuy nhiên, các mc tiêu này thưng đối chi cnh
tranh vi nhau. Vic làm tt hơn mc tiêu này thưng dn ti vic làm xu đi mt s
mc tiêu khác. Vì vy vic gii các bài toán ti ưu đa mc tiêu, tc là tìm ra mt
phương án kh thi tt nht theo mt nghĩa nào đó, thc cht chính là m
t bài toán ra
quyết định. Có th thy li đây mt ln na khng định "Ti ưu hoá chính là công c
định lượng ch yếu nht ca quá trình ra quyết định".
Hin ti các tài liu, sách chuyên kho, tp chí cp nht v lĩnh vc liên ngành
Toán Tin, Khoa hc qun lí, Công ngh, Kinh tế, Đin, Cơ khí nông nghip,... đề cp
rt nhiu ti bài toán ti ưu đa mc tiêu. Vn đề nghiên cu cơ s lí thuyết, thut toán,
lp mô hình, xây dng h máy tính tr giúp quyết định, và áp dng các mô hình ti ưu
đa mc tiêu cho các quá trình công ngh, qun lí,... là mt vn đề liên ngành được rt
nhiu nhà khoa hc và kĩ sư thc hành quan tâm.
Phương án ti ưu Pareto
Khái nim then cht trong ti ưu hoá đa mc tiêu là khái nim phương án ti ưu
Pareto.
Định nghĩa: Mt phương án ti ưu Pareto X
*
có tính cht sau đây:
Trước hết nó phi thuc vào min các phương án kh thi ca bài toán, tc là
phi tho mãn tt c các ràng buc: X
*
D.
Vi mi phương án kh thi khác X D mà có mt mc tiêu nào đó tt hơn (f
i
(X)
tt hơn f
i
(X
*
)) thì cũng phi có ít nht mt mc tiêu khác xu hơn (f
j
(X) xu hơn f
j
(X
*
), j
i).
Nói mt cách khác, không tn ti mt phương án kh thi nào X D có th tri
hơn X
*
trên tng th.
Để minh ho định nghĩa trên, ta xét ví d đã cho.
Ví d:
Xét BTQHTT vi hai mc tiêu.
f
1
(X) = x
1
+ 2x
2
Min
f
2
(X) = 2x
2
Max
Vi các ràng buc
−+
+≥
xx
xx
xx
12
12
12
3
3
0,
-3
3
3
2
A
B
1
n
r
2
n
r
D
o
d
y
x
Hình I.6. Minh ho đồ th BTQHTT hai mc tiêu
Min các phương án kh thi D (min gii hn bi đon AB và các tia Ad, Bx)
được biu th trên hình I.6.
1
n
r
(1, 2) là hướng gim ca mc tiêu 1, còn
2
n
r
(0, 2) là
hướng tăng ca mc tiêu 2.
Lúc này A(0, 3) cũng như B(3, 0) là hai phương án ti ưu Pareto ca bài toán trên.
D thy tp hp P tt c các phương án ti ưu Pareto bao gm các đim nm trên đon
AB và Ad.
3.2. Mt s phương pháp gii BTQHTT đa mc tiêu
Định nghĩa 1
Gii bài toán ti ưu toàn cc đa mc tiêu là chn ra t tp hp P các phương án
ti ưu Pareto ca bài toán mt (hoc mt s) phương án tt nht (tho mãn nht) theo
mt nghĩa nào đó da trên cơ cu ưu tiên ca ngưi ra quyết định.
Trong ví d trên, tu theo cơ cu ưu tiên ca ngưi ra quyết định, chúng ta có th
chn ra mt hoc mt s đim ti ưu Pareto nm trên AB hoc tia Ad làm phương án
ti ưu ca bài toán.
Cách 1: Bng mt phương pháp ti ưu toán hc thích hp tìm ra tp hp P tt c các
phương án ti ưu Pareto. Ngưi ra quyết định s đề ra cơ cu ưu tiên ca mình đối vi tp
P nhm tìm ra phương án ti ưu Pareto tho mãn nht cho bài toán đa mc tiêu ban đầu.
Cách 2: Vic tìm tp hp P trong trưng hp các bài toán nhiu biến là khá khó
và mt nhiu thi gian. Vì vy, so vi cách 1, cách 2 s tiến hành theo trình t ngược
li. Trước hết ngưi ra quyết định s đề ra cơ cu ưu tiên ca mình. Da vào cơ cu ưu
tiên đó, các mc tiêu s được t hp vào mt mc tiêu duy nht, tiêu biu cho hàm tng
tin ích ca bài toán. Bài toán ti ưu vi hàm m
c tiêu t hp này s được gii bng
mt phương pháp ti ưu toán hc thích hp, để tìm ra mt (hoc mt s) phương án ti
ưu Pareto. Lúc này, ngưi ra quyết định s chn ra trong s các phương án ti ưu Pareto
đó mt phương án tt nht.
Chúng ta s tiếp tc phân tích cách th 2. Rõ ràng, ngưi ra quyết định không th
đề ra cơ cu ưu tiên ca mình mt cách chính xác ngay t
đầu. Trong quá trình gii bài
toán, trong mi bước lp, sau khi xem xét li cơ cu ưu tiên đã đề ra, cũng như phương
án trung gian va tìm được, ngưi ra quyết định có th da vào các thông tin đó để thay
đổi li cơ cu ưu tiên ca mình. Sau đó, quá trình gii li được tiếp tc, cho ti khi mt
phương án ti ưu cui cùng được đưa ra.
Định nghĩa 2
Phương pháp gii bài toán ti ưu đa mc tiêu da trên s tr giúp ca h máy
tính, nhm giúp ngưi ra quyết định tng bước thay đổi các quyết định trung gian mt
cách thích hp để đi ti mt phương án ti ưu Pareto thon nht, được gi là
phương pháp tương tác ngưi máy tính.
Phương pháp tương tác ngưi máy tính gii bài toán ti ưu đa mc tiêu có các
yếu t
cu thành sau:
Cơ cu ưu tiên ca ngưi ra quyết định và hàm t hp tương ng.
Kiu tương tác ngưi máy tính: cho biết các thông tin nào máy tính phi đưa
ra li trong các bước lp trung gian, và cách thay đổi các thông s ca cơ cu ưu tiên t
phía ngưi ra quyết định.
Kĩ thut ti ưu toán hc được xây dng da trên lí thuyết ti ưu hoá nhm tìm
ra các phương án ti ưu Pareto cho các bài toán cn gii trong các bước lp trung gian.
Cho ti thi đim hin nay, hàng chc phương pháp gii BTQHTT đa mc tiêu đã
được đề cp ti trong các tp chí chuyên ngành, mà đa s chúng đều có nhng ng
dng rt thành công trong nhiu lĩnh vc, như: phương pháp tham s, phương pháp nón
pháp tuyến, phương pháp véc tơ cc đại, phương pháp trng s tương tác ca
Chebysev, phương pháp tho d
ng m tương tác ca Nguyn Hi Thanh.
3.3. Phương pháp tho dng m tương tác gii BTQHTT đa mc tiêu
Thut gii
a. Bước khi to
Nhp s liu cho các hàm mc tiêu tuyến tính z
i
(i = 1, 2,..., p) và m điu kin
ràng buc.
Gii BTQHTT cho tng mc tiêu z
i
(i = 1, 2,..., p) vi m ràng buc ban đầu,
thu được các phương án ti ưu X
1
, X
2
,..., X
p
(nếu vi mt mc tiêu nào đó bài toán
không cho phương án ti ưu thì cn xem xét để chnh sa li các điu kin ràng buc
ban đầu).
Tính giá tr hàm mc tiêu ti p phương án X
1
, X
2
,..., X
p
.
Lp bng payoff. Xác định giá tr cn trên và giá tr cn dưới ca mc tiêu
z
B
i
z
w
i
z
i
(i=1, 2,..., p).
Xác định các hàm tho dng m µ
1
(z
1
), µ
2
(z
2
),..., µ
p
(z
p
) cho tng mc tiêu da
vào thông tin t bng payoff theo công thc:
w
ii
ii
Bw
ii
zz
(z ) , i 1,2,...,p.
zz
µ= =
Đặt k: = 1.
b. Các bước lp (xét bước lp th k)
Bước 1: Xây dng hàm mc tiêu t hp t các hàm tho dng trên:
w
1
µ
1
(z
1
) + w
2
µ
2
(z
2
) +... + w
p
µ
p
(z
p
) Max
Trong đó: w
1
, w
2
,..., w
p
là các trng s phn ánh tm quan trng ca tng hàm
tho dng trong thành phn hàm t hp, vi
w
1
+ w
2
+... + w
p
= 1 và 0 w
1
, w
2
,..., w
p
1.
Bước 2:
Gii BTQHTT vi hàm mc tiêu t hp và m ràng buc ban đầu để tìm được
phương án ti ưu ca bước lp th k là X
(k)
và giá tr ca các hàm mc tiêu z
i
cũng như
ca các hàm tho dng µ
i
(z
i
) (vi i =1, 2,..., p).
Nếu ngưi ra quyết định cm thy chưa tho mãn vi các giá tr đạt được ca
các hàm mc tiêu cũng như ca các hàm tho dng thì phương án thu được X
(k)
chưa
phi là phương án ti ưu thon nht. Đặt k:= k + 1, quay v bước 1.
Nếu ngưi ra quyết định đã cm thy tho mãn thì phương án thu được là X
(k)
.
Chuyn sang bước 3.
Bước 3: Kết thúc.
Ví d: Gii BTQHTT hai mc tiêu.
z
1
= 8x
1
+ 6x
2
Max
z
2
= x
1
+ 3x
2
Max
vi các ràng buc:
4x
1
+ 3x
2
60
2x
1
+ 4x
2
48
x
1
, x
2
0
(D)
a. Bước khi to
Gii BTQHTT cho tng mc tiêu trong ví d trên ta có hai bài toán: Max z
1
= 8x
1
+
6x
2
Max vi điu kin ràng buc (D) cho phương án ti ưu X
1
(12, 6) và Max z
1
=
132;
z
2
= x
1
+ 3x
2
Max cho phương án ti ưu X
2
(0, 12) và Max z
2
= 36.
Như vy min phương án ti ưu Pareto chính là mi phương án thuc AB (xem
hình I.1), vi A(0, 12) và B(12, 6).
1
n
r
(8, 6) là hướng tăng ca mc tiêu 1, còn
2
n
r
(1, 3)
là hướng tăng ca mc tiêu 2. Do đó, khi chn phương án ti ưu Pareto dch dn t B
v A thì z
1
gim, z
2
tăng. Cn tìm phương án ti ưu Pareto "tho mãn nht" thuc AB
bng cách “thương lượng” gia z
1
và z
2
.
Lp bng payoff cho các mc tiêu
Phương án X
i
z
1
z
2
X
1
(12, 6)
X
2
(0, 12)
132
72
30
36
Da trên thông tin ca bng payoff, ta có = 72, = 132; còn = 30,
= 36. Do đó, đon biến thiên cn xét cho z
W
1
z
B
1
z
W
2
z
B
2
z
1
là [72, 132] và cho z
2
là [30, 36]. T đó
chúng ta có th thiết lp các hàm tho dng m ng vi hai mc tiêu đã cho như sau:
)(
11
z
µ
WB
W
zz
zz
11
11
=
=
72132
72
1
z
=
60
1
z
72
60
=
60
1
z
1,2
Hàm tho dng m trên đây ph thuc vào z
1
, nên ph thuc vào (x
1
, x
2
). Khi có
mt phương án kh thi (x
1
, x
2
) ta tính được độ tho dng
)(
11
z
µ
đối vi mc tiêu z
1
.
Tương t đối vi z
2
ta có hàm tho dng m:
)(
22
z
µ
=
WB
W
zz
zz
22
22
=
3036
30
2
z
=
6
2
z
5.
Lp hàm tho dng t hp u = w
1
11
(z )
µ
+ w
2
22
(z )
µ
, trong đó w
1
, w
2
là các trng
| 1/34

Preview text:

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 = c1x1 + c2x2 + cnxn Max (Min)
với các điều kiện ràng buộc:
a11x1 + a12x2 +... +a1nxn b1
a21x1 + a22x2 +... +a2nxn b2 ...
am1x1 + am2x2 +... +amnxn bm
x1, x2,..., xn
0 (điều kiện không âm)
Ví dụ: z = 8x1 + 6x2 → Max với các ràng buộc: 4x1 + 2x2 ≤ 60 2x1 + 4x2 ≤ 48 x1, x2 ≥ 0
Cần tìm các giá trị c a các biến quyết định x1, x2 để các ràng buộc được thoả mãn
và hàm mục tiêu đạt giá trị lớn nhất.
Bài toán này có ý nghĩa kinh tế như sau: Giả sử một xí nghiệp sản xuất hai loại
sản phẩ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ó ý nghĩa minh hoạ và giúp hiểu bản chất vấn đề.
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 phương án
khả thi (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ố (x1, x2) còn gọi là véc tơ nghiệm, thoả mãn tất cả các ràng buộc đã có (xem hình I.1).
− Trước hết chúng ta vẽ đồ thị 4x1 + 2x2 = 60 bằng cách xác định hai điểm trên
đồ thị: (x1 = 0, x2 = 30) và (x2 = 0, x1 = 15). x2 30 4x1 + 2x2 = 60 12 A 8 B 2x 4 1 + 4x2 = 48 C O 3 6 15 24 x1 Hình I.1. Ph
ương pháp đồ thị giải bài toán quy hoạch tuyến tính
Đồ thị trên là một đư ng thẳng chia mặt phẳng làm hai nửa mặt phẳng: một phần
gồm các điểm (x1, x2) thoả mãn 4x1 + 2x2 ≤ 60; một phần thoả mãn 4x1 + 2x2 ≥ 60. Ta
tìm được nửa mặt phẳng thoả mãn 4x1 + 2x2 ≤ 60.
− Tương tự, có thể vẽ đồ thị 2x1 + 4x2 = 48 bằng cách xác định hai điểm thuộc đồ thị (x1 = 0, x = 12) và ( 2 x = 0, x 2 = 24). Sa 1 u đó tì ử
m n a mặt phẳng thoả mãn 2x + 4x 1 ≤ 2 48.
− 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 (x1, x2)
thoả mãn hai ràng buộc đầu tiên. Tuy nhiên, để thoả mãn điều kiện không âm c a các
biến, 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 (x1, x2) sao cho
z = 8x1 + 6x2 đạt giá trị lớn nhất.
Cách 1: Dùng đường đồng mức. Tùy theo giá trị c a x1, x2 mà z có những m c giá trị khác nhau.
− Vẽ đư ng đồng m c: 8x1 + 6x2 = c m c c = 24, (ta có thể chọn giá trị c bất
kì, nhưng chọn c = 24 là bội số chung c a 6 và 8 để việc tìm toạ độ các điểm cắt hai
trục toạ độ 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à (x1 = 0,
x2 = 4) và (x2 = 0, x1 = 3). Các điểm nằm trên đư ng đồng m c này đều cho giá trị hàm mục tiêu z = 24.
− Tương tự, có thể vẽ đư ng đồng m c th hai: 8x1 + 6x2 = 48 đi qua hai điểm (x1 =
0, x2 = 8) và (x2 = 0, x1 = 6). Chúng ta nhận thấy, nếu tịnh tiến song song đư ng đồng r
m c lên trên theo hướng c a véc tơ pháp tuyến n (8, 6) thì giá trị c a hàm mục tiêu z = 8x1 + 6x2 tăng lên.
Vậy giá trị z lớn nhất đạt được khi đư ng đồng m c đi qua điểm B(12, 6) (tìm
được x1 = 12, x2 = 6 bằng cách giải hệ phương trình 4x1 + 2x2 = 60 và 2x1 + 4x2 = 48).
Kết luận: Trong các phương án khả thi thì phương án tối ưu là (x1 = 12, x2 = 6).
Tại phương án này, giá trị hàm mục tiêu là lớn nhất zmax = 8 × 12 + 6 × 6 = 132.
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 biên c a
đơn hì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.
Cách 2: Từ nhận xét trên, để tìm phương án tối ưu ta chỉ cần so sánh giá trị c a
hàm mục tiêu tại các điểm cực biên c a miền phương án.
Tính giá trị z tại O(0, 0): z(0, 0) = 0; tại A(0, 12): z(0, 12) = 72; tại C(15,0): z(15,
0) = 120; tại B(12, 6): z(12, 6) = 132 = Max{z(O), z(A), z(B), z(C)}. Vậy zmax = 132.
Nhận xét: Muốn tìm phương án tối ưu c a BTQHTT ta xuất phát từ một điểm cực
biên nào đó, tìm cách cải thiện hàm mục tiêu bằng cách đi tới điểm cực biên kề nó. Tiếp
tục như vậy cho tới khi tìm được phương án tối ưu. Trong trư ng hợp BTQHTT có
phương án tối ưu thì quy trình giải này bao gồm hữu hạn bước (do số điểm cực biên là hữu hạn).
Đối với BTQHTT đang xét, quy trình giải được minh hoạ như sau: O(0, 0)
→ A(0,12) → B(12,6) dừng z = 0 → z = 72 → z = 132 hoặc: O(0, 0) → C(15, 0) → B(12, 6) dừng z = 0 → z = 120 → z = 132
Sơ đồ khối Bắt đầu Nhập dữ liệu Tìm điểm cực biên xuất phát Tìm Kiểm tra Sai điểm cực biên điều kiện tối ưu kề tốt hơn Đúng In và lưu trữ kết quả Dừng
Hình I.2. Sơ đồ khối giải BTQHTT uy trình gi Q
ải BTQHTT tổng quát có sơ đồ khối giản lược như trình bày trên hình
I.2. Trong 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).
1.3. Phương pháp đơn hình
Đây là phương pháp số giải BTQHTT theo sơ đồ trên. Để giải ví dụ đã cho, trước
hết chú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 x3 và x4 như sau:
z = 8x1 + 6x2 + 0x3 + 0x4 → Max với các ràng buộc: 4x1 + 2x2 + x3 = 60 2x1 + 4x2 + x4 = 48 x1, x2, x3, x4 ≥ 0
Cách lập và biến đổi các bảng đơn hình
Để giải BTQHTT dạng chính tắc trên đây, cần lập một số bảng đơn hình như trình
bày trong bảng I.1. Trước hết, cần điền số liệu c a bài toán đã cho vào bảng đơn hình bước 1: − ộ
C 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ó thể chọn là x1 = x2 = 0 (đây chính là điểm gốc toạ độ O(0, 0)), do đó x3 = 60, x4 =
48). Như vậy tại bước này chúng ta chưa bước vào sản xuất, nên trong phương án chưa
có đơn vị sản phẩm loại I hay II được sản xuất ra (chỉ “sản xuất” ra các lượng nguyên
liệu dư thừa, ta cũng nói là các “sản phẩm” loại III và IV), và giá trị hàm mục tiêu z
tạm th i bằng 0. Các biến bù có giá trị lớn hơn 0 có nghĩa là các nguyên liệu loại tương
ng chưa được sử dụng hết. Ta gọi các biến x3 và x4 là các biến cơ s vì chúng có giá trị
lớn hơn 0 còn x1 và x2 là các biến ngoài cơ s vì chúng có giá trị bằng 0. Với bài toán
có hai ràng buộc, tại mỗi bước chỉ có hai biến cơ s .
− Cột 2 là cột các biến cơ s . Trong cột 3 (cột phương án) cần ghi các giá trị c a
các biến cơ s đã chọn.
− Các cột tiếp theo 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 biến x1, x2, x3 và x4 c a bài toán đã cho.
Bảng I.1. Các bảng đơn hình giải BTQHTT Hệ số hàm Biến cơ Phương c1 = 8 c2 = 6 c3 = 0 c4 = 0 mục tiêu cj s án x1 x2 x3 x4 0 x3 60 4 2 1 0 0 x4 48 2 4 0 1 Hàng z z0 = 0 z1 = 0 z2 = 0 z3 = 0 z4 = 0 Hàng ∆j = cj − zj ∆1 = 8 ∆2 = 6 ∆3 = 0 ∆4 = 0 8 x1 15 1 1/2 1/4 0 0 x4 18 0 3 −1/2 1 Hàng z z0 = 120 z1 = 8 z2 = 4 z3 = 2 z4 = 0 Hàng ∆j = cj − zj ∆1 = 0 ∆2 = 2 ∆3 = −2 ∆4 = 0 8 x1 12 1 0 1/3 −1/6 6 x2 6 0 1 −1/6 1/3 Hàng z z0 = 132 8 6 5/3 2/3 Hàng ∆j = cj − zj 0 0 −5/3 −2/3
Phân tích bảng đơn hình bước 1
− Hệ số ng với biến x1 trên hàng th nhất là a11 = 4 có nghĩa là tỉ lệ thay thế
riêng giữa một đơn vị sản phẩm loại I và một đơn vị sản phẩm loại III là 4 (giải thích:
xét phương trình / ràng buộc th nhất 4x1 + 2x2 + x3 = 60, x1 tăng một đơn vị thì x3
phải giảm bốn đơn vị nếu giữ nguyên x2). Tương tự ta có thể giải thích được ý nghĩa
c a các hệ số aij khác cho trên hàng 1 và hàng 2 trong bảng đơn hình bước 1.
− Chúng ta xét hàng z c a bảng đơn hình. Để tính z1, cần áp dụng công th c z1 =
(cột hệ số c a hàm mục tiêu) × (cột hệ số c a biến x1) = 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ị zj, 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
xj vào phương án sản xuất mới. Còn z0 là giá trị c a hàm mục tiêu đạt được tại phương
án đang xét: z0 = (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 = cj –zj
= 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ãi biên"/một đơn vị sản phẩm khi đưa thêm một đơn vị sản phẩm loại j vào phương án
sản xuất mới. Nếu ∆j > 0 thì hàm mục tiêu còn tăng được khi ta đưa thêm các đơn vị sản
phẩm loại j vào phương án sản xuất mới. Có thể ch ng minh được ∆j chính là đạo hàm
riêng ∂z/∂xj c a hàm mục tiêu z theo biến xj. Như vậy, x1 tăng lên 1 thì z tăng lên 8 còn
x2 tăng lên 1 thì z tăng lên 6.
Do ∆1 và ∆2 đều dương nên vẫn còn khả năng cải thiện hàm mục tiêu khi chuyển
sang (hay “xoay sang”) một phương án cực biên kề tốt hơn (quay lại nhận xét phần
giải bài toán bằng phương pháp đồ thị: điểm cực biên kề c a điểm (0, 0) có thể là A(0, 12) hay C(15, 0)).
Thủ tục xoay (pivotal procedure)
Bước 1: Chọn cột xoay là cột có ∆j > 0 t c là chọn biến xj làm biến cơ s mới do
xj tăng kéo theo hàm mục tiêu tăng. đây ta chọn đưa x1 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 x3). Do đó cần đưa x3 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)mới = (1) – (2)× (4)/(3), trong đó (3) là đỉnh tương ng với phần tử xoay (xem hình I.3). (2) (3)
Chẳng hạn: (1)cũ = 4, 2(cũ) = 2
(3)cũ = phần tử xoay = 4, (4)cũ = 2 2
⇒ (1)mới = 4 − 2 × = 3. 4 (1) (4)
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 4x1 + 2x2 + x3 = 60 (a) 2x1 + 4x2 + x4 = 48 (b) để có hệ
x1 + (1/2)x2 + (1/4)x3 = 15 (a’)
0x1 + 3x2 − (1/2)x3 + x4 = 18 (b’)
bằng cách lấy phương trình (a) chia cho 4 (phần tử xoay) để có (a’), rồi lấy (b) trừ bớt
2 × (a)/4 để có (b’). Đây chính là nội dung c a bước 4 và bước 5. Còn bước 3 sẽ đảm
bảo rằng giá trị c a các biến cơ s mới không âm (x1 = 15, x4 = 18).
Áp dụng th tục xoay cho các phần tử nằm trên hàng 1 và 2 c a bảng đơn hình
bước 1, sau đó tính các giá trị trên hàng zj và ∆j tương tự như khi lập bảng đơn hình
bước 1, chúng ta sẽ nhận được bảng đơn hình bước 2.
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ì x1 = 15 còn x2 = 0; giá trị c a hàm mục tiêu là
z0 = 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 x2 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 x1 = 12, x2 = 6, x3 = 0, x4 = 0, t c là tại điểm cực biên B(12, 6) với giá trị zmax = 132. Một số chú ý
− Điều kiện tối ưu cho các BTQHTT dạng Max là ∆j ≤ 0 ∀j.
− Đối với các BTQHTT cần cực tiểu hoá hàm mục tiêu thì điều kiện tối ưu (hay
tiêu chuẩn dừng) là ∆j ≥ 0 ∀j (nếu tồn tại j mà ∆j ≤ 0 thì cần tiếp tục cải thiện hàm mục
tiêu bằng cách chọn cột j làm cột xoay...).
− Trong thực tiễn giải các BTQHTT dạng tổng quát có thể xảy ra trư ng hợp
không tìm được phương án xuất phát (t c là không có phương án khả thi, xem thêm
mục 1.2). Lúc này có thể kết luận mô hình đã thiết lập có các điều kiện ràng buộc quá
chặt chẽ, cần xem xét nới lỏng các điều kiện này.
− Trong trư ng hợp ta tìm được cột xoay mà không tìm được hàng xoay thì kết
luận hàm mục tiêu không bị chặn trên (đối với các BTQHTT dạng Max) hoặc không bị
chặn dưới (đối với các BTQHTT dạng Min). Khi đó dừng quá trình giải và kết luận mô
hình quy hoạch tuyến tính đã thiết lập không phù hợp với thực tế.
1.4. Giải mô hình quy hoạch tuyến tính bằng các phần mềm tính toán
Hiện nay có nhiều phần mềm tính toán giải BTQHTT khá hiệu quả như Excel,
Lingo. Những phần mềm này rất thân thiện với ngư i dùng. Tuy nhiên cần nhấn mạnh
rằng, việc phát biểu được mô hình bài toán và phân tích, đánh giá được kết quả mới
chính là những khâu quan trọng nhất trong phương pháp mô hình hoá. Sau đây, chúng
ta dùng phần mềm Lingo để giải ví dụ đã xét trên. z = 8x1 + 6x2 → Max với các ràng buộc: 4x1 + 2x2 ≤ 60 2x1 + 4x2 ≤ 48 x1, x2 ≥ 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 > 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 tiết như trên hình I.5.
Hình I.5. Kết quả giải bài toán quy hoạch tuyến tính trong Lingo
Kết quả chi tiết cho ta biết giá trị cực đại c a hàm mục tiêu là 132 với phương án
tối ưu là: x1 = 12, x2 = 6. Các giá trị tối ưu c a các biến đối ngẫu là y1 = 5/3 và y2 = 2/3
(còn gọi là các giá ước định hay giá bóng Shadow Prices).
1.5. Một số ứng dụng của phương pháp đơn hình
(Giải các bài toán quy hoạch sản xuất trong lĩnh vực cơ khí và điện lực)
Bài toán phân phối điện năng
Có ba hộ phụ tải cần được cung cấp điện năng từ hai nguồn điện nằm cách xa
nhau. Giá thành truyền tải một đơn vị điện năng từ nguồn i đến hộ tiêu thụ j là cij. Khả
năng cung cấp điện năng c a mỗi nguồn bị giới hạn b i trữ lượng hiện có c a chúng là
A1 và A2. Nhu cầu tiêu dùng c a các hộ tiêu thụ là B1, B2 và B3. Gọi xij 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 xij sao cho tổng chi
phí là nhỏ nhất. Như vậy ta có BTQHTT sau: 2 3 z = c x ∑∑ ij ij → Min i 1 = j 1 =
với các điều kiện ràng buộc là: x11 + x12 + x13 ≤ A1, x21 + x22 + x23 ≤ A2, x11 + x21 = B1, x12 + x22 = B2, x13 + x23 = B3,
xij ≥ 0, ∀i = 1, 2 và ∀j = 1, 2, 3.
Bài toán trên đây (hoặc dạng tổng quát hơn) có thể giải được bằng phương pháp
đơ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 M1 và M2. Các loại máy này có thể sản xuất được ba
loại sản phẩm P1, P2 và P3 với các năng suất là aij, chẳng hạn máy M1 sản xuất sản phẩm
P2 với năng suất a12. Mỗi đơn vị sản phẩm mang lại lãi suất cj 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 bj đơn vị và không vượt quá dj đơn vị,
j = 1, 2, 3. Hãy lập kế hoạch phân tải cho các máy sao cho đạt tổng lợi nhuận lớn nhất.
Dễ thấy bài toán này dẫn tới BTQHTT sau: 3 2 z = c a x ∑ ∑ → Max j ij ij j 1 = i 1 =
với các điều kiện ràng buộc: a11x11 + a21x21 ≥ b1, a12x12 + a22x22 ≥ b2, a13x13 + a23x23 ≥ b3, a11x11 + a21x21 ≤ d1, a12x12 + a22x22 ≤ d2, a13x13 + a23x23 ≤ d3, x11 + x12 + x13 ≤ m1, x21 + x22 + x23 ≤ m2,
xij ≥ 0, i = 1, 2 và j = 1, 2, 3.
(trong đó m1 và m2 là tổng th i gian chạy máy M1 và M2).
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 = 8x1 + 6x2 → Max với các ràng buộc: ⎧4x + 2x ≤ 60 1 2 ⎪2x ⎨ + 4x ≤ 48 1 2 ⎪x ,x ⎩ ≥ 0 1 2
Đưa BTQHTT về dạng chính tắc như đã biết bằng cách thêm hai biến bù (slack
variables) x3 và x4. Ta có BTQHTT dạng chính tắc là:
z = 8x1 + 6x2 + 0x3 + 0x4 → Max ⎧4x + 2x + x = 60 1 2 3 ⎪2x ⎨ + 4x + x = 48 1 2 4 ⎪x ,x ,x ,x ⎩ ≥ 0 1 2 3 4
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 = 8x1 + 6x2 → Max với các ràng buộc: 4x ⎧ + 2x ≤ 60 1 2 ⎪2x ⎨ + 4x ≥ 48 1 2 ⎪x ,x ≥ 0 1 2 ⎩
Ta thêm các biến bù x3 (slack variable) mang dấu “+”, x4 (surplus variable) mang
dấu “−” để có hệ điều kiện ràng buộc sau: ⎧4x + 2x + x = 60 1 2 3 ⎪2x ⎨ + 4x − x = 48 1 2 4 ⎪x ,x ,x ,x ⎩ ≥ 0 1 2 3 4
Phải thêm biến giả x5 (x5 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 ⎧4x1 + 2x2 + x3 = 60 ⎪ ⎨2x 1 + 4x 2 − x 4 + x 5 = 48 ⎪⎩x ,x ,x ,x ,x 1 2 3 4 5 ≥ 0
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
bằng phương pháp đơn hình với hàm mục tiêu là z = 8x1 + 6x2 + 0x3 + 0x4 − Mx5 →
Max, trong đó M ≈ +∞ và biểu th c −Mx5 gọi là lượng phạt (đánh thuế). Bài toán đã
được đưa về dạng chính tắc. Lượng vi phạm x5 càng lớn thì hàm mục tiêu càng giảm,
giá trị c a hàm mục tiêu chỉ có thể đạt Max khi x5 = 0.
Ví dụ 3: (Trư ng hợp có biến không dương) z = 8x1 − 6x2 → Max với các ràng buộc: ⎧4x + 2x + x ≤ 60 1 2 3 ⎪2x ⎨ + 4x − x = 48 1 2 4 ⎪x
⎩ ≥ 0,x ≤ 0,x ≥ 0,x ≥ 0 1 2 3 4
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 = −x2.
Ta có BTQHTT với các biến đều không âm. z = 8x1 + 6x'2 → Max với các ràng buộc: ⎧4x − 2x ' + x ≤ 60 1 2 3 ⎪2x ⎨ − 4x ' − x = 48 1 2 4 ⎪x ,x' ,x ,x ⎩ ≥ 0 1 2 3 4
Ví dụ 4: (Trư ng hợp có biến với dấu tuỳ ý) z = 8x1 + 6x2 → Max với các ràng buộc: ⎧4x + 2x ≤ 60 1 2 ⎪2x ⎨ + 4x ≤ 48 1 2 ⎪x ⎩ ≥ 0,x dấu tuỳ ý 1 2
Lúc này ta viết biến x2 dưới dạng x2 = x'2 − x''2 với ⎧x ' = max[0,x ] ⎧x ' ≥ 0 2 ⎨ 2 thì đảm bảo 2 ⎨ x ' ⎩ = max[0,−x ] x ' ⎩ ≥ 0 2 2 2 Các ràng buộc sẽ là ⎧4x + 2x ' − 2x ' + x = 60 1 2 2 3 ⎪2x ⎨ + 4x ' − 4x ' + x = 48 1 2 2 4 ⎪x ,x' ,x' ,x ,x ⎩ ≥ 0 1 2 2 3 4
Bài toán với hàm mục tiêu là: z = 8x
1 + 6x'2 − 6x''2 + 0x3 + 0x4 và các điều kiện
ràng buộc trên là BTQHTT dạng chính tắc.
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 = 8x1 + 6x2 → Max với các ràng buộc: ⎧4x + 2x ≤ 60 1 2 ⎪ (a) 2x ⎨ + 4x ≥ 48 1 2 ⎪x ,x ⎩ ≥ 0 1 2
hay: z = 8x1 + 6x2 +0x3 + 0x4 → Max với các ràng buộc ⎧4x + 2x + x = 60 1 2 3 ⎪ (b) 2x ⎨ + 4x − x = 48 1 2 4 ⎪x ,x ,x ,x ⎩ ≥ 0 1 2 3 4
Ta có thể đưa bài toán về dạng chính tắc sau gọi là bài toán M: Max z = 8x
1 + 6x2 +0x3 + 0x4 − Mx5 (trong đó M ≈ +∞) với các ràng buộc ⎧4x + 2x + x = 60 1 2 3 ⎪ (c) 2x ⎨ + 4x − x + x = 48 1 2 4 5 ⎪x ,x ,x ,x ,x ⎩ ≥ 0 1 2 3 4 5
Cách 1: Có thể giải BTQHTT với các điều kiện ràng buộc (a) bằng phương pháp
đồ thị để nhận được kết quả: phương án tối ưu là (x1 = 0, x2 = 30) và zmax = 180.
Cách 2: Giải BTQHTT với các điều kiện ràng buộc (c) bằng cách lập bảng đơn
hình như thông thư ng nhưng chú ý hệ số M ≈ +∞ (xem bảng I.2).
Bảng I.2. Các bảng đơn hình giải bài toán M Hệ số 8 6 0 0 Phương −M Biến hàm mục cơ s án tiêu x1 x2 x3 x4 x5 0 x3 60 4 2 1 0 0 −M x5 48 2 4 0 −1 +1 Hàng z
z0 = −48M z1 = −2M z2 = −4M z3 = 0 z4 = M z5 = −M Hàng ∆ ∆ j 1 = 8+2M ∆2 = 6+4M ∆3 = 0 ∆4 = −M ∆5 = 0 0 x3 36 3 0 1 1/2 −1/2 6 x2 12 1/2 1 0 −1/4 1/4 Hàng z 72 3 6 0 −3/2 3/2 Hàng ∆ 5 0 0 3/2 − j M − 3/2 0 x4 72 6 0 2 1 −1 6 x2 30 2 1 1/2 0 0 Hàng z 180 12 6 3 0 0 Hàng ∆ − j 4 0 −3 0 −M
Tại bảng đơn hình cuối cùng, ta thấy ∆j ≤ 0 ∀j nên phương án tối ưu đã đạt được
với x2 = 30, x4 = 72, các xj khác = 0 và zMax = 180. Lưu ý
− Khi một biến giả đã được đưa ra khỏi cơ s thì không bao gi quay lại nữa. Do
đó ta có thể xoá cột biến giả đó khỏi bảng đơn hình.
− Nếu dấu hiệu dừng xuất hiện (∆j ≤ 0 ∀j) nhưng vẫn còn biến giả với giá trị
dương trong số các biến cơ s thì điều này ch ng tỏ bài toán ban đầu không thể có
phương án khả thi (có thể ch ng minh bằng phản ch ng).
− Với ví dụ trên (xem bảng I.2) ta thấy quá trình giải chia làm hai pha: pha 1
nhằm giải bài toán M cho tới khi biến giả (x5) được đưa ra khỏi số biến cơ s (lúc này
có phương án cực biên xuất phát cho bài toán (b)) và pha 2 nhằm tìm phương án tối ưu cho bài toán (b).
− Phần mềm tính toán Lingo có thể giải được tất cả các BTQHTT không đòi hỏi
ngư i dùng phải đưa chúng về dạng chính tắc.
3. Mô hình quy hoạch tuyến tính đa mục tiêu 3.1. Các khái
niệm cơ bản
Phát biểu mô hình
Trong các bài toán kĩ thuật, công nghệ, quản lí, kinh tế nông nghiệp v.v... nảy
sinh từ thực tế, chúng ta thư ng phải xem xét để tối ưu hoá đồng th i một lúc nhiều
mục tiêu. Các mục tiêu này thư ng là khác về th nguyên, t c là chúng được đo b i các
đơn vị khác nhau. Những tình huống như vậy tạo ra các bài toán tối ưu đa mục tiêu.
Như vậy, chúng ta cần phải tối ưu hoá (cực đại hoá hoặc cực tiểu hoá tuỳ theo tình
huống thực tế) không phải là chỉ một mục tiêu nào đó, mà là đồng th i tất cả các mục tiêu đã đặt ra.
Bài toán tối ưu đa mục tiêu mà trong đó miền ràng buộc D là tập lồi đa diện và
các mục tiêu zi = fi(X), với i = 1, 2,…, p, là các hàm tuyến tính xác định trên D, được
gọi là bài toán quy hoạch tuyến tính đa mục tiêu. Khi đó, ta có mô hình toán học sau
đây được gọi là mô hình quy hoạch tuyến tính đa mục tiêu :
Max CX với ràng buộc X D, trong đó:
C là ma trận cấp p
× n
D = { X
Rn: AX ≤ B}
với A là ma trận cấp m
× n và B Rm.
Ví dụ: BTQHTT với hai mục tiêu
f1(X) = x1 + 2x2 → Min hay z1 = f’1 (X) = −x1 − 2x2 → Max z2 = f2(X) = 2x2, → Max với các ràng buộc ⎧−x + x ≤ 3 1 2 ⎪ x ⎨ + x ≥ 3 1 2 ⎪ x , x ⎩ ≥ 0 1 2
Ta có thể viết bài toán này dưới dạng ma trận như sau: Max CX với ràng buộc
X ∈ D = {X∈ R2 : AX ≤ B}, trong đó X = (x1, x2)T, B = (3, −3, 0, 0)T, còn ⎡ 1 − 1 ⎤ ⎡− ⎢ ⎥ 1 − 2⎤ 1 − 1 − C = , A = ⎢ ⎢ ⎥ . ⎣ ⎥ 0 2 ⎦ ⎢ 1 − 0⎥ ⎢ ⎥ 0 ⎣ 1 − ⎦
Có thể nói, BTQHTT đa mục tiêu là BTQHTT mà trong đó chúng ta phải tối ưu
hoá cùng một lúc nhiều mục tiêu. Tuy nhiên, các mục tiêu này thư ng đối chọi cạnh
tranh với nhau. Việc làm tốt hơn mục tiêu này thư ng dẫn tới việc làm xấu đi một số
mục tiêu khác. Vì vậy việc giải các bài toán tối ưu đa mục tiêu, t c là tìm ra một
phương án khả thi tốt nhất theo một nghĩa nào đó, thực chất chính là một bài toán ra
quyết định. Có thể thấy lại đây một lần nữa khẳng định "Tối ưu hoá chính là công cụ
định lượng ch yếu nhất c a quá trình ra quyết định".
Hiện tại các tài liệu, sách chuyên khảo, tạp chí cập nhật về lĩnh vực liên ngành
Toán − Tin, Khoa học quản lí, Công nghệ, Kinh tế, Điện, Cơ khí nông nghiệp,... đề cập
rất nhiều tới bài toán tối ưu đa mục tiêu. Vấn đề nghiên c u cơ s lí thuyết, thuật toán,
lập mô hình, xây dựng hệ máy tính trợ giúp quyết định, và áp dụng các mô hình tối ưu
đa mục tiêu cho các quá trình công nghệ, quản lí,... là một vấn đề liên ngành được rất
nhiều nhà khoa học và kĩ sư thực hành quan tâm.
Phương án tối ưu Pareto
Khái niệm then chốt trong tối ưu hoá đa mục tiêu là khái niệm phương án tối ưu Pareto.
Định nghĩa: Một phương án tối ưu Pareto X* có tính chất sau đây:
− Trước hết nó phải thuộc vào miền các phương án khả thi c a bài toán, t c là
phải thoả mãn tất cả các ràng buộc: X* ∈ D.
− Với mọi phương án khả thi khác X ∈ D mà có một mục tiêu nào đó tốt hơn (fi(X)
tốt hơn fi(X*)) thì cũng phải có ít nhất một mục tiêu khác xấu hơn (fj(X) xấu hơn fj(X*), j ≠ i).
Nói một cách khác, không tồn tại một phương án khả thi nào X ∈ D có thể trội hơn X* trên tổng thể.
Để minh hoạ định nghĩa trên, ta xét ví dụ đã cho. Ví dụ:
Xét BTQHTT với hai mục tiêu. f1 (X) = x1 + 2x2 → Min f2 (X) = 2x2 → Max Với các ràng buộc ⎧−x 3 1 + x2 ≤ ⎪ ⎨ x 3 1 + x2 ≥ ⎩⎪ x ,x 0 1 2 ≥ y d A 3 D 2 rn2 B o -3 3 x r n1
Hình I.6. Minh hoạ đồ thị BTQHTT hai mục tiêu
Miền các phương án khả thi D (miền giới hạn b i đoạn AB và các tia Ad, Bx) đượ r r
c biểu thị trên hình I.6. n (−1, −2) là hướng giảm c a mục tiêu 1, còn n (0, 2) là 1 2
hướng tăng c a mục tiêu 2.
Lúc này A(0, 3) cũng như B(3, 0) là hai phương án tối ưu Pareto c a bài toán trên.
Dễ thấy tập hợp P tất cả các phương án tối ưu Pareto bao gồm các điểm nằm trên đoạn AB và Ad.
3.2. Một số phương pháp giải BTQHTT đa mục tiêu Định nghĩa 1
Giải bài toán tối ưu toàn cục đa mục tiêu là chọn ra từ tập hợp P các phương án
tối ưu Pareto c a bài toán một (hoặc một số) phương án tốt nhất (thoả mãn nhất) theo
một nghĩa nào đó dựa trên cơ cấu ưu tiên c a ngư i ra quyết định.
Trong ví dụ trên, tuỳ theo cơ cấu ưu tiên c a ngư i ra quyết định, chúng ta có thể
chọn ra một hoặc một số điểm tối ưu Pareto nằm trên AB hoặc tia Ad làm phương án tối ưu c a bài toán.
Cách 1: Bằng một phương pháp tối ưu toán học thích hợp tìm ra tập hợp P tất cả các
phương án tối ưu Pareto. Ngư i ra quyết định sẽ đề ra cơ cấu ưu tiên c a mình đối với tập
P nhằm tìm ra phương án tối ưu Pareto thoả mãn nhất cho bài toán đa mục tiêu ban đầu.
Cách 2: Việc tìm tập hợp P trong trư ng hợp các bài toán nhiều biến là khá khó
và mất nhiều th i gian. Vì vậy, so với cách 1, cách 2 sẽ tiến hành theo trình tự ngược
lại. Trước hết ngư i ra quyết định sẽ đề ra cơ cấu ưu tiên c a mình. Dựa vào cơ cấu ưu
tiên đó, các mục tiêu sẽ được tổ hợp vào một mục tiêu duy nhất, tiêu biểu cho hàm tổng
tiện ích c a bài toán. Bài toán tối ưu với hàm mục tiêu tổ hợp này sẽ được giải bằng
một phương pháp tối ưu toán học thích hợp, để tìm ra một (hoặc một số) phương án tối
ưu Pareto. Lúc này, ngư i ra quyết định sẽ chọn ra trong số các phương án tối ưu Pareto
đó một phương án tốt nhất.
Chúng ta sẽ tiếp tục phân tích cách th 2. Rõ ràng, ngư i ra quyết định không thể
đề ra cơ cấu ưu tiên c a mình một cách chính xác ngay từ đầu. Trong quá trình giải bài
toán, trong mỗi bước lặp, sau khi xem xét lại cơ cấu ưu tiên đã đề ra, cũng như phương
án trung gian vừa tìm được, ngư i ra quyết định có thể dựa vào các thông tin đó để thay
đổi lại cơ cấu ưu tiên c a mình. Sau đó, quá trình giải lại được tiếp tục, cho tới khi một
phương án tối ưu cuối cùng được đưa ra. Định nghĩa 2
Phương pháp giải bài toán tối ưu đa mục tiêu dựa trên sự trợ giúp c a hệ máy
tính, nhằm giúp ngư i ra quyết định từng bước thay đổi các quyết định trung gian một
cách thích hợp để đi tới một phương án tối ưu Pareto thoả mãn nhất, được gọi là
phương pháp tương tác ngư i − máy tính.
Phương pháp tương tác ngư i − máy tính giải bài toán tối ưu đa mục tiêu có các yếu tố cấu thành sau:
− Cơ cấu ưu tiên c a ngư i ra quyết định và hàm tổ hợp tương ng.
− Kiểu tương tác ngư i − máy tính: cho biết các thông tin nào máy tính phải đưa
ra lại trong các bước lặp trung gian, và cách thay đổi các thông số c a cơ cấu ưu tiên từ
phía ngư i ra quyết định.
− Kĩ thuật tối ưu toán học được xây dựng dựa trên lí thuyết tối ưu hoá nhằm tìm
ra các phương án tối ưu Pareto cho các bài toán cần giải trong các bước lặp trung gian.
Cho tới th i điểm hiện nay, hàng chục phương pháp giải BTQHTT đa mục tiêu đã
được đề cập tới trong các tạp chí chuyên ngành, mà đa số chúng đều có những ng
dụng rất thành công trong nhiều lĩnh vực, như: phương pháp tham số, phương pháp nón
pháp tuyến, phương pháp véc tơ cực đại, phương pháp trọng số tương tác c a
Chebysev, phương pháp thoả dụng m tương tác c a Nguyễn Hải Thanh.
3.3. Phương pháp thoả dụng mờ tương tác giải BTQHTT đa mục tiêu Thuật giải a. Bước khởi tạo
− Nhập số liệu cho các hàm mục tiêu tuyến tính zi (i = 1, 2,..., p) và m điều kiện ràng buộc.
− Giải BTQHTT cho từng mục tiêu zi (i = 1, 2,..., p) với m ràng buộc ban đầu,
thu được các phương án tối ưu X1, X2,..., Xp (nếu với một mục tiêu nào đó bài toán
không cho phương án tối ưu thì cần xem xét để chỉnh sửa lại các điều kiện ràng buộc ban đầu).
− Tính giá trị hàm mục tiêu tại p phương án X1, X2,..., Xp.
Lập bảng pay−off. Xác định giá trị cận trên B
z và giá trị cận dưới w z c a mục tiêu i i zi (i=1, 2,..., p).
− Xác định các hàm thoả dụng m µ1(z1), µ2(z2),..., µp(zp) cho từng mục tiêu dựa
vào thông tin từ bảng pay−off theo công th c: w z − z i i µ (z ) = , i = 1, 2,..., p. i i B w z − z i i − Đặt k: = 1.
b. Các bước lặp (xét bước lặp thứ k)
Bước 1: Xây dựng hàm mục tiêu tổ hợp từ các hàm thoả dụng trên:
w1µ1(z1) + w 2µ2(z2) +... + w pµp(zp) → Max
Trong đó: w1, w2,..., wp là các trọng số phản ánh tầm quan trọng c a từng hàm
thoả dụng trong thành phần hàm tổ hợp, với
w1 + w 2 +... + w p = 1 và 0 ≤ w 1, w 2,..., w p ≤ 1. Bước 2:
− Giải BTQHTT với hàm mục tiêu tổ hợp và m ràng buộc ban đầu để tìm được
phương án tối ưu c a bước lặp th k là X(k) và giá trị c a các hàm mục tiêu zi cũng như
c a các hàm thoả dụng µi(zi) (với i =1, 2,..., p).
− Nếu ngư i ra quyết định cảm thấy chưa thoả mãn với các giá trị đạt được c a
các hàm mục tiêu cũng như c a các hàm thoả dụng thì phương án thu được X(k) chưa
phải là phương án tối ưu thoả mãn nhất. Đặt k:= k + 1, quay về bước 1.
− Nếu ngư i ra quyết định đã cảm thấy thoả mãn thì phương án thu được là X(k). Chuyển sang bước 3.
Bước 3: Kết thúc.
Ví dụ: Giải BTQHTT hai mục tiêu. z1 = 8x1+ 6x2 → Max z2 = x1 + 3x2 → Max với các ràng buộc: 4x + 3x ≤ 60 1 2 (D) 2x + 4x ≤ 48 1 2 x , x ≥ 0 1 2 a. Bước khởi tạo
− Giải BTQHTT cho từng mục tiêu trong ví dụ trên ta có hai bài toán: Max z1 = 8x1 +
6x2 → Max với điều kiện ràng buộc (D) cho phương án tối ưu X1(12, 6) và Max z1 = 132;
z2 = x1 + 3x2 → Max cho phương án tối ưu X2(0, 12) và Max z2 = 36.
Như vậy miền phương án tối ưu Pareto chính là mọi phương án thuộc AB (xem r r
hình I.1), với A(0, 12) và B(12, 6). n (8, 6) là hướng tăng c a mục tiêu 1, còn n (1, 3) 1 2
là hướng tăng c a mục tiêu 2. Do đó, khi chọn phương án tối ưu Pareto dịch dần từ B
về A thì z1 giảm, z2 tăng. Cần tìm phương án tối ưu Pareto "thoả mãn nhất" thuộc AB
bằng cách “thương lượng” giữa z1 và z2.
− Lập bảng pay−off cho các mục tiêu Phương án Xi z1 z2 X1(12, 6) 132 30 X2(0, 12) 72 36
Dựa trên thông tin c a bảng pay−off, ta có W z = 72, B z = 132; còn W z = 30, 1 1 2 B
z = 36. Do đó, đoạn biến thiên cần xét cho z 2
1 là [72, 132] và cho z2 là [30, 36]. Từ đó
chúng ta có thể thiết lập các hàm thoả dụng m ng với hai mục tiêu đã cho như sau: W µ z z z − 72 z 72 z (z ) 1 1 = = 1 = 1 − = 1 − 1,2 1 1 B W z z 132 − 72 60 60 60 1 1
Hàm thoả dụng m trên đây phụ thuộc vào z1, nên phụ thuộc vào (x1, x2). Khi có
một phương án khả thi (x1, x2) ta tính được độ thoả dụng µ (z ) đối với mục tiêu z 1 1 1.
Tương tự đối với z2 ta có hàm thoả dụng m : W µ z z z − 30 z (z ) = 2 2 = 2 = 2 − 5. 2 2 B W z z 36 − 30 6 2 2
Lập hàm thoả dụng tổ hợp u = w1 µ (z ) + w µ (z ) , trong đó w 1 1 2 2 2 1, w2 là các trọng