tailieunhanh - Giáo trình Quy hoạch tuyến tính: Phần 2 - Lê Đức Thắng

Mời các bạn cùng tìm hiểu khái niệm về đối ngẫu; giải thuật đối ngẫu; ứng dụng quy hoạch tuyến tính; bài toán dòng trên mạng; quy hoạch tuyến tính;. được trình bày cụ thể trong "Giáo trình Quy hoạch tuyến tính: Phần 2". | Khái niệm về đối ngẫu Đối ngẫu là một khái niệm cơ bản của việc giải bài toán quy hoạch tuyến tính vì lý thuyết đối ngẫu dẫn đến một kết quả có tầm quan trọng về mặt lý thuyết và cả mặt thực hành. Đối ngẫu của quy hoạch tuyến tính dạng chính tắc Xét một bài toán quy hoạch dạng chính tắc Lmin z x - CTX Ax b ịx ũ Giả sử rằng x là phương án tối ưu cần tìm của bài toán và x0 là một phương án của bài toán thì một cận trên của giá trị mục tiêu tối ưu được xác định vì cTx cTx0 Tuy chưa tìm được phương án tối ưu x nhưng nếu biết thêm được một cận dưới của giá trị mục tiêu tối ưu thì ta đã giới hạn được phần nào giá trị mục tiêu tối ưu. Người ta ước lượng cận dưới này theo cách như sau Với mỗi vectơ xT xi x2 . xn 3 0 thuộc Rn chưa thoả ràng buộc của bài toán tức là b - Ax 1 0 người ta nới lỏng bài toán trên thành bài toán nới lỏng min L x y CTX yT b - Ax X 0 yT yi y2. ym tuỳ ý ĩ Rm Gọi g y là giá trị mục tiêu tối ưu của bài toán nới lỏng ta có g y min cTx yT b - Ax x 3 0 73 129 cTx yT b - Ax Trong trường hợp x là phương án của bài toán ban đầu tức là b - Ax 0 thì g y cTx Vậy g y là một cận dưới của giá trị mục tiêu bất kỳ nên cũng là cận dưới của giá trị mục tiêu tối ưu. Một cách tự nhiên là người ta quan tâm đến bài toán tìm cận dưới lớn nhất đó là max g y y tuỳ ý ĩ Rm Bài toán này được gọi là bài toán đối ngẫu của bài toán ban đầu. Trong phần sau người ta sẽ chứng minh giá trị mục tiêu tối ưu của bài toán đối ngẫu bằng với giá trị mục tiêu tối ưu của bài toán gốc ban đầu. Người ta đưa bài toán đối ngẫu về dạng dể sử dụng bằng cách tính như sau g y min cTx yT b - Ax x 3 0 min cTx yTb - yTAx x 3 0 min yTb cT - yTA x x 3 0 yTb min cT - yTA x x 3 0 Ta thấy . T T 0 khl cT ũ min c - y Ạ X -không xác đinh khi CT - Ấ ũ 74 129 Vậy ta nhận được g y yTb VỚI CT - yTA ũ Suy ra bài toan đôi ngâu có dạng maz g y yTả V e Ẵ tùy ý Hay là max g y bĩy ATy c V RM tùy ỷ Định nghĩa đối ngẫu trong trường hợp quy hoạch tổng quát Trong trường hợp quy hoạch tuyến tính tổng quát những quy tắc sau .

TỪ KHÓA LIÊN QUAN
TÀI LIỆU MỚI ĐĂNG
crossorigin="anonymous">
Đã phát hiện trình chặn quảng cáo AdBlock
Trang web này phụ thuộc vào doanh thu từ số lần hiển thị quảng cáo để tồn tại. Vui lòng tắt trình chặn quảng cáo của bạn hoặc tạm dừng tính năng chặn quảng cáo cho trang web này.