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ạn đang xem trước 20 trang tài liệu Bài giảng môn Tối ưu hóa - Chương 3 Bài toán vận tải, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
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+41. H2: pacb suy biến vì không có vòng và số ô chọn = 5 < 6 = 3+41. 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’] =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 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’]