Qui hoạch tuyến tính

Chia sẻ: Lan Lan | Ngày: | Loại File: PDF | Số trang:70

Thêm vào BST

Báo xấu

152
lượt xem 17
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Biết hao phí nguyên liệu, nguyên liệu dự trữ, lợi nhuận thu được từ mỗi đơn vị sản phẩm cho trong bảng (1). Lập kế hoạch sản xuất (xác định khối lượng sản phẩm mỗi loại), để doanh nghiệp đạt lợi nhuận tối đa, trong điều kiện nguyên liệu dự trữ hiện có, và các yếu tố sản xuất...

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Qui hoạch tuyến tính

QUI HOẠCH TUYẾN TÍNH 1. Bài toán QHTT và các tính chất 2. Giải bài toán QHTT  3. Các cặp bài toán đối ngẫu  1
1. Bài toán QHTT & các tính chất 1.1. Một vài bài toán trong kinh tế a) Bài toán lập kế hoạch sản xuất Tình huống: Một doanh nghiệp dự định sản xuất 4 loại sản phẩm S1, S2, S3, S4 từ 3 loại nguyên liệu N1, N2, N3. Biết hao phí nguyên liệu, nguyên liệu dự trữ, lợi nhuận thu được từ mỗi đơn vị sản phẩm cho trong bảng (1). Lập kế hoạch sản xuất (xác định khối lượng sản phẩm mỗi loại), để doanh nghiệp đạt lợi nhuận tối đa, trong điều kiện nguyên liệu dự trữ hiện có, và các yếu tố sản xuất khác doanh nghiệp 2 luôn có đủ.
Bảng 1 Nguyên liệu S1 S2 S3 S4 Nguyên liệu dự trữ N1 a11 a12 a13 a14 b1 N2 a21 a22 a23 a24 b2 N3 a31 a32 a33 a34 b3 Lợi nhuận c1 c2 c3 c4 X= x1 x2 x3 x4 Mô hình toán: Gọi xj là khối lượng sản phẩm loại Sj mà doanh nghiệp cần sản xuất j=1,2,3,4; F là tổng lợi nhuận. Ta có bài toán sau: 3
Mô hình toán bài toán lập kế hoạch sản xuất F=c1x1+c2x2+c3x3+c4x4Max a11x1+a12x2+a13x3+a14x4  b1 a21x1+a22x2+a23x3+a24x4  b2 a41x1+a32x2+a33x3+a34x4 b3 xj 0 j 4
b) Bài toán lựa chọn danh mục đầu tư Tình huống: Một công ty đầu tư dự định dùng khoản quỹ 500 tỷ để mua một số cổ phiếu trên thị trường chứng khoán. Biết lãi suất của các loại cổ phiếu, và giới hạn mua các loại cổ phiếu cho trong bảng sau: Loại chứng Lãi suất Giới hạn khoán năm A 7% 100 tỷ B 8.5% 300 tỷ C 7.8% 250 tỷ D 8.2% 320 tỷ 5
Tình huống. Để ngăn ngừa rủi ro quỹ đầu tư quy định khoản đầu tư vào cổ phiếu A, C phải chiếm ít nhất 55%, cổ phiếu B chiếm ít nhất 15% trong tổng số tiền đầu tư. Xác định số tiền công ty mua từng loại cổ phiếu (một danh mục đầu tư) sao cho không vượt quá các khoản dự kiến ban đầu, có mức lãi suất trung bình lớn nhất. 6
Mô hình toán: Gọi xA,xB,xC,xD là các khoản tiền mà quỹ dùng để mua các loại cổ phiếu của các công ty tương ứng. Bài toán đặt ra là tìm danh mục đầu tư (xA,xB,xC,xD) thỏa: F = 0.07xA+0.085xB+0.078xC+0.082xDMax xA+xC0.55(xA+xB+xC+xD) xB 0.15(xA+xB+xC+xD) xA+xB+xC+xD500 0xA 100 0 xB 300 0 xC 250 0 xD 320 7
1.2. Bài toán QHTT a)Các khái niệm về bài toán QHTT n F   c j x j  Min / Max (1) j=1 n    a ij x j  b i i  I1  j=1n  a x  b i I (2)   ij j i 2 j=1 I1, I2, I3I={1,2,..m} 8
a) Các khái niệm về bài toán QHTT F(X) được gọi là hàm mục tiêu, hệ (2) là hệ ràng buộc của bài toán QHTT. Với mỗi iI ta có một phương trình hoặc một bất phương trình gọi là ràng buộc thứ i. Với mỗi iI, ta có một véctơ dòng: A*i=(ai1, ai2, .., ain) Hệ {A*j} tạo thành một ma trận Amn=(aij). Hệ ràng buộc có hệ các véctơ {A*i} độc lập tuyến tính được gọi là hệ ràng buộc độc lập. Trong hệ ràng buộc (2), mỗi ẩn xj tương ứng với một vectơ cột Aj =(a1j,a2j,..,amj)T, gọi là vectơ điều kiện. 9
a) Các khái niệm về bài toán QHTT Vectơ X=(x1,x2,..,xn) thỏa hệ (2), gọi là một phương án (PA) của bài toán QHTT, D là tập các PA của bài toán. Nếu ràng buộc thứ i thỏa dấu “=“ với phương án X, thì ta nói ràng buộc thứ i chặt đối với X. Ngược lại ta nói ràng buộc thứ i lỏng đối với X. Một PA thỏa chặt n ràng buộc độc lập, gọi là phương án cực biên (PACB). (n là số ẩn số của bài toán QHTT) PACB thỏa đúng n ràng buộc chặt gọi là PACB không suy biến 10
a) Các khái niệm về bài toán QHTT PACB thỏa nhiều hơn n ràng buộc chặt gọi là PACB suy biến. X* là PATƯ khi và chỉ khi thỏa 2 điều kiện sau: Với FMin: 1) X*  D 2) F(X*)  F(X) X  D Với FMax: 1) X*  D 2) F(X*)  F(X) X  D 11
b) Các tính chất của bài toán QHTT TC1: Nếu bài toán QHTT có tập các phương án D, và r(A)=n, thì bài toán có PACB. TC2: Nếu bài toán QHTT có tập các phương án D, và F(X) bị chặn /D thì có PATƯ. TC3: Bài toán QHTT có và chỉ có 3 khả năng sau: 1) Bài toán không có PATƯ 2) Bài toán có duy nhất 1 PATƯ 3) Bài toán có vô số PATƯ 12
TD1: F=3x1+x2+2x3+x4Min x2 -x3 + x4 =0 x1-4x2 +3x4 15 2x1 -x3 + x4 -2 xj0 j a) Chứng tỏ bài toán có PACB, chỉ ra một PACB suy biến, một PACB không suy biến, PA không cực biên b) Chứng tỏ bài toán có PATƯ Giải: a) r(A)=4 Bài toán có PACB X0=(0,0,0,0) là PACB suy biến X1=(1,0,0,0) là PACB không suy biến X=(16,1,2,1) là PA không cực biên 13
b) Vì xj0 j  F(X)0 Bài toán có D, và F(X) bị chặn dưới nên có PATƯ Bài tập: 1) Cho bài toán QHTT F=-4x2-3x3-x4-3x5-x6Max x1-2x2+x3 -2x5 20 3x2 -x3+x4+ x5 -11 x2+4x3 +2x5+x6 -3 Chứng tỏ bài toán có PATƯ; Tìm một PATƯ HD: Lấy BPT (2)+BPT(3) F(X)14 PATƯ X*=(x1,0,0,-11,0,-3) 14
2) Cho bài toán QHTT (HVNH năm 2001) F = 5x1 – 4x2 + 2x3 + 3x4  Min 3x1 – 2x2 + x3 + 2x4  20 x1 + x2 – 3x3 + 2x4  –15 2x1 – 2x2 + x3 + x4  30 a)Bài toán có PACB hay không? b)Chứng tỏ bài toán có PATƯ c)Có kết luận gì khi vectơ b thay đổi? HD: Lấy BPT(1)+BPT(3)F(X)50; D Bài toán có PATƯ 15
3) Cho bài toán QHTT F = –4x1 –5x2 + 2x3  Min/ Max x1 + 3x2 –3x3 = 17 –x1 – x2 + 2x3  2 4x1 + 5x2 –2x3  43 2x1 – x2 + 8x3 = –1 x3  0 a) Xác định tập các PA và các PACB b) Chứng tỏ bài toán có PATƯ và chỉ ra PATƯ của hai bài toán Min/ Max HD: F=103  XD đều là PATƯ 16
2. Giải bài toán QHTT 2.1. Phân loại bài toán QHTT a) Bài toán n tổng quát F   c j x j  Min/Max (1) j=1  n  ax ij j bi i I1  j=1n   aij x j  bi i  I2 ( 2)  j=1  n   aij x j  bi i  I3  j=1  x  0 j  1..n (3)  j 17 
2.1. Phân loại bài toán QHTT b) Bài toán chính tắc n F   c j x j  Min/Max ( 4) j=1 n  aij x j  bi i  1, 2..m (5)  j=1  x j  0 j  1, 2..n i ( 6)  18
2.1. Phân loại bài toán QHTT c) Bài toán cơ bản 1 khi k  i Ẩn xj là ẩn cơ sỏ của PT thứ i nếu: akj   0 khi k  i Bài toán cơ bản là bài toán chính tắc nếu mỗi phương trình trong hệ ràng buộc có một ẩn cơ sở. TD: F= 2x1+3x2-x3-3x4+x5Min -2x1 +x3 +3x5 =3 3x1+x2 -2x5 =5 x1 +x4 +x5 =1 xj0 j=1,2..5 Bài toán có PACB X0=(0,5,3,1,0) 19
2.1. Phân loại bài toán QHTT c) Bài toán cơ bản n F   c j x j  Min/Max (7 ) j=1   xB i   aij x j  bi i  1, 2..m (8)  jB x j  0 j  1, 2..n; bi  0 i  1, 2..m (9)  XBi là ẩn cơ sở của phương trình thứ i; B là tập các chỉ số của các ẩn cơ sở. 0 bi khi j  Bi  B Bài toán CB có PACB: X0  (x )   j 0 khi j  B 20