运筹03运输问题详解.ppt

产量有上下限的产销不平衡运输问题 解： 设 xij为第 i 季度生产的第 j 季度交货的设备数目，则问题的线性规划模型为： cij = 第 i 季度每台的生产成本 + 0.15?(j-i)（储存、维护等费用）。计算可得： c11 = 9.8 , c12 = 9.95 , c13 = 10.1 , c14 = 10.25 , c22 = 10.5 , c23 = 10.65 , c24 = 10.8 , c33 = 10.3 , c34 = 10.45 , c44 = 10.6 。 于是得到目标函数： Min f = 9.8x11+9.95x12+10.1x13+ 10.25x14 + +10.5x22+10.65x23+10.8x24+10.3x33+ +10.45x34+10.6x44 x11 = 200 x12 + x22 = 300 x13 + x23 + x33 = 500 x14 + x24 + x34 + x44 = 400 交货： 生产： x11 + x12 + x13 + x14 ≤ 500 x22 + x23 + x24 ≤ 700 x33 + x34 ≤ 600 x44 ≤ 200 xij ? 0 i=1,2,3,4 j ? i 由于产大于销，虚构一个销地，可构造下列产销平衡问题: 各季节的生产、交货费用表 交货 生产 第一 季度 第二 季度 第三 季度 第四 季度 虚设 交货 生产 能力 第一季度 9.8 9.95 10.1 10.25 0 500 第二季度 M 10.5 10.65 10.8 0 700 第三季度 M M 10.3 10.45 0 600 第四季度 M M M 10.6 0 200 交货量 200 300 500 400 600 2000 把第 i 季度生产的设备数目看作第 i 个生产厂的产量；把第 j 季度交货的设备数目看作第 j 个销售点的销量；成本加储存、维护等费用看作运费。 * * * 设法转化为标准型 产量大于最小需求；小于最大需求。而标准型是：产量=销量。 处理办法：设想一个虚拟煤矿D，生产50万吨，但这个产量只能供应可有可无的最高需求部分，于是各地的需求也应分为两个部分：基本需求、机动需求 虚拟产量的运输费用为零，但它对于基本需求来讲，运费为无穷大。 1.在作业表上从绝对值最大的负检验数格(k,l)出发,即xkl为起始变量作出闭回路。 2.以空格(k,l)为第一个奇数顶点，沿闭回路的顺（或逆）时针方向依次对顶点编号。 3.在闭回路上的所有偶数顶点中，找出运输量最小的格子，以该格对应的变量为离基变量。 4.调整量 5.将该闭回路上所有奇数顶点处的运输量都增加 所有偶数顶点处的运输量都减去 ij =min{该闭回路中偶数次顶点运输量xij} 闭回路法求调整方案 表上作业法 得到最优方案算出的总运价 分析实际问题 列出产销平衡表 及单位运价表 求检验数 （闭回路法或位势法） 是 确定初始调运方案 （最小元素法 或Vogel法） 找出绝对值最大的负的检验数用闭回路调整，得出新的调运方案 否 循 环 所有检验数≥0 求解 步 骤 表上作业法中需要说明的问题 （1）无穷多最优解 当迭代到运输问题的最优解时，如果有某非基变量的检验数等于零，则说明该运输问题有多重（无穷多）最优解。上面的例题是多解情况 销 产 B1 B2 B3 B4 A1 0 2 A2 2 1 A3 9 12 B1 B2 B3 B4 A1 5 2 A2 3 1 A3 6 3 检验数表 方案表 B1 B2 B3 B4 A1 2 5 0 A2 1 3 A3 6 3 调整方案表 （2）退化 当运输问题某部分产地的产量和，与某一部分销地的销量和相等时，在迭代过程中有可能在某个格填入一个运量时需同时划去运输表的一行和一列，这时就出现了退化。在运输问题中，退化解是时常发生的。为了使