Đ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

Nội dung text: Đ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

1. LUẬN VĂN TỐT NGHIỆP KHOA CÔNG NGHỆ THÔNG TIN Đề 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”, Trang:1
2. Chương mở đầu GIỚI THIỆU CHUNG VỀ NHIỆM VỤ Đề 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”, bao gồm - Tìm hiểu phương pháp PERT-PCM (phương pháp sơ đồ mạng lưới). - Ứng dụng giải bài toán lập lịch thi công công trình. + Lưu trữ lịch thi công các dự án + Cho biết thới gian bắt đầu một dự án và thời gian kết thúc dự án + Thêm một số hạng mục khi dự án đang được thi công + Bỏ một số hạng mục khi dự án đang thi công + Đưa ra lịch thi công các hạng mục tối ưu nhất Trang:2
3. Chương I ĐIỀU HÀNH DỰ ÁN BẰNG PHƯƠNG PHÁP PERT-CMP (Phương pháp sơ đồ mạng lưới) Dự án (Project) là một tập hợp các hoạt động (Activity) liên quan với nhau và phải được thực hiện theo một thứ tự nào đó cho đến khi hoàn thành toàn bộ các hoạt động. Hoạt động được hiểu như là một việc đòi hỏi thời gian, và nguyên liệu (Resource) để hoàn thành. Trước kia để điều hành dự án người ta thường dùng biểu đồ Gantt (Gantt bar chart), là một đồ thị gồm các đường kẻ ngang, biểu thị điểm khởi công và kết thúc hoạt động. Nhược điểm của biểu đồ là không xác định được quan hệ giữa các hoạt động, nên không áp dụng được cho các dự án lớn (large-scale project), đòi hỏi đặt kế hoạch (planning), điều hành thực hiện (scheduling) va kiểm tra (controlling) một cách hệ thống và hiệu quả, thậm chí phải tối ưu hoá hiệu quả (về thời gian và tiết kiệm nguyên liệu). Vì vậy, gần như đồng thời vào năm 1956-1958, hai phương pháp kế hoạch, điều hành và kiểm tra dự án đã ra đời. Phương pháp đường găng hoặc phương pháp đường tới hạn (Critical path method, viết rắt là CPM) được E.I.du Pont de Nemous và công ty xây dựng của ông đưa ra. Phương pháp thứ hai có tên là Kỹ thuật xem xét và đánh giá dự án (Project evaluation and review technique, viết tắt là PERT) là kết quả nghiên cứa của một công ty tư vấn theo đặt hàng của hải quân Mỹ, dùng để điều hành các hoạt động nghiên cứu và phát triển chương trình tên lửa đối cực. Hai phương pháp được hình thành độc lập nhưng rất giống nhau, cùng nhằm vào mục đích điều hành thời gian là chính. Sự khác nhau chính là trong CPM thời gian ước lượng cho công việc, được coi là tất định (Deterministic), còn trong PERT có thể là ngẫu nhiên (Probabilistic). Ngoài ra CPM có tính đến quan hệ thời gian. Ngày nay, khi đã phát triển lên, hai phương pháp được coi là một, dưới một tên chung là Phương pháp điều hành dự án PERT-CPM, hoặc Phương pháp sơ đồ mạng lưới hoặc hệ thống kiểu PERT (PERT-type system). Nó được dùng để thực hiện rất nhiều kiểu dự án, từ xây dựng, lập trình máy tính, sản xuất phim đến vận động tranh cử chính trị hoặc các cuộc giải phẫu phức tạp. Phương pháp điều hánh dự án PERT-CPM gồm ba pha (tức là ba khâu): kế hoạch, điều hành và kiểm tra điều chỉnh. Pha kế hoạch có nội dung là lập một sơ đồ mạng lưới (arrow network diagram hoặc arrow diagram), tương tự một đồ thị có hướng. Pha này mở đầu bằng việc tách dự án thành nhiều hoạt động riêng và định thời gian hoàn thành chúng. Trong mạng, mỗi cung có hướng biểu diễn hoạt động và cả sơ đồ mạng biểu thị mối quan hệ giữa các hoạt động. Mỗi nút biểu thị một biến cố hoặc sự kiện (event), đánh dấu hoàn thành một số hoạt động (activity) là các cung đi vào nút, và bắt đầu các hoạt động ứng với các cung ra khỏi nút. Pha điều hành (scheduling phase) có nhiệm vụ xây dựng biểu đồ thời gian, chỉ rõ thời điểm bắt đầu và kết thúc của mỗi hoạt động và mối quan hệ giữa các hoạt động. Nói riêng, điều quan trọng là phải tính chính xác các hoạt động tới hạn, tức là găng (critical), cần chú ý đặc biệt khi thực hiện, để toàn bộ dự án được hoàn thành đúng hạn. Trang:3
4. Pha kiểm tra bao gồm việc sử dụng sơ đồ mạng lưới, và biểu đồ thời gian để theo dõi và báo cáo định kì tiến triển của dự án. Nếu cần thì phải phân tích lại và xác định sơ đồ mới cho phần dự án còn lại. I. Lập sơ đồ mạng lưới Như trên đã nói, pha đầu của phương pháp PERT-CPM là lập kế hoạch thể hiện ở một sơ đồ mạng lưới, biểu diễn như một đồ thị có hướng. Hãy xét một dự án xây dựng một toà nhà. Việc tách dự án thành các hoạt động như đào đất, xây móng, xây tường thô, lợp mái, đặt đường dây điện là do kiến trúc sư hoặc kỹ sư xây dựng làm. Dựa vào đó, người quản lý dự án lập được sơ đồ mạng lưới như H.1.1. Các số bên cạnh cung là thời gian thực hiện hoạt động đó. Qua sơ đồ mạng lưới H.1.1 ta thấy rõ mối quan hệ giữa các hoạt động về thời gian. Chẳng hạn hoạt động (6, 8) là trát ngoài-phải sau (4, 6) là lợp mái, nhưng độc lập với (5, 7) là chỉnh tường trong. Cũng vậy (4, 7) độc lập với (4, 5) và (5, 7). Ở đây có hai hoạt động gia (dummmy activity) với thời gian để thực hiện bằng 0 được đưa vào để đảm bảo qui tắc sơ đồ. Cung giả (11, 12), ký hiệu bởi đường đứt đoạn, đưa vào để đảm bảo qui tắc không có hai hoạt động cùng biến cố bắt đầu và kết thúc, tức là không có 2 cung có cùng gốc và ngọn (tức là đồ thị đơn). Việc sơn tường trong và làm sàn có cùng biến cố dầu là nút 9, tức là biến cố lát ván tường xong, và biến cố cuối là nút 12 (làm sàn và sơn tường xong, bắt đầu hoàn thiện trong). Do đó ta phải thêm nút 11 là biến cố giả và cung giả (11, 12). Cung giả (5, 8) để chỉ rằng hoạt động (4, 5) phải hoàn thành trước khi bắt đầu hoạt động (8, 10) (nếu bỏ cung giả này thì thời điểm làm hai việc là độc lập). Cung giả này là phục vụ cho qui tắc sơ đồ mạng lưới phải thể hiện đủ quan hệ thứ tự cần có. Nếu quan hệ thời gian có dạng: việc x2 bắt đầu khi xong 1/3 việc x1, việc x3 bắt đầu khi xong một nửa x1, thì ta phải thêm các nút đánh dấu các biến cố xong 1/3x1 và xong 1/2x1 đó như ở H1.2. Trang:4
5. 1 Khởi công 2 Đào móng 2 4 Xây móng 3 10 Xây thô 6 Lợp mái 4 4 Chỉnh thẳng tường ngoài Đặt dây điện 7 6 7 Trát ngoài 5 5 Chỉnh thẳng tường trong 9 Sơn ngoài 8 8 7 Ép ván lát tường 9 10 Làm sàn 4 5 Sơn tường Hoàn thiện ngoài 2 0 Hoàn thiện trong 6 11 12 Kết thúc Hình 1.1 13 Trang:5
6. Tóm lại: Sơ đồ mạng lưới phải là một đồ thị có hướng, đơn, liên thông, không có khuyên (tức là cung có gốc và ngọn cùng là một nút), không có chu trình có hướng (directed cycle), có nút khởi công và nút kết thúc. X2 X3 1 1 1 x1 x1 x1 2 3 2 Hình 1.2 II. Phân tích các chỉ tiêu thời gian. Xác định đường căng. Pha điều hành có nhiệm phân tích các chỉ tiêu thời gian và đưa ra các bảng và số liệu cần thiết trên sơ đồ mạng lưới. Nếu trong dự án phải điều hành cả nguyên liệu (hoặc nhân lực) thì phải xét cả các chỉ tiêu đó, ta sẽ nói đến ở mục sau. II.1. Tính các thời điểm. Chỉ tiêu ở đây là thời điểm sớm của biến cố (earliest time for an event) là thời điểm biến cố xảy ra khi mọi hoạt động trước nó được bắt đầu sớm nhất có thể. Thời điểm sớm của biến cố i thường ký hiệu là Ei. Các Ei được tính theo hướng tăng (forward pass), tức là đi từ nút khởi công theo thứ tự tăng của nút i. Như vậy với nút khởi công 1 thì E1 = 0. Đến nút 2 trong sơ đồ H1.1 thì E2 rõ ràng bằng 2 vì biến cố hoàn thành hoạt động (1, 2) phải là E1 + t12, ở đây t12 là thời gian thực hiện hoạt động (1, 2). Việc tính E3, E4, E5, E6, E9, E10 và E11 cũng tương tự vì các nút tương ứng chỉ có một cung vào, khi đó: Ei = Ej + tji Ở đây j là nút ngay trước i. Chẳng hạn E6 + t46 = 16 + 6 = 22. Nếu có nhiều cung vào nút, tức là nhiều hoạt động kết thúc tại biến cố, thì từ định nghĩa Ei rõ ràng đây là thời điểm mọi hoạt động đó vừa xong cả, tức là phải lấy maximum của các tổng. Chẳng hạ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 Tổng quát, công thức tính Ei cho mọi trường hợp là : Ei = maxmax {Ej + tji}, j ở đây j là các nút ngay trước i, tức là có cung nối tới i. Các Ei được ghi ở H.1.3 là số đầu trong ngoặc ở mỗi nút. Thời điểm muộn (latest time) của biến cố j là thời điểm muộn nhất mọi cung đi vào biến cố j đều hoàn thành mà không làm thay đổi thời điểm kết thúc dự án sớm nhất có thể, ký hiệu là Lj. Đối lại với Ej, các Lj được tính theo hướng lùi (backward pass), tức là đi từ nút kết thúc. Theo định nghĩa, ở nút kết thúc thì En = Ln, ở thí dụ H.1.1 là E13 = L13 = 44. nếu ở biến cố chỉ có một cung ra, tức là một hoạt động được bắt đầu thì, thời điểm muộn là : Lj =Li - tji, Trang:6
7. Tức là thời điểm muộn của nút ngay sau nó trừ đi thời gian thực hiện hoạt động nối hai nút. Các biến cố 12, 11, 10, 8, 7, 6, 3, 2 và 1 ở H.1.1 là trường hợp này. Nếu có nhiều cung ra khỏi biến cố, thì theo định nghĩa ta có : min {Li - t ji } Lj = i Ở đây min theo các nút i ngay sau j và tji là thời gian thực hiện hoạt động nối (j, i). Các nút 9, 5, 4 là ở trường hợp này, chẳng hạn : L9 = min {L11 – t9 11, L12 – t9 12} = min (38 – 4, 38 - 5) = 33 Hãy chú ý sự ‘’đối xứng ‘‘ của quá trình tính Ei và Lj. Các Lj được ghi ở số thứ 2 trong ngoặc ở mỗi nút trong H.1.3. II.2. Tính thời gian dự trữ. Trong thời gian dự trữ (slack hoặc float) của một biến có là 1 (0, 0) hiệu thời điểm muộn và thời điểm 2 sớm của nó : di = Li (2, 2) 2 – Ei. Thời gian dự trữ (slack hoặc 4 float) của hoạt động được chia làm hai 3 (6, 6) loại. Thời gian dự 10 trữ chung (total slack hoặc total (16, 16) 4 float) của 4 6 (22, 26) hoạt động (i, j) là : 4 4 TFij = Lj – Ei – tij. TF chỉ là thời gian (20, 20) ij 5 4 có thể trì hoãn của 2 hoạt động (i,j) mà 5 không ảnh hưởng 4 8 (29, 33) (25, 25) đến thời điểm kết 7 thúc cả dự án. Vì nó 4 bằng thời gian tối 8 đa dành cho hoạt (33, 33) (38, 42) động (i, j) là L - E 9 10 j i 4 trừ đi thời gian để thực hiện là tij. Thời 5 gian dự trữ độc lập 4 1 2 (free float hoặc free (38, 38) 4 slack), ký hiệu là 0 FFij, cũng là ký hiệu 11 12 6 thời gian dành cho (i, j) và thời gian (44, 44) 1 13 thực hiện là tij, nhưng với giả thiết Trang:7 Hình 1.3
8. là mọi hoạt động đều bắt đầu sớm có thể, vậy : FFij = Ej – Ei – tij. Trên sơ đồ mạng lưới thì di là hiệu hai số trong ngoặc ở nút i, thường được ghi bằng số trong ô vuông cạnh nút. Thời gian dự trữ chung của hoạt động TFij được ghi trong ô vuông cạnh ở mỗi cung. Còn thời gian dự trữ độc lập của hoạt động FFij ít quan trọng hơn, thường không ghi, xem H.1.3. II.3. Đường găng. (đường tới hạn) Các hoạt động có thời gian dự trữ chung bằng 0 cần được chú ý đặc biệt vì trì hoãn nó sẽ ảnh hưởng đến thời gian kết thúc dự án. Từ đó có : Định nghĩa II.3.1. Đường găng hoặc đường tới hạn (critical path) là một đường đi từ nút khởi công đến nút kết thúc mà mọi hoạt động trên đường đều có thời gian dự trữ chung bằng 0. (Chẳng hạn trên H.1.3 có một đường găng là 1 –> 2 –> 3 –> 4 –>5 –> 7 –> 9 –> 12 –> 13 ) hoạt động (i, j có TFij = 0 được gọi là hoạt động găng (critital activity). Biến cố i có di =0 được gọi là biến cố găng (critical event). Một số tính chất quan trọng của đường găng là như sau. 1. Mỗi dự án đều có ít nhất một đường găng. 2. Tất cả các hoạt động (i, j) có TFij = 0, tức là mọi hoạt động găng đều phải nằm trên đường găng. 3. Mọi biến cố găng, tức là biến cố i có di = 0, đều phải nằm trên đường găng. Biến có không găng không thể nằm trên đường găng. 4. Đường nối nút khởi công đến nút kết thúc mà mọi biến cố trên đó đều găng có thể không phải đường găng vì có thể có hoạt động không găng. Chẳng hạn đường 1 –> 2 –> 3 –> 4 –> 7 –> 9 –> 12 –> 13 không găng vì TF47 = 2. 5. Đường găng là đường dài nhất trong các đường nối nút khởi công đến nút kết thúc. Điều 5 này là rõ từ định nghĩa vì ở nút khởi công và kết thúc hai thời điểm sớm và muộn trùng nhau và thời gian hoàn thành dự án chính là hiệu thời gian ở hai nút (ở H.1.3 là 44 - 0). Đường găng là đường gồm các hoạt động không có dự trữ nên tổng chiều dài, tức là thời gian thực hiện, là toàn bộ thời gian thực hiện dự án (ở H.1.3 là 44), nên phải dài nhất. Trên H.1.3 đường găng được tô đậm. Một thí dụ dự án có nhiều đường găng là sơ đồ ở H.1.3 nhưng với t46 thay từ 6 thành 10. Khi đó thời gian dự trữ của các hoạt động (6, 8), (8, 10) và (10, 13) và thời gian dự trữ của các biến cố 6, 8 và 10 đều thay từ 4 thành 0. Lúc này đường 1 –> 2 –> 3 –> 4 –> 6 –> 8 –> 10 –> 13 là đường găng thứ hai. Các chỉ tiêu thời gian của dự án ở H.1.3 được ghi vào bảng 1.1 Biến cố Thời điểm Thời điểm Thời gian Hoạt động Thời gian dự sớm muộn dự trữ 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 Trang:8
9. 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 Bảng1.1. Chỉ tiêu thời gian xây nhà Ngoài các chỉ tiêu chính nói trên, khi cần các thông tin chi tiết hơn để điều hành dự án, người ta cũng đưa ra một số khái niệm về thời gian khác nữa như sau. Thời điểm khởi công sớm (earliest start) của hoạt động (i, j) là thời sớm của nút gốc: ESij = Ei. Thời điểm hoàn thành sớm (earliest completion) của hoạt động (i, j) là ECij = Ei + tij. Thời điểm khởi công muộn (latest start) của hoạt động (i, j) là LSij = Lj - tij. Thời điểm hoàn thành muộn (latest completion) của hoạt động (i, j) là LCjj = Lj tức là thời điểm muộn của nút ngọn. Nhận xét rằng ECij Ej , LSij Li. Thật vậy, ta có max Ej = {Ek + tkj} Ei +tij = ECij, k Vì i cũng là một trong các nút k ngay trước j. Bất đẳng thức thứ hai tương tự. Thời gian dự trữ của một đường đi (total float of a path) P từ nút khởi công đến nút kết thúc, ký hiệu TFp, là thời gian có thể kéo dài thêm các hoạt động trên đường này mà không ảnh hưởng đến thời điểm hoàn thành công trình, tức là G P G P TP = tij tij T T , G ở đây t T G là độ dài đường găng và t P  TP là độ dài đường P, là tổng  ij  ij thời gian thực hiện hoạt động trên đường P. Hệ số găng (critital coefficient) biểu thị mức độ căng thẳng về thời gian của một đường P nối nút khởi công và kết thúc, không phải đường găng G, được định nghĩa là T P T PG K P : , T G T PG ở đây TPG là độ dài quãng đường (tức là một phần của đường) mà P trùng với G. Rõ ràng O L4 = 16. Bây giờ giả sử P là đường P P đi 1 –> 2 –> 3 –> 4 –> 5 –> 6 –> 8 –> 10 –> 13 thì T = tij =40 Nên thời gian dự trữ của P là TG – TP = 44 – 40 = 40. Hệ số găng là Trang:9
10. 40 10 KP = (không có quãng chung với đường găng). Gọi Q là đường 1 –> 2 –> 4 11 42 35 7 10 3 –> 4 –> 7 –> 9 –> 12 –> 13 thì TQ = 42, KQ = . Ta thấy mặc dù 44 35 9 11 TQ > TP nhưng thời hạn thực hiện các hoạt động không găng trong P lại chặt chẽ hơn hoạt động không găng (4, 7) duy nhất của Q. Nguyên nhân là (4, 7) là không găng duy nhất, nên mọi sự nới lỏng của Q đều dồn cho hoạt động này. Chú ý rằng các dữ liệu thời gian quan trọng nhất là các chỉ tiêu có trong bảng 1.1. Ở bảng này cũng cho thấy đường găng (đường gồm các hoạt động găng, tức là có thời gian dự trữ chung bằng 0). II.4. Biểu đồ thời gian Một cách truyền thống, bên cạnh sơ dồ lưới bảng, để theo dõi điều hành thời gian cho dự án là dùng biểu đồ thời gian (time chart). Ta hãy xét cách vẽ và sử dụng biểu đồ thời gian qua một thí dụ. Thí dụ II.2. Xét dự án ở H.1.4, và bảng 1.2 tương ứng. (chú ý là hoạt động giả (4, 5) lại là hoạt động găng.) 5 1 3 6 2 4 7 H.1.4 Biến cố Ei Li di Hoạt TFij động 1 0 0 0 (1, 2) 2 2 2 4 2 (1, 3) 0 3 3 3 0 (2, 4) 2 4 6 6 0 (3, 4) 0 5 6 6 0 (3, 5) 1 6 13 13 0 (4, 5) 0 7 19 19 0 (4, 6) 4 (4, 7) 11 (5, 6) 0 (5, 7) 8 (6, 7) 0 Bảng 1.2 Biểu đồ thời gian cho H.1.5. Ở đây chỉ có ttrục hoành là thời gian . Cao độ không quan trọng. Ta biểu diễn các hoạt động găng phía trên. Độ dài (thời gian) là cố định, chặt chẽ cho các hoạt động găng. Hoạt động giả (4, 5) có độ dài bằng 0 nên biểu diễn bằng đoạn đứng. Mỗi hoạt động không găng biểu diễn ở độ cao khác nhau để nhìn rõ vì các hoạt động này có độ cơ động và được điều hành bằng biểu đồ thời gian. Trang:10
11. 3 4 7 1 6 5 1 2 2 2 4 2 3 3 5 4 2 6 5 7 4 5 7 0 2 3 4 6 10 13 16 19 Hình: 1.5 Biểu đồ được vẽ từ các Ei và Li ở Bảng1.2 (hoạt động găng hay không găng thì theo TFij bằng 0 hay khác 0). Các số không có vòng chỉ thời gian thực hiện của hoạt động. Chẳng hạn hoạt động (1, 2) thực hiện trong 2 đơn vị thời gian, được phép xê dịch trong khoảng thời gian 4 đơn vị (từ 0 đến 4). Xét sâu hơn thì sự xê dịch có tự do trong khoảng thời gian này không là phụ thuộc vào FFij = TFij. Nếu FFij = TFij thì hoạt động (i, j) có thể cơ động tuỳ ý trong khoảng thời gian vẽ biểu đồ. Nếu FFij < TFij thì hoạt động (i, j) chỉ được bắt đầu muộn hơn thời điểm khởi công sớm ESij một khoảng thời gian không quá FFij thì mới không ảnh hưởng đến các hoạt động ngay sau nó (duy nhất) là (2, 4) mới được xê dịch tuỳ ý trong khoảng thời gian 2 đến 6. Nếu (1, 2) thực hiện lùi lại khoảng 1 đến 3 chẳng hạn, thì ảnh hưởng đến hoạt động (2, 4). Mặc dù có FF24 = TF24 nhưng lúc này có chỉ còn được xê dịch thực hiện trong khoảng từ 3 đến 6. III. Điều khiển nhân lực. Các hoạt động không găng được phép xê dịch nhất định, nhất là khi FFij = TFij. Có thể sắp đặt chúng đáp ứng các yêu cầu khác nữa. Ngoài thời gian ra, chẳng hạn nhân lực, nguyên liệu, chi phí Về mặt toán học xử lý yêu cầu loại nào cũng vậy. Ở đây ta nói theo ngôn ngữ nhân lực chẳng hạn. Thí Dụ III.1. Giả sử nhân lực cho các hoạt động của dự án ở Thí Dụ II.2 đòi hỏi như sau: Trang:11
12. Hoạt động Số nhân Hoạt động số nhân công cô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 Chú ý rằng tại thời điểm hai hoạt động cùng tiến hành thì số nhân lực cần là tổng hai số công nhân. Vì vậy cần phải sắp xếp khéo các hoạt động không găng để đòi hỏi tổng nhân công của cả dự án ít (tạm coi là mỗi người biết làm mọi việc). Việc sắp xếp tối ưu là phức tạp, đến nay ta sử dụng biểu đồ thời gian biểu diễn thêm nhân lực để sắp xếp theo trực quan. H.1.6 (a) biểu diễn tổng công nhân cần ở mỗi thời điểm nếu tất cả các hoạt động không găng xếp vào lúc sớm nhất có thể, còn H.1.6 (b) là tương ứng khi xếp vào lúc muộn nhất có thể. Hai biểu đồ này nên vẽ thẳng dưới H.1.5 nữa. Sắp đặt sớm nhất ở hình (a) cho thấy ở mỗi thời điểm dự án cần nhiều nhất là 10 công nhân còn ở sắp đặt muộn nhất (b) là 12 công nhân. Ở hai phương án này, số công nhân cần ở các thời điểm không đều. Theo trực quan ta chỉnh lại từ (a) như sau: chuyển hoạt động (4, 6) đến thời điểm muộn nhất có thể, chuyển (4, 7) đến ngay sau khi (5, 7) kết thúc. Kết quả được vẽ lại ở biểu đồ H.1.7. (chú ý là hoạt động (1, 2) và (2, 4) không cần công nhân nên không cần vẽ.). Trang:12
13. (3, 5) (4, 7) (4, 6) 10 8 (3, 4) (5, 7) nhân công (1, 3) (6, 7) ố S Thời gian (5, 6) 6 5 7 2 3 4 6 10 11 13 14 17 19 H .I.6 (a) (4, 7) (3, 5) (3, 4) (5, 7) (1, 3) (4, 6) (6, 7) nhân công nhân ố S (5, 6) Thời gian H .I.6 (b) 2 5 6 7 8 10 10 12 8 7 5 6 2 3 4 6 10 11 13 14 17 19 Trang:13
14. 3 4 6 7 1 5 2 1 4 2 4 3 5 6 4 7 Thời gian 5 7 3 4 6 10 11 13 14 17 19 nhân công ố S 10 9 7 6 5 Th i Gian ờ Hình 1.7 3 4 6 10 11 13 14 17 19 IV. Hoàn thành sớm dự án. Trên đây đã xét thời điểm hoàn thành dự án là cố định và xác định các đường găng, phải thực hiện chặt chẽ để dự án hoàn thành đúng thời gian qui định. Nếu muốn giảm thời gian hoàn thành dự án thì làm thế nào ? Ta cũng sử dụng đường găng, nhưng phải dựa vào kỹ thuật và công nghệ, chứ không phải quản lý bằng toán học được nữa. Cụ thể là phải dùng công nghệ mới, tăng vật tư, công nhân để có thời gian thực hiện các hoạt động ngắn hơn. Nhưng tập chung vào hoạt động nào ? Rõ ràng là vào các hoạt động găng. Cụ thể là nếu ta quan tâm đến hạn chế chi phí thì với (i, j) G, tìm số gia chi phí Cij khi đạt được rút ngắn thời gian thực hiện hoạt động là tij (tìm bằng thực tế công nghệ, không phải thuần tuý toán C học). Khi đó sẽ chọn cách tăng chí phí để giảm thời gian sao cho đạt min ij . Giả tij Trang:14
15. 0 Cij sử cực tiểu là 0 . Khi đó độ dài đường găng mới, tức là thời gian hoàn thành dự tij án mới, là ~ G G 0 T T  tij , ở đây tổng lấy trên mọi hoạt động găng. V. Dự án có tính ngẫu nhiên. Trong các mục trên ta đã coi thời gian thực hiện các hoạt động tij là xác định hoàn toàn từ đầu, khi lập sơ đô mạng lưới. Do đó ta có mô hình tất định (detreministic model). Trong thực tế, nhiều yếu tố bất định phải được tính đến, do đó thời gian thực hiện hoạt động (i, j) là một biến ngẫu nhiên (random variable), mà ta chỉ xác định được phân bố xác suất (probability distributtion) qua kinh nghiệm và sô liệu thống kê. Từ đó dẫn đên phải sử dụng mô hình ngẫu nhiên hoặc gọi khác là mô hình xác suất (probabilistic model). Việc tính toán các chỉ tiêu để điều hành dự án có hai nhiệm vụ chính. Một là tính kỳ vọng (mean hoặc expected value) của các đại lượng cần tính, chẳng hạn thời gian thực hiện hoạt động (activity time), thời gian hoàn thành dự án (project time), và phương sai (variance) của các đại lượng này. Hai là tính xác suất của biến cố nào đó, chẳng hạn biến cố là dự án hoàn thành trước thời điểm T. Thời gian thực hiện mỗi hoạt động, thường gọi tắt là thời gian hoạt động, trong mô hình ngẫu nhiên thường được giả thiết là xác định được ba yêu tố sau. Thời gian lạc quan (optimistic time) ký hiệu là a, là thời gian cần để làm xong khi hoạt động được thực hiện thuận lợi nhất. Thời gian này rất khó đạt được. Theo lý thuyết thống kê, thì đây thực chất là cận dưới (lower bound) của phân bố xác suất. Thời gian bi quan (pressimistic time), ký hiệu là b, là thời gian cần để xong hoạt động khi tiên hành gặp trục trặc nhất, tức là cận trên (upper bound) của phân bố xác suất. Thời gian hợp lý nhất (most likely time), ký hiệu là m, là thời gian hiện thực nhất, tức là có xác suất lớn nhất (đỉnh cao nhất của hàm mật độ). Ba lượng trên chưa đủ để xác định phân bố xác suất của thời gian hoạt động. Do đó chưa đủ 2 để xác định kỳ vọng te tức là giá trị trung bình theo xác suất, và phương sai  đặc trưng cho độ lệch khỏi te của thời gian hoạt động. Mô hình cần hai gải thiết phù hợp thực tế sau đây. Giả thiết 1. b - a, tức là độ dài khoảng mà thời gian hoạt động có thể lấy, bằng 6 lần độ lệch chuẩn (standard deviasion), tức là ta có phương sai 2 2 1  (b a) . (1.1) 6 Điều này đúng cho nhiều biến ngẫu nhiên hay gặp. Giả thiết 2. Phân bố xác suất của mỗi thời gian hoạt động đêu là phân bố beta (beta distribution). Ta hãy nhắc lại vài kiến thức xác suất. Mỗi đại lương ngẫu nhiên x có hai hàm quan trọng nhất. Hàm mật độ xác suất (probability density fuction) f(x), a x b, và hàm phân bố tích luy (cumulative distribution function) F(X), gọi là hàm phân bố. Ở đây giả thiết là x chỉ lấy giá trị trong [a, b] . Ta có các quan hệ sau Trang:15
16. b f (x)dx 1, a X F(X ) P{x X} f (x)dx, a b X xf (x)dx, e a b  2 (x x ) 2 f (x)dx, e a 2 ở đây xe là kỳ vọng và  là phương sai của biến ngẫu nhiên x, P { } là xác suất của biến cố { }. Mỗi một trong hàm mật độ hoặc hàm phân phối đặc trưng hoàn toàn cho biến ngẫu nhiên. Kỳ vọng và phương sai là các đại lượng quan trọng. Ta cũng nói là hàm mật độ (hoặc hàm phân bố), xác định hoàn toàn phân bố xác suất. Phân bố beta (beta distribution) là một trong các phân bố xác suất phổ biến nhất, xác định bởi hàm mật độ sau, nếu 0 x 1, ( ) 1 f (x) x 1 (1 x)  1 x 1 (1 x)  1 , (1.2) ( ) () B( , ) ở đây ,  là tham số, (.) là hàm đặc biệt gamma và B(., .) là hàm đặc biệt beta, được định nghĩa bằng tích phân phụ thuộc tham số ( ) : t 1e t f(x)  0 1 B( ,  ) : t 1(1 t) 1dt 0 =1, =2 =  =2, =2 ==1 m 1 x Hình 1.8 Nếu y lấy giá trị trên [a, b] và có phân bố theo beta thì hàm mật độ nhân được từ (4.2) bằng đổi biến y = a + (b - a)x. Chẳng hạn, hàm mật độ của phân bố beta có dạng như H.1.8 với 1,  1 và a = 0, b = 1. f(x) Phân bố chuẩn (normal distribution) là phân bố xác suất phổ biến nhất, định nghĩa bởi hàm mật độ sau. Trang:16  x
17. (x  )2 1 2 f (x) e 2 , x , ở đây tham số  chính là kỳ vọng và 2 chính 2  2 x  là phương sai của biến ngẫu nhiên x có phân bố chuẩn. Khi đó biến z có  phân bó là phân bô chuẩn với kỳ vọng 0, phương sai là 1. Hàm mật độ của phân bố chuẩn có dạng ở H.1.9 Các biến ngẫu nhiên x1, , xn được gọi là độc lập (independent) nếu. P{x1 X1, , xn Xn} = P{x1 Xn}, Định nghĩa giới hạn trung tâm (centrer – limit thoerem) nói rằng với các điều Hình 1.9 kiện khá nhẹ, tổng các biến ngẫu nhiên độc lập luôn có phân bố chuẩn (không phụ thuộc vào phân bố của từng biến ngẫu nhiên). Trở lại mô hình ngẫu nhiên điều hành dự án. Để tính kỳ vọng te của thời gian a b hoạt động, người ta giả thiết là điểm giữa chiếm tỷ trọng bằng nửa điểm hợp 2 lý nhất m. Khi đó 1 1 te 2m (a b) (II.3) 3 2 Thí dụ V.1. Giả sử dự án xây nhà ở H.1.1 bây giờ có các thời gian hoạt động là ngẫu nhiên có phân bố beta thoả hai giả thiết trên và xác định được ba mốc thời gian lạc quan, bi quan và hợp lý nhất theo bảng1.3. Khi đó phương sai và kỳ vọng của các thời gian hoạt động, tình theo công thức (4, 1) và (4, 3) được ghi ở hai cột cuối. Hoạt động Thời gian Thời gian Thời gian Kỳ vọng te Phương lạc quan a hợp lý nhất bi quan b sai 2 m (1, 2) 1 2 3 2 1 9 (2, 3) 2 1 8 4 1 3 2 (3, 4) 6 9 18 10 4 (4, 5) 1 1 5 4 4 4 2 9 (4, 6) 4 1 10 6 1 5 2 (4, 7) 3 1 9 7 1 7 2 (5, 7) 4 10 5 1 4 (6, 8) 5 1 11 7 1 6 (7, 9) 3 2 9 8 1 (8, 10) 5 9 17 9 4 (9, 11) 4 8 4 4 0 Trang:17
18. 4 (9, 12) 1 1 7 5 4 5 2 1 (10, 13) 1 3 2 2 9 1 4 (12, 13) 5 5 9 6 2 9 Bảng 1.3 Nhận xét rằng cột kỳ vọng ở Bảng1.3, do thí dụ được xây dựng đặc biệt, trùng hoàn toàn với các thời gian hoạt động trong mô hình tất định đã xét ở H.1. Do đó đường găng xây dựng trên các thời gian hoạt động kỳ vọng trùng với đường găng của mô hình tất định ở H.1.2 và thời gian của đường găng này là 44. Tuy nhiên để xác định kỳ vọng và phương sai của thời gian dự án, ta cần thêm hai giả thiết sau. Giả thiết 3. Các thời gian hoạt động là các biến ngẫu nhiên độc lập. Giả thiết 4. Đường găng xây dựng trên các thời gian hoạt động kỳ vọng, luôn đòi hỏi thời gian (hoàn thành mọi hoạt động trên nó) lớn hơn các đường khác. Tính thật chi ly trong các thí dụ cụ thể thì hai giả thiết 3 và 4 có thể không đúng. Chẳng hạn, ở Thí dụ V.1, nếu sảy ra thời gian bi quan ở mọi hoạt động thì đường găng đã tính là 69 (ngày). Còn đường 1 –> 2 –> 3 –> 4 –> 5 –> 7 –> 9 –> 12 –> 13 có thời gian bi quan là 70. Tuy vậy người ta vẫn chấp nhận các giả thuyết xấp xỉ này. Khi đó, vì kỳ vọng và phương sai của tổng các biến ngẫu nhiên là tổng của các kỳ vọng và phương sai nên ta có: Kỳ vọng và phương sai của thời gian dự án là tổng các kỳ vọng và phương sai của các thời gian hoạt động trên đường găng (xây dựng theo các kỳ vọng). Đến đây ta nhận xét rằng một trong các cách áp dụng thực tế là dùng các kỳ vọng của các biến, rồi áp dụng mọi tính toán và lý luận ở các mục trước vào các kỳ vọng, thay cho các biến tất định. Ở Thí dụ V.1 kỳ vọng và phương sai của thời gian dự án là 44 và 9, vì đường găng là 1 –> 2 –> 3 –> 4 –> 5 –> 7 –> 9 –> 12 –> 13 . Bây giờ ta xét vấn đề quan trọng là tính xác suất để dự án hoàn thành trước một thời hạn bắt buộc (deadline). Theo định lý giới hạn trung tâm, thời gian dự án là biến ngẫu nhiên có phân bố chuẩn. Do đó ta tính được xác suất P(x X), thường được tính sẵn để tra theo bảng. Chẳng hạn Bảng A1 ở cuối sách cho biết P {x xe + K }, ở đây  là độ lệch chuẩn. Do đó K là đơn vị lệch chuẩn. Thí dụ, hãy tính xác suất để thời gian xây nhà ở Thí dụ V.1 không quá 47 ngày. Ta thấy 47 = 44 + 3.1 = xe + K nên K = 1. Theo bảng thì P {x 47} = 0,1584. Do đó xác suất cần tìm là  1 – 0,1584  0,84. Phương pháp điều hành dự án có tính ngẫu nhiên trên đây thường được gọi là phương pháp ba ước lượng PERT (PERT three estimate method). Nếu cần tính các yếu tố thời gian ở các biến cố trung gian (không chỉ thời gian hoàn thành dự án, tức là biến cố cuối) thì ta lý luận như sau. Trước hết tính kỳ vọng và phương sai của thời điểm sớm i của biến cố i. Nếu chỉ có một đường từ khởi công đến i thì, do các hoạt động là độc lập kỳ vọng của i ký hiệu là E(i), bằng tổng các kỳ vọng te của thời gian các hoạt động dẫn đến i. Khi có nhiều đường dẫn đến i thì người ta coi xấp xỉ (để đơn giản) E(i) và Var(i) là tổng các te 2 và  của các hoạt động theo đường đến i có tổng E(i) dài nhất. Nếu có nhiều Trang:18
19. 2 đường với cùng E(i) thì Var(i) quy ước lấy lượng của đường có tổng các  dái nhất. Bây giờ hãy tính xác suất để biến cố i xong trước thời gian bắt buộc Ti cho trước. Theo định lý giới hạn trung tâm i tuân theo phân bố chuẩn, ta chỉ việc tra bảng các xác suất ứng với phân bố chuẩn để tính P{i Ti}. Cụ thể, để tra bảng, quy về trường hợp đại lương z có phân bố chuẩn với kỳ vọng 0 và phương sai 1 như sau:  i E(i ) Ti E(i ) P i Ti  P : P{z Ki}, Var(i ) Var(i )  Ti E(i ) ở đây K i đã biết. Var(i ) VI. Dự án có thoả hiệp thời gian – Cước phí. Trong các mục trước ta trình bày về các dựa án có yêu cầu chủ yếu là điều hành thời gian. Theo ngôn ngữ ban đầu thì đây là phương pháp PERT, các thời gian ở đây có thể xét như các biến tất định hoặc ngẫu nhiên. Còn phương pháp đường găng PCM thì đặt ngang nhau về thời gian và cước phí. Mục tiêu chính của PCM là chọn cách thoả hiệp thời gian thực hiện mỗi hoạt động (theo ngôn ngữ hình học) tức là biết đường cong thời gian – cước phí (time – cost curve) của mỗi hoạt động. Trong mô hình toán học (xấp xỉ thô tình trạng thực tế) người ta giả thiết quan hệ thời gian và cước phi là tuyến tính. Do đó chỉ cần biết hai điểm. Người ta chọn hai điển nút như sau: Điểm chuẩn (normal point) có toạ độ là thời gian và cước phí của hoạt động khi nó được tiến hành trong điều kiện bình thường, tức là chuẩn, không có cước phí bổ xung tăng cường (như làm ngoài giờ, tăng thiết bị nhân lực ). Cực điểm (crash point) là điểm ứng với thời gian và cước phí khi đầu tư hết mức để thời gian thực hiện hoạt động ngắn nhất có thể. Mọi điểm trung gian giữa điểm chuẩn và cực điểm, tức là mọi cách thoả hiệp thời gian cước phí (time – cost trade - off) đều coi là chấp nhận được, xem H.1.10. Kij Cực điểm C dij p Cxij ế i m chu n c tic Đ ể ẩ ự CDij Th i gian c phí tr c ờ ớ ư C dij x ij D Hình 1.10 ij Đường cong thời gian – cước phí của hoạt động (i, j). Các ký hiệu trên H.1.10 rõ ràng như sau. Dij là dij là thời gian chuẩn và thời gian cực điểm. CDij và Cdij là cước phí chuẩn (normal cost) và cước phí cực điểm (crash cost), đều của hoạt động (i, j). Gọi xij (thời gian thực hiện hoạt động (i, j)) là Trang:19
20. biến quyết định (decision variable) của bài toán mà ta cần tính. Gọi Sij là độ xiên, tức là hệ số góc đường thẳng biểu thị đường cong thời gian – cước phí , tức là: C C Dij dij Sij . Dij dij Gọi Kij là tung độ điểm đường thẳng cắt trục tung. Khi đó cước phí của hoạt động (i, j) tương ứng với thời gian hoạt động (i, j) ứng với thời gian hoạt động xij rõ ràng là: Bài toán: Chọn các xij để thời gian dự án không quá thời hạn bắt buộc T cho trước và làm cực tiểu cước phí dự án C. Nhận xét rằng các yếu tố của bài toán đều là tuyến tính, ta cố gắng đưa về quy hoạch tuyến tính như sau: Đưa vào các biến bổ xung yk là thời điểm sớm Ek của biến cố k. Khi đó quan hệ giữa các biến theo Mục 4.2 là max E E t , (1, 4) k j j jk ở đây max lấy theo các biến cố j ngay trước k, tức là có hoạt động nối (j, k). Ký hiệu yk = Ek, tjk = xjk và viết lại (4, 4) ta được yi + xjk – yk 0 (số ràng buộc là số các biến cố ngay trước k). Gọi 1 là nút xuất phát và n là nút kết thúc dự án thì y1 = 0, yn T. Ở mục tiêu thì Kij là hằng. Tóm lại ta được quy hoạch tuyến tính min  Sij xij , (i, j) d x D , ij ij ij yi xij yij 0 y1 0, yn T. Để đưa về quy hoạch tuyến tính dạng chuẩn ta làm như sau. Đổi biến xij = dij + ’ ’ x ij thì ràng buộc xij dij trở thành ràng buộc dấu x ij 0. Thêm ràng buộc hình ’ thức yi 0, i. Ràng buộc này tự nhiên thoả do y1 = 0 và yj yi + dij + X ij. Trường hợp không có thời hạn bắt buộc T cho trước, tức là cần tìm thoả hiệp tốt nhất giữa tổng cước phí và tổng thời gian dự án, người ta coi T là tham số và giải quy hoạch tuyến tính tham số để được nghiệm tối ưu như hàm của T. VII. Kiểm tra hiệu chỉnh dự án. Sau khi dùng phương pháp điều hành dự án PERT – CPM xác định được sơ đồ mạng lưới, các biểu đồ và bảng tính các chỉ tiêu và dự án đang được tiến hành, người quản lý luôn phải theo dõi, kiểm tra. Điều kiện lao động thực tế có thể nhiều bất ngờ. Khi cần thiết có thể phải dùng phương pháp PERT – CPM lại, dựa trên các dữ liệu mới, để tính toán cho phần còn lai của dự án. Sau đó điều hành dự án theo các biểu đồ và bảng tính mới. Trang:20
21. CHƯƠNG 2 CƠ SỞ VỀ LÝ THUYẾT ĐỒ THỊ I. Một số khái niệm cơ bản. Lý thuyết độ thị là một lĩnh vực nghiên cứu đã có từ lâu và có nhiều ứng dụng hiện đại. Những tư tưởng cơ bản của lý thuyết đồ thị được đề xuất vào những năm đầu của thế kỷ 18 bởi nhà toán học lỗi lạc người Thụy Sỹ Euler. Chính ông là người sử dụng đồ thị để giải bài toán nổi tiếng về cái cầu ở thành phố Konigsberg. Đồ thị được sử dụng để giải các bài toán trong nhiều lĩnh vực khác nhau. Chẳng hạn, đồ thị có thể sử dụng để xác định các mạch vòng trong vấn đề giải tích mạch điện. Chúng ta có thể phân biệt các hợp chất hóa học hữu cơ khác nhau với cùng công thức phân tử nhưng khác nhau về cấu trúc phân tử nhờ đồ thị. Chúng ta có thể xác định xem hai máy tính trong mạng có thể trao đổi thông tin được với nhau không nhờ mô hình đồ thị của mạng máy tính. Đồ thị có trọng số trên các cạnh có thể sử dụng để giải bài toán như: Tìm đường đi ngắn nhất giữa hai thành phố trong một mạng giao thông. Chúng ta còn sử dụng đồ thị để giải các bài toán về lập lịch, thời khóa biểu, và phân bố tần số cho các trạm phát thanh và truyền hình 1.1. Định nghĩa đồ thị. Đồ thị là một cấu trúc rời rạc bao gồm các đỉnh và các cạnh nối các đỉnh này. Chúng ta phân biệt các loại đồ thị khác nhau bởi kiểu và số lượng cạnh nối hai đỉnh nào đó của đồ thị. Để có thể hình dung được tại sao lại cần đến các loại đồ thị khác nhau, chúng ta sẽ nêu ví dụ sử dụng chúng để mô tả một mạng máy tính. Giả sử ta có một mạng gồm các máy tính và các kênh điện thoại (gọi tắt là kênh thoại) nối các máy tính này. Định nghĩa 1: Đơn đồ thị vô hướng G = (V,E) bao gồm V là tập hợp các đỉnh và E là tập hợp các cặp không có thứ tự gồm hai phần tử khác nhau của V gọi là các cạnh. Trong trường hợp giữa hai máy tính nào đó thường xuyên phải truyền tải nhiều thông tin người ta phải nối hai máy tính này bởi nhiều kênh thoại. Định nghĩa 2: Đa đồ thị vô hướng G = (V,E) bao gồm là tập các đỉnh, và E là họ các cặp không có thứ tự gồm hai phần tử khác nhau của V gọi là các cạnh. Hai cạnh e1 và e2 được gọi là cạnh lặp nếu chúng cùng tương ứng với một cặp đỉnh. Rõ ràng mỗi đơn đồ thị đều là đa đồ thị, nhưng không phải đa đồ thị nào cũng là đơn đồ thị, vì đa đồ thị có thể có 2 (hoặc nhiều hơn) cạnh nối một cặp đỉnh nào đó. Trong mạng máy tính có thể có những kênh thoại nối một máy nào đó với chính nó (chẳng hạn với mục đích thông báo). Mạng như vậy được cho trong hình 3. Khi đó đa đồ thị không thể mô tả được mạng như vậy, bởi vì có những khuyên (cạnh nối một đỉnh với chính nó ). Trong trường hợp này chúng ta cần sử dụng đến các khái niệm giả đồ thị vô hướng, được định nghĩa như sau: Định nghĩa 3: Giả đồ thị vô hướng G = (V,E) bao gồm V là tập các đỉnh, và E là họ các cặp không có thứ tự gồm hai phần tử (không nhất thiết phải khác nhau) của V gọi là các cạnh. Cạnh e được gọi là khuyên nếu có dạng e = (u,u). Trang:21
22. Định nghĩa 4: Đơn đồ thị có hướng G =(V,E) bao gồm V là tập các đỉnh, và E là tập các cặp có thứ tự gồm hai phần tử khác nhau của V gọi là các cung. Nếu trong mạng có thể có đa kênh thoại một chiều, ta phải sử dụng đến khái niệm đa đồ thị có hướng: Định nghĩa 5: Đa đồ thị có hướng G= (V,E) bao gồm V là tập các đỉnh, và E là họ các cặp có thứ tự gồm hai phần tử khác nhau của V gọi là các cung. Hai cung e1 và e2 tương ứng với cùng một cặp đỉnh được gọi là cung lặp. Chúng ta chủ yếu sẽ làm việc với đơn đồ thị vô hướng và đơn đồ thị có hướng. 1.2. Các thuật ngữ cơ bản. Trước tiên ta xét thuật ngữ mô tả các đỉnh và các cạnh của đồ thị vô hướng. Định nghĩa 1: Hai đỉnh u và v của đồ thị vô hướng G được gọi là kề nhau nếu (u,v) là cạnh của đồ thị G. Nếu e = (u,v) là cạnh của đồ thị thì ta nói cạnh này là liên thuộc với hai đỉnh u và v, hoặc cũng nói là cạnh e là nối đỉnh u và đỉnh v, đồng thời các đỉnh u và v sẽ được gọi là các đỉnh đầu của cạnh (u,v). Để có thể biết bao nhiêu cạnh liên thuộc với một đỉnh, ta đưa vào định nghĩa sau: Định nghĩa 2: Ta gọi bậc của đỉnh v trong đồ thị vô hướng là số cạnh liên thuộc với nó và sẽ kí hiệu là deg(v). b c d a f e g Hình 1: Đồ thị vô hướng G. Thí dụ 1: Xét đồ thị trong hình 1, ta có: deg(a)= 1, deg(b)=4, deg(c)=4, deg(f)=3, deg(d)=1, deg(e)=3, deg(g)=0. Đỉnh bậc 0 gọi là đỉnh cô lập. Đỉnh bậc 1 gọi là đỉnh treo. Trong thí dụ trên đỉnh g là đỉnh cô lập, a và d là các đỉnh treo. Bậc của đỉnh có tính chất sau: 2m deg(v) vV Định lý 1: Giả sử G = (V,E) là đồ thị vô hướng với m cạnh. Khi đó. Chứng minh. Rõ ràng mỗi cạnh e = (u,v) được tính một lần trong deg(u) và một lần trong deg(v). Từ đó suy ra tổng tất cả các bậc của các đỉnh bằng hai lần số cạnh. Thí dụ 2: Đồ thị với n đỉnh và mỗi đỉnh có bậc là 6 có bao nhiêu cạnh?. Giải: Theo định lý 1, ta có 2m = 6n. Từ đó suy ra số cạnh của đồ thị là 3n. Hệ quả: Trong đồ thị vô hướng, số đỉnh bậc lẻ (nghĩa là có bậc là số lẻ) là một số chẵn. 2mdeg(v) deg(v) deg(v) vV vO vU Chứng minh: Thực vậy gọi O và U tương ứng là tập đỉnh bậc lẻ và tập đỉnh bậc chẵn của đồ thị. Ta có: Trang:22
23. Do deg(v) là chẵn với v là đỉnh trong U nên tổng thứ hai trong vế phải ở trên là số chẵn. Từ đó suy ra tổng thứ nhất (chính là tổng bậc của các đỉnh bậc lẻ) cũng phải là số chẵn, do tất cả các số hạng của nó là số lẻ, nên tổng này phải gồm một số chẵn các số hạng. Vì vậy, số đỉnh bậc lẻ phải là số chẵn. Ta xét các thuật ngữ tương tự cho đồ thị có hướng. Định nghiã 3: Nếu e = (u, v) là cung của đồ thị có hướng G thì ta nối hai đỉnh u và v là kề nhau, và nói cung (u,v) nối đỉnh u với đỉnh v hoặc cũng nói cung này là đi ra khỏi đỉnh u và đi vào đỉnh v. Đỉnh u(v) sẽ được gọi là đỉnh đầu (cuối) của cung (u, v). Tương tự như khái niệm bậc, đối với đồ thị có hướng ta có khái niệm bán bậc ra (vào) của một đỉnh. Định nghĩa 4: Ta gọi bán bậc ra (bán bậc vào) của các đỉnh v trong đồ thị có hướng là số cung của đồ thị đi ra khỏi nó (đi vào nó) và ký hiệu là deg+(v) (deg(v)). Định lý 2: Giả sử G = (V,E) là đồ thị có hướng. Khi đó deg (v) deg (v) E v V v V Rất nhiều tính chất của đồ thị có hướng không phụ thuộc vào hướng trên các cung của nó. Vì vậy, trong nhiều trường hợp sẽ thuận tiện hơn nếu ta bỏ qua hướng trên các cung của đồ thị. Đồ thị vô hướng thu được bằng cách bỏ qua hướng trên các cung được gọi là đồ thị vô hướng tương ứng với dồ thị có hướng đã cho. 1.3. Đường đi, chu trình, đồ thị liên thông. Định nghĩa 1: Đường đi độ dài n từ đỉnh u đến đỉnh v, trong đó n là số nguyên dương, trên đồ thị vô hướng G =(V,E) là dãy x0, x1, ,xn-1,xn trong đó u =x0, v=xn , (xi, xi+1) E, i= 0, 1, 2 , n-1. Đường đi nói trên còn có thể biểu diễn dưới dạng dãy các cạnh: (x0, x1), (x1, x2), , (xn-1, xn). Đỉnh u gọi là đỉnh đầu còn đỉnh v gọi là đỉnh cuối của đường đi. Đường đi có đỉnh đầu trùng với đỉnh cuối (tức là u= v) được gọi là chu trình. Đường đi hay chu trình được gọi là đơn nếu như không có cạnh nào bị lặp lại. Định nghĩa 2: Đường đi độ dài n từ đỉnh u đến đỉnh v trong đó n là số nguyên dương, trên đồ thị vô hướng G =(V, A) là dãy x0, x1, ,xn-1,xn trong đó u =x0, v=xn , (xi, xi+1) A, i= 0, 1, 2 , n-1. Đường đi nói trên còn có thể biểu diễn dưới dạng dãy các cung: (x0, x1), (x1, x2), , (xn-1, xn). Đỉnh u gọi là đỉnh đầu còn đỉnh v gọi là đỉnh cuối của đường đi. Đường đi có đỉnh đầu trùng với đỉnh cuối (tức là u= v) được gọi là chu trình. Đường đi hay chu trình được gọi là đơn nếu như không có cung nào bị lặp lại. Định nghĩa 3: Đồ thị vô hướng G= (V,E) được gọi là liên thông nếu luôn tìm được đường đi giữa hai đỉnh bất kỳ của nó. Như vậy hai máy tính bấy kỳ trong mạng có thể trao đổi thông tin được với nhau khi và chỉ khi đồ thị tương ứng vơi mạng này là đồ thị liên thông. Định nghĩa 4: Ta gọi đồ thị con của đồ thị G= (V,E) là đồ thị H = (W,F) trong đó W  V và FE. Trong trường hợp đồ thị là liên thông, nó sẽ rã ra thành một số đồ thị con liên thông đôi một không có đỉnh chung. Những đồ thị con liên thông như vậy ta sẽ gọi là các thành phần liên thông của đồ thị. Trang:23
24. Định nghĩa 5: Đỉnh v được gọi là đỉnh rẽ nhánh nếu việc loại bỏ v cùng với các cạnh liên thuộc với nó khỏi đồ thị làm tăng số thành phần liên thông của đồ thị. Cạnh e được gọi là cầu nếu việc loại bỏ nó khỏi đồ thị làm tăng số thành phần liên thông của đồ thị. Định nghĩa 6: Đồ thị có hướng G= (V,A) được gọi là liên thông mạnh nếu luôn tìm được đường đi giữa hai đỉnh bất kỳ của nó. Định nghĩa 7: Đồ thị có hướng G =(V,A) được gọi là liên thông yếu nếu đồ thị vô hướng tương ứng với nó là đồ thị vô hướng liên thông. Rõ ràng nếu đồ thị là liên thông mạnh thì nó cũng là liên thông yếu, nhưng điều ngược lại là không luôn đúng. Định lý1: Đồ thị vô hướng liên thông là định hướng được khi và chỉ khi mỗi cạnh của nó nằm trên ít nhất một chu trình. Chứng minh: Điều kiện cần, giả sử (u, v) là một cạnh của đồ thị. Sự tồn tại đường đi có hướng từ u đến v và ngược lại suy ra (u, v) phải nằm trên ít nhất một chu trình. Điều kiện đủ, thủ tục sau đây cho phép định hướng các cạnh của đồ thi để thu được đồ thị có hướng liên thông mạnh. Giả sử C là chu trình nào đó trong đồ thị. Định hướng các cạnh trên chu trình này theo một hướng đi vòng theo nó. Nếu tất cả các cạnh của đồ thị đã được định hướng thì kết thúc thủ tục. Ngược lại chọn e là cạnh chưa định hướng có chung đỉnh với ít nhất một trong số các cạnh đã định hướng. Theo giả thiết tìm đựơc chu trình C’ chứa cạnh e định nghĩa các cạnh chưa định hướng của C’ theo một hướng dọc theo chu trình này (không định hướng lại các cạnh đã có hướng). Thủ tục trên sẽ lặp lại cho đến khi tất cả các cạnh của đồ thị được định hướng. Khi đó ta thu được đồ thị có hướng liên thông mạnh. II. Biểu diễn đồ thị trên máy tính. Để lưu trữ đồ thị và thực hiện các thuật toán khác nhau với đồ thị trên máy tính cần phải tìm những cấu trúc dữ liệu thích hợp để mô tả đồ thị. Việc chọn cấu trúc dữ liệu nào để biểu diễn đồ thị có tác động rất lớn đến hiệu quả của thuật toán. Vì vậy, việc chọn lựa cấu trúc dữ liệu để biểu diễn đồ thị phụ thuộc vào từng tình huống cụ thể (bài toán và thuật toán cụ thể ). Ở phần này ta sẽ xét một số phương pháp cơ bản để biểu diễn đồ thị trên máy tính, đồng thời cũng phân tích một cách ngắn gọn những ưu điểm cũng như những nhược điểm của chúng. 2.1. Ma trận kề, Ma trận trọng số. Xét đơn đồ thị vô hướng G = (V,E), với tầp đỉnh V= {1, 2, ,n} tập cạnh E = {e1, e2, , em}. Ta gọi ma trận kề của đồ thị G là (0, 1) ma trận A = {aij: i,j = 1, 2, ,n}với các phần tử được xác định theo quy tắc sau đây: aij =0 nếu (i,j) E và aij =1 nếu (i,j) E, i,j =1, 2, ,n Thí dụ1: Ma trận kề củae đồ thị vô hướng cho trong hình 1 là: Trang:24
25. 1 2 3 4 5 6 1 0 1 1 0 0 0 2 1 0 1 0 1 0 3 1 1 0 1 0 0 4 0 0 1 0 1 1 0 1 0 1 0 1 0 0 0 1 1 0 5 6 3 4 2 5 1 6 1 4 2 5 3 6 G G1 Hình 1: Đồ thị vô hướng G và Đồ thị có hướng G1 Các tính chất của ma trận kề: 1. Rõ ràng ma trận kề của đồ thị vô hướng là ma trận đối xứng, tức là a[i, j]= a[j, i], i, j = 1, 2, ,n. Ngược lại, mỗi (0, 1) – ma trận đối xứng cấp n sẽ tương ứng chính xác đến cách đánh số đỉnh (còn nói là: chính xác đến đẳng cấu), với một đơn đồ thị vô hướng n đỉnh. 2. Tổng các phần tử trên dòng i (cột j) của ma trận kề chính bằng bậc của đỉnh i (đỉnh j). p p 3. Nếu ký hiệu aij , i,j = 1, 2, , n. Là các phần tử của ma trận A = A.A .A. p p là thừa số, khi đó aij , i,j = 1, 2, , n. cho ta số đường đi khác nhau từ đỉnh i đến đỉnh j qua p –1 đỉnh trung gian. Ma trận kề của đồ thị có hướng được định nghĩa một cách hoàn toàn tương tự. Thí dụ 2: Đồ thị có hướng G1 cho trong hình 1 có ma trận kề là ma trận sau. 1 2 3 4 5 6 1 0 1 1 0 0 0 2 0 0 0 0 0 0 3 0 1 0 1 0 0 4 0 0 0 0 0 0 5 0 0 0 1 0 1 6 0 0 0 0 1 0 Trang:25
26. Lưu ý rằng ma trận kề của đồ thị có hướng không phải là ma trận đối xứng. Chú ý: Trên đây chúng ta chỉ xét đơn đồ thị. Ma trận kề của đa đồ thị có thể xây dựng hoàn toàn tương tự, chỉ khác, là thay vì ghi 1 vào vị trí a[i, j] nếu (i, j) là cạnh của đồ thị, chúng ta sẽ ghi k là số cạnh nối hai đỉnh i và j. Trong rất nhều vấn đề ứng dụng của lý thuyết đồ thị, mỗi cạnh e= (u, v) của đồ thị được gán với một con số c(e) (còn viết là c (u, v)) gọi là trọng số của cạnh e. Đồ thị trong trường hợp như vậy được gọi là đồ thị trọng số. Trong đồ thị có trọng số, thay vì ma trận kề, để biểu diễn đồ thị ta dùng ma trận trọng số. C = c[i,j], i,j=1,2, ,n. Với c(i, j)= c[i, j], nếu (i, j) E và c[i, j] = nếu (i, j) E Trong đó số , tùy từng trường hợp cụ thể, có thể được đặt bằng một trong các giá trị sau: 0, + , - . Ưu điểm lớn nhất của phương pháp biểu diễn đồ thị bằng ma trận kề (hoặc bằng ma trận trọng số) là để trả lời câu hỏi: hai đỉnh u, v có kề nhau trên đồ thị hay không, chúng ta chỉ phải thực hiện một phép so sánh. Nhược điểm lớn nhất của phương pháp này là không phụ thuộc vào số cạnh của đồ thị, ta luôn phải sử dụng n2 đơn vị bộ nhớ để lưu trữ ma trận kề của nó. 2.2. Danh sách cạnh (cung). Trong trường hợp đồ thị thưa (đồ thị có số cạnh m thỏa mãn bất đẳng thức m < 6n) người ta thường dùng cách biểu diễn đồ thị dưới dạng danh sách cạnh. Trong cách biểu diễn đồ thị bởi danh sách cạnh (cung) chúng ta sẽ lưu trữ danh sách tất cả các cạnh (cung) của đồ thị vô hướng (có hướng). Mỗi cạnh (cung) e = (x, y) của đồ thị sẽ tương ứng với hai biến Dau[e], Cuoi[e]. Như vậy, để lưu trữ đồ thị ta cần sử dụng 2m đơn vị bộ nhớ. Nhược điểm của cách biểu diễn này là để xác định những đỉnh nào của đồ thị là kề với một đỉnh cho trước chúng ta phải làm cỡ m phép so sánh (khi duyệt qua danh sách tất cả các cạch của đồ thị). Chú ý: trong trường hợp đồ thị có trọng số ta cần thêm m đơn vị bộ nhớ để lưu trữ trọng số của các cạch. 2.3. Danh sách kề. Trong rất nhiều vấn đề ứng dụng của lý thuyết đồ thị, cách biểu diễn đồ thị dưới dạng danh sách kề là cách biểu diễn thích hợp nhất được sử dụng. Trong cách biểu diễn này, với mỗi đỉnh v của đồ thị chúng ta lưu trữ danh sách các đỉnh kề với nó, mà ta sẽ ký hiệu là Ke(v), tức là Ke(v)={u V: (v, u) E} khi đó vòng lặp thực hiện với mỗi một phần tử trong danh sách này theo thứ tự các phần tử được xắp xếp như sau: For u Ke(v) do Chẳng hạn, trên PASCAL có thể mô tả danh sách này như sau (Gọi là cấu trúc Forward star ): Const m = 100; {m – số cạnh} n = 100; {n – số đỉnh} var Ke: array {1 m} of integer ; Tro: array {1 n+1} of integer ; Trang:26
27. Trong đó Tro [i] ghi nhận vị trí bắt đầu của danh sách kề của đỉnh i, i = 1, 2, n, Tro[n+1] = 2m + 1. III. Bài toán tìm đường đi ngắn nhất. Trong các ứng dụng thực tế, bài toán tìm đường đi ngắn nhất giữa hai đỉnh của đồ thị liên thông có một ý nghĩa to lớn, có thể dẫn về bài toán như vậy nhiều bài toán thực tế quan trọng. Ví dụ, bài toán chọn một hành trình tiết kiệm nhất (theo tiêu chuẩn khoảng cách hoặc thời gian hoặc chi phí) trên một mạng giao thông đường bộ, đường thủy hoặc đường không; bài toán chọn một phương pháp tiết kiệm nhất để đưa một hệ động lực lực từ trạng thái xuất phát đến một trạng thái đích, bài toán lập lịch thi công các công đoạn trong công trình thi công lớn, bài toán lựa chọn đường truyền tin với chi phí nhỏ nhất trong mạng thông tin, hiện nay có rất nhiều phương pháp để giải các bài toán như vậy. Thế nhưng thông thường các thuật toán được xây dựng dựa trên lý thuyết đồ thị tỏ ra là các thuật toán có hiệu quả nhất. Trong phần này ta sẽ xét một số thuật toán như vậy. 3.1. Các khái niệm mở đầu. Trong phần này ta chỉ xét đồ thị có hướng G = (V,E), |V| = n, |E| = m với các cung được gán trọng số, nghĩa là mỗi cung (u, v) thuộc E của nó đựơc đặt tương ứng với một số thực a (u, v) gọi là trọng số của nó, chúng ta sẽ đặt a(u, v)= , nếu (u, v) E. Nếu dãy v0, v1, vp. là một đường đi trên G, đồ thị độ dài của nó được định nghĩa là tổng sau. P a(Vi 1 ,Vi ) i 1 Tức là, đồ dài của đường đi chính là tổng trọng số trên các cung của nó. (chú ý rằng nếu chúng ta gán trọng số cho tất cả các cung đều bằng 1, thì ta được định nghĩa độ dài của đường đi như là số cung của đường đi giống như các phần trước ta đã xét ). Bài toán tìm đường đi ngắn nhất trên đồ thị dưới dạng tổng quát có thể phát biểu như sau: Tìm đường đi có độ dài nhỏ nhất từ một đỉnh xuất phát s V đến đỉnh cuối (đích) t V. Đường đi như vậy ta sẽ gọi là đường đi ngắn nhất từ s đến t còn độ dài của nó ta sẽ ký hiệu là d(s, t) và còn gọi là khoảng cách từ s đến t (khoảng cách định nghĩa như vậy có thể là số âm ). Nếu như không tồn tại đường đi từ s đến t thì ta sẽ đặt d(s, t) = . Rõ ràng, nếu như mỗi chu trình trong đồ thị đều có độ dài dương, thì trong đường đi ngắn nhất không có đỉnh nào bị lặp lại (đường đi không có đỉnh nào lặp lại sẽ được gọi là dường đi cơ bản). Mặt khác, nếu đồ thị có chu trình với độ dài âm (chu trình như vậy, để ngắn gọn ta gọi là chu trình âm ) thì khoảng cách giữa một số cặp đỉnh nào đó của đồ thị có thể là không xác định, bởi vì bằng cách đi vòng theo chu trình này một số đủ lớn lần, ta có thể chỉ ra đường đi giữa các đỉnh này có độ dài nhỏ hơn bất cứ số thực cho trước nào. Trong các trường hợp như vậy, có thể đặt vấn đề tìm đường đi cơ bản ngắn nhất, tuy nhiên bài toán đặt ra sẽ trở nên phức tạp hơn rất nhiều, bởi vì nó chứa bài toán xét sự tồn tại đường đi Hamilton trong đồ thị như là một trường hợp riêng. Trang:27
28. Trước hết cần chú ý rằng nếu biết khoảng cách từ s đến t, trong trường hợp trọng số không âm, có thể tìm được một cách dễ dàng, để tìm đường đi chỉ cần để ý là đối với cặp đỉnh s, t V tùy ý (s t) luôn tìm được v đỉnh sao cho: d(s, t) = d(s, v) + a(v, t). Thực vậy, đỉnh v như vậy chính là đỉnh đi trước đỉnh t trong đường đi ngắn nhất từ s đến t. Tiếp theo ta lại có thể tìm được đỉnh u sao cho d(s, v)= d(s, u) + a(u, v), từ giả thiết về tính không âm của các trọng số dễ dàng suy ra rằng dãy t, v, u, không chứa đỉnh lặp lại và chứa đỉnh kết thúc ở đỉnh s. Rõ ràng dãy thu được xác định (nếu lật ngược thứ tự các đỉnh trong nó) đường đi ngắn nhất từ s đến t. 3.2. Đường đi ngắn nhất xuất phát từ một đỉnh . Phần lớn các thuật toán tìm khoảng cách giữa hai đỉnh s và t được xây dựng nhờ kỹ thuật tính toán mà ta có thể mô tả đại thể như sau: từ ma trận trọng số a{u, v}, u, v V, ta tính cận trên d{v} của khoảng cách từ s đến tất cả các đỉnh v V , mỗi khi phát hiện . d{u}+a[u, v] < d[v] (1) Cận trên d[v] sẽ được là tốt lên : d[v]=d[u] + a[u, v]. Quá trình đó sẽ kết thúc khi nào chúng ta không làm tốt thêm được bất cứ cận trên nào. Khi đó rõ ràng giá trị của mỗi d[v] sẽ cho ta khoảng cách từ đỉnh được gọi là nhãn của đỉnh v, còn việc tính lại các lại các cận trên này sẽ gọi là phép gán nhãn cho đồ thị và toàn bộ thủ tục thường gọi là thủ tục gán nhãn. Nhận thấy rằng để tính khoảng cách từ s đến t, ở dây, ta phải tính khoảng cách từ s đến tất cả các đỉnh còn lại của đồ thị. Hiện nay vẫn chưa biết thuật toán nào cho phép tìm đường đi ngắn nhất giữa hai đỉnh làm việc thật sự hiệu quả hơn những thuật toán tìm đường đi ngắn nhất từ một đỉnh đến tất cả các đỉnh còn lại. Sơ đồ tính toán mà ta vừa mô tả còn chưa là xác định bởi vì còn phải chỉ ra thứ tự chọn các đỉnh u và v để kiểm tra điều kiện (!) thứ tự chọn này có ảnh hưởng rất lớn đến hiệu quả của thuật toán . Bây giờ ta sẽ mô tả thuật toán Ford-Bellman tìm đường ngắn nhất từ đỉnh s đến tất cả các đỉnh còn lại của đồ thị. Thuật toán làm việc trong trường hợp trọng số của các cung là tùy ý, nhưng giả thiết rằng trong đồ thị không có chu trình âm . Procedure Ford-Bellman; (* Đầu vào: đồ thị có hướng G=(V,E) với n đỉnh s V là đỉnh xuất phát. a[u,v],u,v V ma trận trọng số : Giả thiết : đồ thị không có chu trình âm: Đầu ra : khoảng cách từ đỉnh s đến tất cả các đỉnh còn lại d[v], v Truoc[v],v V , ghi nhận đỉnh trước v trong đường đi ngắn nhất từ s đến v *) Begin (* Khởi tạo *) for v V do begin Trang:28
29. 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 đúng đắn của thuật toán có thể chứng minh trên cơ sở nguyên lý tối ưu của qua hoạch động rõ ràng là độ phước tạp tính toán của thuật toán là O(n3) lưu ý ràng chúng ta có thể chấm dứt vòng lặp theo K khi phát hiện trong quá trình thực hiện hai vòng lặp trong không có biến d[t] nào bị đổi giá trị việc này có thể xảy ra với k d[u]+a[u, v] then begin d[u]:= d[u]+a[u, v]; truoc[v]:=u; end; trong trường hợp này ta thu được thuật toán với độ phức tạp O (n.m). 3.3. Đường đi ngắn nhất giữa tất cả các cặp đỉnh Rõ ràng ta có thể giải bài toán tìm đường đi ngắn nhất giữa tất cả các cặp đỉnh của đồ thị bằng cách sử dụng n lần thuật toán mô tả ở mục trước, trong đó ta sẽ chọn s lần lượt là các đỉnh của độ thị. Rõ ràng, khi đó ta thu được thuật toán với độ phức tạp là O(n3) (nếu sử dụng thuật toán Ford-Bellman) hoặc O(n3) đối với trường hợp trọng số không âm hoặc đồ thị không có chu trình. Trong trường hợp tổng quát, sử dụng thuột toán Ford-Bellman n lần không phải là cách làm tốt nhất. Ở đây ta sẽ mô tả một thuật toán giải bài toán trên với độ phức tạp tính toán O(n3): Thuật toán Floyd. Thuật toán được mô tả dưới đây. Procedure Floyd (* Tìm đường đi ngắn nhất giữa các cặp đỉnh Đầu vào:Đồ thị cho bởi ma trận trọng số a{i,j},i,j=1,2 .,n. .Đầu ra:Ma trận đường đi ngắn nhất giữa các cặp đỉnh d{i, j}=1,2 .n, trong đó d{i, j} cho độ dài đường đi ngắn nhất từ i đến j. Ma trận ghi nhận đường đi P{i,j},i,j=1,2 n. Trong đó p{i,j}ghi nhận đỉnh đi trước đỉnh j Trong đường đi ngắn nhất từ i đến j. Trang:29
30. *) Begin (*khởi tạ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 lặ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; Rõ ràng độ phức tạp tính toán của thuật toán là O(n3). Trang:30
31. CHƯƠNG 3 BÀI TOÁN LẬP LỊCH THI CÔNG CÔNG TRÌNH I. Bài toán. Việc thi công một công trình lớn được chia ra làm n công đoạn, đánh số từ 1 đến n. có một số công đoạn mà việc thực hiện nó chỉ được tiến hành sau khi một số công đoạn nào đó đã hoàn thành. Đối với mỗi công đoạn i biết t[i] là thời gian cần thiết để hoàn thành nó (i = 1, 2, n). Ta có thể xay dựng đồ thị có hướng n đỉnh biểu diễn hạn chế về trình tự thực hiện các công việc sau: mỗi đỉnh của đồ thị tương ứng với một đồ thị, nếu công việc i phải được thực hiện trước công đoạn j thì trên đồ thị có cung (i, j), trọng số trên cung này được gán bằng t[i]. Thêm vào đồ 2 đỉnh 0 và n +1 tương ứng với hai sự kiện đặc biệt: đỉnh số 0 tương ứng với công đoạn Lễ khởi công, nó phải được thực thực hiện trước tất cả các công đoạn khác, và đỉnh n+1 tương ứng với công đoạn Cắt băng khánh thành công trình, nó phải thực hiện sau tất cả các công đoạn, với t[0] = t[n+1] = 0 (trên thực tế chỉ cần nối đỉnh 0 với tất cả đỉnh có bán bậc vào bằng 0 và nối tất cả các đỉnh có bán bậc ra bằng 0 với đỉnh n+1). Gọi đồ thị thu được là G. Rõ ràng bài toán đặt ra vấn đề bài toán tìm đường đi dài nhất từ đỉnh 0 đến tất cả các đỉnh còn lại trên đồ thị G. Do đồ thị G rõ ràng không chứa chu trình, nên để giả bài toán đặt ra có thể áp dụng các thuật toán được nêu ở trên. 1. Thí dụ: Ta có bảng các hạng mục được cho trong bảng dưới đây. Hạng mục t[i] Hạng mục phải hoàn thành trước 1 10 2 15 1 0 1 : 0 3 10 0 1 2 : 10 4 30 2,3 0 3 : 0 5 1 2 4 0 1 2 4 : 25 6 15 2,3 0 1 2 4 5 : 55 7 20 5,6 0 3 6 : 10 8 10 5 0 1 2 4 5 : 55 Đưa về bài toán đồ thị có hướng, các đỉnh là các hạng mụ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) Cách giải quyết: * Thêm hai đỉnh 0 và đỉnh 9 ta thu được một đồ thị có hướng trong đó trọng số t[i] là cạnh xuất phát từ i * Tìm đường đi dài nhất thì - Đổi dấu trọng số Trang:31
32. - Tìm đường đi ngắn nhất xuất phát từ 0 Lặp VH 1 2 3 4 5 6 7 8 9 Ktạ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ử dụng thuật toán Dijkstra để tình thời gian các công việc bắt đầu và kết thúc dự án. Chương trình thi công công trình không sử dụng trực tiếp thuật toán này mà còn phụ thuộc vào các công việc làm đầu tiên, vì vậy công việc đầu tiên là ta phải xác định công việc nào là công việc đầu tiên, việc xác định công việc đầu tiên cũng rất đơn giản, khi ta nhập số liệu thì công việc đầu tiên thì không có công việc nào làm trước nó. Để giải bài toán trên ta có thể dùng nhiều phương pháp. Nhưng trong đề tài này chúng tôi sử dụng thuật toán Dijkstra. II. Thuật toán Dijkstra. Thuật toán Dijkstra được phát biểu như sau: Trong trường hợp trọng số trên các cung là không âm do Dijkstra đề nghị để giải bài toán tìm đường đi ngắn nhất từ dỉnh s đến các đỉnh còn lại của đồ thị . Thuật toán được xây dựng trên cơ sở gán cho các đỉnh các nhãn tạm thời. Nhãn của mỗi đỉnh cho biết cận trên của độ dài đường đi ngắn nhất từ s đến nó. Các nhãn này sẽ được biến đổi theo một thủ tục lặp, mà ở mỗi bước lặp có một nhãn tạm thời trở thành nhãn cố định. Nếu nhãn của một đỉnh nào đó trở thành cố định thì nó sẽ cho ta không phải là cận trên mà là độ dài đường đi ngắn nhất từ đỉnh s đến nó. Thuật toán được mô tả như sau. Procedure Dijkstra; (* Đầu vào: Đồ thị có hướng G=(V, E) với n đỉnh s V là đỉnh xuất phát a[u, v], u, v V, ma trận trọng số Giả thiết: a[u, v] >= 0, u, v V Đầu ra: khoảng cách từ d(s) đến tất cả các đỉnh còn lại d[v], v V Truoc [v], v V, ghi nhận đỉnh trước v trong đường đi ngắn nhất từ s đến v *) Begin (* Khởi tạo *) for v V do Begin d[v] := a[s, v]; Trang:32
33. Truoc[v] := s; End; d[s] := 0; T := V \ {s} (*Tập các đỉnh có nhãn tạp thời *) (* Bước lặp*) while T d[u] + a[u, v] then Begin D[v] := d[u] + a[u, v] Truoc [v] := u; End; End; End; Định lý 1: Thuật toán Dijkstra tìm được đường đi ngắn nhất trên đồ thị sau thời gian cớ O(n2). Chứng minh: Trước hết ta chứng minh là thuật toán tìm đường đi ngắn nhất từ đỉnh s đến các đỉnh còn lại của đồ thị. Giả sử rằng ở một bước lặp nào đó các nhãn cố định cho ta độ dài các đường đi từ s đến các đỉnh có nhãn cố định, ta sẽ chứng minh rằng ở lần lặp tiếp theo nếu đỉnh u* thu được nhãn cố định d(u*) chính là độ dài đường đi ngắn nhất từ s đến u*. Ký hiệu S: là tập hợp có nhãn cố định còn S2 là tập các đỉnh có nhãn tạm thời ở bước lặp đang xét. Kết thúc mỗi bước lặp nhãn tạm thời d(v) cho ta độ dài của đường đi ngắn nhất từ s đến v chỉ qua những đỉnh nằm hoàn toàn trong tập S1. Giả * sử rằng đường đi ngắn nhất từ s đến u không nằm trong tập S1, tức là nó đi qua ít nhất một đỉnh của tập S2. Gọi z S2 là đỉnh đầu tiên như vậy trên đường đi này . Do trọng số trên các cung là không âm, nên đoạn đường từ z đến u* có độ dài L > 0 và d(z) < d(u*) – L < d(u*). Bất đẳng thức này là mâu thuẫn với cách xác định u* là đỉnh có nhãn tạm thời * nhỏ nhất. Vậy đường đi ngắn nhất từ đỉnh s đến u phải nằm chọn trong S1, và vì * thế d[u ] là độ dài của nó. Do ở lầm lặp đầu tiên S1 = {s} và sau mỗi lần lặp ta * chỉ thêm vào S1 một đỉnh u nên giả thiết là d(v) cho độ dài đường đi ngắn nhất từ s đến v với mọi v S1 là đúng với bước lặp đầu tiên. Theo qui nạp suy ra thuật toán cho đường đi ngắn nhất từ s đến mọi đỉnh của đồ thị. Bây giờ ta đánh giá số phép toán cần thực hiện theo thuật toán. Ở mỗi bước lặp để tìm ra đỉnh u cần thực hiện O(n) phép toán, và để gán nhãn lại cũng phải thực hiện một số lượng phép toán cũng la O(n). Thuật toán phải thực hiện n- 1 bước lặp. Vậy thời gian tính toán của thuật toán là cỡ O(n2). Trang:33
34. Thí dụ: Tìm đường đi ngắn nhất từ đỉnh 1 đến các đỉnh còn lại của đồ thị ở hình dưới: (7) 2 3 6 (5) (1) (1) (2) (1) (1) (4) 1 (2) 4 (3) 5 Minh họa thuật toán Dijkstra Kết quả tính toán được trình bày trong bảng dưới đây. Bước lặp Đỉnh 1 Đỉnh 2 Đỉnh 3 Đỉnh 4 Đỉnh 5 Đỉnh 6 Khởi tạ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 - - - - - - Chú ý: 1) Nếu chỉ cần tìm đường đi ngắn nhất từ s đến t nào đó thì có thể kết thúc thuật toán khi đỉnh t trở thành đỉnh có nhãn cố định. Trang:34
35. * Sơ đồ thuật toán Dijkstra. Bắt Đầu Số phần tử:= số đỉnh -1; i:=1; Y i < đnguồn N Tập đỉnh[i]:=i; Đđ-đến[i]:=kc[đnguồn, i]; Đđ- trực tiếp đến[i]:=đnguồn; i:=i+1; i:=đnguồn +1 Y i số đỉnh N Tập đỉnh[i]:=i; Đđ-đến[i]:=kc[đnguồn, i]; Đđ- trực tiếp đến[i]:=đỉnh nguồn; i:=i+1; (1) Trang:35
36. (1) Y j số đỉnh -2 N Min:= đđ-đến[đỉnh[1]]; Vị trí :=1; Y i k N Đđ-đến[đỉnh[i]] <min; N Min:= đđ-đến[đỉnh[i]]; Vị trí :=i; Y i:=i+1 Đỉnh xét:=đỉnh[vị trí]; Đỉnh[vị trí]:=đỉnh[spt]; Spt:=spt-1; i:=1 Y i spt N (3) (2) (4) Trang:36
37. (2) (4) (3) X:=đỉnh[i] Y Đđ-đến[x] > Đđ- đến[đỉnh xét]+ kc[đỉnh xét,x]; N Đđ-đến[x]:=Đđ-đến[đỉnh xét + kc[đỉnh xét,x]]; i:=i+1; Kết Thúc III. Giải quyết bài toán. Sau khi đưa bài toán về dạng đồ thị có hướng, với mỗi đỉnh là một hạng mục ta có thể tiến hành như sau: - Chuyển thành ma trận trọng số có dạng a(i, j), với hạng mục i phải được thi công trước hạng mục j, giá trị của a(i, j) cho biết thời gian hạng mục i làm xong. - Đổi dấu giá trị của ma trận: ví dụ a(i, j) = -a(i, j) - Ap dụng thuật toán Dijkstra. - Kết thúc thuật toán ta thu được d[u] . Trang:37
38. - Đổi dấu giá trị d[u] vừa thu được: d[v] = -d[u] - Giá trị d[v] chính là đường đi dài nhất từ 0 đến đỉnh v, khi đó d[v] cho ta thời điểm sớm nhất có thể bắt đầu thực hiện công đoạn v, nói riêng d[n+1] là thời điểm sớm nhất có thể cắt băng khánh thành toàn bộ công trình. Tương tự như trên ví dụ trên khi kết thúc toàn bộ dự án, kết quả thu được như sau: Giả sử lễ khởi công dự án là 1-1-2003 Thì sau 87 ngày (Giả sử đơn vị tính là ngày) ta có thể cắt băng khánh thành toàn bộ dự án. IV. Điều khiển nhân lực Các hoạt động không găng được phép xê dịch nhất định, nhất là khi FFij = TFij. Có thể sắp đặt chúng đáp ứng các yêu cầu khác nữa. Ngoài thời gian ra, chẳng hạn nhân lực, nguyên liệu, chi phí Về mặt toán học xử lý yêu cầu loại nào cũng vậy. Ở đây ta nói theo ngôn ngữ nhân lực chẳng hạn. Thí Dụ III.1. Giả sử nhân lực cho các hoạt động của dự án ở Thí Dụ II.2 đòi hỏi như sau: Hoạt động Số nhân Hoạt động số nhân công cô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 Chú ý rằng tại thời điểm hai hoạt động cùng tiến hành thì số nhân lực cần là tổng hai số công nhân. Vì vậy cần phải sắp xếp khéo các hoạt động không găng để đòi hỏi tổng nhân công của cả dự án ít (tạm coi là mỗi người biết làm mọi việc). Việc sắp xếp tối ưu là phức tạp, đến nay ta sử dụng biểu đồ thời gian biểu diễn thêm nhân lực để sắp xếp theo trực quan. H.1.6 (a) biểu diễn tổng công nhân cần ở mỗi thời điểm nếu tất cả các hoạt động không găng xếp vào lúc sớm nhất có thể, còn H.1.6 (b) là tương ứng khi xếp vào lúc muộn nhất có thể. Hai biểu đồ này nên vẽ thẳng dưới H.1.5 nữa. Sắp đặt sớm nhất ở hình (a) cho thấy ở mỗi thời điểm dự án cần nhiều nhất là 10 công nhân còn ở sắp đặt muộn nhất (b) là 12 công nhân. Ở hai phương án này, số công nhân cần ở các thời điểm không đều. Theo trực quan ta chỉnh lại từ (a) như sau: chuyển hoạt động (4, 6) đến thời điểm muộn nhất có thể, chuyển (4, 7) đến ngay sau khi (5, 7) kết thúc. Kết quả được vẽ lại ở biểu đồ H.1.7. (chú ý là hoạt động (1, 2) và (2, 4) không cần công nhân nên không cần vẽ.). Trang:38
39. Chương IV GIỚI THIỆU NGÔN NGỮ LẬP TRÌNH Visual Basic là một ngôn ngữ lập trình khá phổ biến hiện nay, nó là một công cụ rất tiện lợi cho hầu hết các chương trình ứng dụng, các chương trình sử lý theo yêu cầu của người dùng. Điều đặc biệt của ngôn ngữ Visual Basic đó là nó dùng ngay giao diện người dùng đồ họa , hay GUI (Graphical User Interface). Điều đặc biệt, Visual Basic cho phép bổ xung các menu, hộp văn bản, nút lệnh, nút tùy chọn (cho các lựa chọn loại trừ), các hộp kiểm tra (cho các lựa chọn không loại trừ), các hộp danh sách, thanh cuốn, các hộp tập tin và thư mục cho các cửa sổ trống. Bạn có thể dùng các lưới (Grid) để quản lý dữ liệu theo bảng. Bạn có thể truyền thông với các ứng dụng Windows khác, và có thể là quan trọng nhất, bạn sẽ có một phương pháp dễ dàng để người dùng điều kiểm và truy cập các cơ sở dữ liệu. (Những thành phần đó đượcVisual basic gọi là Điều Kiểm (control)). Có thể có nhiều cửa sổ trên màn hình. Các cửa sổ này có toàn quền truy cập clipboard và các thông tin trong hầu hết các ứng dụng Windows khác chạy cùng lúc. Bạn có thể dùng Visual Basic để truyền thông với các ứng dụng khác đang chạy dưới Windows. Dùng phiên bản hiện đại nhất của công nghệ COM/OLE trong Windows. Phương thức lập trình của Visual Basic là thiết kế trước, viết lệnh sau. Vì vậy môi trường làm việc không phức tạp như các ngôn ngữ lập trình khác. Chúng bao gồm các đối tượng. I. Cửa sổ thuộc tính. 1. Một số thuộc tính của đối tượng Form. Thuộc tính Thể hiện với giá trị xác lập Name Dùng để đặt tên cho Form, tên này sẽ được dùng cho thủ tục mà bạn viết mã. Appearance Quy định cách thể hiện của Form 0 Flat (Form phẳng) 1 3D (Form nổi) Backcolor Chọn màu nền của Form Bordestyle Quy định kiểu khung của Form Caption Quy định tiêu đề của Form Controlbox Nếu đặt là true thì cửa sổ có Controlmenubox. Nếu đặt là False thì cửa sổ không có Controlmenubox. Icon Dùng Icon có biểu tượngnhư thế nào khi bạn click nút minimize Max buttion Nếu đặt là true thì cửa sổ có nút Maximize Nếu đặt là false thì cửa sổ không có nút Maximize Min buttion Nếu đặt là true thì cửa sổ có nút Minimize Nếu đặt là false thì cửa sổ không có nút Miniimize Moveable Nếu đặt là true thì có thể nhấn Mouse vào tiêu đề và kéo đi nơi khác, nếu False thì không kéo đi được Showintaskbar True: cửa sổ này hiện lên tên của nó cũng thể hiện trong Trang:39
40. taskbar của Ưindớ, nếu False thì không. Visiable True: Thấy Form False: ẩn Form Windowstate Quy định kích thước Form 0 Bình thường 1 Cực tiểu 2 Cực đại 2. Một số thuộc tính của cửa sổ Lable Thuộc tính Thể hiện với giá trị xác lập Name Tên của lable Alignment Canh nội dung của lable 0 Canh trái 1 Canh phải 2 Canh giữa Autosize Bạn chon true nó tự động co giãn cho vừa nội dung của nó Chọn false thì bạn tự điều chỉnh cho vừa Backcolor Quy định màu nền cho lable Caption Ghi chữ trên lable Font Chọn kiểu chữ cho lable Fontcolor Quy định màu chữ trên lable 3. Một số thuộc tính của đối tượng Textbox. Thuộc tính Thể hiện với giá trị xác lập Name Đặt tên cho Textbox Alignment Canh nội dung của textbox 0 Canh trái 1 Canh phải 2 Canh giữa Appearance Quy định cách thể hiện của Textbox 0 flat bình thường 1 3D 3 chiều Backcolor Quy định màu nền cho Textbox Font Chọn kiểu chữ cho textbox Forecolor Quy định màu chữ trên textbox Maxlength Quy định số ký tự tối đa nhập vào textbox Multiline True: có thể xuồng hàng khi chiều ngang không đủ False: không xuống hàng Scrollbar Dùng để xác lập hộp textbox không có thanh cuốn dọc, ngang hặc cả hai với điều kiện thuộc tính Mulltiline = true Text Bạn hãy xóa chữ và để trống Visible Quy định text có được nhìn thấy trên form hay không True: nhìn thấy, False: không nhìn thấy Trang:40
41. 4. Thuộc tính của đối tượng Commandbox Thuộc tính Thể hiện với giá trị xác lập Name Đặt tên cho đối tượng Commandbox Caption Làm tiêu đề cho nút Font Chọn font cho nút Visible True: nút nhìn thấy False: nút không nhìn thấy 5. Thuộc tính đối tượng Checkbox. Thuộc tính Thể hiện với giá trị xác lập Name Đặt tên cho checkbox Alignment Canh nội dung của checkbox Appearance Quy định cách thể hiện của Checkbox Backcolor Quy định màu nền cho checkbox Font Chọn kiểu chữ cho checkbox Caption Dòng tiêu đề cho checkbox Forecolor Quy định màu chữ cho checkbox Value 0: Không chọn 1: trạng thái chọn 2: Trạng thái xám Visible True: Không nhìn thấy False: nhìn thấy 6. Thuộc tính hay dùng của đồi tượng picturebox Thuộc tính Thể hiện với giá trị xác lập Name Tên cho đối tượng picturebox Autosize True: tự động đặt lại kích thước của đối tượng cho vừa với kích thước của hình đã được đặt vào False: nếu hình đặt vào lớn hơn kích thước thì hình này sẽ bị che khuất Picture Dùng để lưu trứ bức hình bạn muốn trình bày Align Dùng để quy định cách bố trí đặc biệt của picture trên form Autoredraw Hình sẽ không bị xóa đi khi bạn thu nhỏ hay phóng to kích thước Fillcolor Quy định màu tô cho các phương thức đồ họa Fillstyle Quy định dạng màu tô Drawstyle Quy định đường nét vẽ Drawith Quy định độ dày nét vẽ 7. Một số thuộc tính hay dùng của đối tượng Image. Thuộc tính Thể hiện với giá trị xác lập Name Đặt tên cho đối tượng Image Picture Tương tự như thuộc tính picture của đói tượng picturebox Trang:41
42. Borderstyle Quy định kiểu khung có (1) hoặc không có khung(0) Stretch True: hình sẽ tự động co giãn sao cho vừa vặn trong đối tượng False: đối tượng sẽ tự điruf chỉnh cho vừa với hình 8. Một số thuộc tính hay dùng của đối tượng Listbox. Thuộc tính Thể hiện với giá trị xác lập Name Đặt tên cho đối tượng Listbox Colums Dùng để thể hiện listbox có bao nhiêu cột, mặc nhiên là 1 Integranlhieght True: Listbox sẽ tự điều chỉnh kích thước sao cho không có mục nào bị che khuất nửa chừng False: thì sẽ chính xác như khi bạn thiết kế Listcount Xác địgh danh sách có bao nhiêu mục, bạn chỉ có thể đọc chứ không đặt lại giá trị List Quy định một danh sách cho Listbox Multiselect Quy định mỗi lần chỉ có thể chọn một hay nhiều mục Listindex Mục đang có focut trong danh sách là mục thứ bao nhiêu Selcount Cho biết hiện đang có bao nhiêu mục được chọn trong danh sách Sorted True: Sắp xếp danh sách theo thứ tự False: sắp xếp như trình tự bạn đưa vào 9. Một số thuộc tính hay dùng của đối tượng Combobox Thuộc tính Thể hiện với giá trị xác lập Name Đặt tên cho đối tượng combobox Style Quy định kiểu cho combobox Sorted True: Sắp xếp theo thứ tự Alphabet False: sắp xếp như trình tự bạn đưa vào 10. Một số thuộc tính hay dùng của đối tượng Timer Thuộc tính Thể hiện với giá trị xác lập Name Đặt tên cho đối tượng Timer Enable True: cho phép phát ra sự kiện thời gian False: ngược lại Interval Là gí trị số dùng để quy định bao nhiêu lâu thì phát ra sự kiện thời gian. Đơn vị tính là miligiây. Nếu đặt là 0 thì đối tượng timer không hoạt động 11. Một số thuộc tính hay dùng của đối tượng frame Thuộc tính Thể hiện với giá trị xác lập Name Đặt tên cho đối tượng frame Caption Nội dung của tiêu đề frame 12. Một số thuộc tính hay dùng của đối tượng Button Trang:42
43. Thuộc tính Thể hiện với giá trị xác lập Name Đặt tên cho đối tượng option button Alignment Quy định vị trí nút chọn 0: nút chọn nằm bên trái tiêu đề 1: nút chọn nằm bên phải tiêu đề Caption Tiêu đề của option button Font Chọn font chữ cho tiêu đề Value Nếu giá trị này bằng true thì option này đang được chọn, ngược lại thì nó đang ở vị tró không được chọn 13. Một số thuộc tính hay dùng của đối tượng line Thuộc tính Thể hiện với giá trị xác lập Name Đặt tên cho đối tượng line Bordercolor Quy định màu cho đường thẳng Borderwith Quy định độ dày của đường thẳng Borderstyle Quy định kiểu đường thẳng có giá trị từ 0 đến 7 X1, X2, X3, X4 Xác định tọa độ của đường thẳng trên form Drawmode Quy định mode để vẽ đường 14. Một số thuộc tính hay dùng của đối tượng Shape Thuộc tính Thể hiện với giá trị xác lập Name Đặt tên cho đối tượng shape Shape Quy định một số hình dáng 0: Hình chữ nhật 1: Hình vuông 2: hình ellipse 3: Hình tròn 4: Hình chữ nhật tròn góc 5: Hình vuông tròn góc Fillstyle Quy định các kiểu vẽ có giá trị từ 0 đến 7 Fillcolor Quy định màu tô bên trong của hình Borderstyle Quy định kiểu kiểu đường viền của hình Borderwith Quy định độ dày nét của hình Berdercolor Quy định màu đường viền Backstyle Quy định màu nền của hình Backcolor Quy định màu của phần nền khi backstyle là Opque II. Biến, Kiểu biến và cách khai báo 1. Biến Tương tự như các ngôn ngữ lập trình khác, biến là một yếu tố không thể thiếu, biến như là một phần của bộ nhớ, muốn dử dụng ta phải khai báo. Tên biến không dài quá 255 ký tự, có tính gợi nhớ, không dùng các ký hiệu, tránh dùng các từ khóa của VB 2. Kiểu của biến Trang:43
44. Khi khai báo biến ta phải khai bóa kiểu cho nó. Trong VB, người ta dùng một loại tiếp ngữ như $, &, #, @, để biết biến đó có kiểu là gì, cụ thể như sau: - String: là kiểu dữ liệu chuỗi, khoảng giá trị có thể lên đến hai tỷ ký tự. Nhận biết biến này bằng tiếp ngữ $ Ví dụ: Hoten$ = “Trần Văn Hai”. - Byte: là kiểu số nguyên dương, khoảng giá trị từ 0 đến 255. - Long: là các số nguyên, khoảng giá trịn từ –2.147.483.648 đến 2.147.483.647. Nhận biết biến này bằng dấu & ở cuối Ví dụ: A& 50. - Integer: là các số nguyên từ –32.768 đến 32.767. Nhận biết bằng dấu % ở cuối Ví dụ: b% = 1234 - Single: là các số có dấu chấm thập phân, có giá trị âm từ – 3,402823E8 đến –1,40129823E8 và có gía trị dương từ 1,401298E-45 đến 3,402823E8. Nhận biết bằng dấu ! ở cuối Ví dụ: C! = 4.7 - Double: là các số có dấu chấm thập phân. Nhận biết bằng dấu # ở cuối. Khoảng giá trị từ –1,797693134486231E308 đến – 44,94065645841247E-324, giá trị dương từ 44,94065645841247E-324 đến 1,797693134486231E308. Ví dụ: D# = 6.432 - Currency: Có 15 số nằm bên trái dấu phảy, 4 số nằm bên trái dấu phảy. Nhập biết bằng dấu @ ở cuối. Khoảng giá trị từ – 922337203685477,5808 đến 922337203685477,5807. Ví dụ: e@ = 5.1234. - Date: Lưu rtữ thông tin về thời gian. Nhận biết bằng dấu # ở đầu và ở cuối. Ví dụ: ngay = #12/12/2003# - Boolean: biến logic có giá trị true hay false dùng để gán giá trị hay trong các câu lệnh điều kiện - Variant: Lưu tất cả các giá trị khác nhau. 3. Cách Khai báo Ngoài cách nhận biết biến bằng các tiếp vị ngữ, ta có thể khai báo biến như sau: DIM AS Vi dụ: DIM Ten AS String III. Các phép toán trong Visual Basic 1. Các toán tử trong Visual Basic - Toán tử ^: Dùng để tính lũy thừa - Toán tử *: Dùng để nhân hai số hạng - Toán tử \: Chia hai số lấy phần nguyên - Toán tử / : Chia hai số lấy giá trị thực - Mod: Chia lấy phần dư - Toán tử +: Cộng hai toán hạng - Toán tử -: Trừ hai toán hạng 2. Thứ tự ưu tiên các phép toán Phép tính lũy thừa Đổi một số thành số âm Nhân và chia Chia số nguyên Trang:44
45. Chia lấy số dư Cộn g và trừ 3. Toán tử gán a = b 4. Toán tử quan hệ Ký hiệu Y nghĩa Ví dụ = Bằng nhau A=b Khác nhau A Lớn hơn a>b >= Lớn hơn hoặc bằng a>=b 5. Toán tử logic A NOT A True False False True - Phép toán AND, OR và 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. Các cấu trúc điều khiển 1. Cấu trúc lựa chọn IF Cấu trúc lựa chọn IF cho phép ta rẽ chương trình thành 2 nhánh, nếu bạn muốn rẽ nhiều nhánh thì có thể sử dụng cấu trúc IF lồng nhau. Cấu trúc If không có Else If Then ___ End If Cấu trúc If có Else If Then ___ Else ___ End If 2. Cấu trúc Select Case Cấu trúc này được dùng khi bạn xét nhiều điều kiện cho một biến nào đó CASE ___’ Các lệnh CASE ___’ Các lệnh CASE Trang:45
46. ___’ Các lệnh CASE ELSE ___ END SELECT 3. Cấu trúc DO WHILE LOOP Cấu trúc như sau DO WHILE ‘ các lệnh LOOP Câu lệnh này thực hiện như sau: Trước tiên nó kiểm tra điều kiện: nếu điều kiện đúng thì thực hiện lệnh sau đó kiểm tra điều kiện cho đến khi diều kiện sai thì thực hiện sau lệnh LOOP Nếu điều kiện sai thì thực hiện lệnh sau LOOP, bỏ qua lệnh giữa DO LOOP 4. Cấu trúc Do . Loop WHILE Cấu trúc như sau Do ‘ Các lệnh Loop While Câu lệnh này thực hiện như sau: Các câu lệnh sau Do sẽ được thực hiện, sau đó mới xét điều kiện khi điều kiện sai thì mới thực hiện lệnh sau Loop Nếu điều kiện sai thì thực hiện lệnh sau Loop 5. Cấu trúc Do Loop Until Cấu trúc như sau: Do ‘ Các lệnh Loop until Câu lệnh thực hiện như sau Các lệnh sau do sẽ được thực hiện trước cho đến khi nào điều kiện đúng 6. Cấu trúc For Next Cấu trúc như sau For to Step [khoảng tăng] ‘ Các lệnh Next Biến Để dừng cấu trúc For ta dùng phát biểu Exit For Ngoài ra, muốn thoát ra khỏi thủ tục với điều kiện nào đó ta dùng thủ tục Exit Sub V. Thủ tục và hàm 1. Thủ tục Khi lập trình ta thường gặp những đoạn chương trình hay lập đi lập lại nhiều lần ở những chỗ khác nhau. Để chương trình đỡ phức tạp, các đoạn này được thay thế bằng các chương trình con tương ứng, khi cần ta chỉ cần gọi nó ra mà không cần pahỉ viết lại cả đoạn. Trang:46
47. Mặt khác, đối với một số chương trình lớn và phức tạp. Việc xem xét tổng quan cũng như việc gỡ rối, hiệu chỉnh sẽ rất khó khăn. Việc lập các chương trình con sẽ chia chương trình ra thành từng khối, từng modul. Điều này giúp cho chúng ta kiểm tra, gỡ rối và điều khiển dễ dàng. Cấu trúc của một thủ tục có dạng như sau: Sub ___’ Các lệnh End Sub Nếu bạn muốn dùng thủ tục này trong toàn bộ chương trình thì bạn dùng thêm từ khóa Public trước từ khóa Sub, còn nếu bạn chỉ muốn dùng trong một form chứa nó thì bạn thêm từ khóa Private trước từ khóa Sub 2. Hàm Hàm cũng tương tự như thủ tục, chỉ khác là ta dùng hàm khi muốn nhận lại một kết quả trả lại của hàm. Cấu trúc hàm như sau: Function (tham số AS Kiểu) AS ___’ Các Lệnh Tên hàm = Giá trị End Function VI. Một số lệnh của Visual Basic 1. Lệnh End Dùng để chấm sứt chương trình đang chạy, khi lệnh này thực hiện thì các cửa sổ chương trình sẽ đóng lại và giải phóng ra khỏi bộ nhớ. Lệnh này thường được sử dụng cho nút lệnh có tên Exit cới biến cố Click Ví dụ Sub Command1_Click() End End Sub 2. Lệnh Exit Do Lệnh này dùng để thoát khỏi vòng lặp Do Ví dụ Do While ___ Exit Do 3. Lệnh Exit For Lệnh này dùng để thoát khỏi vòng lặp For 4. Lệnh Exit Sub Lệnh này dùng để thoát khỏi chương trình con nào đó 5. Lệnh Beep Lệnh này phát ra tiếng Beep 6. Lệnh Date Lệnh này cho phép bạn đặt lại ngày giờ của hệ thống. Cú pháp: Date = #Ngày# Ví dụ Trang:47
48. Date = #07/12/20003# Text1 = Date 7. Lệnh Time Lệnh này cho phép bạn đặt lại giờ của hệ thống Cú pháp: Time = #giờ# Ví dụ: Time = # 11:53:AM# 8. Lệnh Load Lệnh này dùng để nạp một Form vào bộ nhớ Cú pháp: Laod tên Form Ví dụ Load form1 Form1.Show 9. Lệnh Chdrive Dùng để đổi ổ đĩa làm việc Ví dụ: Chdrive “D:” chuyển xang làm việc trên đĩa D 10. Lệnh MkDir Dùng để tạo thư mục mới trên đĩa Ví dụ: MkDir “C:/Baitap” ‘ Tạo thư mục bài tập nằm ở thư mục gốc đĩa C 11. Lệnh ChDir Dùng để thay đổi thư mục làm việc. Ví dụ: ChDir “\Lythuyet” ‘ chuyển xang làm việc thư mục lý thuyết 12. Lệnh RmDir Lệnh này dùng để xóa thư mục rỗng đang tồn tại rên đĩa. Ví dụ: RmDir “C:\Baitap” ‘ Xóa thư mục Baitap trên đĩa C 13. Lệnh Kill Dùng để xóa một hay nhiều tập tin trên đĩa Ví dụ: Kill “C:\baitap\bt1.txt”’ xóa tập tin bt1.txt trong thư mục baitap trên ổ C 14. Lệnh Name Lệnh này dùng để đổi tin một tập tin trên cùng một ổ đĩa. Ví dụ: Name “C:\bt.txt” as “C:\baitap.txt” 15. Lệnh AppActive title [, Wait] Dùng để kích hoạt một cửa sổ trong một chương trình nào đang chạy. VII. Một số hàm dùng trong VB 1. Hàm Abs (Number) Hàm này trả về một số là giá trị tuyệt đối của Nuumber 2. Hàm Sin(Number AS Double) Tính Sin của một góc 3. Hàm Cos (number AS Double) Trang:48
49. Tính Cos của một góc 4. Hàm Tan (number AS Double) Tính Tan của một góc 5. Hàm Atn (number AS Double) Tính Artang của một góc 6. Hàm Int (number) Trả về phần nguyên của một số nếu là số dương. Còn nếu là số âm thì sẽ trả về phần nguyên có giá trị nhỏ hơn một đơn vị. 7. Hàm Fix (number) Hàm trả về phần nguyên của một số. 8. Hàm Sgn (Number) Hàm trả về một số nguyên. - Nếu so >0 sẽ trả về giá trị là 1 - Nếu so <0 sẽ trả về giá trị là –1 - Nếu so = 0 sẽ trả về giá trị là 0 9. Hàm Sqr (Number) Tính căn bậc hai của một số 10. Hàm Exp (Number) Tính e mũ của một số 11. Hàm Log () Tính Logarit của một số. Hàm trả về giá trị thực 12. Hàm round (Biểu thức [,so]) Hàm này sẽ làm tròn số 13. Hàm Rnd ([Number]) Hàm trả về một số thực ngẫu nhiên 14. Hàm Day (Biến) Trả về số ghi ngày của biến nhập vào 15. Hàm Month (Biến) Trả về số ghi tháng của biến nhập vào 16. Hàm Year (biến) Trả về số ghi năm của biến nhập vào 17. Hàm Now Trả về ngày tháng năm và thời gian hiện tại 18. Hàm Weekday (biến) Cho biết thứ mấy trong tuần 19. Hàm Hour (thoigian) Cho biết giờ ứng với biến. 20. Hàm Minute (thoigian) Cho biết phút ứng với biến. 21. second (thoigian) Cho biết giây ứng với biến. 22. Hàm Replace (chuoi, chuoicantim, chuoithaythe, vitrithaythe, solanthaythe) Thay thế chuỗi này bằng một chuỗi khác. 23. Hàm Val (string) Trang:49
50. Trả về một số thực tương ứng với chuỗi String. String phải là một chuỗi gồm các ký số hợp lệ. - Giá trị của hàm là 0 nếu chuỗi có ký tự đầu là ký tự - Giá trị của hàm là một số nếu chuỗi đó hoàn toàn là các ký số. Nếu các ký tự số viết cách nhau thì hàm này sẽ cắt bỏ khoảng trắng và cho trả về giá trị bằng với dãy này. 24. Hàm Str (Number) Hàm trả về một chuỗi ký tự. Chuỗi này luôn luôn có một ký tự đầu ghi dấu trong trường hợp số âm, hoặc một khoảng trống trong trường hợp số dương 25. Hàm Qbcolor (color) Hàm cho màu của một đối tương nào đó 26. Hàm RGB (red, green, blue) Chọn màu bất kỳ qua tỉ lệ 3 màu chuẩn Red, Green, Blue. 27. Hàm Asc (String) Trả về mã Ascii của ký tự string 28. Hàm Chr (CharCode) Hàm trả về một ký tự tương ứng với một mã Ascii nào đó 29. Hàm Len (Expreession) Cho biết chiều dài của chuỗi 30. Hàm Ltrim (string) Hàm này trả về một chuỗi sau khi đã cắt bỏ một số khoảng trống bên trái của chuỗi 31. Hàm Rtrim (string) Hàm này trả về một chuỗi sau khi đã cắt bỏ một số khoảng trống bên phải của chuỗi 32. Hàm Trim (string) Hàm này trả về một chuỗi sau khi đã cắt bỏ một số khoảng trống bên trái và bên phải của chuỗi 33. Hàm Left (String, n) Hàm trả về một chuỗi ký tự được cắt từ n ký tự (kể cả ký tự trắng) bên trái của chuỗi String. 34. Hàm Right (String, n) Hàm trả về một chuỗi ký tự được cắt từ n ký tự (kể cả ký tự trắng) bên phải của chuỗi String. 35. Hàm Mid (String, n [, length]) Hàm này trả về một chuỗi, chuỗi này được lấy từ chuỗi String bắt đầu từ vị trí n với chiều dai length. 36. Hàm Space (n) Hàm trả về một chuỗi gồn n khoảng trắng. 37. Hàm String (n, ký tự) Hàm trả về một chuỗi ký tự giống nhau. 38. Hàm Instr (Start, S1, S2, Compare) Dùng để tìm một chuỗi con có nằm trong chuỗi mẹ hay không, nếu có thì nằm ở vị trí thứ mấy. Start: Vị trí bắt đầu tìm, không ghi thì tìm ở vị trí đầu S1 và S2 là chuỗi mẹ và chuỗi con Trang:50
51. Compare có giá trị 0: So sánh chính xác từng ký tự 1: So sánh không phân biệt chữ hoa, chữ thường 2: Chỉ dùng trong khi lập trình cho Microsoft Acess 39. Hàm Ucase (string) Đổi thành chữ hoa. 40. Hàm Lcase (string) Đổi thành chữ thường. 41. Hàm Format (Value, format) Dùng để định dạng 42. Hàm IIF ( , , ) Hàm này trả về giá trị 1 nếu biểu thức đúng, và ngược lại thì trả về giá trị 2. VIII. Các phương thức trong VB 1. Phương thức Print In ra màn hình của một biểu mẫu, một dòng duy nhất tại vị trí hiện thời của con trỏ. 2. Phương thức CLS Dùng để xóa 3. Phương thức Move (Left As String [,top][,width][,height]) Dùng để di chuyển đối tượng đến vị trí xác định và hiệu chỉnh nó với kích thước mới. 4. Phương thức Scale (x1,y1)-(x2,y2) Dùng để quy định lại tọa độ trên form 5. Phương thức Line (x1, y1) – (x2, y2), color, BF Dùng để vễ một đường thẳng hay một hình chữ nhật 6. Phương thức Circle Dùng để vễ một hình tròn, ellipse, cung tròn, cung ellipse trên Form hay trên Picturebox. Trang:51
52. Chương 5 CÀI ĐẶT BÀI TOÁN I. Phân tích bài toán. 1. Các chức năng chính của bài toán. Chương trình gồm các chức năng sau: - Áp dụng phương pháp PERT-PCM vào để giải quyết bài toán lập lịch thi công công trình, công việc này nhằm lập ra một lịch thi công các công trình trong một dự án sao cho thời gian hoàn thành dự án là tối ưu nhất về thời gian, chúng ta chỉ cần nhìn vào lịch lập ra là đã đièu khiển được dự án của chúng ta. - Điều khiển nhân lực khi thi công các công trình, công việc này giúp chúng ta điều khiển lượng nhân công hiện có. 2. Cấu trúc dữ liệu của bài toán. Dữ liệu của bài toán được lưu trữ dưới dạng một bảng ghi có cấu trúc như sau: Type LuuTru DinhDau As Long DinhCuoi As Long GiaTri As Long NgayThiHanh As Date Ten As String * 50 End Type Trong đó DinhDau lưu trữ số thứ tự của hạng mục cần phải làm trước, ví dụ 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) thì khi đó DinhDau sẽ có giá trị là 1, DinhCuoi sẽ có giá trị là 2 và lúc đó GiaTri sẽ bằng 10, ngày thi hành dùng để lưu trữ ngày bắt đầu thi hành dự án, còn biến Ten dùng để lưu trữ tên các hạng mục cần thi công, ví dụ hạng mục (1,2 ) là xây tường chẳng hạn, khi đó lúc lưu trữ dữ liệu sẽ lưu trữ tất cả các biến đó. Chương trình còn lưu trữ thêm một File dùng để lưu trữ thên tên các hạng mục nó cũng có dạng một bảng ghi như sau; Type HocvienType TenHM As String * 50 End Type Biến TenHM dùng để lưu trữ các tên hạng mục, các tên này sẽ được lưu trữ dưới dạng một File cùng cấp với File nguồn của chương trình khi chương trình chạy, nó có tác dụng cập nhật những tên hạng mục mới cho chương trình của chúng ta. II. Giới thiệu chương trình. Trang:52
53. Chương trình bao gồm hai công việc chính đó là: Lập lịch thi công công trình và Điều khiển nhân lực 1. Lập lịch thi công công trình. Chương trình được tổ chức dưới một Menu chính có dạng như sau Menu chính của chương trình này liên kết với mọi Form của chương trình, ở đây ta có thể sử dụng chương trình Help để được hướng dẫn sử dụng hoặc tại mỗi biểu tượng của chương trình đều có Tooltip bằng tiếng Việt hiện lên, vì vậy bạn có thể dễ dàng sử dụng chương trình này. Từ Form chính này ta có thể tiến hành được các công việc như sau: - Mở một File mới để nhập dữ liệu từ đầu: bằng cách bấm vào biểu tượng New có hình tờ giấy trắng, hoặc bấm vào Menu File/New để chương trình bắt đầu làm việc. + Sau khi bấm New thì chương trình sẽ cho một Form chưa có dữ liệu. Từ đây bạn có thể nhập dữ liệu để tính toán: đầu tiên là nhập số hạng mục cần làm trong một dự án, ở đây số hạng mục phải là số, và số phải là số dương. + Nếu bạn nhập sai chương trình sẽ thông báo lỗi đó và yêu cầu bạn nhập lại cho đến khi nào nhập đúng thì thôi, bạn cũng có thể Click vào nút HủyBo để hủy bỏ công việc nhập dữ liệu. + Sau khi nhập xong bạn có thể bấm nút Enter để xác định số bạn vừa nhập, hoặc Click vào biểu tương Tiếp Tục , chương trình sẽ kiểm tra sem bạn đã nhập đúng chưa. Nếu chưa đúng thì bạn phải nhập lại. Trang:53
54. + Bạn có thể hủy bỏ bằng cách Click vào biểu tượng Hủy Bỏ hoặc nhấn phím ESC để hủy bỏ việc nhập dữ liệu của mình và quay trở lại Form ban đầu. + Sau khi nhập xong số hạng mục cần tính toán và nhấn Enter chương trình sẽ cho một bảng tính trong đó bạn cần phải nhập tên của từng hạng mục mà trong dự án cần phải làm, ở đây bạn có thể gõ trực tiếp tên từng hạng mục hoặc bạn có thể sử dụng phương pháp gắp thả từ một danh sách bên cạnh, nếu tên hạng mục nào chưa có thì bạn có thể bổ xung tên hạng mục bằng cách Click vào mục Bổ xung tên hạng mục, tiếp theo bạn nhập thời gian làm xong của từng hạng mục một và sự ràng buộc giữa các hạng mục với nhau, nếu có một hạng mục mà có nhiều hơn 2 hạng mục phải làm trước thì phải nhập chúng cách nhau bằng dấu “,” + Nếu hạng mục nào mà không làm từ đầu thì bạn có thể bỏ trắng không cần nhập điều kiện ràng buộc tức là hạng mục đó sẽ làm đầu tiên, không cần phải làm sau bất cưa hạng mục nào. + Khi nhập xong bạn có thể bấm Enter hoặc Click vào biểu tượng Số Liệu Nhập để xác định việc nhập dữ liệu của bạn. + Khi lập dữ liệu mới bạn cần chú ý là nhập thời gian bắt đầu tiến hành dự án, thời gian bắt đầu ở đây phải lớn hơn thời gian hiện tại, nều không chương trình cũng sẽ hiện một thông báo nói rằng bạn nhập sai, và tất nhiên bạn phải nhập lại. Trang:54
55. + Nếu bạn muốn hủy bỏ việc nhập của bạn, bạn có thể bấm vào nút Quay Lại hoặc bấm nút ESC để thoát khỏi chương trình và quay trở lại màn hình ban đầu. + Nếu trong quá trình nhập dữ liệu bạn không biết cách bạn có thể tham khảo hướng dẫn bằng cách Click vào biểu tượng Trợ Giúp + Nếu việc nhập dữ liệu tốt bạn có thể bấm nút Quay Lại để tiếp tục chương trình. - Sau khi đã có dữ liệu bạn có thể có được một đồ thị mô tả sự liên hệ giữa các hạng mục bằng cách Click vào biểu tượng Imetate hoặc từ Menu Imetate\Graph sẽ Trang:55
56. cho ta đồ thị mô tả dữ liệu. + Bạn cũng có thể in dữ liệu ra giấy bằng cách bấm vào biểu tượng máy in trên Form dữ liệu này. + Bạn Click vào biểu tượng Quay Lại để trở lại Menu chính. - Tiếp theo, nếu bạn muốn xem lịch thi công các hạng mục trong dự án như thế nào bạn có thể Click vào biểu tượng Design trên Toolbar hoặc Design trên thanh Menu để bạn có thể xem chi tiết lịch thi công các hạng mục trong dự án. Form có dạng như sau: + Ở đây có 4 cột. Cột thứ nhất ghi thứ tự các hạng mục được thi công, cột thứ hai cho biết tên hạng mục cần thi công, cột thứ 3 cho biết số lượng thời gian hạng mục đó bắt đầu tiến hành, tất nhiên đối với hạng mục cuối cùng thì đây là thời điểm cắt băng khánh thành dự án này, cột thứ 4 in ra ngày mà hạng mục đó bắt đầu tiến hành, điều này sẽ giúp cho các nhà quản lý nhân sự tham gia trong các dự án quản lý dự án của mình được dẽ dàng hơn. Những số liệu ở đây bạn chỉ có thể xem chứ không xóa hay sửa đổi một cái gì cả. Bạn cũng có thể xuất dữ liệu ra máy in. + Kết thúc Form này bạn có thể Click vào biểu tượng quay lại để trở về Menu chính. - Sau khi tham khảo song lịch thi hành dự án bạn có thể lưu trữ dữ liệu vào trong máy tính của bạn bằng cách Click vào Menu File\Save + Chương trình sẽ đưa ra hộp hội thoại cho phép bạn lưu trữ dữ liệu vào đâu tùy ý bạn. Sau khi chọn được nơi lưu trữ bạn nhập tên File và Click vào nút Save, nó sẽ ghi toàn bộ dữ liệu cho bạn. Trang:56
57. + Trong chương trình này bạn chỉ có thể lưu tên File với phần mở rộng là *.PCM, ở đây không có gì là ràng buộc cả bởi vì tôi muốn đặt ra một cái gì đó gợi nhớ để cảm ơn những người đi trước họ đã nghiên cứa được một ứng dụng quan trọng như thế này, một ứng dụng mà nó đem lại nhiều lợi nhuận cho con người khi xây dựng các dự án lớn. Form có dạng: - Tương tự như ghi dữ liệu để lưu trữ, bạn cũng có thể đọc dữ liệu mà bạn đã lưu trữ ra bằng cách Click vào Menu\File\Open + Sau đó bạn cũng có thể lự chọn tập tin nào chưa dữ liệu mà bạn cần mở, Form có dạng như sau: Trang:57
58. - Đến đây công việc tưởng chừng như đã hoàn tất nhưng mọi chuyện không phải đơn giản như vậy. Trong thực tế có những dự án mà khi người ta thi công rồi mới thấy có một số công việc không thích hợp, và như thế họ phải phá ra, hoặc có những lúc họ không cần một số hạng mục nào đó, và cũng có những lúc họ lại muốn thêm một số hạng mục nào đó. Tất nhiên đây là những điều mà những nhà quản lý họ cũng không muốn, nhưng trong thực tế những chuyện như thế này nó vẫn tồn tại. Chính vì vậy mà trong chương trình này tôi cũng có đề cập đến vấn đề này. - Form này sẽ mở ra những dự án mà đang được thi công, lúc này thì giả sử đặt trường hợp chúng ta là những người đang điều hành những dự án đó, nhưng ở đây đơn giản hơn nhiều vì đây chỉ là giả sử thôi. Lúc đó bạn có thể bổ xung một hạng mục nào đó vào trong danh sách các hạng mục sẽ được thi công, và một điều tất nhiên là ta chúng phải nhập thời gian làm xong hạng mục vừa nhập đó. Form ở đây có dạng như sau: + Bạn có thể thêm vào bao nhiêu hạng mục tùy ý bạn, nhưng lưu ý là sau mỗi lần thêm vào thì phải nhớ là thứ tự thi công sẽ bị thay đổi, và hạng mục thêm vào không được lớn hơn hạng mục cuối cùng là 2 vì khi bắt đầu thêm vào Giả sử dự án của bạn có 100 hạng mục mà bạn thêm vào hạng muc thứ 102 thì không được, chương trình sẽ báo lỗi và bạn phải nhập lại. Sau mỗi lần nhập dữ liệu bạn có thể nhấn phím Enter để xác định việc nhập của bạn. - Tương tự như thêm hạng mục việc bỏ một số hạng mục cũng diễn ra tương tự, bạn chỉ cần Click vào biểu tượng xóa hạng mục là sẽ có một cửa sổ tương tự như cửa sổ nhập hạng mục thêm vào cho bạn nhập . + Sau Khi kết thúc việc thêm hay xóa một số hạng mục bạn phải Click vào biểu tượng nhập số liệu để chương trình tính toán lại cho bạn, lúc này lịch thi công lại có một lịch mới, khác hẳn lịch ban đầu nếu như bạn đã thêm vào hoặc bỏ đi một số hạng mục không cần thi công. Trang:58
59. - Nếu như bạn nhập dữ liệu mới hay mở một file đã lưu trong đĩa mà bạn đã sửa đổi dữ liệu ở bên trong thì bạn lên lưu dữ liệu vào một File thì việc nhập dữ liệu hay sửa đổi dữ liệu mới có tác dụng. Ơ đây chương trình nó biết được ta đã lưu hay chưa, nếu chưa lưu thì khi nào thoát khỏi chương trình nó sẽ nhắc nhở chúng ta là có lưu dữ liệu hay không. + Nếu bạn click vào yes thì một cửa sổ ghi File lại hiện ra yêu cầu bạn ghi tên file và Click vào nút Save. 2. Điều khiển nhân lực. Cũng tương tự như lập lịch thi công công trình ở đây chương trình cũng bao gồm các công đoạn tương tự như trên. Khi kết thúc chương trình sẽ cho ta một bảng trong đó đưa ra một danh sách bao gồm số công nhân cần có cho mỗi công việc. III. Chương trình nguồn. Trong chương trình này bao gồm rất nhiều hàm và thủ tục ở đây chỉ xin đưa ra một thủ tục quan trọng đó là một thủ tục chính trong chương trình, thủ tục này trong phần lập lịch thi công trình đó là thuật toán Dijsktra, thuật toán được viết như sau. Public Sub Dijkstra() Dim v, u, minp As Long S = 0 For v = 0 To n + 1 D(v) = A(S, v) Truoc(v) = S Final(v) = False Next v Truoc(S) = 0 D(S) = 0 Final(S) = True Trang:59
60. Do W7hile Not Final(T) 'Tim u la dinh co nhan tam thoi nho nhat minp = 3000000 For v = 0 To n + 1 If (Not Final(v)) And (minp > D(v)) Then u = v minp = D(v) End If Final(u) = True Next v ' chu y '=== If Not Final(T) Then For v = 0 To n + 1 If (Not Final(v)) And (D(v) + A(u, v) < D(u)) Then D(v) = D(u) + A(u, v) Truoc(v) = u End If Next v End If Loop End Sub Trang:60
61. KẾT LUẬN Trong sự phát triển vượt bậc của xã hội hiện nay, việc xây dựng các dự án lớn đã có rất nhiều chuyên gia có nhiều kinh nghiệm trợ giúp họ hoàn thành dự án này, đồng thời họ cũng đã có đủ những kinh nghiệm để hoàn thành các dự án đó. Tuy nhiên để hoàn thành những dự án lớn đó thì với sự phát triển của công nghệ thông tin hiện nay đã phần nào đã góp phần vào công cuộc phát triển và xây dựng nền kinh tế của nước nhà. Trong thời gian làm đề tài này. Với một công nghệ tối ưu đã nghiên cứu và phát triển trong xây dựng và điều hành những dự án lớn (Nhất là những dự án đòi hỏi sự chính xác, đòi hỏi phải tiết kiệm nhân lực, tiết kiệm thời gian nhưng phải hoàn thành trong một thời gian sớm nhất), nhưng đã phần nào đáp ứng được được các nhu cầu cần thiết ở trên. Đề tài “Điều hành dự án băng phương pháp PERT-PCM và ứng dụng giải quyết bài toán lập lịch thi công công trình” với sự chỉ bảo tận tình của thầy Đỗ Như An đã giúp em hoàn thành đề tài này. Do thời gian và kinh nghiệm hạn chế nên đề tài chắc vẫn chưa hết khỏi những thiếu xót. Trong thời gian sau tôi sẽ cố gắng hoàn thành chúng và có thể đưa ra sử dụng trong cuộc sống hiện nay. Trang:61