Kiểm Tra Tính Tối Ưu Của Lời Giải Bằng Phương Pháp Modi

Căn cứ vào kết quả tính toán trên, ta nên chọn địa điểm A để bố trí tổng đài.

4.1.3.3. Phương pháp tọa độ trung tâm

Phương pháp này chủ yếu được dùng để lựa chọn địa điểm bố trí doanh nghiệp trung tâm hoặc kho hàng trung tâm có nhiệm vụ cung cấp hàng hoá cho nhiều địa điểm tiêu thụ khác nhau. Mục tiêu của phương pháp là tìm được địa điểm sao cho tổng quãng đường vận chuyển lượng hàng hoá đến các địa điểm tiêu thụ là nhỏ nhất. Phương pháp toạ độ trung tâm coi chi phí tỷ lệ thuận với khối lượng hàng hoá và khoảng cách quãng đường vận chuyển. Mỗi địa điểm tương ứng với toạ độ có hoành độ X và tung độ Y.

Toạ độ của địa điểm đặt doanh nghiệp được xác định như sau:

Trong đó:

XiQi

Xt = Qi và Yt

YiQi

=Qi (4.2)

Xt : hoành độ x của điểm bố trí doanh nghiệp; Yt : tung độ y của điểm bố trí doanh nghiệp ; Xi : hoành độ x của địa điểm i;

Yi : tung độ y của địa điểm i;

Qi :khối lượng hàng hoá cần vận chuyển từ trung tâm tới địa điểm i.

Ví dụ: Doanh nghiệp X cần lựa chọn vị trí đặt trung tâm phân phối chính. Biết toạ độvà khối lượng hàng hoá cần vận chuyển từ trung tâm chính đến các địa điểm khác như sau:

Địađiểm

ToạđộX	ToạđộY	Khốilượngvậnchuyển
A	8	15	250
B	11	16	800
C	10	14	400
D	17	15	320
E	12	21	210
F	9	16	350
G	10	18	150

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

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

Yêucầu: Xácđịnhvịtrítrungtâmphânphốichính. Xácđịnhtoạđộbốtrítrungtâmphânphốichính:

Xt = 250x8+800x11+400x10+320x17+210x12+350x9+150x10=11,05 250+800+400+320+210+350+150

Yt = 250x15+800x16+400x14+320x15+210x21+350x16+150x18 =15,99 250+800+400+320+210+350+150

Theo kết quả tính toán, vị trí trung tâm phân phối chính có toạ độ (11,05; 15,99) gần với địađiểm B nhất. Như vậy ta chọn địa điểm B để đặt trung tâm phân phối.

4.1.3.4. Phương pháp bài toán vận tải

Mục tiêu của phương pháp này là xác định cách vận chuyển hàng có lợi nhất từ nhiều điểm sản xuất (cung cấp) đến nhiều nơi phân phối (thị trường) sao cho có tổng chi phí vận chuyển nhỏ nhất.

Để xây dựng và giải bài toán vận tải cần có các thông tin sau:

- Danh sách các nguồn sản xuất cung cấp hàng hóa;

- Danh sách các địa điểm tiêu thụ và nhu cầu của từng địa điểm;

- Chi phí chuyên chở một đơn vị sản phẩm từ địa điểm cung cấp đến nơi tiêu thụ.

Với các thông tin đó, ta lập ma trận vận tải trong đó có cột nguồn và cột địa điểm tiêu thụ cùng với các số liệu về tổng số lượng cung và tiêu thụ của địa điểm, cùng với chi phí vận chuyển 1 đơn vị sản phẩm. Bài toán vận tải được giải theo ba bước:

- Bước 1: Tìm giải pháp ban đầu;

- Bước 2: Kiểm tra tính tối ưu của giải pháp ban đầu;

- Bước 3: Cải tiến để tìm phương án tối ưu.

a. Tìm giải pháp ban đầu

Tìm giải pháp ban đầu có thể thực hiện bằng nhiều phương pháp. Chúng ta xem xét một trong các phương pháp đó là phương pháp trực quan. Phương pháp trực quan bắt đầu từ ô có chi phí thấp nhất. Cách giải gồm các bước chủ yếu sau:

Bước 1: Tìm ô có chi phí vận chuyển đơn vị sản phẩm nhỏ nhất.

Bước 2: Phân bổ tối đa lượng sản phẩm có thể được vào ô đó và gạch một đường thẳng qua hàng hoặc cột đã dùng hết.

Bước 3: Tìm ô có chi phí thấp nhất trong những ô còn lại.

Bước 4: Lặp lại bước 2 và bước 3 cho đến khi tất cả khối lượng hàng hóa được phân bổ hết.

Ví dụ: Hãy tìm giải pháp ban đầu của bài toán vận tải sau:

Địa điểm tiêu thụ A		Địa điểm tiêu thụ B		Địa điểm tiêu thụ C		Địa điểm tiêu thụ D		Cung
Nhà máy 1		4		7		7		1	100

Nhà máy 2		12		3		8		8	200

Nhà máy 3		8		10		16		5	150

Cầu	80		90		120		160		450 450

Giải pháp ban đầu được xác định như sau:

Bảng 4.3: Giải pháp ban đầu của bài toán vận tải

Địa điểm tiêu thụ A		Địa điểm tiêu thụ B		Địa điểm tiêu thụ C		Địa điểm tiêu thụ D		Cung
Nhà máy 1		4		7		7		1	100
							100
Nhà máy 2		12		3		8		8	200
			90		110
Nhà máy 3		8		10		16		5	150
	80				10		60
Cầu	80		90		120		160		450 450

Tổng chi phí vận chuyển theo phương án này là: (100 x 1) + (90 x 3) + (110 x 8)

+ (80 x 8) + (10 x 16) + (60 x 5) = 2350.

b. Kiểm tra tính tối ưu của lời giải

Cách giải trên cho thấy kết quả là một phương án có thể phân bổ. Nhưng phương án đó liệu đã phải phương án tối ưu hay chưa? Để khẳng định kết quả đã phải tối ưu hay chưa và giúp chúng ta tìm phương án tối ưu, có thể dùng phương pháp chuyển ô và phương pháp MODI.

Phương pháp chuyển ô

Phương pháp chuyên ô phân tích từng ô chưa sử dụng để xác định xem tổng chi phí vận chuyển còn có thể giảm được nữa không. Nguyên tắc thực hiện là chuyển một đơn vị sản phẩm vào ô trống và đánh giá xem chi phí tăng lên hay giảm đi. Nếu chi phí chuyển ô không giảm, phương án là lời giải tối ưu. Ngược lại, nếu chi phí chuyển ô giảm xuống có nghĩa là lời giải chưa tối ưu.

Các bước tiến hành:

1. Chọn một ô chưa sử dụng để đánh giá. Giả sử ta chuyển một đơn vị sản phẩm từ ô đã sử dụng sang ô đó. Vẽ một đường đi của sản phẩm đó theo đường khép kín quay về ô trống ban đầu, đi qua các ô đã sử dụng;

2. Đặt dấu (+) ở ô xuất phát vừa lựa chọn và tuần tự đến dấu (-) rồi lại (+) ở mỗi ô là các góc của đường khép kín vẽ được đi qua;

3. Tính chỉ số cải tiến bằng cách lấy tổng của tất cả các chi phí đơn vị ở các ô chứa dấu cộng và trừ đi tổng chi phí đơn vị của tất cả các ô có chứa dấu trừ;

4. Lặp lại các bước cho đến khi tính được giá trị cải tiến của tất cả các ô chưa dùng đến.

Nếu mọi giá trị tính ra đều lớn hơn hoặc bằng không thì phương án giải trước là tối ưu. Nếu có giá trị âm thì có thể cải tiến để giảm chi phí và tìm giải pháp tối ưu.

Áp dụng cho ví dụ ở trên, tiến trình được thực hiện qua các bảng sau đây: Đối với ô 1 – A:

Bảng 4.4: Phương pháp chuyển ô đối với ô 1 - A

100

110

Địa điểm tiêu thụ A

Địa điểm tiêu thụ B

Địa điểm tiêu thụ C

Địa điểm tiêu thụ D

Cung

Nhà máy 1

100

Nhà máy 2

200

Nhà máy 3

150

Cầu

120

160

450

Chi phí cải tiến của ô 1 – A là: (4 + 5) – (1 + 8) = 0

Tương tự ta có chỉ tiêu cải tiến của ô 1 – B là: (7 + 5 + 8) – (1 + 16 + 3) = 0

Bảng 4.5: Phương pháp chuyển ô đối với ô 1 - B

110

Địa điểm tiêu thụ A

Địa điểm tiêu thụ B

Địa điểm tiêu thụ C

Địa điểm tiêu thụ D

Cung

Nhà máy 1

100

Nhà máy 2

200

Nhà máy 3

150

Cầu

120

160

450

Ô 1 – C có chỉ tiêu cải tiến là -5:

	Địa điểm tiêu thụ A		Địa điểm tiêu thụ B		Địa điểm tiêu thụ C		Địa điểm tiêu thụ D		Cung
Nhà máy 1		4		7	+	7		1	100
							100

Nhà máy 2		12		3	110	8		8	200
			90
Nhà máy 3		8		10		16		5	150
	80				- 10		60 +
Cầu	80		90		120		160		450 450

Bảng 4.6: Phương pháp chuyển ô đối với ô 1 - C

Ô 2 – A có chỉ tiêu cải tiến là 12:

	Địa điểm tiêu thụ A		Địa điểm tiêu thụ B		Địa điểm tiêu thụ C		Địa điểm tiêu thụ D		Cung
Nhà máy 1		4		7		7		1	100
							100
Nhà máy 2		12		3		8		8	200
	+				110
			90
Nhà máy 3		8		10		16		5	150

	80 -				10 +		60
Cầu	80		90		120		160		450 450

Bảng 4.7: Phương pháp chuyển ô đối với ô 2 - A

Ô 2 – D có chỉ tiêu cải tiến là + 11:

Bảng 4.8: Phương pháp chuyển ô đối với ô 2 - D

	Địa điểm tiêu thụ A		Địa điểm tiêu thụ B		Địa điểm tiêu thụ C		Địa điểm tiêu thụ D		Cung
Nhà máy 1		4		7		7		1	100
							100
Nhà máy 2		12		3		8		8	200
			90				+

Nhà máy 3		8		10		16		5	150
	80				10 +		60 -
Cầu	80		90		120		160		450 450

110

Ô 3 – B có chỉ tiêu cải tiến là -1:

Bảng 4.9: Phương pháp chuyển ô đối với ô 3 - B

Địa điểm tiêu thụ A		Địa điểm tiêu thụ B		Địa điểm tiêu thụ C			Địa điểm tiêu thụ D		Cung
Nhà máy 1		4		7			7		1	100
								100
Nhà máy 2		12	- 90	3			8		8	200
					110	+
Nhà máy 3		8	+	10			16		5	150

	80				10 -			60
Cầu	80		90		120			160		450 450

Như vậy, chỉ có hai ô có chỉ tiêu âm là 3-B giá trị - 1 và 1-C giá trị - 5. Vậy, giải pháp trên chưa phải là tối ưu.

Phương pháp MODI

Cách thứ hai là dùng phương pháp MODI để kiểm tra tính tối ưu của lời giải:

Bảng 4.10: Kiểm tra tính tối ưu của lời giải bằng phương pháp MODI

	Địa điểm tiêu thụ A		Địa điểm tiêu thụ B		Địa điểm tiêu thụ C		Địa điểm tiêu thụ D		Cung
Nhà máy 1		4		7		7		1	100
							100
Nhà máy 2		12		3		8		8	200
			90		110
Nhà máy 3		8		10		16		5	150
	80				10		60
Cầu	80		90		120		160		450 450

M1 M2 M3 M4

N1 N

Gọi: Ni là trị số phân bố của hàng i Mj là trị số phân bố của cột j

Cij là chi phí đơn vị trong ô ij Đặt Ni + Mj = Cij

Lập các phương trình cho tất cả các ô đã dùng theo công thức trên. Giải hệ phương trình bằng cách cho Ni = 0.

Tính chỉ số cải tiến cho các ô chưa dùng theo công thức:

Kij = Cij - Ni - Mj (4.3)

Ví dụ trên ta có:

N1 + M4 = 1 N2 + M2 = 3 N2 + M3 = 8 N3 + M1 = 8 N3 + M3 =16 N3 + M4 = 5

Khi N1 = 0 thì N2 = -4; N3 = 4; M4 = 1; M2 = 7; M3 = 12; M1 = 4.

Tính chỉ tiêu cải tiến:

Ô 1 – A: C11– N1– M1 = 4 – 0 – 4 = 0

Ô 1 – B: C12– N1– M2 = 7 – 0 – 7 = 0

Ô 1 – C: C13– N1– M3 = 7 – 0 – 12 = -5

Ô 2 – A: C21– N2– M1 = 12 – (-4) – 4 = 12

Ô 2 – D: C24– N2– M4 = 8 – (-4) – 1 = 11

Ô 3 – B: C32– N3– M2 = 10 – 4 – 7 = -1

Như vậy, theo cách giải này ta cũng có các chỉ tiêu cải tiến đúng như phương pháp chuyển ô bên trên.

c. Cải tiến để tìm phương án tối ưu

Bây giờ để tìm phương án tối ưu có nghĩa là tìm phương án có chi phí thấp nhất, ta chọn ô có chỉ tiêu cải tiến với giá trị âm nhỏ nhất để chuyển sản phẩm sang từ những ô có chỉ tiêu cải tiến cao hơn theo đúng tuyến đường như khi thực hiện chuyển ô. Nhưng ở đây thay vì chuyển 1 đơn vị sản phẩm ta chuyển tối đa số sản phẩm có thể chuyển được. Số sản phẩm tối đa chuyển được là số sản phẩm nhỏ nhất trong các ô mang dấu (-).

Sau khi chuyển, cần tính lại các chỉ tiêu, nếu tất cả đều lớn hơn hoặc bằng không thì đã thu được giải pháp tối ưu. Nếu còn giá trị âm cần tiếp tục thực hiện chuyển cho đến khi không còn chỉ tiêu cải tiến âm nữa.

Tiếp tục ví dụ trên ta chọn ô 1 – C có giá trị -5 và giá trị tối đa có thể chuyển được là 10 đơn vị sản phẩm.

	Địa điểm tiêu thụ A		Địa điểm tiêu thụ B		Địa điểm tiêu thụ C		Địa điểm tiêu thụ D		Cung
Nhà máy 1		4		7	+	7		1	100
					10		90

Nhà máy 2		12		3	110	8		8	200
			90
Nhà máy 3		8		10	-	16		5	150
	80						70 +
Cầu	80		90		120		160		450 450

Bảng 4.11: Cải tiến để tìm phương án tối ưu

Đến đây thử lại ta có tát cả các chỉ tiêu cải tiến đều lớn hơn hoặc bằng 0. Như vậy ta có giải pháp tối ưu.

Các trường hợp đặc biệt trong giải bài toán vận tải

Sự suy biến

Để xác định phương án tối ưu bằng các phương pháp trên, cần đảm bảo một điều kiện là trong bất kỳ phương án đưa ra ban đầu nào, tổng số ô được dùng đều phải bằng tổng số hàng và số cột của ma trận vận tải trừ đi 1. Tức là tổng số ô được dùng phải là n + m – 1. Nếu số ô được dùng ít hơn thì bài toán thuộc dạng suy biến bởi vì ta không thể vẽ được các đường khép kín cho một hoặc nhiều ô chưa dùng đến.

Ví dụ:

Địa điểm tiêu thụ A		Địa điểm tiêu thụ B		Địa điểm tiêu thụ C		Cung
Nhà máy 1		4		7		7	40
	40
Nhà máy 2		12		3		8	60
			50		10
Nhà máy 3		8		10		16	20
					20
Cầu	40		50		30		120 120

Trong bài toán trên, số ô được dùng là 4 < 5 = n + m – 1.

Trong trường hợp này không thể vẽ được đường khép kín qua các ô 1- B, 1 – C, 2 – A và 3 – B.

Xem tất cả 215 trang.

Ngày đăng: 16/07/2022