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

Chia sẻ: Nguyễn Thị Giỏi | Ngày: | Loại File: PDF | Số trang:11

Thêm vào BST

Báo xấu

1.951
lượt xem 436
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

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:

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: BÀI TOÁN QUI HOẠCH TUYẾN TÍNH

CHƯƠNG 1 : BÀI TOÁN QUI HOẠCH TUYẾN TÍNH VÀ PHƯƠNG PHÁ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ÁT III. BÀI TOÁN QUI HOẠCH TUYẾN TÍNH DẠNG CHÍNH TẮC IV. 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 TOP I -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ớ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: 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. TOP II - 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:
TOP III - BÀI TOÁN QUI HOẠCH TUYẾN TÍNH DẠNG CHÍNH TẮC
TOP IV - 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ất phươ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ạch tuyế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ạch tuyến tính tổng quát. TOP V - 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ài toá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 ma trậ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 .