Bài giảng Toán tài chính - Chương 5b: Quy hoạch tuyến tính hai biến

Bài giảng "Toán tài chính - Chương 5b: Quy hoạch tuyến tính hai biến" cung cấp cho người học các kiến thức: Bài toán quy hoạch tuyến tính tổng quát, dạng ma trận của bài toán quy hoạch tuyến tính, bài toán dạng chuẩn tắc,... Mời các bạn cùng tham khảo.
Nội dung trích xuất từ tài liệu:
Bài giảng Toán tài chính - Chương 5b: Quy hoạch tuyến tính hai biến QUY HOẠCH CHƯƠNG TUYẾN TÍNHHAI BIẾN + … 5BVÍ DỤ 1Một xí nghiệp cần sản xuất 3 loại bánh: bánh đậu xanh,bánh thập cẩm và bánh dẻo. Lượng nguyên liệu đường,đậu cho một bánh mỗi loại, lượng dự trữ nguyên liệu,tiền lãi cho một bánh mỗi loại được cho trong bảng sau:Hãy lập mô hình bài toán tìm số lượng mỗi loại bánh cầnsản xuất sao cho không bị động về nguyên liệu mà lãi đạtđược cao nhất.VÍ DỤ 1Gọi x1,x2,x3 lần lượt là số bánh đậu xanh, bánh thậpcẩm, bánh dẻo cần phải sản xuất.Điều kiện: xj ≥ 0 = 1,2,3Tiền lãi thu được (ngàn đồng) f  x   f  x1 , x2 , x3   3 x1  2 x2  2,5 x3Lượng đường sử dụng và điều kiện: 0,04 x1  0,06 x2  0,05 x3  500Lượng đậu sử dụng và điều kiện: 0,07 x1  0,02 x3  300VÍ DỤ 1Vậy ta có mô hình bài toán: f  x   f  x1 , x2 , x3   3 x1  2 x2  2,5 x3  max 0,04 x1  0,06 x2  0,05 x3  500  0,07 x1  0,02 x3  300  x  0 j  1, 2,3  j  Đây là bài toán quy hoạch tuyến tính 3 biến, tìm giá trịlớn nhất của hàm mục tiêu. VÍ DỤ 2Giả sử yêu cầu tối thiểu mỗi ngày về các chất dinh dưỡngđạm, đường, khoáng cho một loại gia súc tương ứng là 90g,130g, 10g. Cho biết hàm lượng các chất dinh dưỡng trên cótrong 1g thức ăn A, B, C và giá mua 1kg thức ăn mỗi loại đượccho trong bảng sau:Hãy lập mô hình toán học của bài toán xác định khối lượngthức ăn mỗi loại phải mua để tổng số tiền chi cho mua thứcăn ít nhất nhưng đáp ứng được nhu cầu dinh dưỡng mỗingày. VÍ DỤ 3Một cơ sở sản xuất đồ gỗ dự định sản xuất ba loại sản phẩm làbàn, ghế và tủ. Định mức sử dụng lao động, chi phí sản xuất và giábán mỗi sản phẩm mỗi loại ước tính trong bảng sau:Hãy lập mô hình toán học của bài toán xác định số sản phẩm mỗiloại cần phải sản xuất sao cho không bị động trong sản xuất vàtổng doanh thu đạt được cao nhất, biết rằng cơ sở có số lao độngtương đương với 500 ngày công, số tiền dành cho chi phí sản xuấtlà 40 triệu đồng và số bàn, ghế phải theo tỉ lệ 1/6.VÍ DỤ 4Một trại cưa các khúc gỗ thành các tấm ván. Có hai loạiván: ván thành phẩm và ván sử dụng trong xây dựng. Giảsử, đối với:Ván thành phẩm cần 2 giờ để cưa và 5 giờ để bào 10mvánVán xây dựng cần 3 giờ để cưa và 3 giờ để bào 10m vánMáy cưa làm việc tối đa 8 giờ trong ngày và máy bào làmviệc tối đa 15 giờ trong ngày. Nếu lợi nhuận của 10m vánthành phẩm là 120 (ngàn đồng) và lợi nhuận của 10m vánxây dựng là 100 (ngàn đồng). Trong ngày, trại cưa phảicưa bao nhiêu ván mỗi loại để lợi nhuận lớn nhất. BÀI TOÁN QHTT TỔNG QUÁT 1 f  x   c1 x1  c2 x2  ...  cn xn  min (max)    2  ai1 x1  ai 2 x2  ...  ain xn   bi  i  1, 2,.., m      0   3 x j  0  j  1, 2,..., n tuy y (1) Hàm f(x) gọi là hàm mục tiêu(2) là hệ ràng buộc chính(3) là hệ ràng buộc dấu(2) Và (3) gọi chung là hệ ràng buộc của bài toánDẠNG MA TRẬN CỦA BÀI TOÁN QHTTXét bài toán QHTT dạng: f  x   c1 x1  c2 x2  ...  cn xn  min (max) a11 x1  a12 x2  ...  a1n xn  b1  a21 x1  a22 x2  ...  a2 n xn  b2  .......................................... am1 x1  am 2 x2  ...  amn xn  bm xj  0DẠNG MA TRẬN CỦA BÀI TOÁN QHTTĐặt:  a11 a12 ... a1n   b1   x1   c1          a a ... a b2  x2  c2 A   21 22 2n  b  x  c   ....................   ...   ...   ...           am1 am 2 ... amn   bm   xn   cn Ta có dạng ma trận của bài toán QHTT: f  cT x  min  max   Ax  b  x  0 BÀI TOÁN DẠNG CHÍNH TẮC: n f  x    cj x j  min (max) • Các ràng buộc j 1 chính đều là n phương trình  aij x j  bi (i  1,m) • Các ẩn đều  j1 không âm x  0 (j  1,n)  jMọi bài toán quy hoạch tuyến tính đều có thể quy về bàitoán dạng chính tắc tương đương theo nghĩa trị tối ưucủa hàm mục tiêu trong hai bài toán là trùng nhau và từphương án tối ưu của bài toán này suy ra phương án tốiưu của bài toán kia BÀI TOÁN DẠNG CHUẨN TẮC n• Các hệ số tự do bi f  x    cj x j  min (max) j 1 không âm (bi ≥ 0)• Trong ma trận hệ số  n  aij x j  bi (i  1,m) có đủ m vecto cột  j 1 đơn vị: e1, e2,…,em x  0 (j  1,n)  j 1  0  0  0  1  0  e1    e2    em     ...   ...   ...        0  0  1 VÍ DỤ 5Bài toán sau có dạng chính tắc: 260 x1  120 x2  600 x3  max 2 x1  x2  3 x3  500  100 x1  40 x2  250 x3  40000  6 x1  x2  x1 , x2 , x3  0VÍ DỤ 6Xét bài toán QHTT sau: f  x   2 x1  4 x2  x3  6 x4  max  x1  x4  x5  12 12 x  x  x  3  1 3 6 x  x  x  x  6  1 2 3 4  x j  0  j  1, 2,...,6 ...