tailieunhanh - Bài giảng Tối ưu hóa và quy hoạch tuyến tính - Chương 2: Bài toán đối ngẫu

Bài giảng Tối ưu hóa và quy hoạch tuyến tính - Chương 2: Bài toán đối ngẫu cung cấp cho người học những kiến thức như: Ý nghĩa và cách lập bài toán đối ngẫu; Giải bài toán đối ngẫu; Ứng dụng của bài toán đối ngẫu. Mời các bạn cùng tham khảo! | Chương 2 BÀI TOÁN ĐỐI NGẪU 1 2 NỘI DUNG CHƯƠNG Ý nghĩa và cách lập bài toán đối ngẫu Giải bài toán đối ngẫu Ứng dụng của bài toán đối ngẫu Ý nghĩa và cách lập bài toán đối ngẫu Xét bài toán sản xuất tối ưu Z 2 x1 3 x2 4 x3 max 10x1 20 x2 30 x3 10000 20 x1 30 x2 30 x3 50000 20 x1 30 x2 40 x3 30000 x j 0 j 1 2 3 Có một đối tác đặt vấn đề mua toàn bộ nguyên liệu của cty A. Hãy lập bài toán định giá mua ng liệu rẻ nhất. 3 Ý nghĩa và cách lập bài toán đối ngẫu Gọi yi i 1 2 3 là giá mua 1 đ vị nguyên liệu đường sữa bột tương ứng. Z 10000 y1 50000 y2 30000 y3 min 10y1 20 y2 20 y3 2 20 y1 30 y2 30 y3 3 30 y1 30 y2 40 y3 4 yi 0 i 1 2 3 Bài toán gọi là BTĐN của . 4 Lập bài toán đối ngẫu Bài toán xuất phát ĐNgẫu Bài toán đối ngẫu Z c1x1 cn xn max Z b1y1 bmym min RBD ngược dấu RBC n 0 aij x j bi i 1 m yi 0 i 1 m j 1 tùy ý RBC cùng dấu RBD x j 0 m x j 0 j 1 n a y cj j 1 n tùy ý ij i i 1 5 6 Lập bài toán đối ngẫu Ví dụ Xét bài toán QHTT BTDN Z 2 x1 x2 8 x3 max Z 28 y1 10 y2 15 y3 min 7 x1 4 x2 2 x3 28 7 y1 3 y2 2 y3 2 3 x1 x2 3 x3 10 4 y1 y2 3 y3 1 2 x1 3 x2 x3 15 2 y1 3 y2 y3 8 y1 0 y3 0 x j 0 j 1 3 7 Lập bài toán đối ngẫu b BTĐN Z x1 2 x2 3x3 min Z 2 y1 3 y2 4 y3 5 y4 max 2x1 2 x2 x3 2 2 y1 y2 y3 2 y4 1 x1 x2 4 x3 3 2 y1 y2 2 y3 2 x1 2 x2 4 y1 4 y2 y4 3 2 x1 x3 5 y1 y3 0 y2 y4 0 x1 x2 0 8 Cặp ràng buộc đối ngẫu Trong một cặp bài toán đối ngẫu ta gọi hai ràng buộc bất đẳng thức trong hai bài toán cùng tương ứng với một chỉ số quy định dấu bất đẳng thức lẫn nhau là một cặp ràng buộc đối ngẫu. 9 Cặp ràng buộc đối ngẫu Ví dụ Ở ví dụ thì có 5 cặp ràng buộc đối ngẫu sau x1 0 7 y1 3 y2 2 y3 2 x2 0 4 y1 y2 3 y3 1 x3 0 2 y1 3 y2 y3 8 7 x1 4 x2 2 x3 28 y1 0 2 x1 3 x2 x3 15 y3 0 10 Các định lý đối ngẫu Định lý đối ngẫu yếu Nếu x là phương án tùy ý của bài toán gốc P và y là phương án tùy ý của bài toán đối ngẫu D thì Z x Z y . Hệ quả 1 Nếu một trong hai bài toán của cặp bài toán đối ngẫu có phương án tối ưu thì bài toán