运筹与优化2征集到的数学规划实用软件课件.ppt

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