Tối ưu hóa phần 8

Hãy giải các BTQHTP sau đây bằng phương pháp thích hợp (phương pháp Wolfe hoặc phương pháp thiết lập bài toán bù):a. Min f(x) = x12 + x22 – 8x1 – 4x2, với các ràng buộcx1 + x2 ≤ 2 x1, x2 ≥ 0.b. Min f(x) = x12 + x22 – x1x2 – 3x1, với các ràng buộcx1 + x2 ≤ 2 x1, x2 ≥ 0.c. Min f(x) = 2x12 + 4x22 – 4x1x2 – 15x1 – 30x2, với các ràng buộcx1 + 2x2 ≤ 30 x1, x2 ≥ 0.Bài 8. Hãy giải các BTQHTP sau đây bằng phương pháp...
Nội dung trích xuất từ tài liệu:
Tối ưu hóa phần 8Bài 7. Hãy giải các BTQHTP sau đây bằng phương pháp thích hợp (phương pháp Wolfe hoặcphương pháp thiết lập bài toán bù): a. Min f(x) = x12 + x22 – 8x1 – 4x2, với các ràng buộc x1 + x2 ≤ 2 x1 , x 2 ≥ 0. b. Min f(x) = x12 + x22 – x1x2 – 3x1, với các ràng buộc x1 + x2 ≤ 2 x1 , x 2 ≥ 0. c. Min f(x) = 2x12 + 4x22 – 4x1x2 – 15x1 – 30x2, với các ràng buộc x1 + 2x2 ≤ 30 x 1 , x 2 ≥ 0.Bài 8. Hãy giải các BTQHTP sau đây bằng phương pháp thích hợp (phương pháp Wolfe hoặcphương pháp thiết lập bài toán bù): a. Min f(x) = 2x1 – 4x2 + x12 – 2x1x2 + x22, với các ràng buộc – x1 + x2 ≤ 1 x1 – 2x2 ≤ 4 x 1 , x 2 ≥ 0. b. Min f(x) = –4x1 – 6x2 + x12 – 2x1x2 + x22, với các ràng buộc 2x1 + x2 ≤ 2 – x1 + x2 ≤ 4 x1, x2 ≥ 0. c. Min f(x) = 5x1 + 6x2 – 12x3 + 2x12 + 4x22 + 6x32 – 2x1x2 – 6x1x3 + 8x2x3 với các ràng buộc x1 + 2x2 + x3 ≥ 6 x1 + x2 + x3 ≤ 16 ≤4 –x1 + 2x2 x1, x2, x3 ≥ 0.Bài 9. Lập chương trình máy tính phương pháp Wolfe hoặc phương pháp thiết lập bài toán bù sửdụng ngôn ngữ Pascal hay C, sau đó chạy kiểm thử cho bài tập 7.Bài 10. Giải các bài toán sau đây bằng phương pháp quy hoạch tách: a. Min f(x) = exp(x1) + x12 + 4x1 + 2x22 – 6x2 + 2x3134 với các ràng buộc sau x12 + exp(x2) + 6x3 ≤ 15 x14 – x2 + 5x3 ≤ 25 0 ≤ x1 ≤ 4, 0 ≤ x2 ≤ 2, 0 ≤ x3 . Cho biết các điểm lưới là 0, 2, 4 cho x1 và 0, 1, 2 cho x2. b. Min f(x) = exp(2x1 + x22) + (x3 – 2)2 với các ràng buộc sau x1 + x2 + x3 ≤ 6 x1, x2, x3 ≥ 0. bằng cách đổi biến thích hợp với các điểm lưới tùy chọn.Bài 11. Giải các bài tập sau đây bằng phương pháp quy hoạch hình học: a. Min f(x) = 2x1–1 + x22 + x14x2–2 + 4x12, với điều kiện x1, x2 > 0. b. Min f(x) = 5x1x2–1x32 + x1–2x3–1+10x23+ 2x1–1x2x3–3 , với điều kiện x1, x2, x3 > 0. c. Min f(x) = 4x1–1x2– 0,5, với điều kiện: x1 + 2x22 ≤ 1 và x1, x2 > 0.Bài 12. Hãy tìm hiểu cơ sở và phát biểu các thuật toán tổng quát cho quy hoạch tách và quyhoạch hình học. 135 Chương VI Một số vấn đề cơ sở của lý thuyết quy hoạch lồi và quy hoạch phi tuyến Xét bài toán quy hoạch phi tuyến tổng quát: Min (Max) f(x), với điều kiện x ∈ D = { x ∈ Rn: gi ( x ) ≤ 0 , i = 1,m 1 ; gi ( x ) = 0 , i = m 1 + 1,m }. Véc tơ x = (x1,……xn) ∈ D được gọi là véc tơ quyết định hay phương án khả thi (hoặcphương án, nếu vắn tắt hơn), xj là các biến quyết định,∀j = 1,n . Người giải bài toán cần tìm mộtvéc tơ x* ∈ D sao cho: f(x*) ≤ f(x), ∀x ∈ D cho bài toán cực tiểu hoá hoặc f(x*) ≥ f(x), ∀x ∈ Dcho bài toán cực đại hoá.1. Tập hợp lồi Trong phần này chúng ta nghiên cứu các khái niệm cơ bản của giải tích lồi bao gồm cácvấn đề sau liên quan đến tập hợp lồi (còn gọi vắn tắt là tập lồi): – Bao lồi của một tập hợp. – Bao đóng và miền trong của tập lồi. – Siêu phẳng tách và siêu phẳng tựa của tập lồi. – Nón lồi và nón đối cực.1.1. Bao lồi Trong chương V, chúng ta đã biết, tập lồi là tập S ⊂ Rn có tính chất: mọi đoạn thẳng nối x1,x2 ∈ S đều nằm trong S. Nói cách khác: S ⊂ Rn là tập lồi khi và chỉ khi x = λx1 + (1 – λ) x2 ∈ S ,∀ λ ∈ [0, 1], ∀ x1, x2 ∈ S . Xét các tập lồi S1, S2 ⊂ Rn. Lúc đó, S1 ∩ S2 lồi, S1 + S2 lồi và S1 – S2 cũng là tập lồi. Định nghĩa 1. Xét tập S ⊂ Rn và các điểm x1 , x2, ..., xk ∈ S. Điểm k kx = ∑ λ j x j (với ∑ λ j = 1 , λ j ≥ 0 ,∀j = 1,k ) được gọi là một tổ hợp lồi của các điểm x1 , x2, ..., j =1 j =1x . Bao lồi (Convex hull) của S, ký hiệu là H(S), gồm tất cả các điểm x ∈ Rn được biểu diễn dưới kdạng một tổ hợp lồi của một số điểm nào đó của S. Ví dụ 1. Bao lồi của 3 điểm x1, x2 và x3 không thẳng hàng trong R3 là một tam giác. Bao lồicủa một hình vành trăng khuyết trong R2 là một hình khuyên.136 Định lý 1. Bao lồi H(S) của một tập S ⊂ Rn là tập lồi nhỏ nhất chứa S. Nói cách khác mọitập lồi chứa S đều chứa H(S). Chứng minh k k ∑λ x ...