Bài giảng Tối ưu hóa: Chương 3 - ThS. Phạm Trí Cao

Chia sẻ: Thôi Kệ | Ngày: | Loại File: PDF | Số trang:25

Thêm vào BST

Báo xấu

126
lượt xem 13
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 trình bày về bài toán vận tải. Chương này cung cấp cho người học các nội dung: Bài toán vận tải cân bằng thu phát, các khái niệm và định nghĩa, thuật toán thế vị, bài toán vận tải không cân bằng thu phát, bài toán dạng vận tải có hàm mục tiêu cực đạ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. Phạm Trí Cao

ThS. Phạm Trí Cao * Chương 3 03/01/2014  I) BAØI TOAÙN VAÄN TAÛI CAÂN BAÈNG THU PHAÙT CHÖÔNG 3:  1) Baøi toaùn  Coù m ñòa ñieåm A1, A2, ..., Am cuøng saûn BAØI TOAÙN VAÄN TAÛI xuaát 1 loaïi haøng vôùi caùc löôïng haøng töông öùng laø a1, a2, .., am. Coù n ñòa ñieåm tieâu thuï loaïi haøng treân laø B1 , B2 , ..., Bn vôùi caùc yeâu caàu töông öùng laø b1 , b2 ,.., bn.  Ta goïi Ai laø traïm phaùt thöù i, Bj laø traïm thu thöù j. Ta coù caùc giaû thieát sau: Giaûi: * Haøng coù theå chôû töø traïm phaùt Ai baát kyø ñeán traïm Goïi xij laø soá ñôn vò haøng chuyeân chôû töø traïm thu Bj baát kyø. phaùt (i) ñeán traïm thu (j). * Chi phí chuyeân chôû 1 ñôn vò haøng töø traïm phaùt (i) * Ñieàu kieän cho bieán goïi: xij >=0 , i,j ñeán traïm thu (j) laø cij , cij >=0 * Ñieàu kieän ñeå caùc traïm phaùt thì phaùt heát haøng: n * Toång löôïng haøng coù ôû m traïm phaùt (toång phaùt)  x ij = ai : traïm phaùt (i) phaùt heát haøng j 1 = toång löôïng haøng yeâu caàu ôû n traïm thu (toång thu): m n * Ñieàu kieän ñeå caùc traïm thu thì thu ñuû haøng:  a i =  b j (ñk caân baèng thu phaùt) m i 1 j 1  x = bj : traïm thu (j) thu ñuû haøng i  1 ij Haõy laäp phöông aùn vaän chuyeån haøng sao cho: caùc * Toång chi phí vaän chuyeån laø: traïm phaùt thì phaùt heát haøng, caùc traïm thu thì thu ñuû n m m n f(X)=   c x    c x haøng vaø toång chi phí vaän chuyeån laø nhoû nhaát? j 1 i 1 ij ij i 1 j 1 ij ij 1
ThS. Phạm Trí Cao * Chương 3 03/01/2014 Vaäy moâ hình baøi toaùn vaän taûi laø: 2) Baûng vaän taûi Ta ghi taát caû caùc tham soá cuûa baøi toaùn vaøo Tìm ma traän X= (xij)m*n sao cho: baûng sau, goïi laø baûng vaän taûi: n m f(X)=   c x  min (1) T B1 Bj Bn j 1i1 ij ij F (b1) (bj) (bn) n A1 c11 c1j c1n  x ij = ai , i (2) (a1) x11 x1j x1j j 1 Ai ci1 cij cin m (ai) xi1 xij xin  x ij = bj , j (3) Am cm1 cmj cmn i 1 (am) xm1 xmj xmn xij >=0 , i,j (4) Ví duï soá:  Ta coù moâ hình baøi toaùn laø: Giaû söû ta coù 2 traïm phaùt vaø 3 traïm thu. Löôïng  f(X)= 7x11 + 3x12 + 4x13 + x21 + 2x22 + 3x23 haøng coù ôû caùc traïm phaùt, löôïng haøng yeâu caàu ôû  min  x11 + x12 + x13 = 60 caùc traïm thu, chi phí vaän chuyeån, vaø 1 pa vaän  x21 + x22 + x23 = 40 chuyeån ñöôïc cho trong baûng sau:  x11 + x21 = 30 T B1 B2 B3  x12 + x22 = 50 F ( 30) (50) (20)  x13 + x23 = 20 A1 7 3 4  xij >=0, i= 1,2 ; j= 1,3 (60) [30] [20] [10] A2 1 2 3  Ta thaáy baøi toaùn vaän taûi laø tröôøng hôïp (40) [30] [10] rieâng cuûa baøi toaùn quy hoaïch tuyeán tính. 2
ThS. Phạm Trí Cao * Chương 3 03/01/2014  II) CAÙC KHAÙI NIEÄM VAØ ÑÒNH NGHÓA  1) OÂ choïn vaø oâ loaïi Ví duï:  OÂ naèm ôû vò trí: doøng i, coät j goïi laø oâ (i,j) Xeùt VD soá ôû treân:  X = (xij)m*n laø 1 pa cuûa baøi toaùn vaän taûi - Neáu xij > 0 thì oâ (i,j) goïi laø oâ choïn (oâ cô sôû) 123 - Neáu xij = 0 thì oâ (i,j) goïi laø oâ loaïi (oâ phi cô 1*** sôû) 2 **  Quy öôùc:  OÂ chọn laø oâ coù daáu * Ta chæ xeùt nhöõng oâ coù daáu * (oâ choïn).  2) Daây chuyeàn vaø voøng  Daây chuyeàn laø moät daõy caùc oâ lieân tieáp nhau (coù theå lieàn keà nhau hoaëc khoâng) thoûa:  - Ñi ngang thì chæ laáy 2 oâ.  - Ñi doïc thì chæ laáy 2 oâ.  - Ñi ngang, ñi doïc xen keõ nhau.  Moät doøng hoaëc moät coät maø daây chuyeàn ñi qua: hoaëc khoâng laáy oâ naøo heát, hoaëc chæ laáy ñuùng 2 oâ. 3
ThS. Phạm Trí Cao * Chương 3 03/01/2014  Voøng laø 1 daây chuyeàn kheùp kín, coù oâ baét ñaàu truøng vôùi oâ keát thuùc.  Chuù yù:  Moät doøng hoaëc moät coät maø voøng ñi qua: neáu khoâng laáy thì thoâi, coøn neáu laáy thì chæ laáy ñuùng 2 oâ.  Nhaän xeùt:  - Soá oâ treân voøng luoân laø moät soá chaún >=4.  - Soá oâ toái ña khoâng taïo thaønh voøng treân baûng coù m doøng, n coät laø m+n–1.  3) Phöông aùn cöïc bieân Ví duï:  Moät pa maø caùc oâ choïn khoâng taïo thaønh 1 2 3 4 1 2 3 4 1 2 3 4 voøng goïi laø pacb. 1 * * * 1 * 1 * * *  Ta luoân coù: pacb coù soá oâ choïn toái ña laø 2 * 2 * * 2 * m+n–1. 3 * * 3 * * 3 * *  Moät pacb coù ñuû m+n-1 oâ choïn goïi laø pacb H1 H2 H3 khoâng suy bieán, neáu coù ít hôn m+n-1 oâ choïn H1: pacb khoâng suy bieán vì khoâng coù voøng vaø soá goïi laø pacb suy bieán. oâ choïn = 6 = 3+41.  Moät pa maø caùc oâ choïn taïo thaønh voøng goïi H2: pacb suy bieán vì khoâng coù voøng vaø soá oâ laø pa khoâng cb. choïn = 5 < 6 = 3+41. H3: pa khoâng cb vì coù voøng (1,1) (1,4) (3,4) (3,1). 4
ThS. Phạm Trí Cao * Chương 3 03/01/2014  Ñònh lyù (moái lieân heä giöõa oâ choïn vaø oâ loaïi)  X laø pacb khoâng suy bieán, coù ñuû m+n-1 oâ choïn. Neáu ta boå sung 1 oâ loaïi baát kyø vaøo baûng vaän taûi thì oâ loaïi naøy seõ taïo thaønh 1 voøng duy nhaát vôùi 1 soá oâ choïn ñaõ coù.  Chuù yù:  Voøng naøy phaûi ñi qua oâ loaïi boå sung vaøo, khoâng nhaát thieát phaûi ñi qua taát caû caùc oâ choïn. 5
ThS. Phạm Trí Cao * Chương 3 03/01/2014  Ñònh lyù:  III) THUAÄT TOAÙN THEÁ VÒ  X laø pacb cuûa baøi toaùn vaän taûi, neáu X chöa  Ta ñöa ra thuaät toaùn theá vò cho baøi toaùn caân baèng toái öu thì luoân tìm ñöôïc moät pacb môùi X’ toát thu phaùt, minf.  1) Tröôøng hôïp baøi toaùn coù pacb khoâng suy bieán hôn X, nghóa laø: f(X’) =0 thì ta noùi ñaõ phaân phoái  Baøi toaùn vaän taûi luoân coù patö. cho oâ (i,j) moät löôïng haøng laø p.  Chöùng minh:  - Nguyeân taéc phaân phoái toái ña laø nguyeân taéc phaân  Xem trong saùch. phoái cho oâ (i,j) moät löôïng haøng lôùn nhaát coù theå ñöôïc, nghóa laø: xij = min{ai,bj}. Ví duï 3.1: Giaûi: Böôùc 1: Baûng vaän taûi xuaát phaùt F T 25 38 25 30 Ta coù: TF = 30+50+38 = 118 = 25+38+25+30 = TT (BT caân baèng thu phaùt) 30 15 10 9 12 T 25 38 25 30 F 50 13 21 14 8 30 15 10 9 12 38 10 11 16 12 50 13 21 [5] 14 [25] 8 [20] [30] Duøng phöông phaùp chi phí beù 38 10 11 16 12 [25] [13] nhaát laäp baûng vaän taûi xuaát phaùt? 6
ThS. Phạm Trí Cao * Chương 3 03/01/2014 Caùch kieåm tra xem phaân phoái ñuùng khoâng?  Caùc oâ choïn khoâng taïo voøng. Soá oâ choïn
ThS. Phạm Trí Cao * Chương 3 03/01/2014  Böôùc 4: Caûi tieán pa (tìm pacb môùi toát hôn)  4.3) Xaùc ñònh löôïng ñieàu chænh q:  4.1) Tìm oâ ñieàu chænh:  Treân voøng ñieàu chænh ta ñaùnh daáu +,  lieân  OÂ ñieàu chænh laø oâ coù  döông lôùn nhaát. tieáp, vôùi quy öôùc oâ ñieàu chænh ñöôïc ñaùnh daáu  rs= max{ij/ij>0} neân oâ (r,s) laø oâ ñieàu chænh. ñaàu tieân vaø mang daáu +.  OÂ ñieàu chænh seõ laø oâ loaïi boå sung vaøo trong baûng  Ta chæ xeùt nhöõng oâ naèm treân voøng ñieàu chænh. vaän taûi môùi.  Löôïng ñieàu chænh q laø soá xij nhoû nhaát trong  4.2) Tìm voøng ñieàu chænh: Laäp voøng ñieàu chænh ñi nhöõng oâ mang daáu  . Giaû söû ñoù laø oâ (t,h). OÂ qua oâ ñieàu chænh (r,s) vaø 1 soá oâ choïn ñaõ coù. (t,h) seõ laø oâ bò loaïi ra trong baûng vaän taûi môùi.  Löu yù: Voøng ñieàu chænh naøy toàn taïi duy nhaát, phaûi  q = min{xij / vôùi moïi oâ (i,j) mang daáu } = xt,h ñi qua oâ ñieàu chænh. neân oâ (t,h) seõ bò loaïi ra trong baûng vaän taûi môùi.  Voøng ñieàu chænh khoâng nhaát thieát phaûi ñi qua taát caû caùc oâ choïn.  Nhaän xeùt: 4.4) Tìm pacb môùi X’: Pa X öùng vôùi baûng vaän taûi cuõ, pa X’ öùng vôùi baûng  Vôùi pp ñôn hình, qua moãi baûng ta loaïi vaän taûi môùi. Vaø f(X’)
ThS. Phạm Trí Cao * Chương 3 03/01/2014 Böôùc 4.4: Xaùc ñònh pacb môùi Böôùc 4: chuyeån baûng Ta coù pacb môùi nhö sau: T 25 38 25 30 ui T 25 38 25 30 ui F 30 15 10 9 12 0 F 6 [5] [25] 8 30 15 10 9 12 0 50 13 21 14 8 4 6 [5] [25] 15 [20] 7 1 [30] 50 13 + 21  14 8 11 38 10 11 16 12 1 7 * [20] 6 [30] [5] [33] 6 7 38 10  11 + 16 12 1 vj 9 10 9 4 [25] [13] 6 14 Ta coù ij 0} neáu coù nhieàu oâ ñeå choïn thì ta laøm theá naøo? Ví duï 3.2:  Qua moãi baûng haøm muïc tieâu giaûm 1 löôïng laø q.rs , f(X’) = f(X)- q.rs . T 30 35 25 10  Löu yù: Trong quaù trình tìm löôïng ñieàu chænh q, F neáu ta coù q ñaït taïi nhieàu oâ mang daáu  . 15 1 3 2 5  Ví duï q = min{xij / vôùi moïi oâ (i,j) mang daáu } = xt,h = xe,f 35 6 8 1 10  Ta laøm nhö theá naøo? Coù theå loaïi ra nhieàu oâ cuøng 10 3 2 6 5 luùc khoâng? 40 3 9 4 9  Xem chi tieát trong saùch. 9
ThS. Phạm Trí Cao * Chương 3 03/01/2014 Coù theå loaïi ra 1 trong 2 oâ (1,1), (4,2). Ta loaïi ra oâ (1,1). T 30 35 25 10 ui T 30 35 25 10 ui F F 15 1 3 2 5 0 15 1  3 + 2 5 0 -4 [15] -6 -2 * [15] 4 -2 2 35 6 8 1 10 5 35 6 8 1 10 1 -4 [10] [25] -2 -4 [10] [25] -2 10 3 2 6 5 -1 10 3 2 6 5 -5 -7 [10] -11 -3 -7 [10] -11 -3 40 3 9 4 9 6 40 3 + 9  4 9 2 [30] [0] -2 [10] [15] [15] -2 [10] vj -3 3 -4 3 Ta coù ij
ThS. Phạm Trí Cao * Chương 3 03/01/2014 Ta theâm oâ choïn ñaëc bieät laø oâ (3,2). F \ T 60 70 40 30 ui F \ T 60 70 40 30 ui 100 12 6 9 12 0 100 12 6 + 9 12  0 2 [70] 1 [30] 5 [70] 4 [30] 80 9 8 7 11 1 80 9 8 7 11 2 [60] 3 [20] 0 [60] 0 [20] 3 20 11 7 6 10 2 20 11 7  6 10 + 1 3 3 [20] [0] 3 * [0] [20] 3 vj 10 6 8 12 vj 7 6 5 12 Ta coù ij
ThS. Phạm Trí Cao * Chương 3 03/01/2014  Löu yù:  IV) BTVT KHOÂNG CAÂN BAÈNG THU PHAÙT  BTVT khoâng caân baèng thu phaùt laø BTVT coù toång  Tuøy theo caáu truùc cuûa baøi toaùn maø phaùt  toång thu. caùch 1 hay caùch 2 cho keát quaû toát hôn,  Thuaät toaùn theá vò chæ aùp duïng cho baøi toaùn vaän ta khoâng theå döï ñoaùn tröôùc ñöôïc. taûi CBTP, do ñoù ta phaûi chuyeån baøi toaùn  Tuøy thuoäc vaøo “linh caûm” cuûa baïn !!! KHOÂNG CBTP veà baøi toaùn CBTP.  1) Toång phaùt > toång thu  * Ñöa baøi toaùn ban ñaàu (P) veà baøi toaùn CBTP (P*) baèng caùch theâm coät traïm thu giaû coù yeâu caàu = toång phaùt  toång thu. Caùc oâ naèm treân coät traïm thu giaû goïi laø caùc oâ giaû, caùc oâ ban ñaàu goïi laø caùc oâ thöïc.  * Chi phí vaän chuyeån cuûa caùc oâ giaû ñeàu baèng 0. Ví duï 3.4:  * Duøng thuaät toaùn theá vò giaûi baøi toaùn (P*). Trong patö cuûa (P*), ta boû ñi coät traïm thu giaû thì ñöôïc F\T 120 130 50 patö cuûa (P). 100 10 8 12  Chuù yù: 150 15 10 14  Khi tìm pacb xuaát phaùt, ta öu tieân phaân phoái cho 80 9 11 12 caùc oâ thöïc tröôùc, khi xeùt heát oâ thöïc roài thì môùi xeùt ñeán caùc oâ giaû. HD:  Nhaän xeùt: Toång phaùt = 330 > 300 = toång thu  theâm coät  OÂ giaû ôû chöông 3  Bieán phuï ôû chöông 1 traïm thu giaû thöù 4 coù yeâu caàu = 330 - 300 = 30 12
ThS. Phạm Trí Cao * Chương 3 03/01/2014 Phöông phaùp chi phí beù nhaát Baûng vaän taûi môùi F \ T 120 130 50 (30) ui F \ T 120 130 50 (30) ui 100 10 8 12 0 0 100 10 + 8  12 0 0 [40] [60] 0 2 3 [100] 0 2 150 15 10 14 0 2 3 [70] [50] [30] 150 15  10 + 14 0 2 80 9 11 12 0 1 * [40] [30] [50] [30] [80] 4 1 3 80 9 11 12 0 4 vj 10 8 12 2 [80] 7 4 6 Ta coù ij
ThS. Phạm Trí Cao * Chương 3 03/01/2014 Phöông phaùp chi phí beù nhaát F \ T 15 25 30 27 ui F \ T 15 25 30 27 ui 35 5 1 4 + 2  0 35 5 1 4 2 0 -4 [25] 1 [10] -4 [25] -2 [10] 20 3 + 4 7  8 2 20 3 + 4 7  8 5 [15] -1 [5] -4 3 2 [20] -1 17 2  6 9 3 + 1 17 2  6 9 3 + 1 * [0] -4 -3 [17] [15] -4 -6 [2] (25) 0 0 0 0 -5 (25) 0 0 0 + 0  -2 -1 -1 [10] * [15] -4 -4 [25] 3 vj 1 1 2 2 vj 1 1 5 2 OÂ ñieàu chænh (2,1) OÂ ñieàu chænh laø (1,3) F \ T 15 25 30 27 ui  V) BTVT COÙ OÂ CAÁM 35 5 1 4 2 0  1) Caám tuyeán ñöôøng vaän chuyeån -5 [25] [0] [10]  Caùc baøi toaùn vaän taûi ta ñaõ xeùt, giaû thieát haøng coù theå 20 3 4 7 8 3 chôû töø traïm phaùt baát kyø ñeán traïm thu baát kyø. [15] 0 [5] -3  Trong thöïc teá ñoâi khi ta khoâng theå vaän chuyeån haøng 17 2 6 9 3 1 treân 1 soá tuyeán ñöôøng vì nhieàu lyù do. -1 -4 -4 [17]  Ta khoâng theå vaän chuyeån haøng töø Ai ñeán Bj töông (25) 0 0 0 0 -4 öùng vôùi oâ (i,j) neân oâ naøy khoâng theå phaân phoái haøng -4 -3 [25] -2 vaøo ñöôïc, do ñoù noù seõ laø oâ caám. vj 0 1 4 2  Laäp baøi toaùn (M) vôùi caùc oâ caám coù chi phí vaän Ta coù ij 0 (raát lôùn). fmin = 176 Ghi patö cuûa baøi toaùn?  Duøng t/toaùn theá vò giaûi bt (M), coù patö laø X*(M). 14
ThS. Phạm Trí Cao * Chương 3 03/01/2014  Ñònh lyù:  Neáu trong X*(M) coù caùc thaønh phaàn öùng vôùi oâ Ví duï 3.8: caám ñeàu baèng 0 thì baøi toaùn ban ñaàu (P) coù patö. Baøi toaùn (P) Patö chính laø X*(M).  Neáu trong X*(M) coù thaønh phaàn öùng vôùi oâ caám F\T 25 38 25 30 khaùc 0 thì (P) khoâng coù patö. 30 15 10 9 12  Nhaän xeùt: 50 13 21 14 8  OÂ caám ôû chöông 3  Bieán giaû ôû chöông 1 38 10 11 16 12  Löu yù:  Ta phaân phoái cho oâ thöïc tröôùc, oâ caám sau. Caám caùc tuyeán ñöôøng A2  B2, A3 B3 Phöông phaùp chi phí beù nhaát F \ T 25 38 25 30 ui F \ T 25 38 25 30 ui 30 15 10 9 12 0 6 [5] [25] 8 30 15 10 9 12 0 50 13 M 14 8 4 6 [5] [25] M+6 [20] 14M 1 [30] 50 13 + M  14 8 M10 38 10 11 M 12 1 M14 * [20] M15 [30] [5] [33] 10M 7 38 10  11 + M 12 1 vj 9 10 9 4 [25] [13] 10M M+7 Ta coù ij
ThS. Phạm Trí Cao * Chương 3 03/01/2014 HD: Ví duï 3.10: Baøi toaùn (M) Baøi toaùn (P) F \ T 25 40 15 50 ui F\T 25 40 15 50 50 8 + M 4 M  0 50 8 3 4 7 M-10 [10] [15] [25] 50 1  7 5 3 + 3-M 50 1 7 5 3 * [25] -4 -M+2 [25] 30 2 2 6 4 30 2 2 6 4 2-M -2 [30] -M -2 vj M-2 M 4 M Caám tuyeán A1  B2, A1  B4 F \ T 25 40 15 50 ui  2) Caám khoâng cho phaùt haøng vaøo oâ giaû 50 8 M 4 M 0  Baøi toaùn coù oâ caám coøn xuaát hieän trong tröôøng hôïp [25] [10] [15] [0] baøi toaùn khoâng CBTP: 50 1 7 5 3 3-M  Toång phaùt > toång thu: -M+10 -4 -M+2 [50]  Theâm ñieàu kieän laø moät traïm phaùt naøo ñoù phaûi phaùt heát haøng. 30 2 2 6 4 2-M  Caùch laøm: -M+8 [30] -M -2  OÂ naèm ôû vò trí: doøng traïm phaùt phaûi phaùt heát vj 8 M 4 M haøng, coät traïm thu giaû laø oâ caám. Ta coù ij
ThS. Phạm Trí Cao * Chương 3 03/01/2014 Ví duï 3.11: HD: Caùch 1: F\T 120 130 50 F \ T 120 130 50 (30) ui 100 10 8  12 0 + 0 100 10 8 12 3 [100] 0 M2 150 15 10 14 150 15 10 + 14 M  2 [40] [30] [50] * [30] 80 9 11 12 80 9 11 12 0 4 [80] 7 4 M6 vj 13 8 12 M2 Traïm A2 phaùt heát haøng. F \ T 120 130 50 (30) ui F \ T 120 130 50 (30) ui 100 10 8 12 0 0 100 10 + 8  12 0 0 [40] [30] 0 [30] 3 [70] 0 [30] 150 15 10 14 M 2 150 15  10 + 14 M 2 3 [100] [50] 2 M 80 9 11 12 0 1 * [40] [60] [50] 2 M [80] 4 1 1 80 9 11 12 0 4 vj 10 8 12 0 [80] 7 4 4 Ta coù ij
ThS. Phạm Trí Cao * Chương 3 03/01/2014  Toång phaùt < toång thu: Ví duï 3.12:  Theâm ñieàu kieän laø moät traïm thu naøo ñoù yeâu caàu phaûi thu ñuû haøng. Baøi toaùn (P)  Caùch laøm: F\T 60 60 80 100  OÂ naèm ôû vò trí: doøng traïm phaùt giaû, coät 80 1 7 6 8 traïm thu phaûi thu ñuû haøng laø oâ caám. 60 5 4 6 5  Löu yù: 110 6 3 2 9  Trình töï phaân phoái caùc oâ: oâ thöïc, oâ giaû, oâ caám. Traïm thu B4 phaûi thu ñuû haøng. HD: F \ T 60 60 80 100 ui Caùch 1: Toång phaùt= 200 < toång thu= 230 Baøi toaùn (M) töông öùng 80 1 7 6 8 0 F \ T 60 60 80 100 ui [60] -M+1 -M+1 [20] 80 1 7 6 8 0 60 5 4 6 5 -3 [60] 0 0 [20] -7 -M+1 -M-2 [60] 60 5 4  6 5 + -3 -7 * [30] -3 [30] 110 6 3  2 9 + M-5 110 6 3 2 9 -4 M-10 [30] [80] M-6 -9 [30] [80] -5 (50) 0 0 + 0 M  M-8 (50) 0 0 + 0 M  M-8 M-7 [30] -1 * [20] M-7 M-1 M-2 [50] vj 1 7 6 8 vj 1 -M+8 -M+7 8 18
ThS. Phạm Trí Cao * Chương 3 03/01/2014 F T 60 60 80 100 ui Ví duï 3.13: 80 1 7 6 8 0 Baøi toaùn (P) [60] -5 -5 [20] F\T 60 60 80 100 60 5 4 6 5 -3 80 1 7 6 8 -7 -5 -8 [60] 60 5 4 6 5 110 6 3 2 9 1 110 6 3 2 9 -4 [10] [80] [20] (50) 0 0 0 M -2 -1 [50] -1 -M+6 Caám tuyeán ñöôøng A3  B2. vj 1 2 1 8 Traïm thu B4 phaûi thu ñuû haøng. Ta coù ij =0 ,  i,j : pa ñang xeùt laø patö.  Qua caùch giaûi giaùn tieáp, ta thaáy chæ coù nhöõng gì  Xong thuaät toaùn. lieân quan ñeán cij môùi bò ñoåi daáu, coøn lieân quan  * Coù ij
ThS. Phạm Trí Cao * Chương 3 03/01/2014  B4) Chuyeån sang baûng vaän taûi môùi:  * OÂ ñieàu chænh laø oâ coù  aâm nhoû nhaát. Ví duï 3.14:  rs = min{ij / ij = 0, i,j : pa ñang xeùt toái öu vj 30 24 14 25 fmax = f(X*) = 2575 . Ghi patö cuûa baøi toaùn? 20