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

0
1.874
lượt xem
434
download

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

Mô tả tài liệu
  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ủ đề:
Lưu

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

  1. 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 .
  2. 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:
  3. TOP III - BÀI TOÁN QUI HOẠCH TUYẾN TÍNH DẠNG CHÍNH TẮC
  4. 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 .
  5. Ðị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 .
  6. 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 .

CÓ THỂ BẠN MUỐN DOWNLOAD

Đồng bộ tài khoản