ketnoitimban
New Member
Download miễn phí Khóa luận Bài toán vận tải ba chỉ số khoảng (interval solid transport problem)
Có m địa điểm A1, A2, ., An cùng sản xuất một loại hàng hóa với các lượng hàng tương ứng là a1, a2, ., an.
Có n nơi tiêu thụ loại hàng hóa đó B1, B2, ., Bn với các yêu cầu tương ứng là b1, b2, ., bn.
Để đơn giản ta sẽ gọi
Ai là điểm phát i, i=1, ., m
Bj là điểm thu j, j=1, ., n
Hàng có thể chở từ một điểm phát bất kỳ (i) đến một điểm thu bất kỳ (j)
Ký hiệu:
cij - chi phí chuyên chở một đơn vị hàng từ điểm phát (i) đến điểm thu (j).
xij - lượng hàng chuyên chở từ (i) đến (j).
Bài toán đặt ra là: xác định những đại lượng xij cho mọi con đường (i,j) sao cho tổng chi phí chuyên chở là nhỏ nhất với giả thiết là:
Để tải bản Đầy Đủ của tài liệu, xin Trả lời bài viết này, Mods sẽ gửi Link download cho bạn sớm nhất qua hòm tin nhắn.
Ai cần download tài liệu gì mà không tìm thấy ở đây, thì đă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:
iể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ý 2.4: 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 (2.14), (2.15). 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 (2.14), (2.15) tức là:
ui + vj < cij với xij = 0
ui + vj = cij với xij > 0
Nên ta có:
(xij > 0 )
Từ (2.17) và (2.18) ta có (2.16).
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ý (2.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ý 2.4 (công thức 2.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 vector 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ương án tựa không suy biến.
iv) Một phương án làm cực tiểu hàm chi phí được gọi là một phương án tối ưu.
v) Ta gọi một tập hợp các ô (i,j,k) tạo thành một vòng nếu các vec...