zunia.vn

Tuyển sinh 2024 dành cho Gen-Z

zunia.vn

» Khoa Học Tự Nhiên

Bài giảng Toán kinh tế: Phần 2 - TS. Trần Ngọc Minh

Chia sẻ: Codon_09 Codon_09 | Ngày: | Loại File: PDF | Số trang:87

Báo xấu

250
lượt xem 22
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Mời các bạn cùng tìm hiểu bài toán tối ưu trên mạng; mô hình hệ thống phục vụ công cộng; mô hình quản lý lưu trữ được trình bày cụ thể trong "Bài giảng Toán kinh tế: Phần 2" của TS. Trần Ngọc Minh. Hy vọng tài liệu là nguồn thông tin hữu ích cho quá trình học tập và nghiên cứu của các bạn.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng Toán kinh tế: Phần 2 - TS. Trần Ngọc Minh

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)} x2 x5 x7 x1 x3 x6 x4 IT 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. PT 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à liê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 x3 x5 ứng là liên thông 119
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}. - Ánh xạ ngược của một đỉnh xj trong đồ thị G ={X.A}ký hiệu Г-1(xi) là tập hợp các đỉnh đầu của tất cả các cung có đỉnh cuối là xj. Chẳng hạn trong hình 4.3: Г-1(x3) = {x1, x4}. b. Cây IT Đồ 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. PT - 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   là một cây trong G  X. A 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 nà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
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ừ IT 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. PT 6' 2' a2 2 3 a1 `` a7 a4 a3 a1 3' 3' a2 6' 1 ' 2 ' a5 6 1 a8 5' a5 a4 4' a6 a7 4' 4 a9 a3 5 a9 a8 a6 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
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 p b i 1 i i .Vậy bài toán của công ty chính là bài IT 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 PT 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ảng 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
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 x4 a7 x5 a6 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 IT  b ij  - 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 PT 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 -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à: a Ti x  x - x ij ji  bi jO(i) jI(i) trong đó a iT 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
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à br  -  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 IT 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á PT 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≠1 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
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 IT 13 Giải bài toán bằng thuật toán Dijkstra: x2 18 x3 9 24 5 PT 25 10 2 13 20 x4 7 x1 4 3 16 x7 14 x6 24 12 9 5 x9 10 6 15 5 x8 x5 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
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 IT 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: PT 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ạm 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
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 IT lần ngược lại liên tiếp theo quan hệ sau: L*(xj) - cij = L*(xi) 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 (4.3) đườ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 PT 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ủa đồ 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
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ị cij > 0 gọi là độ dài cạnh, như hình 4.5 x2 11 x5 10 x8 12 6 7 8 7 x3 5 x6 12 12 x11 x1 x9 3 6 9 10 12 IT x4 Giải bằng thuật toán Prim: 9 Hình 4.5 x7 10 x10 Đầ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 PT 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 x1 x3 x6 x11 x9 x4 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
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 c ( i, j) ij x 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 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ừ IT 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   (i,j)A:iS,jS u ij 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 PT 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 jS, k S jk - x iS, jS ij (4.4) Nói riêng, nếu lấy S = {s} thì v = x sk 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ừ s đế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
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 x2 ∞ a) IT y3 Hình 4.7 x2 b) y3 ∞ 4.4.2 Thuật toán Ford - Fulkerson PT 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ó 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
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 < uij hoặc 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 ; u ij - x ij ) nếu xij < uij ej   min(ei , u ij ) nếu xij > 0 pj = i. Chuyển sang bước 3 IT 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. PT 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 < uij, ta đặt: x'ij = xij + et - Nếu cạnh (i,j) thuộc đường đi này và ngược 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
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) = IT 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 PT 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ông đượ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
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 IT 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 PT 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) X = 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. Đ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òn 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
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í c i, jA ij x ij với các điều kiện của bài toán: IT S  i x ji - i x ij  0 - S  , nếu i = 1 , nếu i ≠ 1, i ≠ n , 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 PT 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 đó. Trê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
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) 5 2 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. IT Ở 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 PT 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: 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
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 x1 x3 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. IT 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ý PT 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. - Đ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
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  (i, j)μ ij 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ự IT 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 PT 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 i b j Hình 4.10a c a, b, c Hình 4.10b i j j1 a b j Hình 4.10c i c j2 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
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 3 Hình 4.11a 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 i e 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. IT a c d e PT 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: 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

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN

TRỢ GIÚP

HỖ TRỢ KHÁCH HÀNG

Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.