

Preview text:
Quy hoạch tuyến tính (linear programming) là gì ?
Quy hoạch tuyến tính là thuật toán hữu ích khi sử dụng lượng nguồn lực có
hạn để đạt được mục tiêu nào đó, chẳng hạn giảm thiểu chi phí hay tối đa
hoá lợi nhuận, trong đó giới hạn nguòn lực được coi là điều kiện ràng buộc.
Ví dụ công ty chế tạo hai sản phẩm là giá sách và ghế tìm cách xác định xem
nên sản xuất mỗi thứ bao nhiêu. Sản lượng bị giới hạn bởi lượng nguồn lực
hiện có và có thể biểu diễn dưới dạng đồ thị như trong hình 67. Trục hoành
biểu thị lượng giá sách và trục tung biểu thị lượng ghế. Nếu công ty có 80 giờ
máy hoạt động mỗi tuần và phải mất 5 giờ máy mới chế tạo được một chiếc
giá sách và cũng cần 5 giờ máy để chế tạo một chiếc ghế, lúc đó sản lượng
tối đa với lượng máy móc hiện có sẽ là đường XT. Nếu công ty chỉ có 84 giờ
công lao động trực tiếp và phải mất 7 giờ lao động trực tiếp để chế tạo một
chiếc giá sách và 3 giờ để chế tạo một chiếc ghế, thì sản lượng tối đa với
lượng lao động hiện có là đường Rĩ. Diện tích OXZT là tất cả các kết hợp hai
sản phẩm giá sách và ghế có thể chế tạo với số giờ máy móc hoạt động và
giờ công lao động hiện có (vùng khả thi). Nếu mỗi chiếc giá sách (h) bán đi
tạo ra lợi nhuận 5 nghìn đồng và giá mỗi chiếc ghế (c) bán di tạo ra lợi nhuận
là 4 nghìn đồng, thì để đạt được lợi nhuận tối đa, công ty này sẽ phải tối đa
hoá sản lượng y = 5h + 4c.
Chẳng hạn, để tạo lợi nhuận bằng 60 nghìn đồng, Công ty phải sản xuất 12
chiếc giá sách hoặc 15 chiếc ghế hoặc một kết hợp nào nằm trên bằng
đường đứt quãng MT trong hình 102. Kết hợp giá sách và ghế với tổng lợi
nhuận cao hơn có thể biểu thị bàng đường khác, chẳng hạn LN song song
với MT nhưng xa điểm gốc 0 hơn. Đường LN cho thấy công ty có thể có lợi
nhuận cao hơn với lượng máy móc và lao động hiện có bởi đó là đường đứt
quãng cao nhất chạm vào giới hạn nguồn lực biểu thị trong diện tích 0XZT.
Do vậy, công ty này nên dừng ở điểm z, chế tạo ov chiếc ghế và ow chiếc giá
sách mỗi tuần để tối đa hoá lợi nhuận với nguồn lực hiện có.
Quy hoạch tuyến tính cũng cung cấp những thông tin về giá trị của các nguồn
lực bổ sung của Công ty. Chẳng hạn, nó cho thấy có thể tăng thêm lợi nhuận
bao nhiêu khi tăng thêm giờ máy và giờ công lao động. Bởi vậy, nó cho thấy
số tiền tối đa công ty nên trả cho các nguồn lực bổ sung. Số tiền tối đa mà
công ty có thể trả mà không ảnh hưởng tới tỷ suất lợi nhuận được gọi là giá
mờ của giờ máy và giờ công lao động. Việc phân tích bằng đồ thị hai chiều
không còn tác dụng khi công ty chế tạo số mặt hàng lớn hơn 2. Tuy nhiên,
chúng ta vẫn có thể tính toán được các kết hợp tối ưu của mức sản lượng
mối mặt hàng thông qua thuật toán có tên là phương pháp đơn hình, nếu áp
dụng cách suy luận như trên.
Document Outline
- Quy hoạch tuyến tính (linear programming) là gì ?