Báo cáo khoa học: Tiếp cận bài toán quy hoạch tuyến tính thông qua bài toán tìm đường đi ngắn nhất

Báo cáo khoa học: Tiếp cận bài toán quy hoạch tuyến tính thông qua bài toán tìm đường đi ngắn nhất trình bày sơ lược về các phương pháp tối ưu, xây dựng mô hình toán học cho các bài toán tối ưu thực tế và bài toán đường đi có trọng số bé nhất.
Nội dung trích xuất từ tài liệu:
Báo cáo khoa học: Tiếp cận bài toán quy hoạch tuyến tính thông qua bài toán tìm đường đi ngắn nhất TIẾPCẬNBÀITOÁNQUYHOẠCHTUYẾN TÍNHTHÔNGQUABÀITOÁNTÌMĐƯỜNGĐI NGẮNNHẤT TrầnNgọcViệtNCSkhóa20102014 ĐạihọcĐàNẵng 1 Nộidungtrìnhbày Tómtắt Sơlượcvềcácphươngpháptốiưu Xâydựngmôhìnhtoánhọcchocácbàitoán tốiưuthựctế Bàitoánđườngđicótrọngsốbénhất+Bàitoán+Địnhlý+ThuậttoánDijkstratìmđườngđingắnnhất+Hướngtiếpcậnbàitoánquyhoạchtuyếntínhthông quabàitoántìmđườngđingắnnhất Kếtluận 2 2TÓMTẮTKếtquảchínhcủabàibáolànghiêncứumối quanhệgiữabàitoánquyhoạchtuyếntínhvới bàitoánđườngđingắnnhất.Dựatrêncơsởvận dụngthuậttoánDijkstracảitiếnđểtìmđườngđi ngắnnhấtcủacặpđỉnhbấtkìtrênmạngđồthị vàkếthợplýthuyếtđốingẫutrongquyhoạch tuyếntính.Bàibáophântích,chứngminhcác kếtquảđưara.Chươngtrìnhtươngứngcàiđặt bằngCvàchokếtquảchínhxác. 3 31.SơlượcvềcácphươngpháptốiưuTrongthựctếsảnxuấtkinhdoanhchúngta thườngphảigiảiquyếtcácnhiệmvụdẫnđến việctìmgiátrịmaxhoặcmincủamộthàmnào đó.Chẳnghạncầnlậpphươngánsảnxuất,thi côngsaochocóthểđạtđượcmộttrongcácyêu cầusau:+Tổnggiátrịsảnlượnglớnnhất;+Tổnglợinhuậnlớnnhất;+Chiphíthấpnhất;+Cướcphírẻnhất;+Thờigianthựchiệnnhanhnhất;+Tổngvốnđầutưnhỏnhất… 4 4 2.Xâydựngmôhìnhtoánhọcchocácbàitoántốiưu thựctếViệcmôhìnhhoátoánhọcchomộtvấnđềthựctếcóthể chialàmbốnbướcnhưsau:Bước1:Xâydựngmôhìnhđịnhtínhchovấnđềđặtra.Bước2:Xâydựngmôhìnhtoánhọcchovấnđềđangxét. Trongbướcnàyviệcquantrọnglàphảixácđịnhhàm mụctiêuvàcácràngbuộctoánhọc.Bước3:Sửdụngcôngcụtoánhọcđểkhảosát,giảiquyết cácbàitoánhìnhthànhtrongbước2.Bước4:Kiểmđịnhlạicáckếtquảthuđượctrongbước3. 5 53.Bàitoánđườngđicótrọngsốbénhất3.1.Bàitoán.ChođồthịG=(V,E,c)vàhaiđỉnha,z. Tìmđườngđingắnnhất(nếucó)đitừđỉnhađếnđỉnhz trongđồthịG.ĐồthịGđượcgọilàđồthịcótrọngsố nếutrênmỗicạnh(i,j)củađồthịđượcgánmộtsố nguyênkhôngâmc(i,j).Nhãnc(i,j)trêncạnh(i,j)củađồthịthườngbiểudiễn “chiphí”thựctếđểđiquacạnhnày.Độdàiđườngđingắnnhấttừđiđỉnhađếnđỉnhz cònđượcgọilàkhoảngcáchtừđỉnhađếnđỉnhztrong đồthị.Nếukhôngcóđườngđitừađếnzthìđặtkhoảng cáchbằng∞. 6 63.2.Địnhlý.Tạimỗiđỉnhzgiátrịnhãnd(z)cuốicùng(nếucó)chính làđộdàicủađườngđingắnnhấttừđỉnhađếnđỉnhz.Chứngminh.Saukhiđãthựchiệnxongthuậttoántrên,nếugiátrịnhãnd(z)xácđịnhthìtacóđườngđitừđỉnhatớiđỉnhz.Takhôiphụcđườngđitừađếnznhưsau:d(i)+c(i,z)=d(z).Đỉnhinhưthếchắcchắnphảitồntạivìxảyrađẳngthứcởlần gánhoặcgiảmgiátrịnhãnd(j)cuốicùng.Cứtiếptụcnhưthếcho đếnkhigặpđỉnha.Giảsửtanhậnđượcdãycáccạnh:(a,a1),(a1,a2),...,(ak1,z)Tacó:d(a)+c(a,a1)=d(a1)d(a1)+c(a1,a2)=d(a2)d(a2)+c(a2,a3)=d(a3)...................... d (ak −1 ) + c(ak −1 , z ) = d ( z )Cộnglạivếtheovế,tađược:c(a,a1)+c(a1,a2)+c(a2,a3)+...+c(ak1,z)=d(z).Vậynhãnd(z)làđộdàicủađườngđingắnnhất. 7 73.3.ThuậttoánDijkstratìmđườngđingắnnhấtThuậtgiảitìmđườngđingắnnhấttừđỉnh nguồnađếnđỉnhđíchztrongđồthịcótrọng số,vớic(i,j)>0vàđỉnhxsẽmangnhãnL(x). KếtthúcgiảithuậtL(z)chínhlàchiềudàingắn nhấttừađếnz.+Đầuvào.ĐồthịG=(V,E,c)cótrọngsốc(i,j)>0vớimọicạnh,đỉnhnguồnavàđỉnh đíchz.+Đầura.L(z)chiềudàiđườngđingắnnhấttừ đỉnhnguồnađ ...