Bài giảng Quản lý sản xuất và tác nghiệp 1 - Chương 5. Mô hình vận tải

1Vũ Lệ Hằng 1 CHƯƠNG 5. MÔ HÌNH VẬN TẢI 1. Giới thiệu chung 2. Tiếp nhận giải pháp ban đầu 2.1. Phương pháp góc tây bắc 2.2. Phương pháp xấp xỉ Vogel (VAM: Vogel Approximation Method) 2.3. Phương pháp trực quan 3. Kiểm tra sự tối ưu 3.1. Phương pháp thế vị 3.2. Phương pháp phân phối có điều chỉnh Vũ Lệ Hằng 2 CHƯƠNG 5. MÔ HÌNH VẬN TẢI 4. Tiếp nhận giải pháp cải thiện 5. Các trường hợp đặc biệt 5.1. Nhu cầu và nguồn cung cấp không bằng nhau 5.2. Mô hình suy biến 6. Sử dụng mô hình vận tải trong các quyết định địa điểm 7. Mô hình vận tải và bài toán cực đại Vũ Lệ Hằng 3 1. Giới thiệu chung
Khái niệm
Bài toán vận tải nhằm xác định cách vận chuyển hàng hoá có lợi nhất từ nhiều nguồn cung cấp đến nhiều nơi nhận khác nhau sao cho tổng chi phí vận chuyển là nhỏ nhất Vũ Lệ Hằng 4 1. Giới thiệu chung
Các thông tin cần thiết cho việc sử dụng mô hình vận tải
 Danh sách các nguồn cung cấp hàng hoá và khả năng cung cấp tối đa của các nguồn trong một giai đoạn.
 Danh sách các nơi tiếp nhận hàng hoá và nhu cầu
 Chi phí vận chuyển một đơn vị sản phẩm từ nơi cung cấp đến nơi tiếp nhận. 2Vũ Lệ Hằng 5 1. Giới thiệu chung
Ví dụ: 4 7 7 1 12 8 8 8 10 16 5 100 200 150 450 450 80 90 120 160 1 2 3 NC NCCA B C D 3 Vũ Lệ Hằng 6 1. Giới thiệu chung
Giả định
Các khoản mục hàng hoá được vận chuyển là như nhau (kể cả nguồn cung cấp và nơi tiếp nhận sản phẩm)
Chi phí vận chuyển đơn vị giữa 2 địa điểm cụ thể là như nhau bất kể số lượng đơn vị được vận chuyển.
Chỉ có một phương thức vận chuyển duy nhất giữa 2 địa điểm (nguồn cung cấp và nơi tiếp nhận sản phẩm) Vũ Lệ Hằng 7 1. Giới thiệu chung
Trình tự giải bài toán mô hình vận tải
Bước 1: Tiếp nhận giải pháp ban đầu (an initial solution)
Bước 2: Kiểm tra sự tối ưu
Bước 3: Cải tiến để đạt được một giải pháp tối ưu (suboptimal solution) Vũ Lệ Hằng 8 2. Tiếp nhận giải pháp ban đầu 2.1. Phương pháp góc Tây - Bắc 2.2. Phương pháp xấp xỉ Vogel 2.3. Phương pháp trực quan 3Vũ Lệ Hằng 9 2. Tiếp nhận giải pháp ban đầu 2.1. Phương pháp góc Tây - Bắc
Khái niệm
Phương pháp góc Tây - Bắc luôn ưu tiên phân phối cho ô nằm ở góc Tây - Bắc của bảng
Phương pháp này không quan tâm tới chi phí vận chuyển trong quá trình phân phối Vũ Lệ Hằng 10 2. Tiếp nhận giải pháp ban đầu 2.1. Phương pháp góc Tây - Bắc
Các bước tiến hành
Bước 1: Xác định ô nằm ở phía trên bên trái (ô Tây - Bắc) của bảng
Bước 2: Phân phối tối đa về ô đó và loại bỏ hàng hoặc cột đã thoả mãn
Bước 3: Xác định ô nằm ở phía trên bên trái trong các ô còn lại của bảng
Bước 4: Lặp lại bước 2 và 3 cho đến khi việc phân phối hoàn thành Vũ Lệ Hằng 11 2.1. Phương pháp góc Tây - Bắc
Ví dụ: 4 7 7 1 12 8 8 8 10 16 5 100 200 150 450 45080 90 120 160 1 2 3 NC NCCA B C D 3 2. Tiếp nhận giải pháp ban đầu 80 20 20 70 70 130 120 10 10 150 150 Vũ Lệ Hằng 12 2.1. Phương pháp góc Tây - Bắc
Ví dụ:
Tổng chi phí vận chuyển = 80*4 + 20*7 + 70*3 + 120*8 + 10*8 + 150*5 = 2.460$ 2. Tiếp nhận giải pháp ban đầu 4Vũ Lệ Hằng 13 2.2. Phương pháp xấp xỉ Vogel (VAM - Vogel Approximation Method)
Khái niệm
Phương pháp xấp xỉ Vogel tập trung vào sự thiệt hại về chi phí xảy ra khi ô có chi phí thấp thứ hai được sử dụng thay vì ô thứ có chi phí thấp nhất
VAM ưu tiên phân phối cho ô có chi phí nhỏ nhất nằm trên hàng hoặc cột có sự chênh lệch giữa chi phí nhỏ nhì và chi phí nhỏ nhất là lớn nhất. 2. Tiếp nhận giải pháp ban đầu Vũ Lệ Hằng 14 2.2. Phương pháp xấp xỉ Vogel (VAM - Vogel Approximation Method)
Các bước tiến hành:
Bước 1: Tính toán sự chênh lệch giữa 2 ô có chi phí thấp nhất trên mỗi hàng và mỗi cột.
Bước 2: Xác định hàng hoặc cột có sự chênh lệch lớn nhất, nếu có sự bằng nhau lựa chọn hàng hoặc cột có chứa ô có chi phí thấp nhất. Nếu vẫn bằng nhau thì lựa chọn tuỳ ý 2. Tiếp nhận giải pháp ban đầu Vũ Lệ Hằng 15 2.2. Phương pháp xấp xỉ Vogel (VAM) (Vogel Approximation Method)
Các bước tiến hành:
Bước 3: Đối với hàng hoặc cột đã lựa chọn, phân phối tối đa về ô có chi phí thấp nhất. Nếu vẫn bằng nhau, tuỳ ý lựa chọn. Loại bỏ hàng hoặc cột đã thoả mãn
Bước 4: Lặp lại bước 1 đến bước 3 cho các hàng và cột còn lại cho đến khi việc phân phối hoàn thành. 2. Tiếp nhận giải pháp ban đầu Vũ Lệ Hằng 16 2.2. Phương pháp xấp xỉ Vogel 4 7 7 1 12 8 8 8 10 16 5 100 200 150 450 45080 90 120 160 1 2 3 NC NCCA B C D 3 110 2. Tiếp nhận giải pháp ban đầu 3 5 3 4 1 90 3 0 3 - 4 - 0 3 100 60 110 10 80 10 60 4 4 - 1 4 4 8 3- 5Vũ Lệ Hằng 17 2. Tiếp nhận giải pháp ban đầu 2.3. Phương pháp trực quan
Khái niệm
Là phương pháp tuần tự phân phối tối đa sản phẩm về ô có chi phí nhỏ nhất Vũ Lệ Hằng 18 2. Tiếp nhận giải pháp ban đầu 2.3. Phương pháp trực quan
Các bước tiến hành
Bước 1: Xác định ô có chi phí vận chuyển đơn vị nhỏ nhất
Bước 2: Phân phối tối đa sản phẩm về ô đó và loại bỏ hàng hoặc cột (hoặc cả hai) đã thoả mãn.
Bước 3: Tìm ô có chi phí thấp nhất tiếp theo trong các ô còn lại
Bước 4: Lặp lại bước 2 và 3 cho đến khi việc phân phối hoàn thành Vũ Lệ Hằng 19 2.3. Phương pháp trực quan
Ví dụ: 4 7 7 1 12 8 8 8 10 16 5 100 200 150 450 45080 90 120 160 1 2 3 NC NCCA B C D 3 100 90 110 110 60 60 2. Tiếp nhận giải pháp ban đầu 90 10 80 10 10 Vũ Lệ Hằng 20 2. Tiếp nhận giải pháp ban đầu 2.3. Phương pháp trực quan
Ví dụ:
Tổng chi phí vận chuyển = 100*1 + 90*3 + 110*8 + 80*8 + 10*16 + 60*5 = 2.350$ 6Vũ Lệ Hằng 21 3. Kiểm tra sự tối ưu 3.1. Phương pháp thế vị (Phương pháp chuyển ô - Stepping Stone) 3.2. Phương pháp phân phối có điều chỉnh (MODI - Modified distribution method)
Kiểm tra điều kiện không suy biến
Số lượng tối thiểu các ô đầy = R + C - 1 Vũ Lệ Hằng 22 3. Kiểm tra sự tối ưu 3.1. Phương pháp thế vị
Nguyên tắc thực hiện
Chuyển 1 đơn vị sản phẩm từ ô đầy vào ô trống và đánh giá xem chi phí tăng lên hay giảm đi
Trình tự thực hiện
Tạo dựng đường đánh giá
Đánh giá các ô trống Vũ Lệ Hằng 23 3. Kiểm tra sự tối ưu 3.1. Phương pháp thế vị
Bước 1: Tạo dựng đường đánh giá
Chọn 1 ô trống (ô chưa sử dụng) để đánh giá. Gán dấu (+) vào ô trống cần đánh giá
Chuyển theo chiều ngang hoặc chiều dọc tới một ô đầy, sao cho từ ô đó có thể chuyển tới một ô đầy khác. Gán dấu (-) cho ô vừa chọn
Đổi hướng và chuyển tới một ô đầy khác, gán dấu (+) cho ô đã lựa chọn
Tuần tự gán dấu (-) hoặc (+) cho đến khi hoàn thiện một con đường khép kín để trở về ô trống ban đầu Vũ Lệ Hằng 24 3. Kiểm tra sự tối ưu 3.1. Phương pháp thế vị
Bước 2: Đánh giá các ô trống
Giá trị ô trống được xác định bằng:
Tổng chi phí đơn vị của các ô có chứa dấu (+) Trừ
Tổng chi phí đơn vị của các ô có chứa dấu (-)
Bước 3: Lặp lại các bước 1 và 2 cho đến khi đánh giá được tất cả các ô trống. 7Vũ Lệ Hằng 25 3.1. Phương pháp thế vị
Ô trống 1-A 4 7 7 1 12 8 8 8 10 16 5 100 200 150 450 45080 90 120 160 1 2 3 NC NCCA B C D 3 100 90 110 60 3. Kiểm tra sự tối ưu (+) 80 10 (-) (+)(-) Vũ Lệ Hằng 26 3.1. Phương pháp thế vị
Ví dụ: 1 - A (+) (-) 1 - B (+) (-) 4 1 5 8 0 7 1 5 16 8 3 0 1 - C (+) (-) 7 5 1 16 - 5 Vũ Lệ Hằng 27 3.1. Phương pháp thế vị
Ví dụ: 2 - A (+) (-) 2 - D (+) (-) 12 8 16 8 12 8 5 16 8 11 3 - B (+) (-) 10 8 16 3 - 1 Vũ Lệ Hằng 28 3.2. Phương pháp phân phối có điều chỉnh - MODI
Các bước tiến hành
Bước 1: Tính toán chỉ số hàng và chỉ số cột a. Gán chỉ số hàng đầu tiên = 0 b. Xác định chỉ số cột có chứa các ô đầy nằm trên hàng đầu tiên: Chỉ số cột = Chi phí ô đầy - Chỉ số hàng c. Xác định chỉ số hàng tiếp theo Chỉ số hàng = Chi phí ô đầy - Chỉ số cột d. Lặp lại các bước b, c cho đến khi xác định được tất cả các chỉ số hàng và chỉ số cột 8Vũ Lệ Hằng 29
Bước 2: Xác định giá trị ô trống Giá trị ô trống = Chi phí ô trống – (Chỉ số hàng + Chỉ số cột)
Chú ý:
Chỉ số hàng hoặc cột có thể có giá trị (+), (-) hoặc = 0
Phân bổ lại sẽ đòi hỏi phải tính lại các chỉ số hàng và cột mới 3.2. Phương pháp phân phối có điều chỉnh - MODI Vũ Lệ Hằng 30
VD: Tiếp nhận giải pháp ban đầu bằng phương pháp trực quan 4 7 7 1 12 8 8 8 10 16 5 100 200 150 450 45080 90 120 160 1 2 3 NC NCCA B C D 3 4 7 12 90 0 - 4 4 100 1 110 80 10 60 3.2. Phương pháp phân phối có điều chỉnh - MODI Vũ Lệ Hằng 31
Xác định giá trị ô trống 1 – A = 4 – (0 + 4) = 0 1 – B = 7 – (0 + 7) = 0 1 – C = 7 – (0 + 12) = - 5 2 – A = 12 – (- 4 + 4) = 12 2 – D = 8 – (- 4 + 1) = 11 3 – B = 10 – (4 + 7) = - 1 3.2. Phương pháp phân phối có điều chỉnh Vũ Lệ Hằng 32 3. Kiểm tra sự tối ưu
Kiểm tra sự tối ưu:
Giá trị các ô trống ≥ 0 → giải pháp tối ưu
Tồn tại ít nhất một ô trống có giá trị < 0 → giải pháp chưa tối ưu 9Vũ Lệ Hằng 33 4. Tiếp nhận giải pháp được cải thiện
Các bước tiến hành
Bước 1: Trong các ô cho giá trị âm, chọn ô có giá trị tuyệt đối lớn nhất
Bước 2:
Chuyển các đơn vị sản phẩm từ ô có dấu (-) sang ô có dấu (+)
Số lượng sản phẩm tối đa chuyển được là giá trị nhỏ nhất trong các ô mang dấu (-).
Bước 3: Đánh giá các ô trống để kiểm tra sự tối ưu
Chú ý kiểm tra điều kiện R + C - 1 trước khi đánh giá ô trống Vũ Lệ Hằng 34
Ví dụ: 4 7 7 1 12 8 8 8 10 16 5 100 200 150 450 45080 90 120 160 1 2 3 NC NCCA B C D 3 90 90 110 7080 4. Tiếp nhận giải pháp được cải thiện 10 Vũ Lệ Hằng 35
Ví dụ: Đánh giá ô trống bằng MODI 4 7 7 1 12 8 8 8 10 16 5 100 200 150 450 45080 90 120 160 1 2 3 NC NCCA B C D 3 90 90 110 7080 4. Tiếp nhận giải pháp được cải thiện 10 0 17 4 1 24 Vũ Lệ Hằng 36
Ví dụ: Kiểm ra sự tối ưu:
1 – A = 0
1 – B = 5
2 – A = 7
2 – D = 6
3 – B = 4
3 – C = 5 ⇒Giải pháp tối ưu, vì giá trị tất cả các ô trống ≥ 0  Tổng chi phí: 10*7 + 90*1 + 90*3 + 110*8 + 80*8 + 70*5 = 2.300 4. Tiếp nhận giải pháp được cải thiện 10 Vũ Lệ Hằng 37 5. Các trường hợp đặc biệt 5.1. Nhu cầu và Nguồn cung cấp không bằng nhau
TH 1: Tổng cung > Tổng cầu => thêm một cột giả (Dummy column):
Nhu cầu (ở cột giả) = ∑ cung - ∑ cầu.
TH 2: Tổng cầu > Tổng cung => thêm một hàng giả (Dummy row) Vũ Lệ Hằng 38 5. Các trường hợp đặc biệt 5.1. Nhu cầu và Nguồn cung cấp không bằng nhau
Chú ý:
Không có đơn vị hàng hoá nào được vận chuyển tại ô giả (ô Dummy)
Chi phí vận chuyển đơn vị ở mỗi ô Dummy bằng 0
Khi sử dụng phương pháp trực quan để tiếp nhận giải pháp ban đầu, nếu tổng nhu cầu và nguồn cung cấp không bằng nhau thì phải phân phối về các ô Dummy cuối cùng. Vũ Lệ Hằng 39 5.1. Nhu cầu và Nguồn cung cấp không bằng nhau
Ví dụ: Sử dụng phương pháp trực quan để tiếp nhận giải pháp ban đầu 5. Các trường hợp đặc biệt 5 9 4 100 100 80 90 1 2 NC NCCA B 2 Vũ Lệ Hằng 40
Ví dụ: 5.1. Tổng NCC và tổng NC không bằng nhau 5 9 4 100 100 200 20080 90 1 2 NC NCCA B 2 0 Dummy 0 30 11 Vũ Lệ Hằng 41 5. Các trường hợp đặc biệt 5.2. Mô hình suy biến (Degeneracy)
Bài toán không thỏa mãn điều kiện số lượng tối thiểu các ô đầy (R + C – 1) → bài toán thuộc dạng suy biến
Nguyên tắc:
Gán một giá trị ε rất nhỏ vào một ô trống nào đó và xem như một ô đầy
Tránh đặt ε vào ô mang dấu (-) trong đường đánh giá; giá trị ε có thể được bỏ ở giải pháp cuối cùng. Vũ Lệ Hằng 42 5.2. Mô hình suy biến VD: Tiếp nhận giải pháp ban đầu bằng phương pháp trực quan 5. Các trường hợp đặc biệt 3 2 5 8 4 7 7 6 40 60 20 120 12040 50 30 1 2 3 NC NCCA B C 1 Vũ Lệ Hằng 43 6. Sử dụng mô hình vận tải trong các quyết định lựa chọn địa điểm
Sử dụng bài toán vận tải để so sánh các giải pháp về địa điểm xét trên tổng chi phí phân phối trong toàn hệ thống.
Ví dụ: Giả sử công ty dự định mở thêm một nhà kho mới với nhu cầu là 30 ở một trong hai địa điểm (Boston hoặc New York), biết chi phí vận chuyển đơn vị đến hai địa điểm như sau: $1$6Từ 2 $4$3Từ 1 Đến New YorkĐến Boston Vũ Lệ Hằng 44 6. Sử dụng mô hình vận tải trong các quyết định địa điểm
Ví dụ: Hiện tại công ty có mô hình vận tải như dưới đây. Xác định địa điểm cho tổng chi phí nhỏ nhất 5 9 4 100 100 200 17080 90 1 2 NC NCCA B 2 12 Vũ Lệ Hằng 45
Ví dụ: 5 9 4 100 100 200 20080 90 1 2 NC NCCA B 2 3 6 30 Boston 6. Sử dụng mô hình vận tải trong các quyết định địa điểm Vũ Lệ Hằng 46
Ví dụ: 5 9 4 100 100 200 20080 90 1 2 NC NCCA B 2 4 1 30 New York 6. Sử dụng mô hình vận tải trong các quyết định địa điểm Vũ Lệ Hằng 47 7. Mô hình vận tải và bài toán cực đại
Bài toán mô hình vận tải có thể áp dụng trong trường hợp các số liệu thể hiện lợi nhuận
Nguyên tắc:
Cách 1: Xác định ô có lợi nhuận lớn nhuận lớn nhất, lấy giá trị của ô đó trừ đi các ô còn lại và xem như một chi phí cơ hội.
Bài toán cực đại lợi nhuận chuyển thành bài toán cực tiểu chi phí. Giải bài toán tương tự như đối với trường hợp cực tiểu chi phí. Vũ Lệ Hằng 48 7. Mô hình vận tải và bài toán cực đại
Nguyên tắc:
Cách 2: Xác định chênh lệch của hai ô có lợi nhuận lớn nhất và lợi nhuận lớn thứ nhì.
Sau đó các bước áp dụng tương tự như đối với bài toán cực tiểu chi phí - Sử dụng VAM.
Giải pháp tối ưu: các ô trống ≤ 0 13 Vũ Lệ Hằng 49
Ví dụ: Xác định giải pháp tối ưu trong trường hợp số liệu thể hiện lợi nhuận 4 7 7 1 12 8 8 8 10 16 5 100 200 150 450 45080 90 120 160 1 2 3 NC NCCA B C D 3 7. Mô hình vận tải và bài toán cực đại 1090 80 120 30120 Vũ Lệ Hằng 50
Ví dụ: Cách 2: Sử dụng VAM 4 7 7 1 12 8 8 8 10 16 5 100 200 150 450 45080 90 120 160 1 2 3 NC NCCA B C D 3 7. Mô hình vận tải và bài toán cực đại 1090 80 120 30120 34 8 0 4 - 3 3 - 3 - 3 3 3 6 4 6 4 2 5 5 30 120 10 Vũ Lệ Hằng 51
Ví dụ: Kiểm tra sự tối ưu bằng phương pháp thế vị
Kiểm tra đk: R+C -1= 6 (ô đầy) → thỏa mãn đk
1 – A = -1
1 – C = -5
2 – B = -11
2 – C = -11
3 – A = -1
3 – B = -1 → gp tối ưu Tổng lợi nhuận: 90*7 + 10*1 + 80*12 + 120*8 + 120*16 + 30*5 = $4.630 7. Mô hình vận tải và bài toán cực đại Vũ Lệ Hằng 52
Ví dụ: Cách 1: Bài toán cực tiểu chi phí 12 9 9 15 4 8 8 8 6 0 11 100 200 150 450 45080 90 120 160 1 2 3 NC NCCA B C D 13 7. Mô hình vận tải và bài toán cực đại 1090 80 120 30120 34 8 0 4 - 3 3 - 3 - 3 3 3 6 4 6 4 2 5 5 30 120 10 14 Vũ Lệ Hằng 53
Ví dụ: Kiểm tra sự tối ưu bằng phương pháp thế vị
Kiểm tra đk: R+C -1= 6 (ô đầy) → thỏa mãn đk
1 – A = +1
1 – C = + 5
2 – B = +11
2 – C = +11
3 – A = +1
3 – B = +1 → gp tối ưu 7. Mô hình vận tải và bài toán cực đại Vũ Lệ Hằng 54
Cách 1: 4 7 7 1 12 8 8 8 10 16 5 100 200 150 450 45080 90 120 160 1 2 3 NC NCCA B C D 3 7. Mô hình vận tải và bài toán cực đại 1090 80 120 30120 Vũ Lệ Hằng 55 Ví dụ: → gp tối ưu Tổng lợi nhuận: 90*7 + 10*1 + 80*12 + 120*8 + 120*16 + 30*5 = $4.630 7. Mô hình vận tải và bài toán cực đại