运筹学课件 第三章运输问题

第三章运输问题2/7/20231例、某公司从两个产地A1、A2将物品运往三个销地B1、B2、B3，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示，问：应如何调运可使总运输费用最小？解：产销平衡问题：总产量=总销量设xij为从产地Ai运往销地Bj的运输量，得到下列运输量表：

Minf=6x11+4x12+6x13+6x21+5x22+5x23s.t.x11+x12+x13=200

x21+x22+x23=300

x11+x21=150

x12+x22=150

x13+x23=200xij≥0(i=1、2；j=1、2、3）一运输问题及其数学模型2/7/20232一般运输模型：产销平衡A1、A2、…、Am表示某物资的m个产地；B1、B2、…、Bn表示某物质的n个销地；si表示产地Ai的产量；dj表示销地Bj的销量；cij表示把物资从产地Ai运往销地Bj的单位运价。设xij为从产地Ai运往销地Bj的运输量，得到下列一般运输量问题的模型：mnMinf=cijxiji=1j=1n

s.t.

xij=sii=1,2,…,m

j=1m

xij=djj=1,2,…,ni=1

xij≥0(i=1,2,…,m;j=1,2,…,n)2/7/20233二、运输问题的表上作业法表上作业法是一种求解运输问题的特殊方法，其实质是单纯形法。运输问题都存在最优解。计算过程（假设产销平衡）：1.找出初始基本可行解。对于有m个产地n个销地的产销平衡问题，则有m个关于产量的约束方程和n个关于销量的约束方程。由于产销平衡，其模型最多只有m+n-1个独立的约束方程，即运输问题有m+n-1个基变量。在m×n的产销平衡表上给出m+n-1个数字格，其相对应的调运量的值即为基变量的值。2.求各非基变量的检验数，即检验除了上述m+n-1个基变量以外的空格的检验数判别是否达到最优解，如果已是最优，停止计算，否则转到下一步。3.确定入基变量和出基变量，找出新的基本可行解。在表上用闭回路法调整。4.重复2、3直到得到最优解。2/7/20234三、初始基本可行解的确定1、最低费用法最低费用法是就近供应，即对单位运价最小的变量分配运输量。2/7/202352、运费差额法初看起来，最小元素法十分合理。但是，有时按某一最小单位运价优先安排物品调运时，却可能导致其他的地方多花几倍的费用，从而使整个运输费用增加。对每一个供应地或销售地，均可由它到各销售地或到各供应地的单位运价中找出最小单位运价和次小单位运价，并称这两个单位运价之差为该供应地或销售地的罚数。若罚数的值不大，当不能按最小单位运价安排运输时造成的运费损失不大，2/7/20236反之，如果罚数的值很大，则不按最小运价组织运输就会造成很大损失。故应尽量按最小单位运价安排运输。运费差额法就是基于这种考虑提出来的。运费差额法的计算方法和步骤：

2/7/20237例、2/7/20238四、最优解的判别运用运费差额法，得到上例的初始基本可行解如下：

2/7/20239现用位势法求这个解各非基变量的检验数。由于所有非基变量的检验数全非负，故这个解为最优解。对这个解来说，因若以为换入变量可再得一解，它与上面最优解的目标函数值相等，故它也是一个最优解，即该运输问题有无穷多最优解。五、需要说明的几个问题1、若运输问题的某一基可行解有几个非基变量的检验数均为负。在继续进行迭代时，取它们中的任一变量为换入变量均可使目标函数值得到改善，但通常取中最小者对应的变量为换入变量。2/7/2023102、当迭代到运输问题的最优解时，如果有某非基变量的检验数等于零，则说明该运输问题有多重（无穷多）最优解。3、当运输问题某部分产地的产量和，与某一部分销地的销量和相等时，在迭代过程中有可能在某个格填入一个运量时需同时划去运输表的一行和一列，这时就出现了退化。在运输问题中，退化解是时常发生的。为了使表上作业法的迭代工作进行下去，退化时应在同时划去的一行或一列中的某个格中填入数字0，表示这个格中的变量是取值为0的基变量，使迭代过程中基可行解的分量恰好为m+n-1个。2/7/202311例：某部门有3个生产同类产品的工厂（产地），生产的产品由3个销售点（销地）出售，各工厂的生产量、各销售点的销售量（假定单位均为吨）各工厂到各销售点的单位运价（元/吨）示于下表中。要求研究产品如何调运才能使总运费最小。2/7/202312运用最小元素法，得到上例的初始基本可行解如下：2/7/202313

运用运费差额法，得到上例的初始基本可行解如下：2/7/202314例：某企业有3个生产同类产品的工厂（产地），生产的产品由4个销售点（销地）出售，各工厂的生产量、各销售点的销售量（假定单位均为吨）各工厂到各销售点的单位运价（元/吨）示于下表中。要求研究产品如何调运才能使总运费最小。2/7/202315运用最小元素法，得到上例的初始基本可行解如下：对初始基本可行解进行最优判断

2/7/202316五、解的改进对运输问题的一个解来说，若最优性检验时某非基变量的检验数为负，说明将这个非基变量变为基变量时运费会更小。因而这个解不是最优解，还可以进一步改进。改进的方法是在运输表中找出这个空格对应的闭回路，在满足所有约束条件的前提下，使尽量增大并相应调整此闭回路上其它顶点的运输量，以得到另一个更好的基可行解。1、闭回路的确定方法2/7/202317首先选取某检验数为负数的空格为调入格，即以它对应的非基变量为入基变量。从调入格出发找一条闭回路，闭回路的确定方法为:以调入格为起点，用水平或垂直线向前划，遇到适当数字格则转90。后继续前进，直到回到起始空格为止。2/7/2023182、解的改进解改进的具体步骤为：（1）以为换入变量，找出它在运输表中的闭回路；

（2）以空格为第一个奇数顶点，沿闭回路的顺（或逆）时针方向前进，对闭回路上的顶点依次编号；

（3）在闭回路上的所有偶数顶点中，找出运输量最小的顶点（格子），以该格中的变量为换出变量；2/7/202319（4）以为调整量，将该闭回路上所有奇数顶点处的运输量都增加这一数值，所有偶数顶点处的运输量都减去这一数值，从而得出一新的运输方案，该运输方案的总运费比原运输方案减少，改变量等于然后，再对得到的新解进行最优性检验，如不是最优解，就重复以上步骤继续进行调整，一直到得出最优解为止。2/7/202320对初始基本可行解迭代寻优得到最优解为：2/7/202321运用运费差额法，得到该问题的初始基本可行解如下：2/7/202322练习1、2/7/202323最小运输费用为1502/7/2023242、2/7/202325无穷多最优解,最小运输成本为7225.2/7/202326六、产销不平衡问题的讨论

；增加销地B其运价：c=0，i=1,2,…，m，销量：

2/7/202327

；增加产地A其运价：c=0,j=1,2,…,n,产量：

2/7/202328例、石家庄北方研究院有一、二、三三个区。每年分别需要用煤3000、1000、2000吨，由河北临城、山西盂县两