Bài giảng Mô hình toán kinh tế - Chương 3: Mô hình tối ưu tuyến tính

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

Thêm vào BST

Báo xấu

603
lượt xem 57
download

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

Bài giảng Mô hình toán kinh tế Chương 3: Mô hình tối ưu tuyến tính trình bày về các khái niệm cơ bản về bài toán quan hệ tuyến tính, thuật toán đơn hình, bài toán đối ngẫu...mời các bạn tham khảo bài giảng để hiểu sâu hon về tối ưu tuyến tính.

Chủ đề:

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

Lưu

Nội dung Text: Bài giảng Mô hình toán kinh tế - Chương 3: Mô hình tối ưu tuyến tính

CHƯƠNG 3 MÔ HÌNH TỐI ƯU TUYẾN TÍNH §1. Khái niệm cơ bản về bài toán QHTT §2. Thuật toán đơn hình §3. Bài toán đối ngẫu 1
§1. KHÁI NIỆM CƠ BẢN VỀ BÀI TOÁN QUY HOẠCH TUYẾN TÍNH 1. Một số ví dụ Ví dụ 1 Một trại chăn nuôi định nuôi 3 loại bò: bò sữa, bò cày, bò thịt. Nguồn cung cấp giống bò sữa chỉ có thể cung cấp tối đa 18 con. Dự trù kinh phí chăn nuôi (tính trên mỗi con bò) được cho trong bảng sau : Loại bò Bò sữa Bò cày Bò thịt Tiền dự tính (đv : 10000 ĐVN) Chi phí Vốn 128 137 165 7020 Chi phí chăn nuôi 59 43 43 860 Tiền lãi 71 45 61 Tìm số bò mỗi loại cần nuôi để đạt lợi nhuận lớn nhất 2
Một nhà đầu tư có 4 tỉ đồng muốn đầu tư vào bốn lĩnh vực Lĩnh vực đầu tư Lãi suất / năm Ví dụ 2 Chứng khoán 20% Công trái 12% Gửi tiết kiệm 15% Bất động sản 18% Ngoài ra, để giảm thiểu rủi ro, nhà đầu tư cho rằng không nên đầu tư vào chứng khoán vượt quá 30% tổng số vốn đầu tư; đầu tư vào công trái và gửi tiết kiệm ít nhất 25% tổng vốn đầu tư; gửi tiết kiệm ít nhất 300 triệu đồng. Hãy xác định kế hoạch phân bổ vốn đầu tư sao cho tổng thu nhập hàng năm là lớn nhất. 3
• Các bước lập bài toán QHTT : 1) Xác định ẩn và hàm mục tiêu. 2) Xác định hệ ràng buộc về biến. 3) Xác định hệ ràng buộc về dấu. 4
Công ty A có kết hoạch quảng cáo sản phẩm trong 1 tháng với tổng chi phí là 120 triệu đồng. Các phương tiện quảng cáo: truyền hình, báo giấy, phát thanh. Các dữ liệu như sau : Phương tiện Chi phí cho 1 Số lần QC Dự đoán số lần QC tối đa người tiếp nhận QC trong 1 lần Truyền hình 1,2 triệu đồng 90 10 000 Báo 0,9 triệu đồng 28 15 000 Phát thanh 0,4 triệu đồng 120 5 000 Vì lí do chiến lược tiếp thị, yêu cầu ít nhất phải có 60 lần quảng cáo trên truyền hình trong 1 tháng. Hãy lập mô hình bài toán xác định kế hoạch quảng cáo. 5
2. Bài toán quy hoạch tuyến tính (QHTT) 2.1 Bài toán QHTT tổng quát Tìm x = (x1, x2, . . . , xn) sao cho: n f (x)   c j x j  Min(Max) (1) hàm mục tiêu j1  ràng buộc biến   n  a ij x j    bi ; i  1,..., m (2) (ràng buộc chính) j1         x j    0 ; j  1,..., n (3) ràng buộc dấu  tùy ý    6
2.2 Một số khái niệm • Một phương án của bài toán QHTT là một bộ n số (một véctơ) x  (x1 , x 2 ,..., x n ) thỏa mãn các hệ ràng buộc (2), (3). • Tập hợp các véctơ thỏa mãn (2),(3) gọi là tập phương án. • Phương án tối ưu (PATƯ) là một phương án thỏa (1). 7
2.2 Một số khái niệm Bài toán giải được là bài toán có PATƯ. Bài toán không giải được là bài toán không có PATƯ. Khi đó hoặc là bài toán không có phương án hoặc có phương án nhưng hàm mục tiêu không bị chặn ( f (x)    () đối với bài toán max (min)).  Nếu phương án x thỏa mãn ràng buộc nào đó với dấu “=” thì ta nói x thỏa mãn chặt ràng buộc đó. Ngược lại nếu thỏa dấu “>” hoặc “
2.2 Một số khái niệm - Ứng với ràng buộc thứ i ta có vectơ Ai* = (ai1, ai2, …,ai3). - Ký hiệu:  a1j    là vectơ các hệ số của biến x trong các ràng a 2 j  A j    buộc (không kể ràng buộc dấu). j    a nj    - Hệ vectơ Ai* tương ứng với các ràng buộc chính tạo thành ma trận ràng buộc chính, ký hiệu là A. - Các ràng buộc gọi là độc lập tuyến tính nếu hệ véctơ Ai* tương ứng độc lập tuyến tính. 9
2.2 Một số khái niệm • Phương án cực biên (phương án cơ bản) (PACB): phương án thỏa mãn chặt n ràng buộc độc lập tuyến tính. Lưu ý: PACB có thể thỏa mãn chặt hơn n ràng buộc, nhưng chỉ có n ràng buộc độc lập tuyến tính. • PACB không suy biến: phương án cực biên thỏa mãn đúng n ràng buộc. • PACB suy biến: phương án cực biên thỏa mãn hơn n ràng buộc. 10
Ví dụ 3 f (x1 , x 2 )  3x1  x 2  min x2  x1  5x 2  24 2x  x  4  1 2   x1  9  x1 ; x 2  0  x =9 • Tìm các PACB của bài toán QHTT sau. x1 2 9 24 –4 11
3. Các dạng đặc biệt của bài toán QHTT 3.1 Bài toán dạng chính tắc n f (x)   c j x j  Min(Max) Dạng ma trận j1 n f (x)  (c, x)  Min(Max) a x j1 ij j  bi ; i  1,..., m Ax  b , x  0 xj  0 ; j  1,..., n Mọi bài toán QHTT dạng tổng quát đều có thể đưa về dạng chính tắc tương đương – theo nghĩa : • Giá trị tối ưu của các hàm mục tiêu là trùng nhau. • Phương án, PATƯ của bài toán này sẽ suy ra phương án, PATƯ của bài toán kia. 12
Ví dụ 4 Đưa các bài toán QHTT sau về dạng chính tắc tương đương a) b) f(x) = 2x1 + x2 – x3  Min f(x) = x1 + x2 + 3x3  Max 2x1  x 2  x 3  5  x1  2x 2  x 3  5 4x  2x  x  8   1 2 3 3x1  x 2  3x 3  6  x ; x  0 3x1  x 2  3x 3  6  1 2  x1 ; x 3  0 ; x 2  0  13
3.2 Đặc điểm PACB của bài toán dạng chính tắc Định lí 1 Gọi Aj là cột thứ j của ma trận A. Phương án x của bài toán QHTT dạng chính tắc là cực biên thì hệ véc tơ {Aj} tương ứng với thành phần dương của phương án là độc lập tuyến tính. Ví dụ 5. Véctơ x=( 2,1,0) là PACB của bài toán QHTT f(x) = x1 + 4 x2 + 6 x3  max 3x1 + 4 x2 + 4 x3 = 10 – x1 + x2 + x3 = – 1 x j  0, j  1, 2, 3 14
Chú ý  Với bài toán QHTT dạng chính tắc : Ta có thể giả thiết r(A)=m và m < n .Từ đó suy ra : -PACB có không quá m thành phần dương; -PACB không suy biến là PA có m thành phần dương; -PACB suy biến là PA có ít hơn m thành phần dương. 15
3.2 Đặc điểm PACB của bài toán dạng chính tắc Định lí 2 (phát biểu cho bài toán QHTT dạng chính tắc) 1. Bài toán có phương án thì có PACB. 2. Nếu bài toán có phương án tối ưu thì có PACB tối ưu. Định lí 3 1. Bài toán có phương án và trị số hàm mục tiêu bị chặn dưới (trên) trên tập các phương án khi f(x)→min (max) thì có PATƯ. 2. Số PACB khác nhau trong mỗi bài toán là hữu hạn. 16
3. Các dạng đặc biệt của bài toán QHTT 3.3 Bài toán dạng chuẩn n f (x)  c x j1 j j  Min(Max) n a j1 ij x j  bi ; i  1,..., m xj  0 ; j  1,..., n bi  0 ; i  1,...m A  (a ij ) mn có ma trận con đ.vị cấp m 17
3.3 Bài toán dạng chuẩn Ví dụ 6 Cho bài toán QHTT: f(x) = x1 – 2x2 + x3 – 3x4 + x5  Min  x1  x 2  x5  1  3x  x  2x  4  2 3 5   2x  x 4  x5  1  2  x  0 j  1, 5  j Bài toán trên có phải là bài toán dạng chuẩn không? Tìm một phương án cực biên. 18
3.3 Bài toán dạng chuẩn • AÅn cô bản (ẩn cơ sở) là ẩn öùng vôùi caùc veùctô coät ñôn vò trong ma traän heä soá A; (caùc aån coøn laïi laø aån khoâng cô baûn) (noùi caùch khaùc noù laø aån coù heä soá laø 1 ôû moät phöông trình vaø coù heä soá laø 0 trong caùc phöông trình coøn laïi). • Phöông aùn cô baûn cuûa BTQHTT daïng chuaån là phöông aùn coù caùc aån khoâng cô baûn baèng 0 . 19
3.3 Bài toán dạng chuẩn Ví dụ 7 Cho bài toán QHTT: f(x) = x1 – 2x2 + x3  Min  x1  x 2  x5  3  3x  x  2x 5  4  2 3   2x  x 4  x5  1  2  x  0 j  1, 5  j a) Hãy tìm một PACB của bài toán, phương án đó có suy biến không ? b) Hãy tìm một PACB mới. 20