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

• Quản trị mạng
• Giáo trình Quy hoạch tuyến tính
• Quy hoạch tuyến tính
• Tài liệu Quy hoạch tuyến tính
• 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 đối ngẫu
• Quy hoạch tuyến tính dạng đặc biệt
• Phân loại quy hoạch tuyến tính
• Bài toán quy hoạch tuyến tính
• Tính chất bài toán quy hoạch tuyến tính
• Phương pháp đơn hình
• Thuật toán đơn hình
• Quy hoạch tuyến tính tổng quát
• Giải thuật đơn hình cơ bản
• Phương pháp biến giả cải biên
• Phương trình tuyến tính
• Bài toán vận tải
• Bài toán lập kế hoạch sản xuất
• Sư phạm toán
• Giáo trình toán
• Giáo trình Quy hoạch toán học
• Quy hoạch toán học
• Đại số tuyến tính
• Bài toán sản xuất đồng bộ
• Giáo trình đại học
• Bài tập quy hoạch tuyến tính
• Đại số tuyển tính
• Phương án cực biên
• Giải bài toán quy hoạch tuyến tính
• Phương pháp đơn hình đặc biệt
• Mô hình tối ưu tuyến tính
• Lập kế hoạch sản xuất
• Phân bố vốn đầu tư
• mô hình quy hoạch tuyến tính
• qui hoạch tuyến tính
• giáo trình MBA
• đề án tốt nghiệp
• đề cương bài giảng
• bài giảng quy hoạch tuyến tính
• Giáo trình Toán kinh tế
• Toán kinh tế
• Tài liệu Toán kinh tế
• Bài toán quy hoạch tuyến tính đối ngẫu
• Giáo trình Đại số tuyến tính
• Ma trận của một ánh xạ tuyến tính
• Dạng song tuyến tính
• Dạng toàn phương
• giáo trình toán học
• tài liệu học môn toán
• ý nghĩa hình học
• phương án tối ưu
• Toán cao cấp
• Song tuyến tính
• Kông gian vectơ
• Ánh xạ tuyến tính
• giáo trình đại cương
• qui hoạch tuyến tinh
• Bài toán phân công lao động
• Bài toán suy biến
• Tính toán hệ số hồi quy
• Quy hoạch thực nghiệm toàn phần
• Lập ma trận quy họach thực nghiệm
• Phương trình hồi quy tuyến tính
• Hệ số phương trình hồi quy