Quy hoạch tuyến tính (linear programming)
?
Quy hoạch tuyến tính thuật toán hữu ích khi sử dụng lượng nguồn lực
hạn để đạt được mục tiêu nào đó, chẳng hạn giảm thiểu chi p hay tối đa
hoá lợi nhuận, trong đó giới hạn nguòn lực được coi điều kiện ràng buộc.
dụ công ty chế tạo hai sản phẩm giá sách ghế tìm 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 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 trục tung biểu thị lượng ghế. Nếu công ty 80 giờ
máy hoạt động mỗi tuần phải mất 5 giờ máy mới chế tạo được một chiếc
giá sách 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 sẽ đường XT. Nếu công ty chỉ 84 giờ
công lao động trực tiếp phải mất 7 giờ lao động trực tiếp để chế tạo một
chiếc giá sách 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 đường Rĩ. Diện tích OXZT tất cả các kết hợp hai
sản phẩm giá sách ghế thể chế tạo với số giờ máy móc hoạt động
giờ công lao động hiện (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 giá mỗi chiếc ghế (c) bán di tạo ra lợi nhuận
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 ghế với tổng lợi
nhuận cao hơn 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 thể lợi
nhuận cao hơn với lượng máy móc lao động hiện bởi đó đườ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 y nên dừng điểm z, chế tạo ov chiếc ghế 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, cho thấy thể tăng thêm lợi nhuận
bao nhiêu khi ng thêm giờ máy giờ công lao động. Bởi vậy, 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
công ty thể trả không ảnh hưởng tới tỷ suất lợi nhuận được gọi giá
mờ của giờ máy giờ ng lao động. Việc phân tích bằng đồ thị hai chiều
không 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 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 tên phương pháp đơn hình, nếu áp
dụng ch suy luận như trên.

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ì ?