Bài giảng "Kinh tế lượng - Chương 4: Bài toán vận tải" cung cấp cho người học các kiến thức: Mô hình vận tải, giải bài toán vận tải, giải bài toán vận tải sử dụng máy tính, mở rộng ứng dụng mô hình vận tải. Mời các bạn cùng tham khảo nội dung chi tiết.
Phụ trách: TS. Đinh Bá Hùng Anh Tel: 01647.077.055/090.9192.766 Mail: anhdbh_ise7@yahoo.com
■ Mô hình vận tải
■ Giải bài toán vận tải
■ Giải bài toán vận tải sử dụng máy tính
■ Mở rộng ứng dụng mô hình vận tải
Bao nhiêu tấn hàng chuyển vận từ nhà cung cấp đến hệ thống siêu thị hàng
tháng với tiêu chí cực tiểu phí vận chuyển?
Nhà cung cấp Cung ứng Siêu thị Yêu cầu
1. Kansas City 150 A. Chicago 220
2. Omaha 175 B. St. Louis 100
3. Des Moines 275 C. Cincinnati 300
Tổng 600 tons Tổng 600 tons
Giá vận chuyển ($/ton)
Nhà cung cấp A. Chicago B. St. Louis C. Cincinnati
1.Kansas City 2.Omaha 3.Des Moines $ 6 7 4 $ 8 11 5 $ 10 11 12
Minimize Z = 6x1A + 8x1B + 10x1C + 7x2A + 11x2B + 11x2C +
4x3A + 5x3B + 12x3C
st:
x1A + x1B + x1C = 150 x2A + x2B + x2C = 175 x3A + x3B + x3C = 275 x1A + x2A + x3A = 200 x1B + x2B + x3B = 100 x1C + x2C + x3C = 300 xij ≥ 0
xij = Tấn hàng được chuyển từ nhà cung cấp i, i = 1, 2, 3, đến nhà máy j, j = A,B,C
• Bài toán vận tải có thể giải bằng tay thông qua bảng vận tải
• Mỗi ô của bảng vận tải tương tự như biến ở bài toán tối ưu để chỉ chi phí cho việc di chuyển từ nhà cung cấp đến đích.
• Khả năng của nhà cung cấp và yêu cầu từ đích sẽ được ghi ở cột bên phải và hàng cuối của bảng vận tải.
- Phương pháp góc Tây Bắc
- Phương pháp chi phí bé nhất
- Phương pháp xấp xỉ Vogel
- Duyệt tuần tự
- Phân phối cải tiến.
- Phân bổ nhiều nhất có thể vào ô góc trên bên trái của bảng vận tải. Khấu trừ lượng cung ở nguồn và lượng cầu ở đích tương ứng. Lượng cung (cầu) thừa (thiếu) được phân bổ nhiều nhất có thể đến các ô góc trên bên trái tương ứng.
- Lời giải của bài toán vận tải được xác định khi tất cả yêu cầu của đích được thảo mãn.
- Chi phí vận chuyển được tính dựa vào hàm mục tiêu: Z = 6x1A + 8x1B + 10x1C + 7x2A + 11x2B + 11x2C + 4x3A + 5x3B + 12x3C
= 6(150) + 8(0) + 10(0) + 7(50) + 11(100) + 11(25) + 4(0) + 5(0) + 12(275) = 5,925 $
- Phân bổ nhiều nhất có thể vào các ô có chi phí đơn vị bé nhất.
(cid:41)
Phương pháp góc Tây-Bắc tuy đơn giản nhưng thường cho lời giải không tốt vì không tính đến chi phí. Phương pháp Chi phí thấp nhất có xét đến chi phí.
- Chi phí vận chuyển được tính bởi phương pháp chi phí thấp nhất = 4,550 $.
- Phương pháp này dựa trên định nghĩa chi phí cơ hội.
- Chi phí cơ hội là sự khác biệt giữa chi phí bé nhất với chi phí bé kế trong
cùng hàng (hay cột).
Bước 1. Xác định chi phí cơ hội cho mỗi hàng và cột.
Bước 2. Chọn hàng hay cột có chi phí cơ hội lớn nhất.
Bước 3. Phân bổ hàng hóa đến ô có chi phí đơn vị bé nhất trong hàng
hay cột có chi phí cơ hội lớn nhất.
Bước 4. Lặp lại bước 1,2 và 3 cho đến khi nào tất cả nguồn và đích đều
thỏa mãn
Xác định hàng hay cột có chi phí cơ hội lớn nhất.
6
8
10
A B C Nguồn
1
11
7
11
2 150
2
4
5
12
4* 175
3
1 275
600 Đích 200 100 300
2 3 1
- Phân bổ tối đa lượng hàng có thể vận chuyển được đến ô có chi phí vận chuyển đơn vị bé nhất ứng với hàng hoặc cột có chi phí cơ hội lớn nhất.
- Loại bỏ hàng đã dùng hết khả năng cung cấp hay cột đã thỏa mãn nhu cầu.
- Tính lại chi phí cơ hội cho những hàng/cột còn lại.
6
8
10
A B C Nguồn
1
11
7
11
2 150
2
4
5
12
175 175
3
1 275
200 100 300 600 Đích
2 3* 1
- Phân bổ tối đa hàng hóa đến ô (3,2) - Tính lại chi phí cơ hội sau đi đã phân bổ và bỏ đi cột B (Vì đã thỏa mãn nhu cầu, đủ 100)
8
6
10
A B C Nguồn
1
11
11
7
4 150
2
5
4
12
175 175
3
8* 275 100
300 600 Đích 100 200
2 2
- Phân bổ hàng hóa đến hàng 3.
6
8
10
A B C Nguồn
1
11
7
11
150
2
4
5
12
175 175
3
275 25 100 150
Đích 200 100 300 600
- Phân bổ hàng hóa còn lại đến ô (1,3) để hoàn thiện bảng vận tải. - Giải pháp tối ưu, chi phí vận chuyển = 5,125 $ - Phương pháp xấp xỉ Vogel và cực tiểu chi phí cho kết quả tốt hơn phương pháp góc Tây Bắc.
- Phương pháp duyệt tuần tự (the stepping-stone) và phân phối cải tiến (the modified distribution MODI) được dùng để tìm nghiệm tối ưu cho bài toán không suy biến(*).
- Lời giải ban đầu được xác định bằng một trong 3 phương pháp đã biết. Lời giải cải tiến được xác định thông qua các bước sau:
Bước 1: Tính chỉ số cải tiến Iij cho tất cả các ô rỗng trong bảng vận tải.
Cách tính chỉ số này được nêu ở ví dụ ở slide tiếp theo.
Bước 2: Nếu các chỉ số Iij của mọi ô rỗng đều ≥ 0, lời giải hiện tại là tối ưu. Nếu tồn tại một số giá trị Iij âm, chọn ô có Iij âm nhất, điều chỉnh lượng hàng lượng hàng vận chuyển trên các ô liên quan.
Bước 3: Xác định lại bảng vận tải và quay lại bước 1
(*) Một bài toán vận tải không suy biến nếu như trong bảng vận tải, số ô có gán giá trị bằng: m + n – 1. Trong đó: m: nguồn (hàng); n: đích (cột).
- Xác định ô rỗng, cộng thêm 1 đơn vị cho này
+1
- Trừ bớt một đơn vị hàng hóa cho ô cùng hàng thuộc chu trình.
Xác định chu trình để tính chỉ số cải tiến Iij
Xác định chỉ số cải tiến Iij cho các ô còn lại.
min =
- Sau khi xác định chỉ số cải tiến Iij cho tất cả các ô, chọn ô có chỉ số cải tiến âm nhất để tiến hành điều chỉnh lượng hàng hóa trên ô. Ở bài toán này, chọn ô 1A. - Xác định ô có giá trị âm nhất trong các ô được gán min. X1B dầu (-), xij min (x1B, x3A) = min (200, 25) = 25. - Lượng hàng vận chuyển ở các ô được gán dấu (+) min, được cộng thêm x1B các ô gán dấu (–) được min. trừ đi một lượng x1B - Chiều quay của chu trình không làm ảnh hưởng đến kết quả của bài toán.
Sau điều chỉnh, tiến hành tính toán lại chỉ số tải tiến Iij cho các ô trống.
Tính lại chỉ số cải tiến Iij
(cid:41)
Dừng tìm kiếm trị tối ưu vì chỉ số cải tiến Iij ở các ô trống không âm.
x1A = 25 tons, x2C = 175 tons, x3A = 175 tons, x1C = 125 tons, x3B = 100 tons Z = $6(25) + 8(0) + 10(125) + 7(0) + 11(0) + 11(175) + 4(175) + 5(100) + 12(0)
= 4,525 $
Phương pháp phân phối cải tiến từ phương pháp duyệt tuần từ với việc thay đổi cách tính chỉ số cải tiến. Các bước của phương pháp phân phối cải tiến.
Bước 1: Xác định giải pháp ban đầu
Bước 2: Ở bảng vận tải, thêm cột bên trái ui và hàng bên trên vj. Trị tại tất cả các ô được xác định bằng công thức: ui + vj = cij = Chi phí đơn vị tại ôij Bước 3: Tính chỉ số cải tiến kij cho tất cả các ô rỗng. kij = cij - ui – vj Bước 4: Chọn ô có chỉ số cải tiến kij âm nhất để phân bổ lại hàng hóa. Bước 5: Lặp lại bước 2-4, (Bước 2: không thêm cột ui, hàng vj mà chỉ định lại trị) cho đến nào chỉ số cải tiến không âm.
x1B: u1 + vB = 8 (1)
x1C: u1 + vC = 10 (2)
x2C: u2 + vC = 11 (3)
x3A: u3 + vA = 4 (4)
x3B: u3 + vB = 5 (5)
Thiết lập công thức tính chi phí đơn vị cho các ô có gán giá trị:
Từ 5 phương trình - 6 biến, để giải, giả sử u1 = 0 ta định trị cho các chỉ số ui, vj
u2 = 1, u3 = -3, vA= 7, vB = 8, vC = 10
Dùng công thức sau để tính chỉ số cải tiến:
kij =cij - ui - vj
-
+
+
-
Chỉ số cải tiến cho những ô trống ở hình 4.26 x1A: k1A = c1A - u1 - vA = 6 - 0 - 7 = -1 x2A: k2A = c2A - u2 - vA = 7 - 1 - 7 = -1 x2B: k2B = c2B - u2 - vB
= 11- 1 - 8 = +2
x3C: k3C = c3C - u3 -vC
= 12 - (-3) - 10 = +5
(cid:41)
min = 25.
Chỉ số cải tiến tại x1A âm nhất và tạo thành chu trình, nên điều chỉnh lượng hàng ở chu trình này theo x1B
Sau đó tính lại trị cho các chỉ số ui, vj
Tính lại trị cho các chỉ số ui, vj, với u1 = 0.
x1A: u1 + vA = 6, vA = 6 x1C: u1 + vC = 10, vC = 10 x2C: u2 + vC = 11, u2 = 1 x3A: u3 + vA = 4, u3 = -2 x3B: u3 + vB = 5, vB = 7
Chỉ số cải tiến của các ô rỗng, kij = cij - ui - vj
x1B: k1B = c1B - u1 - vB = 8 - 0 - 7 = +1 x2A: k2A = c2A - u2 - vA = 7 - 1 - 6 = 0 x2B: k2B = c2B - u2 - vB = 11 - 1 -7 = +3 x3C: k2B = c2B - u3 - vC = 12 - (-2) - 10 = +4
Do các chỉ số cải tiến không âm, giải pháp hiện tại là tối ưu.
Chỉ số tải tiến ở ô 2A = 0 (cid:206) đa nghiệm.
Khi cầu vượt quá cung, một hàng giả được đưa vào bảng vận tải.
- Khi cầu vượt quá cung, cột giả được đưa vào.
- Cột hay hàng giả không ảnh hưởng đến giải pháp tối ưu.
Bài toán vận tải với m hàng, n cột thì phải có m + n – 1 ô được gán trị, nếu không thì được gọi là suy biến.
Bảng vận tải ở Hình 4.30 không thỏa điều kiện m + n – 1 = 3 + 3 – 1 = 5 nên là bài toán suy biến.
- Với bài toán suy biến, không áp dụng được phương pháp duyệt tuần tự và phân phối cải tiến.
- Để giải được bài toán suy biên, một ô với lượng vận chuyển = 0 (ô nhân tạo), có tạo thành chu trình được đưa vào bảng vận tải.
Phương pháp duyệt tuần tự Chỉ số cải tiến Iij:
2A 2C 1C 1A
x2A: 7 - 11 + 10 - 6 = 0
2B 2C 1C 1B x2B: 11 - 11 + 10 - 8 = + 2 3B 1B 1A 3A
x3B: 5 - 8 + 6 - 4 = - 1
3C 1C 1A 3A
x3C: 12 - 10 + 6 - 4 = + 4
- Đường cấm được gán chi phí vận chuyển rất lớn M.
- Khi ô cấm được tính toán, nó luôn mang chi phí vận chuyển M nên không được chọn.
■ Bài toán trung chuyển
(cid:131) Hàng hóa từ nguồn đến đích thông
qua điểm trung chuyển
(cid:131) Giữa các nguồn
(cid:131) Giữa các điểm trung chuyển
(cid:131) Trực tiếp từ nguồn đến đích
(cid:131) Hỗn hợp
Chi phí cho việc di chuyển từ nguồn đến điểm trung chuyển
Điểm trung chuyển
Nguồn 3. Kansas City 4. Omaha 5. Des Moines
1. Nebraska 2. Colorado 16$ 15 10 14 12 17
Minimize Z = $16x13 + 10x14 + 12x15 + 15x23 + 14x24
+ 17x25 + 6x36 + 8x37 + 10x38 + 7x46 + 11x47 + 11x48 + 4x56 + 5x57 + 12x58
st:
x13 + x14 + x15 = 300 x23 + x24 + x25 = 300 x36 + x46 + x56 = 200 x37 + x47 + x57 = 100 x38 + x48 + x58 = 300 x13 + x23 - x36 - x37 - x38 = 0 x14 + x24 - x46 - x47 - x48 = 0 x15 + x25 - x56 - x57 - x58 = 0 xij ≥ 0
Xây dựng mô hình và giải bài toán vận chuyển sau
Minimize Z = $8x1A + 5x1B + 6x1C + 15x2A + 10x2B + 12x2C
+3x3A + 9x3B + 10x3C
st:
x1A + x1B + x1C = 120 x2A + x2B + x2C = 80 x3A + x3B + x3C = 80 x1A + x2A + x3A ≤ 150 x1B + x2B + x3B ≤ 70 x1C + x2C + x3C ≤ 100 xij ≥ 0
