tailieunhanh - 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ị. . | 11/5/2011 ÑAÏI HOÏC TAØI CHÍNH – MARKETING BOÄ MOÂN TOAÙN – KHOA CÔ BAÛN Baøi giaûng QUY HOAÏCH TUYEÁN TÍNH ThS. ThS. Nguyeãn Vaên Phong Email : nvphong1980@, Chương Chương 4. BAØI TOAÙN VAÄN TAÛI 1. PHAÙT BIEÅU BAØI TOAÙN. 2. BAØI TOAÙN VAÄN TAÛI DAÏNG BAÛNG 3. MOÄT SOÁ KHAÙI NIEÄM 4. MOÄT SOÁ TÍNH CHAÁT 5. PHÖÔNG PHAÙP TÌM PHÖÔNG AÙN XUAÁT PHAÙT 6. THUAÄT TOAÙN THEÁ VÒ 2 NGUYEÃN VAÊN PHONG QUY HOAÏCH TUYEÁN TÍNH PHAÙT BIEÅU BAØI TOAÙN PHAÙT BIEÅU BAØI TOAÙN. m : ÑIEÅM PHAÙT n : ÑIEÅM THU B1 a1 LAÄP BAØI TOAÙN cij : cöôùc phí töø Ai ñeán B j x ij : löôïng haøng töø Ai ñeán B j b1 A1 m B2 b2 I) a2 A2 B3 b3 m II ) 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 = ∑b i =1 QUY HOAÏCH TUYEÁN TÍNH n Muïc tieâu: f = ∑∑ cij x ij → min i III ) x ij ≥ 0 j =1 j 3 NGUYEÃN VAÊN PHONG 1 11/5/2011 BAØI TOAÙN VAÄN TAÛI DAÏNG BAÛNG Bj ⋅⋅⋅ b1 Ai ⋅⋅⋅ bj bn c11 a1 x 11 ⋅⋅⋅ Moät oâ (i, j ) cij ai x ij ⋅⋅⋅ cmn am x mn 4 NGUYEÃN VAÊN PHONG QUY HOAÏCH TUYEÁN TÍNH MOÄT SOÁ KHAÙI NIEÄM T = {(i, j ) i = 1, 2,., m; j = 1, 2,., n} Taäp caùc oâ { } Taäp caùc oâ choïn G (x ) = (i, j ) x ij > 0 Caù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 -1 oâ choïn Phöông aùn cöïc bieân khoâng suy bieán : laø phöông aùn coù ñuùng m+nm+n-1 oâ choïn trình: i,j) Chu trình: Taäp caùc oâ (i,j) ñöôïc goïi laø moät chu trình neáu i) 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. 5 NGUYEÃN VAÊN PHONG QUY HOAÏCH TUYEÁN TÍNH MOÄT SOÁ KHAÙI NIEÄM Ví duï Bj Ai b1 ⋅⋅⋅ bj ⋅⋅⋅ bn a1 ⋅⋅⋅ ai ⋅⋅⋅ am QUY HOAÏCH TUYEÁN TÍNH 6 NGUYEÃN VAÊN PHONG 2 11/5/2011 MOÄT SOÁ TÍNH CHAÁT 1. Phöông aùn x laø phöông aùn cöïc bieân neáu G(x) khoâng chöùa chu trình 2. .