《网络优化（双语）》教学大纲

《网络优化（双语）》教学大纲课程英文名NetworkOptimization课程代码J0806Y03学分2.5总学时40理论学时32实验/实践学时8课程类别专业课课程性质任选先修课程《运筹与优化》适用专业信息与计算科学、数学与应用数学开课学院理学院一、课程地位与课程目标（一）课程地位本课程是信息与计算科学的专业选修课。网络优化是在生产实践和科学实验中选取最佳决策，研究在一定限制条件下，选取某种方案，以达到最优目标的一门学科，广泛应用于空间科学、军事科学、系统识别、通讯、工程设计、自动控制、经济管理等各个领域，是信息与计算科学专业学生与工程技术人员的一门重要课程。（二）课程目标1.使学生掌握网络优化的基本理论与一般分析方法，掌握基本的英文专业术语与表达；2.提高学生分析网络模型实际问题的思维能力与计算能力，培养学生的应用数学知识解决问题的意识，同时进一步拓宽学生的知识面，培养学生的科学研究能力。二、课程目标达成的途径与方法对课程目标1，以课堂教学为主，结合课堂讨论、课外作业、课后答疑等方法达成。对课程目标2，以上机实践为主，结合小组讨论、实验报告、课外辅导等方法达成。三、课程目标与相关毕业要求的对应关系课程目标课程目标对毕业要求的支撑程度（H、M、L）毕业要求2毕业要求3毕业要求7课程目标1HMH课程目标2HHH注：1.支撑强度分别填写H、M或L（其中H表示支撑程度高、M为中等、L为低）。四、课程主要内容与基本要求第一章

最小树问题了解图论的基本概念；熟练掌握最小树问题的Kruskal算法和Prim算法的矩阵形式；掌握旅行商问题的四种近似算法。第二章运输问题掌握网络单形法；掌握运输问题及其应用；熟练掌握指派问题的匈牙利算法。第三章

最短路问题了解最短路问题的基本概念；熟练掌握最短路问题的Floyd-Warshall算法；熟练掌握中心点和中位点的概念及解法。第四章

最小费用流问题了解最小费用流问题的基本概念；掌握最小费用流问题的网络单形法；了解最大流问题的标号算法。第五章

匹配问题了解基数匹配和赋权匹配问题的基本概念；熟练掌握中国邮递员问题的算法。Chapter1MinimumspanningtreeproblemsUnderstandthebasicconceptofgraphtheory;skillfullymastertheKruskal’salgorithmandthePrim’salgorithminmatrixformfortheminimumspanningtreeproblem;masterthefourheuristicmethodsfortravelingsalesmanproblem.Chapter2TransshipmentproblemsMasterthenetworksimplexmethod;masterthetransportationproblemanditsapplications;skillfullymastertheHungarianmethodforassignmentproblem.Chapter3ShprtestpathproblemsUnderstandthebasicconceptoftheshortestpathproblem;skillfullymastertheFloyd-Warshallmethodfortheshortestpathproblem;skillfullymastertheconceptandmethodofthecenterandmedianofagraph.Chapter4MinimumcostflowproblemsUnderstandthebasicconceptofminimumcostflowproblem;masterthenetworksimplexmethodfortheminimumcostflowproblem;understandthelabelingalgorithmforsolvingthemaximumflowproblem.Chapter5MatchingsingraphsUnderstandthebasicconceptsofthecardinalitymatchingproblemandtheweightedmatchingproblem;skillfullymasterthealgorithmforChinesepostmanproblem.五、课程学时安排章节号教学内容学时数学生任务对应课程目标第一章最小树问题101.完成第1章课外补充练习题第1,2,3,5题；2.在最小树问题与旅行商问题教学内容后安排2课时上机实践。课程目标1,2第二章运输问题101.完成第2章课外补充练习题第1,3,7,10题；2.在运输问题与指派问题教学内容后安排2课时上机实践。课程目标1,2第三章最短路问题81.完成第3章课外补充练习题第1,2,7,8题；2.在最短路问题教学内容后安排2课时上机实践。课程目标1,2第四章最小费用流问题71.完成第4章课外补充练习题第1,2,3,4题；2.在最小费用流与最大流教学内容后安排1课时上机实践。课程目标1,2第五章匹配问题51.完成第5章课外补充练习题第1,4题；2.在匹配问题教学内容后安排1课时上机实践。课程目标1,2六、实践环节及基本要求序号实验项目学时基本要求学生任务实验性质实验类别1NETSOLVE软件求解最小树问题和旅行商问题2掌握最小树问题与旅行商问题的求解方法建立最小树问题与旅行商问题的模型，并用NETSOLVE软件求解。验证性必做2NETSOLVE软件求解运输问题和指派问题2掌握运输问题与指派问题的求解方法建立运输问题与指派问题的模型，并用NETSOLVE软件求解。验证性必做3NETSOLVE软件求解各种点对之间的最短路问题2掌握最短路问题的求解方法建立最短路问题的模型，并用NETSOLVE软件求解。验证性必做4NETSOLVE软件求解最小费用流问题、最大流问题和匹配问题2掌握最小费用流问题、最大流问题及匹配问题的求解方法建立最小费用流问题、最大流问题与匹配问题的模型，并用NETSOLVE软件求解。验证性必做注：1.实验性质指演示性、验证性、设计性、综合性等；2.实验类别指必做、选做等。七、考核方式及成绩评定考核内容考核方式评定标准（依据）占总成绩比例过程考核含到课率、上机实践、平时作业等平时记录、实验成绩30%期末考核闭卷试卷成绩70%考核类别考试成绩登记方式百分制八、推荐教材与主要参考书（一）推荐教材：(1)V．K．Balakrishnan，NetworkOptimization，Chapmam&Hall，1995。(2)D．P．Bertsekas，NetworkOptimization:ContinuousandDiscreteModels，AthenaScientificPublisher，1998。（