nicholas_chan17
New Member
Download miễn phí Khóa luận Bài toán vận tải ba chỉ số (solid transport problem) không hạn chế và có hạn chế khả năng thông qua, Bài toán vận tải ba chỉ số khoảng (interval solid transport problem) và giới thiệu một số Bài toán vận tải đa mục tiêu
Giải bài toán ISTP thông qua việc đưa sang bài toán phụ STP bằng cách thêm nguồn phát, thu, phương tiện vận tải phù hợp.
Theo cách đó bài toán m nguồn phát, n nguồn thu, l cách vận chuyển được chuyển sang bài toán phụ STP như được trình bày trong Bảng 2.3, và Bảng 2.4, mà có thể giải có hiệu quả cho bài toán chuẩn.
Bài toán phụ trong trường hợp này bao gồm 2m +1, nguồn phát, 2n +1 nguồn thu và 2l +1 cách vận chuyển. Trong số đó có 1 nguồn phát, 1 nguồn thu và 1 cách vận chuyển được gọi là “giả”. Chi phí trong bài toán phụ được thể hiện ở Bảng 2.3.
Trong bài toán phụ, m rằng buộc đầu tiên ứng với mức độ cung cấp nhỏ nhất của nguồn phát và chi phí vận chuyển tương ứng tới nguồn thu. Sau đó là m rằng buộc biểu diễn lượng hàng cung cấp của các nguồn thêm vào nhưng không cần thiết, do đó chi phí vận chuyển tương ứng tới nguồn thu giả bằng cách vận chuyển giả nhận giá trị 0. Rằng buộc cuối thể hiện nguồn phát giả.
Để tải tài liệu này, vui lòng Trả lời bài viết, Mods sẽ gửi Link download cho bạn ngay qua hòm tin nhắn.
Ketnooi -
You must be registered for see links
Ai cần tài liệu gì mà không tìm thấy ở Ketnooi, đăng yêu cầu down tại đây nhé:
Nhận download tài liệu miễn phí
Tóm tắt nội dung tài liệu:
o hàng.
Bắt đầu từ hàng 1: Giả sử c1s = min cik, k = 1, ..., n
Phân phối xis = min(a1, bs).
Nếu x1s = a1 thì xóa dòng 1 rồi tiếp tục quá trình từ dòng 2, b’s = bs - x1s.
Nếu x1s = bs thì xóa cột s rồi tiếp tục quá trình, và lấy a’1 = a1 - x1s.
Phương pháp cực tiểu cước phí theo cột.
Tương tự như phương pháp trên, nhưng xuất phát từ cột thứ 1.
Dùng các phương pháp trên để tìm phương án xuất phát, trong một số lớn các trường hợp, số bước lặp dẫn tới nghiệm giảm đi khá nhiều, nhất là khi giải BTVT mà số điểm phát và thu rất lớn.
2.1.3 Thuật toán
Tiêu chuẩn tối ưu
Định lý 3.1: Phương án X của BTVT là tối ưu Û $ các số ui, i = 1, ..., m và vj, j = 1, ..., n sao cho:
ui + vj Ê cij "(i,j)ẻT (2.14) ui + vj = cij , nếu xij > 0 (2.15)
Các số ui, vj gọi là các thế vị ứng với các điểm phát và thu i,j.
Chứng minh:
Đủ: Giả sử các số ui, vj thỏa mãn (1.13), (1.14). Ta phải chứng minh phương án X = (xij)mxn tương ứng là tối ưu. Muốn vậy, phải chứng minh:
Ê " X’ = (xij)mxn (2.16)
Mặt khác do (1.13), (1.14) tức là:
ui + vj < cij với xij = 0
ui + vj = cij với xij > 0
Nên ta có:
(xij > 0 )
Từ (1.16) và (1.17) ta có (1.15).
Cần:
Xét bài toán đối ngẫu của BTVT .
Giả sử (T) có phương án tối ưu `x ị theo định lý đỗi ngẫu bài toán (T’) có lời giải `z = (`u1, ...,`um,`v1, ...,`vn) tức là $`z. Vì`z là phương án tối ưu, tức cũng là phương án:
`u + `v Ê cij "(i,j)
Mặt khác theo định lý về độ lệch bù
`X,`Z là tối ưu Û = 0
= 0
Nếu`xij > 0 thì PijZ = cij hay`u +`v Ê cij
Thuật toán.
Bước 1: Tìm phương án xuất phát theo 1 trong 4 phương án đễ giới thiệu phần trước.
Bước 2: Kiểm tra phương án:
Nếu các ô sử dụng lập thành chu trình thì ta sử dụng định lý (1.3) để phá chu trình, chuyển phương án xuất phát về phương án cực biên.
Xác định hệ thống các thế vị ui, vj theo định lý 3.1 (công thức 1.15).
Vì giả thiết bài toán không thoái hóa nên tập G = {(i,j) | xij >0} có đúng
m +n -1 ô, do đó có m +n - 1 phương trình.
ui + vj = cij , xij > 0 (2.19)
Để xác định m + n ẩn ui (i=1, ..., m), vj (j=1, ..., n). Như vậy sẽ có một ui hay một vj được xác định tùy ý và m + n -1 ẩn còn lại sẽ xác định duy nhất từ m + n -1 phương trình.
Quy tắc:
Đầu tiên cho ui0 = 0 (i0 thường là dòng đầu tiên hay là dòng chứa 1 ô sử dụng).
Sau đó xác định vj = cij - ui0 cho những cột cắt dòng i0 ở một ô sử dụng.
Bằng quy tắc đó ta xác định được ui và vj cho mọi dòng và cột.
Với mọi ô (i,j) ẻG ta xác định các ước lượng sau đây: Dij sau đây:
Dij = (ui + vj) - cij
Nếu Dij Ê 0, "(i,j) thì phương án đã đánh giá là tối ưu.
Nếu Dij > 0 với ít nhất 1 ô (i,j) thì phương án đã cho chưa tối ưu, ta có thể điều chỉnh để hạ nữa hàm mục tiêu.
Bước 3: Điều chỉnh phương án. Giả sử ô vi phạm tiêu chuẩn tối ưu là (i,j) tức là Di*j* >0 (nếu có nhiều ô vi phạm ta chọn ô ứng với max Dij với hy vọng hàm mục tiêu giảm nhanh nhất).
Ô (i*,j*) ẻG. Bây giờ ta thêm ô (i*,j*) vào tập G. Khi đó tất cả m + n ô sử dụng. Ô (i*,j*) sẽ lập với các ô của G một chu trình K duy nhất. Coi ô (i*,j*) là ô chẵn, tức là (i*,j*) ẻK+. Ta điều chỉnh phương án X để nhận được phương án X’ mà tập G’ không lập thành chu trình ta loại khỏi chu trình 1 ô sử dụng ứng với cực tiểu của (4.1), giả sử là ô (is,js) (Điều chỉnh theo công thức(2.13)).
Đặt xi*j* = xisjs = q > 0
Do đó ô (i*,j*) trở thành ô sử dụng.
G’ = G \ (is,js) ẩ (i*,j*) vẫn gồm m + n -1 không lập thành chu trình.
Ta xác định hệ thống thế vị mới ứng với phương án X’ và G’ và tiếp tục quá trình cho đến khi nào xẩy ra tình huống Dij Ê 0, "(i,j) ị lúc đó ta nhận được phương án tối ưu.
Nếu bài toán không thoái hóa thì sau một số hữu hạn bước ta sẽ đi đến lời giải.
Chú ý: Nếu số ô sử dụng N < m +n - 1 thì thêm (m +n -1) - N ô mới với xij =0 sao cho không tạo thành chu trình.
2.1.4 Ví dụ
Ví dụ: Giải BTVT với các số liệu cho trong bảng sau (Bảng 2.1):
bj
ai
30
25
40
25
20
4
20
2
10
6
45
30
1
5
3
10
8
12
55
5
3
30
9
25
7
Kiểm tra điều kiện cân bằng thu phát:
Lần lặp 1:
Bước 1. Tìm phương án xuất phát bằng phương pháp cực tiểu cước phí trong toàn bảng. Ta được phương án cực biên X (Bảng 2.1).
Bước 2. Phương án X không thoái hóa vì ẵGẵ = m + n - 1 = 6
Tìm các thế vị:
u1 = 0 ị v2 = c12 - u1 = 2 - 0 = 2
u2 = c22 - v2 = 3 - 2 = 1
v1 = c21 - u2 = 1 - 1 = 0
v3 = c23 - u1 = 8 - 1 = 7
u3 = c33 - v3 = 9 - 7 = 2
v4 = c34 - u3 = 7 - 2 = 5
Bước 3. Tính các ước lượng
D11 = u1 + v1 - c11 = 0 + 0 - 4 = -4 < 0
D13 = u1 + v3 - c13 = 0 + 7 - 10 = -3< 0
D14 = u1 + v4 - c14 = 0 + 5 - 6 = -1 < 0
D24 = u2 + v4 - c24 = 1 + 5 - 12 = -6 < 0
D31 = u3 + v1 - c31 = 2 + 2 - 5 = -1 < 0
D32 = u1 + v1 - c11 = 2 + 2 - 3 = 1 > 0
Bước 4. Di*j* = D32 = 1 > 0 ta ghép ô (3,2) vào với G ta được chu trình:
K: (2,2), (2,3), (3,3), (3,2)
lẻ chẵn lẻ chẵn
Bước 5. Phá vỡ chu trình với q = min{xij (i,j)ẻK-} = 5
Ta có bảng mới (Bảng 2.2), Phương án X’.
bj
ai
30
25
40
25
20
4
20
2
10
6
45
30
1
3
15
8
12
55
5
5
3
25
9
25
7
Lần lặp 2:
Bước 2. ẵGẵ = 6
Tìm các thế vị:
u1 = 0 ị v2 = c12 - u1 = 2 - 0 = 2
u3 = c32 - v2 = 3 - 2 = 1
v3 = c33 - u3 = 9 - 1 = 8
u2 = c23 - v3 = 8 - 8 = 0
v1 = c21 - u2 = 1 - 0 = 1
v4 = c34 - u3 = 7 - 1 = 6
Bước 3. Tính các ước lượng
D11 = u1 + v1 - c11 = 0 + 1 - 4 = -3 < 0
D13 = u1 + v3 - c13 = 0 + 8 - 10 = -2 < 0
D14 = u1 + v4 - c14 = 0 + 6 - 6 = 0
D22 = u2 + v2 - c22 = 0 + 2 - 3 = -1 < 0
D24 = u2 + v4 - c24 = 0 + 6 - 12 = -6 < 0
D31 = u3 + v1 - c31 = 1 + 1 - 5 = -3 < 0
Ta có phương án tối ưu là:
x12 = 20, x21 = 30, x23 = 15, x32 = 5, x33 = 25, x34 = 25.
fmin = 20.2 + 30.1 + 15.8 + 5.3 + 25.9 + 25.7 = 605
2.2 Bài toán vận tải ba chỉ số(Solid Transpotion Problem)
2.2.1 Phát biểu bài toán
Một loạt sản phẩm đồng đều được vận chuyển từ một trong m nguồn phát tới một trong n nguồn thu. Các nguồn phát có thể là các nơi sản xuất, các kho hàng, hay các điểm cung cấp được đặc trưng bởi lượng hàng phát ai,, i=1..,m. Nguồn thu là các nơi tiêu thụ, hay các nơi có nhu cầu được đặc trưng bởi mức độ yêu cầu bj, j=1,...,n.
Đặt ek, k=1,...,l là số lượng sản phẩm có thể vận chuyển được bởi một trong l phương án khác nhau hay các phương tiện vận chuyển khác nhau.
cijk ³ 0 là chi phí vận chuyển một đơn vị sản phẩm từ trạm phát i tới trạm thu j bằng phương tiện k.
Mục đích đặt ra của bài toán là cần xác định tất cả các lượng sản phẩm xiịk được vận chuyển từ tất cả các nguồn phát i tới tất cả các nguồn thu j bởi mỗi cách vận chuyển k để cho tổng chi phí vận chuyển là nhỏ nhất.
Về mô hình toán học bài toán STP được phát biểu như sau:
Xác định các số xijk ³ 0 thoả hàm mục tiêu và các ràng buộc sau:
Với các ràng buộc:
Ta có nhận xét mô hình của bài toán STP là dạng tổng quát của mô hình bài toán vận tải hai chỉ số thông thường TP (Transport Problem) nếu chúng ta chỉ nghiên cứu trong một cách vận chuyển duy nhất (l=1).
2.2.2 Một số định nghĩa cơ bản
i) Một bộ giá trị {xijk} i=1, ..., m, j=1, ..., n, k=1, ..., l thoả mãn các ràng buộc được gọi là một phương án của bài toán.
ii) Một phương án mà hệ thống các véc tơ hệ số ứng với các toạ độ dương độc lập tuyến tính gọi là 1 phương án tựa (phương án cực biên).
iii) Một phương án tựa mà số các toạ độ dương đúng bằng hạng của ma trận hệ số gọi là một ph
Bắt đầu từ hàng 1: Giả sử c1s = min cik, k = 1, ..., n
Phân phối xis = min(a1, bs).
Nếu x1s = a1 thì xóa dòng 1 rồi tiếp tục quá trình từ dòng 2, b’s = bs - x1s.
Nếu x1s = bs thì xóa cột s rồi tiếp tục quá trình, và lấy a’1 = a1 - x1s.
Phương pháp cực tiểu cước phí theo cột.
Tương tự như phương pháp trên, nhưng xuất phát từ cột thứ 1.
Dùng các phương pháp trên để tìm phương án xuất phát, trong một số lớn các trường hợp, số bước lặp dẫn tới nghiệm giảm đi khá nhiều, nhất là khi giải BTVT mà số điểm phát và thu rất lớn.
2.1.3 Thuật toán
Tiêu chuẩn tối ưu
Định lý 3.1: Phương án X của BTVT là tối ưu Û $ các số ui, i = 1, ..., m và vj, j = 1, ..., n sao cho:
ui + vj Ê cij "(i,j)ẻT (2.14) ui + vj = cij , nếu xij > 0 (2.15)
Các số ui, vj gọi là các thế vị ứng với các điểm phát và thu i,j.
Chứng minh:
Đủ: Giả sử các số ui, vj thỏa mãn (1.13), (1.14). Ta phải chứng minh phương án X = (xij)mxn tương ứng là tối ưu. Muốn vậy, phải chứng minh:
Ê " X’ = (xij)mxn (2.16)
Mặt khác do (1.13), (1.14) tức là:
ui + vj < cij với xij = 0
ui + vj = cij với xij > 0
Nên ta có:
(xij > 0 )
Từ (1.16) và (1.17) ta có (1.15).
Cần:
Xét bài toán đối ngẫu của BTVT .
Giả sử (T) có phương án tối ưu `x ị theo định lý đỗi ngẫu bài toán (T’) có lời giải `z = (`u1, ...,`um,`v1, ...,`vn) tức là $`z. Vì`z là phương án tối ưu, tức cũng là phương án:
`u + `v Ê cij "(i,j)
Mặt khác theo định lý về độ lệch bù
`X,`Z là tối ưu Û = 0
= 0
Nếu`xij > 0 thì PijZ = cij hay`u +`v Ê cij
Thuật toán.
Bước 1: Tìm phương án xuất phát theo 1 trong 4 phương án đễ giới thiệu phần trước.
Bước 2: Kiểm tra phương án:
Nếu các ô sử dụng lập thành chu trình thì ta sử dụng định lý (1.3) để phá chu trình, chuyển phương án xuất phát về phương án cực biên.
Xác định hệ thống các thế vị ui, vj theo định lý 3.1 (công thức 1.15).
Vì giả thiết bài toán không thoái hóa nên tập G = {(i,j) | xij >0} có đúng
m +n -1 ô, do đó có m +n - 1 phương trình.
ui + vj = cij , xij > 0 (2.19)
Để xác định m + n ẩn ui (i=1, ..., m), vj (j=1, ..., n). Như vậy sẽ có một ui hay một vj được xác định tùy ý và m + n -1 ẩn còn lại sẽ xác định duy nhất từ m + n -1 phương trình.
Quy tắc:
Đầu tiên cho ui0 = 0 (i0 thường là dòng đầu tiên hay là dòng chứa 1 ô sử dụng).
Sau đó xác định vj = cij - ui0 cho những cột cắt dòng i0 ở một ô sử dụng.
Bằng quy tắc đó ta xác định được ui và vj cho mọi dòng và cột.
Với mọi ô (i,j) ẻG ta xác định các ước lượng sau đây: Dij sau đây:
Dij = (ui + vj) - cij
Nếu Dij Ê 0, "(i,j) thì phương án đã đánh giá là tối ưu.
Nếu Dij > 0 với ít nhất 1 ô (i,j) thì phương án đã cho chưa tối ưu, ta có thể điều chỉnh để hạ nữa hàm mục tiêu.
Bước 3: Điều chỉnh phương án. Giả sử ô vi phạm tiêu chuẩn tối ưu là (i,j) tức là Di*j* >0 (nếu có nhiều ô vi phạm ta chọn ô ứng với max Dij với hy vọng hàm mục tiêu giảm nhanh nhất).
Ô (i*,j*) ẻG. Bây giờ ta thêm ô (i*,j*) vào tập G. Khi đó tất cả m + n ô sử dụng. Ô (i*,j*) sẽ lập với các ô của G một chu trình K duy nhất. Coi ô (i*,j*) là ô chẵn, tức là (i*,j*) ẻK+. Ta điều chỉnh phương án X để nhận được phương án X’ mà tập G’ không lập thành chu trình ta loại khỏi chu trình 1 ô sử dụng ứng với cực tiểu của (4.1), giả sử là ô (is,js) (Điều chỉnh theo công thức(2.13)).
Đặt xi*j* = xisjs = q > 0
Do đó ô (i*,j*) trở thành ô sử dụng.
G’ = G \ (is,js) ẩ (i*,j*) vẫn gồm m + n -1 không lập thành chu trình.
Ta xác định hệ thống thế vị mới ứng với phương án X’ và G’ và tiếp tục quá trình cho đến khi nào xẩy ra tình huống Dij Ê 0, "(i,j) ị lúc đó ta nhận được phương án tối ưu.
Nếu bài toán không thoái hóa thì sau một số hữu hạn bước ta sẽ đi đến lời giải.
Chú ý: Nếu số ô sử dụng N < m +n - 1 thì thêm (m +n -1) - N ô mới với xij =0 sao cho không tạo thành chu trình.
2.1.4 Ví dụ
Ví dụ: Giải BTVT với các số liệu cho trong bảng sau (Bảng 2.1):
bj
ai
30
25
40
25
20
4
20
2
10
6
45
30
1
5
3
10
8
12
55
5
3
30
9
25
7
Kiểm tra điều kiện cân bằng thu phát:
Lần lặp 1:
Bước 1. Tìm phương án xuất phát bằng phương pháp cực tiểu cước phí trong toàn bảng. Ta được phương án cực biên X (Bảng 2.1).
Bước 2. Phương án X không thoái hóa vì ẵGẵ = m + n - 1 = 6
Tìm các thế vị:
u1 = 0 ị v2 = c12 - u1 = 2 - 0 = 2
u2 = c22 - v2 = 3 - 2 = 1
v1 = c21 - u2 = 1 - 1 = 0
v3 = c23 - u1 = 8 - 1 = 7
u3 = c33 - v3 = 9 - 7 = 2
v4 = c34 - u3 = 7 - 2 = 5
Bước 3. Tính các ước lượng
D11 = u1 + v1 - c11 = 0 + 0 - 4 = -4 < 0
D13 = u1 + v3 - c13 = 0 + 7 - 10 = -3< 0
D14 = u1 + v4 - c14 = 0 + 5 - 6 = -1 < 0
D24 = u2 + v4 - c24 = 1 + 5 - 12 = -6 < 0
D31 = u3 + v1 - c31 = 2 + 2 - 5 = -1 < 0
D32 = u1 + v1 - c11 = 2 + 2 - 3 = 1 > 0
Bước 4. Di*j* = D32 = 1 > 0 ta ghép ô (3,2) vào với G ta được chu trình:
K: (2,2), (2,3), (3,3), (3,2)
lẻ chẵn lẻ chẵn
Bước 5. Phá vỡ chu trình với q = min{xij (i,j)ẻK-} = 5
Ta có bảng mới (Bảng 2.2), Phương án X’.
bj
ai
30
25
40
25
20
4
20
2
10
6
45
30
1
3
15
8
12
55
5
5
3
25
9
25
7
Lần lặp 2:
Bước 2. ẵGẵ = 6
Tìm các thế vị:
u1 = 0 ị v2 = c12 - u1 = 2 - 0 = 2
u3 = c32 - v2 = 3 - 2 = 1
v3 = c33 - u3 = 9 - 1 = 8
u2 = c23 - v3 = 8 - 8 = 0
v1 = c21 - u2 = 1 - 0 = 1
v4 = c34 - u3 = 7 - 1 = 6
Bước 3. Tính các ước lượng
D11 = u1 + v1 - c11 = 0 + 1 - 4 = -3 < 0
D13 = u1 + v3 - c13 = 0 + 8 - 10 = -2 < 0
D14 = u1 + v4 - c14 = 0 + 6 - 6 = 0
D22 = u2 + v2 - c22 = 0 + 2 - 3 = -1 < 0
D24 = u2 + v4 - c24 = 0 + 6 - 12 = -6 < 0
D31 = u3 + v1 - c31 = 1 + 1 - 5 = -3 < 0
Ta có phương án tối ưu là:
x12 = 20, x21 = 30, x23 = 15, x32 = 5, x33 = 25, x34 = 25.
fmin = 20.2 + 30.1 + 15.8 + 5.3 + 25.9 + 25.7 = 605
2.2 Bài toán vận tải ba chỉ số(Solid Transpotion Problem)
2.2.1 Phát biểu bài toán
Một loạt sản phẩm đồng đều được vận chuyển từ một trong m nguồn phát tới một trong n nguồn thu. Các nguồn phát có thể là các nơi sản xuất, các kho hàng, hay các điểm cung cấp được đặc trưng bởi lượng hàng phát ai,, i=1..,m. Nguồn thu là các nơi tiêu thụ, hay các nơi có nhu cầu được đặc trưng bởi mức độ yêu cầu bj, j=1,...,n.
Đặt ek, k=1,...,l là số lượng sản phẩm có thể vận chuyển được bởi một trong l phương án khác nhau hay các phương tiện vận chuyển khác nhau.
cijk ³ 0 là chi phí vận chuyển một đơn vị sản phẩm từ trạm phát i tới trạm thu j bằng phương tiện k.
Mục đích đặt ra của bài toán là cần xác định tất cả các lượng sản phẩm xiịk được vận chuyển từ tất cả các nguồn phát i tới tất cả các nguồn thu j bởi mỗi cách vận chuyển k để cho tổng chi phí vận chuyển là nhỏ nhất.
Về mô hình toán học bài toán STP được phát biểu như sau:
Xác định các số xijk ³ 0 thoả hàm mục tiêu và các ràng buộc sau:
Với các ràng buộc:
Ta có nhận xét mô hình của bài toán STP là dạng tổng quát của mô hình bài toán vận tải hai chỉ số thông thường TP (Transport Problem) nếu chúng ta chỉ nghiên cứu trong một cách vận chuyển duy nhất (l=1).
2.2.2 Một số định nghĩa cơ bản
i) Một bộ giá trị {xijk} i=1, ..., m, j=1, ..., n, k=1, ..., l thoả mãn các ràng buộc được gọi là một phương án của bài toán.
ii) Một phương án mà hệ thống các véc tơ hệ số ứng với các toạ độ dương độc lập tuyến tính gọi là 1 phương án tựa (phương án cực biên).
iii) Một phương án tựa mà số các toạ độ dương đúng bằng hạng của ma trận hệ số gọi là một ph