Đề tài Điều hành dự án bằng phương pháp PERT-PCM và ứng dụng giải bài toán lập lịch thi công công trình

SV ne t.vn Trang:1 Chöông môû ñaàu GIÔÙI THIEÄU CHUNG VEÀ NHIEÄM VUÏ Ñeà taøi “Ñieàu haønh döï aùn baèng phöông phaùp PERT-PCM vaø öùng duïng giaûi baøi toaùn laäp lòch thi coâng coâng trình”, bao goàm - Tìm hieåu phöông phaùp PERT-PCM (phöông phaùp sô ñoà maïng löôùi). - ÖÙng duïng giaûi baøi toaùn laäp lòch thi coâng coâng trình. + Löu tröõ lòch thi coâng caùc döï aùn + Cho bieát thôùi gian baét ñaàu moät döï aùn vaø thôøi gian keát thuùc döï aùn + Theâm moät soá haïng muïc khi döï aùn ñang ñöôïc thi coâng + Boû moät soá haïng muïc khi döï aùn ñang thi coâng + Ñöa ra lòch thi coâng caùc haïng muïc toái öu nhaát SV ne t.vn Trang:2 Chöông I ÑIEÀU HAØNH DÖÏ AÙN BAÈNG PHÖÔNG PHAÙP PERT-CMP (Phöông phaùp sô ñoà maïng löôùi) Döï aùn (Project) laø moät taäp hôïp caùc hoaït ñoäng (Activity) lieân quan vôùi nhau vaø phaûi ñöôïc thöïc hieän theo moät thöù töï naøo ñoù cho ñeán khi hoaøn thaønh toaøn boä caùc hoaït ñoäng. Hoaït ñoäng ñöôïc hieåu nhö laø moät vieäc ñoøi hoûi thôøi gian, vaø nguyeân lieäu (Resource) ñeå hoaøn thaønh. Tröôùc kia ñeå ñieàu haønh döï aùn ngöôøi ta thöôøng duøng bieåu ñoà Gantt (Gantt bar chart), laø moät ñoà thò goàm caùc ñöôøng keû ngang, bieåu thò ñieåm khôûi coâng vaø keát thuùc hoaït ñoäng. Nhöôïc ñieåm cuûa bieåu ñoà laø khoâng xaùc ñònh ñöôïc quan heä giöõa caùc hoaït ñoäng, neân khoâng aùp duïng ñöôïc cho caùc döï aùn lôùn (large-scale project), ñoøi hoûi ñaët keá hoaïch (planning), ñieàu haønh thöïc hieän (scheduling) va kieåm tra (controlling) moät caùch heä thoáng vaø hieäu quaû, thaäm chí phaûi toái öu hoaù hieäu quaû (veà thôøi gian vaø tieát kieäm nguyeân lieäu). Vì vaäy, gaàn nhö ñoàng thôøi vaøo naêm 1956-1958, hai phöông phaùp keá hoaïch, ñieàu haønh vaø kieåm tra döï aùn ñaõ ra ñôøi. Phöông phaùp ñöôøng gaêng hoaëc phöông phaùp ñöôøng tôùi haïn (Critical path method, vieát raét laø CPM) ñöôïc E.I.du Pont de Nemous vaø coâng ty xaây döïng cuûa oâng ñöa ra. Phöông phaùp thöù hai coù teân laø Kyõ thuaät xem xeùt vaø ñaùnh giaù döï aùn (Project evaluation and review technique, vieát taét laø PERT) laø keát quaû nghieân cöùa cuûa moät coâng ty tö vaán theo ñaët haøng cuûa haûi quaân Myõ, duøng ñeå ñieàu haønh caùc hoaït ñoäng nghieân cöùu vaø phaùt trieån chöông trình teân löûa ñoái cöïc. Hai phöông phaùp ñöôïc hình thaønh ñoäc laäp nhöng raát gioáng nhau, cuøng nhaèm vaøo muïc ñích ñieàu haønh thôøi gian laø chính. Söï khaùc nhau chính laø trong CPM thôøi gian öôùc löôïng cho coâng vieäc, ñöôïc coi laø taát ñònh (Deterministic), coøn trong PERT coù theå laø ngaãu nhieân (Probabilistic). Ngoaøi ra CPM coù tính ñeán quan heä thôøi gian. Ngaøy nay, khi ñaõ phaùt trieån leân, hai phöông phaùp ñöôïc coi laø moät, döôùi moät teân chung laø Phöông phaùp ñieàu haønh döï aùn PERT-CPM, hoaëc Phöông phaùp sô ñoà maïng löôùi hoaëc heä thoáng kieåu PERT (PERT-type system). Noù ñöôïc duøng ñeå thöïc hieän raát nhieàu kieåu döï aùn, töø xaây döïng, laäp trình maùy tính, saûn xuaát phim ñeán vaän ñoäng tranh cöû chính trò hoaëc caùc cuoäc giaûi phaãu phöùc taïp. Phöông phaùp ñieàu haùnh döï aùn PERT-CPM goàm ba pha (töùc laø ba khaâu): keá hoaïch, ñieàu haønh vaø kieåm tra ñieàu chænh. Pha keá hoaïch coù noäi dung laø laäp moät sô ñoà maïng löôùi (arrow network diagram hoaëc arrow diagram), töông töï moät ñoà thò coù höôùng. Pha naøy môû ñaàu baèng vieäc taùch döï aùn thaønh nhieàu hoaït ñoäng rieâng vaø ñònh thôøi gian hoaøn thaønh chuùng. Trong maïng, moãi cung coù höôùng bieåu dieãn hoaït ñoäng vaø caû sô ñoà maïng bieåu thò moái quan heä giöõa caùc hoaït ñoäng. Moãi nuùt bieåu thò moät bieán coá hoaëc söï kieän (event), ñaùnh daáu hoaøn thaønh moät soá hoaït SV ne t.vn Trang:3 ñoäng (activity) laø caùc cung ñi vaøo nuùt, vaø baét ñaàu caùc hoaït ñoäng öùng vôùi caùc cung ra khoûi nuùt. Pha ñieàu haønh (scheduling phase) coù nhieäm vuï xaây döïng bieåu ñoà thôøi gian, chæ roõ thôøi ñieåm baét ñaàu vaø keát thuùc cuûa moãi hoaït ñoäng vaø moái quan heä giöõa caùc hoaït ñoäng. Noùi rieâng, ñieàu quan troïng laø phaûi tính chính xaùc caùc hoaït ñoäng tôùi haïn, töùc laø gaêng (critical), caàn chuù yù ñaëc bieät khi thöïc hieän, ñeå toaøn boä döï aùn ñöôïc hoaøn thaønh ñuùng haïn. Pha kieåm tra bao goàm vieäc söû duïng sô ñoà maïng löôùi, vaø bieåu ñoà thôøi gian ñeå theo doõi vaø baùo caùo ñònh kì tieán trieån cuûa döï aùn. Neáu caàn thì phaûi phaân tích laïi vaø xaùc ñònh sô ñoà môùi cho phaàn döï aùn coøn laïi. I. Laäp sô ñoà maïng löôùi Nhö treân ñaõ noùi, pha ñaàu cuûa phöông phaùp PERT-CPM laø laäp keá hoaïch theå hieän ôû moät sô ñoà maïng löôùi, bieåu dieãn nhö moät ñoà thò coù höôùng. Haõy xeùt moät döï aùn xaây döïng moät toaø nhaø. Vieäc taùch döï aùn thaønh caùc hoaït ñoäng nhö ñaøo ñaát, xaây moùng, xaây töôøng thoâ, lôïp maùi, ñaët ñöôøng daây ñieän … laø do kieán truùc sö hoaëc kyõ sö xaây döïng laøm. Döïa vaøo ñoù, ngöôøi quaûn lyù döï aùn laäp ñöôïc sô ñoà maïng löôùi nhö H.1.1. Caùc soá beân caïnh cung laø thôøi gian thöïc hieän hoaït ñoäng ñoù. Qua sô ñoà maïng löôùi H.1.1 ta thaáy roõ moái quan heä giöõa caùc hoaït ñoäng veà thôøi gian. Chaúng haïn hoaït ñoäng (6, 8) laø traùt ngoaøi-phaûi sau (4, 6) laø lôïp maùi, nhöng ñoäc laäp vôùi (5, 7) laø chænh töôøng trong. Cuõng vaäy (4, 7) ñoäc laäp vôùi (4, 5) vaø (5, 7). ÔÛ ñaây coù hai hoaït ñoäng giaû (dummmy activity) vôùi thôøi gian ñeå thöïc hieän baèng 0 ñöôïc ñöa vaøo ñeå ñaûm baûo qui taéc sô ñoà. Cung giaû (11, 12), kyù hieäu bôûi ñöôøng ñöùt ñoaïn, ñöa vaøo ñeå ñaûm baûo qui taéc khoâng coù hai hoaït ñoäng cuøng bieán coá baét ñaàu vaø keát thuùc, töùc laø khoâng coù 2 cung coù cuøng goác vaø ngoïn (töùc laø ñoà thò ñôn). Vieäc sôn töôøng trong vaø laøm saøn coù cuøng bieán coá daàu laø nuùt 9, töùc laø bieán coá laùt vaùn töôøng xong, vaø bieán coá cuoái laø nuùt 12 (laøm saøn vaø sôn töôøng xong, baét ñaàu hoaøn thieän trong). Do ñoù ta phaûi theâm nuùt 11 laø bieán coá giaû vaø cung giaû (11, 12). Cung giaû (5, 8) ñeå chæ raèng hoaït ñoäng (4, 5) phaûi hoaøn thaønh tröôùc khi baét ñaàu hoaït ñoäng (8, 10) (neáu boû cung giaû naøy thì thôøi ñieåm laøm hai vieäc laø ñoäc laäp). Cung giaû naøy laø phuïc vuï cho qui taéc sô ñoà maïng löôùi phaûi theå hieän ñuû quan heä thöù töï caàn coù. Neáu quan heä thôøi gian coù daïng: vieäc x2 baét ñaàu khi xong 1/3 vieäc x1, vieäc x3 baét ñaàu khi xong moät nöûa x1, thì ta phaûi theâm caùc nuùt ñaùnh daáu caùc bieán coá xong 1/3x1 vaø xong 1/2x1 ñoù nhö ôû H1.2. SV ne t.vn Trang:4 Khôûi coâng 2 Ñaøo moùng 4 Xaây moùng 10 Xaây thoâ 6 Lôïp maùi 4 Chænh thaúng töôøng ngoaøi Ñaët daây ñieän 7 7 Traùt ngoaøi 5 Chænh thaúng töôøng trong 9 Sôn ngoaøi 8 EÙp vaùn laùt töôøng Laøm saøn 4 5 Sôn töôøng Hoaøn thieän ngoaøi 2 0 Hoaøn thieän trong 6 Keát thuùc Hình 1.1 Toùm laïi: Sô ñoà maïng löôùi phaûi laø moät ñoà thò coù höôùng, ñôn, lieân thoâng, khoâng coù khuyeân (töùc laø cung coù goác vaø ngoïn cuøng laø moät nuùt), khoâng coù chu trình coù höôùng (directed cycle), coù nuùt khôûi coâng vaø nuùt keát thuùc. 2 1 x1 3 1 x1 2 1 x1 1 2 3 4 5 7 9 11 12 6 8 10 13 X2 X3 SV ne t.vn Trang:5 Hình 1.2 II. Phaân tích caùc chæ tieâu thôøi gian. Xaùc ñònh ñöôøng caêng. Pha ñieàu haønh coù nhieäm phaân tích caùc chæ tieâu thôøi gian vaø ñöa ra caùc baûng vaø soá lieäu caàn thieát treân sô ñoà maïng löôùi. Neáu trong döï aùn phaûi ñieàu haønh caû nguyeân lieäu (hoaëc nhaân löïc) thì phaûi xeùt caû caùc chæ tieâu ñoù, ta seõ noùi ñeán ôû muïc sau. II.1. Tính caùc thôøi ñieåm. Chæ tieâu ôû ñaây laø thôøi ñieåm sôùm cuûa bieán coá (earliest time for an event) laø thôøi ñieåm bieán coá xaûy ra khi moïi hoaït ñoäng tröôùc noù ñöôïc baét ñaàu sôùm nhaát coù theå. Thôøi ñieåm sôùm cuûa bieán coá i thöôøng kyù hieäu laø Ei. Caùc Ei ñöôïc tính theo höôùng taêng (forward pass), töùc laø ñi töø nuùt khôûi coâng theo thöù töï taêng cuûa nuùt i. Nhö vaäy vôùi nuùt khôûi coâng 1 thì E1 = 0. Ñeán nuùt 2 trong sô ñoà H1.1 thì E2 roõ raøng baèng 2 vì bieán coá hoaøn thaønh hoaït ñoäng (1, 2) phaûi laø E1 + t12, ôû ñaây t12 laø thôøi gian thöïc hieän hoaït ñoäng (1, 2). Vieäc tính E3, E4, E5, E6, E9, E10 vaø E11 cuõng töông töï vì caùc nuùt töông öùng chæ coù moät cung vaøo, khi ñoù: Ei = Ej + tji ÔÛ ñaây j laø nuùt ngay tröôùc i. Chaúng haïn E6 + t46 = 16 + 6 = 22. Neáu coù nhieàu cung vaøo nuùt, töùc laø nhieàu hoaït ñoäng keát thuùc taïi bieán coá, thì töø ñònh nghóa Ei roõ raøng ñaây laø thôøi ñieåm moïi hoaït ñoäng ñoù vöøa xong caû, töùc laø phaûi laáy maximum cuûa caùc toång. Chaúng haïn E7 = max {E4 + t45,E5 + t57} = max {16 + 7, 20 + 5} = 25, E8 = max {E5 + t58,E6 + t68} = max {20 + 0, 22 + 7} = 29 Toång quaùt, coâng thöùc tính Ei cho moïi tröôøng hôïp laø : Ei = maxmax {Ej + tji}, j ôû ñaây j laø caùc nuùt ngay tröôùc i, töùc laø coù cung noái tôùi i. Caùc Ei ñöôïc ghi ôû H.1.3 laø soá ñaàu trong ngoaëc ôû moãi nuùt. Thôøi ñieåm muoän (latest time) cuûa bieán coá j laø thôøi ñieåm muoän nhaát moïi cung ñi vaøo bieán coá j ñeàu hoaøn thaønh maø khoâng laøm thay ñoåi thôøi ñieåm keát thuùc döï aùn sôùm nhaát coù theå, kyù hieäu laø Lj. Ñoái laïi vôùi Ej, caùc Lj ñöôïc tính theo höôùng luøi (backward pass), töùc laø ñi töø nuùt keát thuùc. Theo ñònh nghóa, ôû nuùt keát thuùc thì En = Ln, ôû thí duï H.1.1 laø E13 = L13 = 44. neáu ôû bieán coá chæ coù moät cung ra, töùc laø moät hoaït ñoäng ñöôïc baét ñaàu thì, thôøi ñieåm muoän laø : Lj =Li - tji, Töùc laø thôøi ñieåm muoän cuûa nuùt ngay sau noù tröø ñi thôøi gian thöïc hieän hoaït ñoäng noái hai nuùt. Caùc bieán coá 12, 11, 10, 8, 7, 6, 3, 2 vaø 1 ôû H.1.1 laø tröôøng hôïp naøy. Neáu coù nhieàu cung ra khoûi bieán coá, thì theo ñònh nghóa ta coù : Lj = i }t-{L min jii SV ne t.vn Trang:6 ÔÛ ñaây min theo caùc nuùt i ngay sau j vaø tji laø thôøi gian thöïc hieän hoaït ñoäng noái (j, i). Caùc nuùt 9, 5, 4 laø ôû tröôøng hôïp naøy, chaúng haïn : L9 = min {L11 – t9 11, L12 – t9 12} = min (38 – 4, 38 - 5) = 33 Haõy chuù yù söï ‘’ñoái xöùng ‘‘ cuûa quaù trình tính Ei vaø Lj. Caùc Lj ñöôïc ghi ôû soá thöù 2 trong ngoaëc ôû moãi nuùt trong H.1.3. II.2. Tính thôøi gian döï tröõ. Trong thôøi gian döï tröõ (slack hoaëc float) cuûa moät bieán coù laø hieäu thôøi ñieåm muoän vaø thôøi ñieåm sôùm cuûa noù : di = Li – Ei. Thôøi gian döï tröõ (slack hoaëc float) cuûa hoaït ñoäng ñöôïc chia laøm hai loaïi. Thôøi gian döï tröõ chung (total slack hoaëc total float) cuûa hoaït ñoäng (i, j) laø : TFij = Lj – Ei – tij. TFij chæ laø thôøi gian coù theå trì hoaõn cuûa hoaït ñoäng (i,j) maø khoâng aûnh höôûng ñeán thôøi ñieåm keát thuùc caû döï aùn. Vì noù baèng thôøi gian toái ña daønh cho hoaït ñoäng (i, j) laø Lj - Ei tröø ñi thôøi gian ñeå thöïc hieän laø tij. Thôøi gian döï tröõ ñoäc laäp (free float hoaëc free slack), kyù hieäu laø FFij, cuõng laø kyù hieäu thôøi gian daønh cho (i, j) vaø thôøi gian thöïc hieän laø tij, nhöng vôùi giaû thieát laø moïi hoaït ñoäng ñeàu baét ñaàu sôùm coù theå, vaäy : FFij = Ej – Ei – tij. 1 2 3 4 5 7 9 11 12 6 8 10 13 1 2 4 4 4 4 4 4 4 (44, 44) 6 0 2 (38, 42) (29, 33) (22, 26) (0, 0) (2, 2) (6, 6) (16, 16) (20, 20) (25, 25) (33, 33) 1 4 5 (38, 38) 2 4 10 4 5 8 Hình 1.3 SV ne t.vn Trang:7 Treân sô ñoà maïng löôùi thì di laø hieäu hai soá trong ngoaëc ôû nuùt i, thöôøng ñöôïc ghi baèng soá trong oâ vuoâng caïnh nuùt. Thôøi gian döï tröõ chung cuûa hoaït ñoäng TFij ñöôïc ghi trong oâ vuoâng caïnh ôû moãi cung. Coøn thôøi gian döï tröõ ñoäc laäp cuûa hoaït ñoäng FFij ít quan troïng hôn, thöôøng khoâng ghi, xem H.1.3. II.3. Ñöôøng gaêng. (ñöôøng tôùi haïn) Caùc hoaït ñoäng coù thôøi gian döï tröõ chung baèng 0 caàn ñöôïc chuù yù ñaëc bieät vì trì hoaõn noù seõ aûnh höôûng ñeán thôøi gian keát thuùc döï aùn. Töø ñoù coù : Ñònh nghóa II.3.1. Ñöôøng gaêng hoaëc ñöôøng tôùi haïn (critical path) laø moät ñöôøng ñi töø nuùt khôûi coâng ñeán nuùt keát thuùc maø moïi hoaït ñoäng treân ñöôøng ñeàu coù thôøi gian döï tröõ chung baèng 0. (Chaúng haïn treân H.1.3 coù moät ñöôøng gaêng laø 1 –> 2 –> 3 –> 4 –>5 –> 7 –> 9 –> 12 –> 13 ) hoaït ñoäng (i, j coù TFij = 0 ñöôïc goïi laø hoaït ñoäng gaêng (critital activity). Bieán coá i coù di =0 ñöôïc goïi laø bieán coá gaêng (critical event). Moät soá tính chaát quan troïng cuûa ñöôøng gaêng laø nhö sau. 1. Moãi döï aùn ñeàu coù ít nhaát moät ñöôøng gaêng. 2. Taát caû caùc hoaït ñoäng (i, j) coù TFij = 0, töùc laø moïi hoaït ñoäng gaêng ñeàu phaûi naèm treân ñöôøng gaêng. 3. Moïi bieán coá gaêng, töùc laø bieán coá i coù di = 0, ñeàu phaûi naèm treân ñöôøng gaêng. Bieán coù khoâng gaêng khoâng theå naèm treân ñöôøng gaêng. 4. Ñöôøng noái nuùt khôûi coâng ñeán nuùt keát thuùc maø moïi bieán coá treân ñoù ñeàu gaêng coù theå khoâng phaûi ñöôøng gaêng vì coù theå coù hoaït ñoäng khoâng gaêng. Chaúng haïn ñöôøng 1 –> 2 –> 3 –> 4 –> 7 –> 9 –> 12 –> 13 khoâng gaêng vì TF47 = 2. 5. Ñöôøng gaêng laø ñöôøng daøi nhaát trong caùc ñöôøng noái nuùt khôûi coâng ñeán nuùt keát thuùc. Ñieàu 5 naøy laø roõ töø ñònh nghóa vì ôû nuùt khôûi coâng vaø keát thuùc hai thôøi ñieåm sôùm vaø muoän truøng nhau vaø thôøi gian hoaøn thaønh döï aùn chính laø hieäu thôøi gian ôû hai nuùt (ôû H.1.3 laø 44 - 0). Ñöôøng gaêng laø ñöôøng goàm caùc hoaït ñoäng khoâng coù döï tröõ neân toång chieàu daøi, töùc laø thôøi gian thöïc hieän, laø toaøn boä thôøi gian thöïc hieän döï aùn (ôû H.1.3 laø 44), neân phaûi daøi nhaát. Treân H.1.3 ñöôøng gaêng ñöôïc toâ ñaäm. Moät thí duï döï aùn coù nhieàu ñöôøng gaêng laø sô ñoà ôû H.1.3 nhöng vôùi t46 thay töø 6 thaønh 10. Khi ñoù thôøi gian döï tröõ cuûa caùc hoaït ñoäng (6, 8), (8, 10) vaø (10, 13) vaø thôøi gian döï tröõ cuûa caùc bieán coá 6, 8 vaø 10 ñeàu thay töø 4 thaønh 0. Luùc naøy ñöôøng 1 –> 2 –> 3 –> 4 –> 6 –> 8 –> 10 –> 13 laø ñöôøng gaêng thöù hai. Caùc chæ tieâu thôøi gian cuûa döï aùn ôû H.1.3 ñöôïc ghi vaøo baûng 1.1 Bieán coá Thôøi ñieåm sôùm Thôøi ñieåm muoän Thôøi gian döï tröõ Hoaït ñoäng Thôøi gian döï tröõ chung 1 0 0 0 (1, 2) 0 SV ne t.vn Trang:8 2 2 2 0 (2, 3) 0 3 6 6 0 (3, 4) 0 4 16 16 0 (4, 5) 0 5 20 20 0 (4, 6) 4 6 22 26 4 (4, 7) 2 7 25 25 0 (5, 7) 0 8 29 33 4 (6, 8) 4 9 33 33 0 (7, 9) 0 10 38 42 4 (8, 10) 4 11 37 38 1 (9, 11) 1 12 38 38 0 (9, 12) 0 13 44 44 0 (10, 13) 4 (12, 13) 0 Baûng1.1. Chæ tieâu thôøi gian xaây nhaø Ngoaøi caùc chæ tieâu chính noùi treân, khi caàn caùc thoâng tin chi tieát hôn ñeå ñieàu haønh döï aùn, ngöôøi ta cuõng ñöa ra moät soá khaùi nieäm veà thôøi gian khaùc nöõa nhö sau. Thôøi ñieåm khôûi coâng sôùm (earliest start) cuûa hoaït ñoäng (i, j) laø thôøi sôùm cuûa nuùt goác: ESij = Ei. Thôøi ñieåm hoaøn thaønh sôùm (earliest completion) cuûa hoaït ñoäng (i, j) laø ECij = Ei + tij. Thôøi ñieåm khôûi coâng muoän (latest start) cuûa hoaït ñoäng (i, j) laø LSij = Lj - tij. Thôøi ñieåm hoaøn thaønh muoän (latest completion) cuûa hoaït ñoäng (i, j) laø LCjj = Lj töùc laø thôøi ñieåm muoän cuûa nuùt ngoïn. Nhaän xeùt raèng ECij  Ej , LSij  Li. Thaät vaäy, ta coù Ej = k max {Ek + tkj}  Ei +tij = ECij, Vì i cuõng laø moät trong caùc nuùt k ngay tröôùc j. Baát ñaúng thöùc thöù hai töông töï. Thôøi gian döï tröõ cuûa moät ñöôøng ñi (total float of a path) P töø nuùt khôûi coâng ñeán nuùt keát thuùc, kyù hieäu TFp, laø thôøi gian coù theå keùo daøi theâm caùc hoaït ñoäng treân ñöôøng naøy maø khoâng aûnh höôûng ñeán thôøi ñieåm hoaøn thaønh coâng trình, töùc laø TP =    PGPijGij TTtt , ôû ñaây GG ij Tt  laø ñoä daøi ñöôøng gaêng vaø   TPtPij laø ñoä daøi ñöôøng P, laø toång thôøi gian thöïc hieän hoaït ñoäng treân ñöôøng P. Heä soá gaêng (critital coefficient) bieåu thò möùc ñoä caêng thaúng veà thôøi gian cuûa moät ñöôøng P noái nuùt khôûi coâng vaø keát thuùc, khoâng phaûi ñöôøng gaêng G, ñöôïc ñònh nghóa laø SV ne t.vn Trang:9 PGG PGP P TT TT K   : , ôû ñaây T PG laø ñoä daøi quaõng ñöôøng (töùc laø moät phaàn cuûa ñöôøng) maø P truøng vôùi G. Roõ raøng O < K P < 1 vaø K P caøng gaàn 1 thì thôøi haïn thöïc hieän caùc hoaït ñoäng khoâng gaêng trong P caøng chaët cheõ. Hai ñònh nghóa treân ñaây cuûa ñöôøng ñi coù theå môû roäng cho ñöôøng P coù nuùt ñaàu vaø cuoái truøng vôùi nuùt trong ñöôøng gaêng, khoâng caàn laø nuùt khôûi coâng vaø keát thuùc cuûa caû döï aùn. Thí duï II.1. ÔÛ döï aùn treân H.1.3, ñöôøng gaêng döôïc toâ ñaäm. Thôøi ñieåm hoaøn thaønh sôùm EC68 = E6 + t68 = 22 + 7 = 29 = E8, EC10, 13 = 40 < E13 = 44. Thôøi ñieåm khôûi coâng muoän LS46 = L6 – t46 = 26 – 6 = 20 > L4 = 16. Baây giôø giaû söû P laø ñöôøng ñi 1 –> 2 –> 3 –> 4 –> 5 –> 6 –> 8 –> 10 –> 13 thì TP =  Pijt =40 Neân thôøi gian döï tröõ cuûa P laø T G – TP = 44 – 40 = 40. Heä soá gaêng laø K P = 11 10 4 40  (khoâng coù quaõng chung vôùi ñöôøng gaêng). Goïi Q laø ñöôøng 1 –> 2 – > 3 –> 4 –> 7 –> 9 –> 12 –> 13 thì TQ = 42, KQ = 11 10 9 7 3544 3542    . Ta thaáy maëc duø T Q > T P nhöng thôøi haïn thöïc hieän caùc hoaït ñoäng khoâng gaêng trong P laïi chaët cheõ hôn hoaït ñoäng khoâng gaêng (4, 7) duy nhaát cuûa Q. Nguyeân nhaân laø (4, 7) laø khoâng gaêng duy nhaát, neân moïi söï nôùi loûng cuûa Q ñeàu doàn cho hoaït ñoäng naøy. Chuù yù raèng caùc döõ lieäu thôøi gian quan troïng nhaát laø caùc chæ tieâu coù trong baûng 1.1. ÔÛ baûng naøy cuõng cho thaáy ñöôøng gaêng (ñöôøng goàm caùc hoaït ñoäng gaêng, töùc laø coù thôøi gian döï tröõ chung baèng 0). II.4. Bieåu ñoà thôøi gian Moät caùch truyeàn thoáng, beân caïnh sô doà löôùi baûng, ñeå theo doõi ñieàu haønh thôøi gian cho döï aùn laø duøng bieåu ñoà thôøi gian (time chart). Ta haõy xeùt caùch veõ vaø söû duïng bieåu ñoà thôøi gian qua moät thí duï. Thí duï II.2. Xeùt döï aùn ôû H.1.4, vaø baûng 1.2 töông öùng. (chuù yù laø hoaït ñoäng giaû (4, 5) laïi laø hoaït ñoäng gaêng.) H.1.4 Bieán coá Ei Li di Hoaït ñoäng TFij 1 2 3 4 5 6 7 SV ne t.vn Trang:10 1 2 3 4 5 6 7 0 2 3 6 6 13 19 0 4 3 6 6 13 19 0 2 0 0 0 0 0 (1, 2) (1, 3) (2, 4) (3, 4) (3, 5) (4, 5) (4, 6) (4, 7) (5, 6) (5, 7) (6, 7) 2 0 2 0 1 0 4 11 0 8 0 Baûng 1.2 Bieåu ñoà thôøi gian cho H.1.5. ÔÛ ñaây chæ coù ttruïc hoaønh laø thôøi gian . Cao ñoä khoâng quan troïng. Ta bieåu dieãn caùc hoaït ñoäng gaêng phía treân. Ñoä daøi (thôøi gian) laø coá ñònh, chaët cheõ cho caùc hoaït ñoäng gaêng. Hoaït ñoäng giaû (4, 5) coù ñoä daøi baèng 0 neân bieåu dieãn baèng ñoaïn ñöùng. Moãi hoaït ñoäng khoâng gaêng bieåu dieãn ôû ñoä cao khaùc nhau ñeå nhìn roõ vì caùc hoaït ñoäng naøy coù ñoä cô ñoäng vaø ñöôïc ñieàu haønh baèng bieåu ñoà thôøi gian. 2 2 3 2 5 Hình: 1.5 Bieåu ñoà ñöôïc veõ töø caùc Ei vaø Li ôû Baûng1.2 (hoaït ñoäng gaêng hay khoâng gaêng thì theo TFij baèng 0 hay khaùc 0). Caùc soá khoâng coù voøng chæ thôøi gian thöïc hieän cuûa hoaït ñoäng. Chaúng haïn hoaït ñoäng (1, 2) thöïc hieän trong 2 ñôn vò thôøi gian, ñöôïc pheùp xeâ dòch trong khoaûng thôøi gian 4 ñôn vò (töø 0 ñeán 4). Xeùt saâu hôn thì söï xeâ dòch coù töï do trong khoaûng thôøi gian naøy khoâng laø phuï thuoäc vaøo FFij = 1 1 3 5 4 2 2 3 4 5 4 4 5 6 6 7 7 7 0 2 3 4 6 10 13 16 19 SV ne t.vn Trang:11 TFij. Neáu FFij = TFij thì hoaït ñoäng (i, j) coù theå cô ñoäng tuyø yù trong khoaûng thôøi gian veõ bieåu ñoà. Neáu FFij < TFij thì hoaït ñoäng (i, j) chæ ñöôïc baét ñaàu muoän hôn thôøi ñieåm khôûi coâng sôùm ESij moät khoaûng thôøi gian khoâng quaù FFij thì môùi khoâng aûnh höôûng ñeán caùc hoaït ñoäng ngay sau noù (duy nhaát) laø (2, 4) môùi ñöôïc xeâ dòch tuyø yù trong khoaûng thôøi gian 2 ñeán 6. Neáu (1, 2) thöïc hieän luøi laïi khoaûng 1 ñeán 3 chaúng haïn, thì aûnh höôûng ñeán hoaït ñoäng (2, 4). Maëc duø coù FF24 = TF24 nhöng luùc naøy coù chæ coøn ñöôïc xeâ dòch thöïc hieän trong khoaûng töø 3 ñeán 6. III. Ñieàu khieån nhaân löïc. Caùc hoaït ñoäng khoâng gaêng ñöôïc pheùp xeâ dòch nhaát ñònh, nhaát laø khi FFij = TFij. Coù theå saép ñaët chuùng ñaùp öùng caùc yeâu caàu khaùc nöõa. Ngoaøi thôøi gian ra, chaúng haïn nhaân löïc, nguyeân lieäu, chi phí …Veà maët toaùn hoïc xöû lyù yeâu caàu loaïi naøo cuõng vaäy. ÔÛ ñaây ta noùi theo ngoân ngöõ nhaân löïc chaúng haïn. Thí Duï III.1. Giaû söû nhaân löïc cho caùc hoaït ñoäng cuûa döï aùn ôû Thí Duï II.2 ñoøi hoûi nhö sau: Hoaït ñoäng Soá nhaân coâng Hoaït ñoäng soá nhaân coâng (1, 2) 0 (4, 6) 2 (1, 3) 5 (4, 7) 1 (2, 4) 0 (5, 6) 2 (3, 4) 7 (5, 7) 5 (3, 5) 3 (6, 7) 6 Chuù yù raèng taïi thôøi ñieåm hai hoaït ñoäng cuøng tieán haønh thì soá nhaân löïc caàn laø toång hai soá coâng nhaân. Vì vaäy caàn phaûi saép xeáp kheùo caùc hoaït ñoäng khoâng gaêng ñeå ñoøi hoûi toång nhaân coâng cuûa caû döï aùn ít (taïm coi laø moãi ngöôøi bieát laøm moïi vieäc). Vieäc saép xeáp toái öu laø phöùc taïp, ñeán nay ta söû duïng bieåu ñoà thôøi gian bieåu dieãn theâm nhaân löïc ñeå saép xeáp theo tröïc quan. H.1.6 (a) bieåu dieãn toång coâng nhaân caàn ôû moãi thôøi ñieåm neáu taát caû caùc hoaït ñoäng khoâng gaêng xeáp vaøo luùc sôùm nhaát coù theå, coøn H.1.6 (b) laø töông öùng khi xeáp vaøo luùc muoän nhaát coù theå. Hai bieåu ñoà naøy neân veõ thaúng döôùi H.1.5 nöõa. Saép ñaët sôùm nhaát ôû hình (a) cho thaáy ôû moãi thôøi ñieåm döï aùn caàn nhieàu nhaát laø 10 coâng nhaân coøn ôû saép ñaët muoän nhaát (b) laø 12 coâng nhaân. ÔÛ hai phöông aùn naøy, soá coâng nhaân caàn ôû caùc thôøi ñieåm khoâng ñeàu. Theo tröïc quan ta chænh laïi töø (a) nhö sau: chuyeån hoaït ñoäng (4, 6) ñeáân thôøi ñieåm muoän nhaát coù theå, chuyeån (4, 7) ñeán ngay sau khi (5, 7) keát thuùc. Keát quaû ñöôïc veõ laïi ôû bieåu ñoà H.1.7. (chuù yù laø hoaït ñoäng (1, 2) vaø (2, 4) khoâng caàn coâng nhaân neân khoâng caàn veõ.). SV ne t.vn Trang:12 (3, 5) (4, 7) (4, 6) (3, 4) (5, 7) (1, 3) (6, 7) (5, 6) H .I.6 (a) (4, 7) (3, 5) (3, 4) (5, 7) (1, 3) (4, 6) (6, 7) (5, 6) S o á c o ân g n h a ân 2 5 6 7 8 1 0 S o á n h a ân c o ân g 2 5 6 7 8 1 0 1 2 Thôøi gian Thôøi gian 3 4 6 10 11 13 14 17 19 3 4 6 10 11 13 14 17 19 SV ne t.vn Trang:13 H .I.6 (b) 1 1 3 4 5 6 7 4 6 7 1 7 5 5 3 4 1 2 2 4 Thôøi gian S o á c o ân g n h a ân 5 6 7 9 1 0 3 4 6 10 11 13 14 17 19 3 4 6 10 11 13 14 17 19 Thôøi Gian SV ne t.vn Trang:14 Hình 1.7 IV. Hoaøn thaønh sôùm döï aùn. Treân ñaây ñaõ xeùt thôøi ñieåm hoaøn thaønh döï aùn laø coá ñònh vaø xaùc ñònh caùc ñöôøng gaêng, phaûi thöïc hieän chaët cheõ ñeå döï aùn hoaøn thaønh ñuùng thôøi gian qui ñònh. Neáu muoán giaûm thôøi gian hoaøn thaønh döï aùn thì laøm theá naøo ? Ta cuõng söû duïng ñöôøng gaêng, nhöng phaûi döïa vaøo kyõ thuaät vaø coâng ngheä, chöù khoâng phaûi quaûn lyù baèng toaùn hoïc ñöôïc nöõa. Cuï theå laø phaûi duøng coâng ngheä môùi, taêng vaät tö, coâng nhaân .. ñeå coù thôøi gian thöïc hieän caùc hoaït ñoäng ngaén hôn. Nhöng taäp chung vaøo hoaït ñoäng naøo ? Roõ raøng laø vaøo caùc hoaït ñoäng gaêng. Cuï theå laø neáu ta quan taâm ñeán haïn cheá chi phí thì vôùi (i, j)  G, tìm soá gia chi phí Cij khi ñaït ñöôïc ruùt ngaén thôøi gian thöïc hieän hoaït ñoäng laø tij (tìm baèng thöïc teá coâng ngheä, khoâng phaûi thuaàn tuyù toaùn hoïc). Khi ñoù seõ choïn caùch taêng chí phí ñeå giaûm thôøi gian sao cho ñaït ij ij t C   min . Giaû söû cöïc tieåu laø 0 0 ij ij t C   . Khi ñoù ñoä daøi ñöôøng gaêng môùi, töùc laø thôøi gian hoaøn thaønh döï aùn môùi, laø  ,0 ~ ij GG tTT ôû ñaây toång laáy treân moïi hoaït ñoäng gaêng. V. Döï aùn coù tính ngaãu nhieân. Trong caùc muïc treân ta ñaõ coi thôøi gian thöïc hieän caùc hoaït ñoäng tij laø xaùc ñònh hoaøn toaøn töø ñaàu, khi laäp sô ñoâ maïng löôùi. Do ñoù ta coù moâ hình taát ñònh (detreministic model). Trong thöïc teá, nhieàu yeáu toá baát ñònh phaûi ñöôïc tính ñeán, do ñoù thôøi gian thöïc hieän hoaït ñoäng (i, j) laø moät bieán ngaãu nhieân (random variable), maø ta chæ xaùc ñònh ñöôïc phaân boá xaùc suaát (probability distributtion) qua kinh nghieäm vaø soâù lieäu thoáng keâ. Töø ñoù daãn ñeâùn phaûi söû duïng moâ hình ngaãu nhieân hoaëc goïi khaùc laø moâ hình xaùc suaát (probabilistic model). Vieäc tính toaùn caùc chæ tieâu ñeå ñieàu haønh döï aùn coù hai nhieäm vuï chính. Moät laø tính kyø voïng (mean hoaëc expected value) cuûa caùc ñaïi löôïng caàn tính, chaúng haïn thôøi gian thöïc hieän hoaït ñoäng (activity time), thôøi gian hoaøn thaønh döï aùn (project time), vaø phöông sai (variance) cuûa caùc ñaïi löôïng naøy. Hai laø tính xaùc suaát cuûa bieán coá naøo ñoù, chaúng haïn bieán coá laø döï aùn hoaøn thaønh tröôùc thôøi ñieåm T. Thôøi gian thöïc hieän moãi hoaït ñoäng, thöôøng goïi taét laø thôøi gian hoaït ñoäng, trong moâ hình ngaãu nhieân thöôøng ñöôïc giaû thieát laø xaùc ñònh ñöôïc ba yeâùu toá sau. Thôøi gian laïc quan (optimistic time) kyù hieäu laø a, laø thôøi gian caàn ñeå laøm xong khi hoaït ñoäng ñöôïc thöïc hieän thuaän lôïi nhaát. Thôøi gian naøy raát khoù ñaït ñöôïc. Theo lyù thuyeát thoáng keâ, thì ñaây thöïc chaát laø caän döôùi (lower bound) cuûa phaân boá xaùc suaát. Thôøi gian bi quan (pressimistic time), kyù hieäu laø b, laø thôøi gian caàn ñeå xong hoaït ñoäng khi tieân haønh gaëp truïc traëc nhaát, töùc laø caän treân (upper bound) cuûa phaân boá xaùc suaát. Thôøi gian hôïp lyù nhaát (most likely time), kyù hieäu laø m, laø thôøi gian hieän thöïc nhaát, töùc laø coù xaùc suaát lôùn nhaát (ñænh cao nhaát cuûa SV ne t.vn Trang:15 haøm maät ñoä). Ba löôïng treân chöa ñuû ñeå xaùc ñònh phaân boá xaùc suaát cuûa thôøi gian hoaït ñoäng. Do ñoù chöa ñuû ñeå xaùc ñònh kyø voïng te töùc laø giaù trò trung bình theo xaùc suaát, vaø phöông sai 2 ñaëc tröng cho ñoä leäch khoûi te cuûa thôøi gian hoaït ñoäng. Moâ hình caàn hai gaûi thieát phuø hôïp thöïc teá sau ñaây. Giaû thieát 1. b - a, töùc laø ñoä daøi khoaûng maø thôøi gian hoaït ñoäng coù theå laáy, baèng 6 laàn ñoä leäch chuaån (standard deviasion), töùc laø ta coù phöông sai 2 2 )( 6 1        ab . (1.1) Ñieàu naøy ñuùng cho nhieàu bieán ngaãu nhieân hay gaëp. Giaû thieát 2. Phaân boá xaùc suaát cuûa moãi thôøi gian hoaït ñoäng ñeâøu laø phaân boá beta (beta distribution). Ta haõy nhaéc laïi vaøi kieán thöùc xaùc suaát. Moãi ñaïi löông ngaãu nhieân x coù hai haøm quan troïng nhaát. Haøm maät ñoä xaùc suaát (probability density fuction) f(x), a  x  b, vaø haøm phaân boá tích luyõ (cumulative distribution function) F(X), goïi laø haøm phaân boá. ÔÛ ñaây giaû thieát laø x chæ laáy giaù trò trong [a, b] . Ta coù caùc quan heä sau     X a b a dxxfXxPXF dxxf ,)(}{)( ,1)(     b a e b a e dxxfxx dxxxfX ,)()( ,)( 22 ôû ñaây xe laø kyø voïng vaø  2 laø phöông sai cuûa bieán ngaãu nhieân x, P {…} laø xaùc suaát cuûa bieán coá {…}. Moãi moät trong haøm maät ñoä hoaëc haøm phaân phoái ñaëc tröng hoaøn toaøn cho bieán ngaãu nhieân. Kyø voïng vaø phöông sai laø caùc ñaïi löôïng quan troïng. Ta cuõng noùi laø haøm maät ñoä (hoaëc haøm phaân boá), xaùc ñònh hoaøn toaøn phaân boá xaùc suaát. Phaân boá beta (beta distribution) laø moät trong caùc phaân boá xaùc suaát phoå bieán nhaát, xaùc ñònh bôûi haøm maät ñoä sau, neáu 0  x  1, 1111 )1( ),( 1 )1( )()( )( )(         xxBxxxf , (1.2) ôû ñaây ,  laø tham soá, (.) laø haøm ñaëc bieät gamma vaø B(., .) laø haøm ñaëc bieät beta, ñöôïc ñònh nghóa baèng tích phaân phuï thuoäc tham soá f(x)          1 0 11 0 1 )1(:),( :)( dtttB et t     =1, =2  =  =2, =2 SV ne t.vn Trang:16 ==1 m 1 x Hình 1.8 Neáu y laáy giaù trò treân [a, b] vaø coù phaân boá theo beta thì haøm maät ñoä nhaân ñöôïc töø (4.2) baèng ñoåi bieán y = a + (b - a)x. Chaúng haïn, haøm maät ñoä cuûa phaân boá beta coù daïng nhö H.1.8 vôùi   1,   1 vaø a = 0, b = 1. Phaân boá chuaån (normal distribution) laø phaân boá xaùc suaát phoå bieán nhaát, ñònh nghóa bôûi haøm maät ñoä sau. ,, 2 1 )( 2 2 2 )( 2    xexf x    ôû ñaây tham soá  chính laø kyø voïng vaø 2 chính laø phöông sai cuûa bieán ngaãu nhieân x coù phaân boá chuaån. Khi ñoù bieán    x z coù phaân boù laø phaân boâù chuaån vôùi kyø voïng 0, phöông sai laø 1. Haøm maät ñoä cuûa phaân boá chuaån coù daïng ôû H.1.9 Caùc bieán ngaãu nhieân x1, …, xn ñöôïc goïi laø ñoäc laäp (independent) neáu. P{x1  X1, …, xn  Xn} = P{x1  Xn}, Ñònh nghóa giôùi haïn trung taâm (centrer – limit thoerem) noùi raèng vôùi caùc ñieàu kieän khaù nheï, toång caùc bieán ngaãu nhieân ñoäc laäp luoân coù phaân boá chuaån (khoâng phuï thuoäc vaøo phaân boá cuûa töøng bieán ngaãu nhieân). Trôû laïi moâ hình ngaãu nhieân ñieàu haønh döï aùn. Ñeå tính kyø voïng te cuûa thôøi gian hoaït ñoäng, ngöôøi ta giaû thieát laø ñieåm giöõa 2 ba  chieám tyû troïng baèng nöûa ñieåm hôïp lyù nhaát m. Khi ñoù        )( 2 1 2 3 1 bamte (II.3) Thí duï V.1. Giaû söû döï aùn xaây nhaø ôû H.1.1 baây giôø coù caùc thôøi gian hoaït ñoäng laø ngaãu nhieân coù phaân boá beta thoaû hai giaû thieát treân vaø xaùc ñònh ñöôïc ba moác thôøi gian laïc quan, bi quan vaø hôïp lyù nhaát theo baûng1.3. Khi ñoù phöông sai f(x)  x Hình 1.9 SV ne t.vn Trang:17 vaø kyø voïng cuûa caùc thôøi gian hoaït ñoäng, tình theo coâng thöùc (4, 1) vaø (4, 3) ñöôïc ghi ôû hai coät cuoái. Hoaït ñoäng Thôøi gian laïc quan a Thôøi gian hôïp lyù nhaát m Thôøi gian bi quan b Kyø voïng te Phöông sai 2 (1, 2) (2, 3) (3, 4) (4, 5) (4, 6) (4, 7) (5, 7) (6, 8) (7, 9) (8, 10) (9, 11) (9, 12) (10, 13) (12, 13) 1 2 6 1 4 3 4 5 3 5 4 1 1 5 2 2 1 3 9 2 1 4 2 1 5 2 1 7 4 2 1 6 9 8 4 2 1 5 2 2 1 5 3 8 18 5 10 9 10 11 9 17 4 7 3 9 2 4 10 4 6 7 5 7 8 9 4 5 2 6 9 1 1 4 9 4 1 1 1 1 1 4 0 4 9 1 9 4 Baûng 1.3 Nhaän xeùt raèng coät kyø voïng ôû Baûng1.3, do thí duï ñöôïc xaây döïng ñaëc bieät, truøng hoaøn toaøn vôùi caùc thôøi gian hoaït ñoäng trong moâ hình taát ñònh ñaõ xeùt ôû H.1. Do ñoù ñöôøng gaêng xaây döïng treân caùc thôøi gian hoaït ñoäng kyø voïng truøng vôùi ñöôøng gaêng cuûa moâ hình taát ñònh ôû H.1.2 vaø thôøi gian cuûa ñöôøng gaêng naøy laø 44. Tuy nhieân ñeå xaùc ñònh kyø voïng vaø phöông sai cuûa thôøi gian döï aùn, ta caàn theâm hai giaû thieát sau. Giaû thieát 3. Caùc thôøi gian hoaït ñoäng laø caùc bieán ngaãu nhieân ñoäc laäp. SV ne t.vn Trang:18 Giaû thieát 4. Ñöôøng gaêng xaây döïng treân caùc thôøi gian hoaït ñoäng kyø voïng, luoân ñoøi hoûi thôøi gian (hoaøn thaønh moïi hoaït ñoäng treân noù) lôùn hôn caùc ñöôøng khaùc. Tính thaät chi ly trong caùc thí duï cuï theå thì hai giaû thieát 3 vaø 4 coù theå khoâng ñuùng. Chaúng haïn, ôû Thí duï V.1, neáu saûy ra thôøi gian bi quan ôû moïi hoaït ñoäng thì ñöôøng gaêng ñaõ tính laø 69 (ngaøy). Coøn ñöôøng 1 –> 2 –> 3 –> 4 –> 5 –> 7 –> 9 –> 12 –> 13 coù thôøi gian bi quan laø 70. Tuy vaäy ngöôøi ta vaãn chaáp nhaän caùc giaû thuyeát xaáp xæ naøy. Khi ñoù, vì kyø voïng vaø phöông sai cuûa toång caùc bieán ngaãu nhieân laø toång cuûa caùc kyø voïng vaø phöông sai neân ta coù: Kyø voïng vaø phöông sai cuûa thôøi gian döï aùn laø toång caùc kyø voïng vaø phöông sai cuûa caùc thôøi gian hoaït ñoäng treân ñöôøng gaêng (xaây döïng theo caùc kyø voïng). Ñeán ñaây ta nhaän xeùt raèng moät trong caùc caùch aùp duïng thöïc teá laø duøng caùc kyø voïng cuûa caùc bieán, roài aùp duïng moïi tính toaùn vaø lyù luaän ôû caùc muïc tröôùc vaøo caùc kyø voïng, thay cho caùc bieán taát ñònh. ÔÛ Thí duï V.1 kyø voïng vaø phöông sai cuûa thôøi gian döï aùn laø 44 vaø 9, vì ñöôøng gaêng laø 1 –> 2 –> 3 –> 4 –> 5 –> 7 –> 9 –> 12 –> 13 . Baây giôø ta xeùt vaán ñeà quan troïng laø tính xaùc suaát ñeå döï aùn hoaøn thaønh tröôùc moät thôøi haïn baét buoäc (deadline). Theo ñònh lyù giôùi haïn trung taâm, thôøi gian döï aùn laø bieán ngaãu nhieân coù phaân boá chuaån. Do ñoù ta tính ñöôïc xaùc suaát P(x  X), thöôøng ñöôïc tính saün ñeå tra theo baûng. Chaúng haïn Baûng A1 ôû cuoái saùch cho bieát P {x  xe + K}, ôû ñaây  laø ñoä leäch chuaån. Do ñoù K laø ñôn vò leäch chuaån. Thí duï, haõy tính xaùc suaát ñeå thôøi gian xaây nhaø ôû Thí duï V.1 khoâng quaù 47 ngaøy. Ta thaáy 47 = 44 + 3.1 = xe + K neân K = 1. Theo baûng thì P {x  47} = 0,1584. Do ñoù xaùc suaát caàn tìm laø  1 – 0,1584  0,84. Phöông phaùp ñieàu haønh döï aùn coù tính ngaãu nhieân treân ñaây thöôøng ñöôïc goïi laø phöông phaùp ba öôùc löôïng PERT (PERT three estimate method). Neáu caàn tính caùc yeáu toá thôøi gian ôû caùc bieán coá trung gian (khoâng chæ thôøi gian hoaøn thaønh döï aùn, töùc laø bieán coá cuoái) thì ta lyù luaän nhö sau. Tröôùc heát tính kyø voïng vaø phöông sai cuûa thôøi ñieåm sôùm i cuûa bieán coá i. Neáu chæ coù moät ñöôøng töø khôûi coâng ñeán i thì, do caùc hoaït ñoäng laø ñoäc laäp kyø voïng cuûa i kyù hieäu laø E(i), baèng toång caùc kyø voïng te cuûa thôøi gian caùc hoaït ñoäng daãn ñeán i. Khi coù nhieàu ñöôøng daãn ñeán i thì ngöôøi ta coi xaáp xæ (ñeå ñôn giaûn) E(i) vaø Var(i) laø toång caùc te vaø  2 cuûa caùc hoaït ñoäng theo ñöôøng ñeán i coù toång E(i) daøi nhaát. Neáu coù nhieàu ñöôøng vôùi cuøng E(i) thì Var(i) quy öôùc laáy löôïng cuûa ñöôøng coù toång caùc 2 daùi nhaát. Baây giôø haõy tính xaùc suaát ñeå bieán coá i xong tröôùc thôøi gian baét buoäc Ti cho tröôùc. Theo ñònh lyù giôùi haïn trung taâm i tuaân theo phaân boá chuaån, ta chæ vieäc tra baûng caùc xaùc suaát öùng vôùi phaân boá chuaån ñeå tính P{i  Ti}. Cuï theå, ñeå tra baûng, quy veà tröôøng hôïp ñaïi löông z coù phaân boá chuaån vôùi kyø voïng 0 vaø phöông sai 1 nhö sau: SV ne t.vn Trang:19   }{: )( )( )( )( i i ii i ii ii KzP Var ET Var E PTP                  , ôû ñaây )( )( i ii i Var ET K    ñaõ bieát. VI. Döï aùn coù thoaû hieäp thôøi gian – Cöôùc phí. Trong caùc muïc tröôùc ta trình baøy veà caùc döïa aùn coù yeâu caàu chuû yeáu laø ñieàu haønh thôøi gian. Theo ngoân ngöõ ban ñaàu thì ñaây laø phöông phaùp PERT, caùc thôøi gian ôû ñaây coù theå xeùt nhö caùc bieán taát ñònh hoaëc ngaãu nhieân. Coøn phöông phaùp ñöôøng gaêng PCM thì ñaët ngang nhau veà thôøi gian vaø cöôùc phí. Muïc tieâu chính cuûa PCM laø choïn caùch thoaû hieäp thôøi gian thöïc hieän moãi hoaït ñoäng (theo ngoân ngöõ hình hoïc) töùc laø bieát ñöôøng cong thôøi gian – cöôùc phí (time – cost curve) cuûa moãi hoaït ñoäng. Trong moâ hình toaùn hoïc (xaáp xæ thoâ tình traïng thöïc teá) ngöôøi ta giaû thieát quan heä thôøi gian vaø cöôùc phiù laø tuyeán tính. Do ñoù chæ caàn bieát hai ñieåm. Ngöôøi ta choïn hai ñieån nuùt nhö sau: Ñieåm chuaån (normal point) coù toaï ñoä laø thôøi gian vaø cöôùc phí cuûa hoaït ñoäng khi noù ñöôïc tieán haønh trong ñieàu kieän bình thöôøng, töùc laø chuaån, khoâng coù cöôùc phí boå xung taêng cöôøng (nhö laøm ngoaøi giôø, taêng thieát bò nhaân löïc …). Cöïc ñieåm (crash point) laø ñieåm öùng vôùi thôøi gian vaø cöôùc phí khi ñaàu tö heát möùc ñeå thôøi gian thöïc hieän hoaït ñoäng ngaén nhaát coù theå. Moïi ñieåm trung gian giöõa ñieåm chuaån vaø cöïc ñieåm, töùc laø moïi caùch thoaû hieäp thôøi gian cöôùc phí (time – cost trade - off) ñeàu coi laø chaáp nhaän ñöôïc, xem H.1.10. Hình 1.10 Ñöôøng cong thôøi gian – cöôùc phí cuûa hoaït ñoäng (i, j). Caùc kyù hieäu treân H.1.10 roõ raøng nhö sau. Dij laø dij laø thôøi gian chuaån vaø thôøi gian cöïc ñieåm. CDij vaø Cdij laø cöôùc phí chuaån (normal cost) vaø cöôùc phí cöïc ñieåm (crash cost), ñeàu cuûa hoaït ñoäng (i, j). Goïi xij (thôøi gian thöïc hieän hoaït ñoäng (i, j)) laø bieán quyeát ñònh (decision variable) cuûa baøi toaùn maø ta caàn tính. Goïi Sij laø ñoä xieân, töùc laø heä soá goùc ñöôøng thaúng bieåu thò ñöôøng cong thôøi gian – cöôùc phí , töùc laø: C ö ô ùc p h í tr ö ïc t ie áp Kij Cdij Cöïc ñieåm Ñieåm chuaån Thôøi gian Cxij CDij dij xij Dij SV ne t.vn Trang:20 ijij dD ij dD CC S ijij    . Goïi Kij laø tung ñoä ñieåm ñöôøng thaúng caét truïc tung. Khi ñoù cöôùc phí cuûa hoaït ñoäng (i, j) töông öùng vôùi thôøi gian hoaït ñoäng (i, j) öùng vôùi thôøi gian hoaït ñoäng xij roõ raøng laø: Baøi toaùn: Choïn caùc xij ñeå thôøi gian döï aùn khoâng quaù thôøi haïn baét buoäc T cho tröôùc vaø laøm cöïc tieåu cöôùc phí döï aùn C. Nhaän xeùt raèng caùc yeáu toá cuûa baøi toaùn ñeàu laø tuyeán tính, ta coá gaéng ñöa veà quy hoaïch tuyeán tính nhö sau: Ñöa vaøo caùc bieán boå xung yk laø thôøi ñieåm sôùm Ek cuûa bieán coá k. Khi ñoù quan heä giöõa caùc bieán theo Muïc 4.2 laø   jkjk tEE  j max , (1, 4) ôû ñaây max laáy theo caùc bieán coá j ngay tröôùc k, töùc laø coù hoaït ñoäng noái (j, k). Kyù hieäu yk = Ek, tjk = xjk vaø vieát laïi (4, 4) ta ñöôïc yi + xjk – yk  0 (soá raøng buoäc laø soá caùc bieán coá ngay tröôùc k). Goïi 1 laø nuùt xuaát phaùt vaø n laø nuùt keát thuùc döï aùn thì y1 = 0, yn T. ÔÛ muïc tieâu thì Kij laø haèng. Toùm laïi ta ñöôïc quy hoaïch tuyeán tính .,0 0 , ,min 1 ),( Tyy yxy Dxd xS n ijiji ijijij ji ijij     Ñeå ñöa veà quy hoaïch tuyeán tính daïng chuaån ta laøm nhö sau. Ñoåi bieán xij = dij + x ’ ij thì raøng buoäc xij  dij trôû thaønh raøng buoäc daáu x ’ ij  0. Theâm raøng buoäc hình thöùc yi  0, i. Raøng buoäc naøy töï nhieân thoaû do y1 = 0 vaø yj  yi + dij + X ’ ij. Tröôøng hôïp khoâng coù thôøi haïn baét buoäc T cho tröôùc, töùc laø caàn tìm thoaû hieäp toát nhaát giöõa toång cöôùc phí vaø toång thôøi gian döï aùn, ngöôøi ta coi T laø tham soá vaø giaûi quy hoaïch tuyeán tính tham soá ñeå ñöôïc nghieäm toái öu nhö haøm cuûa T. VII. Kieåm tra hieäu chænh döï aùn. Sau khi duøng phöông phaùp ñieàu haønh döï aùn PERT – CPM xaùc ñònh ñöôïc sô ñoà maïng löôùi, caùc bieåu ñoà vaø baûng tính caùc chæ tieâu vaø döï aùn ñang ñöôïc tieán haønh, ngöôøi quaûn lyù luoân phaûi theo doõi, kieåm tra. Ñieàu kieän lao ñoäng thöïc teá coù theå nhieàu baát ngôø. Khi caàn thieát coù theå phaûi duøng phöông phaùp PERT – CPM laïi, döïa treân caùc döõ lieäu môùi, ñeå tính toaùn cho phaàn coøn lai cuûa döï aùn. Sau ñoù ñieàu haønh döï aùn theo caùc bieåu ñoà vaø baûng tính môùi. SV ne t.vn Trang:21 CHÖÔNG 2 CÔ SÔÛ VEÀ LYÙ THUYEÁT ÑOÀ THÒ I. Moät soá khaùi nieäm cô baûn. Lyù thuyeát ñoä thò laø moät lónh vöïc nghieân cöùu ñaõ coù töø laâu vaø coù nhieàu öùng duïng hieän ñaïi. Nhöõng tö töôûng cô baûn cuûa lyù thuyeát ñoà thò ñöôïc ñeà xuaát vaøo nhöõng naêm ñaàu cuûa theá kyû 18 bôûi nhaø toaùn hoïc loãi laïc ngöôøi Thuïy Syõ Euler. Chính oâng laø ngöôøi söû duïng ñoà thò ñeå giaûi baøi toaùn noåi tieáng veà caùi caàu ôû thaønh phoá Konigsberg. Ñoà thò ñöôïc söû duïng ñeå giaûi caùc baøi toaùn trong nhieàu lónh vöïc khaùc nhau. Chaúng haïn, ñoà thò coù theå söû duïng ñeå xaùc ñònh caùc maïch voøng trong vaán ñeà giaûi tích maïch ñieän. Chuùng ta coù theå phaân bieät caùc hôïp chaát hoùa hoïc höõu cô khaùc nhau vôùi cuøng coâng thöùc phaân töû nhöng khaùc nhau veà caáu truùc phaân töû nhôø ñoà thò. Chuùng ta coù theå xaùc ñònh xem hai maùy tính trong maïng coù theå trao ñoåi thoâng tin ñöôïc vôùi nhau khoâng nhôø moâ hình ñoà thò cuûa maïng maùy tính. Ñoà thò coù troïng soá treân caùc caïnh coù theå söû duïng ñeå giaûi baøi toaùn nhö: Tìm ñöôøng ñi ngaén nhaát giöõa hai thaønh phoá trong moät maïng giao thoâng. Chuùng ta coøn söû duïng ñoà thò ñeå giaûi caùc baøi toaùn veà laäp lòch, thôøi khoùa bieåu, vaø phaân boá taàn soá cho caùc traïm phaùt thanh vaø truyeàn hình… 1.1. Ñònh nghóa ñoà thò. Ñoà thò laø moät caáu truùc rôøi raïc bao goàm caùc ñænh vaø caùc caïnh noái caùc ñænh naøy. Chuùng ta phaân bieät caùc loaïi ñoà thò khaùc nhau bôûi kieåu vaø soá löôïng caïnh noái hai ñænh naøo ñoù cuûa ñoà thò. Ñeå coù theå hình dung ñöôïc taïi sao laïi caàn ñeán caùc loaïi ñoà thò khaùc nhau, chuùng ta seõ neâu ví duï söû duïng chuùng ñeå moâ taû moät maïng maùy tính. Giaû söû ta coù moät maïng goàm caùc maùy tính vaø caùc keânh ñieän thoaïi (goïi taét laø keânh thoaïi) noái caùc maùy tính naøy. Ñònh nghóa 1: Ñôn ñoà thò voâ höôùng G = (V,E) bao goàm V laø taäp hôïp caùc ñænh vaø E laø taäp hôïp caùc caëp khoâng coù thöù töï goàm hai phaàn töû khaùc nhau cuûa V goïi laø caùc caïnh. Trong tröôøng hôïp giöõa hai maùy tính naøo ñoù thöôøng xuyeân phaûi truyeàn taûi nhieàu thoâng tin ngöôøi ta phaûi noái hai maùy tính naøy bôûi nhieàu keânh thoaïi. Ñònh nghóa 2: Ña ñoà thò voâ höôùng G = (V,E) bao goàm laø taäp caùc ñænh, vaø E laø hoï caùc caëp khoâng coù thöù töï goàm hai phaàn töû khaùc nhau cuûa V goïi laø caùc caïnh. Hai caïnh e1 vaø e2 ñöôïc goïi laø caïnh laëp neáu chuùng cuøng töông öùng vôùi moät caëp ñænh. Roõ raøng moãi ñôn ñoà thò ñeàu laø ña ñoà thò, nhöng khoâng phaûi ña ñoà thò naøo cuõng laø ñôn ñoà thò, vì ña ñoà thò coù theå coù 2 (hoaëc nhieàu hôn) caïnh noái moät caëp ñænh naøo ñoù. SV ne t.vn Trang:22 Trong maïng maùy tính coù theå coù nhöõng keânh thoaïi noái moät maùy naøo ñoù vôùi chính noù (chaúng haïn vôùi muïc ñích thoâng baùo). Maïng nhö vaäy ñöôïc cho trong hình 3. Khi ñoù ña ñoà thò khoâng theå moâ taû ñöôïc maïng nhö vaäy, bôûi vì coù nhöõng khuyeân (caïnh noái moät ñænh vôùi chính noù ). Trong tröôøng hôïp naøy chuùng ta caàn söû duïng ñeán caùc khaùi nieäm giaû ñoà thò voâ höôùng, ñöôïc ñònh nghóa nhö sau: Ñònh nghóa 3: Giaû ñoà thò voâ höôùng G = (V,E) bao goàm V laø taäp caùc ñænh, vaø E laø hoï caùc caëp khoâng coù thöù töï goàm hai phaàn töû (khoâng nhaát thieát phaûi khaùc nhau) cuûa V goïi laø caùc caïnh. Caïnh e ñöôïc goïi laø khuyeân neáu coù daïng e = (u,u). Ñònh nghóa 4: Ñôn ñoà thò coù höôùng G =(V,E) bao goàm V laø taäp caùc ñænh, vaø E laø taäp caùc caëp coù thöù töï goàm hai phaàn töû khaùc nhau cuûa V goïi laø caùc cung. Neáu trong maïng coù theå coù ña keânh thoaïi moät chieàu, ta phaûi söû duïng ñeán khaùi nieäm ña ñoà thò coù höôùng: Ñònh nghóa 5: Ña ñoà thò coù höôùng G= (V,E) bao goàm V laø taäp caùc ñænh, vaø E laø hoï caùc caëp coù thöù töï goàm hai phaàn töû khaùc nhau cuûa V goïi laø caùc cung. Hai cung e1 vaø e2 töông öùng vôùi cuøng moät caëp ñænh ñöôïc goïi laø cung laëp. Chuùng ta chuû yeáu seõ laøm vieäc vôùi ñôn ñoà thò voâ höôùng vaø ñôn ñoà thò coù höôùng. 1.2. Caùc thuaät ngöõ cô baûn. Tröôùc tieân ta xeùt thuaät ngöõ moâ taû caùc ñænh vaø caùc caïnh cuûa ñoà thò voâ höôùng. Ñònh nghóa 1: Hai ñænh u vaø v cuûa ñoà thò voâ höôùng G ñöôïc goïi laø keà nhau neáu (u,v) laø caïnh cuûa ñoà thò G. Neáu e = (u,v) laø caïnh cuûa ñoà thò thì ta noùi caïnh naøy laø lieân thuoäc vôùi hai ñænh u vaø v, hoaëc cuõng noùi laø caïnh e laø noái ñænh u vaø ñænh v, ñoàng thôøi caùc ñænh u vaø v seõ ñöôïc goïi laø caùc ñænh ñaàu cuûa caïnh (u,v). Ñeå coù theå bieát bao nhieâu caïnh lieân thuoäc vôùi moät ñænh, ta ñöa vaøo ñònh nghóa sau: Ñònh nghóa 2: Ta goïi baäc cuûa ñænh v trong ñoà thò voâ höôùng laø soá caïnh lieân thuoäc vôùi noù vaø seõ kí hieäu laø deg(v). b c d a f e g Hình 1: Ñoà thò voâ höôùng G. Thí duï 1: Xeùt ñoà thò trong hình 1, ta coù: deg(a)= 1, deg(b)=4, deg(c)=4, deg(f)=3, deg(d)=1, deg(e)=3, deg(g)=0. SV ne t.vn Trang:23 Ñænh baäc 0 goïi laø ñænh coâ laäp. Ñænh baäc 1 goïi laø ñænh treo. Trong thí duï treân ñænh g laø ñænh coâ laäp, a vaø d laø caùc ñænh treo. Baäc cuûa ñænh coù tính chaát sau:    Vv vm )deg(2 Ñònh lyù 1: Giaû söû G = (V,E) laø ñoà thò voâ höôùng vôùi m caïnh. Khi ñoù. Chöùng minh. Roõ raøng moãi caïnh e = (u,v) ñöôïc tính moät laàn trong deg(u) vaø moät laàn trong deg(v). Töø ñoù suy ra toång taát caû caùc baäc cuûa caùc ñænh baèng hai laàn soá caïnh. Thí duï 2: Ñoà thò vôùi n ñænh vaø moãi ñænh coù baäc laø 6 coù bao nhieâu caïnh?. Giaûi: Theo ñònh lyù 1, ta coù 2m = 6n. Töø ñoù suy ra soá caïnh cuûa ñoà thò laø 3n. Heä quaû: Trong ñoà thò voâ höôùng, soá ñænh baäc leû (nghóa laø coù baäc laø soá leû) laø moät soá chaün.    Vv Ov Uv vvvm    )deg()deg()deg(2 Chöùng minh: Thöïc vaäy goïi O vaø U töông öùng laø taäp ñænh baäc leû vaø taäp ñænh baäc chaün cuûa ñoà thò. Ta coù: Do deg(v) laø chaün vôùi v laø ñænh trong U neân toång thöù hai trong veá phaûi ôû treân laø soá chaün. Töø ñoù suy ra toång thöù nhaát (chính laø toång baäc cuûa caùc ñænh baäc leû) cuõng phaûi laø soá chaün, do taát caû caùc soá haïng cuûa noù laø soá leû, neân toång naøy phaûi goàm moät soá chaün caùc soá haïng. Vì vaäy, soá ñænh baäc leû phaûi laø soá chaün. Ta xeùt caùc thuaät ngöõ töông töï cho ñoà thò coù höôùng. Ñònh nghiaõ 3: Neáu e = (u, v) laø cung cuûa ñoà thò coù höôùng G thì ta noái hai ñænh u vaø v laø keà nhau, vaø noùi cung (u,v) noái ñænh u vôùi ñænh v hoaëc cuõng noùi cung naøy laø ñi ra khoûi ñænh u vaø ñi vaøo ñænh v. Ñænh u(v) seõ ñöôïc goïi laø ñænh ñaàu (cuoái) cuûa cung (u, v). Töông töï nhö khaùi nieäm baäc, ñoái vôùi ñoà thò coù höôùng ta coù khaùi nieäm baùn baäc ra (vaøo) cuûa moät ñænh. Ñònh nghóa 4: Ta goïi baùn baäc ra (baùn baäc vaøo) cuûa caùc ñænh v trong ñoà thò coù höôùng laø soá cung cuûa ñoà thò ñi ra khoûi noù (ñi vaøo noù) vaø kyù hieäu laø deg + (v) (deg(v)). Ñònh lyù 2: Giaû söû G = (V,E) laø ñoà thò coù höôùng. Khi ñoù Evv VvVv      )(deg)(deg Raát nhieàu tính chaát cuûa ñoà thò coù höôùng khoâng phuï thuoäc vaøo höôùng treân caùc cung cuûa noù. Vì vaäy, trong nhieàu tröôøng hôïp seõ thuaän tieän hôn neáu ta boû qua höôùng treân caùc cung cuûa ñoà thò. Ñoà thò voâ höôùng thu ñöôïc baèng caùch boû qua höôùng treân caùc cung ñöôïc goïi laø ñoà thò voâ höôùng töông öùng vôùi doà thò coù höôùng ñaõ cho. 1.3. Ñöôøng ñi, chu trình, ñoà thò lieân thoâng. Ñònh nghóa 1: Ñöôøng ñi ñoä daøi n töø ñænh u ñeán ñænh v, trong ñoù n laø soá nguyeân döông, treân ñoà thò voâ höôùng G =(V,E) laø daõy x0, x1, … ,xn-1,xn trong ñoù u SV ne t.vn Trang:24 =x0, v=xn , (xi, xi+1)  E, i= 0, 1, 2… , n-1. Ñöôøng ñi noùi treân coøn coù theå bieåu dieãn döôùi daïng daõy caùc caïnh: (x0, x1), (x1, x2), …, (xn-1, xn). Ñænh u goïi laø ñænh ñaàu coøn ñænh v goïi laø ñænh cuoái cuûa ñöôøng ñi. Ñöôøng ñi coù ñænh ñaàøu truøng vôùi ñænh cuoái (töùc laø u= v) ñöôïc goïi laø chu trình. Ñöôøng ñi hay chu trình ñöôïc goïi laø ñôn neáu nhö khoâng coù caïnh naøo bò laëp laïi. Ñònh nghóa 2: Ñöôøng ñi ñoä daøi n töø ñænh u ñeán ñænh v trong ñoù n laø soá nguyeân döông, treân ñoà thò voâ höôùng G =(V, A) laø daõy x0, x1, … ,xn-1,xn trong ñoù u =x0, v=xn , (xi, xi+1) A, i= 0, 1, 2… , n-1. Ñöôøng ñi noùi treân coøn coù theå bieåu dieãn döôùi daïng daõy caùc cung: (x0, x1), (x1, x2), …, (xn-1, xn). Ñænh u goïi laø ñænh ñaàu coøn ñænh v goïi laø ñænh cuoái cuûa ñöôøng ñi. Ñöôøng ñi coù ñænh ñaàøu truøng vôùi ñænh cuoái (töùc laø u= v) ñöôïc goïi laø chu trình. Ñöôøng ñi hay chu trình ñöôïc goïi laø ñôn neáu nhö khoâng coù cung naøo bò laëp laïi. Ñònh nghóa 3: Ñoà thò voâ höôùng G= (V,E) ñöôïc goïi laø lieân thoâng neáu luoân tìm ñöôïc ñöôøng ñi giöõa hai ñænh baát kyø cuûa noù. Nhö vaäy hai maùy tính baáy kyø trong maïng coù theå trao ñoåi thoâng tin ñöôïc vôùi nhau khi vaø chæ khi ñoà thò töông öùng vôi maïng naøy laø ñoà thò lieân thoâng. Ñònh nghóa 4: Ta goïi ñoà thò con cuûa ñoà thò G= (V,E) laø ñoà thò H = (W,F) trong ñoù W  V vaø FE. Trong tröôøng hôïp ñoà thò laø lieân thoâng, noù seõ raõ ra thaønh moät soá ñoà thò con lieân thoâng ñoâi moät khoâng coù ñænh chung. Nhöõng ñoà thò con lieân thoâng nhö vaäy ta seõ goïi laø caùc thaønh phaàn lieân thoâng cuûa ñoà thò. Ñònh nghóa 5: Ñænh v ñöôïc goïi laø ñænh reõ nhaùnh neáu vieäc loaïi boû v cuøng vôùi caùc caïnh lieân thuoäc vôùi noù khoûi ñoà thò laøm taêng soá thaønh phaàn lieân thoâng cuûa ñoà thò. Caïnh e ñöôïc goïi laø caàu neáu vieäc loaïi boû noù khoûi ñoà thò laøm taêng soá thaønh phaàn lieân thoâng cuûa ñoà thò. Ñònh nghóa 6: Ñoà thò coù höôùng G= (V,A) ñöôïc goïi laø lieân thoâng maïnh neáu luoân tìm ñöôïc ñöôøng ñi giöõa hai ñænh baát kyø cuûa noù. Ñònh nghóa 7: Ñoà thò coù höôùng G =(V,A) ñöôïc goïi laø lieân thoâng yeáu neáu ñoà thò voâ höôùng töông öùng vôùi noù laø ñoà thò voâ höôùng lieân thoâng. Roõ raøng neáu ñoà thò laø lieân thoâng maïnh thì noù cuõng laø lieân thoâng yeáu, nhöng ñieàu ngöôïc laïi laø khoâng luoân ñuùng. Ñònh lyù1: Ñoà thò voâ höôùng lieân thoâng laø ñònh höôùng ñöôïc khi vaø chæ khi moãi caïnh cuûa noù naèm treân ít nhaát moät chu trình. Chöùng minh: Ñieàu kieän caàn, giaû söû (u, v) laø moät caïnh cuûa ñoà thò. Söï toàn taïi ñöôøng ñi coù höôùng töø u ñeán v vaø ngöôïc laïi suy ra (u, v) phaûi naèm treân ít nhaát moät chu trình. Ñieàu kieän ñuû, thuû tuïc sau ñaây cho pheùp ñònh höôùng caùc caïnh cuûa ñoà thi ñeå thu ñöôïc ñoà thò coù höôùng lieân thoâng maïnh. Giaû söû C laø chu trình naøo ñoù trong SV ne t.vn Trang:25 ñoà thò. Ñònh höôùng caùc caïnh treân chu trình naøy theo moät höôùng ñi voøng theo noù. Neáu taát caû caùc caïnh cuûa ñoà thò ñaõ ñöôïc ñònh höôùng thì keát thuùc thuû tuïc. Ngöôïc laïi choïn e laø caïnh chöa ñònh höôùng coù chung ñænh vôùi ít nhaát moät trong soá caùc caïnh ñaõ ñònh höôùng. Theo giaû thieát tìm ñöïôc chu trình C’ chöùa caïnh e ñònh nghóa caùc caïnh chöa ñònh höôùng cuûa C ’ theo moät höôùng doïc theo chu trình naøy (khoâng ñònh höôùng laïi caùc caïnh ñaõ coù höôùng). Thuû tuïc treân seõ laëp laïi cho ñeán khi taát caû caùc caïnh cuûa ñoà thò ñöôïc ñònh höôùng. Khi ñoù ta thu ñöôïc ñoà thò coù höôùng lieân thoâng maïnh. II. Bieåu dieãn ñoà thò treân maùy tính. Ñeå löu tröõ ñoà thò vaø thöïc hieän caùc thuaät toaùn khaùc nhau vôùi ñoà thò treân maùy tính caàn phaûi tìm nhöõng caáu truùc döõ lieäu thích hôïp ñeå moâ taû ñoà thò. Vieäc choïn caáu truùc döõ lieäu naøo ñeå bieåu dieãn ñoà thò coù taùc ñoäng raát lôùn ñeán hieäu quaû cuûa thuaät toaùn. Vì vaäy, vieäc choïn löïa caáu truùc döõ lieäu ñeå bieåu dieãn ñoà thò phuï thuoäc vaøo töøng tình huoáng cuï theå (baøi toaùn vaø thuaät toaùn cuï theå ). ÔÛ phaàn naøy ta seõ xeùt moät soá phöông phaùp cô baûn ñeå bieåu dieãn ñoà thò treân maùy tính, ñoàng thôøi cuõng phaân tích moät caùch ngaén goïn nhöõng öu ñieåm cuõng nhö nhöõng nhöôïc ñieåm cuûa chuùng. 2.1. Ma traän keà, Ma traän troïng soá. Xeùt ñôn ñoà thò voâ höôùng G = (V,E), vôùi taàp ñænh V= {1, 2, …,n} taäp caïnh E = {e1, e2,…, em}. Ta goïi ma traän keà cuûa ñoà thò G laø (0, 1) ma traän A = {aij: i,j = 1, 2,… ,n}vôùi caùc phaàn töû ñöôïc xaùc ñònh theo quy taéc sau ñaây: aij =0 neáu (i,j)  E vaø aij =1 neáu (i,j) E, i,j =1, 2,…,n Thí duï1: Ma traän keà cuûae ñoà thò voâ höôùng cho trong hình 1 laø: 1 2 3 4 5 6 1 2 3 4 5 6 3 4 2 5 1 6 1 4 2 5 3 6 G G1 0 1 1 0 0 0 1 0 1 0 1 0 1 1 0 1 0 0 0 0 1 0 1 1 0 1 0 1 0 1 0 0 0 1 1 0 SV ne t.vn Trang:26 Hình 1: Ñoà thò voâ höôùng G vaø Ñoà thò coù höôùng G1 Caùc tính chaát cuûa ma traän keà: 1. Roõ raøng ma traän keà cuûa ñoà thò voâ höôùng laø ma traän ñoái xöùng, töùc laø a[i, j]= a[j, i], i, j = 1, 2,…,n. Ngöôïc laïi, moãi (0, 1) – ma traän ñoái xöùng caáp n seõ töông öùng chính xaùc ñeán caùch ñaùnh soá ñænh (coøn noùi laø: chính xaùc ñeán ñaúng caáu), vôùi moät ñôn ñoà thò voâ höôùng n ñænh. 2. Toång caùc phaàn töû treân doøng i (coät j) cuûa ma traän keà chính baèng baäc cuûa ñænh i (ñænh j). 3. Neáu kyù hieäu aij p, i,j = 1, 2,…, n. Laø caùc phaàn töû cuûa ma traän Ap = A.A….A. p laø thöøa soá, khi ñoù aij p, i,j = 1, 2,…, n. cho ta soá ñöôøng ñi khaùc nhau töø ñænh i ñeán ñænh j qua p –1 ñænh trung gian. Ma traän keà cuûa ñoà thò coù höôùng ñöôïc ñònh nghóa moät caùch hoaøn toaøn töông töï. Thí duï 2: Ñoà thò coù höôùng G1 cho trong hình 1 coù ma traän keà laø ma traän sau. 1 2 3 4 5 6 1 2 3 4 5 6 Löu yù raèng ma traän keà cuûa ñoà thò coù höôùng khoâng phaûi laø ma traän ñoái xöùng. Chuù yù: Treân ñaây chuùng ta chæ xeùt ñôn ñoà thò. Ma traän keà cuûa ña ñoà thò coù theå xaây döïng hoaøn toaøn töông töï, chæ khaùc, laø thay vì ghi 1 vaøo vò trí a[i, j] neáu (i, j) laø caïnh cuûa ñoà thò, chuùng ta seõ ghi k laø soá caïnh noái hai ñænh i vaø j. Trong raát nheàu vaán ñeà öùng duïng cuûa lyù thuyeát ñoà thò, moãi caïnh e= (u, v) cuûa ñoà thò ñöôïc gaùn vôùi moät con soá c(e) (coøn vieát laø c (u, v)) goïi laø troïng soá cuûa caïnh e. Ñoà thò trong tröôøng hôïp nhö vaäy ñöôïc goïi laø ñoà thò troïng soá. Trong ñoà thò coù troïng soá, thay vì ma traän keà, ñeå bieåu dieãn ñoà thò ta duøng ma traän troïng soá. C = c[i,j], i,j=1,2,…,n. Vôùi c(i, j)= c[i, j], neáu (i, j)  E vaø c[i, j] = neáu (i, j)  E Trong ñoù soá , tuøy töøng tröôøng hôïp cuï theå, coù theå ñöôïc ñaët baèng moät trong caùc giaù trò sau: 0, +, -. 0 1 1 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 1 0 SV ne t.vn Trang:27 Öu ñieåm lôùn nhaát cuûa phöông phaùp bieåu dieãn ñoà thò baèng ma traän keà (hoaëc baèng ma traän troïng soá) laø ñeå traû lôøi caâu hoûi: hai ñænh u, v coù keà nhau treân ñoà thò hay khoâng, chuùng ta chæ phaûi thöïc hieän moät pheùp so saùnh. Nhöôïc ñieåm lôùn nhaát cuûa phöông phaùp naøy laø khoâng phuï thuoäc vaøo soá caïnh cuûa ñoà thò, ta luoân phaûi söû duïng n 2 ñôn vò boä nhôù ñeå löu tröõ ma traän keà cuûa noù. 2.2. Danh saùch caïnh (cung). Trong tröôøng hôïp ñoà thò thöa (ñoà thò coù soá caïnh m thoûa maõn baát ñaúng thöùc m < 6n) ngöôøi ta thöôøng duøng caùch bieåu dieãn ñoà thò döôùi daïng danh saùch caïnh. Trong caùch bieåu dieãn ñoà thò bôûi danh saùch caïnh (cung) chuùng ta seõ löu tröõ danh saùch taát caû caùc caïnh (cung) cuûa ñoà thò voâ höôùng (coù höôùng). Moãi caïnh (cung) e = (x, y) cuûa ñoà thò seõ töông öùng vôùi hai bieán Dau[e], Cuoi[e]. Nhö vaäy, ñeå löu tröõ ñoà thò ta caàn söû duïng 2m ñôn vò boä nhôù. Nhöôïc ñieåm cuûa caùch bieåu dieãn naøy laø ñeå xaùc ñònh nhöõng ñænh naøo cuûa ñoà thò laø keà vôùi moät ñænh cho tröôùc chuùng ta phaûi laøm côõ m pheùp so saùnh (khi duyeät qua danh saùch taát caû caùc caïch cuûa ñoà thò). Chuù yù: trong tröôøng hôïp ñoà thò coù troïng soá ta caàn theâm m ñôn vò boä nhôù ñeå löu tröõ troïng soá cuûa caùc caïch. 2.3. Danh saùch keà. Trong raát nhieàu vaán ñeà öùng duïng cuûa lyù thuyeát ñoà thò, caùch bieåu dieãn ñoà thò döôùi daïng danh saùch keà laø caùch bieåu dieãn thích hôïp nhaát ñöôïc söû duïng. Trong caùch bieåu dieãn naøy, vôùi moãi ñænh v cuûa ñoà thò chuùng ta löu tröõ danh saùch caùc ñænh keà vôùi noù, maø ta seõ kyù hieäu laø Ke(v), töùc laø Ke(v)={uV: (v, u)  E} khi ñoù voøng laëp thöïc hieän vôùi moãi moät phaàn töû trong danh saùch naøy theo thöù töï caùc phaàn töû ñöôïc xaép xeáp nhö sau: For u Ke(v) do… Chaúng haïn, treân PASCAL coù theå moâ taû danh saùch naøy nhö sau (Goïi laø caáu truùc Forward star ): Const m = 100; {m – soá caïnh} n = 100; {n – soá ñænh} var Ke: array {1..m} of integer ; Tro: array {1..n+1} of integer ; Trong ñoù Tro [i] ghi nhaän vò trí baét ñaàu cuûa danh saùch ke à cuûa ñænh i, i = 1, 2, …n, Tro[n+1] = 2m + 1. III. Baøi toaùn tìm ñöôøng ñi ngaén nhaát. Trong caùc öùng duïng thöïc teá, baøi toaùn tìm ñöôøng ñi ngaén nhaát giöõa hai ñænh cuûa ñoà thò lieân thoâng coù moät yù nghóa to lôùn, coù theå daãn veà baøi toaùn nhö vaäy SV ne t.vn Trang:28 nhieàu baøi toaùn thöïc teá quan troïng. Ví duï, baøi toaùn choïn moät haønh trình tieát kieäm nhaát (theo tieâu chuaån khoaûng caùch hoaëc thôøi gian hoaëc chi phí) treân moät maïng giao thoâng ñöôøng boä, ñöôøng thuûy hoaëc ñöôøng khoâng; baøi toaùn choïn moät phöông phaùp tieát kieäm nhaát ñeå ñöa moät heä ñoäng löïc löïc töø traïng thaùi xuaát phaùt ñeán moät traïng thaùi ñích, baøi toaùn laäp lòch thi coâng caùc coâng ñoaïn trong coâng trình thi coâng lôùn, baøi toaùn löïa choïn ñöôøng truyeàn tin vôùi chi phí nhoû nhaát trong maïng thoâng tin, …hieän nay coù raát nhieàu phöông phaùp ñeå giaûi caùc baøi toaùn nhö vaäy. Theá nhöng thoâng thöôøng caùc thuaät toaùn ñöôïc xaây döïng döïa treân lyù thuyeát ñoà thò toû ra laø caùc thuaät toaùn coù hieäu quaû nhaát. Trong phaàn naøy ta seõ xeùt moät soá thuaät toaùn nhö vaäy. 3.1. Caùc khaùi nieäm môû ñaàu. Trong phaàn naøy ta chæ xeùt ñoà thò coù höôùng G = (V,E), |V| = n, |E| = m vôùi caùc cung ñöôïc gaùn troïng soá, nghóa laø moãi cung (u, v) thuoäc E cuûa noù ñöïôc ñaët töông öùng vôùi moät soá thöïc a (u, v) goïi laø troïng soá cuûa noù, chuùng ta seõ ñaët a(u, v)= , neáu (u, v) E. Neáu daõy v0, v1,…vp. laø moät ñöôøng ñi treân G, ñoà thò ñoä daøi cuûa noù ñöôïc ñònh nghóa laø toång sau.    P i ii VVa 1 1 ),( Töùc laø, ñoà daøi cuûa ñöôøng ñi chính laø toång troïng soá treân caùc cung cuûa noù. (chuù yù raèng neáu chuùng ta gaùn troïng soá cho taát caû caùc cung ñeàu baèng 1, thì ta ñöôïc ñònh nghóa ñoä daøi cuûa ñöôøng ñi nhö laø soá cung cuûa ñöôøng ñi gioáng nhö caùc phaàn tröôùc ta ñaõ xeùt ). Baøi toaùn tìm ñöôøng ñi ngaén nhaát treân ñoà thò döôùi daïng toång quaùt coù theå phaùt bieåu nhö sau: Tìm ñöôøng ñi coù ñoä daøi nhoû nhaát töø moät ñænh xuaát phaùt s  V ñeán ñænh cuoái (ñích) t  V. Ñöôøng ñi nhö vaäy ta seõ goïi laø ñöôøng ñi ngaén nhaát töø s ñeán t coøn ñoä daøi cuûa noù ta seõ kyù hieäu laø d(s, t) vaø coøn goïi laø khoaûng caùch töø s ñeán t (khoaûng caùch ñònh nghóa nhö vaäy coù theå laø soá aâm ). Neáu nhö khoâng toàn taïi ñöôøng ñi töø s ñeán t thì ta seõ ñaët d(s, t) = . Roõ raøng, neáu nhö moãi chu trình trong ñoà thò ñeàu coù ñoä daøi döông, thì trong ñöôøng ñi ngaén nhaát khoâng coù ñænh naøo bò laëp laïi (ñöôøng ñi khoâng coù ñænh naøo laëp laïi seõ ñöôïc goïi laø döôøng ñi cô baûn). Maët khaùc, neáu ñoà thò coù chu trình vôùi ñoä daøi aâm (chu trình nhö vaäy, ñeå ngaén goïn ta goïi laø chu trình aâm ) thì khoaûng caùch giöõa moät soá caëp ñænh naøo ñoù cuûa ñoà thò coù theå laø khoâng xaùc ñònh, bôûi vì baèng caùch ñi voøng theo chu trình naøy moät soá ñuû lôùn laàn, ta coù theå chæ ra ñöôøng ñi giöõa caùc ñænh naøy coù ñoä daøi nhoû hôn baát cöù soá thöïc cho tröôùc naøo. Trong caùc tröôøng hôïp nhö vaäy, coù theå ñaët vaán ñeà tìm ñöôøng ñi cô baûn ngaén nhaát, tuy nhieân baøi toaùn ñaët ra seõ trôû neân phöùc taïp hôn raát nhieàu, bôûi vì noù chöùa baøi toaùn xeùt söï toàn taïi ñöôøng ñi Hamilton trong ñoà thò nhö laø moät tröôøng hôïp rieâng. SV ne t.vn Trang:29 Tröôùc heát caàn chuù yù raèng neáu bieát khoaûng caùch töø s ñeán t, trong tröôøng hôïp troïng soá khoâng aâm, coù theå tìm ñöôïc moät caùch deã daøng, ñeå tìm ñöôøng ñi chæ caàn ñeå yù laø ñoái vôùi caëp ñænh s, t  V tuøy yù (s  t) luoân tìm ñöôïc v ñænh sao cho: d(s, t) = d(s, v) + a(v, t). Thöïc vaäy, ñænh v nhö vaäy chính laø ñænh ñi tröôùc ñænh t trong ñöôøng ñi ngaén nhaát töø s ñeán t. Tieáp theo ta laïi coù theå tìm ñöôïc ñænh u sao cho d(s, v)= d(s, u) + a(u, v), … töø giaû thieát veà tính khoâng aâm cuûa caùc troïng soá deã daøng suy ra raèng daõy t, v, u,… khoâng chöùa ñænh laëp laïi vaø chöùa ñænh keát thuùc ôû ñænh s. Roõ raøng daõy thu ñöôïc xaùc ñònh (neáu laät ngöôïc thöù töï caùc ñænh trong noù) ñöôøng ñi ngaén nhaát töø s ñeán t. 3.2. Ñöôøng ñi ngaén nhaát xuaát phaùt töø moät ñænh . Phaàn lôùn caùc thuaät toaùn tìm khoaûng caùch giöõa hai ñænh s vaø t ñöôïc xaây döïng nhôø kyõ thuaät tính toaùn maø ta coù theå moâ taû ñaïi theå nhö sau: töø ma traän troïng soá a{u, v}, u, v  V, ta tính caän treân d{v} cuûa khoaûng caùch töø s ñeán taát caû caùc ñænh v  V , moãi khi phaùt hieän . d{u}+a[u, v] < d[v] (1) Caän treân d[v] seõ ñöôïc laø toát leân : d[v]=d[u] + a[u, v]. Quaù trình ñoù seõ keát thuùc khi naøo chuùng ta khoâng laøm toát theâm ñöôïc baát cöù caän treân naøo. Khi ñoù roõ raøng giaù trò cuûa moãi d[v] seõ cho ta khoaûng caùch töø ñænh ñöôïc goïi laø nhaõn cuûa ñænh v, coøn vieäc tính laïi caùc laïi caùc caän treân naøy seõ goïi laø pheùp gaùn nhaõn cho ñoà thò vaø toaøn boä thuû tuïc thöôøng goïi laø thuû tuïc gaùn nhaõn. Nhaän thaáy raèng ñeå tính khoaûng caùch töø s ñeán t, ôû daây, ta phaûi tính khoaûng caùch töø s ñeán taát caû caùc ñænh coøn laïi cuûa ñoà thò. Hieän nay vaãn chöa bieát thuaät toaùn naøo cho pheùp tìm ñöôøng ñi ngaén nhaát giöõa hai ñænh laøm vieäc thaät söï hieäu quaû hôn nhöõng thuaät toaùn tìm ñöôøng ñi ngaén nhaát töø moät ñænh ñeán taát caû caùc ñænh coøn laïi. Sô ñoà tính toaùn maø ta vöøa moâ taû coøn chöa laø xaùc ñònh bôûi vì coøn phaûi chæ ra thöù töï choïn caùc ñænh u vaø v ñeå kieåm tra ñieàu kieän (!) thöù töï choïn naøy coù aûnh höôûng raát lôùn ñeán hieäu quaû cuûa thuaät toaùn . Baây giôø ta seõ moâ taû thuaät toaùn Ford-Bellman tìm ñöôøng ngaén nhaát töø ñænh s ñeán taát caû caùc ñænh coøn laïi cuûa ñoà thò. Thuaät toaùn laøm vieäc trong tröôøng hôïp troïng soá cuûa caùc cung laø tuøy yù, nhöng giaû thieát raèng trong ñoà thò khoâng coù chu trình aâm . Procedure Ford-Bellman; (* Ñaàu vaøo: ñoà thò coù höôùng G=(V,E) vôùi n ñænh s  V laø ñænh xuaát phaùt. a[u,v],u,v  V ma traän troïng soá : Giaû thieát : ñoà thò khoâng coù chu trình aâm: SV ne t.vn Trang:30 Ñaàu ra : khoaûng caùch töø ñænh s ñeán taát caû caùc ñænh coøn laïi d[v], v  Truoc[v],v  V , ghi nhaän ñænh tröôùc v trong ñöôøng ñi ngaén nhaát töø s ñeán v *) Begin (* Khôûi taïo *) for v  V do begin d[v]: =a[s, v]: truoc[v]: =s: end; d[s]:=0; for k:=1 to n – 2 do for v  V \[s] do for u  V do if d[v] > d[u] + a[u,v] then begin d[v]:=d[u]+a[u,v]: truoc[v]:=u; end; end. Tính ñuùng ñaén cuûa thuaät toaùn coù theå chöùng minh treân cô sôû nguyeân lyù toái öu cuûa qua hoaïch ñoäng roõ raøng laø ñoä phöôùc taïp tính toaùn cuûa thuaät toaùn laø O(n 3 ) löu yù raøng chuùng ta coù theå chaám döùt voøng laëp theo K khi phaùt hieän trong quaù trình thöïc hieän hai voøng laëp trong khoâng coù bieán d[t] naøo bò ñoåi giaù trò vieäc naøy coù theå xaûy ra vôùi k < n-2 vaø ñieàu ñoù laøm taêng hieäu quaû cuûa thuaät toaùn trong vieäc giaûi caùc bìa toaùn thöïc teá. Tuy nhieân, caùi tieán ñoù khoâng thöïc söï caûi thieän ñöôïc ñaùnh giaù ñoä phöùc taïp cuûa baûn thaân thuaät toaùn. Ñoái vôùi ñoà thò thöa thôùt hôn laø söû duïng danh saùch keà Ke(v), v  V, ñeå bieåu dieãn ñoà thò, khi ñoù voøng laëp theo u caàn vieát laïi döôùi daïng . For u  ke(v) do If d[v] > d[u]+a[u, v] then begin d[u]:= d[u]+a[u, v]; truoc[v]:=u; end; trong tröôøng hôïp naøy ta thu ñöôïc thuaät toaùn vôùi ñoä phöùc taïp O (n.m). 3.3. Ñöôøng ñi ngaén nhaát giöõa taát caû caùc caëp ñænh Roõ raøng ta coù theå giaûi baøi toaùn tìm ñöôøng ñi ngaén nhaát giöõa taát caû caùc caëp ñænh cuûa ñoà thò baèng caùch söû duïng n laàn thuaät toaùn moâ taû ôû muïc tröôùc, trong ñoù ta seõ choïn s laàn löôït laø caùc ñænh cuûa ñoä thò. Roõ raøng, khi ñoù ta thu ñöôïc thuaät SV ne t.vn Trang:31 toaùn vôùi ñoä phöùc taïp laø O(n 3 ) (neáu söû duïng thuaät toaùn Ford-Bellman) hoaëc O(n 3 ) ñoái vôùi tröôøng hôïp troïng soá khoâng aâm hoaëc ñoà thò khoâng coù chu trình. Trong tröôøng hôïp toång quaùt, söû duïng thuoät toaùn Ford-Bellman n laàn khoâng phaûi laø caùch laøm toát nhaát. ÔÛ ñaây ta seõ moâ taû moät thuaät toaùn giaûi baøi toaùn treân vôùi ñoä phöùc taïp tính toaùn O(n 3 ): Thuaät toaùn Floyd. Thuaät toaùn ñöôïc moâ taû döôùi ñaây. Procedure Floyd (* Tìm ñöôøng ñi ngaén nhaát giöõa caùc caëp ñænh Ñaàu vaøo:Ñoà thò cho bôûi ma traän troïng soá a{i,j},i,j=1,2….,n. .Ñaàu ra:Ma traän ñöôøng ñi ngaén nhaát giöõa caùc caëp ñænh d{i, j}=1,2….n, trong ñoù d{i, j} cho ñoä daøi ñöôøng ñi ngaén nhaát töø i ñeán j. Ma traän ghi nhaän ñöôøng ñi P{i,j},i,j=1,2…n. Trong ñoù p{i,j}ghi nhaän ñænh ñi tröôùc ñænh j Trong ñöôøng ñi ngaén nhaát töø i ñeán j. *) Begin (*khôûi taïo*) for i:=1 to n do for j:=1 to n do begin d{i, j}:=a{i, j}; p{i, j}:=i; end; (*böôùc laëp *) for k:=1 to n do for i:=1 to n do for j:=1 to n do if d{i, j}>d{i, k}+d{k, j} then begin d{i, j}:=d{i, k}+d{k, j}; p{i, j}:= p{k, j}; end; end; Roõ raøng ñoä phöùc taïp tính toaùn cuûa thuaät toaùn laø O(n 3 ). SV ne t.vn Trang:32 CHÖÔNG 3 BAØI TOAÙN LAÄP LÒCH THI COÂNG COÂNG TRÌNH I. Baøi toaùn. Vieäc thi coâng moät coâng trình lôùn ñöôïc chia ra laøm n coâng ñoaïn, ñaùnh soá töø 1 ñeán n. coù moät soá coâng ñoaïn maø vieäc thöïc hieän noù chæ ñöôïc tieán haønh sau khi moät soá coâng ñoaïn naøo ñoù ñaõ hoaøn thaønh. Ñoái vôùi moãi coâng ñoaïn i bieát t[i] laø thôøi gian caàn thieát ñeå hoaøn thaønh noù (i = 1, 2, ..n). Ta coù theå xay döïng ñoà thò coù höôùng n ñænh bieåu dieãn haïn cheá veà trình töï thöïc hieän caùc coâng vieäc sau: moãi ñænh cuûa ñoà thò töông öùng vôùi moät ñoà thò, neáu coâng vieäc i phaûi ñöôïc thöïc hieän tröôùc coâng ñoaïn j thì treân ñoà thò coù cung (i, j), troïng soá treân cung naøy ñöôïc gaùn baèng t[i]. Theâm vaøo ñoà 2 ñænh 0 vaø n +1 töông öùng vôùi hai söï kieän ñaëc bieät: ñænh soá 0 töông öùng vôùi coâng ñoaïn Leã khôûi coâng, noù phaûi ñöôïc thöïc thöïc hieän tröôùc taát caû caùc coâng ñoaïn khaùc, vaø ñænh n+1 töông öùng vôùi coâng ñoaïn Caét baêng khaùnh thaønh coâng trình, noù phaûi thöïc hieän sau taát caû caùc coâng ñoaïn, vôùi t[0] = t[n+1] = 0 (treân thöïc teá chæ caàn noái ñænh 0 vôùi taát caû ñænh coù baùn baäc vaøo baèng 0 vaø noái taát caû caùc ñænh coù baùn baäc ra baèng 0 vôùi ñænh n+1). Goïi ñoà thò thu ñöôïc laø G. Roõ raøng baøi toaùn ñaët ra vaán ñeà baøi toaùn tìm ñöôøng ñi daøi nhaát töø ñænh 0 ñeán taát caû caùc ñænh coøn laïi treân ñoà thò G. Do ñoà thò G roõ raøng khoâng chöùa chu trình, neân ñeå giaû baøi toaùn ñaët ra coù theå aùp duïng caùc thuaät toaùn ñöôïc neâu ôû treân. 1. Thí duï: Ta coù baûng caùc haïng muïc ñöôïc cho trong baûng döôùi ñaây. Haïng muïc t[i] Haïng muïc phaûi hoaøn thaønh tröôùc 1 2 3 4 5 6 7 8 10 15 10 30 1 2 15 20 10 1 2,3 4 2,3 5,6 5 0 1 : 0 0 1 2 : 10 0 3 : 0 0 1 2 4 : 25 0 1 2 4 5 : 55 0 3 6 : 10 0 1 2 4 5 : 55 Ñöa veà baøi toaùn ñoà thò coù höôùng, caùc ñænh laø caùc haïng muïc nhö hình sau: 1 (10) 2 5 (12) 8 (0) (10) 0 (15) (30) (12) 9 (0) (10) (15) (15) (20) 3 4 6 7 (10) SV ne t.vn Trang:33 Caùch giaûi quyeát: * Theâm hai ñænh 0 vaø ñænh 9 ta thu ñöôïc moät ñoà thò coù höôùng trong ñoù troïng soá t[i] laø caïnh xuaát phaùt töø i * Tìm ñöôøng ñi daøi nhaát thì - Ñoåi daáu troïng soá - Tìm ñöôøng ñi ngaén nhaát xuaát phaùt töø 0 Laëp VH 1 2 3 4 5 6 7 8 9 Ktaïo 0 0,0 0, 0,0 0,  0,  0,  0,  0,  0,  1 * 1,-10 0,0 0,  0,  0,  0,  0,  0,  2 * 0,0 2,-25 0,  2,-25 0,  0,  0,  3 * 2,-25 0,  2,-25 0,  0,  0,  4 * 4,-25 2,-25 0,  0,  0,  5 * 2,-25 5,-67 5,-67 0,  6 * 5,-67 5,-67 0,  7 * 5,-67 7,-87 8 * 7,-87 9 * Chöông trình söû duïng thuaät toaùn Dijkstra ñeå tình thôøi gian caùc coâng vieäc baét ñaàu vaø keát thuùc döï aùn. Chöông trình thi coâng coâng trình khoâng söû duïng tröïc tieáp thuaät toaùn naøy maø coøn phuï thuoäc vaøo caùc coâng vieäc laøm ñaàu tieân, vì vaäy coâng vieäc ñaàu tieân laø ta phaûi xaùc ñònh coâng vieäc naøo laø coâng vieäc ñaàu tieân, vieäc xaùc ñònh coâng vieäc ñaàu tieân cuõng raát ñôn giaûn, khi ta nhaäp soá lieäu thì coâng vieäc ñaàu tieân thì khoâng coù coâng vieäc naøo laøm tröôùc noù. Ñeå giaûi baøi toaùn treân ta coù theå duøng nhieàu phöông phaùp. Nhöng trong ñeà taøi naøy chuùng toâi söû duïng thuaät toaùn Dijkstra. II. Thuaät toaùn Dijkstra. Thuaät toaùn Dijkstra ñöôïc phaùt bieåu nhö sau: Trong tröôøng hôïp troïng soá treân caùc cung laø khoâng aâm do Dijkstra ñeà nghò ñeå giaûi baøi toaùn tìm ñöôøng ñi ngaén nhaát töø dænh s ñeán caùc ñænh coøn laïi cuûa ñoà thò . Thuaät toaùn ñöôïc xaây döïng treân cô sôû gaùn cho caùc ñænh caùc nhaõn taïm thôøi. Nhaõn cuûa moãi ñænh cho bieát caän treân cuûa ñoä daøi ñöôøng ñi ngaén nhaát töø s ñeán noù. Caùc nhaõn naøy seõ ñöôïc bieán ñoåi theo moät thuû tuïc laëp, maø ôû moãi böôùc laëp coù moät nhaõn taïm thôøi trôû thaønh nhaõn coá ñònh. Neáu nhaõn cuûa moät ñænh naøo ñoù trôû thaønh coá ñònh thì noù seõ cho ta khoâng phaûi laø caän treân maø laø ñoä daøi ñöôøng ñi ngaén nhaát töø ñænh s ñeán noù. Thuaät toaùn ñöôïc moâ taû nhö sau. Procedure Dijkstra; (* Ñaàu vaøo: Ñoà thò coù höôùng G=(V, E) vôùi n ñænh s  V laø ñænh xuaát phaùt a[u, v], u, v  V, ma traän troïng soá SV ne t.vn Trang:34 Giaû thieát: a[u, v] >= 0, u, v  V Ñaàu ra: khoaûng caùch töø d(s) ñeán taát caû caùc ñænh coøn laïi d[v], v  V Truoc [v], v  V, ghi nhaän ñænh tröôùc v trong ñöôøng ñi ngaén nhaát töø s ñeán v *) Begin (* Khôûi taïo *) for v  V do Begin d[v] := a[s, v]; Truoc[v] := s; End; d[s] := 0; T := V \ {s} (*Taäp caùc ñænh coù nhaõn taïp thôøi *) (* Böôùc laëp*) while T 0 do Begin Tìm ñænh u  T thoûa maõn d[u] = min { d[z]: z  T} T := T \ {u}; (*Coá ñònh nhaõn cuûa ñænh u*) For v  T do (*Gaùn nhaõn laïi cho caùc ñænh trong T*) If d[v] > d[u] + a[u, v] then Begin D[v] := d[u] + a[u, v] Truoc [v] := u; End; End; End; Ñònh lyù 1: Thuaät toaùn Dijkstra tìm ñöôïc ñöôøng ñi ngaén nhaát treân ñoà thò sau thôøi gian côù O(n 2 ). Chöùng minh: Tröôùc heát ta chöùng minh laø thuaät toaùn tìm ñöôøng ñi ngaén nhaát töø ñænh s ñeán caùc ñænh coøn laïi cuûa ñoà thò. Giaû söû raèng ôû moät böôùc laëp naøo ñoù caùc nhaõn coá ñònh cho ta ñoä daøi caùc ñöôøng ñi töø s ñeán caùc ñænh coù nhaõn coá ñònh, ta seõ chöùng minh raèng ôû laàn laëp tieáp theo neáu ñænh u * thu ñöôïc nhaõn coá ñònh d(u * ) chính laø ñoä daøi ñöôøng ñi ngaén nhaát töø s ñeán u * . Kyù hieäu S: laø taäp hôïp coù nhaõn coá ñònh coøn S2 laø taäp caùc ñænh coù nhaõn taïm thôøi ôû böôùc laëp ñang xeùt. Keát thuùc moãi böôùc laëp nhaõn taïm thôøi d(v) cho ta ñoä daøi cuûa ñöôøng ñi ngaén nhaát töø s ñeán v chæ qua nhöõng ñænh naèm hoaøn toaøn trong taäp S1. Giaû söû raèng ñöôøng ñi ngaén nhaát töø s ñeán u * khoâng naèm trong taäp S1, töùc laø noù ñi qua ít nhaát moät ñænh cuûa taäp S2. Goïi z  S2 laø ñænh ñaàu tieân nhö vaäy treân ñöôøng ñi naøy . Do troïng soá treân caùc cung laø khoâng aâm, neân ñoaïn ñöôøng töø z ñeán u * coù ñoä daøi L > 0 vaø d(z) < d(u * ) – L < d(u*). SV ne t.vn Trang:35 Baát ñaúng thöùc naøy laø maâu thuaãn vôùi caùch xaùc ñònh u * laø ñænh coù nhaõn taïm thôøi nhoû nhaát. Vaäy ñöôøng ñi ngaén nhaát töø ñænh s ñeán u * phaûi naèm choïn trong S1, vaø vì theá d[u * ] laø ñoä daøi cuûa noù. Do ôû laàm laëp ñaàu tieân S1 = {s} vaø sau moãi laàn laëp ta chæ theâm vaøo S1 moät ñænh u * neân giaû thieát laø d(v) cho ñoä daøi ñöôøng ñi ngaén nhaát töø s ñeán v vôùi moïi v  S1 laø ñuùng vôùi böôùc laëp ñaàu tieân. Theo qui naïp suy ra thuaät toaùn cho ñöôøng ñi ngaén nhaát töø s ñeán moïi ñænh cuûa ñoà thò. Baây giôø ta ñaùnh giaù soá pheùp toaùn caàn thöïc hieän theo thuaät toaùn. ÔÛ moãi böôùc laëp ñeå tìm ra ñænh u caàn thöïc hieän O(n) pheùp toaùn, vaø ñeå gaùn nhaõn laïi cuõng phaûi thöïc hieän moät soá löôïng pheùp toaùn cuõng la O(n). Thuaät toaùn phaûi thöïc hieän n- 1 böôùc laëp. Vaäy thôøi gian tính toaùn cuûa thuaät toaùn laø côõ O(n 2 ). Thí duï: Tìm ñöôøng ñi ngaén nhaát töø ñænh 1 ñeán caùc ñænh coøn laïi cuûa ñoà thò ôû hình döôùi: (7) 2 3 6 (5) (1) (1) (2) (1) (1) (4) 1 (2) 4 (3) 5 Minh hoïa thuaät toaùn Dijkstra Keát quaû tính toaùn ñöôïc trình baøy trong baûng döôùi ñaây. Böôùc laëp Ñænh 1 Ñænh 2 Ñænh 3 Ñænh 4 Ñænh 5 Ñænh 6 Khôûi taïo 0, 1 1, 1* , 1 , 1 , 1 , 1 1 - - 6, 2 3, 2* , 1 8, 2 2 - - 4, 4* - 7, 4 8, 2 3 - - - - 7, 4 5, 3 4 - - - - 6, 6 * - 5 - - - - - - Chuù yù: 1) Neáu chæ caàn tìm ñöôøng ñi ngaén nhaát töø s ñeán t naøo ñoù thì coù theå keát thuùc thuaät toaùn khi ñænh t trôû thaønh ñænh coù nhaõn coá ñònh. SV ne t.vn Trang:36 * Sô ñoà thuaät toaùn Dijkstra. (1) Soá phaàn töû:= soá ñænh -1; i:=1; i < ñnguoàn Taäp ñænh[i]:=i; Ññ-ñeán[i]:=kc[ñnguoàn, i]; Ññ- tröïc tieáp ñeán[i]:=ñnguoàn; i:=i+1; i:=ñnguoàn +1 i  soá ñænh Taäp ñænh[i]:=i; Ññ-ñeán[i]:=kc[ñnguoàn, i]; Ññ- tröïc tieáp ñeán[i]:=ñænh nguoàn; i:=i+1; Baét Ñaàu N Y N Y SV ne t.vn Trang:37 SV ne t.vn Trang:38 (1) (3) (4) (2) j soá ñænh -2 Min:= ññ-ñeán[ñænh[1]]; Vò trí :=1; i k Ññ-ñeán[ñænh[i]] <min; Min:= ññ-ñeán[ñænh[i]]; Vò trí :=i; i:=i+1 Ñænh xeùt:=ñænh[vò trí]; Ñænh[vò trí]:=ñænh[spt]; Spt:=spt-1; i:=1 i spt Y N Y N Y N Y N SV ne t.vn Trang:39 III. Giaûi quyeát baøi toaùn. Sau khi ñöa baøi toaùn veà daïng ñoà thò coù höôùng, vôùi moãi ñænh laø moät haïng muïc ta coù theå tieán haønh nhö sau: - Chuyeån thaønh ma traän troïng soá coù daïng a(i, j), vôùi haïng muïc i phaûi ñöôïc thi coâng tröôùc haïng muïc j, giaù trò cuûa a(i, j) cho bieát thôøi gian haïng muïc i laøm xong. - Ñoåi daáu giaù trò cuûa ma traän: ví duï a(i, j) = -a(i, j) (4) (2) X:=ñænh[i] (3) Ññ-ñeán[x] > Ññ- ñeán[ñænh xeùt]+ kc[ñænh xeùt,x]; Ññ-ñeán[x]:=Ññ-ñeán[ñænh xeùt + kc[ñænh xeùt,x]]; i:=i+1; Keát Thuùc Y N SV ne t.vn Trang:40 - Aùp duïng thuaät toaùn Dijkstra. - Keát thuùc thuaät toaùn ta thu ñöôïc d[u] . - Ñoåi daáu giaù trò d[u] vöøa thu ñöôïc: d[v] = -d[u] - Giaù trò d[v] chính laø ñöôøng ñi daøi nhaát töø 0 ñeán ñænh v, khi ñoù d[v] cho ta thôøi ñieåm sôùm nhaát coù theå baét ñaàu thöïc hieän coâng ñoaïn v, noùi rieâng d[n+1] laø thôøi ñieåm sôùm nhaát coù theå caét baêng khaùnh thaønh toaøn boä coâng trình. Töông töï nhö treân ví duï treân khi keát thuùc toaøn boä döï aùn, keát quaû thu ñöôïc nhö sau: Giaû söû leã khôûi coâng döï aùn laø 1-1-2003 Thì sau 87 ngaøy (Giaû söû ñôn vò tính laø ngaøy) ta coù theå caét baêng khaùnh thaønh toaøn boä döï aùn. IV. Ñieàu khieån nhaân löïc Caùc hoaït ñoäng khoâng gaêng ñöôïc pheùp xeâ dòch nhaát ñònh, nhaát laø khi FFij = TFij. Coù theå saép ñaët chuùng ñaùp öùng caùc yeâu caàu khaùc nöõa. Ngoaøi thôøi gian ra, chaúng haïn nhaân löïc, nguyeân lieäu, chi phí …Veà maët toaùn hoïc xöû lyù yeâu caàu loaïi naøo cuõng vaäy. ÔÛ ñaây ta noùi theo ngoân ngöõ nhaân löïc chaúng haïn. Thí Duï III.1. Giaû söû nhaân löïc cho caùc hoaït ñoäng cuûa döï aùn ôû Thí Duï II.2 ñoøi hoûi nhö sau: Hoaït ñoäng Soá nhaân coâng Hoaït ñoäng soá nhaân coâng (1, 2) 0 (4, 6) 2 (1, 3) 5 (4, 7) 1 (2, 4) 0 (5, 6) 2 (3, 4) 7 (5, 7) 5 (3, 5) 3 (6, 7) 6 Chuù yù raèng taïi thôøi ñieåm hai hoaït ñoäng cuøng tieán haønh thì soá nhaân löïc caàn laø toång hai soá coâng nhaân. Vì vaäy caàn phaûi saép xeáp kheùo caùc hoaït ñoäng khoâng gaêng ñeå ñoøi hoûi toång nhaân coâng cuûa caû döï aùn ít (taïm coi laø moãi ngöôøi bieát laøm moïi vieäc). Vieäc saép xeáp toái öu laø phöùc taïp, ñeán nay ta söû duïng bieåu ñoà thôøi gian bieåu dieãn theâm nhaân löïc ñeå saép xeáp theo tröïc quan. H.1.6 (a) bieåu dieãn toång coâng nhaân caàn ôû moãi thôøi ñieåm neáu taát caû caùc hoaït ñoäng khoâng gaêng xeáp vaøo luùc sôùm nhaát coù theå, coøn H.1.6 (b) laø töông öùng khi xeáp vaøo luùc muoän nhaát coù theå. Hai bieåu ñoà naøy neân veõ thaúng döôùi H.1.5 nöõa. Saép ñaët sôùm nhaát ôû hình (a) cho thaáy ôû moãi thôøi ñieåm döï aùn caàn nhieàu nhaát laø 10 coâng nhaân coøn ôû saép ñaët muoän nhaát (b) laø 12 coâng nhaân. ÔÛ hai phöông aùn naøy, soá coâng nhaân caàn ôû caùc thôøi ñieåm khoâng ñeàu. Theo tröïc quan ta chænh laïi töø (a) nhö sau: chuyeån hoaït ñoäng (4, 6) ñeáân thôøi ñieåm muoän nhaát coù theå, chuyeån (4, 7) ñeán ngay sau khi (5, SV ne t.vn Trang:41 7) keát thuùc. Keát quaû ñöôïc veõ laïi ôû bieåu ñoà H.1.7. (chuù yù laø hoaït ñoäng (1, 2) vaø (2, 4) khoâng caàn coâng nhaân neân khoâng caàn veõ.). SV ne t.vn Trang:42 Chöông IV GIÔÙI THIEÄU NGOÂN NGÖÕ LAÄP TRÌNH Visual Basic laø moät ngoân ngöõ laäp trình khaù phoå bieán hieän nay, noù laø moät coâng cuï raát tieän lôïi cho haàu heát caùc chöông trình öùng duïng, caùc chöông trình söû lyù theo yeâu caàu cuûa ngöôøi duøng. Ñieàu ñaëc bieät cuûa ngoân ngöõ Visual Basic ñoù laø noù duøng ngay giao dieän ngöôøi duøng ñoà hoïa , hay GUI (Graphical User Interface). Ñieàu ñaëc bieät, Visual Basic cho pheùp boå xung caùc menu, hoäp vaên baûn, nuùt leänh, nuùt tuøy choïn (cho caùc löïa choïn loaïi tröø), caùc hoäp kieåm tra (cho caùc löïa choïn khoâng loaïi tröø), caùc hoäp danh saùch, thanh cuoán, caùc hoäp taäp tin vaø thö muïc cho caùc cöûa soå troáng. Baïn coù theå duøng caùc löôùi (Grid) ñeå quaûn lyù döõ lieäu theo baûng. Baïn coù theå truyeàn thoâng vôùi caùc öùng duïng Windows khaùc, vaø coù theå laø quan troïng nhaát, baïn seõ coù moät phöông phaùp deã daøng ñeå ngöôøi duøng ñieàu kieåm vaø truy caäp caùc cô sôû döõ lieäu. (Nhöõng thaønh phaàn ñoù ñöôïcVisual basic goïi laø Ñieàu Kieåm (control)). Coù theå coù nhieàu cöûa soå treân maøn hình. Caùc cöûa soå naøy coù toaøn queàn truy caäp clipboard vaø caùc thoâng tin trong haàu heát caùc öùng duïng Windows khaùc chaïy cuøng luùc. Baïn coù theå duøng Visual Basic ñeå truyeàn thoâng vôùi caùc öùng duïng khaùc ñang chaïy döôùi Windows. Duøng phieân baûn hieän ñaïi nhaát cuûa coâng ngheä COM/OLE trong Windows. Phöông thöùc laäp trình cuûa Visual Basic laø thieát keá tröôùc, vieát leänh sau. Vì vaäy moâi tröôøng laøm vieäc khoâng phöùc taïp nhö caùc ngoân ngöõ laäp trình khaùc. Chuùng bao goàm caùc ñoái töôïng. I. Cöûa soå thuoäc tính. 1. Moät soá thuoäc tính cuûa ñoái töôïng Form. Thuoäc tính Theå hieän vôùi giaù trò xaùc laäp Name Duøng ñeå ñaët teân cho Form, teân naøy seõ ñöôïc duøng cho thuû tuïc maø baïn vieát maõ. Appearance Quy ñònh caùch theå hieän cuûa Form 0 Flat (Form phaúng) 1 3D (Form noåi) Backcolor Choïn maøu neàn cuûa Form Bordestyle Quy ñònh kieåu khung cuûa Form Caption Quy ñònh tieâu ñeà cuûa Form Controlbox Neáu ñaët laø true thì cöûa soå coù Controlmenubox. Neáu ñaët laø False thì cöûa soå khoâng coù Controlmenubox. Icon Duøng Icon coù bieåu töôïngnhö theá naøo khi baïn click nuùt SV ne t.vn Trang:43 minimize Max buttion Neáu ñaët laø true thì cöûa soå coù nuùt Maximize Neáu ñaët laø false thì cöûa soå khoâng coù nuùt Maximize Min buttion Neáu ñaët laø true thì cöûa soå coù nuùt Minimize Neáu ñaët laø false thì cöûa soå khoâng coù nuùt Miniimize Moveable Neáu ñaët laø true thì coù theå nhaán Mouse vaøo tieâu ñeà vaø keùo ñi nôi khaùc, neáu False thì khoâng keùo ñi ñöôïc Showintaskba r True: cöûa soå naøy hieän leân teân cuûa noù cuõng theå hieän trong taskbar cuûa Öindôù, neáu False thì khoâng. Visiable True: Thaáy Form False: aån Form Windowstate Quy ñònh kích thöôùc Form 0 Bình thöôøng 1 Cöïc tieåu 2 Cöïc ñaïi 2. Moät soá thuoäc tính cuûa cöûa soå Lable Thuoäc tính Theå hieän vôùi giaù trò xaùc laäp Name Teân cuûa lable Alignment Canh noäi dung cuûa lable 0 Canh traùi 1 Canh phaûi 2 Canh giöõa Autosize Baïn chon true noù töï ñoäng co giaõn cho vöøa noäi dung cuûa noù Choïn false thì baïn töï ñieàu chænh cho vöøa Backcolor Quy ñònh maøu neàn cho lable Caption Ghi chöõ treân lable Font Choïn kieåu chöõ cho lable Fontcolor Quy ñònh maøu chöõ treân lable 3. Moät soá thuoäc tính cuûa ñoái töôïng Textbox. Thuoäc tính Theå hieän vôùi giaù trò xaùc laäp Name Ñaët teân cho Textbox Alignment Canh noäi dung cuûa textbox 0 Canh traùi 1 Canh phaûi 2 Canh giöõa Appearance Quy ñònh caùch theå hieän cuûa Textbox 0 flat bình thöôøng SV ne t.vn Trang:44 1 3D 3 chieàu Backcolor Quy ñònh maøu neàn cho Textbox Font Choïn kieåu chöõ cho textbox Forecolor Quy ñònh maøu chöõ treân textbox Maxlength Quy ñònh soá kyù töï toái ña nhaäp vaøo textbox Multiline True: coù theå xuoàng haøng khi chieàu ngang khoâng ñuû False: khoâng xuoáng haøng Scrollbar Duøng ñeå xaùc laäp hoäp textbox khoâng coù thanh cuoán doïc, ngang haëc caû hai vôùi ñieàu kieän thuoäc tính Mulltiline = true Text Baïn haõy xoùa chöõ vaø ñeå troáng Visible Quy ñònh text coù ñöôïc nhìn thaáy treân form hay khoâng True: nhìn thaáy, False: khoâng nhìn thaáy 4. Thuoäc tính cuûa ñoái töôïng Commandbox Thuoäc tính Theå hieän vôùi giaù trò xaùc laäp Name Ñaët teân cho ñoái töôïng Commandbox Caption Laøm tieâu ñeà cho nuùt Font Choïn font cho nuùt Visible True: nuùt nhìn thaáy False: nuùt khoâng nhìn thaáy 5. Thuoäc tính ñoái töôïng Checkbox. Thuoäc tính Theå hieän vôùi giaù trò xaùc laäp Name Ñaët teân cho checkbox Alignment Canh noäi dung cuûa checkbox Appearance Quy ñònh caùch theå hieän cuûa Checkbox Backcolor Quy ñònh maøu neàn cho checkbox Font Choïn kieåu chöõ cho checkbox Caption Doøng tieâu ñeà cho checkbox Forecolor Quy ñònh maøu chöõ cho checkbox Value 0: Khoâng choïn 1: traïng thaùi choïn 2: Traïng thaùi xaùm Visible True: Khoâng nhìn thaáy False: nhìn thaáy 6. Thuoäc tính hay duøng cuûa ñoài töôïng picturebox Thuoäc tính Theå hieän vôùi giaù trò xaùc laäp Name Teân cho ñoái töôïng picturebox Autosize True: töï ñoäng ñaët laïi kích thöôùc cuûa ñoái töôïng cho vöøa SV ne t.vn Trang:45 vôùi kích thöôùc cuûa hình ñaõ ñöôïc ñaët vaøo False: neáu hình ñaët vaøo lôùn hôn kích thöôùc thì hình naøy seõ bò che khuaát Picture Duøng ñeå löu tröù böùc hình baïn muoán trình baøy Align Duøng ñeå quy ñònh caùch boá trí ñaëc bieät cuûa picture treân form Autoredraw Hình seõ khoâng bò xoùa ñi khi baïn thu nhoû hay phoùng to kích thöôùc Fillcolor Quy ñònh maøu toâ cho caùc phöông thöùc ñoà hoïa Fillstyle Quy ñònh daïng maøu toâ Drawstyle Quy ñònh ñöôøng neùt veõ Drawith Quy ñònh ñoä daøy neùt veõ 7. Moät soá thuoäc tính hay duøng cuûa ñoái töôïng Image. Thuoäc tính Theå hieän vôùi giaù trò xaùc laäp Name Ñaët teân cho ñoái töôïng Image Picture Töông töï nhö thuoäc tính picture cuûa ñoùi töôïng picturebox Borderstyle Quy ñònh kieåu khung coù (1) hoaëc khoâng coù khung(0) Stretch True: hình seõ töï ñoäng co giaõn sao cho vöøa vaëên trong ñoái töôïng False: ñoái töôïng seõ töï ñiruf chænh cho vöøa vôùi hình 8. Moät soá thuoäc tính hay duøng cuûa ñoái töôïng Listbox. Thuoäc tính Theå hieän vôùi giaù trò xaùc laäp Name Ñaët teân cho ñoái töôïng Listbox Colums Duøng ñeå theå hieän listbox coù bao nhieâu coät, maëc nhieân laø 1 Integranlhieght True: Listbox seõ töï ñieàu chænh kích thöôùc sao cho khoâng coù muïc naøo bò che khuaát nöûa chöøng False: thì seõ chính xaùc nhö khi baïn thieát keá Listcount Xaùc ñògh danh saùch coù bao nhieâu muïc, baïn chæ coù theå ñoïc chöù khoâng ñaët laïi giaù trò List Quy ñònh moät danh saùch cho Listbox Multiselect Quy ñònh moãi laàn chæ coù theå choïn moät hay nhieàu muïc Listindex Muïc ñang coù focut trong danh saùch laø muïc thöù bao nhieâu Selcount Cho bieát hieän ñang coù bao nhieâu muïc ñöôïc choïn trong danh saùch Sorted True: Saép xeáp danh saùch theo thöù töï False: saép xeáp nhö trình töï baïn ñöa vaøo SV ne t.vn Trang:46 9. Moät soá thuoäc tính hay duøng cuûa ñoái töôïng Combobox Thuoäc tính Theå hieän vôùi giaù trò xaùc laäp Name Ñaët teân cho ñoái töôïng combobox Style Quy ñònh kieåu cho combobox Sorted True: Saép xeáp theo thöù töï Alphabet False: saép xeáp nhö trình töï baïn ñöa vaøo 10. Moät soá thuoäc tính hay duøng cuûa ñoái töôïng Timer Thuoäc tính Theå hieän vôùi giaù trò xaùc laäp Name Ñaët teân cho ñoái töôïng Timer Enable True: cho pheùp phaùt ra söï kieän thôøi gian False: ngöôïc laïi Interval Laø gí trò soá duøng ñeå quy ñònh bao nhieâu laâu thì phaùt ra söï kieän thôøi gian. Ñôn vò tính laø miligiaây. Neáu ñaët laø 0 thì ñoái töôïng timer khoâng hoaït ñoäng 11. Moät soá thuoäc tính hay duøng cuûa ñoái töôïng frame Thuoäc tính Theå hieän vôùi giaù trò xaùc laäp Name Ñaët teân cho ñoái töôïng frame Caption Noäi dung cuûa tieâu ñeà frame 12. Moät soá thuoäc tính hay duøng cuûa ñoái töôïng Button Thuoäc tính Theå hieän vôùi giaù trò xaùc laäp Name Ñaët teân cho ñoái töôïng option button Alignment Quy ñònh vò trí nuùt choïn 0: nuùt choïn naèm beân traùi tieâu ñeà 1: nuùt choïn naèm beân phaûi tieâu ñeà Caption Tieâu ñeà cuûa option button Font Choïn font chöõ cho tieâu ñeà Value Neáu giaù trò naøy baèng true thì option naøy ñang ñöôïc choïn, ngöôïc laïi thì noù ñang ôû vò troù khoâng ñöôïc choïn 13. Moät soá thuoäc tính hay duøng cuûa ñoái töôïng line Thuoäc tính Theå hieän vôùi giaù trò xaùc laäp Name Ñaët teân cho ñoái töôïng line Bordercolor Quy ñònh maøu cho ñöôøng thaúng Borderwith Quy ñònh ñoä daøy cuûa ñöôøng thaúng Borderstyle Quy ñònh kieåu ñöôøng thaúng coù giaù trò töø 0 ñeán 7 X1, X2, X3, X4 Xaùc ñònh toïa ñoä cuûa ñöôøng thaúng treân form SV ne t.vn Trang:47 Drawmode Quy ñònh mode ñeå veõ ñöôøng 14. Moät soá thuoäc tính hay duøng cuûa ñoái töôïng Shape Thuoäc tính Theå hieän vôùi giaù trò xaùc laäp Name Ñaët teân cho ñoái töôïng shape Shape Quy ñònh moät soá hình daùng 0: Hình chöõ nhaät 1: Hình vuoâng 2: hình ellipse 3: Hình troøn 4: Hình chöõ nhaät troøn goùc 5: Hình vuoâng troøn goùc Fillstyle Quy ñònh caùc kieåu veõ coù giaù trò töø 0 ñeán 7 Fillcolor Quy ñònh maøu toâ beân trong cuûa hình Borderstyle Quy ñònh kieåu kieåu ñöôøng vieàn cuûa hình Borderwith Quy ñònh ñoä daøy neùt cuûa hình Berdercolor Quy ñònh maøu ñöôøng vieàn Backstyle Quy ñònh maøu neàn cuûa hình Backcolor Quy ñònh maøu cuûa phaàn neàn khi backstyle laø Opque II. Bieán, Kieåu bieán vaø caùch khai baùo 1. Bieán Töông töï nhö caùc ngoân ngöõ laäp trình khaùc, bieán laø moät yeáu toá khoâng theå thieáu, bieán nhö laø moät phaàn cuûa boä nhôù, muoán döû duïng ta phaûi khai baùo. Teân bieán khoâng daøi quaù 255 kyù töï, coù tính gôïi nhôù, khoâng duøng caùc kyù hieäu, traùnh duøng caùc töø khoùa cuûa VB 2. Kieåu cuûa bieán Khi khai baùo bieán ta phaûi khai boùa kieåu cho noù. Trong VB, ngöôøi ta duøng moät loaïi tieáp ngöõ nhö $, &, #, @, … ñeå bieát bieán ñoù coù kieåu laø gì, cuï theå nhö sau: - String: laø kieåu döõ lieäu chuoãi, khoaûng giaù trò coù theå leân ñeán hai tyû kyù töï. Nhaän bieát bieán naøy baèng tieáp ngöõ $ Ví duï: Hoten$ = “Traàn Vaên Hai”. - Byte: laø kieåu soá nguyeân döông, khoaûng giaù trò töø 0 ñeán 255. - Long: laø caùc soá nguyeân, khoaûng giaù tròn töø –2.147.483.648 ñeán 2.147.483.647. Nhaän bieát bieán naøy baèng daáu & ôû cuoái Ví duï: A& 50. - Integer: laø caùc soá nguyeân töø –32.768 ñeán 32.767. Nhaän bieát baèng daáu % ôû cuoái SV ne t.vn Trang:48 Ví duï: b% = 1234 - Single: laø caùc soá coù daáu chaám thaäp phaân, coù giaù trò aâm töø – 3,402823E8 ñeán –1,40129823E8 vaø coù gía trò döông töø 1,401298E-45 ñeán 3,402823E8. Nhaän bieát baèng daáu ! ôû cuoái Ví duï: C! = 4.7 - Double: laø caùc soá coù daáu chaám thaäp phaân. Nhaän bieát baèng daáu # ôû cuoái. Khoaûng giaù trò töø –1,797693134486231E308 ñeán – 44,94065645841247E-324, giaù trò döông töø 44,94065645841247E-324 ñeán 1,797693134486231E308. Ví duï: D# = 6.432 - Currency: Coù 15 soá naèm beân traùi daáu phaûy, 4 soá naèm beân traùi daáu phaûy. Nhaäp bieát baèng daáu @ ôû cuoái. Khoaûng giaù trò töø – 922337203685477,5808 ñeán 922337203685477,5807. Ví duï: e@ = 5.1234. - Date: Löu rtöõ thoâng tin veà thôøi gian. Nhaän bieát baèng daáu # ôû ñaàu vaø ôû cuoái. Ví duï: ngay = #12/12/2003# - Boolean: bieán logic coù giaù trò true hay false duøng ñeå gaùn giaù trò hay trong caùc caâu leänh ñieàu kieän - Variant: Löu taát caû caùc giaù trò khaùc nhau. 3. Caùch Khai baùo Ngoaøi caùch nhaän bieát bieán baèng caùc tieáp vò ngöõ, ta coù theå khai baùo bieán nhö sau: DIM AS Vi duï: DIM Ten AS String III. Caùc pheùp toaùn trong Visual Basic 1. Caùc toaùn töû trong Visual Basic - Toaùn töû ^: Duøng ñeå tính luõy thöøa - Toaùn töû *: Duøng ñeå nhaân hai soá haïng - Toaùn töû \: Chia hai soá laáy phaàn nguyeân - Toaùn töû / : Chia hai soá laáy giaù trò thöïc - Mod: Chia laáy phaàn dö - Toaùn töû +: Coäng hai toaùn haïng - Toaùn töû -: Tröø hai toaùn haïng 2. Thöù töï öu tieân caùc pheùp toaùn Pheùp tính luõy thöøa Ñoåi moät soá thaønh soá aâm Nhaân vaø chia Chia soá nguyeân Chia laáy soá dö Coän g vaø tröø 3. Toaùn töû gaùn SV ne t.vn Trang:49 a = b 4. Toaùn töû quan heä Kyù hieäu Yù nghóa Ví duï = Baèng nhau A=b < Nhoû hôn A<b <= Nhoû hôn hoaëc baèng A<=b Khaùc nhau Ab > Lôùn hôn a>b >= Lôùn hôn hoaëc baèng a>=b 5. Toaùn töû logic A NOT A True False False True - Pheùp toaùn AND, OR vaø XOR A B A And B A or B True True True True True False False True False True False True False False False False IV. Caùc caáu truùc ñieàu khieån 1. Caáu truùc löïa choïn IF Caáu truùc löïa choïn IF cho pheùp ta reõ chöông trình thaønh 2 nhaùnh, neáu baïn muoán reõ nhieàu nhaùnh thì coù theå söû duïng caáu truùc IF loàng nhau. Caáu truùc If khoâng coù Else If Then ___________ End If Caáu truùc If coù Else If Then ____________ Else ____________ End If 2. Caáu truùc Select Case Caáu truùc naøy ñöôïc duøng khi baïn xeùt nhieàu ñieàu kieän cho moät bieán naøo ñoù CASE _____’ Caùc leänh CASE _____’ Caùc leänh SV ne t.vn Trang:50 CASE _____’ Caùc leänh CASE ELSE _________ END SELECT 3. Caáu truùc DO WHILE ….. LOOP Caáu truùc nhö sau DO WHILE ‘ caùc leänh LOOP Caâu leänh naøy thöïc hieän nhö sau: Tröôùc tieân noù kieåm tra ñieàu kieän: neáu ñieàu kieän ñuùng thì thöïc hieän leänh sau ñoù kieåm tra ñieàu kieän cho ñeán khi dieàu kieän sai thì thöïc hieän sau leänh LOOP Neáu ñieàu kieän sai thì thöïc hieän leänh sau LOOP, boû qua leänh giöõa DO… LOOP 4. Caáu truùc Do …. Loop WHILE Caáu truùc nhö sau Do ‘ Caùc leänh Loop While Caâu leänh naøy thöïc hieän nhö sau: Caùc caâu leänh sau Do seõ ñöôïc thöïc hieän, sau ñoù môùi xeùt ñieàu kieän khi ñieàu kieän sai thì môùi thöïc hieän leänh sau Loop Neáu ñieàu kieän sai thì thöïc hieän leänh sau Loop 5. Caáu truùc Do … Loop Until Caáu truùc nhö sau: Do ‘ Caùc leänh Loop until Caâu leänh thöïc hieän nhö sau Caùc leänh sau do seõ ñöôïc thöïc hieän tröôùc cho ñeán khi naøo ñieàu kieän ñuùng 6. Caáu truùc For … Next Caáu truùc nhö sau For to Step [khoaûng taêng] ‘ Caùc leänh Next Bieán SV ne t.vn Trang:51 Ñeå döøng caáu truùc For ta duøng phaùt bieåu Exit For Ngoaøi ra, muoán thoaùt ra khoûi thuû tuïc vôùi ñieàu kieän naøo ñoù ta duøng thuû tuïc Exit Sub V. Thuû tuïc vaø haøm 1. Thuû tuïc Khi laäp trình ta thöôøng gaëp nhöõng ñoaïn chöông trình hay laäp ñi laäp laïi nhieàu laàn ôû nhöõng choã khaùc nhau. Ñeå chöông trình ñôõ phöùc taïp, caùc ñoaïn naøy ñöôïc thay theá baèng caùc chöông trình con töông öùng, khi caàn ta chæ caàn goïi noù ra maø khoâng caàn pahæ vieát laïi caû ñoaïn. Maët khaùc, ñoái vôùi moät soá chöông trình lôùn vaø phöùc taïp. Vieäc xem xeùt toång quan cuõng nhö vieäc gôõ roái, hieäu chænh seõ raát khoù khaên. Vieäc laäp caùc chöông trình con seõ chia chöông trình ra thaønh töøng khoái, töøng modul. Ñieàu naøy giuùp cho chuùng ta kieåm tra, gôõ roái vaø ñieàu khieån deã daøng. Caáu truùc cuûa moät thuû tuïc coù daïng nhö sau: Sub ______________’ Caùc leänh End Sub Neáu baïn muoán duøng thuû tuïc naøy trong toaøn boä chöông trình thì baïn duøng theâm töø khoùa Public tröôùc töø khoùa Sub, coøn neáu baïn chæ muoán duøng trong moät form chöùa noù thì baïn theâm töø khoùa Private tröôùc töø khoùa Sub 2. Haøm Haøm cuõng töông töï nhö thuû tuïc, chæ khaùc laø ta duøng haøm khi muoán nhaän laïi moät keát quaû traû laïi cuûa haøm. Caáu truùc haøm nhö sau: Function (tham soá AS Kieåu) AS ______________’ Caùc Leänh Teân haøm = Giaù trò End Function VI. Moät soá leänh cuûa Visual Basic 1. Leänh End Duøng ñeå chaám söùt chöông trình ñang chaïy, khi leänh naøy thöïc hieän thì caùc cöûa soå chöông trình seõ ñoùng laïi vaø giaûi phoùng ra khoûi boä nhôù. Leänh naøy thöôøng ñöôïc söû duïng cho nuùt leänh coù teân Exit côùi bieán coá Click Ví duï Sub Command1_Click() End End Sub 2. Leänh Exit Do SV ne t.vn Trang:52 Leänh naøy duøng ñeå thoaùt khoûi voøng laëp Do Ví duï Do While ____________ Exit Do 3. Leänh Exit For Leänh naøy duøng ñeå thoaùt khoûi voøng laëp For 4. Leänh Exit Sub Leänh naøy duøng ñeå thoaùt khoûi chöông trình con naøo ñoù 5. Leänh Beep Leänh naøy phaùt ra tieáng Beep 6. Leänh Date Leänh naøy cho pheùp baïn ñaët laïi ngaøy giôø cuûa heä thoáng. Cuù phaùp: Date = #Ngaøy# Ví duï Date = #07/12/20003# Text1 = Date 7. Leänh Time Leänh naøy cho pheùp baïn ñaët laïi giôø cuûa heä thoáng Cuù phaùp: Time = #giôø# Ví duï: Time = # 11:53:AM# 8. Leänh Load Leänh naøy duøng ñeå naïp moät Form vaøo boä nhôù Cuù phaùp: Laod teân Form Ví duï Load form1 Form1.Show 9. Leänh Chdrive Duøng ñeå ñoåi oå ñóa laøm vieäc Ví duï: Chdrive “D:” chuyeån xang laøm vieäc treân ñóa D 10. Leänh MkDir Duøng ñeå taïo thö muïc môùi treân ñóa Ví duï: MkDir “C:/Baitap” ‘ Taïo thö muïc baøi taäp naèm ôû thö muïc goác ñóa C 11. Leänh ChDir Duøng ñeå thay ñoåi thö muïc laøm vieäc. Ví duï: ChDir “\Lythuyet” ‘ chuyeån xang laøm vieäc thö muïc lyù thuyeát SV ne t.vn Trang:53 12. Leänh RmDir Leänh naøy duøng ñeå xoùa thö muïc roãng ñang toàn taïi reân ñóa. Ví duï: RmDir “C:\Baitap” ‘ Xoùa thö muïc Baitap treân ñóa C 13. Leänh Kill Duøng ñeå xoùa moät hay nhieàu taäp tin treân ñóa Ví duï: Kill “C:\baitap\bt1.txt”’ xoùa taäp tin bt1.txt trong thö muïc baitap treân oå C 14. Leänh Name Leänh naøy duøng ñeå ñoåi tin moät taäp tin treân cuøng moät oå ñóa. Ví duï: Name “C:\bt.txt” as “C:\baitap.txt” 15. Leänh AppActive title [, Wait] Duøng ñeå kích hoaït moät cöûa soå trong moät chöông trình naøo ñang chaïy. VII. Moät soá haøm duøng trong VB 1. Haøm Abs (Number) Haøm naøy traû veà moät soá laø giaù trò tuyeät ñoái cuûa Nuumber 2. Haøm Sin(Number AS Double) Tính Sin cuûa moät goùc 3. Haøm Cos (number AS Double) Tính Cos cuûa moät goùc 4. Haøm Tan (number AS Double) Tính Tan cuûa moät goùc 5. Haøm Atn (number AS Double) Tính Artang cuûa moät goùc 6. Haøm Int (number) Traû veà phaàn nguyeân cuûa moät soá neáu laø soá döông. Coøn neáu laø soá aâm thì seõ traû veà phaàn nguyeân coù giaù trò nhoû hôn moät ñôn vò. 7. Haøm Fix (number) Haøm traû veà phaàn nguyeân cuûa moät soá. 8. Haøm Sgn (Number) Haøm traû veà moät soá nguyeân. - Neáu so >0 seõ traû veà giaù trò laø 1 - Neáu so <0 seõ traû veà giaù trò laø –1 - Neáu so = 0 seõ traû veà giaù trò laø 0 9. Haøm Sqr (Number) Tính caên baäc hai cuûa moät soá 10. Haøm Exp (Number) Tính e muõ cuûa moät soá 11. Haøm Log () SV ne t.vn Trang:54 Tính Logarit cuûa moät soá. Haøm traû veà giaù trò thöïc 12. Haøm round (Bieåu thöùc [,so]) Haøm naøy seõ laøm troøn soá 13. Haøm Rnd ([Number]) Haøm traû veà moät soá thöïc ngaãu nhieân 14. Haøm Day (Bieán) Traû veà soá ghi ngaøy cuûa bieán nhaäp vaøo 15. Haøm Month (Bieán) Traû veà soá ghi thaùng cuûa bieán nhaäp vaøo 16. Haøm Year (bieán) Traû veà soá ghi naêm cuûa bieán nhaäp vaøo 17. Haøm Now Traû veà ngaøy thaùng naêm vaø thôøi gian hieän taïi 18. Haøm Weekday (bieán) Cho bieát thöù maáy trong tuaàn 19. Haøm Hour (thoigian) Cho bieát giôø öùng vôùi bieán. 20. Haøm Minute (thoigian) Cho bieát phuùt öùng vôùi bieán. 21. second (thoigian) Cho bieát giaây öùng vôùi bieán. 22. Haøm Replace (chuoi, chuoicantim, chuoithaythe, vitrithaythe, solanthaythe) Thay theá chuoãi naøy baèng moät chuoãi khaùc. 23. Haøm Val (string) Traû veà moät soá thöïc töông öùng vôùi chuoãi String. String phaûi laø moät chuoãi goàm caùc kyù soá hôïp leä. - Giaù trò cuûa haøm laø 0 neáu chuoãi coù kyù töï ñaàu laø kyù töï - Giaù trò cuûa haøm laø moät soá neáu chuoãi ñoù hoaøn toaøn laø caùc kyù soá. Neáu caùc kyù töï soá vieát caùch nhau thì haøm naøy seõ caét boû khoaûng traéng vaø cho traû veà giaù trò baèng vôùi daõy naøy. 24. Haøm Str (Number) Haøm traû veà moät chuoãi kyù töï. Chuoãi naøy luoân luoân coù moät kyù töï ñaàu ghi daáu trong tröôøng hôïp soá aâm, hoaëc moät khoaûng troáng trong tröôøng hôïp soá döông 25. Haøm Qbcolor (color) Haøm cho maøu cuûa moät ñoái töông naøo ñoù 26. Haøm RGB (red, green, blue) Choïn maøu baát kyø qua tæ leä 3 maøu chuaån Red, Green, Blue. 27. Haøm Asc (String) SV ne t.vn Trang:55 Traû veà maõ Ascii cuûa kyù töï string 28. Haøm Chr (CharCode) Haøm traû veà moät kyù töï töông öùng vôùi moät maõ Ascii naøo ñoù 29. Haøm Len (Expreession) Cho bieát chieàu daøi cuûa chuoãi 30. Haøm Ltrim (string) Haøm naøy traû veà moät chuoãi sau khi ñaõ caét boû moät soá khoaûng troáng beân traùi cuûa chuoãi 31. Haøm Rtrim (string) Haøm naøy traû veà moät chuoãi sau khi ñaõ caét boû moät soá khoaûng troáng beân phaûi cuûa chuoãi 32. Haøm Trim (string) Haøm naøy traû veà moät chuoãi sau khi ñaõ caét boû moät soá khoaûng troáng beân traùi vaø beân phaûi cuûa chuoãi 33. Haøm Left (String, n) Haøm traû veà moät chuoãi kyù töï ñöôïc caét töø n kyù töï (keå caû kyù töï traéng) beân traùi cuûa chuoãi String. 34. Haøm Right (String, n) Haøm traû veà moät chuoãi kyù töï ñöôïc caét töø n kyù töï (keå caû kyù töï traéng) beân phaûi cuûa chuoãi String. 35. Haøm Mid (String, n [, length]) Haøm naøy traû veà moät chuoãi, chuoãi naøy ñöôïc laáy töø chuoãi String baét ñaàu töø vò trí n vôùi chieàu dai length. 36. Haøm Space (n) Haøm traû veà moät chuoãi goàn n khoaûng traéng. 37. Haøm String (n, kyù töï) Haøm traû veà moät chuoãi kyù töï gioáng nhau. 38. Haøm Instr (Start, S1, S2, Compare) Duøng ñeå tìm moät chuoãi con coù naèm trong chuoãi meï hay khoâng, neáu coù thì n