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

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 ; 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 tốn tìm đường đi ngắn nhất. Trong các ứng dụng thực tế, bài tố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 tốn như vậy nhiều bài tốn thực tế quan trọng. Ví dụ, bài tố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 tố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 tố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 tố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 tốn như vậy. Thế nhưng thông thường các thuật tốn được xây dựng dựa trên lý thuyết đồ thị tỏ ra là các thuật tốn có hiệu quả nhất. Trong phần này ta sẽ xét một số thuật tố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. 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 tố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 tố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 tốn xét sự tồn tại đường đi Hamilton trong đồ thị như là một trường hợp riêng. 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 tố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 tố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à tồ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 tố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 tố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 tố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 tốn . Bây giờ ta sẽ mô tả thuật tố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 tố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 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 tố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 tốn của thuật tố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 < n-2 và điều đó làm tăng hiệu quả của thuật tốn trong việc giải các bìa tốn thực tế. Tuy nhiên, cái tiến đó không thực sự cải thiện được đánh giá độ phức tạp của bản thân thuật tốn. Đối với đồ thị thưa thớt hơn là sử dụng danh sách kề Ke(v), v Î V, để biểu diễn đồ thị, khi đó vòng lặp theo u cần viết lại dưới dạng . For u Î ke(v) do If d[v] > d[u]+a[u, v] then begin d[u]:= d[u]+a[u, v]; truoc[v]:=u; end; trong trường hợp này ta thu được thuật tố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 tố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 tố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 tốn với độ phức tạp là O(n3) (nếu sử dụng thuật tố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 tố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 tốn giải bài tốn trên với độ phức tạp tính tốn O(n3): Thuật tốn Floyd. Thuật tố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. *) 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 tốn của thuật tốn là O(n3). CHƯƠNG 3 BÀI TỐN LẬP LỊCH THI CÔNG CÔNG TRÌNH Bài tố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 đó đã hồ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 để hồ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 tốn đặt ra vấn đề bài tố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 tốn đặt ra có thể áp dụng các thuật tốn được nêu ở trên. 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 hồn thành trước 1 2 3 4 5 6 7 8 10 15 10 30 1 2 15 20 10 1 2,3 4 2,3 5,6 5 1 : 0 0 1 2 : 10 0 3 : 0 0 1 2 4 : 25 0 1 2 4 5 : 55 0 3 6 : 10 0 1 2 4 5 : 55 Đưa về bài tố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ố - 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 tố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 tố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 tố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 tốn Dijkstra. II. Thuật tốn Dijkstra. Thuật tố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 tố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 tố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 tố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]; 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 0 do Begin Tìm đỉnh u Î T thỏa mãn d[u] = min { d[z]: z Î T} T := T \ {u}; (*Cố định nhãn của đỉnh u*) For v Î T do (*Gán nhãn lại cho các đỉnh trong T*) If d[v] > d[u] + a[u, v] then Begin D[v] := d[u] + a[u, v] Truoc [v] := u; End; End; End; Định lý 1: Thuật tố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 tố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 hồn tồ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 tố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 tốn cần thực hiện theo thuật tốn. Ở mỗi bước lặp để tìm ra đỉnh u cần thực hiện O(n) phép tốn, và để gán nhãn lại cũng phải thực hiện một số lượng phép tốn cũng la O(n). Thuật tốn phải thực hiện n- 1 bước lặp. Vậy thời gian tính tốn của thuật tốn là cỡ O(n2). 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 tốn Dijkstra Kết quả tính tố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 tốn khi đỉnh t trở thành đỉnh có nhãn cố định. (1) Số phần tử:= số đỉnh -1; i:=1; i < đnguồ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 i £ số đỉnh Tập đỉnh[i]:=i; Đđ-đến[i]:=kc[đnguồn, i]; Đđ- trực tiếp đến[i]:=đỉnh nguồn; i:=i+1; Bắt Đầu N Y N Y * Sơ đồ thuật tốn Dijkstra. (1) (3) (4) (2) j£ số đỉnh -2 Min:= đđ-đến[đỉnh[1]]; Vị trí :=1; i£ k Đđ-đến[đỉnh[i]] <min; Min:= đđ-đến[đỉnh[i]]; Vị trí :=i; i:=i+1 Đỉnh xét:=đỉnh[vị trí]; Đỉnh[vị trí]:=đỉnh[spt]; Spt:=spt-1; i:=1 i£ spt Y N Y N Y N Y N (4) (2) X:=đỉnh[i] (3) Đđ-đến[x] > Đđ-đến[đỉnh xét]+ kc[đỉnh xét,x]; Đđ-đến[x]:=Đđ-đến[đỉnh xét + kc[đỉnh xét,x]]; i:=i+1; Kết Thúc Y N III. Giải quyết bài tốn. Sau khi đưa bài tố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) - Aùp dụng thuật tốn Dijkstra. - Kết thúc thuật tốn ta thu được d[u] . - Đổ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 tồn bộ công trình. Tương tự như trên ví dụ trên khi kết thúc tồ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 tồ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. Ngồi thời gian ra, chẳng hạn nhân lực, nguyên liệu, chi phí …Về mặt tố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 công Hoạt động số nhân 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ẽ.). 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ó tồ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 Flat (Form phẳng) 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 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 Bình thường Cực tiểu 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 Canh trái Canh phải 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 Canh trái Canh phải Canh giữa Appearance Quy định cách thể hiện của Textbox flat bình thường 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 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 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 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 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 Ngồ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 tốn trong Visual Basic 1. Các tốn tử trong Visual Basic Tốn tử ^: Dùng để tính lũy thừa Tốn tử *: Dùng để nhân hai số hạng Tốn tử \: Chia hai số lấy phần nguyên Tốn tử / : Chia hai số lấy giá trị thực Mod: Chia lấy phần dư Tốn tử +: Cộng hai tốn hạng Tốn tử -: Trừ hai tốn hạng 2. Thứ tự ưu tiên các phép tố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 Chia lấy số dư Cộn g và trừ 3. Tốn tử gán a = b 4. Tốn tử quan hệ Ký hiệu Yù nghĩa Ví dụ = Bằng nhau A=b < Nhỏ hơn A<b <= Nhỏ hơn hoặc bằng A<=b Khác nhau Ab > Lớn hơn a>b >= Lớn hơn hoặc bằng a>=b 5. Tốn tử logic A NOT A True False False True - Phép tố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 _____’ 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 Ngồi ra, muốn thố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. 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 tồ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 để thố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 để thốt khỏi vòng lặp For 4. Lệnh Exit Sub Lệnh này dùng để thố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ụ 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) 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) 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 đó hồn tồ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 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. Chương 5 CÀI ĐẶT BÀI TỐN I. Phân tích bài tốn. 1. Các chức năng chính của bài tố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 tố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 hồ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 tốn. Dữ liệu của bài tố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. 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 tố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ủyBỏ để 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. + 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 tố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. + 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 để thố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ẽ 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 tồn bộ dữ liệu cho bạn. + 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: - Đến đây công việc tưởng chừng như đã hồ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 tố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. - 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 thố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 tốn Dijsktra, thuật tố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 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 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ọ hồn thành dự án này, đồng thời họ cũng đã có đủ những kinh nghiệm để hồn thành các dự án đó. Tuy nhiên để hồ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 hồ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 tố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 hồ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 hồn thành chúng và có thể đưa ra sử dụng trong cuộc sống hiện nay.