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
Bạn đang xem 20 trang mẫu của tài liệu "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", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên
Tài liệu đính kèm:
- bai_giang_quy_hoach_tuyen_tinh_chuong_1_bai_toan_quy_hoach_t.pdf
Nội dung text: 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 MaMH : 501014 Ch ươ ng 1 : Bài toán Quy ho ạch tuy ến tính 1
- 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 MaMH : 501014 Ch ươ ng 1 : Bài toán Quy ho ạch tuy ến tính 2
- Bài toán QHTT tổng quát Là bài toán có dạng: n = → fx( )∑ cxj j max(min) j =1 n ≤ = ∑axij j bi i , 1, , p (1) j =1 n = = + ∑aij x j b i , i p 1, , m (2) j =1 x≥0, j = 1, , q (3) j ∈ = + xj ℝ, jq 1, , n (4) 20/6/2012 MaMH : 501014 Ch ươ ng 1 : Bài toán Quy ho ạch tuy ến tính 3
- Bài toán QHTT tổng quát = trong đó:xj , j 1, , n là n bi ến cần tìm ; = = các sốcj, j 1, , n ; a ij , b i , i 1, , m đượ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. 20/6/2012 MaMH : 501014 Ch ươ ng 1 : Bài toán Quy ho ạch tuy ến tính 4
- 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 x∈ D gọi là ph ương án (PA) cn đ. • PA cn đ x * th ỏa mãn f( x* )≤ f ( x ), ∀ x ∈ D (đ/v bài toán min) được gọi là PA tối ưu (PATƯ). • Giá tr ịf( x * ) được gọi là giá tr ị (mục tiêu) tối ưu. 20/6/2012 MaMH : 501014 Ch ươ ng 1 : Bài toán Quy ho ạch tuy ến tính 5
- 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 MaMH : 501014 Ch ươ ng 1 : Bài toán Quy ho ạch tuy ến tính 6
- 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á 2000 USD; 1 tấn s.ngoài tr ời giá 3000 USD. 20/6/2012 MaMH : 501014 Ch ươ ng 1 : Bài toán Quy ho ạch tuy ến tính 7
- 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: fxy(,)= 2 x + 3 y → max 2x+ y ≤ 6 x+2 y ≤ 8 x− y ≤ 1 ≤ x 2 x, y ≥ 0 20/6/2012 MaMH : 501014 Ch ươ ng 1 : Bài toán Quy ho ạch tuy ến tính 8
- Các dạng của bài toán QHTT 1. Dạng tổng quát n = → fx( )∑ cxj j max(min) j =1 n ≤ = ∑axij j bi i , 1, , p j =1 n = = + ∑aij x j b i , i p 1, , m j =1 x≥0, j = 1, , q j ∈ = + xj ℝ, jq 1, , n 20/6/2012 MaMH : 501014 Ch ươ ng 1 : Bài toán Quy ho ạch tuy ến tính 9
- Các dạng của bài toán QHTT 2. Dạng chính tắc n = → fx( )∑ cxj j max(min) j =1 n = = ∑aij x j b i , i 1, , m j =1 ≥ = xj 0, j 1, , n 20/6/2012 MaMH : 501014 Ch ươ ng 1 : Bài toán Quy ho ạch tuy ến tính 10
- Các dạng của bài toán QHTT 3. Dạng chu ẩn tắc n = → fx()∑ cxj j max(min ) j =1 n ≤≥ = ∑aij x j( ) b i , i 1, , m j =1 ≥ = xj 0, j 1, , n 20/6/2012 MaMH : 501014 Ch ươ ng 1 : Bài toán Quy ho ạch tuy ến tính 11
- 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 MaMH : 501014 Ch ươ ng 1 : Bài toán Quy ho ạch tuy ến tính 12
- 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: = + → fxx(12 , )c1 x 1c2 x 2 min + ≥ = axi1 1 ax i2 2 b i , i 1, m ≥ ≥ (x1 0,x2 0) 20/6/2012 MaMH : 501014 Ch ươ ng 1 : Bài toán Quy ho ạch tuy ến tính 13
- Phương pháp hình học + ≥ • Mỗi bpt tuy ếntínhai11 x a i 22 x b i xác đị nh một nửa mặt ph ẳng. == +≥= • Tập D{ x(,): xxaxax12i 11 i 22 bi i ,1, m} là giao của m nửa mặt ph ẳng. 20/6/2012 MaMH : 501014 Ch ươ ng 1 : Bài toán Quy ho ạch tuy ến tính 14
- x2 (2) (3) (1) D O x1 7/27/2012 MaMH 501014 Ch ươ ng 1 Bài toán Quy ho ạch tuy ến tính 15
- Phương pháp hình học D 20/6/2012 MaMH : 501014 Ch ươ ng 1 : Bài toán Quy ho ạch tuy ến tính 16
- Phương pháp hình học + = α α Ph ươngtrìnhc1x1 c 2 x 2 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 α. 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 MaMH : 501014 Ch ươ ng 1 : Bài toán Quy ho ạch tuy ến tính 17
- Phương pháp hình học Phương pháp: • Xác đị nh D. = • Vẽ véct ơ c (c1,c 2 ) , rồi vẽ đường mức qua gốc = tọa độ và vuông với véct ơ c (c1,c 2 ). • Đ/v bt min, tịnh ti ến đường mức ngược hướng = với véct ơc (c1,c 2 ) đế 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 MaMH : 501014 Ch ươ ng 1 : Bài toán Quy ho ạch tuy ến tính 18
- 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 MaMH : 501014 Ch ươ ng 1 : Bài toán Quy ho ạch tuy ến tính 19
- 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 fxy( , )= 2 x + 3 y → max 2x+ y ≤ 6 (1) x+2 y ≤ 8 (2) x− y ≤ 1 (3) ≤ x 2 (4) x, y ≥ 0. 20/6/2012 MaMH : 501014 Ch ươ ng 1 : Bài toán Quy ho ạch tuy ến tính 20
- 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 MaMH : 501014 Ch ươ ng 1 : Bài toán Quy ho ạch tuy ến tính 21
- 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 MaMH : 501014 Ch ươ ng 1 : Bài toán Quy ho ạch tuy ến tính 22
- Phương pháp đơn hình Xét bài toán có dạng chính tắc sau: = + + + → fxx()c1 1 c 2 x 2 cn x n min x +a x ++ axb = 1 1(mm+ 1) + 1 1 nn 1 + ++ = x2 a2(1)mm+ x + 1 axb 2 nn 2 ⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯ x +a x ++ ax = b m m( m+ 1) m + 1 mn n m ≥ = x j 0,j 1, n > = với bi 0, i1, m. 20/6/2012 MaMH : 501014 Ch ươ ng 1 : Bài toán Quy ho ạch tuy ến tính 23
- 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àx1, x 2 , , x m ,các bi ến còn lại là bi ến không cơ sở (có giá tr ị = 0). 0 = • Khi đó,x( bb1 , 2 , , b m ,0, ,0) là một PACB xu ất phát của bài toán. 20/6/2012 MaMH : 501014 Ch ươ ng 1 : Bài toán Quy ho ạch tuy ến tính 24
- Phương pháp đơn hình Ví dụ 3 Bài toán = + − + → fx( ) 3 x1 5 xx 23 2 x 4 min x+4 x − x = 1 (1) 1 2 3 + + = x23 x 3 x 4 5 (2) ≥ = xj 0, j 1,4 có PACB xu ất phát là x0 = (1,0,0,5), (bi ến x1, x4 là bi ến cơ sở). 20/6/2012 MaMH : 501014 Ch ươ ng 1 : Bài toán Quy ho ạch tuy ến tính 25
- Phương pháp đơn hình = • Mỗi véct ơ cột Aj , j 1,2, , n được bi ểu di ễn qua véct ơ cơ sở: = + ++ = AaAaAj11 j 2 j 2 ⋯ aAj mj m , 1, n • Giá tr ị mục tiêu tại x0 : 0= 0 0 =+ ++ fx( ) cx , cbcb11 22 ⋯ cbm m 20/6/2012 MaMH : 501014 Ch ươ ng 1 : Bài toán Quy ho ạch tuy ến tính 26
- Phương pháp đơn hình ∆ = • Sốj ,j 1, n được gọi là ước lượng tương ứng của bi ếnx j , với m ∆= − = j∑c i a ij c j , j 1, n . i =1 20/6/2012 MaMH : 501014 Ch ươ ng 1 : Bài toán Quy ho ạch tuy ến tính 27
- Phương pháp đơn hình Đị nh lý 1 (Dấu hi ệu tối ưu) 0 ∆ ≤ ∀ = 0 Nếu x làPACB saochoj 0,j 1, n thìx là PATƯ. 20/6/2012 MaMH : 501014 Ch ươ ng 1 : Bài toán Quy ho ạch tuy ến tính 28
- 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) ∃ 0 NếuAj ngoài cơ sở liên kết của PACB x sao cho ∆ > ≤ ∀ ∈ j 0 và aij 0, i I 0 (I0 là tập ch ỉ số bi ến cơ sở), thì bài toán không có PATƯ. 20/6/2012 MaMH : 501014 Ch ươ ng 1 : Bài toán Quy ho ạch tuy ến tính 29
- Phương pháp đơn hình Đị nh lý 3 (Tìm PA mới tốt hơn) ∃ 0 NếuAj ngoài cơ sở liên kết của PACB x sao cho ∆ > ∆ > j 0 và vớij mà j 0 đề u có ít nh ất một ch ỉ ∈ > số i I 0 sao cho aij 0, thì ta có th ể tìm được một PACB mới x1 tốt hơn x0 . 20/6/2012 MaMH : 501014 Ch ươ ng 1 : Bài toán Quy ho ạch tuy ến tính 30
- 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 ∆ Saukhitínhj , ti ến hành ki ểm tra ∆ ≤ = • Nếu dấu hi ệu tối ưu xu ất hi ện(j 0,j 1, 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(j 0,a ij 0, i I 0 ) thì kết lu ận bài toán không có PATƯ. 20/6/2012 MaMH : 501014 Ch ươ ng 1 : Bài toán Quy ho ạch tuy ến tính 31
- 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 x k ∆ ∆ > = ∆ max{j : j 0} k 2. Xác đị nh bi ến ra x s a a i 0> = s 0 min{ :aik 0} aik a s k vớiai 0 làcácph ần tử ở cột PA. Khi đó, ph ần tử ask được gọi là ph ần tử tr ục. 20/6/2012 MaMH : 501014 Ch ươ ng 1 : Bài toán Quy ho ạch tuy ến tính 32
- 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: a ′ =sj ≡ akj , i s ask − Tính các giá tr ị còn lại trong bảng đơn hình: a ′ = −sj ≠ aaij ij ais ik , ask a ∆′ = ∆ −sj ∆ j j k ask 20/6/2012 MaMH : 501014 Ch ươ ng 1 : Bài toán Quy ho ạch tuy ến tính 33
- Phương pháp đơn hình Ví dụ 4 Gi ải bài toán sau bằng pp đơn hình = + − + → fx( ) 3 x1 5 xx 23 2 x 4 min x+4 x − x = 1 (1) 1 2 3 + + = x23 x 3 x 4 5 (2) ≥ = xj 0, j 1,4 20/6/2012 MaMH : 501014 Ch ươ ng 1 : Bài toán Quy ho ạch tuy ến tính 34
- Phương pháp đơn hình Lập bảng đơn hình (PACB x0 = (1,0,0,5)) Hệ Bi ến Ph ương 3 5 -1 2 số cơ sở án x1 x2 x3 x4 3 x1 1 1 4 -1 0 2 x4 5 0 1 3 1 f(x 0) = 13 0 9 4 0 ∆ ∆ ∆ ∆ 1 2 3 4 20/6/2012 MaMH : 501014 Ch ươ ng 1 : Bài toán Quy ho ạch tuy ến tính 35
- Phương pháp đơn hình Tìm PA mới: Hệ Bi ến Ph ương 3 5 -1 2 số cơ sở án x1 x2 x3 x4 5 x2 1/4 1/4 1 -1/4 0 2 x4 19/4 -1/4 0 13/4 1 f(x 1) = 43/4 -9/4 0 25/4 0 20/6/2012 MaMH : 501014 Ch ươ ng 1 : Bài toán Quy ho ạch tuy ến tính 36
- Phương pháp đơn hình Tìm PA mới: Hệ Bi ến Ph ương 3 5 -1 2 số cơ sở án x1 x2 x3 x4 5 x2 8/13 3/13 1 0 1/13 -1 x3 19/13 -1/13 0 1 4/13 f(x 2) = 21/13 -23/13 0 0 -25/13 20/6/2012 MaMH : 501014 Ch ươ ng 1 : Bài toán Quy ho ạch tuy ến tính 37
- Phương pháp đơn hình ∆ ≤ = Vìj 0,j 1,4 nên: • PATƯ của bài toán: x * = (0,8 / 13,19 / 13,0); • Giá tr ị tối ưu: f( x * )= 21/13. 20/6/2012 MaMH : 501014 Ch ươ ng 1 : Bài toán Quy ho ạch tuy ến tính 38
- Phương pháp đơn hình Lưu ý 1. Nếubàitoánf( x )→ max , thìho ặc: - Chuy ển về bài toán gx()= − fx () → min; - Ho ặc gi ải tr ực ti ếp bài toán f( x )→ max. ∆ = 2. Ở bảng đơn hình tối ưu, nếu cój 0, vớixj là bi ến không cơ sở thì bài toán có PATƯ khác. 20/6/2012 MaMH : 501014 Ch ươ ng 1 : Bài toán Quy ho ạch tuy ến tính 39
- 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: = + + + → fx() cx11 cx 22 cxn n min axax+ ++ ax = b 111 122 1n n 1 axax+ ++ ax = b 211 222 2n n 2 ⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯ axax+ ++ ax = b m11 m 22 mnnm ≥ = xj 0, j 1, n 20/6/2012 MaMH : 501014 Ch ươ ng 1 : Bài toán Quy ho ạch tuy ến tính 40
- 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 ả xn+ i 0, i 1, m với hệ số là 1. Trên hàm mục tiêu , các bi ến gi ả có hệ số là +M( f ( x ) → min), −M( f ( x ) → max), với M là số dương rất lớn. 20/6/2012 MaMH : 501014 Ch ươ ng 1 : Bài toán Quy ho ạch tuy ến tính 41
- Phương pháp đơn hình Bài toán mở rộng: m = + + ++ → fx( ) cx11 cx 22 cxn n M(∑ x n+ i ) min i =1 axax+++ ax+1x = b 11 1 12 2 1n n n+1 1 axax+++ ax+1x + = b 21 1 22 2 2n n n 2 2 ⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯ axax+++ ax+1x = b m11 m 22 mn nn+ m m ≥ = + xj 0,j 1 ,n m 20/6/2012 MaMH : 501014 Ch ươ ng 1 : Bài toán Quy ho ạch tuy ến tính 42
- Phương pháp đơn hình ∆ =δ + γ Xét dấu j jM j ∆ > δ > δ = γ > • j 0 nếuj 0 ho ặc(j 0 và j 0) ∆ ∆ δ> δ δ= δ γ> γ ) • j k nếuj k ho ặc( j k và j k Các bước tính toán nh ư pp đơn hình thông th ường. 20/6/2012 MaMH : 501014 Ch ươ ng 1 : Bài toán Quy ho ạch tuy ến tính 43
- 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à *= * x( xx1 , 2 , , x n ,0, ,0) thì bt gốc có PATƯ là *= * x( xx1 , 2 , , x n ) 3. Nếu bt mở rộng có PATƯ là *= * > x( xx1 , 2 , , xn ,0,0, a 0, ,0) thì bt gốc không có PA. xn+ i 20/6/2012 MaMH : 501014 Ch ươ ng 1 : Bài toán Quy ho ạch tuy ến tính 44