Đề thi môn Tối Ưu hoá
Tài liệu tham khảo đề thi môn Tối ưu hoá dành cho sinh viên đang theo học chuyên ngành kinh tế.
ÑEÀ THI TOÁI ÖU HOÙA - K31 CHÍNH QUY
ÑEÀ 1
Caâu 1 (2,5ñ): Moät xí nghieäp cô khí caàn caét nhöõng thanh saét daøi 2m thaønh 400 ñoaïn daøi 0,8m;
500 ñoaïn daøi 0,6m; 600 ñoaïn daøi 0,5m. Haõy laäp moâ hình baøi toaùn tìm phöông aùn caét sao cho soá
saét thöøa ít nhaát (Chæ laäp moâ hình, khoâng giaûi).
Caâu 2 (4ñ): Cho baøi toaùn QHTT (A) sau:
f(x)= x1+3x2-x3+3x4 min
x1+ x2-2x3 +x4 >=4
-x1 +x3 =0, j=1,4
a) (2,5ñ) Giaûi baøi toaùn (A) treân
b) (1,5ñ) Vieát baøi toaùn ñoái ngaãu cuûa (A) vaø tìm patö cuûa baøi toaùn ñoái ngaãu
Caâu 3 (3,5ñ): (3ñ) Giaûi baøi toaùn vaän taûi sau. (0,5ñ) Tìm patö khaùc, neáu coù.
T 50 75 95
F
50 5 7 6
100 6 8 9
50 6 9 9
Caùc sai soùt “cheát ngöôøi” !:
Caâu 1: Ñaët bieán goïi sai. Khoâng coù ñieàu kieän cho bieán goïi. Thieáu ñieàu kieän xj nguyeân.
Khoâng dieãn giaûi moâ hình (giaûi thích yù nghóa caùc ñieàu kieän raøng buoäc).
Caâu 2: Khoâng ñöa baøi toaùn veà daïng chuaån. Khoâng xaùc ñònh pacb ban ñaàu. Khoâng ghi xj>=0,
j=1,8 maø chæ ghi xj>=0, j=1,4 ; thaäm chí khoâng theøm ghi ñieàu kieän cuûa xj.
Khoâng coù ñieàu kieän M>0 raát lôùn. Ghi M ôû raøng buoäc chung.
Keát quaû thay vì ghi coät patö x thì laïi ghi coät c.
Khoâng ghi coät öùng vôùi bieán phuï trong baûng ñôn hình, “töôûng” coù theå boû ñöôïc gioáng nhö bieán
giaû!
Khoâng ghi giaù trò toái öu f, chæ ghi patö x. Khoâng xaùc ñònh patö cuûa baøi toaùn goác maø chæ coù patö
cuûa baøi toaùn chuaån.
Khoâng ghi caùc caëp raøng buoäc ñoái ngaãu ra. Khoâng ghi giaù trò toái öu cuûa baøi toaùn ñoái ngaãu.
Caâu 3: Khoâng ghi patö x cuûa baøi toaùn goác, chæ ghi patö cuûa baøi toaùn CBTP. Khoâng ghi giaù trò toái
öu f.
Taïi sao toâi laøm “quaù trôøi” maø toâi laïi rôùt ! híc híc híc
1 Ñeà thi Toái öu hoùa – K31 CQ * ThS. Phaïm Trí Cao
ÑEÀ 2
Caâu 1 (2ñ): Trong caùc meänh ñeà sau, meänh ñeà naøo ñuùng, meänh ñeà naøo sai? Neáu sai haõy giaûi
thích vì sao?
1) (1ñ) Baøi toaùn vaän taûi khoâng caân baèng thu phaùt cuõng coù theå khoâng coù patö.
2) (1ñ) Phöông aùn X=(xij)m*n cuûa baøi toaùn vaän taûi CBTP coù ñuùng m+n-1 thaønh phaàn xij >0 laø
phöông aùn cô baûn (pa cöïc bieân).
Caâu 2 (4ñ): Cho baøi toaùn QHTT sau:
f= 12x1+3x2+5x3+8x4 min
3x1+2x2+ x3+ x4 =24
xj >=0, j=1,4
1) (3ñ) Giaûi baøi toaùn treân
2) (1ñ) Vieát baøi toaùn ñoái ngaãu vaø chæ ra caùc caëp raøng buoäc ñoái ngaãu
Caâu 3 (4ñ): (3,5ñ) Giaûi BTVT sau. (0,5ñ) Tìm patö khaùc, neáu coù.
T 60 10 50
F
30 1 2 3
40 2 7 9
40 6 3 7
25 7 4 8
ÑEÀ 3
Caâu 1 (2ñ): Ngöôøi ta troàng 3 gioáng luùa R1, R2, R3 treân 3 maûnh ruoäng I, II, III. Do tính chaát cuûa
töøng maûnh ruoäng vaø cuûa ñaëc ñieåm töøng gioáng luùa neân naêng suaát cuûa caùc gioáng luùa treân caùc
maûnh ruoäng laø khaùc nhau vaø ñöôïc cho ôû baûng:
Ruoäng I II III
Gioáng luùa
R1 6 5 7
R2 4 6 -
R3 5 6 4
Bieát raèng:
- Dieän tích caùc maûnh ruoäng I, II, III töông öùng: 30ha, 60ha, 40ha.
- Dieän tích caùc gioáng luùa R1, R2, R3 caàn troàng laàn löôït laø 50ha, 40ha, 40ha.
- Luùa R2 khoâng troàng ñöôïc ôû maûnh ruoäng III.
Haõy laäp moâ hình baøi toaùn tìm keá hoaïch troàng luùa ñeå thu ñöôïc toång saûn löôïng lôùn nhaát.
2 Ñeà thi Toái öu hoùa – K31 CQ * ThS. Phaïm Trí Cao
Caâu 2 (4,5ñ): Cho baøi toaùn QHTT sau:
f(x)= x1-3x2+2x3+6x4 min
-3x1 +x2 +2x4 =23
-x1 +x2+x3 -x4 =8
xj >=0, j=1,4
a) (3ñ) Giaûi baøi toaùn treân
b) (1,5ñ) Vieát baøi toaùn ñoái ngaãu (D) vaø tìm patö cuûa (D)
Caâu 3 (3,5ñ): Giaûi baøi toaùn vaän taûi vôùi soá lieäu sau. Tìm patö khaùc, neáu coù.
T 60 10 50
F
30 1 2 3
40 2 7 9
40 6 3 7
25 7 4 8
ÑEÀ 4
Caâu 1 (2ñ): Laäp moâ hình cho baøi toaùn sau:
Moät doanh nghieäp caàn mua thieát bò môùi ñöa vaøo kinh doanh saûn xuaát vôùi soá tieàn ñaàu tö ñeå mua
thieát bò döï tính laø 200 ngaøn $. Coù hai loaïi thieát bò coù theå mua vôùi caùc thoâng tin nhö sau:
Thieát bò A: ñôn giaù 10 ngaøn $, thoâng soá kyõ thuaät cho bieát trong 1 giôø hoaït ñoäng tieâu hao nhieân
lieäu laø 30 ñôn vò, naêng suaát trung bình laø 60 saûn phaåm/giôø. Moãi thieát bò chieám dieän tích 4m2.
Thieát bò B: ñôn giaù 15 ngaøn $, thoâng soá kyõ thuaät cho bieát trong 1 giôø hoaït ñoäng tieâu hao nhieân
lieäu laø 45 ñôn vò, naêng suaát trung bình laø 70 saûn phaåm/giôø. Moãi thieát bò chieám dieän tích 6m2.
Theo baïn, doanh nghieäp seõ choïn mua thieát bò nhö theá naøo ñeå coù lôïi nhaát (tieâu hao nhieân lieäu ít
nhaát), bieát raèng keá hoaïch cuûa doanh nghieäp laø phaûi ñaït ít nhaát 800 saûn phaåm/giôø, vaø dieän tích
phaân xöôûng laø 100m2.
Caâu 2 (4ñ): Cho baøi toaùn QHTT sau:
f(x)= 12x1+9x2+7x3+8x4 min
3x1+2x2 +x3 +x4=24
xj >=0, j=1,4
a) (3ñ) Giaûi baøi toaùn treân.
b) (1ñ) Vieát baøi toaùn ñoái ngaãu vaø chæ ra caùc caëp raøng buoäc ñoái ngaãu.
3 Ñeà thi Toái öu hoùa – K31 CQ * ThS. Phaïm Trí Cao
Caâu 3 (4ñ): Cho baøi toaùn vaän taûi sau:
T 60 40 30
F
20 6 4 5
60 10 3 5
40 7 6 4
50 13 6 5
a) (3,5ñ) Giaûi baøi toaùn treân.
b) (0,5ñ) Patö tìm ñöôïc ôû caâu a) coù duy nhaát? Neáu khoâng haõy tìm patö khaùc?
ÑEÀ 5
Caâu 1 (2ñ): Trong caùc meänh ñeà sau, meänh ñeà naøo ñuùng, meänh ñeà naøo sai? Neáu sai haõy giaûi
thích vì sao?
1) (1ñ) Baøi toaùn vaän taûi khoâng caân baèng thu phaùt cuõng coù theå khoâng coù patö.
2) (1ñ) Phöông aùn X=(xij)m*n cuûa baøi toaùn vaän taûi CBTP coù ñuùng m+n-1 thaønh phaàn xij >0 laø
phöông aùn cô baûn (pa cöïc bieân).
Caâu 2 (4,5ñ): Cho baøi toaùn QHTT (A) sau:
f(x)= x1+3x2-x3+3x4 min
x1 +x2-2x3+x4 >=4
-x1 +x3 =0, j=1,4
a) (3ñ) Giaûi baøi toaùn (A) treân.
b) (1,5ñ) Vieát baøi toaùn ñoái ngaãu cuûa (A) vaø tìm patö cuûa baøi toaùn ñoái ngaãu.
Caâu 3 (3,5ñ): Giaûi baøi toaùn vaän taûi vôùi soá lieäu sau.
T 60 10 50
F
30 1 2 3
40 2 4 9
40 6 3 7
25 7 5 8
Tìm pa vaän chuyeån sau cho toång chi phí vaän chuyeån laø nhoû nhaát, ñoàng thôøi traïm phaùt thöù 2 phaûi
phaùt heát haøng.
4 Ñeà thi Toái öu hoùa – K31 CQ * ThS. Phaïm Trí Cao
ÑEÀ 6
Caâu 1 (2ñ): Laäp moâ hình cho baøi toaùn sau:
Ñeå cheá taïo 1 loaïi hôïp chaát, ngöôøi ta caàn söû duïng 3 loaïi ñôn chaát A, B, C. Coù 3 loaïi quaëng coù
khaû naêng cung caáp caùc loaïi ñôn chaát naøy, kyù hieäu laø Q1, Q2, Q3. Baûng sau ñaây cho ta bieát haøm
löôïng caùc ñôn chaát coù trong moät ñôn vò quaëng moãi loaïi:
Loaïi quaëng Q1 Q2 Q3
Ñôn chaát
A 2 4
B 1 2 6
C 5 3
Ñeå cheá taïo moät ñôn vò hôïp chaát, ngöôøi ta caàn söû duïng ít nhaát 2,5 ñôn vò chaát A, 3 ñôn vò chaát B
vaø 4 ñôn vò chaát C. Chi phí khai thaùc moãi moät ñôn vò quaëng moãi loaïi laàn löôït laø 3, 6, 5 ngaøn ñ.
Xaùc ñònh löôïng quaëng moãi loaïi caàn khai thaùc ñeå coù theå thöïc hieän cheá taïo ñöôïc loaïi hôïp chaát caàn
thieát vaø chi phí khai thaùc laø ít nhaát.
Caâu 2 (4ñ): Cho baøi toaùn QHTT (P) sau:
f(x)= 2x1+x2+2x3 min
x1 +x2-2x3 >=18
2x2 +x3 >=12
xj >=0, j=1,3
a) (2,5ñ) Giaûi baøi toaùn (P).
b) (1,5ñ) Vieát baøi toaùn ñoái ngaãu cuûa (P) vaø tìm patö cuûa baøi toaùn ñoái ngaãu.
Caâu 3 (4ñ): Cho baøi toaùn vaän taûi sau:
T 70 30 40 60
F
50 7 4 5 0
40 7 6 5 0
40 3 5 4 0
70 8 7 9 M
Vaø pa cho tröôùc:
20 0 0 30
0 0 20 20
0
X = 30 0 0 10
20 30 20 0
Trong ñoù M>0 laø giaù trò voâ cuøng lôùn.
a) (0,5ñ) Haõy cho bieát pa X0 coù phaûi laø pacb khoâng? Vì sao?
(0,5ñ) Xuaát phaùt töø X0, baïn haõy caûi tieán pa ñeå ñöôïc pacb.
b) (3ñ) Tìm pa vaän chuyeån sao cho toång chi phí vaän chuyeån laø nhoû nhaát.
5 Ñeà thi Toái öu hoùa – K31 CQ * ThS. Phaïm Trí Cao
ÑEÀ 7
Caâu 1 (2ñ): Moät nhaø maùy chuyeân saûn xuaát 3 loaïi thuyeàn: thuyeàn coù maùi cheøo, ca noâ, xuoàng
caiac. Lôïi nhuaän thu ñöôïc treân moät ñôn vò saûn phaåm cuûa töøng loaïi thuyeàn töông öùng laø 300$,
180$, 150$. Ñeå saûn xuaát 1 chieác thuyeàn moãi loaïi ngöôøi ta caàn phaûi söû duïng nguyeân lieäu nhoâm
vaø giôø coâng lao ñoäng ôû caùc phaân xöôûng saûn xuaát (1 saûn phaåm do 2 phaân xöôûng cuøng saûn xuaát),
ñöôïc cho ôû baûng sau:
1 thuyeàn coù maùi cheøo 1 ca noâ 1 thuyeàn caiac
Nhoâm (kg) 17 8 6
Phaân xöôûng 1 (giôø) 3 5 4
Phaân xöôûng 2 (giôø) 2 1 3
Nhaø maùy coù khoaûng 500kg nhoâm, giôø coâng lao ñoäng höõu duïng ôû phaân xöôûng 1 vaø 2 töông öùng
laø 150 giôø vaø 100 giôø. Haõy laäp moâ hình baøi toaùn tìm keá hoaïch saûn xuaát cuûa nhaø maùy ñeå ñaït möùc
lôïi nhuaän toái ña.
Caâu 2 (4,5ñ): Cho baøi toaùn QHTT (A) sau:
f(x)= x1+3x2-3x3+2x4 min
x1 +x2-2x3 +x4 >=2
-x1 +x3 >=5
2x2-2x3 +x4 =10
xj >=0, j=1,4
a) (3,5ñ) Giaûi baøi toaùn (A).
b) (1ñ) Vieát baøi toaùn ñoái ngaãu cuûa (A) vaø chæ ra caùc caëp raøng buoäc ñoái ngaãu.
Caâu 3 (3,5ñ): Cho baøi toaùn vaän taûi sau:
T 60 60 80 100
F
80 4 7 6 8
60 5 3 6 5
110 6 4 7 9
(3ñ) Tìm patö cuûa baøi toaùn.
(0,5ñ) Patö coù duy nhaát khoâng, taïi sao?
6 Ñeà thi Toái öu hoùa – K31 CQ * ThS. Phaïm Trí Cao
ÑEÀ 8
Caâu 1 (2ñ): Moät taøu chôû haøng coù troïng taûi 200 taán vaø dung tích chöùa laø 80m3. Taøu coù theå chôû
ñöôïc 5 loaïi haøng vôùi khoái löôïng, theå tích vaø giaù trò nhö sau:
Loaïi haøng 1 2 3 4 5
Khoái löôïng (taán/ñôn vò) 1,1 1,7 2,1 1,6 2,3
Theå tích (m3/ñôn vò) 0,7 0,6 0,5 0,8 0,9
Giaù trò (trieäu ñ/ñôn vò) 7 8 9 10 13
Haõy laäp moâ hình baøi toaùn tìm soá löôïng haøng toái öu moãi loaïi caàn xeáp leân taøu sao cho toång giaù trò
laø lôùn nhaát.
Caâu 2 (4,5ñ): Cho baøi toaùn QHTT sau:
f(x)= 3x1+2x2+3x3+5x4 max
x1 +x2+2x3+2x4 =10
xj >=0, j=1,4
a) (3ñ) Giaûi baøi toaùn treân vaø (0,5ñ) tìm patö khaùc, neáu coù.
b) (1ñ) Vieát baøi toaùn ñoái ngaãu vaø chæ ra caùc caëp raøng buoäc ñoái ngaãu.
Caâu 3 (3,5ñ): (3ñ) Giaûi baøi toaùn vaän taûi vôùi soá lieäu sau. (0,5ñ) Tìm patö khaùc, neáu coù.
T 50 75 95
F
50 5 7 6
100 6 8 9
50 6 9 9
7 Ñeà thi Toái öu hoùa – K31 CQ * ThS. Phaïm Trí Cao
