Giới thiệu bài toán quy hoạch tuyến tính

người ta cần có một lượng (tối thiểu) chất dinh dưỡng i=1,2,..,m do các thức ăn j=1,2,...,n cung cấp. giả sử :

a_ij là số lượng chất dinh dưỡng loại i có trong 1 đơn vị thức ăn loại j

(i=1,2,...,m) và (j=1,2,..., n)

b_i là nhu cầu tối thiểu về loại dinh dưìng i

c_j là giỏ mua một đơn vị thức ăn loại j

vấn đề đặt ra là phải mua các loại thức ăn như thế nào để tổng chi phí bỏ ra ít nhất mà vẫn đáp ứng được yêu cầu về dinh dưỡng. vấn đề được giải quyết theo mô hình sau đây :

gọi x_j ≥ 0 (j= 1,2,...,n) là số lượng thức ăn thứ j cần mua .

tổng chi phí cho việc mua thức ăn là :

vì chi phí bỏ ra để mua thức ăn phải là thấp nhất nên yêu cầu cần được thỏa mãn là :

lượng dinh dưỡng i thu được từ thức ăn 1 là : a_i1x₁ (i=1→m)

lượng dinh dưỡng i thu được từ thức ăn 2 là : a_i2x₂

.........................................................

lượng dinh dưỡng i thu được từ thức ăn n là : a_inx_n

vậy lượng dinh dưỡng thứ i thu được từ các loại thức ăn là :

a_i1x₁+a_i2x₂+...+a_inx_n (i=1→m)

vì lượng dinh dưỡng thứ i thu được phải thỏa yêu cầu b_i về dinh dưỡng loại đó nên ta có ràng buộc sau :

a_i1x₁+a_i2x₂+...+a_inx_n ≥ b_i (i=1→m)

khi đó theo yêu cầu của bài toỏn ta cú mụ hỡnh toỏn sau đây :

từ m loại nguyên liệu hiện có người ta muốn sản xuất n loại sản phẩm

giả sử :

a_ij là lượng nguyên liệu loại i dùng để sản xuất 1 sản phẩm loại j

(i=1,2,...,m) và (j=1,2,..., n)

b_i là số lượng nguyờn liệu loại i hiện cú

c_j là lợi nhuận thu được từ việc bỏn một đơn vị sản phẩm loại j

vấn đề đặt ra là phải sản xuất mỗi loại sản phẩm là bao nhiêu sao cho tổng lợi nhuận thu được từ việc bán các sản phẩm lớn nhất trong điều kiện nguyên liệu hiện có.

gọi x_j ≥ 0 là số lượng sản phẩm thứ j sẽ sản xuất (j=1,2,...,n)

tổng lợi nhuận thu được từ việc bỏn cỏc sản phẩm là :

vì yêu cầu lợi nhuận thu được cao nhất nên ta cần có :

lượng nguyên liệu thứ i=1→m dùng để sản xuất sản phẩm thứ 1 là a_i1x₁

lượng nguyên liệu thứ i=1→m dùng để sản xuất sản phẩm thứ 2 là a_i2x₂

...............................................

lượng nguyên liệu thứ i=1→m dùng để sản xuất sản phẩm thứ n là a_inx_n

vậy lượng nguyên liệu thứ i dùng để sản xuất là các sản phẩm là

a_i1x₁+a_i2x₂+...+a_inx_n

vì lượng nguyên liệu thứ i=1→m dùng để sản xuất các loại sản phẩm không thể vượt quá lượng được cung cấp là b_i nờn :

a_i1x₁+a_i2x₂+...+a_inx_n ≤ b_i (i=1,2,...,m)

vậy theo yêu cầu của bài toán ta có mô hình sau đây :

người ta cần vận chuyển hàng hoá từ m kho đến n cửa hàng bán lẻ. lượng hàng hoá ở kho i là s_i (i=1,2,...,m) và nhu cầu hàng hoỏ của cửa hàng j là d_j (j=1,2,...,n). cước vận chuyển một đơn vị hàng hoá từ kho i đến của hàng j là c_ij ≥ 0 đồng.

giả sử rằng tổng hàng hoá cũ ở các kho và tổng nhu cầu hàng hoá ở các cửa hàng là bằng nhau, tức là :

bài toán đặt ra là lập kế hoạch vận chuyển để tiền cước là nhỏ nhất, với điều kiện là mỗi cửa hàng đều nhận đủ hàng và mỗi kho đều trao hết hàng.

gọi x_ij ≥ 0 là lượng hàng hoá phải vận chuyển từ kho i đến cửa hàng j. cước vận chuyển chuyển hàng hoá i đến tất cả các kho j là :