intTypePromotion=1

Ứ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

Chia sẻ: Thi Thi | Ngày: | Loại File: PDF | Số trang:3

0
36
lượt xem
1
download

Ứ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

Mô tả tài liệu
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

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.

Chủ đề:
Lưu

Nội dung Text: Ứ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<br /> <br /> Tạp chí KHOA HỌC & CÔNG NGHỆ<br /> <br /> 63(1): 28 - 30<br /> <br /> ỨNG DỤNG THUẬT TOÁN NHÁNH CẬN GIẢI BÀI TOÁN<br /> QUY HOẠCH TÍCH AFFINE VỚI CÁC RÀNG BUỘC TUYẾN TÍNH<br /> Trần Đình Hùng<br /> Trường Đại học Sư phạm - ĐH Thái Nguyên<br /> <br /> TÓM TẮT<br /> 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<br /> 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<br /> thành các bài toán nhỏ dễ giải hơn.<br /> 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<br /> hoạch tích hai hàm phân thức affine với các ràng buộc tuyến tính:<br /> <br /> min{ f ( x) <br /> <br /> a1 x  b1 a2 x  b2<br /> c1 x  d1 c2 x  d 2<br /> <br /> x  D} .<br /> <br /> 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ó<br /> 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<br /> 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<br /> đ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<br /> vét kiệt, nhưng vẫn bảo đảm sự hội tụ.<br /> 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<br /> 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.<br /> 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<br /> thức affine.<br /> *<br /> <br /> f ( x, y) được gọi là hàm lồi-lõm nếu nó lồi theo<br /> <br /> BÀI TOÁN QUY HOẠCH TÍCH HAI HÀM<br /> AFFINE VỚI CÁC RÀNG BUỘC TUYẾN<br /> TÍNH<br /> <br /> (<br /> <br /> Xét bài toán ( P ) :<br /> <br /> Thuật toán nhánh cận<br /> <br /> min{f ( x)  f1 ( x) f 2 ( x) : x  D},<br /> trong đó D là một đa diện xác định bởi<br /> <br /> D  {x <br /> <br /> n<br /> <br /> : Ax  b, x  0}, fi ( x) (i  1, 2)<br /> <br /> là các hàm affine trên<br /> <br /> n<br /> <br /> , fi ( x)  ciT x  bi .<br /> <br /> Để giải bài toán này, ta chuyển về một<br /> quy hoạch lồi-lõm như sau:<br /> Đặt y  f 2 ( x) , khi đó bài toán được đưa<br /> về dạng<br /> <br /> min{f ( x, y )  f1 ( x) y : x  D, f 2 (x)=y} (Q)<br /> Đây là bài toán quy hoạch lồi-lõm do<br /> hàm f ( x, y) là hàm lồi-lõm trên tập lồi D<br /> <br /> x khi cố định y và lõm theo y khi cố định x ).<br /> KẾT QUẢ CHÍNH<br /> Áp dụng thuật toán nhánh cận tổng quát trong [5]<br /> và đối với trường hợp bài toán quy hoạch lồi-lõm<br /> trong [2], [3], ý tưởng là chia nhỏ miền ràng buộc<br /> lõm y của bài toán (chia nhánh), trong quá trình đó<br /> tính cận trên và cận dưới của f ( x, y ) trên các<br /> miền ràng buộc lõm (tính cận), từ đó thu hẹp dần<br /> khoảng chứa nghiệm của bài toán.<br /> Nhận xét<br /> <br /> fi ( x) (i  1,2) là các hàm affine, với miền ràng<br /> buộc D gồm các ràng buộc tuyến tính, do đó việc<br /> tính cực tiểu hay cực đại của chúng thực chất là<br /> bài toán quy hoạch tuyến tính đã quen thuộc.<br /> Đặt z0  min f 2 ( x) , Z 0  max f 2 ( x) , khi đó<br /> xD<br /> xD<br /> miền ràng buộc của biến lõm y chỉ là một đoạn<br /> <br /> *<br /> <br /> Tel: 0912347199<br /> 28<br /> Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên<br /> <br /> http://www.Lrc-tnu.edu.vn<br /> <br /> Trần Đình Hùng<br /> <br /> Tạp chí KHOA HỌC & CÔNG NGHỆ<br /> <br /> thẳng, do đó ở trường hợp này phép chia nhánh<br /> được thực hiện trong không gian 1 chiều.<br /> Bổ đề.<br /> <br /> 63(1): 28 - 30<br /> <br />  ( I k1 )<br /> <br /> Tính<br /> <br /> với<br /> <br /> miền<br /> <br /> ràng<br /> <br /> buộc<br /> <br /> {x  D, f2 ( x)  I } ,  ( I ) với miền ràng buộc<br /> 1<br /> k<br /> <br /> 2<br /> k<br /> <br /> Giả sử I = [ a , b ],<br /> <br /> {x  D, f 2 ( x)  I k2} .<br /> <br /> đặt  ( I )  min{ f1 ( x) y, x  D, f 2 ( x)  y  I } ,<br /> <br /> Giả sử  ( I k1 )  f1 ( x1k ) z1k ,  ( I k2 )  f1 ( xk2 ) zk2 , tính<br /> <br />  ( I ) = min{min{ f1 ( x)k : x  D, f2 ( x)  I} ,<br /> k  a, b} , khi đó  ( I )   ( I ) .<br /> <br /> cận trên<br /> <br /> Chứng minh<br /> <br /> Đặt Rk  (k \ I k ) {I k , I k } ,<br /> <br />  k 1  min{ k , f ( x1k ), f ( xk2 )}  f ( x k 1 ) .<br /> 1<br /> <br /> Thật vậy, giả sử x0 thuộc miền ràng buộc, đặt<br /> y0  f2 ( x0 ) , khi đó do y  [a, b] , nên<br /> f1 ( x0 ) y  min{f1 ( x0 )a, f1 ( x0 )b} .<br /> Vậy  ( I )   ( I) .<br /> <br /> 2<br /> <br />  k 1  {I  Rk :  (I )  k 1} , chọn I k 1   k 1<br /> sao<br /> <br /> cho<br /> <br />  ( I k 1 )  min{ (I ) : I   k 1} ;<br /> <br />  k 1   ( I k 1 ), k  k  1 .<br /> <br /> Thuật toán nhánh cận<br /> Tính z0  min f 2 ( x) , Z 0  max f 2 ( x) .<br /> <br /> Sự hội tụ của thuật toán<br /> <br /> Đặt I 0  [ z0 , Z0 ] , tính các đại lượng<br /> <br /> Định lý sau đây chỉ ra rằng, nếu thuật toán không<br /> dừng thì k và k sẽ tiến dần tới nghiệm tối ưu.<br /> <br /> xD<br /> <br /> xD<br /> <br />  ( z0 )  min{ f1 ( x) z0 : x  D}  f1 (u ) z0 ,<br />  (Z0 )  min{ f1 ( x)Z0 : x  D}  f1 (v0 )Z0 .<br /> 0<br /> <br /> Thiết lập cận trên và cận dưới ban đầu:<br /> <br /> Định lý. Nếu thuật toán không dừng thì<br /> k<br /> f * , k<br /> f * và mỗi điểm tụ của dãy<br /> k<br /> x là nghiệm của bài toán.<br /> Chứng minh.<br /> <br /> 0   (I0 )  min{ ( z0 ),  (Z0 )},<br /> <br /> Giả sử thuật toán không dừng, khi đó tồn tại dãy<br /> giảm các đoạn con của I 0 , ký hiệu là {I k } . Khi<br /> <br />  0  min{ f (u 0 ), f (v0 )}  f ( x0 ),<br /> 0 : {I 0 }.<br /> <br /> đó, với mọi k , I k 1  I k  I k1  I k2 , hơn nữa từ<br /> <br /> Bước lặp k :<br /> <br /> đó I k 1  I k1 hoặc I k 1  I k2 .<br /> <br /> Tại thời điểm bắt đầu của bước lặp k<br /> ( k  0,1,... ), ta có một họ  k các đoạn thẳng<br /> I  I0 sao cho D {I : I k } chứa ít nhất<br /> một lời giải tối ưu của (Q), cận dưới  k , cận trên<br />  k  f ( xk ) và đoạn I k k (nghi ngờ chứa<br /> nghiệm).<br /> Nếu  k  k thì x<br /> toán.<br /> <br /> cách phân chia các đoạn, suy ra I k1  I k2 = , do<br /> <br /> k<br /> <br /> là nghiệm tối ưu của bài<br /> <br /> Nếu  k  k thì ta tiến hành chia nhỏ I k<br /> <br /> I k  I k1  I k2 ,<br /> I k1  {y  I k : y  ( z Ik  f 2 ( x Ik )) / 2} ,<br /> I  {y  I k : y  ( z  f 2 ( x )) / 2} ,<br /> Ik<br /> <br /> 2<br /> k<br /> <br /> Ik<br /> <br /> trong đó  ( I k )  f1 ( x k ) z k .<br /> I<br /> <br /> I<br /> <br /> Nếu I k 1  I k1 , giả sử  k  f1 ( x k ) z k ,<br /> khi đó  k  f1 ( x k ) f 2 ( x k ).<br /> Đặt z 'k  f 2 ( xk ) , d k <br /> <br /> zk  z 'k<br /> , khi đó<br /> 2<br /> <br /> 0   k  k  f1 ( xk ) f 2 ( xk )  f1 ( xk ) z k <br />  f1 ( x k )( z 'k  zk ) .<br /> Nếu z 'k  zk , thì z 'k 1  dk , do đó<br /> <br /> 0   k  k  2 f1 ( x k )( z 'k  dk ) <br />  2 f1 ( x k )( z 'k  z 'k 1 ) .<br /> Nếu z 'k  zk , thì zk 1  dk , do đó<br /> <br /> 29<br /> Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên<br /> <br /> http://www.Lrc-tnu.edu.vn<br /> <br /> (1)<br /> <br /> Trần Đình Hùng<br /> <br /> Tạp chí KHOA HỌC & CÔNG NGHỆ<br /> <br /> [1] Trần Đình Hùng (2008), Quy hoạch lồi-lõm<br /> với ràng buộc tuyến tính, Luận văn thạc sĩ toán<br /> học, Viện Toán học Hà Nội.<br /> <br /> 0   k  k  2 f1 ( x k )( zk  d k ) <br />  2 f1 ( x k )( zk  zk 1 ) .<br /> (2)<br /> Do zk , z 'k cùng nằm trong đoạn đóng I 0 , nên<br /> chúng có điểm tụ. Khi đó từ (1) và (2) suy ra k –<br /> k <br /> 0 .<br /> k<br /> Lập luận tương tự trong trường hợp I k 1  I k2 . Do<br /> tính đơn điệu của  k và  k , suy ra  k<br /> <br /> k<br /> <br /> 63(1): 28 - 30<br /> <br /> f *,<br /> <br /> f *.<br /> <br /> Hơn nữa  k  f ( x k ) , do đó mỗi điểm tụ của dãy<br /> k<br /> <br /> x là nghiệm của bài toán.<br /> Chú ý<br /> Trong trường hợp bài toán tích các hàm affine,<br /> f  f1 f2 ... fn , ta đặt y  f 2 ... f n , dùng phương<br /> pháp quy nạp tính được y [y0 ,Y0 ] , khi đó áp<br /> dụng thuật toán nhánh cận tương tự như trên.<br /> Chương trình C++ giải bài toán được trình bày<br /> trong [1].<br /> <br /> [2] R.Horst, L.D.Muu, M.Nast, Branch and Bound<br /> Decomposition<br /> Approach<br /> for<br /> solving<br /> Quasiconvex-Concave Programs, Journal of<br /> Optimization Theory and Applications: Vol. 82,<br /> No. 2, August 1994.<br /> [3] Le Dung Muu, An algorithm for solving<br /> convex programs with an addition convex-concave<br /> constraint, Mathematical Programming 61 (1993),<br /> 75-87, North-Holland.<br /> [4] Le D. Muu and Bui T. Tam, Efficient<br /> Algorithms for Solving Certain Nonconvex<br /> Programs Dealing with the Product of Two Affine<br /> Fractional Functions, Journal of Global<br /> Optimization 6: 179-191, 1995.<br /> [5] Hoang Tuy, Convex analysis and Global<br /> Optimization, Kluwer (Springer) 1998.<br /> <br /> TÀI LIỆU THAM KHẢO<br /> <br /> SUMMARY<br /> BRANCH AND BOUND ALGORITHM APPROACH FOR SOLVING PRODUCT OF<br /> AFFINE FUNCTIONS PROGRAM WITH LINEAR CONSTRAINTS<br /> Tran Dinh Hung2<br /> College of Education – Thai Nguyen University<br /> Product of affine functions program is one of important problems in global optimization, it is a<br /> case of product of two affine fractional functions program that Le Dung Muu and Bui The Tam<br /> presented and showed solution in [4]. The difficulity of problem is that the local solution can’t be<br /> the global solution. Branch and bound algorithm is a efficient method to solve it, then original<br /> problem is separated into easier problems. In this paper, we presented product of two affine<br /> functions with linear constraints, showed brand and bound algorithm solving it and approached for<br /> product of affine functions.<br /> Keywords: Branch and bound algorithm, global optimization, convex-concave program, Product<br /> of Two Affine Fractional functions program.<br /> <br /> 2<br /> <br /> Tel: 0912347199<br /> 30<br /> Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên<br /> <br /> http://www.Lrc-tnu.edu.vn<br /> <br />
ADSENSE
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

 

Đồng bộ tài khoản
2=>2