ĐẠI HỌC ĐÀ NẴNG TRƯỜNG ĐẠI HỌC BÁCH KHOA HỒ VĂN HÙNG LUỒNG ĐA HÀNG HĨA ĐA CHI PHÍ TUYẾN TÍNH TỐI ƯU TRÊN MẠNG HỖN HỢP MỞ RỘNG LUẬN ÁN TIẾN SĨ KỸ THUẬT ĐÀ NẴNG – Năm 2022 HỒ VĂN HÙNG LUỒNG ĐA HÀNG HĨA ĐA CHI PHÍ TUYẾN TÍNH TỐI ƯU TRÊN MẠNG HỖN HỢP MỞ RỘNG Chuyên ngành: Khoa học máy tính Mã số: 9480101 LUẬN ÁN TIẾN SĨ KỸ THUẬT Người hướng dẫn khoa học: PGS.TSKH Trần Quốc Chiến ĐÀ NẴNG – Năm 2022 LỜI CAM ĐOAN Tơi xin cam đoan cơng trình nghiên cứu thực hiện, hướng dẫn PGS.TSKH Trần Quốc Chiến Tôi cam đoan kết nghiên cứu trình bày luận án trung thực không chép từ công trình nghiên cứu khác Mọi trích dẫn luận án có ghi nguồn gốc xuất xứ rõ ràng đầy đủ Tác giả NCS Hồ Văn Hùng Trước tiên, tơi xin bày tỏ lịng biết ơn sâu sắc gửi lời tri ân đến PGS.TSKH Trần Quốc Chiến tận tình hướng dẫn, truyền đạt kiến thức kinh nghiệm nghiên cứu khoa học cho suốt q trình học tập, nghiên cứu hồn thành luận án Tơi xin chân thành cảm ơn Phịng Đào tạo Khoa Công nghệ thông tin đơn vị có liên quan khác Trường Đại học Bách khoa, Đại học Đà Nẵng tạo điều kiện thuận lợi cho thời gian làm nghiên cứu sinh Xin cảm ơn Ban Lãnh đạo Trường Đại học Quảng Nam hỗ trợ tạo điều kiện tốt để tơi hồn thành tốt nghiên cứu Cuối cùng, xin gửi lời cảm ơn sâu sắc đến gia đình bạn bè, đồng nghiệp người bên cạnh, giúp đỡ động viên suốt thời gian học tập, nghiên cứu hoàn thành luận án Đà Nẵng, ngày 14 tháng 11 năm 2022 MỤC LỤC MỤC LỤC i DANH MỤC CÁC THUẬT NGỮ VÀ TỪ VIẾT TẮT v DANH MỤC CÁC KÝ HIỆU vii DANH MỤC BẢNG ix DANH MỤC HÌNH x MỞ ĐẦU CHƯƠNG TỔNG QUAN 10 1.1 Đồ thị 10 1.1.1 Đồ thị vô hướng 10 1.1.2 Đồ thị có hướng 10 1.1.3 Đồ thị hỗn hợp 11 1.2 Mạng, luồng mạng 11 1.2.1 Mạng 11 1.2.2 Luồng mạng 12 1.2.3 Lát cắt, đồ thị tăng luồng, đường tăng luồng 12 1.3 Bài toán luồng cực đại mạng 14 1.3.1 Giới thiệu toán 14 1.3.2 Phát biểu toán 15 1.3.3 Thuật toán Ford- Fulkerson 15 1.3.4 Luồng cực đại lát cắt cực tiểu 20 1.4 Bài toán quy hoạch tuyến tính 21 1.4.1 Giới thiệu quy hoạch tuyến tính 21 1.4.2 Các dạng tốn quy hoạch tuyến tính 22 1.4.3 Bài tốn đối ngẫu 26 1.5 Bài toán luồng cực đại mạng hỗn hợp mở rộng đa hàng hóa đơn chi phí 28 1.5.1 Mạng hỗn hợp mở rộng 28 1.5.2 Mạng hỗn hợp mở rộng đa hàng hóa đơn chi phí 29 1.5.2.1 Giới thiệu 29 1.5.2.2 Mạng hỗn hợp mở rộng đa hàng hóa đơn chi phí 30 1.5.3 Luồng mạng hỗn hợp mở rộng đa hàng hóa đơn chi phí 34 1.5.4 Bài tốn luồng cực đại mạng hỗn hợp mở rộng đa hàng hóa đơn chi phí 34 1.6 Kết luận chương 35 CHƯƠNG XÂY DỰNG MƠ HÌNH VÀ THUẬT TỐN GIẢI QUYẾT CÁC BÀI TOÁN LUỒNG TRÊN MẠNG HỖN HỢP MỞ RỘNG ĐA HÀNG HĨA ĐA CHI PHÍ 2.1 Luồng mạng hỗn hợp mở rộng đa hàng hóa đa chi phí 36 36 2.1.1 Giới thiệu 36 2.1.2 Mạng hỗn hợp mở rộng đa hàng hóa đa chi phí 37 2.1.3 Luồng mạng hỗn hợp mở rộng đa hàng hóa đa chi phí 41 2.1.4 Kết luận 42 2.2 Mơ hình thuật tốn tốn luồng mạng hỗn hợp mở rộng đa hàng hóa đa chi phí 42 2.2.1 Bài toán luồng cực đại mạng hỗn hợp mở rộng đa hàng hóa đa chi phí 42 2.2.1.1 Giới thiệu toán 42 2.2.1.2 Phát biểu toán 42 2.2.1.3 Thuật toán MFMM 45 2.2.1.4 Kết luận 53 2.2.2 Bài toán luồng cực đại đồng thời mạng hỗn hợp mở rộng đa hàng hóa đa chi phí 53 2.2.2.1 Giới thiệu toán 53 2.2.2.2 Phát biểu toán 54 2.2.2.3 Thuật toán CMF 57 2.2.2.4 Kết luận 65 2.3 Mơ hình thuật tốn tốn luồng mạng hỗn hợp mở rộng đa hàng hóa đa chi phí với chi phí giới hạn 65 2.3.1 Bài toán luồng cực đại mạng hỗn hợp mở rộng đa hàng hóa đa chi phí với chi phí giới hạn 65 2.3.1.1 Giới thiệu toán 65 2.3.1.2 Phát biểu toán 66 2.3.1.3 Thuật toán LMF 69 2.3.1.4 Kết luận 79 2.3.2 Bài toán luồng cực đại đồng thời mạng hỗn hợp mở rộng đa hàng hóa đa chi phí với chi phí giới hạn 79 2.3.2.1 Giới thiệu toán 79 2.3.2.2 Phát biểu toán 80 2.3.2.3 Thuật toán LCMF 83 2.3.2.4 Kết luận 92 2.4 Mơ hình thuật tốn tốn luồng cực đại đồng thời mạng hỗn hợp mở rộng đa hàng hóa đa chi phí với chi phí cực tiểu 92 2.4.1 Giới thiệu toán 92 2.4.2 Phát biểu toán 93 2.4.3 Thuật toán MCMF 94 2.4.4 Kết luận 96 2.5 Kết luận chương 97 CHƯƠNG ỨNG DỤNG PHÂN LUỒNG GIAO THÔNG TẠI THÀNH PHỐ ĐÀ NẴNG 98 3.1 Sơ đồ phần mạng lưới giao thông thành phố Đà nẵng 98 3.2 Ứng dụng thuật tốn MFMM phân luồng giao thơng 99 3.2.1 Giới thiệu 99 3.2.2 Cài đặt thuật toán MFMM 99 3.2.3 Kết chạy chương trình 101 3.2.4 Phân tích kết 103 3.2.5 Kết luận 107 3.3 Ứng dụng thuật toán CMF phân luồng giao thông 107 3.3.1 Giới thiệu 107 3.3.2 Cài đặt thuật toán CMF 107 3.3.3 Kết chạy chương trình 109 3.3.4 Phân tích kết 113 3.3.5 Kết luận 3.4 Ứng dụng thuật toán LMF phân luồng giao thông 117 117 3.4.1 Giới thiệu 117 3.4.2 Cài đặt thuật toán LMF 117 3.4.3 Kết chạy chương trình 120 3.4.4 Phân tích kết 122 3.4.5 Kết luận 125 3.5 Ứng dụng thuật toán LCMF phân luồng giao thông 126 3.5.1 Giới thiệu 126 3.5.2 Cài đặt thuật toán LCMF 126 3.5.3 Kết chạy chương trình 128 3.5.4 Phân tích kết 130 3.5.5 Kết luận 135 3.6 Ứng dụng thuật toán MCMF phân luồng giao thông 135 3.6.1 Giới thiệu 135 3.6.2 Cài đặt thuật tốn MCMF 135 3.6.3 Kết chạy chương trình 136 3.6.4 Phân tích kết 138 3.4.4 Kết luận 143 3.7 Kết luận chương 143 KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN 144 DANH MỤC CÁC CƠNG TRÌNH ĐÃ CƠNG BỐ 145 TÀI LIỆU THAM KHẢO 146 PHỤ LỤC Phụ lục 1: Khả thông hành thực tế đỉnh Phụ lục 2: Hệ số quy đổi hàng hóa Phụ lục 3: Các cặp nguồn-đích Phụ lục 4: Khả thông hành thực tế cạnh chi phí cạnh Phụ lục 5: Chi phí rẻ nhánh Phụ lục 6: Các cặp nguồn-đích lượng hàng cần chuyển DANH MỤC CÁC THUẬT NGỮ VÀ TỪ VIẾT TẮT Viết tắt Tiếng Anh Tiếng Việt G Graph Đồ thị V Vertex Đỉnh E Edge Cạnh s Source Nguồn t Target Đích f Flow Luồng c Capacity Khả thông qua D Dual Đối ngẫu Max Maximum Cực đại M Minimum Cực tiểu i Conversion Luồng quy n flow đổi c Real flow Luồng thực tế Maximal flow on multicost multi- Luồng cực đại mạng MFMM commodity extended mixed hỗn hợp mở rộng đa hàng LMF network Maximal flow on multi-cost multi- commodity extended mixed network with limited cost hóa đa chi phí Luồng cực đại mạng hỗn hợp mở rộng đa hàng hóa đa chi phí với chi phí giới hạn Maximal concurrent flow on Luồng cực đại đồng thời multi- cost mạng hỗn hợp mở rộng đa f rf CMF multi- commodity hàng extended hóa đa chi phí mixed network Maximal LCMF concurrent flow on multicost multi- Luồng cực đại đồng thời mạng hỗn hợp mở rộng đa commodity extended hàng mixed network with limited cost hóa đa chi phí với chi phí giới hạn MCMF Maximal concurent flow on multicost multi-commodity extended mixed network with minimal cost Luồng cực đại đồng thời mạng hỗn hợp mở rộng đa hàng hóa đa chi phí với chi phí cực tiểu (3,10) (10,3) (10,13) (13,10) 3 (10,11) (11,10) (2,11) (11,2) (11,14) (14,11) 0 0 0 0 0 0 0 0 0 0 3 9 8 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ 4 4 4 5 (11,1 2) (12,1 1) (1,12) (12,1) (12,1 5) (15,1 2) (1,15) (15,1) (15,1 6) (16,1 5) (13,1 4) (14,1 3) (14,1 5) (15,1 4) 0 0 0 0 0 60 60 80 80 80 80 80 80 80 80 50 50 80 80 0 8 8 8 8 8 8 8 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ Ghi Loại cạnh có hướng, Loại cạnh vơ hướng Trong đó, ce khả thơng hành cạnh, với liệu Bảng Phụ lục khả thông hành cạnh (1,2) ce(1,2)=500 ze hệ số phục vụ cạnh với liệu Bảng Phụ lục hệ số phục vụ cạnh (1,2) ze(1,2)=0.9 Khả thông hành thực tế cạnh (1,2) ce(1,2) x ze(1,2)=500 x 0.9=450 bei chí phí phải trả để vận chuyển hàng loại i quy đổi qua cạnh, với liệu Bảng Phụ lục chi phí phải trả để lưu hành đơn vị hàng hóa loại qua cạnh (1,2) be1=3, hàng hóa loại qua cạnh (1,2) be2=4, ta có be3= be4= ∞ hàng hóa loại loại bị cấm lưu hành cạnh (1,2) Phụ lục 5: Chi phí rẻ nhánh Bảng Phục lục Chi phí rẽ nhánh T T Đỉ nh Cạnh Cạnh b v b v b v bv4 2 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ 3 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ 1 (2,1) (1,8) 1 (2,1) (2,1) (8,1) (1,12) (1,15) (1,2) (8,1) (1,12) 1 (8,1) (1,15) 1 (12,1) (12,1) (1,2) (1,8) 1 (15,1) (15,1) (1,2) (1,8) 1 2 (1,2) (2,7) (1,2) (2,3) (1,2) (2,11) 2 (7,2) (2,3) ∞ ∞ (7,2) (2,1) ∞ (7,2) (2,11) ∞ 1 ∞ ∞ (3,2) (2,11) ∞ ∞ (3,2) (2,1) ∞ ∞ 2 (3,2) (2,7) ∞ ∞ (11,2) (2,1) ∞ ∞ (11,2) (2,7) ∞ (11,2) (2,3) ∞ 2 ∞ ∞ (2,3) (3,6) ∞ ∞ (2,3) (3,4) ∞ (2,3) (3,10) ∞ ∞ ∞ (4,3) (3,10) ∞ ∞ (4,3) (3,2) ∞ (4,3) (3,6) ∞ ∞ ∞ (6,3) (3,4) ∞ ∞ (6,3) (3,10) (6,3) (3,2) 3 3 3 ∞ ∞ (10,3) (3,2) ∞ ∞ (10,3) (3,6) (10,3) (3,4) 3 ∞ ∞ (3,4) (4,5) ∞ ∞ (3,4) (4,9) ∞ (5,4) (4,9) ∞ ∞ ∞ (5,4) (4,3) (9,4) (4,3) ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ 4 ∞ ∞ ∞ (8,7) ∞ (8,1) ∞ 4 (9,4) (4,5) 4 (4,5) (5,6) (6,5) (5,4) 4 (5,6) (6,3) (5,6) (6,7) 6 (3,6) (6,5) (3,6) (6,7) (7,6) (6,5) (7,6) (6,3) (2,7) (7,8) (2,7) (7,6) 5 (6,7) (7,2) (6,7) (7,8) 5 (8,7) (7,6) (8,7) (7,2) 5 (1,8) (1,8) (7,8) (8,16) 8 (7,8) (8,16) 9 (4,9) (9,13) (4,9) (9,10) 6 (13,9) (9,10) (13,9) (9,4) 6 (10,9) (9,4) (10,9) (9,13) 6 6 10 (3,10) (10,9) 10 (3,10) 10 (3,10) (10,11 ) (10,13 ) 10 (13,1 0) (13,1 0) (13,1 0) (10,9) 7 10 (9,10) 10 (9,10) 10 (9,10) (10,13 ) (10,11 ) (10,3) 7 10 (11,1 0) (11,1 0) (11,1 0) 10 10 10 10 ∞ 4.5 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ (10,3) ∞ ∞ (10,9) ∞ ∞ (10,13 ) ∞ ∞ (10,11 ) (10,3) ∞ 7 8 11 (2,11) 11 (14,1 1) (14,1 1) (14,1 1) (10,1 1) 11 11 11 (11,14 ) (11,12 ) (11,2) (11,10 ) (11,12 ) 5 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ 82 11 (10,1 1) (11,2) 83 11 (11,2) 84 11 (12,1 1) (12,1 1) 85 12 (1,12) 86 12 (1,12) (12,11 ) (12,15 ) 87 12 88 12 (11,1 2) (11,1 2) (12,15 ) (12,1) 89 12 (12,1) 90 12 (15,1 2) (15,1 2) 91 13 (9,13) 92 13 (9,13) (13,14 ) (13,10 ) 93 13 (13,9) 94 13 (10,1 3) (10,1 3) 95 13 96 13 (14,1 3) (14,1 3) (13,10 ) (13,9) 97 14 98 14 (13,1 4) (13,1 4) (14,15 ) (14,11 ) 99 14 (11,1 (14,13 (11,10 ) (12,11 ) (13,14 ) ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ 4) (11,1 4) ) (14,15 ) (15,1 4) (15,1 4) (14,11 ) (14,13 ) (14,1 5) (14,1 5) (15,16 ) (15,1) ∞ ∞ ∞ ∞ ∞ ∞ ∞ 2 ∞ ∞ ∞ ∞ 2 ∞ 100 14 101 14 102 14 103 15 104 15 105 15 (14,1 5) (15,12 ) 106 15 107 15 (12,1 5) (12,1 5) (15,14 ) (15,16 ) 108 15 (12,1 5) (15,1) 109 15 (1,15) 110 15 (1,15) (15,12 ) (15,14 ) 111 15 (1,15) (15,16 ) 112 15 (15,1) 113 15 (16,1 5) (16,1 5) (15,12 ) 114 15 (16,1 5) (15,14 ) 115 16 (8,16) 116 16 (15,1 6) (16,15 ) (16,8) Trong đó: 1 1 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ bvi chí phí phải trả để vận chuyển hàng loại i quy đổi qua đỉnh, với liệu Bảng Phụ lục chi phí phải trả để đơn vị hàng hóa loại từ cạnh (2,1) qua đỉnh đến cạnh (1,8) bv1 =1.5, tương tự bv2 = 2.5, bv3= bv4= ∞ hàng hóa loại 3, bị cấm lưu hành tuyến từ cạnh (2,1) qua đỉnh đến cạnh (1,8) Phụ lục 6: Các cặp nguồn-đích lượng hàng cần chuyển Bảng Phục lục 6: Cặp nguồn-đích lượng hàng cần chuyển T T Hàng hóa s t D ij i j ij 1 3 1 3 1 2 2 2 3 5 1 6 Trong đó, Dij số lượng hàng hóa loại i, i=1, ,r cần chuyển từ đỉnh nguồn sij đến đỉnh đích tij, với liệu Bảng Phụ lục số lượng hàng hóa loại cần chuyển từ đỉnh nguồn đến đỉnh đích 330 đơn vị hàng hóa LUẬN ÁN TIẾN SĨ KỸ THUẬT LUẬN ÁN TIẾN SĨ KỸ THUẬT Tơi xin cam đoan cơng trình nghiên cứu thực hiện, hướng dẫn PGS.TSKH Trần Quốc Chiến MỤC LỤC DANH MỤC CÁC KÝ HIỆU DANH MỤC BẢNG DANH MỤC HÌNH MỞ ĐẦU Tính cấp thiết việc nghiên cứu Mục tiêu nghiên cứu Đối tượng phạm vi nghiên cứu Phương pháp nghiên cứu Các đóng góp luận án Bố cục luận án CHƯƠNG TỔNG QUAN 1.1 Đồ thị Hình 1.1 Cạnh nối cặp đỉnh i, j Hình 1.2 Đồ thị vơ hướng Hình 1.3 Cung nối cặp đỉnh i, j Hình 1.4 Đồ thị có hướng Hình Đồ thị hỗn hợp Hình 1.6 Mạng với đỉnh nguồn s đỉnh đích t Hình 1.7 Luồng mạng Hình 1.8 Mạng biểu diễn lát cắt Hình 1.9 Đồ thị tăng luồng Gf Hình 1.10 Luồng sau tăng luồng Hình 1.11 Sơ đồ mạng G Hình 1.12 Mạng sau gán nhãn đỉnh s Hình 1.13 Mạng sau đánh dấu đỉnh s gán nhãn đỉnh b,c Hình 1.14 Mạng sau gán nhãn đỉnh s,c,b,t Hình 1.15 Mạng sau tăng luồng theo P=(s,b,t) Hình 1.16 Mạng sau gán nhãn đỉnh s,c,t Hình 1.18 Mạng sau gán nhãn đỉnh s,d,e,t Hình 1.20 Mạng sau gán nhãn đỉnh s,c với fv=6 1.4 Bài tốn quy hoạch tuyến tính Bảng 1.1 Quy tắc xây dựng toán đối ngẫu dạng chuẩn max 1.5 Bài toán luồng cực đại mạng hỗn hợp mở rộng đa hàng hóa đơn chi phí Hình 1.21 Mơ hình nút giao thơng Hình 1.22 Mơ hình mạng hỗn hợp mở rộng Hình 1.23 Sơ đồ mạng giao thông hỗn hợp mở rộng Bảng 1.2 Hệ số quy đởi hàng hóa theo TCVN 4054-2005 Bảng 1.4 Khả thơng hành cạnh Bảng 1.5 Chi phí đỉnh 1.6 Kết luận chương CHƯƠNG MỞ RỘNG ĐA HÀNG HĨA ĐA CHI PHÍ 2.1 Luồng mạng hỗn hợp mở rộng đa hàng hóa đa chi phí Bảng 2.1 Cặp đỉnh nguồn đích Bảng 2.3 Khả thơng hành thực tế đỉnh 2.2 Mơ hình thuật tốn toán luồng mạng hỗn hợp mở rộng đa hàng hóa đa chi phí 2.3 Mơ hình thuật toán toán luồng mạng hỗn hợp mở rộng đa hàng hóa đa chi phí với chi phí giới hạn δ δ 2.5 Kết luận chương 3.1 Sơ đồ phần mạng lưới giao thông thành phố Đà nẵng Hình 3.1 Sơ đồ phần mạng lưới giao thơng thành phố Đà Nẵng Hình 3.2 Sơ đồ phân luồng rf hàng hóa loại với thuật tốn MFMM cho cặp nguồn-đích (1,4) Hình 3.3 Sơ đồ phân luồng rf hàng hóa loại với thuật tốn MFMM cho cặp nguồn-đích (1,5) Hình 3.4 Sơ đồ phân luồng rf hàng hóa loại với thuật tốn MFMM cho cặp nguồn-đích (1,9) Hình 3.5 Sơ đồ phân luồng rf hàng hóa loại với thuật tốn MFMM cho cặp nguồn-đích (12,4) Hình 3.6 Sơ đồ phân luồng rf hàng hóa loại với thuật tốn MFMM cho cặp nguồn-đích (12,5) Hình 3.7 Sơ đồ phân luồng rf hàng hóa loại với thuật tốn MFMM cho cặp nguồn-đích (12,9) Hình 3.8 Sơ đồ phân luồng rf hàng hóa loại với thuật tốn MFMM cho cặp nguồn-đích (12,16) Hình 3.9 Sơ đồ phân luồng rf hàng hóa loại với thuật tốn MFMM cho cặp nguồn-đích (13,16) 3.3.1 Giới thiệu Hình 3.10 Sơ đồ phân luồng rf hàng hóa loại với thuật tốn CMF cho cặp nguồn–đích (1,4) Hình 3.11 Sơ đồ phân luồng rf hàng hóa loại với thuật tốn CMF cho cặp nguồn–đích (1,5) Hình 3.12 Sơ đồ phân luồng rf hàng hóa loại với thuật tốn CMF cho cặp nguồn–đích (1,9) Hình 3.13 Sơ đồ phân luồng rf hàng hóa loại với thuật tốn CMF cho cặp nguồn–đích (12,4) Hình 3.14 Sơ đồ phân luồng rf hàng hóa loại với thuật tốn CMF cho cặp nguồn–đích (12,5) Hình 3.15 Sơ đồ phân luồng rf hàng hóa loại với thuật tốn CMF cho cặp nguồn–đích (12,9) Hình 3.16 Sơ đồ phân luồng rf hàng hóa loại với thuật tốn CMF cho cặp nguồn–đích (12,16) Hình 3.17 Sơ đồ phân luồng rf hàng hóa loại với thuật tốn CMF cho cặp nguồn–đích (13,16) 3.4.1 Giới thiệu Bảng 3.3 Kết chạy chương trình cài đặt thuật tốn LMF Hình 3.18 Sơ đồ phân luồng rf hàng hóa loại với thuật tốn LMF cho cặp nguồn-đích (1,4) Hình 3.19 Sơ đồ phân luồng rf hàng hóa loại với thuật tốn LMF cho cặp nguồn-đích (1,5) Hình 3.20 Sơ đồ phân luồng rf hàng hóa loại với thuật tốn LMF cho cặp nguồn-đích (1,9) Hình 3.21 Sơ đồ phân luồng rf hàng hóa loại với thuật tốn LMF cho cặp nguồn-đích (12,4) Hình 3.22 Sơ đồ phân luồng rf hàng hóa loại với thuật tốn LMF cho cặp nguồn-đích (12,9) Hình 3.23 Sơ đồ phân luồng rf hàng hóa loại với thuật tốn LMF cho cặp nguồn-đích (12,16) Hình 3.24 Sơ đồ phân luồng rf hàng hóa loại với thuật tốn LMF cho cặp nguồn-đích (13,16) 3.5.1 Giới thiệu Bảng 3.4 Kết chạy chương trình cài đặt thuật tốn LCMF Hình 3.25 Sơ đồ phân luồng rf hàng hóa loại với thuật tốn LCMF cho cặp nguồn –đích (1,4) Hình 3.26 Sơ đồ phân luồng rf hàng hóa loại với thuật tốn LCMF cho cặp nguồn–đích (1,5) Hình 3.27 Sơ đồ phân luồng rf hàng hóa loại với thuật tốn LCMF cho cặp nguồn–đích (1,9) Hình 3.28 Sơ đồ phân luồng rf hàng hóa loại với thuật tốn LCMF cho cặp nguồn–đích (12,4) Hình 3.29 Sơ đồ phân luồng rf hàng hóa loại với thuật tốn LCMF cho cặp nguồn–đích (12,5) Hình 3.30 Sơ đồ phân luồng rf hàng hóa loại với thuật tốn LCMF cho cặp nguồn–đích (12,9) Hình 3.31 Sơ đồ phân luồng rf hàng hóa loại với thuật tốn LCMF cho cặp nguồn–đích (12,16) Hình 3.32 Sơ đồ phân luồng rf hàng hóa loại với thuật tốn LCMF cho cặp nguồn–đích (13,16) 3.6.1 Giới thiệu Hình 3.33 Sơ đồ phân luồng rf hàng hóa loại với thuật tốn MCMF cho cặp nguồn–đích (1,4) Hình 3.34 Sơ đồ phân luồng rf hàng hóa loại với thuật tốn MCMF cho cặp nguồn–đích (1,5) Hình 3.35 Sơ đồ phân luồng rf hàng hóa loại với thuật tốn MCMF cho cặp nguồn–đích (1,9) Hình 3.36 Sơ đồ phân luồng rf hàng hóa loại với thuật tốn MCMF cho cặp nguồn–đích (12,4) Hình 3.37 Sơ đồ phân luồng rf hàng hóa loại với thuật tốn MCMF cho cặp nguồn–đích (12,5) Hình 3.38 Sơ đồ phân luồng rf hàng hóa loại với thuật tốn MCMF cho cặp nguồn–đích (12,9) Hình 3.39 Sơ đồ phân luồng rf hàng hóa loại với thuật tốn MCMF cho cặp nguồn–đích (12,16) Hình 3.40 Sơ đồ phân luồng rf hàng hóa loại với thuật tốn MCMF cho cặp nguồn –đích (13,16) 3.7 Kết luận chương KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN Kết luận Hướng phát triển DANH MỤC CÁC CƠNG TRÌNH ĐÃ CƠNG BỐ TÀI LIỆU THAM KHẢO PHỤ LỤC Phụ lục 1: Khả thông hành thực tế đỉnh Phụ lục 2: Hệ số quy đởi hàng hóa Phụ lục 3: Các cặp nguồn-đích Phụ lục 4: Khả thông hành thực tế cạnh chi phí cạnh Phụ lục 5: Chi phí rẻ nhánh Phụ lục 6: Các cặp nguồn-đích lượng hàng cần chuyển ... hình mạng hỗn hợp mở rộng đa hàng hóa đa chi phí luồng mạng hỗn hợp mở rộng đa hàng hóa đa chi phí, sở xây dựng mơ hình thuật tốn để giải toán luồng tối ưu mạng hỗn hợp mở rộng đa hàng hóa đa chi. .. TOÁN LUỒNG TRÊN MẠNG HỖN HỢP MỞ RỘNG ĐA HÀNG HĨA ĐA CHI PHÍ 2.1 Luồng mạng hỗn hợp mở rộng đa hàng hóa đa chi phí 36 36 2.1.1 Giới thiệu 36 2.1.2 Mạng hỗn hợp mở rộng đa hàng hóa đa chi phí 37... hình mạng hỗn hợp mở rộng đa hàng hóa đa chi phí luồng mạng hỗn hợp mở rộng đa hàng hóa đa chi phí - Đề xuất mơ hình thuật tốn giải toán luồng cực đại, toán luồng cực đại đồng thời mạng hỗn hợp mở