zunia.vn

Tuyển sinh 2024 dành cho Gen-Z

zunia.vn

» Khoa Học Tự Nhiên

Phương pháp chuyển đổi giải bài toán tối ưu biến nguyên không lồi

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

Báo xấu

12
lượt xem 3
download

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

Bài viết Phương pháp chuyển đổi giải bài toán tối ưu biến nguyên không lồi trình bày phương pháp chuyển đổi cho hàm mũ âm; Phương pháp chuyển đổi cho hàm mũ dương; Tuyến tính hóa từng đoạn; Ứng dụng phương pháp chuyển đổi giải bài toán tối ưu.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Phương pháp chuyển đổi giải bài toán tối ưu biến nguyên không lồi

Tuyển tập Hội nghị Khoa học thường niên năm 2019. ISBN: 978-604-82-2981-8 PHƯƠNG PHÁP CHUYỂN ĐỔI GIẢI BÀI TOÁN TỐI ƯU BIẾN NGUYÊN KHÔNG LỒI Phạm Đức Đại1, Nguyễn Thị Thúy Hằng1 1 Trường Đại học Thủy lợi, email: daipd@tlu.edu.vn 1. GIỚI THIỆU chuyển các thành phần mũ không lồi thành các thành phần lồi kết hợp với phương pháp Bài toán tối ưu biến nguyên (MINLP) xấp xỉ từng đoạn (piece-wise linearization). được ứng dụng rộng rãi để giải các bài toán tối ưu hoạt động trong thực tế, như bài toán 2. PHƯƠNG PHÁP CHUYỂN ĐỔI tối ưu hoạt động đóng mở bơm; bài toán tối ưu hộp số; bài toán tối ưu đặt van trong mạng Hàm mũ được định nghĩa như sau: J I  m  z    c j  zi p ji cấp nước. Các bài toán tối ưu MINLP thường j 1 i 1 phi tuyến và không lồi (Non-convex) dẫn đến Với hàm dương c j  0 , hàm mũ lồi khi và nghiệm của bài toán này thường là cục bộ và có chất lượng thấp. Các phương pháp giải bài chỉ khi: toán tối ưu MINLP có thể sử dụng phương (i) pi  0, i  1,..., I pháp Branch and Bound [1], phương áp OA (ii) k : pi   pi  1, pi  0, i  1,..., I , i # k i#k (outer approximation) [1], phương pháp phân Với hàm âm (cj < 0) thì hàm mũ là lồi khi tích Benders (GBD). Các phương pháp trên và chỉ khi: cho nghiệm tin cậy (reliable) khi mà bài toán I MINLP là lồi. Tuy nhiên, hầu hết các bài  m  z   c zip ; c  0; pi  0, i  1,..., I i toán kỹ thuật là phi tuyến không lồi, việc tìm i 1 n được nghiệm thỏa mãn các rằng buộc của bài toán MINLP cũng là một bài toán khó. Rất p i 1 i 1 nhiều phương pháp đã quan tâm đến việc 2.1. Phương pháp chuyển đổi cho hàm chuyển bài toán không lồi MINLP thành bài mũ âm toán lồi. Trong bài báo này tác giả quan tâm đến dạng bài toán có các thành phần mũ Hàm mũ không lồi có thể được chuyển không lồi, có dạng như sau: thành hàm mũ lối với phương pháp chuyển min f  z  đổi như sau: zi  Z iQ hay Z i  z1/i Q . Chú ý rằng: i i s.t. Khi pi  0 thì Qi  0 ; pi  0 thì Qi  0 và pi  0 Az  a thì Qi  0 . Hơn nữa để thành phần sau khi Bz  b chuyển đổi là lồi thì ta cần điều kiện: gn  z   0 I  pQ i i 1 qm  z    m  z   0 i 1 Thành phần mới sẽ là: Trong đó f , g n , qm là các hàm phi tuyến I  m  z   c Z ip Q i i lồi, có đạo hàm;  m  z  là các hàm mũ i 1 (signomial functions) phi tuyến không lồi Điều kiện để hàm mới là lồi như sau: (non-convex). Mục tiêu của bài báo này là áp 0  Qi  1, pi  0 I   pQ i i 1 dụng các phương pháp chuyển đổi nhằm Qi  0, pi  0 i 1 570
Tuyển tập Hội nghị Khoa học thường niên năm 2019. ISBN: 978-604-82-2981-8 2.2. Phương pháp chuyển đổi cho hàm Thực hiện chuyển đổi: mũ dương  1 I y  Y10.25 y  Y2 3 ; các thành phần không lồi sẽ  m  z   c Z ip Q i i trở thành: i 1 Qi  1, pi  0  i  k 2y 2  2 y 0.5  11y  8 x  20   2 x 0.5Y10.5  0.1x1.5Y20.5  0  Qi  0, pi  0  i # k Theo định nghĩa ở trên, 2x 0.5Y10.5 có tổng Q  1, pi  0  i n các mũ  pi  1 , do đó đây là hàm lồi; tương 2.3. Tuyến tính hóa từng đoạn i 1 tự như vậy thành phần 0.1x1.5Y20.5 thỏa mãn Việc thực hiện chuyển đổi Zi  z1/i Q sẽ được i điều kiện k : pi   pi  1, pi  0, i  1,..., I , i # k tuyến tính hóa, để bài toán MINLP trở thành i#k bài toán phi tuyến lồi. Trong bài báo này, tác Bài toán trên còn cần hai điều kiện nữa để giả ứng dụng phương pháp tuyến tính hóa tuyến tính hóa các thành phần sau: từng đoạn (piecewise linear functions) để xấp Y1  y 4 và Y2  y 3 xỉ Zi bởi Z như sau: M Y 1  1w1  (7) 4 w2 và Y 2  1w1  (7) 3 w2 và Z   Z m wm với wm  0 m 1 y  1w1  7 w2 ; w1  w2  1 . Bài toán tối ưu không lồi Và do đó: giờ trở thành bài toán lồi như sau: M M min y  3x z   zm wm và  wm  1 m 1 m 1 s.t. y  5 x  36 2.4. Thuật giải bài toán không lồi MINLP  y  0.25 x  1 Bước 1. Chuyển đổi bài toán MINLP 2y 2  2 y 0.5  11 y  8 x  20   2 x 0.5 Y 1  0.1x1.5 Y 2 0.5 0.5 0 không lồi về bài toán lồi; số điểm tuyến tính Y 1  1w1  (7) w2 4 hóa NTTH  2 ; ObjMINLP   Y 2  1w1  (7) 3 w2 Bước 2: Tuyến tính hóa sử dụng số điểm y  1w1  7 w2 NTTH . w1  w2  1 Bước 3: Giải bài toán MINLP lồi được 1  x  7,1  y  7 hàm mục tiêu ObjMINLP k  . 0  w1 , 0  w2 Nếu ObjMINLP k   ObjMINLP  k 1 đến bước 4, ngược Tác giả sử dụng phần mền GAMs để giải lại dừng và kết thúc. bài toán trên ta được nghiệm là x  6.6, y  3 . Bước 4: Tăng số điểm tuyến tính hóa Tiếp đến ta thêm số điểm tuyến tính hóa từ 2 NTTH  NTTH  1 quay lại bước 1 lên 3, điểm mới là y  3 . Bài toán tối ưu mới 3. ỨNG DỤNG PHƯƠNG PHÁP CHUYỂN sẽ trở thành: ĐỔI GIẢI BÀI TOÁN TỐI ƯU min y  3 x s.t. min y  3 x y  5 x  36 s.t.  y  0.25 x  1 y  5 x  36 2y  2 y 0.5  11 y  8 x  20   2 x 0.5 Y 1  0.1x1.5 Y 2 0.5 0.5 2 0  y  0.25 x  1 2y  11 y  8 x  20   2 x y  0.1x y Y 1  1w1  (7) w2   3 w3 4 4 2  2y 0.5 0.5 2 1.5 1.5 0 Y 2  1w1  (7) 3 w2   3 w3 3 1  x  7,1  y  7 Dựa vào các định lý đã nêu trên, có thể y  1w1  7 w2  3w3 thấy rằng, bài toán có các thành phần phi w1  w2  w3  1 tuyến không lồi sau: 1  x  7,1  y  7 2x 0.5 y 2 và 0.1x1.5 y1.5 0  w1 , 0  w2 , 0  w3 571
Tuyển tập Hội nghị Khoa học thường niên năm 2019. ISBN: 978-604-82-2981-8 Sau khi giải bài toán này, thu được nghiệm Giải bài toán, thu được kết quả là như sau x  6.2, y  5 . Tiếp tục, bài toán được x  6, y  6 , với giá trị của hàm mục tiêu là -12, thêm số điểm tuyến tính hóa: đây là giá trị tối ưu toàn cục. min y  3x s.t. 4. KẾT LUẬN y  5 x  36 Nhóm tác giả đã ứng dụng phương pháp  y  0.25 x  1 chuyển đổi nhằm chuyển đổi bài toán MINLP 2y  2 y 0.5  11 y  8 x  20   2 x 0.5 Y 1  0.1x1.5 Y 2 0.5 0.5 2 0 không lồi thành bài toán MINLP lồi. Phương Y 1  1w1  (7) w2   3 w3   5  w4 4 4 4 pháp tuyến tính hóa liên tục được sử dụng Y 2  1w1  (7) 3 w2   3 w3   5  w4 3 3 nhằm làm giảm khối lượng tính toán cho bài y  1w1  7 w2  3w3  5w4 toán MINLP. w1  w2  w3  w4  1 5. TÀI LIỆU THAM KHẢO 1  x  7,1  y  7 0  w1 , 0  w2 , 0  w3 , 0  w4 [1] Some transformation techniques with applications in global optimization. 572

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN

TRỢ GIÚP

HỖ TRỢ KHÁCH HÀNG

Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright ©2025 TaiLieu.VN. All rights reserved.