运筹学 运输问题表上作业法.pptx

《运筹学 运输问题表上作业法.pptx》由会员分享，可在线阅读，更多相关《运筹学 运输问题表上作业法.pptx（59页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、 确定初始方案(初 始 基本可行解)改进调整（换基迭代）否 判定是否 最 优？是结 束最优方案图3-1 运输问题求解思路图第1页/共59页 二、初始方案的确定 1、作业表（产销平衡表）初始方案就是初始基本可行解。将运输问题的有关信息表和决策变量调运量结合在一起构成“作业表”（产销平衡表）。表3-3是两个产地、三个销地的运输问题作业表。第2页/共59页调调 销地销地 运运 量量产地产地 B1 B2 B3 产产 量量 A1 c11 X11 c12 X12 c13 X13 a1 A2 c21 X21 c22 X22 c23 X23 a2 销销 量量 b1 b2 b3表3-3 运输问题作业表（产销平衡

2、表）第3页/共59页其中xij是决策变量，表示待确定的从第i个产地到第j个销地的调运量，cij为从第i个产地到第j个销地的单位运价或运距。2、确定初始方案的步骤：（1）选择一个xij，令xij=minai，bj=将具体数值填入xij在表中的位置；第4页/共59页（2）调整产销剩余数量：从ai和bj中分别减去xij的值，若ai-xij=0，则划去产地Ai所在的行，即该产地产量已全部运出无剩余，而销地Bj尚有需求缺口bj-ai；若bj-xij=0，则划去销地Bj所在的列，说明该销地需求已得到满足，而产地Ai尚有存余量ai-bj；（3）当作业表中所有的行或列均被划去，说明所有的产量均已运到各个销地，

3、需求全部满足，xij的取值构成初始方案。否则，在作业表剩余的格子中选择下一个决策变量，返回步骤（2）。第5页/共59页 按照上述步骤产生的一组变量必定不构成闭回路，其取值非负，且总数是m+n-1个，因此构成运输问题的基本可行解。对xij的选择采用不同的规则就形成各种不同的方法，比如每次总是在作业表剩余的格子中选择运价（或运距）最小者对应的xij，则构成最小元素法，若每次都选择左上角格子对应的xij就形成西北角法（也称左上角法）。第6页/共59页3、举例举例 例3-2 甲、乙两个煤矿供应A、B、C三个城市用煤，各煤矿产量及各城市需煤量、各煤矿到各城市的运输距离见表3-4，求使总运输量最少的调运方

4、案。第7页/共59页表3-4 例3-2有关信息表 450 200 150 100 日销量（需求量）250 75 65 80 乙 200 100 70 90 甲 日产量（供应量）C B A运距 城市煤矿第8页/共59页例3-2 的数学模型第9页/共59页 分别使用最小元素法和西北角法求出初始方案。&最小元素法的基本思想是“就近供应”；&西北角法则不考虑运距（或运价），每次都选剩余表格的左上角（即西北角）元素作为基变量，其它过程与最小元素法相同；第10页/共59页调调 销地销地 运运 量量产地产地 B1 B2 B3 产产 量量 A1 90 X11 70 X12 100 X13 200 A2 80

5、X21 65 X22 75 X23 250 销销 量量 100 150 200 450 用最小元素法确定例3-2初始调运方案 150100100100100100100第11页/共59页 得到初始调运方案为：x11=100，x13=100，x22=150，x23=100 第12页/共59页调调 销地销地 运运 量量产地产地 B1 B2 B3 产产 量量 A1 90 X11 70 X12 100 X13 200 A2 80 X21 65 X22 75 X23 250 销销 量量 100 150 200 450 用西北角法确定例3-2初始调运方案 100100100 50 50200200第13页

6、/共59页 得到初始调运方案为：x11=100，x12=100，x22=50，x23=200 分别判别表（a）、（b）、（c）所给出的调运方案可否作为表上作业法求解时的初始方案，为什么？第14页/共59页表（a）第15页/共59页表（b）第16页/共59页表（c）第17页/共59页三、最优性检验三、最优性检验 检查当前调运方案是不是最优方案的过程就是最优性检验。检查的方法：计算非基变量（未填上数值的格，即空格）的检验数（也称为空格的检验数），若全部大于等于零，则该方案就是最优调运方案，否则就应进行调整。第18页/共59页1、闭回路法 以确定了初始调运方案的作业表为基础，以一个非基变量作为起始顶

7、点，寻求闭回路。该闭回路的特点是：除了起始顶点是非基变量外，其他顶点均为基变量（对应着填上数值的格）。可以证明，如果对闭回路的方向不加区别，对于每一个非基变量而言，以其为起点的闭回路存在且唯一。第19页/共59页 约定作为起始顶点的非基变量为偶数次顶点，其它顶点从1开始顺次排列，那麽，该非基变量xij的检验数：现在，在用最小元素法确定例3-2初始调运方案的基础上，计算非基变量X12的检验数：=（闭回路上偶数次顶点运距或运价之和）-（闭回路上奇数次顶点运距或运价之和）（3-6）第20页/共59页调调 销地销地 运运 量量产地产地 B1 B2 B3 产产 量量 A1 90 X11 70 X12 1

8、00 X13 200 A2 80 X21 65 X22 75 X23 250 销销 量量 100 150 200 450100100100150例例3-23-2初始调运方案中以初始调运方案中以X X1212(X(X2121)为起点的闭回路为起点的闭回路第21页/共59页非基变量X12的检验数：非基变量X21的检验数：=（c12+c23）-（c13+c22）=70+75-（100+65）=-20，=（c21+c13）-（c11+c23）=80+100-（90+75）=15。经济含义：在保持产销平衡的条件下，该非基变量增加一个单位运量而成为基变量时目标函数值的变化量。第22页/共59页2.2.运输

9、问题的特殊解法位势方法 检验数：目标函数的系数减去对偶变量之和第23页/共59页st.供应供应：需求需求：对偶变量 ui对偶变量 vj第24页/共59页st.对偶变量 xij第25页/共59页原问题检验数：ij=cij-(ui+vj)i=1,2,m;j=1,2,n特别对于m+n-1个基变量，有 ij=cij-(ui+vj)=0第26页/共59页2、位势法 以例3-2初始调运方案为例，设置位势变量 和 ，在初始调运方案表的基础上增加一行和一列（见下页表格）。然后构造下面的方程组：（3-7）第27页/共59页例3-2初始调运方案位势变量对应表 调调 销地销地 运运 量量产地产地 B1 B2 B3产

10、产 量量 A1 90 X11 70 X12 100 X13 200 A2 80 X21 65 X22 75 X23 250 销销 量量 100 150 200 450位势变量位势变量vj v1 v2 v3100100100150位势变量 ui u1 u2第28页/共59页方程组的特点：方程个数是m+n-1=2+3-1=4个，位势变量共有m+n=2+3=5个，通常称ui为第i行的位势，称vj为第j列的位势；初始方案的每一个基变量xij对应一个方程-所在行和列对应的位势变量之和等于该基变量对应的运距（或运价）：ui+vj=cij；方程组恰有一个自由变量，可以证明方程组中任意一个变量均可取作自由变量

11、。第29页/共59页 给定自由变量一个值，解方程组式（3-7），即可求得位势变量的一组值，在式（3-7）中，令u1=0，则可解得v1=90，v3=100，u2=-25，v2=90，于是12=c12-（u1+v2）=70-（0+90）=-2021=c21-（u2+v1）=80-（-25+90）=15与前面用闭回路法求得的结果相同。第30页/共59页位势法计算非基变量xij检验数的公式 ij=cij-（ui+vj）（3-8）=（闭回路上偶数次顶点运距或运价之和）-（闭回路上奇数次顶点运距或运价之和）（3-3-6 6）闭回路法计算非基变量xij检验数的公式：复习比较检验数计算的两种方法思考：试解释位

12、势变量的含义（提示：写出运输问思考：试解释位势变量的含义（提示：写出运输问题的对偶问题）题的对偶问题）第31页/共59页 四、方案调整 当至少有一个非基变量的检验数是负值时，说明作业表上当前的调运方案不是最优的，应进行调整。若检验数ij小于零，则首先在作业表上以xij为起始变量作出闭回路，并求出调整量：ij=min该闭回路中奇数次顶点调运量xij第32页/共59页调调 销地销地 运运 量量产地产地 B1 B2 B3 产产 量量 A1 90 X11 70 X12 100 X13 200 A2 80 X21 65 X22 75 X23 250 销销 量量 100 150 200 450100100

13、100150+-继续上例，因继续上例，因 1212=-20=-20，画出以，画出以x x1212为起始变量的闭为起始变量的闭回路回路 第33页/共59页 计算调整量：=Min（100，150）=100。按照下面的方法调整调运量：闭回路上，奇数次顶点的调运量减去，偶数次顶点（包括起始顶点）的调运量加上；闭回路之外的变量调运量不变。得到新的调运方案：第34页/共59页调调 销地销地 运运 量量产地产地 B1 B2 B3 产产 量量 A1 90 X11 70 X12 100 X13 200 A2 80 X21 65 X22 75 X23 250 销销 量量 100 150 200 450100100

14、200 50重复上面的步骤，直至求出最优调运方案：第35页/共59页调调 销地销地 运运 量量产地产地 B1 B2 B3 产产 量量 A1 90 X11 70 X12 100 X13 200 A2 80 X21 65 X22 75 X23 250 销销 量量 100 150 200 450150 50200 50第36页/共59页 结结 果果 最优调运方案是：x11=50，x12=150，x21=50，x23=200 相应的最小总运输量为：Zmin=9050+70150+8050+75200 =34000（吨公里）第37页/共59页课后习题1 求下列运输问题的最优解第38页/共59页退化问题的

15、处理 保证基变量的个数为m+n-1第39页/共59页500000第40页/共59页3.3运输问题的推广一、产销不平衡的运输问题供大于求供不应求增加虚拟销地增加虚拟销地 增加虚拟产地增加虚拟产地 产销平衡的运输问题对应的运距（或运价）？转化第41页/共59页非平衡问题的处理-转换为平衡问题第42页/共59页供过于求的处理供过于求的处理第43页/共59页供不应求的处理供不应求的处理第44页/共59页二、转运问题特点是所调运的物资不是由产地直接运送到销地，而是经过若干中转站送达。求解思路：转化成一个等价的产销平衡运输问题，再用表上作业法求出最优调运方案。如何转化？第45页/共59页第一步，将产地、转

16、运点、销地重新编排，转运点既作为产地又作为销地；第二步，各地之间的运距（或运价）在原问题运距（运价）表基础上进行扩展：从一地运往自身的单位运距（运价）记为零，不存在运输线路的则记为M（一个足够大的正数）；第46页/共59页第三步，由于经过转运点的物资量既是该点作为销地的需求量，又是该点作为产地时的供应量，但事先又无法获取该数量的确切值，因此通常将调运总量作为该数值的上界。对于产地和销地也作类似的处理。第47页/共59页运输问题的推广转运问题第48页/共59页转运问题转运问题-例例生产厂1Denver2Atlanta6Miami5Detroit7Dallas8NewOrleans零售店60040

17、02003003501503236431162543KansasCity4Louisville64批发部第49页/共59页Min Z=2x13+3x14+3x23+x24+2x35+6x36+3x37+6x38+4x45+4x46+6x47+5x48+4x28+x78S.t.x13+x14600 x23+x24+x28400-x13-x23+x35+x36+x37+x38=0-x14-x24+x45+x46+x47+x48=0 x35+x45=200 x36+x46=150 x37+x47-x78=350 x38+x48+x28+x78=300 xij 0for all i,j供应转运需求线性

18、规划模型线性规划模型第50页/共59页转运问题分析与建模要点转运问题分析与建模要点 纯供应节点有供应量Si，无需求量，无转运功能生产厂1Denver60032供应量第51页/共59页纯需求节点无供应量，有需求量dj，无转运功能5Detroit零售店200需求量24第52页/共59页供应节点有供应量，无需求量，具有转运功能生产厂1Denver60032供应量4第53页/共59页需求节点无供应量，有需求量dj，具有转运功能7Dallas350163销售商需求量第54页/共59页纯转运节点无供应量，无需求量，仅具有转运功能236323KansasCity6批发部第55页/共59页一般转运节点有供应量Si，有需求量di，又具有转运功能2633KansasCity56002001需求量供应量第56页/共59页转运问题的应用转运问题的应用生产与库存计划生产与库存计划 (列出线性规划模型列出线性规划模型)给出满足各个季度需求的最优生产、库存计划。第57页/共59页网络模型生产第一季度第二季度600300235第四季度第三季度500400需求第一季度第二季度400500第四季度第三季度40040030.250.250.25生产能力生产需求量第58页/共59页感谢您的观看！第59页/共59页