CHƯƠNG V: Bài toán quy hoạch tuyến tính
I. Một số ví dụ thực tế dẫn đến bài toán QHTT
1. Bài toán khẩu phần thức ăn
Một cơ sở sử dụng 3loại TA là A, Bvà Cđể SX TACN. Trong 3 loại TA
đều có chứa 3chất dinh dưỡng: protein, lipit, glucide.
Số đơn vị chất dinh dưỡng có trong 1 đơn vị TA;số đơn vị chất dinh
dưỡng yêu cầu tối thiểu trong 1 KPTA cho gia súc phát triển bình thường
và giá mua 3 loại TA được cho trong bảng sau:
Bảng.Định mức kinh tế-kỹ thuật cho gia súc phát triển
Thức
ăn
Đơn giá
(ngđ/kg)
Thành phần dinh dưỡng (đơn vị)
Protein Lipit Glucide
A
16 8 6 2
B
18 4 5 6
C
12 7 7 3
Yêu
cầu tối thiểu d2trong 1 KPTA 20 25 15
Yêu cầu: xác định khối lượng 3 loại TA có trong 1 KPTA sao cho:
1. Chi phí SX ra 1 KPTA là nhỏ nhất
2. Đảm bảo yêu cầu về dinh dưỡng cho gia súc phát triển bình thường.
CHƯƠNG V: Bài toán quy hoạch tuyến tính
I.1. Bài toán khẩu phần thức ăn
Mô hình:
Gọi X1, X2, X3lần lượt là khối lượng 3loại TA A, B,C có trong 1
KPTA.
Chi phí để sx ra 1 KPTA nhỏ nhất:16 X1+18 X2+12 X3→min
RB đảm bảo dinh dưỡng cho gia súc phát triển bình thường:
Lượng protein có trong 1 KPTA: 8 X1+ 4 X2+ 7 X3≥20
Lượng lipit có trong 1 KPTA: 6 X1+ 5 X2+ 7 X3≥25
Lượng glucide có trong 1 KPTA: 2 X1+ 6 X2+ 3 X3≥15
RB ĐN: Xj≥0(j = 1÷3)
CHƯƠNG V: Bài toán quy hoạch tuyến tính
I. Một số ví dụ thực tế dẫn đến bài toán QHTT
I.2. Bài toán lập kế hoạch sản xuất
Một cơ sở SX 3loại SP là A, Bvà C. Để SX 3SP cơ sở phải sử dụng
đến 3loại nguyên liệu:I, II và III.
Số đơn vị nguyên liệu mỗi loại để sản xuất ra 1đơn vị SP;số đơn vị
nguyên liệu tối đa trong 1 chu kì sản xuất và lợi nhuận để sản xuất 1đơn
vị SP được cho trong bảng sau:
Bảng.Định mức kinh tế-kỹ thuật để sản xuất SP
Sản
phẩm Lợi nhuận
(ngđ/đv) Nguyên liệu
III III
A
16 2 4 2
B
10 4 4 4
C
12 1 1 3
Nguyên
liệu được sử dụng tối đa 20 24 18
Yêu cầu: xác định khối lượng 3 loại SP cần sản xuất ra sao cho:
1. Lợi nhuận sản xuất của cơ sở là lớn nhất
2. Sản xuất trong khuôn khổ về nguồn nguyên liệu.
CHƯƠNG V: Bài toán quy hoạch tuyến tính
I.2. Bài toán lập kế hoạch sản xuất
Mô hình:
Gọi X1, X2, X3lần lượt là khối lượng 3loại SP cần sx ra.
Lợi nhuận để sx ra 3loại SP lớn nhất:16 X1+10 X2+12 X3→max
Nguyên liệu Isử dụng trong sx: 2 X1+ 4 X2+ X3≤20
Nguyên liệu II sử dụng trong sx : 4 X1+ 4 X2+ X3≤24
Nguyên liệu III sử dụng trong sx : 2 X1+ 4 X2+ 3 X3≤18
RB ĐN: Xj≥0(j = 1÷3)
Nhận xét
BT trên là 1lớp BT gồm 1 HMT tuyến tính và 1hệ thống các RB là các
phương trình hoặc bất phương trình cũng tuyến tính được gọi là BT qui
hoạch tuyến tính.
CHƯƠNG V: Bài toán quy hoạch tuyến tính
II. Bài toán qui hoạch tuyến tính tổng quát
1. Dạng tổng quát của bài toán QHTT
Gọi: Xjlà biến của bài toán (j = 1÷n);
Cjlà hệ số của các biến trong HMT;
aij là hệ số của các biến trong hệ RB;
bilà hệ số tự do của RB (hệ số vế phải) (i= 1÷m).
Bài toán QHTT tổng quát:
a) Dạng tường minh:
HMT: Z = F(X) = C1X1+ C2X2+ ... + CnXn= ∑CjXj→ max (min)
RB: a11X1+ a12X2+ …+ a1nXn≥(≤/=) b1
a21X1+ a22X2+ …+ a2nXn≥(≤/=) b2
……..…
am1X1+ am2X2+ …+ amnXn≥(≤/=) bm
RB đương nhiên: Xj≥ 0 (j = 1÷ n)