Bài giảng Tối ưu hóa: Chương 3 - ThS. Nguyễn Công Trí

Chia sẻ: Sơn Tùng | Ngày: | Loại File: PDF | Số trang:24

Thêm vào BST

Báo xấu

98
lượt xem 10
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài giảng "Tối ưu hóa - Chương 3: Bài toán vận tải" cung cấp cho người học các kiến thức: 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,... Mời các bạn cùng tham khảo.

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 - ThS. Nguyễn Công Trí

ThS. Nguyễn Công Trí - Tối ưu hóa * Chương 3 BAØI TOAÙN VAÄN TAÛI CHÖÔNG 3 BAØI TOAÙN VAÄN TAÛI DAÏNG TOÅNG QUAÙT NOÄI DUNG BAØI TOAÙN VAÄN TAÛI Giaû söû caàn vaän chuyeån moät loaïi haøng hoùa (xi 1. BAØI TOAÙN VAÄN TAÛI DAÏNG TOÅNG QUAÙT (Xem) maêng, saét theùp, ...) töø m ñieåm cung caáp (traïm 2. CAÙC TÍNH CHAÁT VAØ TIEÂU CHUAÅN TOÁI ÖU CUÛA phaùt), kyù hieäu laø A1, A2, ..., Am ñeán n ñieåm tieâu Ths. BAØI TOAÙNguyeã N VAÄN TAÛI n Coâng Trí (Xem) thuï (traïm thu), kyù hieäu laø B1, B2, ..., Bn, bieát raèng (1) Soá löôïng haøng coù ôû caùc traïm phaùt A1, A2, ..., 3. CAÙC PHÖÔNG PHAÙP TÌM PHÖÔNG AÙN CÖÏC Am laàn löôït laø a1, a2,..., am (2) Soá löôïng haøng caàn ôû caùc traïm thu B1, B2, ..., Copyright 2001 BIEÂN ÑAÀU TIEÂN CUÛA BAØI TOAÙN VAÄN TAÛI (Xem) Bn laàn löôït laø b1, b2,..., bn. 4. THUAÄT GIAÛI THEÁ VÒ CHO BAØI TOAÙN VAÄN TAÛI (Xem) (3) Chi phí vaän chuyeån moät ñôn vò haøng hoùa töø traïm phaùt Ai ñeán traïm thu Bj laø cij. 5. CAÙC DAÏNG KHAÙC CUÛA BAØI TOAÙN VAÄN TAÛI (Xem) Haõy laäp keá hoaïch vaän taûi haøng hoùa sao cho Ths. Nguyeãn Coâng Trí toång chi phí vaän taûi thaáp nhaát vaø thoûa maõn yeâu 6. BAØI TAÄP Copyright 2001(Xem) caàu thu – phaùt. BAØI TOAÙN VAÄN TAÛI DAÏNG TOÅNG QUAÙT BAØI TOAÙN VAÄN TAÛI DAÏNG TOÅNG QUAÙT MOÂ HÌNH BAØI TOAÙN VAÄN TAÛI Vaäy, moâ hình toaùn cuûa baøi toaùn vaän taûi (BTVT) Ñaët xij laø soá löôïng haøng caàn vaän chuyeån töø traïm daïng toång quaùt nhö sau: phaùt Ai ñeán traïm thu Bj. Tìm {xij} sao cho: m n m n Ta coù toång chi phí vaän taûi: Z   cij xij  min Z   cij xij  min i 1 j 1 i 1 j 1 n n (1) Traïm phaùt, phaùt heát haøng: x j 1 ij  ai , i  1, m x ij  ai , i  1, m j 1 m m (2) Traïm thu, thu ñuû haøng: x i 1 ij  b j , j  1, n x ij  b j , j  1, n i 1 (3) Yeâu caàu traïm phaùt, traïm thu ñöôïc thoûa m n m n  ai   b j (ñk caân baèng thu – phaùt). xij  0; cij  0; ai  0; b j  0;  ai   b j i 1 j 1 i 1 j 1 1
ThS. Nguyễn Công Trí - Tối ưu hóa * Chương 3 BAØI TOAÙN VAÄN TAÛI DAÏNG TOÅNG QUAÙT BAØI TOAÙN VAÄN TAÛI DAÏNG TOÅNG QUAÙT BAØI TOAÙN VAÄN TAÛI DÖÔÙI DAÏNG BAØI TOAÙN QHTT BTVT vieát döôùi daïng vectô vaø ma traän nhö sau khai trieån BTVT vaø xeáp heä raøng buoäc döôùi daïng z  CT X  min heä m + n phöông trình cuûa m n bieán nhö sau  x11  x12    x1n  a1  AX  b *  x 21  x22    x2 n  a2  X 0 **     x m1  xm 2    x mn  am  Moät vectô X thoûa (*) vaø (**) goïi laø phöông aùn. x11  x 21   x m1  b1 Moät P.A ñaït cöïc tieåu thì goïi laø P.A.T.Ö cuûa BTVT. x12  x22  xm 2  b2 Moät phöông aùn X ñöôïc goïi laø P.A.C.B khi caùc    x1n  x2 n   x mn  bn vectô coät Aj cuûa ma traän heä soá A öùng vôùi caùc Kyù hieäu Am+n,mn ma traän heä soá cuûa hpt treân. thaønh phaàn xij > 0 laø ñoäc laäp tuyeán tính. XT = (x11 x12 ...…x1n x21 x22 ... x2n ... xm1 xm2…... xmn) laø  Moät P.A.C.B cuûa BTVT coù nhieàu nhaát laø m + n – vectô coät goàm mn thaønh phaàn; C = (c11 c12 1 thaønh phaàn döông. Neáu moät P.A.C.B cuûa BTVT ...…c1n c21 c22 ... c2n… cm1 cm2 ...…cmn) laø vectô doøng coù ñuùng m + n – 1 thaønh phaàn döông thì ñöôïc goàm mn thaønh phaàn; bT = (a1 a2 ...…am b1 b2 ...…bn) goïi laø khoâng suy bieán. Ngöôïc laïi, ñöôïc goïi laø laø vectô coät goàm m+ n thaønh phaàn. phöông aùn cöïc bieân suy bieán. MOÂ TAÛ BAØI TOAÙN DÖÔÙI DAÏNG BAÛNG VAÄN TAÛI MOÂ TAÛ BAØI TOAÙN DÖÔÙI DAÏNG BAÛNG VAÄN TAÛI Traïm thu Bj B1 B2  Bn (1) Kyù hieäu (i, j) laø oâ treân doøng i vaø coät j. b1 b2  bn (2) Chi phí vaän chuyeån cij ñöôïc ghi ôû goùc treân beân traùi cuûa oâ (i, j), löôïng haøng caàn vaän chuyeån Traïm phaùt Ai xij ñöôïc ghi ôû goùc döôùi beân phaûi cuûa oâ (i, j) bieåu A1 c11 c12  c1n dieãn tuyeán ñöôøng vaän chuyeån töø traïm phaùt Ai a1 x11 x12  x1 n ñeán traïm thu Bj. A2 c21 c22  c2n (3) Trong BAÛNG VAÄN TAÛI, moät oâ ñöôïc goïi laø oâ a2 x21 x22  x2 n treo neáu noù laø oâ duy nhaát treân doøng hay treân coät.      (4) Nhöõng oâ öùng vôùi xij > 0 trong BAÛNG VAÄN TAÛI      ñöôïc goïi laø oâ choïn, nhöõng oâ khaùc goïi laø oâ loaïi. Am cm1 cm 2  cmn (5) Moät daõy caùc oâ choïn, trong ñoù 3 oâ lieân tieáp am xm1 xm2  xmn khoâng naèm treân cuøng moät doøng hay moät coät thì ñöôïc goïi laø moät daây chuyeàn. 2
ThS. Nguyễn Công Trí - Tối ưu hóa * Chương 3 MOÂ TAÛ BAØI TOAÙN DÖÔÙI DAÏNG BAÛNG VAÄN TAÛI MOÂ TAÛ BAØI TOAÙN DÖÔÙI DAÏNG BAÛNG VAÄN TAÛI (6) Moät daây chuyeàn kheùp kín ñöôïc goïi laø moät VÍ DUÏ 3.1. chu trình hay moät voøng.           (7) Moät ma traän (xij) laø moät P.A cuûa BTVT neáu noù       thoaû heä raøng buoäc. Moät P.A (xij) laøm cöïc tieåu       haøm muïc tieâu thì (xij) laø P.A.T.Ö. cuûa baøi toaùn.       Hình 2.1. Hình 2.2. Hình 2.3. Hình 2.4. Hình 2.5. (8) Moät P.A cuûa BTVT khoâng taïo thaønh chu trình  Hình 2.1. caùc oâ choïn, coù daáu “”, taïo thaønh (voøng) thì ñöôïc goïi laø Phöông aùn cöïc bieân. daây chuyeàn, caùc oâ (1,1) vaø (4,3) laø caùc oâ treo. (9) Moät P.A.C.B cuûa BTVT coù ñuû m+n-1 oâ choïn thì  Hình 2.2. caùc oâ choïn taïo thaønh daây chuyeàn, ñöôïc goïi laø P.A.C.B khoâng suy bieán, neáu coù ít caùc oâ (4,1) vaø (3,3) laø caùc oâ treo. hôn m+n-1 oâ choïn ñöôïc goïi laø P.A.C.B suy bieán.  Hình 2.3., Hình 2.4 vaø Hình 2.5. caùc oâ choïn taïo thaønh chu trình, khoâng coù oâ treo. CAÙC TÍNH CHAÁT CUÛA BAØI TOAÙN VAÄN TAÛI TIEÂU CHUAÅN TOÁI ÖU CUÛA BAØI TOAÙN VAÄN TAÛI TÍNH CHAÁT 1: Baøi toaùn vaän taûi luoân luoân coù Xeùt baøi toaùn vaän taûi sau Vieát laïi baøi toaùn m n m n phöông aùn toái öu. Z   cij xij  min Z   cij xij  min TÍNH CHAÁT 2: Vôùi moät phöông aùn baát kyø, soá oâ n i 1 j 1 i 1 j 1 m choïn cuûa phöông aùn khoâng vöôït quaù toång soá traïm phaùt vaø traïm thu. x j 1 ij  ai , i  1, m x i 1 ij  b j , j  1, n  ≤ m + n –1 (vôùi  laø soá oâ choïn cuûa P.A) m n TÍNH CHAÁT 3: Vôùi moät phöông aùn coù ñuû m+n–1 oâ  xij  b j , j  1, n   xij   ai , i  1, m j 1 choïn thì vôùi moät oâ loaïi baát kyø ñöôïc ñöa vaøo i 1 phöông aùn seõ taïo thaønh chu trình vaø chu trình xij  0; cij  0; ai  0; b j  0; xij  0; cij  0; ai  0; b j  0; naøy laø duy nhaát. m n m n TÍNH CHAÁT 4: Neáu löôïng cung ai vaø löôïng caàu bj  ai   b j i 1 j 1  ai   b j i 1 j 1 laø soá nguyeân thì baøi toaùn coù lôøi giaûi nguyeân. 3
ThS. Nguyễn Công Trí - Tối ưu hóa * Chương 3 TIEÂU CHUAÅN TOÁI ÖU CUÛA BAØI TOAÙN VAÄN TAÛI PHÖÔNG PHAÙP CHI PHÍ BEÙ NHAÁT Baøi toaùn ñoái ngaãu cuûa BTVT Treân baûng vaän taûi, choïn oâ ñaàu tieân coù cöôùc phí n m Tìm {ui,vj} sao cho: Z *   b j v j   aiui  max vaän chuyeån beù nhaát vaø choïn xij nhö sau: j 1 i 1 Vôùi caùc caëp ñoái ngaãu: a i : loaïi doøng i, bj  b j  ai xij  0 vaø vj – ui ≤ cij, i,j  Theo ñònh lyù ñoä leäch buø thì phöông aùn {xij} cuûa x ij  min  ai , b j    b j : loaïi coät j, ai  ai  b j BTVT coù P.A.T.Ö laø toàn taïi heä thoáng {ui, vj} sao cho: a i  b j : loaïi doøng i vaø coät j Neáu xij > 0 thì vj – ui = cij, Laëp laïi quaù trình treân cho oâ tieáp theo cho ñeán Neáu vj – ui < cij thì xij = 0. ñeán khi yeâu caàu traïm phaùt vaø traïm thu ñöôïc Vaäy tieâu chuaån toái öu cuûa BTVT: vj – ui  cij, i,j thoaû maõn. ui: ñöôïc goïi laø theá vò doøng. Baûng thu ñöôïc vôùi caùc xij > 0 laø phöông aùn cöïc vj: ñöôïc goïi laø theá vò coät. bieân cuûa baøi toaùn. PHÖÔNG PHAÙP CHI PHÍ BEÙ NHAÁT PHÖÔNG PHAÙP CHI PHÍ BEÙ NHAÁT Ví duï 3.2. Duøng phöông phaùp chi phí beù T 30 40 25 35 45 P nhaát, tìm phöông aùn cöïc bieân cuûa baøi 42 13 8 7 2 13 toaùn vaän taûi coù daïng baûng sau ñaây 35 7 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 45 16 5 3 7 16 60 6 3 4 14 10 60 6 3 4 14 10 30 12 18 Kieåm tra ai = bj = 175 P.A.C.B treân khoâng suy bieán, vôùi giaù trò Z = 980. 4
ThS. Nguyễn Công Trí - Tối ưu hóa * Chương 3 PHÖÔNG PHAÙP VOGELS PHÖÔNG PHAÙP VOGELS Phöông phaùp Vogels (1958) cho P.A.C.B khaù toát Ví duï 3.3: Duøng phöông phaùp Vogels, tìm theo nghóa giaù trò haøm muïc tieâu cuûa noù khaù gaàn vôùi P.A.T.Ö. Phöông phaùp ñöôïc moâ taû nhö sau phöông aùn cöïc bieân cuûa baøi toaùn vaän taûi (1) Treân baûng vaän taûi, tính hieäu soá giöõa chi phí beù coù daïng baûng sau thöù hai vôùi chi phí beù thöù nhaát. T 30 40 25 35 45 (2) Choïn soá lôùn nhaát trong caùc hieäu treân vaø phaân P phoái toái ña cho oâ coù chi phí beù nhaát moät löôïng 42 13 8 7 2 13 xij = min(ai, bj), sau ñoù tính laïi hieäu soá doøng (coät). 28 5 1 10 5 11 (3) Quaù trình treân ñöôïc laëp laïi cho ñeán khi chæ coøn laïi moät doøng hay moät coät duy nhaát. 45 16 5 3 7 16 (4) Baûng thu ñöôïc vôùi caùc {xij} laø phöông aùn cöïc 60 6 3 4 14 10 bieân cuûa baøi toaùn. Kieåm tra ai = bj = 175 PHÖÔNG PHAÙP VOGELS HÖÔÙNG GIAÛI BAØI TOAÙN T 30 40 25 35 45 (1) Tìm P.A.C.B khoâng suy bieán ñaàu tieân baèng P phöông phaùp chi phí beù nhaát hoaëc Vogels. 42 13 8 7 2 13 5 ,1,5 K (2) Duøng tieâu chuaån toái öu vi – uj ≤ cij, i,j ñeå kieåm 35 7 tra P.A.C.B vöøa tìm ñöôïc. 28 5 1 10 5 11 4K (3) Neáu P.A.C.B thoaû maõn tieâu chuaån toái öu thì 28 P.A.C.B ñoù laø P.A.T.Ö. 45 16 5 3 7 16 2,11 K (4) Neáu P.A.C.B vöøa tìm chöa thoaû maõn tieâu 12 25 8 chuaån toái öu thì tìm caùch söûa ñoåi P.A.C.B cuõ ñeå 60 6 3 4 14 10 coù P.A.C.B môùi. 1K (5) trôû veà böôùc (2), sau moät soá böôùc laëp höõu haïn, 30 30 1 2 1 3 1 Z = 932 ta seõ coù P.A.T.Ö. 7 3 4 K 3 Phöông phaùp treân goïi laø thuaät toaùn theá vò K K K K 5
ThS. Nguyễn Công Trí - Tối ưu hóa * Chương 3 SÔ LAÄ ÑOÀP BAÛ NG VAÄ THUAÄ N TAÛ T GIAÛ I ITHEÁ VÒ THUAÄT TOAÙN THEÁ VÒ XAÙCUÛ A BAØ C ÑÒNH I TOAÙNÑAÀ P.A.C.B VAÄ N TAÛ U TIEÂ N I Böôùc 1. Laäp baûng vaän taûi (phöông phaùp chi phí beù nhaát hoaëc Vogels) (1) Kieåm tra ñieàu kieän caân baèng thu – phaùt. Suy bieán? Coù Theâm oâ x =0 ij (2) Xaùc ñònh P.A.C.B (baèng phöông phaùp chi phí khoâng beù nhaát). Tính: Vj = Ui + Cij (3) Kieåm tra P.A.C.B coù suy bieán hay khoâng Xaùc ñònh P.A môùi Ui = Vj – Cij  x ij  q daáu ( ).  Neáu P.A.C.B. suy bieán: theâm vaøo oâ (i,j) baát kyø  xij   x ij  q daáu (). ij  0? Coù vôùi xij = 0, khoâng taïo thaønh chu trình.  x khoâng daáu. Baøi toaùn coù P.A.T.Ö  ij khoâng  Neáu P.A.C.B khoâng suy bieán, chuyeån sang [2] Choïn oâ vaøo: Maxij Keát thuùc thuaät giaûi Böôùc 2. Kieåm tra tính toái öu cuûa baøi toaùn Xaùc ñònh voøng ñieàu chænh SOÁ BÖÔÙC LAËP (1) Tính vj = ui + cij vaø ñaùnh daáu (+); daáu (–). LAØ HÖÕU HAÏN q = min{xij/ (i, j) daáu (–)} ui = vj – cij, trong ñoù oâ (i,j) laø oâ choïn. THUAÄT TOAÙN THEÁ VÒ THUAÄT TOAÙN THEÁ VÒ Choïn ui = 0 taïi doøng baát kyø. Böôùc 4. Xaùc ñònh P.A.C.B môùi (2) Ñaët ij = vj – ui – cij  Neáu ij ≤ 0: ta coù P.A.T.Ö. x ij  q daáu ( );   Neáu ij > 0: chuyeån sang [3] xij  x ij  q daáu (); Böôùc 3. Xaùc ñònh voøng ñieàu chænh x khoâng daáu. (1) Choïn oâ vaøo: Maxij (ij > 0)  ij (2) Choïn oâ ra Quay veà böôùc [2].  xaùc ñònh voøng ñieàu chænh Sau moät soá böôùc laëp höõu haïn, baøi toaùn coù  oâ vaøo seõ ñöôïc ñaùnh daáu (+). Xen keû daáu phöông aùn toái öu. (-) vaø daáu (+) treân voøng ñieàu chænh.  löôïng ñieàu chænh q = min{xij/ (i,j) coù daáu (-)} 6
ThS. Nguyễn Công Trí - Tối ưu hóa * Chương 3 THUAÄT TOAÙN THEÁ VÒ THUAÄT TOAÙN THEÁ VÒ CHUÙ YÙ. Ví duï 3.4. Giaûi baøi toaùn vaän taûi (1) Trong thuaät giaûi baøi toaùn vaän taûi, neáu Maxij T 45 55 30 70 50 40 ñaït taïi nhieàu oâ, ta choïn moät oâ tuøy yù trong soá caùc P oâ ñoù laøm oâ ñieàu chænh. 40 12 8 9 10 7 6 (2) Trong P.A.T.Ö tìm ñöôïc Xopt, neáu coù ij = 0, maø 75 12 13 10 11 13 9 (i,j) laø oâ loaïi thì ñoù laø daáu hieäu baøi toaùn coù nhieàu 60 3 9 5 6 7 1 P.A.T.Ö khaùc. Ñeå tìm P.A.C.B.T.Ö khaùc, ta choïn oâ 70 9 8 2 7 6 2 (i, j) ñoù laøm oâ ñieàu chænh, roài aùp duïng thuaät toaùn 45 11 9 6 10 10 8 theá vò ñeå xaùc ñònh P.A.C.B.T.Ö khaùc X/opt. Kieåm tra ñieàu kieän caân baèng thu phaùt (3) Taäp phöông aùn toái öu laø ai = 40 + 75 + 60 + 70 + 45 = 290 X = {Xopt + (1 – )X/opt, 0, 1} bj = 45 + 55 + 30 + 70 + 50 + 40 = 290 Baûng 1 Baûng 2 T 45 55 30 70 50 40 T 45 55 30 70 50 40 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 - 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 9 8 2 7 6 2 70 1 70 1 30 +1 - 40 + +5 30 - 20 + 20 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 7
ThS. Nguyễn Công Trí - Tối ưu hóa * Chương 3 Baûng 3 T 45 55 30 70 50 40 THUAÄT TOAÙN THEÁ VÒ P •Do caùc ij  0 i,j neân P.A.T.Ö cuûa baøi toaùn laø 12 8 9 10 7 6 40 -1 5 35  0 5 0 0 35 0  12 13 10 11 13 9  0 5 0 70 0 0  75 -6   5 70 xopt   45 0 0 0 0 15  3 9 5 6 7 1  0 0 30 0 15 25  60 1 45 15   9 8 2 7 6 2  0 45 0 0 0 0  70 0   30 15 25 Vaø Zmin = 1.875 ñôn vò tieàn teä. 11 9 6 10 10 8 45 -2 Ngoaøi ra, baøi toaùn khoâng coù P.A.T.Ö khaùc vì 45 khoâng coù ij = 0, vôùi (i, j) laø oâ loaïi 4 7 2 5 6 2 THUAÄT TOAÙN THEÁ VÒ T 76 62 88 45 40 Baûng 1 Ví duï 3.5. Giaûi baøi toaùn vaän 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åm tra ñieàu kieän caân baèng thu phaùt 12 18 18 10 9 -2 ai = 79 + 102 + 70 + 60 = 311 60 + 12 - 48 bj = 76 + 62 + 88 + 45 + 40 = 311 q=30 10 16 13 6 4 8
ThS. Nguyễn Công Trí - Tối ưu hóa * Chương 3 T 76 62 88 45 40 Baûng 2 THUAÄT GIAÛI THEÁ VÒ P •Do caùc ij  0 i,j neân 10 19 15 6 7 0 P.A.T.Ö cuûa baøi toaùn vaän taûi 79 34 45  34 0 0 45 0  13 11 8 7 4 5  0 44 58 0 0  102 44 58 xopt   12 17 10 5 3 3  0 0 30 0 40  70  42 18 0 0 0  30 40   12 18 18 10 9 -2 Vaø Zmin = 2.806 ñôn vò tieàn teä. 60 42 18 Baøi toaùn khoâng coù P.A.T.Ö naøo khaùc vì khoâng 10 16 13 6 6 coù ij = 0, vôùi (i, j) laø oâ loaïi. CAÙC DAÏNG KHAÙC CUÛA BAØI TOAÙN VAÄN TAÛI BAØI TOAÙN VAÄN TAÛI KHOÂNG CAÂN BAÈNG THU-PHAÙT 1. TRÖÔØNG HÔÏP 1. ai > bj  Theâm traïm thu giaû thöù Bn+1 1. BAØI TOAÙN VAÄN TAÛI KHOÂNG CAÂN BAÈNG  Vôùi nhu caàu thu bn+1 = ai – bj THU – PHAÙT (Xem)  Cöôùc phí vaän taûi ci,n+1 = 0, i = 1, 2, ..., m. 2. TRÖÔØNG HÔÏP 2. ai < bj 2. BAØI TOAÙN VAÄN TAÛI COÙ DAÏNG HAØM MUÏC  Theâm traïm phaùt giaû thöù Am+1 TIEÂU LAØ MAX (Xem)  Vôùi nhu caàu phaùt am+1 = bj – ai 3. BAØI TOAÙN VAÄN TAÛI COÙ OÂ CAÁM (Xem)  Cöôùc phí vaän taûi cm+1,j = 0, j = 1, 2, ..., n. Vôùi caùc oâ coù cöôùc phí vaän taûi baèng khoâng 4. BAØI TOAÙN VAÄN TAÛI XE KHOÂNG (Xem) ñöôïc goïi laø oâ giaû. Löu yù khi duøng thuaät toaùn theá vò ñeå giaûi baøi toaùn treân, vôùi P.A.C.B ñaàu tieân, ta öu tieân phaân phoái vaøo caùc oâ thöïc. 9
ThS. Nguyễn Công Trí - Tối ưu hóa * Chương 3 BAØI TOAÙN VAÄN TAÛI KHOÂNG CAÂN BAÈNG THU-PHAÙT T 65 45 50 30 Baûng 1 Ví duï 3.6. Giaûi baøi toaùn vaän 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åm tra ñieàu kieän caân baèng thu – phaùt 5 45 ai= 165 < bj= 190 0 0 0 0 12 25 Theâm moät traïm phaùt giaû A4, vôùi 25 q = 25 a4 = 190 – 165 = 25 vaø c4j = 0, j=1, 2, 3, 4 10 9 12 7 T 65 45 50 30 Baûng 2 BAØI TOAÙN VAÄN TAÛI P KHOÂNG CAÂN BAÈNG THU-PHAÙT 10 9 12 7 0 60 •Phöông aùn cöïc bieân toái öu cuûa baøi toaùn - 30 + 0 30 vaän taûi laø 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 0 0  + 5 - 45   0 0 0 0 11 25 •vaø Zmin = 1.385 25 q = 30 10 9 11 7 Coù P.A.T.Ö khaùc 10
ThS. Nguyễn Công Trí - Tối ưu hóa * Chương 3 BAØI TOAÙN VAÄN TAÛI KHOÂNG CAÂN BAÈNG THU-PHAÙT T 65 45 50 30 P •P.A.C.B.T.Ö khaùc cuûa baøi toaùn 10 9 12 7 0  0 30 0 30  60 30 30    30 0 25 0  xopt   9 11 10 15 1  35 15 0 0  55 •Vaø Z min =1.385  ’  30 25 •Taäp P.A.T.Ö cuûa baøi 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    MOÂ HÌNH BAØI TOAÙN VAÄN TAÛI THUAÄT GIAÛI BAØI TOAÙN VAÄN TAÛI COÙ HAØM MUÏC TIEÂU LAØ MAX COÙ HAØM MUÏC TIEÂU LAØ MAX Gioáng nhö baøi toaùn QHTT coù haøm muïc tieâu laø Tìm {xij} sao cho: max, chuùng ta coù theå ñöa baøi toaùn vaän taûi coù m n Z   cij xij  max haøm muïc tieâu Z  max veà Z/ = – Z  min, sau ñoù i 1 j 1 duøng thuaät toaùn theá vò ñeå giaûi. Tuy nhieân, chuùng n ta cuõng coù theå giaûi tröïc tieáp baøi toaùn naøy baèng x j 1 ij  ai , i  1, m thuaät toaùn theá vò vôùi moät vaøi thay ñoåi trong thuaät m giaûi nhö sau: x i 1 ij  b j , j  1, n 1. Khi xaây döïng P.A.C.B ñaàu tieân, ta phaân phoái toái m n ña vaøo oâ coù cöôùc phí lôùn nhaát. xij  0; cij  0; ai  0; b j  0;  ai   b j i  1, m; j  1, n. 2.Tieâu chuaån toái öu laø vj – ui  cij, i,j i 1 j 1 3.OÂ ñieàu chænh laø oâ coù {minij, vôùi ij < 0} 11
ThS. Nguyễn Công Trí - Tối ưu hóa * Chương 3 THUAÄT GIAÛI THEÁ VÒ VÔÙI HAØM MUÏC TIEÂU Z  Max THUAÄT GIAÛI THEÁ VÒ VÔÙI HAØM MUÏC TIEÂU Z  Max Ví duï 3.7. Moät coâng ty coù 3 xí nghieäp cuøng saûn xuaát moät loaïi boùng ñeøn. Naêng suaát trong thaùng T 200 400 600 800 cuûa 3 xí nghieäp laàn löôït laø Ai = (650, 1.000, 350) P boùng. Hôïp ñoàng coâng ty phaûi giao cho 4 nhaø 22 25 20 18 10 phaân phoái laø Bj = (200, 400, 600, 800) boùng. Ñôn 650 giaù baùn cuûa moãi boùng ñeøn töông öùng vôùi caùc -2 -3 + 250 – 400 nhaø phaân phoái ñöôïc cho bôûi ma traän sau: 30 32 25 28 0 Ñvt: 1.000 ñoàng  22 25 20 18  1000 – 200 400 + 400 cij   30 32 25 28  29 28 25 23 5    29 28 25 23  350   + -4 -1 – 350 Haõy tìm keá hoaïch phaân phoái haøng sao cho coâng 30 q = 200 32 30 28 ty ñaït doanh soá lôùn nhaát THUAÄT GIAÛI THEÁ VÒ VÔÙI HAØM MUÏC TIEÂU Z  Max THUAÄT GIAÛI THEÁ VÒ VÔÙI HAØM 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 + -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 12
ThS. Nguyễn Công Trí - Tối ưu hóa * Chương 3 THUAÄT GIAÛI BAØI TOAÙN VAÄN TAÛI BAØI TOAÙN VAÄN TAÛI COÙ OÂ CAÁM COÙ HAØM MUÏC TIEÂU LAØ MAX Baøi toaùn vaän taûi coù oâ caám laø baøi toaùn vaän taûi •Do caùc ij  0, i, j vôùi P.A.T.Ö cuûa noù phaûi thoûa ñieàu kieän cho tröôùc. Ñeå giaûi baøi toaùn naøy, ta laäp baøi toaùn vaän taûi môû •P.A.T.Ö CUÛA BAØI TOAÙN roäng VTM baèng caùch cho giaù cöôùc vaän chuyeån ôû caùc oâ caám baèng M, vôùi M > 0 lôùn tuøy yù roài duøng  0 200 450 0  thuaät toaùn theá vò. Coù 2 tröôøng hôïp xaûy ra   xopt   0 200 0 800  1.Trong P.A.T.Ö cuûa baøi toaùn VTM, neáu caùc oâ caám  200 0 150 0  coù xij = 0 thì P.A.T.Ö cuûa baøi toaùn VTM cuõng chính   laø P.A.T.Ö cuûa baøi toaùn goác. •Vaø ZMax = 52.350 2.Trong P.A.T.Ö cuûa baøi toaùn VTM, neáu caùc oâ caám coù xij  0 thì baøi toaùn goác khoâng coù P.A.T.Ö. BAØI TOAÙN VAÄN TAÛI COÙ OÂ CAÁM T 140 150 180 25 Baûng 1 Ví duï 3.8. Giaûi baøi toaùn vaän taûi sau ñaây vôùi P Nhu caàu traïm phaùt a = (150, 100, 145, 100) 5 4 6 0 4 Nhu caàu traïm thu b = (140, 150, 180)  5 4 150 6 0 150 +3 M-4 Ma traän cöôùc vaän chuyeån 8 5 9 8 5 9 0 1 cij    100 vôùi ñieàu kieän  11 6 12  – 100 +2 +3 + M-1   11 6 12 M 1 traïm A3, A4 phaûi phaùt heát haøng.  9 7 13  145  Kieåm tra ñieàu kieän caân baèng thu – phaùt +1 145 ai = 150 + 100 + 145 + 100 = 495 9 7 13 M 0 bj = 140 + 150 + 180 = 470 100 + 40 +1 35 – 25  Laäp traïm thu giaû, vôùi b4= 25 vaø M > 0 tuøy yù. q = 25 9 8 13 M 13
ThS. Nguyễn Công Trí - Tối ưu hóa * Chương 3 T 140 150 180 25 Baûng 2 T 140 150 180 25 Baû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 – 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 T 140 150 180 25 Baûng 4 T 140 150 180 25 Baû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 -4 9 7 13 M -4 100 100 100 +1 +1 100 +1 q =105 q=5 5 4 10 1 5 4 6 -3 14
ThS. Nguyễn Công Trí - Tối ưu hóa * Chương 3 T 140 150 180 25 Baûng 6 BAØI TOAÙN VAÄN TAÛI COÙ OÂ CAÁM P •Do caùc ij  0 i,j neân 5 4 6 0 3 150 •P.A.C.B.T.Ö cuûa baøi toaùn vaän taûi treân laø – 40 + 110 8 5 9 0 0 100  40 0 110  5 – 70 25  0 70  + 0 11 6 12 M -1 5 145 xopt   145  0 145 0  9 7 13 M -1 100 0 0  100  100 Z =3.285 8 5 9 0 q = 40 •vaø Zmin= 3.285 P.A.T.Ö khaùc T 140 150 180 25 Baûng 7 BAØI TOAÙN VAÄN TAÛI COÙ OÂ CAÁM P •P.A.C.B.T.Ö khaùc cuûa baøi toaùn vaän taûi treân laø 5 4 6 0 3  0 0 150  150  40 0 150 5 30  xopt     8 5 9 0 0 •vaø Zmin= 3.285  0 145 0  100   40 5 30 25 •Taäp phöông aùn toái öu  100 0 0  11 6 12 M -1 145 •Zopt = Xopt + (1 – ) X/opt 145  40 0 150  40  9 7 13 M -1  40  40 5 30  40  100 •Hay Z o p t   100 Z =3.285  0 145 0  8 5 9 0    100 0 0  15
ThS. Nguyễn Công Trí - Tối ưu hóa * Chương 3 MOÂ HÌNH BAØI TOAÙN VAÄN TAÛI XE KHOÂNG THUAÄT GIAÛI BAØI TOAÙN XE KHOÂNG TAÛI  Ñieàu kieän raøng buoäc cuûa baøi toaùn vaän taûi xe 1. Laäp baûng vaän taûi töông öùng vôùi ma traän khoâng laø moät soá traïm phaùt Ai phaûi phaùt ñuû haøng khoaûng caùch. Duøng thuaät toaùn theá vò tìm P.A.T.Ö cho traïm Bj (ñöôïc chæ ñònh). Xaùc ñònh loä trình xe cuûa baøi toaùn xe khoâng taûi. chaïy khoâng taûi töø Bj ñeán Ai laø ít nhaát. 2. Taïo baûng phoái hôïp P.A.T.Ö cuûa baøi toaùn xe  Khi ñoù traïm phaùt Ai trôû thaønh traïm thu xe khoâng taûi vôùi keá hoaïch vaän taûi ñaõ cho tröôùc. Laäp khoâng, traïm thu Bj trôû thaønh traïm phaùt xe khoâng tuyeán ñieàu ñoäng töông öùng. vaø khi ñoù ma traän (cij) laø ma traän khoaûng caùch 3. Giaûm löôïng cheânh leäch giöõa “oâ troøn” vaø “oâ töông öùng giöõa Ai vaø Bj. vuoâng” ñeå coù baûng môùi thu goïn. Qui öôùc söû duïng caùc kyù hieäu nhö sau: 4. Laäp voøng ñieàu ñoäng goàm caùc oâ coù taûi vaø oâ  x ij : löôïng haøng hoùa coù vaän taûi. khoâng taûi lieân tieáp nhau, löôïng ñieàu ñoäng q=  xij : löôïng haøng cuûa xe khoâng taûi. min{xij}, vôùi xij coù taûi vaø xij khoâng taûi. Trôû veà [3].  : tuyeán xe chaïy coù taûi. Sau moät soá böôùc laëp höõu haïn [3] vaø [4], ta seõ thu  : tuyeán xe chaïy khoâng taûi ñöôïc keá hoaïch ñieàu ñoäng haøng hoùa toái öu. THUAÄT GIAÛI BAØI TOAÙN XE KHOÂNG TAÛI THUAÄT GIAÛI BAØI TOAÙN XE KHOÂNG TAÛI Ví duï 3.9. Moät coâng ty vaän taûi coù keá hoaïch vaän Cho bieát khoaûng caùch giöõa ñòa ñieåm cung chuyeån haøng hoùa theo hôïp ñoàng, ñöôïc theå hieän caáp haøng vaø ñòa ñieåm nhaän haøng (km) ñöôïc theå qua baûng yeâu caàu nhö sau hieän qua ma traän nhö sau: Ñòa ñieåm Loaïi Löôïng Nôi nhaän Kyù hieäu  2 1 4 3 caáp haøng Ai haøng (taán) haøng Bj   20 Coâng ty rau quaû B2 L   5 2 6 4 A1 Cam 30 Cöûa haøng soá 3 B3  3 4 2 5 25 Cöûa haøng soá 1 B1   A2 Döa haáu 15 Coâng ty rau quaû B2 Haõy xaùc ñònh loä trình vaän chuyeån haøng hoùa 10 Cöûa haøng soá 3 B3 thoûa yeâu caàu hôïp ñoàng vaø toång taán – km xe 50 Cöûa haøng soá 4 B4 chaïy khoâng taûi nhoû nhaát. A3 Saàu rieâng 20 Coâng ty rau quaû B2 16
ThS. Nguyễn Công Trí - Tối ưu hóa * Chương 3 Böôùc 1 (tìm P.A.T.Ö cuûa baøi toaùn xe khoâng taûi) Böôùc 2 (taïo baûng phoái hôïp) Baûng 2 Bj 25 55 40 50 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 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 A1: 20 T X 1km = 20T – km 3 3 2 5 A2 B2 2km A2: 5 T X 2km = 10T – km Zmin= 420 taán – km A3 B4 5km A3: 5 T X 5km = 25T – km Böôùc 3 (laäp tuyeán ñieàu ñoäng) Baûng 3 Böôùc 3 (laäp tuyeán ñieàu ñoäng) Baûng 4 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 q=5 A2 B1 3km A3 B2 1km A1 B3 3km 2km A2 B1 A3 B4 A3 B4 4km A2:20Tx10km=200T-km 4km A2: 5T x 7km = 35T–km. 17
ThS. Nguyễn Công Trí - Tối ưu hóa * Chương 3 Böôùc 3 (laäp tuyeán ñieàu ñoäng) Baûng 5 Böôùc 3 (laäp tuyeán ñieàu ñoäng) Baûng 6 Bj 25 55 40 50 Bj 25 55 40 50 Ai Ai 2 1 4 10 3 2 1 4 3 50 50 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 20 10 q=10 q=10 A2 B2 1km A1 B3 2km A3 A2 B3 2km A3 B4 B4 4km A2: 10T x 7km = 70T–km 4km A : 10 T x 6km = 60T–km 2 THUAÄT GIAÛI BAØI TOAÙN XE KHOÂNG TAÛI BAØI TAÄP CHÖÔNG 3 BAÛNG ÑIEÀU ÑOÄNG XE LAÄP MOÂ HÌNH CUÛA BAØI TOAÙN VAÄN TAÛI A1 B2 1km A1: 20 T [1] [2] A2 B2 2km A : 5 T 2 TÌM PHÖÔNG AÙN CÖÏC BIEÂN ÑAÀU TIEÂN A3 B4 5km A3: 5 T 3km A3 Ths. Nguyeãn Coâng Trí [3a] [3b] [3c*] [3d] [3e] A2 B1 B2 1km A1 B3 2km A B44km A2: 20 T GIAÛI BAØI TOAÙN VAÄN TAÛI CAÂN BAÈNG THU - PHAÙT A2 3 B1 3km A3 B4 4km A2: 5 T [4] [5] Copyright [6] [7] [8] [9] 2001 A2 B2 1km A1 B3 2km A3 CAÙC DAÏNG KHAÙC CUÛA BAØI TOAÙN VAÄN TAÛI B4 4km A2: 10 T [10a] [10b] [10c] A2 B3 2km A3 B4 4km A2: 10 T [11a] [11b] [11c] [11d] 18
ThS. Nguyễn Công Trí - Tối ưu hóa * Chương 3 BAØI TAÄP CHÖÔNG 3 BAØI TAÄP CHÖÔNG 3 1. Moät coâng ty vaän taûi bieån caàn 110 ngöôøi ñeå boá Goïi xij laø soá lao ñoäng trình ñoä i (i = kyõ sö, trung trí vaøo caùc nhieäm vuï: 10 maùy tröôûng; 25 thôï maùy caáp, coâng nhaân) ñöôïc boá trí vaøo nhieäm vuï j (j = 1; 30 thôï maùy 2; 45 thôï maùy 3. Phoøng toå chöùc maùy tröôûng, maùy 1, maùy 2, maùy 3). z  5 x11  4 x12  3 x21  5 x22  4 x23  x32  5 x33  4 x34  max nhaân söï 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 x11  x12  x13  x14  25 coâng nhaân coù kinh nghieäm. x21  x22  x23  x24  20 Nhieäm vuï Ñieåm ñaùnh giaù naêng löïc (aij) x31  x32  x33  x34  45 Trình ñoä Maùy tröôûng Maùy 1 Maùy 2 Maùy 3 x11  x21  x31  10 Kyõ sö 5 4 0 0 x12  x22  x32  25 Trung caáp 3 5 4 0 x13  x23  x33  30 Coâng nhaân 0 1 5 4 x14  x24  x34  45 Haõy boá trí nhaân löïc sao cho coâng vieäc toái öu. xij  0, i  1,3, j  1, 4 BAØI TAÄP CHÖÔNG 3 BAØI TAÄP CHÖÔNG 3 2. Hai ñoäi tuyeån boùng baøn, moãi ñoäi coù 5 ngöôøi. Goïi xij laø ñaáu thuû i cuûa ñoäi I ñöôïc xeáp thi ñaáu Qua thoáng keâ nhieàu traän ñaáu trong quaù khöù, vôùi ñaáu thuû j cuûa ñoäi II (i, j = 1, 2, ..., 5). ngöôøi ta döï ñoaùn xaùc suaát thaéng cuoäc moãi ñaáu z  0, 4 x11  0, 5 x12  0, 6 x13  0, 7 x14  0,8 x15 thuû cuûa moãi ñoäi ñöôïc theå hieän qua baûng sau 0, 3x22  0, 4 x23  0, 4 x24  0, 7 x25 Ñoäi II Ñaáu Ñaáu Ñaáu Ñaáu Ñaáu 0, 2 x31  0, 6 x32  0, 4 x33  0,3 x34  0, 5 x35 Ñoäi I Thuû 1 Thuû 2 Thuû 3 thuû 4 Thuû 5 0, 6 x41  0,3x42  0, 4 x43  0, 7 x44  0, 6 x45 Ñaáu thuû 1 0,4 0,5 0,6 0,7 0,8 0, 2 x52  0,3 x53  0, 4 x54  0, 6 x55  max Ñaáu thuû 2 0 0,3 0,4 0,4 0,7 5 Ñaáu thuû 3 0,2 0,6 0,4 0,3 0,5 x j 1 ij  1, i  1,5 Ñaáu thuû 4 0,6 0,3 0,4 0,7 0,6 5 Ñaáu thuû 5 0 0,2 0,3 0,4 0,6 x i 1 ij  1, j  1,5 Haõy saép 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. xij  0,1 i, j  1, 5 19
ThS. Nguyễn Công Trí - Tối ưu hóa * Chương 3 BAØI TAÄP CHÖÔNG 3 BAØI TAÄP CHÖÔNG 3 3.a) Tìm phöông aùn cöïc bieân baèng hai phöông 3.b) Tìm phöông aùn cöïc bieân baèng hai phöông phaùp chi phí beù nhaát vaø phöông phaùp Vogels phaùp chi phí beù nhaát vaø phöông phaùp Vogels Bj Bj 20 25 30 15 3 5 10 14 Ai Ai 40 4 5 1 2 10 1 3 7 1 20 3 4 7 8 15 2 4 2 3 30 2 6 9 3 7 6 5 4 1 Kieåm tra ñieàu kieän caân baèng thu phaùt ai = 40 + 20 + 30 = 90 bj = 20 + 25 + 30 + 15 = 90 BAØI TAÄP CHÖÔNG 3 BAØI TAÄP CHÖÔNG 3 3.c*) Tìm phöông aùn cöïc bieân baèng hai phöông 3.d) Tìm phöông aùn cöïc bieân baèng hai phöông phaùp chi phí beù nhaát vaø phöông phaùp Vogels phaùp chi phí beù nhaát vaø phöông phaùp Vogels Bj Bj 10 30 50 40 30 20 50 Ai Ai 25 7 6 5 30 3 7 4 6 10 2 1 4 40 4 6 2 5 45 3 5 2 70 1 5 7 8 Kieåm tra ñieàu kieän caân baèng thu phaùt ai = 25 + 10 + 45 = 80 bj = 10 + 30 + 50 = 90 Thêm trạm phát giả thứ 4, với a4 = bj - ai = 10, c4j = 0, j = 1, 2, 3. 20