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

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

Thêm vào BST
Báo xấu
39
lượt xem 3
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" được biên soạn với các nội dung chính sau: Bài toán vận tải và các khái niệm, tính chất liên quan; Thuật toán thế vị giải bài toán vận tải; Bài toán vận tải mở rộng. 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

  1. BÀI TOÁN VẬN TẢI Lecturer: Phạm Thị Hoài Department of Applied Mathematics - School of Applied Mathematics and Informatics Hanoi University of Science and Technology hoai.phamthi@hust.edu.vn 0 / 21
  2. Content 1 Bài toán vận tải và các khái niệm, tính chất liên quan Mô hình bài toán vận tải Điều kiện tồn tại nghiệm Chu trình và phương án cực biên của bài toán vận tải 2 Thuật toán thế vị giải bài toán vận tải Cơ sở lí thuyết Thuật toán thế vị 3 Bài toán vận tải mở rộng hoai.phamthi@hust.edu.vn 1 / 21
  3. Bài toán vận tải và các khái niệm, tính chất liên quan Mô hình bài toán vận tải Bài toán vận tải Kế hoạch: Cần phát hàng từ m kho {K1 , ..., Km } đến n cửa hàng {H1 , ..., Hn }. Dữ kiện: Lượng hàng cần phát từ kho Ki là ai ; cửa hàng Hj cần nhập lượng hàng là bj . Chi phí vận chuyển 1 đơn vị hàng từ kho Ki đến cửa hàng Hj là cij . Yêu cầu: ? cần chuyển bao nhiêu hàng từ kho Ki đến cửa hàng Hj để tổng chi phí vận chuyển ít nhất? Mô hình toán học m X X n min f (x) = cij xij (PT) i=1 j=1 n X vđk. xij = ai , i = 1, ..., m j=1 Xm xij = bj , j = 1, ..., n i=1 xij ≥ 0, i = 1, ..., m; j = 1, ..., n hoai.phamthi@hust.edu.vn 2 / 21
  4. Bài toán vận tải và các khái niệm, tính chất liên quan Mô hình bài toán vận tải hoai.phamthi@hust.edu.vn 3 / 21
  5. Bài toán vận tải và các khái niệm, tính chất liên quan Mô hình bài toán vận tải hoai.phamthi@hust.edu.vn 4 / 21
  6. Bài toán vận tải và các khái niệm, tính chất liên quan Mô hình bài toán vận tải Mệnh đề 1: rank A = m + n − 1. Kí hiệu: T = {(i, j) : i ∈ {1, ..., m}, j ∈ {1, ..., n}}; G(x0 ) = {(i, j) ∈ T : x0ij > 0}. x0 là pacb không suy biến ⇔ |G(x0 )| = m + n − 1. Bảng vận tải của bài toán (PT) hoai.phamthi@hust.edu.vn 5 / 21
  7. Bài toán vận tải và các khái niệm, tính chất liên quan Điều kiện tồn tại nghiệm m P n P Định lí 1: argmin (VT) 6= ∅ ⇔ ai = bj . i=1 j=1 Chứng minh: in class Ví dụ: Cho bài toán vận tải có   8 2 5 4 7 5 6 8 a = (80, 110, 90, 440); b = (85, 75, 280, 280); c =  1  3 7 5 0 2 3 1   0 75 5 0 0 0 110 0  Hỏi bài toán có nghiệm hay không? Điểm X 0 =  85 0  có phải là một phương án 5 0  0 0 160 280 chấp nhận được của bài toán hay không? hoai.phamthi@hust.edu.vn 6 / 21
  8. Bài toán vận tải và các khái niệm, tính chất liên quan Chu trình và phương án cực biên của bài toán vận tải Chu trình: Một tập sắp thứ tự của bảng vận tải được gọi là chu trình nếu nó thỏa mãn: Hai ô cạnh nhau nằm trong cùng một hàng hay một cột; Không có ba ô nằm trong cùng một hàng hay một cột; Ô đầu tiên nằm trong cùng một hàng hay một cột với ô cuối cùng. Chú ý: Nếu K ⊂ T thỏa mãn tính chất: trên mỗi hàng, mỗi cột của bảng vận tải không chứa ô nào hoai.phamthi@hust.edu.vn 7 / 21
  9. Bài toán vận tải và các khái niệm, tính chất liên quan Chu trình và phương án cực biên của bài toán vận tải Định lí 2: Cho tập các ô K ⊂ T. Khi đó {Aij : (i, j) ∈ K} độc lập tuyến tính khi và chỉ khi K không chứa chu trình. Hệ quả 1: x0 là pacb ⇔ G(x0 ) không chứa chu trình. Hệ quả 2: Nếu K ⊂ T, |K| ≥ m + n, m ≥ 2, n ≥ 2 thì K chứa chu trình. Hệ quả 3: Nếu K ⊂ T, |K| = m + n − 1 và (i0 , j0 ) ∈ / K. K ko chứa chu trình. Khi đó K ∪ {(i0 , j0 )} sẽ chứa một chu trình duy nhất. Ví dụ: Cho bài toán vận tải có   4 7 12 7 a = (50, 70, 41); b = (30, 60, 46, 25); c = 5 9 6 1 8 2 9 1   30 19 1 0 Hỏi bài toán có nghiệm hay không? Điểm X 0 =  0 0 45 25 có phải là một pacb của bài 0 41 0 0 toán hay không? hoai.phamthi@hust.edu.vn 8 / 21
  10. Bài toán vận tải và các khái niệm, tính chất liên quan Chu trình và phương án cực biên của bài toán vận tải Cách tìm 1 pacb của bài toán vận tải Phương pháp góc tây bắc Phương pháp cực tiểu chi phí Ví dụ: Phương pháp góc tây bắc Hình 1: Phương pháp góc tây bắc- Bảng 1, 2 hoai.phamthi@hust.edu.vn 9 / 21
  11. Bài toán vận tải và các khái niệm, tính chất liên quan Chu trình và phương án cực biên của bài toán vận tải Phương pháp góc tây bắc Hình 2: Phương pháp góc tây bắc- Bảng 3, 4, 5, 6 hoai.phamthi@hust.edu.vn 10 / 21
  12. Bài toán vận tải và các khái niệm, tính chất liên quan Chu trình và phương án cực biên của bài toán vận tải Phương pháp góc tây bắc Hình 3: Phương pháp góc tây bắc- Bảng 7, 8, 9, 10 hoai.phamthi@hust.edu.vn 11 / 21
  13. Bài toán vận tải và các khái niệm, tính chất liên quan Chu trình và phương án cực biên của bài toán vận tải Phương pháp góc tây bắc Hình 4: Phương pháp góc tây bắc- Bảng 11, 12 Phương pháp cực tiểu chi phí Hình 5: Phương pháp cực tiểu chi phí- Bảng 1, 2 hoai.phamthi@hust.edu.vn 12 / 21
  14. Bài toán vận tải và các khái niệm, tính chất liên quan Chu trình và phương án cực biên của bài toán vận tải Phương pháp cực tiểu chi phí Hình 6: Minh họa phương pháp cực tiểu chi phí- Bảng 3, 4, 5, 6 hoai.phamthi@hust.edu.vn 13 / 21
  15. Bài toán vận tải và các khái niệm, tính chất liên quan Chu trình và phương án cực biên của bài toán vận tải Phương pháp cực tiểu chi phí Hình 7: Minh họa phương pháp cực tiểu chi phí- Bảng 7 hoai.phamthi@hust.edu.vn 14 / 21
  16. Thuật toán thế vị giải bài toán vận tải Cơ sở lí thuyết Định lí 3: Cho x là một phương án chấp nhận được của bài toán (PT). Khi đó x0 là nghiệm tối ưu 0 của (PT) khi và chỉ khi ∃ u1 , ..., um ; v1 , ..., vn ∈ R thỏa ui + vj ≤ cij ∀(i, j) ∈ T và ui + vj = cij ∀(i, j) ∈ G(x0 ). Chú ý: Giả sử x0 là pacb ksb. Khi đó {Aij : (i, j) ∈ G(x0 )} độc lập tuyến tính; G(x0 ) ko chứa chu trình; |G(x0 )| = m + n − 1. Khi đó hệ ui + vj = cij ∀(i, j) ∈ G(x0 ) có m + n − 1 phương trình và m + n ẩn và do đó có vô số nghiệm. Quy ước: Gán u1 = 0, từ đó tính được u2 , ..., um ; v1 , ..., vn và bộ số này xác định duy nhất. Bộ số u1 , u2 , ..., um ; v1 , ..., vn được gọi là các thế vị tương ứng với pacb x0 . Kí hiệu ∆ij = ui + vj − cij ∀(i, j) ∈ T. Khi đó ( ∆ij ≤ 0 ∀(i, j) ∈ T x0 ∈ argmin (P T ) ⇔ ∆ij = 0 ∀(i, j) ∈ G(x0 ) hoai.phamthi@hust.edu.vn 15 / 21
  17. Thuật toán thế vị giải bài toán vận tải Cơ sở lí thuyết Ví dụ: Xác định pacb của các bài toán dưới đây; kiểm tra tính tối ưu của các pacb tìm được? bj 30 60 46 25 ai (i) 50 4 7 12 7 70 5 9 6 1 41 8 2 9 2 bj 60 30 40 70 ai (ii) 50 2 4 5 1 70 3 6 4 8 80 1 2 5 3 bj 60 60 20 10 ai 10 10 20 17 16 (iii) 20 13 9 12 8 30 4 15 6 9 40 14 7 1 0 50 3 12 5 19 hoai.phamthi@hust.edu.vn 16 / 21
  18. Thuật toán thế vị giải bài toán vận tải Cơ sở lí thuyết 0 Định lí 4: Giả sử biết x là 1 pacb ksb của bài toán (PT) có bộ thế vị tương ứng u1 , ...., um ; / G(x0 ) sao cho ∆ik jk > 0 thì ta tìm được pacb x1 tốt hơn x0 , tức là v1 , ..., vn . Nếu tồn tại (ik , jk ) ∈ 1 0 f (x ) < f (x ). Chứng minh: in class Tập ô G(x0 ) ∪ (ik , jk ) chứa duy nhất một chu trình K. Xuất phát từ ô (ik , jk )+ ∈ K, đánh dấu ô tiếp theo dấu (−), ... K + = {(i, j) ∈ K : đánh dấu +}, K − = {(i, j) ∈ K : đánh dấu −} ⊂ G(x0 ). Kí hiệu θ = min{x0ij : (i, j) ∈ K − } = x0ir jr > 0. Xây dựng x1 như sau:  0 xij + θ,  nếu (i, j) ∈ K + 1 0 xij = xij − θ, nếu (i, j) ∈ K −   0 xij , nếu (i, j) ∈ /K f (x1 ) = f (x0 ) − θ∆ik jk hoai.phamthi@hust.edu.vn 17 / 21
  19. Thuật toán thế vị giải bài toán vận tải Thuật toán thế vị Sơ đồ khối thuật toán thế vị Tính bộ thế vị tương ứng ∆ij = ui + vj − cij Tìm pacb xuất phát x0 ∀ (i, j) ∈ G x0 u1 , ..., um ; v1 , ..., vn chuyển bảng mới (is , js ) := argmax ∆ij > 0 : (i, j) ∈ G x0   Sai ∆ij ≥ 0  ∀ (i, j) ∈ G x0 XĐ chu trình điều chỉnh K xuất phát từ (is , js )+ Đúng STOP Kết luận x0 là nghiệm tối ưu  0 + xi j + θ; (i, j) ∈ K  xi 1j = xi 0j − θ; (i, j) ∈ K − x0 := x1   0 xi j ; (i, j) ∈ /K hoai.phamthi@hust.edu.vn 18 / 21
  20. Thuật toán thế vị giải bài toán vận tải Thuật toán thế vị Nhận xét: Nếu bài toán vận tải ksb thì thuật toán thế vị dừng sau hữu hạn bước lặp. Nếu lượng phát và lượng thu đều là số nguyên thì nghiệm tối ưu thu được cũng gồm toàn số nguyên. Nếu tại nghiệm tối ưu x0 : ∆ij < 0 ∀(i, j) ∈ / G(x0 ) thì nghiệm tối ưu này là duy nhất. Ngược lại, bài toán có nghiệm tối ưu khác ngoài x0 . Tương tự như thuật toán đơn hình, pacb suy biến xuất hiện nếu θ = 0 : Vẫn thực hiện thuật toán như bình thường, kết quả điều chỉnh không thay đổi pacb nhưng thay đổi hệ vecto cơ sở ứng với pacb. θ đạt được tại nhiều ô khác nhau. Khi đó ta sẽ loại ngẫu nhiên một ô trong đó. hoai.phamthi@hust.edu.vn 19 / 21
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
2=>2