tailieunhanh - QUY HOẠCH RỜI RẠC - CHƯƠNG 5

THUẬT TOÁN GOMORY THỨ BA Chương này trình bày thuật toán Gomory thứ ba nhằm xây dựng các lát cắt đảm bảo tất cả các Bảng đơn hình ở mỗi bước đều có tất cả các phần tử là nguyên 1. ẢNH HƯỞNG CỦA SAI SỐ LÀM TRÒN VÀ TƯ TƯỞNG CỦA THUẬT TOÁN GOMORY THỨ BA . Ảnh hưởng của sai số làm tròn có thể dẫn đến lời giải sai khi dùng phương pháp đơn hình giải bài toán quy hoạch tuyến tính. Khi giải bài toán quy hoạch tuyến tính nguyên ảnh hưởng sai số làm tròn tăng. | Bùi Thế Tâm Quy hoạch rời rạc Chương 5 THUẬT TOÁN GOMORY THỨ BA Chương này trình bày thuật toán Gomory thứ ba nhằm xây dựng các lát cắt đảm bảo tất cả các Bảng đơn hình ở mỗi bước đều có tất cả các phần tử là nguyên 1. ẢNH HƯỞNG CỦA SAI SỐ LÀM TRÒN VÀ TƯ TƯỞNG CỦA THUẬT TOÁN GOMORY THỨ BA . Ảnh hưởng của sai số làm tròn có thể dẫn đến lời giải sai khi dùng phương pháp đơn hình giải bài toán quy hoạch tuyến tính. Khi giải bài toán quy hoạch tuyến tính nguyên ảnh hưởng sai số làm tròn tăng mạnh do các nguyên nhân sau - Tăng khối lượng tính toán vì dùng nhiều lần l - phương pháp. - Khả năng mắc sai khi xử lý các số kiểu phần thập phân 0 999999 1 000000 - Khả năng nhận lời giải không đúng vì số nguyên có thể nhận là không nguyên. Để tránh sai số làm tròn Gomory đưa ra thuật toán thứ ba để giải bài toán quy hoạch tuyến tính nguyên toàn phần max X0 ì 1 1 b i 1 2 . m 2 j 1 Xj 0 j 1 2 . n 3 Xj - nguyên j 1 2 . n 4 . Tư tưởng của thuật toán Gomory thứ ba Giả sử bài toán L C - L0 C viết ở dạng bảng T0 l - chuẩn phần tử khác không đầu tiên ở mỗi cột là số dương . Dùng l - phương pháp ta nhận được dãy hữu hạn các bảng l - chuẩn T0 T1 . Ts mà cái cuối cùng là chấp nhận được. Giả sử bảng xuất phát T0 là nguyên hoàn toàn tất cả các phần tử là số nguyên . Các bảng tiếp theo có thể không nguyên là do ngoài các phép toán - khi chuyển từ Tv sang Tv 1 ta còn dùng phép tính chia trên phần tử quay. Nếu phần tử quay trên tất cả các bước là -1 thì các bảng T1 T2 . vẫn là nguyên khi T0 - nguyên cuối cùng phương án tối ưu Xs của bài toán Ls C ứng với Ts cũng là nguyên. Vậy Xs là phương án tối ưu của bài toán quy hoạch tuyến tính nguyên gốc LN C . Vì vậy ta sẽ cải tiến định nghĩa lát cắt đúng sao cho nếu dòng tương ứng với nó chọn làm dòng quay thì phần tử quay bằng -1 . Chính xác hơn bài toán tìm lát cắt đúng nguyên được phát biểu như sau có bài toán L C các điều kiện của nó viết dưới dạng bảng nguyên không chấp nhận được l - chuẩn T Ital ieQn jeN0 vì vậy l - giả phương án .