第三章运输问题第一节运输问题的数学模型产minz=4x11+12x12+4x13+11x14+2x21+10x22+3x23+9x24+8x31+5x32+11x33+6x34x11+x12+x13+x14=16x21+x22+x23+x24=10x31+x32+x33+x34=22X11+x21+x31=8X12+x22+x32=14X13+x23+x33=12X14+x24+x34=14xij≥0i=1,2,3;j=1,2,3,4例2、有三台机床加工三种零件，计划第i台的生产任务为ai（i=1，2，3）个零件，第j种零件的需求量为bj（j=1，2，3），第i台机床加工第j种零件需要的时间为cij，如表所示。问如何安排任务使总的加工时间最少？解、设xij为第i机床加工第j种零件的数量，则有：在运输问题中，如果总产量等于总销量，即：产销平衡运输问题的数学模型如下：二、运输问题数学模型的特点其系数列向量的结构是：回到例1minz=4x11+12x12+4x13+11x14+2x21+10x22+3x23+9x24+8x31+5x32+11x33+6x34x11+x12+x13+x14=16x21+x22+x23+x24=10x31+x32+x33+x34=22X11+x21+x31=8X12+x22+x32=14X13+x23+x33=12X14+x24+x34=14xij≥0i=1,2,3;j=1,2,3,43、运输问题的解下表中填有数字的格为基变量，它们对应的约束方程组的系数列向量线型无关：下面用例子说明表上作业法的迭代过程。例1某公司有三个生产同类产品的加工厂（产地），生产的产品由四个销售点（销地），各加工工厂的生产量，各销售点的销售量（假定单位均为吨）以及各加工工厂到各销售点的单位运价（元/吨）如下表所示，问产品如何调运才能使总运量最小？上述问题属产销平衡运输问题（为48）现用xij表示由第i个加工厂运往第j个销售点的物品数量，则可得该问题的数学模型如下：一、给出初始方案（初始基可行解)产2、西北角法3、沃格尔法产二、解的最优性检验产2、对偶变量法（位势法)vj对偶变量法（位势法）求检验数是根据对偶理论推导出来的一种方法！minz=其对偶规划为：互补松弛定理：x*，y*分别是P和D的可行解，它们分别是P和D的最优解的充要条件是(Y*A-C)X*+Y*(b-AX*)=0用位势法求检验数的方法和步骤：vj三、方案（解）的改进例3、对例1中最小元素法得到的解进行改进。例3、对例1中最小元素法得到的解进行改进。例3、对例1中最小元素法得到的解进行改进。例3、对例1中最小元素法得到的解进行改进。vj四、几点说明第三节产销不平衡运输问题为借助于产销平衡时的表上作业法求解，可增加一个假想的销地Bn+1，令其销量为bn+1，且：2、当总销量大于总产量时，可类似处理，增加一个假想的产地Am+1它的产量等于：例4、试确定如下运输表总运费最小的调运方案。第四节应用举例公司目前做法-----当前的运输策略：许多年来，公司一直用下面的策略确定需要从每个罐头加工工厂运|送多少罐头食品到各个仓库。当前的运输策略：1．因为在贝林翰·的罐头厂距离仓库最远，所以把它的产品运送到最近的一个仓库。也就是萨克拉门托的那个仓库。如果还有剩余的话，就把它们运送到盐湖城的仓库中去。2．因为在澳尔巴古的仓库距离食品罐头厂最远，所以就要从最近的一个罐头厂（艾尔贝·李的罐头厂）中运送产品到澳尔巴古。如果还有剩余的话，就要运送到赖皮特城的仓库中。3．用尤基尼的罐头厂满足其他仓库的剩余需求。对于即将来临的收获季度，每一个罐头厂的产量都进行了估计，并且每一个仓库都从豌豆罐头总供应量中分配了一定的比例。当前的运输计划如下：P&T公司的单位卡车的运输成本即将来临的季节中，当前运输计划下的总运输成本：总的运输成本=75（464元）＋5（352元）＋65(416元）＋55（690元）十15（388元）＋85（685元）＝165，595（元）改进运输计划!最优解如下************************************起至销点发点1234------------------------------------102005528045003007030总费用为152535300I10.810.9511.1011.25II11.1011.2511.40III11.0011.15IV11.30I10.810.9511.1011.25025IIM11.1011.2511.40035IIIMM11.0011.15030IVMMM11