Toan Chi , Student at Đại Học Công Nghiệp Hà Nội (HaUI) 7 years ago
Vinhao 5 years ago Vinhao
Toan Chi , Student at Đại Học Công Nghiệp Hà Nội (HaUI) 7 years ago Toan Chi , Student at Đại Học Công Nghiệp Hà Nội (HaUI)
Tối ưu hóa
1. LOGO Nhóm thảo luận: Nguyễn Đức Trọng Hoàng Hoa Đại Nguyễn Văn Nhâm Mai Văn Thức Nguyễn Công Long Lê Đại Dương BÀI THẢO LUẬN SỐ 2 MÔN HỌC: TỐI ƯU HÓA
2. I. BÀI TOÁN ĐỐI NGẪU Phát biểu bài toán đối ngẫu: - Mỗi BTQHTT (còn gọi là bài toán gốc) có một bài toán đối ngẫu. Như vậy, bài toán gốc và bài toán đối ngẫu của nó lập thành một cặp BTQHTT, tính chất của bài toán này có thể được khảo sát thông qua bài toán kia Đối ngẫu của bài toán QHTT dạng chuẩn - Xét BT QHTT dạng chuẩn tắc: - Ta có bài toán đối ngẫu:
3. I. BÀI TOÁN ĐỐI NGẪU Đối ngẫu của bài toán QHTT dạng chính tắc - Xét BT QHTT dạng chính tắc: Đối ngẫu của bài toán QHTT dạng tổng quát - Xét BT QHTT dạng tổng quát: f(x)=ctx min - Ta có bài toán đối ngẫu: - Ta có bài toán đối ngẫu: g(y)=bty max,
4. I. BÀI TOÁN ĐỐI NGẪU Quy tắc thiết lập bài toán đối ngẫu Quy tắc 1: BTG là bài toán Min BTĐN là bài toán Max. Quy tắc 2: Các hệ số hàm mục tiêu của BTG Các hệ số vế phải của BTĐN. Quy tắc 3: Các hệ số vế phải của BTG Các hệ số hàm mục tiêu của BTĐN. Quy tắc 4: Ma trận hệ số của BTG là A Ma trận hệ số của BTĐN là At. Quy tắc 5: + Biến 0 của BTG Ràng buộc của BTĐN. + Biến 0 của BTG Ràng buộc của BTĐN. + Biến có dấu tuỳ ý của BTG Ràng buộc = của BTĐN. Quy tắc 6: + Ràng buộc BTG Biến 0 của BTĐN. + Ràng buộc BTG Biến 0 của BTĐN. + Ràng buộc = BTG Biến có dấu tuỳ ý của BTĐN. Chú ý: Các quy tắc viết bài toán đối ngẫu tổng quát trên đây được áp dụng khi bài toán gốcđã cho là BTQHTT dạng Min.
5. I. BÀI TOÁN ĐỐI NGẪU Quan hệ giữa cặp bài toán đối ngẫu Định lý 1 (Đối ngẫu yếu). Nếu x là một phương án bất kỳ của BT (P) và y là một phương án bất kỳ của BT (Q) thì f(x)g(y). Chứng minh: g(y) = bty = <Ax,y> = <x,Aty> <x,c> = ctx = f(x). Định lý 2. Nếu x*, y* lần lượt là các p.á của (P) và (Q), đồng thời f(x*)=g(y*) thì x* và y* lần lượt là các p.á.t.ư của (P) và (Q). Chứng minh: xDp: f(x) g(y*)=f(x*) x* là p.á.t.ư của (P). yDQ: g(y)f(x*)=g(y*) y* là p.á.t.ư của (Q). Định lý 3 (đối ngẫu mạnh). a) Nếu (P) có p.á.t.ư thì (Q) cũng có p.á.t.ư và ngược lại, đồng thời giá trị tối ưu bằng nhau. b) Nếu f(x) không bị chặn dưới trong Dp thì (Q) không có phương án. Nếu g(y) không bị chặn trên trong DQ thì (P) không có phương án. Chứng minh: Hệ quả. Điều kiện cần và đủ để cặp p.á x*, y* lần lượt là p.á.t.ư của cặp BT đối ngẫu (P), (Q) là ctx*=bty*.
6. I. BÀI TOÁN ĐỐI NGẪU Quan hệ giữa cặp bài toán đối ngẫu Định lý 4 (Định lý độ lệch bù yếu). Một cặp phương án x, y của hai quy hoạch đối ngẫu (P) và (Q) là cặp phương án tối ưu khi và chỉ khi chúng nghiệm đúng các hệ thức Nhận xét: Nếu biết 1 p.á.t.ư của bài toán gốc thì ta có thể suy ra các p.á.t.ư của bài toán đối ngẫu mà không cần giải nó. 1 1 ( ) 0, 1,2,..., , ( ) 0, 1,2,..., . n i ij j i j m j j ij i i y a x b i m x c a y j n
7. II. PHƯƠNG PHÁP ĐƠN HÌNH ĐỐI NGẪU 2.1. Cơ sở chấp nhận được đối ngẫu Xét BT QHTT dạng chính tắc f(x)=ctxmin, Ax=b, (P) x0. Giả thiết: rank(A)=m; {Aj, jJ} là hệ gồm m vectơ cột đltt của A. Gọi J là cơ sở của A; AJ là ma trận cơ sở. Định nghĩa: Nếu xJ=AJ-1b0 thì J gọi là cơ sở chấp nhận được. Nếu x là p.á.t.ư thì J gọi là cơ sở tối ưu. Định nghĩa: Vectơ y=(AJt)-1cJ được goi là p.á cơ sở đối ngẫu ứng với cơ sở J. Nếu y là p.á chấp nhận được của (Q) thì J được gọi là cơ sở chấp nhận được đối ngẫu.
8. II. PHƯƠNG PHÁP ĐƠN HÌNH ĐỐI NGẪU Bảng đơn hình đối ngẫu Giả sử J là cơ sở chấp nhận được đối ngẫu. Giả thiết J={1,2,,m}. Lập bảng J Cj Xj 1 2 k n C1 C2 Ck Cn 1 2 m C1 C2 ... Cm X1 X2 Xm Z11 Z12 Z1k Z1n Z21 Z22 Z2k Z2n Zm1 Zm2 Zmk Zmn f(x) 1 2 ... k n
9. II. PHƯƠNG PHÁP ĐƠN HÌNH ĐỐI NGẪU 2.2. Thuật toán đơn hình đối ngẫu. Các bước của thuật toán:
10. II. PHƯƠNG PHÁP ĐƠN HÌNH ĐỐI NGẪU LƯU ĐỒ THUẬT TOÁN
11. BÀI TẬP a) Tìm bài toán đối ngẫu của bài toán sau đây. Giải bài toángốc bằng thuật toán đơn hình đối ngẫu và suy ra kết quả của bài toán đối ngẫu tương ứng Bài giải BTG f(x) = x1 + 3x2+2 x3 min Với các ràng buộc
12. BÀI TẬP Ta có bài toán đối ngẫu tương ứng: g(x) = 8y1 2y2 + 2y3 max Chọn J={4,5,6} là 1 cơ sở Lập bảng đơn hình xem J có là cơ sở chấp nhận đối ngẫu không:
13. BÀI TẬPJ Cj Xj C1 1 C2 3 C3 2 C4 0 C5 0 C6 0 4 5 6 0 0 0 8 -2 2 4 -2 1 -5 4 -3 7 -2 2 1 0 0 0 1 0 0 0 1 F(x)=0 -1 -3 -2 0 0 0 Nhận xét: tất cả các đều J là cơ sở chấp nhận đối ngẫu Tiến hành tìm phương án tối ưu theo thuật toán đơn hình đối ngẫu ta được: J Cj Xj C1 1 C2 3 C3 2 C4 0 C5 0 C6 0 4 1 6 0 1 0 4 1 1 0 1 0 3 -2 -1 3 1 1 1 0 0 2 -1/2 1/2 0 0 1 F(x)=1 0 -5 -1 0 -1/2 0
14. BÀI TẬP Nhận thấy cột giả phương án có các thành phần đều dương nên J={4,1,6} là cơ sở tối ưu và phương án tối ưu là x*=(1,0,0,4,0,1) , f(x*) = 1 P/á tối ưu của bài toán đối ngẫu xác định bởi HPT (Aj,y)= Cj ( j Cụ thể là:
15. BÀI TẬP b) Chứng tỏ J = (3,4,5) là một cơ sở đối ngẫu và giải bài toán sau đây bằng thuật toán đơn hình đối ngẫu
16. BÀI TẬP Áp dụng Gauss ta có: Ta thử lập bảng: J Cj Xj C1 1 C2 1 C3 0 C4 0 C5 0 4 3 5 0 0 0 1 -5 -1 1 -1 -2 -3 4 5 0 1 0 1 0 0 0 0 1 F(x)=0 -1 -1 0 0 0
17. BÀI TẬP Ta thấy đều nên J={3,4,5} là cơ sở chấp nhận đối ngẫu. J Cj Xj C1 1 C2 1 C3 0 C4 0 C5 0 4 1 5 0 1 0 -4 5 9 0 1 0 1 -4 -3 1 -1 1 1 0 0 0 0 1 F(x)=5 0 -5 -1 0 0 Vì x4= -4 mà các z4k đều >0 => phương trình đã cho vô nghiệm.
Share Clipboard Name* Description Others can see my Clipboard CancelSave
