Bài học

Bài toán vận chuyển và chi phí tối thiểu

Mục tiêu bài học

Sau bài này, em giải được một bài toán quy hoạch tuyến tính khi ràng buộc mang dấu $\ge$ (cần tối thiểu bao nhiêu, không phải nhiều nhất bao nhiêu) và hàm mục tiêu cần tối thiểu hóa chi phí, ngay cả khi miền nghiệm không bị chặn.

Kiến thức nền cần nhớ

Bài trước đã cho em quy trình bốn bước cho một bài toán sản xuất: gọi ẩn, lập ràng buộc, lập hàm mục tiêu, tìm đỉnh và so sánh (same-grade bridge). Bài Tìm GTLN, GTNN cũng đã lưu ý một trường hợp đặc biệt: nếu miền nghiệm không bị chặn, hàm mục tiêu có thể không có GTLN, nhưng GTNN vẫn có thể tồn tại tại một đỉnh biên gần gốc tọa độ (same-grade bridge). Bài này là đúng tình huống đó, áp dụng vào một bài toán vận chuyển cụ thể.

Khởi động

Một công ty cần vận chuyển đủ hai loại hàng hóa mỗi ngày bằng hai loại xe tải, mỗi loại xe chở được một lượng hàng khác nhau với chi phí khác nhau mỗi chuyến. Công ty phải chở đủ số lượng hàng tối thiểu — không phải tối đa — nhưng vẫn muốn chi phí thấp nhất có thể. Ràng buộc lần này là 'cần ít nhất bao nhiêu' chứ không phải 'nhiều nhất bao nhiêu' — miền nghiệm sẽ trông khác hẳn bài trước.

Kiến thức trọng tâm

Khi ràng buộc của đề bài là một yêu cầu tối thiểu ('cần ít nhất', 'không được ít hơn'), bất phương trình tương ứng mang dấu $\ge$ thay vì $\le$ . Điều này làm thay đổi vị trí điểm thử: với ràng buộc dạng $ax+by\ge c$ ( $c>0$ , $a,b>0$ ), gốc tọa độ $O(0;0)$ cho vế trái bằng 0, nhỏ hơn $c$ , nên $O$ KHÔNG thuộc miền nghiệm — miền nghiệm nằm ở phía xa gốc tọa độ, không phải phía chứa gốc như phần lớn ví dụ ở bài 1. Khi ghép nhiều ràng buộc dạng $\ge$ với $x\ge0, y\ge0$ , miền nghiệm thường mở rộng vô hạn về phía $x, y$ dương — không bị chặn.

Khi ràng buộc của đề bài là một yêu cầu tối thiểu ('cần ít nhất', 'không được ít hơn'), bất phương trình tương ứng mang dấu $\ge$ thay vì $\le$. Điều này làm thay đổi vị trí điểm thử: với ràng buộc dạng $ax+by\ge c$ ($c>0$, $a,b>0$), gốc tọa độ $O(0;0)$ cho vế trái bằng 0, nhỏ hơn $c$, nên $O$ KHÔNG thuộc miền nghiệm — miền nghiệm nằm ở phía xa gốc tọa độ, không phải phía chứa gốc như phần lớn ví dụ ở bài 1. Khi ghép nhiều ràng buộc dạng $\ge$ với $x\ge0, y\ge0$, miền nghiệm thường mở rộng vô hạn về phía $x, y$ dương — không bị chặn.

Dù miền nghiệm không bị chặn, nếu hàm chi phí $F=ax+by$ có $a, b>0$ , giá trị của $F$ vẫn chỉ có thể tăng khi $x$ hoặc $y$ tăng — nên GTNN của $F$ chắc chắn tồn tại và đạt tại một đỉnh nằm trên đúng phần biên gần gốc tọa độ nhất của miền, đường biên 'phía dưới-trái' được tạo bởi các ràng buộc $\ge$ . Cách tìm các đỉnh này không có gì mới: vẫn là giải hệ hai đường thẳng biên kề nhau rồi kiểm tra với các ràng buộc còn lại, đúng kỹ thuật đã học ở bài Hệ bất phương trình bậc nhất hai ẩn.

Dù miền nghiệm không bị chặn, nếu hàm chi phí $F=ax+by$ có $a, b>0$, giá trị của $F$ vẫn chỉ có thể tăng khi $x$ hoặc $y$ tăng — nên GTNN của $F$ chắc chắn tồn tại và đạt tại một đỉnh nằm trên đúng phần biên gần gốc tọa độ nhất của miền, đường biên 'phía dưới-trái' được tạo bởi các ràng buộc $\ge$. Cách tìm các đỉnh này không có gì mới: vẫn là giải hệ hai đường thẳng biên kề nhau rồi kiểm tra với các ràng buộc còn lại, đúng kỹ thuật đã học ở bài Hệ bất phương trình bậc nhất hai ẩn.

Ví dụ

Vận chuyển hàng hóa với chi phí thấp nhất

1
Một công ty cần vận chuyển mỗi ngày ít nhất 12 tấn hàng loại A và ít nhất 6 tấn hàng loại B, dùng hai loại xe. Xe loại I mỗi chuyến chở 3 tấn hàng A và 1 tấn hàng B, chi phí 900 nghìn đồng; xe loại II mỗi chuyến chở 1 tấn hàng A và 1 tấn hàng B, chi phí 500 nghìn đồng. Công ty nên dùng bao nhiêu chuyến mỗi loại xe để đủ hàng mà chi phí thấp nhất?
2
Gọi $x$ là số chuyến xe loại I, $y$ là số chuyến xe loại II trong ngày ( $x, y$ là số tự nhiên).
Gọi $x$ là số chuyến xe loại I, $y$ là số chuyến xe loại II trong ngày ($x, y$ là số tự nhiên).
3
Tổng hàng A chở được là $3x+y$ , cần đạt ít nhất 12 tấn: $3x+y\ge12$ . Tổng hàng B chở được là $x+y$ , cần đạt ít nhất 6 tấn: $x+y\ge6$ . Cùng điều kiện $x\ge0, y\ge0$ , ta có hệ $\begin{cases}3x+y\ge12\\x+y\ge6\\x\ge0\\y\ge0\end{cases}$ .
Tổng hàng A chở được là $3x+y$, cần đạt ít nhất 12 tấn: $3x+y\ge12$. Tổng hàng B chở được là $x+y$, cần đạt ít nhất 6 tấn: $x+y\ge6$. Cùng điều kiện $x\ge0, y\ge0$, ta có hệ $\begin{cases}3x+y\ge12\\x+y\ge6\\x\ge0\\y\ge0\end{cases}$.
4
Chi phí trong ngày (nghìn đồng) là $F(x;y)=900x+500y$ , cần tìm GTNN của $F$ .
Chi phí trong ngày (nghìn đồng) là $F(x;y)=900x+500y$, cần tìm GTNN của $F$.
5
Đường thẳng $3x+y=12$ và $x+y=6$ cắt nhau: trừ hai phương trình được $2x=6$ , tức $x=3$ , suy ra $y=3$ , cho điểm $(3;3)$ . Trên trục $x=0$ : cần $y\ge12$ (từ ràng buộc A, chặt hơn $y\ge6$ của ràng buộc B), cho điểm $(0;12)$ . Trên trục $y=0$ : cần $x\ge6$ (từ ràng buộc B, chặt hơn $x\ge4$ của ràng buộc A), cho điểm $(6;0)$ .
Đường thẳng $3x+y=12$ và $x+y=6$ cắt nhau: trừ hai phương trình được $2x=6$, tức $x=3$, suy ra $y=3$, cho điểm $(3;3)$. Trên trục $x=0$: cần $y\ge12$ (từ ràng buộc A, chặt hơn $y\ge6$ của ràng buộc B), cho điểm $(0;12)$. Trên trục $y=0$: cần $x\ge6$ (từ ràng buộc B, chặt hơn $x\ge4$ của ràng buộc A), cho điểm $(6;0)$.
6
$F(0;12)=900(0)+500(12)=6\,000$ ; $F(3;3)=900(3)+500(3)=2\,700+1\,500=4\,200$ ; $F(6;0)=900(6)+500(0)=5\,400$ .
$F(0;12)=900(0)+500(12)=6\,000$; $F(3;3)=900(3)+500(3)=2\,700+1\,500=4\,200$; $F(6;0)=900(6)+500(0)=5\,400$.
7
Ba điểm này nằm trên đúng phần biên gần gốc tọa độ của miền không bị chặn — không còn đỉnh nào khác gần gốc hơn để xét, vì miền chỉ mở rộng thêm về phía $x, y$ lớn hơn, nơi $F$ chỉ có thể lớn hơn. Trong ba giá trị $6\,000, 4\,200, 5\,400$ , giá trị nhỏ nhất là $4\,200$ , tại $(3;3)$ .
Ba điểm này nằm trên đúng phần biên gần gốc tọa độ của miền không bị chặn — không còn đỉnh nào khác gần gốc hơn để xét, vì miền chỉ mở rộng thêm về phía $x, y$ lớn hơn, nơi $F$ chỉ có thể lớn hơn. Trong ba giá trị $6\,000, 4\,200, 5\,400$, giá trị nhỏ nhất là $4\,200$, tại $(3;3)$.
8
Vậy công ty nên dùng 3 chuyến xe loại I và 3 chuyến xe loại II mỗi ngày, chi phí thấp nhất là $4\,200$ nghìn đồng, tức 4,2 triệu đồng.
Vậy công ty nên dùng 3 chuyến xe loại I và 3 chuyến xe loại II mỗi ngày, chi phí thấp nhất là $4\,200$ nghìn đồng, tức 4,2 triệu đồng.

Miền nghiệm mở rộng vô hạn về phía trên-phải; chỉ ba đỉnh trên biên gần gốc tọa độ cần xét để tìm GTNN.

Cột thấp nhất tại (3;3) xác định trực quan phương án chi phí thấp nhất.

Ví dụ

Luyện tập thêm: nhà máy sản xuất linh kiện

1
Một nhà máy sản xuất hai loại linh kiện I và II. Mỗi linh kiện I cần 2 giờ máy và 1 giờ kiểm tra; mỗi linh kiện II cần 1 giờ máy và 3 giờ kiểm tra. Nhà máy có tối đa 100 giờ máy và 90 giờ kiểm tra mỗi ngày. Lãi mỗi linh kiện I là 30 nghìn đồng, mỗi linh kiện II là 20 nghìn đồng. Tìm số lượng mỗi loại để lợi nhuận lớn nhất.
2
Gọi $x, y$ lần lượt là số linh kiện I, II ( $x, y\ge0$ ). Ràng buộc giờ máy: $2x+y\le100$ . Ràng buộc giờ kiểm tra: $x+3y\le90$ . Hàm mục tiêu: $F=30x+20y$ , cần GTLN.
Gọi $x, y$ lần lượt là số linh kiện I, II ($x, y\ge0$). Ràng buộc giờ máy: $2x+y\le100$. Ràng buộc giờ kiểm tra: $x+3y\le90$. Hàm mục tiêu: $F=30x+20y$, cần GTLN.
3
Giải các cặp đường biên và kiểm tra: $(0;0)$ cho $F=0$ ; $(50;0)$ (từ $y=0$ và $2x+y=100$ , thỏa $x+3y\le90$ ) cho $F=1\,500$ ; $(0;30)$ (từ $x=0$ và $x+3y=90$ , thỏa $2x+y\le100$ ) cho $F=600$ ; giao của $2x+y=100$ và $x+3y=90$ : trừ $3$ lần phương trình đầu cho phương trình sau được $5x=210$ , tức $x=42$ , suy ra $y=16$ , cho $(42;16)$ với $F=30(42)+20(16)=1\,260+320=1\,580$ .
Giải các cặp đường biên và kiểm tra: $(0;0)$ cho $F=0$; $(50;0)$ (từ $y=0$ và $2x+y=100$, thỏa $x+3y\le90$) cho $F=1\,500$; $(0;30)$ (từ $x=0$ và $x+3y=90$, thỏa $2x+y\le100$) cho $F=600$; giao của $2x+y=100$ và $x+3y=90$: trừ $3$ lần phương trình đầu cho phương trình sau được $5x=210$, tức $x=42$, suy ra $y=16$, cho $(42;16)$ với $F=30(42)+20(16)=1\,260+320=1\,580$.
4
So sánh $0, 1\,500, 600, 1\,580$ : GTLN là $1\,580$ nghìn đồng, đạt tại $(42;16)$ — nhà máy nên sản xuất 42 linh kiện I và 16 linh kiện II mỗi ngày.
So sánh $0, 1\,500, 600, 1\,580$: GTLN là $1\,580$ nghìn đồng, đạt tại $(42;16)$ — nhà máy nên sản xuất 42 linh kiện I và 16 linh kiện II mỗi ngày.

Đỉnh (42;16) cho lợi nhuận lớn nhất — cùng quy trình bốn bước như bài xưởng mộc.

Bẫy thường gặp

Sai lầm thường gặp: với ràng buộc dạng $\ge$ , nhiều bạn vẫn quen tay chọn gốc tọa độ $O$ làm điểm thử như bài 1, rồi kết luận sai. Khi vế phải $c>0$ và các hệ số $a, b>0$ , gốc tọa độ luôn cho vế trái bằng 0 — nhỏ hơn $c$ — nên $O$ chắc chắn KHÔNG thuộc miền nghiệm của $ax+by\ge c$ . Hãy thử một điểm khác, ví dụ một điểm có tọa độ đủ lớn, để xác định đúng phía chứa miền nghiệm.

Sai lầm thường gặp: với ràng buộc dạng $\ge$, nhiều bạn vẫn quen tay chọn gốc tọa độ $O$ làm điểm thử như bài 1, rồi kết luận sai. Khi vế phải $c>0$ và các hệ số $a, b>0$, gốc tọa độ luôn cho vế trái bằng 0 — nhỏ hơn $c$ — nên $O$ chắc chắn KHÔNG thuộc miền nghiệm của $ax+by\ge c$. Hãy thử một điểm khác, ví dụ một điểm có tọa độ đủ lớn, để xác định đúng phía chứa miền nghiệm.

Tóm lại, khi ràng buộc mang dấu $\ge$ , gốc tọa độ thường không thuộc miền nghiệm và miền có thể không bị chặn — nhưng nếu hàm chi phí có hệ số dương, GTNN vẫn tồn tại và vẫn được tìm bằng đúng kỹ thuật đã học: giải hệ các đường biên để tìm đỉnh, tính F, so sánh.

Tóm lại, khi ràng buộc mang dấu $\ge$, gốc tọa độ thường không thuộc miền nghiệm và miền có thể không bị chặn — nhưng nếu hàm chi phí có hệ số dương, GTNN vẫn tồn tại và vẫn được tìm bằng đúng kỹ thuật đã học: giải hệ các đường biên để tìm đỉnh, tính F, so sánh.

Đến đây, em đã giải trọn cả hai dạng bài toán quy hoạch tuyến tính phổ biến nhất: tối đa hóa lợi nhuận trên miền bị chặn, và tối thiểu hóa chi phí trên miền không bị chặn. Chương cuối cùng của khoá học sẽ ôn lại toàn bộ quy trình — từ đọc đề, lập hệ, vẽ miền, tìm đỉnh, đến kết luận — qua một bài toán tổng hợp mới.