Đ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

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 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 ñ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. 1 2 3 4 5 7 9 11 12 6 8 10 13 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 X2 X3 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. x1 x1 x1 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 = ÔÛ ñ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öõ. 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 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å Hình 1.3 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. 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. Moãi döï aùn ñeàu coù ít nhaát moät ñöôøng gaêng. 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. 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. Ñöôø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. Ñöôø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 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 = {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 = , ôû ñaây laø ñoä daøi ñöôøng gaêng vaø 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ø , ôû ñaây TPG 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 < KP < 1 vaø KP 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 L4 = 16. Baây giôø giaû söû P laø ñöôøng ñi 1 –> 2 –> 3 –> 4 –> 5 –> 6 –> 8 –> 10 –> 13 thì TP = =40 Neân thôøi gian döï tröõ cuûa P laø TG – TP = 44 – 40 = 40. Heä soá gaêng laø KP = (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 = . Ta thaáy maëc duø TQ > TP 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ï. 1 2 3 4 5 6 7 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 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. 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 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 = 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õ.). Soá coâng nhaân 2 5 6 7 8 10 Soá nhaân coâng 2 5 6 7 8 10 12 Thôøi gian Thôøi gian 3 4 6 10 11 13 14 17 19 3 4 6 10 11 13 14 17 19 (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) H .I.6 (b) 1 1 3 4 5 6 7 4 6 71 7 5 5 3 41 2 2 4 Thôøi gian Soá coâng nhaân 5 6 7 9 10 3 4 6 10 11 13 14 17 19 3 4 6 10 11 13 14 17 19 Thôøi Gian 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í DCij khi ñaït ñöôïc ruùt ngaén thôøi gian thöïc hieän hoaït ñoäng laø Dtij (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 . Giaû söû cöïc tieåu laø . 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ø ôû ñ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 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 d2 ñ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 . (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 ôû ñaây xe laø kyø voïng vaø s2 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, , (1.2) ôû ñaây a, b laø tham soá, G(.) 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) a b a=1, b=2 a = b a=2, b=2 a=b=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 a ³ 1, b ³ 1 vaø a = 0, b = 1. f(x) m x 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. Hình 1.9 ôû ñaây tham soá m chính laø kyø voïng vaø s2 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 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 chieám tyû troïng baèng nöûa ñieåm hôïp lyù nhaát m. Khi ñoù (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 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 s2 (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 9 4 9 8 4 2 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 1 4 1 1 1 1 1 4 0 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. 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 –&g._.t; 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 + sKa}, ôû ñaây s laø ñoä leäch chuaån. Do ñoù Ks 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 + sKs neân Ks = 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 mi 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 mi kyù hieäu laø E(mi), 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(mi) vaø Var(mi) laø toång caùc te vaø s2 cuûa caùc hoaït ñoäng theo ñöôøng ñeán i coù toång E(mi) daøi nhaát. Neáu coù nhieàu ñöôøng vôùi cuøng E(mi) thì Var(mi) quy öôùc laáy löôïng cuûa ñöôøng coù toång caùc s2 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 mi 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{mi £ 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: , ôû ñaây ñ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. Cöôùc phí tröïc tieáp Kij Cdij Cöïc ñieåm Ñieåm chuaån Thôøi gian Cxij CDij dij xij Dij 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ø: . 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ø , (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 Ñ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. CHÖÔNG 2 CÔ SÔÛ VEÀ LYÙ THUYEÁT ÑOÀ THÒ 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ù. 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. Ñæ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: Ñò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. 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ù 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 =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 ñ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ø: 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 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 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 aijp, 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ù aijp, 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. 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 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] =q neáu (i, j) Ï E Trong ñoù soá q, 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, +¥, -¥. Ö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 n2 ñô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 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. 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. 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: Ñ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(n3) 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û._.