ĐẠI HỌC ĐÀ NẴNG TRƯỜNG ĐẠI HỌC SƯ PHẠM - HOÀNG VĂN TÁM BÀI TỐN LUỒNG CỰC ĐẠI VỚI CHI PHÍ CỰC TIỂU VÀ ỨNG DỤNG TRONG VẬN CHUYỂN HÀNG CỨU TRỢ BÃO LŨ LUẬN VĂN THẠC SĨ NGÀNH HỆ THỐNG THÔNG TIN Đà Nẵng - Năm 2018 ĐẠI HỌC ĐÀ NẴNG TRƯỜNG ĐẠI HỌC SƯ PHẠM - HOÀNG VĂN TÁM BÀI TỐN LUỒNG CỰC ĐẠI VỚI CHI PHÍ CỰC TIỂU VÀ ỨNG DỤNG TRONG VẬN CHUYỂN HÀNG CỨU TRỢ BÃO LŨ Chuyên ngành: Hệ thống thông tin Mã số: 8480104 LUẬN VĂN THẠC SĨ NGƯỜI HƯỚNG DẪN KHOA HỌC: PGS TSKH Trần Quốc Chiến Đà Nẵng - Năm 2018 ii MỤC LỤC LỜI CAM ĐOAN i TÓM TẮT ĐỀ TÀI TIẾNG VIỆT iv TÓM TẮT ĐỀ TÀI TIẾNG ANH v DANH MỤC CÁC TỪ VIẾT TẮT vi DANH MỤC CÁC BẢNG vii DANH MỤC CÁC HÌNH viii MỞ ĐẦU 1 Lý chọn đề tài Mục tiêu nhiệm vụ Đối tượng phạm vi nghiên cứu Phương pháp nghiên cứu Ý nghĩa đề tài Bố cục đề tài CHƯƠNG BÀI TOÁN LUỒNG CỰC ĐẠI 1.1 Phát biểu toán 1.1.1 Mạng, Luồng mạng 1.1.2 Bài toán luồng cực đại mạng 1.2 Thuật toán Ford-Fulkerson 1.2.1 Đường tăng luồng 1.2.2 Phương pháp FordFulkerson CHƯƠNG BÀI TOÁN LUỒNG CỰC ĐẠI VỚI CHI PHÍ CỰC TIỂU 17 2.1 Giới thiệu 17 2.1.1 Phát biểu toán 17 2.1.2 Các giả thiết 18 2.1.3 Đồ thi thăng dư 18 2.2 Điều kiện tối ưu toán 18 2.2.1 Điều kiện tối ưu chu trình âm 18 2.2.2 Điều kiện tối ưu chi phí rút gọn 19 2.2.3 Điều kiện tối ưu bổ sung 20 2.3 Mối quan hệ luồng tối ưu khả thông qua đỉnh 21 2.4 Một số thuật toán giải toán luồng cực đại với chi phí cực tiểu 22 2.4.1 Thuật tốn khử chu trình âm (Cycle canceling) 22 2.4.2 Thuật tốn tìm đường ngắn liên tiếp (Successive shortest Path) 27 2.4.3 Thuật toán Primal-Dual 30 iii 2.4.4 Các thuật toán cải tiến 33 CHƯƠNG XÂY DỰNG ỨNG DỤNG 37 3.1 Yêu cầu thực tế lí xây dựng ứng dụng 37 3.2 Mục tiêu ứng dụng 37 3.3 Tiếp cận toán 37 3.3.1 Phát biểu toán 37 3.3.2 Mơ hình tốn học 39 3.3.3 Thuật toán 40 3.4 Phân tích 42 3.4.1 Yêu cầu chức 42 3.4.2 Mơ hình Use – Case 43 3.4.3 Biểu đồ (Sequence Diagram) 50 3.4.4 Cơ sở liệu (Database) 55 3.5 Thiết kế đặc tả giao diện 56 3.5.1 Giao diện “Trang chủ” 56 3.5.2 Giao diện “Menu trái” 58 3.5.3 Giao diện “Danh sách địa điểm” 59 3.5.4 Giao diện “Thông tin địa điểm” 61 3.5.5 Giao diện “Cập nhật địa điểm” 62 3.5.6 Giao diện “Thêm địa điểm” 64 3.5.7 Giao diện “Hiển thị kết quả” 65 3.6 Đánh giá kết 67 KẾT LUẬN 68 DANH MỤC TÀI LIỆU THAM KHẢO 69 QUYẾT ĐỊNH GIAO ĐỀ TÀI (Bản sao) vi DANH MỤC CÁC CHỮ VIẾT TẮT Từ viết tắt Ý nghĩa USD United States dollar GDP Gross Domestic Product HTML HyperText Markup Language CSS Cascading Style Sheets SDK Software Development Kit API Application Programming Interface SQL Structured Query Language NNLT Ngơn ngữ lập trình DFS Depth first search ATNĐ Áp thấp nhiệt đới UBND Ủy ban nhân dân vii DANH MỤC CÁC BẢNG Số hiệu Tên bảng Trang 3.1 Khoảng cách điểm thu - phát 41 3.2 Khả thông qua điểm thu – phát 41 3.3 Ma trận kết 42 3.4 Yêu cầu chức 43 3.5 Đặc tả Use – Case thêm địa điểm 44 3.6 Luồng kiện chức thêm địa điểm 44 3.7 Đặc tả Use – Case cập nhật địa điểm 44 3.8 Luồng kiện chức cập nhật địa điểm 45 3.9 Đặc tả Use – Case xóa địa điểm 45 3.10 Luồng kiện chức xóa địa điểm 46 3.11 Đặc tả Use – Case tìm đường tối ưu 46 3.12 Luồng kiện chức tìm đường tối ưu 46 3.13 Đặc tả Use – Case xem đồ 47 3.14 Luồng kiện chức xem đồ 48 3.15 Đặc tả Use – Case xem chi tiết đường 48 3.16 Luồng kiện chức xem chi tiết đường 48 3.17 Đặc tả Use – Case định vị vị trí 49 3.18 Luồng kiện chức định vị vị trí 49 3.19 Đặc tả sở liệu 55 3.20 Ràng buộc sở liệu 56 viii DANH MỤC CÁC HÌNH Số hiệu Tên hình hình Trang 1.1 Bài toán 1.2 Bài toán 13 2.1 Ví dụ mạng vận tải 17 2.2 Minh họa thuật tốn khử chu trình âm 26 2.3 Minh họa thuật toán đường ngắn liên tiếp 30 2.4 Minh họa thuật tốn Primal-dual 33 3.1 Mơ hình toán 38 3.2 Sơ đồ toán sau thêm đỉnh ảo 41 3.3 Biểu đồ Use – Case tổng quát 43 3.4 Biểu đồ Use – Case “Quản lí danh sách địa điểm” 43 3.5 Biểu đồ Use – Case “Tìm đường tối ưu” 46 3.6 Biểu đồ Use – Case “Xem đồ” 47 3.7 Biểu đồ Use – Case “Xem chi tiết lộ trình đi” 48 3.8 Biểu đồ Use – Case “Định vị vị trí” 49 3.9 Biểu đồ “Thêm địa điểm” 50 3.10 Biểu đồ “Cập nhật địa điểm” 51 3.11 Biểu đổ “Xóa địa điểm” 52 3.12 Biểu đồ “Tìm đường tối ưu” 53 3.13 Biểu đồ “Xem đồ” 53 3.14 Biểu đồ “Chi tiết đường đi” 54 3.15 Biểu đồ “Định vị vị trí” 54 3.16 Giao diện ứng dụng 56 3.17 Giao diện menu 58 3.18 Giao diện danh sách địa điểm 59 3.19 Giao diện thông tin địa điểm 61 3.20 Giao diện cập nhật thông tin địa điểm 62 3.21 Giao diện thêm địa điểm 64 3.22 Giao diện hiển thị kết 65 64 3.5.6 Giao diện “Thêm địa điểm” Hình 3.21 Giao diện thêm địa điểm Hiển thị Thêm địa điểm Mô tả Thêm thông tin địa điểm Hiển thị truy cập Nhấn vào buttonAdd giao diện “Danh sách địa điểm” Nội dung hiển thị Data Mô tả Item Type buttonSave ImageButton Lưu thông tin địa điểm buttonBack ImageButton Trở lại hình giao diện trước buttonSearch ImageButton Tìm kiếm địa điểm 65 Hành động Tên hành động Mô tả Thành công Không thành công Click vào buttonSave Lưu thông tin địa điểm Quay trở lại giao diện “Thông tin địa điểm” tương ứng với thông tin cập nhật Thông báo “Cập nhật địa điểm khơng thành cơng” Click vào buttonSearch Tìm kiếm địa điểm Hiển thị địa điểm gợi ý Click vào buttonBack Trở lại Quay trở lại trang giao diện trước 3.5.7 Giao diện “Hiển thị kết quả” Hình 3.22 Giao diện hiển thị kết 66 Hiển thị Đường đô Mô tả Hiển thị đường người dùng xem kết Hiển thị truy cập Truy cập vào ứng dụng Nội dung hiển thị Data Mô tả Item Type map Google Map Hiển thị đường đồ buttonLocation ImageButton Định vị vị trí buttonFindWay ImageButton Tìm đường buttonWayDetail ImageButton Chi tiết đường spinnerWay Spinner Danh sách điểm xuất phát buttonMenu ImageButton Hiển thị menu Tên hành động Mô tả Thành công Click đơi vào map Phóng to đồ Phóng to đồ Click vào buttonFindWay Tìm kiếm đường Hiển thị đường Thơng lên đồ báo: “Lỗi tìm đường đi” Click vào buttonLocation Định vị vị trí Hiển thị đồ vị trí Click vào buttonWayDetail Hiển thị chi tiết lộ trình Chuyển sang giao diện hiển thị chi tiết lộ trình bắt đầu kho chọn Click vào buttonMenu Hiển thị menu bên trái Hiển thị menu bên trái Hành động Chọn item khác Hiển thị đồ spinnerWay Hiển thị đường lên đồ tương ứng với mục chọn spinner Không thành công 67 3.6 Đánh giá kết Với việc sử dụng Google Map API, ứng dụng đưa lời giải tương đối xác đáp ứng yêu cầu khối lượng hàng hóa vận chuyển tối đa với chi phí vận chuyển thấp nhất, thõa mãn yêu cầu toán đặt Giao diện smartphone, trực quan dễ sử dụng có kết nối Internet Tuy nhiên ứng dụng nhiều hạn chế: - Chưa quản lí phương tiện phương án vận chuyển phương tiện - Chưa tính tốn phương pháp giao hàng tối ưu theo tiêu chí khác tiết kiệm thời gian, số lượng xe thấp nhất, tổng đường ngắn nhất,… - Ứng dụng tìm phương án vận chuyển hàng chiều đi, chưa tính đến việc quay phương tiện - Ứng dụng sử dụng Google Map API nên có giới hạn số truy vấn ngày yêu cầu phải có kết nối Internet 68 KẾT LUẬN Dựa sở tìm hiểu số vấn đề lý thuyết đồ thị, đặc biệt toán luồng cực đại với chi phí cực tiểu, thuật tốn cắt vịng pha, luận văn xây dựng ứng dụng MapV1 cho smartphone giúp tìm phương pháp vận chuyển tối ưu đảm bảo chi phí tối thiểu cho cơng tác cứu trợ thiên tai địa bàn tỉnh Quảng Bình Tuy nhiên kết ứng dụng nhiều hạn chế nêu Hướng phát triển luận văn thời gian tới hoàn thiện ứng dụng với đầy đủ tính năng: - Quản lí phương tiện phương án vận chuyển phương tiện - Tính toán phương pháp giao hàng tối ưu theo tiêu chí khác tiết kiệm thời gian, số lượng xe thấp nhất, tổng đường ngắn nhất,… - Tìm đường phương tiện chiều: 69 DANH MỤC TÀI LIỆU THAM KHẢO Tài liệu viết: [1] Trần Quốc Chiến (1995), Giáo trình lý thuyết tối ưu, Trường Đại học Bách khoa Đà Nẵng [2] Trần Quốc Chiến (2007), Giáo trình Lí thuyết đồ thị ứng dụng, Đại học Đà Nẵng [3] Trần Quốc Chiến (2008), Ứng dụng toán tối ưu mạng, Đề tài khoa học, Đại học Đà Nẵng [4] Nguyễn Đức Nghĩa - Nguyễn Tơ Thành (2003), Tốn rời rạc, Nhà xuất Đại học Quốc gia Hà Nội [5] Robert Sedgewick (1994), Cẩm nang thuật toán, Nhà xuất khoa học kỹ thuật [6] Claude Berge (1971), Lý thuyết đồ thị ứng dụng, Nhà xuất khoa học kỹ thuật [7] Reinhard Diestel (2000), Graph Theory, Springer - Verlag NewYork [8] Ravindra K Ahuja - Thomas L Magnanti - James B Orlin (1993), Network flows : Theory, Algorithms, and Applications, Prentice Hall [9] Robin Wilson (1996), Introduction to Graph Theory, Oliver & Boyd [10] Minieka (1978), Optimization Algorithms for Networks and Graphs, Dekker, New York [11] J.B Orlin (2013), Max Flows In O (nm) Time, or Better In Proceeding of the 45th Annual ACM Symposium on Theory of Computing, pp 765-744 ACM Website: [12] Giải thuật lập trình, http://www.giaithuatlaptrinh.com [13] MathWorld Site, http://mathworld.wolfram.com/NetworkFlow.html [14] MIT OpenCourseWare, http://ocw.mit.edu/OcwWeb/SloanSchool-ofManagement/15-082JNetwork- OptimizationSpring2003/CourseHome/ [15] Institute for Operations Research and the Management Sciences Site, http://www.informs.org/Conf/Montreal98/TALKS/MA36.html ... lý thuyết toán luồng cực đại số toán ứng dụng toán luồng cực đại - Nghiên cứu kỹ thuật toán toán luồng cực đại với chi phí cực tiểu - Nắm quy trình cài đặt thuật tốn, xây dựng ứng dụng cho smartphone... luận văn chia làm chương sau: Chương 1: Bài toán luồng cực đại Chương 2: Bài toán luồng cực đại với chi phí cực tiểu Chương 3: Xây dựng ứng dụng CHƯƠNG BÀI TOÁN LUỒNG CỰC ĐẠI 1.1 Phát biểu toán 1.1.1... CHƯƠNG BÀI TOÁN LUỒNG CỰC ĐẠI VỚI CHI PHÍ CỰC TIỂU 2.1 Giới thiệu 2.1.1 Phát biểu toán Trong thực tế ta thường phải giải toán: luồng cực đại tìm luồng có chi phí nhỏ nhất, chi phí tổng chi phí thực