运输问题模型与算法

4运输问题数学模型及其解法,4.1运输问题数学模型,4.2运输问题的求解方法,4.3对解进行检验及改进,4.4运输问题的进一步讨论,4.5应用问题举例,P基变量对应的约束方程组的系数列向量线性无关;解中非零变量Xij的个数不能大于(m+n-1)个;为使迭代求解顺利进行,基变量的个数在迭代过程中保持为(m+n-1)个;基变量的个数远小于决策变量的个数.,4.2运输问题的求解方法,采用表上作业法，称为位势法运算中涉及两个表：运费表和产销平衡表(分配表),运费表,分配表,寻找初始可行解的方法,1、西北角法从x11开始分配，从西北向东南方向逐个分配xij的分配公式,例2,例4.2.1西北角法,2、最低费用法,采用最小费用优先分配的原则,f(x)=121，费用比西北角法低84,3、运费差额法（沃格尔法-Volge）,最小元素法初看十分合理。但是，有时按某一最小单位运价优先安排物品调运时，却可能导致对其它代销点配送时费用更高，从而使总费用增加。对每一个供销地或销售地，均可由它到各销售地到各供应地的单位运价中找出最小单位运价和次小单位运价，并称这两个单位运价之差为该供应地或销售地的罚数。若罚数的值不大，当不能按最小单位运价安排运输时造成的运费损失不大；反之，如果罚数的值很大，不按最小运价组织运输就会造成很大的损失，故应尽量按最小单位运价安排运输。,采用最大差额费用(即利用每行或列中最小费用与次最小之间的差额中选最大)优先分配的原则。,f(x)=98，比最低费用法又低了23,种某种物品先放在A1、A2和A3三个仓库中，再运往使用地B1、B2、B3和B4，其间的距离（或单位运价）如下表所示，各仓库的存量和使用地的需要量也都表示于下表中，试建立使总运输费用最小的运输问题数学模型。用前面讲的三种方法分别求可行解,用上面的三种求下列运输问题的解,4,12,4,11,2,10,3,9,8,5,11,6,表1,用上面的三种求下列运输问题的解,4,12,4,11,2,10,3,9,8,5,11,6,用西北角法求的可行解,表2,4,12,用上面的三种求下列运输问题的解,4,12,4,11,2,10,3,9,8,5,11,6,用最小元素法求的可行解,表3,用上面的三种求下列运输问题的解,4,12,4,11,2,10,3,9,8,5,11,6,用沃尔格法求的可行解,表4,4.3对解的可行性进行检验,运输表中的格子是空的,则代表是非基变量.若存在非基变量的检验数小于零,说明得到的解不是最优解！,运输问题常用的解检验方法有2种：闭回路法；位势法,4,12,4,11,2,10,3,9,8,5,11,6,检验用最小元素法求的可行解（下表）是否最优,表3,4.3.1利用闭回路法检验分配方案是否最优,表3中的可行解用闭回路法计算的检验数,因X23的检验数小于0，表3的调运方案不是最优解,4.3.2利用位势法检验分配方案是否最优,思路：不采用单纯型法，如何获得xij的检验数找到原问题的基础可行解，保持互补松弛条件，求出对应对偶问题的解，若该对偶问题的解非可行，则原问题的解不是最优解；否则，达到最优解,利用位势法检验分配方案是否最优,平衡运输问题数学模型,平衡运输问题的对偶问题,动输问题变量的检验数表示为:,设已得到运输问题的基可行解,其基变量是:,由于基变量的检验数等于0,故对于这组基变量可写出议程组:,可以证明上面的方程有解,且由于对偶变量数比方程数多一个,故解不唯一.称上面方程的解为位势.,对上面的方程组求解,然后计算运输问题的检验数,若有检验数小于零,则原运输问题的解不是最优解.,4.3.3解的改进,运输问题中,若某一非基变量的检验数小于零,说明这个非基变量作为基变量时,运输费用将更小.因而当前解不是最优解.用闭回路法进行调整.,将检验数最小的非基变量作为换入变量,找出它在运输表中的闭回去路,取闭回路中所有偶数点中最小运量,在所有奇数点上都增加这一最小运量,在所有偶数点上增加这一最小运量.,然后,再对调整后的解进行最优性检验,如不是最优解,就重复以上步骤继续进行调整,一直到得出最优解为止.,4.3.4需要说明的几个问题,1)若运输问题的某一可行解有几个非基变量的检验数均为负,在继续进行迭代时,取它们中的任一变量为换入变量均可使目标函数值得到改善,但通常取检验数小于零中最小者对应的变量为换入变量.2)当迭代到运输问题有最优解时,如果有某非基变量的检验数等于零,则说明该运输问题有无穷多最优解.3)当运输问题某部分产地的产量和,与某一部分销地的销量和相等时,在迭代过程中有可能在某个格填入一个运量时需要同时划去运输表的一行和一列,这时就出现了退化.在运输问题中,退化解是时常发生的,为了使一表上作业法的迭代工作进行下去,退化时在同时划去一行或一列的某个格中填入数字0,表示这个格中的变量是取值为0的基变量,使迭代过程中可行解的分量恰好为(m+n-1)个.,4.4运输问题的进一步讨论,4.4.1产销不平衡1)供过于求，即aibj.数学模型为:,为借助于产销平衡时的表上作业法求解,可增加一个假想的销地Bn+1,由于实际上它不存在,因而由产地Ai(i=1,2,m)调运到这个假想销地的物品数量xi,n+1(相当于松驰变量),实际上是就地存贮在Ai的物品数量.就地存贮的物品不经运输,故其单位运费ci,n+1=0(i=1,2,m),令假想销地的销量为bn+1,且,注意相对应的运输表!,4.4.1产销不平衡1)供过于求，即aibj.假想产地Am+1,它的产量等于:,由于这个假想的产地不存在,求出的由它发往各个销地的物品数量xm+1,j(j=1,2,n),实际上是各销地所需物品的欠缺额,显然有:,例某市有三个造纸厂A1、A2、A3，其纸的产量分别为8、5和9个单位。有4个集中用户，其需要量分别是4、3、5和6个单位。由各造纸厂到各用户的单位运输价格如下表所示，请确定总运费最小的调运方案。,假定m个产地A1,A2,Am和n个销地B1,B2,Bn都可以作为中间转运站使用，从而发送物品的地点和接收物品的地点都有m+n个，这就是转运问题。为建立数学模型，令：,4.4.2有转运的运输问题,ai:第i个产地的产量（净供应量）；bj:第j个销地的销量（净需要量）；Xij:由第i个发送地运到第j个接收地的物品数量；cij:由第i个发送地到第j个接收地的单位运价；ti:第i个地点转运物品的数量；ci:第i个地点转运物品的费用。,现将产地和销地统一编号，并把产地排在前面，销地排在后面，则有：,am+1=am+2=am+n=0,b1=b2=bm=0,假定为平衡运输问题，即有,有转运的运输问题,有转运的运输问题的数学模型,将上式中各约束条件中的ti或tj移到等式左侧，然后两侧加上Q并令：有下面的运输表达式：,有转运的运输问题的运量表,有转运的运输问题运价表,例一个运输系统包括了二个产地和、二个销地和及一个中间转运站，各产地的产量和各销地的销量用相应节点处箭线旁的数字表示，节点数字表示期间的运输单价，节点联线上的数字表示期间的运输单价，节点旁的数字为该地的转运单价，试确定最优运输方案。,4.5应用问题举例,由于运输问题的表上作业法,远比一般单纯形法计算简单,因而人们在解决有些实际问题时,常设法将其转化为运输问题的数学模型求解,下面通过几个例子加以说明.,例4.5.1某企业和用户签订了设备交货合同,已知该企业各季度的生产能力，每台设备的生产成本和每季度末的交货量（见下表），若生产出来的设备当季不交货，每台设备每季度需支付保管维护费0.1万元,试问在遵守合同的条件下,企业应如何安排生产计划,才能使年消耗费用最低?,求解步骤:1)设xij表示第i季度生产第j季度交货的设备台数,ai表示第i季度的生产能力,表示bj第j季度的交货量;2)计算成本,第i季度生产第j季度交货的每台设备成本(生产成本+保管成本);3)建立数学模型;4)当ji时,cij是一个充分大的正数,把不平衡运输问题转化为平衡运输问题,设计运输表:,例4.5.2有三个产地A1、A2和A3生产同一种物品，使用者为B1、B2和B3，各产地到各使用者的单位运输价格表示于下表中，这三个使用者的需求量分别为10、4和6个单位。由于销售需要和客观条件的限制，产地A1至少要发出6个单位的产品，它最多只能生产11个单位的产品；A2必须发出7个单位的产品；A3至少要发出4个单位的产品。试根据上述条