QUY HOẠCH TUYẾN TÍNH 02/09/2012
Chuongnn-hui.blogspot.com 1
Toán chuyên đề 4: QUY HOẠCH TUYẾN TÍNH
MÔN QUY HOẠCH TUYẾN TÍNH
Giảng viên : Ths. NGUYỄN NGỌC CHƯƠNG
1
Toán chuyên đề 4: QUY HOẠCH TUYẾN TÍNH
Số tín chỉ: 2 (30 tiết).
Điều kiện tiên quyết: Đã học xong chương trình
toán C2.
Mục đích của học phần: Trang bị cho sinh viên
các kiến thức về một số mô hình tối ưu trong
kinh tế.
Về kiến thức:
Hiểu biết các khái niệm về bài toán quy hoạch
tuyến tính, bài toán đối ngẫu, bài toán vận tải.
Nắm vững các phương pháp giải toán: phương
pháp đơn hình, đơn hình đối ngẫu, phương
pháp thế vị.
2
Toán chuyên đề 4: QUY HOẠCH TUYẾN TÍNH
Về kỹ năng:
Biết vận dụng các phương pháp vào giải một
số bài toán cụ thể trong thực tế.
Nội dung của học phần:
Chương 1: Bài toán quy hoạch tuyến tính.
Chương 2: Bài toán đối ngẫu.
Chương 3: Bài toán vận tải.
Giáo trình:
[1] TS Nguyễn Phú Vinh,
Giáo trình Quy hoạch
tuyến tính
, Trường ĐHCN TP.HCM.
3
Toán chuyên đề 4: QUY HOẠCH TUYẾN TÍNH
Tài liệu tham khảo:
[1] GS. Đặng Hấn,
Quy hoạch tuyến tính
, ĐHKT
TP.HCM.
[2] GS. Phan Quốc Khánh,
Quy hoạch tuyến tính
,
NXBGD 1998.
Tiêu chuẩn và hình thức đánh giá kết quả :
Dự lớp
:
Từ 80% số tiết trở lên.
Tiểu luận
: (tuần thứ 6)
Thi giữa kỳ
:
Tự luận (tuần thứ 6)
Thi kết thúc học phần
:
Tự luận
Thang điểm: Theo học chế tín chỉ.
4
Toán chuyên đề 4: QUY HOẠCH TUYẾN TÍNH
Chương1: BÀI TOÁN QUY HOẠCH TUYẾN TÍNH
MỘT SỐ BÀI TOÁN DẪN ĐẾN
BÀI TOÁN QUY HOẠCH TUYẾN TÍNH
5
Toán chuyên đề 4: QUY HOẠCH TUYẾN TÍNH
Một công ty sản xuất n loại sản phẩm Sj (j=1,2, ..,n)
sử dụng m loại nguyên liệu Ni (i = 1,2, ..,m).
Biết:
+ Lượng nguyên liệu Ni cần thiết dùng để sản xuất
một đơn vị sản phẩm Sj là: aij
+ Trữ lượng nguyên liệu loại Ni là: bi
+ Tiền lãi một đơn vị sản phẩm Sj là: cj
Hãy xây dựng kế hoạch sản xuất cho công ty để có
lợi nhuận nhiều nhất.
Bài toán lập kế hoạch sản xuất
6
QUY HOẠCH TUYẾN TÍNH 02/09/2012
Chuongnn-hui.blogspot.com 2
Toán chuyên đề 4: QUY HOẠCH TUYẾN TÍNH
Sản
phẩm
Nguyên
liệu S1 S2
…
Sn
Số
nguyên
liệu tối đa
N1 a11 a12
…
a1n b1
N2 a21 a22
…
a2n b2
… … …
…
… …
Nm am1 am2
…
a
mn bm
Tiền
lãi/đơn vị
sản phẩm c1 c2
…
cn
Minh hoạ dữ liệu bài toán:
7
Toán chuyên đề 4: QUY HOẠCH TUYẾN TÍNH
Gọi xj là lượng Sj (j=1,2, ..,n) cần sản xuất. xj ≥ 0.
Lượng nguyên liệu N1 dùng cho sản xuất:
a11x1 + a12x2 + … + a1nxn ≤ b1
Lượng nguyên liệu N2 dùng cho sản xuất:
a21x1 + a22x2 + … + a2nxn ≤ b2
…………………………………………………………..
Lượng nguyên liệu Nm dùng cho sản xuất:
am1x1 + am2x2 + … + amnxn ≤ bm
Số tiền lãi mà công ty thu được là:
f = f(x1, x2, … , xn) = c1x1 + c2x2 + … + cnxn
Giải:
8
Toán chuyên đề 4: QUY HOẠCH TUYẾN TÍNH
Mô hình toán học của bài toán
Tìm x = (x1, x2, …, xn) sao cho
f(x) = c1x1 + c2x2 + … + cnxn ⟶ max
với các ràng buộc
a11x1 + a12x2 + … + a1nxn ≤ b1 .
a21x1 + a22x2 + … + a2nxn ≤ b2 ..
……...........................................................
am1x1 + am2x2 + … + amnxn ≤ bm
x1, x2, …, xn ≥ 0 .
Đây là một bài toán quy hoạch tuyến tính.
9
Toán chuyên đề 4: QUY HOẠCH TUYẾN TÍNH
Bài toán vốn đầu tư
Một xí nghiệp xử lý giấy có n phân xưởng Sj
(j=1,2,…,n) xử lý m loại giấy Ni (i=1,2,…,m).
Biết:
+ Lượng giấy loại Ni mà cuối năm phân xưởng Sj có
thể xử lý (nếu cùng đầu tư một đơn vị vốn vào các
phân xưởng) là: aij
+ Lượng giấy Ni tối thiểu cần phải xử lý theo hợp
đồng lao động là: bi
Lập kế hoạch đầu tư để xí nghiệp hoàn thành hợp
đồng lao động với tổng vốn đầu tư là nhỏ nhất.
10
Toán chuyên đề 4: QUY HOẠCH TUYẾN TÍNH
Phân
rác thải
S
1
S
2
…
S
n
Lượng
rác xử
lý tối thiểu
N1
a11
a12
…
a1n
b1
N2
a21
a22
…
a2n
b2
…
…
…
…
…
…
Nm
am1
am2
…
amn
bm
Minh hoạ dữ liệu bài toán:
11
Toán chuyên đề 4: QUY HOẠCH TUYẾN TÍNH
Gọi xj là lượng vốn đầu tư cho Sj (j=1,2, ..,n). xj ≥ 0.
Lượng giấy N1 xử lý được:
a11x1 + a12x2 + … + a1nxn ≥ b1
Lượng giấy N2 xử lý được:
a21x1 + a22x2 + … + a2nxn ≥ b2
………………………………………
Lượng giấy Nm xử lý được:
am1x1 + am2x2 + … + amnxn ≥ bm
Số vốn mà xí nghiệp cần đầu tư là:
f = f(x1, x2, … , xn) = x1 + x2 + … + xn
Giải:
12
QUY HOẠCH TUYẾN TÍNH 02/09/2012
Chuongnn-hui.blogspot.com 3
Toán chuyên đề 4: QUY HOẠCH TUYẾN TÍNH
Mô hình toán học của bài toán
Tìm x = (x1, x2, …, xn) sao cho
f(x) = x1 + x2 + … + xn ⟶ min
với các ràng buộc
a11x1 + a12x2 + … + a1nxn ≥ b1 .
a21x1 + a22x2 + … + a2nxn ≥ b2 .
……………………………………………..
am1x1 + am2x2 + … + amnxn ≥ bm
x1, x2, …, xn ≥ 0 .
Đây là một bài toán quy hoạch tuyến tính.
13
Toán chuyên đề 4: QUY HOẠCH TUYẾN TÍNH
Bài toán vận tải
Xí nghiệp cần vận chuyển hàng hoá từ m điểm phát
Pi (i=1,2,…,m) đến n điểm thu Tj (j=1,2,…,n). Biết
+ Lượng hàng có ở điểm phát Pi là: ai
+ Lượng hàng cần ở mỗi điểm thu Tj là: bj
+ Phí chuyển một đơn vị hàng từ Pi đến Tj là: cij
Giả sử tổng lượng hàng có ở các điểm phát bằng
tổng lượng hàng cần ở các điểm thu.
Hãy lập kế hoạch vận chuyển hàng hoá với tổng chi
phí là nhỏ nhất và đảm bảo yêu cầu thu phát.
14
Toán chuyên đề 4: QUY HOẠCH TUYẾN TÍNH
Điểm
thu
Điểm
phát T1:b1 T2:b2 … Tn:bn
P1:a1
c
11
c
12
…
c
1n
P2:a2
c
21
c
22
…
c
2n
… … … … …
Pm:am
c
m1
c
m2
…
c
mn
Minh hoạ dữ liệu bài toán:
15
Toán chuyên đề 4: QUY HOẠCH TUYẾN TÍNH
Gọi xij là lượng hàng cần chuyển từ Pi (i=1,2, ..,m)
đến Tj (i=1,2, ..,m). xij ≥ 0.
Lượng hàng chuyển đi từ Pi là:
xi1 + xi2 + … + xin = ai
……………………………………………
Lượng hàng chuyển đến Tj là:
x1j + x2j + … + xmj = bj
……………………………………………
Tổng chi phí vận chuyển là:
f = f(x11, x12, …, xmn) = c11x11 + c12x12 + … + cmnxmn
Giải:
16
Toán chuyên đề 4: QUY HOẠCH TUYẾN TÍNH
Mô hình toán học của bài toán
Tìm x = (x11, x12, …, xmn) sao cho
f(x) = c11x11 + c12x12 + … + cmnxmn ⟶ min
với các ràng buộc
x11 + x12 + … + x1n = a1
…………………………………….
xm1 + xm2 + … + xmn= am
x11 + x21 + … + xm1 = b1
…………………………………….
x1n + x2n + … + xmn = bn
x11, x12, …, xmn ≥ 0 .
17
Toán chuyên đề 4: QUY HOẠCH TUYẾN TÍNH
Bài tập:
Lập mô hình toán học của các bài toán sau:
1. Một xí nghiệp sản xuất ba loại sản phẩm A, B và
C chế tạo từ ba loại nguyên liệu I, II và III . Lượng
nguyên liệu I, II và III mà xí nghiệp có lần lượt là
20, 40, 30. Lượng nguyên liệu I, II, III cần cho một
đơn vị sản phẩm loại A lần lượt là 3, 3, 2, loại B lần
lượt là 3, 2, 1, loại C lần lượt là 2, 1, 1 đơn vị.
Hãy lập kế hoạch sản xuất để xí nghiệp thu tiền lãi
nhiều nhất, biết tiền lãi một đơn vị sản phẩm loại A
lãi 2 triệu đồng, loại B lãi 4 triệu đồng và loại C lãi
3 triệu đồng.
QUY HOẠCH TUYẾN TÍNH 02/09/2012
Chuongnn-hui.blogspot.com 4
Toán chuyên đề 4: QUY HOẠCH TUYẾN TÍNH
2. Một Xí nghiệp chăn nuôi cần mua thức ăn tổng
hợp T1, T2, T3 cho gia súc với tỷ lệ chất dinh
dưỡng là: 1 kg T1 chứa 3 đơn vị D1, 3 đơn vị D2 và
2 đơn vị D3; 1 kg T2 chứa 3 đơn vị D1, 2 đơn vị D2
và 1 đơn vị D3; 1 kg T3 chứa 2 đơn vị D1, 1 đơn vị
D2 và 1 đơn vị D3. Mỗi bữa ăn, gia súc cần tối thiểu
20 đơn vị D1, 40 đơn vị D2 và 30 đơn vị D3. Biết
rằng 1 kg T1 có giá là 2 ngàn đồng, 1 kg T2 có giá là
4 ngàn đồng, 1 kg T3 có giá là 3 ngàn đồng.
Hỏi Xí nghiệp phải mua bao nhiêu kg T1, T2, T3
cho một bữa ăn để bảo đảm tốt về chất dinh dưỡng
và tổng số tiền mua là nhỏ nhất?
Toán chuyên đề 4: QUY HOẠCH TUYẾN TÍNH
3. Một Xí nghiệp xử lý giấy có ba phân xưởng I, II,
III cùng xử lý ba loại giấy A, B, C. Nếu đầu tư 10
triệu đồng vào mỗi phân xưởng thì cuối năm phân
xưởng I xử lý được 3 tạ giấy A, 3 tạ giấy B, 2 tạ giấy
C, phân xưởng II xử lý được 3 tạ giấy A, 2 tạ giấy B,
1 tạ giấy C, phân xưởng III xử lý được 2 tạ giấy A, 1
tạ giấy B, 1 tạ giấy C.
Theo yêu cầu Xí nghiệp phải xử lý ít nhất 2 tấn giấy
loại A, 4 tấn giấy loại B, 3 tấn giấy loại C. Hỏi cần
đầu tư vào mỗi phân xưởng bao nhiêu tiền để xí
nghiệp hoàn thành công việc với giá tiền đầu tư là
nhỏ nhất.
Toán chuyên đề 4: QUY HOẠCH TUYẾN TÍNH
4. Một xí nghiệp chế biến đồ gỗ dùng 3000 đơn vị
gỗ nguyên liệu nhóm I, 5000 đơn vị gỗ nguyên liệu
nhóm II và 2000 đơn vị gỗ nguyên liệu nhóm III để
sản xuất tủ trang trí, bàn ghế và giường cao cấp.
Một bộ tủ trang trí bán giá 500000đ dùng 30 đơn
vị nhóm I, 10 đơn vị nhóm II và 10 đơn vị nhóm III.
Một bộ bàn ghế bán giá 800000đ dùng 40 đơn vị
nhóm I, 20 đơn vị nhóm II và 50 đơn vị nhóm III.
Một bộ giường bán giá 400000đ dùng 10 đơn vị
nhóm I, 50 đơn vị nhóm II và 80 đơn vị nhóm III.
Hãy xác định số lượng các sản phẩm cần sản xuất
sao cho xí nghiệp đạt lợi nhuận nhiều nhất?
Toán chuyên đề 4: QUY HOẠCH TUYẾN TÍNH
5. Một xí nghiệp có thể sử dụng tối đa 510 giờ máy
cán, 360 giờ máy tiện và 150 giờ máy mài để chế
tạo 3 sản phẩm A, B và C. Để chế tạo một sản phẩm
A cần 9 giờ máy cán, 5 giờ máy tiện và 3 giờ máy
mài; một sản phẩm B cần 3 giờ máy cán, 4 giờ máy
tiện; một sản phẩm C cần 5 giờ máy cán, 3 giờ máy
tiện và 2 giờ máy mài. Mỗi sản phẩm A trị giá 48
ngàn đồng, mỗi sản phẩm B trị giá 16 ngàn đồng và
mỗi sản phẩm C trị giá 27 ngàn đồng. Hãy cho biết
xí nghiệp cần chế tạo mỗi loại bao nhiêu sản phẩm
để có tổng giá trị sản phẩm lớn nhất.
Toán chuyên đề 4: QUY HOẠCH TUYẾN TÍNH
6. Một người nông dân muốn sản xuất lúa gạo và
lúa mì trên 50 ha đất của ông ta với nguồn nước
dự trữ là 90 ngàn m3 nước và nguồn nhân lực gổm
250 công. Biết rằng để sản xuất 1 tấn lúa gạo cần
sử dụng 3 ha đất, 5 ngàn m3 nước và 15 công với
lợi nhuận là 18 USD, để sản xuất một tấn lúa mì
cần sử dụng 3 ha đất, 4 ngàn m3 nước và 12 công
với lợi nhuận là 21 USD.
Hỏi người nông dân phải sản xuất bao nhiêu tấn
lúa mỗi loại để đạt lợi nhuận cao nhất.
Toán chuyên đề 4: QUY HOẠCH TUYẾN TÍNH
7. Một xưởng làm cửa sắt có những thanh thép dài
12 m, cần cắt thành 8 đoạn dài 4m, 5 đoạn dài 5m
và 3 đoạn dài 7m. Có 5 mẫu cắt sau. Mẫu 1: 3 đoạn
dài 4m, không thừa. Mẫu 2: 1 đoạn 4m, 1 đoạn 5m,
thừa 3m. Mẫu 3: 1 đoạn 4m, 1 đoạn 7m, thừa 1m.
Mẫu 4: 2 đoạn 5m, thừa 2m. Mẫu 5: 1 đoạn 5m, 1
đoạn 7m, không thừa.
Hỏi cần dùng những mẫu cắt nào để tiết kiệm nhất.
QUY HOẠCH TUYẾN TÍNH 02/09/2012
Chuongnn-hui.blogspot.com 5
Toán chuyên đề 4: QUY HOẠCH TUYẾN TÍNH
8. Một xưởng sản xuất dự định mua hai loại máy để
in hình vẽ trên vải. Máy A có thể in 100m/phút và
chiếm 50 mét vuông diện tích sàn, còn máy B có
thể in 200m/phút và chiếm 140 mét vuông diện
tích sàn. Xưởng cần in ít nhất 600m/phút và có
diện tích sàn để đặt máy in tối đa là 350 mét
vuông. Mỗi máy A có giá là 22 triệu đồng và mỗi
máy B có giá 42 là triệu đồng.
Hỏi cần mua bao nhiêu máy in mỗi loại sao cho tốn
ít chi phí nhất.
Toán chuyên đề 4: QUY HOẠCH TUYẾN TÍNH
BÀI TOÁN QUY HOẠCH TUYẾN TÍNH
VÀ Ý NGHĨA HÌNH HỌC
26
Toán chuyên đề 4: QUY HOẠCH TUYẾN TÍNH
Bài toán quy hoạch tuyến tính tổng quát
Tìm x = (x1, x2, … , xn) sao cho
f(x) = c1x1 + c2x2 + … + cnxn ⟶ max(min) (1)
với các ràng buộc
ai1x1 + ai2x2 + … + ainxn ≤ bi, i ∊ I1 (2)
ai1x1 + ai2x2 + … + ainxn ≥ bi, i ∊ I2 (3)
ai1x1 + ai2x2 + … + ainxn = bi, i ∊ I3 (4)
xj ≥ 0, j ∊ J1 (5) .
xj ≤ 0, j ∊ J2 (6) .
xj ∊ ℝ, j ∊ J3 (7) .
Với I1∪I2∪I3={1,2,…,m},
I1∩I2∩I3=∅
và J1∪J2∪J3={1,2,…,n},
J1∩J2∩J3=∅
Toán chuyên đề 4: QUY HOẠCH TUYẾN TÍNH
Ví dụ:
+ f(x) = x1 – 2x3 – x4 – 2x6 ⟶ max
x1 + 2x2 – x4 + x5 ≤ 8
x1 – 3x3 – x4 + 3x6 ≥ 2
2x1 + x2 + x3 – x4 = 5
– x1 + x3 + 2x4 – 3x5 ≥ 6
2x2 – 2x3 – x4 – 2x6 ≤ 11
x1, x4 ≥ 0
x2, x3, x6 ≤ 0
x5 ∊ ℝ
Toán chuyên đề 4: QUY HOẠCH TUYẾN TÍNH
Một số khái niệm
Hàm mục tiêu: hàm f(x) = c1x1 + c2x2 + … + cnxn
Phương án: vectơ x = (x1, x2, … , xn) thoả mãn các
điều kiện ràng buộc từ (2) đến (7).
Phương án tối ưu: phương án làm cho hàm mục
tiêu đạt max hay min nghĩa là thoả mãn (1).
Tập phương án tối ưu: tập hợp tất cả các phương
án của bài toán.
Giải bài toán quy hoạch tuyến tính: là tìm phương
án tối ưu cho bài toán.
Toán chuyên đề 4: QUY HOẠCH TUYẾN TÍNH
Dạng chính tắc của bài toán quy hoạch tuyến tính
Tìm x = (x1, x2, … , xn) sao cho
f(x) = c1x1 + c2x2 + … + cnxn ⟶ max(min)
ai1x1 + ai2x2 + … + ainxn = bi, i = 1, 2, …, m
xj ≥ 0, j = 1, 2, …, n .
hay f(x) = ∑cjxj ⟶ max(min)
∑aijxj = bi, i = 1, 2, …, m
xj ≥ 0, j = 1, 2, …, n .
Lưu ý: Mọi bài toán quy hoạch tuyến tính đều có
thể biến đổi đưa về dạng chính tắc.