intTypePromotion=1
zunia.vn Tuyển sinh 2024 dành cho Gen-Z zunia.vn zunia.vn
ADSENSE
 » 
 » 

Bài giảng Toán kinh tế: Bài toán vận tải mở rộng

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:49

Thêm vào BST
Báo xấu
39
lượt xem 13
download
 
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài giảng "Toán kinh tế: Bài toán vận tải mở rộng" được biên soạn với các nội dung chính sau: Bài toán không cân bằng thu phát; Bài toán vận tải với ràng buộc bất đẳng thức; Bài toán lập kho hàng; Bài toán vận tải có ô cấm; Bài toán vận tải dạng max; Bài toán phân việc. Mời các bạn cùng tham khảo bài giảng!

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 Toán kinh tế: Bài toán vận tải mở rộng

  1. Bài toán vận tải mở rộng GV : Phạm Thị Hoài Viện Toán ứng dụng và Tin học Trường Đại học Bách khoa Hà Nội 1 / 49
  2. Nội dung chính 1 Bài toán không cân bằng thu phát Cung lớn hơn cầu Cầu lớn hơn cung 2 Bài toán vận tải với ràng buộc bất đẳng thức 3 Bài toán lập kho hàng Phương pháp giải Ví dụ 3.1 4 Bài toán vận tải có ô cấm Phương pháp giải Ví dụ 4.1 5 Bài toán vận tải dạng max Phương pháp giải Ví dụ 5.1 6 Bài toán phân việc Thuật toán Hungarian Ví dụ 6.1 2 / 49
  3. Bài toán không cân bằng thu phát Nội dung 1 Bài toán không cân bằng thu phát Cung lớn hơn cầu Cầu lớn hơn cung 2 Bài toán vận tải với ràng buộc bất đẳng thức 3 Bài toán lập kho hàng Phương pháp giải Ví dụ 3.1 4 Bài toán vận tải có ô cấm Phương pháp giải Ví dụ 4.1 5 Bài toán vận tải dạng max Phương pháp giải Ví dụ 5.1 6 Bài toán phân việc Thuật toán Hungarian Ví dụ 6.1 3 / 49
  4. Bài toán không cân bằng thu phát Cung lớn hơn cầu Bài toán đặt ra cung lớn hơn cầu Tức là: m n X X ai > bj i=1 j=1 Mô hình bài toán: m X n X min f (x) = cij xij (1) i=1 j=1 n X v.đ.k. xij ≤ ai , i = 1, · · · , m j=1 m X xij = bj , j = 1, · · · , n i=1 xij ≥ 0, i = 1, · · · , m, j = 1, · · · , n. 4 / 49
  5. Bài toán không cân bằng thu phát Cung lớn hơn cầu Phương pháp giải Ta chỉ cần thêm vào điểm thu giả với cước phí tại các ô đó đều là 0. Bài toán với m điểm phát và n+1 điểm thu là : m n+1 X X min f (x) = cij xij (2) i=1 j=1 n+1 X v.đ.k. xij = ai , i = 1, · · · , m j=1 m X xij = bj , j = 1, · · · , n + 1 i=1 xij ≥ 0, i = 1, · · · , m, j = 1, · · · , n + 1. m X n X Với bn+1 = ai − bj i=1 j=1 5 / 49
  6. Bài toán không cân bằng thu phát Cung lớn hơn cầu Ví dụ 1.1 Xét Bài toán không cân bằng thu phát được cho bởi bảng vận tải dưới đây bj 80 70 100 90 ai 6 5 3 1 100 9 7 5 8 160 2 9 4 6 140 6 / 49
  7. Bài toán không cân bằng thu phát Cung lớn hơn cầu Ví dụ 1.1(tiếp) Ta thêm trạm thu giả n+1=5 với yêu cầu là b5 = 400 − 340 = 60 và đặt c15 = c25 = c35 = 0. bj 80 70 100 90 60 ai 6 5 3 1 0 100 9 7 5 8 0 160 2 9 4 6 0 140 7 / 49
  8. Bài toán không cân bằng thu phát Cung lớn hơn cầu Ví dụ 1.1(tiếp) vj −4 0 −2 1 0 ui bj 80 70 100 90 60 ai 6 5 3 1 0 0 100 + − −10 −5 −5 40 60 9 7 5 8 0 7 160 − + −6 70 40 50 7 2 9 4 6 0 6 140 80 −3 60 1 6 8 / 49
  9. Bài toán không cân bằng thu phát Cung lớn hơn cầu Ví dụ 1.1(tiếp) vj 3 7 5 1 0 ui bj 80 70 100 90 60 ai 6 5 3 1 0 0 100 −3 2 2 90 10 9 7 5 8 0 0 160 −6 70 40 −7 50 2 9 4 6 0 −1 140 80 −3 60 −6 −1 9 / 49
  10. Bài toán không cân bằng thu phát Cung lớn hơn cầu Ví dụ 1.1(tiếp) vj 1 5 3 1 −2 ui bj 80 70 100 90 60 ai 6 5 3 1 0 0 100 −5 0 10 90 −2 9 7 5 8 0 2 160 −6 70 30 −5 60 2 9 4 6 0 1 140 80 −3 60 −4 −1 10 / 49
  11. Bài toán không cân bằng thu phát Cung lớn hơn cầu Ví dụ 1.1(tiếp) Bảng tương ứng với phương án cực biên tối ưu x∗ của bài toán:   0 0 10 90 0 ∗ x =  0 70 30 0 60   80 0 60 0 0 Trở lại bài toán ban đầu, ta có phương án vận chuyển tối ưu là   0 0 10 90 xopt =  0 70 30 0    80 0 60 0 với giá trị tối ưu là f (xopt ) = 1160. 11 / 49
  12. Bài toán không cân bằng thu phát Cầu lớn hơn cung Cầu lớn hơn cung Bài toán Tức là: m n X X ai < bj i=1 j=1 Mô hình bài toán: m X n X min f (x) = cij xij (3) i=1 j=1 n X v.đ.k. xij = ai , i = 1, · · · , m j=1 m X xij ≤ bj , j = 1, · · · , n i=1 xij ≥ 0, i = 1, · · · , m, j = 1, · · · , n. 12 / 49
  13. Bài toán không cân bằng thu phát Cầu lớn hơn cung Phương pháp giải Ta chỉ cần thêm vào điểm phát giả với cước phí tại các ô đó đều là 0. Bài toán với m+1 điểm phát và n điểm thu là : m+1 XX n min f (x) = cij xij (4) i=1 j=1 n X v.đ.k. xij = ai , i = 1, · · · , m + 1 j=1 m+1 X xij = bj , j = 1, · · · , n i=1 xij ≥ 0, i = 1, · · · , m + 1, j = 1, · · · , n. n X m X Với am+1 = bj − ai j=1 i=1 13 / 49
  14. Bài toán vận tải với ràng buộc bất đẳng thức Nội dung 1 Bài toán không cân bằng thu phát Cung lớn hơn cầu Cầu lớn hơn cung 2 Bài toán vận tải với ràng buộc bất đẳng thức 3 Bài toán lập kho hàng Phương pháp giải Ví dụ 3.1 4 Bài toán vận tải có ô cấm Phương pháp giải Ví dụ 4.1 5 Bài toán vận tải dạng max Phương pháp giải Ví dụ 5.1 6 Bài toán phân việc Thuật toán Hungarian Ví dụ 6.1 14 / 49
  15. Bài toán vận tải với ràng buộc bất đẳng thức Bài toán Trong thực tế, nhiều mô hình bài toán vận tải có dạng: m X X n min f (x) = cij xij (5) i=1 j=1 n X v.đ.k. xij ≤ ai , i = 1, · · · , m j=1 m X xij ≥ bj , j = 1, · · · , n i=1 xij ≥ 0, i = 1, · · · , m, j = 1, · · · , n. 15 / 49
  16. Bài toán vận tải với ràng buộc bất đẳng thức Định lý tồn tại nghiệm Định lý 1 Bài toán vận tải có phương án tối ưu khi và chỉ khi tổng lượng phát không bé hơn tổng lượng thu, nghĩa là m X n X ai ≥ bj (6) i=1 j=1 16 / 49
  17. Bài toán vận tải với ràng buộc bất đẳng thức Phương pháp giải Trường hợp 1: Ta có m X n X ai = bj , i=1 j=1 tức bài toán thỏa mãn điều kiện cân bằng thu phát. Trường hợp 2: Ta có m X n X ai > bj , i=1 j=1 tức tổng lượng phát lớn hơn tổng lượng thu. 17 / 49
  18. Bài toán lập kho hàng Nội dung 1 Bài toán không cân bằng thu phát Cung lớn hơn cầu Cầu lớn hơn cung 2 Bài toán vận tải với ràng buộc bất đẳng thức 3 Bài toán lập kho hàng Phương pháp giải Ví dụ 3.1 4 Bài toán vận tải có ô cấm Phương pháp giải Ví dụ 4.1 5 Bài toán vận tải dạng max Phương pháp giải Ví dụ 5.1 6 Bài toán phân việc Thuật toán Hungarian Ví dụ 6.1 18 / 49
  19. Bài toán lập kho hàng Bài toán Giả sử một tập đoàn gồm m nhà máy sản xuất một loại hàng hóa với sản lượng tương ứng là ai , i = 1, ..., m và họ đã sản xuất sẵn nold kho chứa hàng với trữ lượng là b1 , b2 , ..., bnold . Người ta định xây dựng nnew kho mới. Bài toán đặt ra là mỗi kho mới phải được thiết kế để chứ bao nhiêu hàng và tìm phương án vận chuyển hết hàng từ m nhà máy đến n = nold + nnew kho sao cho chi phí vận chuyển là nhỏ nhất với giả thiết các kho mới có thể chứa được lượng hàng không hạn chế. Cho biết cước phí vận chuyển một đơn vị hàng từ nhà máy i đến kho j là cij ; i = 1, ..., m; j = 1, ..., n. 19 / 49
  20. Bài toán lập kho hàng Phương pháp giải Phương pháp giải Ta có thể dể dàng đưa bài toán về dạng vận tải cầu vượt cung bằng việc đặt: m X bj = ai , ∀j = nold + 1, ..., nold + nnew i=1 Do đó, ta chỉ cần thêm điểm phát giả với lượng phát: n X m X am+1 = bj − ai j=1 i=1 và cm+1,j = 0; ∀j = 1, ..., n. 20 / 49
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN
TRỢ GIÚP
HỖ TRỢ KHÁCH HÀNG
Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.

 

Đồng bộ tài khoản
6=>0