Bài giảng Phương pháp định lượng trong quản lý - Chương 4: Bài toán vận tải - Nguyễn Thống

Nội dung text: Bài giảng Phương pháp định lượng trong quản lý - Chương 4: Bài toán vận tải - Nguyễn Thống

1. TRƯỜNG ĐẠI HỌC BÁCH KHOA TP. HCM PHƯƠNG PHÁP ĐỊNH LƯỢNG TRONG QUẢN LÝ Khoa KTXD - Bộ mơn KTTNN NỘI DUNG MƠN HỌC CHƯƠNG 1: Giới thiệu Phương pháp định lượng trong Quản lý. CHƯƠNG 2: Quy hoạch tuyến tính. CHƯƠNG 3: Cơ sở lý thuyết ra quyết định. CHƯƠNG 4: Bài toán vận tải. Giảng viên: PGS. TS. NGUYỄN THỐNG CHƯƠNG 5: Quản lý kho. E-mail: nguyenthong@hcmut.edu.vn or nthong56@yahoo.fr CHƯƠNG 6: Ra quyết định đa mục tiêu. Web: 11/26/2013 1 CHƯƠNG11/26/2013 7: Lý thuyết sắp hàng. 2 Tél. (08) 38 640 979 - 098 99 66 719 PHƯƠNG PHÁP ĐỊNH PHƯƠNG PHÁP ĐỊNH LƯỢNG TRONG QUẢN LÝ LƯỢNG TRONG QUẢN LÝ NỘI DUNG MƠN HỌC (tt) TÀI LIỆU THAM KHẢO Chương 8: Phân tích thành phần chính (PCA). 1. Phương pháp định lượng trong quản lý. Chương 9: Kiểm định Cronbach’s Alpha & NXB Trẻ 1999. Tác giả PGS. Dr. Nguyễn KMO Thống & Dr. Cao Hào Thi. Chương 10: Phương pháp AHP Chương 11: Qui hoạch động 2. Phân tích số liệu và áp dụng vào dự báo. Chương 12: Hoạch định dự án NXB Thanh Niên 2000. Tác giả PGS. Dr. Chương 13: Xích Markov Nguyễn Thống Chương 14: Lý thuyết trị chơi. 3. Phần mềm QSB, Crystal Ball Chương 15: Mơ phỏng Monte Carlo. 11/26/20133 11/26/2013 4 PHƯƠNG PHÁP ĐỊNH LƯỢNG TRONG QUẢN LÝ PHƯƠNG PHÁP ĐỊNH LƯỢNG TRONG QUẢN LÝ Chương 4: Bài toán vận tải Chương 4: Bài toán vận tải GIỚI THIỆU • Bài toán này đầu tiên được trình bày • Bài toán vận tải (1939) là dạng đặc biệt của trong công tác vận chuyển hàng hóa. Bài toán Qui Hoạch Tuyến Tính do đó có Vì vậy có tên là bài toán vận tải. thể giải bài toán theo các phương pháp đã trình bày trong Qui Hoạch Tuyến Tính. Nhưng mô hình của bài toán vận tải, Tuy nhiên cấu trúc bài toán có những tính chất sau khi được công bố, đã được rất đặc biệt nên có phương pháp giải riêng hữu nhiều ngành kinh tế khác nhau ứng hiệu hơn. dụng như lãnh vực quân sự, quản lý, y tế, 11/26/2013 5 11/26/2013 6 PGS. Dr. Nguyễn Thống PGS. Dr. Nguyễn Thống 1
2. PHƯƠNG PHÁP ĐỊNH LƯỢNG TRONG QUẢN LÝ PHƯƠNG PHÁP ĐỊNH LƯỢNG TRONG QUẢN LÝ Chương 4: Bài toán vận tải Chương 4: Bài toán vận tải MÔ HÌNH TỔNG QUÁT MÔ HÌNH TỔNG QUÁT • Có n trạm phát hàng. Mỗi trạm ký • Chi phí vận chuyển một đơn vị hàng hóa hiệu là Ai ( i= 1,n ). Khả năng cung cấp từ Ai đến Bj là Cij. hàng hóa của trạm phát thứ i là ai. HÀM MỤC TIÊU CỦA BÀI TOÁN • Có m trạm thu hàng. Mỗi trạm ký hiệu Xác định phương án vận chuyển sao là Bj ( j = 1,m ). Nhu cầu hàng hóa của cho tổng chi phí vận chuyển là nhỏ nhất. trạm thu thứ j là b . j 11/26/2013 7 11/26/2013 8 PGS. Dr. Nguyễn Thống PGS. Dr. Nguyễn Thống PHƯƠNG PHÁP ĐỊNH LƯỢNG TRONG QUẢN LÝ PHƯƠNG PHÁP ĐỊNH LƯỢNG TRONG QUẢN LÝ Chương 4: Bài toán vận tải Chương 4: Bài toán vận tải SỐ LIỆU DẠNG BẢNG • Biến quyết định: Gọi xij là số lượng đơn vị Nhận hàng Bj hàng hóa vận chuyển từ trạm phát thứ i đến Ai b1 b2 . bm trạm thu thứ j. MinZ C x • Hàm mục tiêu:  ij ij a1 x11(c11) x12(c12) . x1m (Công suất trạm phát) a2 x21 x22 . x2m m x a . . . Chi. phí đơn. vị  ij i i=1,n • Ràng buộc: j 1 a x x . x n n1 n2 nm (Công suất trạm thu) xij >=0 n Phát hàng Biến quyết định 11/26/2013 9 11/26/2013  xij bj j=1,m10 PGS. Dr. Nguyễn Thống (lượng hàng hóa) PGS. Dr. Nguyễn Thống i 1 PHƯƠNG PHÁP ĐỊNH LƯỢNG TRONG QUẢN LÝ PHƯƠNG PHÁP ĐỊNH LƯỢNG TRONG QUẢN LÝ Chương 4: Bài toán vận tải Chương 4: Bài toán vận tải n m • Ghi chú: Nếu giữa một trạm A nào đó Trường hợp: Cung = Cầu i  ai bj đến một trạm Bj nào đó không có đường i 1 j 1 vận chuyển nghĩa là giữa 2 trạm đó Ví du 1: Bài toán vận chuyển chất đốt không thể tổ chức vận chuyển được Ở các trạm phát A và B có 150 tấn và 90 tấn khi đó ta lấy đơn gía vận chuyển C = chất đốt. Phải cung cấp cho các vị trí 1, 2, 3 ij tương ứng 60, 70 và 110 tấn chất đốt đó. Chi M với M là một số dương lớn tùy ý. phí chở 1 tấn chất đốt từ A đến các vị trí 1, 2, Trong trường hợp đó lời giải cho x sẽ 3 tương ứng là 6, 10 và 4$ còn từ B đến 1, 2, 3 ij là 12, 2 và 8$. Hãy lập kế hoạch vận chuyển là 0. tối ưu sao cho tổng chi phí vận chuyển là bé 11/26/2013 11 11nhất/26/2013 . 12 PGS. Dr. Nguyễn Thống PGS. Dr. Nguyễn Thống 2
3. PHƯƠNG PHÁP ĐỊNH LƯỢNG TRONG QUẢN LÝ PHƯƠNG PHÁP ĐỊNH LƯỢNG TRONG QUẢN LÝ Chương 4: Bài toán vận tải Chương 4: Bài toán vận tải n 2 Trong trường hợp không có sự cân bằng giữa  ai 150 90 240 Cung và Cầu, ta có thể luôn luôn trở về bài i 1 Cung = Cầu toán cân bằng Cung và Cầu bằng cách thêm m 3 b 60 70 110 240 vào nguồn Cung giả hoặc Cầu giả và gán các  j chi phí vận chuyển LỚN tương ứng tuyến vận j 1 chuyển. Trạm thu Trạm phát 1 2 3 Lời giải vẫn tìm được sau khi loại các nguồn 60T 70T 110T giả từ kết quả tìm ra cuối cùng. A 150T x11=?(6$) x12=?(10$) x13=?(4$) B 90T x =?(12$) x =?(2$) x =?(8$) 11/26/2013 21 22 23 13 11/26/2013 14 PGS. Dr. Nguyễn Thống PGS. Dr. Nguyễn Thống PHƯƠNG PHÁP ĐỊNH LƯỢNG TRONG QUẢN LÝ PHƯƠNG PHÁP ĐỊNH LƯỢNG TRONG QUẢN LÝ Chương 4: Bài toán vận tải Chương 4: Bài toán vận tải PHƯƠNG PHÁP GIẢI BÀI TOÁN VẬN TẢI PHƯƠNG PHÁP GIẢI BÀI TOÁN VẬN Vì bài toán vận tải cũng là một bài toán QHTT TẢI nên hoàn toàn có thể giải bằng phương pháp • Phương pháp chi phí bé nhất C (The đơn hình. Nhưng do tính chất đặc thù của bài min toán vận tải nên ta có những phương pháp Least Cost Method). GIẢI đơn giản hơn. • Phương pháp xấp xỉ của Vogel (Vogel’s Có 3 phương pháp LỜI GIẢI GẦN ĐÚNG: Approximation Method - VAM). • Phương pháp góc Tây Bắc P/án đầu (The PHƯƠNG PHÁP TỔNG QUÁT (tìm lời North West Corner Method). giải chính xác) PHƯƠNG PHÁP THẾ VỊ 11/26/2013 15 11/26/2013 16 PGS. Dr. Nguyễn Thống PGS. Dr. Nguyễn Thống PHƯƠNG PHÁP ĐỊNH LƯỢNG TRONG QUẢN LÝ PHƯƠNG PHÁP ĐỊNH LƯỢNG TRONG QUẢN LÝ Chương 4: Bài toán vận tải Chương 4: Bài toán vận tải • Xuất phát từ ô nằm ở góc Tây Bắc, tức ô (1,1) ta tiến dần xuống ô ở góc Đông Nam, PHƯƠNG PHÁP GÓC TÂY BẮC tức ô (n,m). Trên đường đi gặp ô nào ta phân phối cho (Dantzig) ô đó một lượng hàng lớn nhất có thể được dựa trên nguyên tắc đảm bảo điều kiện cân bằng giữa số cung và số cầu. Khi phân phối hết thì dừng lại. 11/26/2013 17 11/26/2013 18 PGS. Dr. Nguyễn Thống PGS. Dr. Nguyễn Thống 3
4. PHƯƠNG PHÁP ĐỊNH LƯỢNG TRONG QUẢN LÝ PHƯƠNG PHÁP ĐỊNH LƯỢNG TRONG QUẢN LÝ Chương 4: Bài toán vận tải Chương 4: Bài toán vận tải Sau đó kiểm tra xem tổng ô chọn có bằng Lấy lại số liệu ở trên: (m + n - 1) hay không. Ô chọn là ô có xij > 0. Trạm thu Trạm phát 1 2 3 Nếu điều kiện nầy thỏa mãn thì phương 60T 70T 110T án nhận được gọi là phương án đầu. A 150T x11=?(6$) x12=?(10$) x13=?(4$) Nhận xét: Lời giải của phương án đầu B 90T x21=?(12$) x22=?(2$) x23=?(8$) trong phương pháp góc Tây Bắc ít khi Tìm lời giải sơ bộ bằng phương pháp tối ưu bởi vì khi giải KHÔNG quan tâm góc Tây Bắc. đến chi phí vận chuyển. 11/26/2013 19 11/26/2013 20 PGS. Dr. Nguyễn Thống PGS. Dr. Nguyễn Thống PHƯƠNG PHÁP ĐỊNH LƯỢNG TRONG QUẢN LÝ PHƯƠNG PHÁP ĐỊNH LƯỢNG TRONG QUẢN LÝ Chương 4: Bài toán vận tải Chương 4: Bài toán vận tải Lấy ví dụ 1 nói trên: Bài tập: Lấy lại ví dụ 1 nói trên, dùng Trạm thu phương pháp góc Tây Bắc để tìm lời Trạm phát 1 2 3 giải sơ bộ với các trường hợp sau: 60T 70T 110T 1. Khả năng cung cấp của trạm A bây giờ là 100T. A 150T 60 70 20 B 90T 90 2. Khả năng trạm thu 3 là 80T. (Chú ý: Trong trường hợp Cung < Cầu Bổ sung trạm Cung GIẢ) Ví dụ phương pháp giải Tây Bắc: Z = 60*6 + 70*10 + 20*4 + 90*8 = 1860 $ 11/26/2013 21 11/26/2013 22 PGS. Dr. Nguyễn Thống PGS. Dr. Nguyễn Thống PHƯƠNG PHÁP ĐỊNH LƯỢNG TRONG QUẢN LÝ PHƯƠNG PHÁP ĐỊNH LƯỢNG TRONG QUẢN LÝ Chương 4: Bài toán vận tải Chương 4: Bài toán vận tải Ví dụ: Bài toán quản lý sản xuất (p/p góc Tây Bắc) Chi phí sản xuất Một Công ty có 3 nhà máy 1, 2, 3. Mỗi nhà máy có Sản phẩm thể sản xuất 5 loại sản phẩm 1, 2, 3, 4, 5 với khả năng xuất và tiêu thụ tổng 5 loại như sau. Nhà máy 1 2 3 4 5 1 20 19 14 21 16 Nhà máy 1 2 3 Khả năng sản 40 đơn vị 60 90 2 15 20 13 19 16 xuất 5 loại 3 18 15 18 20 ? Sản phẩm 1 2 3 4 5 Biết rằng nhà máy 3 không thể sản xuất sản phẩm 5. Khả năng 30 40 70 40 60 Giả thiết mỗi đơn vị sản phẩm đều có lợi nhuận bán bằng nhau. Vậy mỗi nhà máy nên sản xuất bao 11/26/2013 23 11/26nhiêu/2013 đơn vị cho mỗi loại sản phẩm ? 24 PGS. Dr. Nguyễn Thống PGS. Dr. Nguyễn Thống 4
5. PHƯƠNG PHÁP ĐỊNH LƯỢNG TRONG QUẢN LÝ PHƯƠNG PHÁP ĐỊNH LƯỢNG TRONG QUẢN LÝ Chương 4: Bài toán vận tải Chương 4: Bài toán vận tải Vì không có sự cân bằng giữa sản xuất và nhu cầu thêm một nhà máy giả số 4 có khả năng sản xuất 240 - 190 = 50 đơn vị sản phẩm với chi phí sản xuất bằng 0. PHƯƠNG PHÁP CHI PHÍ Sản phẩm Nhà máy 1 2 3 4 5 BÉ NHẤT CMIN 30 40 70 40 60 1 40 30 10 2 60 30 30 3 90 40 40 10 11/26/20134 25 11/26/2013 26 PGS. Dr. Nguyễn Thống50 50 PGS. Dr. Nguyễn Thống PHƯƠNG PHÁP ĐỊNH LƯỢNG TRONG QUẢN LÝ PHƯƠNG PHÁP ĐỊNH LƯỢNG TRONG QUẢN LÝ Chương 4: Bài toán vận tải Chương 4: Bài toán vận tải Khi dùng phương pháp góc Tây Bắc • Trong phương pháp Cmin, trước tiên ta ta không để ý đến chi phí vận tìm ô có trị số Cij nhỏ nhất. Phân phối lượng hàng lớn nhất có thể có được vào chuyển Cij. Do đó kết quả có được ở phương án đầu còn cách xa phương ô đó. án tối ưu. • Sau đó ta phân phối hàng hóa cho ô có trị số C nhỏ nhất trong các ô còn lại. Phương pháp C khắc phục được ij min • Cứ tiếp tục như thế cho đến hết. một phần nhược điểm này. 11/26/2013 27 11/26/2013 28 PGS. Dr. Nguyễn Thống PGS. Dr. Nguyễn Thống PHƯƠNG PHÁP ĐỊNH LƯỢNG TRONG QUẢN LÝ PHƯƠNG PHÁP ĐỊNH LƯỢNG TRONG QUẢN LÝ Chương 4: Bài toán vận tải Chương 4: Bài toán vận tải • Trong quá trình phân phối cần đảm Phương pháp Cmin. Lấy ví dụ 1 nói trên: bảo điều kiện cân bằng giữa số cung Trạm thu Trạm phát 1 2 3 và số cầu. 60T 70T 110T 3 2 • Kiểm tra điều kiện : Tổng số ô chọn A 150T 40(6) 110(4) = m + n - 1 B 90T 20(12)4 70 (2)1 Trình Ví dụ phương pháp giải Cmin tự chọn Z = 40*6 + 110*4 + 70*2 + 20*12 = 1060 $ (1860$) chỉ trình tự phân bố khối lượng vận chuyển 11/26/2013 29 11/26/2013 30 PGS. Dr. Nguyễn Thống PGS. Dr. Nguyễn Thống 5
6. PHƯƠNG PHÁP ĐỊNH LƯỢNG TRONG QUẢN LÝ PHƯƠNG PHÁP ĐỊNH LƯỢNG TRONG QUẢN LÝ Chương 4: Bài toán vận tải Chương 4: Bài toán vận tải Bài tập: Tìm lời giải bằng phương pháp Cmin : Bài tập: Tìm lời giải bằng phương pháp Cmin : Trạm thu Trạm thu Trạm phát 1 2 3 Trạm phát 1 2 3 60T 70T 110T 60T 70T 110T A 90T x11=?(6$) x12=?(10$) x13=?(4$) A 90T x11=?(6$) x12=?(10$) x13=?(4$) B 150T x21=?(12$) x22=?(2$) x23=?(8$) B 150T x21=?(12$) x22=?(2$) x23=?(4$) Trạm thu (Xét trường hợp có một số Trạm phát 1 2 3 phương án có chi phí như nhau) 60T 70T 110T A 80T x11=?(6$) x12=?(10$) x13=?(4$) 11/26/2013 31 11/26/2013 32 PGS. Dr.B Nguyễn Thống120T x21=?(12$) x22=?(2$) x23=?(8$) PGS. Dr. Nguyễn Thống PHƯƠNG PHÁP ĐỊNH LƯỢNG TRONG QUẢN LÝ PHƯƠNG PHÁP ĐỊNH LƯỢNG TRONG QUẢN LÝ Chương 4: Bài toán vận tải Chương 4: Bài toán vận tải PHƯƠNG PHÁP XẤP XỈ CỦA VOGEL • Trong phương pháp Cmin ta đã xem xét đến PHƯƠNG PHÁP chi phí vận chuyển Cij nhưng chưa chú ý đến hiệu số của chúng (sự chênh lệch về chi phí XẤP XỈVOGEL vận chuyển). Vì vậy có thể xảy ra trường hợp bước trước thì tốt nhưng bước sau lại xấu (bước trước rơi vào ô có chi phí thấp nhưng bước sau rơi vào ô có chi phí rất cao). 11/26/2013 33 11/26/2013 34 PGS. Dr. Nguyễn Thống PGS. Dr. Nguyễn Thống PHƯƠNG PHÁP ĐỊNH LƯỢNG TRONG QUẢN LÝ PHƯƠNG PHÁP ĐỊNH LƯỢNG TRONG QUẢN LÝ Chương 4: Bài toán vận tải Chương 4: Bài toán vận tải CÁC BƯỚC CỦA PHƯƠNG PHÁP VOGEL: PHƯƠNG PHÁP XẤP XỈ CỦA • Bước 1: Trên mỗi hàng và mỗi cột chọn chi phí Cij VOGEL bé nhất và Cij bé thứ hai. Lấy hiệu số của chúng rồi ghi vào ô bên phải và bên dưới bảng. Tìm số lớn • Phương pháp Vogel khắc phục được nhất trong các hiệu số đó. nhược điểm nầy Trạm thu Cho kết quả tốt hơn, gần bằng Trạm phát 1 2 3 hoặc bằng kết quả lời giải tối ưu. 60T 70T 110T A 150T 6$ 10$ 4$ 2(6-4) B 90T 12$ 2$ 8$ 6(8-2) 11/26/2013 35 11/26/2013 6 (12-6) 8 4 36 PGS. Dr. Nguyễn Thống PGS. Dr. Nguyễn Thống 6
7. PHƯƠNG PHÁP ĐỊNH LƯỢNG TRONG QUẢN LÝ PHƯƠNG PHÁP ĐỊNH LƯỢNG TRONG QUẢN LÝ Chương 4: Bài toán vận tải Chương 4: Bài toán vận tải Bước 2: Phân phối trước lượng hàng cho Bước 2: Phương pháp Vogel : Trạm thu hàng (hoặc cột) có trị số hiệu số lớn nhất Trạm phát 1 2 3 (cột trạm thu số 2). 60T 70T 110T • Lúc phân phối, thì phân phối lượng hàng A 150T 6$ 10$ 4$ 2 B 90T 12$ (70)2$ 8$ 6 lớn nhất có thể được vào ô có Cij nhỏ 6 8 4 nhất của hàng và cột ứng với hiệu số lớn nhất nói trên (hàng trạm phát B). Chọn cột số [2] phân phối vì giá trị (8) là lớn • Trong quá trình phân phối cần đảm bảo nhất và lựa chọn ô trên cột này có chi phí bé sự cân bằng giữa số cung và số cầu. nhất ô B-2 11/26/2013 37 11/26/2013 38 PGS. Dr. Nguyễn Thống PGS. Dr. Nguyễn Thống PHƯƠNG PHÁP ĐỊNH LƯỢNG TRONG QUẢN LÝ PHƯƠNG PHÁP ĐỊNH LƯỢNG TRONG QUẢN LÝ Chương 4: Bài toán vận tải Chương 4: Bài toán vận tải • Bước 3: Sau khi thỏa mãn một hàng hay một Bước 3: Phương pháp Vogel : nào thì đánh dấu (-) và các ô bị loại của hàng Trạm thu Trạm phát 1 2 3 hay cột đó. Ô loại là ô có x = 0. ij 60T 70T 110T Tiếp tục lập lại quá trình trên cho các ô còn A 150T 6$ 10$ 4$ 2 lại cho đến khi thỏa mãn hết các hàng và cột B 90T 12$ (-) 8$ 4 thì thôi. 6 8 4 Dòng hoặc cột nào thỏa mãn rồi thì đánh chữ k (kết thúc) để về sau khỏi xét nữa. Loại ở bước 3 Kiểm tra về điều kiện: 11 /26/2013Tổng số ô chọn = m + n -1. 39 11/26/2013 40 PGS. Dr. Nguyễn Thống PGS. Dr. Nguyễn Thống PHƯƠNG PHÁP ĐỊNH LƯỢNG TRONG QUẢN LÝ PHƯƠNG PHÁP ĐỊNH LƯỢNG TRONG QUẢN LÝ Chương 4: Bài toán vận tải Chương 4: Bài toán vận tải Bước 3: Phương pháp Vogel : Bước 3: Phương pháp Vogel : Trạm thu Trạm thu Trạm phát 1 3 Trạm phát 1 3 60T 110T 60T 110T A 150T 6$ 4$ 2 A 150T 60 4$ 2 B 90T 12$ 8$ 4 B 90T 12$ (70) 8$ 4 4 4 6 6 Giá trị (6) cột 1 là lớn nhất, kết hợp giá nhỏ Giá trị (6) cột 1 là lớn nhất, kết hợp giá nhỏ nhất phân phối ô A-1. nhất phân phối ô A-1. Và sau đó loại cột số 1 vì trạm thi 1 đã thỏa mãn. 11/26/2013 41 11/26/2013 42 PGS. Dr. Nguyễn Thống PGS. Dr. Nguyễn Thống 7
8. PHƯƠNG PHÁP ĐỊNH LƯỢNG TRONG QUẢN LÝ PHƯƠNG PHÁP ĐỊNH LƯỢNG TRONG QUẢN LÝ Chương 4: Bài toán vận tải Chương 4: Bài toán vận tải Bước 3: Phương pháp Vogel : Bước 3: Phương pháp Vogel : Trạm thu Trạm thu Trạm phát 1 3 Trạm phát 1 3 60T 110T 60T 110T A 150T (60) 4$ A 150T (60) 90 (4$) B 90T (70) 8$ B 90T (70) 8$ 4 4 Loại Và sau đó loại cột số 1 vì trạm thi 1 đã thỏa Cột 3 còn lại có có ô A-3 chi phí bé ta sẽ mãn. phân phối giá trị vào đó (chú ý đến điều kiện cân bằng theo hàng trường hợp này). 11/26/2013 43 11/26/2013 44 PGS. Dr. Nguyễn Thống PGS. Dr. Nguyễn Thống PHƯƠNG PHÁP ĐỊNH LƯỢNG TRONG QUẢN LÝ PHƯƠNG PHÁP ĐỊNH LƯỢNG TRONG QUẢN LÝ Chương 4: Bài toán vận tải Chương 4: Bài toán vận tải Bước 3: Phương pháp Vogel : Bài tập 1: Dùng các phương pháp góc Tây Bắc, Cmin Trạm thu và Vogel để tìm lời giải ban đầu cho bài toán sau: Trạm phát 1 3 60T 110T Đến Khả A 150T (60) (90) Từ X Y Z năng B 90T (70) 20 A 5 4 3 100 Kết quả cuối cùng là phân bổ vào B-3. 4 B 8 4 3 300 Lời giải chi phí cho phương pháp Vogel như sau: C 9 7 5 300 F=60*6+90*4+70*2+20*8=1020$ (tốt HƠN so Yêu cầu 300 200 200 =700 với p/p góc Tây Bắc và Cmin 1060$) 11/26/2013 45 11/26/2013 46 PGS. Dr. Nguyễn Thống PGS. Dr. Nguyễn Thống PHƯƠNG PHÁP ĐỊNH LƯỢNG TRONG QUẢN LÝ PHƯƠNG PHÁP ĐỊNH LƯỢNG TRONG QUẢN LÝ Chương 4: Bài toán vận tải Chương 4: Bài toán vận tải Đáp số: Phương pháp Vogel Bài tập 2: Dùng các phương pháp góc Tây Bắc, Cmin và Vogel để tìm lời giải ban đầu cho bài Đến Khả toán sau: Từ X Y Z năng Đến A 100 100 Từ X Y Z Khả năng B 200 100 300 A 5 2 7 200 C 200 100 300 B 9 6 1 300 Yêu cầu 300 200 200 C 10 13 3 500 11/26/2013 47 11/26/2013 48 PGS. Dr. Nguyễn Thống PGS.Yêu Dr. cầu Nguyễn Thống300 200 200 1&2 ! 8
9. PHƯƠNG PHÁP ĐỊNH LƯỢNG TRONG QUẢN LÝ PHƯƠNG PHÁP ĐỊNH LƯỢNG TRONG QUẢN LÝ Chương 4: Bài toán vận tải Chương 4: Bài toán vận tải Lấy ví dụ 1 nói trên và lời giải ban đầu Cmin có Z=1060$. LỜI GIẢI TỐI ƯU BÀI TOÁN VẬN TẢI Trạm thu Trạm phát 1 2 3 PHƯƠNG PHÁP THẾ VỊ 60T 70T 110T A 150T 40 (6) (10) 110 (4) B 90T 20 (12) 70 (2) (8) Dùng phương pháp thế vị để tìm lời giải tối ưu. 11/26/2013 49 11/26/2013 50 PGS. Dr. Nguyễn Thống PGS. Dr. Nguyễn Thống PHƯƠNG PHÁP ĐỊNH LƯỢNG TRONG QUẢN LÝ PHƯƠNG PHÁP ĐỊNH LƯỢNG TRONG QUẢN LÝ Chương 4: Bài toán vận tải Chương 4: Bài toán vận tải Xét sự hoán vị kiến nghị nêu trên ta có: Bài tập: Cho bài toán vận tải được trình bày ở bảng B(1) A(1): tiết kiệm 12-6=6 ĐV sau: A(3) B(3): mất 4-8 =-4ĐV Thu Phát 75 60 65 Tiết kiệm: 6Đ-4ĐV =2ĐV Nên thực hiện Trạm thu 100 5 4 1 Trạm phát 1 2 3 50 2 6 3 60T 70T 110T 50 10 7 2 A 150T 60 (6) (10) 90 (4) a/ Lập phương án đầu bằng phương pháp góc Tây B 90T 00 (12) 70 (2) 20 (8) Bắc, phương pháp Cmin. F=60*6+90*4+ 20*8+70*2= 1020$ <1060$ b/ Dựa trên kết quả của phương pháp góc Tây Bắc hãy tìm phương án tối ưu. 11/26/2013 51 11/26/2013 52 PGS. Dr. Nguyễn Thống PGS. Dr. Nguyễn Thống PHƯƠNG PHÁP ĐỊNH LƯỢNG TRONG QUẢN LÝ PHƯƠNG PHÁP ĐỊNH LƯỢNG TRONG QUẢN LÝ Chương 4: Bài toán vận tải Chương 4: Bài toán vận tải Ví dụ: Một Công ty mua 3 máy mới A, B, C và có 4 vị trí có thể đặt máy. Ước tính chi phí đặt mỗi máy vào mỗi vị trí được cho như sau, trong đó máy B không thể đặt ở vị trí 2. BÀI TOÁN PHÂN CÔNG Tìm các vị trí hợp lý cho A, B, C sao cho chi phí nhỏ nhất. (The assigment problem) Vị trí Máy 1 2 3 4 A 13 10 12 11 B 15 - 13 20 C 5 7 10 6 11/26/2013 53 11/26/2013 54 PGS. Dr. Nguyễn Thống PGS. Dr. Nguyễn Thống 9
10. PHƯƠNG PHÁP ĐỊNH LƯỢNG TRONG QUẢN LÝ PHƯƠNG PHÁP ĐỊNH LƯỢNG TRONG QUẢN LÝ Chương 4: Bài toán vận tải Chương 4: Bài toán vận tải PHƯƠNG PHÁP HUNGARY PHƯƠNG PHÁP HUNGARY Bước 1: Tìm bảng chi phí cơ hội Bước 2: Thử điều kiện tối ưu Trừ chi phí nhỏ nhất trong mỗi hàng Vẽ một số tối thiểu các đường thẳng trên vào mọi phần tử trong hàng ấy. hàng hay trên cột mà đi qua mọi số 0 Trừ chi phí nhỏ nhất trong mỗi cột trong bảng. vào mọi chi phí trong cột ấy (có được từ Nếu số đường thẳng bằng số hàng hay số a). cột (bằng n) thì có lời giải tối ưu như sau: 11/26/2013 55 11/26/2013 56 PGS. Dr. Nguyễn Thống PGS. Dr. Nguyễn Thống PHƯƠNG PHÁP ĐỊNH LƯỢNG TRONG QUẢN LÝ PHƯƠNG PHÁP ĐỊNH LƯỢNG TRONG QUẢN LÝ Chương 4: Bài toán vận tải Chương 4: Bài toán vận tải a. Phân phối vào ô có số 0. Ưu tiên phân vào Bước 3: Tạo ra bảng chi phí cơ hội mới ô có số 0 duy nhất nằm trên giao điểm của Trừ số nhỏ nhất chưa nằm trên một hàng và một cột. đường thẳng nào vào mọi số chưa nằm b. Loại bỏ hàng và cột chứa số 0 đã phân trên đường thẳng nào. phối. Quay về bước a và tiếp tục cho đến khi phân phối xong. Cộng số nhỏ nhất ấy vào mọi số nằm Nếu số đường thẳng tối thiểu nhỏ hơn n, chúng trên giao điểm của hai đường thẳng. ta chuyển qua bước 3. Trở lại bước 2. 11/26/2013 57 11/26/2013 58 PGS. Dr. Nguyễn Thống PGS. Dr. Nguyễn Thống PHƯƠNG PHÁP ĐỊNH LƯỢNG TRONG QUẢN LÝ PHƯƠNG PHÁP ĐỊNH LƯỢNG TRONG QUẢN LÝ Chương 4: Bài toán vận tải Chương 4: Bài toán vận tải Bước 1a Min hàng 1 Máy \Vị trí 1 2 3 4 Vị trí Máy 1 2 3 4 A 3 0 2 1 B 2 M 0 7 A 13 10 12 11 C 0 2 5 1 B 15 M 20 13 D 0 0 0 0 C 5 7 10 6 Bước 1b (không cần trong t/h này) D 0 0 0 0 11/26/2013 Mỗi hàng xác định chi phí Min 59 11/26/2013 60 PGS. Dr. Nguyễn Thống PGS. Dr. Nguyễn Thống 10
11. PHƯƠNG PHÁP ĐỊNH LƯỢNG TRONG QUẢN LÝ PHƯƠNG PHÁP ĐỊNH LƯỢNG TRONG QUẢN LÝ Chương 4: Bài toán vận tải Chương 4: Bài toán vận tải Bước 2 Ví dụ: Có 3 người X, Y, Z. Mỗi người có thể làm 1 trong 3 việc 1, 2, 3 với chi phí cho ở bảng sau. Hãy Máy \Vị trí phân công sao cho tổng chi phí là nhỏ nhất. 1 2 3 4 A 3 0 2 1 1 2 3 B 2 M 0 7 X 11 14 6 C 0 2 5 1 D 0 0 0 0 Y 8 10 11 Số đường ngang = Số đường thẳng tìm lời giải. Z 9 12 7 Máy A vị trí 2, máy B vị trí 3 và máy C vị trí 1. 11/26/2013 61 11/26/2013 Chi phí 62 PGS. Dr. Nguyễn Thống PGS. Dr. Nguyễn Thống PHƯƠNG PHÁP ĐỊNH LƯỢNG TRONG QUẢN LÝ PHƯƠNG PHÁP ĐỊNH LƯỢNG TRONG QUẢN LÝ Chương 4: Bài toán vận tải Chương 4: Bài toán vận tải Bước 2: Số đường thẳng bằng 2 nhỏ hơn số hàng 1 2 3 bằng số cột và bằng 3 X 11 14 6 ===> lời giải chưa tối ưu Y 8 10 11 Bước 3a: Trừ số nhỏ nhất chưa nằm trên đường Z 9 12 7 thẳng nào vào mọi số chưa nằm trên đường thẳng nào. 1 2 3 Bảng 0 1 2 3 X 5 8 0 X 5( 3) 8( 6) 0 Y 0 2 3 Y 0 2 (0) 3 Z 2 5 0 Z 2( 0) 5( 3) 0 11/26/2013 63 11/26/2013 64 PGS. Dr. Nguyễn Thống PGS. Dr. Nguyễn Thống PHƯƠNG PHÁP ĐỊNH LƯỢNG TRONG QUẢN LÝ PHƯƠNG PHÁP ĐỊNH LƯỢNG TRONG QUẢN LÝ Chương 4: Bài toán vận tải Chương 4: Bài toán vận tải Bước 3b: Cộng số nhỏ nhất ấy vào mọi số nằm trên Bài tập: Dùng Solver trong Excel để giao điểm của hai đường thẳng. giải các bài tập nêu trên. Bảng 0 1 2 3 X 3 6 0 Y 0 0 5 Z 0 3 0 Số đường ngang = Sồ đường đứng Có lời giải tối ưu (X=3, Y=2, Z=1). 11/26/2013 65 11/26/2013 66 PGS. Dr. Nguyễn Thống PGS. Dr. Nguyễn Thống 11
12. PHƯƠNG PHÁP ĐỊNH LƯỢNG TRONG QUẢN LÝ Chương 4: Bài toán vận tải HẾT CHƯƠNG 11/26/2013 67 PGS. Dr. Nguyễn Thống 12