Tiểu luận: Lý thuyết đối ngẫu

Tiểu luận: Lý thuyết đối ngẫu nhằm phân tích tổng quan các vấn đề liên quan đến đề tài luận án như thuật toán đường đi ngắn nhất, thuật toán Bellmen - Ford,...và phương pháp nghiên cứu, kết quả dự kiến và phương hướng phát triển của đề tài.
Nội dung trích xuất từ tài liệu:
Tiểu luận: Lý thuyết đối ngẫu BỘ GIÁO DỤC VÀ ĐÀO TẠO ĐẠI HỌC ĐÀ NẴNG TIỂU LUẬN LÝ THUYẾT ĐỐI NGẪU Học phần: Tối ưu hóa Chuyên ngành: Khoa học máy tính Mã sô: 62.48.01.01 ́ Khóa học: 2011 - 2015 NCS. Trần Ngọc ViệtNgười hướng dẫn: PGS.TSKH. Trần Quốc Chiến PGS.TS. Lê Mạnh Thạnh ĐÀ NẴNG – 2012 1 MỤC LỤCMỞ ĐẦU ……………………………………………………………… 2Chương 1. PHÂN TÍCH TỔNG QUAN CÁC VẤN ĐỀ LIÊN QUAN ĐẾN ĐỀ TÀI LUẬN ÁN 1. Tổng quan về các công trình trong nước liên quan đến đề tài luận án …………………………………………………….. 3 1.1. Công trình về thuật toán tìm đường đi ngắn nhất ……….. 3 1.1.1. Thuật toán đường đi ngắn nhất xuất phát từ một đỉnh .. 5 1.1.2. Thuật toán đường đi ngắn nhất trong k cặp đỉnh nguồn đích ……………………………………………….. 6 1.2. Thuật toán Bellman – Ford …………………………….. 8 1.3. Thuật toán Floyd-Warshall ……………………………. . 9 1.4. Công trình về thuật toán luồng cực đại …………………. 10 1.5. Bài toán luồng đa phương tiện cực đại …………………. 14 1.6. Bài toán luồng đa phương tiện cực đại đồng thời ………. 19 1.7. Bài toán luồng đa phương tiện cực đại đồng thời có ràng buộc chi phí …………………………………………….. 23 2. Tổng quan về các công trình đã nghiên cứu trên thế giới …. 27 3. Một số ứng dụng lớn trên thế giới ………………………. 28 4. Danh mục các công trình liên quan ………………………. 29Chương 2. PHƯƠNG PHÁP NGHIÊN CỨU, KẾT QUẢDỰ KIẾN VÀ HƯỚNG PHÁT TRIỂN CỦA ĐỀ TÀI …………. 31KẾT LUẬN ………………………………………………………… 33TÀI LIỆU THAM KHẢO …………………………………………. 34 2Chương 1. LÝ THUYẾT ĐỐI NGẪU1.1. Khái niệm về đối ngẫu Đối ngẫu là một khái niệm cơ bản của việc giải bài toán quy ho ạchtuyến tính vì lý thuyết đối ngẫu dẫn đến một kết quả có tầm quan trọng v ềmặt lý thuyết và cả mặt thực hành.1.2. Phát biểu bài toán đối ngẫu Tương ứng với mỗi bài toán Quy hoạch tuyến tính (còn gọi là bài toángốc) có một bài toán đối ngẫu. Bài toán đối ngẫu của bài toán QHTT cũng làmột bài toán QHTT. Như vậy, bài toán gốc và bài toán đối ngẫu của nó lậpthành một cặp bài toán QHTT, tính chất của bài toán này có th ể được kh ảo sátthông qua bài toán kia. Nhiều quy trình tính toán hay phân tích đ ược hoàn thi ệnkhi xem xét cặp bài toán trên trong mối liên quan ch ặt ch ẽ của chúng, mang l ạilợi ích trong việc giải quyết các vấn đề phát sinh từ th ực tế. Với m ục đích tìmhiểu bước đầu, chúng ta xét bài toán gốc là bài toán quy hoạch tuyến tính dạngMax với các ràng buộc chỉ có dấu ≤ và các biến đều thoả mãn điều kiệnkhông âm.Bài toán gốc max f ( x) = c1 x1 + c2 x2 + ... + cn xn với các điều kiện ràng buộc  a11 x1 + a12 x2 + ... + a1n xn ≤ b1  a x + a x + ... + a x ≤ b  21 1  22 2 2n n 2  ... a x + a x + ... + a x ≤ b  m1 1 m2 2 mn n m   x1 , x2 ,..., xn ≥ 0 3Lúc đó bài toán QHTT sau đây được gọi là bài toán đối ngẫu của bài toánQHTT trên.Bài toán đối ngẫu min g ( y ) = b1 y1 + b2 y 2 + ... + bm y m với các điều kiện ràng buộc:  a11 y1 + a21 y 2 + ... + am1 y m ≥ c1 a y + a y + ... + a y ≥ c  12 1  22 2 m2 m 2  ... a y + a y + ... + a y ≥ c  1n 1 2n 2 mn m n   y1 , y 2 ,..., y m ≥ 0Các biến y1 , y 2 ,..., y m được gọi là các biến đối ngẫu. Trong trường hợp này,do bài toán gốc có m ràng buộc, nên bài toán đối ngẫu có m bi ến đối ng ẫu.Biến đối ngẫu yi tương ứng với ràng buộc thứ i của bài toán gốc.Trong trường hợp quy hoạch tuyến tính tổng quát, những quy tắc sau đây đượcáp dụng để xây dựng bài toán đối ngẫu : - Hàm mục tiêu đối ngẫu : . max ↔ min - Biến đối ngẫu : . mỗi ràng buộc ↔ một biến đối ngẫu - Chi phí đối ngẫu và giới hạn ràng buộc : . chi phí đối ngẫu ↔ giới hạn ràng buộc - Ma trận ràng buộc đối ngẫu : . ma trận ...