Bài giảng Chương 7: Bài toán tối ưu tuyến tính

Một số ví dụ về bài toán quy hoạch tuyến tính, các dạng bài toán quy hoạch tuyến tính, bài toán vận tải là những nội dung trong bài giảng chương 7 "Bài toán tối ưu tuyến tính". Mời các bạn cùng tham khảo nội dung bài giảng để nắm bắt nội dung chi tiết.
Nội dung trích xuất từ tài liệu:
Bài giảng Chương 7: Bài toán tối ưu tuyến tính Sự cạnh tranh trong hoạt động sản xuất kinhChương 7 doanh luôn đòi hỏi các nhà quản lý doanh nghiệp phải thường xuyên lựa chọn phương ánBÀI TOÁN để đưa ra các quyết định nhanh chóng, chínhTỐI ƯU xác và kịp thời với những ràng buộc và hạn chếTUYẾN về các điều kiện liên quan tới tiềm năng của TÍNH doanh nghiệp, điều kiện thị trường, hoàn cảnh tự nhiên và xã hội… Việc lựa chọn phương án nào là tối ưu theo mục tiêu định trước là hết sức quan trọng. Nếu tất cả các yếu tố (biến số) liên quan đến khả năng, mục đích và quyết định lựa chọn đều có mối quan hệ tuyến tính thì ta có thể sử dụng mô hình tối ưu tuyến tính hay quy hoạch tuyến tính (QHTT) để mô tả, phân tích và tìm lời giải tối ưu của vấn đề đặt ra. 1Trong môn học Toán kinh tế việc giải bài toán QHTTthường được thực hiện bằng thuật toán đơn hình.Trong phần mềm Excel bài toán QHTT được giảinhanh chóng qua công cụ cài thêm là Solver.5.1. MỘT SỐ VÍ DỤ VỀ BÀI TOÁN QHTTT1. Bài toán lập kế hoạch sản xuất:Một xí nghiệp dự định sản xuất hai loại sản phẩm là S1và S2 từ vật liệu V1 và V2. Số liệu được cho ở bảngsau:Hỏi xí nghiệp nên sản xuất bao nhiêu đơn vị sản phẩmS1 và S2 để tổng thu nhập là lớn nhất?` 2Mô hình toán học. Gọi x1, x2 lần lượt là số đơn vị sảnphẩm S1, S2 cần sản xuất.Tổng thu nhập của xí nghiệp (cần làm cực đại) sẽ là f = 50000*X1 + 30000*X2.Vậy bài toán đặt ra được phát biểu thành: Tìm các biếnsố x1 và x2 sao cho f = 50000 * X1 + 30000 * X2  max,với các điều kiện 4x1 + 3x2  1.200, 5x1 + 2x2  1.080, (1.1) x1  0, x2  0. 32. Bài toán xác định khẩu phần thức ănKhẩu phần thức ăn/ 1 bửa ăn của một xí nghiệp chănnuôi như sau:Hỏi xí nghiệp cần mua bao nhiêu kg T1, T2 cho mỗibữa ăn, sao cho vừa đảm bảo tốt dinh dưỡng cho bữaăn của gia súc, vừa để tổng số tiền chi mua thức ăn lànhỏ nhất? 4Mô hình toán học. Gọi x1, x2 lần lượt là số kg thứcăn T1, T2 cần mua cho mỗi bữa ăn.Số tiền chi mua thức ăn (cần làm cực tiểu) bằng f = 20x1 + 15x2 (ngàn đồng).Vậy bài toán nêu trên được phát biểu thành: Tìm cácbiến số x1 và x2 sao cho: f = 20x1 + 15x2  min,với các điều kiện 3x1+ x2  60, x1 + x2  40, (1.2) x1 + 2x2  60, x1  0, x2  0. 53. Bài toán vận tảiCần vận chuyển xi măng từ 3 kho K1, K2, K3 tới 4công trường xây dựng T1, T2, T3, T4. Số liệu cho ởbảng sau:Vấn đề là tìm kế hoạch vận chuyển xi măng từ cáckho tới các công trường sao cho mọi kho phát hếtlượng xi măng có, mọi công trường nhận đủ lượng ximăng cần và tổng chi phí vận chuyển là nhỏ nhất? 6Mô hình toán học. Gọi xij là lượng xi măng cần vậnchuyển từ kho Ki (i = 1, 2, 3) tới công trường Tj(j = 1, 2, 3, 4).Ham muc tieu : Tổng chi phí vận chuyển be nhat:f = 20x11 + 18x12 + 22x13 + 25x14 + 15x21 + 25x22 +30x23 + 15x24 + 45x31 + 30x32 + 40x33 + 35x34=>minVậy bài toán nêu trên được phát biểu thành: 7Tìm các biến số xij sao cho: f  min,với các điều kiện x11 + x12 + x13 + x14 = 170, x21 + x22 + x23 + x24 = 200, x31 + x32 + x33 + x34 = 180, x11 + x21 + x31 = 130, (1.3) x12 + x22 + x32 = 160, x13 + x23 + x33 = 120, x14 + x24 + x34 = 140, xij  0, i = 1, 2, 3; j = 1, 2, 3, 4. 85.2. CÁC DẠNG BÀI TOÁN QHTTTQui hoạch tuyến tính là bài toán tìm cực tiểu (hay cựcđại) của một hàm tuyến tính thỏa mãn các phương trìnhvà/hoặc bất phương trình tuyến tính.1. Bài toán tổng quátBài toán này có dạng: Tìm các biến số x1, x2,..., xn sao ncho: f ( x )   c j x j  min (hay max) (1.4) j 1Thỏa mãn các điều kiện:    n  =  b , i=1,2,...,m,  ij j   i a x (1.5)  j=1     ...