›
›

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

pdf 44 trang hapham 2180
Download
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:

  • pdfbai_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

  1. 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
  2. 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
  3. 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
  4. 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
  5. 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
  6. 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
  7. 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
  8. 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
  9. 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
  10. 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
  11. 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
  12. 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
  13. 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
  14. 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
  15. 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
  16. 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
  17. 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
  18. 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
  19. 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
  20. 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
  21. 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
  22. 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
  23. 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
  24. 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
  25. 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
  26. 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
  27. 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
  28. 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
  29. 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
  30. 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
  31. 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
  32. 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
  33. 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
  34. 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
  35. 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
  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 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
  37. 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
  38. 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
  39. 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
  40. 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
  41. 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
  42. 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
  43. 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
  44. 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