Bài giảng Tin học ứng dụng - Chương 6: Bài toán tối ưu tuyến tính - Lê Hữu Hùng

Chương 6BÀI TOÁN TỐI ƯUTUYẾNTÍNH Sự cạnh tranh trong hoạt động sản xuất kinh 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 án để đưa ra các quyết định nhanh chóng, chính xác và kịp thời với những ràng buộc và hạn chế về các điều kiện liên quan tới tiềm năng của 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.Trong môn học Toán kinh tế việc giải bài toán QHTT thườ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ải nhanh chóng qua công cụ cài thêm là Solver.6.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à S1 và S2 từ vật liệu V1 và V2. Số liệu được cho ở bảng sau:Hỏi xí nghiệp nên sản xuất bao nhiêu đơn vị sản phẩm S1 và S2 để tổng thu nhập là lớn nhất?Mô hình toán học. Gọi x1, x2 lần lượt là số đơn vị sản phẩ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 = 50x1 + 30x2 (ngàn đồng).Vậy bài toán đặt ra được phát biểu thành: Tìm các biến số x1 và x2 sao cho f = 50x1 + 30x2  max, với các điều kiện 4x1 + 3x2  1.200, 5x1 + 2x2  1.080, (1.1) x1  0, x2  0. 2. 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ăn nuôi như sau:Hỏi xí nghiệp cần mua bao nhiêu kg T1, T2 cho mỗi bữ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? Mô 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ác biế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.3. Bài toán vận tảiCầ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 ở bảng sau:Vấn đề là tìm kế hoạch vận chuyển xi măng từ các kho tới các công trường sao cho mọi kho phát hết lượng xi măng có, mọi công trường nhận đủ lượng xi măng cần và tổng chi phí vận chuyển là nhỏ nhất?Mô hình toán học. Gọi xij là 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).Tổng chi phí vận chuyển (cần làm cực tiểu) bằng: f = 20x11 + 18x12 + 22x13 + 25x14 + 15x21 + 25x22 + 30x23 + 15x24 + 45x31 + 30x32 + 40x33 + 35x34. Vậy bài toán nêu trên được phát biểu thành: Tì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.6.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ình và/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 cho: Thỏa mãn các điều kiện: f gọi là hàm mục tiêu, (1.5) là các ràng buộc chính (các PT và/hoặc bpt tuyến tính). (1.6) là các ràng buộc về biến (có thể không âm, không dương hay tùy ý). Điểm x = (x1, x2, ..., xn)  Rn thỏa mãn (1.5), (1.6) gọi là phương án của bài toán. Tập hợp tất cả các phương án, ký hiệu là D, gọi là miền ràng buộc hay miền chấp nhận được. Một phương án thoả mãn (1.4) gọi là một phương án tối ưu hay lời giải của bài toán đã cho.2. Bài toán dạng chí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).Ví dụ: mô hình bài toán vận tải nêu ở (1.1) có dạng chính tắc.3. Bài toán dạng chuẩn tắc(ràng buộc chính chỉ gồm các bất đẳng thức  đối với bài toán min hoặc  đối với bài toán max, và mọi biến đều không âm). Ví dụ: mô hình bài toán xác định khẩu phần thức ăn hay mô hình bài toán lập kế hoạch sản xuất đã xét ở (1.1) có dạng chuẩn tắc.Giải quy hoạch tuyến tính trên EXCELĐể giải các bài toán QHTT, phần mềm Excel cung cấp cho ta một công cụ khá hữu ích là Solver trong Menu Tools của Excel. Các bài toán QHTT dạng chính tắc và dạng chuẩn chỉ là trường hợp riêng của bài toán QHTT dạng tổng quát. Vì thế ở đây ta sẽ xem xét cách giải quyết bài toán QHTT dạng tổng quát.Ví dụ: Xét bài toán QHTT sau: f (x) = x1 + 4x2 + x3  minCá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. 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 bảng tính dưới dạ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á trị hàm mục tiêu tạ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á trị vế trái của 4 ràng buộc của bài toán.Bước 3: Dùng lệnh Tools | Solver, xuất hiện hộp thoại Solver Parameters: Mục Set Target Cell: chọn ô đích (chứa giá trị hàm mục tiêu), trong ví dụ chọn ô E3.Mục Equal To: chọn Max nếu cực đại hàm mục tiêu; chọn Min nếu cực tiểu hàm mục tiêu; chọn Value of và nhập giá trị nếu muốn ô đích bằng 1 giá trị nhất định, trong ví dụ chọn Min. Mục By Changing Cells: chọn các ô chứa các biến của bài toán, trong ví dụ chọn khối ô B3:D2. Nháy nút Add để nhập tất cả 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 thoại Solver Options, đánh dấu kiểm vào mục Assume Linear Model (khẳng định mô hình của ta là tuyến tính.)Bước 4: Trong hộp thoại Solver Parameters, nháy vào nút Solver để bắt đầu giải bài toán. Giải xong bài toán xuất hiện hộp thoại Solver Results.Chọn mục Keep Solver Solution (giữ lại lời giải), nháy OK, kết quả giải bài toán nằm ở các ô B2:D2.Kết quả ta có phương án tối ưu là x* = (0,5; 0; 4,75), và trị tối ưu là fmin = 5,25.6.3. BÀI TOÁN VẬN TẢI1. Nội dung bài toán: Giả sử cần vận chuyển một loại hàng thuần nhất (vật tư, lương thực, ...) từ m địa điểm cung cấp (điểm phát) A1, A2, ..., Am đến n địa điểm tiêu thụ (điểm thu) B1, B2, ..., Bn. Biết rằng : Số lượng hàng có ở Ai là ai (i = 1,..., m), Số lượng hàng cần ở Bj là bj (j = 1,..., n), Chi phí vận chuyển một đơn vị hàng từ Ai đến Bj là cij (i = 1,...,m; j = 1,...,n).Vấn đề đặt ra: Lập kế hoạch vận chuyển hàng từ các điểm phát đến các địa điểm thu để tổng chi phí vận chuyển bé nhất và thoả mãn nhu cầu thu phát.Đây là một trong những bài toán điển hình và có nhiều ứng dụng nhất của QHTT. Bài toán này không có gì phức tạp nếu mạng lưới giao thông tương đối đơn giản và số địa điểm cung cấp, tiêu thụ không nhiều lắm. Tuy nhiên với những mạng lưới đường giao thông phức tạp thì bằng kinh nghiệm và trực giác khó có thể tìm ra được phương án tối ưu. Khi ấy, cần sử dụng các phương pháp, dựa vào tính chất đặc thù của bài toán để tìm phương án tối ưu.Mô hình toán học của bài toán:Gọi xij là số lượng hàng cần vận chuyển từ Ai đến Bj. Ta có: Mô hình toán học của bài toán là:Bài toán vận tải là một dạng đặc biệt của qui hoạch tuyến tính, do đó có thể sử dụng PP đơn hình để giải. Tuy nhiên do bài toán có cấu trúc đặc biệt nên người ta đã đề ra nhiều phương pháp giải khác có hiệu quả hơn.Giải Bài toán vận tải trên EXCELVí dụ: Cần vận chuyển gạo từ 4 kho A1, A2, A3, A4 đến 5 cửa hàng B1, B2, B3, B4, B5. Cho biết lượng gạo có ở mỗi kho, lượng gạo cần ở mỗi cửa hàng và giá cước vận chuyển (ngàn đồng) 1 tạ gạo từ mỗi kho tới mỗi cửa hàng như sau: Hãy lập kế hoạch vận chuyển gạo từ các kho tới các cửa hàng sao cho mọi kho phát hết gạo có, mọi cửa hàng nhận đủ gạo cần và tổng chi phí vận chuyển là bé nhất ? Các bước thực hiện giải bài toán bằng Solver:Bước 1: Nhập dữ liệu bài toán vào bảng tính dưới dạng sau:Trong đó: Khối B2:F5 là ma trận chi phí vận chuyển. Khối B8:F11 là phương án vận chuyển (giá trị ban đầu cho tất cả bằng 1). Khối H8:H11 là khả năng của các điểm phát. Khối B13:F13 là nhu cầu của các điểm thu.Bước 2: Tính giá trị hàm mục tiêu trong ô H3 theo công thức: H3 =SUMPRODUCT(B2:F5;B8:F11)Tính lượng hàng phát của điểm phát A1 tại ô G8 theo công thức: G8 =SUM(B8:F8), sao chép công thức vào các ô G9:G12.Tính lượng hàng nhận được của điểm thu B1 tại ô B12 theo công thức: B12 =SUM(B8:B11), sao chép công thức vào các ô C12:F12.Bước 3: Dùng lệnh Tools | Solver với các lựa chọn hàm mục tiêu và các ràng buộc:Sau khi nhập xong các ràng buộc, nháy nút options, hiện hộp thoại Solver Options, đánh dấu kiểm vào mục Assume Linear Model.Bước 4: Trong hộp thoại Solver Parameters, nháy vào nút Solver để bắt đầu giải bài toán. Giải xong bài toán xuất hiện hộp thoại Solver Results, chọn mục Keep Solver Solution, nháy OK. Kết quả nhận được:Giá trí tối ưu hàm mục tiêu bằng fmin = 2420 (đvcp). Phương án vận chuyển tối ưu: x[1,1] = 35, x[1,4] = 40, X[2,2]=40, X[2,3]=60, X[3,3]=25, X[3,5]=40, X[4,1]=40, X[4,2] =20. Kết quả trong bảng tính:Bài tập6.1. Lập mô hình toán học và giải các bài toán sau:1. Công ty may mặc Long Vũ hiện đang lập kế hoạch sản xuất 3 mặt hàng Áo Jaket, Áo Chemis và Áo Bludong. Được biết chi phí giờ công sản xuất của từng mặt hàng qua 3 công đoạn cắt, may, hoàn chỉnh như sau:Năng lực tối đa của các bộ phận như sau:Bộ phận cắt : 1250 giờ côngBộ phận may : 1650 giờ côngBộ phận hoàn chỉnh : 540 giờ công ChemisBludongJaketGiờ công bộ phận cắt0.20.40.3Giờ công bộ phận may0.30.50.4Giờ công bộ phận hoàn chỉnh0.10.20.1Đơn giá (USD)/1SP2.33.62.8Tối thiểu trong một tháng mỗi loại phải sản xuất 200 sản phẩm.Hãy tính kế hoạch sản xuất mỗi loại sản phẩm bao nhiêu để đạt tổng giá trị sản phẩm lớn nhất và vẫn bảo đảm các điều kiện về năng lực sản phẩm và quy định số lượng sản phẩm tối thiểu.Tên bộ phậnKhoSố lượng bộ phận sử dụng khi lắp rápTVStereoLoa thùng Khung450110 Đèn hình250100 Loa800221 Nguồn450110 Hệ thống điện600211Lợi nhuận đơn vị ($)755035Tìm giải pháp lắp ráp số lượng máy thu hình TV, Stereo, Loa thùng từ số bộ phận còn trong kho để đem lại tổng lợi nhuận cao nhất?2. Nhà máy sản xuất thiết bị nghe nhìn điện tử Hanel lắp ráp thành phẩm máy thu hình TV, Stereo và Loa thùng từ các bộ phận khác nhau. Tên các bộ phận và số lượng còn trong kho của chúng được bộ phận KHO cung cấp trong bảng sau:6.2. Giải các bài toán quy hoạch tuyến tính sau:1. f = -x1 - 2x2 - 3x3 + x4  min, x1 + 2x2 + 3x3 = 15, 2x1 + x2 + 5x3 = 20, x1 + 2x2 + x3 + x4 = 10, xj  0 (j = 1,...,4).2. f = x1 + 2x2 - x3  max, -x1 + 4x2 - 2x3  6, x1 + x2 + 2x3  6, 2x1 - x2 + 2x3 = 4, x1 0, x2  0, x3  0. 3. f = -x1 - x2 + 1  max, x1 - x2  -1, 3x1 + 2x2  6, -3x1 - x2  -9, x1 0, x2  0.6.3. Lập mô hình toán học và giải bài toán sau:Cần vận chuyển xi măng từ 4 kho K1, K2, K3, K4 đến 5 công trường T1, T2, T3, T4, T5. Cho biết số lượng xi măng có ở mỗi kho, số lượng xi măng cần ở mỗi công trường và giá cước vận chuyển (ngàn đồng) 1 bao xi măng từ mỗi kho tới mỗi công trường như sau:Hãy lập kế hoạch vận chuyển xi măng từ các kho tới các công trường sao cho mọi kho phát hết xi măng có, mọi công trường nhận đủ xi măng cần và tổng chi phí vận chuyển là bé nhất ? 6.4. Giải các bài toán sau:1. Một công ty vận tải biển cần 110 người để bố trí 10 máy trưởng, 25 thợ máy 1, 30 thợ máy 2 và 45 thợ máy 3. Phòng tổ chức công ty tìm được 90 người, gồm 25 kỹ sư máy, 20 trung cấp kỹ thuật và 45 công nhân. Phòng tổ chức đánh giá khả năng của cán bộ theo công việc như ở bảng sau:Vậy cần bố trí sao cho sử dụng hết năng lực của mọi người. Công việcTrình độcán bộHệ số đánh giá năng lực (qij)máy trưởngmáy 1máy 2máy 3Kỹ sư5400Trung cấp3540Công nhân0154Ghi chú: Giả thiết đánh giá năng lực cán bộ theo thang điểm 5, tức là qij = 5: cán bộ i có năng lực hoàn thành xuất sắc công việc j, qij = 4,3,2,1 tương ứng với các mức độ khác nhau, còn qij = 0 là cán bộ i hoàn toàn không thể làm công việc j.2. Một đội làm rau gồm 23 lao động nữ, chia làm 3 loại: loại A và B có 10 người; loại C có 3 người. Đội đó cần bố trí 3 người đi hái rau, 8 người làm cỏ rau và 12 người trồng rau. Năng suất lao động của từng loại được cho trong bảng sau:Vậy phải phân công như thế nào để năng suất đạt được cao nhất?