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 2 1. Một số ví dụ §1. KHÁI NIỆM CƠ BẢN VỀ BÀI TOÁN QUY HOẠCH TUYẾN TÍNH 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 : Tìm số bò mỗi loại cần nuôi để đạt lợi nhuận lớn nhất Loại bò Chi phí Bò sữa Bò cày Bò thịt Tiền dự tính (đv : 10000 ĐVN) Vốn 128 137 165 7020 Chi phí chăn nuôi 59 43 43 860 Tiền lãi 71 45 61 3 Ví dụ 2 Một nhà đầu tư có 4 tỉ đồng muốn đầu tư vào bốn lĩnh vực Lĩnh vực đầu tư Lãi suất / năm Chứng khoán Công trái Gửi tiết kiệm Bất động sản 20% 12% 15% 18% Ngoài ra, để giảm thiểu rủi ro, nhà đầu tư cho rằng không nên đầu tư vào chứng khoán vượt quá 30% tổng sô ́ vốn đầu tư; đầu tư vào công trái và gửi tiết kiệm ít nhất 25% tổng vốn đầu tư; gửi tiết kiệm ít nhất 300 triệu đồng. Hãy xác định kế hoạch phân bô ̉ vốn đầu tư sao cho tổng thu nhập hàng năm là lớn nhất. 4 • Các bước lập bài toán QHTT : 1) Xác định ẩn và hàm mục tiêu. 2) Xác định hệ ràng buộc về biến. 3) Xác định hệ ràng buộc về dấu. 5 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 : 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. Phương tiện Chi phí cho 1 lần QC Số lần QC tối đa Dự đoán số người tiếp nhận QC trong 1 lần Truyền hình Báo Phát thanh 1,2 triệu đồng 0,9 triệu đồng 0,4 triệu đồng 90 28 120 10 000 15 000 5 000 6 2.1 Bài toán QHTT tổng quát 2. Bài toán quy hoạch tuyến tính (QHTT) Tìm x = (x1, x2, . . . , xn) sao cho: n j j j 1 n ij j i j 1 j f (x) c x Min(Max) (1) a x b ; i 1,..., m (2) x 0 ; j 1,..., n (3) tùy ý                            hàm mục tiêu ràng buộc biến (ràng buộc chính) ràng buộc dấu 7 2.2 Một số khái niệm • Một phương án của bài toán QHTT là một bộ n số (một véctơ) 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). 1 2 nx (x ,x ,..., x ) Bài toán giải được là bài toán có PATƯ. Bài toán không giải được là bài toán không có PATƯ. Khi đó hoặc là bài toán không có phương án hoặc có phương án nhưng hàm mục tiêu không bị chặn ( đối với bài toán max (min)).  Nếu phương án x thỏa mãn ràng buộc nào đó với dấu “=” thi ̀ ta nói x thỏa mãn chặt ràng buộc đó. Ngược lại nếu thỏa dấu “>” hoặc “<” thi ̀ ta nói thỏa mãn lỏng ràng buộc đó. f (x) ( )   2.2 Một số khái niệm 8 - Ứng với ràng buộc thứ i ta có vectơ Ai* = (ai1, ai2, …,ai3). - Ký hiệu: là vectơ các hê ̣ sô ́ của biến xj trong các ràng buộc (không kê ̉ ràng buộc dấu). - Hê ̣ vectơ Ai* tương ứng với các ràng buộc chính tạo thành ma trận ràng buộc chính, ký hiệu là A. - Các ràng buộc gọi là độc lập tuyến tính nếu hê ̣ véctơ Ai* tương ứng độc lập tuyến tính. 1j 2 j j nj a a A a              2.2 Một số khái niệm 9 10 • Phương án cực biên (phương án cơ bả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. 2.2 Một số khái niệm 11 Ví dụ 3 • Tìm các PACB của bài toán QHTT sau. 1 2 1 2 1 2 1 2 1 1 2 f (x ,x ) 3x x min x 5x 24 2x x 4 x 9 x ;x 0             x1 x2 –4 2 24 x =9 9 12 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 j j j 1 n ij j i j 1 j f (x) c x Min(Max) a x b ; i 1,...,m x 0 ; j 1,..., n           Dạng ma trận f (x) (c, x) Min(Max) Ax b , x 0     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 nghĩa : • Giá trị tối ưu của các hàm mục tiêu là trùng nhau. • Phương án, PATƯ của bài toán này sẽ suy ra phương án, PATƯ của bài toán kia. 13 Đưa các bài toán QHTT sau về dạng chính tắc tương đương Ví dụ 4 f(x) = 2x1 + x2 – x3  Min 1 2 3 1 2 3 1 2 3 1 3 2 2x x x 5 4x 2x x 8 3x x 3x 6 x ; x 0 ; x 0               f(x) = x1 + x2 + 3x3  Max 1 2 3 1 2 3 1 2 x 2x x 5 3x x 3x 6 x ; x 0          a) b) Định lí 1 Gọi Aj là cột thứ j của ma trận A. Phương án x củ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 của phương án là độc lập tuyến tính. Ví dụ 5. Véctơ x=( 2,1,0) là PACB của bài toán QHTT f(x) = x1 + 4 x2 + 6 x3  max 3x1 + 4 x2 + 4 x3 = 10 – x1 + x2 + x3 = – 1 jx 0, j 1,2,3  3.2 Đặc điểm PACB của bài toán dạng chính tắc 14  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ừ đó 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. Chú ý 15 16 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. 17 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 j j j 1 n ij j i j 1 j i ij m n f (x) c x Min(Max) a x b ; i 1,...,m x 0 ; j 1,..., n b 0 ; i 1,...m A (a )               có ma trận con đ.vị cấp m Ví dụ 6 Cho bài toán QHTT: f(x) = x1 – 2x2 + x3 – 3x4 + x5  Min 1 2 5 2 3 5 2 4 5 j x x x 1 3x x 2x 4 2x x x 1 x 0 j 1, 5                 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. 3.3 Bài toán dạng chuẩn 18 19 • 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 . 3.3 Bài toán dạng chuẩn a) Hãy tìm một PACB của bài toán, phương án đó có suy biến không ? b) Hãy tìm một PACB mới. 1 2 5 2 3 5 2 4 5 j x x x 3 3x x 2x 4 2x x x 1 x 0 j 1, 5                 20 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 21 Ví dụ 8 Đưa các bài toán QHTT sau về dạng chuẩn tương đương 1 2 3 1 2 3 4 2 3 4 2 3 4 j f(x) = 2x x 3x min x x x x 2 x + x 3x 1 2x +3x 4x 3 x 0, j 1,..., 4                 1 2 3 1 2 3 4 2 3 4 2 3 4 j f(x) = x x x max x x x x 2 x + x 3x 1 2x +3x 5x 3 x 0, j 1,..., 4                 a) b)