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

Chia sẻ: Baozowen Ko | Ngày: | Loại File: PDF | Số trang:26

Thêm vào BST

Báo xấu

279
lượt xem 75
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

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...

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: CÁC BÀI TOÁN VỀ VẬN TẢI

BÀI TOÁN 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 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 thu thứ j. C   cij i 1,m ma trận cước phí. j 1, n
Hàng hóa có thể chuyển từ một điểm phá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àng hóa từ các điểm phát đến các điểm thu sao 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àng xij 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 1 từ các điểm phát i đến các điểm thu j.
n x  xi1  xi 2   xin : lượng hàng ij j 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1 Vớ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 cmn
3. 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ột dòng hoặc một cột. • Ba ô liên tiếp không nằm trên một dòng hoặ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 X X X X X X X X X X X Dây chuyền ( đường đi )
X X X X X X X X X X X X Chu trình ( vòng )
II. Phương pháp tìm phương án xuất phá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 đầu tiê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ột thu đủ hàng) hoặc cột (nếu dòng phát hết hà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àng chú ý 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ằng phươ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ận cướ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 đến khi chỉ còn lại một dòng hay cột duy nhấ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ượng hàng hóa nhiều nhất. Ô được chọn tiếp theo sẽ nằm trong cù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òn lại. Trong khi chọn ta cũng chú ý tới yêu cầ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 thu và 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 j1
 Nội dung phương pháp thế vị Bước 1: Lập phương án xuất phát ( bằng một trong ba phương pháp : gốc Tây – Bắc, Forgel, cước phí bé )  Nếu số ô chọn bằng m + n – 1 thì phương án xuất phát là không suy biến.
 Nếu số ô chọn nhỏ hơn m + n – 1 thì phương án xuất phát gọi là suy biến, khi đó ta phải bổ sung thêm các ô (loại) để được phương án xuất phát không suy biến, nhưng ô được bổ sung vào phải không tạo thành chu trình với các ô đã chọn.
Bước 2: Lập hệ phương trình ở các ô chọn (i, j) có dạng ui + vj = cij Hệ phương trình trên có m + n - 1 phương trình và m + n ẩn số nên hệ vô số nghiệm. Để giải hệ phương trình trên ta cho 1 giá trị tùy ý cho biến tự do ( nên chọn biến tự do là biến xuất hiện nhiều nhất trong hệ phương trình)