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ệt Người hướng dẫn: PGS.TSKH. Trần Quốc Chiến PGS.TS. Lê Mạnh Thạnh ĐÀ NẴNG – 2012 MỤC LỤC MỞ ĐẦU 2 Chươ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 . 29 Chươ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 . 31 KẾT LUẬN 33 TÀI LIỆU THAM KHẢO . 34 Chương 1. LÝ THUYẾT ĐỐI NGẪU 1.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ạch tuyế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án gố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ập thà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át thô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ện khi 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ại lợ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ìm hiể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ạng Max với các ràng buộc chỉ có dấu và các biến đều thoả mãn điều kiện không âm. Bài toán gốc với các điều kiện ràng buộc Lúc đó bài toán QHTT sau đây được gọi là bài toán đối ngẫu của bài toán QHTT trên. Bài toán đối ngẫu với các điều kiện ràng buộc: Các biến đượ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 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 chuyển vị - Chiều của ràng buộc và dấu của biến : . ràng buộc trong bài toán max có dấu ≤ thì biến đối ngẫu trong bài toán min có dấu ≥ 0 ( trái chiều ) . ràng buộc trong bài toán max có dấu = thì biến đối ngẫu trong bài toán min có dấu tùy ý. . ràng buộc trong bài toán max có dấu ≥ thì biến đối ngẫu trong bài toán min có dấu ≤ 0 ( trái chiều ) . biến của bài toán max có dấu ≥ 0 thì ràng buộc đối ngẫu trong bài toán min có dấu ≥ ( cùng chiều ) . biến của bài toán max có dấu tùy ý thì ràng buộc đối ngẫu trong bài toán min có dấu = . biến của bài toán max có dấu ≤ 0 thì ràng buộc trong bài toán đối ngẫu min có dấu ≤ ( cùng chiều ) 1.3. Định lý độ lệch bù Giả sử x* và y* là các phương án tối ưu của cặp bài toán đối ngẫu. Lúc đó (x*, y*) thoả mãn hệ: Chứng minh Với hay Mặt khác, Chú ý rằng: Vậy, ta có điều phải chứng minh. 1.4. Cơ sở của phương pháp đơn hình đối ngẫu Xét bài toán gốc: với Dễ dàng đưa bài toán này về dạng chính tắc: với các ràng buộc , trong đó , với chỉ số dưới s dùng để ký hiệu các chỉ số bù. Xét một véc tơ thỏa mãn . Bằng cách phân rã và cho với . Các véc tơ cột của B được gọi là: - Cơ sở gốc chấp nhận nếu , nhưng không nhất thiết - Cơ sở đối ngẫu chấp nhận nếu , nhưng không nhất thiết Kiểm tra lại các bước của thuật toán đơn hình đối ngẫu. Giả sử, là một phương án đối ngẫu khả thi, tức là các véc tơ cột , là cơ sở đối ngẫu chấp nhận. Nên Nếu thì là phương án tối ưu. Chú ý rằng, thuật toán đơn hình đối ngẫu được bắt đầu với ma trận , do đó có Nếu chưa được thỏa mãn thì tồn tại Lúc đó ta cần thực hiện thủ tục xoay. Trường hợp 1: ( là tập các chỉ số của các véc tơ cột của ma trận ), Điều này có nghĩa là tất cả các tọa độ thứ q của các véc tơ đều không âm. Ta sẽ chỉ ra rằng bài toán gốc không có phương án, hay bài toán đối ngẫu có hàm mục tiêu không bị chặn trên. Xét véc tơ: Dễ dàng chứng minh được đây đúng là phương án của bài toán đối ngẫu. Thật vậy, ta có: Đặt là véc tơ hàng q trong ma trận và xét với nào đó. Thế thì . Ta có , nên . Do đó, hay cũng là phương án của bài toán đối ngẫu. Mặt khác, giá trị của hàm mục tiêu trong bài toán đối ngẫu là khi Để chứng minh bài toán gốc không có phương án có thể lập luận ngắn gọn hơn. Thật vậy, ta có (do . Nếu bài toán gốc có phương án với các tọa độ không âm thì đây là điều vô lý vì: Trường hợp 2: Ta chọn cột xoay theo “qui tắc tỷ số âm lớn nhất”, tức là chọn chỉ số s sao cho: Tiếp tục thực hiện thủ tục xoay trong bài toán đơn hình đối ngẫu, ta sẽ chuyển được sang phương án đối ngẫu khả thi mới. Trong phương án mới sẽ là biến cơ sở thay chỗ cho biến . Vì mỗi phương án đối ngẫu khả thi tìm được trong quá trình giải tương ứng với một ma trận cơ sở B trong một phân rã nào đó A = [N B], nên số phương án đối ngẫu khả thi được xem xét là một số hữu hạn. Do đó, sau một số hữu hạn bước, ta sẽ kết thúc việc giải bài toán QHTT bằng phương pháp đơn hình đối ngẫu. 1.5. Thuật toán đơn hình đối ngẫu Thuật toán đơn hình đối ngẫu được xây dựng dựa trên tính chất của cặp bài toán đối ngẫu. Thuật toán của phương pháp đơn hình đối ngẫu được phát biểu cho bài toán QHTT: , với Bước khởi tạo -Tìm một phương án đối ngẫu khả thi tương ứng với ma trận cơ sở B trong một phân rã nào đó : điều kiện có thể không được thỏa mãn nhưng luôn có -Tính: trong đó n là số biến của bài toán đang xét. Các bước lặp Bước 1: Kiểm tra điều kiện tối ưu. Nếu điều kiện tối ưu đã được thỏa mãn thì in / lưu kết quả của bài toán và dừng. Bước 2: Nếu tồn tại một chỉ số sao cho thì tiến hành thủ tục xoay gồm nhiều bước tương tự theo thủ tục xoay của phương pháp đơn hình với các khác biệt sau: - Trước tiên chọn hàng xoay là hàng với biến có giá trị âm (thông thường với trị tuyệt đối lớn nhất, hoặc chọn ngẫu nhiên). - Sau đó chọn cột xoay theo quy tắc tỷ số âm lớn nhất (các tỷ số được tạo ra bằng cách lấy hàng chia cho hàng và chỉ xét các tỷ số có mẫu số âm). Nếu không tìm được cột xoay thì kết luận bài toán không có phương án khả thi, in / lưu kết quả của bài toán và chuyển sang bước kết thúc. - Nếu tìm được cột xoay thì thực hiện các bước tiếp theo của thủ tục xoay. -Tính lại các và quay lại bước 1. -Việc thực hiện giải bài toán gốc bằng phương pháp đơn hình đối ngẫu thực chất là việc giải bài toán đối ngẫu bằng phương pháp đơn hình. Điều này cũng giải thích lí do tại sao khi thực hiện thủ tục xoay của phương pháp đơn hình đối ngẫu cần trước hết xác định hàng xoay rồi sau đó mới xác định cột xoay. Ví dụ: Xét cặp bài toán đối ngẫu Bài toán gốc với các ràng buộc Nếu giải trực tiếp bài toán trên bằng phương pháp đơn hình, thì cần đưa bài toán về dạng chính tắc với 8 biến (thêm ba biến bù “thừa” và ba biến giả). Một phương pháp khác như đã biết là, trước hết tìm cách giải bài toán đối ngẫu (chỉ với 5 biến), sau đó sẽ tìm được phương án tối ưu của bài toán gốc. Bài toán đối ngẫu với các ràng buộc Viết bài toán đối ngẫu dưới dạng chính tắc: với các ràng buộc Cách 1. Giải bài toán đối ngẫu bằng phương pháp đơn hình. Kết quả được cho trong bảng. Theo tính chất của cặp bài toán đối ngẫu, ta có phương án tối ưu của bài toán gốc là với Hệ số Biến cơ sở P/án y y y y y 0 0 y y 3 2 1 2 1 1 [2] 1 1 0 0 1 0 0 4 0 3 0 4 0 0 0 0 4 0 y y 3/2 1/2 ½ [3/2] ½ 1/2 1 0 ½ -1/2 0 1 6 2 2 2 1 4 0 2 -2 0 0 4 4 y y 4/3 1/3 0 1 1/3 [1/3] 1 0 2/3 -1/3 -1/3 2/3 20/3 4 0 8/3 1/3 4 0 4/3 -4/3 4/3 -4/3 4 3 y y 1 1 -1 3 0 1 1 0 1 -1 -1 2 7 5 -1 3 0 4 0 1 -1 2 -2 Cách 2. Giải bài toán gốc bằng phương pháp đơn hình đối ngẫu. Trước hết đưa Bài toán gốc về dạng sau: với các ràng buộc Nội dung tóm tắt của phương pháp đơn hình đối ngẫu: Trong phương pháp đơn hình, dịch chuyển dần từ phương án khả thi, tức là ≥ 0, ∀j nhưng điều kiện Δ≥ 0, ∀j chưa được thoả mãn, tới phương án tối ưu, tức là x≥ 0 và Δ ≥ 0, ∀j. Trong phương pháp đơn hình đối ngẫu, ta dịch chuyển dần từ phương án không khả thi (nhưng đối ngẫu khả thi), tức là điều kiện ≥ 0, ∀j không được thoả mãn nhưng luôn có Δ ≥ 0, ∀j, tới phương án tối ưu, tức là có x ≥ 0 và Δ ≥ 0, ∀j. Quy trình giải bài toán gốc dạng chuẩn tắc trên đây bằng phương pháp đơn hình đối ngẫu được mô tả trong bảng như sau: Hệ số Biến cơ sở P/án 3 2 0 0 0 x x x x x 0 0 0 x x x -4 -3 -4 -1 -1 [-2] -2 -1 -1 1 0 0 0 1 0 0 0 1 0 0 3 0 2 0 0 0 0 0 0 0 0 3 x x x -2 -1 2 0 0 1 [-3/2] -1/2 1/2 1 0 0 0 1 0 -1/2 -1/2 -1/2 6 3 0 3/2 1/2 0 0 0 0 -3/2 3/2 2 0 3 x x x 4/3 -1/3 4/3 0 0 1 1 0 0 -2/3 [-1/3] 1/3 0 1 0 1/3 -1/3 -2/3 20/3 4 0 2 0 -1/3 1/3 0 0 -4/3 4/3 2 0 3 x x x 2 1 1 0 0 1 1 0 0 0 1 0 -2 -3 1 1 1 -1 7 3 0 2 0 0 0 -1 1 -1 1 Chương 2. ỨNG DỤNG BÀI TOÁN ĐỐI NGẪU 2.1. Ứng dụng bài toán đối ngẫu cho bài toán phân luồng giao thông tuyến tính + Cho một đồ thị có hướng G = (V, E) với khả năng thông qua của các cung là Trong V có đỉnh nguồn tương ứng với đỉnh đích và các đỉnh trung gian khác tạo thành một mạng có hướng. Ở đây mỗi cặp đỉnh nguồn đích được gắn với một phương tiện . Giả thiết rằng phương tiện xuất phát từ đỉnh nguồn định trước, thì sẽ kết thúc tại đỉnh đích tương ứng, với Bài toán luồng đa phương tiện cực đại là tìm một luồng đa phương tiện trong mạng G đã cho, sao cho tổng các luồng của tất cả phương tiện đạt cực đại. +Cơ sở lý thuyết thuật toán: Gọi là tập hợp các đường đi từ đến trong mạng G, Gọi , là hợp của Với là tập hợp các đường trong P đi qua Mỗi đường , gắn một biến của luồng gửi dọc theo đường Yêu cầu bài toán được phát biểu dạng bài toán quy hoạch tuyến tính như sau: (P) Giải bài toán (P) ta xây dựng mô hình tuyến tính đối ngẫu với (P) gọi là bài toán (D) như sau: , gắn cho một hàm độ dài . Định nghĩa: (D) Gọi là độ dài ngắn nhất tính theo trong các đường thuộc , Đặt Vậy là độ dài ngắn nhất trong mọi đường giữa các cặp nguồn đích. Xét bài toán Ta có Khi đó, ta được là phương án chấp nhận của (D) và Từ đó suy ra . Ngược lại, nếu là phương án chấp nhận của (D) thì , từ đó suy ra . Cuối cùng ta được . Tiếp theo, nếu là nghiệm tối ưu của bài toán thì là nghiệm tối ưu của bài toán (D). +Thuật toán: Thuật toán được thực hiện bởi một số bước lặp. Gọi là hàm độ dài tại điểm bắt đầu bước lặp thứ và là giá trị tổng luồng đã đạt được sau các bước lặp Ta có là độ dài ngắn nhất trong các đường nối giữa các cặp nguồn đích, tính theo . Gọi là đường đi có độ dài và là khả năng thông qua cực tiểu trên . Tại bước lặp , ta chuyển đơn vị phương tiện dọc theo . Theo đó Tiếp theo ta đặt trong đó là hằng số sẽ chọn sau. Ban đầu, , đặt , trong đó là hằng số cũng được chọn sau. Thuật toán dừng sau bước, với là số nhỏ nhất mà 2.2. Ứng dụng bài toán đối ngẫu cho bài toán luồng đa phương tiện cực đại đồng thời Cho một đồ thị có hướng G = (V, E) với khả năng thông qua của các cung là Trong V có đỉnh nguồn tương ứng với đỉnh đích và các đỉnh trung gian khác tạo thành một mạng có hướng. Ở đây mỗi cặp đỉnh nguồn đích được gắn với một phương tiện . Giả thiết rằng phương tiện xuất phát từ đỉnh nguồn định trước, thì sẽ kết thúc tại đỉnh đích tương ứng, với Bài toán luồng đa phương tiện cực đại đồng thời là mỗi phương tiện có một yêu cầu vận chuyển gắn với nó. Nhiệm vụ của bài toán là tìm số lớn nhất sao cho có một luồng đa phương tiện chuyển đơn vị phương tiện qua luồng, +Cách biểu diễn đường đi, ta có bài toán theo mô hình quy hoạch tuyến tính như sau: (P) Để giải (P) ta xây dựng mô hình tuyến tính đối ngẫu với (P), gọi là (D), như sau: gắn cho một hàm độ dài , với mỗi phương tiện , gán một biến Định nghĩa: (D) Định nghĩa (còn gọi là ) là độ dài ngắn nhất trong các đường thuộc tính theo Đặt Bài toán đối ngẫu (D) tương đương với tìm hàm sao cho hàm đạt cực tiểu. Đặt Thuật toán: Thuật toán được thực hiện qua một số giai đoạn, mỗi giai đoạn gồm vòng lặp ( là số phương tiện). Ở vòng lặp thứ của giai đoạn ta chuyển đơn vị phương tiện thứ qua luồng. Việc vận chuyển này được thực hiện trong một số bước. Gọi là hàm độ dài ở đầu bước thứ , gọi là đường ngắn nhất giữa và lúc này, tức là có độ dài là . Trong bước này ta vận chuyển đơn vị phương tiện thứ dọc theo . Trong đó là khả năng thông qua nhỏ nhất trên , là lượng phương tiện thứ còn lại cần chuyển qua (số đơn vị cần chuyển qua trong bước này). Sau đó ta đặt và Tiếp theo ta có Vòng lặp thứ của giai đoạn kết thúc sau bước, khi mà Giai đoạn kết thúc, khi vòng lặp thứ của giai đoạn kết thúc. Hàm độ dài được tính như sau: - Hàm độ dài ban đầu: - Hàm độ dài ở đầu bước lặp đầu tiên của mỗi giai đoạn bằng hàm độ dài ở cuối giai đoạn trước: . - Hàm độ dài ở đầu mỗi vòng lặp tiếp theo có giá trị bằng hàm độ dài ở cuối vòng lặp trước: . Ta có Ký hiệu: là giá trị các hàm ở cuối mỗi giai đoạn. Từ quan hệ trên suy ra Thuật toán dừng sau giai đoạn , khi mà