Chương 1. BÀI TOÁN QUI HOẠCH TUYẾN TÍNH 1.1 MỘT SỐ VÍ DỤ DẪN ĐẾN BÀI TOÁN QUI HOẠCH TUYẾN TÍNH 1.1 Bài toán lập kế hoạch sản xuất Công ty Toàn Thắng dự định trong kế hoạch năm sẽ sản xuất n loại sản phẩm SP1, SP2,…,SPn. Biết định mức kinh tế - kỹ thuật, mức dự trữ các yếu tố sản xuất và lợi nhuận trên mỗi đơn vị sản phẩm cho trong sau: 2 Các yếu Định mức kinh tế - kỹ thuật Mức dự tố sản SP1 SP2 … SPn trữ xuất I1 b1 a11 a12 … a1n I2 b2 a21 a22 … a2n. Im bm am1 am2 … amn Lợi nhuận/Đơn vị P1 P2 … Pn sản phẩm 3 Xác định sản lượng sản phẩm từng loại mà công ty Toàn Thắng cần sản xuất trong kế hoạch năm sao cho tổng lợi nhuận lớn nhất., xn là lượng sản phẩm tương ứng SP1, SP2 ,., SPn cần sản xuất trong năm kế hoạch.
Tổng lợi nhuận tương ứng với kế hoạch 1 1 P2 x2 . Pn xn sản xuất trên là: Px Với yêu cầu tối đa hóa lợi nhuận: 1 1 P2 x2 . Pn xn Max Px Để sản xuất ra lượng sản phẩm các loại thì tổng mức tiêu hao các yếu tố sản xuất là: 5 Yếu tố sản xuất loại 1: a11 x1 a12 x2 . a1n xn Yếu tố sản xuất loại 2: a21x1 a22 x2 .
a2 n xn Ta có thể thiết lập tổng mức tiêu hao các yếu tố sản xuất từng loại. Ứng với khả năng dự trữ tối đa các yếu tố sản xuất, ta có: a11 x1 a12 x2 . a2 n xn b2 am1 x1 am 2 x2 . amn xn bm Vì lượng sản phẩm cần sản xuất trong năm kế hoạch là lượng không âm, nên x1 , x2 ,., xn 0 6 Các bước lập bài toán quy hoạch tuyến tính 1.
Xác định phương án 2. Xác định hàm mục tiêu 3. Xác định các ràng buộc 7 Ví dụ: Nhân dịp Tết Trung Thu, xí nghiệp sản xuất bánh Trăng muốn sản xuất ba loại bánh: Đậu xanh, thập cẩm, bánh dẻo nhân đậu xanh. Để sản xuất ba loại bánh này, xí nghiệp cần: đường, đậu, bột, trứng, mứt, lạp xưởng … Giả sử số đường có thể chuẩn bị được là 500 kg, đậu là 300 kg, các nguyên liệu khác muốn bao nhiêu cũng có.
Lượng đường, đậu cần thiết và số tiền lãi khi bán một chiếc bánh cho mỗi loại cho trong bảng sau: 8 Bánh Bánh đậu Bánh thập Bánh dẻo xanh cẩm Nguyên liệu Đường:500kg 0,06 kg 0,04 kg 0,07 kg Đậu: 300 kg 0,08 kg 0 kg 0,04 kg Lãi 2000đ 1700đ 1800đ 9 Vậy ta có được mô hình của bài toán như sau: Gọi x1 , x2 , x3 lần lượt là số chiếc bánh đậu xanh, thập cẩm, bánh dẻo nhân đậu xanh sẽ sản xuất.2 Bài toán xác định công thức pha trộn Công ty chăn nuôi Vĩnh Nguyên cần pha trộn một loại thức ăn hỗn hợp cho gia súc từ n loại nguyên liệu thô (NL1, NL2,…, NLn). Phân tích các nguyên liệu trên, ta biết hàm lượng các dưỡng chất có trong từng loại nguyên liệu. Đồng thời, ta cũng biết các yêu cầu về mức dinh dưỡng cần thiết cho gia súc và đơn giá cho từng loại nguyên liệu cho trong bảng sau: 11 Các loại Hàm lượng dưỡng chất có trong từng Mức cần nguyên liệu dưỡng thiết chất NL1 NL2 … NLn I1 b1 a11 a12 … a1n I2 b2 a21 a22 … a2n. Im bm am1 am2 … amn Đơn giá nguyên liệu P1 P2 … Pn 12 Lập mô hình bài toán: Gọi x1 , x2 ,., xn là phần lượng từng loại nguyên liệu có trong thức ăn hỗn hợp.
Ta có tổng chi phí nguyên liệu trong giá 1 1 P2 x2 . Pn xn thành thức ăn là: Px Nhằm cực tiểu hóa chi phí nguyên 1 1 P2 x2 . Pn xn Min liệu: Px 13 Với phần lượng từng loại nguyên liệu trong thức ăn như trên, ta có hàm lượng dưỡng chất Ii trong thức ăn như sau: Tổng mức dinh dưỡng I1: a11x1 a12 x2 . a1n xn Tương tự đối với I2: a21 x1 a22 x2 .
a2 n xn 14 Theo yêu cầu về mặt kỹ thuật, để đảm bảo sự phát triển tốt cho gia súc thì thức ăn phải đảm bảo về mặt chất lượng nghĩa là phải thỏa mãn về mặt dinh dưỡng. a2 n xn b2 am1 x1 am 2 x2 . amn xn bm Ngoài ra phần lượng các loại nguyên liệu không âm, do đó x1, x2 ,., xn 0 15 Ví dụ: Một xí nghiệp luyện kim muốn sản xuất một loại hợp kim với 20% bạc, 30% đồng, 50% nhôm. Người ta sử dụng các nguyên liệu: bạc, đồng, nhôm, hợp kim A, hợp kim B, hợp kim C.
Hàm lượng bạc, đồng, nhôm trong các nguyên liệu trên cũng như giá một đơn vị khối lượng mỗi loại (USD/kg) được cho trong bảng sau: 16 Nguyên Hợp Hợp Hợp liệu Bạc Đồng Nhôm kim A kim B kim C Chất Bạc 100 0 0 30% 50% 40% % Đồng 0 100% 0 40% 20% 35% Nhôm 0 0 100% 30% 30% 25% Giá 1500 300 100 1000 1200 1100 17 Mô hình của bài toán như sau: Gọi x j j 1,., 6 lần lượt là khối lượng bạc, đồng, nhôm, hợp kim A, hợp kim B, hợp kim C tương ứng để sản xuất 1 kg hợp kim cần thiết.3 Bài toán cắt nguyên liệu Phân xưởng Hoàng Gia cần thực hiện một đơn đặt hàng cung ứng các tấm thép theo các kích cỡ và số lượng cho trong bảng bên dưới. Các tấm thép này được cắt ra từ các tấm thép có kích cỡ chuẩn (kích cỡ được sản xuất). 19 Các loại Số lượng thép cắt được/Cách cắt Mức yêu cầu thép C1 C2 … Cn I1 b1 a11 a12 … a1n I2 b2 a21 a22 … a2n. Im bm am1 am2 … amn Phần dư ra/Cách cắt P1 P2 … Pn Hãy xác định phương án cắt tối ưu sao cho vừa bảo đảm thực hiện đủ số lượng theo đơn đặt hàng vừa đảm bảo tổng phế liệu (tổng số thép dư ra) tối thiểu.
20 Mô hình của bài toán như sau: Gọi x1 , x2 ,., xn là số tấm thép chuẩn được cắt theo các cách C1, C2 ,., Cn Với phương án cắt trên ta có tổng 1 1 P2 x2 . Pn xn mức phế liệu là: Px Nhằm cực tiểu hóa mức phế liệu: 1 1 P2 x2 . Pn xn Min Px 21 Để đảm bảo cung ứng số tấm thép theo đơn đặt hàng, ta phải có: a11 x1 a12 x2 . a2 n xn b2 am1 x1 am 2 x2 .
amn xn bm Ta cũng có x j ( j 1,2,., n) là số tấm thép chuẩn được cắt theo một cách nào đó, do vậy x1, x2 ,.3 Một số bài toán ứng dụng 1.1 Bài toán phân bổ vốn đầu tư Một nhà đầu tư có 2 tỉ đồng, muốn đầu tư vào 4 lĩnh vực: chứng khoán, công trái, gởi tiết kiệm và bất động sản. Biết lãi suất hằng năm của các lĩnh vực đầu tư như sau: Lĩnh vực đầu tư Lãi suất hàng năm Chứng khoán 20% Công trái 12% Gởi tiết kiệm 10% Bất động sản 15% 23 Ngoài ra, để giảm thiểu mức độ rủi ro, nhà đầu tư cho rằng không nên đầu tư vào chứng khoán vượt quá 40% tổng vốn đầu tư, còn đầu tư vào công trái và gởi tiết kiệm phải ít nhất là 25% tổng vốn đầu tư và tiền gởi tiết kiệm phải ít nhất là 100 triệu đồng. Hãy lập kế hoạch phân bổ vốn đầu tư sao cho tổng thu nhập hàng năm là lớn nhất.,4 lần lượt là số tiền (triệu đồng) đầu tư vào chứng khoán, công trái, gởi tiết kiệm và bất động sản. Tổng thu nhập hàng năm là lớn nhất: 0,2 x1 0,12 x2 0,1x3 0,15x4 Max Tổng số tiền đầu tư không vượt quá số tiền hiện có: x1 x2 x3 x4 2.000 Điều kiện về số tiền đầu tư vào chứng khoán: x1 0, 4( x1 x2 x3 x4 ) 0, 6 x1 0, 4 x2 0, 4 x3 0, 4 x4 0 25 Điều kiện về số tiền đầu tư vào công trái và gởi tiết kiệm: x2 x3 0, 25( x1 x2 x3 x4 ) 0, 25 x1 0,75 x2 0,75 x3 0, 25 x4 0 Điều kiện về số tiền gởi tiết kiệm tối thiểu: x3 100 Điều kiện không âm của các khoản đầu tư: x j 0 j 1,., 4 26 Vậy ta có được mô hình của bài toán như sau: ĐK1: 0, 2 x1 0,12 x2 0,1x3 0,15 x4 Max x1 x2 x3 x4 2.1 Bài toán vận tải Một xí nghiệp cần vận chuyển vật liệu xây dựng từ 2 kho K1, K2 đến 3 công trường xây dựng C1, C2, C3.
Tổng số vật liệu có ở mỗi kho, tổng số vật liệu cần ở mỗi công trường cũng như khoảng cách từ mỗi kho đến mỗi công trường được cho trong bảng dưới: 28 Công trường C1 (15 tấn) C2 (20 tấn) C3 (25 tấn) Kho K1 (20 tấn) 5 km 7 km 2 km K2 (40 tấn) 4 km 3 km 6 km Hãy lập kế hoạch vận chuyển để: - Các kho giải phóng hết vật liệu - Các công trường nhận đủ vật liệu - Tổng số tấn x số km ít nhất 29 Gọi xij (i 1.3) lần lượt là khối lượng vật liệu được vận chuyển từ kho Ki đến công trường Cj. Mục tiêu chi phí thấp nhất nên: 5 x11 7 x12 2 x13 4 x21 3x22 6 x23 Min Các kho giải phóng hết vật liệu nên: x11 x12 x13 20 x21 x22 x23 40 Các công trường nhận đủ vật liệu nên: 30 x11 x21 15 x12 x22 20 x x 25 13 23 Ta có mô hình bài toán sau: ĐK1: 5 x11 7 x12 2 x13 4 x21 3x22 6 x23 Min x11 x12 x13 20 x x x 40 21 22 23 ĐK2: x11 x21 15 x x 20 12 22 x13 x23 25 ĐK3: xij 0, i 1.5 150 0 1 2 0 1 2 4 0 1 3 4 6 Dư 0,3 0 0,2 0 0,2 0,4 0,1 0,2 0,4 0,1 0,3 0 32 TRƢỜNG ĐẠI HỌC TÂY ĐÔ Chƣơng 2.