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.
AMBIENT/
Chủ đề:
Nội dung Text: Bài giảng Kinh tế lượng: Chương 4 - TS. Đinh Bá Hùng Anh
- Chapter 4
Bài toán vận tải
Phụ trách: TS. Đinh Bá Hùng Anh
Tel: 01647.077.055/090.9192.766
Mail: anhdbh_ise7@yahoo.com
- Nội dung
■ 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
- Bài toán 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 $ 6 $8 $ 10
2.Omaha 7 11 11
3.Des Moines 4 5 12
- Sơ đồ chuyển vận
Hình 4.1 Mạng lưới chuyển vận hàng hóa
- Mô hình bài toán vận tải
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ảng vận tải
• 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.
Hình 4.2: Cấu hình
bảng vận tải.
- Phương pháp giải bài toán vận tải
Phương pháp để tìm lời giải bài ban đầu
- 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
Phương pháp để tìm lời giải tối ưu
- Duyệt tuần tự
- Phân phối cải tiến.
- Phương pháp góc Tây Bắc
- 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.
Hình 4.3 Nghiện ban đầu
của bài toá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ương pháp chi phí thấp nhất
- Phân bổ nhiều nhất có thể vào các ô có chi phí đơn vị bé nhất.
Hình 4.4: Phân bổ đến Ô (3,A) đầu tiên do chi
phí đơn bị bé nhất của ô này.
) 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ó Hình 4.5: Ô kế (3,B) được chọn do chi
phí đơn vị bé của ô này.
xét đến chi phí.
- Phương pháp chi phí thấp nhất
- Chi phí vận chuyển được tính bởi phương pháp chi phí thấp nhất = 4,550 $.
Hình 4.6: Lời giải khi sử dụng phương pháp góc Tây Bắc
- Phương pháp xấp xỉ Vogel (1 of 6)
(Vogel’s Approximation Method VAM)
- 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).
Các bước để giải bài toán theo phương pháp xấp xỉ Vogel
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
- Phương pháp xấp xỉ Vogel (2 of 6)
Xác định hàng hay cột có chi phí cơ hội lớn nhất.
A B C Nguồn
6 8 10
1 150 2
7 11 11
2 175 4*
4 5 12
3 275 1
Đích 200 100 300 600
2 3 1
Hình 4.8: Xác định hàng hay cột có chi phí cơ hội lớn nhất
- Phương pháp xấp xỉ Vogel (3 of 6)
- 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.
A B C Nguồn
6 8 10
1 150 2
7 11 11
2 175
175
4 5 12
3 275 1
Hình 4.9: Phân bổ tối
đa hàng hóa đến ô có
chi phí đơn vị bé nhất Đích 200 100 300 600
2 3* 1
- Phương pháp xấp xỉ Vogel (4 of 6)
- 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)
A B C Nguồn
6 8 10
1 150 4
7 11 11
2 175
175
Hình 4.10: Phân bổ
tối đa hàng đến ô
4 5 12
(3,2) do có chi phí 3 275 8*
đơn vị bé nhất cột B 100
(Cột B được chọn do
có chi phí đơn vị lớn Đích 200 100 300 600
nhất)
2 2
- Phương pháp xấp xỉ Vogel (5 of 6)
- Phân bổ hàng hóa đến hàng 3.
A B C Nguồn
6 8 10
1 150
7 11 11
2 175
175
4 5 12
3 25 100 150 275
Đích 200 100 300 600
Hình 4.11: Hàng (3) được chọn do chi phí cơ hội lớn nhất của hàng này (=8).
- Phương pháp xấp xỉ Vogel (6 of 6)
- 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.
Hình 4.12: Kết quả của bài toán khi áp dụng phương pháp xấp xỉ Vogel
- Phương pháp duyệt tuần tự (1 of 9)
(The Stepping-Stone Solution Method)
- 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).
- Phương pháp duyệt tuần tự (2 of 9)
- Xác định ô rỗng, cộng thêm 1 đơn vị cho này
+1
201
Hình 4.13: Do được cộng thêm một đơn vị hàng hóa (ô 1A), số hàng hóa
yêu cầu từ nhà cung cấp và yêu cầu của đích đều tăng 1.
- Phương pháp duyệt tuần tự (3 of 9)
- Trừ bớt một đơn vị
hàng hóa cho ô cùng
hàng thuộc chu trình.
Hình 4.14: Do bị trừ đi một
đơn vị hàng hóa ở ô cùng
hàng thuộc chu trình (1B),
số hàng hóa yêu cầu từ nhà
cung cấp B giảm 1
201
Hình 4.15: Một số chu trình thường gặp
- Phương pháp duyệt tuần tự (4 of 9)
Xác định chu trình để tính chỉ số cải tiến Iij
1A → 1B → 3B → 3A
6$ - 8 + 5 – 4 = -1 $
Hình 4.16: Thêm một đơn vị cho ô 3B và trừ 1 đơn vị cho ô 3A để tạo thành chu trình
Thêm vào BST
Báo xấu
Download
Vui lòng tải xuống để xem tài liệu đầy đủ
