Chương 1 CƠ SỞ LÝ THUYẾT 1.1 Bài toán tối ưu 1.1 Các khái niệm cơ bản Bài toán tối ưu tổng quát được phát biểu như sau: min f (x), với điều kiện x ∈ D (P1 ) hoặc max f (x), với điều kiện x ∈ D (P2 ) trong đó D ⊂ Rn được gọi là tập nghiệm chấp nhận được hay tập ràng buộc và f là hàm mục tiêu. Mỗi điểm x ∈ D được gọi là một nghiệm chấp nhận được hay một phương án chấp nhận được. Điểm x∗ ∈ D được gọi là nghiệm cực tiểu toàn cục chặt nếu f (x∗ ) < f (x), ∀x ∈ D và x 6= x∗. Không phải bài toán (P1 ) nào cũng có nghiệm cực tiểu toàn cục và nếu bài toán có nghiệm cực tiểu toàn cục thì chưa chắc có nghiệm cực tiểu toàn cục chặt.
Giá trị tối ưu (hay giá trị cực tiểu) của bài toán (P1 ) được kí hiệu là min f (x) hoặc min{f (x)|x ∈ D}. x∈D Điểm x∗ ∈ D được gọi là nghiệm tối ưu địa phương, hoặc nghiệm cực tiểu địa phương của bài toán (P1 ) nếu tồn tại ε -lân cận B(x∗ , ε) của điểm x∗ ∈ D sao cho f (x∗ ) ≤ f (x), ∀x ∈ B(x∗ , ε) ∩ D, trong đó B(x∗ , ε) := {x ∈ Rn | ||x − x∗ || < ε}. 13 Trang 14 Luận văn thạc sĩ Điểm x∗ ∈ D được gọi là nghiệm tối ưu địa phương chặt, hoặc nghiệm cực tiểu địa phương chặt của bài toán (P1 ) nếu tồn tại ε -lân cận B(x∗ , ε) của điểm x∗ ∈ D sao cho f (x∗ ) < f (x), ∀x ∈ B(x∗ , ε) ∩ D và x 6= x∗. Các khái niệm tương tự cũng được định nghĩa cho bài toán (P2 ).
Nhận xét: Bài toán (P1 ) tương đương với bài toán max −f (x), với điều kiện x ∈ D theo nghĩa tập nghiệm tối ưu của hai bài toán này là trùng nhau và giá trị tối ưu ngược dấu.2 Điều kiện tồn tại nghiệm Mục đích của Quy hoạch toán học là nghiên cứu các tính chất của tập nghiệm và xây dựng các thuật toán để tìm nghiệm của bài toán tối ưu. Câu hỏi đầu tiên đặt ra là "bài toán cần giải có nghiệm tối ưu hay không?". Xét bài toán tối ưu: min f (x), với điều kiện x ∈ D (P1 ) trong đó D ⊂ Rn và f (x) là một hàm thực xác định trên một tập mở chứa D. Khi đó một trong bốn khả năng sau có thể xảy ra: - Bài toán (P1 ) không có phương án chấp nhận được, tức là D = ∅; - Bài toán có nghiệm tối ưu; - Bài toán không có nghiệm tối ưu và giá trị hàm mục tiêu giảm vô hạn trên tập chấp nhận được D, tức là giá trị tối ưu inf{f (x)|x ∈ D} = −∞; - Bài toán không có nghiệm tối ưu và giá trị tối ưu inf{f (x)|x ∈ D} là hữu hạn.
Như vậy, trừ trường hợp tập chấp nhận được bằng rỗng, giá trị tối ưu của bài toán (P1 ) luôn tồn tại nhưng nghiệm tối ưu thì không nhất thiết tồn tại. Việc tìm kiếm điều kiện đảm bảo để bài toán có nghiệm tối ưu là quan trọng. Cho hàm số f xác định trên tập mở X ⊂ Rn. Hàm f được gọi là liên tục tại điểm x0 ∈ X nếu với mỗi ε > 0 cho trước, tồn tại δ > 0 sao cho f (x) − f (x0 ) < ε với mọi x0 ∈ X thỏa mãn 0 xk− x < δ.
Nói cách0 khác hàm f k liên tục tại x0 ∈ X nếu với mọi dãy x ⊂ X hội tụ đến x , ta có f (x ) → f (x0 ). Hàm f được gọi là nửa liên tục dưới (tương ứng, nửa liên tục trên) tại điểm x0 ∈ X nếu với mỗi ε > 0 cho trước, tồn tại δ > 0 sao cho f (x) ≥ f (x0 ) − ε (tương ứng, f (x) ≤ f (x0 ) + ε) với mọi x0 ∈ X thỏa mãn x − x0 < δ. Nhận xét: Nếu f nửa liên tục dưới tại x0 thì −f nửa liên tục trên tại x0. Nguyễn Ngọc Bảo - Cao học khóa 2013.
Trang 14 Luận văn thạc sĩ - Chuyên ngành Toán Ứng Dụng Trang 15 Hàm f vừa nửa liên tục trên, vừa nửa liên tục dưới tại x0 thì liên tục tại điểm đó. Hàm f được gọi là liên tục (tương ứng, nửa liên tục dưới, nửa liên tục trên) trên X nếu nó liên tục (tương ứng, nửa liên tục dưới, nửa liên tục trên) tại mọi điểm của X. ([10] trang 20) Cho D là tập compact khác rỗng. Khi đó: i) Nếu hàm f nửa liên tục dưới trên D thì bài toán (P1 ) có nghiệm tối ưu, ii) Nếu hàm f nửa liên tục trên trên D thì bài toán (P2 ) có nghiệm tối ưu, Chứng minh.
Do tính tương tự, ta chỉ cần chứng minh (i). Giả sử giá trị tối ưu của bài toán (P1 ) là t0 = inf f (D). Theo định nghĩa (x) ≥ t0 , ∀x ∈ D (1.1) và tồn tại dãy xk ⊂ D sao cho lim f (xk ) = t0. k→∞ Do D là tập compact nên có một dãy con của dãy xk hội tụ đến một điểm x0 ∈ D.
Để đơn giản, ta có thể giả thiết rằng lim xk = x0 ∈ D. Do k→∞ f nửa liên tục dưới tại x0 ∈ D nên f (x0 ) ≤ lim f (xk ) = t0. Kết hợp điều k→∞ này với (1. (Định lý Weierstrass) Nếu tập D compact và hàm f liên tục trên D thì cả hai bài toán (P1 ) và (P2 ) đều có nghiệm tối ưu.
Hàm liên tục là hàm nửa liên tục trên và nửa liên tục dưới. Kết luận của Hệ quả được suy trực tiếp từ Định lý 1.3 Phân loại bài toán tối ưu Để tiện cho việc nghiên cứu, người ta thường chia các bài toán tối ưu thành một số lớp dựa trên tính chất của hàm mục tiêu và tập chấp nhận được. • Quy hoạch tuyến tính: Hàm mục tiêu f (x) là hàm tuyến tính và tập chấp nhận được là tập lồi đa diện. • Quy hoạch nguyên: Tập chấp nhận được có cấu trúc rời rạc • Quy hoạch phi tuyến: Hàm mục tiêu hoặc một trong các hàm ràng buộc không phải là hàm afin.
Trong các bài toán tối ưu phi tuyến có hai lớp đặc biệt quan trọng, đó là Quy hoạch lồi và Quy hoạch lõm. Nguyễn Ngọc Bảo - Cao học khóa 2013. Trang 15 Trang 16 Luận văn thạc sĩ • Quy hoạch động: Bài toán Quy hoạch động xét các đối tượng là các quá trình có thể chia ra thành nhiều giai đoạn hoặc các quá trình phát triển theo thời gian. Nhiều bài toán quy hoạch động có thể đưa về bài toán quy hoạch tuyến tính cỡ lớn.
• Quy hoạch đa mục tiêu: Bài toán có có nhiều hàm mục tiêu mà ta phải cực tiểu hóa (cực đại hóa) đồng thời. • Ngoài ra còn có Quy hoạch ngẫu nhiên, Quy hoạch tham số.1 Hàm lồi Định nghĩa 1. Cho x1 , x2 là hai điểm trong Rn. Đường thẳng qua x1 và x2 là tập các điểm x = λx1 + (1 − λ) x2 = x2 + λ(x1 − x2 ) với λ ∈ R.
Tập M ⊂ Rn được gọi là tập afin nếu M chứa trọn cả đường thẳng đi qua hai điểm bất kì của M, nghĩa là ∀x1 , x2 ∈ M, λ ∈ R ⇒ λx1 + (1 − λ)x2 ∈ M. Tập M ⊂ Rn được gọi là tập lồi nếu M chứa trọn đoạn thẳng nối hai điểm bất kì thuộc nó, tức là ∀x1 , x2 ∈ M, λ ∈ [0; 1] ⇒ λx1 + (1 − λ)x2 ∈ M. Hàm số có dạng f (x) = hc, xi+α, trong đó vectơ c ∈ Rn và α ∈ R cho trước được gọi là hàm afin. Cho hàm f xác định trên tập lồi X ⊆ Rn.
Ta gọi f là hàm lồi nếu f (λx1 + (1 − λ)x2 ) 6 λf (x1 ) + (1 − λ)f (x2 ) với bất kì x1 , x2 ∈ X và số thực λ ∈ [0; 1]. Hàm f được gọi là hàm lồi chặt nếu f (λx1 + (1 − λ)x2 ) < λf (x1 ) + (1 − λ)f (x2 ) với bất kì x1 , x2 ∈ X, x1 6= x2 và λ ∈ (0; 1). Miền xác định hữu hiệu của hàm f là domf := {x ∈ X|f (x) < +∞}. Hàm f : X → R ∪ {+∞} có thể được mở rộng thành một hàm lồi trên toán không gian Rn bằng cách đặt f (x) = +∞ nếu x ∈ / domf.
Vì vậy để n đơn giản ta thường xét f là hàm lồi trên R. Hàm f được gọi là hàm lõm (tương ứng, hàm lõm chặt) trên tập lồi X nếu −f là hàm lồi (tương ứng, hàm lồi chặt).([10] trang 200) Cho hàm số f xác định trên tập lồi khác rỗng X ⊆ Rn. Khi đó: Nguyễn Ngọc Bảo - Cao học khóa 2013. Trang 16 Luận văn thạc sĩ - Chuyên ngành Toán Ứng Dụng Trang 17 i) Hàm f là hàm lồi khi và chỉ khi epi(f ) là tập lồi.
ii) hàm f là hàm lõm khi và chỉ khi hypo(f ) là tập lồi. ([10] trang 201) i) Nếu hàm số f xác định trên tập lồi X ⊆ Rn là hàm lồi thì tập mức dưới Lα (f ) := {x ∈ X|f (x) 6 α} là tập lồi với mọi α ∈ R. ii) Nếu hàm số f xác định trên tập lồi X ⊆ Rn là hàm lõm thì tập mức trên Lα (g) := {x ∈ X|g(x) > α} là tập lồi với mọi α ∈ R.2 Các phép toán về hàm lồi Định nghĩa 1. Cho hàm số f1 xác định trên tập lồi X1 ⊆ Rn , hàm số f2 xác định trên tập lồi X2 ⊆ Rn và số thực λ > 0.
Các phép toán λf1 , f1 + f 2 , max{f1 , f 2 } được định nghĩa như sau: (λf1 )(x) := λ f1 (x), x ∈ X1 ; (f1 + f2 )(x) := f1 (x) + f2 (x), x ∈ X1 ∩ X2 ; max{f1 , f2 }(x) := max{f1 (x), f2 (x)}, x ∈ X1 ∩ X2 .([10] trang 202) Cho hàm số f1 xác định trên tập lồi X1 ⊆ Rn , hàm số f2 xác định trên tập lồi X2 ⊆ Rn và các số thực α > 0, β > 0. Khi đó các hàm λf1 , f1 + f 2 , max{f1 , f 2 } là lồi trên X1 ∩ X2 .3 Tính liên tục của hàm lồi Một hàm lồi f xác định trên tập lồi X ⊆ Rn không nhất thiết là hàm liên tục.