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

Chia sẻ: Lan Lan | Ngày: | Loại File: PPT | Số trang:29

Thêm vào BST

Báo xấu

107
lượt xem 12
download

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

A1, …,Am là m trạm phát, có lượng hàng phát ra tương ứng là a1,…,am B1,…, Bn là n trạm thu cần nhập lượng hàng tương ứng là b1,…,bn cij cước phí vận chuyển một đơn vị hàng hóa từ trạm phát Ai đến trạm thu Bj.

Chủ đề:

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

Lưu

Nội dung Text: Bài toán về vận tải

BÀI 3
̣ nghia: 1. Đinh ̃ A1, …,Am là m tram ̣ phat,́ có lượng hang ̀ phat́ ra tương ứng là a1,…,am B1,…, Bn là n tram ̣ thu cân ̀ nhâp̣ lượng hang ̀ tương ứng là b1,…,bn cij cước phí vâṇ chuyên ̉ môṭ đơn vị hang ̀ hoa ́ từ tram ̣ phat́ Ai đêń mtraṃ thun B j. �a = �bi j Thu B1 B2 … Bn ̀ kiên: Điêu ̣ i =1 j =1 Phat́ b1 b2 … bn A1 a1 c11 c12 c1n A2 a2 c21 c22 c2n Am am cm1 cm2 cmn
̀ toan 2. Mô hinh ́ hoc ̣ cua ̉ baì toan ́ vân ̣ tai: ̉ Goị xij là khôí lượng hang ̀ ́ ta sẽ vân hoa ̣ chuyên ̉ từ tram ̣ phat́ Ai đên ́ tram ̣ thu Bj (i = 1,..,m; j = 1,…,n), ta có mô ̀ hinh: m n � � cij xij min i=1 j =1 n xij = ai , i = 1,..., m j =1 m xij = b j , j = 1,..., n i=1 xij 0, i = 1,..., m; j = 1,..., n
3. Phương an ́ cua ̉ baì toan ́ vân ̣ tai: ̉ Môṭ phương an ́ cua ̉ baì toan ́ vân ̣ taỉ là môṭ ma trân ̣ X 0 = ( xij0 ) trong đó x0 ij là cac ́ số không âm sao m n cho: n m x = ai , i = 1,..., m và 0 ij x = b j , j = 1,..., n 0 ij j =1 i =1
4. Phương an ́ cơ ban ̉ cua ̉ baì toan ́ vân ̣ tai: ̉ ̣ : trong môṭ phương an - Ô chon ́ cơ ban ̉ cua ̉ baì toan ́ ̣ taỉ cac vân ́ ô có lượng hang ̀ dương được goị là ô ̣ cac chon, ́ ô có lượng hang ̀ ̀ băng 0 được goị là ô loai. ̣ ̀ - Vong: Môṭ day ̃ cac ́ ô chon ̣ cua ̉ môṭ phương an ́ nao ̀ đó được goị là tao ̣ nên môṭ vong ̀ nêu ́ môĩ ô trong day ̃ ô đó đêu ̀ phaỉ năm ̀ trên cung ̀ môṭ dong ̀ (côt) ̣ chỉ với môṭ ô đứng trước nó đông ̀ thời phaỉ năm ̀ trên cung ̀ môṭ côṭ (dong) ̀ chỉ với môṭ ô đứng sau no.́
̀ thường có dang Vong ̣ sau: * * * * * * * * * * * * * * * *  Số ô chon ̣ trong vong ̀ luôn là môṭ số chăn: ̃
Phương an ́ cơ ban: ̉ môṭ PA cua ̉ baì toan ́ vân ̣ taỉ được goị là PA cơ ban ̉ nêu ́ cac ́ ô chon ̣ cua ̉ PA đó không tao ̣ ̀ vong. thanh ̀ Chú y:́  Môṭ phương an ́ cua ̉ baì toan ́ vân ̣ taỉ có m + n ô ̣ trở lên luôn là môṭ phương an chon ́ không cơ ban. ̉  PACB có số ô chon ̣ băng ̀ m + n -1 goị là PACB ́ không suy biên  PACB có số ô chon ̣ nhỏ hơn m + n – 1 goị là PACB ́ suy biên  “Ô choṇ không” là ô loaị được bổ sung để có ́ PACB không suy biên.
5. Xây dựng phương an ́ cơ ban: ̉ a. Phương phap ́ tây – băc: ́ Ưu tiên phân phôí tôí đa hang ̀ lân ̀ lượt vao ̀ cac ́ ô ở phiá Tây băc ́ cua ̉ bang ̉ cho đên ́ khi cac ́ tram ̣ phat́ phat́ hêt́ hang̀ và cac ́ tram ̣ thu nhân ̣ đủ hang. ̀ Ví du:̣ B1:25 B2:25 B3:10 A1:10 5 3 1 A2:30 7 6 8 A3:20 3 2 2
b. Phương phap ́ cước phí thâp ́ nhât: ́ Ưu tiên phân phôí tôí đa hang̀ lâǹ lượt vao ̀ cać ô có cước phí thâp ́ nhât́ cho đên ́ khi cać tram ̣ phat́ phat́ hêt́ hang̀ và cac ́ traṃ thu nhân ̣ đủ hang. ̀ Ví du:̣ B1:25 B2:25 B3:10 A1:10 5 3 1 A2:30 7 6 8 A3:20 3 2 2
6. Tính chất của bài toán vận tải: Tính chất 1: Mọi bài toán vận tải đều có PATƯ. Tính chất 2: Số ô chọn trong một phương án cơ bản của một bài toán vận tải không bao giờ vượt quá m + n – 1 ô. Tính chất 3: Khi thêm vào một phương án cơ bản không suy biến của một bài toán vận tải một ô chọn thì ô chọn đó cũng tạo với một số ô chọn của phương án thành một vòng duy nhất.
7. Giải bài toán vận tải bằng phương pháp thế vị: Bước 1: Lập PACB không suy biến xuất phát 1) Xây dựng PACB xuất phát. 2) Kiểm tra tính không suy biến của PACB xuất phát:  Trường hợp 1: Nếu tổng số ô chọn là m + n – 1 thì PACB xuất phát là phương án không suy biến, ta chuyển qua bước 2.  Trường hợp 2: Nếu tổng số ô chọn < m + n – 1 thì ta phải bổ sung vào PACB xuất phát một số “ô chọn không” để được một phương án không suy biến trước khi chuyển sang bước 2.
Bước 2: Đánh giá tính tối ưu của PACB xuất phát. 1) Xây dựng hệ thống thế vị (ui, vj). Hệ thống thế vị (ui, vj) của PACB xuất phát được xây dựng theo công thức ui + vj = cij.
2) Tính các hệ số ước lượng Δij. Các hệ số ước lượng của các số được tính theo quy tắc sau: Hệ số ước lượng của các ô chọn là 0. Hệ số ước lượng của ô loại (i, j) được tính theo công thức Δij = ui + vj – cij
3) Đánh giá tính tối ưu của PACB xuất phát.  Trường hợp 1: nếu các hệ số ước lượng ở các ô đều không dương thì PACB xuất phát là PATƯ của bài toán, thuật toán kết thúc với PATƯ là PACB xuất phát.  Trường hợp 2: Nếu có một ô loại có hệ số ước lượng dương thì PACB xuất phát chưa tối ưu, bài toán tiếp tục bằng cách lập PACB mới. Chú ý: nếu các hệ số ước lượng của các ô loại đều là số âm thì PACB xuất phát là PATƯ duy nhất của bài toán. Ngược lại thì bài toán có thể có nhiều PACB tối ưu.
Bước 3: Xây dựng PACB mới. 1) Tìm ô loại đưa vào hệ thống ô chọn. Ô loại được đưa vào làm ô chọn trong PACB mới là ô có hệ số ước lượng dương lớn nhất.
Bước 3: Xây dựng PACB mới. 2) Tìm ô đưa ra khỏi hệ thống ô chọn  Để xác định được ô đưa ra khỏi hệ thống ô chọn ta phải thực hiện các công việc sau:  Tìm vòng điều chỉnh: Từ ô chọn mới đưa vào ta nối với ô chọn còn lại để tìm vòng gọi là vòng điểu chỉnh.  Xác định ô chẵn, lẽ trong vòng điều chỉnh: Lấy ô mới đưa vào làm ô số 1, ta đánh số các ô trong vòng điều chỉnh. Các ô 1,3,… là ô lẽ; các ô 2, 4, … là các ô chẵn.  Tìm ô chẵn có lượng hàng nhỏ nhất. Ô chẵn có lượng hàng q nhỏ nhất là ô được đưa ra khỏi hệ thống ô chọn. Lượng hàng q gọi là lượng
Bước 3: Xây dựng PACB mới. 3) Cải tiến phương án PACB mới được xây dựng theo quy tắc sau: Các ô lẽ trong vòng điều chỉnh được cộng vào lượng hàng điều chỉnh. Các ô chẵn trong vòng điều chỉnh bị trừ đi lượng hàng điều chỉnh. Các ô còn lại giữ nguyên lượng hàng.
Bước 4: Đánh giá tính tối ưu của PACB mới Được thực hiện như bước 2. Chú ý: a) Khi bổ sung “ô chọn không” hay chọn ô đưa vào: nếu có nhiều ô cùng thỏa mãn điều kiện thì ta nên ưu tiên chọn các ô ở phía tây – bắc. b) Khi ô đưa ra, nếu lượng hàng nhỏ nhất trong các ô chẵn của vòng điều chỉnh là 0 thì ô đó vẫn được chọn làm ô đưa ra. Trong trường hợp này, PACB vẫn không thay đổi nhưng hệ thống ô chọn có thay đổi, kết quả đánh giá tính tối ưu của PACB có thể thay đổi.
Ví dụ 1: Giải bài toán vận tải sau: 20 40 30 30 1 3 5 25 5 4 2 35 8 5 4
Giải: Bằng phương pháp cước phí thấp nhất ta lập được PACB xuất phát sau: 20 40 30 1 3 5 30 20 10 0 5 4 2 25 0 0 25 8 5 4 35 0 30 5 Số ô chọn là 5 = 3 + 2 – 1 nên phương án trên không suy biến.