Thuật toán chuyển bài toán qui hoạch phi tuyến về qui hoạch tuyến tính

Trong lý thuyết điều khiển tự động, khi giải bài toán tối ưu hoặc tìm thông số tối ưu cho bộ điều chỉnh, ta thường sử dụng chỉ tiêu tích phân bình phương sai lệch.
Nội dung trích xuất từ tài liệu:
Thuật toán chuyển bài toán qui hoạch phi tuyến về qui hoạch tuyến tính T¹p chÝ Khoa häc & C«ng nghÖ - Sè 3(43)/N¨m 2007 THUẬT TOÁN CHUYỂN BÀI TOÁN QUI HOẠCH PHI TUYẾN VỀ QUI HOẠCH TUYẾN TÍNH Nguyễn Hữu Công (Trường ĐH Kỹ thuật Công nghiệp - ĐH Thái Nguyên) 1. Đặt vấn đề Trong lý thuyết điều khiển tự động, khi giải bài toán tối ưu hoặc tìm thông số tối ưu cho bộ điều chỉnh, ta thường sử dụng chỉ tiêu tích phân bình phương sai lệch. Nếu ta áp dụng phương pháp số để tìm nghiệm tối ưu, thường dẫn tới việc giải bài toán qui hoạch phi tuyến sau: m   Tìm min của F ( w ) = ∑ ci  qi* − ∑ aij w j  i =0 j =0   n 2 (1) Với ràng buộc A1 ≤ wj ≤ A2 (j = 0,1,...,m) (2) * Trong đó wj là Nn cần tìm, qi , aij, ci là các hằng số dương đã biết Như vậy, bài toán được đặt ra là hãy tìm cực tiểu hàm (1) phụ thuộc vào m+1 biến wj tuân theo ràng buộc (2). Rõ ràng (1) là bài toán qui hoạch phi tuyến của các biến wj và các ràng buộc (2) là tuyến tính. Với bài toán này có thể tìm nghiệm đúng bằng phương pháp số sau một số hữu hạn phép lặp[2], [3]. Mặc dù nghiệm của bài toán qui hoạch bậc hai có thể thu được sau một số hữu hạn phép lặp nhưng thuật toán của nó phức tạp hơn và thời gian tính toán lâu hơn so với thuật toán của phương pháp đơn hình cho bài toán quy hoạch tuyến tính. 2. Nội dung của thuật toán Thay vì việc sử dụng chỉ tiêu tích phân bình phương sai lệch, ta đặt chỉ tiêu là tích phân trị tuyệt đối của sai lệch. Như vậy, thay vì tìm min của (1) với ràng buộc (2), ta tìm min của bài toán tương đương sau: n m i =0 j =0 L ( w ) = ∑ ci qi* − ∑ aij w j (3) Để giải bài toán tìm min (3) với các ràng buộc (2), ta có thể đưa về bài toán quy hoạch tuyến tính bằng cách dùng các kỹ thuật như sau[1]: Ta đưa ra 2 ( n + 1) biến phụ không âm là yi và zi (i = 0,1,... n). Ta sẽ chứng minh rằng min của (3) với ràng buộc (2) tương đương với min của n L = ∑ ci ( y i + z i ) (4) i =0 với ràng buộc:  − qi* = yi − zi  j =0  ( i = 0,1,..., n )  yi ≥ 0, zi ≥ 0  m ∑a w ij 32 j (5) T¹p chÝ Khoa häc & C«ng nghÖ - Sè 3(43)/N¨m 2007 và A1 ≤ w j ≤ A2 với j = 0, 1, 2,…, m Khi đó với bất kỳ [wj, yi, zi] nào là phương án tối ưu của bài toán (4), (5) thì zi , yi phải thoả mãn điều kiện: zi = 0 nếu : yi = 0 nếu: m ∑a w ij j =0 j − qi* không âm và j − qi* m ∑a w ij j =0 âm Với cách đặt biến phụ như vậy, ta sẽ có: minL = minL’ (6) Ta có thể chứng minh các kết luận trên như sau ( ) Bổ đề 1: Giả sử w, z , y là một phương án tối ưu của bài toán (4), (5) khi đó ta phải có: a, y i .z i = 0 với ∀i = 0, 1,.., n (tức là 1 trong 2 biến y i hoặc z i phải = 0). b, L( w ) = L ( w , z, y) Chứng minh: a, Giả sử trái lại z i . y i ≠ 0. Do yi ≥ 0 và zi ≥ 0 nên lúc đó ta phải có z i > 0, yi > 0 Ta đặt : h = min { z i , y i }; ta thấy h > 0 lại đặt : y i = y i − h và z i = z i − h (7) Rõ ràng: z i ≥ 0 ; y i ≥ 0 và với mỗi i thì hoặc yi’ = 0 hoặc zi’ = 0 nghĩa là y i z i = 0 với mọi i. Mặt khác ta thấy: yi − zi = yi − zi . Vì thế w j, yi, zi vẫn thoả mãn điều kiện (5) nghĩa là [ w j, yi, zi] cũng là phương án của bài toán (4),(5) Song ( ) ( ) L w j , yi , z i = ∑ ci ( yi + z i ) = ∑ (ci yi + z i − 2ci . h) n n i=0 i =0 (8) ở đây chú ý : h>0 , ci > 0 với ∀ i=0,1….n Vậy ta dễ thấy ( ) n ( ) ( L w j , zi , yi < ∑ ci yi + zi = L w j , yi , zi i =0 ) (9) 33 T¹p chÝ Khoa häc & C«ng nghÖ - Sè 3(43)/N¨m 2007 ( ) Điều này trái với giả thiết w j , z i , y i là phương án tối ưu của (4), (5). Tóm lại ta phải có y i . z i = 0 với ∀i = 0,1 ,..n. b, Do ( w , y, z ) là phương án tối ưu của bài toán (4), (5) nên phải thoả mãn ràng buộc (5). Theo chứng minh ở phần a, với mỗi i = 0,1,2,…n thì hoặc y i = 0 hoặc z i = 0 . - Nếu z i = 0 thì m ∑ a ij w j − q*i = yi ≥ 0 j= 0 m từ đó q*i − ∑ a ij w j = yi + z i (10) j= 0 - Nếu y i = 0 thì m ∑ a ij w j − q*i = - z i ≤0 j= 0 m từ đó qi* − ∑ aij w j = yi = zi (11) j =0 Tóm lại ta luôn có: n m n j =0 i=0 ( ) L(w) = ∑ ci q i − ∑ aij w j = ∑ (ci yi + zi = L ( w, z , y ) * i =0 Vậy L( w ) = L ( w , z, y) (đpcm) (12) (13) Mệnh đề 1: Giả sử ( w , y, z ) là phương án tối ưu của bài toán (4) ,(5). Khi đó w chính là phương án tối ưu của bài toán (3) với ràng buộc (2). Chứng minh: Thật vậy, giả sử trái lại, ∃ wˆ là phương án của bài toán (3), (2) với ( ) ˆ ) = L w . Từ wˆ ta sẽ xây d ự ng ph ươ ng án [ w ˆ , yˆ, zˆ ] củ a bài toán (4), (5) L(w nh ư sau: m Đặt yˆi = ∑ aij . wˆ j − qi* và zˆ i = 0 j =0 m nếu ∑ a . wˆ j =0 34 ij j − qi* ≥ 0 T¹p chÝ Khoa häc & C«ng nghÖ - Sè 3(43)/N¨m 2007  m  Đặt zˆ i = −  ∑ aij . wˆ j − qi*  và yˆi = 0  j =0  m nếu ∑a j =0 ij − qi* < 0 Khi đó ta có :   a) Bộ tham số  wˆ , yˆ , zˆ  cũng là phương án của bài toán (4), (5)   ˆ ) = L  wˆ , yˆ , zˆ  b) yˆ i + zˆ i = qi* − ∑ aij . wˆ j , nghĩa là L ( w   j =0 m (14) Theo giả thiết, theo (14) và theo bổ đề 1 (13) ta có :   L  wˆ , yˆ ...