Bài toán vận tải (TS. Nguyễn Công Trí)

Số trang: 17
Mã số: 109723
Loại file: PDF
Nhúng
Toàn màn hình
Thích
/ 17
Sao chép
Đang tải
BẤM ĐỂ XEM THÊM
Thông tin tài liệu
Ngày đăng: 2011-07-21 10:25:40
Các tính chất và tiêu chuẩn tối ưu của bài toán vận tảiCá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ảiThuật giải thế vị cho bài toán vận tải... Ths. Nguyeãn Coâng Tr Ths. Nguyeãn Coâng Tr Ths. Nguyeãn Coâng Tr í í í Copyright 2001 Copyright 2001 Copyright 2001 Ths. Nguyeãn Coâng Tr Ths. Nguyeãn Coâng Tr Ths. Nguyeãn Coâng Tr í í í Copyright 2001 Copyright 2001 Copyright 2001 BA BA Ø Ø I TOA I TOA Ù Ù N VA N VA Ä Ä N TA N TA Û Û I I 1. 1. BA BA Ø Ø I TOA I TOA Ù Ù N VA N VA Ä Ä N TA N TA Û Û I DA I DA Ï Ï NG TO NG TO Å Å NG QUA NG QUA Ù Ù T T (Xem) (Xem) 2. 2. CA CA Ù Ù C T C T Í Í NH CHA NH CHA Á Á T VA T VA Ø Ø TIEÂU CHUA TIEÂU CHUA Å Å N TO N TO Á Á I I Ö Ö U U CU CU Û Û A A BA BA Ø Ø I TOA I TOA Ù Ù N VA N VA Ä Ä N TA N TA Û Û I I (Xem) (Xem)3. 3. CA CA Ù Ù C PH C PH Ö Ö ÔNG PHA ÔNG PHA Ù Ù P TÌM PH P TÌM PH Ö Ö ÔNG A ÔNG A Ù Ù N C N C ÖÏ ÖÏ C C BIEÂN BIEÂN Ñ Ñ A A À À U TIEÂN CU U TIEÂN CU Û Û A BA A BA Ø Ø I TOA I TOA Ù Ù N VA N VA Ä Ä N TA N TA Û Û I I (Xem) (Xem) 4. 4. THUA THUA Ä Ä T GIA T GIA Û Û I THE I THE Á Á VÒ CHO BA VÒ CHO BA Ø Ø I TOA I TOA Ù Ù N VA N VA Ä Ä N TA N TA Û Û I I (Xem) (Xem) 5. 5. CA CA Ù Ù C DA C DA Ï Ï NG KHA NG KHA Ù Ù C CU C CU Û Û A BA A BA Ø Ø I TOA I TOA Ù Ù N VA N VA Ä Ä N TA N TA Û Û I I (Xem) (Xem) 6. 6. BA BA Ø Ø I TA I TA Ä Ä P P (Xem) (Xem) CHÖÔNG 3 NO NO Ä Ä I DUNG BA I DUNG BA Ø Ø I TOA I TOA Ù Ù N VA N VA Ä Ä N TA N TA Û Û I I Gia Gia û û s s öû öû ca ca à à n va n va ä ä n chuye n chuye å å n mo n mo ä ä t loa t loa ï ï i ha i ha ø ø ng ho ng ho ù ù a (xi a (xi maêng, sa maêng, sa é é t the t the ù ù p, ...) t p, ...) t öø öø m m ñ ñ ie ie å å m cung ca m cung ca á á p (tra p (tra ï ï m m pha pha ù ù t), ky t), ky ù ù hie hie ä ä u la u la ø ø A A 1 1 , A , A 2 2 , ..., A , ..., A m m ñ ñ e e á á n n n n ñ ñ ie ie å å m tieâu m tieâu thu thu ï ï (tra (tra ï ï m thu), ky m thu), ky ù ù hie hie ä ä u la u la ø ø B B 1 1 , B , B 2 2 , ..., B , ..., B n n , bie , bie á á t ra t ra è è ng ng (1) (1) So So á á l l ö ö ô ô ï ï ng ha ng ha ø ø ng co ng co ù ù ô ô û û ca ca ù ù c tra c tra ï ï m pha m pha ù ù t A t A 1 1 , A , A 2 2 , ..., , ..., A A m m la la à à n l n l ö ö ô ô ï ï t la t la ø ø a a 1 1 , a , a 2 2 ,..., a ,..., a m m (2) (2) So So á á l l ö ö ô ô ï ï ng ha ng ha ø ø ng ca ng ca à à n ô n ô û û ca ca ù ù c tra c tra ï ï m thu B m thu B 1 1 , B , B 2 2 , ..., , ..., B B n n la la à à n l n l ö ö ô ô ï ï t la t la ø ø b b 1 1 , b , b 2 2 ,..., b ,..., b n n . . (3) (3) Chi ph Chi ph í í va va ä ä n chuye n chuye å å n mo n mo ä ä t t ñ ñ ôn vò ha ôn vò ha ø ø ng ho ng ho ù ù a t a t öø öø tra tra ï ï m pha m pha ù ù t A t A i i ñ ñ e e á á n tra n tra ï ï m thu B m thu B j j la la ø ø c c ij ij . . Haõy la Haõy la ä ä p ke p ke á á hoa hoa ï ï ch va ch va ä ä n ta n ta û û i ha i ha ø ø ng ho ng ho ù ù a sao cho a sao cho to to å å ng chi ph ng chi ph í í va va ä ä n ta n ta û û i tha i tha á á p nha p nha á á t va t va ø ø tho tho û û a maõn yeâu a maõn yeâu ca ca à à u thu u thu – – pha pha ù ù t. t. BA BA Ø Ø I TOA I TOA Ù Ù N VA N VA Ä Ä N TA N TA Û Û I DA I DA Ï Ï NG TO NG TO Å Å NG QUA NG QUA Ù Ù T T MO HÌNH BA MO HÌNH BA Ø Ø I TOA I TOA Ù Ù N VA N VA Ä Ä N TA N TA Û Û I I Ñ Ñ a a ë ë t x t x ij ij la la ø ø so so á á l l ö ö ô ô ï ï ng ha ng ha ø ø ng ca ng ca à à n va n va ä ä n chuye n chuye å å n t n t öø öø tra tra ï ï m m pha pha ù ù t A t A i i ñ ñ e e á á n tra n tra ï ï m thu B m thu B j j . . Ta co Ta co ù ù to to å å ng chi ph ng chi ph í í va va ä ä n ta n ta û û i: i: (1) (1) Tra Tra ï ï m pha m pha ù ù t, pha t, pha ù ù t he t he á á t ha t ha ø ø ng: ng: (2) (2) Tra Tra ï ï m thu, thu m thu, thu ñ ñ u u û û ha ha ø ø ng: ng: (3) (3) Yeâu ca Yeâu ca à à u tra u tra ï ï m pha m pha ù ù t, tra t, tra ï ï m thu m thu ñö ñö ô ô ï ï c tho c tho û û a a ( ( ñ ñ k caân ba k caân ba è è ng thu ng thu – – pha pha ù ù t). t). BA BA Ø Ø I TOA I TOA Ù Ù N VA N VA Ä Ä N TA N TA Û Û I DA I DA Ï Ï NG TO NG TO Å Å NG QUA NG QUA Ù Ù T T 11 min mn ijij ij Zcx 1 ,1, n iji j x aim 1 ,1, m ijj i x bjn 11 mn ij ij ab Va Va ä ä y, moâ h y, moâ h ì ì nh toa nh toa ù ù n cu n cu û û a ba a ba ø ø i toa i toa ù ù n va n va ä ä n ta n ta û û i (BTVT) i (BTVT) da da ï ï ng to ng to å å ng qua ng qua ù ù t nh t nh ö ö sau: sau: T T ì ì m {x m {x ij ij } sao cho: } sao cho: BA BA Ø Ø I TOA I TOA Ù Ù N VA N VA Ä Ä N TA N TA Û Û I DA I DA Ï Ï NG TO NG TO Å Å NG QUA NG QUA Ù Ù T T 11 1 1 11 min ,1, ,1, 0;0;0;0; mn ijij ij n iji j m ijj i mn ijijijij ij Zcx xaim xbjn x cabab BA BA Ø Ø I TOA I TOA Ù Ù N VA N VA Ä Ä N TA N TA Û Û I D I D Ö Ö Ô Ô Ù Ù I DA I DA Ï Ï NG BA NG BA Ø Ø I TOA I TOA Ù Ù N QHTT N QHTT khai trie khai trie å å n BTVT va n BTVT va ø ø xe xe á á p he p he ä ä ra ra ø ø ng buo ng buo ä ä c d c d ö ö ô ô ù ù i da i da ï ï ng ng he he ä ä m + n ph m + n ph ö ö ông tr ông tr ì ì nh cu nh cu û û a m a m n bie n bie á á n nh n nh ö ö sau sau Ky Ky ù ù hie hie ä ä u A u A m+n,m m+n,m n n ma tra ma tra ä ä n he n he ä ä so so á á cu cu û û a hpt treân. a hpt treân. X X T T = (x = (x 11 11 x x 12 12 ... ... x x 1n 1n x x 21 21 x x 22 22 ... x ... x 2n 2n ... x ... x m1 m1 x x m2 m2 ... x ... x mn mn ) la ) la ø ø vectô co vectô co ä ä t go t go à à m m m m n tha n tha ø ø nh pha nh pha à à n; C = (c n; C = (c 11 11 c c 12 12 ... ... c c 1n 1n c c 21 21 c c 22 22 ... c ... c 2n 2n c c m1 m1 c c m2 m2 ... ... c c mn mn ) la ) la ø ø vectô do vectô do ø ø ng ng go go à à m m m m n tha n tha ø ø nh pha nh pha à à n; b n; b T T = (a = (a 1 1 a a 2 2 ... ... a a m m b b 1 1 b b 2 2 ... ... b b n n) ) la la ø ø vectô co vectô co ä ä t go t go à à m m+ n tha m m+ n tha ø ø nh pha nh pha à à n. n. BA BA Ø Ø I TOA I TOA Ù Ù N VA N VA Ä Ä N TA N TA Û Û I DA I DA Ï Ï NG TO NG TO Å Å NG QUA NG QUA Ù Ù T T 11121 1 212222 12 112111 122222 12n n mmmnm mm nnmnn x xxa xxxa xxxa x xxb x xxb x xxb BTVT vie BTVT vie á á t d t d ö ö ô ô ù ù i da i da ï ï ng vectô va ng vectô va ø ø ma tra ma tra ä ä n nh n nh ö ö sau sau Mo Mo ä ä t vectô X tho t vectô X tho û û a (*) va a (*) va ø ø (**) go (**) go ï ï i la i la ø ø ph ph ö ö ông a ông a ù ù n n . . Mo Mo ä ä t P.A t P.A ñ ñ a a ï ï t c t c öï öï c tie c tie å å u th u th ì ì go go ï ï i la i la ø ø P.A.T. P.A.T. Ö Ö cu cu û û a BTVT. a BTVT. Mo Mo ä ä t ph t ph ö ö ông a ông a ù ù n X n X ñö ñö ô ô ï ï c go c go ï ï i la i la ø ø P.A.C.B P.A.C.B khi ca khi ca ù ù c c vectô co vectô co ä ä t A t A j j cu cu û û a ma tra a ma tra ä ä n he n he ä ä so so á á A A öù öù ng vô ng vô ù ù i ca i ca ù ù c c tha tha ø ø nh pha nh pha à à n x n x ij ij 0 la 0 la ø ø ñ ñ o o ä ä c la c la ä ä p tuye p tuye á á n t n t í í nh. nh. Mo Mo ä ä t P.A.C.B cu t P.A.C.B cu û û a BTVT co a BTVT co ù ù nhie nhie à à u nha u nha á á t la t la ø ø m + n m + n – – 1 tha 1 tha ø ø nh pha nh pha à à n d n d ö ö ông. Ne ông. Ne á á u mo u mo ä ä t P.A.C.B cu t P.A.C.B cu û û a BTVT a BTVT co co ù ù ñ ñ u u ù ù ng m + n ng m + n – – 1 tha 1 tha ø ø nh pha nh pha à à n d n d ö ö ông th ông th ì ì ñö ñö ô ô ï ï c c go go ï ï i la i la ø ø khoâng suy bie khoâng suy bie á á n. n. Ng Ng ö ö ô ô ï ï c la c la ï ï i, i, ñö ñö ô ô ï ï c go c go ï ï i la i la ø ø ph ph ö ö ông a ông a ù ù n c n c öï öï c bieân suy bie c bieân suy bie á á n n . . BA BA Ø Ø I TOA I TOA Ù Ù N VA N VA Ä Ä N TA N TA Û Û I DA I DA Ï Ï NG TO NG TO Å Å NG QUA NG QUA Ù Ù T T min * 0** T zCX AXb X ÝØJLÒÙ íæ ÞßH× ÌÑßGÒ Êß\Ò ÌßE× ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ\ ÁÁÁÁÁÁÁÁÁÁÁÁ ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ\ ÁÁÁÁÁÁÁÁÁÁÁÁ ̸­ò Ò¹«§»=² ݱ²¹ Ì®3 ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ\ ÁÁÁÁÁÁÁÁÁÁÁÁ ¸¬¬°æññ²½¬®·ò½±ò½½Nguyeãn Coâng Trí PDF created with pdfFactory Pro trial version www.pdffactory.com B B 1 1 B B 2 2 B B n n T T r r a a ï ï m m t t h h u u B B j j T T r r a a ï ï m m p p h h a a ù ù t t A A i i b b 1 1 b b 2 2 b b n n A A 1 1 c c 1 1 1 1 c c 1 1 2 2 c c 1 1 n n a a 1 1 x x 1 1 1 1 x x 1 1 2 2 x x 1 1 n n A A 2 2 c c 2 2 1 1 c c 2 2 2 2 c c 2 2 n n a a 2 2 x x 2 2 1 1 x x 2 2 2 2 x x 2 2 n n A A m m c c m m 1 1 c c m m 2 2 c c m m n n a a m m x x m m 1 1 x x m m 2 2 x x m m n n MO TA MO TA Û Û BA BA Ø Ø I TOA I TOA Ù Ù N D N D Ö Ö Ô Ô Ù Ù I DA I DA Ï Ï NG BA NG BA Û Û NG VA NG VA Ä Ä N TA N TA Û Û I I (1) (1) Ky Ky ù ù hie hie ä ä u (i, j) la u (i, j) la ø ø oâ treân oâ treân do do ø ø ng i va ng i va ø ø co co ä ä t j t j . . (2) (2) Chi ph Chi ph í í va va ä ä n chuye n chuye å å n c n c ij ij ñö ñö ô ô ï ï c ghi ô c ghi ô û û go go ù ù c treân c treân beân tra beân tra ù ù i cu i ...
— Xem thêm —
Từ khóa:
Bình luận