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.

Quản trị sản xuất tác nghiệp - 11

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

-

90

110

-

80

60

+

Đị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

10

Cầu

80

90

120

160

450

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

+

-

-

90

110

80

10

60

+

Đị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

Nhà máy 3

8

10

16

5

150

Cầu

80

90

120

160

450

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

2


N3


N4


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 trang tiếp theo?
⇦ Trang trước - Trang tiếp theo ⇨

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