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

Bài giảng Tối ưu hóa - Chương 3: Bài toán vận tải

Chia sẻ: Lê Na | Ngày: | Loại File: PDF | Số trang:17

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

Chương 3 bài giảng môn Tối ưu hóa do ThS. Nguyễn Công Trí biên soạn cung cấp cho người học các kiến thức về bài toán vận tải dạng tổng quát, các tính chất và tiêu chuẩn tối ưu của bài toán vận tải, các phương pháp tìm phương án cực biên đầu tiên của bài toán vận tải,... Cuối mỗi chương có bài tập và lời giải chi tiết.

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 Tối ưu hóa - Chương 3: Bài toán vận tải

  1. ÝØJLÒÙ íæ ÞßH× ÌÑßGÒ Êß\Ò ÌßE× Ì¸-ò Ò¹«§»=² ݱ>²¹ Ì®3 ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ BAØ BAØI TOAÙ TOAÙN VAÄ VAÄN TAÛ TAÛI CHÖÔNG 3 BAØ BAØI TOAÙ TOAÙN VAÄ VAÄN TAÛ TAÛI DAÏ DAÏNG NG TOÅ TOÅNG NG QUAÙ QUAÙT NOÄ NOÄI DUNG BAØ BAØI TOAÙ TOAÙN VAÄVAÄN TAÛ TAÛI Giaû Giaû söû caàcaàn vaävaän chuyeå chuyeån moä moät loaï loaïi haø haøng ng hoù hoùa (xi 1. BAØ BAØI TOAÙ TOAÙN VAÄ VAÄN TAÛ TAÛI DAÏ DAÏNG NG TOÅ TOÅNG NG QUAÙ QUAÙT (Xem) maêng, saé saét theù theùp, p, ...) töø töø m ñieå ieåm cung caá caáp (traï (traïm phaù phaùt), t), kyù kyù hieä hieäu laø laø A1, A2, ..., A m ñeán n ñieå ieåm tieâu Ths. Nguyeãn Coâng Tr Tríí 2. CAÙ CAÙC TÍTÍNH CHAÁ CHAÁT VAØ VAØ TIEÂU CHUAÅ CHUAÅN TOÁ TOÁI ÖU CUÛ CUÛA thuï thuï (traï (traïm thu), kyù kyù hieä hieäu laø laø B1, B2, ..., Bn, bieá bieát raè raèng ng BAØ Ø I TOAÙÙN BA TOA VA TA VAÄ ÄN TAÛ ÛI (Xem) (1) Soá Soá löôïng ng haøhaøng ng coù coù ôû caù caùc traï traïm phaù phaùt A1, A2, ..., 3. CAÙ CAÙC PHÖ PHÖÔNG PHAÙ PHAÙP TÌM PHÖ PHÖÔNG AÙ AÙN CÖÏ CÖÏC A m laà laàn lö löôït laø laø a1, a2,..., am Copyright 2001 (2) Soá Soá löôïng ng haøhaøngng caà caàn ôûôû caù caùc traï traïm thu B1, B2, ..., BIEÂN ÑAÀU TIEÂN CUÛ CUÛA BAØ BAØI TOAÙ TOAÙN VAÄ VAÄN TAÛ TAÛI (Xem) Bn laà laàn lö löôït laø laø b1, b2,..., bn. í 4. THUAÄ THUAÄT GIAÛ GIAÛI THEÁ THEÁ VÒ CHO BAØ BAØI TOAÙ TOAÙN VAÄ VAÄN TAÛ TAÛI (Xem) (3) Chi phí phí vaä vaän chuyeå chuyeån moä moät ñôn vò haø haøng ng hoù hoùa töø töø Tr traï traïm phaù phaùt A i ñeán traï traïm thu Bj laø laø cij. 5. CAÙ CAÙC DAÏ DAÏNG NG KHAÙ KHAÙC CUÛ CUÛA BAØ BAØI TOAÙ TOAÙN VAÄ VAÄN TAÛ TAÛI (Xem) Haõy laälaäp keá keá hoaï hoaïchch vaävaän taû taûi haø haøng ng hoù hoùa sao cho Ths. Nguyeãn Coân g Tr Tríí toå toång ng chi phí phí vaä vaän taû taûi thaá thaáp nhaá nhaát vaø vaø thoû thoûa maõn yeâu 6. BAØ BAØI TAÄ TAÄP Copyright 2001(Xem) caà caàu thu – phaùphaùt.t. g oân BAØ BAØI TOAÙ TOAÙN VAÄ VAÄN TAÛ TAÛI DAÏ DAÏNG TOÅ TOÅNG QUAÙ QUAÙT BAØ BAØI TOAÙ TOAÙN VAÄ VAÄN TAÛ TAÛI DAÏ DAÏNG NG TOÅ TOÅNG NG QUAÙ QUAÙT MO HÌNH BAØ BAØI TOAÙ TOAÙN VAÄ VAÄN TAÛ TAÛI Vaä Vaäy, y, moâ hìhình toaù toaùn cuû cuûa baø baøi toaù toaùn vaä vaän taû taûi (BTVT) Ñ aët xij laø laø soá soá löôïng ng haø haøng ng caà caàn vaä vaän chuyeå chuyeån töø töø traï traïm daï daïng ng toå toång ng quaù quaùt nhö nhö sau: phaù traïm thu Bj. phaùt A i ñeán traï Tìm {x ij} sao cho: m n m n Ta coù coù toå toång ng chi phí phí vaä vaän taû taûi:i: Z C cij xij min Z cij xij min i 1 j 1 i 1 j 1 n n (1) Traï Traïm phaù phaùt, t, phaù phaùt heá heát haø haøng: ng: xij ai , i 1, m xij ai , i 1, m j 1 j 1 m (2) Traï Traïm thu, thu ñuû haø haøng: ng: m xij b j , j 1, n eãn xij b j , j 1, n i 1 (3) Yeâu caà caàu traï traïm phaù phaùt, t, traï traïm thu ñöô ñöôïc thoû thoûa i 1 m n m n ai b j (ñk caân baè baèng ng thu – phaù phaùt). t). xij 0; cij 0; ai 0; b j 0; ai bj i 1 j 1 i 1 j 1 y gu BAØ BAØI TOAÙ TOAÙN VAÄ VAÄN TAÛ TAÛI DAÏ DAÏNG TOÅ TOÅNG QUAÙ QUAÙT BAØ BAØI TOAÙ TOAÙN VAÄ VAÄN TAÛ TAÛI DAÏ DAÏNG NG TOÅ TOÅNG NG QUAÙ QUAÙT BAØ BAØI TOAÙ TOAÙN VAÄ VAÄN TAÛ TAÛI DÖ DÖ ÔÙI DAÏ DAÏNG NG BAØ BAØI TOAÙ TOAÙN QHTT BTVT vieá vieát dö döôùi daï daïng ng vectô vaø vaø ma traä traän nhö nhö sau khai trieå trieån BTVT vaø vaø xeá xeáp heä heä raø raøng ng buoä buoäc dö döôùi daï daïng ng z CT X min heä heä m + n phö phöông trìtrình cuû cuûa m n bieá bieán nhö nhö sau AX b * x11 x12 x1n a1 x 21 x 22 x 2n a2 X 0 ** Moä Moät vectô X thoûthoûa (*) vaø vaø (**) goï goïi laø laø phö phöông aù aùn. N Moä Moät P.A ñaït cöï cöïc tieå tieåu thì thì goï goïi laø laø P.A.T.Ö P.A.T.Ö cuûcuûa BTVT. xm 1 xm 2 xmn am x11 x 21 xm 1 b1 x12 x22 xm2 b2 Moä Moät phö phöông aù aùn X ñöô ñöôïc goï goïi laø laø P.A.C.B khi caù caùc vectô coäcoät Aj cuû cuûa ma traä traän heä heä soá soá A öùng ng vôù vôùi caù caùc thaø thaønh nh phaà phaàn xij > 0 laø laø ñoäc laä laäp tuyeá tuyeán tí tính. x1n x2 n x mn bn Kyù Kyù hieä hieäu Am+n,m n ma traätraän heä heä soá soá cuû cuûa hpt treân. X T = (x11 x 12 ... x1n x21 x22 ... x2n ... xm1 xm2 ... x mn) laø laø Moä Moät P.A.C.B cuûcuûa BTVT coù coù nhieà nhieàu nhaá nhaát laø laø m + n – vectô coä coät goà goàm m n thaø thaønh nh phaà phaàn;n; C = (c11 c12 1 thaø thaønh nh phaà phaàn dödöông. Neá Neáu moä moät P.A.C.B cuû cuûa BTVT ... c 1n c21 c22 ... c2n cm1 cm2 ... cmn) laø laø vectô doø doøng ng coù coù ñuùngng m + n – 1 thaø thaønh nh phaà phaàn dö döông thì thì ñöô ñöôïc goà goàm m n thaø thaønh nh phaà phaàn;n; bT = (a1 a2 ... am b1 b2 ... bn) goï goïi laø laø khoâng suy bieá n. Ngö bieán. Ngöôïc laï laïi, i, ñöô ñöôïc goï goïi laø laø laø laø vectô coä coät goà goàm m+ n thaø thaønh nh phaà phaàn.n. phö phöông aù aùn cöï cöïcc bieân suy bieá bieán. ¸¬¬°æññ²½¬®·ò½±ò½½ PDF created with pdfFactory Pro trial version www.pdffactory.com
  2. ÝØJLÒÙ íæ ÞßH× ÌÑßGÒ Êß\Ò ÌßE× Ì¸-ò Ò¹«§»=² ݱ>²¹ Ì®3 ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ MO TAÛ TAÛ BAØ BAØI TOAÙ TOAÙN DÖ DÖÔÙI DAÏ DAÏNG NG BAÛ BAÛNG VAÄ VAÄN TAÛ TAÛI MO TAÛ TAÛ BAØ BAØI TOAÙ TOAÙN DÖ DÖÔÙI DAÏ DAÏNG NG BAÛ BAÛNG NG VAÄ VAÄN TAÛ TAÛI Traïm thu Bj B1 B2 Bn (1) Kyù Kyù hieä hieäu (i, j) laø laø oâ treân doø doøng ng i vaø vaø coä coät j.j. b1 b2 bn (2) Chi phíphí vaävaän chuyeå chuyeån cij ñöô ñöôïc ghi ôû ôû goù goùc treân Traïm phaùt Ai beân traù traùi cuû cuûa oâ (i, j), lö löôïng ng haø haøng ng caà caàn vaä vaän chuyeå chuyeån x ij ñöô ñöôïc ghi ôû ôû goù goùc dö döôùi beân phaûphaûi cuû cuûa oâ (i, j) bieå bieåu A1 c11 c12 c 1n dieãn tuyeá tuyeán ñöôñöôøng ng vaä vaän chuyeå chuyeån töø töø traï traïm phaùphaùt Ai a1 x 11 x12 x 1n ñeán traï traïm thu Bj. A2 c21 c22 c 2n (3) Trong BAÛ BAÛNGNG VAÄ VAÄN TAÛ TAÛI,I, moä moät oâ ñöô ñöôïc goï goïi laø laø oâ a2 x 21 x22 x 2n treo neá neáu noù noù laø laø oâ duy nhaá nhaát treân doø doøng ng hay treân coä coät. t. (4) Nhö Nhöõng oâ öùng ng vôù vôùi x ij > 0 trong BAÛ BAÛNG NG VAÄ VAÄN TAÛTAÛI í ñöô ñöôïc goïgoïi laø laø oâ choï choïn, nhönhöõng oâ khaù khaùc goï goïi laø laø oâ loaï loaïi. Tr Am cm1 cm2 c mn (5) Moä Moät daõy caù caùc oâ choï choïn, n, trong ñoù 3 oâ lieân tieá tieáp am xm1 xm2 xmn khoâng naè naèm treân cuø cuøng ng moämoät doø doøng ng hay moämoät coäcoät thì thì ñöô ñöôïc goïgoïi laø laø moä chuyeàn. moät daây chuyeà g oân MO TAÛ TAÛ BAØ BAØI TOAÙ TOAÙN DÖ DÖÔÙI DAÏ DAÏNG NG BAÛ BAÛNG NG VAÄ VAÄN TAÛ TAÛI MO TAÛ TAÛ BAØ BAØI TOAÙ TOAÙN DÖ DÖÔÙI DAÏ DAÏNG NG BAÛ BAÛNG NG VAÄ VAÄN TAÛ TAÛI (6) Moä Moät daây chuyeà chuyeàn kheù kheùp kí kín ñöô ñöôïc goï goïi laø laø moä moät VÍ DUÏ DUÏ 3.1. trình hay moä chu trì moät voø ng. voøng. (7) Moä traän (xij) laø Moät ma traä laø moä moät P.A cuû cuûa BTVT neá neáu noù noù C thoaû thoaû heä heä raø raøng ng buoä buoäc. Moät P.A (xij) laø c. Moä laøm cöï cöïc tieå tieåu haø haøm muï thì (xij) laø muïc tieâu thì laø P.A.T.Ö P.A.T.Ö. cuû cuûa baø baøi toaù toaùn. n. Hình 2.1. Hình 2.2. Hình 2.3. Hình 2.4. Hình 2.5. (8) Moä Moät P.A cuû cuûa BTVT khoâng taï taïo thaø thaønh nh chu trì trình Hình 2.1. caù caùc oâ choï choïn, n, coù coù daá daáu “ ”, taï taïo thaø thaønh nh (voø (voøng) ng) thì thì ñöô ñöôïc goï goïi laø laø Phö Phöông aù aùn cöï cöïc bieân. daây chuyeà chuyeàn, n, caù caùc oâ (1,1) vaø vaø (4,3) laø laø caù caùc oâ treo. eãn (9) Moä Moät P.A.C.B cuû cuûa BTVT coù coù ñuû m+n- m+n-1 oâ choï choïn thì thì Hình 2.2. caù caùc oâ choï choïn taï taïo thaø thaønh nh daây chuyeà chuyeàn, n, ñöô ñöôïc goï goïi laø laø P.A.C.B khoâng suy bieá bieán, neá neáu coù coù ít caù caùc oâ (4,1) vaø vaø (3,3) laø laø caù caùc oâ treo. hôn m+n- m+n-1 oâ choï choïn ñöô ñöôïc goï goïi laø laø P.A.C.B suy bieá bieán. Hình 2.3., Hì Hình 2.4 vaø vaø Hình 2.5. caù caùc oâ choï choïn taï taïo thaø thaønh nh chu trì trình, khoâng coùcoù oâ treo. y gu CAÙ CAÙC TÍ TÍNH CHAÁ CHAÁT CUÛ CUÛA BAØ BAØI TOAÙ TOAÙN VAÄ VAÄN TAÛ TAÛI TIEÂU CHUAÅ CHUAÅN TOÁ TOÁI ÖU CUÛ CUÛA BAØ BAØI TOAÙ TOAÙN VAÄ VAÄN TAÛ TAÛI TÍNH CHAÁ CHAÁT 1: Baø Baøi toaù toaùn vaävaän taûtaûi luoân luoân coù coù Xeù Xeùt baø baøi toaù toaùn vaä vaän taû taûi sau Vieá Vieát laï laïi baø baøi toaù toaùn phö phöông aù aùn toá toái öu. m n m n Z cij xij min Z cij xij min TÍNH CHAÁ CHAÁT 2: Vôù Vôùi moä moät phö phöông aù aùn baá baát kyø kyø, soá soá oâ n i 1 j 1 m i 1 j 1 choï choïn cuûcuûa phö phöông aù aùn khoâng vö vöôït quaù quaù toå toång ng soá soá xij ai , i 1, m xij b j , j 1, n traï traïm phaù phaùt vaø vaø traï traïm thu. thu. N j 1 i 1 m + n –1 (vôù(vôùi laølaø soá soá oâ choï choïn cuûcuûa P.A) m n TÍNH CHAÁ CHAÁT 3: Vôù Vôùi moä moät phö phöông aù aùn coù coù ñuû m+n– m+n–1 oâ xij b j , j 1, n xij ai , i 1, m choï choïn thìthì vôù vôùi moä moät oâ loaï loaïi baá baát kyø kyø ñöô ñöôïc ñöa ñöa vaø vaøo i 1 j 1 phö phöông aù aùn seõ taï taïo thaø thaønh nh chu trì trình vaø vaø chu trì trình xij 0; cij 0; ai 0; b j 0; xij 0; cij 0; ai 0; b j 0; naø naøy laø laø duy nhaá nhaát.t. m n m n TÍNH CHAÁ CHAÁT 4: Neá Neáu lölöôïng ng cung ai vaø vaø löôïng ng caà caàu bj ai bj ai bj laø laø soá soá nguyeân thìthì baø baøi toaù toaùn coù coù lôø lôøi giaû giaûi nguyeân. i 1 j 1 i 1 j 1 ¸¬¬°æññ²½¬®·ò½±ò½½ PDF created with pdfFactory Pro trial version www.pdffactory.com
  3. ÝØJLÒÙ íæ ÞßH× ÌÑßGÒ Êß\Ò ÌßE× Ì¸-ò Ò¹«§»=² ݱ>²¹ Ì®3 ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ TIEÂU CHUAÅ CHUAÅN TOÁ TOÁI ÖU CUÛ CUÛA BAØ BAØI TOAÙ TOAÙN VAÄ VAÄN TAÛ TAÛI PHÖ PHÖÔNG PHAÙ PHAÙP CHI PHÍ PHÍ BEÙ BEÙ NHAÁ NHAÁT Baø Baøi toaù toaùn ñoái ngaãu cuû cuûa BTVT Treân baû baûng ng vaä vaän taû taûi, i, choï choïn oâ ñaàu tieân coù coù cöôùc phí phí n m Tìm {ui,vj} sao cho: Z vaä vaän chuyeå chuyeån beù beù nhaá nhaát vaø vaø choï choïn xij nhö nhö sau: * b jv j aiui max Vôù Vôùi caù caùc caë caëp ñoái ngaãu: j 1 i 1 a i : loaï i doø ng i, b j bj ai x ij 0 vaø vaø v j – ui c ij, i,j Theo ñònh lyù lyù ñoä leä leäch ch buø buø thì thì phö phöông aù aùn {xij} cuû cuûa x ij min ai , b j b j : loaï i coä t j, ai ai b j BTVT coù coù P.A.T.Ö P.A.T.Ö laø laø toà toàn taï taïi heä heä thoá thoáng ng {ui, v j} sao cho: a i b j : loaï i doø ng i vaø coä t j Neá Neáu xij > 0 thì thì vj – ui = cij, Laë Laëp laï laïi quaù quaù trì trình treân cho oâ tieá tieáp theo cho ñeán Neá Neáu vj – ui < cij thì thì xij = 0. í ñeán khi yeâu caàcaàu traï traïm phaù phaùt vaø vaø traï traïm thu ñöô ñöôïc Tr Vaä Vaäy tieâu chuaå chuaån toá toái öu cuû cuûa BTVT: v j – ui cij, i,j thoaû thoaû maõn. ui: ñöô ñöô ïc goï goïi laø laø theá theá vò doøng. doøng. Baû Baûng ng thu ñöô ñöôïc vôù vôùi caù caùc xij > 0 laø laø phö phöông aù aùn cöï cöïc c vj: ñöô ñöôïc goï goïi laø laø theá coät. theá vò coä bieân cuû cuûa baø baøi toaù toaùn. n. g oân PHÖ PHÖÔNG PHAÙ PHAÙP CHI PHÍ PHÍ BEÙ BEÙ NHAÁ NHAÁT PHÖ PHÖÔNG PHAÙ PHAÙP CHI PHÍ PHÍ BEÙ BEÙ NHAÁ NHAÁT Ví duï duï 3.2. Duø Duøng ng phö phöông phaù phaùp chi phí phí beù beù T 30 40 25 35 45 P nhaáá t, nhat, t tì ì m phö phö ông aù ù a cn cöï öï c bieân cuû cu baøi û a baø 42 13 8 7 2 13 toaù toaùn vaä vaän taû taûi coù coù daï daïng ng baû baûng sau ñaây 35 7 C T 30 40 25 35 45 28 5 1 10 5 11 P 28 42 13 8 7 2 13 45 16 5 3 7 16 28 5 1 10 5 11 25 20 eãn 45 16 5 3 7 16 60 6 3 4 14 10 60 6 3 4 14 10 30 12 18 Kieåm tra a i = bj = 175 Kieå P.A.C.B treân khoâng suy bieá bieán, n, vôù vôùi giaù giaù trò Z = 980. y gu PHÖ PHÖÔNG PHAÙ PHAÙP VOGELS PHÖ PHÖÔNG PHAÙ PHAÙP VOGELS Phö Phöông phaù phaùp Vogels (1958) cho P.A.C.B khaù khaù toá toát Ví duï duï 3.3: Duø Duøng ng phö phöông phaù phaùp Vogels, tì tìm theo nghó nghóa giaù giaù trò haø haøm muïmuïc tieâu cuû cuûa noù noù khaù khaù gaà gaàn vôù vôùi P.A.T.Ö P.A.T.Ö . PhöPhöông phaù phaùp ñöô ñöôïc moâ taû taû nhö nhö sau phö ph ö ông aùù a c n cöï öï c bieâ n cuû cu ba toa va taû û a baø øi toaù ù n vaä än taûi (1) Treân baû û ng vaä ä n ba ng va ta i, t taû ûi, tí í nh hieä äu hie so gi soá á giöö õa chi phí phí beù beù coù coù daï daïng ng baû baûngng sau thöù thöù hai vôù vôùi chi phí phí beùbeù thöù thöù nhaá nhaát. t. T 30 40 25 35 45 N (2) Choï Choïn soásoá lôù lôùn nhaá nhaát trong caù caùc hieä hieäu treân vaø vaø phaân P phoá phoái toá toái ña cho oâ coù coù chi phíphí beù beù nhaánhaát moämoät lö löôïng ng 42 13 8 7 2 13 xij = min(ai, bj), sau ñoù tính laï la hie so do ng (coät). ï i hieä äu soáá doøø ng (coä t). 28 5 1 10 5 11 (3) Quaù Quaù trìtrình treân ñöô ñöôïc laë laëp laï laïi cho ñeán khi chæ chæ 45 16 5 3 7 16 coø coøn laï laïi moä moät doødoøng ng hay moä moät coä coät duy nhaá nhaát. t. (4) Baû 60 6 3 4 14 10 Baûng ng thu ñöô ñöôïc vôù vôùi caù caùc {xij} laø laø phö phöông aù aùn cöï cöïc bieân cuû cuûa baø baøi toaù toaùn. n. Kieå Kieåm tra ai = bj = 175 ¸¬¬°æññ²½¬®·ò½±ò½½ PDF created with pdfFactory Pro trial version www.pdffactory.com
  4. ÝØJLÒÙ íæ ÞßH× ÌÑßGÒ Êß\Ò ÌßE× Ì¸-ò Ò¹«§»=² ݱ>²¹ Ì®3 ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ PHÖ PHÖÔNG PHAÙ PHAÙP VOGELS HÖÔÙNG NG GIAÛ GIAÛI BAØ BAØI TOAÙ TOAÙN T 30 40 25 35 45 (1) Tìm P.A.C.B khoâng suy bieá bieán ñaàu tieân baèbaèng ng P phö phöông phaùphaùp chi phí phí beù beù nhaá nhaát hoaë hoaëc Vogels. 42 13 8 7 2 13 5 ,1 ,5 K (2) Duø Duøngng tieâu chuaå chuaån toá toái öu vi – uj cij, i,j ñeå kieå kieåm 35 7 tra P.A.C.B vöø vöøa tì tìm ñöô ñöôïc.c. 28 5 1 10 5 11 4K (3) Neá Neáu P.A.C.B thoaû thoaû maõn tieâu chuaåchuaån toá toái öu thì thì 28 P.A.C.B ñoù laø laø P.A.T.Ö P.A.T.Ö . 45 16 5 3 7 16 2,11 K (4) Neá Neáu P.A.C.B vöø vöøa tì tìm chö chöa thoaû thoaû maõn tieâu 12 25 8 chuaå chuaån toátoái öu thì thì tìm caù caùchch söû söûa ño åi P.A.C.B cuõ ñeå í 60 6 3 4 14 10 coù coù P.A.C.B môù môùi. i. Tr 1K (5) trôû û veàà b öô ùc (2), sau moä 30 30 trô ve moät soá soá böôùc laë laëp hö höõu haï haïn, n, 1 2 1 3 1 Z = 932 ta seõ coù coù P.A.T.Ö P.A.T.Ö . 7 3 4 K 3 K K K K Phö Phöông phaùphaùp treân goï goïi laø laø thuaä thuaät toaù toaùn theá theá vò g oân SÔ LAÄ LA ÑO ÄP ÀBAÛ BA ÛNG NG VAÄ THUAÄ THUA VA ÄN TAÛ ÄT GIAÛ GIA ÛI ÛITHEÁ TA THEÁ VÒ THUAÄ THUAÄT TOAÙ TOAÙN THEÁ THEÁ VÒ CUÛ CU Û A BAØ BA Ø I TOAÙ TOA ÙN VAÄ VA ÄN TAÛ N ÛI TA Böôùc 1. Laä XAÙ XAÙC ÑÒNH P.A.C.B ÑAÀU TIE Laäp baû baûng ng vaä vaän taû taûi (phö (phöông phaù phaùp chi phí phí beù beù nhaá nhaát hoaë hoac ë Vogels) (1) Kieå Kieåm tra ñieà ieàu kieä kieän caân baè baèng ng thu – phaù phaùt. t. Suy bieá Coù Coù Theâm oâ x =0 (2) Xaù Xaùc ñònh P.A.C.B (baè (baèng ng phö phöông phaù phaùp chi phí phí bieán? n? ij beù beù nhaá nhaát). t). C khoâng Xaù Xaùc ñònh P.A môù môùi Tính: Vj = Ui + Cij (3) Kieå Kieåm tra P.A.C.B coù coù suy bieá bieán hay khoâng Ui = Vj – Cij x ij q daá u ( ). Neá Neáu P.A.C.B. suy bieá bieán: n: theâm vaø vaøo oâ (i,j) baá baát kyø kyø xij x ij q daáu ( ). 0? Coù Coù Baø vôùi x ij = 0, khoâng taï vôù taïo thaø thaønh nh chu trì trình. ij Baøi toaù toaùn coù coù P.A.T.Ö P.A.T.Ö x ij khoâng daáu. khoâng Neá Neáu P.A.C.B khoâng suy bieá bieán, n, chuyeå chuyeån sang [2] eãn Choï Choïn oâ vaø vaøo:o: Max ij Keá Keát thuù thuùc thuaä thuaät giaû giaûi Böôùc 2. Kieå Kieåm tra tí tính toá toái öu cuû cuûa baø baøi toaù toaùn Xaù Xaùc ñònh voø voøng ng ñieà ieàu chæ chænh SOÁ SOÁ BÖÔÙC LAËLAËP (1) Tí Tính vj = ui + cij vaø vaø ñaùnh nh daá daáu (+); daádaáu (– (–). LAØ LAØ HÖÕU HAÏ HAÏN q = min{x ij/ (i, j) daá daáu (– (–)} ui = vj – cij, trong ñoù oâ (i,j) laø laø oâ choï choïn. n. y gu THUAÄ THUAÄT TOAÙ TOAÙN THEÁ THEÁ VÒ THUAÄ THUAÄT TOAÙ TOAÙN THEÁ THEÁ VÒ Choï Choïn ui = 0 taï taïi doø doøng ng baá baát kyø kyø. Böôùc 4. Xaù Xaùc ñònh P.A.C.B môù môùi (2) Ñ aët ij = vj – ui – cij Neá Neáu 0: ta coù coù P.A.T.Ö P.A.T.Ö. x ij q daáu ( ); ij Neá Neáu ij > 0: chuyeå chuye ån sang [3] xij x ij q daáu ( ); N Böôùc 3. Xaù Xaùc ñònh voø voøng ng ñieà ieàu chæ chænh (1) Choï Choïn oâ vaø vaøo: o: Max ij ( ij > 0) x ij khoâng daáu. (2) Choï Choïn oâ ra Quay veà veà böôùc [2]. xaù xaùc ñònh voø voøng ng ñieà ieàu chæ chænh Sau moä moät soá soá böôùc laë laëp hö höõu haï haïn, n, baø baøi toaù toaùn coù coù oâ vaø vaøo seõ ñöô ñöôïc ñaùnhnh daá daáu (+). Xen keû keû daá daáu phö phöông aù aùn toá toái öu. (-) vaø vaø daá daáu (+) treân voø voøng ng ñieà ieàu chæ chænh. löôïng ng ñieà ieàu chæ chænh q = min{xij/ (i,j) coù coù daá daáu (- (-)} ¸¬¬°æññ²½¬®·ò½±ò½½ PDF created with pdfFactory Pro trial version www.pdffactory.com
  5. ÝØJLÒÙ íæ ÞßH× ÌÑßGÒ Êß\Ò ÌßE× Ì¸-ò Ò¹«§»=² ݱ>²¹ Ì®3 ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ THUAÄ THUAÄT TOAÙ TOAÙN THEÁ THEÁ VÒ THUAÄ THUAÄT TOAÙ TOAÙN THEÁ THEÁ VÒ CHUÙ CHUÙ YÙ. Ví duï duï 3.4. Giaû Giaûi baø baøi toaù toaùn vaä vaän taû taûi (1) Trong thuaä thuaät giaû giaûi baø baøi toaù toaùn vaä vaän taû taûi, i, neá neáu Max ij T 45 55 30 70 50 40 ñaït taï taïi nhieà nhieàu oâ, ta choï choïn moä moät oâ tuø tuøy yù yù trong soá soá caù caùc P oâ ñoù laø laøm oâ ñieà ieàu chæ chænh. 40 12 8 9 10 7 6 (2) Trong P.A.T.Ö P.A.T.Ö tìm ñöô ñöôïc X opt, neá neáu coù coù ij = 0, maø maø 75 12 13 10 11 13 9 (i,j) laø laø oâ loaï loaïi thì thì ñoù laø laø daá daáu hieä hieäu baø baøi toaù toaùn coù coù nhieà nhieàu 60 3 9 5 6 7 1 P.A.T.Ö P.A.T.Ö khaù khaùc.c. Ñe å tìm P.A.C.B.T.Ö P.A.C.B.T.Ö khaù khaùc,c, ta choï choïn oâ 70 9 8 2 7 6 2 (i, j) ñoù laø laøm oâ ñieà ieàu chæ chænh, roà roài aù aùp duï duïngng thuaä thuaät toaù toaùn 45 11 9 6 10 10 8 í theá theá vò ñeå xaù xaùc ñònh P.A.C.B.T.Ö P.A.C.B.T.Ö khaù khaùc X /opt. Tr Kieå Kieåm tra ñieà ieàu kieä kieän caân baè baèng ng thu phaù phaùt (3) Taä Taäp phö phöông aù aùn toá toái öu laø laø a i = 40 + 75 + 60 + 70 + 45 = 290 X = { X opt + (1 – )X/opt, 0, 1 } bj = 45 + 55 + 30 + 70 + 50 + 40 = 290 g oân T 45 55 30 70 50 40 T 45 55 30 70 50 40 Baû ng Baû Baû Baûng 1 2 P P 12 8 9 10 7 6 12 8 9 10 7 6 40 40 - 30 + 10 +2 0 - 10 + 30 0 12 13 10 11 13 9 12 13 10 11 13 9 75 -2 75 -7 C - 25 + 50 +1 - 5 + +2 70 +1 +1 3 9 5 6 7 1 3 9 5 6 7 1 60 7 60 2 + 20 - 40 + 40 - 20 9 8 2 7 6 2 1 9 8 2 7 6 2 1 70 70 30 +1 - 40 + +5 30 - 20 + 20 eãn 11 9 6 10 10 8 11 9 6 10 10 8 45 -1 45 -1 + 25 - 20 +1 45 q= 20 10 8 3 9 7 8 q= 5 5 8 3 4 7 3 y gu T 45 55 30 70 50 40 THUAÄ THUAÄT TOAÙ TOAÙN THEÁ THEÁ VÒ Baû Baû ng 3 P •Do caù caùc ij 0 i,j neân P.A.T.Ö P.A.T.Ö cuû cuûa baø baøi toaù toaùn laø laø 12 8 9 10 7 6 40 -1 5 35 0 5 0 0 35 0 12 13 10 11 13 9 75 -6 0 5 0 70 0 0 5 70 N xopt 45 0 0 0 0 15 3 9 5 6 7 1 60 1 45 15 0 0 30 0 15 25 9 8 2 7 6 2 70 0 0 45 0 0 0 0 30 15 25 Vaø Vaø Z min = 1.875 ñôn vò tieà tieàn teä teä. 11 9 6 10 10 8 45 -2 Ngoaø Ngoaøi ra, baø baøi toaù toaùn khoâng coù coù P.A.T.Ö P.A.T.Ö khaù khaùc vì vì 45 khoâng coù coù ij = 0, vôù vôùi (i, j) laø laø oâ loaï loaïi 4 7 2 5 6 2 ¸¬¬°æññ²½¬®·ò½±ò½½ PDF created with pdfFactory Pro trial version www.pdffactory.com
  6. ÝØJLÒÙ íæ ÞßH× ÌÑßGÒ Êß\Ò ÌßE× Ì¸-ò Ò¹«§»=² ݱ>²¹ Ì®3 ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ THUAÄ THUAÄT TOAÙ TOAÙN THEÁ THEÁ VÒ T 76 62 88 45 40 Baûûng 1 Ba Ví duï duï 3.5. Giaû Giaûi baø baøi toaù toaùn vaä vaän taû taûi P 10 19 15 6 7 0 T 76 62 88 45 40 79 P - 64 + 15 79 10 19 15 6 7 13 11 8 7 4 5 102 102 13 11 8 7 4 + 14 - 88 70 12 17 10 5 3 12 17 10 5 3 1 60 12 18 18 10 9 70 + +2 - 30 40 í Kieå Kieåm tra ñieà ieàu kieä kieän caân baè baèng ng thu phaù phaùt 12 18 18 10 9 -2 Tr 60 ai = 79 + 102 + 70 + 60 = 311 + 12 - 48 bj = 76 + 62 + 88 + 45 + 40 = 311 q=30 10 16 13 6 4 g oân T 76 62 88 45 40 Ba Baûûng 2 THUAÄ THUAÄT GIAÛ GIAÛI THEÁ THEÁ VÒ P •Do caù caùc ij 0 i,j neân 10 19 15 6 7 0 P.A.T.Ö P.A.T.Ö cuû cuûa baø baøi toaù toaùn vaä vaän taû taûi 79 34 45 34 0 0 45 0 C 13 11 8 7 4 5 102 0 44 58 0 0 44 58 xopt 12 17 10 5 3 3 0 0 30 0 40 70 42 18 0 0 0 30 40 eãn 12 18 18 10 9 -2 Vaø Zmin = 2.806 ñôn vò tieà Vaø tieàn teä teä. 60 42 18 Baø Baøi toaù toaùn khoâng coù coù P.A.T.Ö P.A.T.Ö naø naøo khaù khaùc vì vì khoâng 10 16 13 6 6 coù coù ij = 0, vôù vôùi (i, j) laø laø oâ loaï loaïi.i. y gu CAÙ CAÙC DAÏ DAÏNG NG KHAÙ KHAÙC CUÛ CUÛA BAØ BAØI TOAÙ TOAÙN VAÄ VAÄN TAÛ TAÛI BAØ BAØI TOAÙ TOAÙN VAÄ VAÄN TAÛ TAÛI KHOÂNG CAÂN BAÈ BAÈNG NG THU- THU-PHAÙ PHAÙT 1. TRÖ TRÖ ÔØNG NG HÔÏ HÔÏP 1. ai > bj Theâm traï traïm thu giaû giaû thöù thöù Bn+1 1. BAØ BAØI TOAÙ TOAÙN VAÄ VAÄN TAÛ TAÛI KHOÂNG CAÂN BAÈ BAÈNG NG Vôù Vôùi nhu caà caàu thu b n+1 = ai – bj THU – PHAÙ PHAÙT (Xem) Cöôùc phí phí vaä vaän taû taûi ci,n+1 = 0, i = 1, 2, ..., m. 2. TRÖ TRÖ ÔØNG NG HÔÏ HÔÏP 2. ai < bj N 2. BAØ BAØI TOAÙ TOAÙN VAÄ VAÄN TAÛ TAÛI COÙ COÙ DAÏ DAÏNG NG HAØ HAØM MUÏ MUÏC Theâm traï traïm phaù phaùt giaû giaû thöù thöù Am+1 TIEÂU LAØ LAØ MAX (Xem) Vôù Vôùi nhu caà caàu phaù phaùt am+1 = bj – ai 3. BAØ BAØI TOAÙ TOAÙN VAÄ VAÄN TAÛ TAÛI COÙ COÙ O CAÁ CAÁM (Xem) Cöôùc phí phí vaä vaän taû taûi cm+1,j = 0, j = 1, 2, ..., n. Vôù Vôùi caù caùc oâ coù coù cöôùc phí phí vaä vaän taû taûi baè baèng ng khoâng 4. BAØ BAØI TOAÙ TOAÙN VAÄ VAÄN TAÛ TAÛI XE KHOÂNG (Xem) ñöô ñöôïc goï goïi laø laø oâ giaû giaû. Lö Löu yùyù khi duø duøng ng thuaä thuaät toaù toaùn theá theá vò ñeå giaû giaûi baø baøi toaù toaùn treân, vôùvôùi P.A.C.B ñaàu tieân, ta öu tieân phaân phoá phoái vaø vaøo caù caùc oâ thöï thöïc. c. ¸¬¬°æññ²½¬®·ò½±ò½½ PDF created with pdfFactory Pro trial version www.pdffactory.com
  7. ÝØJLÒÙ íæ ÞßH× ÌÑßGÒ Êß\Ò ÌßE× Ì¸-ò Ò¹«§»=² ݱ>²¹ Ì®3 ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ BAØ BAØI TOAÙ TOAÙN VAÄ VAÄN TAÛ TAÛI KHOÂNG CAÂN BAÈ BAÈNG NG THU- THU-PHAÙ PHAÙT T 65 45 50 30 Baûûng 1 Ba Ví duï duï 3.6. Giaû Giaûi baø baøi toaù toaùn vaä vaän taû taûi sau P T 65 45 50 30 10 9 12 7 0 P 60 + 5 - 25 30 60 10 9 12 7 9 11 10 15 1 55 55 9 11 10 15 - 55 + +1 50 8 7 14 12 8 7 14 12 2 50 Kieå Kieåm tra ñieà ieàu kieä kieän caân baè baèng ng thu – phaù phaùt 5 45 í 0 0 0 0 12 Tr ai= 165 < bj= 190 25 Theâm moä moät traï traïm phaù phaùt giaû giaû A4, vôù vôùi 25 q = 25 a4 = 190 – 165 = 25 vaø vaø c4j = 0, j=1, 2, 3, 4 10 9 12 7 g oân T 65 45 50 30 BAØ BAØI TOAÙ TOAÙN VAÄ VAÄN TAÛ TAÛI Baû Baûng 2 P KHOÂNG CAÂN BAÈBAÈNG NG THU- THU-PHAÙ PHAÙT 10 9 12 7 0 60 •Phö Phöông aù aùn cöï cöïc bieân toá toái öu cuû cuûa baø baøi toaù toaùn - 30 + 0 30 vaä vaän taû taûi laø laø C 9 11 10 15 1 55 30 0 0 30 30 25 8 7 14 12 2 xopt 30 0 25 0 50 + 5 - 45 5 45 0 0 eãn 0 0 0 0 11 25 vaø Zmin = 1.385 •vaø 25 q = 30 10 9 11 7 Coù Coù P.A.T.Ö P.A.T.Ö khaù khaùc y gu T 65 45 50 30 BAØ BAØI TOAÙ TOAÙN VAÄ VAÄN TAÛ TAÛI KHOÂNG CAÂN BAÈ BAÈNG NG THU- THU-PHAÙ PHAÙT P •P.A.C.B.T.Ö P.A.C.B.T.Ö khaù khaùc cuû cuûa baø baøi toaù toaùn 10 9 12 7 0 0 30 0 30 60 30 30 xopt 30 0 25 0 9 11 10 15 1 35 15 0 0 55 N •Vaø Vaø Z ’min =1.385 30 25 •Taä Taäp P.A.T.Ö P.A.T.Ö cuû cuûa baø baøi toaù toaùn 8 7 14 12 2 50 •Zopt = Xopt + (1 – ) X/opt 35 15 0 0 0 0 11 30 30 30 0 30 25 •Hay Zopt 30 0 25 0 25 10 9 11 7 35 30 15 30 0 0 ¸¬¬°æññ²½¬®·ò½±ò½½ PDF created with pdfFactory Pro trial version www.pdffactory.com
  8. ÝØJLÒÙ íæ ÞßH× ÌÑßGÒ Êß\Ò ÌßE× Ì¸-ò Ò¹«§»=² ݱ>²¹ Ì®3 ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ MO HÌNH BAØ BAØI TOAÙ TOAÙN VAÄ VAÄN TAÛ TAÛI THUAÄ THUAÄT GIAÛ GIAÛI BAØ BAØI TOAÙ TOAÙN VAÄ VAÄN TAÛ TAÛI COÙ COÙ HAØ HAØM MUÏ MUÏC TIEÂU LAØ LAØ MAX COÙ Ù HAØØ CO HA MUM MUÏÏ C TIE U LAØ LAØ MAX Gioá Gioáng ng nhö nhö baø baøi toaù toaùn QHTT coù coù haø haøm muï muïc tieâu laø laø Tìm {x ij} sao cho: max, chuù chuùng ng ta coùcoù theå theå ñöa ñöa baø baøi toaù toaùn vaä vaän taû taûi coù coù haø haøm muï muïc tieâu Z max veà veà Z/ = – Z min, sau ñoù m n Z cij xij max i 1 j 1 duø duøng ng thuaä thuaät toaù toaùn theá theá vò ñeå giaû giaûi. Tuy nhieân, chuù chuùng ng n ta cuõng coù coù theå theå giaû giaûi tröï tröïc tieá tieáp baø baøi toaù toaùn naø naøy baè baèng ng xij ai , i 1, m j 1 thuaä thuaät toaù toaùn theá theá vò vôù vôùi moä moät vaø vaøi thay ñoåi trong thuaä thuaät m giaû giaûi nhö nhö sau: í xij b j , j 1, n 1. Khi xaây döï döïng ng P.A.C.B ñaàu tieân, ta phaân phoá phoái toá toái Tr ña vaø vaøo oâ coù coù cöôùc phí phí lôù lôùn nhaá nhaát. t. i 1 m n xij 0; cij 0; ai 0; b j 0; ai b j i 1, m; j 1, n. 2.Tieâ 2.Tieâu chuaå chuaån toá toái öu laø laø vj – ui cij, i,j 3.O 3.O ñieà ieàu chæ chænh laø laø oâ coù coù {min ij, vôù vôùi < 0} i 1 j 1 ij g oân THUAÄ THUAÄT GIAÛ GIAÛI THEÁ THEÁ VÒ VÔÙ VÔÙI HAØ HAØM MUÏ MUÏC TIEÂU Z Max THUAÄ THUAÄT GIAÛ GIAÛI THEÁ THEÁ VÒ VÔÙ VÔÙI HAØ HAØM MUÏ MUÏC TIEÂU Z Max Ví duï duï 3.7. Moä Moät coâng ty coùcoù 3 xíxí nghieä nghieäp cuø cuøng ng saû saûn xuaá xuaát moä moät loaï loaïi boù boùng ng ñeøn. n. Naêng suaásuaát trong thaù thaùng ng T 200 400 600 800 cuû cuûa 3 xí xí nghieä nghieäp laà laàn lö laø A i = (650, 1.000, 350) löôït laø P boù boùng. ng. Hôï Hôïp ñoàngng coâng ty phaû phaûi giao cho 4 nhaø nhaø 22 25 20 18 10 C phaân phoá laø Bj = (200, 400, 600, 800) boù phoái laø boùng. ng. Ñ ôn 650 giaù giaù baù baùn cuû cuûa moãi boùboùng ng ñe øn tötöông öùng ng vôù vôùi caù caùc -2 -3 + 250 – 400 nhaø nhaø phaân phoá phoái ñöô ñöôïc cho bôû bôûi ma traä traän sau: 30 32 25 28 0 Ñvt: 1.000 ñoàngng 22 25 20 18 1000 – 200 400 + 400 cij 30 32 25 28 29 28 25 23 5 eãn 350 + -1 – 350 29 28 25 23 -4 Haõy tì tìm keá keá hoaï hoaïch ch phaân phoá phoái haø haøng ng sao cho coâng 30 32 30 28 q = 200 ty ñaït doanh soá soá lôù lôùn nhaá nhaát y gu THUAÄ THUAÄT GIAÛ GIAÛI THEÁ THEÁ VÒ VÔÙ VÔÙI HAØ HAØM MUÏ MUÏC TIEÂU Z Max THUAÄ THUAÄT GIAÛ GIAÛI THEÁ THEÁ VÒ VÔÙ VÔÙI HAØ HAØM MUÏ MUÏC TIEÂU Z Max T 200 400 600 800 T 200 400 600 800 P P 22 25 20 18 10 22 25 20 18 7 650 650 N + -3 450 – 200 200 450 30 32 25 28 0 30 32 25 28 0 1000 1000 – 400 + 600 200 800 29 28 25 23 5 29 28 25 23 2 350 350 200 -1 150 200 150 34 32 30 28 q = 200 31 32 27 28 Z = 52.350 ¸¬¬°æññ²½¬®·ò½±ò½½ PDF created with pdfFactory Pro trial version www.pdffactory.com
  9. ÝØJLÒÙ íæ ÞßH× ÌÑßGÒ Êß\Ò ÌßE× Ì¸-ò Ò¹«§»=² ݱ>²¹ Ì®3 ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ THUAÄ THUAÄT GIAÛ GIAÛI BAØ BAØI TOAÙ TOAÙN VAÄ VAÄN TAÛ TAÛI BAØ BAØI TOAÙ TOAÙN VAÄ VAÄN TAÛ TAÛI COÙ COÙ O CAÁ CAÁM COÙ COÙ HAØ HAØM MUÏ MUÏC TIEÂU LAØ LAØ MAX Baø Baøi toaù toaùn vaä vaän taû taûi coù caám laø coù oâ caá laø baø baøi toaù toaùn vaä vaän taû taûi •Do caù caùc 0, i, j vôù vôùi P.A.T.Ö P.A.T.Ö cuû cuûa noù noù phaû phaûi thoû thoûa ñieà ieàu kieä kieän cho trö tröô ùc. c. ij Ñeå giaû giaûi baø baøi toaù toaùn naø naøy, y, ta laä laäp baø baøi toaù toaùn vaä vaän taû taûi môû môû •P.A.T.Ö P.A.T.Ö CUÛ CUÛA BAØ BAØI TOAÙ TOAÙN roä roäng ng VTM baè baèng ng caù caùch ch cho giaù giaù cöôùc vaä vaän chuyeå chuyeån ôû ôû 0 200 450 0 caù caùc oâ caá caám baè baèng ng M, vôù vôùi M > 0 lôù lôùn tuø tuøy yù yù roà roài duø duøng ng thuaä thuaät toaù toaùn theá theá vò. Coù Coù 2 trö tröôøng ng hôï hôïp xaû xaûy ra xopt 0 200 0 800 1.Trong 1.Trong P.A.T.Ö P.A.T.Ö cuû cuûa baø baøi toaù toaùn VTM, neá neáu caù caùc oâ caá caám í 200 0 150 0 coù coù xij = 0 thì thì P.A.T.Ö P.A.T.Ö cuû cuûa baø baøi toaù toaùn VTM cuõng chí chính Tr laø laø P.A.T.Ö P.A.T.Ö cuû cuûa baø baøi toaù toaùn goá goác. c. •Vaø Vaø ZMax = 52.350 2.Trong 2.Trong P.A.T.Ö P.A.T.Ö cuû cuûa baø baøi toaù toaùn VTM, neá neáu caù caùc oâ caá caám coù coù xij 0 thì thì baø baøi toaù toaùn goá goác khoâng coù coù P.A.T.Ö P.A.T.Ö. g oân BAØ BAØI TOAÙ TOAÙN VAÄ VAÄN TAÛ TAÛI COÙ COÙ O CAÁ CAÁM T 140 150 180 25 Baû Baûng ng 1 Ví duï duï 3.8. Giaû Giaûi baø baøi toaù toaùn vaä vaän taû taûi sau ñaây vôù vôùi P Nhu caà caàu traï traïm phaù phaùt a = (150, 100, 145, 100) 5 4 6 0 4 Nhu caà caàu traï traïm thu b = (140, 150, 180) 5 4 150 6 0 150 +3 M-4 Ma traä traän cö cöôùc vaä vaän chuyeå chuyeån C 8 5 9 8 5 9 0 1 cij 100 vôù vôùi ñieà ieàu kieä kieän 11 6 12 – 100 +2 +3 + M-1 11 6 12 M 1 traïm A3, A4 phaû traï phaûi phaù phaùt heá heát haø haøng. ng. 9 7 13 145 Kieå Kieåm tra ñieà ieàu kieä kieän caân baè baèng ng thu – phaù phaùt +1 145 eãn ai = 150 + 100 + 145 + 100 = 495 9 7 13 M 0 bj = 140 + 150 + 180 = 470 100 + 40 +1 35 – 25 q = 25 Laä Laäp traï traïm thu giaû vôùi b4= 25 vaø giaû, vôù vaø M > 0 tuø tuøy yù yù. 9 8 13 M y gu T 140 150 180 25 Baû Baûng ng 2 T 140 150 180 25 Baû Baûng ng 3 P P 5 4 6 0 4 5 4 6 0 3 150 150 0 150 +3 + 0 – 150 8 5 9 0 1 8 5 9 0 0 100 100 N – 75 +2 + +3 25 – 40 +2 + 35 25 11 6 12 M 1 11 6 12 M -3 145 145 +1 145 + +4 – 145 9 7 13 M 0 9 7 13 M -1 100 100 + 65 +1 – 35 100 +1 q = 35 q = 40 9 8 13 1 8 7 9 0 ¸¬¬°æññ²½¬®·ò½±ò½½ PDF created with pdfFactory Pro trial version www.pdffactory.com
  10. ÝØJLÒÙ íæ ÞßH× ÌÑßGÒ Êß\Ò ÌßE× Ì¸-ò Ò¹«§»=² ݱ>²¹ Ì®3 ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ T 140 150 180 25 Baû Baûng ng 4 T 140 150 180 25 Baû Baûng ng 5 P P 5 4 6 0 0 5 4 6 0 0 150 150 40 – 110 + +4 +1 40 – 5 + 105 8 5 9 0 1 8 5 9 0 -3 100 100 75 25 + +2 – 75 25 11 6 12 M -2 11 6 12 M -2 145 145 + 40 – 105 145 í 9 7 13 M 9 7 13 M Tr -4 -4 100 100 100 +1 +1 100 +1 q =105 q=5 5 4 10 1 5 4 6 -3 g oân T 140 150 180 25 Baû Baûng ng 6 BAØ BAØI TOAÙ TOAÙN VAÄ VAÄN TAÛ TAÛI COÙ COÙ O CAÁ CAÁM P •Do caù caùc 0 i,j neân 5 4 6 0 3 ij 150 •P.A.C.B.T.Ö P.A.C.B.T.Ö cuû cuûa baø baøi toaù toaùn vaä vaän taû taûi treân laø laø – 40 + 110 C 8 5 9 0 0 100 40 0 110 + 0 5 – 70 25 11 6 12 M -1 0 5 70 145 xopt 145 0 145 0 eãn 9 7 13 M -1 100 100 0 0 100 Z =3.285 P.A.T.Ö P.A.T.Ö khaù khaùc8 5 9 0 q = 40 vaø Zmin= 3.285 •vaø y gu T 140 150 180 25 Baû Baûng ng 7 BAØ BAØI TOAÙ TOAÙN VAÄ VAÄN TAÛ TAÛI COÙ COÙ O CAÁ CAÁM P •P.A.C.B.T.Ö P.A.C.B.T.Ö khaù khaùc cuû cuûa baø baøi toaù toaùn vaä vaän taû taûi treân laø laø 5 4 6 0 3 0 0 150 150 0 150 40 5 30 x op t 8 5 9 0 0 •vaø 0 145 0 100 vaø Z min= 3.285 N 40 5 30 25 •Taä 100 0 0 Taäp phö phöông aù aùn toá toái öu 11 6 12 M -1 145 •Z opt = Xopt + (1 – ) X/opt 145 40 0 150 40 9 7 13 M -1 100 40 40 5 30 40 •Hay Z o p t 100 Z =3.285 0 145 0 8 5 9 0 100 0 0 ¸¬¬°æññ²½¬®·ò½±ò½½ PDF created with pdfFactory Pro trial version www.pdffactory.com
  11. ÝØJLÒÙ íæ ÞßH× ÌÑßGÒ Êß\Ò ÌßE× Ì¸-ò Ò¹«§»=² ݱ>²¹ Ì®3 ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ MO HÌNH BAØ BAØI TOAÙ TOAÙN VAÄ VAÄN TAÛ TAÛI XE KHOÂNG THUAÄ THUAÄT GIAÛ GIAÛI BAØ BAØI TOAÙ TOAÙN XE KHOÂNG TAÛ TAÛI Ñieà ieàu kieä kieän raø raøng ng buoä buoäc cuû cuûa baø baøi toaù toaùn vaä vaän taû taûi xe 1. Laä Laäp baû baûng ng vaä vaän taû taûi tö töông öùng ng vôù vôùi ma traä traän khoâng laø laø moä moät soá soá traï traïm phaù phaùt A i phaûphaûi phaù phaùt ñuû haø haøng ng khoaû khoaûngng caù caùch. ch. Duø Duøng ng thuaä thuaät toaù toaùn theá theá vò tì tìm P.A.T.Ö P.A.T.Ö cho traïtraïm Bj (ñöôñöôïc chæchæ ñònh). Xaù Xaùc ñònh loä loä trì trình xe cuû cuûa baø baøi toaù toaùn xe khoâng taû taûi. i. chaï chaïy khoâng taû taûi töø töø Bj ñeán Ai laølaø ít nhaá nhaát. t. 2. Taï Taïo baû baûngng phoá phoái hôï hôïp P.A.T.Ö P.A.T.Ö cuû cuûa baøbaøi toaù toaùn xe Khi ñoù traï traïm phaù phaùt A i trôûtrôû thaø thaønh nh traïtraïm thu xe khoâng taû taûi vôù vôùi keá keá hoaï hoaïch ch vaävaän taû taûi ñaõ cho trö tröôùc. c. Laä Laäp khoâng, traï traïm thu Bj trôûtrôû thaø thaønh nh traï traïm phaù phaùt xe khoâng tuyeá tuyeán ñieà ieàu ñoäng ng tötöông öùng. ng. vaø vaø khi ñoù ma traä traän (c ij) laø laø ma traä traän khoaû khoaûng ng caùcaùch ch 3. Giaû Giaûm lö löôïng ng cheânh leä leäch ch giögiöõa “oâ troø troøn” vaøvaø “oâ töông öùng ng giö giöõa Ai vaø vaø Bj. vuoâng”g” ñeå coù coù baû baûngng môùmôùi thu goï goïn.n. Qui öôùc söûsöû duï duïng ng caù caùc kyù kyù hieähieäu nhö nhö sau: 4. Laä Laäp voø voøng ng ñieà ieàu ño äng ng goà goàm caù caùc oâ coù coù taû taûi vaø vaø oâ í x ij : lö löôïng ng haø haøngng hoù hoùa coù coù vaä vaän taû taûi. i. khoâng taûtaûi lieân tieá tieáp nhau, lö löôïng ng ñieà ieàu ñoäng ng q= Tr xij : lö löôïng ng haø haøngng cuû cuûa xe khoâng taû taûi.i. min{xij}, vôù vôùi x ij coù coù taû taûi vaø vaø xij khoâng taû taûi. i. Trôû Trôû veà veà [3]. : tuyeá tuyeán xe chaïchaïy coù coù taû taûi.i. Sau moä moät soá soá böôùc laë laëp hö höõu haï haïn [3] vaøvaø [4], ta seõ thu : tuyeá tuyeán xe chaïchaïy khoâng taû taûi ñöô ñöôïc keá keá hoaï hoaïch ch ñieà ieàu ñoängng haøhaøng ng hoùhoùa toátoái öu. g oân THUAÄ THUAÄT GIAÛ GIAÛI BAØ BAØI TOAÙ TOAÙN XE KHOÂNG TAÛ TAÛI THUAÄ THUAÄT GIAÛ GIAÛI BAØ BAØI TOAÙ TOAÙN XE KHOÂNG TAÛ TAÛI Ví duï duï 3.9. Moä Moät coâng ty vaä vaän taû taûi coù coù keá keá hoaï hoaïch ch vaä vaän Cho bieá bieát khoaû khoaûngng caù caùch ch giö giöõa ñòa ñieå ieåm cung chuyeå chuyeån haø haøng ng hoù hoùa theo hôï hôïp ñoàng, ng, ñöô ñöôïc theå theå hieä hieän caá caáp haø haøng ng vaø vaø ñòa ñieå ieåm nhaä nhaän haø haøng ng (km) ñöô ñöôïc theå theå qua baû baûng ng yeâu caà caàu nhö nhö sau hieä hieän qua ma traä traän nhö nhö sau: C Ñòa ñieå ieåm Loaï Loaïi Lö ôïng ng Nôi nhaä nhaän Kyù Kyù hieä hieäu 2 1 4 3 caá caáp haø haøng ng Ai haø haøng ng (taá (taán) n) haø haøng ng Bj 20 Coâng ty rau quaû quaû B2 L 5 2 6 4 A1 Cam 30 Cöûa haø haøng ng soá soá 3 B3 25 Cöûa haø haøng ng soá soá 1 B1 3 4 2 5 eãn A2 Döa haá haáu 15 Coâng ty rau quaû quaû B2 Haõy xaù xaùc ñònh loäloä trì trình vaä vaän chuyeå chuyeån haøhaøng ng hoù hoùa 10 Cöûa haø haøng ng soá soá 3 B3 thoû thoûa yeâu caà caàu hôï hôïp ñoàngng vaø vaø toå toång ng taá taán – km xe 50 Cöûa haø haøng ng soá soá 4 B4 A3 Saà Saàu rieâng chaï chaïy khoâng taû taûi nhoû nhoû nhaá nhaát. t. 20 Coâng ty rau quaû quaû B2 y gu Böôùc 1 (tì (tìm P.A.T.Ö P.A.T.Ö cuû cuûa baø baøi toaù toaùn xe khoâng taû taûi) i) Böôùc 2 (taï (taïo baû baûng ng phoá phoái hôï hôïp) p) Baûûng 2 Ba Bj 25 55 40 50 Baû Baûng 1 Bj 25 55 40 50 Ai Ai 2 1 4 3 2 2 1 20 4 30 3 50 50 50 50 N 5 2 6 4 1 5 25 2 15 6 10 4 50 50 5 45 5 45 3 4 2 5 0 3 4 20 2 5 50 70 70 25 40 5 25 40 5 A1 B2 1km A 1: 20 T X 1km = 20T – km 3 3 2 5 A2 B2 2km A 2: 5 T X 2km = 10T – km Zmin= 420 taá taán – km A3 B4 5km A 3: 5 T X 5km = 25T – km ¸¬¬°æññ²½¬®·ò½±ò½½ PDF created with pdfFactory Pro trial version www.pdffactory.com
  12. ÝØJLÒÙ íæ ÞßH× ÌÑßGÒ Êß\Ò ÌßE× Ì¸-ò Ò¹«§»=² ݱ>²¹ Ì®3 ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ Böôùc 3 (laä (laäp tuyeá tuyeán ñieà ieàu ñoäng) ng) Baû Baûng 3 Böôùc 3 (laä (laäp tuyeá tuyeán ñieà ieàu ñoäng) ng) Baûûng 4 Ba Bj 25 55 40 50 Bj 25 55 40 50 Ai Ai 2 1 4 30 3 2 1 4 10 3 50 50 30 10 5 25 2 10 6 10 4 5 5 2 10 6 10 4 50 50 45 25 3 4 20 2 5 45 3 4 2 5 25 70 í 70 25 40 q=20 5 20 Tr q=5 A2 B1 3km A3 B2 1km A1 B3 A2 B1 3km A3 B4 3km 2km A3 B4 4km A 2:20Tx10km=200T- :20Tx10km=200T-km 4km A2: 5T x 7km = 35T– 35T–km. g oân Böôùc 3 (laä (laäp tuyeá tuyeán ñieà ieàu ñoäng) ng) Baû Baûng 5 Böôùc 3 (laä (laäp tuyeá tuyeán ñieà ieàu ñoäng) ng) Baûûng 6 Ba Bj 25 55 40 50 Bj 25 55 40 50 Ai Ai 2 1 4 10 3 2 1 4 3 50 50 C 10 5 2 10 6 10 4 5 2 6 10 4 50 50 20 10 3 4 2 5 20 3 4 2 5 10 70 70 eãn 20 10 q=10 q=10 A2 B2 1km A1 A3 B3 2km A2 B3 2km A3 B4 B4 4km A2: 10T x 7km = 70T– 70T–km 4km A : 10 T x 6km = 60T– 2 60T–km y gu THUAÄ THUAÄT GIAÛ GIAÛI BAØ BAØI TOAÙ TOAÙN XE KHOÂNG TAÛ TAÛI BAØ BAØI TAÄ TAÄP CHÖ CHÖÔNG 3 BAÛ BAÛNG ÑIEÀ IEÀU ÑOÄNG NG XE LAÄ LAÄP MO HÌNH CUÛ CUÛA BAØ BAØI TOAÙ TOAÙN VAÄ VAÄN TAÛ TAÛI A1 B2 1km A1: 20 T [ 1] [ 2] A2 B2 2km A2: 5 T Ths. 3b] Nguyeã 3e] n Coâng Tr Tríí TÌM PHÖ PHÖ ÔNG AÙ AÙN CÖÏ CÖÏC BIEÂN ÑA ÀU TIEÂN A3 B4 5km A3: 5 T N [3a] 3a] [3b] [3c ] [3d] 3d] [3e] * A2 B1 3km A3 B2 1km A1 B3 2km A GIAÛ GIAÛI BAØ BAØI TOAÙ TOAÙN VAÄ VAÄN TAÛ TAÛI CAÂN BAÈ BAÈNG NG THU - PHAÙ PHAÙT B4 A2: 20 T Copyright [6] [7] [8] [9] 2001 4km 3 [ 4] [ 5] A2 B1 3km A3 B4 4km A2: 5 T A2 B2 1km A1 B3 2km A3 CAÙ CAÙC DAÏ DAÏNG NG KHAÙ KHAÙC CUÛ CUÛA BAØ BAØI TOAÙ TOAÙN VAÄ VAÄN TAÛ TAÛI B4 4km A2: 10 T [10a] 10a] [10b] 10b] [10c] 10c] A2 B3 2km A3 B4 4km A2: 10 T [11a] 11a] [11b] 11b] [11c] 11c] [11d] 11d] ¸¬¬°æññ²½¬®·ò½±ò½½ PDF created with pdfFactory Pro trial version www.pdffactory.com
  13. ÝØJLÒÙ íæ ÞßH× ÌÑßGÒ Êß\Ò ÌßE× Ì¸-ò Ò¹«§»=² ݱ>²¹ Ì®3 ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ BAØI TAÄP CHÖÔNG 3 LAÄP MO HÌNH CUÛA BAØI TOAÙN VAÄN TAÛI DÖÔÙI DAÏNG BAØI TOAÙN QHTT [1] Moät coâng ty vaän taûi bieån caàn 110 ngöôøi ñeå boá trí vaøo caùc nhieäm vuï: 10 maùy tröôûng; 25 thôï maùy 1; 30 thôï maùy 2; 45 thôï maùy 3. Phoøng toå chöùc nhaân söï coâng ty tuyeån ñöôïc 90 ngöôøi, trong ñoù goàm 25 kyõ sö maùy; 20 kyõ thuaät vieân trung caáp vaø 45 coâng nhaân coù kinh nghieäm. Phoøng toå chöùc nhaân söï ñaùnh giaù trình ñoä nhaân söï töông öùng vôùi töøng coâng vieäc theo thang ñieåm 5, ví duï aij = 5 nghóa laøvôùi trình ñoä i coù khaû naêng hoaøn thaønh xuaát saéc coâng vieäc j (ñaït ñieåm toái ña laø 5), coøn aij = 0 laø vôùi trình ñoä i í khoâng coù khaû naêng hoaøn thaønh coâng vieäc j (ñaït ñieåm 0), ñöôïc theå hieän chi tieát trong Tr baûng sau Nhieäm vuï Ñieåm ñaùnh giaù naêng löïc (aij) Trình ñoä Maùy tröôûng Maùy 1 Maùy 2 Maùy 3 g Kyõ sö 5 4 0 0 Trung caáp 3 5 4 0 oân Coâng nhaân 0 1 5 4 Haõy laäp keá hoaïch boá trí nhaân löïc sao cho coâng vieäc ñaït toái öu. [2] Hai ñoäi tuyeån boùng baøn, moãi ñoäi coù 5 ngöôøi. Qua thoáng keâ nhieàu traän ñaáu trong quaù khöù, ngöôøi ta döï ñoaùn xaùc suaát thaéng cuoäc moãi ñaáu thuû cuûa moãi ñoäi ñöôïc theå hieän C qua baûng sau Ñoäi II Ñaáu thuû 1 Ñaáu thuû 2 Ñaáu thuû 3 Ñaáu thuû 4 Ñaáu thuû 5 Ñoäi I eãn Ñaáu thuû 1 0,4 0,5 0,6 0,7 0,8 Ñaáu thuû 2 0 0,3 0,4 0,4 0,7 Ñaáu thuû 3 0,2 0,6 0,4 0,3 0,5 Ñaáu thuû 4 0,6 0,3 0,4 0,7 0,6 y Ñaáu thuû 5 0 0,2 0,3 0,4 0,6 Giaû söû caùc ñaáu thuû cuûa ñoäi I ñöôïc quyeàn choïn thi ñaáu vôùi caùc tuyeån thuû ñoäi II. Haõy saép gu xeáp caùc ñaáu thuû cuûa ñoäi I sao cho xaùc suaát thaéng toaøn ñoaøn cuûa ñoäi I cao nhaát. TÌM PHÖÔNG AÙN CÖÏC BIEÂN ÑAÀU TIEÂN [3] Tìm phöông aùn cöïc bieân ñaàu tieân baèng hai phöông phaùp chi phí beù nhaát vaø phöông phaùp Vogels cuûa caùc baøi toaùn vaän taûi sau ñaây N a) Bj b) Bj c)* Bj 20 25 30 15 3 5 10 14 10 30 50 Ai Ai Ai 40 4 5 1 2 10 1 3 7 1 25 7 6 5 20 3 4 7 8 15 2 4 2 3 10 2 1 4 30 2 6 9 3 7 6 5 4 1 45 3 5 2 ¸¬¬°æññ²½¬®·ò½±ò½½ PDF created with pdfFactory Pro trial version www.pdffactory.com
  14. ÝØJLÒÙ íæ ÞßH× ÌÑßGÒ Êß\Ò ÌßE× Ì¸-ò Ò¹«§»=² ݱ>²¹ Ì®3 ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ d) Bj e) Bj 40 30 20 50 30 20 25 35 40 Ai Ai 30 3 7 4 6 30 13 7 6 2 12 40 4 6 2 5 20 5 1 10 5 11 70 1 5 7 8 40 10 5 3 7 14 60 6 3 2 11 10 GIAÛI BAØI TOAÙN VAÄN TAÛI BAÈNG THUAÄT TOAÙN THEÁ VÒ [4] Giaûi baøi taäp [3], vôùi phöông aùn cöïc bieân ñaàu tieân thu ñöôïc baèng phöông phaùp chi í phí beù nhaát. Tr 0 0 30 10 3 0 0 7 Ñs: a) xopt 20 0 0 vaø Zmin = 215; b) xopt 0 0 5 10 0 vaø Zmin = 57; 20 5 0 5 0 0 0 7 g 0 20 5 0 0 0 30 * c) xopt 0 10 0 vaø Zmin = 245; d) xopt 0 0 20 20 vaø Zmin = 510; oân 0 0 45 40 30 0 0 0 0 0 30 0 10 10 0 0 0 e) xopt vaø Zmin = 800. 0 10 25 5 0 C 20 0 0 0 40 [5] a) Giaûi baøi toaùn vaän taûi Bj eãn 50 160 120 80 Ai 220 5 4 3 10 100 5 9 7 12 90 10 6 8 15 y b) Baøi toaùn coù phöông aùn toái öu khaùc hay khoâng? 0 70 120 30 gu Ñs: a) xopt 50 0 0 50 vaø zmin = 2330; b) khoâng coù PATU khaùc. 0 90 0 0 [6] a) Giaûi baøi toaùn vaän taûi N Bj 20 100 45 15 Ai 90 10 6 4 1 40 3 4 2 5 50 9 4 3 7 b) Baøi toaùn coù P.A.T.Ö khaùc hay khoâng? Neáu coù, haõy chæ ra taäp phöông aùn toái öu. ¸¬¬°æññ²½¬®·ò½±ò½½ PDF created with pdfFactory Pro trial version www.pdffactory.com
  15. ÝØJLÒÙ íæ ÞßH× ÌÑßGÒ Êß\Ò ÌßE× Ì¸-ò Ò¹«§»=² ݱ>²¹ Ì®3 ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ 0 50 25 15 0 30 45 15 / Ñs: a) xopt 20 0 20 0 ; b) xopt 20 20 0 0 Zmin= Z min =715; 0 50 0 0 0 50 0 0 0 30 20 45 20 15 Topt 20 20 20 20 0 , 0,1 . 0 50 0 0 [7] Cho baøi toaùn vaän taûi coù daïng sau ñaây: ai 20 110 120 bj 70 40 30 60 50 4 2 5 7 6 í Tr cij 5 8 3 4 5 2 1 4 3 2 a) Tìm phöông aùn toái öu cuûa baøi toaùn treân. g b) Theo anh (chò) daáu hieäu naøo cho ta bieát baøi toaùn vaän taûi coù nhieàu phöông aùn toái öu? Phöông aùn toái öu tìm ñöôïc ôû caâu a) coù duy nhaát khoâng? Neáu coù haõy chæ ra phöông aùn cöïc bieân toái öu khaùc. oân c) Tìm taäp caùc phöông aùn toái öu vaø chæ ra 3 phöông aùn toái öu khaùc nhau. 0 20 0 0 0 0 20 0 0 0 a) Ñs: xopt 0 0 30 60 20 vaø zmin=690; b) Ñs: xopt 20 0 30 60 0 70 20 0 0 30 50 20 0 0 50 C [8] Cho baøi toaùn vaän taûi coù daïng sau ñaây: ai 38, 45, 66, 45 bj 52, 45, 38, 59 eãn 9 5 6 14 10 7 9 15 cij 10 10 6 7 4 8 13 14 y a) Tìm phöông aùn toái öu cuûa baøi toaùn treân. b) Phöông aùn toái öu vöøa tìm ñöôïc coù duy nhaát khoâng? (coù giaûi thích). Chæ ra gu moät phöông aùn toái öu khaùc? (neáu coù). 0 7 31 0 7 38 0 0 a) Ñs: xopt vaø Zmin = 1.192; b) P.A.T.Ö. treân duy nhaát. 0 0 7 59 N 45 0 0 0 [9] Giaûi baøi taäp [1], [2]. ¸¬¬°æññ²½¬®·ò½±ò½½ PDF created with pdfFactory Pro trial version www.pdffactory.com
  16. ÝØJLÒÙ íæ ÞßH× ÌÑßGÒ Êß\Ò ÌßE× Ì¸-ò Ò¹«§»=² ݱ>²¹ Ì®3 ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ CAÙC DAÏNG KHAÙC CUÛA BAØI TOAÙN VAÄN TAÛI [10] Giaûi caùc baøi toaùn vaän taûi sau ñaây vaø tìm phöông aùn toái öu khaùc (neáu coù) a) Bj 60 60 80 100 Ai 80 4 5 6 12 70 10 3 9 5 100 6 4 7 9 í 60 0 20 0 Tr Ñs: xopt 0 0 0 70 vaø Zmin = 1.230; P.A.T.Ö. treân duy nhaát. 0 60 40 0 b) Traïm phaùt: ai 100 20 30 50 ; Traïm thu b j g 70 60 25 50 10 14 24 8 oân 30 20 18 14 Ma traän cöôùc phí vaän taûi cij 2 12 6 7 8 16 14 36 0 50 0 50 0 55 0 45 C 0 5 15 0 0 0 15 5 Ñs: xopt Zmin = 1.970; xopt vaø Z/min = 1.970. 20 0 10 0 20 0 10 0 50 0 0 0 50 0 0 0 c) Traïm phaùt: ai 79, 50, 60, 50 ; traïm thu : b j 46, 45, 76, 20, 52 eãn 10 1 5 13 8 5 6 10 8 13 Ma traän cöôùc phí vaän taûi cij 3 2 8 9 6 y 13 5 7 10 13 0 45 34 0 0 gu 38 0 0 12 0 Ñs: xopt Zmin = 1.211; P.A.T.Ö. treân duy nhaát. 8 0 0 0 52 0 0 42 8 0 [11] Giaûi caùc baøi toaùn vaän taûi coù oâ caám sau ñaây vaø tìm phöông aùn toái öu khaùc (neáu coù) N a) Traïm phaùt: a i 90 40 50 ; traïm thu : b j 20 100 45 10 6 4 Ma traän cöôùc phí vaän taûi cij 3 4 2 9 4 3 Ñieàu kieän traïm A3 phaûi phaùt heát haøng. b) Traïm phaùt: ai 100 80 50 ; traïm thu : b j 65 90 50 30 ¸¬¬°æññ²½¬®·ò½±ò½½ PDF created with pdfFactory Pro trial version www.pdffactory.com
  17. ÝØJLÒÙ íæ ÞßH× ÌÑßGÒ Êß\Ò ÌßE× Ì¸-ò Ò¹«§»=² ݱ>²¹ Ì®3 ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ 10 9 12 7 Ma traän cöôùc phí vaän taûi cij 9 11 10 15 8 7 14 12 Ñieàu kieän traïm B2 phaûi thu ñuû haøng. c) Traïm phaùt: a i 220, 100, 90 ; traïm thu : b j 50, 160, 120, 80 5 4 3 10 Ma traän cöôùc phí vaän taûi cij 5 9 7 12 10 6 8 15 í Ñieàu kieän traïm phaùt A 3 khoâng ñöôïc phaùt cho traïm thu B2. Tr d) Traïm phaùt: a i 90 40 50 ; traïm thu : b j 20 100 45 10 6 4 Ma traän cöôùc phí vaän taûi cij g 3 4 2 9 4 3 oân Ñieàu kieän traïm thu B2 khoâng ñöôïc thu cuûa traïm phaùt A1. C y eãn gu N ¸¬¬°æññ²½¬®·ò½±ò½½ PDF created with pdfFactory Pro trial version www.pdffactory.com
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