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

ThS. Phạm Trí Cao * Chương 3 03/01/2014 1 CHƯƠNG 3: BÀI TOÁN VẬN TẢI I) BÀI TOÁN VẬN TẢI CÂN BẰNG THU PHÁT 1) Bài toán 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: * Hàng có thể chở từ trạm phát Ai bất kỳ đến trạm thu Bj bất kỳ. * Chi phí chuyên chở 1 đơn vị hàng từ trạm phát (i) đến trạm thu (j) là cij , cij >=0 * Tổng lượng hàng có ở m trạm phát (tổng phát) = tổng lượng hàng yêu cầu ở n trạm thu (tổng thu):  m i i a 1 =  n j j b 1 (đk cân bằng thu phát) Hãy lập phương án vận chuyển hàng sao cho: các trạm phát thì phát hết hàng, các trạm thu thì thu đủ hàng và tổng chi phí vận chuyển là nhỏ nhất? Giải: Gọi xij là số đơn vị hàng chuyên chở từ trạm phát (i) đến trạm thu (j). * Điều kiện cho biến gọi: xij >=0 , i,j * Điều kiện để các trạm phát thì phát hết hàng:  n j ij x 1 = ai : trạm phát (i) phát hết hàng * Điều kiện để các trạm thu thì thu đủ hàng:  m i ij x 1 = bj : trạm thu (j) thu đủ hàng * Tổng chi phí vận chuyển là: f(X)=     m i n j ij xijc n j m i ij xijc 1 11 1 ThS. Phạm Trí Cao * Chương 3 03/01/2014 2 Vậy mô hình bài toán vận tải là: Tìm ma trận X= (xij)m*n sao cho: f(X)=   n j m i ij xijc1 1  min (1)  n j ij x 1 = ai , i (2)  m i ij x 1 = bj , j (3) xij >=0 , i,j (4) 2) Bảng vận tải Ta ghi tất cả các tham số của bài toán vào bảng sau, gọi là bảng vận tải: T F B1 (b1) Bj (bj) Bn (bn) A1 (a1) c11 x11 c1j x1j c1n x1j Ai (ai) ci1 xi1 cij xij cin xin Am (am) cm1 xm1 cmj xmj cmn xmn Ví dụ số: Giả sử ta có 2 trạm phát và 3 trạm thu. Lượng hàng có ở các trạm phát, lượng hàng yêu cầu ở các trạm thu, chi phí vận chuyển, và 1 pa vận chuyển được cho trong bảng sau: T F B1 ( 30) B2 (50) B3 (20) A1 (60) 7 [30] 3 [20] 4 [10] A2 (40) 1 2 [30] 3 [10] Ta có mô hình bài toán là:  f(X)= 7x11 + 3x12 + 4x13 + x21 + 2x22 + 3x23 min  x11 + x12 + x13 = 60  x21 + x22 + x23 = 40 x11 + x21 = 30 x12 + x22 = 50  x13 + x23 = 20 xij >=0, i= 1,2 ; j= 1,3  Ta thấy bài toán vận tải là trường hợp riêng của bài toán quy hoạch tuyến tính. ThS. Phạm Trí Cao * Chương 3 03/01/2014 3  II) CÁC KHÁI NIỆM VÀ ĐỊNH NGHĨA 1) Ô chọn và ô loại  Ô nằm ở vị trí: dòng i, cột j gọi là ô (i,j)  X = (xij)m*n là 1 pa của bài toán vận tải - Nếu xij > 0 thì ô (i,j) gọi là ô chọn (ô cơ sở) - Nếu xij = 0 thì ô (i,j) gọi là ô loại (ô phi cơ sở) Quy ước: Ô chọn là ô có dấu * Ví dụ: Xét VD số ở trên: 1 2 3 1 * * * 2 * * 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 ô. ThS. Phạm Trí Cao * Chương 3 03/01/2014 4  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  Một pa mà các ô chọn không tạo thành vòng gọi là pacb.  Ta luôn có: pacb có số ô chọn tối đa là m+n–1.  Một pacb có đủ m+n-1 ô chọn gọi là pacb không suy biến, nếu có ít hơn m+n-1 ô chọn gọi là pacb suy biến.  Một pa mà các ô chọn tạo thành vòng gọi là pa không cb. Ví dụ: 1 2 3 4 1 2 3 4 1 2 3 4 1 * * * 1 * 1 * * * 2 * 2 * * 2 * 3 * * 3 * * 3 * * H1 H2 H3 H1: pacb không suy biến vì không có vòng và số ô chọn = 6 = 3+41. H2: pacb suy biến vì không có vòng và số ô chọn = 5 < 6 = 3+41. H3: pa không cb vì có vòng (1,1) (1,4) (3,4) (3,1). ThS. Phạm Trí Cao * Chương 3 03/01/2014 5 Đị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. ThS. Phạm Trí Cao * Chương 3 03/01/2014 6 Định lý: X là pacb của bài toán vận tải, nếu X chưa tối ưu thì luôn tìm được một pacb mới X’ tốt hơn X, nghĩa là: f(X’) <= f(X) Định lý (sự tồn tại patư của bài toán vận tải): Bài toán vận tải luôn có patư. Chứng minh: Xem trong sách.  III) THUẬT TOÁN THẾ VỊ  Ta đưa ra thuật toán thế vị cho bài toán cân bằng thu phát, minf.  1) Trường hợp bài toán có pacb không suy biến  Thuật toán gồm 4 bước như sau:  Bước1: Tìm pacb xuất phát (bảng vt xuất phát) Quy ước:  - Nếu ô (i,j) có xij = p >=0 thì ta nói đã phân phối cho ô (i,j) một lượng hàng là p.  - Nguyên tắc phân phối tối đa là nguyên tắc phân 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}. Ví dụ 3.1: F T 25 38 25 30 30 15 10 9 12 50 13 21 14 8 38 10 11 16 12 Dùng phương pháp chi phí bé nhất lập bảng vận tải xuất phát? Giải: Bước 1: Bảng vận tải xuất phát Ta có: TF = 30+50+38 = 118 = 25+38+25+30 = TT (BT cân bằng thu phát) T F 25 38 25 30 30 15 10 [5] 9 [25] 12 50 13 21 [20] 14 8 [30] 38 10 [25] 11 [13] 16 12 ThS. Phạm Trí Cao * Chương 3 03/01/2014 7 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 <= m+n-1.  Tổng các số của ô chọn trên dòng i = ai (VD dòng 1: 5 + 25 = 30)  Tổng các số của ô chọn trên cột j = bj (VD cột 2: 5 + 20 + 13 = 38) CHÚ Ý: TA CÓ 5 CÁCH PHÂN PHỐI, NGƯỜI TA HỔNG CẦN BIẾT BẠN PHÂN PHỐI THEO CÁCH NÀO, MIỄN SAO KẾT QUẢ THU ĐƯỢC LÀ PACB.  BƯỚC 2: TÌM HỆ THỐNG THẾ VỊ (ui ,vj):  ui gọi là thế vị dòng  vj gọi là thế vị cột  Ta xây dựng hệ thống thế vị (ui,vj) theo công thức:  ui + vj = cij , với mọi ô chọn (i,j) (*) Quy ước:  Chọn u1 = 0.  LƯU Ý: Quá trình tìm hệ thống thế vị (ui,vj) chỉ được canh theo ô chọn.  BƯỚC 3: KIỂM TRA DẤU HIỆU TỐI ƯU  Tính ij = ui + vj - cij : lượng kiểm tra của ô (i,j)  * Nếu ij <=0, i,j : pa đang xét là patư.  Thuật toán kết thúc.  * Nếu có ij >0 : pa đang xét chưa tối ưu.  Chuyển sang bước 4.  Chú ý:  ij = 0 với ô (i,j) là ô chọn.  Nhận xét: Ô chọn ở chương 3 Biến cơ sở ở chương 1 ThS. Phạm Trí Cao * Chương 3 03/01/2014 8  Bước 4: Cải tiến pa (tìm pacb mới tốt hơn)  4.1) Tìm ô điều chỉnh: Ô điều chỉnh là ô có  dương lớn nhất.  rs= max{ij/ij>0} nên ô (r,s) là ô điều chỉnh. Ô điều chỉnh sẽ là ô loại bổ sung vào trong bảng vận tải mới.  4.2) Tìm vòng điều chỉnh: Lập vòng điều chỉnh đi qua ô điều chỉnh (r,s) và 1 số ô chọn đã có.  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. Vòng điều chỉnh không nhất thiết phải đi qua tất cả các ô chọn.  4.3) Xác định lượng điều chỉnh q: Trên vòng điều chỉnh ta đánh dấu +,  liên tiếp, với quy ước ô điều chỉnh được đánh dấu đầu tiên và mang dấu +. Ta chỉ xét những ô nằm trên vòng điều chỉnh. Lượng điều chỉnh q là số xij nhỏ nhất trong những ô mang dấu  . Giả sử đó là ô (t,h). Ô (t,h) sẽ là ô bị loại ra trong bảng vận tải mới.  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. Nhận xét: Với pp đơn hình, qua mỗi bảng ta loại ra 1 véc tơ và bổ sung vào 1 véc tơ mới. Với thuật toán thế vị, qua mỗi bảng ta loại ra 1 ô và bổ sung vào 1 ô mới. 4.4) Tìm pacb mới X’: Pa X ứng với bảng vận tải cũ, pa X’ ứng với bảng vận tải mới. Và f(X’) <= f(X) Ta có: X’= (x’ij) xij + q , ô (i,j) mang dấu + x’ij = xij – q , ô (i,j) mang dấu – 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. ThS. Phạm Trí Cao * Chương 3 03/01/2014 9 Bước 4.4: Xác định pacb mới Ta có pacb mới như sau: T F 25 38 25 30 ui 30 15 6 10 [5] 9 [25] 12 15 0 50 13 + 7 21  * [20] 14 6 8 [30] 11 38 10  [25] 11 + [13] 16 6 12 14 1 vj 9 10 9 3 Bước 4: chuyển bảng T F 25 38 25 30 ui 30 15 6 10 [5] 9 [25] 12 8 0 50 13 [20] 21 7 14 1 8 [30] 4 38 10 [5] 11 [33] 16 6 12 7 1 vj 9 10 9 4 Ta có ij <=0,  i,j : pa đang xét là tối ưu. fmin = f(X*) = 10(5) + 9(25) + 13(20) + 8(30) + 10(5) + 11(33) = 1188  Chú ý: Khi xác định ô điều chỉnh theo công thức rs = max{ij / ij >0} nếu có nhiều ô để chọn thì ta làm thế nào? Qua mỗi bảng hàm mục tiêu giảm 1 lượng là q.rs , f(X’) = f(X)- q.rs .  Lưu ý: Trong quá trình tìm lượng điều chỉnh q, nếu ta có q đạt tại nhiều ô mang dấu  . Ví dụ q = min{xij / với mọi ô (i,j) mang dấu } = xt,h = xe,f  Ta làm như thế nào? Có thể loại ra nhiều ô cùng lúc không? Xem chi tiết trong sách. Ghi patư cho VD3.1? Ví dụ 3.2: T F 30 35 25 10 15 1 3 2 5 35 6 8 1 10 10 3 2 6 5 40 3 9 4 9 ThS. Phạm Trí Cao * Chương 3 03/01/2014 10 Có thể loại ra 1 trong 2 ô (1,1), (4,2). Ta loại ra ô (1,1). T F 30 35 25 10 ui 15 1  * [15] 3 + 4 2 -2 5 2 0 35 6 -4 8 [10] 1 [25] 10 -2 1 10 3 -7 2 [10] 6 -11 5 -3 -5 40 3 + [15] 9  [15] 4 -2 9 [10] 2 vj 1 7 0 7 T F 30 35 25 10 ui 15 1 -4 3 [15] 2 -6 5 -2 0 35 6 -4 8 [10] 1 [25] 10 -2 5 10 3 -7 2 [10] 6 -11 5 -3 -1 40 3 [30] 9 [0] 4 -2 9 [10] 6 vj -3 3 -4 3 Ta có ij <=0,  i,j : pa đang xét là tối ưu. fmin = f(X*) = 3(15) + 8(10) + . + 9(0) + 9(10) = 350 Ghi patư của VD3.2? 2) Trường hợp bài toán có pacb suy biến Ví dụ 3.3: T F 60 70 40 30 100 12 6 9 12 80 9 8 7 11 20 11 7 6 10  Ta không thể áp dụng thuật toán thế vị cho 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:  Cách 1: Thêm ô chọn đặc biệt  Ta thêm các ô chọn đặc biệt (i,j) thỏa:  - Có xij = 0  - Các ô chọn đặc biệt này không tạo thành vòng với các ô chọn đã có.  Lưu ý: Vậy ta thêm bao nhiêu ô chọn, và thêm vào ở vị trí ô nào?  Ta thêm ô chọn đặc biệt là ô (3,2). ThS. Phạm Trí Cao * Chương 3 03/01/2014 11 Ta thêm ô chọn đặc biệt là ô (3,2). F \ T 60 70 40 30 ui 100 12 5 6 + [70] 9 4 12  [30] 0 80 9 [60] 8 0 7 [20] 11 3 2 20 11 3 7  * [0] 6 [20] 10 + 3 1 vj 7 6 5 12 F \ T 60 70 40 30 ui 100 12 2 6 [70] 9 1 12 [30] 0 80 9 [60] 8 3 7 [20] 11 0 1 20 11 3 7 3 6 [20] 10 [0] 2 vj 10 6 8 12 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 \ T 60 70 40 30 ui 100 12  * [30] 6 [70] 9 1 12 + 2 0 80 9 + [30] 8 -5 7 [20] 11  [30] -3 20 11 -3 7 -5 6 [20] 10 0 4 vj 12 6 10 14 F \ T 60 70 40 30 ui 100 12 2 6 [70] 9 1 12 [30] 0 80 9 [60] 8 -3 7 [20] 11 [0] 1 20 11 -3 7 -3 6 [20] 10 0 2 vj 10 6 8 12 Ta có ij <= 0 ,  i, j: pa đang xét tối ưu fmin = 70(6) + 30(12) + + 20(6) + 0(10) = 1580 ThS. Phạm Trí Cao * Chương 3 03/01/2014 12 Lưu ý: Tùy theo cấu trúc của bài toán mà cách 1 hay cách 2 cho kết quả tốt hơn, ta không thể dự đoán trước được. Tùy thuộc vào “linh cảm” của bạn !!!  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 phát  tổng thu.  Thuật toán thế vị chỉ áp dụng cho bài toán vận tải CBTP, do đó ta phải chuyển bài toá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.  * 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 patư của (P).  Chú ý: Khi tìm pacb xuất phát, ta ưu tiên phân phối cho các ô thực trước, khi xét hết ô thực rồi thì mới xét đến các ô giả.  Nhận xét: Ô giả ở chương 3 Biến phụ ở chương 1 Ví dụ 3.4: F \ T 120 130 50 100 10 8 12 150 15 10 14 80 9 11 12 HD: Tổng phát = 330 > 300 = tổng thu  thêm cột trạm thu giả thứ 4 có yêu cầu = 330 - 300 = 30 ThS. Phạm Trí Cao * Chương 3 03/01/2014 13 Phương pháp chi phí bé nhất F \ T 120 130 50 (30) ui 100 10 + 3 8  [100] 12 0 0 2 0 150 15  * [40] 10 + [30] 14 [50] 0 [30] 2 80 9 [80] 11 7 12 4 0 6 4 vj 13 8 12 2 Bảng vận tải mới F \ T 120 130 50 (30) ui 100 10 [40] 8 [60] 12 0 0 2 0 150 15 3 10 [70] 14 [50] 0 [30] 2 80 9 [80] 11 4 12 1 0 3 1 vj 10 8 12 2 Ta có ij <=0, i,j : pa đang xét tối ưu fmin = 3000 Ghi patư của bài toán?  2) 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 dòng trạm phát giả có lượng hàng = tổng thu  tổng phát.  Các ô nằm trên dòng trạm phát 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.  * Dùng thuật toán thế vị giải bài toán (P*). Trong patư của (P*), ta bỏ đi dòng trạm phát giả thì được patư của (P). Ví dụ 3.6: F \ T 15 25 30 27 35 5 1 4 2 20 3 4 7 8 17 2 6 9 3 HD: tổng phát = 35+20+17 = 72 < tổng thu = 15+25+30+27 = 97 Thêm dòng trạm phát giả thứ 4 có lượng hàng = 97-72 = 25 ThS. Phạm Trí Cao * Chương 3 03/01/2014 14 Phương pháp chi phí bé nhất F \ T 15 25 30 27 ui 35 5 -4 1 [25] 4 -2 2 [10] 0 20 3 + 3 4 2 7  [20] 8 -1 5 17 2  [15] 6 -4 9 -6 3 + [2] 1 (25) 0 -1 0 -1 0 + [10] 0  * [15] -2 vj 1 1 2 2 Ô điều chỉnh (2,1) F \ T 15 25 30 27 ui 35 5 -4 1 [25] 4 + 1 2  [10] 0 20 3 + [15] 4 -1 7  [5] 8 -4 2 17 2  * [0] 6 -4 9 -3 3 + [17] 1 (25) 0 -4 0 -4 0 [25] 0 3 -5 vj 1 1 5 2 Ô điều chỉnh là (1,3) F \ T 15 25 30 27 ui 35 5 -5 1 [25] 4 [0] 2 [10] 0 20 3 [15] 4 0 7 [5] 8 -3 3 17 2 -1 6 -4 9 -4 3 [17] 1 (25) 0 -4 0 -3 0 [25] 0 -2 -4 vj 0 1 4 2 Ta có ij <=0,  i, j : pa đang xét tối ưu. fmin = 176 Ghi patư của bài toán?  V) BTVT CÓ Ô CẤM  1) Cấm tuyến đường vận chuyển  Các bài toán vận tải ta đã xét, giả thiết hàng có thể chở từ trạm phát bất kỳ đến trạm thu bất kỳ.  Trong thực tế đôi khi ta không thể vận chuyển hàng trên 1 số tuyến đường vì nhiều lý do.  Ta không thể vận chuyển hàng từ Ai đến Bj tương ứng với ô (i,j) nên ô này không thể phân phối hàng vào được, do đó nó sẽ là ô cấm.  Lập bài toán (M) với các ô cấm có chi phí vận chuyển = M >0 (rất lớn).  Dùng t/toán thế vị giải bt (M), có patư là X*(M). ThS. Phạm Trí Cao * Chương 3 03/01/2014 15 Định lý:  Nếu trong X*(M) có các thành phần ứng với ô cấm đều bằng 0 thì bài toán ban đầu (P) có patư. Patư chính là X*(M).  Nếu trong X*(M) có thành phần ứng với ô cấm khác 0 thì (P) không có patư.  Nhận xét: Ô cấm ở chương 3 Biến giả ở chương 1  Lưu ý:  Ta phân phối cho ô thực trước, ô cấm sau. Ví dụ 3.8: Bài toán (P) F \ T 25 38 25 30 30 15 10 9 12 50 13 21 14 8 38 10 11 16 12 Cấm các tuyến đường A2  B2, A3 B3 Phương pháp chi phí bé nhất F \ T 25 38 25 30 ui 30 15 6 10 [5] 9 [25] 12 M+6 0 50 13 + M14 M  * [20] 14 M15 8 [30] M10 38 10  [25] 11 + [13] M 10M 12 M+7 1 vj 9 10 9 M+18 F \ T 25 38 25 30 ui 30 15 6 10 [5] 9 [25] 12 8 0 50 13 [20] M 14M 14 1 8 [30] 4 38 10 [5] 11 [33] M 10M 12 7 1 vj 9 10 9 4 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 Kết luận? ThS. Phạm Trí Cao * Chương 3 03/01/2014 16 Ví dụ 3.10: Bài toán (P) F \ T 25 40 15 50 50 8 3 4 7 50 1 7 5 3 30 2 2 6 4 Cấm tuyến A1  B2, A1  B4 HD: Bài toán (M) F \ T 25 40 15 50 ui 50 8 + M-10 M [10] 4 [15] M  [25] 0 50 1  * [25] 7 -4 5 -M+2 3 + [25] 3-M 30 2 -2 2 [30] 6 -M 4 -2 2-M vj M-2 M 4 M F \ T 25 40 15 50 ui 50 8 [25] M [10] 4 [15] M [0] 0 50 1 -M+10 7 -4 5 -M+2 3 [50] 3-M 30 2 -M+8 2 [30] 6 -M 4 -2 2-M vj 8 M 4 M Ta có ij <=0, i,j : pa đang xét tối ưu Ta có x12 = 10  0 (ô cấm) nên bài toán (P) không có patư.  2) Cấm không cho phát hàng vào ô giả  Bài toán có ô cấm còn xuất hiện trong trường hợp bài toán không CBTP:  Tổng phát > tổng thu:  Thêm điều kiện là một trạm phát nào đó phải phát hết hàng. Cách làm: Ô nằm ở vị trí: dòng trạm phát phải phát hết hàng, cột trạm thu giả là ô cấm.  Lưu ý:  Trình tự phân phối các ô: ô thực, ô giả, ô cấm. ThS. Phạm Trí Cao * Chương 3 03/01/2014 17 Ví dụ 3.11: F \ T 120 130 50 100 10 8 12 150 15 10 14 80 9 11 12 Trạm A2 phát hết hàng. HD: Cách 1: F \ T 120 130 50 (30) ui 100 10 3 8  [100] 12 0 0 + M2 0 150 15 [40] 10 + [30] 14 [50] M  * [30] 2 80 9 [80] 11 7 12 4 0 M6 4 vj 13 8 12 M2 F \ T 120 130 50 (30) ui 100 10 + 3 8  [70] 12 0 0 [30] 0 150 15  * [40] 10 + [60] 14 [50] M 2 M 2 80 9 [80] 11 7 12 4 0 4 4 vj 13 8 12 0 F \ T 120 130 50 (30) ui 100 10 [40] 8 [30] 12 0 0 [30] 0 150 15 3 10 [100] 14 [50] M 2 M 2 80 9 [80] 11 4 12 1 0 1 1 vj 10 8 12 0 Ta có ij <=0, i,j : pa đang xét tối ưu fmin = 3060 Cách 2: Lợi dụng patư của VD3.4 : xem trong sách. ThS. Phạm Trí Cao * Chương 3 03/01/2014 18  Tổng phát < tổng thu: Thêm điều kiện là một trạm thu nào đó yêu cầu phải thu đủ hàng. Cách làm: Ô nằm ở vị trí: dòng trạm phát giả, cột trạm thu phải thu đủ hàng là ô cấm. Lưu ý: Trình tự phân phối các ô: ô thực, ô giả, ô cấm. Ví dụ 3.12: Bài toán (P) F \ T 60 60 80 100 80 1 7 6 8 60 5 4 6 5 110 6 3 2 9 Trạm thu B4 phải thu đủ hàng. HD: Cách 1: Tổng phát= 200 < tổng thu= 230 Bài toán (M) tương ứng F \ T 60 60 80 100 ui 80 1 [60] 7 0 6 0 8 [20] 0 60 5 -7 4  * [30] 6 -3 5 + [30] -3 110 6 -9 3 [30] 2 [80] 9 -5 -4 (50) 0 M-7 0 + M-1 0 M-2 M  [50] M-8 vj 1 7 6 8 F \ T 60 60 80 100 ui 80 1 [60] 7 -M+1 6 -M+1 8 [20] 0 60 5 -7 4 -M+1 6 -M-2 5 [60] -3 110 6 M-10 3  [30] 2 [80] 9 + M-6 M-5 (50) 0 M-7 0 + [30] 0 -1 M  * [20] M-8 vj 1 -M+8 -M+7 8 ThS. Phạm Trí Cao * Chương 3 03/01/2014 19 F T 60 60 80 100 ui 80 1 [60] 7 -5 6 -5 8 [20] 0 60 5 -7 4 -5 6 -8 5 [60] -3 110 6 -4 3 [10] 2 [80] 9 [20] 1 (50) 0 -1 0 [50] 0 -1 M -M+6 -2 vj 1 2 1 8 Ta có ij <=0, i,j : pa đang xét tối ưu fmin = 890 Ví dụ 3.13: Bài toán (P) F \ T 60 60 80 100 80 1 7 6 8 60 5 4 6 5 110 6 3 2 9 Cấm tuyến đường A3  B2. Trạm thu B4 phải thu đủ hàng. fmin = 940 Bài giải chi tiết xem trong sách. VI) BÀI TOÁN DẠNG VẬN TẢI CÓ HÀM MỤC TIÊU CỰC ĐẠI Với bài toán minf thì ý nghĩa cij là chi phí vận chuyển, còn với maxf thì ý nghĩa cij là lợi nhuận có được khi vận chuyển hàng. Cách 1 (giải gián tiếp) Xem chi tiết trong sách.  Nhận xét: Qua cách giải gián tiếp, ta thấy chỉ có những gì liên quan đến cij mới bị đổi dấu, còn liên quan đến xij, ai, bj không bị thay đổi. Cách 2 (giải trực tiếp)  Thuật toán thế vị minf được thay đổi như sau:  B1) Tìm pacb ban đầu: phân phối theo lợi nhuận lớn nhất.  B2) Xác định hệ thống thế vị: Giống như cũ.  B3) Kiểm tra tính tối ưu:  ij = ui + vj cij  * ij >=0 ,  i,j : pa đang xét là patư.  Xong thuật toán.  * Có ij <0 : pa đang xét chưa tối ưu.  Sang B4. ThS. Phạm Trí Cao * Chương 3 03/01/2014 20 B4) Chuyển sang bảng vận tải mới:  * Ô điều chỉnh là ô có  âm nhỏ nhất.  rs = min{ij / ij <0}  * Các công việc còn lại giống như cũ. Ví dụ 3.14: F \ T 50 18 32 20 40 30 28 3 10 25 27 14 11 2 30 5 14 11 22 25 9 16 6 12 Cách 2: Bước 1) Bảng vận tải xuất phát. F T 50 18 32 20 ui 40 30  [40] 28 + 4 3 11 10 15 0 25 27 + [10] 14 7 11  * [15] 2 20 -3 30 5 22 14 7 11 [10] 22 [20] -3 25 9 13 16  [18] 6 + [7] 12 5 -8 vj 30 24 14 25 Bước 4: F T 50 18 32 20 ui 40 30 [25] 28 [15] 3 15 10 19 0 25 27 [25] 14 11 11 4 2 24 -3 30 5 18 14 7 11 [10] 22 [20] -7 25 9 9 16 [3] 6 [22] 12 5 -12 vj 30 28 18 29 Ta có ij >= 0, i,j : pa đang xét tối ưu fmax = f(X*) = 2575 . Ghi patư của bài toán? ThS. Phạm Trí Cao * Chương 3 03/01/2014 21 Ví dụ 3.15: F \ T 35 30 55 30 10 9 8 50 7 6 7 40 5 4 3 f max Cấm tuyến A3  B3 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 ui 30 10  [30] 9 0 8 + -M-3 0 50 7 M+5 6 M+5 7 [50] M+2 40 5 + [5] 4 [30] M  * [5] -5 vj 10 9 -M+5 F \ T 35 30 55 ui 30 10 [25] 9 0 8 [5] 0 50 7 2 6 2 7 [50] -1 40 5 [10] 4 [30] M M+3 -5 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. Quy ước: Nếu trong đề thi không nói gì về f thì có nghĩa là f  min. Còn nếu muốn f  max thì sẽ nói rõ trong đề. ThS. Phạm Trí Cao * Chương 3 03/01/2014 22 VII) VẤN ĐỀ VỀ PATƯ DUY NHẤT Định lý: Bài toán có các pacbtư là X1, X2, , Xk thì patư tổng quát có dạng X=  k i iXi1  , với   k i i1 1 , 0<=i <=1 Lưu ý: Tất cả pa có từ bảng vận tải đều là pacb, pa có từ bảng tối ưu (là bảng mà từ đó ta lấy ra patư) là pacbtư. Ta có các kết quả sau: Xét bảng vận tải tối ưu. B1) Nếu ij  0 với mọi ô loại (i,j) : Bài toán có 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.  Cách xác định xem có patư khác hay không:  * Lấy ô loại (i,j) có ij = 0 làm ô điều chỉnh.  * Xác định vòng điều chỉnh.  * Xác định lượng điều chỉnh q.  Có 2 khả năng xảy ra:  * Lượng điều chỉnh q = 0 : Bài toán có patư duy nhất.  * Lượng điều chỉnh q > 0 : Bài toán có patư không duy nhất.  Lưu ý:  Phân biệt pacb và pacbtư, phân biệt patư và pacbtư. Ví dụ 3.16: Bài toán minf : 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 có patư duy nhất.  Trong trường hợp này: pacbtư duy nhất, patư duy nhất. Bài toán maxf : VD 3.14 có ij >0 với mọi ô loại (i,j) : bài toán có patư duy nhất.  Trong trường hợp này: pacbtư duy nhất, patư duy nhất. Ví dụ 3.17 : Xem lại VD 3.3, cách 1. Ở 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. Tìm vòng điều chỉnh, xác định lượng điều chỉnh q F \ T 60 70 40 30 ui 100 12 2 6 [70] 9 1 12 [30] 0 80 9 [60] 8 3 7  [20] 11 + 0 1 20 11 3 7 3 6 + [20] 10  * [0] 2 vj 10 6 8 12 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. ThS. Phạm Trí Cao * Chương 3 03/01/2014 23 Ví dụ 3.18: Xem lại VD 3.4. Bảng tối ưu: F \ T 120 130 50 (30) ui 100 10 [40] 8  [60] 12 + 0 0 2 0 150 15 3 10 + [70] 14  * [50] 0 [30] 2 80 9 [80] 11 4 12 1 0 3 1 vj 10 8 12 2 B1 Ta có ij <=0, i,j : pa đang xét tối ưu              0080 50700 06040 1X fmin = 3000 Ở bảng 1: Ta có ô loại (1,3) có =0 nên lấy làm ô điều chỉnh. Tìm vòng điều chỉnh. Lượng điều chỉnh q= 50 >0 nên bài toán có patư khác. Từ bảng 1 ta được bảng 2. F \ T 120 130 50 (30) ui 100 10 [40] 8 + [10] 12  * [50] 0 -2 0 150 15 -3 10  [120] 14 + 0 0 [30] 2 80 9 [80] 11 -4 12 -1 0 -3 -1 vj 10 8 12 -2 B2              0080 01200 501040 2X Ở bảng 2: Ta có ô loại (2,3) có =0 nên lấy làm ô đ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. Patư tổng quát có dạng: X= X1 + (1-)X2 với 0 <=  <= 1 Trong trường hợp này: pacbtư không duy nhất, patư không duy nhất. ThS. Phạm Trí Cao * Chương 3 03/01/2014 24 Ví dụ 3.19: Xem lại VD 3.5 F \ T 50 100 50 (20) ui 50 5 -2 6  [25] 6 + [25] 0 -3 0 75 7 -2 8 [75] 9 -1 0 -1 2 95 6 [50] 9 + 0 9  [25] 0 [20] 3 vj 3 6 6 -3 B1              25050 0750 25250 1X Ở bảng 1: ô điều chỉnh là (3,2). Nếu loại ra ô (1,2), từ bảng 1 ta được bảng 2. Nếu loại ra ô (3,3), từ bảng 1 ta được bảng 3. F \ T 50 100 50 (20) ui 50 5 -2 6 + 0 6  [50] 0 -3 0 75 7 -2 8 [75] 9 -1 0 -1 2 95 6 [50] 9  * [25] 9 + [0] 0 [20] 3 vj 3 6 6 -3 B2              02550 0750 5000 2X Ở bảng 2: lấy ô (1,2) làm ô điều chỉnh, biến đổi từ bảng 2 quay về bảng 1. Ở bảng 3: lấy ô (3,3) làm ô điều chỉnh, biến đổi từ bảng 3 quay về bảng 1. ThS. Phạm Trí Cao * Chương 3 03/01/2014 25 F \ T 50 100 50 (20) ui 50 5 -2 6 + [0] 6  [50] 0 -3 0 75 7 -2 8 [75] 9 -1 0 -1 2 95 6 [50] 9  * [25] 9 + 0 0 [20] 3 vj 3 6 6 -3 B3 Ta có X3 = X2 Trong trường hợp này: pacbtư không duy nhất, patư không duy nhất. Mời ghé thăm trang web: 98  https://sites.google.com/a/ueh.edu.vn/phamtricao/  https://sites.google.com/site/phamtricao/