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

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...
Nội dung trích xuất từ tài liệu:
Bài giảng Quy hoạch tuyến tính: Chương 4 - ĐH Tôn Đức Thắng Chương 4 BÀI TOÁN V N T I20/6/2012 MaMH: C01019 Chương 4: Bài toán v n t i 1 N I DUNG1. 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 i2. Thu t toán th v 2.1 Tiêu chu n t i ưu 2.2 Thu t toán3. Các trư ng h p đ c bi t c a BTVT20/6/2012 MaMH: C01019 Chương 4: Bài toán v n t i 2 Bài toán v n t i d ng t ng quát1. Phát bi u bài toánCó 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 ilư ng thu tương ng b j , j = 1,..., n. Si : ai →T j : b j xij cijv 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,..., nxij 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 Bài toán v n t i d ng t ng quátV 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 nghàng hóa có th v n chuy n t m t đi m phát b tkỳ đ 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 Bài toán v n t i d ng t ng quátMô 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 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 j20/6/2012 MaMH: C01019 Chương 4: Bài toán v n t i 6 Bài toán v n t i d ng t ng quát2. Đ 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 xmn20/6/2012 MaMH: C01019 Chương 4: Bài toán v n t i 7 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 Bài toán v n t i d ng t ng quátĐ nh nghĩa 2Nh 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 nkhô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ôngsuy bi n.20/6/2012 MaMH: C01019 Chương 4: Bài toán v n t i 9 Bài toán v n t i d ng t ng quát3. Các tính ch t c a BTVTi. 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 Thu t toán th v1. Tiêu chu n t i ưuXé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 Thu t toán th vBài toán đ i ng u c a bài toán trên: m n ...