资源描述
单击此处编辑母版标题样式,*,*,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,征集到的数学规划实用软件,Maple,Mosek,Xpress,1stOpt,SAS,Mathematica,Gurobi,CPLEX,GLPK,网络优化模型,问题：,网络最小费用流问题,网络最大流问题,最短路径问题,运输问题的重要性：,运输是物流系统中的一个必不可少的重要环节，物流系统的节支生效的来源之一是物资的合理运输，即物资应以最佳的方案进行运输。,很多实际问题可以转化为运输问题模型。,问,题,运输问题案例一：,物资调运问题,其它的运输问题案例,能源运输问题：,电力调度问题,热源供应,由于在一个地区或一个工厂存在若干个供能基地（发电厂），企业如何将这些能源有效、最佳地调配到各个用能单位去，从而最大限度地发挥企业的自身生产潜力和机能，已经逐渐成为各企业极为重视的环节。,职工调配问题,职工调配问题,某钢铁公司动力厂供电车间共有十三个变电所，分布在公司数十里厂区。总共有一百零四名需要通勤的职工，散居在全市各地。不少职工每天上班或舍近去远，或甲乙地对流。不仅浪费了宝贵的时间，增加了负担，又加剧了交通拥挤，厂里还得为此多支出职工通勤费。此问题如能很好解决，对国家、单位、个人都有利。,该厂运用运输问题的原理，提出了新的职工分配方案，解决了职工就近上班问题。,职工调配问题建模的思路,按以下步骤建立模型,（1）,发点及其容量约束：,将职工分散的住地，按就近乘车的原则，合并为十八个点，并逐点求出每个住地的职工数。于是得到第,i,个住地的职工数,ai,（i=1、218），建立起受住地职工人数约束的条件方程。,（2）,收点及其容量约束：,将十三个变电所按上班终到站合并为八个工作地，并按定员确定每个工作地所需职工数。于是得到第j个工作地所需职工数,bj,（j=1、28），建立起受工作地职工定员约定的条件方程。,（3）,运费价格：,逐个求出第,i,个住地至第,j,个工作地单人日通勤费,cij,。,（4）,决策变量：,设第,i,个住地应去第,j,个工作地上班的人数为,xij,。,（5）,优化目标：,总通勤费最小。,d,1,d,2,d,3,d,4,S,1,6,7,5,3,S,2,8,4,2,7,S,3,5,9,10,6,表1：单位运价表,门市,加工厂,2,3,2,1,3,4,1,运输问题网络图,s,2,=10,s,3,=15,d,1,=13,d,2,=21,d,3,=9,d,4,=7,s,1,=25,供应量,供应地,运价,需求量,需求地,6,7,5,3,8,4,2,7,5,9,10,6,运输问题线性规划模型,供应地约束,需求地约束,运输问题是特殊的最小费用流问题,多发点多收点的运输问题，在引入一个虚拟发点和一个虚拟收点后就可转化为单发点单收点的最小费用流问题。,运输问题的最小费用流网络图,2,3,2,1,3,4,1,s,2,=10,s,3,=15,d,1,=13,d,2,=21,d,3,=9,d,4,=7,s,1,25,供应地,需求地,6,7,5,3,8,4,2,7,5,9,10,6,O,D,最小费用流的求解算法,转化成线性规划模型求解,图论方法求解,启发式方法求解,网络最大流问题,2,3,5,4,6,7,1,f,f,u,25,=6,u,42,=2,u,45,=4,u,23,=3,u,13,=7,u,34,=4,u,46,=3,u,36,=1,u,65,=7,u,57,=9,u,67,=8,u,12,=8,最大流问题案例：,邮政网络优化,两个邮局V1和V2发往T1、T2、T3三地的邮件需经V3和V4两个经转局其中“O”中的数字为该局的最大处理能力，弧上所标的权值为该线路的最大运输能力。现欲计算此邮运网的最大运输能力，并对结果进行分析，改善网中的薄弱环节，提高该网的最大运能，如图1。,两个邮局V1和V2发往T1、T2、T3三地的邮件需经V3和V4两个经转局其中“O”中的数字为该局的最大处理能力，弧上所标的权值为该线路的最大运输能力。现欲计算此邮运网的最大运输能力，并对结果进行分析，改善网中的薄弱环节，提高该网的最大运能，如图1。,这个问题属于多收点、多发点的网络最大流问题。首先，虚拟一发点Vs和一收点Vt，将该问题转化为一个收点和发点，如图2所示：,最短路径问题,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,求从1到8的最短路径,最短路径问题案例：,船舶航线问题,船舶最佳航线选择问题可以描述为：某船从起始港S出发前往目的港E，S、E两港之间存在多条可供船舶航行的航线，并且这些航线和船舶在航线上的挂靠港或锚地组成了一个交通网络图。那么从起始港S出发前往目的港E，哪一条航线是最佳的航线呢？,最短路径问题案例：,邮政局（店铺、基站）选址问题,邮政局所是邮政通信网的重要组成部分，是联系用户和邮政企业的枢纽。其设置是直接影响邮件能否顺利入网、出网及在网中畅通运行的重要因素之一。它作为对外的“窗口”，关系到邮政行业的信誉，是用户使用邮政业务的物质技术条件，直接影响到社会效益和企业效益。因此，其最优设置成为邮政通信网合理规划的一个重要组成部分。,现有一地区（可划分为6个服务区域），要在这6个服务区域中心中选一处设置一个邮政局所，该局所的服务面积即为这6个区域。根据实际的调查分析，发现该地区交通地理条件相差不大。为了使这6个服务区域的用户用邮方便，从图论的观点出发，在设置该局所时主要考虑的问题是：使6个区域用户用邮时所行的最大距离最短。这就将该问题转为一个求各服务区中心到邮政局所的最短路问题。,旅行商问题:TSP,城市数：100,很多实际问题可以转化为TSP问题：,物流配送问题：,一个物流配送公司，欲将n个客户的订货沿最短路线全部送到。如何确定最短路线？,TSP问题的求解,TSP问题是NP-complete问题。,精确算法可以得到最优解，但只能求解中小规模问题,分支定界算法,动态规划法,启发式算法以放弃最优解为代价，可以求解大规模问题。算法种类很多。,课后作业6,一、找到一个可以转化为运输问题的实际案例，并将其转化为运输问题模型（即给出运输问题的几个要点）。,二、检索阅读文献，了解求解TSP问题的有关算法的概念、分类等，举出至少两种求解TSP问题的启发式算法。,征集,网络优化问题的实际案例,关于课后作业,所有未交的课后作业最后全部钉在一起，外加一个封面，上写姓名、学号、小组，在第十周上课时交给课代表，由课代表一起上交。,
展开阅读全文