Bài giảng Tối ưu hóa - Chương 4: Sơ đồ mạng

Nội dung text: Bài giảng Tối ưu hóa - Chương 4: Sơ đồ mạng

1. CHÖÔNG 4: SÔ ÑOÀ MAÏNG
2. I) MOÄT VÍ DUÏ THÖÏC TEÁ Ví duï 4.1: Giaû söû moät quy trình cöôùi vôï “chuaån” goàm caùc coâng vieäc coù trình töï thöïc hieän, ñònh möùc thôøi gian (thaùng) nhö sau : Coâng vieäc Trình töï thöïc hieän Ñònh möùc thôøi gian 1. Kieám vôï Baét ñaàu ngay 6 2. Kieám tieàn mua nhaø Baét ñaàu ngay 12 3. Kieám tieàn cöôùi vôï Baét ñaàu ngay 7 4. Ñaùm noùi Sau 1 2 5. Ñaùm hoûi Sau 2, 3, 4 4 6. Chuïp hình cöôùi Sau 5 3 7. Choïn ñoà cöôùi, nöõ trang Sau 5 4 8. Choïn nôi ñaët tieäc cöôùi Sau 5 5 9. Ñaùm cöôùi Sau 6, 7, 8 1
3.  Caâu hoûi ñaët ra laø:  Vôùi thôøi gian ñònh möùc nhö treân thì:  Thôøi gian ngaén nhaát hoaøn thaønh quy trình naøy (cöôùi ñöôïc vôï) laø bao nhieâu thaùng?  Muoán ruùt ngaén thôøi gian ngaén nhaát hoaøn thaønh quy trình naøy ta chæ caàn tìm caùch ruùt ngaén thôøi gian thöïc hieän cuûa moät soá coâng vieäïc naøo?  Nhöõng coâng vieäc naøo coù theå hoaøn thaønh chaäm treã moät khoaûng thôøi gian naøo ñoù so vôùi thôøi gian ñònh möùc maø khoâng aûnh höôûng ñeán thôøi gian ngaén nhaát hoaøn thaønh toaøn boä quy trình?   Caùc caâu hoûi treân ñöôïc traû lôøi 1 caùch deã daøng khi ta laäp sô ñoà maïng cho quy trình vaø tính 1 soá chæ tieâu cuûa sô ñoà.
4.  II) CAÙC KHAÙI NIEÄM VAØ ÑÒNH NGHÓA  1) Ñoà thò Laø 1 taäp hôïp caùc ñænh A vaø taäp hôïp caùc caïnh, cung U noái lieàn caùc ñænh cuûa A. Kyù hieäu: G = (A, U) : ñoà thò G  Ví duï 1: Trích 1 phaàn baûn ñoà TP.HCM coù caùc ñòa ñieåm a1,a2,a3, a4 ñöôïc noái vôùi nhau baèng ñöôøng 1 chieàu vaø ñöôøng 2 chieàu.
5.  Caùc ñænh: a1,a2,a3,a4. Taäp hôïp caùc ñænh A={a1,a2,a3 ,a4}  Caùc cung: (a1,a2),(a2,a4),(a4,a3); caùc caïnh: (a1,a3),(a2,a3)  Taäp hôïp caùc caïnh, cung: U= {(a1,a2),(a2,a4),(a4,a3),(a1,a3),(a2,a3)}  Cung (a1,a2) : ñænh goác (ñænh ñöùùng tröôùc) laø a1 , ñænh ngoïn (ñænh ñöùng sau) laø a2  Caïnh (a1,a3) : khoâng phaân bieät ñænh goác, ñænh ngoïn  2) Ñoà thò höõu haïn A laø taäp höõu haïn.  3) Ñoà thò coù höôùng Moïi phaàn töû trong U ñeàu laø cung.
6.  4) Daây chuyeàn töø ñænh a ñeán ñænh b laø 1 daõy ñænh vaø cung keá tieáp nhau.  Daây chuyeàn (1, u1,2,u2,3,u3, 4) noái ñænh 1 vôùi ñænh 4.
7.  5) Ñöôøng ñi laøø 1 daây chuyeàn coù caùc cung noái ñuoâi nhau (ngoïn cung tröôùc laø goác cuûa cung sau).  Ñöôøng ñi (1, u1,2,u2,3,u3, 4) coù ñænh baét ñaàu 1, ñænh keát thuùc 4.
8.  6) Khuyeân laø 1 cung coù ñænh goác vaø ñænh ngoïn truøng nhau.  Khuyeân (2, u2,2).
9.  7) Chu trình laø ñöôøng ñi coù ñænh baét ñaàu truøng vôùi ñænh keát thuùc.  Chu trình (1, u1,2,u2,3,u3,1)
10.  8) Ñoà thò lieân thoâng laø ñoà thò coù moïi caëp ñænh a, b cuûa A ñeàu noái vôùi nhau bôûi 1 daây chuyeàn.  Ví duï 5: ñoà thò lieân thoâng
11.  9) Ñoà thò phaûn xöùng  neáu 2 ñænh a, b baát kyø cuûa A coù cung noái töø a bthìseõ khoâng coù cung noái ngöôïc laïi töø b a.  Ví duï 5: ñoà thò phaûn xöùng
12.  10) Ñoà thò ñôn Giöõa 2 ñænh a, b baát kyø cuûa A coù nhieàu nhaát 1 cung noái.  Ví duï 5: ñoà thò ñôn
13.  11) Sô ñoà maïng laø 1 ñoà thò höõu haïn, coù höôùng, khoâng khuyeân, khoâng chu trình, lieân thoâng, phaûn xöùng, ñôn; ñoàng thôøi treân moãi cung gaùn cho 1 soá thöïc khoâng aâm goïi laø ñoä daøi cung.
14.  12) Ñoä daøi ñöôøng ñi laø toång caùc ñoä daøi cuûa caùc cung thuoäc ñöôøng ñi. Ví duï 9: Xeùt caùc ñöôøng ñi töø ñænh 1 tôùi ñænh 5 laø: Ñöôøng ñi A : (1, u1,2,u2,3,u4, 5) coù ñoä daøi 3 + 5 + 9 = 17 Ñöôøng ñi B : (1, u3,3,u4, 5) coù ñoä daøi 7 + 9 = 16 Ñöôøng ñi C : (1, u5,4,u6, 5) coù ñoä daøi 5 + 8 = 13  13) Ñöôøng ñi daøi nhaát trong caùc ñöôøng ñi töø ñænh i ñeán ñænh j laø ñöôøng ñi coù ñoä daøi lôùn nhaát töø ñænh i ñeán ñænh j. Ví duï 9: Trong 3 ñöôøng ñi töø ñænh 1 tôùi ñænh 5 thì ñöôøng ñi A laø ñöôøng ñi daøi nhaát (ñöôøng ñi coù ñoä daøi lôùn nhaát).
15. III) LAÄP SÔ ÑOÀ MAÏNG Ta laäp sô ñoà maïng löôùi (PERT - Program Evaluation and Review Technique) vôùi caùc töông öùng nhö sau: Ñænh töông öùng vôùi söï kieän hoaøn thaønh moät soá coâng vieäc vaø baét ñaàu moät soá coâng vieäc khaùc. Cung töông öùng vôùi coâng vieäc. Ñoä daøi cung töông öùng vôùi thôøi gian ñònh möùc cho coâng vieäc.
16.  Coâng vieäc (i,j) coù : söï kieän ñaàu (ñænh goác) i,söïkieänsau (ñænh ngoïn) j , thôøi gian ñònh möùc tij  Döï aùn laø 1 quaù trình goàm caùc coâng vieäc, nhieäm vuï coù lieân quan vôùi nhau, ñöôïc thöïc hieän nhaèm ñaït ñöôïc muïc tieâu ñaõ ñeà ra trong ñieàu kieän raøng buoäc veà thôøi gian, nguoàn löïc vaø ngaân saùch.
17. 1) Caùc chuù yù caàn thieát Khi laäp sô ñoà maïng ta chuù yù nhöõng tröôøng hôïp sau:
18.  2) Caùch veõ sô ñoà  Ví duï 4.1: Xaùc ñònh 3 loaïi coâng vieäc: - Coâng vieäc khôûi coâng (baét ñaàu ngay): y1,y2,y3 - Coâng vieäc keát thuùc (laø caùc coâng vieäc chæ naèm ôû coät coâng vieäc, khoâng naèm ôû coät trình töï thöïc hieän): y9 - Coâng vieäc trung gian: laø caùc coâng vieäc coøn laïi
19. Ví duï 4.2: Laäp sô ñoà maïng cho quy trình saûn xuaát sau: Coâng vieäc Trình töï thöïc hieän Ñònh möùc thôøi gian (ngaøy) y1 baét ñaàu ngay 15 y2 baét ñaàu ngay 21 y3 sau y1 9 y4 sau y1 16 y5 sau y2 17 y6 sau y2 20 y7 sau y2 19 y8 sau y3 vaø y5 14 y9 sau y4 11 y10 sau y4 14 y11 sau y7 10 y12 sau y6 , y8 , y9 , y11 18 y 13 sau y7 11
20. Xaùc ñònh 3 loaïi coâng vieäc: - Coâng vieäc khôûi coâng (baét ñaàu ngay): y1,y2 - Coâng vieäc keát thuùc (laø caùc coâng vieäc chæ naèm ôû coät coâng vieäc, khoâng naèm ôû coät trình töï thöïc hieän): y10 ,y12 ,y13 - Coâng vieäc trung gian: laø caùc coâng vieäc coøn laïi
21. Caùc phaàn xem theâm trong saùch.  3) Ñaùnh soá caùc ñænh  IV) PHAÂN TÍCH SÔ ÑOÀ MAÏNG THEO CAÙC CHÆ TIEÂU THÔØI GIAN  1) Chæ tieâu thôøi gian ñoái vôùi ñænh  1.5) Ñöôøng gaêng:  2) Chæ tieâu thôøi gian ñoái vôùi coâng vieäc  V) MOÄT SOÁ LÖU YÙ VEÀ SÔ ÑOÀ MAÏNG  1) Thôøi gian döï tröõ chung cuûa coâng vieäc  2) Ruùt ngaén thôøi gian hoaøn thaønh döï aùn  4) Baøi toaùn giaù thaønh reû nhaát  5) Ñaùnh giaù khaû naêng hoaøn thaønh döï aùn
22. Môøi gheù thaêm trang web: 42  