chương 1 trình bày mô hình tổng quát của bài toán tối ưu hóa, phân loại bài toán. Mô hình bài toán tối ưu đa mục tiêu và một số mô hình trong thực tế. Một số phương pháp đưa bài toán đa mục tiêu về bài toán một mục tiêu. Các kiến thức được tham khảo trong các tài liệu [1][2][3].1Mô hình bài toán tối ưu 1 tiêu [1][2] Trong thực tế, chúng ta thường gặp các bài toán cần xác định một giá trị nào đó đạt cực đại hoặc cực tiếu trong đó các biến phụ thuộc vào một số các ràng buộc nào đó.
Các bài toán này thường xuất hiện trong các lĩnh vực kinh tế thương mại, lý thuyết hệ thống, công nghệ thông tin. Các bài toán đó thường được gọi là các bài toán tối ưu. Sau đây chúng ta sẽ nghiên cứu mô hình tổng quát của bài toán này.1 Mô hình tổng quát Ta xét biến số X = ( x1 , x2 ,., xn ) và một hàm f = f ( X ) là ánh xạ từ không gian n chiều vào không gian 1 chiều. Bài toán đặt ra là tìm giá trị X* để sao cho f ( X * ) → max(min) (1.1) Trong đó X* cần thỏa mãn các điều kiện g i ( X ) = bi , i J1 (1.4) Khi đó bài toán được gọi là bài toán tối ưu, trong đó + Hàm f ( X ) được gọi là hàm mục tiêu của bài toán + Các điều kiện (1.2) được gọi là ràng buộc đẳng thức, điều kiện (1.3) được gọi là ràng buộc bất đẳng thức.4) được gọi là ràng buộc về dấu., xn ) thỏa mãn hệ ràng buộc (1.4) được gọi là một phương án của bài toán.
Tập các vector X thỏa mãn hệ ràng buộc lập nên một miền D được gọi là miền phương án + Phương án X * D làm cho hàm mục tiêu f ( X ) đạt max (min) được gọi là phương án tối ưu. Một số tính chất của bài toán tối ưu: + Bài toán max luôn chuyển về bài toán min bằng cách đổi dấu hàm mục tiêu + Dạng ràng buộc bất đẳng thức luôn chuyển về dạng đẳng thức bằng cách bổ sung thêm các biến phụ. + Một biến không ràng buộc dấu được thay thế bằng 2 biến có ràng buộc dấu 1.2 Phân loại bài toán tối ưu Xuất phát từ mô hình tổng quát, tùy thuộc vào dạng của hàm mục tiêu, dạng các ràng buộc hoặc tính chất nghiệm của từng bài toán, người ta thường phân loại lớp các bài toán tối ưu như sau: • Qui hoạch tuyến tính: là những bài toán mà hàm mục tiêu f ( X ) và tất cả các hàm ràng buộc gi ( X ), g j ( X ), gk ( X ) là tuyến tính. • Qui hoạch phi tuyến: là những bài toán một trong hàm mục tiêu f ( X ) hoặc các hàm ràng buộc gi ( X ) , g j ( X ) , gk ( X ) là phi tuyến.
• Qui hoạch lồi: Là các bài toán qui hoạch mà các hàm mục tiêu f ( X ) là lồi trên tập các ràng buộc D lồi. • Qui hoạch lõm: Là các bài toán qui hoạch mà các hàm mục tiêu f ( X ) là lõm trên tập các ràng buộc D hoặc tập D là tập lõm. • Qui hoạch rời rạc: Bài toán tối ưu được gọi là qui hoạch rời rạc nếu miền ràng buộc D là tập hợp rời rạc. Trong trường hợp riêng khi các biến chỉ nhận giá trị nguyên thì ta có quy hoạch nguyên.
10 Để nghiên cứu việc tìm nghiệm tối ưu của bài toán quy hoạch tuyến tính, đã có rất nhiều thuật toán được đề xuất như thuật toán đơn hình nổi tiếng của tác giả Danzic, thuật toán đơn hình cải biên, thuật toán phân phối. Các thuật toán này đã được phát triển thành các phần mềm giải trực tiếp trên công cụ máy tinh. Đối với các bài toán tối ưu hóa phi tuyến, dựa trên cơ sở toán học cùng với một số điều kiện về tính trơn của hàm mục tiêu và tính lồi của miền phương án cũng đã có nhiều thuật toán đã được đề xuất như: Thuật toán gradient, thuật toán newton, thuật toán Powell, thuật toán Neldel_Mead, Thuật toán Frank_wolfe, Thuật toán Carroll, Thuật toán Fiacco và Cormick, Thuật toán Pietrzykowki. Có thể thấy rằng mỗi thuật toán sẽ có những ưu điểm và nhược điểm riêng.
Tốc độ hội tụ tùy thuộc vào dáng điệu của hàm mục tiêu. Ngoài ra trong tất cả các thuật toán đã trình bày ở trên, chúng ta đều thấy rằng hàm f(X) phải tồn tại đạo hàm và hiển nhiên chúng ta phải xác định được gradient của f(X) tại mỗi bước lặp. Chính vì vậy, người ta thường gọi các thuật toán trên là các thuật toán sử dụng đạo hàm. Tuy nhiên trong thực tế chính điều đó sẽ hạn chế lớp các bài toán trong ứng dụng và đặc biệt là số liệu trong thực tế chủ yếu là các số liệu thực nghiệm tức là không xác định hàm số dạng tường minh.
Vì vậy hiện nay người ta thường phát triển các thuật toán trong đó không cần sử dụng đạo hàm của hàm mục tiêu. Một trong những hướng đó là sử dụng kỹ thuật tính toán mềm để giải quyết bài toán tối ưu phi tuyến. Một số modun giải bài toán tối ưu trên môi trường Matlab Dạng 1 : Bài toán quy hoạch tuyến tính Bài toán Quy hoạch tuyến tính có dạng tổng quát: Hàm mục tiêu: f = C T X → min Hệ ràng buộc: AX b; Aeq X = beq ; ul X ub ., cn ) ; ul = ( ul1 ,., uln ) ; ub = ( ub1 ,., bp ) ; beq = ( beq1 ,. n p n q Khi đó, để tìm nghiệm tối ưu của bài toán, ta sử dụng thủ tục X , fval , exitflag , output = linprog (C , A, b, Aeq, beq, lb, ub ) X , fval , exitflag , output = int prog (C , A, b, Aeq, beq ) Trong đó: Lệnh linprog để lấy các nghiệm không âm Lệnh intprog để lấy các nghiệm nguyên có giá trị 1 hoặc 0.
Trong dấu là các đại lượng cần tính: X-giá trị tối ưu của nghiệm; fval- giá trị min của hàm mục tiêu; Exitflag – số nguyên thông báo kết thúc tính toán. Các kết quả tính khi exitflag=1, được coi là thành công tốt đẹp, nghĩa là hàm số hội tụ về một nghiệm. Các kết quả tính tương ứng exitflag 0 được coi là không thành công với các giải thích tương ứng Output- cho các thông tin về phép tính đã thực hiện. Dạng 2 : Bài toán tối ưu phi tuyến Bài toán tối ưu phi tuyến có dạng tổng quát: Hàm mục tiêu: f ( X ) → Min Hệ ràng buộc tuyến tính: AX b; Aeq X = beq ; ul X ub.
Hệ ràng buộc phi tuyến: C ( X ) ; Ceq ( X ) = . Đặt: F ( X ) = ( f ( X ), f ( X ) ) ; G ( X ) = (C ( X ), Ceq ( X ) ) Khi đó, để tìm nghiệm tối ưu của bài toán, ta sử dụng thủ tục X , fval , exitflag, output = f min con (@ F , X 0, A, b, Aeq, beq, lb, ub,@ G ) 12 Trong đó: Lệnh fmincon để để tìm min của hàm f X0 là giá trị xuất phát ban đàu của X trong phương pháp lặp Trong dấu là các đại lượng cần tính: X-giá trị tối ưu của nghiệm; fval- giá trị min của hàm mục tiêu; Exitflag – số nguyên thông báo kết thúc tính toán. Các kết quả tính khi exitflag>0, được coi là thành công. Các kết quả tính tương ứng exitflag 0 được coi là không thành công với các giải thích tương ứng Output- cho các thông tin về phép tính đã thực hiện.
Chú ý: các hàm F(X) và G(X) được mô tả là các function tương ứng phải được xây dựng do người sử dụng bằng ngôn ngữ matlab.2 Mô hình bài toán tối ưu đa mục tiêu [3] Trong các bài toán kinh tế, kỹ thuật, khoa học công nghệ,. nảy sinh từ thực tế, chúng ta phải xem xét tối ưu hóa đồng thời nhiều mục tiêu. Việc làm tốt hơn mục tiêu này thường dẫn tới việc làm xấu đi một số mục tiêu khác (nghĩa là không có lời giải nào tối ưu theo mọi mục tiêu). Như vậy, chúng ta cần phải tối ưu hóa (cực đại hóa hoặc cực tiểu hóa tùy theo tình huống cụ thể) không phải là chỉ một mục tiêu nào đó, mà là đồng thời tất cả các mục tiêu đã đặt ra thường là không tương thích với nhau.
Ta xét biến số X = ( x1 , x2 ,., xn ) và các hàm F1 = F1 ( X ); F2 = F2 ( X );.; Fk = Fk ( X ) là các ánh xạ từ không gian n chiều vào không gian 1 chiều. Bài toán đặt ra là tìm giá trị X* để sao cho Fi ( X ) → Max; i = 1.5) Trong đó X* cần thỏa mãn các điều kiện G j ( X ) bj , j J 2 (1.7) 13 Khi đó bài toán được gọi là bài toán tối ưu đa mục tiêu, trong đó + Các hàm Fi ( X ) , i=1.k được gọi là các hàm mục tiêu của bài toán + Một vecto X = ( x1 , x2 ,., xn ) thỏa mãn hệ ràng buộc (1.7) được gọi là một phương án của bài toán. Tập các vector X thỏa mãn hệ ràng buộc lập nên một miền D được gọi là miền phương án. + Phương án X * D làm cho tất cả các hàm mục tiêu đạt Max được gọi là phương án tối ưu của bài toán đa mục tiêu.
Nhận xét: + Khác với bài toán tối ưu 1 mục tiêu, bài toán tối ưu đa mục tiêu khó có thể tồn tại nghiệm tối ưu theo đúng nghĩa tức là không thể tìm được X* để sao cho tất cả các hàm mục tiêu đạt max do đó nghiệm chỉ có thể tối ưu theo một nghĩa tương đối nào đó. + Dễ dàng thấy rằng chúng ta không thể áp dụng các phương pháp tối ưu của bài toán một mục tiêu cho bài toán đa mục tiêu vì tính chất phức tạp của bài toán đa mục tiêu. + Mô hình bài toán đa mục tiêu là mô hình xuất hiện phổ biến trong tất cả các lĩnh vực do nhu cầu thực tế.3 Một số mô hình tối ưu đa mục tiêu trong thực tế [3] Mô hình 1: Một công ty dự kiến sản xuất m loại hàng hóa A1,A2,…,Am. Vật tư dùng để sản xuất các loại hàng hóa này là V1, V2 ,…, Vn.