Bài giảng Quy hoạch tuyến tính - Chương 1: Bài toán quy hoạch tuyến tính

Chương 1 BÀI TOÁN QUY HOẠCH TUYẾN TÍNH 20/6/2012 1MaMH: 501014 Chương 1: Bài toán Quy hoạch tuyến tính NỘI DUNG 1. Bài toán QHTT tổng quát 2. Các dạng của bài toán QHTT 3. Các tính chất của bài toán QHTT 4. Phương pháp hình học 5. Phương pháp đơn hình 20/6/2012 2MaMH: 501014 Chương 1: Bài toán Quy hoạch tuyến tính Bài toán QHTT tổng quát Là bài toán có dạng: = = →  ≤ = ∑ ∑ 1 ( ) max(min) , 1,..., (1) n j j j n f x c x a x b i p 20/6/2012 3MaMH: 501014 Chương 1: Bài toán Quy hoạch tuyến tính = =   = = +   ≥ =  ∈ = + ∑ ℝ 1 1 , 1,..., (2) 0, 1,..., (3) , 1,..., (4) ij j i j n ij j i j j j a x b i p m x j q x j q n Bài toán QHTT tổng quát trong đó: là n biến cần tìm ; các số được cho sẵn. biểu thức (1),(2) gọi là các ràng buộc(RB) của bài toán; biểu thức (3), (4) gọi là RB (điều kiện) về dấu của biến. =, 1,...,jx j n = =, 1,..., ; , , 1,...,j ij ic j n a b i m 20/6/2012 4MaMH: 501014 Chương 1: Bài toán Quy hoạch tuyến tính Bài toán QHTT tổng quát • Gọi D:= {x : thỏa mãn các ràng buộc (1) – (4)} là tập ràng buộc (hay miền chấp nhận được (cnđ)) của bt. • Mỗi gọi là phương án (PA) cnđ.∈x D • PA cnđ thỏa mãn (đ/v bài toán min) được gọi là PA tối ưu (PATƯ). • Giá trị được gọi là giá trị (mục tiêu) tối ưu. 20/6/2012 5MaMH: 501014 Chương 1: Bài toán Quy hoạch tuyến tính *x ≤ ∀ ∈*( ) ( ),f x f x x D *( )f x Bài toán QHTT tổng quát Ví dụ 1 [1] Công ty RM sản xuất hai loại nước sơn: s.nội thất và s.ngoài trời. Nguyên liệu gồm A (có 6 tấn) và B (có 8 tấn). Biết rằng: • 1 tấn s.nội thất cần: 2 tấn A , 1 tấn B; • 1 tấn s.ngoài trời cần: 1 tấn A, 2 tấn B. Qua tiếp thị, được biết nhu cầu thị trường là như sau (cho 1 ngày): 20/6/2012 6MaMH: 501014 Chương 1: Bài toán Quy hoạch tuyến tính Bài toán QHTT tổng quát • Nhu cầu s.nội thất không hơn nhu cầu s. ngoài trời quá 1 tấn; • Nhu cầu cực đại của s.nội thất là 2 tấn. Vấn đề: Cty cần phải sx mỗi ngày như thế nào để doanh thu là lơn nhất? Biết rằng: 1 tấn s.nội thất giá 2000USD; 1 tấn s.ngoài trời giá 3000 USD. 20/6/2012 7MaMH: 501014 Chương 1: Bài toán Quy hoạch tuyến tính Bài toán QHTT tổng quát Gọi x, y là số tấn s.nội thất và s.ngoài trời được sx ra trong ngày. Mô hình bài toán: = + →( , ) 2 3 maxf x y x y 20/6/2012 8MaMH: 501014 Chương 1: Bài toán Quy hoạch tuyến tính + ≤  + ≤ − ≤  ≤  ≥ 2 6 2 8 1 2 , 0 x y x y x y x x y Các dạng của bài toán QHTT 1. Dạng tổng quát = = →  ≤ = ∑ ∑ 1 ( ) max(min) , 1,..., n j j j n f x c x a x b i p 20/6/2012 9MaMH: 501014 Chương 1: Bài toán Quy hoạch tuyến tính = =   = = +   ≥ =  ∈ = + ∑ ℝ 1 1 , 1,..., 0, 1,..., , 1,..., ij j i j n ij j i j j j a x b i p m x j q x j q n Các dạng của bài toán QHTT 2. Dạng chính tắc = = →  ∑ 1 ( ) max(min) n j j j n f x c x 20/6/2012 10MaMH: 501014 Chương 1: Bài toán Quy hoạch tuyến tính = = =   ≥ = ∑ 1 , 1,..., 0, 1,..., ij j i j j a x b i m x j n Các dạng của bài toán QHTT 3. Dạng chuẩn tắc = = →  ∑ 1 ( ) max( )min n j j j n f x c x 20/6/2012 11MaMH: 501014 Chương 1: Bài toán Quy hoạch tuyến tính = ≤ =   ≥ = ≥∑ 1 ( ) , 1,..., 0, 1,..., ij j i j j a x b i m x j n Các tính chất của bài toán QHTT Xét 2 tính chất cơ bản: • Tập hợp D các PA của bài toán QHTT (dạng bất kỳ) là một tập lồi. • Nếu một QHTT có ít nhất một PA và hàm mục tiêu bị chặn dưới trong miền ràng buộc (đ/v bài toán min) thì bài toán chắc chắn có PATƯ. 20/6/2012 12MaMH: 501014 Chương 1: Bài toán Quy hoạch tuyến tính Phương pháp hình học (pp đồ thị) Thường dùng để giải bài toán QHTT có 2 biến. Xét bài toán có dạng: Tìm x1, x2 sao cho: = + → 20/6/2012 13MaMH: 501014 Chương 1: Bài toán Quy hoạch tuyến tính + ≥ = ≥ ≥ 1 2 1 2 1 1 1 2 2 2 1 2 ( , ) min , 1, ( 0, 0) i i i f x x x x a x a x i c x c b m x Phương pháp hình học • Mỗi bpt tuyến tính xác định một nửa mặt phẳng. • Tập là + ≥1 1 2 2i i ia x a x b { }= = + ≥ =1 2 1 1 2 2( , ) : , 1,i i iD x x x a x a x b i m giao của m nửa mặt phẳng. 20/6/2012 14MaMH: 501014 Chương 1: Bài toán Quy hoạch tuyến tính x2 (3)(2) x1O (1) D 7/27/2012 15MaMH 501014 Chương 1 Bài toán Quy hoạch tuyến tính Phương pháp hình học 20/6/2012 16MaMH: 501014 Chương 1: Bài toán Quy hoạch tuyến tính D Phương pháp hình học Phương trình khi thay đổi sẽ xác định trên mặt phẳng các đường thẳng song song với nhau (gọi là đường mức), với giá trị mức α+ =21 1 2c cx x α α. Bài toán: Trong số các đường mức cắt D, hãy tìm đường mức với giá trị mức nhỏ nhất. 20/6/2012 17MaMH: 501014 Chương 1: Bài toán Quy hoạch tuyến tính α Phương pháp hình học Phương pháp: • Xác định D. • Vẽ véctơ , rồi vẽ đường mức qua gốc tọa độ và vuông với véctơ • Đ/v bt min, tịnh tiến đường mức ngược hướng = 1 2( ),cc c = 1 2,( ).cc c với véctơ đến mức thấp nhất mà vẫn còn cắt miền D (đường min). Khi đó, “đường min” tiếp xúc với D và đặt D về cùng một phía. Tiếp điểm tương ứng chính là PATƯ. 20/6/2012 18MaMH: 501014 Chương 1: Bài toán Quy hoạch tuyến tính = 1 2( ),cc c Phương pháp hình học • Đối với bài toán max, thì làm ngược lại. •Tịnh tiến mãi mà không tìm được điểm tiếp xúc→ bài toán không có PATƯ. 20/6/2012 19MaMH: 501014 Chương 1: Bài toán Quy hoạch tuyến tính Phương pháp hình học Ví dụ 2 Giải bài toán sau bằng pp hình học = + → + ≤  (1) ( , ) 2 3 max 2 6 f x y x y x y 20/6/2012 20MaMH: 501014 Chương 1: Bài toán Quy hoạch tuyến tính + ≤ − ≤  ≤  ≥ (2) (3) (4) 2 8 1 2 , 0. x y x y x x y Phương pháp hình học PATƯ của bài toán là tọa độ của điểm F = (1)∩(2). 20/6/2012 21MaMH: 501014 Chương 1: Bài toán Quy hoạch tuyến tính Phương pháp đơn hình Ý tưởng: tiến hành khảo sát các đỉnh của miền ràng buộc để tìm ra đỉnh tối ưu. 20/6/2012 22MaMH: 501014 Chương 1: Bài toán Quy hoạch tuyến tính Phương pháp đơn hình Xét bài toán có dạng chính tắc sau: + + = + + + →  + + + =  + + + = 1 2 1( 1) 1 1 1 1 1 2( ) ... min ... ... n m m n n nf x x x x a x a x b a x a x b c c x x c với 20/6/2012 23MaMH: 501014 Chương 1: Bài toán Quy hoạch tuyến tính + + + +    + + + =   ≥ = ⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯ 2( 1) 1 2 2 ( 1) 1 2 ... 0, 1, m m n n m m m n m j m mna x a xx j n b x > =0, .1,ib i m Phương pháp đơn hình Định nghĩa 1: Biến cơ sở là biến đi với véctơ cột đơn vị. • Trong bt trên, các biến cơ sở là , các biến còn lại là biến không cơ sở (có giá trị = 0). 1 2, ,..., mx x x • Khi đó, là một PACB xuất phát của bài toán. 20/6/2012 24MaMH: 501014 Chương 1: Bài toán Quy hoạch tuyến tính = 0 1 2( , ,..., ,0,...,0)mx b b b Phương pháp đơn hình Ví dụ 3 Bài toán = + − + →  + − =  1 2 3 4 1 2 3 (1) ( ) 3 5 2 min 4 1 f x x x x x x x x có PACB xuất phát là (biến x1, x4 là biến cơ sở). 20/6/2012 25MaMH: 501014 Chương 1: Bài toán Quy hoạch tuyến tính + + =  ≥ = 2 3 4 (2)3 5 0, 1,4j x x x x j = 0 (1,0,0,5),x Phương pháp đơn hình • Mỗi véctơ cột được biểu diễn qua véctơ cơ sở: =, 1,2,...,jA j n = + + + =⋯1 1 2 2 , 1,j j j mj mA a A a A a A j n • Giá trị mục tiêu tại x0 : 20/6/2012 26MaMH: 501014 Chương 1: Bài toán Quy hoạch tuyến tính = = + + +⋯0 0 0 1 1 2 2( ) , m mf x c x c b c b c b Phương pháp đơn hình • Số được gọi là ước lượng tương ứng của biến , với ∆ =, 1,j j n jx = ∆ = − =∑ 1 , 1, . m j i ij j i c a c j n 20/6/2012 27MaMH: 501014 Chương 1: Bài toán Quy hoạch tuyến tính Phương pháp đơn hình Định lý 1 (Dấu hiệu tối ưu) Nếu x0 là PACB sao cho thì x0 là PATƯ. ∆ ≤ ∀ =0, 1,j j n 20/6/2012 28MaMH: 501014 Chương 1: Bài toán Quy hoạch tuyến tính Phương pháp đơn hình Định lý 2 (Dấu hiệu bài toán không có lời giải) Nếu ngoài cơ sở liên kết của PACB x0 sao cho và (I0 là tập chỉ số biến cơ sở), thì bài toán không có PATƯ. ∃ jA ∆ > 0j ≤ ∀ ∈ 00,ija i I 20/6/2012 29MaMH: 501014 Chương 1: Bài toán Quy hoạch tuyến tính Phương pháp đơn hình Định lý 3 (Tìm PAmới tốt hơn) Nếu ngoài cơ sở liên kết của PACB x0 sao cho và với mà đều có ít nhất một chỉ số sao cho thì ta có thể tìm được một ∃ jA ∆ > 0j > 0,ija j ∆ > 0j ∈ 0i I PACB mới x1 tốt hơn x0 . 20/6/2012 30MaMH: 501014 Chương 1: Bài toán Quy hoạch tuyến tính Phương pháp đơn hình Thuật toán đơn hình − Bước 1: Lập bảng đơn hình (tương ứng với x0) − Bước 2: Kiểm tra các ước lượng Sau khi tính tiến hành kiểm tra∆ ,j ∆ ≤ =• Nếu dấu hiệu tối ưu xuất hiện thì PA đang xét là PATƯ. • Nếu xuất hiện dấu hiệu hàm mục tiêu không bị chặn thì kết luận bài toán không có PATƯ. 20/6/2012 31MaMH: 501014 Chương 1: Bài toán Quy hoạch tuyến tính ( 0, 1, )j j n ∃∆ > ≤ ∈ 0( 0, 0, )j ija i I Phương pháp đơn hình • Nếu không xảy ra 2 trường hợp trên, thì ta có thể tìm được PA mới tốt hơn như sau: 1. Xác định biến vào ∆ ∆ > = ∆max{ : 0}j j k kx 2. Xác định biến ra với là các phần tử ở cột PA. Khi đó, phần tử được gọi là phần tử trục. 20/6/2012 32MaMH: 501014 Chương 1: Bài toán Quy hoạch tuyến tính > =0 0min{ : 0}i i s ik ks k a a a a a sx ska0ia Phương pháp đơn hình Tiếp theo, lập bảng đơn hình mới, − Tính các giá trị của hàng mới vào: ′ = ≡, sj kj sk a a i s a − Tính các giá trị còn lại trong bảng đơn hình: 20/6/2012 33MaMH: 501014 Chương 1: Bài toán Quy hoạch tuyến tính ′ = − ≠,sjij ij ik sk a a a a i s a ′∆ = ∆ − ∆sjj j k sk a a Phương pháp đơn hình Ví dụ 4 Giải bài toán sau bằng pp đơn hình = + − + →  + − =  1 2 3 4 1 2 3 (1) ( ) 3 5 2 min 4 1 f x x x x x x x x 20/6/2012 34MaMH: 501014 Chương 1: Bài toán Quy hoạch tuyến tính + + =  ≥ = 2 3 4 (2)3 5 0, 1,4j x x x x j Phương pháp đơn hình Lập bảng đơn hình (PACB Hệ số Biến cơ sở Phương án 3 5 -1 2 x1 x2 x3 x4 = 0 (1,0,0,5))x 20/6/2012 35MaMH: 501014 Chương 1: Bài toán Quy hoạch tuyến tính 3 x1 1 1 4 -1 0 2 x4 5 0 1 3 1 f(x0) = 13 0 9 4 0  ∆1  ∆2  ∆3  ∆4 Phương pháp đơn hình Tìm PA mới: Hệ số Biến cơ sở Phương án 3 5 -1 2 x1 x2 x3 x4 20/6/2012 36MaMH: 501014 Chương 1: Bài toán Quy hoạch tuyến tính 5 x2 1/4 1/4 1 -1/4 0 2 x4 19/4 -1/4 0 13/4 1 f(x1) = 43/4 -9/4 0 25/4 0 Phương pháp đơn hình Tìm PA mới: Hệ số Biến cơ sở Phương án 3 5 -1 2 x1 x2 x3 x4 5 x 8/13 3/13 1 0 1/13 20/6/2012 37MaMH: 501014 Chương 1: Bài toán Quy hoạch tuyến tính 2 -1 x3 19/13 -1/13 0 1 4/13 f(x2) = 21/13 -23/13 0 0 -25/13 Phương pháp đơn hình Vì nên: • PATƯ của bài toán: =* (0,8 / 13,19 / 13,0);x ∆ ≤ =0, 1,4j j • Giá trị tối ưu: 20/6/2012 38MaMH: 501014 Chương 1: Bài toán Quy hoạch tuyến tính = *( ) 21/ 13.f x Phương pháp đơn hình Lưu ý 1. Nếu bài toán , thì hoặc: - Chuyển về bài toán - Hoặc giải trực tiếp bài toán ( ) maxf x → ( ) ( ) min;g x f x= − → ( ) max.f x → 2. Ở bảng đơn hình tối ưu, nếu có với là biến không cơ sở thì bài toán có PATƯ khác. 20/6/2012 39MaMH: 501014 Chương 1: Bài toán Quy hoạch tuyến tính 0,j∆ = jx Phương pháp đơn hình Bài toán mở rộng Xét bài toán ở dạng chính tắc: 1 1 2 2 11 1 12 2 1 1 ( ) ... min ... n n n n f x c x c x c x a x a x a x b = + + + →  + + + =  20/6/2012 40MaMH: 501014 Chương 1: Bài toán Quy hoạch tuyến tính 21 1 22 2 2 2 1 1 2 2 ... ... 0, 1, n n m m mn n m j a x a x a x b a x a x a x b x j n + + + =    + + + =   ≥ = ⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯ Phương pháp đơn hình Giả sử bài toán chưa có biến cơ sở. Ta thêm vào mỗi phương trình một biến giả với hệ số là 1. Trên hàm mục tiêu, các biến giả có hệ số là 0, 1,n ix i m+ ≥ = với M là số dương rất lớn. 20/6/2012 41MaMH: 501014 Chương 1: Bài toán Quy hoạch tuyến tính ( ( ) min),M f x+ → ( ( ) max),M f x− → Phương pháp đơn hình Bài toán mở rộng: 1 1 2 2 11 1 12 2 1 1 1 1 ( ) ... min ... 1 ( ) m n i i n n n n n M x x f x c x c x c x a x a x a x b + = + = + + + →  + + + =  + + ∑ 20/6/2012 42MaMH: 501014 Chương 1: Bài toán Quy hoạch tuyến tính 21 1 22 2 2 2 1 1 2 2 2... ... 0, 1 1 1 , n n m n n m m mn n m j xa x a x a x b a x a x a x b x mj x n + + + + + =    + + + =   ≥ += + + ⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯ Phương pháp đơn hình Xét dấu • nếu hoặc và • nếu hoặc và j j jMδ γ∆ = + 0j∆ > 0jδ > ( 0jδ = 0)jγ > 0j∆ < 0jδ < ( 0jδ = 0)jγ < • nếu hoặc và Các bước tính toán như pp đơn hình thông thường. 20/6/2012 43MaMH: 501014 Chương 1: Bài toán Quy hoạch tuyến tính j k∆ > ∆ j kδ δ> ( j kδ δ= )j kγ γ> Phương pháp đơn hình Quan hệ giữa bt mở rộng và bt gốc: 1. Nếu bt mở rộng không có PATƯ, thì bt gốc cũng không có PATƯ. 2. Nếu bt mở rộng có PATƯ là * * * *( , ,..., ,0,...,0)x x x x= thì bt gốc có PATƯ là 3. Nếu bt mở rộng có PATƯ là thì bt gốc không có PA. 20/6/2012 44MaMH: 501014 Chương 1: Bài toán Quy hoạch tuyến tính 1 2 n * * * * 1 2( , ,..., )nx x x x=  * * * * 1 2( , ,..., ,0,0, 0,..,0) n i n x x x x x a + = >