›
›

Bài giảng Tối ưu hóa - Chương 3: Bài toán vận tải

pdf 25 trang hapham 1630
Download
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Tối ưu hóa - Chương 3: 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:

  • pdfbai_giang_toi_uu_hoa_chuong_3_bai_toan_van_tai.pdf

Nội dung text: Bài giảng Tối ưu hóa - Chương 3: Bài toán vận tải

  1. ThS. Phạm Trí Cao * Chương 3 03/01/2014 I) BÀI TOÁN VẬN TẢI CÂN BẰNG THU PHÁT CHƯƠNG 3: 1) Bài toán BÀI TOÁN VẬN TẢI Có m địa điểm A1,A2, , Am cùng sản xuất 1 loại hàng với các lượng hàng tương ứng là a1,a2, , am. Có n địa điểm tiêu thụ loại hàng trên là B1 ,B2 , , Bn với các yêu cầu tương ứng là b1 ,b2 , , bn. Ta gọi Ai là trạm phát thứ i, Bj là trạm thu thứ j. Ta có các giả thiết sau: Giải: * Hàng có thể chở từ trạm phát Ai bất kỳ đến trạm Gọi xij là số đơn vị hàng chuyên chở từ trạm thu Bj bất kỳ. phát (i) đến trạm thu (j). * Chi phí chuyên chở 1 đơn vị hàng từ trạm phát (i) * Điều kiện cho biến gọi: xij >=0 , i,j đến trạm thu (j) là c , c >=0 * Điều kiện để các trạm phát thì phát hết hàng: ij ij n * Tổng lượng hàng có ở m trạm phát (tổng phát)  x = ai : trạm phát (i) phát hết hàng j 1 ij = tổng lượng hàng yêu cầu ở n trạm thu (tổng thu): m n * Điều kiện để các trạm thu thì thu đủ hàng:  a =  b (đk cân bằng thu phát) m i 1 i j 1 j  x = bj : trạm thu (j) thu đủ hàng i 1 ij Hãy lập phương án vận chuyển hàng sao cho: các * Tổng chi phí vận chuyển là: trạm phát thì phát hết hàng, các trạm thu thì thu đủ n m m n f(X)=   c x   c x hàng và tổng chi phí vận chuyển là nhỏ nhất? j 11i ij ij i 11j ij ij 1
  2. ThS. Phạm Trí Cao * Chương 3 03/01/2014 Vậy mô hình bài toán vận tải là: 2) Bảng vận tải Ta ghi tất cả các tham số của bài toán vào Tìm ma trận X= (xij)m*n sao cho: n m bảng sau, gọi là bảng vận tải: f(X)= c x min (1) T B1 Bj Bn   ij ij j 11i F (b1) (bj) (bn) n A1 c11 c1j c1n x = a , i (2)  ij i (a1) x11 x1j x1j j 1 A c c c m i i1 ij in x = b , j (3) (ai) xi1 xij xin  ij j i 1 Am cm1 cmj cmn (am) xm1 xmj xmn xij >=0 , i,j (4) Ví dụ số:  Ta có mô hình bài toán là: Giả sử ta có 2 trạm phát và 3 trạm thu. Lượng  f(X)= 7x11 +3x12 +4x13 +x21 +2x22 +3x23 hàng có ở các trạm phát, lượng hàng yêu cầu ở min  x +x +x =60 các trạm thu, chi phí vận chuyển, và 1 pa vận 11 12 13  x21 +x22 +x23 =40 chuyển được cho trong bảng sau:  x11 +x21 =30 T B1 B2 B3  x12 +x22 =50 F ( 30) (50) (20)  x13 +x23 =20  xij >=0,i=1,2;j=1,3 A1 7 3 4 (60) [30] [20] [10] A2 1 2 3  Ta thấy bài toán vận tải là trường hợp (40) [30] [10] riêng của bài toán quy hoạch tuyến tính. 2
  3. ThS. Phạm Trí Cao * Chương 3 03/01/2014  II) CÁC KHÁI NIỆM VÀ ĐỊNH NGHĨA  1) Ô chọn và ô loại Ví dụ: Ô nằm ở vị trí: dòng i, cột j gọi là ô (i,j) Xét VD số ở trên: X=(x) là 1 pa của bài toán vận tải ij m*n 123 -Nếuxij > 0 thì ô (i,j) gọi là ô chọn (ô cơ sở) -Nếuxij = 0 thì ô (i,j) gọi là ô loại (ô phi cơ 1 sở) 2  Quy ước:  Ô chọn là ô có dấu * Ta chỉ xét những ô có dấu * (ô chọn). 2) Dây chuyền và vòng Dây chuyền là một dãy các ô liên tiếp nhau (có thể liền kề nhau hoặc không) thỏa: - Đi ngang thì chỉ lấy 2 ô. - Đi dọc thì chỉ lấy 2 ô. - Đi ngang, đi dọc xen kẽ nhau. Một dòng hoặc một cột mà dây chuyền đi qua: hoặc không lấy ô nào hết, hoặc chỉ lấy đúng 2 ô. 3
  4. ThS. Phạm Trí Cao * Chương 3 03/01/2014 Vòng là 1 dây chuyền khép kín, có ô bắt đầu trùng với ô kết thúc.  Chú ý:  Một dòng hoặc một cột mà vòng đi qua: nếu không lấy thì thôi, còn nếu lấy thì chỉ lấy đúng 2 ô.  Nhận xét:  - Số ô trên vòng luôn là một số chẳn >=4.  - Số ô tối đa không tạo thành vòng trên bảng có m dòng, n cột là m+n–1.  3) Phương án cực biên Ví dụ: Một pa mà các ô chọn không tạo thành 1 23 4 1 2 3 4 1 2 3 4 vòng gọi là pacb. 1 * * * 1 * 1 * * * Ta luôn có: pacb có số ô chọn tối đa là 2 * 2 * * 2 * m+n–1. 3 * * 3 * * 3 * * Một pacb có đủ m+n-1 ô chọn gọi là pacb H1 H2 H3 không suy biến, nếu có ít hơn m+n-1 ô chọn H1: pacb không suy biến vì không có vòng và số gọi là pacb suy biến. ô chọn = 6 = 3+4 1. Một pa mà các ô chọn tạo thành vòng gọi H2: pacb suy biến vì không có vòng và số ô là pa không cb. chọn = 5 < 6 = 3+4 1. H3: pa không cb vì có vòng (1,1) (1,4) (3,4) (3,1). 4
  5. ThS. Phạm Trí Cao * Chương 3 03/01/2014  Định lý (mối liên hệ giữa ô chọn và ô loại)  X là pacb không suy biến, có đủ m+n-1 ô chọn. Nếu ta bổ sung 1 ô loại bất kỳ vào bảng vận tải thì ô loại này sẽ tạo thành 1 vòng duy nhất với 1 số ô chọn đã có.  Chú ý:  Vòng này phải đi qua ô loại bổ sung vào, không nhất thiết phải đi qua tất cả các ô chọn. 5
  6. ThS. Phạm Trí Cao * Chương 3 03/01/2014  Định lý:  III) THUẬT TOÁN THẾ VỊ  X là pacb của bài toán vận tải, nếu X chưa  Ta đưa ra thuật toán thế vị cho bài toán cân bằng tối ưu thì luôn tìm được một pacb mới X’ tốt thu phát, minf.  1) Trường hợp bài toán có pacb không suy biến hơn X, nghĩa là: f(X’) =0 thì ta nói đã phân phối  Bài toán vận tải luôn có patư. cho ô (i,j) một lượng hàng là p.  Chứng minh:  - Nguyên tắc phân phối tối đa là nguyên tắc phân  Xem trong sách. phối cho ô (i,j) một lượng hàng lớn nhất có thể được, nghĩa là: xij =min{ai,bj}. Giải: Ví dụ 3.1: Bước 1: Bảng vận tải xuất phát F T 25 38 25 30 Ta có: TF = 30+50+38 = 118 = 25+38+25+30 = TT (BT cân bằng thu phát) 30 15 10 9 12 T 25 38 25 30 F 50 13 21 14 8 30 15 10 9 12 [5] [25] 38 10 11 16 12 50 13 21 14 8 [20] [30] Dùng phương pháp chi phí bé 38 10 11 16 12 [25] [13] nhất lập bảng vận tải xuất phát? 6
  7. ThS. Phạm Trí Cao * Chương 3 03/01/2014 Cách kiểm tra xem phân phối đúng không? Các ô chọn không tạo vòng. Số ô chọn 0 : pa đang xét chưa tối ưu.  ui +vj =cij , với mọi ô chọn (i,j) (*)  Chuyển sang bước 4.  Quy ước:  Chú ý:  Chọn u =0. 1  ij = 0 với ô (i,j) là ô chọn.  LƯU Ý:  Quá trình tìm hệ thống thế vị (ui,vj) chỉ được canh  Nhận xét: theo ô chọn.  Ô chọn ở chương 3 Biến cơ sở ở chương 1 7
  8. ThS. Phạm Trí Cao * Chương 3 03/01/2014  Bước 4: Cải tiến pa (tìm pacb mới tốt hơn)  4.3) Xác định lượng điều chỉnh q:  4.1) Tìm ô điều chỉnh:  Trên vòng điều chỉnh ta đánh dấu +, liên  Ô điều chỉnh là ô có dương lớn nhất. tiếp, với quy ước ô điều chỉnh được đánh dấu  rs=max{ ij/ ij>0} nên ô (r,s) là ô điều chỉnh. đầu tiên và mang dấu +.  Ô điều chỉnh sẽ là ô loại bổ sung vào trong bảng  Ta chỉ xét những ô nằm trên vòng điều chỉnh. vận tải mới.  Lượng điều chỉnh q là số xij nhỏ nhất trong  4.2) Tìm vòng điều chỉnh: Lập vòng điều chỉnh đi những ô mang dấu . Giả sử đó là ô (t,h). Ô qua ô điều chỉnh (r,s) và 1 số ô chọn đã có. (t,h) sẽ là ô bị loại ra trong bảng vận tải mới.  Lưu ý: Vòng điều chỉnh này tồn tại duy nhất, phải  đi qua ô điều chỉnh. q=min{xij / với mọi ô (i,j) mang dấu }=xt,h nên ô (t,h) sẽ bị loại ra trong bảng vận tải mới.  Vòng điều chỉnh không nhất thiết phải đi qua tất cả các ô chọn. Nhận xét: 4.4) Tìm pacb mới X’: Với pp đơn hình, qua mỗi bảng ta loại Pa X ứng với bảng vận tải cũ, pa X’ ứng với bảng ra 1 véc tơ và bổ sung vào 1 véc tơ vận tải mới. Và f(X’) <= f(X) Ta có: X’= (x’ ) mới. Với thuật toán thế vị, qua mỗi ij x + q , ô (i,j) mang dấu + bảng ta loại ra 1 ô và bổ sung vào 1 ô ij x’ij = xij – q , ô (i,j) mang dấu – mới. xij , ô (i,j) không mang dấu Lưu ý: Qua mỗi bảng, giá trị hàm mục tiêu giảm 1 lượng là q. rs : f(X’) = f(X) – q. rs Sau khi chuyển bảng xong, ta quay trở lại bước 2. 8
  9. ThS. Phạm Trí Cao * Chương 3 03/01/2014 Bước 4.4: Xác định pacb mới Bước 4: chuyển bảng Ta có pacb mới như sau: T 25 38 25 30 ui F T 25 38 25 30 ui 30 15 10 9 12 0 F 6 [5] [25] 8 30 15 10 9 12 0 50 13 21 14 8 4 6 [5] [25] 15 [20] 7 1 [30] 50 13 + 21 14 8 11 38 10 11 16 12 1 7 * [20] 6 [30] [5] [33] 6 7 38 10 11 + 16 12 1 vj 91094 [25] [13] 6 14 Ta có ij 0} nếu có nhiều ô để chọn thì ta làm thế nào? Ví dụ 3.2:  Qua mỗi bảng hàm mục tiêu giảm 1 lượng là q. rs T 30 35 25 10 , f(X’) = f(X)- q. rs .  Lưu ý: Trong quá trình tìm lượng điều chỉnh q, F nếu ta có q đạt tại nhiều ô mang dấu . 15 1325  Ví dụ q = min{x /vớimọiô(i,j)mangdấu }= ij 35 68110 xt,h =xe,f  Ta làm như thế nào? Có thể loại ra nhiều ô cùng 10 3265 lúc không? 40 3949  Xem chi tiết trong sách. 9
  10. ThS. Phạm Trí Cao * Chương 3 03/01/2014 Có thể loại ra 1 trong 2 ô (1,1), (4,2). Ta loại ra ô (1,1). T 30 35 25 10 ui T 30 35 25 10 ui F F 15 1 3 2 5 0 15 1 3 + 2 5 0 -4 [15] -6 -2 * [15] 4 -2 2 35 6 8 1 10 5 35 6 8 1 10 1 -4 [10] [25] -2 -4 [10] [25] -2 10 3 2 6 5 -1 10 3 2 6 5 -5 -7 [10] -11 -3 -7 [10] -11 -3 40 3 9 4 9 6 40 3 + 9 4 9 2 [30] [0] -2 [10] [15] [15] -2 [10] vj -3 3 -4 3 Ta có ij <=0,  i,j : pa đang xét là tối ưu. vj 17 07 fmin = f(X*) = 3(15) + 8(10) + . + 9(0) + 9(10) = 350 Ghi patư của VD3.2?  Ta không thể áp dụng thuật toán thế vị cho pacb suy biến. 2) Trường hợp bài toán có pacb suy biến  Cách giải quyết: Khi gặp pacb suy biến ta có 2 cách giải quyết sau: Ví dụ 3.3:  Cách 1: Thêm ô chọn đặc biệt T 60 70 40 30  Ta thêm các ô chọn đặc biệt (i,j) thỏa: F  -Cóxij =0 100 12 6 9 12  - Các ô chọn đặc biệt này không tạo thành vòng với các ô chọn đã có. 80 9 8 7 11  Lưu ý: Vậy ta thêm bao nhiêu ô chọn, và thêm 20 11 7 6 10 vào ở vị trí ô nào?  Ta thêm ô chọn đặc biệt là ô (3,2). 10
  11. ThS. Phạm Trí Cao * Chương 3 03/01/2014 Ta thêm ô chọn đặc biệt là ô (3,2). F \ T 60 70 40 30 ui F \ T 60 70 40 30 ui 100 12 6 9 12 0 100 12 6 + 9 12 0 2 [70] 1 [30] 5 [70] 4 [30] 80 9 8 7 11 1 80 9 8 7 11 2 [60] 3 [20] 0 [60] 0 [20] 3 20 11 7 6 10 2 20 11 7 6 10 + 1 3 3 [20] [0] 3 * [0] [20] 3 vj 10 6 8 12 vj 76 512 Ta có ij <= 0, i,j : pa đang xét tối ưu fmin = 70(6) + 30(12) + + 20(6) + 0(10) = 1580 Cách 2: Phân phối lại F \ T60 70 40 30 ui F \ T 60 70 40 30 ui 100 12 6 9 12 0 100 12 6 9 12 + 0 2 [70] 1 [30] * [30] [70] 1 2 80 9 8 7 11 1 80 9 + 8 7 11 -3 [60] -3 [20] [0] [30] -5 [20] [30] 20 11 7 6 10 2 20 11 7 6 10 4 -3 -3 [20] 0 v 10 6 8 12 -3 -5 [20] 0 j Ta có ij <= 0 ,  i, j: pa đang xét tối ưu vj 12 6 10 14 fmin = 70(6) + 30(12) + + 20(6) + 0(10) = 1580 11
  12. ThS. Phạm Trí Cao * Chương 3 03/01/2014 Lưu ý:  IV) BTVT KHÔNG CÂN BẰNG THU PHÁT  BTVT không cân bằng thu phát là BTVT có tổng Tùy theo cấu trúc của bài toán mà phát tổng thu. cách 1 hay cách 2 cho kết quả tốt hơn,  Thuật toán thế vị chỉ áp dụng cho bài toán vận ta không thể dự đoán trước được. tải CBTP, do đó ta phải chuyển bài toán Tùy thuộc vào “linh cảm” của bạn !!! KHÔNG CBTP về bài toán CBTP.  1) Tổng phát > tổng thu  * Đưa bài toán ban đầu (P) về bài toán CBTP (P*) bằng cách thêm cột trạm thu giả có yêu cầu = tổng phát tổng thu. Các ô nằm trên cột trạm thu giả gọi là các ô giả, các ô ban đầu gọi là các ô thực.  * Chi phí vận chuyển của các ô giả đều bằng 0. Ví dụ 3.4:  * Dùng thuật toán thế vị giải bài toán (P*). Trong patư của (P*), ta bỏ đi cột trạm thu giả thì được F \ T 120 130 50 patư của (P). 100 10 8 12  Chú ý: 150 15 10 14  Khi tìm pacb xuất phát, ta ưu tiên phân phối cho 80 9 11 12 các ô thực trước, khi xét hết ô thực rồi thì mới xét đến các ô giả. HD:  Nhận xét: Tổng phát = 330 > 300 = tổng thu thêm cột  Ô giả ở chương 3 Biến phụ ở chương 1 trạm thu giả thứ 4 có yêu cầu = 330 - 300 = 30 12
  13. ThS. Phạm Trí Cao * Chương 3 03/01/2014 Phương pháp chi phí bé nhất Bảng vận tải mới F \ T 120 130 50 (30) ui F \ T 120 130 50 (30) ui 100 10 8 12 0 0 100 10 + 8 12 0 0 [40] [60] 0 2 3 [100] 0 2 150 15 10 14 0 2 3 [70] [50] [30] 150 15 10 + 14 0 2 80 9 11 12 0 1 * [40] [30] [50] [30] [80] 4 1 3 80 9 11 12 0 4 vj 10 8 12 2 [80] 7 4 6 Ta có ij <=0, i,j : pa đang xét tối ưu fmin = 3000 vj 13 8 12 2 Ghi patư của bài toán?  2) Tổng phát < tổng thu Ví dụ 3.6:  * Đưa bài toán ban đầu (P) về bài toán CBTP F \ T15253027 (P*) bằng cách thêm dòng trạm phát giả có 35 5 1 4 2 lượng hàng = tổng thu tổng phát. 203478  Các ô nằm trên dòng trạm phát giả gọi là 172693 các ô giả, các ô ban đầu gọi là các ô thực. HD:  * Chi phí vận chuyển của các ô giả đều bằng 0. tổng phát = 35+20+17 = 72 < tổng thu  * Dùng thuật toán thế vị giải bài toán (P*). = 15+25+30+27 = 97 Trong patư của (P*), ta bỏ đi dòng trạm phát Thêm dòng trạm phát giả thứ 4 giả thì được patư của (P). có lượng hàng = 97-72 = 25 13
  14. ThS. Phạm Trí Cao * Chương 3 03/01/2014 Phương pháp chi phí bé nhất F \ T15253027ui F \ T 15 25 30 27 ui 35 5 1 4 + 2 0 35 5 1 4 2 0 -4 [25] 1 [10] -4 [25] -2 [10] 20 3 + 4 7 8 2 20 3 + 4 7 8 5 [15] -1 [5] -4 3 2 [20] -1 17 2 6 9 3 + 1 17 2 6 9 3 + 1 * [0] -4 -3 [17] [15] -4 -6 [2] (25) 0 0 0 0 -5 (25) 0 0 0 + 0 -2 -1 -1 [10] * [15] -4 -4 [25] 3 v 1152 vj 11 2 2 j Ô điều chỉnh (2,1) Ô điều chỉnh là (1,3) F \ T 15 25 30 27 ui  V) BTVT CÓ Ô CẤM 35 5 1 4 2 0  1) Cấm tuyến đường vận chuyển -5 [25] [0] [10]  Các bài toán vận tải ta đã xét, giả thiết hàng có thể 20 3 4 7 8 3 chở từ trạm phát bất kỳ đến trạm thu bất kỳ. [15] 0 [5] -3  Trong thực tế đôi khi ta không thể vận chuyển hàng 17 2 6 9 3 1 trên 1 số tuyến đường vì nhiều lý do. -1 -4 -4 [17]  Ta không thể vận chuyển hàng từ A đến B tương (25) 0 0 0 0 -4 i j ứng với ô (i,j) nên ô này không thể phân phối hàng -4 -3 [25] -2 vào được, do đó nó sẽ là ô cấm. vj 01 42  Lập bài toán (M) với các ô cấm có chi phí vận Ta có ij 0 (rất lớn). fmin = 176 Ghi patư của bài toán?  Dùng t/toán thế vị giải bt (M), có patư là X*(M). 14
  15. ThS. Phạm Trí Cao * Chương 3 03/01/2014  Định lý: Nếu trong X*(M) có các thành phần ứng với ô Ví dụ 3.8: cấm đều bằng 0 thì bài toán ban đầu (P) có patư. Bài toán (P) Patư chính là X*(M). Nếu trong X*(M) có thành phần ứng với ô cấm F \ T25382530 khác 0 thì (P) không có patư. 30 15 10 9 12  Nhận xét: 50 13 21 14 8  Ô cấm ở chương 3 Biến giả ở chương 1 38 10 11 16 12  Lưu ý:  Ta phân phối cho ô thực trước, ô cấm sau. Cấm các tuyến đường A2 B2, A3 B3 Phương pháp chi phí bé nhất F \ T25 38 25 30 ui 30 15 10 9 12 0 F \ T 25 38 25 30 ui 6 [5] [25] 8 30 15 10 9 12 0 50 13 M 14 8 4 6 [5] [25] M+6 [20] 14 M 1 [30] 50 13 + M 14 8 M 10 38 10 11 M 12 1 M 14 * [20] M 15 [30] [5] [33] 10 M 7 38 10 11 + M 12 1 vj 91094 [25] [13] 10 M M+7 Ta có ij <=0,  i,j : pa đang xét là tối ưu fmin = f(X*(M)) = 10(5)+ 9(25)+ +10(5)+11(33) = 1188 vj 9 10 9 M+18 Kết luận? 15
  16. ThS. Phạm Trí Cao * Chương 3 03/01/2014 Ví dụ 3.10: HD: Bài toán (M) Bài toán (P) F \ T25401550ui F \ T 25 40 15 50 50 8 + M 4 M 0 50 8 3 4 7 M-10 [10] [15] [25] 50 1 7 5 3 50 1 7 5 3 + 3-M * [25] -4 -M+2 [25] 30 2 2 6 4 30 2 2 6 4 2-M -2 [30] -M -2 vj M-2 M 4 M Cấm tuyến A1 B2, A1 B4 F \ T 25 40 15 50 ui  2) Cấm không cho phát hàng vào ô giả 50 8 M 4 M 0  Bài toán có ô cấm còn xuất hiện trong trường hợp [25] [10] [15] [0] bài toán không CBTP: 50 1 7 5 3 3-M Tổng phát > tổng thu: -M+10 -4 -M+2 [50]  Thêm điều kiện là một trạm phát nào đó phải phát hết hàng. 30 2 2 6 4 2-M  Cách làm: -M+8 [30] -M -2  Ô nằm ở vị trí: dòng trạm phát phải phát hết v 8M 4 M j hàng, cột trạm thu giả là ô cấm. Ta có <=0, i,j : pa đang xét tối ưu ij  Lưu ý: Ta có x = 10 0 (ô cấm) nên bài toán (P) 12  Trình tự phân phối các ô: ô thực, ô giả, ô cấm. không có patư. 16
  17. ThS. Phạm Trí Cao * Chương 3 03/01/2014 Ví dụ 3.11: HD: Cách 1: F \ T 120 130 50 F \ T 120 130 50 (30) ui 100 10 8 12 100 10 8 12 0 + 0 3 [100] 0 M 2 150 15 10 14 150 15 10 + 14 M 2 80 9 11 12 [40] [30] [50] * [30] 80 9 11 12 0 4 [80] 7 4 M 6 vj 13 8 12 M 2 Trạm A2 phát hết hàng. F \ T 120 130 50 (30) ui F \ T 120 130 50 (30) ui 100 10 8 12 0 0 100 10 + 8 12 0 0 [40] [30] 0 [30] 3 [70] 0 [30] 150 15 10 14 M 2 150 15 10 + 14 M 2 3 [100] [50] 2 M 80 9 11 12 0 1 * [40] [60] [50] 2 M [80] 4 1 1 80 9 11 12 0 4 vj 10 8 12 0 [80] 7 4 4 Ta có ij <=0, i,j : pa đang xét tối ưu fmin = 3060 vj 13 8 12 0 Cách 2: Lợi dụng patư của VD3.4 : xem trong sách. 17
  18. ThS. Phạm Trí Cao * Chương 3 03/01/2014 Tổng phát < tổng thu: Ví dụ 3.12:  Thêm điều kiện là một trạm thu nào đó Bài toán (P) yêu cầu phải thu đủ hàng.  Cách làm: F \ T606080100  Ô nằm ở vị trí: dòng trạm phát giả, cột 80 1 7 6 8 trạm thu phải thu đủ hàng là ô cấm. 605465 110 6 3 2 9  Lưu ý:  Trình tự phân phối các ô: ô thực, ô giả, ô cấm. Trạm thu B4 phải thu đủ hàng. HD: F \ T 60 60 80 100 u Cách 1: Tổng phát= 200 < tổng thu= 230 i Bài toán (M) tương ứng 80 1 7 6 8 0 F \ T 60 60 80 100 ui [60] -M+1 -M+1 [20] 80 1 7 6 8 0 60 5 4 6 5 -3 [60] 0 0 [20] -7 -M+1 -M-2 [60] 60 5 4 6 5 + -3 -7 * [30] -3 [30] 110 6 3 2 9 + M-5 110 6 3 2 9 -4 M-10 [30] [80] M-6 -9 [30] [80] -5 (50) 0 0 + 0 M M-8 (50) 0 0 + 0 M M-8 M-7 [30] -1 * [20] M-7 M-1 M-2 [50] vj 1 -M+8 -M+7 8 vj 17 6 8 18
  19. ThS. Phạm Trí Cao * Chương 3 03/01/2014 F T 60 60 80 100 ui Ví dụ 3.13: 80 1 7 6 8 0 Bài toán (P) [60] -5 -5 [20] F \ T 60 60 80 100 60 5 4 6 5 -3 801768 -7 -5 -8 [60] 605465 110 6 3 2 9 1 1106329 -4 [10] [80] [20] (50) 0 0 0 M -2 -1 [50] -1 -M+6 Cấm tuyến đường A3 B2. vj 1 2 1 8 Trạm thu B4 phải thu đủ hàng. Ta có ij =0 ,  i,j:pađangxétlàpatư.  Qua cách giải gián tiếp, ta thấy chỉ có những gì  Xong thuật toán. liên quan đến cij mới bị đổi dấu, còn liên quan  *Có <0 : pa đang xét chưa tối ưu. đến x ,a,b không bị thay đổi. ij ij i j  Sang B4. 19
  20. ThS. Phạm Trí Cao * Chương 3 03/01/2014  B4) Chuyển sang bảng vận tải mới: Ví dụ 3.14:  * Ô điều chỉnh là ô có âm nhỏ nhất.  rs =min{ ij / ij = 0, i,j : pa đang xét tối ưu vj 30 24 14 25 fmax = f(X*) = 2575 . Ghi patư của bài toán? 20
  21. ThS. Phạm Trí Cao * Chương 3 03/01/2014 Ví dụ 3.15: HD: Ô cấm (3,3) có lợi nhuận là –M với M>0 (rất lớn) F \ T 35 30 55 F \ T 35 30 55 ui 30 10 9 8 30 10 9 8 + 0 [30] 0 -M-3 50 7 6 7 50 7 6 7 M+2 40 5 4 3 M+5 M+5 [50] 40 5 + 4 M -5 f max [5] [30] * [5] Cấm tuyến A B vj 10 9 -M+5 3 3 F \ T 35 30 55 ui  Quy ước: 30 10 9 8 0  Nếu trong đề thi không nói gì về f thì có [25] 0 [5] nghĩa là f min. 50 7 6 7 -1 2 2 [50] 40 5 4 M -5  Còn nếu muốn f max thì sẽ nói rõ trong [10] [30] M+3 đề. vj 10 9 8 Ta có ij >= 0, i,j : pa đang xét tối ưu fmax = f(X) = 1020 Ghi patư của bài toán. 21
  22. ThS. Phạm Trí Cao * Chương 3 03/01/2014 VII) VẤN ĐỀ VỀ PATƯ DUY NHẤT  B2) Nếu có ij = 0 ứng với ô loại (i,j) : Bài toán có thể có patư khác. Định lý:  Cách xác định xem có patư khác hay không: 1 2 k Bài toán có các pacbtư là X , X , , X thì patư tổng  * Lấy ô loại (i,j) có ij = 0 làm ô điều chỉnh. k i k  * Xác định vòng điều chỉnh. quát có dạng X=  X , với  1, 0 0 : Bài toán có patư không Ta có các kết quả sau: duy nhất. Xét bảng vận tải tối ưu.  Lưu ý: B1) Nếu ij 0 với mọi ô loại (i,j) : Bài toán có patư  Phân biệt pacb và pacbtư, phân biệt patư và pacbtư. duy nhất.  Ví dụ 3.16: Ví dụ 3.17 : Xem lại VD 3.3, cách 1.  Bài toán minf : Ở bảng tối ưu ta có: Ô loại (2,4) có = 0, lấy ô loại này làm ô điều chỉnh.  VD 3.1, 3.2, 3.7, 3.8, 3.9, 3.10, 3.12 có ij 0 với mọi ô loại (i,j) : bài toán 20 11 7 6 + 10 2 có patư duy nhất. 3 3 [20] * [0]  Trong trường hợp này: pacbtư duy nhất, patư vj 10 6 8 12 duy nhất. Ta có q= 0 nên bài toán có patư duy nhất. Trong trường hợp này: pacbtư duy nhất, patư duy nhất. 22
  23. ThS. Phạm Trí Cao * Chương 3 03/01/2014 Ví dụ 3.18: Xem lại VD 3.4. 40 60 0 Bảng tối ưu: F \ T 120 130 50 (30) u i X1 0 70 50 100 10 8 12 + 0 0 [40] [60] 0 2 80 0 0 150 15 10 + 14 0 2 3 [70] * [50] [30] fmin = 3000 80 9 11 12 0 1 Ở bảng 1: Ta có ô loại (1,3) có =0 nên lấy làm [80] 4 1 3 ô điều chỉnh. Tìm vòng điều chỉnh. Lượng điều vj 10 8 12 2B1 Ta có ij 0 nên bài toán có patư khác. Từ bảng 1 ta được bảng 2. 40 10 50 X 2 0 120 0 F \ T 120 130 50 (30) ui 80 0 0 100 10 8 + 12 0 0 [40] [10] * [50] -2 Ở bảng 2: Ta có ô loại (2,3) có =0 nên lấy làm ô 150 15 10 14 + 0 2 điều chỉnh. Biến đổi từ bảng 2 ta quay về bảng 1. Vậy bài toán có 2 pacbtư là X1 và X2. -3 [120] 0 [30] Patư tổng quát có dạng: 80 9 11 12 0 -1 X= X1 + (1- )X2 với 0 <= <= 1 [80] -4 -1 -3 Trong trường hợp này: pacbtư không duy nhất, vj 10 8 12 -2 B2 patư không duy nhất. 23
  24. ThS. Phạm Trí Cao * Chương 3 03/01/2014 Ví dụ 3.19: 0 25 25 Xem lại VD 3.5 F \ T 50 100 50 (20) ui X1 0 75 0 50 5 6 6 + 0 0 -2 [25] [25] -3 50 0 25 75 7 8 9 0 2 -2 [75] -1 -1 Ở bảng 1: ô điều chỉnh là (3,2). 95 6 9 + 9 0 3 [50] 0 [25] [20] Nếu loại ra ô (1,2), từ bảng 1 ta được bảng 2. vj 3 6 6 -3 B1 Nếu loại ra ô (3,3), từ bảng 1 ta được bảng 3. F \ T 50 100 50 (20) ui 0 0 50 50 5 6 + 6 0 0 X 2 0 75 0 -2 0 [50] -3 50 25 0 75 7 8 9 0 2 -2 [75] -1 -1 Ở bảng 2: lấy ô (1,2) làm ô điều chỉnh, 95 6 9 9 + 0 3 biến đổi từ bảng 2 quay về bảng 1. [50] * [25] [0] [20] Ở bảng 3: lấy ô (3,3) làm ô điều chỉnh, vj 3 6 6 -3 B2 biến đổi từ bảng 3 quay về bảng 1. 24
  25. ThS. Phạm Trí Cao * Chương 3 03/01/2014 F \ T 50 100 50 (20) u i Mời ghé thăm trang web: 50 5 6 + 6 0 0 98 -2 [0] [50] -3  75 7 8 9 0 2  -2 [75] -1 -1 95 6 9 9 + 0 3 [50] * [25] 0 [20] vj 36 6-3B3 Ta có X3 = X2 Trong trường hợp này: pacbtư không duy nhất, patư không duy nhất. 25