Luận án Tiến sĩ Kỹ thuật: 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 "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" trình bày các nội dung chính sau: Xây dựng mô hình và thuật toá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í; Ứng dụng phân luồng giao thông tại thành phố Đà Nẵng.
Nội dung trích xuất từ tài liệu:
Luận án Tiến sĩ Kỹ thuật: 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 ĐẠ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 ĐẠ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 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 đây là công trình nghiên cứu do tôi thực hiện, dưới sự hướng dẫn của PGS.TSKH. Trần Quốc Chiến. Tôi cam đoan các kết quả nghiên cứu được trình bày trong luận án là trung thực và không sao chép từ bất kỳ công trình nghiên cứu nào khác. Mọi trích dẫn trong luận án đều có ghi nguồn gốc xuất xứ rõ ràng và đầy đủ. Tác giả NCS. Hồ Văn Hùng LỜI CẢM ƠN Trước tiên, tôi xin bày tỏ lòng biết ơn sâu sắc và 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 và kinh nghiệm nghiên cứu khoa học cho tôi trong suốt quá trình học tập, nghiên cứu và hoàn thành luận án. Tôi xin chân thành cảm ơn Phòng Đào tạo và Khoa Công nghệ thông tin cũng như các đơn vị có liên quan khác của Trường Đại học Bách khoa, Đại học Đà Nẵng đã luôn tạo điều kiện thuận lợi cho tôi trong thời gian làm nghiên cứu sinh tại đây. Xin cảm ơn Ban Lãnh đạo Trường Đại học Quảng Nam đã luôn hỗ trợ và tạo điều kiện tốt nhất để tôi hoàn thành tốt nghiên cứu này. Cuối cùng, tôi xin được gửi lời cảm ơn sâu sắc đến gia đình và bạn bè, đồng nghiệp những người luôn bên cạnh, giúp đỡ và động viên tôi trong suốt thời gian học tập, nghiên cứu và hoàn thành luận án. Đà Nẵng, ngày 14 tháng 11 năm 2022 i 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 ........................................................................................... 1 CHƯƠNG 1. 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 trên mạng ............................................................ 11 1.2.1. Mạng ........................................................................................................... 11 1.2.2. Luồng trên mạng ......................................................................................... 12 1.2.3. Lát cắt, đồ thị tăng luồng, đường đi tăng luồng .......................................... 12 1.3. Bài toán luồng cực đại trên mạng ............................................. 14 1.3.1. Giới thiệu bài toán ...................................................................................... 14 1.3.2. Phát biểu bài toán........................................................................................ 15 1.3.3. Thuật toán Ford- Fulkerson ........................................................................ 15 1.3.4. Luồng cực đại và 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 về quy hoạch tuyến tính ............................................................. 21 1.4.2. Các dạng bài toán quy hoạch tuyến tính ..................................................... 22 1.4.3. Bài toán đối ngẫu ........................................................................................ 26 1.5. Bài toán luồng cực đại trên mạng hỗn hợp mở rộng đa hàng hó ...