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

Bài giảng Quy hoạch tuyến tính: Chương 4 - ĐH Tôn Đức Thắng

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

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

Bài giảng Quy hoạch tuyến tính: Chương 4 Bài toán vận tải nhằm trình bày về bài toán vận tải dạng tổng quát: phát biểu bài toán vận tải, đặt bài toán vận tải dưới bằng bảng, các tính chất của bài toán vận tải; thuật toán thế vị, tiêu chuẩn tối ưu, thuật toán...

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 Quy hoạch tuyến tính: Chương 4 - ĐH Tôn Đức Thắng

  1. Chương 4 BÀI TOÁN V N T I 20/6/2012 MaMH: C01019 Chương 4: Bài toán v n t i 1
  2. N I DUNG 1. Bài toán v n t i d ng t ng quát 1.1 Phát bi u bài toán v n t i (BTVT) 1.2 Đ t bài toán v n t i dư i d ng b ng 1.3 Các tính ch t c a bài toán v n t i 2. Thu t toán th v 2.1 Tiêu chu n t i ưu 2.2 Thu t toán 3. Các trư ng h p đ c bi t c a BTVT 20/6/2012 MaMH: C01019 Chương 4: Bài toán v n t i 2
  3. Bài toán v n t i d ng t ng quát 1. Phát bi u bài toán Có m đi m phát S i , v i lư ng phát tương ng ai , i = 1,..., m; phát hàng đ n n đi m thu T j , v i lư ng thu tương ng b j , j = 1,..., n. Si : ai →T j : b j xij cij v i: cij là cư c phí v n chuy n 1 đơn v hàng t đi m phát S i , i = 1,..., m đ n đi m thu T j , j = 1,..., n xij là lư ng hàng đư c v n chuy n t S i đ n Tj , i = 1,..., m; j = 1,..., n. 20/6/2012 MaMH: C01019 Chương 4: Bài toán v n t i 3
  4. Bài toán v n t i d ng t ng quát V n đ : L p k ho ch v n chuy n như th nào đ t ng cư c phí v n chuy n là bé nh t? Bi t r ng hàng hóa có th v n chuy n t m t đi m phát b t kỳ đ n m t đi m thu b t kỳ. 20/6/2012 MaMH: C01019 Chương 4: Bài toán v n t i 4
  5. Bài toán v n t i d ng t ng quát Mô hình bài toán có d ng: n m f(X) = ∑∑c j =1 i =1 ij x ij → min  n  ∑ x ij = ai , i = 1,..., m  j =1 m   ∑ x ij = b j , j = 1,..., n  i =1  x ij ≥ 0, i = 1,..., m ; j = 1,..., n    20/6/2012 MaMH: C01019 Chương 4: Bài toán v n t i 5
  6. Bài toán v n t i d ng t ng quát Đi u ki n cân b ng thu phát: m n ∑a i =1 i = ∑b j =1 j 20/6/2012 MaMH: C01019 Chương 4: Bài toán v n t i 6
  7. Bài toán v n t i d ng t ng quát 2. Đ t bài toán dư i d ng b ng Thu T1 : b1 ... Tj : bj ... Tn : bn Phát c11 c1j c1n S1 : a1 x11 x1j x1n ⋮ ... ... ci1 cij cin Si : ai xi 1 xij xin ⋮ ... ... cm1 cmj cmn Sm : am x m1 xmj xmn 20/6/2012 MaMH: C01019 Chương 4: Bài toán v n t i 7
  8. Bài toán v n t i d ng t ng quát Đ nh nghĩa 1 M t t p h p các ô th a mãn tính ch t: • 2 ô liên ti p cùng n m trên cùng 1 hàng hay 1 c t; • 3 ô liên ti p không cùng n m trên cùng 1 hàng hay 1 c t đư c g i là m t dây chuy n. M t dây chuy n khép kín đư c g i là m t chu trình. 20/6/2012 MaMH: C01019 Chương 4: Bài toán v n t i 8
  9. Bài toán v n t i d ng t ng quát Đ nh nghĩa 2 Nh ng ô có x ij > 0 đư c g i là ô ch n, nh ng ô còn l i đư c g i là ô lo i. Đ nh nghĩa 3 M t phương án (PA) mà các ô ch n không t o thành chu trình đgl PA cơ b n (PACB). M t PACB đ (m + n – 1) ô ch n đgl PACB không suy bi n. 20/6/2012 MaMH: C01019 Chương 4: Bài toán v n t i 9
  10. Bài toán v n t i d ng t ng quát 3. Các tính ch t c a BTVT i. BTVT cân b ng thu phát luôn luôn có PATƯ. ii. Trong 1 PACB b t kỳ, t ng s ô ch n luôn nh hơn ho c b ng t ng s đi m phát và thu tr đi 1. (S ô ch n ≤ (m + n − 1) ). iii. V i PACB có đ (m + n − 1) ô ch n, thì v i 1 ô lo i b t kỳ s t o thành m t chu trình duy nh t v i m t s ô ch n. 20/6/2012 MaMH: C01019 Chương 4: Bài toán v n t i 10
  11. Thu t toán th v 1. Tiêu chu n t i ưu Xét BTVT cân b ng thu phát m n f (x) = ∑∑c i =1 j =1 ij x ij → min  n  ∑ x ij = ai , i = 1,..., m  j =1 m  ∑ x ij = b j , j = 1,..., n  i =1  x ij ≥ 0, i = 1,..., m ; j = 1,..., n   20/6/2012 MaMH: C01019 Chương 4: Bài toán v n t i 11
  12. Thu t toán th v Bài toán đ i ng u c a bài toán trên: m n g (u,v ) = ∑ ai ui + ∑ b j v j → max i =1 j =1 ui + v j ≤ cij , i = 1, m; j = 1, n. 20/6/2012 MaMH: C01019 Chương 4: Bài toán v n t i 12
  13. Thu t toán th v Đ nh lý 1 PA X = ( xij ) c a BTVT là PATƯ khi và ch khi tìm đư c các s ui ,v j , i = 1, m; j = 1, n th a mãn: ui + v j ≤ cij , ∀(i , j )   ui + v j = cij , ∀(i , j ) ∈ G( X ),  G( X ) = {(i , j ) : xij > 0} 20/6/2012 MaMH: C01019 Chương 4: Bài toán v n t i 13
  14. Thu t toán th v 2. Thu t toán th v - Bư c 1 (Bư c kh i t o) Tìm PACB xu t phát X 0 = ( xij ) theo nguyên t c phân 0 ph i t i đa: Gi s c n phân ph i cho ô (i,j). Lư ng hàng t i đa có th phân ph i là xij = min{ai , b j } Sau đó, đi u ch nh l i các yêu c u: ai′ = ai − xij   b′ = b j − xij  j 20/6/2012 MaMH: C01019 Chương 4: Bài toán v n t i 14
  15. Thu t toán th v • N u ai′ = 0 , thì lo i dòng i. • N u b′ = 0 , thì lo i c t j. j • N u ai′ = b′ = 0 , thì lo i c dòng i và c t j. j 20/6/2012 MaMH: C01019 Chương 4: Bài toán v n t i 15
  16. Thu t toán th v x Ví d 1 19 bj ai 30 60 46 25 50 4 7 12 7 51 70 5 9 6 1 19 x 41 8 2 9 1 41 20/6/2012 MaMH: C01019 Chương 4: Bài toán v n t i 16
  17. Thu t toán th v Ta đư c b ng m i thu g n. L p l i hai phép toán trên v i b ng m i thu g n đ n khi yêu c u c a đi m phát và đi m thu đư c th a mãn. Các ô đư c phân ph i có xij > 0, nh ng ô còn l i có xij = 0. 20/6/2012 MaMH: C01019 Chương 4: Bài toán v n t i 17
  18. Thu t toán th v D a vào nguyên t c phân ph i t i đa và cách th c ch n ô ưu tiên phân ph i, xét 3 phương pháp: i. Phương pháp góc Tây B c: ô đ u tiên đư c ch n đ phân ph i là ô v trí góc Tây B c (ô (1,1)). ii. Phương pháp c c ti u cư c phí: ô đ u tiên đư c ch n đ phân ph i là ô có cư c phí bé nh t. iii. Phương pháp Fogel: trên m i hàng, c t ch n ra hai ô có cư c phí bé nh t (bé nhì), l y hi u s c a chúng. Ô có cư c phí bé nh t tương ng hàng, c t có hi u s l n nh t s là ô đ u tiên đư c ch n đ phân ph i. 20/6/2012 MaMH: C01019 Chương 4: Bài toán v n t i 18
  19. Thu t toán th v N u PACB tìm đư c có đ ( m + n − 1) ô ch n, thì sang Bư c 2. Ngư c l i, thêm vào ô (i , j ) nào đó m t lư ng hàng xij = 0 sao cho: • đ s ( m + n − 1) • và ô (i , j ) này không t o thành chu trình v i các ô ch n. → Bư c 2. 20/6/2012 MaMH: C01019 Chương 4: Bài toán v n t i 19
  20. Thu t toán th v - Bư c 2 (Bư c l p) đ u bư c l p đã có PACB đ ( m + n − 1) ô ch n. i. Xác đ nh các th v ui ,v j , i = 1, m ; j = 1, n ui + v j = cij , ∀(i , j ) ∈ G( X ) Ch n u1 = 0. ii. Tính các ư c lư ng theo công th c: ∆ ij = ui + v j − cij , ∀(i , j ) 20/6/2012 MaMH: C01019 Chương 4: Bài toán v n t i 20
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