Toán học - Chương 3: Bài toán vận tải

Ths. Nguyễn Công Tr. ã â ã â íí Copyright 2001 Ths. Nguyễn Công Trã âã â í Copyright 2001 BÀØI TOÁÙN VẬÄN TẢÛI 1. BÀØI TOÁÙN VẬÄN TẢÛI DẠÏNG TỔÅNG QUÁÙT (Xem) 2. CÁÙC TÍNH CHẤÁT VÀØ TIÊU CHU ÅÅN TỐÁI ƯU CỦÛA BÀØI TOÁÙ VẬÄN TẢÛI (Xem) 3. CÁÙC PHƯƠNG PHÁÙP TÌM PHƯƠNG ÁÙN CỰÏC BIÊN ĐẦÀU TIÊN CU ÛÛA BÀØI TOÁÙN VẬÄN TẢÛI (Xem) 4. THUẬÄT GIẢÛI THẾÁ VỊ CHO BÀØI TOÁÙN VẬÄN TẢÛI (Xem) 5. CÁÙC DẠÏNG KHÁÙC CỦÛA BÀØI TOÁÙN VẬÄN TẢÛI (Xem) 6. BÀØI TẬÄP (Xem) CHƯƠNG 3 NỘÄI DUNG BÀØI TOÁÙN VẬÄN TẢÛI Giảû sửû cầàn vậän chuyểån mộät loạïi hàøng hóùa (xi măng, să éét théùp, ...) từø m điểåm cung cấáp (trạïm pháùt), kýù hiệäu làø A1, A2, ..., Am đếán n điểåm tiêu â thụï (trạïm thu), kýù hiệäu làø B1, B2, ..., Bn, biếát rằèng (1) Sốá lượïng hàøng cóù ởû cáùc trạïm pháùt A1, A2, ..., Am lầàn lượït làø a1, a2,..., am (2) Sốá lượïng hàøng cầàn ởû cáùc trạïm thu B1, B2, ..., Bn lầàn lượït làø b1, b2,..., bn. (3) Chi phí vậän chuyểån mộät đơn vị hàøng hóùa từø trạïm pháùt Ai đếán trạïm thu Bj làø cij. Hãy lã ääp kếá hoạïch vậän tảûi hàøng hóùa sao cho tổång chi phí vậän tảûi thấáp nhấát vàø thỏûa mãn yêu õ â cầàu thu – pháùt. BÀØI TOÁÙN VẬÄN TẢÛI DẠÏNG TỔÅNG QUÁÙT MÔ HÌNH B ØØI TOÁÙN VẬÄN TẢÛI Đặët xij làø sốá lượïng hàøng cầàn vậän chuyểån từø trạïm pháùt Ai đếán trạïm thu Bj. Ta cóù tổång chi phí vậän tảûi: (1) Trạïm pháùt, pháùt hếát hàøng: (2) Trạïm thu, thu đủû hàøng: (3) Yêu câ ààu trạïm pháùt, trạïm thu đượïc thỏûa (đk cân bâ èèng thu – pháùt). BÀØI TOÁÙN VẬÄN TẢÛI DẠÏNG TỔÅNG QUÁÙT 1 1 min m n ij ij i j Z c x 1 , 1, n ij i j x a i m 1 , 1, m ij j i x b j n 1 1 m n i j i j a b Vậäy, mô hâ ình toáùn củûa bàøi toáùn vậän tảûi (BTVT) dạïng tổång quáùt như sau: Tìm {xij} sao cho: BÀØI TOÁÙN VẬÄN TẢÛI DẠÏNG TỔÅNG QUÁÙT 1 1 1 1 1 1 min , 1, , 1, 0; 0; 0; 0; m n ij ij i j n ij i j m ij j i m n ij ij i j i j i j Z c x x a i m x b j n x c a b a b BÀØI TOÁÙN VẬÄN TẢÛI DƯỚÙI DẠÏNG BÀØI TOÁÙN QHTT khai triểån BTVT vàø xếáp hệä ràøng buộäc dướùi dạïng hệä m + n phương trình củûa m n biếán như sau Kýù hiệäu Am+n,m n ma trậän hệä sốá củûa hpt trên.â XT = (x11 x12 ... x1n x21 x22 ... x2n ... xm1 xm2 ... xmn) làø vectơ cộät gồàm m n thàønh phầàn; C = (c11 c12 ... c1n c21 c22 ... c2n cm1 cm2 ... cmn) làø vectơ dòøng gồàm m n thàønh phầàn; bT = (a1 a2 ... am b1 b2 ... bn) làø vectơ cộät gồàm m+ n thàønh phầàn. BÀØI TOÁÙN VẬÄN TẢÛI DẠÏNG TỔÅNG QUÁÙT 11 12 1 1 21 22 2 2 1 2 11 21 1 1 12 22 2 2 1 2 n n m m mn m m m n n mn n x x x a x x x a x x x a x x x b x x x b x x x b BTVT viếát dướùi dạïng vectơ vàø ma trậän như sau Mộät vectơ X thỏûa (*) vàø (**) gọïi làø phương áùn. Mộät P.A đạït cựïc tiểåu thì gọïi làø P.A.T.Ư củûa BTVT. Mộät phương áùn X đượïc gọïi làø P.A.C.B khi cáùc vectơ cộät Aj củûa ma trậän hệä sốá A ứùng vớùi cáùc thàønh phầàn xij > 0 làø độäc lậäp tuyếán tính. Mộät P.A.C.B củûa BTVT cóù nhiềàu nhấát làø m + n – 1 thàønh phầàn dương. Nếáu mộät P.A.C.B củûa BTVT cóù đúùng m + n – 1 thàønh phầàn dương thì đượïc gọïi làø không suy biê áán. Ngượïc lạïi, đượïc gọïi làø phương áùn cựïc biên suy biê áán. BÀØI TOÁÙN VẬÄN TẢÛI DẠÏNG TỔÅNG QUÁÙT min * 0 ** Tz C X AX b X ÝØJLỊÙ íỉ ÞßH× ÌĐßGỊ Êß\Ị ÌßE× ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ̸­ị Ị¹«§»=² ݱ>²¹ Ì®3 ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ¸¬¬°ỉđđ²½¬®·ị½±ị½½ Ng uy ễn C â g Tr í PDF created with pdfFactory Pro trial version www.pdffactory.com B1 B2 BnTrạïm thu Bj Trạïm pháùt Ai b1 b2 bn A1 c11 c12 c1n a1 x11 x12 x1n A2 c21 c22 c2n a2 x21 x22 x2n Am cm1 cm2 cmn am xm1 xm2 xmn MÔ T ÛÛ BÀØI TOÁÙN DƯỚÙI DẠÏNG BẢÛNG VẬÄN TẢÛI (1) Kýù hiệäu (i, j) làø ô trên â â dòøng i vàø cộät j. (2) Chi phí vậän chuyểån cij đượïc ghi ởû góùc trên â bên trâ ùùi củûa ô (i, j), lâ ượïng hàøng cầàn vậän chuyểån xij đượïc ghi ởû góùc dướùi bên phâ ûûi củûa ô (i, j) biê ååu diễn tuyễ áán đườøng vậän chuyểån từø trạïm pháùt Ai đếán trạïm thu Bj. (3) Trong BẢÛNG VẬÄN TẢÛI, mộät ô â đượïc gọïi làø ô â treo nếáu nóù làø ô duy nhâ áát trên dô øøng hay trên cô äät. (4) Những ô õ â ứùng vớùi xij > 0 trong BẢÛNG VẬÄN TẢÛI đượïc gọïi làø ô chô ïïn, những ô khã â ùùc gọïi làø ô loâ ïïi. (5) Mộät dãy cã ùùc ô chô ïïn, trong đóù 3 ô liên tiê â ááp không nâ èèm trên cuâ øøng mộät dòøng hay mộät cộät thì đượïc gọïi làø mộät dây chuyê ààn. MÔ T ÛÛ BÀØI TOÁÙN DƯỚÙI DẠÏNG BẢÛNG VẬÄN TẢÛI (6) Mộät dây chuyê ààn khéùp kín đượïc gọïi làø mộät chu trình hay mộät vòøng. (7) Mộät ma trậän (xij) làø mộät P.A củûa BTVT nếáu nóù thoảû hệä ràøng buộäc. Mộät P.A (xij) làøm cựïc tiểåu hàøm mụïc tiêu thâ ì (xij) làø P.A.T.Ư. củûa bàøi toáùn. (8) Mộät P.A củûa BTVT không tâ ïïo thàønh chu trình (vòøng) thì đượïc gọïi làø Phương áùn cựïc biên.â (9) Mộät P.A.C.B củûa BTVT cóù đủû m+n-1 ô chô ïïn thì đượïc gọïi làø P.A.C.B không suy biê áán, nếáu cóù ít hơn m+n-1 ô chô ïïn đượïc gọïi làø P.A.C.B suy biếán. MÔ T ÛÛ BÀØI TOÁÙN DƯỚÙI DẠÏNG BẢÛNG VẬÄN TẢÛI VÍ DỤÏ 3.1. Hình 2.1. Hình 2.2. Hình 2.3. Hình 2.4. Hình 2.5. Hình 2.1. cáùc ô chô ïïn, cóù dấáu “ ”, tạïo thàønh dây chuyê ààn, cáùc ô (1,1) vâ øø (4,3) làø cáùc ô treo.â Hình 2.2. cáùc ô chô ïïn tạïo thàønh dây chuyê ààn, cáùc ô (4,1) vâ øø (3,3) làø cáùc ô treo.â Hình 2.3., Hình 2.4 vàø Hình 2.5. cáùc ô chô ïïn tạïo thàønh chu trình, không cô ùù ô treo.â MÔ T ÛÛ BÀØI TOÁÙN DƯỚÙI DẠÏNG BẢÛNG VẬÄN TẢÛI TÍNH CHẤÁT 1: Bàøi toáùn vậän tảûi luôn luôn cô â ùù phương áùn tốái ưu. TÍNH CHẤÁT 2: Vớùi mộät phương áùn bấát kỳø, sốá ô â chọïn củûa phương áùn không vâ ượït quáù tổång sốá trạïm pháùt vàø trạïm thu. m + n –1 (vớùi làø sốá ô chô ïïn củûa P.A) TÍNH CHẤÁT 3: Vớùi mộät phương áùn cóù đủû m+n–1 ô â chọïn thì vớùi mộät ô loâ ïïi bấát kỳø đượïc đưa vàøo phương áùn sẽ tã ïïo thàønh chu trình vàø chu trình nàøy làø duy nhấát. TÍNH CHẤÁT 4: Nếáu lượïng cung ai vàø lượïng cầàu bj làø sốá nguyên thâ ì bàøi toáùn cóù lờøi giảûi nguyên.â CÁÙC TÍNH CHẤÁT CỦÛA BÀØI TOÁÙN VẬÄN TẢÛI Xéùt bàøi toáùn vậän tảûi sau 1 1 min m n ij ij i j Z c x 1 1 , 1, , 1, n ij i j m ij j i x a i m x b j n TIÊU CHU ÅÅN TỐÁI ƯU CỦÛA BÀØI TOÁÙN VẬÄN TẢÛI 1 1 0; 0; 0; 0;ij ij i j m n i j i j x c a b a b Viếát lạïi bàøi toáùn 1 1 min m n ij ij i j Z c x 1 1 , 1, , 1, m ij j i n ij i j x b j n x a i m 1 1 0; 0; 0; 0;ij ij i j m n i j i j x c a b a b ÝØJLỊÙ íỉ ÞßH× ÌĐßGỊ Êß\Ị ÌßE× ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ̸­ị Ị¹«§»=² ݱ>²¹ Ì®3 ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ¸¬¬°ỉđđ²½¬®·ị½±ị½½ N uy ễn C ôn g T rí PDF created with pdfFactory Pro trial version www.pdffactory.com Bàøi toáùn đốái ngẫu cuã ûûa BTVT Tìm {ui,vj} sao cho: Vớùi cáùc cặëp đốái ngẫu:ã xij 0 vàø vj – ui cij, i,j Theo định lýù độä lệäch bùø thì phương áùn {xij} củûa BTVT cóù P.A.T.Ư làø tồàn tạïi hệä thốáng {ui, vj} sao cho: Nếáu xij > 0 thì vj – ui = cij, Nếáu vj – ui < cij thì xij = 0. Vậäy tiêu chuâ åån tốái ưu củûa BTVT: vj – ui cij, i,j ui: đượïc gọïi làø thếá vị dòøng. vj: đượïc gọïi làø thếá vị cộät. * 1 1 max n m j j i i j i Z b v a u TIÊU CHU ÅÅN TỐÁI ƯU CỦÛA BÀØI TOÁÙN VẬÄN TẢÛI Trên bâ ûûng vậän tảûi, chọïn ô â đầàu tiên cô ùù cướùc phí vậän chuyểån béù nhấát vàø chọïn xij như sau: Lặëp lạïi quáù trình trên cho ô tiê â ááp theo cho đếán đếán khi yêu câ ààu trạïm pháùt vàø trạïm thu đượïc thoảû mãn.õ Bảûng thu đượïc vớùi cáùc xij > 0 làø phương áùn cựïc biên cuâ ûûa bàøi toáùn. PHƯƠNG PHÁÙP CHI PHÍ BÉÙ NHẤÁT in ,m j i i j i j b a a b a b i j j i i j ij a : loại dòng i, b b : loại cột j, a a b : loại dòng i và cột j x Ví dụï 3.2. Dùøng phương pháùp chi phí béù nhấát, tìm phương áùn cựïc biên cuâ ûûa bàøi toáùn vậän tảûi cóù dạïng bảûng sau đâyâ Kiểåm tra ai = bj = 175 PHƯƠNG PHÁÙP CHI PHÍ BÉÙ NHẤÁT 101443660 167351645 115101528 132781342 4535254030T P 28 35 25 1230 18 7 20 PHƯƠNG PHÁÙP CHI PHÍ BÉÙ NHẤÁT P.A.C.B trên không suy biê â áán, vớùi giáù trị Z = 980. 101443660 167351645 115101528 132781342 4535254030T P Phương pháùp Vogels (1958) cho P.A.C.B kháù tốát theo nghĩa giáù trị hàøm mụïc tiêu cuâ ûûa nóù kháù gầàn vớùi P.A.T.Ư. Phương pháùp đượïc mô tâ ûû như sau (1) Trên bâ ûûng vậän tảûi, tính hiệäu sốá giữa chi phõ í béù thứù hai vớùi chi phí béù thứù nhấát. (2) Chọïn sốá lớùn nhấát trong cáùc hiệäu trên vâ øø phânâ phốái tốái đa cho ô cô ùù chi phí béù nhấát mộät lượïng xij = min(ai, bj), sau đóù tính lạïi hiệäu sốá dòøng (cộät). (3) Quáù trình trên â đượïc lặëp lạïi cho đếán khi chỉ còøn lạïi mộät dòøng hay mộät cộät duy nhấát. (4) Bảûng thu đượïc vớùi cáùc {xij} làø phương áùn cựïc biên cuâ ûûa bàøi toáùn. PHƯƠNG PHÁÙP VOGELS Ví dụï 3.3: Dùøng phương pháùp Vogels, tìm phương áùn cựïc biên cuâ ûûa bàøi toáùn vậän tảûi cóù dạïng bảûng sau Kiểåm tra ai = bj = 175 PHƯƠNG PHÁÙP VOGELS 101443660 167351645 115101528 132781342 4535254030T P ÝØJLỊÙ íỉ ÞßH× ÌĐßGỊ Êß\Ị ÌßE× ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ̸­ị Ị¹«§»=² ݱ>²¹ Ì®3 ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ¸¬¬°ỉđđ²½¬®·ị½±ị½½ Ng uy ễn C ôn g T rí PDF created with pdfFactory Pro trial version www.pdffactory.com 5 35 4 2 1 1 2 1 3 1 K ,1 28 K 7 3 30 K 30 K 3 4 25 K ,11 ,5 12 K 8 K 7 K K PHƯƠNG PHÁÙP VOGELS Z = 932 101443660 167351645 115101528 132781342 4535254030T P (1) Tìm P.A.C.B không suy biê áán đầàu tiên bâ èèng phương pháùp chi phí béù nhấát hoặëc Vogels. (2) Dùøng tiêu chuâ åån tốái ưu vi – uj cij, i,j đểå kiểåm tra P.A.C.B vừøa tìm đượïc. (3) Nếáu P.A.C.B thoảû mãn tiêu chuã â åån tốái ưu thì P.A.C.B đóù làø P.A.T.Ư. (4) Nếáu P.A.C.B vừøa tìm chưa thoảû mãn tiêu õ â chuẩån tốái ưu thì tìm cáùch sửûa đổåi P.A.C.B cũ õ đểå cóù P.A.C.B mớùi. (5) trởû vềà bướùc (2), sau mộät sốá bướùc lặëp hữu hã ïïn, ta sẽ cõ ùù P.A.T.Ư. Phương pháùp trên gô ïïi làø thuậät toáùn thếá vị HƯỚÙNG GIẢÛI BÀØI TOÁÙN khôngâ Cóù khôngâ Suy biếán? XÁÙC ĐỊNH P.A.C.B ĐẦÀU TIÊN (phương pháùp chi phí béù nhấát hoặëc Vogels) Chọïn ô vâ øøo: Max ij Xáùc định vòøng điềàu chỉnh vàø đáùnh dấáu (+); dấáu (–). q = min{xij/ (i, j) dấáu (–)} Cóù Thêm ô xâ â ij=0 Kếát thúùc thuậät giảûi Bàøi toáùn cóù P.A.T.Ư LẬÄP BẢÛNG VẬÄN TẢÛI Tính: Vj = Ui + Cij Ui = Vj – Cij Xáùc định P.A mớùi ij 0? ij ij ij x q dấu ( ). x q dấu ( ). x không dấu. ijx SƠ ĐỒÀ THUẬÄT GIẢÛI THẾÁ VỊ CỦÛA BÀØI TOÁÙN VẬÄN TẢÛI SỐÁ BƯỚÙC LẶËP LÀØ HỮU Hà ÏÏN Bướùc 1. Lậäp bảûng vậän tảûi (1) Kiểåm tra điềàu kiệän cân bâ èèng thu – pháùt. (2) Xáùc định P.A.C.B (bằèng phương pháùp chi phí béù nhấát). (3) Kiểåm tra P.A.C.B cóù suy biếán hay khôngâ Nếáu P.A.C.B. suy biếán: thêm vâ øøo ô (i,j) bâ áát kỳø vớùi xij = 0, không tâ ïïo thàønh chu trình. Nếáu P.A.C.B không suy biê áán, chuyểån sang [2] Bướùc 2. Kiểåm tra tính tốái ưu củûa bàøi toáùn (1) Tính vj = ui + cij ui = vj – cij, trong đóù ô (i,j) lâ øø ô chô ïïn. THUẬÄT TOÁÙN THẾÁ VỊ Chọïn ui = 0 tạïi dòøng bấát kỳø. (2) Đặët ij = vj – ui – cij Nếáu ij 0: ta cóù P.A.T.Ư. Nếáu ij > 0: chuyểån sang [3] Bướùc 3. Xáùc định vòøng điềàu chỉnh (1) Chọïn ô vâ øøo: Max ij ( ij > 0) (2) Chọïn ô râ xáùc định vòøng điềàu chỉnh ô vâ øøo sẽ õ đượïc đáùnh dấáu (+). Xen kẻû dấáu (-) vàø dấáu (+) trên vô øøng điềàu chỉnh. lượïng điềàu chỉnh q = min{xij/ (i,j) cóù dấáu (-)} THUẬÄT TOÁÙN THẾÁ VỊ Bướùc 4. Xáùc định P.A.C.B mớùi Quay vềà bướùc [2]. Sau mộät sốá bướùc lặëp hữu hã ïïn, bàøi toáùn cóù phương áùn tốái ưu. THUẬÄT TOÁÙN THẾÁ VỊ ijx ij ij ij x q dấu ( ); x q dấu ( ); x không dấu. ÝØJLỊÙ íỉ ÞßH× ÌĐßGỊ Êß\Ị ÌßE× ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ̸­ị Ị¹«§»=² ݱ>²¹ Ì®3 ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ¸¬¬°ỉđđ²½¬®·ị½±ị½½ Ng uy ễn C ô g T rí PDF created with pdfFactory Pro trial version www.pdffactory.com CHÚÙ ÝÙ. (1) Trong thuậät giảûi bàøi toáùn vậän tảûi, nếáu Max ij đạït tạïi nhiềàu ô, ta chô ïïn mộät ô tuâ øøy ýù trong sốá cáùc ôâ đóù làøm ô â điềàu chỉnh. (2) Trong P.A.T.Ư tìm đượïc Xopt, nếáu cóù ij = 0, màø (i,j) làø ô loâ ïïi thì đóù làø dấáu hiệäu bàøi toáùn cóù nhiềàu P.A.T.Ư kháùc. Đểå tìm P.A.C.B.T.Ư kháùc, ta chọïn ô â (i, j) đóù làøm ô â điềàu chỉnh, rồài áùp dụïng thuậät toáùn thếá vị đểå xáùc định P.A.C.B.T.Ư kháùc X/opt. (3) Tậäp phương áùn tốái ưu làø X = { Xopt + (1 – )X/opt, 0, 1 } THUẬÄT TOÁÙN THẾÁ VỊ Ví dụï 3.4. Giảûi bàøi toáùn vậän tảûi Kiểåm tra điềàu kiệän cân bâ èèng thu pháùt ai = 40 + 75 + 60 + 70 + 45 = 290 bj = 45 + 55 + 30 + 70 + 50 + 40 = 290 81010691145 26728970 17659360 9131110131275 6710981240 405070305545T P THUẬÄT TOÁÙN THẾÁ VỊ 40 30 20 40 1030 25 20 5025 0 78 1 3 -1 9 -2 10 7 8 +2 +1 +1 +5 +1 + -+ - + -+ - + - q= 20 Bảng 1 81010691145 26728970 17659360 9131110131275 6710981240 405070305545T P 10 30 705 2040 30 20 20 45 0 78 1 3 -1 4 -7 5 2 3 +2 +1 +1+ - + - + -+ - q= 5 Bảng 2 81010691145 26728970 17659360 9131110131275 6710981240 405070305545T P 5 35 5 70 45 15 30 15 25 45 0 62 2 1 4 -1 7 -6 5 -2 Bảng 3 81010691145 26728970 17659360 9131110131275 6710981240 405070305545T P •Do cáùc ij 0 i,j nên â P.A.T.Ư củûa bàøi toáùn làø Vàø Zmin = 1.875 đơn vị tiềàn tệä. Ngoàøi ra, bàøi toáùn không cô ùù P.A.T.Ư kháùc vì không cô ùù ij = 0, vớùi (i, j) làø ô loâ ïïi 0 5 0 0 35 0 0 5 0 70 0 0 45 0 0 0 0 15 0 0 30 0 15 25 0 45 0 0 0 0 optx THUẬÄT TOÁÙN THẾÁ VỊ ÝØJLỊÙ íỉ ÞßH× ÌĐßGỊ Êß\Ị ÌßE× ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ̸­ị Ị¹«§»=² ݱ>²¹ Ì®3 ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ¸¬¬°ỉđđ²½¬®·ị½±ị½½ Ng uy ễn C ôn g T rí PDF created with pdfFactory Pro trial version www.pdffactory.com Ví dụï 3.5. Giảûi bàøi toáùn vậän tảûi Kiểåm tra điềàu kiệän cân bâ èèng thu pháùt ai = 79 + 102 + 70 + 60 = 311 bj = 76 + 62 + 88 + 45 + 40 = 311 91018181260 3510171270 4781113102 7615191079 4045886276T P THUẬÄT TOÁÙN THẾÁ VỊ + -+ -+ - + - q=30 Bảûng 1 4030 15 88 64 14 12 48 0 10 6 -2 16 5 13 1 4 +2 910181812 60 35101712 70 4781113 102 76151910 79 4045886276T P Bảûng 2 4030 45 58 34 44 42 18 0 10 6 -2 16 5 13 3 6 910181812 60 35101712 70 4781113 102 76151910 79 4045886276T P •Do cáùc ij 0 i,j nên â P.A.T.Ư củûa bàøi toáùn vậän tảûi Vàø Zmin = 2.806 đơn vị tiềàn tệä. Bàøi toáùn không cô ùù P.A.T.Ư nàøo kháùc vì không â cóù ij = 0, vớùi (i, j) làø ô loâ ïïi. 34 0 0 45 0 0 44 58 0 0 0 0 30 0 40 42 18 0 0 0 optx THUẬÄT GIẢÛI THẾÁ VỊ CÁÙC DẠÏNG KHÁÙC CỦÛA BÀØI TOÁÙN VẬÄN TẢÛI 1. BÀØI TOÁÙN VẬÄN TẢÛI KHÔNG CÂN B  ÈÈNG THU – PHÁÙT (Xem) 2. BÀØI TOÁÙN VẬÄN TẢÛI CÓÙ DẠÏNG HÀØM MỤÏC TIÊU L ØØ MAX (Xem) 3. BÀØI TOÁÙN VẬÄN TẢÛI CÓÙ Ô C ÁÁM (Xem) 4. BÀØI TOÁÙN VẬÄN TẢÛI XE KHÔNG  (Xem) 1. TRƯỜØNG HỢÏP 1. ai > bj Thêm trâ ïïm thu giảû thứù Bn+1 Vớùi nhu cầàu thu bn+1 = ai – bj Cướùc phí vậän tảûi ci,n+1 = 0, i = 1, 2, ..., m. 2. TRƯỜØNG HỢÏP 2. ai < bj Thêm trâ ïïm pháùt giảû thứù Am+1 Vớùi nhu cầàu pháùt am+1 = bj – ai Cướùc phí vậän tảûi cm+1,j = 0, j = 1, 2, ..., n. Vớùi cáùc ô cô ùù cướùc phí vậän tảûi bằèng không â đượïc gọïi làø ô giâ ûû. Lưu ýù khi dùøng thuậät toáùn thếá vị đểå giảûi bàøi toáùn trên, vơâ ùùi P.A.C.B đầàu tiên, ta â ưu tiên phân phô â áái vàøo cáùc ô thâ ựïc. BÀØI TOÁÙN VẬÄN TẢÛI KHÔNG CÂN B  ÈÈNG THU-PHÁÙT ÝØJLỊÙ íỉ ÞßH× ÌĐßGỊ Êß\Ị ÌßE× ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ̸­ị Ị¹«§»=² ݱ>²¹ Ì®3 ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ¸¬¬°ỉđđ²½¬®·ị½±ị½½ gu ye ãn C ô g T rí PDF created with pdfFactory Pro trial version www.pdffactory.com Ví dụï 3.6. Giảûi bàøi toáùn vậän tảûi sau Kiểåm tra điềàu kiệän cân bâ èèng thu – pháùt ai= 165 < bj= 190 Thêm mô äät trạïm pháùt giảû A4, vớùi a4 = 190 – 165 = 25 vàø c4j = 0, j=1, 2, 3, 4 BÀØI TOÁÙN VẬÄN TẢÛI KHÔNG CÂN B  ÈÈNG THU-PHÁÙT 12147850 151011955 71291060 30504565T P 000025 12147850 151011955 712910 60 30504565T P + -+ - 5 25 30 55 5 45 25 0 1 2 12 10 9 12 7 +1 q = 25 Bảûng 1 + - + - q = 30 Cóù P.A.T.Ư kháùc Bảûng 2 30 25 30 30 5 45 25 0 1 2 11 10 9 11 7 0 000025 12147850 151011955 71291060 30504565T P •Phương áùn cựïc biên tô áái ưu củûa bàøi toáùn vậän tảûi làø •vàø Zmin = 1.385 30 0 0 30 30 0 25 0 5 45 0 0 optx BÀØI TOÁÙN VẬÄN TẢÛI KHÔNG CÂN B  ÈÈNG THU-PHÁÙT 000025 12147850 151011955 71291060 30504565T P 30 25 30 30 35 15 25 0 1 2 11 10 9 11 7 •P.A.C.B.T.Ư kháùc củûa bàøi toáùn •Vàø Z’min =1.385 •Tậäp P.A.T.Ư củûa bàøi toáùn •Zopt = Xopt + (1 – ) X/opt •Hay 0 30 0 30 30 0 25 0 35 15 0 0 optx BÀØI TOÁÙN VẬÄN TẢÛI KHÔNG CÂN B  ÈÈNG THU-PHÁÙT 30 30 30 0 30 30 0 25 0 35 30 15 30 0 0 optZ ÝØJLỊÙ íỉ ÞßH× ÌĐßGỊ Êß\Ị ÌßE× ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ̸­ị Ị¹«§»=² ݱ>²¹ Ì®3 ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ¸¬¬°ỉđđ²½¬®·ị½±ị½½ Ng uy ễn C ôn g T rí PDF created with pdfFactory Pro trial version www.pdffactory.com Tìm {xij} sao cho: MÔ HÌNH B ØØI TOÁÙN VẬÄN TẢÛI CÓÙ HÀØM MỤÏC TIÊU L ØØ MAX 1 1 1 1 1 1 max , 1, , 1, 0; 0; 0; 0; 1, ; 1, . m n ij ij i j n ij i j m ij j i m n ij ij i j i j i j Z c x x a i m x b j n x c a b a b i m j n Giốáng như bàøi toáùn QHTT cóù hàøm mụïc tiêu lâ øø max, chúùng ta cóù thểå đưa bàøi toáùn vậän tảûi cóù hàøm mụïc tiêu Z â max vềà Z/ = – Z min, sau đóù dùøng thuậät toáùn thếá vị đểå giảûi. Tuy nhiên, chuâ ùùng ta cũng cõ ùù thểå giảûi trựïc tiếáp bàøi toáùn nàøy bằèng thuậät toáùn thếá vị vớùi mộät vàøi thay đổåi trong thuậät giảûi như sau: 1. Khi xây dâ ựïng P.A.C.B đầàu tiên, ta phân phô â áái tốái đa vàøo ô cô ùù cướùc phí lớùn nhấát. 2.Tiêu chuâ åån tốái ưu làø vj – ui cij, i,j 3.Ô điềàu chỉnh làø ô cô ùù {min ij, vớùi ij < 0} THUẬÄT GIẢÛI BÀØI TOÁÙN VẬÄN TẢÛI CÓÙ HÀØM MỤÏC TIÊU L ØØ MAX Ví dụï 3.7. Mộät công ty cô ùù 3 xí nghiệäp cùøng sảûn xuấát mộät loạïi bóùng đèøn. Năng suă áát trong tháùng củûa 3 xí nghiệäp lầàn lượït làø Ai = (650, 1.000, 350) bóùng. Hợïp đồàng công ty phâ ûûi giao cho 4 nhàø phân phô áái làø Bj = (200, 400, 600, 800) bóùng. Đơn giáù báùn củûa mỗi bỗ ùùng đèøn tương ứùng vớùi cáùc nhàø phân phô áái đượïc cho bởûi ma trậän sau: Đvt: 1.000 đồàng Hãy tõ ìm kếá hoạïch phân phô áái hàøng sao cho công â ty đạït doanh sốá lớùn nhấát THUẬÄT GIẢÛI THẾÁ VỊ VỚÙI HÀØM MỤÏC TIÊU Z  Max 22 25 20 18 30 32 25 28 29 28 25 23 ijc 23252829 350 28253230 1000 18202522 650 800600400200T P THUẬÄT GIẢÛI THẾÁ VỊ VỚÙI HÀØM MỤÏC TIÊU Z  Max 250 200 400 400 400 350 0 283230 5 30 10 -2 -3 -4 -1+ – + – +– q = 200 23252829 350 28253230 1000 18202522 650 800600400200T P THUẬÄT GIẢÛI THẾÁ VỊ VỚÙI HÀØM MỤÏC TIÊU Z  Max 450 200 400 600 200 150 0 283234 5 30 10 -3 -1 + – +– q = 200 23252829 350 28253230 1000 18202522 650 800600400200T P THUẬÄT GIẢÛI THẾÁ VỊ VỚÙI HÀØM MỤÏC TIÊU Z  Max 450 200 200 800 200 150 0 283231 2 27 7 Z = 52.350 ÝØJLỊÙ íỉ ÞßH× ÌĐßGỊ Êß\Ị ÌßE× ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ̸­ị Ị¹«§»=² ݱ>²¹ Ì®3 ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ¸¬¬°ỉđđ²½¬®·ị½±ị½½ Ng uy ễn C ôn g T rí PDF created with pdfFactory Pro trial version www.pdffactory.com •Do cáùc ij 0, i, j •P.A.T.Ư CỦÛA BÀØI TOÁÙN •Vàø ZMax = 52.350 0 200 450 0 0 200 0 800 200 0 150 0 optx THUẬÄT GIẢÛI BÀØI TOÁÙN VẬÄN TẢÛI CÓÙ HÀØM MỤÏC TIÊU L ØØ MAX Bàøi toáùn vậän tảûi cóù ô câ áám làø bàøi toáùn vậän tảûi vớùi P.A.T.Ư củûa nóù phảûi thỏûa điềàu kiệän cho trướùc. Đểå giảûi bàøi toáùn nàøy, ta lậäp bàøi toáùn vậän tảûi mởû rộäng VTM bằèng cáùch cho giáù cướùc vậän chuyểån ởû cáùc ô câ áám bằèng M, vớùi M > 0 lớùn tùøy ýù rồài dùøng thuậät toáùn thếá vị. Cóù 2 trườøng hợïp xảûy ra 1.Trong P.A.T.Ư củûa bàøi toáùn VTM, nếáu cáùc ô câ áám cóù xij = 0 thì P.A.T.Ư củûa bàøi toáùn VTM cũng chõ ính làø P.A.T.Ư củûa bàøi toáùn gốác. 2.Trong P.A.T.Ư củûa bàøi toáùn VTM, nếáu cáùc ô câ áám cóù xij 0 thì bàøi toáùn gốác không cô ùù P.A.T.Ư. BÀØI TOÁÙN VẬÄN TẢÛI CÓÙ Ô C ÁÁM Ví dụï 3.8. Giảûi bàøi toáùn vậän tảûi sau đây vơâ ùùi Nhu cầàu trạïm pháùt a = (150, 100, 145, 100) Nhu cầàu trạïm thu b = (140, 150, 180) Ma trậän cướùc vậän chuyểån vớùi điềàu kiệän trạïm A3, A4 phảûi pháùt hếát hàøng. Kiểåm tra điềàu kiệän cân bâ èèng thu – pháùt ai = 150 + 100 + 145 + 100 = 495 bj = 140 + 150 + 180 = 470 Lậäp trạïm thu giảû, vớùi b4= 25 vàø M > 0 tùøy ýù. BÀØI TOÁÙN VẬÄN TẢÛI CÓÙ Ô C ÁÁM 5 4 6 8 5 9 11 6 12 9 7 13 ijc M1379 100 M12611 145 0958 100 0645 150 25180150140T P + –+ – 0 150 100 145 40 35 25 +3 M-4 +2 +3 M-1 +1 +1 4 1 1 0 9 8 13 M q = 25 Bảûng 1 M1379 100 M12611 145 0958 100 0645 150 25180150140T P + + – – +3 +2 +3 +1 +1 q = 35 Bảûng 2 0 150 75 25 145 65 35 4 1 1 0 9 8 13 1 M1379 100 M12611 145 0958 100 0645 150 25180150140T P + – +– + – +2 +4 +1 q = 40 Bảûng 3 0 150 40 25 145 100 35 3 0 -3 -1 8 7 9 0 ÝØJLỊÙ íỉ ÞßH× ÌĐßGỊ Êß\Ị ÌßE× ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ̸­ị Ị¹«§»=² ݱ>²¹ Ì®3 ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ¸¬¬°ỉđđ²½¬®·ị½±ị½½ Ng uy ễn C ôn g rí PDF created with pdfFactory Pro trial version www.pdffactory.com M1379 100 M12611 145 0958 100 0645 150 25180150140T P – + + – +4 +1 +1 +1 q =105 Bảûng 4 40 110 40 25 105 100 75 0 1 -2 -4 5 4 10 1 M1379 100 M12611 145 0958 100 0645 150 25180150140T P +2 +1 + – + – q = 5 Bảûng 5 40 5 145 25 100 75 105 0 -3 -2 -4 5 4 6 -3 M1379 100 M12611 145 0958 100 0645 150 25180150140T P Bảûng 6 40 5 145 25 100 70 110 3 0 -1 -1 8 5 9 0 Z =3.285 0+ – + – q = 40P.A.T.Ư kháùc •Do cáùc ij 0 i,j nên ⠕P.A.C.B.T.Ư củûa bàøi toáùn vậän tảûi trên lâ øø •vàø Zmin= 3.285 40 0 110 0 5 70 0 145 0 100 0 0 optx BÀØI TOÁÙN VẬÄN TẢÛI CÓÙ Ô C ÁÁM M1379 100 M12611 145 0958 100 0645 150 25180150140T P Bảûng 7 40 5 145 25 100 30 150 3 0 -1 -1 8 5 9 0 Z =3.285 0 •P.A.C.B.T.Ư kháùc củûa bàøi toáùn vậän tảûi trên lâ øø •vàø Zmin= 3.285 •Tậäp phương áùn tốái ưu •Zopt = Xopt + (1 – ) X/opt •Hay 0 0 150 40 5 30 0 145 0 100 0 0 op tx BÀØI TOÁÙN VẬÄN TẢÛI CÓÙ Ô C ÁÁM 40 0 150 40 40 4 0 5 30 40 0 145 0 100 0 0 optZ ÝØJLỊÙ íỉ ÞßH× ÌĐßGỊ Êß\Ị ÌßE× ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ̸­ị Ị¹«§»=² ݱ>²¹ Ì®3 ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ¸¬¬°ỉđđ²½¬®·ị½±ị½½ Ng uy ễn C ôn g T rí PDF created with pdfFactory Pro trial version www.pdffactory.com Điềàu kiệän ràøng buộäc củûa bàøi toáùn vậän tảûi xe không lâ øø mộät sốá trạïm pháùt Ai phảûi pháùt đủû hàøng cho trạïm Bj (đượïc chỉ định). Xáùc định lộä trình xe chạïy không tâ ûûi từø Bj đếán Ai làø ít nhấát. Khi đóù trạïm pháùt Ai trởû thàønh trạïm thu xe không, trâ ïïm thu Bj trởû thàønh trạïm pháùt xe không â vàø khi đóù ma trậän (cij) làø ma trậän khoảûng cáùch tương ứùng giữa Aõ i vàø Bj. Qui ướùc sửû dụïng cáùc kýù hiệäu như sau: : lượïng hàøng hóùa cóù vậän tảûi. : lượïng hàøng củûa xe không tâ ûûi. : tuyếán xe chạïy cóù tảûi. : tuyếán xe chạïy không tâ ûûi MÔ HÌNH B ØØI TOÁÙN VẬÄN TẢÛI XE KHÔNG ijx xij THUẬÄT GIẢÛI BÀØI TOÁÙN XE KHÔNG T ÛÛI 1. Lậäp bảûng vậän tảûi tương ứùng vớùi ma trậän khoảûng cáùch. Dùøng thuậät toáùn thếá vị tìm P.A.T.Ư củûa bàøi toáùn xe không tâ ûûi. 2. Tạïo bảûng phốái hợïp P.A.T.Ư củûa bàøi toáùn xe không tâ ûûi vớùi kếá hoạïch vậän tảûi đã cho trõ ướùc. Lậäp tuyếán điềàu độäng tương ứùng. 3. Giảûm lượïng chênh lê ääch giữ㠓ô trô øøn” vàø “ô â vuông⠔ đểå cóù bảûng mớùi thu gọïn. 4. Lậäp vòøng điềàu độäng gồàm cáùc ô cô ùù tảûi vàø ô â không tâ ûûi liên tiê ááp nhau, lượïng điềàu độäng q= min{xij}, vớùi xij cóù tảûi vàø xij không tâ ûûi. Trởû vềà [3]. Sau mộät sốá bướùc lặëp hữu hã ïïn [3] vàø [4], ta sẽ thu õ đượïc kếá hoạïch điềàu độäng hàøng hóùa tốái ưu. Ví dụï 3.9. Mộät công ty vâ ään tảûi cóù kếá hoạïch vậän chuyểån hàøng hóùa theo hợïp đồàng, đượïc thểå hiệän qua bảûng yêu câ ààu như sau THUẬÄT GIẢÛI BÀØI TOÁÙN XE KHÔNG T ÛÛI B2Công ty rau quâ ûû20 B4Cửûa hàøng sốá 450Sầàu riêngâA3 B3Cửûa hàøng sốá 310 B2Công ty rau quâ ûû15 B1Cửûa hàøng sốá 125 Dưa hấáuA2 B3Cửûa hàøng sốá 330 B2Công ty rau quâ ûû20CamA1 Kýù hiệäuNơi nhậän hàøng Bj Lượïng (tấán) Loạïi hàøng Địa điểåm cấáp hàøng Ai Cho biếát khoảûng cáùch giữã địa điểåm cung cấáp hàøng vàø địa điểåm nhậän hàøng (km) đượïc thểå hiệän qua ma trậän như sau: Hãy xã ùùc định lộä trình vậän chuyểån hàøng hóùa thỏûa yêu câ ààu hợïp đồàng vàø tổång tấán – km xe chạïy không tâ ûûi nhỏû nhấát. THUẬÄT GIẢÛI BÀØI TOÁÙN XE KHÔNG T ÛÛI 5243 4625 3412 L 5243 70 4625 50 3412 50 50405525Bj Ai Bướùc 1 (tìm P.A.T.Ư củûa bàøi toáùn xe không tâ ûûi) Zmin= 420 tấán – km 50 5 40 2 1 0 3 3 2 5 Bảûng 1 45 25 5 Bướùc 2 (tạïo bảûng phốái hợïp) A1 B2 A1: 20 T X 1km = 20T – km A2 B2 A2: 5 T X 2km = 10T – km A3 B4 A3: 5 T X 5km = 25T – km 5243 70 4625 50 3412 50 50405525Bj Ai 50 5 40 Bảûng 2 45 25 5 20 30 25 15 10 5020 1km 2km 5km ÝØJLỊÙ íỉ ÞßH× ÌĐßGỊ Êß\Ị ÌßE× ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ̸­ị Ị¹«§»=² ݱ>²¹ Ì®3 ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ¸¬¬°ỉđđ²½¬®·ị½±ị½½ Ng uy ễn C ô g T rí PDF created with pdfFactory Pro trial version www.pdffactory.com Bướùc 3 (lậäp tuyếán điềàu độäng) A2 B1 A3 B2 A1 B3 A3 B4 A2:20Tx10km=200T-km 5243 70 4625 50 3412 50 50405525Bj Ai 30 40 Bảûng 3 45 25 30 25 10 10 4520 q=20 3km 1km 2km 4km Bướùc 3 (lậäp tuyếán điềàu độäng) A2 B1 A3 B4 A2: 5T x 7km = 35T–km. 5243 70 4625 50 3412 50 50405525Bj Ai 10 20 Bảûng 4 25 5 10 5 10 10 25 q=5 3km 4km Bướùc 3 (lậäp tuyếán điềàu độäng) A2 B2 A1 B3 A3 B4 A2: 10T x 7km = 70T–km 5243 70 4625 50 3412 50 50405525Bj Ai 10 20 Bảûng 5 20 10 10 10 20 q=101km 2km 4km Bướùc 3 (lậäp tuyếán điềàu độäng) A2 B3 A3 B4 A2 : 10 T x 6km = 60T–km 5243 70 4625 50 3412 50 50405525Bj Ai 10 Bảûng 6 10 10 10 q=10 2km 4km BẢÛNG ĐIỀÀU ĐỘÄNG XE A1 B2 A1: 20 T A2 B2 A2: 5 T A3 B4 A3: 5 T A2 B1 A3 B2 A1 B3 A3 B4 A2: 20 T A2 B1 A3 B4 A2: 5 T A2 B2 A1 B3 A3 B4 A2: 10 T A2 B3 A3 B4 A2: 10 T THUẬÄT GIẢÛI BÀØI TOÁÙN XE KHÔNG T ÛÛI 1km 2km 5km 3km 1km 2km 4km 3km 4km 1km 2km 4km 2km 4km Ths. Nguyễn Công Trã â í Copyright 2001 LẬÄP MÔ HÌNH CU ÛÛA BÀØI TOÁÙN VẬÄN TẢÛI [1] [2] TÌM PHƯƠNG ÁÙN CỰÏC BIÊN  ĐẦÀU TIÊN [3a] [3b] [3c*] [3d] [3e] GIẢÛI BÀØI TOÁÙN VẬÄN TẢÛI CÂN B ÈÈNG THU - PHÁÙT [4] [5] [6] [7] [8] [9] CÁÙC DẠÏNG KHÁÙC CỦÛA BÀØI TOÁÙN VẬÄN TẢÛI [10a] [10b] [10c] [11a] [11b] [11c] [11d] BÀØI TẬÄP CHƯƠNG 3 ÝØJLỊÙ íỉ ÞßH× ÌĐßGỊ Êß\Ị ÌßE× ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ̸­ị Ị¹«§»=² ݱ>²¹ Ì®3 ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ¸¬¬°ỉđđ²½¬®·ị½±ị½½ Ng uy ễn C ôn g T rí PDF created with pdfFactory Pro trial version www.pdffactory.com BÀI TẬP CHƯƠNG 3 LẬP MÔ HÌNH CỦA BÀI TOÁN VẬN TẢI DƯỚI DẠNG BÀI TOÁN QHTT [1] Một công ty vận tải biển cần 110 người để bố trí vào các nhiệm vụ: 10 máy trưởng; 25 thợ máy 1; 30 thợ máy 2; 45 thợ máy 3. Phòng tổ chức nhân sự công ty tuyển được 90 người, trong đó gồm 25 kỹ sư máy; 20 kỹ thuật viên trung cấp và 45 công nhân có kinh nghiệm. Phòng tổ chức nhân sự đánh giá trình độ nhân sự tương ứng với từng công việc theo thang điểm 5, ví dụ aij = 5 nghĩa làvới trình độ i có khả năng hoàn thành xuất sắc công việc j (đạt điểm tối đa là 5), còn aij = 0 là với trình độ i không có khả năng hoàn thành công việc j (đạt điểm 0), được thể hiện chi tiết trong bảng sau Điểm đánh giá năng lực (aij)Nhiệm vụ Trình độ Máy trưởng Máy 1 Máy 2 Máy 3 Kỹ sư 5 4 0 0 Trung cấp 3 5 4 0 Công nhân 0 1 5 4 Hãy lập kế hoạch bố trí nhân lực sao cho công việc đạt tối ưu. [2] Hai đội tuyển bóng bàn, mỗi đội có 5 người. Qua thống kê nhiều trận đấu trong quá khứ, người ta dự đoán xác suất thắng cuộc mỗi đấu thủ của mỗi đội được thể hiện qua bảng sau Đội II Đội I Đấu thủ 1 Đấu thủ 2 Đấu thủ 3 Đấu thủ 4 Đấu thủ 5 Đấu thủ 1 0,4 0,5 0,6 0,7 0,8 Đấu thủ 2 0 0,3 0,4 0,4 0,7 Đấu thủ 3 0,2 0,6 0,4 0,3 0,5 Đấu thủ 4 0,6 0,3 0,4 0,7 0,6 Đấu thủ 5 0 0,2 0,3 0,4 0,6 Giả sử các đấu thủ của đội I được quyền chọn thi đấu với các tuyển thủ đội II. Hãy sắp xếp các đấu thủ của đội I sao cho xác suất thắng toàn đoàn của đội I cao nhất. TÌM PHƯƠNG ÁN CỰC BIÊN ĐẦU TIÊN [3] Tìm phương án cực biên đầu tiên bằng hai phương pháp chi phí bé nhất và phương pháp Vogels của các bài toán vận tải sau đây a) Bj Ai 20 25 30 15 b) Bj Ai 3 5 10 14 c)* Bj Ai 10 30 50 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 ÝØJLỊÙ íỉ ÞßH× ÌĐßGỊ Êß\Ị ÌßE× ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ̸­ị Ị¹«§»=² ݱ>²¹ Ì®3 ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ¸¬¬°ỉđđ²½¬®·ị½±ị½½ N uy ễn C ôn g T rí PDF created with pdfFactory Pro trial version www.pdffactory.com d) Bj Ai 40 30 20 50 e) Bj Ai 30 20 25 35 40 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 GIẢI BÀI TOÁN VẬN TẢI BẰNG THUẬT TOÁN THẾ VỊ [4] Giải bài tập [3], với phương án cực biên đầu tiên thu được bằng phương pháp chi phí bé nhất. Đs: a) và Z 0 0 30 10 0 20 0 0 20 5 0 5 optx min = 215; b) và Z 3 0 0 7 0 5 10 0 0 0 0 7 optx min = 57; c)* và Z = 245; d) và Z = 510; e) và Z = 800. 0 20 5 0 10 0 0 0 45 optx min 0 0 0 30 0 0 20 20 40 30 0 0 optx min 0 0 0 30 0 10 10 0 0 0 0 10 25 5 0 20 0 0 0 40 optx min [5] a) Giải bài toán vận tải Bj Ai 50 160 120 80 220 5 4 3 10 100 5 9 7 12 90 10 6 8 15 b) Bài toán có phương án tối ưu khác hay không? Đs: a) và z 0 70 120 30 50 0 0 50 0 90 0 0 optx min = 2330; b) không có PATU khác. [6] a) Giải bài toán vận tải Bj Ai 20 100 45 15 90 10 6 4 1 40 3 4 2 5 50 9 4 3 7 b) Bài toán có P.A.T.Ư khác hay không? Nếu có, hãy chỉ ra tập phương án tối ưu. ÝØJLỊÙ íỉ ÞßH× ÌĐßGỊ Êß\Ị ÌßE× ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ̸­ị Ị¹«§»=² ݱ>²¹ Ì®3 ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ¸¬¬°ỉđđ²½¬®·ị½±ị½½ Ng uy ễn C ôn g T rí PDF created with pdfFactory Pro trial version www.pdffactory.com Đs: a) ; b) Z 0 50 25 15 20 0 20 0 0 50 0 0 optx 0 30 45 15 20 20 0 0 0 50 0 0 optx min= Z / min =715; . 0 30 20 45 20 15 20 20 20 20 0 , 0,1 0 50 0 0 optT [7] Cho bài toán vận tải có dạng sau đây: 12011020ia 5060304070jb 23412 54385 67524 ijc a) Tìm phương án tối ưu của bài toán trên. b) Theo anh (chị) dấu hiệu nào cho ta biết bài toán vận tải có nhiều phương án tối ưu? Phương án tối ưu tìm được ở câu a) có duy nhất không? Nếu có hãy chỉ ra phương án cực biên tối ưu khác. c) Tìm tập các phương án tối ưu và chỉ ra 3 phương án tối ưu khác nhau. a) Đs: và z 0 20 0 0 0 0 0 30 60 20 70 20 0 0 30 optx min=690; b) Đs: 0 20 0 0 0 20 0 30 60 0 50 20 0 0 50 optx [8] Cho bài toán vận tải có dạng sau đây: 38, 45, 66, 45ia 52, 45, 38, 59jb 9 5 6 14 10 7 9 15 10 10 6 7 4 8 13 14 ijc a) Tìm phương án tối ưu của bài toán trên. b) Phương án tối ưu vừa tìm được có duy nhất không? (có giải thích). Chỉ ra một phương án tối ưu khác? (nếu có). a) Đs: và Z 0 7 31 0 7 38 0 0 0 0 7 59 45 0 0 0 optx min = 1.192; b) P.A.T.Ư. trên duy nhất. [9] Giải bài tập [1], [2]. ÝØJLỊÙ íỉ ÞßH× ÌĐßGỊ Êß\Ị ÌßE× ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ̸­ị Ị¹«§»=² ݱ>²¹ Ì®3 ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ¸¬¬°ỉđđ²½¬®·ị½±ị½½ Ng uy ễn C âng Tr í PDF created with pdfFactory Pro trial version www.pdffactory.com CÁC DẠNG KHÁC CỦA BÀI TOÁN VẬN TẢI [10] Giải các bài toán vận tải sau đây và tìm phương án tối ưu khác (nếu có) a) Bj Ai 60 60 80 100 80 4 5 6 12 70 10 3 9 5 100 6 4 7 9 Đs: và Z 60 0 20 0 0 0 0 70 0 60 40 0 optx min = 1.230; P.A.T.Ư. trên duy nhất. b) Trạm phát: ; Trạm thu 100 20 30 50ia 70 60 25 50jb Ma trận cước phí vận tải 10 14 24 8 30 20 18 14 2 12 6 7 8 16 14 36 ijc Đs: Z 0 50 0 50 0 5 15 0 20 0 10 0 50 0 0 0 optx min = 1.970; và Z 0 55 0 45 0 0 15 5 20 0 10 0 50 0 0 0 optx / min = 1.970. c) Trạm phát: ; trạm thu :79, 50, 60, 50ia 46, 45, 76, 20, 52jb Ma trận cước phí vận tải 10 1 5 13 8 5 6 10 8 13 3 2 8 9 6 13 5 7 10 13 ijc Đs: Z 0 45 34 0 0 38 0 0 12 0 8 0 0 0 52 0 0 42 8 0 optx min = 1.211; P.A.T.Ư. trên duy nhất. [11] Giải các bài toán vận tải có ô cấm sau đây và tìm phương án tối ưu khác (nếu có) a) Trạm phát: ; trạm thu : 504090ia 4510020jb Ma trận cước phí vận tải 349 243 4610 ijc Điều kiện trạm A3 phải phát hết hàng. b) Trạm phát: ; trạm thu : 100 80 50ia 65 90 50 30jb ÝØJLỊÙ íỉ ÞßH× ÌĐßGỊ Êß\Ị ÌßE× ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ̸­ị Ị¹«§»=² ݱ>²¹ Ì®3 ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ¸¬¬°ỉđđ²½¬®·ị½±ị½½ Ng uy ễn C ôn g T rí PDF created with pdfFactory Pro trial version www.pdffactory.com Ma trận cước phí vận tải 10 9 12 7 9 11 10 15 8 7 14 12 ijc Điều kiện trạm B2 phải thu đủ hàng. c) Trạm phát: ; trạm thu : 90,100,220ia 80,120,160,50jb Ma trận cước phí vận tải 158610 12795 10345 ijc Điều kiện trạm phát A3 không được phát cho trạm thu B2. d) Trạm phát: ; trạm thu : 504090ia 4510020jb Ma trận cước phí vận tải 349 243 4610 ijc Điều kiện trạm thu B2 không được thu của trạm phát A1. ÝØJLỊÙ íỉ ÞßH× ÌĐßGỊ Êß\Ị ÌßE× ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ̸­ị Ị¹«§»=² ݱ>²¹ Ì®3 ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ¸¬¬°ỉđđ²½¬®·ị½±ị½½ Ng uy ễn C ôn g T rí PDF created with pdfFactory Pro trial version www.pdffactory.com