Chương 1 Một số kiến thức cơ bản Nội dung chính của chương là trình bày mô hình tổng quát của bài toán tối ưu hóa, phân loại bài toán tối ưu, các phương pháp biến đổi cơ bản, một số thuật toán giải bài toán tối ưu hàm lồi một biến, giải bài toán quy hoạch tuyến tính trên MATLAB. Các kết quả là các kiến thức quan trọng được ứng dụng trong các chương sau của luận văn. Các kiến thức được tham khảo trong các tài liệu [1], [2], [4]. Mô hình tổng quát của bài toán tối ưu hóa Tối ưu hóa là một trong những lĩnh vực quan trọng của bài toán có ảnh hưởng đến hầu hết các lĩnh vực khoa học, công nghệ, kinh tế và xã hội.
Việc tìm giải pháp tối ưu cho một bài toán thực tế nào đó chiếm một vai trò hết sức quan trọng như việc tiến hành lập kế hoạch sản xuất hay thiết kế hệ thống điều khiển các quá trình. Nếu sử dụng các kiến thức trên nền tảng của toán học để giải quyết các bài toán cực trị, người ta sẽ đạt được hiệu quả kinh tế rất cao. Điều này phù hợp với mục đích của các bài toán đặt ra trong thực tế hiện nay. Mô hình bài toán tối ưu tổng quát được phát biểu như sau: LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 4 Cực đại hóa (cực tiểu hóa) hàm: f (X) → max/min Với các điều kiện: gi (X) = bi , i ∈ J1 (1.4) Trong đó f (X) được gọi là hàm mục tiêu, các điều kiện (1.1) được gọi là ràng buộc đẳng thức.3) được gọi là ràng buộc bất đẳng thức.4) được gọi là ràng buộc về dấu., xn )T là vectơ thuộc không gian Rn.
Tập các vectơ X thỏa mãn hệ ràng buộc lập nên một miền D được gọi là miền phương án (hay miền chấp nhận được), mỗi điểm X ∈ D gọi là một phương án. Một phương án X ∗ ∈ D làm cho hàm mục tiêu f (X) đạt cực đại hoặc cực tiểu được gọi là phương án tối ưu. Phân loại bài toán tối ưu Dựa trên mô hình tổng quát, người ta thường phân loại lớp các bài toán tối ưu như sau: - Quy hoạch tuyến tính: Là những bài toán mà hàm mục tiêu f (X) và tất cả các hàm ràng buộc gi (X), gj (X), gk (X) là tuyến tính. - Quy hoạch phi tuyến: Là những bài toán một trong hàm mục tiêu f (X) hoặc các hàm ràng buộc gi (X), gj (X), gk (X) là phi tuyến.
- Quy hoạch lồi: Là các bài toán quy hoạch mà các hàm mục tiêu f (X) là lồi trên tập các ràng buộc D lồi. LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 5 - Quy hoạch lõm: Là các bài toán quy hoạch mà các hàm mục tiêu f (X) là lõm trên tập các ràng buộc D lõm. - Quy hoạch rời rạc: Bài toán tối ưu được gọi là quy hoạch rời rạc nếu miền ràng buộc D là tập hợp rời rạc. Trong trường hợp riêng khi các biến chỉ nhận giá trị nguyên thì ta có quy hoạch nguyên.
- Quy hoạch đa mục tiêu: Nếu trên cùng một miền ràng buộc ta xét đồng thời các hàm mục tiêu khác nhau. Trong các lĩnh vực kinh tế kỹ thuật thì quy hoạch phi tuyến, quy hoạch tuyến tính là những bài toán thường gặp. Một số phương pháp giải cơ bản bài toán tuyến tính 1. Thuật toán hình học Xét bài toán: f (x1 , x2 ) = c1 x1 + c2 x2 → M ax; a11 x1 + a12 x2 ≤ b1 ; a21 x1 + a22 x2 ≤ b2 ;.
an1 x1 + an2 x2 ≤ bn ; x1 ≥ 0; x2 ≥ 0. Vì các ràng buộc của bài toán luôn luôn là các nửa mặt phẳng, do đó miền phương án luôn luôn là một đa giác lồi (là giao của các nửa mặt phẳng). Xét đường thẳng f = m được gọi là đường mức. Hiển nhiên khi đường mức chuyển động song song trong miền phương án thì điểm chạm LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 6 cuối cùng của đường mức với miền luôn luôn là một trong các đỉnh của đa giác (hoặc một cạnh của đa giác).
Đấy chính là phương án tối ưu cần tìm. Xuất phát từ nhận xét trên, chúng ta có thuật toán hình học gồm các bước như sau: Thuật toán: Bước 1: Vẽ miền phương án D là đa giác lồi bằng cách xác định miền giao của các nửa mặt phẳng trong hệ ràng buộc. Bước 2 : Xác định tọa độ của các đỉnh đa giác: Giả sử là các điểm A1 , A2 ,. Bước 3: Xác định phương án tối ưu fmax = max(f (A1 ), f (A2 ),.
Chú ý Trong trường hợp khi miền phương án không phải là miền kín thì tùy thuộc vào hướng di chuyển của đường mức, chúng ta sẽ xác định được phương án tối ưu của bài toán. Mô hình bài toán quy hoạch lồi tổng quát 1. Khái niệm tập lồi, hàm lồi a. Tập lồi Định nghĩa: Tập C ⊂ Rn được gọi là tập lồi nếu x, y ∈ C ⇒ λx + (1 − λ)y ∈ C, ∀λ ∈ [0; 1].
Nghĩa là nếu x, y ∈ C thì đoạn thẳng [x, y] ∈ C b. Hàm lồi Định nghĩa: Hàm số f (x) là lồi (convex function) trên tập C nếu với mọi cặp điểm (x1 , x2 ) thuộc C và mọi số λ ∈ [0, 1], ta có: f [λx1 + (1 − λ)x2 ] ≤ λf (x1 ) + (1 − λ)f (x2 ) LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 7 có nghĩa là điểm x = λx1 + (1 − λ)x2 trong [x1 , x2 ] thì mọi điểm của đồ thị luôn nằm dưới M1 M2 Điểm A: x = λx1 + (1 − λ)x2 Điểm B: f (x) = λf (x1 ) + (1 − λ)f (x2 ) Điểm C: f (x) = f (λx1 + (1 − λ)x2 ) Một số điều kiện - Hàm f (x) là lồi, nếu đối với hai điểm x1 , x2 thỏa mãn điều kiện f (x2 ) ≥ 0 f (x1 ) + 5f (x1 ).(x2 − x1 ) - Hàm f (x) là hàm lồi, nếu ma trận Hesian H(x) = [∂ 2 f (x)/∂x2 ∂x2 ] là bán xác định dương. Khi H(x) xác định dương thì hàm f (x) gọi là hàm lồi chặt. Cực trị của hàm lồi Bất cứ cực tiểu địa phương nào của hàm lồi trên tập lồi cũng là cực tiểu của hàm trên tập đó.
Ta sẽ chứng minh tính chất này bằng phản chứng: Giả thiết hàm f (x) có hai điểm cực tiểu là x1 và x2 .s ≤ 0 Trong đó s = (x2 − x1 ) là vectơ nối điểm x1 và x2. Theo (*), hàm f (x) giảm khi di chuyển theo hướng s khi xuất phát từ điểm x1. Điều này trái LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 8 với giả thiết x1 là cực tiểu. Do đó f (x) chỉ có một cực tiểu duy nhất.
Như vậy trong quy hoạch lồi thì giá trị tối ưu địa phương cũng là giá trị tối ưu toàn cục. Khái niệm về Gradient và đạo hàm hướng + Gradient của f (x) là một vectơ có các thành phần là đạo hàm riêng ∂f (x)/∂x1 T ∂f ∂f ∂f 5f (x) = , ,. Nếu đi theo hướng − 5 f (x0 ) thì f (x) giảm nhanh nhất. + Đạo hàm theo hướng z của hàm f (x) tại điểm x0 : 0 fz (x0 ) = h5f (x0 ), zi = | 5 f (x0 )|.cos(5f (x0 ), z) Đó là hình chiếu của vectơ 5f (x0 ) lên hướng z.
+ Ma trận Hessian H(x) là ma trận có các thành phần là Gradient cấp hai của f (x) ∂2f ∂2f ∂2f. Bài toán quy hoạch lồi tổng quát, điều kiện tối ưu a. Phát biểu bài toán Tìm x sao cho hàm mục tiêu f (x) → min Các ràng buộc: x ∈ C : gi (x) ≤ 0; i = 1, 2,. LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 9 trong đó C là tập lồi, f , gi là các hàm lồi trên C.
Điều kiện tối ưu + Miền nghiệm chấp nhận được: D = {x ∈ C : gi (x) ≤ 0} : i = 1, 2,. + Khái niệm về điểm yên ngựa (saddle point) m λi gi (x) = f (x) + λT g(x) P Ký hiệu hàm Lagrange L(x, λ) = f (x) + i=1 Khi đó điểm yên ngựa của hàm L(x, λ) là điểm (x∗ , λ∗ ) với x∗ ∈ D; λ∗ ≥ 0 sao cho: L(x, λ∗ ) ≤ L(x∗ , λ∗ ) ≤ L(x∗ , λ). Các thành phần λi của vectơ λ = [λ1 , ., λm ]T được gọi là các nhân tử Lagrange. Khi λ = λ∗ thì điểm (x∗ , λ∗ ) là điểm cao nhất của L(x, λ).
Khi x = x∗ thì điểm (x∗ , λ∗ ) là điểm thấp nhất của L(x, λ). Phương pháp xác định điểm yên ngựa: Điểm (x∗ , λ∗ ) là điểm yên ngựa của hàm L(x∗ , λ∗ ) khi và chỉ khi: +OL(x, λ) = 0 +gi (x) ≤ 0; i = 1, 2, ., m + Điều kiện cần và đủ của tối ưu Định lí 1.1 Điểm x∗ là tối ưu khi và chỉ khi fz (x∗ ) = h5f (x∗ ), zi ≥ 0; ∀z ∈ D(x∗ ) Tức là nếu xuất phát từ x∗ theo hướng bất kỳ z mà f (x) tăng thì f (x) đạt giá trị min tại x∗ ., m LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 10 Khi đó điều cần và đủ để x∗ trở thành nghiệm tối ưu là tồn tại một vectơ m chiều, không âm λ∗ = [λ∗1 , λ∗2 , ., λ∗m ]T sao cho cặp (x∗ , λ∗ ) là điểm yên ngựa của hàm Lagrange L(x, λ). Chú ý Điều kiện Slater không được thỏa mãn thì có thể không tồn tại điểm yên ngựa của hàm L(x, λ) loại (x∗ , λ∗ ). Ví dụ 1 Tìm min của f (x) = −x với ràng buộc g = x2 < 0 Ta có x∗ = 0.x2 Xác định điểm dừng: ∂L = −1 + 2λ.x = 0 ∂x Điều kiện Slater không thỏa mãn khi x = 0, do đó không tồn tại λ và hàm L(x, λ) không có điểm yên ngựa loại (0, λ).
Cực tiểu hàm lồi một biến Thuật toán chia đôi Cho hàm số f (x) xác định trên đoạn [a, b] với điều kiện f (x) lồi trên [a, b]. Cần xác định điểm xopt để hàm f (x) đạt min.