›
›

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

ppt 92 trang huongle 9320
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 4: Bài toán vận tải", để 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:

  • pptbai_giang_quy_hoach_tuyen_tinh_chuong_4_bai_toan_van_tai.ppt

Nội dung text: Bài giảng Quy hoạch tuyến tính - Chương 4: Bài toán vận tải

  1. NHÓM I
  2. BÀI TOÁN VẬN TẢI THÀNH LẬP BÀI TOÁN ĐẶC ĐIỂM CỦA BÀI TOÁN VTCĐ PHƯƠNG ÁN CỰC BIÊN CỦA BÀI TOÁN VTCĐ XÂY DỰNG PACB ĐẦU TIÊN PHƯƠNG PHÁP THẾ VỊ GIẢI BÀI TOÁN VẬN TẢI BÀI TOÁN VẬN TẢI KHÔNG CÂN BẰNG THU PHÁT BÀI TOÁN VẬN TẢI CÓ Ô CẤM TRƯỜNG HỢP SUY BIẾN
  3. BÀI TOÁN VẬN TẢI Một dạng đặc biệt của bài toán QHTT có nhiều ứng dụng trong thực tế là Bài toán vận tải, sẽ được nghiên cứu trong chương này. Về mặt lý thuyết, bài toán vận tải (đã được giới thiệu khái niệm trong đoạn 1.2) cũng là một bài toán QHTT, nên chúng ta cũng có thể dùng phương pháp đơn hình để giải. Tuy nhiên, nếu dùng thuật toán đơn hình như trong chương 2, khối lượng tính toán sẽ rất lớn và phức tạp vì số ẩn quá nhiều. Do có một số đặc điểm riêng, nên người ta xây dựng các phương pháp giải riêng đơn giản hơn, nhanh hơn cho bài toán vận tải. Chương này vẫn dùng ký hiệu: I = {1, 2, , m} và J = {1, 2, , n}.
  4. BÀI TOÁN VẬN TẢI 4.1. THÀNH LẬP BÀI TOÁN
  5. BÀI TOÁN VẬN TẢI 4.1.1 Bài toán vận tải cân bằng thu phát mn Ta có pi= tj (4.1.1) ij==11
  6. BÀI TOÁN VẬN TẢI mn zfXcx==→()min  ijij ij==11 n  xpiIiji = j=1 m  xtjJijj = i=1 xiIjJij 0,,
  7. BÀI TOÁN VẬN TẢI 4.1.2 Bài toán không cân bằng thu phát gọi là bài toán dạng mở: m n m n pi  tj,à v  pi  tj i=1 j = 1 i = 1 j = 1 mn 4.1.2.1 Trường hợp 1: pi tj ij==11
  8. BÀI TOÁN VẬN TẢI mn z= f( X ) = cij x ij → min ij==11 n  xij== p i i1, m j=1 m  xij = t j j1, n i=1 x 0, i = 1, m , j = 1, n ij
  9. BÀI TOÁN VẬN TẢI 4.1.3 Định lý tồn tại: 4.2 ĐẶC ĐIỂM CỦA BÀI TOÁN VTCĐ mn z= f( X ) = cij x ij → min ij==11 n  xij= p i i I j=1 m  xij= t j j J i=1 xij 0, i I , j J
  10. BÀI TOÁN VẬN TẢI
  11. BÀI TOÁN VẬN TẢI 1 1 1 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 A = 1 1 1 0 0 0 1 1 1 1 0 0 1 0 0 1 0 0 0 1 0 0 1 0 0 1 0 0 0 1 0 0 1 0 0 1
  12. BÀI TOÁN VẬN TẢI 4.2.1 Định lý :
  13. BÀI TOÁN VẬN TẢI Thật vậy, với các số thực 21, , mn ,  , ,  thỏa: 2HHHHH 2+ 3 3 + + m m +  1 m++ 1 +  2 m 2 + + +nH m+ n = 0 mn chúng ta có ngay12=  = = n = 0 và 2+  1 =0, 3 +  1 = 0, , m +  1 = 0 từ đó, 23= = = m = 0 Do đó, r(A) = m + n - 1.
  14. BÀI TOÁN VẬN TẢI
  15. BÀI TOÁN VẬN TẢI 4.3 PHƯƠNG ÁN CỰC BIÊN CỦA BÀI TOÁN VTCĐ 4.3.1 Mô tả bài toán VTCĐ dưới dạng bảng :
  16. BÀI TOÁN VẬN TẢI Thu t t j i tn phát c11 c1 j c1n p1 c ci1 ij cin pi ( xij ) cmj c cm1 mn pm
  17. BÀI TOÁN VẬN TẢI
  18. BÀI TOÁN VẬN TẢI 4.3.2 Định nghĩa :
  19. BÀI TOÁN VẬN TẢI 4.3.3 Bổ đề :
  20. BÀI TOÁN VẬN TẢI
  21. BÀI TOÁN VẬN TẢI  ijAO ij= m+ n (,)i j U AAAAAi1 j 1− i 2 j 1 + i 2 j 2 − + ikjk − i 1 jk + += ijAO ij m+ n (,)i j U
  22. BÀI TOÁN VẬN TẢI 4.3.4 Định lý :
  23. BÀI TOÁN VẬN TẢI
  24. BÀI TOÁN VẬN TẢI 4.3.5 Định nghĩa : 4.3.6 Định lý :
  25. BÀI TOÁN VẬN TẢI
  26. BÀI TOÁN VẬN TẢI Giả sử: V1={( ijijijij ', '),( ', 1 ),( 1 , 1 ),( 1 , 2 ), ,( ijijk , k ),( k , ')} V21={( i ', j '),( i ', l ), ,( ip , l p ),( i p , j ')} từ đây ta lại có một vòng V3={( ijijij ', 1 ),( 1 , 1 ),( 1 , 2 ), ,( ijijijilk , k ),( k , '),( p , '),( p , p ), ,( il ', 1 )}
  27. BÀI TOÁN VẬN TẢI 4.4 XÂY DỰNG PACB ĐẦU TIÊN:
  28. BÀI TOÁN VẬN TẢI
  29. BÀI TOÁN VẬN TẢI
  30. BÀI TOÁN VẬN TẢI
  31. BÀI TOÁN VẬN TẢI
  32. BÀI TOÁN VẬN TẢI
  33. BÀI TOÁN VẬN TẢI
  34. BÀI TOÁN VẬN TẢI 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 Fogels
  35. BÀI TOÁN VẬN TẢI 4.4.1 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 (t1; p1) Nếu t1 > p1 : ta đặt x12 = min (t1 – p1; p2) Nếu t1 < p1 : ta đặt x21 = min (p1 – t1; t2) 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.
  36. BÀI TOÁN VẬN TẢI 4.4.1.1 Thí dụ:
  37. BÀI TOÁN VẬN TẢI
  38. BÀI TOÁN VẬN TẢI
  39. BÀI TOÁN VẬN TẢI 4.4.2 PHƯƠNG PHÁP PHẦN TỬ NHỎ NHẤT
  40. BÀI TOÁN VẬN TẢI Chọn ô cij có giá trị nhỏ nhất trong bảngchi phí vận chuyển. Tính và điền vào ô đó giá trị xij = min (ti,pj). 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 ti = pj thì không xét đồng thời cả cột Bj lẫn hàng Ai. 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ụ.
  41. BÀI TOÁN VẬN TẢI 4.4.2.1 Thí dụ: Giải : Ưu tỉên phân phối hàng vào ô có cij nhỏ nhất trong mỗi hàng. Lần lượt phân phối hàng, theo thứ tự, vào các ô: (1,3); (2,1); (1,2); (3,2) và (3,1):
  42. BÀI TOÁN VẬN TẢI
  43. BÀI TOÁN VẬN TẢI
  44. BÀI TOÁN VẬN TẢI 4.4.3 PHƯƠNG PHÁP FOGELS 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.
  45. BÀI TOÁN VẬN TẢI 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 xoá 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.
  46. BÀI TOÁN VẬN TẢI 4.4.3.1 Thí dụ: Hiệu số lớn nhất là 5 ở hàng 3, nên đầu tiên phân phối cho ô (3,3) với lượng hàng là x33 = 50 Không kể đến hàng 3, tính lại các hiệu số chi phí, rồi tiếp tục tìm hiểu số lớn nhất, Lần lượt phân phối hàng, theo thứ tự, vào các ô: (3,3); (1,3); (2,1); (1,2); (1,1)
  47. BÀI TOÁN VẬN TẢI
  48. BÀI TOÁN VẬN TẢI 25 60 15 X = 50 0 0 0 0 50 Giá trị mục tiêu tương ứng là: fx( )= + 5 25 4 60 + + 1 15 2 50 + 2 50 = 580
  49. BÀI TOÁN VẬN TẢI 4.5 PHƯƠNG PHÁP THẾ VỊ THUẬT GIẢI Bước 1: Xác định hệ thế vị (ui,vj) Bước 2: Kiểm tra tiêu chuẩn tối ưu Bước 3: Điều chỉnh phương án
  50. BÀI TOÁN VẬN TẢI Bước 1: Xác định hệ thế vị (ui,vj) Từ phương án tựa ban đầu, xác định hệ số thế vị (ui, vj). Hệ thế vị được tính từ các ô cơ sở: ui + vj = cij * Ô 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.
  51. BÀI TOÁN VẬN TẢI Bước 2: Kiểm tra tiêu chuẩn tối ưu Dùng Định lý 4.5.1. Hiển nhiên điều kiện (b) được thoả mãn tại các ô cơ sở, nên chúng ta chỉ cần kiểm tra điều kiện (a) tại các ô phi cơ sở. Với mọi ô (i, j) S, tính đại lượng: ( gọi là ước lượng của ô (i, j) ) ij = ui + vj - cij · Nếu ij 0, với mọi (i, j) S, thì X là một PATƯ. Thuật toán kết thúc. · Nếu có một (i, j) S sao cho ij > 0, thì X không là một PATƯ. Ô (i, j) đó được gọi là ô vi phạm. Chuyển sang bước 3.
  52. BÀI TOÁN VẬN TẢI Giả sử: =rs ma x ij ij 0 − Xác địnhq = min {xij / ( i, j) V }, gọi là lượng điều chỉnh.
  53. BÀI TOÁN VẬN TẢI x ij + xij= x ij + q vôùi(,) i j V x− q vôùi(,) i j V − ij '' f()() X− f X = cij x ij − c ij x ij = − q rs (,)(,)i j V i j V
  54. BÀI TOÁN VẬN TẢI
  55. BÀI TOÁN VẬN TẢI 4.5.3 Thí dụ:
  56. BÀI TOÁN VẬN TẢI
  57. BÀI TOÁN VẬN TẢI
  58. BÀI TOÁN VẬN TẢI
  59. BÀI TOÁN VẬN TẢI
  60. BÀI TOÁN VẬN TẢI
  61. BÀI TOÁN VẬN TẢI
  62. BÀI TOÁN VẬN TẢI
  63. BÀI TOÁN VẬN TẢI
  64. BÀI TOÁN VẬN TẢI 4.6. BÀI TOÁN VẬN TẢI KHÔNG CÂN BẰNG THU PHÁT: mn 4.6.1.TRƯỜNG HỢP: ptij ii==11
  65. BÀI TOÁN VẬN TẢI nm pm+1 = t j − p i 0 ji==11
  66. BÀI TOÁN VẬN TẢI m n n cij x ij+→ 0. x m+1, j min i=1 j = 1 j = 1 n  xij= p i ( i = 1, , m + 1) j=1 m  xij= t j () j J i=1 x 0 ( i = 1, , m + 1; j J ) ij
  67. BÀI TOÁN VẬN TẢI
  68. BÀI TOÁN VẬN TẢI Giải. Đây là một bài toán không cân bằng thu phát, với
  69. BÀI TOÁN VẬN TẢI nm tpji− =300 − 262 = 38 ji==11
  70. BÀI TOÁN VẬN TẢI
  71. BÀI TOÁN VẬN TẢI Kiểm tra tiêu chuẩn tối ưu: Vì max =45 3 , nên chọn ô (4,5) làm ô điều chỉnh ij 0
  72. BÀI TOÁN VẬN TẢI
  73. BÀI TOÁN VẬN TẢI
  74. BÀI TOÁN VẬN TẢI
  75. BÀI TOÁN VẬN TẢI mn 4.6.2. Trường hợp ptij ii==11 Đưa vào một điểm thu ảo Tn +1, với yêu cầu lượng thu tương ứng làmn t= p − t 0 và đặt , với mọi n+1  i j ci,n + 1 = 0 iI ij==11 Chúng ta có bài toán VTCĐ tương ứng gồm có m điểm phát và n + 1 điểm thu như sau:
  76. BÀI TOÁN VẬN TẢI m n m cij x ij+→ 0. x i,1 n+ min i=1 j = 1 i = 1 n  xij= p i () i I j=1 m  xij= t j ( j = 1, , n + 1) i=1 x 0 ( j = 1, , n + 1; i I ) ij Dùng thuật toán thế vị để giải bài toán này. Từ một PATƯ của nó, loại bỏ các thành phần xi,n+1, chúng ta có được một PATƯ của bài toán đã cho.
  77. BÀI TOÁN VẬN TẢI 4.7 BÀI TOÁN VẬN TẢI CÓ Ô CẤM. Trong trường hợp, vì một lý do nào đó, không thể vận chuyển hàng từ điểm phát i đến điểm thu j thì ô (i, j) trên bảng tương ứng được gọilà một ô cấm. Không được phân phối hàng vào ô cấm. Để giải quyếttrường hợp này, người ta gán chi phí vận chuyển ở ô cấm bằng M > 0lớn tuỳ ý, chúng ta có một bài toán khác gọi là bài toán (VM).Dùng thuật toán thế vị để giải bài toán này. Nếu trong PATƯ của bài toán (VM), tất cả các thành phần ứng với ô cấm đều bằng 0 thì PATƯ đó cũng chính là một PATƯ của bài toán ban đầu.
  78. BÀI TOÁN VẬN TẢI Nếu trong PATƯ của bài toán (VM) có một thành phần ứng với ô cấm khác 0,thì bài toán ban đầu không có phương án. 4.8 TRƯỜNG HỢP SUY BIẾN Trường hợp một PACB X có /G(X)/ < m + n - 1 thì X là suy biến.Khi đó, chúng ta phải bố sung một ô nào đó vào G(X) để có tập ô cơ sở S.Ô bổ sung đó phải thoả mãn các yêu cầu sau: Không được tạo thành vòng với các ô cơ sở đã có, giúp chúng ta tính đủ hệ thống thế vị {ui, vj}, và đặt xij = 0 vào ô đó.
  79. BÀI TOÁN VẬN TẢI Thí dụ: Một công ty cần vận chuyển một loại hàng từ 4 kho chứa hàng đến 3 cửa hàng của công ty đó. Số lượng hàng hiện có ở các kho, yêu cầu của các cửa hàng và chi phí vận chuyển từ mỗi kho đến mỗi cửa hàng được cho trong bảng sau:
  80. BÀI TOÁN VẬN TẢI Bài toán đặt ra là: Lập kế hoạch vận chuyển hàng sao cho các cửa hàng được thu đủ theo yêu cầu và tổng chi phí vận chuyển là thấp nhất. 1) Hãy tìm một PATƯ cho bài toán và cho biết chi phí thấp nhất. 2) Giải lại câu (a), nếu có thêm điều kiện “ kho hàng thứ tư phải phát hết hàng ”. Giải. (a) Đây là một bài toán không cân bằng thu phát, với mn ptij− =495 − 470 = 25 ij==11
  81. BÀI TOÁN VẬN TẢI Đưa vào một điểm thu ảo, với yêu cầu lượng thu tương ứng là 25, chúng ta có bài toán VTCĐ tương ứng. Xây dựng PACB đầu tiên bằng phương pháp đường gần và tính hệ thống thế vị. PACB thu được là suy biến, nên chúng ta bổ sung thêm ô (1,1) để có tập ô cơ sở tương ứng. Kết quả được trình bày trong bảng 4.15:
  82. BÀI TOÁN VẬN TẢI
  83. BÀI TOÁN VẬN TẢI và lượng điều chỉnh là q = min {100,35} = 35 = x43. Sau khi điều chỉnh, chúng ta có bảng sau:
  84. BÀI TOÁN VẬN TẢI
  85. BÀI TOÁN VẬN TẢI
  86. BÀI TOÁN VẬN TẢI
  87. BÀI TOÁN VẬN TẢI Ô điều chỉnh là ô (3,4), lượng điều chỉnh là q = 25 = x44. Sau khi điều chỉnh, chúng ta có bảng sau:
  88. BÀI TOÁN VẬN TẢI
  89. BÀI TOÁN VẬN TẢI
  90. Xin cảm ơn các bạn đã theo dõi. Hoàng em- Lớp DH7A2- Su phạm toán Đại học An Giang