TÀI TRỌNG NGUYỄN TỐI ƯU HÓA NGUYỄN THỊ NGỌC THANH
taitrongnguyen107@gmail.com Trang 1/10 – BÀI TẬP QUY HOẠCH TUYẾN TÍNH
BAØI TAÄP QUI HOAÏCH TUYEÁN TÍNH
TS. Nguyeãn Thò Ngoïc Thanh
I. PHÖÔNG PHAÙP ÑÔN HÌNH VAØ BAØI TOAÙN ÑOÁI NGAÃU
Giaûi baøi toaùn qui hoaïch tuyeán tính sau vaø tìm phöông aùn toái öu khaùc (neáu coù ) :
1) f(x) = -x1 + 2x2 - x3 max
x1 - 2x2 + x3 6
-2x1 + x2 - 2x3 + 4x4 5
x1 + x3 - x4 3
xj 0 ( j = 1,2,3,4)
ÑS : fmax =19
2) f(x) = 2x1 + x2 - x3 + x4 min
x1 + x2 - x3 - 2 x4 = 2
- x2 + 3x3 + 7x4 2
2x3 + 3x4 5
xj 0 ( j = 1,2,3 )
(Chuù yù : Ñaët x4 = x14 - x24 . Ñaùp soá : x= (0, 0, 16 , - 9 , 17, 0) ; f(x) = - 25 )
3) f(x) = 3x1 - x2 + 2x3 - x4 max
x1 - x2 + x3 + x4 + x5 = 6
2x1 + x2 - 2x4 + x5 8
x1 + 2x4 + x5 9
xj 0 ( j = 1,2,3,4,5 )
(Chuù yù : Caùch choïn aån ñöa vaøo trong baûng ñôn hình 2.)
Ñaùp soá : x= (0, 17, 37/2 , 9/2 , 0, ) ; f(x) = 31/2 )
4) f(x) = 2x1 - 3x2 - 4x3 + x4 min
3x1 + x2 + 2x3 - 4x4 = 2
2x1 - x3 - 3x4 1
x1 - 4x3 - 2x4 4
xj 0 ( j = 1,2,3 ) , x4 0
Ñ.S : x = ( 0, 2/3,0, -1/3) fmin = - 7/3.
5) Cho baøi toaùn qui hoaïch tuyeán tính sau :
f(x) = 3x1 + 2m x2 + x3 min
- x1 + x2 + 2x3 = 6
x1 + 2x2 + (m-2) x3 5
3x1 - x2 + 2x3 = 14
xj 0 ( j = 1,2, 3 )
a) Giaûi baøi toaùn vôùi m =1.
b) Tìm giaù trò cuûa m ñeå x0 = (2,0,4) laø phöông aùn toái öu cuûa baøi toaùn.
(Ñaùp soá : a) x = (2,0,4,7) ; f(x) = 10. b) – 5/8 m 11/4
6 ) Cho baøi toaùn qui hoaïch tuyeán tính sau :
f(x) = -2x1 + mx2 + 4x3 + 4 x4 min
-x1 + 2x3 + x4 = 6
3x3 - 2x4 - 4
- x2 + x3 + x4 = 4
xj 0 ( j = 12,3,4 )
TÀI TRỌNG NGUYỄN TỐI ƯU HÓA NGUYỄN THỊ NGỌC THANH
taitrongnguyen107@gmail.com Trang 2/10 – BÀI TẬP QUY HOẠCH TUYẾN TÍNH
a) Giaûi baøi toaùn treân khi m = 2.
b) Vôùi giaù trò naøo cuûa m phöông aùn toái öu tìm ñöôïc trong caâu a cuõng laø phöông aùn toái
öu cuûa baøi toaùn?
c) Vôùi nhöõng giaù trò naøo cuûa m baøi toaùn khoâng coù phöông aùn toái öu ?
( Ñ.S : ( 2 , 0 , 4 , 0 , 16 ) ; m 0 ; m < 0)
7) Cho baøi toaùn qui hoaïch tuyeán tính sau :
f(x) = (8 + 2)x1 + (7 + 7)x2 + (3 + 2)x3 min
2x1 + x2 1
x1 + 2x2 + x3 1
xj 0 ( j = 1,2,3 )
a) Giaûi baøi toaùn treân vôùi = 0 vaø = 1
b) Chöùng toû raèng vôùi (-oo ; -3/2 ) , f(x) khoâng bò chaën döôùi treân taäp hôïp caùc
phöông aùn
(Höôùng daãn : döaï vaøo phöông aùn toái öu cuaû baøi toaùn khi = 1)
8) Cho baøi toaùn qui hoaïch tuyeán tính sau :
f(x) = x1 + 2x2 + 3x3 min
x1 + x2 + x3 6
2x1 + x2 + x3 7
x1 + 2x2 = 5
xj 0 ( j = 1,2,3 )
a/ Giaûi baøi toaùn treân. Tìm phöông aùn toái öu khaùc (neáu coù)
b) Vieát baøi toaùn ñoái ngaãu. Tìm phöông aùn toái öu cuûa baøi toaùn ñoái ngaãu.
(Ñs: x1 = (3,1,0,2,0) ; x2 = (5,0, 0,1,3) ; y = ( 0, 0 ,1) , fmin = dmax = 5 )
9) Cho baøi toaùn qui hoaïch tuyeán tính sau :
f(x) = -2x1 +3x2 +x3 +x4 - 4x5 max
3x1 - 2x2 + x3 - 4x4 + 2x5 = 9
7x1 - 3x2 - 7x4 + 5x5 = 14
4x1 - 2x2 - 4x4 + 3x5 = 8
xj 0 ( j = 1,2,3,4,5 )
a) Giaûi baøi toaùn treân
b) Vieát baøi toaùn ñoái ngaãu, chæ caùc caëp raøng buoäc ñoái ngaãu. Tìm taát caû phöông aùn toái
öu cuûa baøi toaùn ñoái ngaãu.
(ÑS: x = (2,0,3,0,0) f(x) = -1
y1 =1 ; y2 =t ; yû 3 = - (5+ 7t )/4 vôùi 5 t 9 hoaëc y1 = 1 ; y2 = - ( 5+ 4t )/7; yû 3 = t vôùi –
17 t -10)
10) Cho baøi toaùn qui hoaïch tuyeán tính sau :
f(x) = 3x1 - 2x2 +x3 min
x1 + 4x2 - 2x3 = 4
-x1 + 2x2 + 4x3 ≤ 6
4x1 + x2 + 5x3 ≥ 2
x1 0; x2≤ 0
coù phöông aùn toái öu laø x= (24/13; 0; -14/13).
TÀI TRỌNG NGUYỄN TỐI ƯU HÓA NGUYỄN THỊ NGỌC THANH
taitrongnguyen107@gmail.com Trang 3/10 – BÀI TẬP QUY HOẠCH TUYẾN TÍNH
Haõy vieát baøi toaùn ñoái ngaãu, chæ caùc caëp raøng buoäc ñoái ngaãu, tìm phöông aùn toái öu
cuûa baøi toaùn ñoái ngaãu vaø giaù trò haøm muïc tieâu öùng vôùi PATÖ tìm ñöôïc.
(ÑS Y = (11/13, 0, 7/13) dmax= 58/13 )
11) Cho baøi toaùn qui hoaïch tuyeán tính sau :
f(x) = x1 + x2 + 2x3 + x4 min
2x1 + x2 + x3 + x4 11
x1 + 2x3 + x4 11
x1+ 3x2 + x3 + x4 1 4
xj 0 ( j = 1,2,3,4 )
(ÑS: x1 =(0,1,0,11) f(x) = 12) x2= (11, 1, 0, 0 )
(Neân chuyeån veà baøi toaùn ñoái ngaãu ñeå giaûi )
12 ) Cho baøi toaùn qui hoaïch tuyeán tính sau :
f(x) = x1 + 3x2 + 4x3 min
3x1 - x2 + 2x3 7
- 2x1 + 4x2 + x3 = 12
- 4x1 + 3x2 + 8x3 10
xj 0 ( j = 1,2,3 )
Haõy xeùt xem caù vec-to x1 = ( 7/2, 9/2,1); x2 = ( 2, 7/2, 2) vaø x3 = (4, 5, 0 ) coù phaûi laø
phöông aùn toái öu cuûa baøi toùan treân khoâng?
13) Moät nhaø maùy coù 2,8 tyû ñoàng duøng ñeå mua thieát bò cho khu vöïc saûn xuaát môùi . Khu vöïc
daønh ñeå ñaët thieát bò coù dieän tích 166 m2. Coù 2 loaïi thieát bò coù theå choïn mua :
-Maùy loaïi A: moät maùy giaù 160 tr . ñoàng , trong 1 giôø hoaït ñoäng saûn xuaát ñöôïc 110 saûn
phaåm , ñeå hoaït ñoäng vaø cung caáp saûn phaåm ñöôïc caàn chieám 1 dieän tích laø 12m2
- Maùy loaïi B: moät maùy giaù 180 tr. ñoàng , trong 1 giôø hoaït ñoäng saûn xuaát ñöôïc 100 saûn
phaåm , ñeå hoaït ñoäng vaø cung caáp saûn phaåm ñöôïc caàn chieám 1 dieän tích laø 9m2
Tìm phöông aùn mua thieát bò toái öu sao cho trong 1 giôø toång soá saûn phaåm ñöôïc saûn xuaát ra
trong khu vöïc saûn xuaát môùi laø nhieàu nhaát.
( ÑS: 7maùy loaïi A vaø 9 maùy loaïi B)
14) Moät nhaø maùy loïc daàu hieän coù caùc loaïi daàu thoâ vôùi khoái löôïng laàn löôït laø 30000 ,
25000vaø 42000 ñôn vò . Kí hieäu caùc loaïi daàu thoâ laàn löôït laø A,B,C . Ngöôøi ta coù theå cheá bieán
thaønh 3 loaïi saûn phaåm laø khí ñoát , xaêng , daàu theo 3 phöông thöùc cheá bieán sau ñaây:
Phöông thöùc cheá bieán
Keát quaû
Khí ñoát Xaêng Daàu
2A + 1B + 1C (I)
2A + 2B + 1C (II)
1A + 1B + 1C (III)
9
10
6
4
6
3
7
10
5
Giaù baùn 1 ñv saûn phaåm 1 3 2
Giaûi baøi toaùn tìm keá hoaïch saûn xuaát toá öu sao cho toång doanh soá baùn ra laø nhieàu
nhaát.
( Ñ.S : f(x) = 675000)
TÀI TRỌNG NGUYỄN TỐI ƯU HÓA NGUYỄN THỊ NGỌC THANH
taitrongnguyen107@gmail.com Trang 4/10 – BÀI TẬP QUY HOẠCH TUYẾN TÍNH
15) Bieát yeâu caàu caùc chaát dinh döôõng Protit , Lipit trong 1 ngaøy cuûa moät loaïi gia suùc ; tæ leä
% theo khoái löôïng , caùc chaát dinh döôõng coù trong caùc loaïi thöùc aên A , B , C vaø giaù thöùc aên
cho trong baûng sau :
.Chaát dinh
döôõng
Khoái löôïng
toái thieåu (g)
Khoái löôïng toái
ña (g)
Tæ leä % trong caùc loaïi thöùc aên
A B C
Protit 70 Khoâng haïn cheá 50 40 30
Lipit 20 30 20 30 30
Giaù (ngaøn ñoàng / kg ) 8 7 6
Yeâu caàu laäp moâ hình vaø giaûi baøi toaùn tìm khoái löôïng thöùc aên toái öu caàn mua trong 1
ngaøy ñeå nuoâi loaïi gia suùc ñoù.
(Ñ.S :f(x) = 1120 ñoàng )
16) Moät xí nghieäp coù theå saûn xuaát 3 loaïi saûn phaåm , kyù hieäu laø A , B, C . Ñònh möùc hao phí
nguyeân vaät lieäu , voán, lao ñoäng (giôø coâng ) vaø lôïi nhuaän thu ñöôïc tính cho 1 ñôn vò saûn phaåm
moãi loaïi cho trong baûng sau :
Saûn phaåm A B C Möùc huy ñoäng toái ña
Nguyeân lieäu ( kg )
Voán ( 1000ñ)
Lao ñoäng (giôø coâng)
Lôïi nhuaän (1000ñ)
2
1
4
2
3
3
8
3
3
5
1
5
150
120
100
Xí nghieäp seõ saûn xuaát bao nhieâu saûn phaåm moãi loaïi sao cho trong phaïm vi soá nguyeân
lieäu , voán, giôø coâng huy ñoäng ñöôïc , xí nghieäp ñaït lôïi nhuaän cao nhaát .(Bieát raèng SP saûn xuaát
ra tieâu thuï ñöôïc heát).
a) Haõy laäp moâ hình baøi toaùn treân.
b) Giaûi baøi toaùn tìm phöông aùn saûn xuaát toái öu ?
c) Tìm lôøi giaûi toái öu cuûa baøi toaùn ñoái ngaãu ?
Ñ.S : fmax = 140 (ngaøn ñoàng)
17) Moät xí nghieäp coù theå saûn xuaát 3 loaïi saûn phaåm , kyù hieäu laø S1, S2, S3 , cung öùng cho thò
tröôøng . Cho bieát naêng suaát cuûa xí nghieäp ñoái vôùi moãi saûn phaåm laø S1 : 50 sp/giôø ,
S2 : 25 sp/giôø , S3 : 75 sp/giôø. Naêng löïc saûn xuaát trong moät tuaàn cuûa xí nghieäp theå hieän baèng
soá giôø saûn xuaát toái ña laø 45 giôø. Nhu caàu haøng tuaàn veà saûn phaåm cuûa xí nghieäp ôû thò tröôøng
do xí nghieäp cung öùng laø 600 saûn phaåm S1 , 800 saûn phaåm S2 vaø 1200 saûn phaåm S3. Giaù baùn
moãi ñôn vò saûn phaåm S1 laø 40.000ñ, saûn phaåm S2 laø 120.000ñ vaø saûn phaåm S3 laø 30.000ñ.
a) Laäp moâ hình baøi toaùn QHTT tìm keá hoaïch saûn xuaát cuûa xí nghieäp trong moät tuaàn cho
doanh thu cao nhaát ( boû qua ñieàu kieän nguyeâu ôû caùc bieán soá ).
b) Döïa vaøo suy luaän kinh teá tröïc tieáp , caên cöù vaøo giaù baùn , naêng löïc saûn xuaát , naêng löïc lao
ñoäng ( saûn phaåm/giôø saûn xuaát) , haõy tìm keá hoaïch saûn xuaát toái öu cho baøi toaùn .
c) Duøng phöông phaùp ñôn hình giaûi baøi toaùn ôû phaàn a.
d) Vieát baøi toaùn QHTT ñoái ngaãu töông öùng . Tìm lôøi giaûi toái öu cho baøi toaùn ñoái ngaãu.
fmax = 125.250 (ngaøn ñoàng )
18) Moät xí nghieäp goàm 2 phaân xöôûng , coù theå saûn xuaát hai loaïi saûn phaåm , kyù hieäu S1 vaø S2 .
Hao phí saûn xuaát ñöôïc tính baèng giôø maùy .
Giaû raèng xí nghieäp coù theå söû duïng nhaân coâng khoâng haïn cheá . Saûn löôïng trong thaùng vöøa
qua cuûa xí nghieäp laø 5.000 saûn phaåm S1 vaø 7.000 saûn phaåm S2 . Ñeå coù ñöôïc 5.000 saûn phaåm
S1 xí nghieäp ñaõ söû duïng 650 giôø maùy ôû phaân xöôûng 1 vaø 125 giôø maùy ôû phaân xöôûng 2 . Soá
giôø maùy hao toán ñeå saûn xuaát 7.000 saûn phaåm S2 ôû moãi phaân xöôûng laø 350 giôø .
Cho bieát giaù baùn moãi saûn phaåm S1 laø 25.000 ñ , moãi saûn phaåm S2 laø 15.000 ñ.
TÀI TRỌNG NGUYỄN TỐI ƯU HÓA NGUYỄN THỊ NGỌC THANH
taitrongnguyen107@gmail.com Trang 5/10 – BÀI TẬP QUY HOẠCH TUYẾN TÍNH
a) Döïa vaøo soá lieäu thaùng vöøa qua haõy laäp moâ hình baøi toaùn QHTT tìm keá hoaïch saûn
xuaát cho thaùng naøy sao cho toång doanh thu ñaït cao nhaát , neáu bieát toång soá giôø maùy coù ñöôïc ôû
phaân xöôûng 1 laø 1100 giôø vaø ôû phaân xöôûng 2 laø 550 giôø , giaù baùn saûn phaåm khoâng thay ñoåi .
b) Giaûi baøi toaùn treân baêng phöông phaùp ñôn hình .
c) Vieát baøi toaùn QHTT ñoái ngaãu töông öùng. Tìm lôøi giaûi toái öu cuûa baøi toaùn ñoái ngaãu.
(* Ñ.S : soá saûn phaåm S1laø 5238 , S2 laø 8381 fmax = 256.665 ngaøn ñoàng )
19) Moät xí nghieäp coù theå saûn xuaát moät loaïi saûn phaåm töø hai phaân xöôûng khaùc nhau. Caên cöù
vaøo caùc nguoàn löïc hieän coù trong 1 tuaàn phaân xöôûng 1 coù theå saûn xuaát toái ña 70 saûn phaåm ,
phaân xöôûng 2 saûn xuaát toái ña laø 100 saûn phaåm . Toång soá giôø coâng xí nghieäp coù theå söû duïng
trong tuaàn ôû caû hai phaân xöôûng laø 600 giôø . Soá giôø coâng caàn thieát ñeå saûn xuaát moät ñôn vò saûn
phaåm ôû phaân xöôûng 1 laø 10 giôø , ôû phaân xöôûng 2 laø 5 giôø . Möùc saûn löôïng toái thieåu trong
tuaàn cuûa xí nghieäp laø 80 saûn phaåm . Chi phí saûn xuaát cho moät ñôn vò saûn phaåm ôû phaân xöôûng
1 laø 20 ngaøn ñoàng vaø ôû phaân xöôûng 2 laø 30 ngaøn ñoàng .
a) Haõy laäp moâ hình baøi toaùn QHTT , giaûi vaø tìm keá hoaïch saûn xuaát trong tuaàn ñaûm baûo toång
chi phí saûn xuaát thaáp nhaát.
b) Trong moâ hình a) cho bieát baøi toaùn QHTT coøn coù yù nghóa nöõa khoâng ,neáu boû raøng buoäc
veà saûn löôïng toái thieåu ( 80 saûn phaåm ).
c) Cho bieát giaù baùn moät ñôn vò saûn phaåm ñöôïc aán ñònh laø 50 ngaøn ñoàng . Döïa theo naêng löïc
hieän coù vaø yeâu caàu saûn löôïng toái thieåu trong tuaàn , moãi phaân xöôûng phaûi saûn xuaát bao
nhieâu saûn phaåm ñeå xí nghieäp ñaït lôïi nhuaän cao nhaát ?
d) Vieát baøi toaùn QHTT ñoái ngaãu cuûa baøi toaùn ôû phaàn c. Tìm PATU cuûa baøi toaùn ñoái ngaãu.
* Ñ.S : a) : fmin = 2000 ngaøn ñoàng ; c) : fmax = 2300 ngaøn ñoàng )
20) Ñeå saûn xuaát moät hoãn hôïp nhieân lieäu ngöôøi ta söû duïng 3 loaïi thaønh phaàn , kí hieäu laø
N1,N2,N3. Nhieät löôïng rieâng cuûa N1, N2, N3 töông öùng laø 7.000, 4.000, 5.000 (Kcal/ñvkl).
Ñvkl : ñôn vò khoái löôïng . Chi phí söû duïng 1 ñvkl nhieân lieäu N1, N2, N3 töông öùng laø 2, 1, 2
ñôn vò tieàn teä.Haõy choïn cô caáu thaønh phaàn hoãn hôïp sao cho toång khoái löôïng nhieân lieäu hoãn
hôïp khoâng vöôït quùa 3.000 ñvkl,toång chi phí söû duïng khoâng vöôït quùa 4.000 ñôn vò tieàn teä ,
loaïi nhieân lieäu N3 ñöôïc söû duïng khoâng quùa 500 ñvkl, loaïi nhieân lieäu N1 phaûi ñöôïc söû duïng ít
nhaát 500 ñvkl vaø ñaït ñöôïc nhieät löôïng toûa ra toái ña khi söû duïng heát hoãn hôïp nhieân lieäu thaønh
phaàn .
Ñ.S : fmax = 15.000.000 Kcal
21) Ngöôøi ta caàn caét nhöõng thanh goã daøi 2m thaønh 520 ñoaïn daøi 1,2m ; 400 ñoaïn daøi 0,8m vaø
300 ñoaïn daøi 0,6m . Haõy giaûi baøi toaùn tìm phöông aùn SX sao cho soá goå thöøa laø ít nhaát.
(Ñ.S:fmin = 36m )
22) Moät coâng ty coù caùc ñôn ñaët haøng trong voøng 4 thaùng . Chi phí saûn xuaát thay ñoåi haèng
thaùng do caùc thay ñoåi trong chi phí nguyeân vaät lieäu . Naêng löïc saûn xuaát cuûa coâng ty laø 100
ñôn vò/thaùng laøm trong giôø vaø 15 ñôn vò / thaùng laøm ngoaøi giôø. Baûng sau ñaây cho thaáy nhu
caàu cuûa caùc ñôn ñaët haøng vaø chi phí saûn xuaát haøng thaùng :
Döõ lieäu Thaùng 1 Thaùng 2 Thaùng 3 thaùng 4
Khoái löôïng ñôn haøng(ñôn vò)
Chi phí trong giôø/ñ.v (tr.ñ)
Chi phí ngoaøi giôø/ñ.v (tr.ñ)
95
30
35
85
30
35
110
32
37
115
32
36
Chi phí löu kho cho 1 ñôn vò haøng hoùa chöa baùn ñöôïc laø 2 tr.ñ/thaùng/1ñ.vò. Coâng ty
khoâng coù 1 ñôn vò haøng hoùa naøo vaøo ñaàu thaùng 1vaø mong raèng cuõng khoâng coøn 1 ñôn vò
haøng hoùa naøo vaøo cuoái thaùng 4.