Hoc toi ưu hóa bài toán đối ngẫu
Khoa Khoa học Tự nhiên và Xã hội – Đại học Thái Nguyên Bài giảng : Toán Quy hoạch03/2008 Ths. Ngô Văn Định Chương 3. Bài toán đối ngẫu 3.1.Khái niệm3.2.Quan hệ giữa cặp BT đối ngẫu3.3. Ý nghĩa của BT đối ngẫu (tự nghiên cứu) 3.4.Phương pháp đơn hình đối ngẫu Khoa Khoa học Tự nhiên và Xã hội – Đại học Thái Nguyên Bài giảng : Toán Quy hoạch03/2008 Ths. Ngô Văn Định 3.1. Khái niệm bài toán đối ngẫu 3.1.1. Hàm Lagrange- Xét BT QHTT dạng chuẩn tắc:f(x)=c t x → min,Ax ≥ b,(P)x ≥ 0.- Hàm L(x,y)=c t x+(b-Ax) t y, x ∈ R n+ , y ∈ R m+ gọi là hàmLagrange của BT (P).- Điểm (x*,y*) ∈ R n+ × R m+ gọi là điểm yên ngựa củahàm Lagrange L(x,y) nếu:L(x*,y)≤L(x*,y*)≤L(x,y*), ∀ x ∈ R n+ , ∀ y ∈ R m+ Khoa Khoa học Tự nhiên và Xã hội – Đại học Thái Nguyên Bài giảng : Toán Quy hoạch03/2008 Ths. Ngô Văn Định 3.1.2. Đối ngẫu của BT dạng chuẩn tắcTa có ∀ x ∈ R n+ , Ax ≥ b ⇒ b-Ax ≤ 0c t x, nếu x ∈ R n+ t/m Ax ≥ b, ⇒ max y L(x,y)=+ ∞ , còn lại.Do vậy, (P) ⇔ min x max y L(x,y)(*)Đổi thứ tự lấy cực trị ta có bài toán:max y min x L(x,y)(**)Bài toán (*) là bài toán gốc, (**) gọi là bài toán đốingẫu. 3.1. Khái niệm bài toán đối ngẫu Bạn đang xem tài liệu "Bài giảng Tối ưu hóa - Chương 2: Bài toán quy hoạch tuyến tính đối ngẫu", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên Nội dung text: Bài giảng Tối ưu hóa - Chương 2: Bài toán quy hoạch tuyến tính đối ngẫu
|