CÁC MÔ HÌNH VÀ PHẦN MỀM TỐI ƯU - CHƯƠNG 3

BÀI TOÁN QUY HOẠCH PHI TUYẾN 1. PHƯƠNG PHÁP RST2ANU GIẢI BÀI TOÁN TỐI ƯU PHI TUYẾN TOÀN CỤC HỖN HỢP NGUYÊN 1.1. Đặt vấn đềDạng chính tắc của bài toán tối ưu một mục tiêu được biểu diễn như sau:Min (Max) f(X) , X = (x1, x2, …, xn)∈ Rn, với các điều kiện ràng buộc j = 1, 2, …, k, j = k+1, k+2, …, .m. (i) gj(X) ≤ 0, (ii) gj(X) = 0,Trong các bài toán thực tế có thể bổ sung thêm các ràng buộc (iii) ai ≤ xi ≤ bi, i = 1,...
Nội dung trích xuất từ tài liệu:
CÁC MÔ HÌNH VÀ PHẦN MỀM TỐI ƯU - CHƯƠNG 3Chương IIIBÀI TOÁN QUY HOẠCH PHI TUYẾN1. PHƯƠNG PHÁP RST2ANU GIẢI BÀI TOÁN TỐI ƯUPHI TUYẾN TOÀN CỤC HỖN HỢP NGUYÊN1.1. Đặt vấn đề Dạng chính tắc của bài toán tối ưu một mục tiêu được biểu diễn như sau: X = (x1, x2, …, xn)∈ Rn, với các điều kiện ràng buộc Min (Max) f(X) , (i) gj(X) ≤ 0, j = 1, 2, …, k, (ii) gj(X) = 0, j = k+1, k+2, …, .m. Trong các bài toán thực tế có thể bổ sung thêm các ràng buộc (iii) ai ≤ xi ≤ bi, i = 1, 2, …, n. Trong trường hợp hàm mục tiêu f(X) hay có ít nhất một trong các hàm ràng buộcgj(X), j = 1, 2, …, m, là hàm phi tuyến, chúng ta có bài toán tối ưu phi tuyến. Khi tất cảcác toạ độ xi đều bắt buộc nhận các giá trị nguyên, i = 1, 2, …, n, thì ta có bài toán tốiưu nguyên. Còn nếu chỉ có một số toạ độ (nhưng không phải tất cả các toạ độ) bắt buộcnhận giá trị nguyên thì ta có bài toán tối ưu hỗn hợp nguyên. Ký hiệu D là miền các phương án (miền ràng buộc) cho bởi các ràng buộc (i),(ii) và / hoặc (iii) thì bài toán tối ưu trên đây có thể viết gọn hơn như sau: f(X) → Min(Max) với X ∈ D. Lúc này, đối với bài toán cực tiểu hoá, X* ∈ D được gọi là phương án tối ưu toàncục nếu ∀ X∈D ta luôn có: f(X*) ≤ f(X). Trong trường hợp f(X*) ≤ f(X) chỉ đúng với∀X∈D trong một lân cận nào đó của X* thì X* được gọi là phương án tối ưu địaphương. Một cách tương tự, ta có thể định nghĩa khái niệm phương án tối ưu toàn cục /địa phương cho bài toán cực đại hoá. Nếu chúng ta chỉ quan tâm tới việc tìm kiếmphương án tối ưu toàn cục thì ta có bài toán tối ưu toàn cục. Các phương pháp giải bài toán tối ưu toàn cục phi tuyến đơn mục tiêu đượcphân ra thành hai lớp: phương pháp tất định và phương pháp ngẫu nhiên (deterministicand stochastic methods). Phương pháp tất định sử dụng các tính chất giải tích của hàmmục tiêu và các hàm ràng buộc. Một số dạng bài toán tối ưu toàn cục với những tínhchất giải tích nhất định của hàm mục tiêu và các hàm ràng buộc có thể giải được bằngcác phương pháp tất định thích hợp, chẳng hạn như phương pháp quy hoạch toànphương, quy hoạch tách, quy hoạch lồi, quy hoạch d.c… Trong các trường hợp đóphương án tối ưu toàn cục có thể tìm được sau một số hữu hạn bước tính toán với độchính xác chọn trước. Tuy nhiên, đối với nhiều lớp bài toán tối ưu toàn cục phương pháp tất định tỏ rakhông có hiệu quả. Trong khi đó, các phương pháp ngẫu nhiên như: phương pháp đakhởi tạo (multistart), mô phỏng tôi (simulated annealing), thuật giải di truyền (genetic 40algorithm)… có thể áp dụng để giải các bài toán tối ưu toàn cục dạng bất kỳ, không đòihỏi các tính chất đặc biệt của hàm mục tiêu hay các hàm ràng buộc. Các phương phápngẫu nhiên đặc biệt tỏ ra có hiệu quả đối với các bài toán tối ưu phi tuyến nguyên vàhỗn hợp nguyên. Tuy nhiên, các phương pháp này thường chỉ cho phương án “gần” tốiưu khá tốt sau một số hữu hạn bước mà không kiểm soát được độ chính xác của phươngán tìm được. Như vậy, hiện tại có nhiều phương pháp tối ưu toàn cục được đề xuất. Tuy nhiênchưa có một phương pháp nào tỏ ra hữu hiệu cho mọi bài toán tối ưu, đặc biệt là các bàitoán tối ưu với biến nguyên hay hỗn hợp nguyên. Hơn nữa, các phương pháp tối ưu cầnphải được lập trình để đóng gói thành các phần mềm thân thiện đối với người sử dụng.Đây là một đòi hỏi rất thực tế của các kĩ sư, các nhà khoa học, các doanh nghiệp trongnhiều lĩnh vực công nghiệp cũng như nông nghiệp. Trong bài báo này, chúng tôi trìnhbày một phần mềm tính toán khoa học (RST2ANU) có thể đáp ứng được phần nào cácđòi hỏi nêu trên đối với người sử dụng để giải các bài toán tối ưu phi tuyến toàn cục vớicác biến liên tục, nguyên hoặc hỗn hợp nguyên. Phần mềm này được xây dựng dựa trênphương pháp tìm kiếm ngẫu nhiên có kiểm soát (cùng tên gọi RST2ANU) do Mohan vàNguyễn Hải Thanh đề xuất (Xem “A controlled random search technique incorporatingthe simulated annealing concept for solving integer and mixed integer globaloptimization problems”, Computational Optimization and Applications, Vol. 14, pp.103-132, 1999). Đây là một phương pháp tối ưu đã được chạy kiểm thử trên hàng trămbài toán mẫu và nhiều bài toán thực tế với độ tin cậy rất cao và tốc độ tính toán chấpnhận được.1.2. Thuật giải tìm kiếm ngẫu nhiên có kiểm soát RST2ANU Thuật giải RST2ANU là thuật giải lặp, bao gồm hai pha, pha địa phương và phatoàn cục. Trong pha toàn cục, một số lượng thích hợp đủ lớn các phương án chấp nhậnđược được phát sinh ra một cách ngẫu nhiên và lưu trữ trong mảng có tên A. Đánh dấuhai điểm có giá trị hàm mục tiêu lớn nhất và nhỏ nhất tương ứng là M và L. Trong pha địa phương, các phương án được xử lý nhằm thu được giá trị ướclượng tốt hơn của hàm mục tiêu. Trong pha này, thuật giải xác định X* là điểm đượcnội suy bậc hai dựa ...