运筹与优化 (四).ppt

《运筹与优化 (四).ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。

1、征集到的数学规划实用软件MapleMosekXpress1stOptSASMathematicaGurobiCPLEXGLPK网络优化模型问题：网络最小费用流问题网络最大流问题最短路径问题运输问题的重要性：运输是物流系统中的一个必不可少的重要环节，物流系统的节支生效的来源之一是物资的合理运输，即物资应以最佳的方案进行运输。很多实际问题可以转化为运输问题模型。问题运输问题案例一：物资调运问题线性规划模型决策变量：其它的运输问题案例能源运输问题：电力调度问题热源供应由于在一个地区或一个工厂存在若干个供能基地（发电厂），企业如何将

2、这些能源有效、最佳地调配到各个用能单位去，从而最大限度地发挥企业的自身生产潜力和机能，已经逐渐成为各企业极为重视的环节。职工调配问题职工调配问题某钢铁公司动力厂供电车间共有十三个变电所，分布在公司数十里厂区。总共有一百零四名需要通勤的职工，散居在全市各地。不少职工每天上班或舍近去远，或甲乙地对流。不仅浪费了宝贵的时间，增加了负担，又加剧了交通拥挤，厂里还得为此多支出职工通勤费。此问题如能很好解决，对国家、单位、个人都有利。该厂运用运输问题的原理，提出了新的职工分配方案，解决了职工就近上班问题。职工调配问题建模的思路按以下步骤

3、建立模型（1）发点及其容量约束：将职工分散的住地，按就近乘车的原则，合并为十八个点，并逐点求出每个住地的职工数。于是得到第i个住地的职工数ai（i=1、2……18），建立起受住地职工人数约束的条件方程。（2）收点及其容量约束：将十三个变电所按上班终到站合并为八个工作地，并按定员确定每个工作地所需职工数。于是得到第j个工作地所需职工数bj（j=1、2……8），建立起受工作地职工定员约定的条件方程。（3）运费价格：逐个求出第i个住地至第j个工作地单人日通勤费cij。（4）决策变量：设第i个住地应去第j个工作地上班的人数为xij。

4、（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供应量供应地运价需求量需求地675384

5、2759106运输问题的数学规划模型是线性规划运输问题线性规划模型供应地约束需求地约束运输问题的要点：出发地（发点）及其容量约束接收地（收点）及其容量约束已知各个出发地向不同接收地运输的价格决策变量（运输方案）：各个出发地向各个接收地运输的量。目标：运输总费用最小运输问题是特殊的最小费用流问题多发点多收点的运输问题，在引入一个虚拟发点和一个虚拟收点后就可转化为单发点单收点的最小费用流问题。运输问题的最小费用流网络图2321341s2=10s3=15d1=13d2=21d3=9d4=7s125供应地需求地67538427591

6、06OD更一般的网络最小费用流问题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两个经转局其中

7、“O”中的数字为该局的最大处理能力，弧上所标的权值为该线路的最大运输能力。现欲计算此邮运网的最大运输能力，并对结果进行分析，改善网中的薄弱环节，提高该网的最大运能，如图1。两个邮局V1和V2发往T1、T2、T3三地的邮件需经V3和V4两个经转局其中“O”中的数字为该局的最大处理能力，弧上所标的权值为该线路的最大运输能力。现欲计算此邮运网的最大运输能力，并对结果进行分析，改善网中的薄弱环节，提高该网的最大运能，如图1。这个问题属于多收点、多发点的网络最大流问题。首先，虚拟一发点Vs和一收点Vt，将该问题转化为一个收点和发点，如

8、图2所示：其它最大流问题案例公路网络车流量最大化问题供电网络电流量最大化问题物流配送网络流量最大化问题互联网信息流量最大化问题最短路径问题237184566134105275934682求从1到8的最短路径最短路径问题案例：船舶航线问题船舶最佳航线选择问题可以描述为：某船从起始港S出发前往