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 6  BÀI TOÁN  TỐI ƯUTUYẾN TÍ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 QHTTT 
1. 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à S 1 và S 2 từ vật liệu V 1 và V 2 . 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 S 1 và S 2 để tổng thu nhập là lớn nhất? 
Mô hình toán học . Gọi x 1 , x 2 lần lượt là số đơn vị sản phẩm S 1 , S 2 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 = 50x 1 + 30x 2 ( 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ố x 1 và x 2 sao cho 
 f = 50x 1 + 30x 2 max, 
với các điều kiện 
 	4x 1 + 3x 2 1.200, 
	5x 1 + 2x 2 1.080, 	(1.1) 
	x 1 0, x 2 0. 
2. Bài toán xác định khẩu phần thức ăn 
Khẩ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 T 1 , T 2 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 x 1 , x 2 lần lượt là số kg thức ăn T 1 , T 2 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 = 20x 1 + 15x 2 ( 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ố x 1 và x 2 sao cho: 
 	 f = 20x 1 + 15x 2 min, 
với các điều kiện 
	3x 1 + x 2 60, 
 x 1 + x 2 40, 	(1.2) 
 x 1 + 2x 2 60, 
 x 1 0, x 2 0. 
3. Bài toán vận tải 
Cần vận chuyển xi măng từ 3 kho K 1 , K 2 , K 3 tới 4 công trường xây dựng T 1 , T 2 , T 3 , T 4 . 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 x ij là lượng xi măng cần vận chuyển từ kho K i (i = 1, 2, 3) tới công trường T j (j = 1, 2, 3, 4). 
Tổng chi phí vận chuyển (cần làm cực tiểu) bằng: 
f = 20x 11 + 18x 12 + 22x 13 + 25x 14 + 15x 21 + 25x 22 + 30x 23 + 15x 24 + 45x 31 + 30x 32 + 40x 33 + 35x 34 . 
Vậy bài toán nêu trên được phát biểu thành: 
Tìm các biến số x ij sao cho: 
	f min, 
với các điều kiện 
	 x 11 + x 12 + x 13 + x 14 = 170, 
	x 21 + x 22 + x 23 + x 24 = 200, 
 x 31 + x 32 + x 33 + x 34 = 180, 
 x 11 + x 21 + x 31 	 = 130, (1.3) 
 x 12 + x 22 + x 32	 = 160, 
 x 13 + x 23 + x 33 	 = 120, 
 x 14 + x 24 + x 34 	 = 140, 
 x ij 0, i = 1, 2, 3; j = 1, 2, 3, 4. 
6.2. CÁC DẠNG BÀI TOÁN QHTTT 
Qui 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át 
Bài toán này có dạng: Tìm các biến số x 1 , x 2 ,..., x n 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 = (x 1 , x 2 , ..., x n ) R n 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) = x 1 + 4x 2 + x 3 min 
Các ràng buộc: 
	 -5x 1 + x 2 – 2x 3 -12 
 x 1 + 2x 2 - x 3 2 
	 -x 1 + 4x 2 – 2x 3 1 
	 2x 1 + 3x 2 + 4x 3 ≥ 20 
	 x 1, x 2, x 3 ≥ 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à f min = 5,25 . 
6.3. BÀI TOÁN VẬN TẢI 
1. 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 ) A 1 , A 2 , ..., A m đến n địa điểm tiêu thụ ( điểm thu ) B 1 , B 2 , ..., B n . Biết rằng : 
 Số lượng hàng có ở A i là a i (i = 1,..., m), 
 Số lượng hàng cần ở B j là b j (j = 1,..., n), 
 Chi phí vận chuyển một đơn vị hàng từ A i đến B j là c ij (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 x ij là số lượng hàng cần vận chuyển từ A i đến B j . 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 EXCEL 
Ví dụ : Cần vận chuyển gạo từ 4 kho A 1 , A 2 , A 3 , A 4 đến 5 cửa hàng B 1 , B 2 , B 3 , B 4 , B 5 . 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 A 1 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 B 1 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 f min = 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ập 
6.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ông 
Bộ phận may	: 1650 giờ công 
Bộ phận hoàn chỉnh	: 540 giờ công	 
Chemis 
Bludong 
Jaket 
Giờ công bộ phận cắt 
0.2 
0.4 
0.3 
Giờ công bộ phận may 
0.3 
0.5 
0.4 
Giờ công bộ phận hoàn chỉnh 
0.1 
0.2 
0.1 
Đơn giá (USD)/1SP 
2.3 
3.6 
2.8 
Tố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ận 
Kho 
Số lượng bộ phận sử dụng khi lắp ráp 
TV 
Stereo 
Loa thùng 
 Khung 
450 
1 
1 
0 
 Đèn hình 
250 
1 
0 
0 
 Loa 
800 
2 
2 
1 
 Nguồn 
450 
1 
1 
0 
 Hệ thống điện 
600 
2 
1 
1 
Lợi nhuận đơn vị ($) 
75 
50 
35 
Tì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. G iải các bài toán quy hoạch tuyến tính sau: 
1. f = -x 1 - 2x 2 - 3x 3 + x 4 min, 
 	 x 1 + 2x 2 + 3x 3 = 15, 
 	2x 1 + x 2 + 5x 3 = 20, 
 	 x 1 + 2x 2 + x 3 + x 4 = 10, 
 	 x j 0 (j = 1,...,4). 
2. f = x 1 + 2x 2 - x 3 max,	 
	- x 1 + 4x 2 - 2x 3 6,	 
	 x 1 + x 2 + 2x 3 6,	 
	2x 1 - x 2 + 2x 3 = 4,	 
	x 1 0, x 2 0, x 3 0. 
3. f = -x 1 - x 2 + 1 max, 
	 x 1 - x 2 -1, 
	 3x 1 + 2x 2 6, 
	-3x 1 - x 2 -9, 
	 x 1 0, x 2 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 K 1 , K 2 , K 3 , K 4 đến 5 công trường T 1 , T 2 , T 3 , T 4 , T 5 . 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ệc 
Trình độ 
cán bộ 
Hệ số đánh giá năng lực (q ij ) 
máy trưởng 
máy 1 
máy 2 
máy 3 
Kỹ sư 
5 
4 
0 
0 
Trung cấp 
3 
5 
4 
0 
Công nhân 
0 
1 
5 
4 
Ghi chú : Giả thiết đánh giá năng lực cán bộ theo thang điểm 5, tức là q ij = 5: cán bộ i có năng lực hoàn thành xuất sắc công việc j, q ij = 4,3,2,1 tương ứng với các mức độ khác nhau, còn q ij = 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?