›
›

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

pdf 24 trang phuongnguyen 3960
Download
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Tối ưu hóa - Chương 3: Bài toán vận tải - ThS. Nguyễn Công Trí", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pdfbai_giang_toi_uu_hoa_chuong_3_bai_toan_van_tai_ths_nguyen_co.pdf

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

  1. 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 thuï (traïm thu), kyù hieäu laø B1, B2, , Bn, bieát raèng Ths.BAØI TOAÙN Nguyeãn VAÄN TAÛI Coâng Trí(Xem) (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, , BIEÂN ÑAÀU TIEÂN CUÛA BAØI TOAÙN VAÄN TAÛI (Xem) Copyright 2001 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) daïng toång quaùt nhö sau: Ñaët xij laø soá löôïng haøng caàn vaän chuyeån töø traïm phaùt A ñeán traïm thu B . Tìm {xij} sao cho: i j m n m n Ta coù toång chi phí vaän taûi: Z c x min Z  cij x ij min  ij ij i 1 j 1 i 1 j 1 n n (1) Traïm phaùt, phaùt heát haøng: x a, i 1, m  ij i  xij a i , i 1, m j 1 j 1 m (2) Traïm thu, thu ñuû haøng: x b, j 1, n m  ij j x b, j 1, n i 1  ij j (3) Yeâu caàu traïm phaùt, traïm thu ñöôïc thoûa i 1 m n m n a b (ñk caân baèng thu – phaùt). i  j xij 0; c ij 0; a i 0; b j 0;  a i  b j i 1 j 1 i 1 j 1 1
  2. 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 AX b * x11 x 12  x 1n a 1 x x  x a 21 22 2n 2 X 0     Moät vectô X thoûa (*) vaø ( ) goïi laø phöông aùn. xm1 x m 2  x mn a m x11 x 21 xm 1 b 1 Moät P.A ñaït cöïc tieåu thì goïi laø P.A.T.Ö cuûa BTVT. x x x b 12 22m 2 2 Moät phöông aùn X ñöôïc goïi laø P.A.C.B khi caùc    vectô coät Aj cuûa ma traän heä soá A öùng vôùi caùc x1n x 2 n x mn b n thaønh phaàn xij > 0 laø ñoäc laäp tuyeán tính. Kyù hieäu Am+n,m n ma traän heä soá cuûa hpt treân. T  Moät P.A.C.B cuûa BTVT coù nhieàu nhaát laø m + n – X = (x11 x12 x1n x21 x22 x2n xm1 xm2 xmn) laø 1 thaønh phaàn döông. Neáu moät P.A.C.B cuûa BTVT vectô coät goàm m n thaønh phaàn; C = (c11 c12 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 T goàm m n thaønh phaàn; b = (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  (1) Kyù hieäu (i, j) laø oâ treân doøng i vaø coät j. Traïïm thu Bj B1 B2 Bn  (2) Chi phí vaän chuyeån c ñöôïc ghi ôû goùc treân b1 b2 bn ij beân traùi cuûa oâ (i, j), löôïng haøng caàn vaän chuyeån Traïïm phaùùt A i x ñöôïc ghi ôû goùc döôùi beân phaûi cuûa oâ (i, j) bieåu  ij A1 c11 c12 c1n dieãn tuyeán ñöôøng vaän chuyeån töø traïm phaùt A  i a1 x11 x12 x1n ñ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 x2n 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 cm2 cmn (5) Moät daõy caùc oâ choïn, trong ñoù 3 oâ lieân tieáp  khoâng naèm treân cuøng moät doøng hay moät coät thì am xm1 xm2 xmn ñöôïc goïi laø moät daây chuyeàn. 2
  3. 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 phöông aùn toái öu. m n m n Z  cij x ij min Z  cij x ij min TÍNH CHAÁT 2: Vôùi moät phöông aùn baát kyø, soá oâ i 1 j 1 i 1 j 1 n m choïn cuûa phöông aùn khoâng vöôït quaù toång soá  xij a i , i 1, m  xij b j , j 1, n traïm phaùt vaø traïm thu. j 1 i 1 ≤ m + n –1 (vôùi laø soá oâ choïn cuûa P.A) m n x a, i 1, m 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  ij i choïn thì vôùi moät oâ loaïi baát kyø ñöôïc ñöa vaøo i 1 j 1 phöông aùn seõ taïo thaønh chu trình vaø chu trình xij 0; c ij 0; a i 0; b j 0; xij 0; c ij 0; a i 0; b j 0; naøy laø duy nhaát. m n m n a b a b TÍNH CHAÁT 4: Neáu löôïng cung ai vaø löôïng caàu bj i  j i  j laø soá nguyeân thì baøi toaùn coù lôøi giaûi nguyeân. i 1 j 1 i 1 j 1 3
  4. 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 n m Treân baûng vaän taûi, choïn oâ ñaàu tieân coù cöôùc phí * Tìm {ui,vj} sao cho: Z  bj v j  a i u i 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 : loaïi doøng i, b b a ≤  i j j i xij 0 vaø vj – ui cij, i,j x minai , b j b : loaïi coät j, a a i b j Theo ñònh lyù ñoä leäch buø thì phöông aùn {xij} cuûa ij j i BTVT coù P.A.T.Ö laø toàn taïi heä thoáng {u , v } sao cho: i j ai 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 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 a = b = 175 i j P.A.C.B treân khoâng suy bieán, vôùi giaù trò Z = 980. 4
  5. 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 x = min(a , b ), sau ñoù tính laïi hieäu soá doøng (coät). ij i j 28 5 1 10 5 11 (3) Quaù trình treân ñöôïc laëp laïi cho ñeán khi chæ 45 16 5 3 7 16 coøn laïi moät doøng hay moät coät duy nhaát. 60 6 3 4 14 10 (4) Baûng thu ñöôïc vôùi caùc {xij} laø phöông aùn cöïc 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. 5,1,5 K 42 13 8 7 2 13 (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 4 K (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. 1 K 30 30 (5) trôû veà böôùc (2), sau moät soá böôùc laëp höõu haïn, 1 2 1 3 1 Z = 932 ta seõ coù P.A.T.Ö. 7 3 4 K 3 K K K K Phöông phaùp treân goïi laø thuaät toaùn theá vò 5
  6. ThS. Nguyễn Công Trí - Tối ưu hóa * Chương 3 SÔ LAÄPÑOÀ BAÛNGTHUAÄT VAÄN GIAÛI TAÛI THEÁ VÒ THUAÄT TOAÙN THEÁ VÒ XAÙCCUÛA ÑÒNH BAØI P.A.C.B TOAÙN ÑAÀU VAÄN TIEÂN TAÛ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. Coù (2) Xaùc ñònh P.A.C.B (baèng phöông phaùp chi phí Suy bieán? Theâm oâ xij=0 khoâng beù nhaát). Tính: V = U + C (3) Kieåm tra P.A.C.B coù suy bieán hay khoâng Xaùc ñònh P.A môùi j i ij Ui = Vj – Cij Neáu P.A.C.B. suy bieán: theâm vaøo oâ (i,j) baát kyø xij q daáu ( ). xij xij q daáu ( ). Coù vôùi xij = 0, khoâng taïo thaønh chu trình. ij 0? Baøi toaùn coù P.A.T.Ö x khoâng daáu. ij khoâng Neáu P.A.C.B khoâng suy bieán, chuyeån sang [2] Keát thuùc thuaät giaûi Choïn oâ vaøo: Max ij 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 ≤ 0: ta coù P.A.T.Ö. xij q daáu ( ); ij Neáu  > 0: chuyeån sang [3] ij xij xij q daáu ( ); Böôùc 3. Xaùc ñònh voøng ñieàu chænh xij khoâng daáu. (1) Choïn oâ vaøo: Max ij ( ij > 0) (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
  7. 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 = {X + (1 – )X/ ,  0, 1} opt opt 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
  8. 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 5 35 -1 0 5 0 0 35 0 12 13 10 11 13 9 75 -6 0 5 0 70 0 0 5 70 x 45 0 0 0 0 15 3 9 5 6 7 1 opt 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ø 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ù = 0, vôùi (i, j) laø oâ loaïi 4 7 2 5 6 2 ij 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  60 ai = 79 + 102 + 70 + 60 = 311 + 12 - 48 bj = 76 + 62 + 88 + 45 + 40 = 311 q=30 10 16 13 6 4 8
  9. 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 30 40 42 18 0 0 0 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öù B 1. BAØI TOAÙN VAÄN TAÛI KHOÂNG CAÂN BAÈNG n+1 . 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. BAØI TOAÙN VAÄN TAÛI COÙ DAÏNG HAØM MUÏC 2. TRÖÔØNG HÔÏP 2. ai < bj . 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
  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 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 a = 165 < b = 190 0 0 0 0 12 i j 25 Theâm moät traïm phaùt giaû A , vôùi 25 4 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 x 30 0 25 0 8 7 14 12 2 opt 50 + 5 - 45 5 45 0 0 0 0 0 0 11 25 •vaø Zmin = 1.385 25 q = 30 10 9 11 7 Coù P.A.T.Ö khaùc 10
  11. ThS. Nguyễn Công Trí - Tối ưu hóa * Chương 3 T 65 45 50 30 BAØI TOAÙN VAÄN TAÛI KHOÂNG CAÂN BAÈNG THU-PHAÙT 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 x 30 0 25 0 opt 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 •Z = X + (1 – ) X/ 35 15 opt opt opt 0 0 0 0 11 30 30 30  0 30 25 •Hay Z 30 0 25 0 25 opt 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 haøm muïc tieâu Z max veà Z/ = – Z min, sau ñoù Z  cij x ij max 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 a, i 1, m  ij i thuaät toaùn theá vò vôùi moät vaøi thay ñoåi trong thuaät j 1 m giaûi nhö sau:  xij 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 i 1 ña vaøo oâ coù cöôùc phí lôùn nhaát. m n xij 0; c ij 0; a i 0; b j 0; a i  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
  12. 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 1000 22 25 20 18 – 200 400 + 400 c 30 32 25 28 ij 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 32 30 28 q = 200 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
  13. 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 vôùi P.A.T.Ö cuûa noù phaûi thoûa ñieàu kieän cho tröôùc. •Do caùc ij 0, i, j Ñ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 ôû 0 200 450 0 caùc oâ caám baèng M, vôùi M > 0 lôùn tuøy yù roài duøng thuaät toaùn theá vò. Coù 2 tröôøng hôïp xaûy ra x 0 200 0 800 opt 1.Trong P.A.T.Ö cuûa baøi toaùn VTM, neáu caùc oâ caám coù x = 0 thì P.A.T.Ö cuûa baøi toaùn VT cuõng chính 200 0 150 0 ij M laø P.A.T.Ö cuûa baøi toaùn goác. 2.Trong P.A.T.Ö cuûa baøi toaùn VT , neáu caùc oâ caám •Vaø ZMax = 52.350 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) 150 5 4 6 0 150 +3 M-4 Ma traän cöôùc vaän chuyeån 8 5 9 8 5 9 0 1 c 100 ij 100 vôùi ñieàu kieän 11 6 12 – +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  100 bj = 140 + 150 + 180 = 470 + 40 +1 35 – 25  q = 25 Laäp traïm thu giaû, vôùi b4= 25 vaø M > 0 tuøy yù. 9 8 13 M 13
  14. 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
  15. 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 0 i,j neân 5 4 6 0 3 ij 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 – 0 5 70 11 6 12 M -1 145 xopt 145 0 145 0 9 7 13 M -1 100 100 0 0 100 Z =3.285 •vaø Z = 3.285 P.A.T.Ö khaùc8 5 9 0 q = 40 min 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 5 30 0 150 x opt 8 5 9 0 0 •vaø Z = 3.285 0 145 0 100 min 100 0 0 40 5 30 25 •Taäp phöông aùn toái öu -1 11 6 12 M •   / 145 Zopt = Xopt + (1 – ) X opt 145 40 0 150 40  9 7 13 M -1 40 40 5 30 40  •Hay 100 Z opt 100 Z =3.285 0 145 0 8 5 9 0 100 0 0 15
  16. 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=  x ij : 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 haøng (taán) caáp haøng Ai 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
  17. 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 Baûng 1 Bj 25 55 40 50 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 1km A1 B2 A1: 20 T X 1km = 20T – km 3 3 2 5 2km A2 B2 A2: 5 T X 2km = 10T – km Zmin= 420 taán – km 5km A3 B4 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 3km 1km A2 B1 A3 B2 A1 B3 3km 2km 4km A2 B1 A3 B4 A3 B4 A2:20Tx10km=200T-km 4km A2: 5T x 7km = 35T–km. 17
  18. 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 1km 2km q=10 2km A2 B2 A1 B3 A3 A2 B3 A3 B4 4km 4km B4 A2: 10T x 7km = 70T–km A2 : 10 T x 6km = 60T–km 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] 2km A2 B2 A2: 5 T TÌM PHÖÔNG AÙN CÖÏC BIEÂN ÑAÀU TIEÂN A B 5km A : 5 T 3 4 3 [Ths.3a] [3b] Nguyeãn[3c*] [3d] [3e] Coâng Trí 3km 1km A2 B1 A3 B2 A1 B3 2km 4km GIAÛI BAØI TOAÙN VAÄN TAÛI CAÂN BAÈNG THU - PHAÙT A3 B4 A2: 20 T 3km 4km [4] [5] [6] [7] [8] [9] A2 B1 A3 B4 A2: 5 T Copyright 2001 1km 2km CAÙC DAÏNG KHAÙC CUÛA BAØI TOAÙN VAÄN TAÛI A2 B2 A1 B3 A3 4km B4 A2: 10 T [10a] [10b] [10c] 2km 4km A2 B3 A3 B4 A2: 10 T [11a] [11b] [11c] [11d] 18
  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 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 x 4 x 3 x 5 x 4 x x 5 x 4 x max nhaân söï tuyeån ñöôïc 90 ngöôøi, trong ñoù goàm 25 11 12 21 22 23 32 33 34 x x x x 25 kyõ sö maùy; 20 kyõ thuaät vieân trung caáp vaø 45 11 12 13 14 coâng nhaân coù kinh nghieäm. x21 x 22 x 23 x 24 20 x31 x 32 x 33 x 34 45 Nhieäm vuï Ñieåm ñaùnh giaù naêng löïc (aij) x x x 10 Trình ñoä Maùy tröôûng Maùy 1 Maùy 2 Maùy 3 11 21 31 x x x 25 Kyõ sö 5 4 0 0 12 22 32 Trung caáp 3 5 4 0 x13 x 23 x 33 30 Coâng nhaân 0 1 5 4 x14 x 24 x 34 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 x 12 0,6 x 13 0,7 x 14 0,8 x 15 thuû cuûa moãi ñoäi ñöôïc theå hieän qua baûng sau 0,3x22 0,4 x 23 0,4 x 24 0,7 x 25 Ñoäi II Ñaáu Ñaáu Ñaáu Ñaáu Ñaáu 0,2x31 0,6 x 32 0,4 x 33 0,3 x 34 0,5 x 35 Ñoäi I Thuû 1 Thuû 2 Thuû 3 thuû 4 Thuû 5 0,6x41 0,3 x 42 0,4 x 43 0,7 x 44 0,6 x 45 Ñaáu thuû 1 0,4 0,5 0,6 0,7 0,8 0,2x52 0,3 x 53 0,4 x 54 0,6 x 55 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  xij 1, i 1,5 j 1 Ñ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  xij 1, j 1,5 Haõy saép xeáp caùc ñaáu thuû cuûa ñoäi I sao cho xaùc i 1 suaát thaéng toaøn ñoaøn cuûa ñoäi I cao nhaát. xij 0,1i , j 1,5 19
  20. 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 B Bj j 3 5 10 14 20 25 30 15 A Ai i 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 B j 10 30 50 Bj A 40 30 20 50 i 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
  21. 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.e) Tìm phöông aùn cöïc bieân baèng hai phöông 4. Giaûi baøi taäp [3], vôùi phaùp chi phí beù nhaát vaø phöông phaùp Vogels a)Phöông aùn cöïc bieân ñaàu tieân thu ñöôïc baèng B j 30 20 25 35 40 phöông phaùp chi phí beù nhaát, Ai 30 13 7 6 2 12 b)Phöông aùn cöïc bieân ñaàu tieân thu ñöôïc baèng phöông phaùp Vogels. 20 5 1 10 5 11 40 10 5 3 7 14 60 6 3 2 11 10 BAØI TAÄP CHÖÔNG 3 BAØI TAÄP CHÖÔNG 3 5. a) Giaûi baøi toaùn vaän taûi 6. a) Giaûi baøi toaùn vaän taûi B 50 160 120 80 B j j 20 100 45 15 Ai Ai 220 5 4 3 10 90 10 6 4 1 100 5 9 7 12 40 3 4 2 5 90 10 6 8 15 50 9 4 3 7 b) Baøi toaùn coù phöông aùn toái öu khaùc hay b) Baøi toaùn coù phöông aùn toái öu khaùc hay khoâng? Neáu coù, chæ ra phöông aùn toái öu ñoù. khoâng? Neáu coù, chæ ra taäp phöông aùn toái öu. 21
  22. 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 7. Cho baøi toaùn vaän taûi coù daïng 8. Cho baøi toaùn vaän taûi coù daïng 9 5 6 14 4 2 5 7 6 ai 20, 110, 120 ai 38, 45, 66, 45 c 5 8 3 4 5 10 7 9 15 ij cij bj 70,40,30,60,50 b 10 10 6 7 2 1 4 3 2 j 52, 45, 38, 59 a) Tìm P.A.T.Ö cuûa baøi toaùn treân. 4 8 13 14 b) Theo baïn daáu hieäu naøo cho ta bieát BTVT coù a) Tìm P.A.T.Ö cuûa baøi toaùn treân. nhieàu P.A.T.Ö? P.A.C.B.T.Ö tìm ñöôïc ôû caâu b) Phöông aùn toái öu vöøa tìm ñöôïc coù duy a) coù duy nhaát khoâng? Neáu coù, haõy chæ ra nhaát khoâng? (coù giaûi thích). Chæ ra moät P.A.C.B.T.Ö khaùc? phöông aùn toái öu khaùc? (neáu coù). c) Tìm taäp caùc P.A.T.Ö vaø chæ ra 3 P.A.T.Ö? BAØI TAÄP CHÖÔNG 3 BAØI TAÄP CHÖÔNG 3 10. a) Giaûi baøi toaùn vaän taûi sau ñaây vaø tìm 9. Giaûi baøi taäp [1], [2]. phöông aùn toái öu khaùc (neáu coù). B j 60 60 80 100 Ai 80 4 5 6 12 70 10 3 9 5 100 6 4 7 9 22
  23. 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 10. b) Giaûi baøi toaùn vaän taûi sau ñaây vaø tìm 10. c) Giaûi 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ù). phöông aùn toái öu khaùc (neáu coù). Traïm phaùt ai 100, 20, 30, 50 Traïm phaùt ai 79, 50, 60, 50 Traïm thu bj 70, 60, 25, 50 Traïm thu bj 46, 45, 76, 20, 52 Ma traän cöôùc phí vaän taûi Ma traän cöôùc phí vaän taûi 10 14 24 8 10 1 5 13 8 30 20 18 14 5 6 10 8 13 c c ij 2 12 6 7 ij 3 2 8 9 6 8 16 14 36 13 5 7 10 13 BAØI TAÄP CHÖÔNG 3 BAØI TAÄP CHÖÔNG 3 11. a) Giaûi baøi toaùn vaän taûi coù oâ caám sau ñaây vaø 11. b) Giaûi 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ù). tìm phöông aùn toái öu khaùc (neáu coù). Traïm phaùt ai 90, 40, 50 Traïm phaùt ai 100, 80, 50 Traïm thu bj 20, 100, 45 Traïm thu bj 65, 90, 50, 30 Ma traän cöôùc phí vaän taûi Ma traän cöôùc phí vaän taûi 10 6 4 10 9 12 7 c c ij 3 4 2 ij 9 11 10 15 9 4 3 8 7 14 12 Ñieàu kieän A3 phaûi phaùt heát haøng. Ñieàu kieän B2 phaûi thu ñuû haøng. 23
  24. 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 11. c) Giaûi baøi toaùn vaän taûi coù oâ caám sau ñaây vaø 11. d) Giaûi 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ù). tìm phöông aùn toái öu khaùc (neáu coù). Traïm phaùt ai 220, 100, 90 Traïm phaùt ai 90, 40, 50 Traïm thu bj 50, 160, 120, 80 Traïm thu bj 20, 100, 45 Ma traän cöôùc phí vaän taûi Ma traän cöôùc phí vaän taûi 5 4 3 10 10 6 4 c c ij 5 9 7 12 ij 3 4 2 10 6 8 15 9 4 3 Ñieàu kieän traïm phaùt A3 khoâng ñöôïc phaùt cho Ñieàu kieän traïm thu B2 khoâng ñöôïc thu cuûa traïm thu B2. traïm phaùt A1. 24