TAILIEUCHUNG - 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

• Toán học
• Bài giảng Tối ưu hóa
• Quy hoạch tuyến tính
• Tối ưu hóa
• Bài toán đối ngẫu
• Giải bài toán đối ngẫu
• Cách lập bài toán đối ngẫu
• Tối ưu hóa logic
• Tối ưu hóa câu hỏi
• Bài giảng Tối ưu hóa câu hỏi
• Xử lý câu hỏi truy vấn
• Kỹ thuật tối ưu hóa
• Bài giảng Tối ưu hóa trong thiết kế cơ khí
• Tối ưu hóa trong thiết kế cơ khí
• Thiết kế cơ khí
• Bài toán tối ưu hóa
• Lập mô hình toán tối ưu hóa
• Phương pháp đồ thị
• Giải bài toán tối ưu hóa
• Ứng dụng excel solver
• Ứng dụng Matlab
• Bài giảng Tối ưu hóa nâng cao
• Tối ưu hóa nâng cao
• Ứng dụng của toán học
• Mô hình tối ưu hóa nâng cao
• Bài toán tối ưu không ràng buộc
• Cực tiểu của hàm lồi
• Tổng quan về thuật toán
• Tối ưu hàm nhiều biến số
• Ma trận Hessian
• Vi phân bậc r của hàm f
• Feasible direction
• Điều kiện Karush Kuhn Tucker
• Tối ưu hóa thực nghiệm
• Vấn đề tối ưu hóa thực nghiệm
• Các phương pháp tối ưu hóa
• Phân loại các phương pháp tối ưu hóa
• Phương pháp thực nghiệm theo đường dốc nhất
• Phương pháp khảo sát mặt mục tiêu
• Bài giảng Toán tối ưu
• Toán tối ưu
• Bài toán tối ưu đa mục tiêu
• Phương pháp tuyến tính hóa
• Bài toán tối ưu
• Giải tích lồi
• Tài liệu về Toán tối ưu
• Điều kiện tối ưu
• Phương pháp có thể
• Tối ưu đa mục tiêu
• Bài toán quy hoạch tuyến tính
• Quy hoạch tuyến tính dạng chính tắc
• Quy hoạch tuyến tính đối ngẫu
• Định lý đối ngẫu
• Bài toán quy hoạch tuyến tính đối ngẫu
• Hướng dẫn làm bài tập
• Trọng tâm vật rắn phức hợp
• Bài toán vận tải
• Tiêu chuẩn tối ưu
• Giải thuật thế vị
• Phương án cực biên
• Mô hình kinh tế
• Phương pháp tối ưu hóa
• Bài giảng Mô hình kinh tế
• Cấu trúc tối ưu hóa
• Lý thuyết kinh tế
• Giả định tối ưu hóa
• Tính lồi lõm
• Hàm nhiều biến
• Đồ thị hàm số
• Line search method
• Điều kiện Wolfe
• Backtracking line search
• Gradient descent
• Fixed step size