运筹与优化 (四)

1、收集数学规划实用软件Maple Mosek Xpress 1st opt SAS Mathematica Gurobi CPLEX GLPK，网络优化模型，问题：网络最小成本流问题，网络最大流问题，最短路径问题，运输问题的重要性：运输是物流系统中不可缺少的重要环节，物流系统有效节约的来源之一是合理的物料运输，即物料应以最佳方案运输。许多实际问题可以转化为运输问题模型。运输问题案例1:材料调度问题、线性规划模型、决策变量、其他运输问题案例、能源运输问题：电力调度问题由于一个地区或一个工厂中有几个能源供应基地(发电厂)，如何有效和优化地将这些能源分配给各个用能单位，从而最大限度地发挥其自身的生产潜

2、力和功能，已逐渐成为企业非常重视的一个关键环节。人员分配问题，人员分配问题，在一个钢铁公司的发电厂的供电车间中有13个变电站，它们分布在公司的工厂区域中几十英里。总共有104名工人需要通勤，分散在城市各处。每天都有许多工人去上班，或离家，或甲乙双方之间的对流.不仅浪费了宝贵的时间，增加了负担，还加剧了交通堵塞，工厂不得不为员工花费更多的通勤费用。如果这个问题能得到很好的解决，将对国家、单位和个人都有好处。根据运输问题的原理，工厂提出了新的员工分配方案，解决了员工就近工作的问题。对员工分配问题建模的思想，按以下步骤建立模型(1)起点及其能力约束：根据就近旅游的原则，将分散的员工住所合并为十八个点

3、，并逐点计算每个住所的员工人数。因此，获得了第I住宅ai(i=1，218)中的雇员数量，并建立了受住宅中雇员数量约束的条件方程。(2)接收点和容量限制：根据工作结束和到达情况，13个变电站将合并为8个工作场所，每个工作场所所需的员工人数将根据配额确定。因此，获得了第j工作场所所需的员工人数bj(j=1，28)，并建立了工作场所员工定额所同意的条件方程。(3)运费价格：逐个计算单人从第六住所到第六工作地点的每日通勤费用。(4)决策变量：设xij为第二居住地第三工作场所应去工作的人数。(5)优化目标：总通勤成本最小。食品公司销售的主要产品之一是糖果。下设三个加工厂，日生产能力分别为：-125吨、S

4、210吨和S315吨。计划将这些糖果运送到四个销售点，日销量分别为d113吨、d221吨、d39吨和d47吨。货运时间表如下。如何最小化总运费？运输问题案例2:货物运输问题，表1:单价表，商店，加工厂，2，3，2，1，3，4，1，运输问题网络图，S2=10，S3=15，D1=13，D2运输问题的数学规划模型是线性规划，运输问题的线性规划模型，供应地的约束，需求地的约束， 运输问题的关键点：出发地点(出发地点)及其容量约束接收地点(接收地点)及其容量约束知道从每个出发地点到不同接收地点的运输的价格决策变量(运输方案):从每个出发地点到每个接收地点的运输量。 目标：总运输成本最小，运输问题是一个特

5、殊的最小成本流问题。引入虚拟出发点和虚拟收货点后，多点多点运输问题可以转化为单点和单点的最小成本流问题。，运输问题的最小成本流网络图，2，3，2，1，3，4，1，S2=10，S3=15，D1=13，D2=21，D3=9，D4=7，S125，供应地B4=3，B3=5，b5=-6，B6=-5，B1=5，c24=5，c46=1，c13=3，c35=2，c56=4，c34=4，c12=6， cij单位流程成本从V1和V2两个邮局发送到T1、T2和T3的邮件需要通过V3和V4传输，其中“o”中的数字是该邮局的最大处理能力，弧线上标记的重量是该线路的最大运输能力。 现在我们要计算这个邮政网络的最大传输容量

6、，并对结果进行分析，以改善薄弱环节，提高这个网络的最大传输容量，如图1所示。从V1和V2两个邮局发往T1、T2和T3的邮件需要通过V3和V4转送，其中“o”表示该邮局的最大处理能力，弧线上标注的重量表示该线路的最大运输能力。现在我们要计算这个邮政网络的最大传输容量，并对结果进行分析，以改善薄弱环节，提高这个网络的最大传输容量，如图1所示。该问题属于具有多个接收点和多个发送点的网络最大流问题。首先，问题通过虚拟起点Vs和Vt转化为接收点和接收点，如图2所示：最大流量问题的其他情况，高速公路网络中交通流量的最大化，供电网络中电流流量的最大化，物流配送网络中交通流量的最大化，互联网信息流的最大化，最

7、短路径问题，2，3，7，1，8，4，5，6，10，5，2，7，5，9，3，4，6，8，2，找到从1到8的最短路径。最短路径问题案例：船舶航线问题，船舶的最佳航线选择问题可以描述为：一艘船舶从出发港S出发到目的港E，船舶在S和E之间航行的路线有很多，这些路线和船舶在路线上称之为港口。那么，从起始端口S到目的端口E，哪条路由最好？最短路径问题案例：邮局(商店、基站)选址问题，它是邮政通信网络的重要组成部分，是联系用户和邮政企业的枢纽。它的设置是直接影响邮件能否在网络中顺利进出和运行的重要因素之一。作为一个外部“窗口”，它关系到邮政行业的声誉，是用户使用邮政服务的物质和技术条件，直接影响到社会和企业

8、的效益。因此，其优化设置已成为邮政通信网络合理规划的重要组成部分。现有区域(可分为六个服务区域)。应在六个服务区中心中的一个设立邮局，邮局的服务区是六个区。根据实际调查分析，发现该地区交通地理条件差异不大。为了方便这六个服务区域的用户使用邮件，从图论的角度来看，建立办公室时主要考虑的是使这六个区域的用户使用邮件的最大行程最短。这将问题转化为从每个服务区中心到邮局的最短路径。表1六个区域的中心距离和可达性表单位：公里，旅行商问题：TSP，城市数：100，旅行商问题是一个特殊的最短路径问题，旅行商问题：“旅行商问题”通常被称为“旅行商问题”，它指的是如何找出当一个推销员想访问多个地方。虽然规则很简单，但是当位置数量增加时，解决它们就变得非常复杂了。许多实际问题可以转化为TSP问题：物流配送问题：一个物流配送公司想沿着最短的路线运送来自N个客户的所有订单。如何确定最短路线？TSP问题是一个NP完全问题。精确算法可以得到最优解，但它只能解决中小型问题。分枝定界算法动态规划启发式算法能够以放弃最优解为代价解决大规模问题。有许多种算法。课后作业。首先，找到一个可以转化为运输问题的实际案例，并将其转化为运输问题模型(即给出运输问题的几个关键点)