Chương 3ÀI TOÁN VẬN TẢI 3 Giới thiệu bài toán vận tải Bài toán mở đầu. Ta cần vận chuyển máy tính từ 2 công ty (trạm phát)A 1 vàA 2 đến 3 nơi tiêu thụ (trạm thu)B 1 ; B 2 vàB 3. Số lượng máy tính ở mỗi công ty cần chuyển, nhu cầu máy tính tại các nơi tiêu thụ cũng như cước phí vận chuyển cho mỗi máy tính được chuyển từ công tyAi; i= 1; 2 đến nơi tiêu thụBj; j= 1; 2 ; 3 được cho trong bảng sau: Show Trạm thu B 1 : 15 B 2 : 20 B 3 : 25 Trạm A 1 : 20 5 7 2 phát A 2 : 40 4 4 6 Hãy mô hình toán lập kế hoạch vận tải sao cho: Số máy tính ở các công ty phải vận chuyển hết, số máy tính tại các nơi tiêu thụ phải nhận đủ và chi phí vận chuyển là thấp nhất. Giảiọixijlà số máy tính được chuyển từ công tyAiđến nơi tiêu thụBj. Khi đó, theo yêu cầu của bài toán ta có các ràng buộc như sau: Số máy tính chuyển đi từ các công ty (trạm phát) thỏa: Công tyA 1 :x 11 +x 12 +x 13 = 20 Công tyA 2 :x 21 +x 22 +x 23 = 40 Số máy tính thu về tại nơi tiêu thụ (trạm thu) thỏa: Nơi tiêu thụB 1 :x 11 +x 21 = 15 Nơi tiêu thụB 2 :x 12 +x 22 = 20 Nơi tiêu thụB 3 :x 13 +x 23 = 25 Vì số máy tính phát đi từ các công ty và nhận được tại các điểm tiêu thụ không âm nên ta có điều kiện:xij 0 : Tổng chi phí vận tải là: 5 x 11 + 7x 12 + 2x 13 + 4x 21 + 4x 22 + 6x 23 : Tóm lại ta có mô hình toán của bài toán vận tải ở trên là: Tìm ma trậnx= (xij) 2 3 sao cho f(x) = 5x 11 + 7x 12 + 2x 13 + 4x 21 + 4x 22 + 6x 23 !min; 8 >>> >< \>> >>: x 11 +x 12 +x 13 = 20 x 21 +x 22 +x 23 = 40 x 11 +x 21 = 15 x 12 +x 22 = 20 x 13 +x 23 = 25 xij 0 ; i= 1;2;j= 1; 2 ; 3 : 3.1 Mô hình tổng quát của bài toán vận tải (cổ điển) Gọixijlà lượng hàng chuyển từ trạm phátAi; i= 1; 2 ; :::; mđến nơi trạm thuBj; j= 1; 2 ; :::; n, vàcijlà cước phí vận chuyển từ tam phátAiđến tram thụBj Trạm thu B 1 :b 1 B 2 :b 2 ... Bn:bn Trạm phát ... A 1 :a 1 c 11 c 12 ... c 1 n A 2 :a 2 c 21 c 22 c 2 n Am:am cm 1 cm 2 ... cmn Bài toán trong Ví dụ mở đầu ở trên có thể được mô hình toán thành bài toán vận tải (cân bằng phát-thu) có mô hình tổng quát như sau: Tìm ma trậnx= (xij)mnsao cho f(x) = Pm i= Pn j= cijxij!min; (3) 8 >> < >> : Pn j= xij=ai; i= 1 ; m; Pm i= xij=bj; j= 1 ; n; (3)xij 0 ; i= 1 ; m; j= 1 ; n; (3) trong đó xijlà số lượng hàng hóa được chuyển từ trạm phátaiđến trạm thubj. ai; i= 1 ; mlà số lượng hàng hóa phát đi từ trạm phát thứi. bj; j= 1 ; nlà số lượng hàng hóa thu về tại các trạm thu thứj. cij; i= 1 ; m; j= 1 ; nlà số tiền vận chuyển 1 đơn vị hàng hóa từ trạm phát thứiđến trạm thu thứ j. Chú ý rằng bài toán trên thỏa điều kiện sau được gọi làđiều kiện cân bằng phát-thu Pm i= ai= Pn j= bj: (3) 3.1 Phương án của bài toán vận tải Định nghĩa. Một ma trậnx= (xij)mnthỏa mãn (3)-(3) được gọi là một phương án. Ví dụ 1ìm một phương án cho bài toán vận tải được cho bởi bảng sau Trạm thu B 1 : 40 B 2 : 20 B 3 : 60 Trạm A 1 : 30 5 7 1 Phát A 2 : 40 4 4 6 A 3 :50 3 3 2 Giải. Ta có ma trận x(1)= 0@30 0 010 10 200 10 401A;là một phương án của bài toán vận tải trên. Hoặc các ma trận x(2)= 0@0 10 2040 0 00 10 401A; x(0)= 0@0 0 3020 20 020 0 301Acũng đều là các phương án của bài toán vận tải trên. Định nghĩa. Ô nằm trên dòngivà cộtjđược gọi làô chọnnếu lượng hàngxijtương ứng với ô này có giá trịdương. Khi đó, biếnxijtương ứng với ô chọn gọi làbiến cơ sở. Trong Ví dụ 1, đối với phương ánx(1)thì các biếnx 11 ; x 21 ; x 22 ; x 23 ; x 32 ; x 33 là các biến cơ sở (giá trị tương ứng là 30,10,10,20,10,40). Định nghĩa. Ô chứa biến phi cơ bản (ô có lượng hàng bằng 0) được gọi là "ô chọn 0" của một PACB suy biến nếu nó và các ô chọn không tạo thành chu trình. Nhận xét. Để PACB suy biến trở thành một PACB không suy biến thì ta phải bổ sung một số "ô chọn 0" sao cho số ô chọn đủ bằngm+n 1. Chẳng hạn, trong Ví dụ 2 ta có thể bổ sung thêm 1 "ô chọn 0" để được một PACB không suy biến. Trong trường hợp này, một trong các ô (1;1);(1;2);(2;3);(3;3)đều có thể được chọn là "ô chọn 0" và chỉ được chọn một ô trong các ô này. Ô(3;1)không thể được chọn là "ô chọn 0" do nó cùng với các ô(2;1);(2;2);(3;2)sẽ trở thành chu trình. 3.1 Tính chấtét bài toán vận tải được có mô hình xác định bởi (3)-(3). Khi đó, ta có: (i) Mọi bài toán vận tải đều có phương án tối ưu. (ii) Trong một bài toán vận tải thì số ô chọn của một PACB không bao giờ vượt quám+n 1 ô. (iii) Với một PACB không suy biến thì một ô loại bất kỳ (có lượng hàng bằng 0) cũng tạo với các ô chọn thành một chu trình duy nhất. 3 Thuật toán thế vị Trong phần này, ta sẽ xây dựng một thuật toán gọi làthuật toán thế vịđể giải bài toán vận tải. Thuật toán thế vị về thực chất là phương pháp đơn hình vận dụng vào bài toán vận tải cũng bao gồm 3 bước chính: (i) Xây dựng PACB xuất phát, (ii) Kiểm tra tính tối ưu, (iii) Xây dựng PACB mới (tốt hơn). Để xây dựng một PACB xuất phát của bài toán vận tải ta có thể sử dụng một trong các phương pháp sau. 3.2 Phương pháp góc Tây-Bắc(xem tài liệu tham khảo) 3.2 Phương pháp cước phí thấp nhất Quá trình phân phối được ưu tiên cho các ô có giá cước thấp nhất được thực hiện theo các bước như sau: Bước 1. Phân phối hàng hóa tối đa vào ô có cước phí thấp nhất trong bảng. Bước 2. Điều chỉnh lượng hàng hóa ở các trạm phát và trạm thu chứa ô phân phối hàng ở Bước 1 và bỏ đi dòng hoặc cột chứa trạm phát hoặc trạm thu có lượng hàng bằng 0. Bước 3. Phân phối hàng hóa tối đa vào ô có cước phí thấp nhất trong bảng còn lại. Bước 4. Thực hiện lại Bước 2. Quá trình này được lặp lại cho đến khi các trạm phát phát hết hàng và các trạn thu nhận đủ hàng ta sẽ được PACB của bài toán. Ví dụ 1ử dụng phương pháp cước phí thấp nhất tìm PACB của bài toán vận tải được cho bởi bảng sau Trạm thu B 1 : 40 B 2 : 75 B 3 : 60 B 4 : 70 Trạm A 1 : 45 82 73 74 79 Phát A 2 : 90 80 75 81 79 A 3 :110 80 77 77 82 Giải.Đầu tiên ta có giá cước nhỏ nhất là 73, ứng với (1,2) và xác định lượng hàng sẽ chuyển vào ô này là:x 12 = minf 45 ; 75 g= 45. Sau đó, điều chỉnh lại các yêu cầu tương ứng với ô được phân phối: a 1 = 4545 = 0; b 2 = 7545 = 30:Đánh dấu ( - ) vào các ô nằm trên dòng có yêu cầu = 0 (dòng 1). ThuPhátTrong phần bảng còn lại, ta có giá cước nhỏ nhất là 75, ứng với (2,2), ta phân phối: x 22 = minf 90 ; 30 g= 30:Đánh dấu ( - ) vào các ô nằm trên cột có yêu cầu = 0 (cột 2). Sau đó lặp lại quá trình như trên đến cuối cùng ta có PACB xuất phát được xác định trong bảng trên. 3.2 Thuật toán thế vị Thuật toán thế vị được xây dựng dùng để giải bài toán vận tải có các bước chính như sau: Bước 1. Xây dựng PACB xuất phát (i) Xây dựng PACB bằng pp cước phí thấp nhất. (ii) Kiểm tra tính không suy biến của PACB
xij:với mọi ô(i; j)mang dấu . Lượng hàng điều chỉnhqđược xác định sẽ tương ứng với một ô(r; s)nào đó. Tức là:q=xrs. Khi đó(r; s)sẽ là ô loại trong bảng mới. PACB mới đựoc xác định như sau: x 0 ij=xij+q, với(i; j)mang dấu + x 0 ij=xijq, với(i; j)mang dấu – |
