ThS. Nguyễn Công Trí - Tối ưu hóa * Chương 1
CHÖÔNG 1
MOÄT VAØI VÍ DUÏ VEÀ BAØI TOAÙN QHTT
BAØI TOAÙN QUY HOAÏCH TUYEÁN TÍNH
(Xem)
1. THIEÁT LAÄP MOÂ HÌNH BAØI TOAÙN
2. CAÙC DAÏNG CUÛA BAØI TOAÙN QUY
(Xem)
Ths. Nguyeãn Coâng Trí
HOAÏCH TUYEÁN TÍNH
3. CAÙC KHAÙI NIEÄM CÔ BAÛN VEÀ BAØI TOAÙN
(Xem)
QUY HOAÏCH TUYEÁN TÍNH
Copyright 2001
4. CAÙC PHÖÔNG PHAÙP GIAÛI BAØI TOAÙN
QUY HOAÏCH TUYEÁN TÍNH
(Xem) Ths. Nguyeãn Coâng Trí
(Xem)
5. BAØI TAÄP
Copyright 2001
Soá löôïng hieän coù (ñv) 250 350 450 Ví duï 1.1. BAØI TOAÙN LAÄP KEÁ HOAÏCH SAÛN XUAÁT Moät xí nghieäp duøng 3 loaïi nguyeân lieäu: N1; N2; N3 ñeå saûn xuaát ra moät loaïi saûn phaåm theo 3 phöông phaùp khaùc nhau: PP1; PP2; PP3. Ñònh möùc nguyeân lieäu vaø soá löôïng saûn phaåm saûn xuaát ra trong 1 giôø ñöôïc cho ôû baûng sau: Nguyeân Lieäu N1 N2 N3 Ñònh möùc nguyeân lieäu PP3 PP2 3 5 1 4 4 6 9 12 Soá saûn phaåm (sp/giôø) PP1 4 2 3 10
MOÄT VAØI VÍ DUÏ VEÀ BAØI TOAÙN QHTT
Haõy laäp moâ hình baøi toaùn sao cho xí nghieäp saûn xuaát ra nhieàu saûn phaåm nhaát?
Ví duï 1.2. BAØI TOAÙN PHA CAÉT VAÄT LIEÄU Moät xí nghieäp may maëc caàn saûn xuaát ñuùng 2.000 quaàn vaø ít nhaát 1.000 aùo. Moãi taám vaûi coù 6 caùch caét nhö sau:
Caùch caét Quaàn AÙo 35 55 70 90 0 100 90 80 70 60 120 0 1 2 3 4 5 6
MOÄT VAØI VÍ DUÏ VEÀ BAØI TOAÙN QHTT Goïi x1, x2, x3 laàn löôït laø thôøi gian saûn xuaát ra saûn phaåm theo 3 phöông phaùp PP1, PP2, PP3. Toång saûn phaåm saûn xuaát (caàn laøm cöïc ñaïi) f(x) = 10x1 + 12x2 + 9x3 max Do xí nghieäp chæ coù 250 nguyeân lieäu N1 neân x1, x2, x3 phaûi thoûa maõn 4x1 + 5x2 + 3x3 ≤ 250 Töông töï cho caùc nguyeân lieäu N2, N3 ta coù 2x1 + 4x2 + x3 ≤ 350 vaø 3x1 + 6x2 + 4x3 ≤ 450 Dó nhieân ta phaûi coù x1, x2, x3 khoâng aâm Vaäy moâ hình baøi toaùn ñöôïc phaùt bieåu nhö sau: Tìm caùc bieán x1, x2, x3 sao cho f(x)= 10x1 + 12x2 + 9x3 max, thoûa caùc ñieàu kieän 4x1 + 5x2 + 3x3 ≤ 250 2x1 + 4x2 + x3 ≤ 350 3x1 + 6x2 + 4x3 ≤ 450 x1 0 x2 0 x3 0
1
Haõy tìm phöông aùn caét quaàn aùo sao cho toång soá taám vaûi laø ít nhaát?
ThS. Nguyễn Công Trí - Tối ưu hóa * Chương 1
MOÄT VAØI VÍ DUÏ VEÀ BAØI TOAÙN QHTT
Ví duï 1.3. BAØI TOAÙN XAÙC ÑÒNH KHAÅU PHAÀN Ñeå nuoâi moät loaïi gia suùc coù hieäu quaû, moãi ngaøy caàn phaûi coù khoái löôïng toái thieåu caùc chaát protit, glucit, khoaùng töông öùng laø 90 gram, 130 gram, 10 gram. Tyû leä (%) theo khoái löôïng caùc chaát treân coù trong caùc loaïi thöùc aên A, B, C nhö sau: Chaát dinh döôõng (%) Thöùc aên Protit Glucit
A B C 10 20 30 30 40 20 Khoaùng 2 1 3
MOÄT VAØI VÍ DUÏ VEÀ BAØI TOAÙN QHTT Goïi xj (j = 1, 2, ..., 6) laø soá taám vaûi ñöôïc caét theo caùch thöù j. Toång soá taám vaûi duøng ñeå saûn xuaát (caàn laøm cöïc tieåu) laø f(x) = x1 + x2 + x3 + x4 + x5 + x6 min Do xí nghieäp caàn saûn xuaát ñuùng 2.000 quaàn neân caùc xj phaûi thoûa maõn 90x1 + 80x2 + 70x3 + 60x4 + 120x5 = 2000 Töông töï cho ñieàu kieän veà saûn xuaát aùo, ta coù + 100x6 1000 35x1 + 55x2 + 70x3 + 90x4 Dó nhieân ta phaûi coù xj (j = 1, 2, ..., 6) khoâng aâm Vaäy moâ hình baøi toaùn ñöôïc phaùt bieåu nhö sau: Tìm caùc bieán xj (j = 1, 2, ..., 6) sao cho f(x)= xj min, thoûa caùc ñieàu kieän 90x1 + 80x2 + 70x3 + 60x4 + 120x5 35x1 + 55x2 + 70x3 + 90x4 xj 0, (j = 1, 2, ..., 6).
MOÄT VAØI VÍ DUÏ VEÀ BAØI TOAÙN QHTT
= 2000 + 100x6 1000 Giaù 1 kg thöùc aên A, B, C töông öùng laø 3.000 ñoàng, 4.000 ñoàng, 5.000 ñoàng. Haõy laäp moâ hình baøi toaùn xaùc ñònh khoái löôïng thöùc aên caàn thieát sao cho chi phí nuoâi gia suùc laø thaáp nhaát?
Ví duï 1.4. BAØI TOAÙN VAÄN TAÛI Caàn vaän chuyeån xi maêng töø 3 kho K1, K2, K3 ñeán 4 coâng tröôøng xaây döïng T1, T2, T3, T4. Cho bieát löôïng xi maêng coù ôû moãi kho, löôïng xi maêng caàn ôû moãi coâng tröôøng vaø cöôùc phí vaän chuyeån (ngaøn ñoàng/ taán) töø moãi kho ñeán coâng tröôøng nhö sau: Coâng tröôøng T1: 130 t T2: 160 t T3: 120 t T4: 140 t
20 15 45 18 25 30 22 30 40 25 15 35
MOÄT VAØI VÍ DUÏ VEÀ BAØI TOAÙN QHTT Goïi xj (j = 1, 2, 3) laø soá gram thöùc aên A, B, C caàn mua moãi ngaøy. Toång chi phí duøng ñeå mua thöùc aên (caàn laøm cöïc tieåu) laø f(x) = 3x1 + 4x2 + 5x3 min (ñoàng) Do caùc tyû leä caùc chaát protit, glucit vaø khoaùng coù trong thöùc aên A neân caùc xj phaûi thoûa maõn 0,1x1 + 0,2x2 + 0,3x3 90 Töông töï cho ñieàu kieän cuûa thöùc aên B vaø C, ta coù 0,3x1+0,4x2+0,2x3 130 vaø 0,02x1+0,01x2+0,03x310 Vaäy moâ hình baøi toaùn ñöôïc phaùt bieåu nhö sau: Tìm caùc bieán xj (j = 1, 2, 3) sao cho f(x) = 3x1 + 4x2 + 5x3 min, thoûa caùc ñieàu kieän 0,1x1 + 0,2x2 + 0,3x3 90 0,3x1 + 0,4x2 + 0,2x3 130 0,02x1 + 0,01x2 + 0,03x3 10 xj 0, (j = 1, 2, 3).
2
Kho K1: 170 taán K2: 200 taán K3: 180 taán Laäp moâ hình baøi toaùn vaän chuyeån sao cho caùc kho phaùt heát xi maêng coù, coâng tröôøng nhaän ñuû xi maêng caàn vaø chi phí vaän chuyeån thaáp nhaát?
ThS. Nguyễn Công Trí - Tối ưu hóa * Chương 1
CAÙC DAÏNG CUÛA BAØI TOAÙN QHTT
n
f x ( )
min (
hay
max)
(2.1)
j
j
1
MOÄT VAØI VÍ DUÏ VEÀ BAØI TOAÙN QHTT Goïi xij (i = 1, 2, 3, j = 1, 2, 3, 4) laø löôïng xi maêng caàn vaän chuyeån töø kho Ki ñeán coâng tröôøng Tj. Toång chi phí vaän chuyeån (caàn laøm cöïc tieåu) laø f(x) = 20x11 + 18x12 + 22x13 + 25x14 15x21 + 25x22 + 30x23 + 15x24 45x31 + 30x32 + 40x33 + 35x34 min
2.1. DAÏNG TOÅNG QUAÙT Tìm x = (x1, x2,..., xn) sao cho:
n
1,
m
2.2
a x ij
j
b i i
1
j
x
n
0,
0,
2.3
k
c x j x k
j
Ñieàu kieän cuûa caùc kho
x11 + x12 + x13 + x14 = 170 x21 + x22 + x23 + x24 = 200 x31 + x32 + x33 + x34 = 180 Ñieàu kieän cuûa caùc coâng tröôøng laø heä raøng
j laø haøm muïc tieâu. (2.2) goïi (2.1) goïi buoäc. (2.3) goïi laø raøng buoäc veà daáu cuûa aån soá. Ví duï 1.1, Ví duï 1.2 vaø Ví duï 1.3 laø caùc baøi toaùn QHTT coù daïng toång quaùt.
CAÙC DAÏNG CUÛA BAØI TOAÙN QHTT
CAÙC DAÏNG CUÛA BAØI TOAÙN QHTT
x11 + x21 + x31 = 130 x12 + x22 + x32 = 160 x13 + x23 + x33 = 120 x14 + x24 + x34 = 140 xij 0, i = 1, 2, 3, j = 1, 2, 3, 4.
2.2. DAÏNG CHÍNH TAÉC
f x ( )
hay
max)
j
c x j
j 1 n
1,
m
a x ij
j
b i i
j
1
x
0,
j
1,
n
j
Tìm x = (x1, x2,..., xn) sao cho: n min ( laø mieàn
3
Nhaän xeùt: Heä raøng buoäc cuûa baøi toaùn daïng chính taéc ñeàu laø caùc ñaúng thöùc vaø moïi bieán cuûa baøi toaùn ñeàu khoâng aâm. Ví duï 1.4 BAØI TOAÙN VAÄN TAÛI coù daïng chính taéc. Moät vectô x = (x1, x2,..., xn) thoûa maõn ñieàu kieän (2) vaø (3) ñöôïc goïi laø moät phöông aùn (P.A) cuûa baøi toaùn quy hoaïch tuyeán tính (QHTT). Taäp caùc P.A cuûa baøi toaùn ñöôïc goïi raøng buoäc hay mieàn xaùc ñònh. Kyù hieäu laø D. Phöông aùn toái öu (P.A.T.Ö) hay nghieäm cuûa baøi toaùn, kyù hieäu laø Xopt (optimality), neáu vectô X laø moät P.A vaø haøm muïc tieâu (2.1) bò chaën. Baøi toaùn ñöôïc goïi laø giaûi ñöôïc hay coù lôøi giaûi hay coù nghieäm neáu noù coù ít nhaát moät P.A.T.Ö. Baøi toaùn khoâng giaûi ñöôïc hay voâ nghieäm neáu D = hay noù coù P.A nhöng khoâng coù PA.T.Ö.
ThS. Nguyễn Công Trí - Tối ưu hóa * Chương 1
CAÙC DAÏNG CUÛA BAØI TOAÙN QHTT
CAÙC DAÏNG CUÛA BAØI TOAÙN QHTT
n
f x ( )
hay
max)
j
c x j
j
1
n m
1,
m
x a i m k m k ,
b i , i
x i
k
1
j
x
0
0
j
n b i
j = – xj 0.
j sao cho xj = x/
j vaø x//
j – x//
2.3. DAÏNG CHUAÅN Tìm x = (x1, x2,..., xn) sao cho: min (
j 0, x//
j 0.
1, Nhaän xeùt: Baøi toaùn daïng chuaån laø baøi toaùn ôû daïng chính taéc vôùi heä raøng buoäc chöùa ma traän con Im laø ma traän ñôn vò caáp m. Trong ñoù caùc xi (i = 1, 2,..., m) ñöôïc goïi laø aån cô baûn (A.C.B), coøn caùc aån xi,m+k, (k = 0, 1,..., n – m) ñöôïc goïi laø aån khoâng cô baûn.
CAÙC DAÏNG CUÛA BAØI TOAÙN QHTT
CAÙC DAÏNG CUÛA BAØI TOAÙN QHTT
2.4. CHUYEÅN ÑOÅI DAÏNG BAØI TOAÙN QHTT Khi xeùt baøi toaùn QHTT, ngöôøi ta thöôøng söû duïng daïng chính taéc, coù theå ñöa baøi toaùn daïng toång quaùt veà daïng chính taéc baèng caùc bieán ñoåi sau: 1) Neáu raøng buoäc thöù i coù daïng aijxj ≤ bi thì theâm vaøo moät aån phuï xn+1 0, sao cho aijxj + xn+1 = bi. 2) Neáu raøng buoäc thöù i coù daïng aijxj bi thì theâm vaøo moät aån phuï xn+1 0, sao cho aijxj – xn+1 = bi. 3) Neáu aån xj ≤ 0 thì ñöôïc thay baèng x/ 4) Neáu aån xj khoâng raøng buoäc veà daáu thì thay xj baèng hai aån phuï x/ j, vôùi x/
0
j
Ñeå baøi toaùn goïn hôn, chuùng ta duøng caùc kyù hieäu
a 12 a 22
,
x
b
c ,
0 ,
,
A
A
,
j
f x ( )
3
2
min
x 2
x 3
a 1 a 2 j
x 1 x 2
c 1 c 2
b 1 b 2
0
a a 11 1 n a a 21 2 n
2
0
a mj
b m
c n
x n
2
a m
a m 1
a mn
4 3
3 2 4
7 12 10
8
x 1 x 1 x 1 x 1
x 3 x 3 x 3
0
0
x 3
Trong ñoù A laø ma traän mn goàm caùc heä soá ôû veá traùi cuûa heä raøng buoäc; Aj laø vectô coät thöù j cuûa ma traän A; b laø vectô heä soá ôû veá phaûi cuûa heä raøng buoäc; c laø vectô heä soá ôû haøm muïc tieâu; x laø vectô aån soá; 0 laø vectô khoâng. Khi ñoù baøi toaùn QHTT ôû daïng chính taéc coù daïng f(x) = cTx min (hay max)
Ví duï 1.5. Ñöa baøi toaùn QHTT sau ñaây veà daïng chính taéc vaø vieát baøi toaùn chính taéc döôùi daïng ma traän
x 2 x 2 x 2 x 1 Theâm 2 aån phuï x4, x5 0 vaøo raøng buoäc thöù nhaát vaø raøng buoäc thöù ba. Thay x/ 3 = –x3 0 2 –x// Thay x2 = x/
2 0, vôùi x/
2, x//
2 0
4
Ax = b, x 0
ThS. Nguyễn Công Trí - Tối ưu hóa * Chương 1
CAÙC DAÏNG CUÛA BAØI TOAÙN QHTT
CAÙC DAÏNG CUÛA BAØI TOAÙN QHTT
f x ( )
min
3
3
x 2
x 2
f x ( )
min
x 5
2
x 4
2
1
x 2 x 1
x 5
3
3
x 3
x 3
3 2 4
7 12 10
2
x 2 x 2 2 x 2
x 5 x 5
x 4
x 1 x 1 x 1 x 1
0,
0,
0,
0,
x 2 x 2 x 2
x 3 x 3 x 3 0,
0
x 1
x 4
x 5 x 5
8 x 3
4 3 x 2
x
0
j
1,5
j
Ví duï 1.6. Cho baøi toaùn QHTT: Baøi toaùn QHTT coù daïng chính taéc nhö sau 2
3, x4, x5) min
2, x//
2, x/
1
1
00
2
A
0 0
3 01 102
1 1
2 1 1 0 8 0
1 4 3
1 4 3
0 0 1
7 12 10
3 2 4
Ta coù ma traän heä soá cuûa heä raøng buoäc:
x 2 4 x 2 3 x 2 x 2 Baøi toaùn QHTT döôùi daïng ma traän nhö sau f(x) = (1, 3, – 2, 0, 0, 0)T(x1, x/ x 1 x 2 x 2 x 3 x 4 x 5 3, x4, x5) (0, 0, 0, 0, 0, 0)
2, x//
2, x/
ÑÒNH NGHÓA PHÖÔNG AÙN CÖÏC BIEÂN
min
23
16
f x
( ) 50
x 3
x 2
4
2
3
5
x 3
x 2
ÑÒNH NGHÓA PHÖÔNG AÙN CÖÏC BIEÂN Moät phöông aùn x* = (x1*, x2*,..., xn*) cuûa baøi toaùn QHTT daïng toång quaùt laø phöông aùn cöïc bieân (P.A.C.B) neáu x* = (x1*, x2*,..., xn*) thoûa maõn chaët n raøng buoäc ñoäc laäp tuyeán tính. Töùc laø:
n
*
a x = b , i=1,k, k m
i
ij
j
3
2 1
j=1
*
k +l n,det A
0
*X la P.A.C.B
4
2
x 3 x 3
* j
0
0
chöùa I3 neân baøi toaùn quy hoaïch tuyeán tính treân coù daïng chuaån. (x1, x/
x 2 x 2 x 3
Caùc vectô naøo sau ñaây
Z
2,
,
X
0, 1, 3
Y
3, 0, 0
23 5
6 5
Ví duï 1.7. Cho baøi toaùn QHTT x 1 x 1 x 1 x 1 x 6 1 x 2
x =0, j=1,l, l n Trong ñoù A laø ma traän con caáp n cuûa hpt (*). Moät P.A.C.B khoâng suy bieán laø moät P.A.C.B thoûa maõn ñuùng n raøng buoäc chaët. Moät P.A.C.B suy bieán laø moät P.A.C.B thoûa maõn hôn n raøng buoäc chaët. P.A.C.B coøn ñöôïc goïi laø phöông aùn cô baûn.
5
laø phöông aùn cöïc bieân?
ThS. Nguyễn Công Trí - Tối ưu hóa * Chương 1
ÑÒNH NGHÓA PHÖÔNG AÙN CÖÏC BIEÂN
CAÙC TÍNH CHAÁT CUÛA BAØI TOAÙN QHTT
º Deã daøng kieåm tra X khoâng phaûi laø phöông aùn. Y, Z laø phöông aùn cuûa baøi toaùn.
º Y thoûa 2 raøng buoäc chaët (2 raøng buoäc veà daáu) neân Y chæ laø P.A.
f x ( )
2
3
min
ÑÒNH LYÙ 1. (TÍNH ÑAËC TRÖNG CUÛA P.A.C.B) Moät phöông aùn X* = (x1*, x2*,…, xn*) cuûa baøi toaùn QHTT daïng chính taéc laø phöông aùn cöïc bieân neáu vaø chæ neáu heä vectô coät Aj öùng vôùi thaønh phaàn xj* > 0 laø ñoäc laäp tuyeán tính. Ví duï 1.8. Cho baøi toaùn QHTT
x 1
x 2
x 3
4
x 3
0
x 1 x 1
x 2 x 2
1 0 0 det 1 1 3
1
5 0
6
x
0,
j
1,3
6 2 1
j
º Z thoûa 3 raøng buoäc chaët (raøng buoäc 2, raøng buoäc 3, raøng buoäc 4) vaø
CAÙC TÍNH CHAÁT CUÛA BAØI TOAÙN QHTT
CAÙC TÍNH CHAÁT CUÛA BAØI TOAÙN QHTT
Vaäy Z laø phöông aùn cöïc bieân cuûa baøi toaùn. Caùc vectô naøo sau ñaây X = (2, 2, 0), Y = (0, 0, 4), Z = (1, 1, 2), laø P.A.C.B cuûa baøi toaùn.
A 3
A 1
A 2
1 0
1 1
X, Y, Z thoûa caùc raøng buoäc neân chuùng laø P.A. Maët khaùc ta coù
det
2
1 1
1 1 1 1
Vôùi X = (2, 2, 0), neân X laø P.A.C.B.
6
toaùn QHTT HEÄ QUAÛ 2. Soáù thaønh phaàn döông trong moãi phöông aùn cöïc bieân cuûa baøi toaùn quy hoaïch tuyeán tính daïng chính taéc toái ña baèng m (m laø soá doøng cuûa ma taän A). ÑÒNH LYÙ 2. (SÖÏ TOÀN TAÏI CUÛA PHÖÔNG AÙN TOÁI ÖU) Neáu baøi toaùn quy hoaïch tuyeán tính coù phöông aùn vaø haøm muïc tieâu bò chaën döôùi (ñoái vôùi f(x) min) hoaëc haøm muïc tieâu bò chaën treân (ñoái vôùi f(x) max) treân taäp caùc phöông aùn thì baøi toaùn coù phöông aùn toái öu. ÑÒNH LYÙ 3. (SÖÏ TOÀN TAÏI CUÛA P.A.C.B. TOÁI ÖU) Neáu baøi toaùn QHTT daïng chính taéc coù P.A.T.Ö thì baøi toaùn coù P.A.C.B toái öu (P.A.C.B.T.Ö). Vôùi Y = (0, 0, 4), heä chæ goàm moät vectô A3 neân Y cuõng laø P.A.C.B. Vôùi Z=(1, 1, 2), ta thaáy heä {A1, A2, A3} phuï thuoäc tuyeán tính vì A1+A2–2A3=0 neân Z khoâng laø P.A.C.B. HEÄ QUAÛ 1. (tính höõu haïn cuûa P.A.C.B). Soáù phöông aùn cöïc bieân cuûa baøi daïng chính taéc laø höõu haïn.
ThS. Nguyễn Công Trí - Tối ưu hóa * Chương 1
CAÙC TÍNH CHAÁT CUÛA BAØI TOAÙN QHTT
CAÙC TÍNH CHAÁT CUÛA BAØI TOAÙN QHTT
Ví duï 1.9 .
xf )(
min
x
x 5
2
Vôùi baøi toaùn quy hoaïch tuyeán tính
x
2
x
1
x 1
5
x
5
3
2 x 3 2 2
x
x x
3 2
x
5
4
j
2 5,1
x
0
j
theå tìm P.A.T.Ö cuûa baøi
CAÙC TÍNH CHAÁT CUÛA BAØI TOAÙN QHTT
CAÙC PHÖÔNG PHAÙP GIAÛI BAØI TOAÙN QUY HOAÏCH TUYEÁN TÍNH
( ) 3
min
f x
4
2
2
Ta coù phöông aùn X = (1, 0, 3, 2, 0) laø phöông aùn cöïc bieân cuûa baøi toaùn vì caùc aån x1, x3, x4 laø caùc aån cô baûn cuûa baøi toaùn daïng chuaån. ÑÒNH LYÙ 4. (SÖÏ TOÀN TAÏI NHIEÀU P.A.C.B.T.Ö) Neáu baøi toaùn coù P.A.T.Ö laø Xopt vaø X(1), X(2) laø 2 phöông aùn khaùc nhau cuûa baøi toaùn thoaû Xopt = X(1) + (1–)X(2), 0 1 thì X(1), X(2) laø P.A.T.Ö. NHAÄN XEÙT 1. Ta coù toaùn QHTT trong soá caùc P.A.C.B cuûa baøi toaùn vaø coù theå toaùn daïng xaùc ñònh ngay P.A.C.B cuûa baøi chuaån baèng caùch cho caùc aån khoâng cô baûn baèng khoâng (xem Ví duï 1.9). 2. Trong baøi toaùn QHTT daïng chính taéc. Neáu haïng cuûa ma traän heä soá A laø m thì P.A.C.B ñöôïc goïi laø khoâng suy bieán neáu noù coù ñuùng m thaønh phaàn döông. Neáu P.A.C.B coù ít hôn m thaønh phaàn döông thì ñöôïc goïi laø P.A.C.B suy bieán (xem Ví duï 1.10).
x 4
x 1 x 1
(Xem)
4.1. PHÖÔNG PHAÙP HÌNH HOÏC
x 2 2 5
28 26
3
x 4 x 2 4
Ví duï 1.10 . Vôùi baøi toaùn quy hoaïch tuyeán tính x 3
Ths. Nguyeãn Coâng Trí
(Xem)
4.2. PHÖÔNG PHAÙP ÑÔN HÌNH
2
16
2
2 x 1 x 2 1
x 2 x 2 x 2
x 4
x 3 x 3
x
0
j
1, 4
j
4.3. PHÖÔNG PHAÙP ÑÔN HÌNH MÔÛ ROÄNG
(Xem)
(BAØI TOAÙN M)
Kieåm tra vectô X = (11, 3, 0, 0) coù phaûi laø P.A.C.B?
Copyright 2001
Kieåm tra tröïc tieáp, ta coù X laø P.A cuûa baøi toaùn.
7
Haïng cuûa ma traän heä soá cuûa heä raøng buoäc tuyeán tính baèng 3 vaø X coù 2 thaønh phaàn döông laø x1 =11, x2 = 3 neân X laø P.A.C.B suy bieán.
ThS. Nguyễn Công Trí - Tối ưu hóa * Chương 1
PHÖÔNG PHAÙP HÌNH HOÏC
PHÖÔNG PHAÙP HÌNH HOÏC
Xeùt baøi toaùn QHTT coù 2 bieán.
taêng
ax+by=c Ví duï 1.11. Moät coâng ty coù 2 phaân xöôûng: PX1 vaø
PX2 cuøng saûn xuaát 2 loaïi saûn phaåm A vaø B. Naêng
suaát vaø chi phí saûn xuaát cuûa moãi PX trong 1 giôø: =m (ñöôøng möùc) Phaân xöôûng PX1 PX2 ax+by a ax+by>c O
b giaûm N(a,b) (cid:0) Naêng suaát
Saûn phaåm A
Saûn phaåm B
Chi phí (trieäu ñoàng/ giôø) 250
100
0,6 250
200
1 PHÖÔNG PHAÙP HÌNH HOÏC PHÖÔNG PHAÙP HÌNH HOÏC 0,6x1+x2=m Ñôn ñaët haøng: ít nhaát 5.000 SpA, 3.000 SpB.
Haõy phaân phoái thôøi gian hoaït ñoäng cuûa 2 phaân
xöôûng sao cho thoaû yeâu caàu ñôn ñaët haøng vaø
chi phí saûn xuaát thaáp nhaát. 100x1+200x2=3000 Mieàn raøng buoäc
D 20 A1(0,20) 0,6 min
f x Goïi x1, x2 laàn löôït laø soá giôø hoaït ñoäng cuûa phaân
xöôûng thöù nhaát vaø phaân xöôûng thöù hai. x
1 15 10 250 250 5000 taêng 200 3000 A3
(10,10)
10
20 A2(30,0)
30 x
2
x
2
0 x
2 giaûm x
1
100
x
1
x
0
1 250x1+250x2=5000 Ta coù moâ hình baøi toaùn
x
2 8 Vaäy P.A.T.Ö: xopt(10,10) vaø f(xopt)=16 trieäu ñoàng. Duøng phöông phaùp hình hoïc ñeå giaûi baøi toaùn
treân nhö sau ThS. Nguyễn Công Trí - Tối ưu hóa * Chương 1 PHÖÔNG PHAÙP HÌNH HOÏC PHÖÔNG PHAÙP HÌNH HOÏC -2x1+x2= m x1-x2= -2 Ví duï 1.12.
Giaûi baøi toaùn quy hoaïch tuyeán tính
2 min x
1 2 A1(0,2)
2
2 2 2 -1 O A2(2,0)
x
2
x
2
x
2
0 x
2 -2
taêng Mieàn raøng buoäc
D -x1+2x2= -2 giaûm
-1 baèng phöông phaùp hình hoïc CÔ SÔÛ PHÖÔNG PHAÙP ÑÔN HÌNH 3 2 min Haøm muïc tieâu khoâng bò chaën. Baøi toaùn khoâng
coù phöông aùn toái öu. x
2 x
1 CÔ SÔÛ PHÖÔNG PHAÙP ÑÔN HÌNH
x
f x
( )
3
3
4 2 10 x
2 Ví duï 13: giaûi baøi toaùn f x
( )
3 2 min
4 5 x
1 x
1
x
1 2
2 8 x
2
10
x
3
2
4
3 x
2
x
2 x
3
x
3
x
3 x
1 x
2 3 5
4 x
1
x
1 x j 1,3 j
3
0
Ñöa baøi toaùn veà daïng chính taéc
2 8
2 x
1 x
2
x
2 x
3
x
3
x
3 w
1
w
2
w
3 f x
( )
3 2 min x
1 x
2 x 0 j 1,3, 0, i 1,3 j w
i
x
3
3
4 10 2 w
1 x
2
4 5 w
2 x
1
x
1
2
2 8 x
3
x
3
x
3 x
2
x
2 w
3 x
1 Ta coù P.A.C.B laø x = (0, 0, 0, 10, 5, 8)
Baøi toaùn töông ñöông 0, j 1,3, 0, i 1,3 x w
i j
3
9 coù P.A.C.B laø x = (0, 0, 0, 10, 5, 8) vaø f(x) = 0.
Nhaän xeùt:
coù theå ñoåi P.A baèng caùch taêng x1 baèng moät giaù
trò döông vaø giöû x2 = x3 = 0 thoûa ñieàu kieän wi ≥ 0. ThS. Nguyễn Công Trí - Tối ưu hóa * Chương 1 CÔ SÔÛ PHÖÔNG PHAÙP ÑÔN HÌNH CÔ SÔÛ PHÖÔNG PHAÙP ÑÔN HÌNH f x
( ) 3 min 5 x
1
10
5
0
0 2
3
x
1 x
1 w
2 x
2 w
1 x
3 5
3 8 0 w
1
w
2
w
3 x
1
x
1
x
1
(Choïn doøng 2) 5
3
8 x
1
w
2 x
2 x
1 x
3 w
2 x
2 w
3 x
3
x
3
2
3
1
3
1
3 1
3
4
3
2
3
w x
2
2
20
3
5
3
19
3
j 10
3
1
3
5
3
i x 0 1,3, 0, 1,3 j w
i
Ta coù Ta coù keát quaû
5 CÔ SÔÛ PHÖÔNG PHAÙP ÑÔN HÌNH CÔ SÔÛ PHÖÔNG PHAÙP ÑÔN HÌNH Choïn x1 = 5/3, ta ñöôïc P.A môùi laø
x1 = 5/3, x2 = x3 = w2 = 0, w1 = 20/3, w3 = 19/3.
Vaø f(x) = - 5.
Baøi toaùn töông ñöông: taïi raøng buoäc thöù hai tính
x1 theo caùc bieán coøn laïi, roài theá giaù trò x1 vöøa tính
ñöôïc vaøo caùc raøng buoäc vaø haøm muïc tieâu. Nhaän xeùt:
coù theå ñoåi P.A baèng caùch taêng x2 baèng moät giaù
trò döông vaø giöû x3 = w2 = 0 thoûa ñieàu kieän wi ≥ 0. f x
( ) min w
1 w
2 x
3 0 31
10 3
10 4
5 x
1 w
1 2 2 x
2 w
1 w
2 x
3 5
0 2 x
1 x
2 x
2
x
2
x
2 (Choïn doøng 1) 1 x
1 w
1 w
2 x
3 x
2 0 1
5
6
15 w
3 x
2 19
5
20
3
5
3
19
3 3 w
3 w
1 x
3 1
10
39
30
2
3 3
10
1
10
1
2
1,3, x 0 j 0, i 1,3 j w
i
Ta coù keát quaû
7 10 Ta coù
10
3
1
3
5
3
Choïn x2 = 2, ta ñöôïc P.A môùi laø
x1 = 1, x3 = w1 = w2 = 0, w3 = 3 vaø f(x) = - 7.
Baøi toaùn töông ñöông: taïi raøng buoäc thöù nhaát
tính x2 theo caùc bieán coøn laïi, roài theá giaù trò x2 vöøa
tính ñöôïc vaøo caùc raøng buoäc vaø haøm muïc tieâu. Baøi toaùn coù P.A.T.U laø xopt = (1, 2, 0)
vaø f(xopt) = - 7 ThS. Nguyễn Công Trí - Tối ưu hóa * Chương 1 CÔ SÔÛ PHÖÔNG PHAÙP ÑÔN HÌNH CÔ SÔÛ PHÖÔNG PHAÙP ÑÔN HÌNH
n m m m
n m ,
2
x
i b
i x
a
i m k m k
,
f x n c x
i
i c
a
i m k i
, c
m k k
1 i
1
1
1 k i
x
m k
m f x
( ) min hay
max 1
n m c x
j j j
1 Döïa treân cô sôû baøi toaùn coù daïng chuaån
f x x
m k m k m k
c
a
i m k i
, c
m k
f x 0 k
1
n m i
1 0
2 x
i x
a
i m k m k
, b
i Ñaët thì 0 0 ,
f x m k m kx
f x k
1 j 0 1,
3 n b
i
Neáu vì thì 0 0 m kx m k
f x Neáu vì thì m m c
j j 0 0
a c
ij
i
x
0
j
Daáu hieäu toái öu cuûa baøi toaùn
Phöông aùn cöïc bieân ñaàu tieân laø:
,
f x
( ,0) ,.0 x ( ; ) b b
,
1
2 b
m c b
i
i i
1 Kyù hieäu laïi: ( ) f x 1
i
Min j
0; j n m
n m x D x , (
,
, f x
( ) x x
,
1
2 x
)n c x
j j c x
i
i x
c
m k m k (1) Khi thì Choïn moät P.A baát kyø cuûa baøi toaùn j
0; ( ) f x Max j
1 i
1 k
1 j CÔ SÔÛ PHÖÔNG PHAÙP ÑÔN HÌNH CÔ SÔÛ PHÖÔNG PHAÙP ÑÔN HÌNH (2) Khi thì HHeeää
ssooáá AAåånn
CC..BB PPAA
CCBB ……......…… CCjj
……......…… xxjj HHeeää
ssooáá AAåånn
CC..BB PPAA
CCBB ……......…… CCjj
……......…… xxjj CC11 CC22 ……...... CCii …………...... CCmm CCmm++11
xx11 xx22 ...... xxii ……......…… xxmm xxmm++11
11 00 CC11 CC22 ……...... CCii …………...... CCmm CCmm++11
xx11 xx22 ...... xxii ……......…… xxmm xxmm++11
11 00 00 11 00 11 CC11 xx11 bb11
CC22 xx22 bb22
......
......
...... ...... CCnn
...... xxnn
...... ...... ...... 00 aa11,,mm++11 ……......…… aa11jj ...... aa11nn
……...... ...... ...... 00 aa22,,mm++11 …………...... aa22jj ...... aa22nn
...... ...... ...... ...... ...... ...... ...... ...... ...... ...... ...... CC11 xx11 bb11
CC22 xx22 bb22
......
......
...... ...... CCnn
...... xxnn
...... ...... ...... 00 aa11,,mm++11 ……......…… aa11jj ...... aa11nn
……...... ...... ...... 00 aa22,,mm++11 …………...... aa22jj ...... aa22nn
...... ...... ...... ...... ...... ...... ...... ...... ...... ...... ...... 00 00 ……...... ...... ……...... 00 aaii,,mm++11 00 00 ……...... ...... ……...... 00 aaii,,mm++11 CCii xxii bbii
......
......
...... ...... ...... ……...... ...... ……...... ...... ...... ...... aaiijj
......
...... ......…… aaiinn
...... ...... CCii xxii bbii
......
......
...... ...... ...... ……...... ...... ……...... ...... ...... ...... aaiijj
......
...... ......…… aaiinn
...... ...... CCmm xxmm bbmm 00 00
ff((xx)) ff((xx00)) 00 00 ……...... ...... ……...... 11 aamm,,mm++11 ......…… aammjj ……...... aammnn
……...... ...... ……...... 00 mm++11 ……...... jj ......…… nn CCmm xxmm bbmm 00 00
ff((xx)) ff((xx00)) 00 00 ……...... ...... ……...... 11 aamm,,mm++11 ......…… aammjj ……...... aammnn
……...... ...... ……...... 00 mm++11 ……...... jj ......…… nn 11 Daáu hieäu baøi toaùn coù P.A.C.B. khaùc toát hôn
Ñònh lyù. Vôùi moät P.A.C.B, neáu j>0, i: aij > 0 thì baøi
toaùn coù P.A.C.B khaùc toát hôn P.A.C.B ñang xeùt. Daáu hieäu baøi toaùn khoâng coù P.A.T.Ö
Ñònh lyù. Vôùi moät phöông aùn cöïc bieân, neáu toàn taïi
j > 0 maø aij ≤ 0, i thì baøi toaùn khoâng coù P.A.T.Ö.
(xem Ví duï 1.13) ThS. Nguyễn Công Trí - Tối ưu hóa * Chương 1 BAÛNG ÑÔN HÌNH THUAÄT GIAÛI ÑÔN HÌNH Ñuùng HHeeää
ssooáá AAåånn
CC..BB PPAA
CCBB ……......…… CCjj
……......…… xxjj j ≤ 0,j? LAÄP BAÛNG ÑÔN HÌNH Sai Ñuùng P.A.T.Ö ...... ...... aij ≤ 0,i?
Sai ……...... ...... ……...... 00 aaii,,mm++11 x XAÙC ÑÒNH PHÖÔNG AÙN MÔÙI
Aån vaøo:
j j Max
0j BAØI TOAÙN
KHOÂNG COÙ P.A.T.Ö CC11 CC22 ……...... CCii …………...... CCmm CCmm++11
xx11 xx22 ...... xxii ……......…… xxmm xxmm++11
11 00
00 11
...... ...... ...... ...... ......
00 00
...... ...... ……...... ...... ……...... ...... ...... CCnn
...... xxnn
...... ...... ...... 00 aa11,,mm++11 ……......…… aa11jj ...... aa11nn
……...... ...... ...... 00 aa22,,mm++11 …………...... aa22jj ...... aa22nn
...... ......
......…… aaiinn
...... ...... ......
......
...... aaiijj
......
...... ...... Aån ra: x
i
Min
0ij
a b
i
a
ij CC11 xx11 bb11
CC22 xx22 bb22
......
......
......
CCii xxii bbii
......
......
......
CCmm xxmm bbmm 00 00
ff((xx)) ff((xx00)) 00 00 ……...... ...... ……...... 11 aamm,,mm++11 ......…… aammjj ……...... aammnn
……...... ...... ……...... 00 mm++11 ……...... jj ......…… nn KEÁT THUÙC
THUAÄT GIAÛI THUAÄT GIAÛI ÑÔN HÌNH THUAÄT GIAÛI ÑÔN HÌNH BIEÁN ÑOÅI BAÛNG ÑÔN HÌNH SOÁ BÖÔÙC LAËP
LAØ HÖÕU HAÏN Böôùc 4: Tìm P.A.C.B môùi cuûa baøi toaùn Thuaät giaûi goàm 4 böôùc: Choïn aån vaøo: Böôùc 1: Laäp baûng ñôn hình Choïn Maxj (j > 0), aån xj seõ ñöôïc choïn ñöa vaøo
heä aån cô baûn öùng vôùi j ñaõ ñöôïc choïn. Baøi toaùn phaûi ôû daïng chuaån, ñöa caùc soá lieäu vaøo
baûng ñôn hình. Choïn aån ra: Böôùc 2: Kieåm tra tính toái öu cuûa baøi toaùn
Tính j = ∑aijci – cj Neáu j ≤ 0: baøi toaùn coù P.A.T.U.
Neáu j > 0: chuyeån sang böôùc 3. Choïn = Min{bi/aij} (aij > 0), aån xi seõ ñöôïc choïn
ñöa ra khoûi heä aån cô baûn öùng vôùi nhoû nhaát.
Phaàn töû aij (öùng vôùi aån vaøo xi vaø aån ra xj) ñöôïc
goïi laø phaàn töû truïc. Böôùc 3: Kieåm tra tính giaûi ñöôïc cuûa baøi toaùn 12 Duøng phöông phaùp bieán ñoåi sô caáp doøng
treân ma traän heä soá ñeå bieán ñoåi aån môùi ñöa vaøo
trôû thaønh aån cô baûn. Sau ñoù quay veà böôùc 2. Neáu aij ≤ 0, i: baøi toaùn khoâng coù P.A.T.U.
Neáu aij > 0: chuyeån sang böôùc 4. ThS. Nguyễn Công Trí - Tối ưu hóa * Chương 1 THUAÄT GIAÛI ÑÔN HÌNH THUAÄT GIAÛI ÑÔN HÌNH NHAÄN XEÙT. Daáu hieäu baøi toaùn coù nhieàu P.A.T.Ö. f x
( ) 6 3 7 min 6 x
1 x
2 x
3 x
5 x
6 Ví duï 1.14.
Giaûi baøi toaùn quy hoaïch tuyeán tính opt (xem Ví duï 1.15). x
4
3 x
2 Vôùi P.A.C.B.T.Ö Xopt tìm ñöôïc, neáu j = 0, maø xj
khoâng laø P.A.C.B thì baøi toaùn coù P.A.C.B.T.Ö khaùc
X/ x
7
x
7 x
3 Taäp phöông aùn toái öu: opt
4
2
2
3
9
2
2
4 x
4
x
4
x
4
x
7
x
6
x
6
x
6 x
5 x
1
x
1
x
1 Tröôøng hôïp coù hai P.A.C.B.T.Ö laø Xopt vaø X/ x 0 j 1,7 j Topt = {Xopt + (1 – )X/ opt, [0, 1]}
opt, X(2) opt, X(3) opt opt + X(2) opt + X(3) opt, }, vôùi , , 0 vaø Tröôøng hôïp coù 3 P.A.C.B.T.Ö X(1) THUAÄT GIAÛI ÑÔN HÌNH Topt = { X(1)
+ + = 1. min HEÄ P.A AÅN x
4
2 x
5 152 x
2
4
x
4 Ví duï 1.15.
Giaûi baøi toaùn quy hoaïch tuyeán tính
3
x
6
( ) 5
x
f x
1
4
x
2
2
x
2
x
5
60
36 x
2
1
x
4
1
x
3
1 x
5
3
3
x
3
3
x
3
x
3
x
6 0 j 1,6 x
j 7
1
1 6
7
7x
6x
1
1
1
2
3
0
6
7
1
1
3
0
3
0
0 13 THUAÄT GIAÛI ÑÔN HÌNH
3 1
1
5x
4x
2x
0
1
1
0
0
4
0
2
1
0
6
0
0
1
1
0
2
2
3
1
1
1 0
7 3
9
2
14
3
3
11
7 1
3x
0
1
0
0
0
1
0
0 6
1x
1
2
4
5
1
0
1
2 SOÁ
1
1
1 13 C.B
2x
3x
5x
f x
6x
3x
5x
f x Baøi toaùn coù phöông aùn toái öu khaùc hay khoâng?
Neáu coù tìm taäp phöông aùn toái öu vaø chæ ra 3
phöông aùn toái öu. BT khoâng coù P.A.T.Ö vì 4= 1 > 0 maø ai4 < 0, i. ThS. Nguyễn Công Trí - Tối ưu hóa * Chương 1 THUAÄT GIAÛI ÑÔN HÌNH 3
6x
2
2 5
3x
1
5 1
5x
2
1 3 6 1 1 HEÄ P.A AÅN HEÄ P.A AÅN THUAÄT GIAÛI ÑÔN HÌNH
2
4x
1
0
0
0 3
0 4
2x
0
1
0
0 2
0
3 3
2 5
1x
C.B
4x
104 0
2x
0
6
1x
1
12
f x 292 0 3
6x
0
0
1
0
2 5
3x
3
3
1
7
7 3 3 5 3 3 1 2
1
5 2
4x
1
0
0
0
1
0
0
0 3
4 4
2x
4
2
0
6
4
2
0
6 3
3 1
5x
0
1
0
0
0
1
4
1
0
0 5
1x
C.B
4x
152
2
5x
60
4
6x
3
36
f x 472 12
4x
128 0
5x
0
12
1x
1
12
f x 328
0 SOÁ
2
4
5 SOÁ
2
1
3 THUAÄT GIAÛI ÑÔN HÌNH THUAÄT GIAÛI ÑÔN HÌNH Baøi toaùn coù P.A.T.Ö xopt=(12, 6, 0, 104, 0, 0) vaø
f(xopt)= 292.
Baøi toaùn coøn P.A.C.B.T.Ö khaùc vì 6 = 0, nhöng x6
khoâng phaûi
laø A.C.B. Ta coù P.A.C.B.T.Ö thöù hai
baèng caùch choïn aån x6 laø aån ñöa vaøo. HEÄ P.A AÅN Vôùi taäp phöông aùn toái öu, ta coù :
xopt + (1 - )x/
opt = 5
3x
3
3 1
5x
2
1 (12, 6, 0, 104, 0, 0) + (1-)(0, 30, 0, 32, 0, 36)
= (12 , 30–24, 0, 32 + 72, 0, 36 - 36) 2
4x
1
0
0
0 3
6x
0
0
1
0 4
2x
0
1
0
0 2
0
3 2
1
2 5
1x
C.B
4x
32
6
2x
30
2
6x
3
36
f x 292 0 SOÁ
2
4
3 3 phöông aùn toái öu laø
Vôùi = 0, ta coù P.A.T.Ö: opt = (0, 30, 0, 32, 0, 36) vaø f(x/ opt) = 292. x/ opt = (0, 30, 0, 32, 0, 36) vaø f(x/ opt) = 292. opt) = 292. Vôùi = 1, ta coù P.A.T.Ö: Baøi toaùn coù phöông aùn cöïc bieân toái öu khaùc laø
x/ xopt = (12, 6, 0, 104, 0, 0) vaø f(x/ Taäp phöông aùn toái öu Vôùi = ½, ta coù P.A.T.Ö: opt, 0, 1} 14 Zopt = (6, 18, 0, 68, 0, 18) vaø f(zopt) = 292. Topt={xopt + (1 - )x/ ThS. Nguyễn Công Trí - Tối ưu hóa * Chương 1 THUAÄT GIAÛI ÑÔN HÌNH THUAÄT GIAÛI ÑÔN HÌNH f x
( ) Max j
c x
j j
1 f x
( )
2 Ví duï 1.16. NHAÄN XEÙT. Neáu baøi toaùn coù haøm muïc tieâu
n x
1 x
3 Coù hai caùch giaûi: x
1 Giaûi tröïc tieáp baøi toaùn (xem Ví duï 1.16), vôùi: j
0, j
x
4
2
7
2
2 x
2
x
2 Tieâu chuaån toái öu laø Giaûi baøi toaùn quy hoaïch tuyeán tính
x
max
2
2 5 x
3
x
3
3
x
3
x
4
3
x
4
x
4 • AÅn vaøo laø x 0 j 1,4 j
jMin
0
j
b
i
Min
a
a
0ij
ij
Chuyeån haøm muïc tieâu cuûa baøi toaùn veà min
g x
( ) f x
( ) Min • AÅn ra laø THUAÄT GIAÛI ÑÔN HÌNH THUAÄT GIAÛI ÑÔN HÌNH Baøi toaùn coù phöông aùn toái öu khaùc hay khoâng?
Neáu coù, haõy chæ ra phöông aùn toái öu khaùc. f x
( ) max HEÄ P.A AÅN x
4
2 x
1 2
1x
1
0
0
0
1 1
2x
1
1
0
1
1 1
4x
1
3
2
1
1
x
2
1
x
2
x
2 x
5 2 2 2
1 7 5
2
5 2
x
3
2
x
3
7
x
3
x
3
3 x
4
3
x
4
x
2
4 x
6 2 2 3 3 1 1
0
0 2 2 x 0 j 1,6 j 2
3 5 3 0
6x
0
0
1
0
0
0
1
0 2 1
3x
2
7
3
5
1
0
0
0 0
5x
0
1
0
0
0
1
0
0 2
2
5
4
1
9
8
1 2 2 Ñöa baøi toaùn veà daïng chính taéc baèng caùch
theâm aån phuï x5 ≥ 0 vaøo raøng buoäc thöù hai vaø aån
phuï x6 ≥ 0 vaøo raøng buoäc thöù ba.
Ta coù baøi toaùn ôû daïng chuaån
x
2 SOÁ
2
0
0 15 C.B
1x
5x
6x
f x
3x
5x
6x
f x Laäp baûng ñôn hình ThS. Nguyễn Công Trí - Tối ưu hóa * Chương 1 THUAÄT GIAÛI ÑÔN HÌNH CÔ SÔÛ THUAÄT GIAÛI ÑÔN HÌNH MÔÛ ROÄNG f x
( ) Min c x
j j HEÄ P.A AÅN j
1 n 1, m a x
ij j b i
,
i Xuaát phaùt töø baøi toaùn daïng chính taéc
n
j
1
I x 0 j 1, 0 j n b
i 1
4x
0
0
1
0 0
6x
1
1
2
3 1
3x
1
0
0
0 1
2x
2
4
3
6 SOÁ
1
0
1
C.B
3x
9
5x
17
4x
16
f x 25 0
2
1x
5x
0
2
5
1
3
0
0
7
Vì caùc j 0, j neân baøi toaùn coù P.A.T.Ö laø
Xopt = (0, 0, 9, 16) vaø f(Xopt) = 25.
Baøi toaùn treân khoâng coøn phöông aùn toái öu naøo
khaùc vì khoâng coù j = 0 naøo vôùi xj laø aån khoâng
cô baûn. BAÛNG ÑÔN HÌNH MÔÛ ROÄNG CÔ SÔÛ THUAÄT GIAÛI ÑÔN HÌNH MÔÛ ROÄNG n m HHeeää PPAA AAÅÅnn CC11 CC22 f x
( ) Min j j
g
c x M x
i j
1 i
1 SSooáá CCBB CC..BB xx11 xx22 n MM xxnn++11 bb11 aa1111 aa1122 1, m II a x
ij j g
x
i b i
,
i …… CCjj
…… xxjj
…… aa11jj
…… aa22jj …… CCmm CCmm++11
…… xxmm xxmm++11
…… aa11mm aa11,,mm++11
…… aa22mm aa22,,mm++11
1 j 0, j n
1, ; 0, i 1, m M
, 0 vo âcuøng lôùn. j g
x
i
x
…… aaiimm aaii,,mm++11 …… aaiijj Khoâng laøm maát tính toång quaùt cuûa baøi toaùn, ta
giaû söû caùc bi 0 vaø ma traän heä soá cuûa heä raøng
buoäc khoâng chöùa vectô (coät) ñôn vò naøo.
Coäng vaøo moãi raøng buoäc vôùi moät aån giaû töông
(g) ≥ 0 thì ta ñöôïc baøi toaùn coù daïng:
öùng xi …… CCnn
…… xxnn
…… aa11,,nn
…… aa22,,nn
MM xx nn++22 bb22 aa2211 aa2222
…… …… …… …… …… …… …… …… …… …… …… ……
…… aaii,,nn
MM xx nn++ii bbii aaii11 aaii22
…… …… …… …… …… …… …… …… …… …… …… ……
…… aamm,,nn
…… nn MM xxnn++mm bbmm aamm11 aamm22
ff((xx)) ff((xx00)) 11 22 …… aammmm aamm,,mm++11
…… mm mm++11 …… aammjj
…… jj x Baøi toaùn (I) ñöôïc goïi laø baøi toaùn goác, baøi toaùn g
x x
,
j
i
(g) goàm m aån giaû. 16 (II) goïi laø baøi toaùn môû roäng hay baøi toaùn M.
Trong ñoù caùc xn+i (i = 1, 2, ..., m) laø caùc aån giaû. Moät phöông aùn cuûa baøi toaùn M coù daïng
trong ñoù xj goàm n aån thaät vaø xi ThS. Nguyễn Công Trí - Tối ưu hóa * Chương 1 CÔ SÔÛ THUAÄT GIAÛI ÑÔN HÌNH MÔÛ ROÄNG CÔ SÔÛ THUAÄT GIAÛI ÑÔN HÌNH MÔÛ ROÄNG NHAÄN XEÙT. Khi thuaät giaûi cuûa baøi toaùn M keát thuùc thì coù hai
tröôøng hôïp sau ñaây coù theå xaûy ra: toaùn M (Baøi b) Neáu trong heä aån cô baûn cuûa baøi toaùn M coù
chöùa aån giaû nhöng giaù trò cuûa chuùng ñeàu baèng
khoâng thì P.A.T.Ö cuûa baøi toaùn goác laø P.A.T.Ö.
cuûa baøi toaùn M loaïi boû caùc aån giaû baèng khoâng
(xem Ví duï 1.18). [1] Neáu baøi
toaùn II) khoâng coù
phöông aùn toái öu thì baøi toaùn goác (Baøi toaùn I)
cuõng khoâng coù phöông aùn toái öu. c) Neáu trong heä aån cô baûn cuûa baøi toaùn M coù
moät aån giaû maø giaù trò cuûa chuùng khaùc khoâng thì
baøi toaùn goác khoâng coù P.A.T.Ö. [2] Neáu baøi toaùn M (Baøi toaùn II) coù phöông aùn toái
öu thì coù 3 tröôøng hôïp xaûy ra sau ñaây: THUAÄT GIAÛI ÑÔN HÌNH MÔÛ ROÄNG THUAÄT GIAÛI ÑÔN HÌNH MÔÛ ROÄNG ÑÖA BAØI TOAÙN VEÀ DAÏNG CHUAÅN Chuù yù. Neáu haøm muïc tieâu laø f(x) Max thì heä soá
caùc aån giaû trong haøm muïc tieâu cuûa baøi toaùn M
laø (– M), vôùi M > 0 voâ cuøng lôùn (xem Ví duï 1.19). a) Trong heä A.C.B khoâng chöùa aån giaû naøo thì
P.A.T.Ö cuûa baøi toaùn M cuõng chính laø P.A.T.Ö
cuûa baøi toaùn goác (xem Ví duï 1.17). f x
( ) 2 min 8 6
x
3 LAÄP BAÛNG ÑÔN HÌNH x
2
4 3 18 Ñuùng Ñuùng Coù 0?g
ix j ≤ 0? ?g
ix 4
3
4 16 x
1
4
x
1
x
1 x
2
x
2 x
3
x
3 COÙ
P.A.T.Ö Sai Sai Khoâng j x 0 j Ñuùng COÙ P.A.T.Ö aij ≤ 0?
Sai KHOÂNG
COÙ
P.A.T.Ö KHOÂNG
COÙ
P.A.T.Ö 1,3
Nhaân (– 1) vaøo raøng buoäc thöù nhaát, baøi toaùn coù
daïng chính taéc nhö sau
f x
( ) min 2 6 8
x
3 x
2 Aån vaøo: KEÁT THUÙC THUAÄT GIAÛI Aån ra: Xaùc ñònh phöông aùn môùi
Max
0j
Min
0ij
a j
b
i
a
ij
4
3
3
4
18
16 x
1
x
4
1
x
4
1 x
2
x
2 x
3
x
3 x 0 j 1,3 BIEÁN ÑOÅI BAÛNG ÑÔN HÌNH j Ví duï 1.17. (tröôøng hôïp a). Giaûi baøi toaùn QHTT 17 SOÁ BÖÔÙC LAËP
LAØ HÖÕU HAÏN ThS. Nguyễn Công Trí - Tối ưu hóa * Chương 1 THUAÄT GIAÛI ÑÔN HÌNH MÔÛ ROÄNG P.A 18
16
34M 8 7 Min f x
( ) x
6
2 x
)
5 M
8 x
4 x
8
1
x
4
2
x
3
2 4
x
1
x
4
1 x M x
2
(
3
4
x
3
3
x
4
3
18
x
16
5 6
8 x 0 j 1,5 M 0 vo â cuøng lôùn. j THUAÄT GIAÛI ÑÔN HÌNH MÔÛ ROÄNG
2
3x
3
4
2M
7
1
7
10M
7
25
4
94 8
1x
4
4
8M
0
1
0
0
1
0 6
2x
4
3
6M
1
3
4
12M
1
0
0 2
4
32M
2
5
2
8 HEÄ
SOÁ
M
M Ñöa baøi toaùn veà daïng chuaån:
Theâm hai aån giaû x4 ≥ 0 vaø x5 ≥ 0 vaøo laàn löôït vaøo
raøng buoäc thöù nhaát vaø thöù hai cuûa baøi toaùn
Baøi toaùn coù daïng chuaån nhö sau: THUAÄT GIAÛI ÑÔN HÌNH MÔÛ ROÄNG THUAÄT GIAÛI ÑÔN HÌNH MÔÛ ROÄNG
( ) 6 min f x
x
3 AÅN
C.B
4x
5x
f x
4x
1x
f x 2
2x
1x
f x Ta coù baûng ñôn hình môû roäng Baøi toaùn coù P.A.T.Ö Xopt=(5/2, 2, 0), f(Xopt)= –8. 10 2
3
2 16 4 ) min x
3
2
4 8 2 x
2
x
2
x
2 x
3
x
3
x
3 x
1
x
1
x
1
x
1 x 0 j 1,3 j
0
1 x
5 Ví duï 1.18. (tröôøng hôïp b). Giaûi baøi toaùn QHTT
x
3
2
5
( ) 6 min f x
x
3 x
2
5 10 2 x
4 1
6
8
Theâm aån phuï x4 0 vaøo raøng buoäc thöù nhaát
3 x
3
2
x
3
x
3 x
2
1
x
4
1
x
2
1 x
6 j 0 ,
1 M 0 j
3
4
2
16
8 4
2 x
2
x
2
x
2 x
3
x
3
x
3 x
1
x
1
x
1
x
1 x
6
Ta coù baûng ñôn hình môû roäng x 0 j 1, 4 j
18 Theâm hai aån giaû x5 ≥ 0, x6 ≥ 0 laàn löôït vaøo raøng
buoäc thöù hai vaø raøng buoäc thöù ba.
Ta coù baøi toaùn daïng chuaån nhö sau
x
x M x
(
( ) 6
x
f x
5
3
1
6
x
5
x
4
2
3
x
2
4
x
2 ThS. Nguyễn Công Trí - Tối ưu hóa * Chương 1 THUAÄT GIAÛI ÑÔN HÌNH MÔÛ ROÄNG THUAÄT GIAÛI ÑÔN HÌNH MÔÛ ROÄNG HEÄ AÅN HEÄ AÅN P.A P.A 2
0
8
8 3
2x
1
11
4
1M 11 0
4x
1
0
0
0 1
3x
0
0
1
0 6
1x
0
0
2
4 SOÁ
0
M
M SOÁ
0
M
1 0, 0, 8, 2, 0, 0 x 1
3x
1
2
1
1M
3
0
0
1 0
M
6 3
2x
5
3
4
3M
1
11
2
9M 11 10
16
8
24M 6
2
0
4
24 0
4x
1
0
0
0
1
0
0
0 6
1x
2
4
2
6M
0
0
1
0 2
2 C.B
4x
5x
3x
f x THUAÄT GIAÛI ÑÔN HÌNH MÔÛ ROÄNG THUAÄT GIAÛI ÑÔN HÌNH MÔÛ ROÄNG C.B
4x
5x
6x
f x
4x
5x
1x
f x P.A.T.Ö cuûa BTM laø
vôùi aån giaû x5 = 0
P.A.T.Ö cuûa BT goác laø xopt = (0, 0, 8)
vaø f(xopt) = 8. f x
( )
2 max x
2 Ví duï 1.19. (tröôøng hôïp c). Giaûi baøi toaùn QHTT Theâm 2 aån giaû vaøo x6, x7 0 laàn löôït vaøo raøng
buoäc (1) & (3).
2
2
12
10 4
2 f x
( )
2 max x
2
x
7 2 1 2 10
x
3
x
2
x
2
x
2 x
3
x
3
x
3 x
1
x
1
x
1
x
1 j 0 x x
6 j
4
2 x
1
2
12
10 x
1
x
1 x
2
x
2 x
3
x
3 x
5 f x
( )
2 max x 2
2 10 x
4 x
1 x
2 x
3 x
7
2 2
12
10
x
5 1 2
2 10 j 0 1,7
x M x
3
6
x
2
4
1
2
M 0 1,3
Theâm 2 aån phuï x4, x5 ≥ 0 vaøo raøng buoäc (1) & (2)
x
3
x
2
x
2
x
2 x
1
x
1
x
1
x
1 x
3
x
3
x
3 j x
Ta coù baûng ñôn hình môû roäng 0 j 1,5 x j 4
2
19 Ta coù baøi toaùn daïng chuaån nhö sau ThS. Nguyễn Công Trí - Tối ưu hóa * Chương 1 THUAÄT GIAÛI ÑÔN HÌNH MÔÛ ROÄNG BAØI TAÄP CHÖÔNG 1 [2] [4] [3] [5b] 1
3x
2
1
1 P.A 2 [7a] 0
4x
1
0
0
M
1 1
2x
1
2
2
1M 3
1 2 2
1 3 2 2 [8b]
9
1 1
0
M 12
10
10
22M
6
16
13 1 1 4
4 M
1
2 4
4 M
9 HEÄ
SOÁ
M
0
M 2
1x
4
2
1
2M 3
3
2
4
0
0 2
1M
1
0
0
0 0
5x
0
1
0
0
0
1
0
0 LAÄP MOÂ HÌNH BAØI TOAÙN
[1]
BAØI TOAÙN QHTT DAÏNG CHÍNH TAÉC
[5a]
XAÙC ÑÒNH P.A – P.A.C.B VAØ P.A.T.Ö.
[7c]
[7b]
[6]
GIAÛI BAØI TOAÙN QHTT BAÈNG PP HÌNH HOÏC
[8a]
[8c]
GIAÛI BAØI TOAÙN QHTT BAÈNG PP ÑÔN HÌNH
[11]
[9] [10] [12] [13] 2
P.A.T.Ö Xopt = (0, 0, 6, 0, 16, 0, 13), vôùi x7 = 13 0
neân baøi toaùn goác khoâng coù P.A.T.Ö. [14] [15] [16] [17] BAØI TAÄP CHÖÔNG 1 AÅN
C.B
6x
5x
7x
f x
3x
5x
7x
f x 6 13M BAØI TAÄP CHÖÔNG 1
1. Moät xí nghieäp cheá bieán ñoà goã hieän coù 3.000
ñôn vò goã nguyeân lieäu nhoùm I, 5.000 ñôn vò goã
nguyeân lieäu nhoùm II vaø 2.000 ñôn vò goã nguyeân
lieäu nhoùm III. Theo keá hoaïch xí nghieäp phaûi saûn
xuaát boán loaïi haøng hoaù vôùi ñònh möùc nguyeân
lieäu vaø lôïi nhuaän ñöôïc theå hieän trong baûng sau 1.Goïi xj (j=1, 2, 3, 4) laàn löôït laø soá löôïng boä tuû,
boä cöûa, boä sa–loâng vaø boä giöôøng nguû do xí
nghieäp saûn xuaát. SSaaûûnn pphhaaååmm ÑÑòònnhh mmööùùcc BBooää ttuuûû BBooää ccööûûaa BBooää ssaa--llooâânngg BBooää ggiiööôôøønngg nngguuûû NNgguuyyeeâânn lliieeääuu GGooãã nnhhooùùmm II 3300 4400 00 1100 GGooãã nnhhooùùmm IIII 1100 2200 5500 6600 GGooãã nnhhooùùmm IIIIII 1100 5500 8800 2200 Moâ hình cuûa baøi toaùn
f(x) = 0,5x1 + 0,8x2 + 0,4x3 + 0,6x4 Max Vôùi caùc raøng buoäc veà nguyeân lieäu 00,,55 00,,88 LLôôïïii nnhhuuaaäänn ((ttrriieeääuu ññooàànngg)) 00,,44 00,,66 +10x4 ≤ 3000,
30x1 + 40x2 +
10x1 + 20x2 + 50x3 + 60x4 ≤ 5000,
10x1 + 50x2 + 80x3 + 20x4 ≤ 2000, Raøng buoäc caùc aån soá Haõy laäp moâ hình baøi toaùn sao cho xí nghieäp ñaït
lôïi nhuaän nhieàu nhaát? 20 xj ≥ 0 , j = 1, 2, 3, 4 ThS. Nguyễn Công Trí - Tối ưu hóa * Chương 1 BAØI TAÄP CHÖÔNG 1 BAØI TAÄP CHÖÔNG 1
2. Moät coâng ty coù keá hoaïch quaûng caùo moät loaïi
saûn phaåm do coâng ty saûn xuaát trong thôøi gian
laø 100 trieäu ñoàng.
moät thaùng vôùi toång chi phí
Caùc phöông tieän ñöôïc choïn ñeå quaûng caùo saûn
phaåm vôùi soá lieäu ñöôïc döï kieán nhö sau:
Chi phí moãi laàn
quaûng caùo (trieäu Ñ) Soá laàn quaûng caùo
toái ña trong thaùng Döï ñoaùn soá ngöôøi
xem quaûng caùo Phöông tieän
quaûng caùo Truyeàn hình (1 phuùt) Baùo (1/2 trang) 1,5
1
0,5 60
26
90 15.000
30.000
9.000 Phaùt thanh (1 phuùt)
Coâng ty yeâu caàu phaûi coù ít nhaát 30 laàn quaûng
caùo treân truyeàn hình trong thaùng. Haõy laäp moâ
hình baøi toaùn sao cho phöông aùn quaûng caùo
saûn phaåm cuûa coâng ty laø toái öu. min 2 3 4 BAØI TAÄP CHÖÔNG 1
5. a) Ñöa baøi toaùn quy hoaïch tuyeán tính sau ñaây
veà daïng chính taéc
f x
( )
x
3 x
2 6 4 2 8 3 3 2 4 x
3
x
3
x
3 x
1
x
1
x
1
x
1
0, x
2
x
2
x
2
0 BAØI TAÄP CHÖÔNG 1
4. Moät xí nghieäp vaän taûi caàn chuyeån moät loaïi
haøng hoùa töø ba kho haøng A1, A2 vaø A3 ñeán boán
cöûa haøng B1, B2, B3 vaø B4. Chi phí vaän chuyeån
moät ñôn vò haøng hoùa töø kho Ai (i = 1, 2, 3) ñeán
cöûa haøng Bj (j = 1, 2, 3, 4) ñöôïc cho ôû baûng sau
LLööôôïïnngg hhaaøønngg CCööûûaa hhaaøønngg x
2 3 – x// CChhii pphhíí vvaaäänn cchhuuyyeeåånn hhiieeäänn ccooùù ((ttaaáánn)) BB11 BB22 BB33 BB44 KKhhoo min 2 2 33 44 00 11 4400
x
3 11 22 55 66 3300 11 55 88 22 3300 AA11
AA22
AA33 x
4 NNhhuu ccaaààuu ccuuûûaa ccööûûaa hhaaøønngg ((ttaaáánn)) 2200 2255 3300 1155
4
2
3
6
8
3
Theâm 2 aån phuï x4, x5 0
3
vaøo raøng buoäc thöù hai,
x
thöù ba vaø x3 = x/
3,
1
3 0, x//
vôùi x/
3 0, ta coù baøi toaùn daïng chính taéc
x
x
f x
( )
3
4
1
2
x
1
x
1
x
1
0,
x
3
x
3
x
3
x
3
0,
x
3
x
3
x
3
0, x
2
x
2
x
2
0 x
5
0 0, 4
3
2
x
3 4
3
2
x
3 x
2 x
4 x
5 x
1
3. Moät xí nghieäp coù theå söû duïng toái ña 510 giôø
maùy caùn, 360 giôø maùy tieän vaø 150 giôø maùy maøi
ñeå cheá taïo 3 saûn phaåm A, B vaø C. Ñeå cheá taïo
moät saûn phaåm A caàn 9 giôø maùy caùn, 5 giôø maùy
tieän vaø 3 giôø maùy maøi; moät saûn phaåm B caàn 3
giôø maùy caùn, 4 giôø maùy tieän; moät saûn phaåm C
caàn 5 giôø maùy caùn, 3 giôø maùy tieän vaø 2 giôø maùy
maøi. Moãi saûn phaåm A trò giaù 48 ngaøn ñoàng, moãi
saûn phaåm B trò giaù 16 ngaøn ñoàng vaø moãi saûn
phaåm C trò giaù 27 ngaøn ñoàng.
Haõy laäp moâ hình baøi toaùn xí nghieäp caàn cheá taïo
moãi loaïi bao nhieâu saûn phaåm ñeå coù toång giaù trò
saûn phaåm lôùn nhaát. 21 Haõy laäp moâ hình baøi toaùn vaän taûi haøng hoùa sao
cho toång chi phí vaän taûi beù nhaát? ThS. Nguyễn Công Trí - Tối ưu hóa * Chương 1 BAØI TAÄP CHÖÔNG 1 max 2 3 BAØI TAÄP CHÖÔNG 1
5. b) Ñöa baøi toaùn quy hoaïch tuyeán tính sau ñaây
veà daïng chính taéc
f x
( )
x
3 7 max f(x) 30 x
4 3
x
1
2x
1 60 2
2
15
10
25 x
3
x
3
x
3 32 2 x
3
x
3
x
2 3
3
x
2 3 + 4
3 x
2
x
3
2
x
2
x
2 x
4 x
1
x
1 x
1
x
1
x
1
x
1
0, 2, 2 – x// x
2
2
x
2
2
x
2
6
x
2
x
0
3 4
5
3
x
1 x 0 (j 1,4) j min 3
x
2 6. Cho baøi toaùn QHTT sau ñaây
x
2
4
2 x
4 Xeùt caùc veùctô X = (0, 0, 0, 8), Y = (14, 0, 0, 1),
Z = (7, 0, 0, 9/2) vaø T = (16, 1, 0, ½)
x
3
2
2
6 4
5
3
2 15
10
25
2
2
6
x
2
x
2
x
2
0,
x
2
x
2
x
2
0 x
3
x
3
x
3
0, x
5
0 0, (a) Vectô naøo laø P.A; vectô naøo laø P.A.C.B?
x
2 x
4 x
3 x
5 x
1
BAØI TAÄP CHÖÔNG 1 f x
( ) min 3 2 4 (b) Cho bieát Y laø P.A.T.Ö. Trong caùc vectô coøn laïi,
vectô naøo laø P.A.T.Ö cuûa baøi toaùn treân? Theâm 2 aån phuï x4, x5 0
vaøo raøng buoäc thöù nhaát,
thöù ba vaø x2 = x/
2 0, x//
vôùi x/
2 0, ta coù baøi toaùn daïng chính taéc
x
x
f x
( )
3
2
2
1
x
1
x
1
x
1
x
0,
2
x
3 x
1
3 4
0
0
2
0 2
1
1
3
x
3
x
3 1 0 0
4 det 0 1 0
4 det 0 0 0 1 x
1
x
1
0, x
2
x
2
1, 2, 3 j x j 0 0 1
0 0 1 BAØI TAÄP CHÖÔNG 1
(a) Caùc vectô X, Y, Z vaø T laø P.A cuûa baøi toaùn vì
chuùng thoûa heä raøng buoäc.
Vôùi X = (0, 0, 0, 8) thoûa 4 raøng buoäc chaët, ta coù
0
Vaäy X laø P.A.C.B khoâng suy bieán.
Töông töï, Y = (14, 0, 0, 1) laø P.A.C.B khoâng suy
bieán. Z vaø T khoâng phaûi laø P.A.C.B.
cho x1 = 0, ta coù heä phöông trình voâ nghieäm.
cho x2 = 0, giaûi hpt, ta coù x1 = 2, x3 = 1. Kieåm tra
tröïc tieáp phöông aùn X = (2, 0, 1) laø P.A.C.B khoâng
suy bieán. 7. a) Tìm P.A.C.B khoâng suy bieán cuûa baøi toaùn
x
2 22 cho x3 = 0, ta coù Y = (2, 1, 0). Kieåm tra tröïc tieáp
phöông aùn Y laø P.A.C.B khoâng suy bieán. (b) Vôùi Y laø P.A.T.Ö, ta coù f(Y) = 40, ta coù f(X) = –
16 f(Y), f(Z) = 12 f(Y) vaø f(T) = 40 = f(Y).
Vaäy T laø P.A.T.Ö. ThS. Nguyễn Công Trí - Tối ưu hóa * Chương 1 BAØI TAÄP CHÖÔNG 1 BAØI TAÄP CHÖÔNG 1 f x
( ) min 4 3 2 f x
( ) 4 3 2 min 7. b) Tìm P.A.C.B khoâng suy bieán cuûa baøi toaùn
x
3 x
1 x
1 x
2
x
3 4 10 x
3 0 2
3 14 x
3
x
3 x
1
x
1
0, x j x
2
x
2
1, 2,3 j x
1
x
1
0, x j x
2
x
2
1, 2,3
j
BAØI TAÄP CHÖÔNG 1 BAØI TAÄP CHÖÔNG 1 7. c) Tìm P.A.C.B khoâng suy bieán cuûa baøi toaùn
x
2 f x
( ) max x
1 f x
( ) 5 max 4 1
x
2
2 8 3
2 6 2 4 9 12 x x
1
x
1
x
1
0, 3
x
2
x
2
x
2
1, 2 j x
1
x
1
x
1
x
1
0, x
2
x
2
x
2
2
1, 2
j 3
x j j
23 8. b) Giaûi baøi toaùn baèng phöông phaùp hình hoïc 8. a) Giaûi baøi toaùn baèng phöông phaùp hình hoïc
x
2 ThS. Nguyễn Công Trí - Tối ưu hóa * Chương 1 BAØI TAÄP CHÖÔNG 1 BAØI TAÄP CHÖÔNG 1 f x
( ) 5 3 min
x
2 x x x 8. c) Giaûi baøi toaùn baèng phöông phaùp hình hoïc 3 2 min x
6 x
1 2 4 2 x x x 5
2 x
1 4 5 6 x 2 4 6
6
0
0 x
1
x
1
x
1
x
1
0, 2
x
x
2
x
2
x
2
1, 2 j j x
x x
x x x 3 12
9 2 4
4 6 3 5 x j 0 1,6 j BAØI TAÄP CHÖÔNG 1 BAØI TAÄP CHÖÔNG 1 9. Giaûi baøi toaùn QHTT sau ñaây
f x
2
( ) min 2 x x xf
)( 3 4 x 3 x max 3 2 2 3 x
4 10. Giaûi baøi toaùn QHTT sau ñaây 3 x 2 x 7 x
1 2 5 3 x 2 x x 3 x
1 2 4 5 x
1
1
2 x 3 4 2 3 x x x x 1 x
1 3 4 5 6
4
2 x
x 8 x x
12
10 3 5 6 17 x 1
4
1
4
x 1
2
2 x x 20 4 5 6 7 x
2
x
4
2
6,1
j
x 0 j
x x
11
1
0 j 7,1 j 24 11. Giaûi baøi toaùn QHTT sau ñaây
xf
x
)(
2
5
x ThS. Nguyễn Công Trí - Tối ưu hóa * Chương 1 BAØI TAÄP CHÖÔNG 1 BAØI TAÄP CHÖÔNG 1 x f x
( ) min xf
)( 3 2 2 x x min x
1 2 3 2 3 x
1
x
1 2 x
x x
x
x
3
2 2
4 1
2 2
2
5 x
x
x
2 4
x
28
31 3 x 2 3 2 4 x 3 5 x 16 2 3
x x
1
x
1
x
1 3 4 3 12. Giaûi baøi toaùn QHTT sau ñaây
3 13. Giaûi baøi toaùn QHTT sau ñaây
x
4
4 2
x
1
x
2
1
x
j x
2
2
4,1
x j 0 1,3 j j x f x
( ) min 3 x
1 2 0
Ñöa baøi toaùn veà daïng chính taéc
( ) 3 min f x 2 2 4
x
4 x
3 x x x x
3
2 1 2 4 3 2 x
2
2 28 x
1
x
1 x
2 x x x 2 4 2 2 3 5
5
2
3 31 x
4
x
4 x
5 x x 3 5 x
1
x
1
x
1 3 6
2
2 16 x
1
x
2
1 x
2
x
2 x
4 x
3
x
3 x j 0 1,6 j x 0 j 1,5 j BAØI TAÄP CHÖÔNG 1 BAØI TAÄP CHÖÔNG 1 x x Theâm 3 aån phuï
x4, x5, x6 0 vaøo 3 raøng
buoäc, ta coù baøi toaùn
daïng chuaån nhö sau f x
( ) 3 2 2 min xf
)( 3 2 x x min 3 3 x x x 2
x
4
10 x 3 2 3 2
x 4
x 4
x 2
2 8 2
2
x x
4
3
5
x
x
15
20 2 4 x
1
2
x
1 3 2
x 3
x 4 2 4 x x 10 x
1
x
1
x
3
1
x
1 2 3 3 4 x
1
x 0
j 2
2
x
2
4,1 x j 0 1, 4 j j 25 15. Giaûi baøi toaùn QHTT sau ñaây
14. Giaûi baøi toaùn QHTT sau ñaây
x
1 ThS. Nguyễn Công Trí - Tối ưu hóa * Chương 1 BAØI TAÄP CHÖÔNG 1 BAØI TAÄP CHÖÔNG 1 xf
)( 2 x x x 5 min 16. Giaûi baøi toaùn QHTT sau ñaây 17. Duøng phöông phaùp ñôn hình giaûi caùc baøi x
1 2 5 x
6 x 6 x x x 2 x 4 2 x
1 3 4 5 6 x 2 x x x 3 2 x
1 3 4 5 4
2
1
3 3 x 2 x 2 x 4 x x x
1 5 2 3 4 6
1
2
1
2 x 0 j 6,1 j 26 toaùn töø baøi taäp [1] ñeán baøi taäp [8].
f x
x
1
x
1
x
0
1
f x
0 ,
