Thư viện tri thức trực tuyến
Kho tài liệu với 50,000+ tài liệu học thuật
© 2023 Siêu thị PDF - Kho tài liệu học thuật hàng đầu Việt Nam
Thuật toán chuyển bài toán qui hoạch phi tuyến về qui hoạch tuyến tính
Nội dung xem thử
Mô tả chi tiết
T¹p chÝ Khoa häc & C«ng nghÖ - Sè 3(43)/N¨m 2007
32
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:
Tìm min của ( )
2
*
0 0
n m
i i ij j
i j
F w c q a w
= =
= − ∑ ∑ (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: ( ) *
0 0
n m
i i ij j
i j
L w c q a w
= =
= − ∑ ∑ (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 1 (n + ) biến phụ không âm là i
y và i
z (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
( ) i i
n
i
i L = ∑c y + z
=0
' (4)
với ràng buộc:
( )
*
0 0,1,...,
0, 0
m
ij j i i i
j
i i
a w q y z
i n
y z
=
− = −
=
≥ ≥
∑ (5)