Thuật Toán “Quy O Cước Phí Các Ô Chọn”

Ví dụ 1: Tìm phương án cơ bản ban đầu

B1 = 76	B2 = 62	B3 = 88	B4 = 45	B5 = 40
A1 = 79	10	19	15	6	7
A2 = 102	13	11	8	7	4
A3 = 70	12	17	10	5	3
A4 = 60	12	18	18	9	10

Có thể bạn quan tâm!

Xem toàn bộ 152 trang tài liệu này.

Bảng 1

Đây là bài toán cân bằng thu phát ∑ ai = ∑ bj = 311

Nhìn trên toàn bảng 1, ta thấy ô có cước phí = 3 là cước phí nhỏ nhất.

min{70 , 40} = 40 nên ta phân cho ô này lượng hàng là 40. Khi đó trạm thu B5 đã nhận đủ hàng nên ta gạch bỏ trạm này ra khỏi bảng, lượng hàng còn lại ở trạm phát A3 là 30. Khi đó ta có bảng sau:

B1 = 76	B2 = 62	B3 = 88	B4 = 45	B5 = 40
A1 = 79	10	19	15	6	7
A2 = 102	13	11	8	7	4
A3 = 70 – 40	12	17	10	5	3 40
A4 = 60	12	18	18	9	10

Bảng 2

Nhìn trên toàn bảng 2, ta thấy ô có cước phí = 5 là cước phí nhỏ nhất.

min{30 , 45} = 30 nên ta phân cho ô này lượng hàng là 30. Khi đó trạm phát A3 đã phát hết hàng nên ta gạch bỏ trạm này ra khỏi bảng, lượng hàng còn lại ở trạm thu B4 là 15. Khi đó ta có bảng sau:

B1 = 76	B2 = 62	B3 = 88	B4 = 45 – 30	B5 = 40
A1 = 79	10	19	15	6	7
A2 = 102	13	11	8	7	4
A3 = 70 – 40	12	17	10	5 30	3 40
A4 = 60	12	18	18	9	10

Cứ tiếp tục quá trình trên cho đến khi ta thu được PACB ban đầu như sau:

Bj Ai

B1 = 76

B2 = 62

B3 = 88

B4 = 45 – 30

B5 = 40

A1 = 79

A2 = 102

A3 = 30

A4 = 60

Ví dụ 2: Tìm PACB ban đầu

30	45	50	25
60	6	2	7	4
70	8	4	1	7
20	3	9	2	1

Ví dụ 3: Tìm PACB ban đầu

40	55	50	15
60	6	2	7	4
70	8	4	1	7
20	3	9	2	1
30	7	3	8	2

3.1.3. Thuật toán “Quy O cước phí các ô chọn”

Thuật toán gồm 3 bước:

Bước 1: Quy O các ô chọn

1) Giả sử đã có một PACB ban đầu với m + n – 1 ô chọn (có thể có một số ô

“chọn O”).

2) Ta cộng vào hàng i của ma trận cước phí C số ui (i=1, 2, . . ., m) và cộng vào cột j số vj (j=1, 2, . . ., n), ta được ma trận cước phí mới C’ = (c’ij)m x n

c’ij = cij + ui + vj

3) Ta chọn các số ui và vj sao cho ở ma trận cước phí mới C’sao cho: tại các ô chọn đều có có cước phí mới c’ij = 0.

Để làm được điều này, ta chỉ cần cho ui* hoặc vj* bằng một số nào đó tại một ô chọn (i* , j*) bất kỳ, sau đó ta dựa vào việc làm cho các ô chọn có cước phí bằng 0, ta có thể suy ra các ui và vj cần tìm.

Do có việc làm cho các ô chọn bằng 0 nên phương pháp này được gọi là “Quy O cước phí các ô chọn”

Bước 2: Kiểm tra tính tối ưu

1) Nếu sau khi quy 0 cước phí các ô chọn, mà các ô loại đều có cước phí  0 thì phương án đang xét là phương án tối ưu.

2) Nếu sau khi quy 0 cước phí các ô chọn, mà có ít nhất một ô loại có cước phí < 0, thì phương án đang xét chưa phải là tối ưu và ta chuyển sang bước 3.

Bước 3: Xây dựng phương án mới tốt hơn

1) Tìm ô đưa vào: Giả sử ô (i* , j*) có cước phí âm nhỏ nhất. Ô (i* , j*) là ô đưa vào.

2) Tìm vòng điều chỉnh: Bổ xung ô (i* , j*) vào m + n – 1 ô chọn ban đầu sẽ xuất hiện một vòng duy nhất là V gọi là vòng điều chỉnh.

3) Phân ô chẵn lẻ của vòng V:

Ta đánh dấu các ô của vòng V bắt đầu từ ô (i* , j*) có dấu “+”, ô tiếp theo có dấu “ - ”, ô tiếp theo lại đánh dấu “+” . . . cứ như thế cho đến khi ta đánh dấu xong vòng V . Khi đó, vòng V phân thành 2 lớp:

V - : Các ô đánh dấu “ – ”

V+ : Các ô đánh dấu “+” (chứa “ô chọn 0” là ô(i* , j*))

x

4) Tìm ô đưa ra và lượng điều chỉnh:

Giả sử:

min x

( i, j)V 

ij rs

Khi đó: ô (r , s) là ô đưa ra và xrs là lượng điều chỉnh

5) Lập phương án mới: X’ = [x’ij]mxn được tính như sau:



ij ij rs

x x, x

x khi (i, j) V

ij rs

x khi (i, j) V



x khi (i, j) V

Sau khi lập phương án mới, ta lại quay lại bước 1, rồi bước 2 . . . Cứ tiếp tục như vậy, vì bài toán vận tải luôn có phương án tối ưu và số phương án cơ bản là hữu hạn nên sau hữu hạn lần điều chỉnh phương án, ta có phương án tối ưu.

Ví dụ 1:Giải bài toán vận tải sau

25	20	15	40
30	3	4	6	1
50	1	5	3	3
20	4	2	7	2

Đây là bài toán cân bằng thu phát

1) PACB ban đầu là

Trong PACB ban đầu này, chưa đủ m + n – 1 ô chọn nên ta có bổ xung thêm “ô chọn O” không tạo thành vòng, đó là ô (3 , 4)

2) Ta quy O các ô chọn

Cho u1 = 0, dựa vào các ô chọn ta tìm được các số ri và sj như sau:

u1 = 0

u2 = -2

u3 = -1

v1 = 1

v2 = -1

v3 = -1

v4 = -1

Sau đó, cộng ui và vj vừa tìm được vào cước phí của ô (i , j), ta được ma trận cước phí mới như sau (lập bảng cước phí mới):

Ta thấy các ô loại đều có cước phí mới ≥ 0, nên phương án đang xét là PA tối ưu. Kết luận:

0 0 0 30 



- PA tối ưu là: x = 25 0 15 10 

0 20 0 0 



- Chi phí tối ưu là: F(x) = 170

Ví dụ 2: Giải bài toán vận tải sau:

35	20	40	30
20	1	4	7	2
30	3	4	1	9
50	1	6	3	4
25	3	4	5	7

Đây là bài toán vận tải cân bằng thu phát

Lặp lần 1:

1) Tìm PACB ban đầu

35	20	40	30
20	1	4	7	2 20
30	3	4	1 30	9
50	1 35	6	3 10	4 5
25	3	4 20	5	7 5

Trong PACB ban đầu này, đã đủ m + n – 1 ô chọn, do đó ta chuyển sang bước sau:

2) Quy O ô chọn và kiểm tra PA tối ưu

Cho u1 = 0, dựa vào các ô chọn ta tìm được các số ui và vj như sau:

4	7	2 20	u1 = 0
3	4	1 30	9	u2 = 0
1 35	6	3 10	4 5	u3 = -2
3	4 20	5	7 5	u4 = -5
v1 = 1	v2 = 1	v3 = -1	v4 = -2

Sau đó, cộng ui và vj vừa tìm được vào cước phí của ô (i , j), ta được ma trận cước phí mới như sau (lập bảng cước phí mới):

-1

Nhìn vào ma trận cước phí mới, ta thấy tồn tại ô có cước phí < 0. Ta tìm ô có cước phí âm nhỏ nhất – ô đó là ô đưa vào (i* , j*) = (4,1) làm ô chọn (nếu có nhiều ô có cước phí