tailieunhanh - Bài giảng Toán kinh tế: Đối ngẫu

Bài giảng "Toán kinh tế: Đối ngẫu" được biên soạn với các nội dung chính sau: Quy tắc viết đối ngẫu; Cặp bài toán QHTT đối ngẫu; Định lí đối ngẫu yếu; Định lí đối ngẫu mạnh; Định lí về độ lệch bù; Định lí tồn tại; . Mời các bạn cùng tham khảo bài giảng! | Đối ngẫu Lecturer Phạm Thị Hoài Department of Applied Mathematics - School of Applied Mathematics and Informatics - Hanoi University of Science and Technology 0 8 Nội dung 1 Cặp bài toán QHTT đối ngẫu 2 Các định lí về đối ngẫu 1 8 Cặp bài toán QHTT đối ngẫu Quy tắc viết đối ngẫu Gốc P min c T x max b T y Đối ngẫu D ai x bi i M1 yi tự do i M1 Ràng buộc ai x bi i M2 yi 0 i M2 Biến ai x bi i M3 yi 0 i M3 xj 0 j N1 AT j y cj j N1 Biến xj 0 j N2 AT j y cj j N2 Ràng buộc xj tự do j N3 AT j y cj j N3 ai là các véc tơ hàng Aj là các véc tơ cột của ma trận A A Rm n M1 M2 M3 m N1 N2 N3 n 2 8 Cặp bài toán QHTT đối ngẫu Viết bài toán đối ngẫu của QHTT chuẩn tắc minimize cT x subject to Ax b x 0 QHTT chính tắc minimize cT x subject to Ax b x 0 3 8 Cặp bài toán QHTT đối ngẫu Đối ngẫu của bài toán đối ngẫu chính là bài toán gốc tại sao Ví dụ viết bài toán đối ngẫu của bài toán sau minimize x1 2x2 3x3 8x4 subject to 4x1 2x2 x3 9x4 7 x1 x2 5x3 x4 5 6x1 8x2 3x3 x4 10 x1 0 x2 tự do x3 x4 0 4 8 Các định lí về đối ngẫu Định lí đối ngẫu yếu Theorem 1 Nếu x là phương án chấp nhận được bất kì của bài toán gốc P và y là phương án chấp nhận được bất kì của bài toán đối ngẫu D thì bT y c T x Hệ quả 1 Nếu hàm mục tiêu của bài toán min max không bị chặn dưới trên thì bài toán đối ngẫu của nó có tập chấp nhận được bằng rỗng. Giả sử x y tương ứng là phương án chấp nhận được của bài toán P và D thỏa mãn c T x b T y . Khi đó x y tương ứng là phương án tối ưu của bài toán P và D . 5 8 Các định lí về đối ngẫu Định lí đối ngẫu mạnh Theorem 2 Nếu bài toán QHTT có phương án tối ưu thì bài toán đối ngẫu của nó cũng có phương án tối ưu và giá trị tối ưu của hai bài toán bằng nhau. Hệ quả 2 Điều kiện cần và đủ để cặp phương án chấp nhận được x y của bài toán P và D là phương án tối ưu là c T x b T y . 6 8 Các định lí về đối ngẫu .