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

øø 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