Quy Hoạch Tuyến Tính và Ứng Dụng - Bài Tập Tuần 1 | Môn Đại số tuyến tính 1 - Đại học Sư phạm Kỹ thuật Thành phố Hồ Chí Minh

lOMoAR cPSD| 58707906
Bài toán tối ưu và quy hoạch tuyến tính Tuần 1 Bài 1 :
Một doanh nghiệp sản xuất quần áo, có một máy sản xuất quần và hai máy sản xuất
áo. Công suất tối đa của máy sản xuất quần là 5000 cái/ Tháng. Công xuất tối đa
của máy sản xuất áo là 10000 cái/Tháng. Tổng vốn công ty chi tiêu cho sản xuất
hàng tháng là 500 triệu đồng. Chi phí sản xuất 1 quần là: 60000 đ/cái. Chi phí sản
xuất 1 áo là: 40000 đ/cái. Giá bán một quần là: 100 000 đ/cái. Giá bán một áo là 65 000 đ/cái.
Mục tiêu của công ty là tối đa hóa lợi nhuận. Anh/Chị hãy lập mô hình bài toán quy
hoạch tuyến tính để tính số lượng quần, số lượng áo cần thiết sản xuất, và lợi nhuận hàng tháng của công ty. Giải :
Số lượng quần (Q) cần sản xuất hàng tháng.
Số lượng áo (A) cần sản xuất hàng tháng.
Yêu cầu bài toán là tối đa hóa lợi nhuận, với giả định rằng lợi nhuận là sự khác biệt
giữa doanh thu và chi phí sản xuất. Vì vậy, Công thức lợi nhuận như sau:
Lợi nhuận = (Giá bán quần * Số lượng quần sản xuất) + (Giá bán áo * Số lượng áo
sản xuất) - (Chi phí sản xuất quần * Số lượng quần sản xuất) - (Chi phí sản xuất áo
* Số lượng áo sản xuất)
Lợi nhuận = (100,000 * Q) + (65,000 * A) - (60,000 * Q) - (40,000 * A)
Lợi nhuận = 40,000*Q + 25,000*A
Xác định các ràng buộc: lOMoAR cPSD| 58707906
1. Công suất sản xuất tối đa của máy sản xuất quần là 5,000 cái/tháng: Q ≤ 5,000
2. Công suất sản xuất tối đa của máy sản xuất áo là 10,000 cái/tháng: A ≤ 10,000
3. Tổng số tiền chi tiêu hàng tháng không vượt quá 500 triệu đồng:
(Chi phí sản xuất quần * Số lượng quần sản xuất) + (Chi phí sản xuất áo * Số
lượng áo sản xuất) ≤ 500,000,000
(60,000 * Q) + (40,000 * A) ≤ 500,000,000
Mô hình bài toán quy hoạch tuyến tính hoàn chỉnh:
Hàm mục tiêu : Tối đa hóa lợi nhuận = 40,000*Q + 25,000*A Ràng buộc: 1. Q ≤ 5,000 2. A ≤ 10,000
3. 60,000*Q + 40,000*A ≤ 500,000,000 Bài 2 lOMoAR cPSD| 58707906
Một xưởng mộc làm bàn và ghế. Một công nhân làm xong một cái bàn phải mất 2
giờ, một cái ghế phải mất 30 phút. Khách hàng thường mua nhiều nhất là 4 ghế
kèm theo 1 bàn do đó tỷ lệ sản xuất giữa ghế và bàn nhiều nhất là 4:1. Giá bán một
cái bàn là 135 USD, một cái ghế là 50 USD.
Hãy lập mô hình bài toán tìm kế hoạch sản xuất để xưởng mộc đạt doanh thu cao
nhất, biết rằng xưởng có 4 công nhân đều làm việc 8 giờ mỗi ngày. Giải : Đặt :
Số lượng bàn cần sản xuất là X .
Số lượng ghế cần sản xuất là Y. Các ràng buộc như sau:
1. Thời gian làm việc của 4 công nhân là 8 giờ mỗi ngày.
2. Một cái bàn mất 2 giờ để sản xuất, và một cái ghế mất 30 phút để sản xuất.
3. Tỉ lệ sản xuất giữa ghế và bàn không vượt quá 4:1.
4. Giá bán của mỗi cái bàn là 135 USD, và giá bán của mỗi cái ghế là 50 USD.
Mô hình tối ưu hoá có thể được viết như sau:
Hàm mục tiêu (tối đa hóa doanh thu): 135*X + 50*Y = MAX
Các ràng buộc (hạn chế):
1. Thời gian sản xuất bàn: 2X + 0.5Y ≤ 8 *4 (do 1 giờ = 60 phút).
2. Tỉ lệ sản xuất ghế và bàn: Y ≤ 4*X.
3. Số lượng sản phẩm : X ≥ 0, Y ≥ 0. lOMoAR cPSD| 58707906 Bài 3 :
Công ty Alpha sản xuất hai loại sản phẩm S1 và S2. Nguyên liệu để sản xuất gồm
hai loại A và B, với trữ lượng lần lượt là 6 tấn và 8 tấn. Để sản xuất 1 tấn sản phẩm
S1 cần 1 tấn nguyên liệu A và 2 tấn nguyên liệu B. Hai số tương ứng của sản phẩm
S2 là 2 tấn và 1 tấn. Được biết nhu cầu thị trường trong một ngày là như sau:
Nhu cầu của S2 không hơn nhu cầu của S1 quá 1 tấn;
Nhu cầu tối đa của S2 là 2 tấn.
Giá bán 1 tấn sản phẩm S1 là 6 triệu VNĐ và 1 tấn sản phẩm S2 là 9 triệu VNĐ.
Với các điều kiện đã cho, hãy viết mô hình toán học cho bài toán lập kế hoạch sản
xuất sao cho tổng doanh thu là lớn nhất. Giải :
Đặt : X: Số tấn sản phẩm S1 sản xuất trong một ngày .
Y: Số tấn sản phẩm S2 sản xuất trong một ngày .
Mục tiêu là tối đa hóa tổng doanh thu, được tính bằng cách nhân số lượng sản phẩm
bán ra với giá bán tương ứng:
Tổng doanh thu (Z) = 6*X + 9*Y
Đặt các ràng buộc dựa trên nguyên liệu và nhu cầu thị trường: 1. Nguyên liệu A:
1*X + 2*Y ≤ 6 (vì mỗi tấn S1 cần 1 tấn A và mỗi tấn S2 cần 2 tấn A). 2. Nguyên liệu B:
2*X + 1*Y ≤ 8 (vì mỗi tấn S1 cần 2 tấn B và mỗi tấn S2 cần 1 tấn B).
3. Nhu cầu thị trường S2 không hơn nhu cầu S1 quá 1 tấn: Y ≤ X + 1.
4. Nhu cầu tối đa của S2 là 2 tấn: Y ≤ 2.
5. Số lượng sản phẩm : X ≥ 0, Y ≥ 0. lOMoAR cPSD| 58707906 Hàm Mục Tiêu : Max = 6*X + 9*Y Ràng buộc : 1. X + 2*Y ≤ 6 2. 2*X + Y ≤ 8 3. Y ≤ X + 1 4. Y ≤ 2 5. X ≥ 0 6. Y ≥ 0 Bài 4:
Một nhà máy cán thép có thể sản xuất hai loại sản phẩm : thép tấm và thép cuộn.
Nếu chỉ sản xuất một loại sản phẩm thì nhà máy chỉ có thể sản xuất 200 tấn thép
tấm hoặc 140 tấn thép cuộn trong một giờ. Lợi nhuận thu được khi bán một tấn
thép tấm là 25 USD, một tấn thép cuộn là 30 USD. Nhà máy làm việc 40 giờ trong
một tuần và thị trường tiêu thụ tối đa là 6000 tấn thép tấm và 4000 tấn thép cuộn .
Vấn đề đặt ra là nhà máy cần sản xuất mỗi loại sản phẩm là bao nhiêu trong một
tuần để đạt lợi nhuận cao nhất. Hãy lập mô hình bài toán xác định kế hoạch sản
xuất tối ưu cho vấn đề trên. Giải :
Đặt :Số tấn thép tấm (T) cần sản xuất trong một tuần .
Số tấn thép cuộn (C) cần sản xuất trong một tuần .
Biểu thức lợi nhuận (Hàm mục tiêu ):
Lợi nhuận (Z) = 25T + 30C (đơn vị: triệu USD) lOMoAR cPSD| 58707906
Các ràng buộc dựa trên thông tin đã cho: 1.
Sản lượng tối đa cho thép tấm: T ≤ 200 (tấn/giờ) x 40 (giờ/tuần) = 8000 tấn/tuần 2.
Sản lượng tối đa cho thép cuộn: C ≤ 140 (tấn/giờ) x 40 (giờ/tuần) = 5600 tấn/tuần 3.
Thị trường tiêu thụ tối đa cho thép tấm: T ≤ 6000 tấn/tuần4. Thị trường tiêu
thụ tối đa cho thép cuộn: C ≤ 4000 tấn/tuần
5. Sản lượng không thể âm: T ≥ 0 C ≥ 0 TỐI ƯU : Hàm Mục Tiêu : Max Z = 25T + 30C Hàm Ràng Buộc: 1. T ≤ 8000 2. C ≤ 5600 3. T ≤ 6000 4. C ≤ 4000 5. T ≥ 0 6. C ≥ 0 Bài 5 : lOMoAR cPSD| 58707906
Một xí nghiệp dệt hiện có 3 loại sợi : Cotton, Kate, Polyester với khối lượng tương
ứng là 3; 2.5; 4.2 (tấn) . Các yếu tố sản xuất khác có số lượng lớn. Xí nghiệp có thể
sản xuất ra 3 loại vải A, B, C (với khổ bề rộng nhất định) với mức tiêu hao các loại
sợi để sản xuất ra 1 mét vải các loại cho trong bảng sau : Loại sợi Loại vải (gam) A B C Cotton 200 200 100 Kate 100 200 100 Polyester 100 100 200
Biết lợi nhuận thu được khi sản xuất 1 mét vải các loại A, B, C tương ứng là 350;
480; 250 (đ). Sản phẩm sản xuất ra đều có thể tiêu thụ được hết với số lượng không
hạn chế , nhưng điều kiện tiêu thụ sản phẩm yêu cầu số mét vải B và C phải có tỉ lệ 1:2.
Hãy xây dựng mô hình bài toán tìm kế hoạch sản xuất tối ưu. Giải : Đặt :
X1: Số mét vải loại A sản xuất.
X2: Số mét vải loại B sản xuất.
X3: Số mét vải loại C sản xuất.
Mục tiêu là tối đa hóa lợi nhuận. Lợi nhuận từ sản xuất các loại vải là tổng lợi nhuận
từ sản xuất vải A, B và C:
Lợi nhuận (Z) = 350*X1 + 480*X2 + 250*X3
Đặt các ràng buộc dựa trên thông tin đã cho:
1. Khối lượng sợi sẵn có:
- 3 tấn Cotton, 2.5 tấn Kate, 4.2 tấn Polyester.
2. Mức tiêu hao sợi cho sản xuất 1 mét vải:
- Loại A: Cotton (200), Kate (100), Polyester (100).
- Loại B: Cotton (200), Kate (200), Polyester (100).
- Loại C: Cotton (100), Kate (100), Polyester (200). lOMoAR cPSD| 58707906
3. Ràng buộc khối lượng sợi:
- Số lượng sợi Cotton cần: 200*X1 + 200*X2 + 100*X3 ≤ 3,000.
- Số lượng sợi Kate cần: 100*X1 + 200*X2 + 100*X3 ≤ 2,500.
- Số lượng sợi Polyester cần: 100*X1 + 100*X2 + 200*X3 ≤ 4,200.
4. Ràng buộc về tỉ lệ sản phẩm B và C: - X2 = 2*X3.
5. Số mét vải sản xuất không thể âm: X1 ≥ 0, X2 ≥ 0, X3 ≥ 0.
Bây giờ, bài toán tối ưu có thể được viết như sau: Hàm mục tiêu :
Max Z = 350*X1 + 480*X2 + 250*X3 Ràng buộc :
1. 200*X1 + 200*X2 + 100*X3 ≤ 3,000
2. 100*X1 + 200*X2 + 100*X3 ≤ 2,500
3. 100*X1 + 100*X2 + 200*X3 ≤ 4,200 4. X2 = 2*X3
5. X1 ≥ 0, X2 ≥ 0, X3 ≥ 0 lOMoAR cPSD| 58707906 Bài 6 : lOMoAR cPSD| 58707906
Để nuôi một loại gia súc trong 24 giờ cần có khối lượng tối thiểu của các chất :
Protit, Gluxit, Khoáng tương ứng là 80, 120, 6 (gam). Tỉ lệ %, theo khối lượng, các
chất trên có trong các loại thức ăn A, B, C như sau : Chất dinh dưỡng Thức ăn Protit Gluxit Khoáng A 10 30 2 B 20 40 1 C 25 20 3
Ngoài ra, biết giá của 1kg thức ăn A, B, C tương ứng là 2000, 3000, 2500 (đồng).
Hãy lập mô hình bài toán xác định khối lượng thức ăn tối ưu cần phải mua. Giải : Đặt các biến :
X1: Khối lượng thức ăn loại A cần mua (kg).
X2: Khối lượng thức ăn loại B cần mua (kg).
X3: Khối lượng thức ăn loại C cần mua (kg).
Chi phí mua thức ăn là tổng giá trị của từng loại thức ăn được mua:
Tổng chi phí (Z) = 2000*X1 + 3000*X2 + 2500*X3 Đặt
các ràng buộc dựa trên thông tin đã cho:
1. Khối lượng tối thiểu các chất dinh dưỡng cần có: Protit (80g), Gluxit (120g),Khoáng (6g).
2. Tỉ lệ % chất dinh dưỡng trong từng loại thức ăn:
- Loại A: Protit (10%), Gluxit (30%), Khoáng (2%).
- Loại B: Protit (20%), Gluxit (40%), Khoáng (1%).
- Loại C: Protit (25%), Gluxit (20%), Khoáng (3%).
3. Ràng buộc về tổng lượng các chất dinh dưỡng cần có: lOMoAR cPSD| 58707906
- 10*X1 + 20*X2 + 25*X3 ≥ 80 (Protit)
- 30*X1 + 40*X2 + 20*X3 ≥ 120 (Gluxit)
- 2*X1 + X2 + 3*X3 ≥ 6 (Khoáng)
4. Khối lượng thức ăn không thể âm: X1 ≥ 0, X2 ≥ 0, X3 ≥ 0.
Bài toán tối ưu có thể được viết như sau:
Min Z = 2000*X1 + 3000*X2 + 2500*X3 Ràng buộc :
1. 10*X1 + 20*X2 + 25*X3 ≥ 80
2. 30*X1 + 40*X2 + 20*X3 ≥ 120 3. 2*X1 + X2 + 3*X3 ≥ 6
4. X1 ≥ 0, X2 ≥ 0, X3 ≥ 0 Bài 7 :
Một xí nghiệp sản xuất một loại sản phẩm gồm có 3 dạng : thường, tốt và siêu hạng với các dữ liệu sau : Dạng sản phẩm
Thường Tốt Siêu hạng
Giá bán 1 đơn vị (1000 đồng) 70 150 250
Chi phí nguyên liệu cho 1 đơn vị (1000 đồng) 30 60 100
Thời gian hoàn tất 1 đơn vị sản phẩm (giờ) 0.1 0.2 0.5
Nhu cầu tối đa trong 1 tuần (đơn vị) 1000 800 300
Xí nghiệp có lực lượng lao động là 5 người làm việc 40 giờ/tuần và được trả
lương 500,000 đồng/tuần/người dù họ có làm đủ 40 giờ hay không.
Hãy lập mô hình bài toán tìm kế hoạch sản xuất tối ưu hàng tuần. Giải : lOMoAR cPSD| 58707906
Để lập mô hình bài toán tìm kế hoạch sản xuất tối ưu hàng tuần cho xí nghiệp,
chúng ta cần đặt các biến quyết định và mục tiêu tối ưu, cùng với các ràng buộc.
Đầu tiên, đặt các biến quyết định:
X1: Số đơn vị sản phẩm dạng "Thường" sản xuất hàng tuần.
X2: Số đơn vị sản phẩm dạng "Tốt" sản xuất hàng tuần.
X3: Số đơn vị sản phẩm dạng "Siêu hạng" sản xuất hàng tuần.
Lợi nhuận từ sản xuất các dạng sản phẩm là tổng lợi nhuận từ sản xuất sản phẩm
"Thường", "Tốt", và "Siêu hạng":
Lợi nhuận (Z) = 70*X1 + 150*X2 + 250*X3 - (500,000 * 5) Bây
giờ, Các ràng buộc dựa trên thông tin đã cho:
1. Chi phí nguyên liệu cho sản xuất 1 đơn vị của từng dạng sản phẩm: - Thường: 30,000 đồng. - Tốt: 60,000 đồng.
- Siêu hạng: 100,000 đồng.
2. Thời gian hoàn tất 1 đơn vị sản phẩm của từng dạng sản phẩm: - Thường: 0.1 giờ. - Tốt: 0.2 giờ. - Siêu hạng: 0.5 giờ.
3. Số lượng sản phẩm không thể vượt quá nhu cầu tối đa trong 1 tuần: - X1 ≤ 1000 - X2 ≤ 800 - X3 ≤ 300 lOMoAR cPSD| 58707906
4. Số lượng sản phẩm sản xuất không thể âm: X1 ≥ 0, X2 ≥ 0, X3 ≥ 0.
5. Lực lượng lao động có 5 người làm việc 40 giờ/tuần và được trả lương 500,000
đồng/tuần/người dù họ có làm đủ 40 giờ hay không, nên thời gian lao động không
vượt quá 200 giờ/tuần:
- 0.1*X1 + 0.2*X2 + 0.5*X3 ≤ 200
Bài toán tối ưu có thể được viết như sau:
Max Z = 70*X1 + 150*X2 + 250*X3 - (500,000 * 5)
F(X) = 40X1+ 90X2+150X3+2500 => Max Ràng buộc :
1. 0.1*X1 + 0.2*X2 + 0.5*X3 ≤ 200 1. 0.1X1+0.2X2+0.5X3 <= 32 2. X1 ≤ 1000 2. X1<=1000 3. X2 ≤ 800 3. X2 <= 800 4. X3 ≤ 300 4 X3<=300
5. X1 ≥ 0, X2 ≥ 0, X3 ≥ 0 5 . X1 ≥ 0, X2 ≥ 0, X3 ≥ 0 Bài 8 :
Giả sử người ta cần tạo một hỗn hợp gồm hai loại thực phẩm T1 và T2.
Hỗn hợp đó cần có 60 đơn vị chất dinh dưỡng D1, 160 đơn vị chất dinh dưỡng D2
và 180 đơn vị chất dinh dưỡng D3. Một kilôgam T1 chứa 3 đơn vị D1, 4 đơn vị D2,
3 đơn vị D3 và giá 15 ngàn đồng. Một kilôgam T2 chứa 1 đơn vị D1, 4 đơn vị D2, 6
đơn vị D3 và giá 12 ngàn đồng.
Hãy viết mô hình toán học cho bài toán: Xác định thành phần của T1 và T2 sao cho
hỗn hợp được tạo ra bảo đảm nhu cầu về các chất dinh dưỡng và có giá thành rẻ nhất. Giải :
Đặt biến quyết định:
X1: Khối lượng (trong kilogram) của thực phẩm T1 cần thêm vào hỗn hợp. lOMoAR cPSD| 58707906
X2: Khối lượng (trong kilogram) của thực phẩm T2 cần thêm vào hỗn hợp.
Mục tiêu của chúng ta là tối thiểu hóa giá thành tổng cộng của hỗn hợp, bao gồm
cả giá tiền của T1 và T2:
Giá thành tổng cộng (Z) = 15*X1 + 12*X2
Bây giờ, chúng ta cần đặt các ràng buộc dựa trên thông tin đã cho:
1. Ràng buộc về chất dinh dưỡng D1: - 3*X1 + X2 >= 60
2. Ràng buộc về chất dinh dưỡng D2: - 4*X1 + 4*X2 >= 160
3. Ràng buộc về chất dinh dưỡng D3: - 3*X1 + 6*X2 >= 180
4. Số lượng T1 và T2 không thể âm: - X1 ≥ 0, X2 ≥ 0
Cuối cùng, bài toán tối ưu có thể được viết như sau: Min Z = 15*X1 + 12*X2 Ràng buộc : 1. 3X1 + X2 >= 60 2. 4X1 + 4X2 >= 160 lOMoAR cPSD| 58707906 3. 3X1 + 6X2 >= 180 4. X1 ≥ 0, X2 ≥ 0 Bài 9 :
Một xí nghiệp đồ gỗ dự định sản xuất bàn, ghế và tủ. Biết định mức tiêu hao các
yếu tố sản xuất khi làm ra 1 sản phẩm cho trong bảng sau : Yếu tố Sản phẩm Sản xuất Bàn Ghế Tủ Lao động (ngày công) 2 0.5 3 Chi phí SX (ngàn đồng) 200 50 350
Ngoài ra, biết giá bán 1 sản phẩm bàn, ghế ,tủ tương ứng là 240; 60; 410 (ngàn
đồng) và xí nghiệp hiện có số lao động là 100 ngày công, số vốn là 12 triệu đồng.
Giả sử sản phẩm tiêu thụ theo toàn bộ lô hàng sản xuất ra với số lượng không hạn
chế, nhưng số bàn và số ghế phải tuân theo tỉ lệ 1:6.
Hãy lập mô hình bài toán tìm kế hoạch sản xuất tối ưu. Giải : Đặt các biến:
X1: Số lượng sản phẩm "Bàn" sản xuất.
X2: Số lượng sản phẩm "Ghế" sản xuất.
X3: Số lượng sản phẩm "Tủ" sản xuất.
Mục tiêu của chúng ta là tối đa hóa lợi nhuận. Lợi nhuận từ sản xuất các sản
phẩm là tổng lợi nhuận từ sản phẩm "Bàn", "Ghế", và "Tủ":
Lợi nhuận (Z) = 240*X1 + 60*X2 + 410*X3
Bây giờ, chúng ta cần đặt các ràng buộc dựa trên thông tin đã cho: lOMoAR cPSD| 58707906
1. Số ngày công cần sử dụng:
- 2*X1 + 0.5*X2 + 3*X3 ≤ 100 (100 ngày công có sẵn). 2. Số vốn có sẵn:
- 200*X1 + 50*X2 + 350*X3 ≤ 12,000 (12 triệu đồng có sẵn).
3. Số sản phẩm "Bàn" và "Ghế" phải tuân theo tỉ lệ 1:6: - X1 = 6*X2
4. Số lượng sản phẩm sản xuất không thể âm:
- X1 ≥ 0, X2 ≥ 0, X3 ≥ 0
Bây giờ, bài toán tối ưu có thể được viết như sau: Hàm mục tiêu :
Max Z = 240*X1 + 60*X2 + 410*X3 Ràng buộc:
1. 2*X1 + 0.5*X2 + 3*X3 ≤ 100
2. 200*X1 + 50*X2 + 350*X3 ≤ 12,000 3. X1 = 6*X2
4. X1 ≥ 0, X2 ≥ 0, X3 ≥ 0