Tối ưu hóa tuyến tính

Miền xác định A của hàm f được gọi là không gian tìm kiếm. Thông thường, A là một tập con của không gian Euclid Rn, thường được xác định bởi một tập các ràng buộc, các đẳng thức hay bất đẳng thức mà các thành viên của A phải thỏa mãn. Các phần tử của A được gọi là các lời giải khả thi. Hàm f được gọi là hàm mục tiêu, hoặc hàm chi phí. Lời giải khả thi nào cực tiểu hóa (hoặc cực đại hóa, nếu đó là mục đích) hàm mục tiêu được gọi là...
Nội dung trích xuất từ tài liệu:
Tối ưu hóa tuyến tính T I ƯU HÓA TUY N TÍNH Chương 2Financial Modeling 1 2.1 BÀI TOÁN QUY HO CH TUY N TÍNH• M i mô hình quy ho ch tuy n tính đ u có 2 đ c đi m quan tr ng: m t hàm m c tiêu đư c t i đa hóa ho c t i thi u hóa, và các đi u ki n ràng bu c.• Bài toán quy ho ch tuy n tính còn đư c g i là mô hình t i ưu hóa đ i ng u.• M t mô hình t i ưu hóa đ i ng u trình bày m t v n đ v phân b ngu n l c b gi i h n sao cho t i ưu hóa m c tiêu v l i ích.Financial Modeling 2 1 2.1 BÀI TOÁN QUY HO CH TUY N TÍNH• Các đi u ki n ràng bu c• Các ràng bu c có th đư c xem như là t t c nh ng gi i h n mà các bi n s ra quy t đ nh ph i tuân theo.• Có 2 lo i ràng bu c: ràng bu c t nh ng h n ch và ràng bu c t nh ng yêu c u đòi h i.• Ho c có th phân lo i ràng bu c như: ràng bu c mang tính t nhiên; ràng bu c mang tính kinh t ; ho c ràng bu t do chính sách chi ph i.Financial Modeling 3 2.1 BÀI TOÁN QUY HO CH TUY N TÍNH• Nhà qu n lý danh m c b ràng bu c b i h n ch v ngu n v n (gi i h n mang tính t nhiên) và nh ng quy đ nh c a y ban ch ng khóan (gi i h n do chính sách).• Các quy t đ nh s n xu t b ràng bu c v gi i h n kh năng s n xu t (gi i h n t nhiên) và ngu n l c có s n (gi i h n v kinh t và gi i h n t nhiên).• M t doanh nghi p không th chi tr c t c n u không có l i nhu n (gi i h n t nhiên) hay khi t su t l i nhu n không vư t qua m t m c t i thi u nào đó (gi i h n chính sách).Financial Modeling 4 2 2.1 BÀI TOÁN QUY HO CH TUY N TÍNH• Hàm m c tiêu:• Thông s đo lư ng k t qu th c hi n đư c các nhà qu n lý mong mu n t i đa hóa (ch ng h n l i nhu n, t su t sinh l i, hi u năng, ho c tính hi u qu ) ho c t i thi u hóa (như chi phí ho c th i gian).• Nhà qu n lý danh m c có th mu n t i đa hóa t su t sinh l i c a danh m c, và giám đ c s n xu t có th mu n chi phí s n xu t là th p nh t. Tương t hãng hàng không mu n có m t l ch trình bay sao cho t i thi u hóa chí phí và công ty d u khí mu n khai thác các m d u hi n có sao cho t i đa hóa l i nhu n.Financial Modeling 5 2.2 VÍ D V BÀI TOÁN QUY HO CH TUY N TÍNH• Khung tình hu ng:• Ph n bù đ nh phí đơn v (giá bán tr bi n phí đơn v ) là 56$ cho Sp1 và 40$ cho Sp2.• Các ph tùng g1, g2, g3, g4 là có gi i h n và không th tăng thêm.• D tr ph tùng là: g1= 1.280; g2=1.600; Sp1 s d ng 8 g1 và 4 g2. Đ i v i Sp2 s d ng 4 g1 và 12 g2.• T n kho chân gh là 760 đơn v . M i chi c gh s n xu t ra c n 4 chân gh .• T n kho ph tùng g3 và g4 là 140 và 120 đơn v . Đ s n xu t Sp1 và Sp2 đ u s d ng ph tùng g3 và g4 như nhau.• Theo h p đ ng t ng s lư ng s n xu t trong tu n không đư c th p hơn 100 s n ph m.Financial Modeling 6 3 2.2 VÍ D V BÀI TOÁN QUY HO CH TUY N TÍNH Lo i ph tùng Sp1 Sp2 T ng s g1 8 4 1280 g2 4 12 1600 Chân gh 4 4 760 g3 1 0 140 g4 0 1 120 Financial Modeling 7 2.2 VÍ D V BÀI TOÁN QUY HO CH TUY N TÍNH• Bi n s ra quy t đ nh:• Các c p giá tr x1 và x2 đ i di n cho s lư ng SP1 và SP2• Các c p giá tr x1 và x2 ph i n m trong t p h p các quy t đ nh kh thi (không vi ph m các ràng bu c do gi i h n t nhiên và gi i h n chính sách).Financial Modeling 8 4 2.2 VÍ D V BÀI TOÁN QUY HO CH TUY N TÍNH• Hàm m c tiêu:• Công ty C có m c tiêu là t i đa hóa l i nhu n và m c tiêu này là k t h p 2 m c tiêu thành ph n:• T ng ph n bù đ nh phí đ t đư c t doanh s c a Sp1• T ng ph n bù đ nh phí đ t đư c t doanh s c a Sp2• Ph n bù đ nh phí đơn v c a Sp1 là 56$ và c a Sp2 là 40$. Chúng ta có hàm m c tiêu sau:• 56x1 + 40x2 = t ng ph n bù đ nh phí => maxFinancial Modeling 9 2.2 VÍ D V BÀI TOÁN QUY HO CH TUY N TÍNH• Bài toán quy ho ch tuy n tính• 56x1 + 40x2 –> max (hàm m c tiêu)• 8x1 + 4x2 ≤ 1280 (2.1) (gi i h n ph tùng g1)• 4x1 + 12x2 ≤ 1600 (2.2) (gi i h n ph tùng g2)• x1 +x2 ≥ 100 ...