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

Chia sẻ: Hoàng Quốc Trung | Ngày: | Loại File: PDF | Số trang:13

Thêm vào BST

Báo xấu

101
lượt xem 5
download

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

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à...

Chủ đề:

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

Lưu

Nội dung Text: Tối ưu hóa tuyến tính

T I ƯU HÓA TUY N TÍNH Chương 2 Financial 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í => max Financial 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 (2.3) (gi i h n chính sách h p đ ng) • 4x1+ 4x2 ≤ 760 (2.4) (gi i h n chân gh ) • x1 ≤ 140 và x2≤ 120 (2.5) (gi i h n ph tùng g3,g4) • x1 ≥ 0 và x2 ≥ 0 (2.6) (gi i h n t nhiên) • Lưu ý: Bài toán trên là bài toán t i ưu hoá tuy n tính vì t t c hàm m c tiêu và ràng bu c đ u là b c nh t (tuy n tính). Financial Modeling 10 5
Financial Modeling 11 2.3 NGH THU T L P BÀI TOÁN QUY HO CH TUY N TÍNH •Di n đ t m c tiêu b ng t ng và đo lư ng k t qu th c hi n c a hàm m c tiêu. •Di n đ t b ng t ng m i m t ràng bu c, xác l p các yêu c u c a t ng ràng bu c m t các c n tr ng theo đó nh ng yêu c u này là ≥; ≤ hay = •Xác đ nh các bi n s ra quy t đ nh. M t đi u r t quan tr ng là các bi n s ra quy t đ nh c n đư c xác đ nh chính xác. Đôi lúc b n c m th y r ng có m t vài kh năng ch n l a. Ví d , b n nên •Di n đ t m i m t ràng bu c b ng nh ng ký hi u theo bi n s ra quy t đ nh. •Di n đ t m i m t hàm m c tiêu b ng nh ng ký hi u theo bi n s ra quy t đ nh. Financial Modeling 12 6
2.4 CHI PHÍ CHÌM VÀ CHI PHÍ BI N Đ I • Chi phí chìm là nh ng chi phí đã b ra và nh ng quy t đ nh trong tương lai không th tác đ ng hay s a đ i đư c gì đ i v i nh ng chi phí đã chi tiêu này. Vì th , chi phí chìm không đưa vào mô hình t i ưu hóa. • Chi phí bi n đ i là nh ng thông s đ u vào (bi n ngo i sinh) nên đư c tính vào trong mô hình t i ưu hoá. Financial Modeling 13 2.5 GI I QUY T MÔ HÌNH T I ƯU HÓA B NG B NG TÍNH • Mô hình t i ưu hóa c a công ty C đư c th hi n trên b ng tính Financial Modeling 14 7
2.5 GI I QUY T MÔ HÌNH T I ƯU HÓA B NG B NG TÍNH • M i m t bi n s quy t đ nh đư c trình bày trong các ô khác nhau, thư ng đư c nhóm l i v i nhau theo dòng hay c t • M i m t ràng bu c đư c trình bày trong các dòng và c t riêng r trong m t b ng tính. • Các bi n s ra quy t đ nh đư c nhóm l i v i nhau theo các c t/các dòng li n k nhau và các ràng bu c đư c nhóm l i v i nhau theo các dòng/c t li n k nhau. • M i m t ô bi n s ra quy t đ nh và ô hàm m c tiêu ph i đư c đ t tên t i ô trên cùng c a c t đó. Và m i m t ràng bu c ph i đư c đ t tên t i ô bên trái ngoài cùng c a dòng đó. • Các thông s đư c đ t trong các ô n m trong các dòng riêng bi t li n k ngay bên trên hay bên dư i các bi n s ra quy t đ nh đ ph n ánh tác đ ng t nh ng h s này và công th c hàm m c tiêu xu t hi n g n k ngay bên c nh nh ng ô này. Financial Modeling 15 2.5 GI I QUY T MÔ HÌNH T I ƯU HÓA B NG B NG TÍNH • Các ô bi n s ra quy t đ nh và ô hàm m c tiêu đư c đ nh d ng n i b t b ng cách tô n n hay t o đư ng vi n • Đ i v i m i m t ràng bu c, ô ch a các thông s liên quan đ n bi n s ra quy t đ nh đư c đ t t i góc giao nhau gi a c t ho c dòng ch a các bi n s ra quy t đ nh đó và nh ng c t ho c dòng ch a các đi u ki n ràng bu c đó. • Đ i v i các dòng ràng bu c thì ô th hi n n i dung c a v bên ph i b t đ ng th c ch đư c ch a h ng s ho c công th c không có liên quan đ n các bi n s ra quy t đ nh. Đ tránh vi c Solver s báo l i sau này, b t kỳ m t công th c nào c a ô th hi n n i dung c a v bên ph i b t đ ng th c có liên quan tr c ti p hay gián ti p t i các bi n s ra quy t đ nh ph i đư c c t chuy n sang v bên trái c a c a ràng bu c đó. Financial Modeling 16 8
2.5 GI I QUY T MÔ HÌNH T I ƯU HÓA B NG B NG TÍNH Thu t ng quy ho ch tuy n tính Thu t ng Solver Hàm m c tiêu Ô m c tiêu (Set target cell) Các bi n s ra quy t ñ nh Bi n s ra quy t ñ nh (By changing cells) Các ñi u ki n ràng bu c Ràng bu c (Subject to the constraints/add) Hàm ràng bu c (V trái c a b t ñ ng th c) Tham chi u ô ràng bu c (Cell reference) Gi i h n ràng bu c- V ph i b t ñ ng th c Các ràng bu c ho c gi i h n (Constraint) Gi ñ nh mô hình tuy n Mô hình tuy n tính LP Financial Modeling 17 2.5 GI I QUY T MÔ HÌNH T I ƯU HÓA B NG B NG TÍNH • Kích ho t Solver Financial Modeling 18 9
2.5 GI I QUY T MÔ HÌNH T I ƯU HÓA B NG B NG TÍNH • H p tho i Solver Financial Modeling 19 2.5 GI I QUY T MÔ HÌNH T I ƯU HÓA B NG B NG TÍNH • Gi đ nh tuy n tính Financial Modeling 20 10
2.5 GI I QUY T MÔ HÌNH T I ƯU HÓA B NG B NG TÍNH • H p tho i Answer c a Solver Financial Modeling 21 2.5 GI I QUY T MÔ HÌNH T I ƯU HÓA B NG B NG TÍNH • K t qu mô hình t i ưu hóa c a Công ty C Financial Modeling 22 11
2.5 GI I QUY T MÔ HÌNH T I ƯU HÓA B NG B NG TÍNH • Báo cáo đ nh y c a công ty C Financial Modeling 23 2.5 GI I QUY T MÔ HÌNH T I ƯU HÓA B NG B NG TÍNH • Hình th c khác c a báo cáo đ nh y Financial Modeling 24 12
2.6 T I ƯU HÓA KHI NGU N V N B GI I HN • Khung tình hu ng: D án Năm 0 Năm 1 Năm 2 Năm 3 NPV (r = 10%) W – 70 – 20 60 60 6,44 X ––– – 90 60 50 5,30 Y – 80 10 60 30 1,18 Z ––– – 50 30 30 1,86 • V n đ u tư hi n t i và năm th nh t không vư t quá 100 t đ ng Financial Modeling 25 2.6 T I ƯU HÓA KHI NGU N V N B GI I HN • Bư c 1: Bài toán t i ưu hóa tuy n tính • NPV = 6,44w + 5,30 x + 1,18y + 1,86z –> max • Các đi u ki n ràng bu c: 70w + 80y ≤ 100 • 20w + 90 x – 10y + 50z ≤ 100 • 0 ≤ w ≤ 1 ; 0 ≤ x≤ 1 ; 0 ≤ y ≤ 1 ; 0 ≤ z ≤ 1 • Financial Modeling 26 13