Thư viện tri thức trực tuyến
Kho tài liệu với 50,000+ tài liệu học thuật
© 2023 Siêu thị PDF - Kho tài liệu học thuật hàng đầu Việt Nam
Chương1: BÀI TOÁN QUY HOẠCH TUYẾN TÍNH ppt
Nội dung xem thử
Mô tả chi tiết
QUY HOẠCH TUYẾN TÍNH 02/09/2012
Chuongnn-hui.blogspot.com 1
Chương1: BÀI TOÁN QUY HOẠCH TUYẾN TÍNH
MỘT SỐ BÀI TOÁN MỞ ĐẦU
Chương1: BÀI TOÁN 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
Chương1: BÀI TOÁN 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 … amn bm
Tiền lãi/đơn vị
sản phẩm c1
c2 … cn
Minh hoạ dữ liệu bài toán:
Chương1: BÀI TOÁN 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:
Chương1: BÀI TOÁN 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.
Chương1: BÀI TOÁN 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.