Chapter3运输问题(TransportationProblem)从m个发点向n个收点发送某种货物.发点的发量为，收点的收量为。由运往单位货物的运费为，问如何调配，才能使运费最省？表1产销平衡表运输问题的数学模型运输问题的约束方程组系数矩阵及特征表上作业法的基本思路：1确定初始基可行解思路：为了减少运费，应优先考虑单位运价最小(或运距最短)的供销业务，最大限度地满足其供销量。在可供物品已用完的产地或需求已全部满足的销地，以后将不再考虑。然后，在余下的供、销点的供销关系中，继续按上述方法安排调运，直至安排完所有供销任务，得到一个完整的调运方案(完整的解)为止。这样就得到了运输问题的一个初始基可行解(初始调运方案)。由于该方法基于优先满足单位运价(或运距)最小的供销业务，故称为最小元素法。1.最小元素法最小元素法，有时按某一最小单位运价优先安排物品调运时，却可能在其他供销点多花几倍的运费，从而使整个运输费用增加。沃格尔法计算步骤：1)分别算出各行、各列的最小运费与次小运费的差额。2)从行、列中选出差额最大者，选择它所在行、列中的最小元素，进行运量调整。3)对剩余行、列再分别计算各行、列的差额。返回1)、2)。2.伏格尔法1若有两个以上相同的最大差值，可任取其一。2剩下一行或者一列有空格，填数字，不能划掉。3计算行差，列差时，已经划去的列或者行不再考虑。销产销产2.2最优解的判别55检验数表2.位势法定理：运输问题变量xij的检验数位势法求检验数的步骤:2找到最小调整量以后,按照闭回路上的正、负号，分别加上和减去此值，得到新的运输方案。销产销产表上作业法的计算步骤：表上作业法计算中的问题：⑵退化解：※表格中一般要有(m+n-1)个数字格。但有时在分配运量时则需要同时划去一行和一列，这时需要补一个0，以保证有(m+n-1)个数字格作为基变量。一般可在划去的行和列的任意空格处加一个0即可。※利用进基变量的闭回路对解进行调整时，标有负号的最小运量（超过2个最小值）作为调整量θ，选择任意一个最小运量对应的基变量作为换出变量，而经调整后，得到退化解。这时另一个数字格必须填入一个“0”以示它为基变量。销地产地销地产地第三节产销不平衡的运输问题及其求解方法产销不平衡运输问题向产销平衡运输问题的转化设xin+1是产地Ai的储存量，化成标准形产小于销的运输问题：总供应量为19千吨，而总需求量为15千吨需求地生产地假如例2中各产地的蔬菜总产量不是19千吨，而是12千吨，就成了一个供不应求的运输问题。例3设有三个化肥厂供应四个地区的农用化肥。假定等量的化肥在这些地区使用效果相同，已知各化肥厂年产量，各地区年需要量及从各个化肥厂到各地区单位化肥的运价如下表所示，试决定使总运费最省的化肥调拨方案。这是一个产销不平衡的运输问题，总产量160万吨，四个地区的最低需求量为110万吨，最高需求为无限。根据现有产量，第四个地区每年最多能分配到60万吨，这样最高需求为210万吨，大于总产量。为了求得平衡，在产销平衡表中增加一个假想的化肥厂D，其产量为50万吨。由于各个地区的需求量包含两部分，其中最低需求量不能由假想的化肥厂D供应，令运价为M，而另一部分满足或不满足均可以，故也可以由假想的化肥厂供应，令相应运价为0。把需求是两种情况的看成两个地区，得到这个问题的产销平衡表。需求地区化肥厂需求地区化肥厂作业：