Quy hoạch tuyến tính - Chương 4: Bài toán vận tải

11/5/2011 1 Bài giảng QUY HOẠCH TUYẾN TÍNHÏ ÁÏ ÁÏ Á ThS. Nguyễnããã Vănêêê Phong Email : nvphong1980@gmail.com, nv.phong@ufm.edu.com ĐẠI HỌC TÀI CHÍNH Ï Ï ØÏ Ï ØÏ Ï Ø – MARKETING BỘ MÔN TOÁN Ä Â ÙÄ Â ÙÄ Â Ù – KHOA CƠ BẢNÛÛÛ 2 Chương 4. BÀI TOÁN VẬN TẢI Ø Ù Ä ÛØ Ù Ä ÛØ Ù Ä Û QUY HOẠCH TUYẾN TÍNHÏ ÁÏ ÁÏ Á NGUYỄN VĂN PHONGÃ ÊÃ ÊÃ Ê 1. PHÁTÙÙÙ BIỂUÅÅÅ BÀIØØØ TOÁNÙÙÙ . 2. BÀIØØØ TOÁNÙÙÙ VẬNÄÄÄ TẢIÛÛÛ DẠNGÏÏÏ BẢNGÛÛÛ 3. MỘTÄÄÄ SỐÁÁÁ KHÁIÙÙÙ NIỆMÄÄÄ 4. MỘTÄÄÄ SỐÁÁÁ TÍNH CHẤTÁÁÁ 5. PHƯƠNG PHÁPÙÙÙ TÌM PHƯƠNG ÁNÙÙÙ XUẤTÁÁÁ PHÁTÙÙÙ 6. THUẬTÄÄÄ TOÁNÙÙÙ THẾÁÁÁ VỊ 3 PHÁT BIỂU BÀI TOÁNÙ Å Ø ÙÙ Å Ø ÙÙ Å Ø Ù 1A 2A 3B 2B 1B PHÁTÙÙÙ BIỂUÅÅÅ BÀIØØØ TOÁNÙÙÙ . m : ĐIỂMÅÅÅ PHÁTÙÙÙ n : ĐIỂMÅÅÅ THU : cước phí từ đến B ij i j c A : lượng hàng từ A đến B ij i j x 1a 2a 1b 2b 3b LẬPÄÄÄ BÀIØØØ TOÁNÙÙÙ 1 1 min m n ij ij i j f c x = = = →∑∑Mục tiêu: QUY HOẠCH TUYẾN TÍNHÏ ÁÏ ÁÏ Á NGUYỄN VĂN PHONGÃ ÊÃ ÊÃ Ê 1 1 1 1 1 1 0 = = = =  = =    = =  = ≥ ∑ ∑ ∑ ∑ , , , ) , , , ) ) n i j i j m i j j i m n i j i j ij x a i m I x b j n II a b III x 11/5/2011 2 4 BÀI TOÁN VẬN TẢI DẠNG BẢNGØ Ù Ä Û Ï ÛØ Ù Ä Û Ï ÛØ Ù Ä Û Ï Û QUY HOẠCH TUYẾN TÍNHÏ ÁÏ ÁÏ Á NGUYỄN VĂN PHONGÃ ÊÃ ÊÃ Ê j B 1a ma ⋅ ⋅ ⋅ 11x 11c jb i A 1 b ⋅ ⋅ ⋅ nb ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ i a ij x ijc mnx mnc Một ô ( , )i j 5 MỘT SỐ KHÁI NIỆMÄ Á Ù ÄÄ Á Ù ÄÄ Á Ù Ä QUY HOẠCH TUYẾN TÍNHÏ ÁÏ ÁÏ Á NGUYỄN VĂN PHONGÃ ÊÃ ÊÃ Ê Tậpäää cácùùù ôâââ { }1 2 1 2( , ) , ,..., ; , ,...,T i j i m j n= = = Tậpäää cácùùù ôâââ chọnïïï { }0( ) ( , ) ijG x i j x= > Cácùùù ôâââ loạiïïï ( , ) ( )i j G x∉ Phương ánùùù cựcïïï biênâââ : làøøø phương ánùùù cóùùù khôngâââ quáùùù m + n -1 ôâââ chọnïïï Phương ánùùù cựcïïï biênâââ khôngâââ suy biếnááá : làøøø phương ánùùù cóùùù đúngùùù m+n-1 ôâââ chọnïïï Chu trình: Tậpäää cácùùù ôâââ (i,j) đượcïïï gọiïïï làøøø mộtäää chu trình nếuááá i) Hai ôâââ cạnhïïï nhau phảiûûû nằmèèè trênâââ cùngøøø hàngøøø hay mộtäää cộtäää , ii) Khôngâââ cóùùù 3 ôâââ nằmèèè trênâââ cùngøøø mộtäää hàngøøø hay mộtäää cộtäää , iii) ÔÂÂÂ đầuààà tiênâââ vàøøø ôâââ cuốiááá cùngøøø trùngøøø nhau. |G(x)| làøøø sốááá phầnààà tửûûû củảûû G(x) 6 MỘT SỐ KHÁI NIỆMÄ Á Ù ÄÄ Á Ù ÄÄ Á Ù Ä QUY HOẠCH TUYẾN TÍNHÏ ÁÏ ÁÏ Á NGUYỄN VĂN PHONGÃ ÊÃ ÊÃ Ê jB 1a ma ⋅ ⋅ ⋅ jb iA 1b ⋅ ⋅ ⋅ nb ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ia Ví dụïïï 11/5/2011 3 7 MỘT SỐ TÍNH CHẤTÄ Á ÁÄ Á ÁÄ Á Á QUY HOẠCH TUYẾN TÍNHÏ ÁÏ ÁÏ Á NGUYỄN VĂN PHONGÃ ÊÃ ÊÃ Ê 1. Phương ánùùù x làøøø phương ánùùù cựcïïï biênâââ nếuááá G(x) khôngâââ chứáùù chu trình 2. Mọiïïï tậpäää G co ùùùù |G(x)|=m+n đềuààà chứáùù chu trình. 3. Cho P làøøø tậpäää gồmààà m+n -1 ôâââ khôngâââ chứáùù chu trình vàøøø (i0, j0) khôngâââ thuộcäää vềààà P. Khi đóùùù sẽõõõ chứáùù mộtäää chu trình duy nhấtááá 0 0( , )P i j∪ 8 TÌM PHƯƠNG ÁN XUẤT PHÁTÙ Á ÙÙ Á ÙÙ Á Ù QUY HOẠCH TUYẾN TÍNHÏ ÁÏ ÁÏ Á NGUYỄN VĂN PHONGÃ ÊÃ ÊÃ Ê 1. Phương phápùùù Gócùùù tâyâââ bắcééé - Đi từøøø ôâââ (1,1) đếnááá ôâââ (m,n) theo hướngùùù từøøø trênâââ xuốngááá dướiùùù từøøø tráiùùù sang phảiûûû . - Phânâââ phốiááá tốiááá đa hàngøøø vàòøø ôâââ (i,j). { } nếu a nếu a min , i i j ij i j j i j a b x a b b b ≤ = =  ≤ 2. Phương phápùùù Cmin - Duyệtäää tấtááá cảûûû cácùùù ôâââ từøøø (1,1) đếnááá ôâââ (m,n) - Phânâââ phốiááá tốiááá đa hàngøøø vàòøø ôâââ (i,j) cóùùù cmin. 9 THUẬT TOÁN THẾ VỊÄ Ù ÁÄ Ù ÁÄ Ù Á QUY HOẠCH TUYẾN TÍNHÏ ÁÏ ÁÏ Á NGUYỄN VĂN PHONGÃ ÊÃ ÊÃ Ê 1. Điềuààà kiệnäää tốiááá ưu: - Điềuààà kiệnäää cầnààà vàøøø đủûûû đểååå mộtäää phương ánùùù X làøøø phương ánùùù tốiááá ưu, nếuááá tồnààà tạiïïï cácùùù thếááá vị 1 2 1 2, , , ,.., ; , ,...,i ju v i m j n= = thoảûûû mãnõõõ nếu nếu ; ( , ) ( ) ; ( , ) ( ) i j ij i j ij u v c i j G X u v c i j G X + = ∈  + ≤ ∉ 11/5/2011 4 10 THUẬT TOÁN THẾ VỊÄ Ù ÁÄ Ù ÁÄ Ù Á QUY HOẠCH TUYẾN TÍNHÏ ÁÏ ÁÏ Á NGUYỄN VĂN PHONGÃ ÊÃ ÊÃ Ê 2. Thuậtäää toánùùù Bướcùùù 1: Tìm phương ánùùù suấtááá phátùùù (Gócùùù tâyâââ bắcééé , Cmin) 1 2 1 2, , , ,.., ; , ,..., i j u v i m j n= = thoảûûû mãnõõõ 0 nếu ; ( , ) ( )i j iju v c i j G X+ = ∈ Bướcùùù 2: Tìm cácùùù thếááá vị Bướcùùù 3: Tính độäää chênhâââ lệchäää 0 tại ; ( , ) ( )ij i j iju v c i j G X∆ = + − ∉ Bướcùùù 4: Kiểmååå tra tính tốiááá ưu - Nếuááá 0 0 ( , ) ( ) : iji j G X∀ ∉ ∆ ≤ Thì X làøøø PATƯ - Nếuááá 0 0( , ) ( ): iji j G X∃ ∉ ∆ > Chuyểnååå qua bướcùùù 5 Bướcùùù 5: Điềuààà chỉnh phương ánùùù - Xácùùù định ôâââ hiệuäää chỉnh 00( , ) max{ |( , ) ( )}s ss s i j iji j i j G X∆ = ∆ > ∉ - Tìm mộtäää chu trình điềuààà chỉnh duy nhấtááá K trong 0( ) ( , )s sG X i j∪ - Đánhùùù dấuááá (+), (-) xen kẻûûû vàòøø cácùùù ôâââ trong K vớiùùù ( , )s si j K +∈ - Xácùùù định lượngïïï hiệuäää chỉnh 0 0 , ,min{ |( , ) }r ri j i jx x i j Kθ − = = ∈ 0 0 ( )ijX x= 11 THUẬT TOÁN THẾ VỊÄ Ù ÁÄ Ù ÁÄ Ù Á QUY HOẠCH TUYẾN TÍNHÏ ÁÏ ÁÏ Á NGUYỄN VĂN PHONGÃ ÊÃ ÊÃ Ê - Xâyâââ dựngïïï phương ánùùù mớiùùù 0 1 0 0 nếu nếu nếu ( , ) ( , ) ( , ) ij ij ij ij x i j K x x i j K x i j K θ θ + −  + ∈  = − ∈  ∉ Khi đóùùù , - Ta cóùùù mộtäää phương ánùùù xuấtááá phátùùù mớiùùù . (Quay lạiïïï bướcùùù 1) - Vớiùùù giáùùù trị củảûû hàmøøø mụcïïï tiêuâââ mớiùùù đượcïïï xácùùù định 1 0( ) ( ) s si jf X f X θ= − × ∆ 1 1 ( )ijX x= vớiùùù Trong đóùùù Các ô trong được đánh dấu + Các ô trong được đánh dấu - { } { } K K K K + − = = 12 THUẬT TOÁN THẾ VỊÄ Ù ÁÄ Ù ÁÄ Ù Á QUY HOẠCH TUYẾN TÍNHÏ ÁÏ ÁÏ Á NGUYỄN VĂN PHONGÃ ÊÃ ÊÃ Ê Ví dụïïï. j B 50 30 2 70 i A 60 40 70 80 54 1 3 6 4 8 1 2 5 3 11/5/2011 5 13 CÁC TRƯỜNG HỢP SUY BIẾNÙ Ø Ï ÁÙ Ø Ï ÁÙ Ø Ï Á QUY HOẠCH TUYẾN TÍNHÏ ÁÏ ÁÏ Á NGUYỄN VĂN PHONGÃ ÊÃ ÊÃ Ê i) Khôngâââ cânâââ bằngèèè thu phátùùù 1 1 1 1 hay m n m n i j i j i j i j a b a b = = = = > <∑ ∑ ∑ ∑ ii) Phương ánùùù xuấtááá phátùùù X0 suy biếnááá 0 1| ( )|G X m n< + − iii) Bàiøøø toánùùù cóùùù ôâââ cấmááá : Khi ta khôngâââ thểååå chuyểnååå hàngøøø từøøø ai đếnááá bj (trong mộtäää sốááá điềuààà kiệnäää nàòøø đóùùù) thì ôâââ (i,j ) làøøø ôâââ cấmááá