运筹学第三章课后习题答案ppt课件

2020/5/3,1,3.1与一般线性规划的数学模型相比，运输问题的数学模型具有什么特征？,答：与一般线性规划的数学模型相比，运输问题的数学模型具有如下特征：1.运输问题不象一般线性规划问题那样，线性规划问题有可能有无穷多最优解，运输问题只有有限个最优。2.运输问题约束条件系数矩阵的元素等于0或1；且每一列有两个非零元素。3.运输问题的解的个数不可能大于(m+n-1)个。,3.2运输问题的基可行解应满足什么条件?试判断形表3-26和表3-27中给出的调运方案是否作为表上作业法迭代时的基可行解?为什么?,2020/5/3,2,表3-26,解：表3-26产地个数m=3，销地个数n=4，m+n-1=3+4-1=6个，而表3-26中非零个数的分量为5个6个，所以表3-26不可作为表上作业法时的基可行解。,2020/5/3,3,表3-27,解：表3-27产地个数m=5，销地个数n=5，m+n-1=5+5-1=9个，而表3-27中非零个数的分量为10个9个，也不可作为表上作业法时的基可行解。,2020/5/3,4,3.3试对给出运输问题初始基可行解的最小元素法和Vogel法进行比较，分析给出的解之质量不同的原因。,解：对于任意给出运输问题初始基可行解的最小元素法和Vogel法进行比较，分析给出的两种不同的方法求出的解确有不同的原因。初看起来，最小元素法十分合理。但是，有时按某一最小单位运价优先安排物品调运时，却可能导致不得不采用运费很高的其他供销点时，从而使整个运输费用增加。我们称各销售地或供应地的单位运价中找出的最小单位运价和次小单位运价之差为罚数，若罚数的值不大，当不能按最小单位运价安排运输时造成的运费损失不大；但如果罚数很大，不按最小运价组织运输就会造成很大损失，故应尽量按最小运价安,2020/5/3,5,排运输。这就是最小元素法和沃格尔法质量不同的原因。,3.7表3-28和表3-29分别给出了各产地和各销地的产量和销量，以及各产地至各销地的单位运价，试用表上作业法求最优解。,表3-28,2020/5/3,6,表3-29,解：（1）表3-28用三种方法计算，用闭回路法检验。用最小元素法计算如下表所示,2020/5/3,7,最小元素法求解如下：,从上表计算知：x12=5，x13=3，x21=5，x24=3，x31=1，x33=3。总费用=513451301335=40,2020/5/3,8,西北解法计算如下：,从上表计算知：x11=6，x12=2，x22=3，x23=5，x33=1，x34=3。总费用=642132551531=65,2020/5/3,9,用沃格尔法求解如下：,2020/5/3,10,从上表计算知：x12=5，x13=3，x21=3，x23=2，x24=3，x33=1。总费用=513431253015=35，在上述三种计算方法中，这种方法计算所需运输费用是最省的。但还不知是否最优。现用闭回路法检验如下：,闭回路法检验如下：,2020/5/3,11,第一个闭回路11，走4154线路,11=4-1+5-4=4,2020/5/3,12,第二闭回路14，走6054线路,14=6-0+5-4=7,2020/5/3,13,第三个闭回路22，走2145线路,22=2-1+4-5=0,2020/5/3,14,第四个闭回路31，走3155线路,31=3-1+5-5=2,2020/5/3,15,第五个闭回路32，走7145线路,32=7-1+4-5=2,2020/5/3,16,第六个闭回路34，走1550线路,34=1-5+5-0=1，至此，六个闭回路全部计算完，11=4，14=2，22=0，31=2，32=2，34=1，即全部检验数均大于或等于0。即用上述三种方法计算中，用沃格尔法计算所得结果z*=35为最优解。,2020/5/3,17,解：（2）表3-29用三种方法计算，用位势法检验。因为总产量=13，总销量=10，所以该题的总产量总销量，所以该题是产销不平衡的问题，故假设一销地B5用最小元素法计算如下表所示,表3-29,2020/5/3,18,最小元素法求解：,x11=1，x14=1，x15=3，x21=2，x32=3，x33=2，x34=1，总费用=1314302233281541,2020/5/3,19,西北角法求解：,x11=3，x12=2，x22=1，x23=1，x33=2，x34=2，x35=2，总费用=3327141318253048,2020/5/3,20,沃格尔法求解：,2020/5/3,21,x11=2，x15=3，x23=2，x31=1，x32=3，X33=0，x34=2，总费用=2306302314332535。在最小元素法中，总费用=41，在用西北角法计算中，总费用=56，因此用沃格尔法计算所需费用=35是最小的，但不知是否最优，还要用对偶变量法（位势法）加以检验。如表3-30所示：,表3-30位势法检验,表3-30位势法检验,表3-30位势法检验,表3-30位势法检验,表3-30位势法检验,表3-30位势法检验,2020/5/3,22,表3-30位势法检验,由13=-1，故知z=35还不是最优解。经上表调整后得：x11=1，x13=1，x15=3，x23=1，x24=1，x31=2，x32=3，x33=0，x34=1，z*=131630131224331536,2020/5/3,2