Toán học - Bài toán vận tải
Bạn đang xem 20 trang mẫu của tài liệu "Toán học - Bài toán vận tải", để 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:
- toan_hoc_bai_toan_van_tai.ppt
Nội dung text: Toán học - Bài toán vận tải
- NHÓM I
- BÀI TOÁN VẬN TẢI THÀNHLTHÀNHLẬẬPBÀITOÁNPBÀITOÁN ĐẶC ĐIỂM CỦA BÀI TOÁN VTCĐ PHƯƠNG ÁN CỰC BIÊN CỦA BÀI TOÁN VTCĐ XÂY DỰNG PACB ĐẦU TIÊN PHƯƠNGPHÁPTHẾVỊGIẢIBÀITOÁNVẬNTẢI BÀITOÁNVẬNTẢIKHÔNGCÂNBẰNGTHUPHÁT BÀITOÁNVẬNTẢICÓÔCẤM TRƯỜNGHỢPSUYBIẾN
- BÀI TOÁN VẬN TẢI MMộộttddạạngngđđặặccbibiệệttccủủaabàibàitoántoánQHTTQHTTcócónhinhiềềuuứứngngddụụngng trongtrongththựựccttếếlàlàBàiBàitoántoánvvậậnnttảảii,,ssẽẽđđượượccnghiênnghiênccứứuutrongtrong chchươươngngnàynày..VVềềmmặặttlýlýthuythuyếếtt,,bàibàitoántoánvvậậnnttảảii((đãđãđđượượccgigiớớii thithiệệuukháikháininiệệmmtrongtrongđođoạạnn1.2)1.2)cũngcũnglàlàmmộộttbàibàitoántoánQHTT,QHTT, nênnênchúngchúngtatacũngcũngcócóththểểdùngdùngphphươươngngphápphápđđơơnnhìnhhìnhđđểể gigiảảii..TuyTuynhiênnhiên,,nnếếuudùngdùngthuthuậậtttoántoánđđơơnnhìnhhìnhnhnhưưtrongtrong chchươươngng2,2,khkhốốiillượượngngtínhtínhtoántoánssẽẽrrấấttllớớnnvàvàphphứứccttạạppvìvìssốố ẩẩnnquáquánhinhiềềuu.Do.Docócómmộộttssốốđđặặccđiđiểểmmriêngriêng,,nênnênngngườườiitataxâyxây ddựựngngcáccácphphươươngngphápphápgigiảảiiriêngriêngđđơơnngigiảảnnhhơơnn,,nhanhnhanhhhơơnn chochobàibàitoántoánvvậậnnttảảii..ChChươươngngnàynàyvvẫẫnndùngdùngkýkýhihiệệuu:I={1,2,:I={1,2, ,m} ,m}vàvàJ={1,2, ,n}.J={1,2, ,n}.
- BÀI TOÁN VẬN TẢI 4.1.THÀNHL4.1.THÀNHLẬẬPBÀITOÁNPBÀITOÁN
- BÀI TOÁN VẬN TẢI 4.1.1 Bài toán vận tải cân bằng thu phát Ta có
- BÀI TOÁN VẬN TẢI
- BÀI TOÁN VẬN TẢI 4.1.2 Bài toán không cân bằng thu phát gọi là bài toán dạng mở: 4.1.2.1 Trường hợp 1:
- BÀI TOÁN VẬN TẢI
- BÀI TOÁN VẬN TẢI 4.1.3Địnhlýtồntại: 4.2ĐẶCĐIỂMCỦABÀITOÁNVTCĐ
- BÀI TOÁN VẬN TẢI
- BÀI TOÁN VẬN TẢI
- BÀI TOÁN VẬN TẢI 4.2.1Địnhlý:
- BÀI TOÁN VẬN TẢI Thật vậy, với các số thực thỏa: chúng ta có ngay và từ đó, Dođó,r(A)=m+n-1.
- BÀI TOÁN VẬN TẢI
- BÀI TOÁN VẬN TẢI 4.3 PHƯƠNG ÁN CỰC BIÊN CỦA BÀI TOÁN VTCĐ 4.3.1MôtảbàitoánVTCĐdướidạngbảng:
- BÀI TOÁN VẬN TẢI Thu phát
- BÀI TOÁN VẬN TẢI
- BÀI TOÁN VẬN TẢI 4.3.2Địnhnghĩa:
- BÀI TOÁN VẬN TẢI 4.3.3Bổđề:
- BÀI TOÁN VẬN TẢI
- BÀI TOÁN VẬN TẢI
- BÀI TOÁN VẬN TẢI 4.3.4Địnhlý:
- BÀI TOÁN VẬN TẢI
- BÀI TOÁN VẬN TẢI 4.3.5Địnhnghĩa: 4.3.6Địnhlý:
- BÀI TOÁN VẬN TẢI
- BÀI TOÁN VẬN TẢI Giả sử: từ đây ta lại có một vòng
- BÀI TOÁN VẬN TẢI 4.4 XÂY DỰNG PACB ĐẦU TIÊN:
- BÀI TOÁN VẬN TẢI
- BÀI TOÁN VẬN TẢI
- BÀI TOÁN VẬN TẢI
- BÀI TOÁN VẬN TẢI
- BÀI TOÁN VẬN TẢI
- BÀI TOÁN VẬN TẢI
- BÀITOÁNVẬNTẢI XÂYDXÂYDỰỰNGPHNGPHƯƠƯƠNGÁNĐNGÁNĐẦẦUTIÊNUTIÊN 1.1. PhươngPhương pháppháp gócgóc TâyTây BắcBắc 2.2. PhươngPhương pháppháp phầnphần tửtử nhỏnhỏ nhấtnhất 3.3. PhươngPhương pháppháp FogelsFogels
- BÀITOÁNVẬNTẢI 4.4.1 PHƯƠNG PHÁP GÓC TÂY BẮC Điền dần phương án vận chuyển vào ma trận vận chuyển, bắt đầu từ ô bên trái phía trên. Đặt x11 = min (t1; p1) Nếu t1 > p1 : ta đặt x12 = min (t1 – p1; p2) Nếu t1 < p1 : ta đặt x21 = min (p1 – t1; t2) Theo cách trên ta tiếp tục điền vào các ô của ma trận vận chuyển cho đến khi không còn hàng ở các điểm phát hàng và thoả mãn nhu cầu ở các điểm nhận hàng.
- BÀI TOÁN VẬN TẢI 4.4.1.14.4.1.1ThíThíddụụ::
- BÀI TOÁN VẬN TẢI
- BÀI TOÁN VẬN TẢI
- BÀI TOÁN VẬN TẢI 4.4.2PH4.4.2PHƯƠƯƠNGPHÁPPHNGPHÁPPHẦẦNTNTỬỬNHNHỎỎNHNHẤẤTT
- BÀITOÁNVẬNTẢI Chọn ô cij có giá trị nhỏ nhất trong bảngchi phí vận chuyển. Tính và điền vào ô đó giá trị xij = min (ti,pj). Sau đó, ta không xét hàng hoặc cột có dự trữ đã hết hay nhu cầu đã thoả mãn. Nếu ti = pj thì không xét đồng thời cả cột Bj lẫn hàng Ai. Từ phần còn lại của bảng ta lại chọn ô có giá trị nhỏ nhất và quá trình phân phối tiếp tục cho đến khi thoả mãn nhu cầu ở các điểm tiêu thụ.
- BÀI TOÁN VẬN TẢI 4.4.2.14.4.2.1ThíThíddụụ:: Giải:Ưutỉênphânphốihàngvàoôcócijnhỏnhấttrong mỗihàng. Lầnlượtphânphốihàng,theothứtự,vàocácô:(1,3);(2,1); (1,2);(3,2)và(3,1):
- BÀI TOÁN VẬN TẢI
- BÀI TOÁN VẬN TẢI
- BÀITOÁNVẬNTẢI 4.4.3PH4.4.3PHƯƠƯƠNGPHÁPFOGELSNGPHÁPFOGELS B1:B1: TínhTính độđộ lệchlệch củacủa cáccác hànghàng vàvà cộtcột ĐộĐộ lệchlệch củacủa mỗimỗi hànghàng ((cộtcột)) == chichi phíphí thấpthấp thứthứ nhìnhì trongtrong hànghàng ((cộtcột)) –– chichi phíphí thấpthấp nhấtnhất trongtrong hànghàng ((cộtcột)) ấyấy B2:B2: ChọnChọn hànghàng ((cộtcột)) cócó độđộ lệchlệch lớnlớn nhấtnhất đểđể ưuưu tiêntiên phânphân phốiphối trướctrước TrongTrong hànghàng ((cộtcột)) ấyấy ưuưu tiêntiên phânphân phốiphối tốitối đađa chocho ôô nàonào cócó chichi phíphí nhỏnhỏ nhấtnhất
- BÀITOÁNVẬNTẢI B3B3:: NếuNếu cócó nhiềunhiều hànghàng ((cộtcột)) cócó cùngcùng độđộ lệchlệch lớnlớn nhấtnhất thìthì tata xácxác địnhđịnh ôô trũngtrũng ÔÔ trũngtrũng làlà ôô cócó chichi phíphí nhỏnhỏ nhấtnhất nằmnằm giữagiữa giaogiao củacủa mộtmột hànghàng vàvà mộtmột cộtcột đangđang xétxét đểđể ưuưu tiêntiên phânphân phốiphối chocho ôô nàonào cócó chichi phíphí nhỏnhỏ nhấtnhất trongtrong tấttất cảcả cáccác hànghàng vàvà cộtcột đangđang xétxét B4B4:: SauSau mỗimỗi lầnlần phânphân phốiphối tata xoáxoá hànghàng ((cộtcột)) tươngtương ứngứng vớivới nónó TaTa cócó mộtmột bảngbảng mớimới,, tínhtính lạilại độđộ lệchlệch củacủa cáccác cộtcột trongtrong bảngbảng nàynày,, sửasửa lạilại lượnglượng hànghàng B5B5:: VớiVới bảngbảng còncòn lạilại tiếptiếp tụctục cáccác bướcbước 22 vàvà 33 chocho tớitới khikhi kếtkết thúcthúc
- BÀI TOÁN VẬN TẢI 4.4.3.1Thídụ: Hiệu số lớn nhất là 5 ở hàng 3, nên đầu tiên phân phối cho ô (3,3) với lượng hàng là Không kể đến hàng 3, tính lại các hiệu số chi phí, rồi tiếp tục tìm hiểu số lớn nhất, Lần lượt phân phối hàng, theo thứ tự, vào các ô:
- BÀI TOÁN VẬN TẢI
- BÀI TOÁN VẬN TẢI Giá trị mục tiêu tương ứng là:
- BÀITOÁNVẬNTẢI 4.5PH4.5PHƯƠƯƠNGPHÁPTHNGPHÁPTHẾẾVVỊỊ THUẬT GIẢI Bước 1: Xác định hệ thế vị (ui,vj) Bước 2:Kiểm tra tiêu chuẩn tối ưu Bước 3:Điều chỉnh phương án
- BÀITOÁNVẬNTẢI Bước1:Xácđịnhhệthếvị(ui,vj) TừTừ phươngphương ánán tựatựa banban đầuđầu,, xácxác địnhđịnh hệhệ sốsố thếthế vịvị ((uuii,, vvjj).). HệHệ thếthế vịvị đượcđược tínhtính từtừ cáccác ôô cơcơ sởsở:: uuii ++ vvjj == ccijij ÔÔ cơcơ sởsở làlà nhữngnhững ôô cócó điềnđiền giágiá trịtrị củacủa biếnbiến sốsố kháckhác 0.0. ÔÔ tựtự dodo làlà nhữngnhững ôô còncòn lạilại ChọnChọn mộtmột ẩnẩn chocho giágiá trịtrị bằngbằng 0,0, sausau đóđó xácxác địnhđịnh cáccác ẩnẩn còncòn lạilại
- BÀITOÁNVẬNTẢI Bước2:Kiểmtratiêuchuẩntốiưu Dùng Định lý 4.5.1. Hiển nhiên điều kiện (b) được thoả mãn tại các ô cơ sở, nên chúng ta chỉ cần kiểm tra điều kiện (a) tại các ô phi cơ sở. Với mọi ô (i, j) S, tính đại lượng: ( gọi là ước lượng của ô (i, j) ) ij = ui + vj - cij · Nếu ij 0, với mọi (i, j) S, thì X là một PATƯ. Thuật toán kết thúc. · Nếu có một (i, j) S sao cho ij > 0, thì X không là một PATƯ. Ô (i, j) đó được gọi là ô vi phạm. Chuyển sang bước 3.
- BÀITOÁNVẬNTẢI Giảsử: Xácđịnh ,gọilàlượngđiềuchỉnh.
- BÀITOÁNVẬNTẢI
- BÀITOÁNVẬNTẢI
- BÀITOÁNVẬNTẢI 4.5.3Thídụ:
- BÀITOÁNVẬNTẢI
- BÀITOÁNVẬNTẢI
- BÀITOÁNVẬNTẢI
- BÀITOÁNVẬNTẢI
- BÀITOÁNVẬNTẢI
- BÀITOÁNVẬNTẢI
- BÀITOÁNVẬNTẢI
- BÀITOÁNVẬNTẢI
- BÀITOÁNVẬNTẢI 4.6.BÀITOÁNVẬNTẢIKHÔNGCÂNBẰNGTHUPHÁT: 4.6.1.TRƯỜNGHỢP:
- BÀITOÁNVẬNTẢI
- BÀITOÁNVẬNTẢI
- BÀITOÁNVẬNTẢI
- BÀITOÁNVẬNTẢI Giải. Đâylàmộtbàitoánkhôngcânbằngthuphát,với
- BÀITOÁNVẬNTẢI
- BÀITOÁNVẬNTẢI
- BÀITOÁNVẬNTẢI Kiểmtratiêuchuẩntốiưu: Vì , nên chọn ô (4,5) làm ô điều chỉnh
- BÀITOÁNVẬNTẢI
- BÀITOÁNVẬNTẢI
- BÀITOÁNVẬNTẢI
- BÀITOÁNVẬNTẢI 4.6.2. Trường hợp ĐưavàomộtđiểmthuảoTn +1, với yêu cầu lượng thu tương ứng là và đặt , với mọi ChúngtacóbàitoánVTCĐtươngứnggồmcó mđiểmphátvàn+1điểmthunhưsau:
- BÀITOÁNVẬNTẢI Dùngthuậttoánthếvịđểgiảibàitoánnày. TừmộtPATƯcủanó,loạibỏcácthànhphầnxi,n+1, chúngtacóđượcmộtPATƯcủabàitoánđãcho.
- BÀITOÁNVẬNTẢI 4.7BÀITOÁNVẬNTẢICÓÔCẤM. Trongtrườnghợp,vìmộtlýdonàođó,khôngthểvậnchuyển hàngtừđiểmphátiđếnđiểmthujthìô(i,j)trênbảngtương ứngđượcgọilàmộtôcấm.Khôngđượcphânphốihàngvào ôcấm.Đểgiảiquyếttrườnghợpnày,ngườitagánchiphívận chuyểnởôcấmbằngM>0lớntuỳý,chúngtacómộtbài toánkhácgọilàbàitoán(VM).Dùngthuậttoánthếvịđểgiải bàitoánnày. NếutrongPATƯcủabàitoán(VM),tấtcảcácthànhphần ứngvớiôcấmđềubằng0thìPATƯđócũngchínhlàmột PATƯcủabàitoánbanđầu.
- BÀITOÁNVẬNTẢI NếutrongPATƯcủabàitoán(VM)cómộtthànhphầnứng vớiôcấmkhác0,thìbàitoánbanđầukhôngcóphươngán. 4.8TRƯỜNGHỢPSUYBIẾN TrườnghợpmộtPACBXcó/G(X)/<m+n-1thìX làsuybiến.Khiđó,chúngtaphảibốsungmộtônàođóvào G(X)đểcótậpôcơsởS.Ôbổsungđóphảithoảmãncác yêucầusau: Khôngđượctạothànhvòngvớicácôcơsởđãcó,giúp chúngtatínhđủhệthốngthếvị{ui,vj},vàđặtxij=0vàoô đó.
- BÀITOÁNVẬNTẢI Thídụ:Mộtcôngtycầnvậnchuyểnmộtloạihàngtừ4kho chứahàngđến3cửahàngcủacôngtyđó.Sốlượnghàng hiệncóởcáckho,yêucầucủacáccửahàngvàchiphívận chuyểntừmỗikhođếnmỗicửahàngđượcchotrongbảng sau:
- BÀITOÁNVẬNTẢI Bàitoánđặtralà:Lậpkếhoạchvậnchuyểnhàngsaochocác cửahàngđượcthuđủtheoyêucầuvàtổngchiphívận chuyểnlàthấpnhất. 1)HãytìmmộtPATƯchobàitoánvàchobiếtchiphíthấp nhất. 2)Giảilạicâu(a),nếucóthêmđiềukiện“khohàngthứtư phảipháthếthàng”. Giải.(a)Đâylàmộtbàitoánkhôngcânbằngthuphát,với
- BÀITOÁNVẬNTẢI Đưavàomộtđiểmthuảo,vớiyêucầulượngthu tươngứnglà25,chúngtacóbàitoánVTCĐtươngứng. XâydựngPACBđầutiênbằngphươngphápđường gầnvàtínhhệthốngthếvị.PACBthuđượclàsuybiến,nên chúngtabổsungthêmô(1,1)đểcótậpôcơsởtươngứng. Kếtquảđượctrìnhbàytrongbảng4.15:
- BÀITOÁNVẬNTẢI
- BÀITOÁNVẬNTẢI vàlượngđiềuchỉnhlàq=min{100,35}=35=x43.Saukhiđiều chỉnh,chúngtacóbảngsau:
- BÀITOÁNVẬNTẢI
- BÀITOÁNVẬNTẢI
- BÀITOÁNVẬNTẢI
- BÀITOÁNVẬNTẢI Ôđiềuchỉnhlàô(3,4),lượngđiềuchỉnhlàq=25=x44. Saukhiđiềuchỉnh,chúngtacóbảngsau:
- BÀITOÁNVẬNTẢI
- BÀITOÁNVẬNTẢI
- Xincảmơncácbạnđãtheodõi. Hoàngem-LớpDH7A2-Suphạmtoán ĐạihọcAnGiang