Đang chuẩn bị liên kết để tải về tài liệu:
TOÁN GIẢI THUẬT - CHƯƠNG III: BÀI TOÁN ĐỐI NGẪU

Tham khảo tài liệu 'toán giải thuật - chương iii: bài toán đối ngẫu', khoa học xã hội, kinh tế chính trị phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả | BÀI TOÁN ĐỐI NGẪU CHƯƠNG III BÀI TOÁN ĐỐI NGẪU Chương này trình bày trình bày khái niệm đối ngẫu các quy tắc đối ngẫu và giải thuật đối ngẫu. Đây là các kiến thức có giá trị trong ứng dụng vì nhờ đó có thể giải một quy hoạch tuyến tính từ quy hoạch tuyến tính đối ngẫu của nó. Nội dung chi tiết của chương này bao gồm I- KHÁI NIỆM VỀ ĐỐI NGẪU 1- Đối ngẫu của quy hoạch tuyến tính dạng chính tắc 2- Định nghĩa đối ngẫu trong trường hợp tổng quát 3- Các đị nh lý về sự đối ngẫu a- Định lý 1 đối ngẫu yếu b- Định lý 2 c- Định lý 3 d- Định lý 4 sự đối ngẫu e- Định lý 5 tính bổ sung II- GIẢI THUẬT ĐỐI NGẪU 70 BÀI TOÁN ĐỐI NGẪU CHƯƠNG III BÀI TOÁN ĐỐI NGẪU I- 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. 1- Đố 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 tuyến tính dạng chính tắc min z x cTx Ax b 1 x 0 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 x1 x2 . xn 0 thuộc Rn chưa thoả ràng buộc của bài toán tức là b - Ax 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ỳ ý e 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 0 71 BÀI TOÁN ĐỐI NGẪU 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ỳ ý e Rm Bài toán này được gọi là bài toán đối .