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

Chia sẻ: Nguyễn Minh đức | Ngày: | Loại File: PDF | Số trang:33

Thêm vào BST

Báo xấu

245
lượt xem 21
download

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

Một số ví dụ về bài toán quy hoạch tuyến tính, các dạng bài toán quy hoạch tuyến tính, bài toá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.

Chủ đề:

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

Lưu

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

Sự cạnh tranh trong hoạt động sản xuất kinh Chương 7 doanh luôn đòi hỏi các nhà quản lý doanh nghiệp phải thường xuyên lựa chọn phương án BÀI TOÁN để đưa ra các quyết định nhanh chóng, chính TỐI ƯU xác và kịp thời với những ràng buộc và hạn chế TUYẾN về các điều kiện liên quan tới tiềm năng của TÍNH doanh nghiệp, điều kiện thị trường, hoàn cảnh tự nhiên và xã hội… Việc lựa chọn phương án nào là tối ưu theo mục tiêu định trước là hết sức quan trọng. Nếu tất cả các yếu tố (biến số) liên quan đến khả năng, mục đích và quyết định lựa chọn đều có mối quan hệ tuyến tính thì ta có thể sử dụng mô hình tối ưu tuyến tính hay quy hoạch tuyến tính (QHTT) để mô tả, phân tích và tìm lời giải tối ưu của vấn đề đặt ra. 1
Trong môn học Toán kinh tế việc giải bài toán QHTT thường được thực hiện bằng thuật toán đơn hình. Trong phần mềm Excel bài toán QHTT được giải nhanh chóng qua công cụ cài thêm là Solver. 5.1. MỘT SỐ VÍ DỤ VỀ BÀI TOÁN QHTTT 1. Bài toán lập kế hoạch sản xuất: Một xí nghiệp dự định sản xuất hai loại sản phẩm là S1 và S2 từ vật liệu V1 và V2. Số liệu được cho ở bảng sau: Hỏi xí nghiệp nên sản xuất bao nhiêu đơn vị sản phẩm S1 và S2 để tổng thu nhập là lớn nhất?` 2
Mô hình toán học. Gọi x1, x2 lần lượt là số đơn vị sản phẩm S1, S2 cần sản xuất. Tổng thu nhập của xí nghiệp (cần làm cực đại) sẽ là f = 50000*X1 + 30000*X2. Vậy bài toán đặt ra được phát biểu thành: Tìm các biến số x1 và x2 sao cho f = 50000 * X1 + 30000 * X2  max, với các điều kiện 4x1 + 3x2  1.200, 5x1 + 2x2  1.080, (1.1) x1  0, x2  0. 3
2. Bài toán xác định khẩu phần thức ăn Khẩu phần thức ăn/ 1 bửa ăn của một xí nghiệp chăn nuôi như sau: Hỏi xí nghiệp cần mua bao nhiêu kg T1, T2 cho mỗi bữa ăn, sao cho vừa đảm bảo tốt dinh dưỡng cho bữa ăn của gia súc, vừa để tổng số tiền chi mua thức ăn là nhỏ nhất? 4
Mô hình toán học. Gọi x1, x2 lần lượt là 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 làm cực tiểu) bằng f = 20x1 + 15x2 (ngàn đồng). Vậy bài toán nêu trên được phát biểu thành: Tìm các biến số x1 và x2 sao cho: f = 20x1 + 15x2  min, với các điều kiện 3x1+ x2  60, x1 + x2  40, (1.2) x1 + 2x2  60, x1  0, x2  0. 5
3. Bài toán vận tải Cần vận chuyển xi măng từ 3 kho K1, K2, K3 tới 4 công trường xây dựng T1, T2, T3, T4. Số liệu cho ở bảng sau: Vấn đề là tìm kế hoạch vận chuyển xi măng từ các kho tới các công trường sao cho mọi kho phát hết lượng xi măng có, mọi công trường nhận đủ lượng xi măng cần và tổng chi phí vận chuyển là nhỏ nhất? 6
Mô hình toán học. Gọi xij là lượng xi măng cần vận chuyể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 phí vận chuyển be nhat: f = 20x11 + 18x12 + 22x13 + 25x14 + 15x21 + 25x22 + 30x23 + 15x24 + 45x31 + 30x32 + 40x33 + 35x34=> min Vậy bài toán nêu trên được phát biểu thành: 7
Tìm các biến số xij sao cho: f  min, với cá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. 8
5.2. CÁC DẠNG BÀI TOÁN QHTTT Qui hoạch tuyến tính là bài toán tìm cực tiểu (hay cực đại) của một hàm tuyến tính thỏa mãn các phương trình và/hoặc bất phương trình tuyến tính. 1. Bài toán tổng quát Bài toán này có dạng: Tìm các biến số x1, x2,..., xn sao n cho: f ( x )   c j x j  min (hay max) (1.4) j 1 Thỏa mãn các điều kiện:    n  =  b , i=1,2,...,m,  ij j   i a x (1.5)  j=1      x   0, j=1,2,...,n  n. (1.6)  j   1 9
 f gọi là hàm mục tiêu,  (1.5) là các ràng buộc chính (các PT và/hoặc bpt tuyến tính).  (1.6) là các ràng buộc về biến (có thể không âm, không dương hay tùy ý). Điểm x = (x1, x2, ..., xn)  Rn thỏa mãn (1.5), (1.6) gọi là phương án của bài toán. Tập hợp tất cả các phương án, ký hiệu là D, gọi là miền ràng buộc hay miền chấp nhận được. Một phương án thoả mãn (1.4) gọi là một phương án tối ưu hay lời giải của bài toán đã cho. 10
2. Bài toán dạng chính tắc (ràng buộc chính chỉ là các đẳng thức và mọi biến đều không âm). Ví dụ: mô hình bài toán vận tải nêu ở (1.1) có dạng chính tắc. 11
3. Bài toán dạng chuẩn tắc (ràng buộc chính chỉ gồm các bất đẳng thức  đối với bài toán min hoặc  đối với bài toán max, và mọi biến đều không âm). Ví dụ: mô hình bài toán xác định khẩu phần thức ăn hay mô hình bài toán lập kế hoạch sản xuất đã xét ở (1.1) có dạng chuẩn tắc. 12
Giải quy hoạch tuyến tính trên EXCEL Để giải các bài toán QHTT, phần mềm Excel cung cấp cho ta một công cụ khá hữu ích là Solver trong Menu Tools của Excel. Các bài toán QHTT dạng chính tắc và dạng chuẩn chỉ là trường hợp riêng của bài toán QHTT dạng tổng quát. Vì thế ở đây ta sẽ xem xét cách giải quyết bài toán QHTT dạng tổng quát. Ví dụ: Xét bài toán QHTT sau: f (x) = x1 + 4x2 + x3  min Các ràng buộc: -5x1 + x2 - 2x3  -12 x1 + 2x2 - x3  2 -x1 + 4x2 - 2x3  1 2x1 + 3x2 + 4x3 ≥ 20 x1, x2, x3 ≥ 0. 13
Các bước thực hiện giải bài toán: Bước 1: Nhập dữ liệu bài toán vào bảng tính dưới dạng sau: Phương án ban đầu X = (1, 1, 1) có thể không chấp nhận được. Bước 2: Tính giá trị hàm mục tiêu tại ô E3 bằng công thức: E3 =SUMPRODUCT($B$2:$D$2;B3:D3) Copy công thức từ ô E3 sang dãy các ô E4:E7 để tính giá trị vế trái của 4 ràng buộc của bài toán. 14
Bước 3: Dùng lệnh Tools | Solver, xuất hiện hộp thoại Solver Parameters: Mục Set Target Cell: chọn ô đích (chứa giá trị hàm mục tiêu), trong ví dụ chọn ô E3. Mục Equal To: chọn Max nếu cực đại hàm mục tiêu; chọn Min nếu cực tiểu hàm mục tiêu; chọn Value of và nhập giá trị nếu muốn ô đích bằng 1 giá trị nhất định, trong ví dụ chọn Min. 15
Mục By Changing Cells: chọn các ô chứa các biến của bài toán, trong ví dụ chọn khối ô B3:D2. Nháy nút Add để nhập tất cả các ràng buộc vào khung Subject to the Contraints. Sau khi nhập xong các ràng buộc , nháy nút options, hiện hộp thoại Solver Options, đánh dấu kiểm vào mục Assume Linear Model (khẳng định mô hình của ta là tuyến tính.) 16
Bước 4: Trong hộp thoại Solver Parameters, nháy vào nút Solver để bắt đầu giải bài toán. Giải xong bài toán xuất hiện hộp thoại Solver Results. Chọn mục Keep Solver Solution (giữ lại lời giải), nháy OK, kết quả giải bài toán nằm ở các ô B2:D2. Kết quả ta có phương án tối ưu là x* = (0,5; 0; 4,75), và trị tối ưu là fmin = 5,25. 17
5.3. BÀI TOÁN VẬN TẢI 1. Nội dung bài toán: Giả sử cần vận chuyển một loại hàng thuần nhất (vật tư, lương thực, ...) từ m địa điểm cung cấp (điểm phát) A1, A2, ..., Am đến n địa điểm tiêu thụ (điểm thu) B1, B2, ..., Bn. Biết rằng : Số lượng hàng có ở Ai là ai (i = 1,..., m), Số lượng hàng cần ở Bj là bj (j = 1,..., n), Chi phí vận chuyển một đơn vị hàng từ Ai đến Bj là cij (i = 1,...,m; j = 1,...,n). Vấn đề đặt ra: Lập kế hoạch vận chuyển hàng từ các điểm phát đến các địa điểm thu để tổng chi phí vận chuyển bé nhất và thoả mãn nhu cầu thu phát. 18
Đây là một trong những bài toán điển hình và có nhiều ứng dụng nhất của QHTT. Bài toán này không có gì phức tạp nếu mạng lưới giao thông tương đối đơn giản và số địa điểm cung cấp, tiêu thụ không nhiều lắm. Tuy nhiên với những mạng lưới đường giao thông phức tạp thì bằng kinh nghiệm và trực giác khó có thể tìm ra được phương án tối ưu. Khi ấy, cần sử dụng các phương pháp, dựa vào tính chất đặc thù của bài toán để tìm phương án tối ưu. 19
Mô hình toán học của bài toán: Gọi xij là số lượng hàng cần vận chuyển từ Ai đến Bj. Ta có: m n  c x i 1 j 1 ij ij : Toång chi phí vaän chuyeån, n x j 1 ij : Soá löôïng haøng chôû ñi töø A i , m x i 1 ij : Soá löôïng haøng chôû tôùi Bj ,  Mô hình toán học của bài toán là: 20