Bài toán vận tải

11 BÀI TOÁN VẬN TẢI 2 S1 S2 S3 D1 D2 D3 D4 Xác định Xij để TC min Các dữ liệu : • Các điểm nguồn (Si) và khả năng cung cấp của từng điểm nguồn. • Các điểm đích (Dj) và nhu cầu của từng điểm đích. • Chi phí vận chuyển từ điểm nguồn i đến điểm đích j. Cij 23 Ví dụ : Một doanh nghiệp có ba kho chứa hàng với khả năng cung cấp từng kho là 120, 140 và 100 sản phẩm/ngày. Giả sử hàng ngày hàng phải được vận chuyển đến 4 điểm bán lẻ với nhu cầu là 100, 60, 80 và 120 sản phẩm. Tìm phương án vận chuyển tối ưu (Tổng chi phí vận chuyển bé nhất) Biết rằng chi phí vận chuyển một đơn vị sản phẩm giữa các kho và điểm bán lẻ cho ở bảng sau : 140510762 12069751 120 1 4 3608060100Tổng cầu 1008673 321 Tổng cungĐiểm bán lẻKho 4 CÁC KÝ HIỆU Để thuận tiện cho việc thiết lập mô hình, ta sử dụng một số ký hiệu sau : m : Số điểm nguồn n : Số điểm đích si : Khả năng cung cấp của điểm nguồn thứ i (i = 1, 2, , m) dj : Nhu cầu nhận của điểm đích thứ j (j = 1, 2, , n) xij : Lượng hàng hoá chuyển từ điểm nguồn thứ i đến điểm đích thứ j . Cij : Chi phí vận chuyển hàng hoá từ điểm nguồn thứ i đến điểm đích thứ j . 35 S2C2nC22C212 S1C1nC12C111 dn Cmn n d2d1Tổng cầu SmCm2Cm1m 21 Tổng cung Điểm đíchĐiểm nguồn 0xij n)1,2,...,(jdjxij m)1,2,...,(isixij Minxij.cijZ m 1i n 1j m 1i n 1j ≥ == == ⇒= ∑ ∑ ∑ ∑ = = = = MÔ HÌNH TỔNG QUÁT x11 x12 x1n x22x21 xm1 x2n xm2 xmn 6 PHƯƠNG PHÁP GIẢI BƯỚC 1 : TÌM LỜI GIẢI BAN ĐẦU. BƯỚC 2 : CẢI THIỆN NGHIỆM BAN ĐẦU CHO TỚI KHI ĐẠT ĐƯỢC ĐIỂM TỐI ƯU. 47 TÌM LỜI GIẢI BAN ĐẦU 1-PHƯƠNG PHÁP GÓC TÂY BẮC 2-PHƯƠNG PHÁP CHI PHÍ BÉ NHẤT 3-PHƯƠNG PHÁP VAM 8 PHƯƠNG PHÁP GÓC TÂY BẮC (The Northwest Corner Method)
Chọn ô ở góc tây bắc làm ô xuất phát.
Cung cấp tối đa từ khả năng của một điểm nguồn cho các điểm đích theo thứ tự từ trái sang phải. Nếu nguồn i đã hết thì chuyển sang nguồn i+1.
Đáp ứng tối đa nhu cầu của một điểm đích từ các nguồn theo thứ tự ưu tiên từ tre ân xuống dưới. Nhu cầu j đã đủ thì chuyển sang nhu cầu j+1. 1405107 62 12069 751 120 1 4 3608060100Tổng cầu 1008 6 7 3 321 Tổng cung Điểm bán lẻ (j)Kho (i) 100 20 80 2040 100 59 PHƯƠNG PHÁP CHI PHÍ BÉ NHẤT (The Minimal Cost Method) :
Ưu tiên chọn ô có chi phí thấp nhất để đáp ứng tối đa khả năng cũng như nhu cầu.
Loại bỏ các ô của điểm nguồn hoặc điểm đích đã hết khả năng cũng như nhu cầu.
Xác định lại ô có chi phí thấp nhất trong các ô còn lại và tiếp tục phân bổ giống như các bước trên. 1405107 62 12069 751 120 1 4 3608060100Tổng cầu 1008 6 7 3 321 Tổng cung Điểm bán lẻKho 100 20 60 60 20 100XX X X XX 10 PHƯƠNG PHÁP XẤP XỈ VOLGEL - VAM (The Volgel’s Approximation Method)
Ứng với mỗi hàng và cột của bảng, xác định đôï chênh lệch giữa hai ô có chi phí vận chuyển bé nhất và bé nhì. Xác định hàng hay cột có chênh lệch Max.
Phân bổ tối đa lượng hàng có thể vào ô có chi phí bé nhất và loại bỏ các ô còn lại trong hàng hoặc cột đã chọn ở bước trên.
Thực hiện lặp lại các bước trên cho các ô còn lại. Chú ý : Khi xuất hiện chi phí cơ hội Max ở nhiều hàng hoặc cột khác nhau, thì chọn hàng (cột) có chứa ô có nhu cầu (khả năng) cao nhất . 611 Theo ví dụ trên, ta có : 1405107 62 12069 751 120 1 4 3608060100Tổng cầu 1008 6 7 3 321 Tổng cung Điểm bán lẻKho 100 1 1 5 4111 XXX 12 1405107 62 12069 751 120 1 4 3608060100Tổng cầu 1008 X 6 X 7 X 3 321 Tổng cung Điểm bán lẻKho 100 1 1 1 101 100 X 1 1 2 10 1405107 6 X 2 12069 751 120 1 4 3608060100Tổng cầu 1008 X 6 X 7 X 3 321 Tổng cung Điểm bán lẻKho 100 100 20 X 713 1405107 6 X 2 1206 X 9 751 120 1 4 3608060100Tổng cầu 1008 X 6 X 7 X 3 321 Tổng cung Điểm bán lẻKho 100 100 20 2 3 10 60 X 1405107 6 X 2 1206 X 9 7 X 51 120 1 4 3608060100Tổng cầu 1008 X 6 X 7 X 3 321 Tổng cung Điểm bán lẻKho 100 100 2060 20 60 14 CẢI THIỆN NGHIỆM BAN ĐẦU CHO TỚI KHI ĐẠT ĐƯỢC ĐIỂM TỐI ƯU. 815 Bước 1 : Tính toán chỉ số cải tiến Iij cho các ô rổng (ô không có phân bổ hàng). Có hai phương pháp xác định : 1- Phương pháp duyệt tuần tự :
Ứng với một ô rổng nào đó, vẽ đường đi kín nối ô rổng này với các ô đã gán giá trị ban đầu bằng các đường nằm ngang và thẳng đứng (Vòng).
Gán dấu cho các ô trong đường đi bắt đầu từ ô rổng có dấu dương (+), các ô kế tiếp đổi dấu (dấu âm -).
Tính các chỉ số Iij = Tổng đại số các Cij trong đường đi đang xét với dấu đã được gán ở bước trên. 16 Ví dụ : Bằng phương pháp góc tây bắc, ta có phương án ban đầu như sau : 1405 20 10 80 7 40 62 12069 7 20 5 100 1 120 1 100 4 3608060100Tổng cầu 1008 6 73 321 Tổng cung Điểm bán lẻKho Lúc đó : I13 = + 9 -10 + 7 - 7 = -1 + - - + Xét ô rổng (1,3) : 917 2- Phương pháp thế vị :
Gọi ui (i = 1,2,,m) ; vj (j =1,2,n) là các biến ứng với các điểm nguồn i và điểm đích j,
Tại các ô không rổng ta có đẳng thức : cij – (ui +vj) = 0
Dựa vào các phương trình tương ứng với các ô không rổng, ta có thể xác định được các giá trị ui và vj
Tại các ô rổng, tính các chỉ số cải tiến Iij = cij – (ui + vj).
Chú ý : - Thông thường người ta gán giá trị u1 = 0 và từ đó tính các giá trị ui, vj còn lại. - Sau mỗi bước lặp, tính lại các ui, vj và Iij . 18 Ví dụ : Bằng phương pháp góc tây bắc, ta có phương án ban đầu như sau : 1405 20 10 80 7 40 62 (u2) 12069 7 20 5 100 1 (u1) 120 1 100 4 (v4) 3608060100Tổng cầu 1008 6 73 (u3) 3 (v3)2 (v2)1 (v1) Tổng cung Điểm bán lẻKho 0 510 0 75 - 4 Với u1 = 0 → v1 = c11 – u1 = 5 – 0 = 5 ; v2 = c12 – u1 = 7 – 0 = 7 Với v2 = 7 → u2 = c22 – v2 = 7 – 7 = 0 Với u2 = 0 → v3 = c23 – u2 = 10 – 0 = 10 ; v4 = c24 – u2 = 5 – 0 = 5 Với v4 = 5 → u3 = c34 – v4 = 1 – 5 = -4 10 19 Tính các chỉ số cải tiến Iij của các ô rổng : Iij = cij – (ui + vj) 1405 20 10 80 7 40 6 I21 = 1 2 (u2) 1206 I14 = 1 9 I13 = -1 7 20 5 100 1 (u1) 120 1 100 4 (v4) 3608060100Tổng cầu 1008 I33 = 2 6 I32 = 3 7 I31 = 6 3 (u3) 3 (v3)2 (v2)1 (v1) Tổng cung Điểm bán lẻKho 0 0 51075 - 4 + - - + 20 Bước 2 : kiểm tra dấu hiệu tối ưu và phân bố lại hàng :
Nếu các chỉ số Iij của các ô rổng đều không âm, phương án hiện hành là tối ưu.
Nếu tồn tại một hay một số chỉ số Iij của ô rổng nào đó âm, phương án hiện tại chưa tối ưu.
Ta chọn chỉ số Iij bé nhất và điều chỉnh lượng hàng đã phân bổ cho các ô có liên quan theo nguyên tắc sau : * Xác định xij min trong các ô được gán dấu trừ (-). * Bớt đi một lượng xij min cho các ô gán dấu trừ. * Cộng thêm một lượng xij min cho các ô gán dấu cộng (+). 11 21 1405 20 _ 10 60 + 7 60 62 1206+ 9 20 _ 7 0 5 100 1 120 1 100 4 3608060100Tổng cầu 1008 6 73 321 Tổng cungĐiểm bán lẻKho Tiếp tục làm cho các ô rổng còn lại cho tới khi không còn chỉ số Iij < 0 thì dừng lại. Phương án cuối cùng này là phương án tối ưu. ∑∑ = = == 3 1 4 1 1900. i j xijcij*Z Trong ví dụ trên, ô (1,3) có I13 = -1 < 0 ⇒ Chưa thỏa điều kiện tối ưu. Tiến hành phân bổ lại lượng hàng vận chuyển cho các ô như sau : * Giá trị điều chỉnh = min (x12,x23) = 20 * Giá trị các ô mới là : x12 = 20 – 20 = 0 x13 = 0 +20 = 20 x23 = 80 – 20 = 60 x22 = 40 + 20 = 60 Ta được bảng sau : 22 Bài 1 : Một công ty có ba kho chứa hàng với khả năng cung cấp từng kho là 15, 75 và 20 tấn nguyên liệu / ngày. Công ty có 4 phân xưởng sản xuất với với nhu cầu nguyên liệu cho từng phân xưởng là 5 ; 35 ; 15 và 55 tấn / ngày. Chi phí vận chuyển một tấn nguyên liệu từ kho i đến phân xưởng j cho ở ma trận sau : Yêu cầu : Xác định phương án vận chuyển tối ưu. (Z = 1325)           = 1614108 209712 1115510 cij 12 23 Lập kế hoạch vận chuyển hàng từ các xí nghiệp đến các cửa hàng sao cho tổng chi phí vận chuyển là thấp nhất. (Z = 1680) Bài 2 : Một công ty bách hoá có ba cửa hàng có nhu cầu về một loại hàng tương ứng là 45, 90 và 110 tấn. Công ty đã đặt mua loại hàng đó ở bốn xí nghiệp với khả năng cung ứng là 40, 75, 60, 70 tấn. Cước vận chuyển (ngàn đồng/tấn) từ xí nghiệp i đến cửa hàng j cho ở ma trận sau :               = 1288 683 854 101012 cij 24 Ta cĩ thể sử dụng phần mềm QM để tìm nghiệm : • Khởi động phần mềm QM và di chuyển con trỏ đến phần mềm thích hợp (Transportation). • Cĩ thể đánh ký tự E để chọn. 13 25 Ta được giao diện Transportation : • Chọn New (N) và khai báo các thơng số cần thiết. • Cĩ thể sử dụng các số liệu của ví dụ 1. 26 • Chọn Run (R) để giải 14 27 • Dùng phím mủi tên lên, xuống để xem kết quả. 28 BÀI TOÁN VẬN TẢI KHÔNG CÂN BẰNG THU VÀ PHÁT
Ta phân biệt hai trường hợp : - Trường hợp tổng phát lớn hơn tổng thu : Đưa bài toán về dạng cân bằng thu phát bằng cách thêm một trạm thu giả có nhu cầu bằng phần chênh lệch của phần phát và phần thu. - Trường hợp tổng phát nhỏ hơn tổng thu : Đưa bài toán về dạng cân bằng thu phát bằng cách thêm một trạm phát giả có khả năng cung bằng phần chênh lệch của phần thu và phần phát.
Gán chi phí vận chuyển đơn vị từ mọi điểm nguồn thực đến điểm đích giả hay điểm nguồn giả đến điểm đích thực bằng 0.
Xác định phương án xuất phát và phương án tối ưu giống như bài toán cân bằng thu phát. 15 29 Ví dụ : Một công ty cần vận chuyển một loại hàng từ bốn kho chứa hàng đến ba cửa hàng. Số lượng hàng có ở các kho là 150, 100, 145 và 100. Nhu cầu hàng hóa ở các cửa hàng là 140, 150 và 180. Giá cước vận chuyển đơn vị hàng hóa từ kho i đến cửa hàng j cho ở ma trận sau : Tìm phương án vận chuyển tối ưu.             = 1379 12611 958 645 cij 30 Do tổng cung = 495 > tổng cầu = 470. Do đó, ta cần tạo thêm trạm thu giả có nhu cầu = 495 – 470 = 25 và gán cho các ô giả này có cước phí vận chuyển bằng 0 : 495 100 145 100 150 Tổng cung 0645A1 012611A3 0958A2 180 13 B3 25150140Tổng cầu 079A4 B4B2B1 Cửa hàngKho Phương pháp giải 16 31 Ví dụ : Một công ty cần vận chuyển một loại hàng từ ba kho chứa hàng đến bốn cửa hàng. Số lượng hàng ở các kho là 80, 70 và 50. Nhu cầu của các cửa hàng là 100, 50, 30 và 70. giá cước vận chuyển đơn vị hàng hóa từ kho i đến cửa hàng j cho ở ma trận sau : Tìm phương án vận chuyển tối ưu.           = 3443 8754 5653 cij 32 Do tổng cung = 200 < tổng cầu = 250. Do đó, ta cần tạo thêm trạm phát giả có khả năng phát = 250 – 200 = 50 và gán cho các ô giả này có cước phí vận chuyển bằng 0 : 250 50 50 70 80 Tổng cung 5653A1 3443A3 8754A2 30 0 B3 7050100Tổng cầu 000A4 B4B2B1 Cửa hàngKho Phương pháp giải