Báo khoa học: Tiếp cận bài toán quy hoạch tuyến tính thông qua bài toán tìm đường đi ngắn nhất
lượt xem 16
download
Kết quả chính của bài báo là nghiên cứu mối quan hệ giữa bài toán quy hoạch tuyến tính với bài toán đường đi ngăn nhất. Dựa trên cơ sở vận dụng thuật toán Dijkstra cải tiến để tìm đường đi ngắn nhất của cặp đỉnh bất kì trên mạng đồ thị và kết hợp lý thuyết đối ngẫu trong quy hoạch tuyến tính. Bài báo phân tích, chứng minh các kết quả đưa ra cũng như đánh giá độ phức tạp của thuật toán.
Bình luận(0) Đăng nhập để gửi bình luận!
Nội dung Text: Báo khoa học: Tiếp cận bài toán quy hoạch tuyến tính thông qua bài toán tìm đường đi ngắn nhất
- TIẾP CẬN BÀI TOÁN QUY HOẠCH TUYẾN TÍNH THÔNG QUA BÀI TOÁN TÌM ĐƯỜNG ĐI NGẮN NHẤT ACCESS LINEAR PROGRAMMING PROBLEM SEARCH THROUGH SHORTEST PATH Trần Ngọc Việt Nguyễn Đình Lầu Phạm Văn Tiến NCS khóa 2010-2014 NCS khóa 2010-2014 Trường CĐ Công nghệ-KT và Thủy Lợi Đại học Đà Nẵng Đại học Đà Nẵng Miền Trung TÓM TẮT Kết quả chính của bài báo là nghiên cứu mối quan hệ giữa bài toán quy hoạch tuyến tính với bài toán đường đi ngắn nhất. Dựa trên cơ sở vận dụng thuật toán Dijkstra cải tiến để tìm đường đi ngắn nhất của cặp đỉnh bất kì trên mạng đồ thị và kết hợp lý thuyết đối ngẫu trong quy hoạch tuyến tính. Bài báo phân tích, chứng minh các kết quả đưa ra cũng như đánh giá độ phức tạp của thuật toán. Chương trình tương ứng cài đặt bằng C và cho kết quả chính xác. ABSTRACT The results of the paper is to study the relationship between linear programming problem with the shortest path problem. Based on applying improved Dijkstra algorithm to find the shortest path of any pair of vertices on the graph and associated duality theory of linear programming. The article analysis, the results prove out as well as evaluating the complexity of the algorithm. Corresponding program installed in C and for accurate results. Key word: Shortest path, linear programming, graph 1. Sơ lược về các phương pháp tối ưu Trong thực tế sản xuất kinh doanh chúng ta th ường phải gi ải quy ết các nhiệm vụ dẫn đến việc tìm giá trị max hoặc min của một hàm nào đó. Chẳng hạn cần lập phương án sản xuất, thi công sao cho có th ể đ ạt được m ột trong các yêu cầu sau: + Tổng giá trị sản lượng lớn nhất; + Tổng lợi nhuận lớn nhất; + Chi phí thấp nhất; + Cước phí rẻ nhất; + Thời gian thực hiện nhanh nhất; + Tổng vốn đầu tư nhỏ nhất… 1
- Những yêu cầu (hoặc mục tiêu) nói trên được biểu diễn bằng một hàm và ta cần lập phương án sản xuất, thi công sao cho hàm đó đ ạt giá tr ị max ho ặc min. Những bài toán như vậy gọi chung là các bài toán tối ưu. Đ ể gi ải các bài toán đó, một loạt các lý thuyết toán học ra đời đặt cơ sở lý lu ận và tìm tòi l ời gi ải, … T ừ đó hình thành lớp các phương pháp toán học giúp ta tìm lời giải tốt nh ất cho các bài toán thực tế. Các phương pháp đó gọi là các phương pháp tối ưu hoá. 2. Xây dựng mô hình toán học cho các bài toán tối ưu thực tế Việc mô hình hoá toán học cho một vấn đề th ực t ế có th ể chia làm b ốn bước như sau: Bước 1: Xây dựng mô hình định tính cho vấn đề đặt ra. Bước 2: Xây dựng mô hình toán học cho vấn đề đang xét. Trong bước này việc quan trọng là phải xác định hàm mục tiêu và các ràng buộc toán học. Bước 3: Sử dụng công cụ toán học để khảo sát, giải quyết các bài toán hình thành trong bước 2. Bước 4: Kiểm định lại các kết quả thu được trong bước 3. 3. Bài toán đường đi có trọng số bé nhất 3.1. Bài toán. Cho đồ thị G = (V, E, c) và hai đỉnh a, z. Tìm đường đi ngắn nhất (nếu có) đi từ đỉnh a đến đỉnh z trong đồ thị G. Đồ thị G được gọi là đồ thị có trọng số nếu trên mỗi cạnh (i, j) của đồ thị được gán một số nguyên không âm c(i,j). -Nhãn c(i,j) trên cạnh (i,j) của đồ thị thường biểu diễn “ chi phí” thực tế để đi qua cạnh này. -Độ dài đường đi ngắn nhất từ đi đỉnh a đến đỉnh z còn được gọi là khoảng cách từ đỉnh a đến đỉnh z trong đồ thị. Nếu không có đường đi từ a đến z thì đặt khoảng cách bằng ∞. -Ý nghĩa thực tế: Bài toán này giúp chúng ta chọn các hành trình ti ết ki ệm nh ất (quãng đường, thời gian, chi phí ...) trong giao thông, lập lịch thi công các công trình một cách tối ưu, ... 3.2. Định lý. Tại mỗi đỉnh z giá trị nhãn d(z) cuối cùng (nếu có) chính là độ dài của đường đi ngắn nhất từ đỉnh a đến đỉnh z. Chứng minh. Sau khi đã thực hiện xong thuật toán trên, nếu giá trị nhãn d(z) xác định thì ta có đường đi từ đỉnh a tới đỉnh z. Ta khôi phục đường đi từ a đến z như sau: d(i) + c(i,z) = d(z). Đỉnh i như thế chắc chắn phải tồn tại vì xảy ra đẳng thức ở lần gán hoặc giảm giá trị nhãn d(j) cuối cùng. Cứ tiếp tục như thế cho đến khi gặp đỉnh a. Giả sử ta nhận được dãy các cạnh: (a, a1) , (a1, a2) , ... , (ak-1, z) Ta có: 2
- d(a) + c(a,a1) = d(a1) d(a1) + c(a1,a2) = d(a2) d(a2) + c(a2,a3) = d(a3) .. . .. . . . .. .. .. . . .. .. . . d(ak-1) + c(ak-1, z) = d(z). Cộng lại vế theo vế, ta được: c(a,a1) + c(a1,a2) + c(a2,a3)+ ... + c(ak-1,z) = d(z). Giá trị nhãn d(z) chính là độ dài đường đi nói trên. Bất kỳ đường đi nào khác từ đỉnh a đến đỉnh z cũng có các hệ thức tương tự nhưng có dấu ≥. Vậy nhãn d(z) là độ dài của đường đi ngắn nhất. 3.3.Thuật toán Dijkstra tìm đường đi ngắn nhất Thuật giải tìm đường đi ngắn nhất từ đỉnh nguồn a đến đỉnh đích z trong đồ thị có trọng số, với c(i,j) > 0 và đỉnh x sẽ mang nhãn L(x). Kết thúc giải thuật L(z) chính là chiều dài ngắn nhất từ a đến z. + Đầu vào. Đồ thị G = (V, E, c) có trọng số c(i,j) > 0 với mọi cạnh (i, j ) , đỉnh nguồn a và đỉnh đích z. + Đầu ra. L(z) chiều dài đường đi ngắn nhất từ đỉnh nguồn a đến đỉnh đích z và đường đi ngắn nhất (nếu L(z) < + ∞ ). + Phương pháp gồm các bước sau: (1)Khởi tạo: Gán L(a):=0. Với mọi đỉnh x ≠ a gán L(x) := ∞ . Đặt T:=V. (2)Tính m := min{L(u ) u ∈ T }. Nếu m = + ∞, kết thúc và ta nói không tồn tại đường đi từ a đến z. Ngược lại, nếu m < + ∞, chọn v ∈ T sao cho L(v) = m và đặt T := T − {v} . Sang bước 3. (3)Nếu z = v , kết thúc, L(z) là chiều dài đường đi ngắn nhất từ a đến z. Từ z lần ngược theo đỉnh được ghi nhớ ta có đường đi ngắn nhất. Ngược lại, nếu z ≠ v , sang bước 4. (4)Với mỗi x ∈ T kề (kề sau) v, nếu L( x) > L(v) + c(v, x), thì gán L( x) := L(v) + c(v, x) và ghi nhớ đỉnh v cạnh x để xây dựng đường đi ngắn nhất. Quay về bước 2. *)Ghi chú. Độ phức tạp của thuật toán là O( n 2 ). 3.4. Hướng tiếp cận bài toán quy hoạch tuyến tính thông qua bài toán tìm đường đi ngắn nhất : Xét bài toán quy hoạch tuyến tính dạng tổng quát: { } max cT x Ax ≤ b, x ≥ 0 trong đó: b = (b1 , b2 ,..., bm ) vectơ vế phải, x = ( x1 , x2 ,..., xn ) vectơ biến số, 3
- c = (c1 , c2 ,..., cn ) vectơ hệ số hàm mục tiêu. Bài toán đối ngẫu của nó là: { min bT y AT y ≥ c, y ≥ 0 } Biến đối ngẫu y (i ) của độ dài cạnh i length y ( j ) = ∑ i A(i, j ) y (i ) / c( j ) Tìm 1 đường đi ngắn nhất tương ứng với tìm kiếm 1 cột có chiều dài tối thiểu: α ( y ) = min j length y ( j ) Đặt: D( y ) = bT y Tìm biến đối ngẫu y sao cho: D( y ) / α ( y ) là nhỏ nhất Giả sử, biến đối ngẫu y k −1 và biến của bài toán gốc f k −1 Cho q là cột có chiều dài nhỏ nhất từ ma trận A: α ( y k −1 ) = length y k −1 (q ) Từ ma trận A có cột xem là cạnh với: b(i ) / A(i, q ) là nhỏ nhất Dùng biến x(q ) từ bài toán gốc với: b( p ) / A( p, q ) ⇒ f k = f k −1 + c(q)b( p) / A( p, q) b( p ) / A( p, q ) Ta được cấu trúc bài toán đối ngẫu: y k (i ) = y k −1 (i )1 + ε b(i ) / A(i, q) Ta chọn hằng số ε sao cho hợp lí; Tính biến đối ngẫu y0 (i ) = δ / b(i ) dựa vào hằng số δ chọn hợp lí. Từ α ( y k ), D( yk ) biến đổi thành α (k ), D(k ) . Do đó, ta được D(0) = mδ , với D(t ) ≥ 1,α (t ) ≥ 1. Cho k ≥ 1 : D(k ) = ∑ b(i ) y k (i ) i b( p ) = ∑ b(i ) y k −1 (i ) + ε ∑ A(i, q) y k −1 (i ) i A( p, q ) i = D(k − 1) + ε ( f k − f k −1 )α (k − 1) k ⇒ D(k ) = D(0) + ε ∑ ( f l − f l −1 )α (l − 1) l =1 Giả sử β = min y D( y ) / α ( y ) thì ta được β ≤ D(l − 1) / α (l − 1) 4
- ε k và D(k ) ≤ mδ + ∑ ( f l − f l −1 ) D(l − 1) β l =1 ε k ⇒ x(i ) = mδ + ∑ ( f l − f l −1 ) x(l − 1) β l =1 ε k −1 ε ⇒ x( k ) = mδ + ∑ ( f l − f l −1 ) x(l − 1) + ( f k − f k −1 ) x(k − 1) β l =1 β ε = 1 + ( f k − f k −1 ) x( k − 1) β ≤ eε ( f k − f k −1 ) / β .x(k − 1) ≤ eε . f k / β .x(0) = mδ .eε . f k / β Dùng BĐT: D(k ) ≤ x( k ) ⇒ D(k ) ≤ mδ .eε . f k / β Vậy, 1 ≤ D(t ) ≤ mδ .eε . f t / β β ε Suy ra: ≤ f t ln(mδ ) −1 3.5.Thử nghiệm chương trình: Sau đây là ví dụ kết quả chạy chương trình bài toán quy hoạch tuyến tính thông qua bài toán tìm đường đi ngắn nhất. Ví dụ: Cho mạng đồ thị gồm 4 đỉnh, 7 cạnh và các nút từ 1 đến 4 1 2 6 7 4 7 1 11 5 3 5
- 4 (Hình 1) Kết quả chạy chương trình như sau: 4. Kết luận Kết quả của bài báo đã đáp ứng được mục tiêu đề tài là “ Ti ếp c ận bài toán quy hoạch tuyến tính thông qua tìm đường đi ngắn nhất ” đã đặt ra, đó là nghiên cứu xây dựng mô hình toán học cho bài toán Quy hoạch, trong đó các ràng buộc về khả năng thông qua, mục tiêu tối ưu, phát triển và áp dụng hiệu qu ả các thu ật toán tối ưu. 6
- TÀI LIỆU THAM KHẢO [1] NguyÔn Cam, Chu §øc Kh¸nh: Lý thuyÕt ®å thÞ. NXB TP.HCM, 1999. [2] TrÇn Quèc ChiÕn, Gi¸o tr×nh lý thuyÕt ®å thÞ, §¹i häc §µ N½ng 2002. [3] TrÇn Quèc ChiÕn, Thuật toán hoán chuyển nguồn đích tìm luồng cực đại, T¹p chÝ Khoa häc & c«ng nghÖ số 26-năm 2008, ĐHĐN. [4] NguyÔn Xu©n Quúnh: C¬ së To¸n rêi r¹c vµ øng dông. NXB Gi¸o dôc. Hµ Néi 1995. [5] A.V.Goldberg, R.E.Tarjan, Expected performance of Dijkstra’s shortest path algorithm, Technical Report 96-070, NEC Research Institute Inc, 1996. [6] V.K. Balakrishnan: Theory and Problems of Graph Theory. McGRAW-HILL. 1997. [7] Christofides Nicos: Graph Theory. Academic Press. New York London San Francisco, 1975. [8] R.G. Busacker & T.L. Saaty: Finite Graph and Networks. Mc Graw-Hill Book Company. New York - St. Louis - San Francisco - Toronto - London - Sydney, 1974. 7
- [9] Frederic Babonneau: Solving the multicommodity flow problem with the analytic center cutting plane method. UNIVERSITY DE GENEVE, 2006. [10] Ellis L. Johnson, Committee Chair, George L. Nemhauser: Shortest paths and multicommodity network flow, 2002. 8
CÓ THỂ BẠN MUỐN DOWNLOAD
-
Luận văn tốt nghiệp: Một cách tiếp cận bài toán về hàm số
22 p | 397 | 100
-
Tìm hiểu các hướng tiếp cận bài toán phân loại văn bản và xây dựng phần mềm phân loại tin tức báo điện tử - 1
44 p | 205 | 59
-
Báo cáo nghiên cứu khoa học: " TIẾP CẬN CHUỖI GIÁ TRỊ CHO VIỆC NÂNG CẤP NGÀNH DỆT MAY VIỆT NAM"
11 p | 175 | 59
-
Báo cáo nghiên cứu khoa học: " TÁC ĐỘNG CỦA VỐN VAY TỪ NGÂN HÀNG CHÍNH SÁCH XÃ HỘI THỪA THIÊN HUẾ ĐẾN HỘ NGHÈO THEO QUAN ĐIỂM TIẾP CẬN MỨC SỐNG"
10 p | 188 | 43
-
Báo cáo khoa học: Tiếp cận bài toán quy hoạch tuyến tính thông qua bài toán tìm đường đi ngắn nhất
16 p | 135 | 21
-
Báo cáo " Thử xác định đối tượng cho chính sách kích cầu ở Việt Nam cách tiếp cận phân tích bảng cân đối liên ngành liên vùng "
9 p | 164 | 19
-
Báo cáo nghiên cứu khoa học: "CẤU TRÚC THÔNG TIN VÀ CẤU TRÚC ĐỀ THUYẾT TRONG DỊCH THUẬT"
13 p | 176 | 18
-
Báo cáo khoa học: Phương pháp lọc thư rác tiếng Việt dựa trên từ ghép và theo vết người sử dụng
11 p | 129 | 14
-
Báo cáo khoa học: Một số phương pháp hiệu chỉnh góc nghiêng của ảnh và ứng dụng
10 p | 158 | 13
-
Báo cáo nghiên cứu khoa học: "MỘT PHƯƠNG PHÁP XỬ LÝ TRUY VẤN CON TRONG CƠ SỞ DỮ LIỆU MỜ THEO CÁCH TIẾP CẬN ĐẠI SỐ GIA TỬ"
9 p | 108 | 11
-
Báo cáo " Về phương pháp tiếp cận nghiên cứu ngôn ngữ chuyên ngành "
7 p | 129 | 11
-
khả năng tiếp cận thị tr-ờng với sản xuất và tiêu thụ nông lâm sản ở vùng núi Tây Bắc Việt Nam
0 p | 72 | 9
-
Luận án tiến sĩ Khoa học máy tính: Xây dựng mô hình lai cho bài toán dự báo theo tiếp cận mờ hướng dữ liệu
132 p | 76 | 9
-
Báo cáo nghiên cứu khoa học: "TIẾP CẬN MỚI BẢN CHẤT NĂNG SUẤT VÀ PHÂN TÍCH NÓ"
5 p | 80 | 9
-
Báo cáo nghiên cứu khoa học: " TIẾP CẬN LÝ THUYẾT VÀ THỰC TIỄN LUSTER NGÀNH CHO PHÁT TRIỂN KINH TẾ KHU VỰC"
9 p | 78 | 9
-
Báo cáo nghiên cứu khoa học: " DỊCH CHUYỂN TRUY VẤN OQL VÀO CÁC PHÉP TÍNH BAO HÀM"
9 p | 89 | 7
-
Báo cáo khoa học: "TIẾP CẬN ĐA XU HƯỚNG PHÁT TRIỂN CỦA CÁC NGHIÊN CỨU LÍ THUYẾT VÀ THỰC NGHIỆM VỀ BÊ TÔNG HIỆN NAY"
8 p | 85 | 6
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