CÁC BÀI TOÁN VỀ VẬN TẢI

I. Bài toán vận tải dạng tổng quát 1. Phát biểu bài toán vận tải Giả sử có nguồn phát A gồm m địa điểm phát S1,S2,…,Sm cùng sản xuất một loại hàng hóa nào đó với trữ lượng tương ứng lần lượt là a1,a2,…,am. và nguồn thu B gồm n nơi tiêu thụ T1,T2,…,Tn cùng thu một loại hàng hóa nói trên với trữ lượng cần thu tương ứng lần lượt là b1,b2,…,bn..Hay đơn giản, ta gọi :Si : là điểm phát thứ i T j : là điểm thu thứ j ai : được gọi là lượng phát...
Nội dung trích xuất từ tài liệu:
CÁC BÀI TOÁN VỀ VẬN TẢI BÀI TOÁN VẬN TẢII. Bài toán vận tải dạng tổng quát1. Phát biểu bài toán vận tải Giả sử có nguồn phát A gồm m địađiểm phát S1,S2,…,Sm cùng sản xuất mộtloại hàng hóa nào đó với trữ lượng tươngứng lần lượt là a1,a2,…,am. và nguồn thu Bgồm n nơi tiêu thụ T1,T2,…,Tn cùng thumột loại hàng hóa nói trên với trữ lượngcần thu tương ứng lần lượt là b1,b2,…,bn.Hay đơn giản, ta gọi : Si : là điểm phát thứ i T j : là điểm thu thứ j ai : được gọi là lượng phát thứ i b j : được gọi là lượng thu thứ j cij : là cước phí vận chuyển một đơn vịhàng hóa từ điểm phát thứ i đến điểm thuthứ j. C   cij i 1,m ma trận cước phí. j 1, nHàng hóa có thể chuyển từ một điểmphát bất kỳ đến một điểm thu bất kỳ. Yêu cầu của bài toán vận tải là : Hãy lập kế hoạch vận chuyển hànghóa từ các điểm phát đến các điểm thusao cho tổng cước phí vận chuyển là bénhất và thỏa mãn nhu cầu thu phát.Gọi xij là lượng hàng vận chuyển từđiểm phát thứ i đến điểm thu thứ j.Ta có :cij xij : chi phí vận chuyển lượng hàngxij từ điểm phát i đến điểm thu j.m n c x : tổng chi phí vận chuyển hàng ij ij i 1 j 1từ các điểm phát i đến các điểm thu j.nx  xi1  xi 2   xin : lượng hàng ijj 1được chuyển đi khỏi điểm phát thứ i. mx  x1 j  x2 j   xmj : lượng hàng ij i 1được chuyển đến điểm thu thứ j .Vậy ta có mô hình bài toán như sau : m n f  x    cij x ij  min  i 1 j1Với ràng buộc : n  x ij  a i , i  1, m  j1 m   x ij  b j , j  1, n  i 1 x  0 , i  1, m ; j  1, n  ij  2. Đặt bài toán vận tải dưới dạng bảng B … T1 : b1 T2 : b2 Tn : bn A x11 x12 x1n S1 : a1 c11 c12 c1n x21 x22 x2n S2 : a2 c21 c22 c2n … xm1 xm2 xmn Sm : am cm1 cm2 cmn3. Dây chuyền (đường đi) Dây chuyền là tập hợp các ô thỏa :• Hai ô liên tiếp bao giờ cũng nằm trên mộtdòng hoặc một cột.• Ba ô liên tiếp không nằm trên một dònghoặc một cột.4. Chu trình Một dây chuyền khép kín được gọi làmột Chu trình ( hay còn gọi là một Vòng). X XX X X X X X X X X X Dây chuyền ( đường đi ) X XX X X X X X X XX X Chu trình ( vòng )II. Phương pháp tìm phương án xuấtphát (phương án ban đầu)1. Phương pháp gốc Tây – Bắc Chọn ô (1,1) là ô phân phối hàng đầutiên với lượng hàng x11= min{a1;b1}, chọnô tiếp theo nằm trong cùng dòng (nếu cộtthu đủ hàng) hoặc cột (nếu dòng phát hếthàng) với ô đã chọn từ trên xuống dưới, từtrái sang phải. Trong khi phân phối hàngchú ý tới yêu cầu thu, phát của các trạm.Ví dụ 1: Cho bài toán vận tải với :Nguồn phát A  30, 50, 70Nguồn thu B  20, 40, 60, 30 2 3 1 4và ma trận cước phí C  1 2 4 5    3 1 2 1   Tìm phương án xuất phát (ban đầu) bằngphương pháp gốc “ Tây – Bắc ”2. Phương pháp Forgel. Ở mỗi dòng và mỗi cột của ma trậncước phí ta tính hiệu số giữa hai giá trịcước phí nhỏ nhất trên dòng (cột) đó. Chọn dòng hay cột có hiệu số lớn nhất. Phân lượng hàng tối đa có thể vào ô cócước phí bé nhất trên dòng (cột) đã chọn,sau đó loại bỏ dòng (cột) đã nhận đủhàng. Thực hiện lại phương pháp cho đếnkhi chỉ còn lại một dòng hay cột duynhất ( phân phối hết hàng)Làm lại VD1 bằng phương pháp Forgel.3. Phương pháp cước phí bé nhất. Chọn ô đầu tiên là ô có cước phí bénhất trong bảng để phân phối một lượnghàng hóa nhiều nhất. Ô được chọn tiếp theo sẽ nằm trongcùng dòng hoặc cột với ô vừa chọn vàcũng có cước phí bé nhất trong các ô cònlại. Trong khi chọn ta cũng chú ý tới yêucầu thu – phát của các trạm.Làm lại VD1 bằng Pp cước phí bé.III. Phương pháp thế vị Cho bài toán vận tải với :Nguồn phát A  a1 ,a 2 , , a m  B  b1 , b2 , , bn Nguồn thuvà ma trận cước phí C  cij  ,i  1, m , j  1, n  Bài toán cân bằng “Thu – Phát ” m n a  bi j i 1 ...