Bài toán quy hoạch tuyến tính

Bài toán về quy hoạch tuyến tính giúp bạn ôn tập, hệ thống và nắm vững kiến thức, áp dụng chúng vào giải bài tập, chuẩn bị cho kì thi sắp tới đạt kết quả cao. Tài liệu đi kèm đáp án giúp bạn so sánh kết quả và tham khảo giải bài tập theo những cách khác nhau. Mời các bạn cùng tham khảo. Chúc các bạn thành công!

Nội dung trích xuất từ tài liệu:
Bài toán quy hoạch tuyến tính 2.Bài toán quy ho ch tuy n tính (QHTT) Tình hu ng: M t công ty c n lên m t k ho ch qu ng cáo cho s n ph m c mình trên sóng phát thanh và sóng truy n hình. Chi phí cho 1 phút qu ng cáo trên sóng phát thành là 80.000 ñ, trên sóng truy n hình là 400.000 ñ. ðài phát thanh ch nh n qu ng cáo các chương trình dài ít nh t 5 phút. Còn ñài truy n hình ch nh n phát các chương trình t i ña 4 phút. Theo các phân tích xã h i hoc, cùng m t th i lư ng 1 phút qu ng cáo trên truy n hình s có hi u qu g p 6 l n trên sóng phát thanh. Công ty d ñ nh ch chi t i ña là 1.600.000 ñ cho qu ng cáo. H i c n ñ t th i lư ng qu ng có trên sóng phát thanh và sóng truy n hình như th nào cho ñ t hi u qu nh t? Mô hình hóa: G i th i lư ng công ty ñ t qu ng cáo trên sóng phát thanh là a phút. Trên sóng truy n hình là b phút . chi phí cho vi c này là 80.000*a + 400.000*b ≤ 1.600.000 ñ. Trong ñó; a ≥ 5; b ≤ 4; a ≥ 0; b ≥ 0. Hi u qu chung c a qu ng cáo là a + 6.b Bài toán: Xác ñinh a; b sao cho a + 6b Max V i ñi u ki n : 80.000*a + 400.000*b ≤ 1.600.000 ñ. a ≥ 5; b ≤ 4 và: a ≥ 0; b ≥ 0. Bài toán có c u trúc như trên là m t ví d v bài toán QHTT. Chú ý : do Maxf(x) = -Minf(x) nên t nay v sau ta ch nói t i bài toán tìm Minf(x) 2.1Các ñ nh nghĩa: Bài toán: Xác ñ nh véc tơ x = ( x1; x2 ;...; xn ) sao cho Trong ñó I1; I 2 ; I 3 là t p các ch s không giao nhau kí hi u i = I1 ∪ I 2 ∪ I 3 ; a ii ; b ii ; c j là các h s ; xj j:=1,2,…,n là các bi n. +Hàm f(x) g i là hàm m c tiêu +H (1.1) ñ n (1.4) g i là h ràng bu c ( h ñi u ki n) c a bài toán . V i m i ch s i ta có m t phương trình ho c b t phương trình tương ng và ñư c g i là ràng bu c th i.Các h s v trái trong m i ràng bu c th i là m t véc tơ dòng A * =(ai1; ai2;….;ain) . M t nhóm ràng bu c có h véc tơ Ai* ñ c l p tuy n tính ñư c g i là các i ràng bu c ñ c l p tuy n tính. xj ≥ 0; xj ≤ 0 g i là các ràng bu c v d u ñ i v i xj + Trong h t (1.1) ñ n (1.4) xét các ràng bu c không ph i là ràng bu c v d u các h s v trái tương ng v i m i ràng bu c này là m t ma tr n, ký hi u là A. Ma tr n A có n c t, m i c t này là m t véc tơ, ký hi u là Aj – chính là véc tơ các h s c a bi n xj Aj g i là véc tơ ñi u ki n ng v i bi n xj + Phương án: m t véc tơ x th a mãn h ràng bu c c a bài toán g i là m t phương án c a bài toán. Trong ràng bu c th i n u d u “=” x y ra thì ta nói phương án x th a mãn ch t ñ i v i ràng bu c th i; còn n u x y ra d u ≤ ho c (≥ ) thì phương án x là l ng ñ i v i ràng bu c th i + Phương án t i ưu: là phương án mà hàm m c tiêu ñ t ñư c Min + Phương án t t hơn N u f(x1) ≤ f(x2) thì phương án x1 g i là t t hơn phương án x2 M t bài toán t n t i phương án t i ưu g i là bài toán gi i ñư c, n u không có phương án t i ưu g i là bài toán không gi i ñư c. +Phương án c c biên: M t phương án th a mãn ch t n ràng bu c ñ c l p tuy n tính ñư c g i là phương án c c biên (PACB) * phương án c c biên th a mãn ch t ñúng n ràng bu c g i là phương án c c biên không suy bi n, th a mãn ch t hơn n ràng bu c g i là phương án c c biên suy bi n. Thí d 1: Cho .f(x) = x1 + x2 – 2x3 + x4 + x5 Min .x1 + x2 + x3 - x5 ≤ 40 (1) .-2x1 – 2x2 + 5x3 + 2x5 = 65 (2) .x2 + x3 +x4 + 2x5 ≥ 12 (3) .xj ≥ 0 v i j:=1,2,..,5 A1* = (1;1;1;0;−1) 1 1  1  0  − 1      * Ta có: A = (−2;−2;5;0;2) A1 =  − 2  ; A2 =  − 2 ; A3 =  5 ; A4 =  0 ; A5 =  2  2 0 1  1 1 2 * A3 = (0;1;1;1;2)      1 1 1 0 − 1 − 2 − 2 5 0 2  Ma tr n A =   0 1 1 1 2   V i x1 = ( 0; 0; 13; 0; 0) ; x2 = ( 0; 0; 1; 0; 30) ñây là hai phương án c a bài toán. Phương án x1 th a mãn ch t ñ i v i ràng bu c (2) và là l ng ñ i v i (1) và (3) và x3 ≥ 0 Phương án x2 th a mãn ch t ñ i v i (2) và l ng ñ i v i (1); (3) và x3 ≥ 0; x5 ≥ 0 Do f(x1) < f(x2) nên phương án x1 t t hơn th c s phương án x2 Thí d 2: f(x) = - x1 - 6x2 Min 80.000.x1 + 400.000x2 ≤ 1.600.000 .x1 ≥ 5; x2 ≤ 4 .x1 ≥ 0; x2 ≥ 0 Các phương án x1 = ( 5;3); x2 = ( 0;4); x3 = (20;0) là các phương án c c biên c a bài toán N u t t c các phương án c c biên c a bài toán ñ u không suy bi n thì bài toán g i là • không suy bi n; trái l i, g i là bài toán suy bi n. 2.2.Các d ng ñ c bi t c a ...