《網(wǎng)絡(luò)優(yōu)化（雙語(yǔ)）》教學(xué)大綱

《網(wǎng)絡(luò)優(yōu)化（雙語(yǔ)）》教學(xué)大綱課程英文名NetworkOptimization課程代碼J0806Y03學(xué)分2.5總學(xué)時(shí)40理論學(xué)時(shí)32實(shí)驗(yàn)/實(shí)踐學(xué)時(shí)8課程類(lèi)別專(zhuān)業(yè)課課程性質(zhì)任選先修課程《運(yùn)籌與優(yōu)化》適用專(zhuān)業(yè)信息與計(jì)算科學(xué)、數(shù)學(xué)與應(yīng)用數(shù)學(xué)開(kāi)課學(xué)院理學(xué)院一、課程地位與課程目標(biāo)（一）課程地位本課程是信息與計(jì)算科學(xué)的專(zhuān)業(yè)選修課。網(wǎng)絡(luò)優(yōu)化是在生產(chǎn)實(shí)踐和科學(xué)實(shí)驗(yàn)中選取最佳決策，研究在一定限制條件下，選取某種方案，以達(dá)到最優(yōu)目標(biāo)的一門(mén)學(xué)科，廣泛應(yīng)用于空間科學(xué)、軍事科學(xué)、系統(tǒng)識(shí)別、通訊、工程設(shè)計(jì)、自動(dòng)控制、經(jīng)濟(jì)管理等各個(gè)領(lǐng)域，是信息與計(jì)算科學(xué)專(zhuān)業(yè)學(xué)生與工程技術(shù)人員的一門(mén)重要課程。（二）課程目標(biāo)1.使學(xué)生掌握網(wǎng)絡(luò)優(yōu)化的基本理論與一般分析方法，掌握基本的英文專(zhuān)業(yè)術(shù)語(yǔ)與表達(dá)；2.提高學(xué)生分析網(wǎng)絡(luò)模型實(shí)際問(wèn)題的思維能力與計(jì)算能力，培養(yǎng)學(xué)生的應(yīng)用數(shù)學(xué)知識(shí)解決問(wèn)題的意識(shí)，同時(shí)進(jìn)一步拓寬學(xué)生的知識(shí)面，培養(yǎng)學(xué)生的科學(xué)研究能力。二、課程目標(biāo)達(dá)成的途徑與方法對(duì)課程目標(biāo)1，以課堂教學(xué)為主，結(jié)合課堂討論、課外作業(yè)、課后答疑等方法達(dá)成。對(duì)課程目標(biāo)2，以上機(jī)實(shí)踐為主，結(jié)合小組討論、實(shí)驗(yàn)報(bào)告、課外輔導(dǎo)等方法達(dá)成。三、課程目標(biāo)與相關(guān)畢業(yè)要求的對(duì)應(yīng)關(guān)系課程目標(biāo)課程目標(biāo)對(duì)畢業(yè)要求的支撐程度（H、M、L）畢業(yè)要求2畢業(yè)要求3畢業(yè)要求7課程目標(biāo)1HMH課程目標(biāo)2HHH注：1.支撐強(qiáng)度分別填寫(xiě)H、M或L（其中H表示支撐程度高、M為中等、L為低）。四、課程主要內(nèi)容與基本要求第一章

最小樹(shù)問(wèn)題了解圖論的基本概念；熟練掌握最小樹(shù)問(wèn)題的Kruskal算法和Prim算法的矩陣形式；掌握旅行商問(wèn)題的四種近似算法。第二章運(yùn)輸問(wèn)題掌握網(wǎng)絡(luò)單形法；掌握運(yùn)輸問(wèn)題及其應(yīng)用；熟練掌握指派問(wèn)題的匈牙利算法。第三章

最短路問(wèn)題了解最短路問(wèn)題的基本概念；熟練掌握最短路問(wèn)題的Floyd-Warshall算法；熟練掌握中心點(diǎn)和中位點(diǎn)的概念及解法。第四章

最小費(fèi)用流問(wèn)題了解最小費(fèi)用流問(wèn)題的基本概念；掌握最小費(fèi)用流問(wèn)題的網(wǎng)絡(luò)單形法；了解最大流問(wèn)題的標(biāo)號(hào)算法。第五章

匹配問(wèn)題了解基數(shù)匹配和賦權(quán)匹配問(wèn)題的基本概念；熟練掌握中國(guó)郵遞員問(wèn)題的算法。Chapter1MinimumspanningtreeproblemsUnderstandthebasicconceptofgraphtheory;skillfullymastertheKruskal’salgorithmandthePrim’salgorithminmatrixformfortheminimumspanningtreeproblem;masterthefourheuristicmethodsfortravelingsalesmanproblem.Chapter2TransshipmentproblemsMasterthenetworksimplexmethod;masterthetransportationproblemanditsapplications;skillfullymastertheHungarianmethodforassignmentproblem.Chapter3ShprtestpathproblemsUnderstandthebasicconceptoftheshortestpathproblem;skillfullymastertheFloyd-Warshallmethodfortheshortestpathproblem;skillfullymastertheconceptandmethodofthecenterandmedianofagraph.Chapter4MinimumcostflowproblemsUnderstandthebasicconceptofminimumcostflowproblem;masterthenetworksimplexmethodfortheminimumcostflowproblem;understandthelabelingalgorithmforsolvingthemaximumflowproblem.Chapter5MatchingsingraphsUnderstandthebasicconceptsofthecardinalitymatchingproblemandtheweightedmatchingproblem;skillfullymasterthealgorithmforChinesepostmanproblem.五、課程學(xué)時(shí)安排章節(jié)號(hào)教學(xué)內(nèi)容學(xué)時(shí)數(shù)學(xué)生任務(wù)對(duì)應(yīng)課程目標(biāo)第一章最小樹(shù)問(wèn)題101.完成第1章課外補(bǔ)充練習(xí)題第1,2,3,5題；2.在最小樹(shù)問(wèn)題與旅行商問(wèn)題教學(xué)內(nèi)容后安排2課時(shí)上機(jī)實(shí)踐。課程目標(biāo)1,2第二章運(yùn)輸問(wèn)題101.完成第2章課外補(bǔ)充練習(xí)題第1,3,7,10題；2.在運(yùn)輸問(wèn)題與指派問(wèn)題教學(xué)內(nèi)容后安排2課時(shí)上機(jī)實(shí)踐。課程目標(biāo)1,2第三章最短路問(wèn)題81.完成第3章課外補(bǔ)充練習(xí)題第1,2,7,8題；2.在最短路問(wèn)題教學(xué)內(nèi)容后安排2課時(shí)上機(jī)實(shí)踐。課程目標(biāo)1,2第四章最小費(fèi)用流問(wèn)題71.完成第4章課外補(bǔ)充練習(xí)題第1,2,3,4題；2.在最小費(fèi)用流與最大流教學(xué)內(nèi)容后安排1課時(shí)上機(jī)實(shí)踐。課程目標(biāo)1,2第五章匹配問(wèn)題51.完成第5章課外補(bǔ)充練習(xí)題第1,4題；2.在匹配問(wèn)題教學(xué)內(nèi)容后安排1課時(shí)上機(jī)實(shí)踐。課程目標(biāo)1,2六、實(shí)踐環(huán)節(jié)及基本要求序號(hào)實(shí)驗(yàn)項(xiàng)目學(xué)時(shí)基本要求學(xué)生任務(wù)實(shí)驗(yàn)性質(zhì)實(shí)驗(yàn)類(lèi)別1NETSOLVE軟件求解最小樹(shù)問(wèn)題和旅行商問(wèn)題2掌握最小樹(shù)問(wèn)題與旅行商問(wèn)題的求解方法建立最小樹(shù)問(wèn)題與旅行商問(wèn)題的模型，并用NETSOLVE軟件求解。驗(yàn)證性必做2NETSOLVE軟件求解運(yùn)輸問(wèn)題和指派問(wèn)題2掌握運(yùn)輸問(wèn)題與指派問(wèn)題的求解方法建立運(yùn)輸問(wèn)題與指派問(wèn)題的模型，并用NETSOLVE軟件求解。驗(yàn)證性必做3NETSOLVE軟件求解各種點(diǎn)對(duì)之間的最短路問(wèn)題2掌握最短路問(wèn)題的求解方法建立最短路問(wèn)題的模型，并用NETSOLVE軟件求解。驗(yàn)證性必做4NETSOLVE軟件求解最小費(fèi)用流問(wèn)題、最大流問(wèn)題和匹配問(wèn)題2掌握最小費(fèi)用流問(wèn)題、最大流問(wèn)題及匹配問(wèn)題的求解方法建立最小費(fèi)用流問(wèn)題、最大流問(wèn)題與匹配問(wèn)題的模型，并用NETSOLVE軟件求解。驗(yàn)證性必做注：1.實(shí)驗(yàn)性質(zhì)指演示性、驗(yàn)證性、設(shè)計(jì)性、綜合性等；2.實(shí)驗(yàn)類(lèi)別指必做、選做等。七、考核方式及成績(jī)?cè)u(píng)定考核內(nèi)容考核方式評(píng)定標(biāo)準(zhǔn)（依據(jù)）占總成績(jī)比例過(guò)程考核含到課率、上機(jī)實(shí)踐、平時(shí)作業(yè)等平時(shí)記錄、實(shí)驗(yàn)成績(jī)30%期末考核閉卷試卷成績(jī)70%考核類(lèi)別考試成績(jī)登記方式百分制八、推薦教材與主要參考書(shū)（一）推薦教材：(1)V．K．Balakrishnan，NetworkOptimization，Chapmam&Hall，1995。(2)D．P．Bertsekas，NetworkOptimization:ContinuousandDiscreteModels，AthenaScientificPublisher，1998。（