›
›

Toán học - Quy hoạch tuyến tính

ppt 58 trang vanle 2830
Download
Bạn đang xem 20 trang mẫu của tài liệu "Toán học - 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:

  • ppttoan_hoc_quy_hoach_tuyen_tinh.ppt

Nội dung text: Toán học - Quy hoạch tuyến tính

  1. LÊ HUỲNH TUYẾT ANH ThángTháng 33 20082008
  2. QUY HOẠCH TUYẾN TÍNH PHÁT BIỂU BÀI TỐN QUY HOẠCH TUYẾN TÍNH ymax = max c1x1 + c2x2 + + cnxn ymin = min c1x1 + c2x2 + + cnxn Ràng buộc a11x1 + a12x2 + + a1nxn (≤, =, ≥) b1 a21x1 + a22x2 + + a2nxn (≤, =, ≥) b2 : am1x1 + am2x2 + + amnxn (≤, =, ≥) bm Bài tốn quy hoạch tuyến tính thuộc loại bài tốn tối ưu thực định
  3. ĐIỀUĐIỀU KIỆNKIỆN ĐỂĐỂ BÀIBÀI TỐNTỐN TỐITỐI ƯUƯU THUỘCTHUỘC DẠNGDẠNG BÀIBÀI TỐNTỐN QUYQUY HOẠCHHOẠCH TUYẾNTUYẾN TÍNHTÍNH HÀM￿MỤC￿TIÊU￿là￿hàm￿bậc￿nhất￿đối￿với￿các￿biến CÁC￿ĐIỀU￿KIỆN￿RÀNG￿BUỘC￿ phải￿được￿thể￿hiện￿qua￿ các￿hàm￿tốn￿học￿bậc￿nhất￿tuyến￿tính
  4. PHƯƠNG PHÁP ĐỒ THỊ BÀI TỐN Thời gian làm việc Đất sét Doanh thu Sản phẩm (giờ/đơn vị) (kg/đơn vị) (1000$/đơn vị) Tơ 1 4 40 Bình 2 3 50 Trong một xưởng mỗi ngày,,￿cĩ tối đa 40 giờ làm việc và 120 kg đất sét để sản xuất tơ và bình. Với x1 = số tơ được sản xuất trong ngày x2 = số bình được sản xuất trong ngày
  5. PHÁT BIỂU BÀI TỐN TỐI ƯU yymaxmax == MaxMax 4040 xx11 ++ 5050 xx22 ĐiềuĐiều kiệnkiện ràngràng buộcbuộc xx11 ++ 22xx22  4040 (ràng(ràng buộcbuộc vềvề giờgiờ làmlàm việc)việc) 44xx11 ++ 33xx22  120120 (ràng(ràng buộcbuộc vềvề đấtđất sét)sét) xx11 ,, xx22  00
  6. GIẢI BẰNG PHƯƠNG PHÁP ĐỒ THỊ Vẽ hệ trục tọa độ x1Ox2 Xác định miền giới hạn của bài tốn trên hình vẽ Vẽ hàm mục tiêu sao cho đi qua trục tọa độ Tịnh tiến đường thẳng này trong miền giới hạn bài tốn Xác định nghiệm tối ưu bài tốn trên biên miền xác định
  7. ĐỊNH LÝ VỀ ĐIỂM CỰC BIÊN Đối với bài tốn quy hoạch tuyến tính thì cực trị nằm trên biên của miền xác định và thường nằm trên đỉnh gọi là các điểm cực biên
  8. GIẢI BẰNG PHƯƠNG PHÁP ĐỒ THỊ x2 50 – 40 – 4 x1 + 3 x2 =120 30 – 4 x1 + 3 x2 120 10 – 0 – | | | | | | 10 20 30 40 50 60 x1
  9. GIẢI BẰNG PHƯƠNG PHÁP ĐỒ THỊ x2 50 – 40 – 4 x1 + 3 x2 120 30 – 20 – Miền xác định 10 – x1 + 2 x2 40 0 – | | | | | | 10 20 30 40 50 60 x1
  10. TÍNH GIÁ TRỊ TỐI ƯU x2 40 – 30 – MiềnMiền xácxác địnhđịnh OABCOABC 20 – A B 10 – B 8 24 x 0 – | | | | 1 10 20 30 C 40
  11. TÍNH GIÁ TRỊ TỐI ƯU x1 + 2x2 = 40 x2 1 2 4x + 3x = 120 40 – 1 2 44 xx11 ++ 33 xx22  120120 4x1 + 8x2 = 160 30 – -4x1 - 3x2 = -120 5x = 40 20 – 2 x2 = 8 xx11 ++ 22 xx22  4040 10 – 8 x1 + 2(8) = 40 24 x 0 – | | | | 1 x = 24 10 20 30 40 1 y = 40(24) + 50(8) = 1,360
  12. TÍNH TỐN ĐIỂM CỰC BIÊN x1 = 0 x x1 = 24 2 x2 =20 x2 =8 40 – y = 1,000 x = 30 40 y = 1,360 1 x =0 30 – 2 y = 1,200 20 – A 10 – B 0 – | | | C| 10 20 30 40 x1
  13. PHƯƠNG PHÁP ĐỒ THỊ BÀI TỐN A B Điều kiện lưu trữ Dầu thơ (tấn) (tấn) (tấn) Xăng 0.2 0.4 1200 DO 0.2 0.2 1200 FO 0.4 0.4 1400 Hiệu quả kinh tế 140 150 (USD/tấn) Một nhà máy lọc dầu xử lý hai loại dầu thơ 1 và 2 để sản xuất xăng, DO, FO. Với: x1 = số lượng dầu thơ A cần xử lý x2 = số lượng dầu thơ B cần xử lý
  14. PHÁT BIỂU BÀI TỐN TỐI ƯU yymaxmax == MaxMax 140140 xx11 ++ 150150 xx22 ĐiềuĐiều kiệnkiện ràngràng buộcbuộc 0.2x0.2x11++0.40.4xx22  12001200 (ràng(ràng buộcbuộc vềvề xăng)xăng) (1)(1) 0.40.4xx11++0.20.2xx22  12001200 (ràng(ràng buộcbuộc vềvề DO)DO) (2)(2) 0.4x0.4x11++0.4x0.4x22  14001400 (ràng(ràng buộcbuộc vềvề FO)FO) (3)(3) xx11 ,, xx22  00 (4)(4)
  15. 5. Giải bài toán bằng phương pháp đồ thị: 0.4x x2 1 + 0.2x A(2,3) B(8,0) D 0.4x (2) 2 1 + 0.4x = 1200 C(4,6) D(8,8) C (4) 2 = 1400 (1) A B (3) 0.2x 1 + 0.4x A C 2 = 1200 Z=0 B O D x1 Zmin
  16. 5. Giải bài toán bằng phương pháp đồ thị: 0.4x x2 1 + 0.2x A(2,3) B(8,0) D 0.4x (2) 2 = 1200 1 + 0.4x C(4,6) D(8,8) C A(4) (0,3000) MiềnMiền2 = 1400 xácxác địnhđịnh OABCDOABCD B (1) B (1000,2500)(3) 0.2x 1 + 0.4x A C 2 = 1200 C (2500,1000) Z=0 D (3000,0)B O x1 Zmin
  17. PHÁT BIỂU BÀI TỐN TỐI ƯU Tại￿điểm￿B,￿hàm￿mục￿tiêu￿đạt￿giá￿trị￿cao￿nhất. Giá￿trị￿lớn￿nhất￿tại￿B(1000,2500)￿:￿ ￿￿￿￿￿ymax￿=￿1000x140￿+￿2500x150￿=￿515000 Kết￿luận:￿ Ta￿cần￿xử￿lý￿1000￿tấn￿dầu￿thơ￿A￿và￿2500￿tấn￿ dầu￿thơ￿B￿để￿đạt￿lợi￿nhuận￿là￿515000￿USD
  18. PHÁT BIỂU BÀI TỐN TỐI ƯU Lập phương án phân bổ lượng chất thải hàng ngày từ 4 bệnh viện A1, A2, A3, A4 đến 4 bãi rác B1, B2, B3, B4. Biết rằng: Lượng chất thải hàng ngày aii (kg/ngày) được thải ra từ bệnh viện Aii là: a1 = 160, a2 = 150, a3 = 190, a4 = 100. Lượng chất thải hàng ngày bjj (kg/ngày) được nhận vào ở bãi rác Bjj là: b1 = 120, b2 = 175, b3 = 155, b4 = 150. Chi phí vận chuyển 1kg chất thải từ Aii đến Bjj là cijij (ngàn đồng) được cho theo bảng sau: BTTƯ được đặt ra là tìm đường đi giữa các điểm cho các xe sao cho chi phí vận chuyển là tối thiểu.
  19. XÁC ĐỊNH ĐẠI LƯỢNG •Chi phí vận chuyển 1 kg chất thải từ Aii đến Bjj: cijij •Lượng chất thải vận chuyển từ Aii đến Bjj: xijij •Lượng chất thải ở từng bệnh viện : ajj •KhảKhả năngnăng nhậnnhận chấtchất thảithải củacủa mỗimỗi bãibãi rácrác:: bbii •TổngTổng chichi phíphí vậnvận chuyểnchuyển tấttất cảcả lượnglượng chấtchất thảithải yy
  20. BẢNG CHI PHÍ VẬN CHUYỂN 1KG CHẤT THẢI TỪ Ai ĐẾN Bj Bãi rác 1 Bãi rác 2 Bãi rác 3 Bãi rác 4 Cung (kg/ngày) Bệnh viện A 31 19 25 25 160 Bệnh viện B 25 13 18 22 150 Bệnh viện C 37 29 27 20 190 Bệnh viện D 13 24 30 18 100 Cầu 120 175 155 150 600 (kg/ngày)
  21. PHÁT BIỂU BÀI TỐN TỐI ƯU ĐốiĐối tượngtượng cơngcơng nghệnghệ:: HệHệ thốngthống vậnvận chuyểnchuyển rácrác từtừ bệnhbệnh việnviện đếnđến bãibãi rác.rác. HàmHàm mụcmục tiêutiêu:: Với:Với: xxijij (kg/ngày)(kg/ngày) làlà lượnglượng chấtchất thảithải cầncần chuyểnchuyển từtừ AAii đếnđến BBj.j.
  22. PHÁT BIỂU BÀI TỐN TỐI ƯU CácCác ràngràng buộcbuộc:: BàiBài tốntốn trêntrên thuộcthuộc loạiloại bàibài tốntốn vậnvận tảitải
  23. PHƯƠNG PHÁP THẾ VỊ THUẬT GIẢI BƯỚC 1: Xây dựng phương án đầu tiên (điểm xuât phát X0) BƯỚC 2: Xác định hệ thế vị (ui,vj) BƯỚC 3: Kiểm tra tiêu chuẩn tối ưu Lặp lại quá trình cho đến khi thu được nghiệm tối ưu
  24. XÂY DỰNG PHƯƠNG ÁN ĐẦU TIÊN 1. Phương pháp gĩc Tây Bắc 2. Phương pháp phần tử nhỏ nhất 3. Phương pháp Vogel
  25. PHƯƠNG PHÁP GĨC TÂY BẮC Điền dần phương án vận chuyển vào ma trận vận chuyển, bắt đầu từ ơ bên trái phía trên. Đặt x11 = min (a1; b1) Nếu a1 > b1 : ta đặt x12 = min (a1 – b1; b2) Nếu a1 < b1 : ta đặt x21 = min (b1 – a1; a2) Theo cách trên ta tiếp tục điền vào các ơ của ma trận vận chuyển cho đến khi khơng cịn hàng ở các điểm phát hàng và thoả mãn nhu cầu ở các điểm nhận hàng.
  26. PHƯƠNG PHÁP PHẦN TỬ NHỎ NHẤT Chọn ơ cijij cĩ giá trị nhỏ nhất trong bảng chi phí vận chuyển. Tính và điền vào ơ đĩ giá trị xijij = min (aii, bjj). Sau đĩ, ta khơng xét hàng hoặc cột cĩ dự trữ đã hết hay nhu cầu đã thoả mãn. Nếu aii = bjj thì khơng xét đồng thời cả cột Bjj lẫn hàng Aii. Từ phần cịn lại của bảng ta lại chọn ơ cĩ giá trị nhỏ nhất và quá trình phân phối tiếp tục cho đến khi thoả mãn nhu cầu ở các điểm tiêu thụ.
  27. PHƯƠNG PHÁP VOGEL B1: Tính độ lệch của các hàng và cột. Độ lệch của mỗi hàng (cột) = chi phí thấp thứ nhì trong hàng (cột) – chi phí thấp nhất trong hàng (cột) ấy. B2: Chọn hàng (cột) cĩ độ lệch lớn nhất để ưu tiên phân phối trước. Trong hàng (cột) ấy ưu tiên phân phối tối đa cho ơ nào cĩ chi phí nhỏ nhất.
  28. PHƯƠNG PHÁP VOGEL B3: Nếu cĩ nhiều hàng (cột) cĩ cùng độ lệch lớn nhất thì ta xác định ơ trũng. Ơ trũng là ơ cĩ chi phí nhỏ nhất nằm giữa giao của một hàng và một cột đang xét để ưu tiên phân phối cho ơ nào cĩ chi phí nhỏ nhất trong tất cả các hàng và cột đang xét. B4: Sau mỗi lần phân phối ta xố hàng (cột) tương ứng với nĩ. Ta cĩ một bảng mới, tính lại độ lệch của các cột trong bảng này, sửa lại lượng hàng. B5: Với bảng cịn lại tiếp tục các bước 2 và 3 cho tới khi kết thúc.
  29. PP GĨC TÂY BẮC §Điền phương án vận chuyển, bắt đầu từ ơ bên trái phía trên. §Đặt x11 = min (a1; b1) = min (160; 120) = 120. §Nhu cầu ở B1 được thỏa mãn nên ta bỏ cột B1. §Vì a1 > b1 nên phần dư (a1 – b1) = 40 được chuyển từ A1 đến B2 nên x12 = min (a1 – b1; b2) = min (40; 175) = 40. §Lúc này, nhu cầu ở A1 đã thỏa nên ta bỏ hàng A1. Nhu cầu ở B2 chưa đáp ứng được là: 175 – 40 = 135 nên phải chuyển từ A2 đến B2 một lượng x22 = min (135; 150) = 135. §Quá trình trên được tiếp tục với kết quả được trình bày ở bảng sau:
  30. Bãi rác Bãi rác 2 Bãi rác 3 Bãi rác 4 Cung 1 (kg/ngày) Bệnh viện A 31 19 25 25 160160 120 40 160-120=40 Bệnh viện B 25 13 18 22 150150 135 15 150-135=15 Bệnh viện C 37 29 27 20 190190 140 50 190-140=50 Bệnh viện D 13 24 30 18 100100 100 CầuCầu 120120 175175 155155 150150 600600 (kg/(kg/ngàyngày)) 175-40=135 155-15=140
  31. Bãi rác Bãi rác 2 Bãi rác 3 Bãi rác 4 Cung 1 (kg/ngày) Bệnh viện A 31 19 25 25 160160 120 40 Bệnh viện B 25 13 18 22 150150 135 15 Bệnh viện C 37 29 27 20 190190 140 50 Bệnh viện D 13 24 30 18 100100 100 CầuCầu 120120 175175 155155 150150 600600 (kg/(kg/ngàyngày))
  32. XÂY DỰNG PHƯƠNG ÁN ĐẦU TIÊN – PP GĨC TÂY BẮC VớiVới phươngphương ánán trêntrên tổngtổng chichi phíphí vậnvận chuyểnchuyển là:là: ZZ == 31x12031x120 ++ 19x4019x40 ++ 13x13513x135 ++ 18x1518x15 ++ 27x4027x40 ++ 20x5020x50 ++ 18x10018x100 == 13.08513.085 (ngàn(ngàn đồng)đồng)
  33. XÁC ĐỊNH HỆ THẾ VỊ (ui,vj) Từ phương án tựa ban đầu, xác định hệ số thế vị (uii, vjj). Hệ thế vị được tính từ các ơ cơ sở: uii + vjj = cijij * Ơ cơ sở là những ơ cĩ điền giá trị của biến số khác 0. * Ơ tự do là những ơ cịn lại. * Chọn một ẩn cho giá trị bằng 0, sau đĩ xác định các ẩn cịn lại.
  34. XÁC ĐỊNH HỆ SỐ THẾ VỊ Hệ thế vị được tính từ các ơ cơ sở: ui + vj = cij u1 + v1 = 31 ; u1 + v2 = 19 ; u2 + v2 = 13 ; u2 + v3 = 18 ; u3 + v3 = 27 ; u3 + v4 = 20 ; u4 + v4 = 18. Cho u1 = 0  v1 = 31 ; v2 = 19 ; v3 = 24 ; v4 = 17; u2 = – 6 ; u3 = 3 ; u4 = 1.
  35. KIỂM TRA Kiểm tra tiêu chuẩn tối ưu ở các ơ tự do. * Nếu các ơ tự do thỏa ui + vj ≤ cij thì phương án tối ưu. * Nếu ở một ơ tự do bất kỳ cĩ ui + vj > cij thì phương án chưa tối ưu, ta phải cải thiện phương án vận chuyển. * Chọn ơ tự do cĩ Δij = max (ui + vj – cij) > 0 và tìm một chu trình tính đổi ứng với ơ tự do ấy. * Chu trình là một đường gãy khép kín, các chỗ gãy vuơng gĩc với nhau, cĩ một đỉnh là ơ tự do, các đỉnh cịn lại là các ơ cơ sở.
  36. KIỂM TRA Kiểm tra tiêu chuẩn tối ưu: u1 + v3 = 24 c41 ; u2 + v4 = 11 c41 = 13 => Phương án chưa tối ưu. Chọn ∆41 = u4 + v1 – c41 = 32 – 13 = 19 Ta xác định chu trình vận chuyển như bảng sau:
  37. Bãi rác 1 Bãi rác 2 Bãi rác 3 Bãi rác 4 Cung (kg/ngày) v1 = 31 v2 = 19 v3 = 24 v4 = 17 Bệnh viện A 31 19 25 25 160 u1 = 0 120 40 Bệnh viện B 25 13 18 22 150 u2 = – 6 135 15 Bệnh viện C 37 29 27 20 190 u3 = 3 140 50 Bệnh viện D 13 24 30 18 100 u4 = 1 100 Cầu 120 175 155 150 600 (kg/ngày)
  38. Bãi rác 1 Bãi rác 2 Bãi rác 3 Bãi rác 4 Cung (kg/ngày) v1 = 31 v2 = 19 v3 = 24 v4 = 17 Bệnh viện A 31 19 25 25 160 u1 = 0 20 140 Bệnh viện B 25 13 18 22 150 u2 = – 6 35 115 Bệnh viện C 37 29 27 20 190 u3 = 3 40 150 Bệnh viện D 13 24 30 18 100 u4 = 1 100 0 Cầu 120 175 155 150 600 (kg/ngày)
  39. XÁC ĐỊNH HỆ SỐ THẾ VỊ Sau khi xác định được phương án mới, ta lặp lại các bước (a) và (b) để kiểm tra xem phương án đã tối ưu hay chưa? u1 + v1 = 31 ; u1 + v2 = 19 ; u2 + v2 = 13 ; u2 + v3 = 18 ; u3 + v3 = 27 ; u3 + v4 = 20 ; u4 + v1 = 13. Cho u1 = 0  v1 = 31 ; v2 = 19 ; v3 = 24 ; v4 = 17; u2 = – 6 ; u3 = 3 ; u4 = – 18.
  40. KIỂM TRA Kiểm tra tiêu chuẩn tối ưu: u1 + v3 = 24 c42 ; u2 + v4 = 11 Phương án đã tối ưu.
  41. Bãi rác 1 Bãi rác 2 Bãi rác 3 Bãi rác 4 Cung v1 = 31 v2 = 19 v3 = 24 v4 = 17 (kg/ngày) Bệnh viện A 31 19 25 25 160 u1 = 0 20 140 Bệnh viện B 25 13 18 22 150 u2 = – 6 35 115 Bệnh viện C 37 29 27 20 190 u3 = 3 40 150 Bệnh viện D 13 24 30 18 100 u4 = – 18 100 Cầu 120 175 155 150 600 (kg/ngày)
  42. KIỂM TRA BẰNG PP THẾ VỊ Với phương án trên tổng chi phí vận chuyển là: Z = 31x20 + 19x140 + 13x35 + 18x115 + 27x40 + 20x150 + 13x100 = 11.185 (ngàn đồng)
  43. PHƯƠNG PHÁP VOGEL B1: Tính độ lệch của các hàng và cột. B2: Chọn hàng (cột) cĩ độ lệch lớn nhất để ưu tiên phân phối trước, ưu tiên phân phối tối đa cho ơ nào cĩ chi phí nhỏ nhất.
  44. PHƯƠNG PHÁP VOGEL B3: Nếu cĩ nhiều hàng (cột) cĩ cùng độ lệch lớn nhất thì ta xác định ơ trũng (ơ cĩ chi phí nhỏ nhất nằm giữa giao của một hàng và một cột) B4: Sau mỗi lần phân phối: -Xố hàng (cột) tương ứng với nĩ. -Tính lại độ lệch -Lặp lại quy trình phân phối
  45. BẢNG￿CHI￿PHÍ￿VẬN￿CHUYỂN￿ HÀNG￿HĨA￿TỪ￿Ai￿ĐẾN￿Bj Cung B B B B B 1 2 3 4 5 (kg/ngày) 10 6 5 8 9 A1 55 6 7 8 6 5 A2 20 8 6 10 8 6 A3 32 7 5 4 6 7 A4 29 Cầu 19 30 38 14 35 (kg/ngày)
  46. Độ lệch Cung 1 1 1 0 1 Δ 1 10 6 5 8 9 55 1 6 7 8 6 5 20 0 8 6 10 8 6 32 1 7 5 4 6 7 29 19 30 9 14 35 Cầu 38-29
  47. Độ lệch Cung Δ 2 0 3 2 1 1 10 6 5 8 9 46 55-9 9 1 6 7 8 6 5 20 2 8 6 10 8 6 32 Cầu 19 30 0 14 35 9-9
  48. Độ lệch Cung Δ 2 0 2 1 2 10 6 8 9 16 46-30 30 1 6 7 6 5 20 0 8 6 8 6 32 Cầu 19 0 14 35 30-30
  49. Độ lệch Cung Δ 2 2 1 1 10 8 9 16 1 6 6 5 6 20-14 14 0 8 8 6 32 Cầu 19 0 35 14-14
  50. B1 B2 B3 B4 B5 Cung 10 6 5 8 9 A1 16 30 9 55 6 7 8 6 5 A2 3 14 3 20 8 6 10 8 6 A3 32 32 7 5 4 6 7 A4 29 29 Cầu 19 30 38 14 35