Bài giảng Quy hoạch tuyến tính: Chương 4 - ThS. Nguyễn Văn Phong

Bài giảng "Quy hoạch tuyến tính - Chương 4: Bài toán vận tải" cung cấp cho người học các kiến thức: Phát biểu bài toán, bài toán vận tải dạng bảng, một số khái niệm, một số tính chất, phương pháp tìm phương án xuất phát, thuật toán thế vị. Mời các bạn cùng tham khảo.
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 - ThS. Nguyễn Văn Phong11/5/2011ÑAÏI HOÏC TAØI CHÍNH – MARKETINGBOÄ MOÂN TOAÙN – KHOA CÔ BAÛNBaøi giaûngQUY HOAÏCH TUYEÁN TÍNHThS.ThS. Nguyeãn Vaên PhongEmail : nvphong1980@gmail.com, nv.phong@ufm.edu.comChươngChương 4. BAØI TOAÙN VAÄN TAÛI1. PHAÙT BIEÅU BAØI TOAÙN.2. BAØI TOAÙN VAÄN TAÛI DAÏNG BAÛNG3. MOÄT SOÁ KHAÙI NIEÄM4. MOÄT SOÁ TÍNH CHAÁT5. PHÖÔNG PHAÙP TÌM PHÖÔNG AÙN XUAÁT PHAÙT6. THUAÄT TOAÙN THEÁ VÒ2NGUYEÃN VAÊN PHONGQUY HOAÏCH TUYEÁN TÍNHPHAÙT BIEÅU BAØI TOAÙNPHAÙT BIEÅU BAØI TOAÙN.m : ÑIEÅM PHAÙT n : ÑIEÅM THUB1a1LAÄP BAØI TOAÙNcij : cöôùc phí töø Ai ñeán B jx ij : löôïng haøng töø Ai ñeán B jb1A1mB2b2I)a2A2B3b3mII )i =1 j =1n∑ x i j j =1m x∑ i j i =1= ai, i = 1, m,= bj, j = 1,n,n∑ a = ∑bi =1QUY HOAÏCH TUYEÁN TÍNHnMuïc tieâu: f = ∑∑ cij x ij → miniIII ) x ij ≥ 0j =1j3NGUYEÃN VAÊN PHONG111/5/2011BAØI TOAÙN VAÄN TAÛI DAÏNG BAÛNGBj⋅⋅⋅b1Ai⋅⋅⋅bjbnc11a1x 11⋅⋅⋅Moät oâ (i, j )cijaix ij⋅⋅⋅cmnamx mn4NGUYEÃN VAÊN PHONGQUY HOAÏCH TUYEÁN TÍNHMOÄT SOÁ KHAÙI NIEÄMT = {(i, j ) i = 1, 2,..., m; j = 1, 2,..., n}Taäp caùc oâ{}Taäp caùc oâ choïnG (x ) = (i, j ) x ij > 0Caùc oâ loaïi(i, j ) ∉G (x )|G(x)| laø soá phaàn töû cuûa G(x)Phöông aùn cöïc bieân : laø phöông aùn coù khoâng quaù m + n -1oâ choïnPhöông aùn cöïc bieân khoâng suy bieán : laø phöông aùn coù ñuùngm+nm+n-1 oâ choïntrình:i,j)Chu trình: Taäp caùc oâ (i,j) ñöôïc goïi laø moät chu trình neáui) Hai oâ caïnh nhau phaûi naèm treân cuøng haøng hay moät coät,ii)ii) Khoâng coù 3 oâ naèm treân cuøng moät haøng hay moät coät,iii)nhau.iii) OÂ ñaàu tieân vaø oâ cuoái cuøng truøng nhau.5NGUYEÃN VAÊN PHONGQUY HOAÏCH TUYEÁN TÍNHMOÄT SOÁ KHAÙI NIEÄMVí duïBjAib1⋅⋅⋅bj⋅⋅⋅bna1⋅⋅⋅ai⋅⋅⋅amQUY HOAÏCH TUYEÁN TÍNH6NGUYEÃN VAÊN PHONG211/5/2011MOÄT SOÁ TÍNH CHAÁT1. Phöông aùn x laø phöông aùn cöïc bieân neáu G(x) khoângchöùa chu trình2. Moïi taäp G coùù |G(x)|=m+n ñeàu chöùa chu trình.co)|=mtrình.3. Cho P laø taäp goàm m+n -1 oâ khoâng chöùa chu trình vaø(i0, j0) khoâng thuoäc veà P. Khi ñoù P ∪ (i0 , j 0 ) seõ chöùa moätchu trình duy nhaát7NGUYEÃN VAÊN PHONGQUY HOAÏCH TUYEÁN TÍNHTÌM PHÖÔNG AÙN XUAÁT PHAÙT1. Phöông phaùp Goùc taây baéc- Ñi töø oâ (1,1) ñeán oâ (m,n) theo höôùng töø treân xuoáng döôùitöø traùi sang phaûi.- Phaân phoái toái ña haøng vaøo oâ (i,j).ai neáu a i ≤ bjx ij = min {ai ,bj } = bj neáu a i ≤ bj2. Phöông phaùp Cmin- Duyeät taát caû caùc oâ töø (1,1) ñeán oâ (m,n)- Phaân phoái toái ña haøng vaøo oâ (i,j) coù cmin.8NGUYEÃN VAÊN PHONGQUY HOAÏCH TUYEÁN TÍNHTHUAÄT TOAÙN THEÁ VÒ1. Ñieàu kieän toái öu:öu:- Ñieàu kieän caàn vaø ñuû ñeå moät phöông aùn X laø phöông aùn toáiöu,öu, neáu toàn taïi caùc theá vòui , v j , i = 1, 2,.., m; j = 1, 2,..., nthoaû maõnui + v j = cij ; neáu (i, j ) ∈G (X )ui + v j ≤ cij ; neáu (i, j ) ∉G (X )QUY HOAÏCH TUYEÁN TÍNH9NGUYEÃN VAÊN PHONG311/5/2011THUAÄT TOAÙN THEÁ VÒ2. Thuaät toaùn0Böôùc 1: Tìm phöông aùn suaát phaùt X 0 = (x ij ) (Goùc taây baéc, Cmin)ui , v j , i = 1, 2,.., m; j = 1, 2,..., nBöôùc 2: Tìm caùc theá vòui + v j = cij ; neáu (i, j ) ∈G (X 0 )thoaû maõn∆ ij = ui + v j − cij ; taïi (i, j ) ∉G (X 0 )Böôùc 3: Tính ñoä cheânh leächBöôùc 4: Kieåm tra tính toái öu- Neáu ∀ (i, j ) ∉G (X 0 ): ∆ij ≤ 0 Thì X laø PATÖ- Neáu ∃(i, j ) ∉G (X 0 ): ∆ ij > 0 Chuyeån qua böôùc 5Böôùc 5: Ñieàu chænh phöông aùn- Xaùc ñònh oâ hieäu chænh (is , js ) ∆is js = max{∆ij > 0 |(i, j ) ∉G (X 0 )}- Tìm moät chu trình ñieàu chænh duy nhaát K trong G (X 0 ) ∪ (is , js )+(- Ñaùnh daáu (+), (-) xen keû vaøo caùc oâ trong K vôùi (is , js ) ∈ K- Xaùc ñònh löôïng hieäu chænh θ = x i0 , j = min{x i0, j |(i, j ) ∈ K − }r r10NGUYEÃN VAÊN PHONGQUY HOAÏCH TUYEÁN TÍNHTHUAÄT TOAÙN THEÁ VÒ1- Xaây döïng phöông aùn môùi X1 = (x ij ) vôùi0x ij + θ 0x = x ij − θ 0x ij1ijTrong ñoùneáu (i, j ) ∈ K +neáu (i, j ) ∈ K −neáu (i, j ) ∉ KK + = {Caùc oâ trong K ñöôïc ñaùnh daáu +}K − = {Caùc oâ trong K ñöôïc ñaùnh daáu -}Khi ñoù,- Ta coù moät phöông aùn xuaát phaùt môùi. (Quay laïi böôùc 1)- Vôùi giaù trò cuûa haøm muïc tieâu môùi ñöôïc xaùc ñònhf (X1) = f (X 0 ) − θ × ∆is js11NGUYEÃN VAÊN PHONGQUY HOAÏCH TUYEÁN TÍNHTHUAÄT TOAÙN THEÁ VÒVí duï.Bj60Ai507080QUY HOAÏCH TUYEÁN TÍNH30407024513648125312NGUYEÃN VAÊN PHONG411/5/2011CAÙC TRÖÔØNG HÔÏP SUY BIEÁNi) Khoâng caân baèng thu phaùtmn∑ a > ∑bi =1ij =1jhaymn∑ a < ∑bi =1ij =1jii) Phöông aùn xuaát phaùt X0 suy bieán|G (X 0 )|< m + n − 1iii) Baøi toaùn coù oâ caám: Khi ta khoâng theå chuyeån haøng töø ai ñeánbj (trong moät soá ñieàu kieän naøo ñoù) thì oâ (i,j ) laø oâ caámQUY HOAÏCH TUYEÁN TÍNH13NG ...