Bài toán phân bổ

Có một nguồn tài nguyên tổng cộng $C$ đơn vị và $n$ sản phẩm. Sản phẩm $i$ cho lợi nhuận $p_i$/đơn vị, tiêu tốn $w_i$ tài nguyên/đơn vị và có giới hạn sản lượng $\ell_i$. Hãy tối đa hóa tổng lợi nhuận (cho phép sản lượng phân số).

Đây là LP một ràng buộc: ưu tiên sản phẩm có tỉ lệ $p_i/w_i$ cao nhất.

Ví dụ

$C=10$; sản phẩm A $(p=6,w=2,\ell=3)$, B $(p=5,w=1,\ell=100)$. Ưu tiên B (tỉ lệ 5) rồi A.