Thuật Toán “ Quy 0 Cước Phí Các Ô Chọn” Giải Bài Toán Vận Tải Hàm Mục

Thu

Phát

B1 60

B2 70

B3 40

B4 30

A1 : 100

( 100-60 =40)

0 

-1 

Đưa vào

A2 : 80

0 

Đưara 30

A3 : 20

0 

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

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

Bước 3Còn ô (1,4) có cước phí âm nên PACB hiện có chưa tối ưu.

Bước 4Đưa ô (1,4) vào ta được vòng V = (1,2), (1,4), (2,2), (2,4)

Phân ô chẵn lẻ : VC= (1,2), (2,4), VL= (1,4), (2,2).

Ô đưa ra là ô (2,4) và lượng điều chỉnh là 30.

Thu Phát	B1 60	B2 70	B3 40	B4 30
A1 : 100 ( 100-60 =40)	0  60	0  10	4	-1  30
A2 : 80	1	0  60	0  20	0 0
A3 : 20	3	0	0  20	0
s1 = 0 s2 = 0 s3 = 0 s4 = 1

Lập phương án mới.

r1 = 0

r2 = 0

r3 = 0

Bước 2Qui 0 cước phí

Thu Phát	B1 60	B2 70	B3 40	B4 30
A1 : 100 ( 100-60 =40)	0  60	0  10	4	0  30
A2 : 80	1	0  60	0  20	1 0
A3 : 20	3	0	0  20	1
s1 = 0 s2 = 0 s3 = 0 s4 = 1

Từ hàng 1 cho r1= 0 tính được s1= 0, s2= 0, s4= 1; s2= 0r2= 0; r2= 0s3= 0; s3= 0r3= 0 ; r3= 0 s4= 1.

r1 = 0

r2 = 0

r3 = 0

Tất cả các ô đều có cước phí không âm nên PACB hiện có tối ưu. Vậy PATƯ của bài toán là

60 10

X = 0 60

0 30

20 0 , f

= 460







20 

min

1.6. THUẬT TOÁN THẾ VỊ

1.6.1 Cơ sở toán học của thuật toán.

Thuật toán thế vị được xây dựng dựa trên bài toán đối ngẫu và định lý độ lệch bù yếu . Do đó, để hiểu được cơ sở toán học của thuật toán, bạn đọc cần nắm vững qui tắc thành lập bài toán đối ngẫu và định lý độ lệch bù yếu.

Xét bài toán vận tải (P):

m n

(1) f(x) = cijxijmin

i1 j1





(2) j1

x ij

ai i 1, m



m

i1

b j

j 1, n

(3) xij

 0i  1, m; j  1, n

Bài toán đối ngẫu của bài toán này là (D):

m n

(1) g(u,v) = ui + v j max

i1 j1

(2) ui v j cij , i 1, m, j 1, n

(3) ui, vj tùy ý i 1, m; j 1, n



Cặp ràng buộc đối ngẫu : xij0 ui+ vjcij

Theo định lý độ lệch bù yếu thì

X x

mn

và (U,V) = (ui, vj) i 1, m; j 1, nlà

PATƯ của (P) và (D) khi và chỉ khi

xij(ui + vj - cij) = 0 , i 1, m; j 1, n

Xét bài toán dạng bảng như sau:

Thu phát

B1 b1	B2 b2	…	Bj bj	…	Bn bn
A1 : a1	c11	c12	…	c1j	…	c1n	u1
A2 : a2	c21	c22	…	c2j	…	c2n	u2
			…		…
Ai : ai	ci1	ci2	…	cij	…	cin	ui
			…		…
Am : am	cm1	cm2	…	cmj	…	cmn	um
	v1	v2		vj		vn

Như vậy, ta cần tìm hệ thống các thế vị hàng ui, và thế vị cột vjsao cho :

Tại các ô chọn mà xij> 0 thì ui+ vj- cij= 0

Tại các ô còn lại ui+ vj- cij0

Suy ra, dấu hiệu tối ưu là ui+ vj- cij0 i 1, m; j 1, n

Cách tính ui, vjở đây cũng tương tự như cách tính ri, sjtrong thuật toán “ qui 0 cước phí

các ô chọn”. Tức là ta có thể cho một ẩn

uio

hoặc

v jo

nào đó bằng 0 rồi dựa vào các

ô chọn có xij> 0 để tính các ẩn còn lại sao cho ui+ vj- cij= 0. Tiếp theo tính

đặt

kij

ui+ vj- cij cho tất cả các ô còn lại rồi kiểm tra tính tối ưu.

Nếu kij 0 i 1, m; j 1, nthì PACB hiện có tối ưu.

Nếu tồn tại ô (i,j) nào đó thỏa kij> 0 thì PACB hiện có không tối ưu. Chọn ô có kijdương lớn nhất để đưa vào và các bước tiếp theo tương tư như thuật toán thuật toán “qui 0 cước phí các ô chọn”.

1.6.2 Thuật toán thế vị

Bước 1 : Tìm PACB ban đầu để xuất phát.

Tìm 1 PACB ban đầu bằng phương pháp cực tiểu cước phí hoặc phương pháp Folgels.

Nếu PACB ban đầu có đủ m+n-1 ô thì thì sang bước 2; nếu có ít hơn n+m-1 ô thì bổ sung thêm “ ô chọn 0” cho đủ rồi sang bước 2.

Bước 2 : Tìm hệ thống thế vị hàng, thế vị cột.

Dựa vào các ô chọn có xij> 0 cho một ẩn

uio

hoặc

v jo

nào đó bằng 0 rồi tính

các ẩn còn lại sao cho các ô đó đều thỏa ui+ vj- cij= 0.

cij

kij

xij

đặt

Tính kij ui+ vj- cij ở tất cả các ô còn lại.

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

Nếu kij 0 i 1, m; j 1, nthì PACB hiện có tối ưu.

Nếu tồn tại ô (i,j) nào đó thỏa kij > 0 thì PACB hiện có không tối ưu. Sang bước 4.

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

Tìm ô đưa vào: Ô đưa vào là ô có kij dương lớn nhất ; giả sử đó là ôâ (i*, j*).

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

Phân ô chẵn lẻ của vòng V : Ta đánh số thứ tự các ô của vòng V bắt đầu từ ô (i*, j*), ô này được đánh số 1. Khi đó, V được phân hoạch thành hai tập:

VClà tập các ô có số thứ tự chẵn VLlà tập các ô có số thứ tự lẻ

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

x io jo

minx ij/(i, j) VCthì (io,jo) là ô

đưa ra và

x iojolà lượng điều chỉnh. Tức là, trong các ô có số thứ tự chẵn, ô

ij mn

nào đã phân ít hàng nhất là ô đưa ra và lượng hàng ở ô đó chính là lượng điều chỉnh.

Lập phương án mới:

X ' x' 

xij x 0 0

, với

x'ijđược tính như sau

nếu i, jVC

i j

L

x'ij xij xi0 j0

nếu i, j V

()



xij

nếu i, jV

Lúc này, ô (i*,j*) trở thành ô chọn, ô (io,jo) trở thành ô loại. Quay lại bước 2.

Ví dụ7Giải bài toán vận tải trong ví dụ 6 bằng thuật toán thế vị.

Giải

Bước 1Phương án cực biên ban đầu được tìm như trong ví dụ 6.

Thu Phát	B1 60	B2 70	B3 40	B4 30
A1 : 100	2  60	1  40	4	3
A2 : 80	5	3  30	2  20	6  30
A3 : 20	6	2	1  20	5
v1 =4 v2 = 3 v3 = 2 v4 = 6

Bước 2Tìm hệ thống thế vị hàng và thế vị cột.

u1= -2

cho u2 = 0

u3 = -1

Từ hàng 2 cho u2= 0 tính được v2= 3, v3= 2, v4= 6; v3= 2 u3= -1; v2= 3

u1 = -2 ; u1 = -2v1 = 4.

Thu Phát	B1 60			B2 70			B3 40	B4 30
A1 : 100 ( 100-60 =40)	2		0 60	1		0 40	4 -4	3 1 Đưa vào
A2 : 80	5		-1	3		0 30	2 0 20	6 0 Đưa ra 30
A3 : 20	6		-3	2		0	1 0 20	5 0
		v1 =4			v2 = 3		v3 = 2	v4 = 6

Tính kij = ui+ vj–cij, ghi vào góc trên bên phải mỗi ô ta được :

u1= -2

u2 = 0

u3 = -1

Bước 3Còn ô (1,4) có k14 = 1 > 0 nên PACB hiện có chưa tối ưu.

Bước 4Đưa ô (1,4) vào ta được vòng V = (1,2), (1,4), (2,2), (2,4)

Phân ô chẵn lẻ : VC= (1,2), (2,4), VL= (1,4), (2,2).

Ô đưa ra là ô (2,4) và lượng điều chỉnh là 30.

Thu Phát	B1 60	B2 70	B3 40	B4 30
A1 : 100	2  60	1  10	4	3  30
A2 : 80	5	3  60	2  20	6 0
A3 : 20	6	2	1  20	5
v1 = 2 v2 = 1 v3 = 0 v4 = 3

Lập phương án mới.

cho u1 = 0

u2 = 2

u3 = 1

Bước 2Tìm hệ thống thế vị hàng và thế vị cột.

Phát	Thu	B1 60		B2 70			B3 40			B4 30
A1 : 100 ( 100-60 =40)	2		0 60	1		0 10	4			3		0 30
A2 : 80	5		-1	3		0 60	2		0 20	6		-1 0
A3 : 20	6		-3	2		0	1		0 20	5		-1
			v1 = 2			v2 = 1		v3 = 0		v4 = 3

Từ hàng 1 cho u1= 0 tính được v1= 0, v2= 1, v4= 3; v2= 1u2= 2; u2= 2v3= 0; v3= 0u3= 1 . Tính kij = ui+ vj–cij, ghi vào góc trên bên phải mỗi ô ta được

u1 = 0

u2 = 2

u3 = 1

Tất cả các ô đều có kij0 nên PACB hiện có tối ưu. Vậy PATƯ của bài toán là

60 10



X = 0 60

0

0 30



20 

20 

Vớ du ù8Giải bài toán vận tảicân bằng thu phát sau:

Thu

Phát

B180	B220	B3 60
A1 : 50	5	4	1
A2 : 40	3	2	6
A3 : 70	7	9	11

Giải

Bước 1 Ta tìm phương án cơ bản ban đầu của bài toán bằng phương pháp Folgels.

Thu

Phát

B1 80	B2 20	B3 60 (60-50=10)	Hiệu số
B1 80	B2 20	B3 60 (60-50=10)	lần 1	lần 2	Lần 3
A1 : 50	5	4	1 50	3
A2 : 40 (40-20=20) (20-10=10)	3 10	2 20	6 10	1	1	3
A3 : 70	7 70	9	11	2	2	4
Hiệu số	lần 1	2	2	5(max)
	lần 2	4	7(max)	5
	lần 2	4		5(max)

Tính các hiệu số hàng cột lần 1 ta thấy giá trị lớn nhất ở cột B3. Phân phối tối đa vào ô (1,3) 50 tấn , điểm thu B3chỉ còn cần 10 tấn, xóa hàng A1.

Tính các hiệu số hàng cột lần 2 ta thấy giá trị lớn nhất ở cột B2. Phân phối tối đa vào ô (2,2) 20 tấn , điểm phát A2chỉ còn 20 tấn, xóa cột B2.

Tính các hiệu số hàng cột lần 3 ta thấy giá trị lớn nhất ở cột B3. Phân phối tối đa vào ô (2,3) 10 tấn , điểm phát A2chỉ còn 10 tấn, xóa cột B3.

Đến đây chỉ còn hai ô ở cột 1, ta phân phối vào ô (2,1) 10 tấn và ô (3,1) 70 tấn. Vậy ta có PACB ban đầu .

Bước 2 Qui 0 cước phí :

Từ hàng 2 cho r2= 0 suy ra s1= -3, s2= -2, s3= -6; s3= -6 r1= 5; s1= -3 r3=-4

s1 = -3 s2 = -2 s3 =-6

Tính lại cước phí tất cả các ô ta được

r1= 5

Thu Phát	B1 80	B2 20	B3 60
A1 : 50	5	4	1  50
A2 : 40	3  10	2  20	6  10
A3 : 70	7  70	9	11

cho r2= 0

r3 =-4

Thu

Phát

B180	B220	B3 60
A1 : 50	7	7	0  50
A2 : 40	0  10	0  20	0  10
A3 : 70	0  70	3	1

Tất cả các ô đều có cước phí không âm nên PACB hiện có tối ưu. Vậy PATƯ của bài toán là

Nhận xét

0



X = 10



70

0 50 



20 10 

0 

i) Về mặt cơ sở toán học thì thuật toán “qui 0 cước phí” dễ hiểu hơn thuật toán thế vị. Đối với thuật toán thế vị, cần nắm vững lý thuyết đối ngẫu thì mới có thể hiểu được cơ sở toán học của thuật toán.

ii) Về mức độ phức tạp trong tính toán thì hai thuật toán này như nhau. Vai trò của các rivà sjtương tự như các uivà vj. Tuy nhiên, trong mỗi vòng tính toán của thuật toán, thì thuật toán “qui 0 cước phí” phải lập nhiều hơn thuật toán thế vị 1 bảng.

Đ 2 .CÁC DẠNG KHÁC CỦA BÀI TOÁN VẬN TẢI

2.1. Bài toán vận tải có hàm mục tiêu cực đại.

2.1.1 Nội dung bài toán:

m n

(1) f(x) = cijxij

max





(2) j1

x ij

i j

ai

(i 1, m)

m



x ij b j

i1

(3) xij 0 i,j.

( j 1, n)

Có nhiều bài toán trong thực tế không phải là bài toán vận tải nhưng có dạng giống như bài toán vận tải, chỉ khác là hàm mục tiêu cực đại. Bài toán này được giải bình thường như các bài toán vận tải f(x) min với một số lưu ý sau :

Khi tìm PACB ban đầu thì ưu tiên phân phối vào ô có cước phí lớn nhất (cực đại cước phí ).

Sau khi “qui 0 cước phí các ô chọn” thì phương án cơ bản đang có tối ưu nếu tất cả các ô loại đều có cước phí đều 0.

Khi tìm ô đưa vào thì chọn ô có cước phí dương lớn nhất .

2.1.2. Thuật toán “ quy 0 cước phí các ô chọn” giải bài toán vận tải hàm mục tiêu cực đại:



Bước 1 : Tìm PACB ban đầu để xuất phát bằng phương pháp cực đại cước phí. Ý tưởng phương pháp này là ưu tiên phân phối nhiều nhất vào các ô có cước phí lớn nhất.

Giả sử trong ma trận C c

mn

, crs là lớn nhất trong các cij. Khi đó, ta phân phối tối



ar

nếu

ar bs

(TH1)

đa vào ô (r,s), cụ thể:

x rs

bs

nếu

ar bs

(TH2)



ar

nếu

ar bs

(TH3)

Trong trường hợp 1, điểm phát Arđã phát hết hàng nên có thể xóa đi hàng Ar của bảng; ở điểm thu Bschỉ còn cần (bs– ar) tấn hàng.

Trong trường hợp 2, điểm thu Bsđã nhận đủ hàng, nên có thể xóa đi cột Bscủa bảng và ở điểm phát Archỉ còn lại (ar– bs) tấn hàng.

Trong trường hợp 3, điểm phát Arđã phát hết hàng và điểm thu Bsđã nhận đủ hàng nên có thể xóa đi hàng Arvà cột Bscủa bảng.