Ứ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.
Nội dung trích xuất từ tài liệu:
Ứ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 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ố định y và lõm theo y khi cố định x ). KẾT QUẢ CHÍNH Áp dụng thuật toán nhánh cận tổng quát trong [5] và đối với trường hợp bài toán quy hoạch lồi-lõm trong [2], [3], ý tưởng là chia nhỏ miền ràng buộc lõm y của bài toán (chia nhánh), trong quá trình đó tính cận trên và cận dưới của f ( x, y ) trên các miền ràng buộc lõm (tính cận), từ đó thu hẹp dần khoảng chứa nghiệm của bài toán. Nhận xét fi ( x) (i  1,2) là các hàm affine, với miền ràng buộc D gồm các ràng buộc tuyến tính, do đó việc tính cực tiểu hay cực đại của chúng thực chất là bài toán quy hoạch tuyến tính đã quen thuộc. Đặt z0  min f 2 ( x) , Z 0  max f 2 ( x) , khi đó xD xD miền ràng buộc của biến lõm y chỉ là một đoạn * Tel: 0912347199 28 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.Lrc-tnu.edu.vn Trần Đình Hùng Tạp chí KHOA HỌC & CÔNG NGHỆ thẳng, do đó ở trường hợp này phép chia nhánh được thực hiện trong không gian 1 chiều. Bổ đề. 63(1): 28 - 30  ( I k1 ) Tính với miền ràng buộc {x  D, f2 ( x)  I } ,  ( I ) với miền ràng buộc 1 k 2 k Giả sử I = [ a , b ], {x  D, f 2 ( x)  I k2} . đặt  ( I )  min{ f1 ( x) y, x  D, f 2 ( x)  y  I } , Giả sử  ( I k1 )  f1 ( x1k ) z1k ,  ( I k2 )  f1 ( xk2 ) zk2 , tính  ( I ) = min{min{ f1 ( x)k : x  D, f2 ( x)  I} , k  a, b} , khi đó  ( I )   ( I ) . cận trên Chứng minh Đặt Rk  (k I k ) {I k , I k } ,  k 1  min{ k , f ( x1k ), f ( xk2 )}  f ( x k 1 ) . 1 Thật vậy, giả sử x0 thuộc miền ràng buộc, đặt y0  f2 ( x0 ) , khi đó do y  [a, b] , nên f1 ( x0 ) y  min{f1 ( x0 )a, f1 ( x0 )b} . Vậy  ( I )   ( I) . 2  k 1  {I  Rk :  (I )  k 1} , chọn I k 1   k 1 sao cho  ( I k 1 )  min{ (I ) : I   k 1} ;  k 1   ( I k 1 ), k  k  1 . Thuật toán nhánh cận Tính z0  min f 2 ( x) , Z 0  max f 2 ( x) . Sự hội tụ của thuật toán Đặt I 0  [ z0 , Z0 ] , tính các đại lượng Định lý sau đây chỉ ra rằng, nếu thuật toán không dừng thì k và k sẽ tiến dần tới nghiệm tối ưu. xD xD  ( z0 )  min{ f1 ( x) z0 : x  D}  f1 (u ) z0 ,  (Z0 )  min{ f1 ( x)Z0 : x  D}  f1 (v0 )Z0 . 0 Thiết lập cận trên và cận dưới ban đầu: Định lý. Nếu thuật toán không dừng thì k f * , k f * và mỗi điểm tụ của dãy k x là nghiệm của bài toán. Chứng minh. 0   (I0 )  min{ ( z0 ),  (Z0 )}, Giả sử thuật toán không dừng, khi đó tồn tại dãy giảm các đoạn con của I 0 , ký hiệu là {I k } . Khi  0  min{ f (u 0 ), f (v0 )}  f ( x0 ), 0 : {I 0 }. đó, với mọi k , I k 1  I k  I k1  I k2 , hơn nữa từ Bước lặp k : đó I k 1  I k1 hoặc I k 1  I k2 . Tại thời điểm bắt đầu của bước lặp k ( k  0,1,... ), ta có một họ  k các đoạn thẳng I  I0 sao cho D {I : I k } chứa ít nhất một lời giải tối ưu của (Q), cận dưới  k , cận trên  k  f ( xk ) và đoạn I k k (nghi ngờ chứa nghiệm). Nếu  k  k thì x toán. cách phân chia các đ ...