运筹与优化 (四)

征集到的数学规划实用软件MapleMosekXpress1stOptSASMathematicaGurobiCPLEXGLPK网络优化模型问题：网络最小费用流问题网络最大流问题最短路径问题运输问题的重要性：运输是物流系统中的一个必不可少的重要环节，物流系统的节支生效的来源之一是物资的合理运输，即物资应以最佳的方案进行运输。很多实际问题可以转化为运输问题模型。设要从甲地调出物质2000吨，从乙地调出物质1100吨，分别供给A地1700吨、B地1100吨、C地200吨、D地100吨。已知每吨运费(单位百元)如表所示：假定运费与运量成正比，问怎样才能找出运费最省的调拨计划?ABCD甲地2125715乙地51513715问题运输问题案例一：物资调运问题•线性规划模型2423222114131211153751511572521minxxxxxxxx111213142122232411211222132314241112131421222324200011001700..1100200100,,,,,,,0xxxxxxxxxxstxxxxxxxxxxxxxx决策变量：1112131421222324(,,,,,,,)Txxxxxxxxx其它的运输问题案例能源运输问题：电力调度问题热源供应由于在一个地区或一个工厂存在若干个供能基地（发电厂），企业如何将这些能源有效、最佳地调配到各个用能单位去，从而最大限度地发挥企业的自身生产潜力和机能，已经逐渐成为各企业极为重视的环节。职工调配问题职工调配问题某钢铁公司动力厂供电车间共有十三个变电所，分布在公司数十里厂区。总共有一百零四名需要通勤的职工，散居在全市各地。不少职工每天上班或舍近去远，或甲乙地对流。不仅浪费了宝贵的时间，增加了负担，又加剧了交通拥挤，厂里还得为此多支出职工通勤费。此问题如能很好解决，对国家、单位、个人都有利。该厂运用运输问题的原理，提出了新的职工分配方案，解决了职工就近上班问题。职工调配问题建模的思路按以下步骤建立模型（1）发点及其容量约束：将职工分散的住地，按就近乘车的原则，合并为十八个点，并逐点求出每个住地的职工数。于是得到第i个住地的职工数ai（i=1、2……18），建立起受住地职工人数约束的条件方程。（2）收点及其容量约束：将十三个变电所按上班终到站合并为八个工作地，并按定员确定每个工作地所需职工数。于是得到第j个工作地所需职工数bj（j=1、2……8），建立起受工作地职工定员约定的条件方程。（3）运费价格：逐个求出第i个住地至第j个工作地单人日通勤费cij。（4）决策变量：设第i个住地应去第j个工作地上班的人数为xij。（5）优化目标：总通勤费最小。某食品公司经销的主要产品之一是糖果。它下面设有三个加工厂，每天的生产量分别为:S1－25吨，S2－10吨，S3－15吨。拟把这些糖果运往四个门市销售，各门市的每日销量为d1－13吨，d2－21吨，d3－9吨，d4－7吨。运价表如下，问：如何运送使总运费最小？运输问题案例二：货物运输问题d1d2d3d4S16753S28427S359106表1：单位运价表门市加工厂2321341运输问题网络图s2=10s3=15d1=13d2=21d3=9d4=7s1=25供应量供应地运价需求量需求地6753842759106运输问题的数学规划模型是线性规划运输问题线性规划模型11121314212223243132333411121314212223243132333411213112223213233314243411121314212223min=6+7+5+3+8+4+2+7+5+9+10+6+++=25+++=10+++=15++=13++=21++=9++=17zxxxxxxxxxxxxs.t.xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx24313233340xxxx供应地约束需求地约束运输问题的要点：出发地（发点）及其容量约束接收地（收点）及其容量约束已知各个出发地向不同接收地运输的价格决策变量（运输方案）：各个出发地向各个接收地运输的量。目标：运输总费用最小运输问题是特殊的最小费用流问题多发点多收点的运输问题，在引入一个虚拟发点和一个虚拟收点后就可转化为单发点单收点的最小费用流问题。运输问题的最小费用流网络图2321341s2=10s3=15d1=13d2=21d3=9d4=7s125供应地需求地6753842759106OD更一般的网络最小费用流问题b2=-2b4=3b3=5b5=-6b6=-5b1=5c24=5c46=1c13=3c35=2c56=4c34=4c12=6234561需求节点供应节点cij单位流量的费用最小费用流的求解算法转化成线性规划模型求解图论方法求解启发式方法求解网络最大流问题2354671ffu25=6u42=2u45=4u23=3u13=7u34=4u46=3u36=1u65=7u57=9u67=8u12=8最大流问题案例：邮政网络优化两个邮局V1和V2发往T1、T2、T3三地的邮件需经V3和V4两个经转局其中“O”中的数字为该局的最大处理能力，弧上所标的权值为该线路的最大运输能力。现欲计算此邮运网的最大运输能力，并对结果进行分析，改善网中的薄弱环节，提高该网的最大运能，如图1。两个邮局V1和V2发往T1、T2、T3三地的邮件需经V3和V4两个经转局其中“O”中的数字为该局的最大处理能力，弧上所标的权值为该线路的最大运输能力。现欲计算此邮运网的最大运输能力，并对结果进行分析，改善网中的薄弱环节，提高该网的最大运能，如图1。这个问题属于多收点、多发点的网络最大流问题。首先，虚拟一发点Vs和一收点Vt，将该问题转化为一个收点和发点，如图2所示：其它最大流问题案例公路网络车流量最大化问题供电网络电流量最大化问题物流配送网络流量最大化问题互联网信息流量最大化问题最短路径问题237184566134105275934682求从1到8的最短路径最短路径问题案例：船舶航线问题船舶最佳航线选择问题可以描述为：某船从起始港S出发前往目的港E，S、E两港之间存在多条可供船舶航行的航线，并且这些航线和船舶在航线上的挂靠港或锚地组成了一个交通网络图。那么从起始港S出发前往目的港E，哪一条航线是最佳的航线呢？最短路径问题案例：邮政局（店铺、基站）选址问题邮政局所是邮政通信网的重要组成部分，是联系用户和邮政企业的枢纽。其设置是直接影响邮件能否顺利入网、出网及在网中畅通运行的重要因素之一。它作为对外的“窗口”，关系到邮政行业的信誉，是用户使用邮政业务的物质技术条件，直接影响到社会效益和企业效益。因此，其最优设置成为邮政通信网合理规划的一个重要组成部分。现有一地区（可划分为6个服务区域），要在这6个服务区域中心中选一处设置一个邮政局所，该局所的服务面积即为这6个区域。根据实际的调查分析，发现该地区交通地理条件相差不大。为了使这6个服务区域的用户用邮方便，从图论的观点出发，在设置该局所时主要考虑的问题是：使6个区域用户用邮时所行的最大距离最短。这就将该问题转为一个求各服务区中心到邮政局所的最短路问题。表16个区域中心间距及可达情况表单位：kmDijV1V2V3V4V5V6V1034V230546V345025V4403V562304V6540旅行商问题:TSP城市数：100旅行商问题是特殊的最短路径问题旅行商问题（TSP:TravelingSalerProblem):“旅行商问题”常被称为“旅行推销员问题”，是指一名推销员要拜访多个地点时，如何找到在拜访每个地点一次后再回到起点的最短路径。规则虽然简单，但在地点数目增多后求解却极为复杂。很多实际问题可以转化为TSP问题：物流配送问题：一个物流配送公司，欲将n个客户的订货沿最短路线全部送到。如何确定最短路线？TSP问题的求解TSP问题是NP-complete问题。精确算法可以得到最优解，但只能求解中小规模问题分支定界算法动态规划法启发式算法以放弃最优解为代价，可以求解大规模问题。算法种类很多。课后作业6一、找到一个可以转化为运输问题的实际案例，并将其转化为运输问题模型（即给出运输问题的几个要点）。二、检索阅读文献，了解求解TSP问题的有关算法的概念、分类等，举出至少两种求解TSP问题的启发式算法。征集网络优化问题的实际案例关于课后作业所有未交的课后作业最后全部钉在一起，外加一个封面，上写姓名、学号、小组，在第十周上课时交给课代表，由课代表一起上交。