BÀI TOÁN QUI HOẠCH TUYẾN TÍNH

Xí nghiệp sản xuất càc mặt hàng A, B, C, D từ các loại nguyên liệu I, II, III với lượng dự trữ tương ứng là u1, u2, u3 (đơn vị nguyên liệu). Bảng sau cho biết lợi nhuận thu được và chi phí nguyên liệu cho mỗi đơn vị sản phẩm:
Nội dung trích xuất từ tài liệu:
BÀI TOÁN QUI HOẠCH TUYẾN TÍNHCHƯƠNG 1 : BÀI TOÁN QUI HOẠCH TUYẾN TÍNH VÀ PHƯƠNGPHÁP ĐƠN HÌNH BÀI 1: BÀI TOÁN QUI HOẠCH TUYẾN TÍNH I. VÍ DỤ MỞ ĐẦU II. BÀI TOÁN QUI HOẠCH TUYẾN TÍNH TỔNG QUÁTIII. BÀI TOÁN QUI HOẠCH TUYẾN TÍNH DẠNG CHÍNH TẮCIV. BÀI TOÁN QUI HOẠCH TUYẾN TÍNH DẠNG CHUẨN TẮC V. BÀI TOÁN QUI HOẠCH TUYẾN TÍNH DẠNG MA TRẬN BÀI 1: BÀI TOÁN QUI HOẠCH TUYẾN TÍNH TOPI -Ví dụ mở đầu ( Bài toán lập kế họach sản xuất ) Xí nghiệp sản xuất càc mặt hàng A, B, C, D từ các loại nguyên liệu I, II, III vớilượng dự trữ tương ứng là u1, u2, u3 (đơn vị nguyên liệu). Bảng sau cho biết lợi nhuậnthu được và chi phí nguyên liệu cho mỗi đơn vị sản phẩm: Lập kế hoạch sản xuất các mặt hàng sao cho: a) Tổng lợi nhuận thu được lớn nhất . b) Sử dụng hết nguyên liệu, riêng loại nguyên liệu III có thể dư. c) Tổng số lượng sản phẩm A và D không nhỏ hơn u4 . Phân tích mô hình: Bài toán trên được gọi là bài toán Qui hoạch tuyến tính. TOPII - Bài toán Qui hoạch tuyến tính tổng quát Bài toán Qui hoạch tuyến tính tổng quát được phát biểu như sau: TOPIII - BÀI TOÁN QUI HOẠCH TUYẾN TÍNH DẠNG CHÍNH TẮC TOPIV - BÀI TOÁN QUI HOẠCH TUYẾN TÍNH DẠNG CHUẨN TẮC Bài toán Qui hoạch tuyến tính dạng chuẩn tắc có tất cả điều kiện ràng buộc là bấtphương trình và tất cả các ẩn số đều không âm :Ðịnh lí 1 Bài toán Qui hoạch tuyến tính tổng quát có thể đưa về dạng chính tắc hoặc dạng chuẩn tắc .Chứng minh Trước hết , ta chứng tỏ rằng bài toán Qui hoạch tuyến tính tổng quát có thể đưa vềdạng chính tắc . Ðịnh lí 1 cho thấy rằng chỉ cần xây dựng thuật toán giải cho bài toán Qui hoạchtuyến tính dạng chính tắc ( hoặc chuẩn tắc ) và từ đó có thể giải được bài toán Qui hoạchtuyến tính tổng quát. TOPV - BÀI TOÁN QUI HOẠCH TUYẾN TÍNH DẠNG MA TRẬN Trong nhiều trường hợp , để thuận tiện trong việc trình bày , ta có thể viết các bàitoán Qui hoạch tuyến tính dạng chính tắc ( 1-3 ) và dạng chuẩn tắc ( 1-4 ) dưới dạng matrận . Khi đó bài toán (1- 6 ) được viêt thành dạng ma trận ( 1-8 ) hoặc (1- 9 ) , trong đóhàm mục tiêu là g , n= 9 , m = 5 .