Qui hoạch tuyến tính

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...
Nội dung trích xuất từ tài liệu:
Qui hoạch tuyến tính QUI HOẠCH TUYẾN TÍNH1. Bài toán QHTT và các tính chất2. Giải bài toán QHTT 3. Các cặp bài toán đối ngẫu  11. Bài toán QHTT & các tính chất1.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ấtTì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 x4Mô 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: 3Mô 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 4b) 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ỷ 5Tì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 trungbình lớn nhất. 6Mô 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 71.2. Bài toán QHTTa)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} 8a) 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àngbuộ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ấtphươ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ếntí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ớimột vectơ cột Aj =(a1j,a2j,..,amj)T, gọi là vectơ điềukiện. 9a) 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ộtphương án (PA) của bài toán QHTT, D là tập cácPA của bài toán. Nếu ràng buộc thứ i thỏa dấu “=“ với phương ánX, thì ta nói ràng buộc thứ i chặt đối với X. Ngượclạ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àitoán QHTT) PACB thỏa đúng n ràng buộc chặt gọi là PACBkhông suy biến 10a) 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 11b) Các tính chất của bài toán QHTTTC1: 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 s ...