Giáo trình tối ưu hóa - Chương 6

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ặc phương án, nếu vắn tắt hơn), xj là các biến quyết định,∀j = 1,n . Người...
Nội dung trích xuất từ tài liệu:
Giáo trình tối ưu hóa - Chương 6 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ặc phươ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ột vé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 ∈ D cho 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ác vấ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 k x = ∑ λ 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 =1 x . 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 k dạ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ồi củ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ọi tập lồi chứa S đều chứa H(S). Chứng minh k k ∑λ x ∑λ Ta có H(S) ={x ∈ Rn: ∃ xj ∈ S, ∀j = 1,k sao cho x = = 1 , λ j ≥ 0 ,∀j = j v ới j j j =1 j =1 1,k }. Cần chứng minh với mọi tập lồi A mà S ⊂ A thì H (S) ⊂ A. k ∑λ Tức là, cho xj ∈ S ⊂ A ,∀j = 1,k và = 1 , λ j ≥ 0 , cần phải chứng tỏ rằng: j j =1 k ∑λ x ∈ A. j x= (6.1) j j =1 Ta chứng minh kết luận (6.1) bằng phép quy nạp. Với k = 1, (6.1) hiển nhiên đúng. Giả sử (6.1) đúng với k = s, cần chứng minh (6.1) đúng với k = s + 1. s+1 Thật vậy, cho xj ∈ S ⊂ A ,∀j = 1,s + 1 và ∑ λ j = 1 , λ j ≥ 0 . Chúng ta sẽ chỉ ra rằng x = j =1 ...