TAILIEUCHUNG - Ứng dụng thuật toán nhánh cận giải bài toán quy hoạch tích Affine với các ràng buộc tuyến tính
Quy hoạch tích affine là một trong những bài toán quan trọng của tối ưu toàn cục. Một phương pháp khá hữu hiệu để giải bài toán này là phương pháp nhánh cận, ở đó bài toán gốc được chia thành các bài toán nhỏ dễ giải hơn. | Trần Đình Hùng Tạp chí KHOA HỌC & CÔNG NGHỆ 63(1): 28 - 30 ỨNG DỤNG THUẬT TOÁN NHÁNH CẬN GIẢI BÀI TOÁN QUY HOẠCH TÍCH AFFINE VỚI CÁC RÀNG BUỘC TUYẾN TÍNH Trần Đình Hùng Trường Đại học Sư phạm - ĐH Thái Nguyên TÓM TẮT Quy hoạch tích affine là một trong những bài toán quan trọng của tối ưu toàn cục. Một phương pháp khá hữu hiệu để giải bài toán này là phương pháp nhánh cận, ở đó bài toán gốc được chia thành các bài toán nhỏ dễ giải hơn. Trong [4] Lê Dũng Mưu và Bùi Thế Tâm đã phát biểu và đưa ra phương pháp giải bài toán quy hoạch tích hai hàm phân thức affine với các ràng buộc tuyến tính: min{ f ( x) a1 x b1 a2 x b2 c1 x d1 c2 x d 2 x D} . Bài toán quy hoạch tích hai hàm affine là một trường hợp riêng của bài toán này, trong đó khó khăn nằm ở chỗ, nghiệm tối ưu địa phương không nhất thiết là nghiệm tối ưu toàn cục. Để giải bài toán, ta chuyển về một dạng quy hoạch lồi-lõm và áp dụng thuật toán nhánh cận trong [2], đặc điểm quan trọng của thuật toán này là có sử dụng các thông tin của các bước lặp trước, không cần vét kiệt, nhưng vẫn bảo đảm sự hội tụ. Mục đích của bài báo này là nghiên cứu thuật toán nhánh cận để giải bài toán quy hoạch tích hai hàm affine với các ràng buộc tuyến tính, từ đó mở rộng cho trường hợp tích nhiều hàm affine. Từ khoá: Thuật toán nhánh cận, tối ưu toàn cục, quy hoạch lồi-lõm, quy hoạch tích hai hàm phân thức affine. * f ( x, y) được gọi là hàm lồi-lõm nếu nó lồi theo BÀI TOÁN QUY HOẠCH TÍCH HAI HÀM AFFINE VỚI CÁC RÀNG BUỘC TUYẾN TÍNH ( Xét bài toán ( P ) : Thuật toán nhánh cận min{f ( x) f1 ( x) f 2 ( x) : x D}, trong đó D là một đa diện xác định bởi D {x n : Ax b, x 0}, fi ( x) (i 1, 2) là các hàm affine trên n , fi ( x) ciT x bi . Để giải bài toán này, ta chuyển về một quy hoạch lồi-lõm như sau: Đặt y f 2 ( x) , khi đó bài toán được đưa về dạng min{f ( x, y ) f1 ( x) y : x D, f 2 (x)=y} (Q) Đây là bài toán quy hoạch lồi-lõm do hàm f ( x, y) là hàm lồi-lõm trên tập lồi D x khi cố
đang nạp các trang xem trước
