THUẬT TOÁN GOMORY THỨ HAI Chương này trình bày hai thuật toán: thuật toán Gomory thứ hai dùng để giải bài toán quy hoạch tuyến tính nguyên bộ phận, thuật toán Dalton - Llewellyn dùng để giải bài toán quy hoạch tuyến tính với các biến nhận giá trị rời rạc. | Bùi Thế Tâm Quy hoạch rời rạc Chương 4 THUẬT TOÁN GOMORY THỨ HAI Chương này trình bày hai thuật toán thuật toán Gomory thứ hai dùng để giải bài toán quy hoạch tuyến tính nguyên bộ phận thuật toán Dalton - Llewellyn dùng để giải bài toán quy hoạch tuyến tính với các biến nhận giá trị rời rạc. 1. LƯỢC ĐỒ LOGIC CHUNG CỦA THUẬT TOÁN Xét bài toán quy hoạch rời rạc Max X0 CjXj 1 i 1 j ij Xj bi i 1 . m 2 j 1 Xj 0 j 1 . n 3 Xj e Dj j 1 . n n1 n 4 Bài toán này kí hiệu là LDC LoD C Ld là miền chấp nhận được của bài toán LDC Dj là các tập rời rạc. Điều kiện rời rạc 4 có thể có các dạng khác nhau trong các trường hợp cụ thể. Ta giả sử rằng 1 Hàm mục tiêu x0 bị chặn trên trên miền 2 - 3 2 Nếu tập phương án tối ưu của bài toán 1 - 3 khác rỗng thì nó phải bị chặn Lược đồ logic của thuật toán như sau Bước lặp ban đầu. Giải l - bài toán L C L0 C xác định bởi 1 - 3 . Nếu nó không giải được thì bài toán L0 C cũng không giải được. Nếu bài toán L0 C giải được và phương án X L0 C thoả mãn điều kiện rời rạc 4 thì nó đồng thời là phương án tối ưu của bài toán LD C . Nếu X L0 C không thoả mãn điều kiện rời rạc thì chuyển sang bước lặp thứ r 0 Bước lặp thứ r r 0 . Giả sử X Lr C không thoả mãn điều kiện rời rạc ta biểu diễn hàm mục tiêu x0 CX và x1 x2 . . xn qua các biến phi cơ sở Xj j e Nr xi x X xỊj -xj i 0 1 n jeNr và nhận được bảng đơn hình Tr I xij Chọn k là dòng có chỉ số nhỏ nhất ứng với thành phần không thoả mãn điều kiện rời rạc là chấp nhận được và là l - chuẩn. k min i i e 1 . n Xi0 Di Bùi Thế Tâm Quy hoạch rời rạc và theo một qui tắc nào đó tùy từng thuật toán ta xây dựng lát cắt đúng Xn r 1 Yo s Yj -xj 5 jeNr Xn r 1 0 6 Viết dòng 5 vào cuối bảng đơn hình Tr ta được bảng mới là không chấp nhận được chỉ đối với dòng cuối cùng vừa thêm vào và là l - chuẩn. Sau khi đưa xn r 1 ra khỏi cơ sở thì dòng tương ứng sẽ bị xoá nếu đưa vào cơ sở xl l n 1 thì dòng tương ứng không phục hồi. Nếu nhận được bảng đơn hình ứng với bài toán qui hoạch tuyến tính không giải được thì bài toán
