Bài giảng Quản lý sản xuất và tác nghiệp 1: Chương 5 - ThS. Vũ Lệ Hằng (ĐH Thăng Long)

Chia sẻ: Thanh Hoa | Ngày: | Loại File: PDF | Số trang:14

Thêm vào BST

Báo xấu

95
lượt xem 8
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

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" cung cấp cho người học các kiến thức: Giới thiệu chung, tiếp nhận giải pháp ban đầu, kiểm tra sự tối ưu. Mời các bạn cùng tham khảo nội dung chi tiết.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng Quản lý sản xuất và tác nghiệp 1: Chương 5 - ThS. Vũ Lệ Hằng (ĐH Thăng Long)

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