Bài giảng Toán kinh tế - Chương 4: Mô hình bài toán tối ưu trên mạng

Nội dung text: Bài giảng Toán kinh tế - Chương 4: Mô hình bài toán tối ưu trên mạng

1. Bài giảngToán kinh tế Chương 4: Mô hình bài toán tối ưu trên mạng CHƯƠNG 4 BÀI TOÁN TỐI ƯU TRÊN MẠNG 4.1 Một số khái niệm cơ bản 4.1.1 Định nghĩa về đồ thị hữu hạn a) Đồ thị hữu hạn (Graph) là một cặp tập hợp; ký hiệu là G = {X.A}, trong đó X = {x1, x2, , xn} là tập hữu hạn các điểm (đỉnh, nút). A = {(i, j)} là tập hợp các cạnh (cung) nối tất cả hoặc một phần các điểm xi X lại với nhau, cách nối điểm i với điểm j, ký hiệu là (i, j). Thí dụ 4.1 G = {X.A}, trong đó X = {x1, x2, x3, x4, x5, x6, x7} và A = {(1,2), (2,1), (1,4),(1,3), (2,5), (4,3), (3,5), (3,6), (3,7), (5,7), (4,6), (6,7)} x x 2 5 x7 x1 x3 x6 x4 Hình 4.1 Đồ thị vô hướng: Ký hiệu {G X.A}trong đó X là tập các đỉnh (nút, điểm) và A là tập các nhánh. Nhánh là một cặp không kể đến thứ tự hai đỉnh khác nhau xi và xj nào đó với xi X, xj X, ký hiệu là (i, j). Vậy (xi, xj) = (xj, xi) trong đồ thị vô hướng. Cung còn được gọi là cạnh có hướng. Cung (xi, xj) được gọi là nối đỉnh xi với đỉnh xj. Cấp của một đỉnh là số cung nối tới nó. Cấp của đồ thị là cấp cực đại trong các cấp của các đỉnh của nó. Một đường đi từ đỉnh x1 đến đỉnh xt là bộ t nút khác nhau x1, x2, , xk sao cho (xk , xk+1) A với k= 1, 2, , t-1. Chu trình (mạch vòng) là bộ t đỉnh: x1, x2, , xt sao cho x1, , xt-1 là một đường đi, xt ≡ x1 và có ít nhất ba đỉnh khác nhau (tức là t - 1 ≥ 3). Đồ thị vô hướng được gọi là PTITliên thông nếu ứng với mỗi cặp xi, xj X đều có một đường đi từ xi đến xj. Số các đỉnh của đồ thị thường ký hiệu là n còn số nhánh là m. Đồ thị có hướng: Ký hiệu là G = {X.A} nhưng mỗi nhánh là là một cặp có thứ tự. Vì vậy (xi , xj) ≠ (xj, xi). Nhưng đồ thị không được chứa cung tự nối dạng (xi, xi). Thí d ụ 4.2 : Hình 4.2 là một đồ thị có hướng x1 G = {X.A}.Với X = {x1, x2, x3, x4, x5} và A = {(x1,x2),(x2,x1),(x1,x3),(x1,x4),(x3,x2),(x4,x3), (x3,x5)}. Ta sẽ nói là cung (xi, xj) ký hiệu (i, j) là đi từ đỉnh i đến đỉnh j. x4 Đồ thị vô hướng tương ứng với một đồ thị có hướng là đồ x 2 thị nhận được khi không tính đến hướng trên các cung nữa. Hình 4.2 Đồ thị có hướng là liên thông nếu đồ thị vô hướng tương x x ứng là liên thông 3 5 119
2. Bài giảngToán kinh tế Chương 4: Mô hình bài toán tối ưu trên mạng Mỗi đường đi trong đồ thị vô hướng tương ứng đều gọi là một đường đi trong đồ thị có hướng. Nhưng đồ thị có thể chứa cả hai cung (i, j) và (j, i), nên để xác định một đường đi phải nói rõ cả dãy đỉnh x1, , xt và dãy cung a1, , at-1. Khi đó nếu một cung ak có dạng "thuận" ak = (ik, ik+1) thì ta nói ak là cung tiến trong đường đi này. Ngược lại nếu ak = (ik+1, ik) thì ak là cung lùi. Chu trình cũng được định nghĩa như ở đồ thị vô hướng, nhưng ở đây cho phép chu trình chỉ gồm hai đỉnh khác nhau.Một đường đi hoặc chu trình được gọi là có hướng nếu nó chỉ chứa các cung tiến. Trong hình 4.2 thì (1,3), (3,2), (2,1) là một chu trình có hướng. Nhưng (1,3), (1,2), (3,2) là một chu trình không có hướng vì (1,3) và (3,2) là cung lùi. Đường đi tối giản là đường đi qua một đỉnh của đường đi đó chỉ một lần. Tương tự chu trình tối giản là chu trình mà trong đó mỗi đỉnh của đồ thị chỉ gặp một lần, từ đỉnh đầu tiên đến đỉnh cuối cùng. 4.1.2 Các yếu tố khác của đồ thị a. Ánh xạ và ánh xạ ngược: - Một ánh xạ của đỉnh xi trong đồ thị G = {X.A}ký hiệu là Г(xi) là tập hợp các đỉnh cuối của tất cả các cung có đỉnh đầu là xi. Thí dụ trong hình 4.2: Г(x1) = {x2, x3, x4}. -1 - Ánh xạ ngược của một đỉnh xj trong đồ thị G ={X.A}ký hiệu Г (xi) là tập hợp các đỉnh đầu -1 của tất cả các cung có đỉnh cuối là xj. Chẳng hạn trong hình 4.3: Г (x3) = {x1, x4}. b. Cây Đồ thị vô hướng được gọi là cây nếu nó liên thông và không chứa chu trình. Mỗi đỉnh cấp 1 của cây gọi là một lá. Định lý 4.1: - Mỗi cây có hơn một đỉnh sẽ có lá. - Đồ thị vô hướng là một cây khi và chỉ khi nó liên thông và có n- 1 cung. - Với bất kỳ hai đỉnh xi ≠ xj trên cây đều có tồn tại duy nhất một đường đi từ xi tới xj. - Nếu thêm một cạnh mới vào một cây thì đồ thị mới nhận được có đúng một chu trình. Cây bao trùm:(cây tối đại) của đồ thị liên thông, vô hướng G X. A  là một cây trong G mà chứa tất cả các đỉnh của G . Vậy cây bao trùm là cây T có dạng T = {X.A1} trong đó A1 A . Định lý 4.2 Giả sử {G X.A} là một đồ thị vô hướng liên thông và A0 A . Nếu các cung của A0 không tạo thành một chu trình PTITnào thì có thể bổ sung thêm các cung của đồ thị vào A0 để được tập mới A1 sao cho {X. A1} là một cây bao trùm. Trong hệ thống kỹ thuật, người ta thường sử dụng các loại cây sau đây: - Cây người chào hàng: Là một đường đi qua tất cả các đỉnh của đồ thị, mỗi đỉnh chỉ qua một lần. - Cây có chiều dài ngắn nhất: Là một đường đi nhận được từ đồ thị bằng cách loại ra khỏi nó các cung theo trình tự giảm dần chiều dài của cung và kiểm tra tính liên thông của đồ thị, hoặc đưa dần vào các cung vào đồ thị theo trình tự tăng dần chiều dài cung và cấm không được tạo thành chu trình. - Cây Steiner: Nếu cho phép đưa thêm vào tập hợp đỉnh của đồ thị những đỉnh phụ thì độ dài của cây ngắn nhất có thể giảm xuống. Đỉnh phụ đưa thêm vào đồ thị có 3 nhánh cách nhau 1200 được gọi là đỉnh Steiner. c. Lát cắt: là tập hợp các nhánh sao cho nếu loại chúng ra khỏi đồ thị thì đồ thị trở nên không liên thông. 120
3. Bài giảngToán kinh tế Chương 4: Mô hình bài toán tối ưu trên mạng Lát cắt gọi là phân chia hai đỉnh xi và xj của đồ thị, nếu sau khi loại lát cắt này ra khỏi đồ thị thì hai đỉnh xi và xj không còn liên hệ với nhau nữa. Lát cắt tối giản là lát cắt không chứa trong nó những lát cắt khác. d. Đồ thị phẳng và đồ thị không phẳng: - Đồ thị G = (X.A) được gọi là đồ thị phẳng nếu nó có thể biểu diễn được trên mặt phẳng hoặc mặt cầu sao cho không có bất kỳ hai cạnh nào cắt nhau. - Đồ thị không thỏa mãn điều kiện trên gọi là đồ thị không phẳng. e. Đồ thị đối ngẫu Đối với một đồ thị G = (X. A), giữa một cặp đỉnh nào đó ta gọi là đỉnh vào (đỉnh đầu) và đỉnh ra (đỉnh cuối) ta có thể xây dựng được một đồ thị đối ngẫu G' = {X'.A} theo trình tự sau đây: - Vẽ thêm một cung nối liền hai đỉnh "vào" và "ra" của đồ thị G = {X.A}. - Trong mỗi "diện" của G = {X.A}("diện" là một phần của đồ thị được giới hạn bởi các cung mà bên trong nó không chứa các cung khác của đồ thị), kể cả diện ngoài (diện ngoài là phần mặt phẳng không giới hạn bởi các cung của đồ thị) ta đặt một đỉnh x' trong tập X' của đồ thị đối ngẫu sẽ được xây dựng. - Nối các đỉnh trong tập X' lại với nhau bởi các cung, cắt các cung tương ứng của đồ thị phẳng ban đầu, số cung của đồ thị đối ngẫu đúng bằng số cung của đồ thị phẳng ban đầu. Hướng của cung trong đồ thị đối ngẫu được xác định như sau: Nếu cung của đồ thị đối ngẫu đi từ một đỉnh nằm bên trong một diện của đồ thị phẳng ban đầu cắt cung của G ={X.A} có hướng thuận với chiều kim đồng hồ theo mạch vòng của đa diện, thì hướng của cung đang xét trong đồ thị đối ngẫu sẽ đi từ bên trong diện ra bên ngoài diện và ngược lại. Nếu cung của đồ thị phẳng ban đầu không có hướng thì cung tương ứng của G' = {X'.A} cũng không có hướng. Hình 4.3a và 4.3b cho một thí dụ về cách xây dựng đồ thị đối ngẫu. 6' 2' a2 2 3 a1 a7 `` a4 a3 a1 3' ' a2 3 6' ' 1 2' 6 1 a5 5' a8 PTITa5 a 4 4' a6 ' a 4 7 a 4 9 a3 5 a9 a a6 8 5' 1' Hình 4.3 a Hình 4.3 b - Tính đối ngẫu của đường và lát cắt trong đồ thị phẳng Đối với một đồ thị phẳng G = {X.A}, tương ứng với một cặp đỉnh "vào", "ra", ta có thể dựng một đồ thị đối ngấu G' = {X'.A}. 121
4. Bài giảngToán kinh tế Chương 4: Mô hình bài toán tối ưu trên mạng Đường đi trong G = {X.A} sẽ tương ứng với lát cắt trong G' = {X'.A} và ngược lại. Ta có cặp đối ngẫu sau: ' ' Trong G = {X.A} Trong G = {X.A} Đường đi Lát cắt Lát cắt Đường đi - Ý nghĩa mạng của đối ngẫu: Giả sử ta phải chuyển lượng hàng bi > 0 từ mỗi đỉnh i = 1, 2, , n-1 tới đỉnh n theo một mạng riêng của mình. Khi đó nghiệm tối ưu của bài toán dòng trên mạng cho ta cách vận chuyển tốt nhất. Lại giả sử có một công ty vận tải mở dịch vụ vận chuyển từ mọi đỉnh i đến đỉnh n (theo mạng của họ) với giá vận chuyển một đơn vị hàng là pi. Nếu (i, j) là một cung trong mạng riêng của ta và phí tổn vận chuyển một đơn vị hàng trên cung này là cij, thì ta có thể tự chuyển hàng từ i đến j rồi giao cho công ty vận tải chuyển nốt đến đỉnh n, với giá đơn vị là cij + pi. Công ty vận tải biết các véc tơ b và c và tìm cách bao hết việc vận chuyển hàng của ta, kể cả trên cung (i, j). Khi đó họ phải ra giá để cạnh tranh là pi ≤ cij + pj và pn = 0. Với giá đủ hấp dẫn này, coi như ràng buộc, n 1 mục đích của họ tất nhiên là làm cực đại doanh thu  pi b i .Vậy bài toán của công ty chính là bài i 1 toán đối ngẫu với bài toán tự vận chuyển của ta. Định lý đối ngẫu mạnh của quy hoạch tuyến tính nói rằng doanh thu tối ưu của công ty đúng bằng phí tổn tối ưu khi ta tự vận chuyển bằng mạng riêng. Nói cách khác, nếu hai phía đều tìm cách vận chuyển tối ưu và giá của công ty đặt ra đúng thì cước phí là như nhau. 4.1.3. Biểu diễn đồ thị dưới dạng ma trận a. Ma trận liên hệ trực tiếp Giả sử cho đồ thị G = {X .A}, ma trận liên hệ trực tiếp của nó được ký hiệu là A = {aij}, được xác định như sau: 1 , nếu trong G = {X.A} có cung (i, j) (kể cả cung tự nối) a ij , nếu trong G = {X.A} không có cung (i, j) 0 Thí dụ 4.3 Cho đồ thị G = {X.A} như hình 4.4. Khi đó ma trận liên hệ trực tiếp của đồ thị cho ở bảng 4.1 BảngPTIT 4.1 0 1 1 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 1 0 0 1 0 0 0 1 0 122
5. Bài giảngToán kinh tế Chương 4: Mô hình bài toán tối ưu trên mạng a3 ` a1 x2 x1 a2 x3 a9 a4 a8 a5 x6 a10 x 4 a7 x a 5 6 Hình 4.4 Với mỗi đồ thị G = {X.A}ta có một ma trận liên hệ trực tiếp tương ứng, xác định đầy đủ cấu trúc của đồ thị. Tổng các phần tử theo dòng trong bảng 4.1 cho ta số cung đi khỏi đỉnh xi, còn tổng các phần tử theo cột cho ta số cung đi vào đỉnh xi. b. Ma trận liên hệ cung nút Cho đồ thị G = {X.A} có n đỉnh và m cung. Ma trận liên hệ cung nút của đồ thị, ký hiệu là B = {bij}, có kích thước m×n với các phần tử được xác định như sau: 1 , nếu xi là đỉnh đầu của cung aj bij -1 , n ếu xi là đỉnh cuối của cung aj 0 , nếu xi không phải là đỉnh đầu hoặc đỉnh cuối của cung aj hoặc nếu cung aj là cung tự nối Thí dụ 4.4 Đối với đồ thị cho ở hình 4.4 thì ma trận cung nút có dạng như ở bảng 4.2 Bảng 4.2 a1 a2 a3 a4 a5 a6 a7 a8 a9 a10 x1 1 1 0 0 0 0 0 -1 -1 0 x2 -1 0 0 1 0 0 0 0 0 0 x3 0 -1 0 0 -1 0 0 0 0 0 x4 0 0 0 0 1 -1 0 0 0 0 x5 0 0 0 PTIT-1 0 1 -1 1 0 0 x6 0 0 0 0 0 0 1 0 1 0 Vậy mỗi cột của B có đúng hai phần tử khác không là 1 và -1; chỉ đỉnh đầu và đỉnh cuối của cung tương ứng của cột này. Khi xét các hàng ta thấy hàng i ứng với đỉnh i và ràng buộc sẽ là: T a i x  x ij -  x ji bi j O(i) j I(i) T trong đó a i x là hàng i của ma trận B. Như vậy, các phần tử khác 0 (là 1 hoặc -1) trên hàng i của B ở cột nào thì có nghĩa là cung tương ứng cột đó có nối tới đỉnh i (1 ứng với cung đi ra từ đỉnh i, -1 ứng với cung đi vào đỉnh i). Ma trận B gọi là ma trận nối cung - nút hoặc gọi tắt là ma trận nối. Nhận xét rằng tổng tất cả các hàng của B là véc tơ 0. Vì vậy n hàng của B là phụ thuộc tuyến tính. Vì vậy, có thể bỏ đi một hàng (nếu bài toán là chấp nhận được), thường là hàng ứng với đỉnh ra của đồ thị. 123
6. Bài giảngToán kinh tế Chương 4: Mô hình bài toán tối ưu trên mạng 4.2 Bài toán đường đi ngắn nhất 4.2.1 Ý nghĩa và nội dung bài toán Bài toán đường đi ngắn nhất là một bài toán quan trọng nảy sinh từ nhiều bài toán thực tế về vận tải, mạng thông tin, điều khiển tối ưu, Có thể phát biểu một dạng toán học chung cho các bài toán như vậy thành bài toán dòng trên mạng như sau. Cho một đồ thị có hướng G = {X.A}. Mỗi cung (i, j) có cước phí cij > 0 chính là độ dài của cung. Để tìm đường ngắn nhất từ một đỉnh s đến một đỉnh r ta sẽ thấy cần tính nhiều hoặc thậm chí đường ngắn nhất từ mọi đỉnh khác đỉnh r tới đỉnh r. Vì vậy người ta gọi bài toán đường ngắn nhất là bài toán tìm đường đi ngắn nhất từ mọi đỉnh trong X tới một đỉnh r thuộc X cho trước, gọi là đỉnh gốc. Để đưa về bài toán dòng trên mạng, đặt bi = 1 cho mỗi đỉnh i ≠ r và b r -  bi i r Ta có thể giải bài toán đường ngắn nhất bằng thuật toán đơn hình mạng. Đường ngắn nhất từ đỉnh i tới đỉnh r chính là các cung thuộc cây bao trùm tối ưu T nối từ đỉnh i đến đỉnh r (đây là đường đi có hướng, trong đường đi không có cung lùi). Có nhiều cách để giải bài toán tìm đường đi ngắn nhất, nhưng trong khuôn khổ bài giảng này ta nghiên cứu một thuật toán tỏ ra có hiệu quả nhất, đó là thuật toán gán nhãn do Dijkstra công bố năm 1959. Ý tưởng của thuật toán là lần lượt tìm đường đi ngắn nhất từ mỗi đỉnh đến đỉnh gốc ký hiệu là n, bắt đầu từ đỉnh có đường đi này ngắn hơn cả, rồi theo thứ tự đỉnh có đường ngắn hơn làm trước. Cụ thể là lần lượt gán cho các đỉnh của đồ thị một số gọi là nhãn của đỉnh. Cho đỉnh vào của đồ thị là x1 có nhãn bằng 0, sau đó các cung đi từ x1 đến các đỉnh xj, j Г(x1), ta chọn cung có độ dài nhỏ nhất và gán nhãn cố định cho nó.Tiếp theo trong các cung đi từ một đỉnh đã có nhãn cố định đến một đỉnh có nhãn tạm thời ta lại chọn cung sao cho độ dài của nó cộng với nhãn của đỉnh đã được gán nhãn là nhỏ nhất, giá trị này được gán cho đỉnh cuối của đường đi này. Quá trình tiếp tục cho đến khi đỉnh cuối (đỉnh gốc) được gán nhãn cố định. 4.2.2 Thuật toán Dijkstra Cho đồ thị G = {X.A}, tìm đường đi ngắn nhất từ xs đến xt, ký hiệu L(xi) là nhãn của đỉnh xi (i = 1,n ). Thuật toán như sau: Bước 1: Đặt L(x1) = L(xs) = +0 và coi đây là nhãn cố định. Đặt L(xi) = +∞ với i≠1PTIT và xem các đỉnh này có nhãn tạm thời. Gán xp ≡ xs Bước 2: Với tất cả các đỉnh xi Г(xp) có nhãn tạm thời sẽ được thay đổi nhãn tạm thời mới theo điều kiện sau: L(xi) = Min{L(xi); L(xp) + cpi} (4.1) Bước 3: Trong số các đỉnh đang có nhãn tạm thời (cũ và mới thay đổi) ta tìm một đỉnh j có nhãn tạm thời thỏa mãn điều kiện: * L (xj) = Min{L(xi)│L(xi) có nhãn tạm thời mới} (4.2) Coi nhãn của đỉnh xj ứng với điều kiện (4.2) là nhãn cố định và đặt xp ≡ xj chuyển sang bước sau. Bước 4: a. Nếu chỉ cần tìm đường đi ngắn nhất từ đỉnh xs đến đỉnh xt thì có hai trường hợp xảy ra: - Khi xp≡xt thì L(xp) là chiều dài đường đi ngắn nhất cần tìm. Thuật toán dừng. - Khi xp ≠ xt quay lại bước 2. 124
7. Bài giảngToán kinh tế Chương 4: Mô hình bài toán tối ưu trên mạng b. Nếu cần tìm đường đi ngắn nhất từ đỉnh xs đến các đỉnh còn lại của đồ thị, thì có hai trường hợp xảy ra: - Khi nhãn của tất cả các đỉnh là nhãn cố định thì trị số nhãn của đỉnh xj (j ≠ s) là chiều dài đường đi ngắn nhất từ đỉnh xs đến đỉnh xj trong đồ thị G = {X.A}. - Nếu đồ thị vẫn còn đỉnh có nhãn tạm thời thì quay lại bước 2. Thí dụ 4.5 Cho đồ thị G ={X.A} thể hiện bởi ma trận khoảng cách cho ở bảng 4.3. Các trị số trong các ô biểu thị độ dài đường đi từ i đến j.(đơn vị tính: km) Hãy vẽ đồ thị G và tìm đường đi ngắn nhất từ đỉnh x1 đến tất cả các đỉnh còn lại. Bảng 4.3 x1 x2 x3 x4 x5 x6 x7 x8 x9 x1 10 3 6 12 x2 10 18 2 13 x3 18 25 20 7 x4 25 5 16 4 x5 5 10 x6 20 10 14 15 9 x7 2 4 14 24 x8 6 23 5 x9 12 13 9 24 5 Giải bài toán bằng thuật toán Dijkstra: 18 x2 x3 25 10 20 2 13 x4 7 x1 4 3 16 x7 14 x6 24 12 PTIT9 5 x9 10 6 15 5 x x 8 5 23 Hình 4.5 Vòng lặp 1: Bước 1: Đặt L(x1) = +0; L(xi) = +∞  i ≠ 1. Đặt xp ≡ x1 → B2 Bước 2: Г(xp) = Г(x1) = {x2, x7, x8, x9}, các đỉnh x2, x7, x8, x9 được thay nhãn tạm thời như sau: L(x2) = Min{L(x2); L(xp)+cp2} = Min{+∞; 0 + 10} = 10 L(x7) = Min{L(x7); L(xp)+cp7} = Min{+∞; 0 + 3} = 3 L(x8) = Min{L(x8); L(xp)+cp8} = Min{+∞; 0 + 6} = 6 L(x9) = Min{L(x9); L(xp)+cp9} = Min{+∞; 0 + 12} = 12 Bước 3: Gán nhãn có định 125
8. Bài giảngToán kinh tế Chương 4: Mô hình bài toán tối ưu trên mạng * L (xi) = Min{L(x2), L(x7), L(x8), L(x9), L(x3), L(x4), L(x5), L(x6) = Min{10, 3, 6, 12, +∞, +∞, +∞, +∞, +∞} = 3- ứng với đỉnh x7. Gán xp ≡ x7 → B4 Bước 4: Đồ thị còn có nhãn tạm thời → B2 Vòng lặp 2: Bước 2: Г(xp) = Г(x7) = {x2, x4, x6, x9}, các đỉnh x2, x4, x6, x9 được thay nhãn tạm thời như sau: L(x2) = Min{L(x2); L(xp)+cp2} = Min{10; 3 + 2} = 5 L(x4) = Min{L(x4); L(xp)+cp4} = Min{+∞; 3 + 4} = 7 L(x6) = Min{L(x6); L(xp)+cp6} = Min{+∞; 3 + 14} = 17 L(x9) = Min{L(x9); L(xp)+cp9} = Min{12; 3 + 24} = 12 Bước 3: Gán nhãn có định * L (xi) = Min{L(x2), L(x8), L(x9), L(x4), L(x6), L(x3), L(x5), = Min{5, 6, 12, 7, 17 +∞, +∞, +∞, +∞, +∞} = 5- ứng với đỉnh x2. Gán xp ≡ x2 → B4 Bước 4: Đồ thị còn có nhãn tạm thời → B2 Vòng lặp 3: Bước 2: Г(xp) = Г(x2) = {x3, x9}, các đỉnh x3, x9 được thay nhãn tạm thời như sau: L(x3) = Min{L(x3); L(xp)+cp3} = Min{+∞; 5 + 18} = 23 L(x9) = Min{L(x9); L(xp)+cp9} = Min{12; 5 + 13} = 12 Bước 3: Gán nhãn có định * L (xi) = Min{L(x8), L(x9), L(x4), L(x6), L(x3), L(x5), = Min{ 6, 12, 7, 17, 23 +∞} = 6- ứng với đỉnh x8. Gán xp ≡ x8 → B4 Bước 4: Đồ thị còn có nhãn tạm thời → B2 Vòng lặp 4: Bước 2: Г(xp) = Г(x8) = {x5, x6, x9}, các đỉnh x5, x6, x9 được thay nhãn tạm thời như sau: L(x5) = Min{L(x5); L(xp)+cp5} = Min{+∞; 6 + 23} = 29 L(x6) = Min{L(x6); L(xp)+cp6} = Min{17; 6 + 15} = 17 L(x9) = Min{L(x9); L(xp)+cp9} = Min{12; 6 + 5} = 11 Bước 3: Gán nhãn có định * L (xi) = Min{L(x9), L(x4), L(x6), L(x3), L(x5), = Min{ 11, 7, 17, 23, 29} = 7- ứng với đỉnh x4. Gán xp ≡ x4 → B4 Bước 4: Đồ thị còn có nhãn tạmPTIT thời → B2 Vòng lặp 5: Bước 2: Г(xp) = Г(x4) = {x3,x5, x6}, các đỉnh x3,x5, x6 được thay nhãn tạm thời như sau: L(x3) = Min{L(x3); L(xp)+cp3} = Min{23; 7 + 25} = 23 L(x5) = Min{L(x5); L(xp)+cp5} = Min{29; 7 + 5} = 12 L(x6) = Min{L(x6); L(xp)+cp6} = Min{17; 7 + 16} = 17 Bước 3: Gán nhãn có định * L (xi) = Min{L(x9), L(x6), L(x3), L(x5), = Min{ 11, 17, 23, 12} = 11- ứng với đỉnh x9. Gán xp ≡ x9 → B4 Bước 4: Đồ thị còn có nhãn tạm thời → B2 Vòng lặp 6: Bước 2: Г(xp) = Г(x9) = {x6}, các đỉnh x6 được thay nhãn tạm thời như sau: L(x6) = Min{L(x6); L(xp)+cp6} = Min{17; 11 + 9} = 17 Bước 3: Gán nhãn có định 126
9. Bài giảngToán kinh tế Chương 4: Mô hình bài toán tối ưu trên mạng * L (xi) = Min{L(x6), L(x3), L(x5)} = Min{ 17, 23, 12} = 12- ứng với đỉnh x5. Gán xp ≡ x5 → B4 Bước 4: Đồ thị còn có nhãn tạm thời → B2 Vòng lặp 7: Bước 2: Г(xp) = Г(x5) = {x6}, các đỉnh x6 được thay nhãn tạm thời như sau: L(x6) = Min{L(x6); L(xp)+cp6} = Min{17; 12 + 10} = 17 Bước 3: Gán nhãn có định * L (xi) = Min{L(x6), L(x3)} = Min{ 17, 23} = 17- ứng với đỉnh x6. Gán xp ≡ x6 → B4 Bước 4: Đồ thị còn có nhãn tạm thời → B2 Vòng lặp 8: Bước 2: Г(xp) = Г(x6) = {x3}, các đỉnh x3 được thay nhãn tạm thời như sau: L(x3) = Min{L(x3); L(xp)+cp3} = Min{23; 17 + 20} = 23 Bước 3: Gán nhãn có định * L (xi) = Min{L(x3)} = Min{ 23} = 23- ứng với đỉnh x3. Gán xp ≡ x6 → B4 Bước 4: Đồ thị không còn nhãn tạm thời. Stop. Chú ý: - Để tìm lộ trình đường đi ngắn nhất từ đỉnh s đến các đỉnh còn lại ta bắt đầu từ đỉnh gốc lần ngược lại liên tiếp theo quan hệ sau: * * L (xj) - cij = L (xi) (4.3) trong đó xj là đỉnh nằm liền kề trước đỉnh xi trên đường đi ngắn nhất từ đỉnh xs đến đỉnh xj. - Nếu đường đi ngắn nhất từ đỉnh xs đến đỉnh xt là duy nhất thì các cạnh hoặc cung (i, j) của đường đi ngắn nhất này tạo nên một cây có gốc là xs và ngọn là xt.Nếu đường đi này không duy nhất thì có nhiều cây tương ứng. - Thuật toán Dijkstra chỉ áp dụng được khi cij ≥ 0. Trong trường hợp tổng quát, cij có thể âm, khi đó có thuật toán giải riêng. 4.3 Mạng liên thông 4.3.1 Nội dung và ý nghĩa của bài toán a. Nội dung bài toán: Cho đồ thị vô hướng đối xứng G X.A , với tập X = {x1, x2, , xn}; tập A = {a1, a2, , am}, mỗi cạnh củaPTIT đồ thị gán một số không âm, gọi là độ dài của cạnh. Hãy tìm một cây bao trùm có tổng độ dài các cạnh là nhỏ nhất? Theo định nghĩa cây là một đồ thị liên thông và không chứa chu trình. Cây của một đồ thị liên thông n đỉnh gồm n-1 cạnh không chứa chu trình. b. Ý nghĩa của bài toán: Nếu coi các đỉnh của đồ thị là các điểm cần đặt máy điện thoại cố định thuê bao thì nên thiết kế mạng đường dây theo những cạnh nào để tổng chiều dài đặt dây là nhỏ nhất tính từ tổng đài nội hạt đến các thuê bao. Hoặc phải thiết kế hệ thống cáp truyền thông như thế nào để cung cấp thông tin đến các địa phương trong vùng từ một trung tâm viễn thông sao cho tiết kiệm cáp nhất. Nếu xem các đỉnh của đồ thị là những thành phố và các trung tâm huyện lỵ, muốn xây dựng mạng lưới giao thông nối liền tất cả các điểm đó lại sao cho tổng kinh phí xây dựng là nhỏ nhất. 4.3.2 Thuật toán Prim Ta có thể tìm cây bao trùm của đồ thị sao cho tổng độ dài các cạnh thuộc cây là nhỏ nhất theo thuật toán đơn giản sau đây do Prim đề xuất. Đầu tiên ta chọn một cạnh ngắn nhất trong đồ thị làm 127
10. Bài giảngToán kinh tế Chương 4: Mô hình bài toán tối ưu trên mạng gốc cây. Sau đó, cắt trong tất cả các cạnh có một đầu mút thuộc phần cây đã chọn và một đầu mút ở ngoài cây và ta chọn cạnh có độ dài nhỏ nhất nối vào cây. Quá trình tiếp tục cho đến khi cây có đủ n - 1 cạnh thì ta nhận được cây bao trùm có tổng độ dài nhỏ nhất. Có thể có nhiều cây như vậy, nhưng tổng độ dài của các cây bằng nhau. Có thể làm ngược lại, trên đồ thị chọn cạnh có độ dài lớn nhất "xóa" khỏi đồ thị, kiểm tra xem đồ thị còn liên thông hay không, nếu có thì tìm cạnh có độ dài lớn nhất tiếp theo và "xóa" khỏi đồ thị rồi lại kiểm tra tính liên thông của đồ thị. Quá trình tiếp tục cho đến khi đồ thị còn đúng n - 1 không chứa chu trình thì ta nhận được cây bao trùm có tổng độ dài nhỏ nhất. Thí dụ 4.6 Cho đồ thị vô hướng G X.A , mỗi cạnh gán một giá trị c > 0 gọi là độ dài cạnh, như ij hình 4.5 11 x2 x5 10 x8 12 7 6 7 8 5 x3 x6 12 12 x1 x9 x11 3 6 9 10 12 10 x4 9 x7 x10 Hình 4.5 Giải bằng thuật toán Prim: Đầu tiên ta chọn cạnh ngắn nhất (3,4) làm gốc cây, tiếp đó chọn cạnh (3,6) nối vào cây, rồi lần lượt chọn cạnh (3,2), (6,7), (5,6), (5,8), (8,11), (8,9), (9,10) và cuối cùng là chọn cạnh (1,2) hoặc (1,4). Đến đây ta có đủ n - 1 = 10 cạnh và ta được một cây bao trùm có tổng độ dài các cạnh là ngắn nhất, hình 4.6 x2 x5 x8 PTIT x1 x3 x6 x11 x9 x 4 x7 x10 Hình 4.6 4.4 Bài toán luồng lớn nhất 4.4.1 Nội dung bài toán: Cho một đồ thị có hướng G = {X.A}có tải năng các cung là uij, (i, j) A, có thể bằng +∞. Giả sử s và t là hai nút đặc biệt, gọi tương ứng là nguồn và đích. Bài toán đặt ra là tìm dòng lớn nhất có thể chuyển qua mạng từ s đến t? Phát bểu toán học của bài toán là: Maxbs, 128
11. Bài giảngToán kinh tế Chương 4: Mô hình bài toán tối ưu trên mạng Ax = b, bt = -bs. bi = 0, i s, t , 0 ≤ xij ≤ uij, (i, j) A Giá trị của bs sẽ gọi là giá trị của dòng chấp nhận được tương ứng. Bài toán luồng lớn nhất có thể đưa về bài toán dòng trên mạng bằng cách sau. Trước hết, ta phải đưa vào các cij. Ta đặt cij = 0 (i, j) A . Ta vẽ thêm cung mới (t, s) với uts = +∞ và cts = - 1. Tìm cực tiểu hàm mục tiêu cijx ij  - x ts ở bài toán dòng trên mạng mới được đặt, do đó, chính là dòng chấp nhận được sao (i, j) cho xts là lớn nhất. Nhưng vì bài toán mới đặt không có nguồn và đích nên toàn bộ dòng này phải đi qua mạng để từ s quay lại t. Vậy xts chính là giá trị nghiệm của bài toán luồng lớn nhất. Ngược lại, việc tìm dòng chấp nhận được của bài toán dòng trên mạng có tải năng hạn chế có thể đưa về giải bài toán luồng lớn nhất như sau. Trước hết ta bỏ các hệ số cij đi và đưa thêm vào nút nguồn s và nút đích t. Ta vẽ thêm cung (s, j) tới mỗi đỉnh j có bi > 0 và đặt tải năng của nó là usj = bj và cung (i, t) từ mỗi nút t có bi < 0 và đặt uti = -bi. Vì ∑bk = 0 ta có ∑usj = ∑uit := w. Bây giờ ta đưa vào khái niệm cắt, dùng đến nhiều cho bài toán luồng lớn nhất. Một tập con S của tập các đỉnh X được gọi là một cắt hoặc cụ thể hơn, (s.t) cắt của bài toán luồng (dòng) lớn nhất nếu s S và t S. Dung lượng C(S) của cắt S là tổng tải năng của các cung đi từ S ra ngoài phần bù của S, tức là các cung có đuôi thuộc S, đầu không thuộc S. Vậy: CS  uij (i,j) A:i S,j S Mỗi dòng đi từ s đến t có thể tách thành hai phần là tổng các dòng trên các cung ra khỏi S trừ đi tổng các dòng trên các cung quay ngược lại S. Tức là mỗi véc tơ dòng x có giá trị v (chính là dòng từ s đến t): v  x jk -  x ij (4.4) j S,k S i S, j S Nói riêng, nếu lấy S = {s} thì v =  xsk hoặc S = X\{s} thì v =  x jt , vì ta luôn giả thiết là trong k s j t mạng không có cung dạng (t,j), tức là cung ra khỏi điểm hút. từ (4.4) ta thấy ngay là giá trị của mọi dòng chấp nhận được (từ sPTIT đến t) phải thỏa mãn: v ≤ C(S) (4.5) với mọi cắt S. Vậy dung lượng của bất kỳ cắt nào cũng là một "cổ chai" mà dòng cực đại không thể vượt quá được. Bây giờ quay lại bài toán luồng lớn nhất ta vừa lập từ bài toán dòng trên mạng. Rõ ràng giá trị w = ∑usj = ∑uit là dung lượng của cắt gồm chỉ có đỉnh s (và cũng là dung lượng của cắt gồm mọi đỉnh, chỉ trừ đỉnh t). Do đó theo (4.5) mọi dòng chấp nhận được của bài toán luồng lớn nhất đang xét đều có giá trị không vượt quá w. Cụ thể hơn là đối với dòng x chấp nhận được của bài toán luồng lớn nhất này thì 3 khẳng định sau là tương đương: - Giá trị của x là w. - xsj = usj với mọi cung (s,j). - xit = uit với mọi cung (i,t). 129
12. Bài giảngToán kinh tế Chương 4: Mô hình bài toán tối ưu trên mạng Dễ thấy dòng chấp nhận được của bài toán luồng lớn nhất (mà có giá trị w) luôn là dòng chấp nhận được của bài toán dòng chấp nhận được ban đầu (vì ở các điểm nguồn và điểm đích luật bảo toàn dòng được thỏa mãn, còn ở các đỉnh khác thì sự bảo toàn dòng ở hai bài toán là như nhau). Ngược lại, mỗi dòng chấp nhận được của bài toán dòng trên mạng phải thỏa xsj = usj theo sự bảo toàn dòng ở các điểm nguồn (vì usj = bsj), nên phải là dòng chấp nhận được với giá trị w của bài toán luồng lớn nhất tương ứng. Định lý 4.3 Đối với bài toán luồng lớn nhất đúng một trong hai trường hợp sau sẽ xảy ra: - Có dòng chấp nhận được với giá trị lớn tùy ý và mọi cắt đều có dung lượng vô hạn. - Tồn tại luồng lớn nhất và giá trị của nó là cực tiểu của dung lượng của tất cả các cắt. Bài toán tìm luồng lớn nhất trên một mạng có nhiều điểm nguồn và nhiều điểm đích có thể dễ dàng quy về bài toán luồng lớn nhất trên mạng chỉ có một điểm nguồn và một điểm đích bằng cách thêm vào các đỉnh giả và cung giả thích hợp như hình 4.7a, b y1 y1 x1 x1 ∞ ∞ y2 x0 y2 ∞ y0 x 2 ∞ ∞ x y3 2 a) y3 b) Hình 4.7 4.4.2 Thuật toán Ford - Fulkerson a. Ý tưởng của thuật toán. Xuất phát từ luồng không (xij = 0  (i,j)). Tiếp đó, tìm một đường đi từ đỉnh nguồn xs đến đỉnh đích xt (xs và xt xác định trước) sao cho trên cạnh có vận chuyển theo chiều thuận (từ điểm nguồn tới điểm hút) thì lượng hàng vận chuyển chưa đạt tới khả năng thông qua của cung có dung lượng nhỏ nhất. Nếu không có đường đi nào như thế thì luồng hiện có là luồng lớn nhất, còn nếu phát hiện có đường đi như thế thì điều chỉnh luồng hiện có như sau: thêm một lượng hàng h vào mỗi cung chưa vận chuyển hoặc cóPTIT vận chuyển hàng theo chiều thuận, giảm lượng hàng vận chuyển h trên các cung có vận chuyển hàng theo chiều ngược (từ điển hút về điểm nguồn), với h là giá trị lớn nhất có thể được sao cho luồng sau khi điều chỉnh vẫn còn phù hợp với khả năng thông qua của mạng, nghĩa là 0 ≤ xij ≤ uij. Mỗi lần điều chỉnh như vậy ta sẽ vận chuyển thêm được h đơn vị hàng từ điểm nguồn tới điểm hút. Sau khi điều chỉnh ta kiểm tra xem có đường đi nào từ điểm nguồn đến điểm đích có tính chất trên không, nếu không thì thuật toán dừng. Nếu có thì điều chỉnh luồng như trên. Quá trình tiếp tục sau một số hữu hạn bước ta sẽ thu được luồng lớn nhất. b. Lược đồ thuật toán: Bước 0: Xuất phát từ luồng 0 (chưa vận chuyển xij = 0 trên mọi cung), ta lần lượt gán cho các đỉnh của đồ thị một cặp số, gọi là nhãn, như sau: gán cho đỉnh nguồn (đỉnh x0) nhãn (∞,0). Mỗi đỉnh trong quá trình thực hiện thuật toán sẽ ở một trong ba trạng thái: chưa có nhãn, có nhãn chưa xét và có nhãn đã xét. Nhãn của đỉnh gồm hai phần và có một trong hai dạng sau: [(ei,pi)] hoặc [(ei,-pi)] 130
13. Bài giảngToán kinh tế Chương 4: Mô hình bài toán tối ưu trên mạng Phần thứ nhất chỉ ra lượng lớn nhất có thể tăng hoặc giảm luồng theo cung này, còn phần thứ hai chỉ ra cần tăng hay giảm luồng theo cung (i,j) hay (j,i). Đầu tiên chỉ có đỉnh xs được khởi tạo nhãn và nhãn của nó là chưa xét, các đỉnh còn lại đều chưa có nhãn. Từ xs ta gán nhãn cho các đỉnh kề với nó và nhãn của đỉnh xs trở thành đã xét Bước 1: Gọi N1 là tập các đỉnh i (i ≠ s) của mạng nối trực tiếp với đỉnh nguồn bởi một cung mà lượng hàng vận chuyển từ đỉnh nguồn trên đó chưa vượt quá khả năng thông qua. tiếp sau đó ta gán cho đỉnh i thuộc N1 một cặp số (ei,pi) gọi là nhãn, như sau: ei = u1i - x1i = khả năng thông qua còn lại trên cung (0,i) pi = 0 = Số hiệu của đỉnh nguồn đến đỉnh i. Nếu N1 chứa đỉnh nguồn (hút) xt thì chuyển sang thức hiện bước 5 để tăng giá trị của luồng. Trái lại chuyển sang bước 2. Bước 2: Ký hiệu N2 là tập hợp tất cả các đỉnh j chưa được gán nhãn của đồ thị sao cho đỉnh này được nối với một đỉnh đã được gán nhãn thuộc tập N1, chẳng hạn đỉnh i, bởi cung (i,j) với xij 0. tiếp theo, ta gán cho mỗi đỉnh j một cặp số (ej,pj) gọi là nhãn, theo công thức sau: min(ei ; uij - xij ) nếu xij 0 min(ei , uij ) ij pj = i. Chuyển sang bước 3 Bước 3: Lặp lại bước 2 với Nt thay cho Nt-1. Sau một số hữu hạn bước ta gặp một trong hai tình huống sau: 3a. Nhãn của tất cả các đỉnh có nhãn đã xét nhưng đỉnh xt vẫn không có nhẫn. Thuật toán dừng. Luồng hiện có là lớn nhất.(Không tồn tại đường tăng luồng) 3b. Đỉnh xt đã được gán nhãn. Chuyển sang bước 4. Bước 4: Tăng luồng hiện có như sau: Giả sử đỉnh đích (điểm hút) (xt) đã được gán nhãn (et,pt), et chỉ rõ lượng hàng sẽ vận chuyển thêm từ nguồn đến đích, số thứ hai (pt) cho biết đỉnh đã được dùng để gán nhãn cho đỉnh đích. Dựa vào số thứ hai trong nhãn của đỉnh đích ta tìm được đỉnh trước đó,v.v cứ thế ta lần ngược lại đỉnh nguồn. Kết quả là xác định được đường đi từ nguồn tới đích làm tăng giá trị luồng. Cách điều chỉnh luồng như sau: - Nếu cạnh (i,j) không thuộc đường đi trên thì luồng giữ nguyên. - Nếu cạnh (i,j) thuộc đường đi này và thuận chiều thì khi đó trên cạnh này xij 0, ta đặt: ' x ij = xij - et . Chuyển sang bước 5. Bước 5: Xóa nhãn của mọi đỉnh, trừ đỉnh nguồn rồi quay lại bước 1. Đối với luồng mới thu được ta lại sử dụng phép gán nhãn các đỉnh để tìm đường đi tăng.Thuật toán sẽ kết thúc sau một số hữu hạn bước, nghĩa là sau một số hữu hạn lần áp dụng các bước từ 1 đến 5 ta sẽ gặp trường hợp 3a.(trong mạng không tìm được đường đi tăng) Thí dụ 4.7: Cho đồ thị như ở hình 4.8. số ghi trên mỗi cung là khả năng thông qua của cung. Đỉnh 1 là đỉnh nguồn, đỉnh 7 là điểm hút. 131
14. Bài giảngToán kinh tế Chương 4: Mô hình bài toán tối ưu trên mạng 2 2 4 3 ` 2 6 7 1 3 5 1 1 1 3 3 3 6 2 Hình 4.8 Giải: Xuất phát từ luồng 0. Đỉnh nguồn được gán nhãn (∞, 0). Ở bước lặp đầu tiên ta gán cho đỉnh 2 nhãn: e2 = u12 = 6; p2 = 1. Gán cho đỉnh 3 nhãn: e3 = u13 = 3; p3 = 1 Tiếp đó dựa vào các đỉnh đã được gán nhãn 2 và 3, ta gán cho đỉnh 4 nhãn: e4 = min(e2, u24) = min(6, 2) = 2; p4 = 2. Gán cho đỉnh 5 nhãn: e5 = min(e3, u35)= min(3, 1)= 1; p5 = 3. Gán cho đỉnh 6 nhãn: e6 = min(e3,u36) = min(3, 2) = 2; p6 = 3. Gán cho đỉnh 7 nhãn: e7 = min(e4, u47) = min(2, 3) = 2; p7 = 4. Đỉnh 7 là điểm hút được gán nhãn. Ta vận chuyển e7 = 2 đơn vị hàng theo đường 1-2-4- 7 (x12 = x24 = x47 = 2, các đỉnh khác xij = 0), giá trị luồng tương ứng là 2. Ở vòng lặp tiếp theo, ta gán cho đỉnh 2 nhãn: e2 = u12 - x12 = 6 -2 = 4, p2 = 1. Gán cho đỉnh 3 nhãn e3 = u13 = 3, p3 = 1. Tiếp đó gán cho đỉnh 5 nhãn: e5 = min(e3, u35) = min(3, 1) = 1, p5 = 3. Gán cho đỉnh 6 nhãn e6 = min(e3,u36) = min(3, 2) = 2, p6 = 3. Lúc này đỉnh 4 không được gán nhãn vì cung (2,4) đã vận chuyển hết khả năng thông qua. Cuối cùng dựa vào các đỉnh đã được gán nhãn 5 và 6 ta gán cho đỉnh 7 nhãn e7 = min(e5, u57) = min(1,1) = 1. p7 = 5. Đỉnh 7 là đỉnh hút đã được gán nhãn. Ta vận chuyển e7 = 1 đơn vị hàng theo đường 1-3-5-7 (x13 = x35 = x57 = 1, các xij khác không đổi). Giá trị luồng bây giờ là 2 + 1 = 3. Ở vòng lặp thứ ba, ta gán cho đỉnh 2 nhãn: e2 = u12 - x12 = 6 -2 = 4, p2 = 1. Gán cho đỉnh 3 nhãn: e3 = u13 - x13 = 3 - 1 = 2, p3 = 1. Tiếp theo gán cho đỉnh 6 nhãn: e6 = min(e3, u36) = min(2, 2) = 2, p6 = 3. Lúc này đỉnh 4, 5 khôngPTIT được gán nhãn. từ đỉnh 6 ta gán cho đỉnh 7 nhãn: e7 = min(e6,u67) = min(2, 3) = 2, p7 = 6. Kết quả ta vận chuyển thêm được e7 = 2 đơn vị hàng theo đường 1-3-6-7(x13 = x36 = x67 = 2, các xij khác không đổi). Giá trị của luồng bây giờ là 3 + 2 = 5. Để kiểm tra luồng hiện có đã lớn nhất hay chưa, ta tiếp tục quá trình gán nhãn: ta gán cho đỉnh 2 nhãn: e2 = u12 - x12 = 4, p2 = 1. Gán cho đỉnh 3 nhãn: e3 = min(e2, u23) = min(4, 3) = 3, p3 = 2. Đến đây đỉnh 7 chưa được gán nhãn nhưng ta không thể gán nhãn cho đỉnh nào nữa (tình huống 3a). Vậy luồng hiện có là lớn nhất. Đó là: x12 = 2, x13 = 3, x24 = 2 x35 = 1; x36 = 2, x47 = 2, x57 = 1, x67 = 2. Lượng hàng vận chuyển lớn nhất từ điểm nguồn đến điểm hút là 5 đơn vị. Các lát cắt nhỏ nhất C(S) là (2,4), (3,5) và (3,6). tổng cộng khả năng thông qua trên các cung này đúng bằng 5 đơn vị. Thí dụ 4.8: Mạng vận tải gồm 4 nút. Nút nguồn là A, nút đích (điểm hút) là D. Các đường đi tăng được tìm bằng phương pháp tìm kiếm theo chiều sâu, trong đó các đỉnh lân cận được duyệt theo 132
15. Bài giảngToán kinh tế Chương 4: Mô hình bài toán tối ưu trên mạng thứ tự bảng chữ cái. Thí dụ nà cho thấy biểu hiện của trường hợp xấu nhất của thuật toán. Mỗi bước chỉ gửi thêm được một luồng có giá trị bằng 1. B B 0/1000 0/1000 1/1000 0/1000 A 0/1000 D A 1/1000 D 0/1000 0/1000 0/1000 1/1000 CA C B B 1/1000 1/1000 1/1000 1/1000 A 0/1000 D A 0/1000 D 1/1000 1/1000 1/1000 1/1000 C C Thuật toán đánh dấu: Nếu tồn tại một đường đi từ nguồn đến đích với điều kiện tất cả các cung trên đường đi đó vẫn còn khả năng thông qua thì ta sẽ gửi đi một luồng dọc theo đường đi đó. Sau đó ta tìm một đường đi khác và tiếp tục như vậy. Một đường đi còn khả năng thông qua là một đường đi có khả năng mở rộng thêm hay một đường đi mà luồng qua đó còn khả năng tăng thêm - gọi tắt là đường tăng. Cho đồ thị G = {X.A}, với khả năng thông qua uij và luồng f(i,j) = 0 trên các cung từ i đến j. Ta muốn tìm luồng cực đại từ nút nguồn s đến đến điểm hút t. Sau mỗi bước các điều kiện sau đây được duy trì: - f(i,j) ≤ c(i,j): Luồng từ i đến j không vượt quá khả năng thông qua. - f(i,j) = - f(j,i): Cân bằng luồng - f(i,j) = 0 cho tất cả các nút ngoại trừ s và t. Lượng vào nút bằng lượng ra khỏi nút. X Điều này có nghĩa là một luồng đi qua một mạng là một luồng hợp lệ sau mỗi vòng của thuật toán. Chúng ta định nghĩa mạng cònPTIT dư Gt = {X, At} là mạng với sức chứa ut(i,j) = uij - f(i,j) và luồng bằng 0. Chú ý rằng không chắc chắn là A = At bởi vì việc gửi luồng theo cung (i,j) (làm nó bảo hòa), nhưng lại mở một cung mới (j,i) trong mạng còn dư. Đầu vào: Đồ thị G với khả năng thông qua u. Nút nguồn s và nút đích t. Đầu ra: Luồng f sao cho f là cực đại từ s đến t. - f(i,j) ← 0 trên tất cả các cung (i,j). - Trong khi còn có một đường đi từ s đến t trong Gt: Tìm một đường đị x1, x2, , xk với x1 s, xk t: ut(xt,xt+1) > 0 Tìm m = Min{ut(xt,xt+1)}. f(xi, xi+1) ← f(xi, xi+1) + m: Gửi luồng dọc theo đường đi.(chiều thuận) f(xi+1, xi,) ← f(xi+1, xi,) - m: Luồng có thể "quay lại" sau.(Chiều ngược) Khái niệm mạng còn dư: Thể hiện lượng khả năng thông qua hiện có.Để ý rằng có thể có một cung từ i đến j trong mạng còn dư, ngay cả khi không có cung từ i đến j trong mạng ban đầu. Do 133
16. Bài giảngToán kinh tế Chương 4: Mô hình bài toán tối ưu trên mạng các luồng theo các hướng ngược nhau triệt tiêu lẫn nhau. Giảm luồng từ j đến i tương đương với tăng luồng từ i đến j. Khái niệm đường đi tăng: là một đường đi từ x1, x2, , xk trong đó x1 s và xk t và ut(xi,xi+1) > 0. Nghĩa là có thể gửi thêm luồng dọc theo đường đi này. 4. 5. Bài toán luồng nhỏ nhất 4.5.1 Bài toán Cho một đồ thị đối xứng có n đỉnh, mỗi cạnh có khả năng thông qua nhất định và có một cước phí vận chuyển xác định (như nhau theo cả hai chiều). Cho trước một lượng S cần phải vận chuyển từ đỉnh nguồn (đỉnh số 1) tới điểm hút (số n). Hãy tìm một phương án vận chuyển sao cho phù hợp với khả năng thông qua của mạng và vận chuyển được lượng hàng S từ nguồn đến điểm hút với tổng chi phí vận chuyển là nhỏ nhất. Đây là bài toán vận tải hạn chế khả năng thông qua. Tuy bài toán có một đỉnh nguồn và một điểm hút, như bất kỳ bài toán vận tải trên mạng có nhiều nguồn và nhiều điểm hút có thể quy về bài toán dạng trên bằng cách thêm vào các đỉnh giả và cung giả thích hợp như đã trình bày trong bài toán luồng lớn nhất. Về mặt toán học, bài toán luồng chi phí nhỏ nhất có thể phát biểu như sau: Cực tiểu hàm chi phí cijx ij với các điều kiện của bài toán: i, j A S , nếu i = 1 , nếu i ≠ 1, i ≠ n  x ji -  x ij 0 i i - S , nếu i = n Ở đây đỉnh nguồn được đánh số 1, đích đánh số n, cij là chi phí vận chuyển một đơn vị hàng trên cạnh (i, j), uij là khả năng thông qua của cạnh (i, j), xij là khối lượng hàng vận chuyển trên cạnh (i, j) và là biến cần xác định. 4.5.2 Phương pháp giải: Luồng chi phí nhỏ nhất có thể giải bằng thuật toán đơn giản như sau: Xuất phát từ phương án vận chuyển không (xij = 0 trên mọi cạnh của đồ thị). Ở mỗi bước lặp, ta tìm đường đi có chi phí nhỏ nhất từ nguồn đến điểm hút. Đường đi này bao gồm một dãy các cạnh kế tiếp nhau sao cho trên các cạnh có vận chuyển hàng theo chiều thuận thì lượng hàng vận chuyển chưa vượt quá khả năng thông qua của cạnh đó. TrPTITên đường đi này, cạnh chưa vận chuyển hàng hoặc có vận chuyển hàng theo chiều thuận thì chi phí vận chuyển là số dương, còn trên cạnh vận chuyển hàng theo chiều ngược thì chi phí vận chuyển là âm Tiếp đó, ta xác định khả năng thông qua của đường đi vừa tìm được, đó là số nhỏ nhất trong số các khả năng thông qua còn lại trên các cạnh có chi phí vận chuyển âm. Thêm khả năng thông qua này vào các cạnh chưa vận chuyển hàng hoặc vận chuyển hàng theo chiều thuận và bớt đi ở các cạnh vận chuyển hàng theo chiều ngược của đường đi này, rồi chuyển sang bước lặp sau. Quá trình tiếp tục cho đến khi vận chuyển hết lượng hàng S từ nguồn đến điểm hút hoặc phát hiện mạng không đủ khả năng vận chuyển hết lượng hàng S từ nguồn đến điểm hút. Chú ý: Ở mỗi bước lặp ta phải giải một bài toán phụ: tìm đường đi ngắn nhất từ nguồn đến điểm hút trên mạng với cước phí có thể là số âm. Thí dụ 4.9 Cho đồ thị vô hướng như hình 4.9. Mỗi cạnh tương ứng với một cặp số thứ tự mà số thứ nhất là chi phí vận chuyển một đơn vị hàng trên cạnh, số thứ hai là khả năng thông qua của 134
17. Bài giảngToán kinh tế Chương 4: Mô hình bài toán tối ưu trên mạng cạnh này. Đỉnh nguồn là đỉnh 1, điểm hút là 6. Tổng khối lượng hàng cần vận chuyển từ đỉnh nguồn đến điểm hút là 5 đơn vị. 4 (4,1) (3,4) (2,4) 6 1 (1,2) 3 (1,2) (1,4) (6,2) (5,2) 2 5 Hình 4.9 Giải: Ở bước lặp đầu tiên, phương án vận chuyển bằng 0 trên tất cả các cạnh. Tiếp đó, tìm đường đi có chi phí nhỏ nhất từ đỉnh nguồn đến điểm hút, đó là 1-2-3-6 với tổng chi phí vận chuyển bằng 3, khả năng thông qua của đường đi này bằng 2 bằng khả năng thông qua của \cạnh (1,2) hoặc (3,6). Ta vận chuyển thêm hai đơn vị hàng từ đỉnh nguồn đến điểm hút theo đường đi vừa tìm được. Ở bước lặp tiếp theo, đường đi có chi phí nhỏ nhất từ đỉnh nguồn đến điểm hút là 1 - 4- 6, với chi phí vận chuyển bằng 7 và khả năng thông qua bằng 1 bằng khả năng của cạnh (4,6). Ta vận chuyển thêm được 1 đơn vị hàng từ đỉnh nguồn tới điểm hút. Ở bước lặp thứ 3, đường đi có chi phí nhỏ nhất từ đỉnh nguồn tới điểm hút là 1 - 4 - 3 - 2 - 5 - 6. Trên đường đi này có 3 cạnh chưa vận chuyển, đó là (3,4), (2,5), (5,6); cạnh có vận chuyển hàng theo chiều thuận là (1,4) và cạnh vận chuyển hàng theo chiều ngược là (2,3). Vì thế, chi phí vận chuyển trên đường đi này bằng: 3 + 2 - 1 + 5 + 6 = 15. Khả năng thông qua của đường đi này bằng: Min(4-1, 4-0, 2, 2-0) = 2 Ta vận chuyển thêm 2 đơn vị hàng trên các cạnh (1,4), (4,3),(2,5), (5,6) và bớt 2 đơn vị hàng trên cạnh (2,3). Kết quả ta vận chuyển được 5 đơn vị hàng từ đỉnh nguồn tới điểm hút, với tổng chi phí bằng: PTIT 3.2 + 7.1 + 15.2 = 43 Luồng chi phí nhỏ nhất là: x12 = 2, x14 = 3, x23 = 0, x25 = 2, x36 = 2, x43 = 2, x46 = 1, x56 = 2 Thuật toán đánh dấu: Cho mạng (G,u) trong đó G = {X.A}, u là năng lực thông qua trên mỗi cạnh. Tìm luồng t qua mạng với giá trị tz nhỏ nhất và thỏa mãn điều kiện:  (i,j) A, t(i,j) ≥ u(i,j) Xuất phát từ một luồng t nào đó thỏa mãn điều kiện trên, ta dùng phương pháp sau đây để giảm giá trị của luồng t. Bước 1: Đánh dấu các đỉnh. Đầu tiên đánh dấu cho đỉnh đích (z) số 0. Nếu đỉnh j đã được đánh dấu, có cạnh (i,j) với đỉnh đầu chưa được đánh dấu và t(i,j) > u(i,j) thì đánh dấu cho đỉnh i là +j. Nếu đỉnh i đã được đánh dấu, có cạnh (i,j) thì đánh dấu cho đỉnh j là -i. 135
18. Bài giảngToán kinh tế Chương 4: Mô hình bài toán tối ưu trên mạng Với cách đánh dấu này mà đi tới được đỉnh nguồn (x0) thì ta đã tìm được một đường đi vô hướng từ z tới x0 được đánh dấu. Bước 2: Giảm luồng Bây giờ ta có thể giảm luồng đi 1 bằng cách chọn luồng mới t' như sau: Nếu cạnh (i,j) không thuộc đường đi trên thì giữ nguyên luồng, nghĩa là: t'(i,j) = t(i,j) ' Nếu cạnh (i,j) thuộc đường đi này và cùng chiều với chiều từ x0 đến z thì đặt: t(i,j) = t(i,j) - 1 (vì trên cạnh đó t(i,j) > u(i,j)), còn nếu cạnh (i,j) ngược chiều thì đặt t'(i,j) = t(i,j) + 1. Lặp lại quá trình giảm luồng trên cho đến khi không đánh dấu được tới đỉnh nguồn x0. Khi đó ta nhận được luồng có giá trị nhỏ nhất, Thí dụ 4.10: Xét mạng vận tải: 5/5 +0 x x 1 3 6-5/5 0 4/3 z 9/8 3-4/3 +2 +4 4/3 +3 13/13 x0 x2 x4 10-9/8 6-5/5 Luồng hiện có có giá trị là tz = 19. Luồng mới sau khi cải tiến có giá trị là tz' = 18 là luồng nhỏ nhất. 4.6 Phương pháp sơ đồ mạng lưới (Pert) 4.6.1 Một số khái niệm và quy tắc lập sơ đồ mạng lưới a. Định nghĩa: Định nghĩa 1: Một tập hợp các điểm (ta gọi là các đỉnh, ký hiệu là X) và tập hợp các cung (ký hiệu là A) được gọi là sơ đồ mạng lưới nếu chúng thỏa mãn các điều kiện sau: - Giữa 2 đỉnh có không quá một cung nối liền và ngược lại mỗi cung phải liên kết 2 đỉnh nào đó với nhau. i j Cung nối từ đỉnh i đến đỉnh j được ký hiệu là (i, j), trong đó i là điểm gốc của cung và j là điểm ngọn của cung. PTIT - Điểm gốc và điểm ngọn của mỗi cung không trùng nhau. - Trong một dãy các cung nối tiếp nhau (tức là điểm ngọn của mỗi cung là điểm gốc của cung tiếp theo) thì không bao giờ điểm ngọn của cung cuối cùng trùng với điểm gốc của cung đầu tiên. Một dãy như vậy được gọi là một đường đi trong sơ đồ mạng lưới. - Giữa 2 đỉnh tùy ý bao giờ cũng có một dãy các cung nối liền. - Có một đỉnh chỉ toàn cung đi ra gọi là đỉnh khởi công toàn bộ và có một đỉnh chỉ toàn cung đi tới gọi là đỉnh kết thúc toàn bộ. Các đỉnh còn lại có cả cung đi ra lẫn cung đi tới gọi là đỉnh trung gian. Định nghĩa 2: Ứng với mỗi cung (i, j) có một số tij đặc trưng cho cung đó về mặt lượng được gọi là độ dài hay thời hạn của cung đó. Định nghĩa 3: Độ dài đường đi μ trong sơ đồ mạng lưới là tổng độ dài của tất cả các cung thuộc đường đi đó, ký hiệu là l(μ). Theo định nghĩa thì: 136
19. Bài giảngToán kinh tế Chương 4: Mô hình bài toán tối ưu trên mạng l(µ)  t ij (i, j) μ b. Công dụng của sơ đồ mạng lưới: Nó được dùng để mô tả quá trình thi công một công trình nào đó hoặc bất cứ một quy trình nào đó mà trong đó bao gồm nhiều công việc thành phần với những trình tự tiến hành khác nhau. Hai yếu tố chính trong quá trình thi công là công việc và sự kiện. Các công việc được mô tả bởi các cung, các sự kiện được biểu thị bằng các đỉnh. Thời điểm khởi công toàn bộ công trình (sự kiện đầu tiên khởi công toàn bộ công trình) được biểu thị bằng đỉnh khởi công toàn bộ (thường ký hiệu là đỉnh 1). Thời điểm kết thúc toàn bộ công trình (sự kiện cuối cùng hoàn thành toàn bộ công trình) được biểu thị bởi đỉnh kết thúc toàn bộ (thường ký hiệu là đỉnh n). Các đỉnh còn lại biểu thị các sự kiện trung gian, đó là những mốc thời gian trong quy trình thi công, nó đánh dấu sự hoàn thành cuả một số công việc nào đó của công trình và sự bắt đầu của một số công việc tiếp theo. Một cách chính xác, ta định nghĩa: Định nghĩa 4: Một sự kiện được gọi là hoàn thành nếu mọi việc ứng với các cung đi đến nó đều đã hoàn thành. Một sự kiện có hoàn thành thì các công việc ứng với các cung đi khỏi nó mới có thể bắt đầu. c. Các quy tắc thiết lập sơ đồ mạng lưới. Quy tắc1: Nếu một nhóm 2 hay nhiều công việc cùng chung sự kiện khởi công và cùng chung sự kiện kết thúc thì không được biểu diễn như hình 4.10a, tùy thuộc vào tính chất của các công việc mà ta có thể xử lý như sau: - Nếu tính chất của các công việc như nhau hoặc trong thực tế không thể làm tách rời nhau được thì gộp chúng lại thành một cung duy nhất (hình 4.10b). - Nếu tính chất các công việc khác nhau mà không thể gộp chúng lại được thì phải thêm đỉnh mới và cung giả (hình 4.10c). Các đỉnh mới là j1 và j2; các cung (j1, j) và (j2, j) gọi là các cung giả (biểu thị bằng nét đứt). a b j i Hình 4.10a c a, b, c Hình 4.10b i j j1 PTIT a b i j Hình 4.10c c j 2 Quy tắc2: Nếu một nhóm công việc lập thành một mạng con trong sơ đồ mạng lưới (các công việc và sự kiện của nhóm này không phụ thuộc gì vào và không ảnh hưởng đến các công việc khác của sơ đồ mạng lưới, trừ sự kiện đầu tiên và sự kiện cuối cùng của nhóm này) thì ta có thể gộp mạng con đó thành một cung duy nhất, nếu sự gộp đó không làm cho sơ đồ mạng lưới trở nên quá thô (hình 4.11a chuyển sang hình 4.11b), cung (2, 4) trong hình 4.11b mô tả cả 3 công việc a, b, c trong sơ đồ mạng lưới hình 4.11a. 137
20. Bài giảngToán kinh tế Chương 4: Mô hình bài toán tối ưu trên mạng 1 2 4 5 Hình 4.11a 3 1 2 4 5 Hình 4.11b Quy tắc 3: Nếu một nhóm các công việc liên hệ với nhau theo trật tự: Việc d sau việc a, b, c Việc e sau việc a, b thì ta phải biểu diễn như hình 4.12 ` a e i b d Hình 4.12 Việc d sau việc a, c Việc e sau việc a, b thì ta phải biểu diễn như hình 4.13. c d a e b Hình 4.13 Quy tắc 4: Nếu một nhóm các công việc liên hệ với nhau theo trật tự: Việc a sau việc b Việc c sau việc d Việc e sau việc b, d thì ta phải biểu diễn như hình 4.14:PTIT b a e Hình 4.14 d c Quy tắc 5: Nếu việc a bắt đầu khi hoàn thành 1/5 công việc x Nếu việc b bắt đầu khi hoàn thành 1/2công việc x Nếu việc c bắt đầu khi hoàn thành 4/5 công việc x Nếu việc d bắt đầu khi hoàn thành toàn bộ công việc x 138
21. Bài giảngToán kinh tế Chương 4: Mô hình bài toán tối ưu trên mạng a b c 1/5x 3/10x 3/10x 1/5x d j j1 j2 j3 j Hình 4.15 Qui tắc 6: - Nếu một đỉnh không phải đỉnh khởi công toàn bộ mà chỉ toàn những cung đi ra thì ta phải thêm một cung giả nối từ đỉnh khởi công toàn bộ với đỉnh đó: Hình 4.14a chuyển sang hình 4.16b. - Nếu một đỉnh không phải đỉnh kết thúc toàn bộ mà chỉ toàn những cung đi tới thì ta phải thêm một cung giả nối từ đỉnh đó đến đỉnh kết thúc toàn bộ: Hình 4.14c chuyển sang hình 4.16d 3 3 ` 1 2 5 1 2 5 4 4 Hình 4.16b Hình 4.16a 2 2 1 4 5 1 4 5 3 3 Hình 4.16c Hình 4.16d Chú ý: Muốn cho sơ đồ mạng lưới vẽ được cân đối đẹp đẽ, ta tiến hành như sau: - Cho sự kiện khởi công toàn bộ mang số 1 và xếp nó vào lớp thứ nhất. - "Xóa" sự kiện 1 và các cung PTITđi khỏi nó, chọn những sự kiện toàn cung đi tới xếp vào lớp thứ 2. - Đánh số thứ tự cho các đỉnh thuộc lớp thứ hai bắt đầu từ số 2, các đỉnh trong một lớp có thể đánh số tùy ý. - "Xóa" các sự kiện thuộc lớp thứ i cùng các cung đi khỏi các sự kiện thứ i, chọn ra các sự kiện chỉ toàn những cung đi ra xếp vào lớp thứ i + 1. Quá trình lặp lặp lại cho đến khi sự kiện kết thúc toàn bộ được đánh số. - Việc giả có độ dài tij = 0 nếu việc giả đó phản ánh trật tự lô gíc giữa các việc. Việc giả có độ dài khác 0 nếu việc giả đó phản ánh sự chờ đợi. - Khi vẽ sơ đồ mạng lưới ta nên đưa các sự kiện có liên quan nhiều với các sự kiện khác vào bên trong, các sự kiện ít liên quan đến các sự kiện khác thì vẽ ra phía ngoài. 4.6.2 Các chỉ tiêu thời gian của sơ đồ mạng lưới Cho sơ đồ mạng lưới G = {X.A} trong đó X là tập các sự kiện thể hiện bởi các đỉnh và A là tập các công việc thể hiện bởi các cung. a. Thời điểm sớm nhất hoàn thành sự kiện: 139
22. Bài giảngToán kinh tế Chương 4: Mô hình bài toán tối ưu trên mạng s Ký hiệu thời điểm sớm nhất hoàn thành j là Tj  j X Ta biết rằng sự kiện j là hoàn thành nếu mọi công việc ứng với các cung đi tới sự kiện j đều đã hoàn thành. Vì vậy đối với sự kiện 1 là sự kiện khởi công toàn bộ, trước đó chưa có công việc nào s nên T1 = 0. Đối với sự kiện j tùy ý, như trên hình 4.16 thì đến thời điểm 24 mới có việc (i1, j) hoàn thành, nếu việc này thi công sớm nhất vào thời điểm 18, việc (i2, j) và (i3, j) chưa hoàn thành, dù cho 2 việc này thi công sớm nhất có thể được thứ tự là 19 và 16, cũng xét như vậy ta được: s s Tj 27 max Ti t ij ;(i, j) A j  s T =18 i1 ` i1 t =6 i1 j s T =19 i2 s t = 8 T `= ? i2 j j i2 j T s =16 i3 t = 10 i3 j ` i3 Hình 4.17 trong đó A j = {(i1,j), (i2,j), (i3,j)} - tập hợp các công việc ứng với các cung đi tới sự kiện j. s s - Một cách tổng quát: Tj = max{ Ti t ij (i, j) A j } (1), trong đó Aj là tập hợp các công việc ứng với các cung đi tới sự kiện j. s Từ định nghĩa về sự hoàn thành một sự kiện ta suy ra Tj là độ dài đường đi dài nhất từ sự kiện 1 s ' đến sự kiện j: Tj = l(Δj) j X (1) Trong đó Δj là đường đi dài nhất từ sự kiện 1 đến sự kiện j. s Gọi n là sự kiện hoàn thành toàn bộ công trình thì Tn = l(Δn) - thời hạn hoàn thành toàn bộ công trình. b. Thời điểm muộn nhất hoàn thành sự kiện. m m Ký hiệu Ti i` X . Nếu sự kiện i hoàn thành muộn hơn thời điểm Ti thì thời gian hoàn thành toàn bộ công trình bị kéo dài. Đối với sự kiện n thì: T m T s PTITn n Giả sử biết thời điểm muộn nhất hoàn thành các sự kiện kề sau sự kiện i. Ta biết rằng sự kiện i có hoàn thành thì các công việc ứng với các cung ra khỏi i mới bắt đầu được. Tm= 60 j1 j1 t = 8 ij1 tij = 9 m 2 Hình 4.17 T =? m j1 i j2 T = 59 j2 t = 11 ij3 m j3 T = 62 j3 140
23. Bài giảngToán kinh tế Chương 4: Mô hình bài toán tối ưu trên mạng Trên hình 4.17, nếu sự kiện i hoàn thành vào thời điểm 51 và cả 3 việc đều thi công ngay khi sự kiện i hoàn thành thì đến thời điểm 62, việc (i,j3) đã hoàn thành, việc (i, j1) cũng đã hoàn thành m m trước thời điểm 60, chúng đều không làm ảnh hưởng đến T và T , nhưng việc (i, j2) chưa hoàn j1 j3 thành được ở thời điểm Tm do đó làm ảnh hưởng đến thời gian hoàn thành toàn bộ công trình. j2 Cũng xét như vậy, ta được ở thời điểm 50 sự kiện i phải hoàn thành thì mới không làm ảnh hưởng đến T m , T m , T m và do đó sẽ không làm ảnh hưởng đến thời gian hoàn thành toàn bộ công trình. j1 j2 j3 m m Một cách tổng quát: Ti = min{Tj - tij; (i, j) Aj } (2) trong dó A - tập hợp các công việc ứng với các cung ra khỏi sự kiện i. j1 Từ bản chất của thuật ngữ "muộn nhất hoàn thành" suy ra độ dài đường đi dài nhất từ sự kiện i m m đến sự kiện n là Tn - Ti . Nếu ký hiệu γi - đường đi dài nhất từ sự kiện i đến sự kiện n thì: m m m m ' l(γi) = Tn - Ti hoặc Ti = Tn - l(γi) i < n (2) m m m với i = 1 thì T1 = Tn - l(γ1) = Tn - l(Δn) = 0. Thí dụ 4.11: Một quy trình công nghệ gồm một số các công việc chính sau đây: h Công việc a1 làm trong 6 bắt đầu ngay. h Công việc a2 làm trong 4 sau a1 hoàn thành. h Công việc a3 làm trong 5 bắt đầu ngay. h Công việc a4 làm trong 7 bắt đầu ngay. h Công việc a5 làm trong 6 sau a1 hoàn thành. h Công việc a6 làm trong 8 sau a4 hoàn thành. h Công việc a7 làm trong 6 sau a4 hoàn thành. h Công việc a8 làm trong 9 sau a3, a6, a7 hoàn thành. h Công việc a9 làm trong 7 sau a3, a6 hoàn thành. h Công việc a10 làm trong 9 sau a2, a5 hoàn thành. h Công việc a11 làm trong 5 sau a2, a9 hoàn thành. h Công việc a12 làm trong 5 sau a7 hoàn thành. h Công việc a13 làm trong 8 sau a8, a12 hoàn thành. a) Lập sơ đồ mạng lưới mô ta quá trình thi công các công việc trên? b) Tính thời điểm sớm nhất và PTITmuộn nhất hoàn thành các sự kiện? Giải: - Vẽ sơ đồ mạng lưới 141
24. Bài giảngToán kinh tế Chương 4: Mô hình bài toán tối ưu trên mạng a5=6 2 7 ` a10=9 a2=4 a1=6 4 a =5 8 11 11 a =7 1 a3=5 9 5 a13=8 a6=8 a4=7 9 a8=9 3 6 a7=6 10 Hình 4.18 a12=5 - Tính thời điểm sớm nhất hoàn thành các sự kiện: s T1 = 0 s s h T2 = max{T1 + t1,2} = 0 + 6 = 6 s s h T3 = max{T1 + t1,3} = 0 + 7 = 7 s s h T4 = max{T2 + t2,4} = 6 + 4 = 10 s s s h T5 = max{T1 + t1,5; T3 + t3,5} = max{0 + 5; 7 + 8} = 15 s s h T6 = max{T3 + t3,6} = 7 + 6 = 13 s s s h T7 = max{T2 + t2,7; T4 + t4,7 } = max{6 + 6; 10 + 0} = 12 s s s h T8 = max{ T4 + t4,8, T5 + t5,8} = max{10 + 5; 15 + 7} = 22 s s s h T9 = max{ T5 + t5,9; T6 + t6,9PTIT } = max{15 + 0; 13 + 0} = 15 s s s h T10 = max{ T6 + t6,10; T9 + t9,10} = max{13 + 5; 15 + 9}= 24 s s s s T11 = max{ T7 + t7,11; T8 + t8,11; T10 + t10,11} = max{12 + 9; 22 + 5; 24 + 8}= 32 - Tính thời điểm muộn nhất hoàn thành các sự kiện: m s T11 = T11 = 32 m m h T10 = min{ T11 - t10,11} = 32 - 8 = 24 m m h T9 = min{ T10 - t9,10} = 24 - 9 = 15 m m h T8 = min{ T11 - t8,11} = 32 - 5 = 27 m m h T7 = min{ T11 - t7,11} = 32 - 9 = 23 m m m h T6 = min{ T10 - t6,10; T9 - t6.9} = min{24 - 5; 15 - 0} = 15 142
25. Bài giảngToán kinh tế Chương 4: Mô hình bài toán tối ưu trên mạng m m m h T5 = min{ T9 - t5,9; T8 - t5,8} = min{15 - 0; 27 - 7} = 15 m m m h T4 = min{ T8 - t4,8; T7 _ t4,7} = min{27 - 5; 23 - 0} = 22 m m m h T3 = min{ T6 - t3,6; T5 - t3,5} = min{15 - 6; 15 - 8} = 7 m m m h T2 = min{ T7 - t2,7; T4 - t2,4} = min{23 - 6; 22 - 4} = 17 m m m m T1 = min{ T3 - t1,3; T2 - t1,2; T5 - t1,5} = min{7 - 7; 17 - 6; 15 - 5} = 0 c. Thời gian dự trữ của sự kiện. - Định nghĩa 1: Chênh lệch giữa thời đỉểm muộn nhất và thời điểm sớm nhất hoàn thành một sự kiện được gọi là thời gian dự trữ của sự kiện đó, ký hiệu thời gian dự trữ của sự kiện i là Di: m s Di = Ti - Ti i X (3) ' ' m ' Theo (1) và (2) ta có: Di = Tn -[l(Δi) + l(γi)] i X (3) Nhận xét: Tổng l(Δi) + l(γi) là tổng độ dài đường đi dài nhất từ sự kiện 1 đến sự kiện i và từ sự kiện i đến sự kiện n nên tổng ấy chính là độ dài đường đi dài nhất từ sự kiện 1 qua sự kiện đến sự m kiện n và gọi là đường đi dài có điều kiện i. Tn là độ dài của đường đi dài nhất từ sự kiện 1 đến sự kiện n, đó là đường đi dài nhất không điều kiện. Như vậy Di là chênh lệch giữa 2 đường đi dài nhất: dài nhất không điều kiện và dài nhất có điều kiện. m Tn m 1 n Di = T -[l(Δi) + l(γi)] n l(γi ) l( i ) i Hình 4.19 - Định nghĩa 2: Sự kiện i được gọi là sự kiện găng nếu nó không có thời gian dự trữ, tức là Di = m s 0 hay Ti = Ti . Trong thí dụ 4.1 các sự kiện 1, 3, 5, 9, 10, 11 là các sự kiện găng. Đường đi qua các sự kiện đó gọi là đường găng. Lưu ý: Trong một sơ đồ mạngPTIT lưới có thể có nhiều hơn một đường găng. Trong thí dụ 4.1 ngoài đường găng trên còn có đường găng thứ hai đi qua các sự kiện 1, 3, 6, 9, 10, 11. d. Thời điểm sớm nhất khởi công và hoàn thành công việc - Thời điểm sớm nhất khởi công công việc. ks Ký hiệu Tij là thời điểm sớm nhất hoàn thành công việc (i, j) (i, j) A Ta biết rằng, sự kiện i có hoàn thành thì công việc (i, j) mới bắt đầu được (i < n) nên: ks s Tij = Ti . (4) - Thời điểm sớm nhất hoàn thành công việc. hs Ký hiệu thời điểm sớm nhất hoàn thành công việc (i, j) là Tij (i, j) A Ta biết rằng, giữa thời điểm hoàn thành (sớm nhất) và thời điểm khởi công (sớm nhất) công việc (i, j) chênh nhau bởi thời gian thi công tij, nên: hs ks Tij = Tij + tij (i, j) A (5) 143
26. Bài giảngToán kinh tế Chương 4: Mô hình bài toán tối ưu trên mạng từ (4) và (5) ta suy ra: hs s ' Tij = Ti + tij (i, j) A (5) e. Thời điểm muộn nhất hoàn thành và khởi công công viêc. - Thời điểm muộn nhất hoàn thành công việc: hm Ký hiệu thời điểm muộn nhất hoàn thành công việc (i, j) là Tij (i, j) A - Ta biết rằng sự kiện j được coi là hoàn thành nếu (i, j) A j đều đã hoàn thành, như vậy công m việc (i, j) không được phép hoàn thành muộn hơn Tj . Do đó: hm m Tij = Tj với(i, j) A (6) - Thời điểm muộn nhất khởi công công việc: km Ký hiệu thời điểm muộn nhất khởi công công việc (i, j) là Tij (i, j) A . Cũng lập luận như công thức (5), ta được: km hm Tij = Tij - tij (i, j) A (7) km m ' Từ (6) và (7) suy ra: Tij = Tj - tij (i, j) A (7) f. Thời gian dự trữ chung của công việc. - Định nghĩa 3: Thời gian dự trữ chung của công việc (i, j) được ký hiệu và xác định như sau: c km ks Dij = Tij - Tij (i, j) A (8) từ (4) và (7') ta có: c m s Dij = Tj - tij - Ti (i, j) A (9) theo (5') và (6) ta được: c hm hs Dij = Tij - Tij (i, j) A (10) c công thức (10) cũng được lấy làm định nghĩa cho Dij . Thay (1') và (2') vào (9) ta được: c m Dij = Tn - [l(Δi) + tij + l(γj)] (i, j) A (11) Nhận xét: Tổng l(Δi) + tij + l(γj) là độ dài đường đi dài nhất từ sự kiện 1 qua công việc (i, j) đến sự c kiện n . Như vậy: Dij là chênh lệch giữa 2 đường đi dài nhất: đường đi dài nhất không điều kiện và đường đi dài nhất có điều kiện PTIT(qua công việc (i, j)). t ij i j l(γj) l(Δi) m Dc = T - [l(Δ ) + t + l(γ )] n 1 ij n i ij j m Tn Hình 4.20 Định nghĩa 4: Công việc (i, j) được gọi là công việc găng nếu nó không có thời gian dự trữ c chung, thức là Dij = 0. g. Đường găng. 144
27. Bài giảngToán kinh tế Chương 4: Mô hình bài toán tối ưu trên mạng + Định nghĩa: Đường đi có độ dài lớn nhất từ sự kiện 1 đến sự kiện n trong sơ đồ mạng lưới được gọi là đường găng. m s Ký hiệu đường găng là g thì hiển nhiên l(g) = Tn = Tn + Tính chất: (Định lý về điều kiện cần và đủ để một sự kiện, công việc là găng) - Sự kiện i là sự kiện găng khi và chỉ khi i nằm trên đường găng. - Công việc (i, j) là công việc găng khi và chỉ khi (i, j) nằm trên đường găng. + Cách xác định đường găng Từ định lý trên, ta suy ra cách xác định đường găng như sau: - Tính thời gian dự trữ chung cho tất cả các công việc. - Tách ra các công việc không có thời gian dự trữ chung (những việc găng). - Lập những dãy các việc găng nối tiếp nhau từ sự kiện 1 đến sự kiện n. Một dãy như vậy chính là một đường găng. Chú ý: Để thuận tiện cho việc khảo sát sơ đồ mạng lưới ta biểu thị mỗi sự kiện bởi một vòng tròn, chia làm 4 phần (hình 4.20): Phần phía trên ghi số thứ tự của sự kiện. i Phần bên trái ghi thời điểm sớm nhất hoàn thành sự kiện s m Phần bên phải ghi thời điểm muộn nhất hoàn thành sự kiện Ti Ti Phần phía dưới ghi thời gian dự trữ của sự kiện. D i Để dễ dàng nhận ra đường găng, ta ký hiệu mỗi việc găng bởi một mũi tên đậm (hoặc mũi tên kép). Hình 4.21 Để khảo sát sơ đồ mạng lưới được sâu hơn ta phân các việc không găng làm hai loại: - Việc không găng độc lập là việc không găng mà sự kiện gốc và sự kiện ngọn của việc ấy đều là những sự kiện găng. i j tij s m s m Ti Ti Tj Tj c Di Dij > 0 D j HìnhPTIT 4.22 m s Ti = Tj (sự kiện i - găng) m s Tj = Tj (sự kiện j - găng) m s c tij 0 (việc (i, j) không găng). Công việc không găng độc lập được sử dụng toàn bộ thời gian dự trữ chung của nó mà không làm ảnh hưởng đến các công việc khác. - Việc không găng liên găng là việc không găng mà ít nhất một trong hai sự kiện gốc hoặc sự kiện ngọn của nó là sự kiện không găng. 4.6.3 Kết hợp các ước tính thời gian xác suất Việc đóng góp chủ yếu của sơ đồ mạng lưới đối với việc lên thời biểu dự án trở thành phương tiện cho phép giám đốc dự án kết hợp tính bấp bênh vào trong một hệ thống phân tích cấu trúc tốt. Dùng các kỹ thuật tìm ra dưới kiểu sơ đồ mạng lưới, các giám đốc có thể chấp nhận việc ước 145
28. Bài giảngToán kinh tế Chương 4: Mô hình bài toán tối ưu trên mạng lượng thời gian không chắc chắn của những người đứng đầu, các nhà cung cấp, các nhà thầu phụ và các nhà cung cấp dịch vụ khác. Thông tin này cũng cho phép họ triển khai một thước đo trọng tâm về thời gian hoàn thành đối với một dự án và là một thước đo độ lệch chuẩn. Độ lệch chuẩn và phương tiện đã đề cập của việc phân bố thời gian hoàn thành, các xác suất kết thúc dự án với khoảng thời gian ít hơn hay nhiều hơn so với thời gian trung bình sẽ được xác định. Phương pháp sơ đồ mạng lưới kết hợp tính bấp bênh (và xác suất) bao gồm ba bước ước lượng cho mỗi hoạt động hơn là 1. Các ước lượng được định nghĩa như sau: ● a: thời gian tối ưu: Đây là thời gian tốt nhất có thể được dự tính nếu mọi thứ diễn ra tốt đẹp và sẽ đạt đến với khoảng 1 phần trăm thời gian. ● m: thời gian khả thi nhất: Đây là việc ước lượng tốt nhất hoặc sự dự tính khả thi. ● b: thời gian yếm thế: Đây là thời gian trễ nhất có thể được dự tính mộ cách hợp lý nếu mọi thứ diễn ra sai, và nó sẽ xảy ra chỉ khoảng 1 phần trăm thời gian. 2 Thời gian trung bình dự tính (te) và phương sai (σ ) của mỗi hoạt động được xác định như sau: a + 4m + b t = (12) e 6 2 2 b - a σ = (13) 6 Với a là ước lượng thời gian tích cực m là ước lượng thời gian khả thi nhất. b là ước lượng thời gian yếm thế. Các khoảng thời gian hoạt động tách biệt được tính tổng từ các đường đi tương ứng và đường đi có khoảng thời gian dài nhất gọi là đường găng. Các phương sai của các khoảng thời gian hoạt động thành phần cùng với đường gawngcos thể được tính tổng. Sự phân phối thời gian kết thúc xấp xỉ trung bình với thời gian hoàn tất TE và độ lệch chuẩn σ. TE = ∑te (14) 2 2 σ = σcp (15) với σ2 là phương sai của các hoạt động tách biệt trên đường găng. Độ lệch chuẩn và số trung bình đã cho của việc phân bố kết thúc, các xác suất của các khoảng thời gian hoàn thành khác nhau cóPTIT thể được tính bằng cách dùng sự phân phối trung bình. Thi dụ, để xác định xác suất một dự án sẽ mất thời TX ở hình 4.23, chúng ta sẽ tính: T - T Z = X E σ Sau đó tìm xác suất kết hợp với giá trị Z từ các giá trị phân phối trung bình (ở phần phụ lục) và trừ nó với 0,5. Các kết quả sẽ biểu thị một vùng tạo vạch dưới đường cong như hình 4.23 σ Xác suất của thời gian Hình 4.23 vượt quá TX TE TX Thí dụ 4.12: Một dự án bao gồm 10 công việc được trình bày ở bảng dưới đây: 146
29. Bài giảngToán kinh tế Chương 4: Mô hình bài toán tối ưu trên mạng Bảng 4.4 Công việc (Hoạt động) Các ước lượng về thời gian Mô tả Số a m b Thiết kế nhà máy 1-2 10 12 16 Chọn vị trí 2-3 2 8 36 Chọn nhà cung cấp 2-4 1 4 5 Chọn nhân sự 2-6 2 3 4 Chuẩn bị mặt bằng 3-5 8 12 20 Sản xuất máy phát điện 4-5 15 18 30 Chuẩn bị nhân công 4-6 3 5 8 Cài đặt máy phát điện 5-7 2 4 8 Đào tạo các nhân viên điều hành 6-7 6 9 12 Xin giấy phép nhà máy 7-8 4 6 14 Yêu cầu: a. Vẽ sơ đồ mạng lưới và tìm đường găng? b. Tìm xác suất để dự án kết thúc trong vòng 4 năm? c. Xác suất để dự án mất hơn 55 tháng là bao nhiêu? Giải: a. 3 12,67 11,67 5 4,33 19,5 12,33 3,67 7,00 1 2 4 7 8 5,17 3,00 9,00 PTIT6 Đường găng: 1-2-3-5-7-8. Lg = 48 Để tính thời gian trung bình thực hiện các công việc và phương sai tương ứng ta sử dụng công thức (12) và (13) Kết quả như sau: Bảng 4.5 2 te σ 12,33 1,00 11,67 32,11 3,67 0,44 3,00 0,11 12,67 4,00 147
30. Bài giảngToán kinh tế Chương 4: Mô hình bài toán tối ưu trên mạng 19,50 6,25 5,17 0,69 4,33 1,00 9,00 1,00 7,00 2,78 b. Ước lượng tốt nhất của thời gian hoàn thành dự án là TE = 48 tháng, vì thế cơ hội 50% dự án sẽ kết thúc trong khoảng thời gian 4 năm. c. Để xác định bất kỳ thời gian hoàn thành, chúng ta phải tính các phương sai của việc phân phối các khoảng thời gian kết thúc cùng với đường găng, tổng của chúng và ước lượng σ. 2 σ = σcp = 1,00 32,11 4,00 1,00 2,78 = 6,4 T - T 55 - 48 Z = X E = = 1,09 σ 6,4 P(X > TX) = 0,5000 – 0,3621 = 0,1379 Do đó xác xuất này xấp xỉ 14% 4.6.4 Tối ưu hóa quá trình rút ngắn đường găng Việc điều hành quá trình thực hiện một công trình lớn thường dẫn đến việc phải rút ngắn đường găng trên sơ đồ mạng lưới, nhằm đạt một trong hai mục tiêu sau: - Đảm bảo hoàn thành công trình không vượt quá thời hạn cho phép Tcp, nghĩa là: m Tn ≤ Tcp - Đảm bảo hoàn thành công trình với chi phí dự kiến và thời hạn cho phép. Quá trình rút ngắn đường găng có thể thực hiện bằng nhiều giải pháp khác nhau, nhưng tùy từng công trình nên chọn giải pháp sao cho quá trình này được tối ưu (cả về mặt thời gian và kinh phí). Chú ý: + Trong quá trình tối ưu hóa thời hạn hoàn thành công trình, hành trình của đường găng và hình dạng của sơ đồ mạng lưới có thể thay đổi. + Thời hạn hoàn thành toàn bộ công trình có thể thực hiện bởi 3 biện pháp sau: - Thay đổi trình tự nối tiếp các công việc thuộc đường găng bằng việc thực hiện các công việc song song với nhau (nhưng phảiPTIT phù hợp với quy trình công nghệ và biện pháp thi công). - Phân bố lực lượng thi công, phương tiện thiết bị thi công giữa các công việc găng và không găng. Trong quá trình thi công có thể điều chuyển lao động, phương tiện thiết bị kỹ thuật từ công việc không găng sang công việc găng. - Áp dụng cá biện pháp công nghệ mới và tổ chức thi công tiên tiến để rút ngắn thời gian hoàn thành công việc. - Quá trình tối ưu hóa để rút ngắn đường găng thường được tiến hành theo các bước sau: Bước 1: Lập biểu đồ tiến độ thi công công trình. Bao gồm Liệt kê tât cả các công việc hiện có, đặt tên cho công việc theo ký hiệu. Sắp xếp các công việc theo trình tự logíc và quy trình công nghệ. Xác định thời hạn thực hiện các công việc. Bước 2: Xây dựng sơ đồ mạng lưới từ biểu tiến độ thi công. Bước 3: Xác định các yếu tố của sơ đồ mạng lưới. Bước 4: Tìm đường găng g và chiều dài l(g) theo thuật toán đã biết. 148
31. Bài giảngToán kinh tế Chương 4: Mô hình bài toán tối ưu trên mạng Bước 5: Nếu l(g) > Tcp thì thực hiện việc rút ngắn đường găng theo nguyên tắc sau: Thời gian hoàn thành công việc càng ngắn thì chi phí càng phải cao (do phải đầu tư thêm máy móc thiết bị và nhân lực). Tuy nhiên thời gian không thể rút ngắn một cách tùy ý mà chỉ có thể rút ngắn trong giới hạn cho phép. Mặc khác ta cũng không thể kéo dài một công việc với thừi gian tùy ý vì khi đó sẽ gây ra những tổn thất không thể chấp nhận được. Hình 4.23 biểu diễn sự phụ thuộc giữa nhu cầu chi phí và thời gian của một công việc. Chi phí Pc Pn Thời gian tc t n Hình 4.23 Trong thực tế thời gian dành cho việc hoàn thành một công việc của công trình chỉ có thể dao động trong khoảng tc và tn với chi phí tương ứng là Pc và Pn. Tỷ số (Pc - Pn)/(tn - tc) được gọi là độ dốc, ký hiệu là S. Vấn đề đặt ra là làm thế nào để rút ngắn thời gian hoàn thành công trình với chi phí nhỏ nhất. Giả sử những công việc của công trình được mô tả bằng sơ đồ mạng lưới thiết lập ứng với tn có tổng thời gian trên đường găng là T. Chủ công trình yêu cầu rút ngắn thời gian hoàn thành công trình ΔT ngày. Làm thế nào thỏa mãn yêu cầu này với chi phí bổ sung nhỏ nhất. Vấn đề được giải quyết như sau: - Dựa vào sơ đồ mạng lưới xác định đường găng. - Rút ngắn tối đa thời gian của công việc có độ dốc nhỏ nhất. - Kiểm tra xem đường găng có bị thay đổi không. Nếu đường găng không bị thayPTIT đổi thì quay lại bước 2. - Tìm đường găng mới của sơ đồ mạng lưới theo kết quả rút ngắn ở bước 2. - Nếu thời gian rút ngắn đã đáp ứng yêu cầu, kết thúc quá trình rút ngắn thời gian hoàn thành công trình. Nếu thời gian rút ngắn chưa thỏa mãn yêu cầu, quay lại bước 2. Thí dụ 4.12: Một công trình bao gồm các công việc A, B, C, D, E và F có sơ đồ mạng như hình 4.24 với các số liệu về thời gian và chi phí ghi trong bảng 4.4 E 4 5 F 6 D ` 1 C ` A Hình 4.24 2 3 B 149
32. Bài giảngToán kinh tế Chương 4: Mô hình bài toán tối ưu trên mạng Bảng 4.6 Công việc tn Pn tc Pc S A 8 1800 7 2200 400 B 16 1500 11 2200 140 C 14 1800 9 2400 120 D 12 2400 9 3000 200 E 15 1200 14 2000 800 F 10 2000 8 4000 1000 Yêu cầu: Tìm phương án thi công công trình với thời hạn cho phép là 36 ngày. Giải: B1- Dựa vào sơ đồ mạng xác định đường găng ứng với tn (Hình 4.24a). 4 15 5 10 6 12 23 38 38 48 48 11 0 0 12 1 0 0 0 14 8 2 3 8 8 24 24 0 16 0 Hình 4.24a Trên đường găng ta nhận thấy, thời gian hoàn thành công trình hiện thời T = 48 ngày. Chúng ta phải rút ngắn 12 ngày. B2- Ta nhận thấy công việc C có độ dốc 120 là nhỏ nhất. Rút ngắn tối đa thời gian công việc C từ 14 ngày xuống 9 ngày. Thời hạn hoàn thành toàn bộ công trình là T = 43 ngày (Hình 4.24b). 4 15 5 10 6 12 23 PTIT33 33 43 43 11 0 0 12 1 0 0 0 9 8 2 3 8 8 24 24 0 16 0 Hình 4.24b B3- Kiểm tra, đường găng vẫn không thay đổi, quay lại B2 B2- Rút ngắn tối đa thời gian công việc B (có độ dốc 140) từ 16 ngày xuống 11 ngày. Thời gian hoàn thành toàn bộ công trình bây giờ là T = 38 ngày (Hình 4.24c) 150
33. Bài giảngToán kinh tế Chương 4: Mô hình bài toán tối ưu trên mạng 4 15 5 10 6 12 23 28 28 38 38 11 0 0 12 1 0 0 0 9 8 2 3 8 8 19 19 0 11 0 Hình 4.24c B3- Kiểm tra, đường găng vẫn không thay đổi, quay lại B2 B2- Ta nhận thấy công việc A độ dốc là 400, ta chỉ có thể rút ngắn thời gian công việc A từ 8 xuống 7 ngày. Thời hạn hoàn thành công trình bây giờ là T = 37 ngày (Hình 4.24d) 4 15 5 10 6 12 23 27 27 37 37 11 0 0 ` 12 1 0 0 0 9 7 2 3 7 7 18 18 0 11 0 Hình 4.24d B3- Kiểm tra, đường găng vẫn không thay đổi, quay lại B2. B2- Mắc dù công việc D và E có độ dốc bé hơn nhưng chúng không nằm trên đường găng nên ta chỉ có thể rút ngắn công việcPTIT F (có độ dốc 1000). Rút ngắn tối đa thời gian công việc F từ 10 xuống 9 ngày. Thời hạn hoàn thành toàn bộ công trình lúc này là T = 36 ngày (Hình 4.24e) thỏa mãn điều kiện của chủ công trình. 4 15 5 9 6 12 23 27 27 36 36 11 0 0 12 ` 1 0 0 0 9 7 2 11 3 7 7 18 18 0 0 Hình 4.24e 151
34. Bài giảngToán kinh tế Chương 4: Mô hình bài toán tối ưu trên mạng Kết quả rút gọn được tóm tắt trong bảng 4.5 Bảng 4.7 Công việc tn tc S ΔT ΔP A 8 7 200 1 400 B 16 11 140 5 700 C 14 9 120 5 600 F 10 9 1000 1 1000 Tổng cộng 12 2700 Câu hỏi và bài tập ôn chương 4 I. Lý thuyết 1. Trình bày các khái niệm cơ bản về đồ thị hữu hạn? 2. Nêu các khái niệm:, đường đi, chu trình, lát cắt, đồ thị đối ngẫu, đồ thị phẳng? 3. Khái niệm ma trận liên hệ trực tiếp và ma trận liên hệ cung nút? Cho thí dụ? 4. Nội dung và mô hình bài toán đường đi ngắn nhất? 5. Nội dung và mô hình bài toán mạng liên thông? 6. Nội dung và mô hình bài toán luồng lớn nhất? 7. Nội dung và mô hình bài toán luồng nhỏ nhất? 8. Nội dung và mô hình bài toán sơ đồ mạng lưới? II. Bài tập 1. Viết ma trận liên hệ trực tiếp và ma trận liên hệ cung nút của đồ thị sau: 1 2 4 3 5 PTIT 2. Cho ma trận liên h ệ cung nút sau: 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 -1 0 0 0 -1 0 0 0 1 0 0 0 -1 0 0 -1` 1 0 0 0 -1 1 0 0 -1 Hãy vẽ đồ thị cho bởi ma trận trên? 152
35. Bài giảngToán kinh tế Chương 4: Mô hình bài toán tối ưu trên mạng 3. Xác định đường đi ngắn nhất từ nút 1 đến mỗi nút khác trong mạng cho ở đồ thị sau: 6 2 6 7 2 5 1 7 4 6 7 1 2 4 6 ` 1 5 7 3 9 7 33 5 4. Phải thiết kế mạng thông tin cáp nối các địa điểm chính (có khoảng cách cho trong hình vẽ) của một khu vực thế nào để tổng độ dài dây cáp là nhỏ nhất: A 2000 1300 800 E 1000 D 1100 C 200 2000 2600 G B 780 1400 1300 F 5. Cho đồ thị hữu hạn G = (X.A) sau: ` 6 x2 x6 4 8 PTITx7 6 4 5 8 7 x1 x3 x9 4 5 5 5 6 9 4 x8 x 4 x5 2 6 (Các số ghi trên cạnh, cung là độ dài của cạnh, cung tương ứng) a.Từ đồ thị G = (X.A), bỏ cạnh (x6, x8) xây dựng đồ thị đối ngẫu? b. Tìm đường đi ngắn nhất từ x1 đến các nút còn lại? 6. Cho đồ thị hữu hạn G = (X.A) sau: 153
36. Bài giảngToán kinh tế Chương 4: Mô hình bài toán tối ưu trên mạng 7 2 7 8 5 4 5 5 8 7 1 3 7 8 6 5 7 3 7 9 4 5 6 (Các số ghi trên mỗi cạnh, cung, cạnh là khả năng thông qua của cạnh, cung đó) a.Từ đồ thị đã cho G = (X.A) hãy vẽ đồ thị đối ngẫu? b. Xác định luồng lớn nhất trên mạng cho bởi đồ thị G = (X.A), trong đó đỉnh 1 là đỉnh nguồn và đỉnh 8 là đỉnh đích? 7. Một doanh nghiệp sản xuất nhỏ triển khai các hoạt động cho ở bảng dưới đây cần thiết để phóng thích một đơn hàng cho một nhà máy mới Bảng 4.8 Mô tả công việc Công việc Thời gian hoạt động trước a m b A – B. Khảo sát sơ bộ Không 4 6 10 B-C. Yêu cầu địa điểm A-B 2 8 24 B–D.Chuẩn bị dự án A-B 10 12 16 B-F.Chiến lược tiếp thị A-B 4 5 10 C-D. Kiểm tra đất B-C 1 2 3 D-E.Chấp thuận về luật C-D và B-D 6 8 30 D-F.Áp dụng khoản tiền vay C-D và B-D 2 3 4 E-F. Cấp giấy chứng nhận D-E 0 0 0 E-G.Danh mục D-E 6 6 6 F-G.Tài chính an toàn D-F và B-F 2 6 12 G-H.Phóng thích hợp đồng E-G và F-G 2 2 3 a. Vẽ sơ đồ mạng thích hợp? b. Tìm độ dài đường găng? c. tính các chỉ tiêu thời gian PTITcho các công việc? 8. Cho dữ liệu về mạng PERT trong bảng sau: Bảng 4.9 Sự kiên Sự kiện Thời gian hoạt động trước sau A m b 1 2 5 6 13 1 3 2 7 12 2 4 1.5 2 2.5 2 5 1 3 5 3 5 4 5 6 3 6 1 1 1 4 7 2 3 10 5 7 4 5 6 6 7 3 5 7 154
37. Bài giảngToán kinh tế Chương 4: Mô hình bài toán tối ưu trên mạng a. Vẽ sơ đồ mạng và tìm đường găng? b. Xác định thời gian khởi đầu sớm nhất và thời gian khởi đầu muộn nhất và thời gian dự trữ cho tất cả các sự kiện trong sơ đồ? c. Mỗi ngày dự án có thể rút ngắn trị giá 5.000USD. Doanh nghiệp có nên chi trả 12.500USD để giảm công việc 3 – 5 đến 3 ngày không? PTIT 155
38. Bài giảng Toán kinh tế Chương 5: Mô hình hệ thống phục vụ công cộng CHƯƠNG 5 MÔ HÌNH HỆ THỐNG PHỤC VỤ CÔNG CỘNG Đặt vấn đề: Lớp mô hình bài toán hệ thống phục vụ công cộng hay còn gọi là mô hình hệ thống xếp hàng, phục vụ đám đông là một trong những lớp mô hình xuất phát từ các bài toán thực tế. Như bài toán tổ chức các hệ thống phục vụ như bản thân tên gọi của nó. Trong những hệ thống như vậy người ta thấy có rât nhiều yếu tố tác động, chi phối đến cách thức hoạt động cũng như hiệu quả hoạt động của hệ thống. Nếu xem xét một hệ thống phục vụ dưới giác độ mô hình hoá thì các mô hình tương ứng đôi khi không cho phép chung ta xác định các yếu tố ngoại sinh và nội sinh ngay từ đầu. Việc hình thành bài toán đối với lớp mô hình này cũng có những yếu tố đặc biệt. Thông thường với các mô hình của kinh tế vi mô hay vĩ mô đã biết, cùng với bài toán là hình ảnh một mô hình rất rõ nét. Với các mô hình thực tế nói chung và mô hình phục vụ công cộng nói riêng hệ thống chỉ tiêu đánh giá sẽ đóng vai trò là các biến nội sinh. Chúng là cơ sở để đánh giá hiệu quả và chất lượng phục vụ của hệ thống. Các yếu tố ngoại sinh trong những tình huống khác nhau có thể được lựa chọn từ các tham số. Với mô hình hệ thống phục vụ công cộng, chúng ta sẽ thấy rõ hơn một trong các phương thức xây dựng, phân tích mô hình mà cơ sở toán học đã được thiết lập ở chương 1. Ngoài ra chúng ta tiếp cận với một lớp đơn giản các mô hình ngẫu nhiên, chúng đòi hỏi những thủ thuật riêng trong xây dựng và phân tích mô hình. 5.1 Bài toán lý thuyết phục vụ công cộng. Trong các hoạt động kinh tế xã hội, chúng ta thường gặp những quá trình phục vụ, trong đó người ta quan tâm đến hiệu quả hoạt động của cơ sở phục vụ về cả hai mặt: lợi ích của cơ sở phục vụ và lợi ích của đối tượng được phục vụ. Một trong những đặc điểm quan trọng của các quá trình này là đối tượng có tính chất đám đông và ngẫu nhiên, thời gian thoả mãn yêu cầu của đối tượng cũng có tính chất ngẫu nhiên. Điều đó không cho phép chúng ta tổ chức, quản lý hệ thống phục vụ như một quá trình thường xuyên, đều đặn. Bài toán lý thuyết phục vụ công cộng nghiên cứu các hệ thống phục vụ trong điều kiện tác động của các yếu tố ngẫu nhiên và đưa ra các phân tích, đánh giá hiệu quả phục vụ của chúng. Thông qua việc nghiên cứu các mô hình hệ thống phục vụ công cộng cũng cho chúng ta cách nhìn một hệ thống ngẫu nhiên trong trường hợp đơn giản, sự khác biệt của nó với các hệ thống trongPTIT đó mọi quá trình diễn ra đều đặn, đồng thời chúng ta cũng tiếp cận với một trong những cách mô hình hoá các hiện tượng kinh tế, xã hội đó là mô hình hoá bằng sơ đồ trạng thái. Chúng ta sẽ thấy sự không ăn khớp của các quá trình tưởng như đã được thiết kế đồng bộ. Chẳng hạn, nếu thời gian sản xuất một loại sản phẩm là ngẫu nhiên với cường độ trung bình là k sản phẩm/phút, bộ phận kiểm tra cũng có cường độ tương đương có cùng phân phối xác suất thì không phải vì thế mà mọi việc diễn ra một cách bình thường theo nghĩa mọi sản phẩm đều được kiểm tra tức thì sau khi ra khỏi dây chuyền sản xuất. Các mô hình này có nhiều ứng dụng trong thực tế, từ đơn giản đến phức tạp. Trong khuôn khổ cho phép, chúng ta chỉ nghiên cứu một vài dạng cơ bản, tuy nhiên phương pháp nghiên cứu có thể sử dụng cho các hệ thống phức tạp hơn nhiều. Sau đây là một số thí dụ dẫn đến các bài toán phục vụ công cộng đơn giản. Thí dụ 5.1 Xét một siêu thị có 14 cửa thanh toán, ta gọi A là sự kiện có khách hàng có nhu cầu thanh toán sau khi mua hàng xong. Trong đa số các trường hợp A là biến ngẫu nhiên, mỗi khách hàng vào siêu thị có lượng hàng mua khác nhau nên thời gian thanh toán (T) cũng khác nhau và đây cũng là một biến ngẫu nhiên. Như vậy không thể tính toán lưu lượng khách hàng vào siêu thị 156
39. Bài giảng Toán kinh tế Chương 5: Mô hình hệ thống phục vụ công cộng một cách thông thường, phù hợp theo một nghĩa nào đó. Chỉ có thể tính khả năng và các chỉ tiêu đánh giá hoạt động của siêu thị và chỉ có thể tính một cách trung bình. Bài toán dẫn đến việc thiết kế bao nhiêu cửa thanh toán để đảm bảo khả năng thanh toán cho khách hàng nhanh nhất với những hạn chế về mặt hiệu quả sử dụng các cửa thanh toán cũng như các yêu cầu khác có liên quan. Thí dụ 5.2: Một Bưu cục trung tâm có 5 cabin điện thoại. Khách hàng có nhu cầu đến gọi điện là một biến ngẫu nhiên và thời gian gọi cũng là một biến ngẫu nhiên. Vấn đề đặt ra là một khách hàng đến bưu cục gọi điện phải chờ đợi với thời gian bao nhiêu và việc khai thác các cabin có hiệu quả hay không? Nếu không đáp ứng nhu cầu khách hàng và không mang lại hiệu quả cho nhà cung cấp thì phải cải tạo bổ sung như thế nào? 5.2 Mô hình hoá hệ thống phục vụ công cộng. Với những bài toán phân tích hệ thống có thể quy về hệ phục vụ công cộng. Có thể mô tả những nội dung cơ bản nhất của quá trình mô hình hoá các hệ thống này như sau: 5.2.1. Hệ thống phục vụ công cộng và các yếu tố cấu thành. Sau đây ta nghiên cứu sơ bộ về cấu trúc của một hệ thống phục vụ công cộng với các yếu tố cơ bản của nó. Có thể mô tả một cách sơ bộ hệ thống phục vụ như sau: Dòng phục vụ Hàng chờ Yêu cầu Các kênh phục vụ [ ] Và chế độ phục vụ Y/c không được thoả mãn * Hình 5.1: Mô hình hệ thống phục vụ công cộng a) Dòng yêu cầu đến hệ thống (dòng yêu cầu) Dòng các đối tượng hướng đến hệ thống nhằm thoả mãn một loại nhu cầu mà hệ thống phục vụ có khả năng đáp ứng. Đặc trưng quan trọng của dòng yêu cầu là quy luật về sự xuất hiện các yêu cầu theo thời gian. Một trong những dòng yêu cầu phổ biến là dòng tuân theo quy luật Poisson và đặc biệt là dòng tuân theo quy luật poisson dừng. Để có thể nhận biết dòng yêu cầu có phân phối Poisson, người ta có thể căn cứ vào các tính chất của nó, đó là: - Tính đơn nhất: Một dòng yêu cầu có tính đơn nhất nếu trong một khoảng thời gian đủ nhỏ hầu như chắc chắn là không có quáPTIT một yêu cầu xuất hiện. Như vậy, nếu ta ký hiệu Pk(t, Δt) là xác suất trong thời gian từ t đến t + Δt có k yêu cầu xuất hiện thì: P0(t, Δt) + P1(t, Δt) = 1 – o(Δt) với o(Δt) là vô cùng bé của Δt. - Tính không hậu quả: một dòng yêu cầu có tính không hậu quả nếu xác suất xuất hiện x yêu cầu trong khoảng thời gian t đến t + Δt không phụ thuộc vào việc trước thời điểm t đã có bao nhiêu yêu cầu xuất hiện. Như vậy biến cố có x yêu cầu xuất hiện trong khoảng thời gian t đến t + Δt khi trước đó đã có k yêu cầu xuất hiện độc lập với nhau với mọi k, tức là: Px(t, Δt) = Px(t, Δt/k yêu cầu đã xuất hiện) với mọi k. Dòng yêu cầu như vậy có xác suất xuất hiện x yêu cầu trong khoảng thời gian t đến t + Δt được tính theo công thức Poisson như sau: a(t,Δt)xe-a(t,Δt) P (t,Δt) = , x 0. (5.1) x x! Trong đó a(t, Δt) là số trung bình yêu cầu xuất hiện từ t đến t + Δt. 157
40. Bài giảng Toán kinh tế Chương 5: Mô hình hệ thống phục vụ công cộng - Tính dừng: Dòng yêu cầu có tính dừng nếu như xác suất xuất hiện x yêu cầu trong khoảng thời gian Δt không phụ thuộc vào điểm đặt của khoảng thời gian đó. Tức là: Px(t, Δt) = Px(Δt) với mọi t. (5.2) Nói cách khác mật độ dòng yêu cầu không đổi : a(Δt) = λΔt và ta có : (λΔt)xe-λΔt P (Δt) = (5.3) x x! Trong đó: λ là số yêu cầu trung bình xuất hiện trong một đơn vị thời gian. Nếu chọn Δt = 1 thì có công thức của quy luật phân phối Poisson quen thuộc. b) Kênh phục vụ: Tập hợp một số điều kiện vật chất, con người, thông tin, có chức năng thoả mãn một loại yêu cầu nào đó gọi là kênh phục vụ. Đặc trưng của kênh phục vụ là thời gian phục vụ một yêu cầu. Thời gian phục vụ một yêu cầu cũng là một biến ngẫu nhiên, tuân theo quy luật phân phối xác suất nào đó. Một trong những quy luật phổ biến là quy luật chỉ số (hay phân phối mũ), với hàm mật độ: f(t) = μe-μt. Đó cũng chính là quy luật phân phối của thời gian giữa hai lần xuất hiện liên tiếp của các yêu cầu đối với dòng yêu cầu Poisson dừng. c) Dòng phục vụ: Là dòng các đối tượng đã được phục vụ đi ra khỏi hệ thống. Quy luật phân phối xác suất của dòng phục vụ tuỳ thuộc quy luật phân phối của thời gian phục vụ của các kênh. Nếu thời gian phục vụ tuân theo quy luật chỉ số thì dòng phục vụ là dòng Poisson dừng và ngược lại. d) Hàng chờ: Đối với một số hệ thống, tuỳ thuộc chế độ tiếp nhận yêu cầu và tính chất của các yêu cầu, có thể xuất hiện hàng chờ trước các kênh phục vụ, đó là dòng các yêu cầu đến hệ thống nhưng chưa được phục vụ ngay, phải xếp hàng chờ theo một nguyên tắc nào đó, ở đây ta chỉ xét hàng chờ đơn giản, không có sự phân biệt, ưu tiên nào. e) Dòng các yêu cầu không được phục vụ: Đây là bộ phận yêu cầu đến hệ thống nhưng không được nhận vào phục vụ vì một lý do nào đó. f) Chế độ phục vụ: Chế độ phục vụ xác định cách thức làm việc của các kênh và cách thức tiếp nhận các yêu cầu. Có thể phân chia chế độ phục vụ theo một số cách khác nhau, thông thường người ta chia các hệ thống thành các hệ thống không chờ (từ chối) và có chờ; hệ thống phục vụ song song độc lập hay hợp tác, hệ thống đơn hay hệ thốngPTIT nối tiếp. 5.2.2 Phân loại hệ thống Theo các tiêu thức khác nhau hệ thống phục vụ công cộng có thể được phân loại như sau: - Hệ dừng và không dừng: Thực tế các hệ tồn tại ở trạng thái dừng hay dừng theo chu kỳ. Với các hệ thống không dừng các phân tích tập trung chủ yếu vào tính chất hội tụ đến hệ dừng và thời gian hệ được xem là dừng có tính thống kê. - Hệ chờ và không chờ (từ chối): Với các hệ chờ người ta có thể chia thành các hệ chờ với các ràng buộc về thời gian, số chổ chờ hay số yêu cầu tối đa có trong hệ thống. - Hệ thống một giai đoạn , một kênh. Hệ thống một giai đoạn, nhiều kênh. Hệ thống nhiều giai đoạn, một kênh. Hệ thống nhiều giai đoạn, nhiều kênh. Các hệ thống này được mô tả trong hình 5.2 158
41. Bài giảng Toán kinh tế Chương 5: Mô hình hệ thống phục vụ công cộng 1. M ột giai đoan 2. Nhiều giai đoan Ngu ồn đầu Hàng Các Nguồn đầu Hàng Tiện ích Hàng Tiện ích vào chờ dịch vụ vào chờ dịch vụ chờ dịch vụ Một kênh S . A S A A 1 1 2 A A Nhiều kênh A1 1 1 S S B B . B1 1 1 . C1 C1 C1 . Hình 5.2. Các loại hệ thống xếp hàng Trong giới hạn cho phép về thời lượng và cơ sở toán học, chúng ta chỉ xem xét một số hệ thống Poisson dừng. 5.2.3 Trạng thái hệ thống, quá trình chuyển trạng thái. a) Phương pháp phân tích: Khi nghiên cứu một hệ thống phục vụ công cộng, người ta có thể dùng các cách tiếp cận khác nhau, ở đây ta sử dụng phương pháp phân tích, nội dung cụ thể là: Thu thập số liệu về các dòng biến cố liên quan đến hệ thống: dòng yêu cầu, dòng phục vụ hoặc thời gian phục vụ của các kênh. Xác định quy luật dòng yêu cầu và dòng phục vụ, xác định chế độ phục vụ. Xác định trạng thái hệ thống, sơ đồ trạng thái và lập hệ phương trình trạng thái. Giải hệ phương trình trạng thái, tính các chỉ tiêu đánh giá hoạt động của hệ thống Cải tiến hệ thống theo một chỉ tiêu hiệu quả nào đó. Việc xác định quy luật các dòng yêu cầu và dòng phục vụ; lập sơ đồ trạng thái là hai nội dung quan trọng hơn cả. Sau đây ta sẽ đề cập kỹ hơn về hai nội dung đó. b) Tiêu chuẩn χ2 (khi bình phương) và việc kiểm tra giả thiết phân phối xác suất của dòng biến cố. Kiểm định giả thiết về một dạng phân phối đã được trình bày trong các giáo trình xác suất thống kê. Người ta có thể sử dụng mộtPTIT số kiểm định khác nhau (kiểm định khi bình phương, kiểm định Kolmogorov – Smirnov, .). Kiểm định khi bình phương là một trong những kiểm định thông dụng nhất và dễ dàng nhất với bộ số liệu quan sát. Sau đây ta xét cụ thể kiểm định này đối với dòng biến cố của hệ thống phục vụ công cộng. Để kiểm định giả thiết dòng yêu cầu phân phối Poisson ta thực hiện như sau: Chia thời gian thành các đơn vị nhỏ và tiến hành quan sát sự xuất hiện các yêu cầu trong khoảng thời gian đó. Ta nhận được bộ số liệu bao gồm số yêu cầu xuất hiện trong một đơn vị thời gian (lượng biến xi); và số khoảng thời gian tương ứng (tần số ni). Để đảm bảo tính đại diện của các giá trị quan sát không quá nhỏ đối với mỗi giá trị, thông thường nếu các khoảng thời gian có số yêu cầu tương ứng nhỏ hơn 5 thì ta ghép các khoảng đó để có ni ≥ 5, giá trị đại diện là giá trị trung bình. Tính giá trị thống kê: 159
42. Bài giảng Toán kinh tế Chương 5: Mô hình hệ thống phục vụ công cộng k (n - n' )2 χ 2 i i (5.4)  ' i=1 ni x -λ ' λ e ' với n = nP(x ) ; P(xi) = . Trong đó n là giá trị tần số lý thuyết nhận được từ phân phối i i x! i k xini Poisson với trung bình là λ =  , k là số nhóm giá trị xi, ni tần số quan sát tương ứng và n là i=1 ni tổng tần số. Thí dụ 5.3. Khi quan sát số khách hàng đến giao dịch tại một bưu cục, người ta thu được số liệu sau : Bảng 5.1 Xi 0 1 2 3 4 5 6 7 ni 21 23 10 4 1 0 0 1 Trong đó : xi là thời gian giao dịch của khách hàng. ni số khách hàng tương ứng. Để kiểm tra giả thiết : « Khách hàng đến bưu cục có phân phối Poisson », ta tiến hành như sau : k xini Tính giá trị quan sát λ =  =1,1; k là số nhóm giá trị xi. i=1 ni Dùng giá trị này ước lượng giá trị trung bình của phân phối, từ đó tra bảng Poisson P(λ) với các giá trị có tần số nhỏ hơn 5 đã được ghép lại, thoả mãn điều kiện ni ≥ 5. Chọn một mức ý nghĩa α, nếu giá trị thống kê χ 2 < χ 2 ( α, m), trong đó m = k – 2 (bậc tự do) thì giả thiết dòng yêu cầu phân phối Poisson không bị bác bỏ. Lập bảng tính toán như sau : Bảng 5.2 ' xi ni P(xi) ' 2 ni (ni - ni ) ' ni 0 21 0,33287 6,79027 29,7357 1 23 0.36616 8,421680 25,2358 2 10 0,20139 2,0139 31,6687 3 4 0.07384 4 1 PTIT0,02031 5 0 0,00447 0,29549 9,83233 6 0 0,00082 7 1 0,00013 n=60 96,09383 Với các quan sát trên ta có λ = 1,1, giá trị quan sát của thống kê khi bình phương là: 96,09383, giá trị lý thuyết (tra bảng) là: χ 2 (0,05, 5) = 11,0705. Vậy giả thiết dòng yêu cầu phân phối Poisson bị bác bỏ. c) Trạng thái hệ thống và quá trình chuyển trạng thái. +/ Trạng thái hệ thống : Ta gọi tập hợp một hay một số đặc trưng mà trên cơ sở đó có thể phân biệt sự tồn tại của hệ thống trong những tình trạng khác nhau tại mỗi thời điểm là trạng thái của hệ thống. 160
43. Bài giảng Toán kinh tế Chương 5: Mô hình hệ thống phục vụ công cộng Nếu ký hiệu A(t) là một trạng thái của hệ thống thì A(t) là một biến cố ngẫu nhiên. Để có thể phân tích hệ thống phục vụ công cộng, cần xác định tất cả các trạng thái có thể có của hệ thống, tập hợp các trạng thái tại một thời điểm t bất kỳ là một nhóm đầy đủ các biến cố. Với những hệ thống phục vụ công cộng Poisson, từ đây về sau ta ký hiệu các trạng thái của chúng là Xk(t), để chỉ hệ thống ở trạng thái Xk tại thời điểm t. +/ Xác suất trạng thái: Việc hệ thống tồn tại ở một trạng thái cụ thể là một biến cố ngẫu nhiên nên tương ứng với mỗi trạng thái có một giá trị xác suất gọi là xác suất trạng thái, để chỉ ra khả năng hệ thống ở trạng thái tương ứng. Ta ký hiệu xác suất hệ thống ở trạng thái Xk tại thời điểm t là Pk(t). +/ Quá trình chuyển trạng thái. Tại mỗi thời điểm t hệ thống tồn tại ở một trạng thái nhất định, chẳng hạn Xk(t), sau một thời gian Δt hệ thống có thể chuyển đến một trạng thái khác Xj(t + Δt) nhờ sự tác động của các yếu tố ngẫu nhiên nào đó. Ta gọi xác suất hệ thống chuyển từ Xk(t) đến Xj(t + Δt) là xác suất chuyển trạng thái. Trong các mô hình sẽ đề cập sau này ta quan tâm đến sự tác động chuyển trạng thái, thay vì xác suất chuyển trạng thái. Ta ký hiệu cường độ của dòng biến cố làm cho hệ thống chuyển từ Xk(t) đến Xj(t + Δt) là λkj(t). 5.2.4 Sơ đồ trạng thái và hệ phương trình trạng thái. a) Sơ đồ trạng thái: Người ta dùng một sơ đồ mô tả các trạng thái và quá trình chuyển trạng thái của hệ thống. Trong đó mỗi trạng thái được thể hiện bởi một ô vuông với tên trạng thái, chẳng hạn: Xk(t). Để chỉ sự chuyển trạng thái người ta dùng một mũi tên trên đó ghi cường độ của dòng biến cố làm hệ thống chuyển trạng thái theo chiều mũi tên, chẳng hạn: λkj(t) Xk(t) Xj(t) Hình 5.3 b) Hệ phương trình trạng thái. Để phân tích một hệ thống phục vụ công cộng cần xác định các trạng thái có thể có và các xác suất trạng thái tương ứng. Theo thời gian, do tác động của các yếu tố đến quá trình vận động của hệ thống đều có tính ngẫu nhiên,PTIT nên việc hệ thống chuyển từ trạng thái này sang trạng thái khác cũng có tính ngẫu nhiên. Để mô tả mối liên hệ về khả năng chuyển trạng thái như vậy, người ta sử dụng hệ phương trình trạng thái, trong đó các xác suất trạng thái và đạo hàm bậc nhất theo thời gian của nó là các biến còn các tác động làm chuyển trạng thái là các hệ số. Hệ phương trình này cho phép xác định các xác suất trạng thái, làm cơ sở phân tích hệ thống. Nhờ sơ đồ chuyển trạng thái có thể thiết lập hệ phương trình trạng thái theo quy tắc sau: Quy tắc viết hệ phương trình trạng thái Đạo hàm bậc nhất theo thời gian của xác suất trạng thái Pk(t) bằng tổng của một số số hạng, số số hạng đó đúng bằng số mũi tên nối trạng thái đó với trạng thái khác. Mỗi số hạng là tích của xác suất trạng thái mà mũi tên xuất phát và cường độ dòng biến cố ghi theo chiều mũi tên đó dấu của số hạng là dấu “-” nếu mũi tên xuất phát từ Xk(t); là dấu “+” nếu mũi tên hướng đến Xk(t). Tức là: dPk (t) =  λ jk (t)Pj (t) -  λkj (t)Pk (t) (5.5) dt j j Với điều kiện chuẩn là: 161
44. Bài giảng Toán kinh tế Chương 5: Mô hình hệ thống phục vụ công cộng  Pk (t) = 1 (5.6) k Điều kiện chuẩn thể hiện tập hợp Xk(t) là một nhóm đầy đủ các biến cố, tức là tại một thời điểm hệ thống phải tồn tại ở một và chỉ một trạng thái nói trên. Đây là hệ phương trình vi phân cấp 1. Tuy nhiên với hệ thống mà các dòng biến cố tác động đến hệ thống đều là dòng Poisson dừng (hệ thống dừng), thì hệ phương trình trên trở thành hệ phương trình thuần nhất và việc giải hệ trở nên đơn giản. c) Quá trình huỷ và sinh – Nghiệm hệ phương trình trạng thái. +/ Sơ đồ trạng thái: Trong các hệ thống phục vụ công cộng sẽ xét sau đây ta gặp các sơ đồ chuyển trạng thái có dạng: λ (t) λk-1,k(t) λ01(t) 12 λk,k+1(t) X0(t) X1(t) Xk(t) Xk+1(t) λk,k-1(t) λ10(t) λ21(t) λk+1,k(t) λn -1,n(t) Xn-1(t) Xn(t) λn,n-1(t) Hình 5.4 Trong đó mỗi trạng thái chỉ có thể chuyển qua lại với các trạng thái kề nó (trừ trạng thái đầu tiên và cuối cùng nếu có). Ta gọi các quá trình như vậy là quá trình huỷ và sinh. Quá trình này cho phép thiết lập và giải hệ phương trình trạng thái khá đơn giản. +/ Hệ phương trình trạng thái: Với sơ đồ chuyển trạng thái như trên, áp dụng quy tắc viết hệ phương trình trạng thái hệ thống ta có hệ phương trình sau: ' P0 (t) = -λ01P0(t) + λ10P1(t) ' P1 (t) = -λ10P1(t) - λ12P1(t) + λ01P0(t) + λ21P2(t) ' Pk (t) = -λk,k-1Pk(t) – λk, k+1Pk(t)PTIT + λk-1,kPk-1(t) + λk+1,kPk+1(t) Với điều kiện chuẩn là :  Pk (t) = 1 k Trong trường hệ dừng, các đạo hàm theo thời gian đều bằng 0, ta có hệ phương trình sau: 0= -λ01P0(t) + λ10P1(t) 0= -λ10P1(t) - λ12P1(t) + λ01P0(t) + λ21P2(t) 0= -λk,k-1Pk(t) – λk, k+1Pk(t) + λk-1,kPk-1(t) + λk+1,kPk+1(t) Với điều kiện chuẩn là :  Pk (t) = 1 k 162
45. Bài giảng Toán kinh tế Chương 5: Mô hình hệ thống phục vụ công cộng +/ Lời giải của hệ: Hệ (1) có thể giải nhờ các thế dần các xác suất theo P0. Tuy nhiên, đơn giản hơn nếu đặt Ui = - λi,i+1Pi(t) + λi+1,iPi+1(t) thì hệ (1) trở thành: U0 = 0 Ui – Ui – 1 = 0 (i = 1, 2, ) Nghiệm của hệ là Ui  0. Từ đó ta có thể đưa ra công thức tính xác suất Pk theo P0 như sau: P1 = (λ01/ λ10)P0; Pk = (λk,k+1/ λk+1,k)Pk k λi,i+1 Hay: Pk + 1 =  P0 (5.7) i=0 λi+1,i Công thức này được sử dụng để làm nhẹ việc giải hệ phương trình trạng thái của các hệ thống phục vụ công cộng trình bày trong chương này. Trong đó: λk,k+1 = λ và λk+1,k = (k+1)μ αk Nếu đặt α = λ/μ thì P = P (5.8) k k! 0 5.3 Một số hệ thống phục vụ công cộng. Trong khuôn khổ của bài giảng này, chúng sẽ nghiên cứu một số hệ thống phục vụ công cộng đơn giản. Mục đích chủ yếu của phần này là giới thiệu cách tiếp cận hệ thống và một vài cách thức phân tích hệ thống, là cơ sở nghiên cứu các hệ thống phức tạp, gần gũi với các hệ thống phục vụ công cộng trong thực tế hơn. Chính vì vậy các hệ thống được nghiên cứu dưới đây phải chấp nhận một số giả thiết mà theo truyền thống các hệ thống này có thể thoả mãn. Mặc dù có sự hạn chế nhất định, các ứng dụng của các mô hình này cũng rất hiệu quả trong thực tế. 5.3.1 Hệ thống phục vụ công cộng từ chối cổ điển (Hệ thống Eclang) a) Mô tả hệ thống: Hệ thống phục vụ công cộng có n kênh phục vụ, năng suất các kênh bằng nhau và bằng μ, dòng yêu cầu đến hệ thống là dòng Poisson dừng mật độ λ. Thời gian phục vụ một yêu cầu của kênh tuân theo quy luật chỉ số. Một yêu cầu đến hệ thống gặp lúc có it nhất một kênh rỗi thì được nhận vào phục vụ cho đến thỏa mãn tại một trong các kênh rỗi đó. Ngược lại, nếu tất cả các kênh đều bận thì yêu cầu phải ra khỏi hệ thống. Cần xác định các chỉ tiêu phân tích hệ thống. b) Quá trình thay đổi trạng tháiPTIT và sơ đồ trạng thái của hệ thống: +/ Trạng thái: Ta quan tâm đến hiệu quả phục vụ của hệ thống vì vậy đặc trưng được chọn để xác định trạng thái là số kênh bận tại mỗi thời điểm. Gọi Xk(t) là trạng thái hệ thống có k kênh bận tại thời điểm t (k = 0, 1, 2, , n). Chú ý rằng với chế độ phục vụ của hệ thống Eclang số kênh bận cũng chính là số yêu cầu đang được phục vụ tại thời điểm t. +/ Sơ đồ chuyển trạng thái: λ λ λ λ λ X0(t) X1(t) Xk-1(t) Xk(t) μ 2μ (k-1) μ kμ (k+1)μ λ λ λ λ Xk+1(t) Xn-1(t) Xn(t) (k+1) μ (k+2)μ (n-1) μ nμ Hình 5.5 163
46. Bài giảng Toán kinh tế Chương 5: Mô hình hệ thống phục vụ công cộng Sơ đồ trên thiết lập trên cơ sở phân tích tính chất của các dòng Poisson dừng như sau: Nhờ tính đơn nhất của dòng yêu cầu mà khi hệ thống ở trạng thái Xk(t) nó chỉ có thể chuyển đến trạng thái Xk+1(t), không thể chuyển thẳng đến các trạng thái Xk+i(t) với i >1. cũng tương tự, do tính đơn nhất của dòng phục vụ của các kênh, hệ thống chỉ có thể chuyển đến Xk-1(t) mà không thể chuyển thẳng đến các trạng thái Xk-i(t) với i > 1. Nhờ tính không hiệu quả của các dòng biến cố nêu trên mà cường độ các dòng biến cố không phụ thuộc vào trạng thái của hệ thống khi nó tác động đến. Với tính chất dừng ta có dòng mật độ yêu cầu không đổi, cũng như vậy mật độ dòng phục vụ chỉ phụ thuộc vào số kênh đang phục vụ. Những phân tích như trên cũng ứng dụng cho việc xác lập sơ đồ chuyển trạng thái của các hệ thống tương tự. c) Hệ phương trình trạng thái và các xác suất trạng thái. 0= -λP0(t) + μP1(t) 0= -λP1(t) - μP1(t) + λP0(t) + 2μP2(t) (5.9) 0= -λPk(t) – kμPk(t) + λPk-1(t) + (k+1) μPk+1(t) 0 = -nμPn(t) + λPn-1(t) Với điều kiện chuẩn là :  Pk (t) = 1 k αk Đặt α = λ/μ, từ (2) ta có: P = P k k! 0 Thay vào điều kiện chuẩn ta có: n n αk 1 P = P = 1 P = (5.10)  k  k! 0 0 n αk k=0 k=0  k=0 k! Bằng cách nhân cả tử và mẫu số của công thức trên với e-α ta có: e αα0 / 0! P = (5.11) 0 n PTITe ααk  k=0 k! Ký hiệu P(α, k) = e-α αk/k! Là xác suất một biến ngẫu nhiên phân phối Poisson nhận giá trị k và k R(α, k) =  P(α, i) là xác suất tích luỹ tương ứng; ta có: i=0 e-αα0 /0! P(α,0) P0 = n -α k = (5.12)  e α P(α,n) k=0 k! αk P(α, k) Từ đó: P = P = (5.13) k k! 0 R(α, n) Các giá trị xác suất nói trên có thể tính dễ dàng khi các tham số hữu tỷ và n đủ nhỏ. Trong trường hợp tổng quát ta có thể sử dụng bảng giá trị phân phối Poisson (Bảng: Giá trị phân phối Poisson). d) Các chỉ tiêu đánh giá hoạt động của hệ thống: 164
47. Bài giảng Toán kinh tế Chương 5: Mô hình hệ thống phục vụ công cộng Đối với hệ thống này các chỉ tiêu cơ bản đánh giá hoạt động của hệ thống là: 1. Xác suất hệ thống có n kênh rỗi: α0 P(α, 0) P = P = P = (5.14) r 0 0! 0 R(α, n) Chỉ tiêu này cho biết tỷ lệ thời gian hệ thống rỗi hoàn toàn, thời gian rỗi hoàn toàn ở mọi hệ thống Poisson nói riêng và các hệ thống ngẫu nhiên nói chung, dù ta có giảm đến tối thiểu số kênh phục vụ hay tăng tối đa cường độ dòng yêu cầu. 2. Xác suất hệ thống có n kênh bận (hay xác suất một yêu cầu đến hệ thống bị từ chối Ptc): αn P(α, n) P = P = P = (5.15) tc n n! 0 R(α, n) Đây cũng là hiệu suất lý thuyết tối đa của hệ thống, như vậy trong trường hợp hệ ngẫu nhiên, không có khả năng thiết kế một hệ thống khai thác toàn bộ công suất kỹ thuật của các kênh. 3. Xác suất phục vụ (xác suất một yêu cầu đến hệ thống được nhận phục vụ ngay) là: Ppv = 1 – Ptc = 1 – Pn. (5.16) Đó cũng là tỷ lệ các đối tượng được hệ thống tiếp nhận và phục vụ, đối với hệ thống phục vụ công cộng, đây là một trong số ít các chỉ tiêu quan trọng nhất, với cùng một tiềm năng kỹ thuật như nhau có thể chọn chỉ tiêu này làm mục tiêu thiết kế hệ thống. Sau đây là một số chỉ tiêu tính toán ở mức trung bình, vì vậy các công thức dựa trên cơ sở tính kỳ vọng toán học của các đại lượng ngẫu nhiên. 4. Số kênh bận trung bình (hay số yêu cầu trung bình có trong hệ thống): n n αn n-1 αk Nb = kP = P = α P = α(1 P )  k  n! 0  k! 0 n k=0 k=1 k=1 (5.17) P(α, n) α 1 = α.Ppv R(α, n) 5. Số kênh rỗi trung bình: Nr = 1 - Nb (5.18) 6. Hệ số bận (rỗi): Nb H = ; Hr = 1 - Hb (5.19) b n 7. Hiệu quả chung (F): PTIT Tuỳ theo cách đánh giá lợi ích và thiệt hại trong quá trình phục vụ và việc tận dụng công suất hệ thống cũng như các loại lợi ích khác, người ta có thể lập một chỉ tiêu tổng hợp đánh giá hiệu quả chung của hệ thống. Chẳng hạn: Việc phục vụ một yêu cầu mang lại một lợi ích là cpv; mỗi yêu cầu bị từ chối gây thiệt hại là ctc; mỗi kênh rối gây lãng phí là ckr, thì trong một đơn vị thời gian có thể tính được chỉ tiêu hiệu quả chung là: F = λPpvcpv - Nr ckr – λPnctc (5.20) Trên cơ sở các chỉ tiêu đó ta có thể chọn một hay một vài chỉ tiêu để tối ưu hoá hệ thống. e) Phân tích và cải tiến hệ thống Trong thực tế, ngoài việc đánh giá hệ thống phục vụ công cộng bằng một số chỉ tiêu, xuất phát từ các giá trị xác suất cơ bản như giá trị các biến nội sinh của mô hình, người ta còn quan tâm đến sự biến động của các chỉ tiêu đó khi các tham số của hệ thống (với tư cách là biến ngoại sinh) thay 165
48. Bài giảng Toán kinh tế Chương 5: Mô hình hệ thống phục vụ công cộng đổi. Trên cơ sở phân tích cụ thể các chỉ tiêu này người ta có thể cải tiến hệ thống theo một hay một số chỉ tiêu chủ yếu. Sau đây là một số phân tích cụ thể và một vài hướng cải tiến hệ thống. 1. Trước hết ta xem xét vấn đề hiệu suất lý thuyết của một hệ thống phục vụ công cộng kiểu Eclang phụ thuộc vào n và α như thế nào. Hiệu suất lý thuyết được xem là công suất phục vụ tối đa của hệ thống, chỉ tiêu này được tính theo công thức: αn P(α, n) P = P = n n! 0 R(α, n) Như vậy, hiệu suất lý thuyết là không đổi nếu số kênh và hệ số đảm nhận yêu cầu (hệ số α) của mỗi kênh không đổi. Tuy nhiên khi α/n < 1 thì P(α, n) là hàm giảm theo n, khi n tăng Pn giảm, hay hiệu suất lý thuyết giảm. Nếu lấy đạo hàm bậc nhất của Pn theo α ta thấy: αn-1 n αke α αn n-1 αke α   ' (n-1)! k=0 k! n! k=0 k! P (α) = 2 0 (5.21) n n αke α  k=0 k! Vậy khi tăng α, hiệu suất lý thuyết tăng. Như vậy trong điều kiện nhu cầu không có cạnh tranh (tức λ không đổi) thì giảm số kênh hay giảm năng suất kênh sẽ tận dụng được công suất thiết bị. Kết luận này sẽ không có ý nghĩa khi hệ thống phục vụ chỉ tồn tại trong điều kiện tiện lợi tối thiểu đối với các yêu cầu. 2. Vấn đề thu hút nhu cầu và chất lượng phục vụ: Rõ ràng là độ thu hút nhu cầu được đánh giá qua khả năng phục vụ của hệ thống (ngoài các chỉ tiêu như giá cả, thời gian phục vụ, .). Chỉ tiêu tỷ lệ yêu cầu đến hệ thống được phục vụ có thể xem là thước đo chỉ tiêu này. Ta có: Ppv =1- Pn Trên quan điểm thu hút yêu cầu, hành vi của hệ thống phục vụ rõ ràng là ngược chiều với việc tăng hiệu suất của hệ thống. Có thể kết hợp hai chỉ tiêu này bằng cách cho mỗi chỉ tiêu một trọng số (đánh giá lợi ích) hoặc đặt trước một chỉ tiêu và tìm cách hướng chỉ tiêu thứ hai có lợi nhất cho cơ sở phục vụ. Hàm F nêu trên thực chất là một trong hai cách làm như vậy. Ta có thể biến đổi chút ít hàm F như sau: PTIT F = λPpvcpv - Nr ckr – λPnctc = λPpvcpv – (n - αPpv)ckr – λ(1 –Ppv)ctc = λPpvcpv – nckr + αPpvckr – λ ctc + Ppvctc =Ppv(λcpv + λ ctc + αckr) - nckr – λctc Đối với mỗi hệ thống phục vụ có thể xem λ là cho trước (tham số) vấn đề còn lại là năng suất kênh và số kênh (biến ngoại sinh) hoặc ngược lại số kênh và năng suất kênh cho trước (tham số) và λ thay đổi (bíến ngoại sinh) sẽ làm thay đổi chỉ tiêu hiệu quả F. Bằng các công cụ đạo hàm và vi phân đã trình bày trong chương 1, ta có thể khảo sát sự thay đổi của hiệu quả F khi có sự thay đổi của các biến ngoại sinh trong mỗi trường hợp. Thí dụ 5.4. Bộ phận kiểm tra sản phẩm của một cơ sở sản xuất có 3 máy làm việc tự động, năng suất các máy đều là 6 sản phẩm một phút. Mỗi sản phẩm ra khỏi dây chuyền đến bộ phận kiểm tra nếu gặp lúc có máy rỗi sẽ được kiểm tra tại 1 trong các máy rỗi, ngược lại sản phẩm nhập kho 166