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

1、2022-4-1913.1 与一般线性规划的数学模型相比，运输问题的数学模型具有什么特征？答： 与一般线性规划的数学模型相比，运输问题的数学模型具有如下特征：1.运输问题不象一般线性规划问题那样，线性规划问题有可能有无穷多最优解，运输问题只有有限个最优。2.运输问题约束条件系数矩阵的元素等于0或1；且每一列有两个非零元素。3.运输问题的解的个数不可能大于(m+n-1)个。3.2 运输问题的基可行解应满足什么条件?试判断形表3-26和表3-27中给出的调运方案是否作为表上作业法迭代时的基可行解?为什么?销地产地B1B2B3B4产量A1A2A30515151015255销量51515102022-

2、4-192表表3-26解：表解：表3-26产地个数产地个数m=3，销地个数，销地个数n=4，m+n-1=3+4-1=6个，而表个，而表3-26中非零个数的分量为中非零个数的分量为5个个6个，所以表个，所以表3-26不不可作为表上作业法时的基可行解。可作为表上作业法时的基可行解。销地产地B1B2B3B4B5产量A1A2A3A4A515090200210300250250805020400500300300100销量240410550330702022-4-193表表3-27解：表解：表3-27产地个数产地个数m=5，销地个数，销地个数n=5，m+n-1=5+5-1=9个，而表个，而表3-27中非

3、零个数的分量为中非零个数的分量为10个个9个，也不可作为表个，也不可作为表上作业法时的基可行解。上作业法时的基可行解。2022-4-1943.3 试对给出运输问题初始基可行解的最小元素法和试对给出运输问题初始基可行解的最小元素法和Vogel法进行比较，分析给出的解之质量不同的原因。法进行比较，分析给出的解之质量不同的原因。解：解： 对于任意给出运输问题初始基可行解的最小元素对于任意给出运输问题初始基可行解的最小元素法和法和Vogel法进行比较，分析给出的两种不同的方法求出法进行比较，分析给出的两种不同的方法求出的解确有不同的原因。初看起来，最小元素法十分合理的解确有不同的原因。初看起来，最小元

4、素法十分合理。但是，有时按某一最小单位运价优先安排物品调运时。但是，有时按某一最小单位运价优先安排物品调运时，却可能导致不得不采用运费很高的其他供销点时，从，却可能导致不得不采用运费很高的其他供销点时，从而使整个运输费用增加。我们称各销售地或供应地的单而使整个运输费用增加。我们称各销售地或供应地的单位运价中找出的最小单位运价和次小单位运价之差为罚位运价中找出的最小单位运价和次小单位运价之差为罚数，若罚数的值不大，当不能按最小单位运价安排运输数，若罚数的值不大，当不能按最小单位运价安排运输时造成的运费损失不大；但如果罚数很大，不按最小运时造成的运费损失不大；但如果罚数很大，不按最小运价组织运输就

5、会造成很大损失，故应尽量按最小运价安价组织运输就会造成很大损失，故应尽量按最小运价安销地产地B1B2B3B4产量A141468A212508A337514销量6563202022-4-195排运输。这就是最小元素法和沃格尔法质量不同的原因。排运输。这就是最小元素法和沃格尔法质量不同的原因。3.7 表表3-28和表和表3-29分别给出了各产地和各销地的产量分别给出了各产地和各销地的产量和销量，以及各产地至各销地的单位运价，试用表上作业和销量，以及各产地至各销地的单位运价，试用表上作业法求最优解。法求最优解。表3-282022-4-196销地产地B1B2B3B4产量A137645A224322A3

6、43856销量3332表3-29解：（解：（1）表）表3-28用三种方法计算，用闭回路法检验。用三种方法计算，用闭回路法检验。用最小元素法计算如下表所示用最小元素法计算如下表所示销地产地B1B2B3B4产量A137645A224322A343856销量3332销地产地B1B2B3B4产量A137645A224322A343856销量33322022-4-197销地产地B1B2B3B4产量A14 5 13 468A25 1253 08A31 373 5 1 4销量656320 最小元素法求解如下：最小元素法求解如下：从上表计算知：从上表计算知：x12=5，x13=3，x21=5，x24=3，x3

7、1=1，x33=3。总费用。总费用=513451301335=402022-4-198销地产地B1B2B3B4产量A1 6 4 2 1468A21 3 25 5 08A3 371 5 3 1 4销量656320西北解法计算如下：西北解法计算如下：从上表计算知：从上表计算知：x11=6，x12=2，x22=3，x23=5，x33=1，x34=3。总费用。总费用=642132551531=652022-4-199销地产地B1B2B3B4产量ui1234A14 51 3468302A231225308115A337 15 1 4224销量6563 用沃格尔法求解如下：用沃格尔法求解如下：列罚数vj1

8、21112211311412022-4-1910从上表计算知：从上表计算知：x12=5，x13=3，x21=3，x23=2，x24=3，x33=1。总费用。总费用=513431253015=35，在上述三种计算方法中，这种方法计算所需，在上述三种计算方法中，这种方法计算所需运输费用是最省的。但还不知是否最优。现用闭回路法运输费用是最省的。但还不知是否最优。现用闭回路法检验如下：检验如下：闭回路法检验如下：闭回路法检验如下：产地销地B1B2B3B4产量A1 45 13 4 68A23 1 2 2 53 08A3 3 71 5 14销量65632022-4-1911第一个闭回路第一个闭回路11，走

9、，走4154线路线路11=4-1+5-4=4产地销地B1B2B3B4产量A1 45 13 4 68A23 1 2 2 53 08A3 3 71 5 14销量65632022-4-1912第二闭回路第二闭回路14，走，走6054线路线路14=6-0+5-4=7产地销地B1B2B3B4产量A1 45 13 4 68A23 1 2 2 53 08A3 3 71 5 14销量65632022-4-1913第三个闭回路第三个闭回路22，走，走2145线路线路22=2-1+4-5=0产地销地B1B2B3B4产量A1 45 13 4 68A23 1 2 2 53 08A3 3 71 5 14销量656320

10、22-4-1914第四个闭回路31，走3155线路31=3-1+5-5=2产地销地B1B2B3B4产量A1 45 13 4 68A23 1 2 2 53 08A3 3 71 5 14销量65632022-4-1915第五个闭回路32，走7145线路32=7-1+4-5=2产地销地B1B2B3B4产量A1 45 13 4 68A23 1 2 2 53 08A3 3 71 5 14销量65632022-4-1916第六个闭回路第六个闭回路34，走，走1550线路线路34=1-5+5-0=1，至此，六个闭回路全部计算完，至此，六个闭回路全部计算完，11=4，14=2，22=0，31=2，32=2，3

11、4=1，即全部检验数，即全部检验数均大于或等于均大于或等于0。即用上述三种方法计算中，用沃格尔法。即用上述三种方法计算中，用沃格尔法计算所得结果计算所得结果z*=35为最优解。为最优解。2022-4-1917解：（解：（2）表）表3-29用三种方法计算，用位势法检验。因用三种方法计算，用位势法检验。因为总产量为总产量=13，总销量，总销量=10，所以该题的总产量总销，所以该题的总产量总销量，所以该题是产销不平衡的问题，故假设一销地量，所以该题是产销不平衡的问题，故假设一销地B5用最小元素法计算如下表所示用最小元素法计算如下表所示销地产地B1B2B3B4产量A137645A224322A3438

12、56销量3322表3-29销地产地B1B2B3B4B5产量A11 3761 43 05A22 243202A343 32 81 506销量33223 2022-4-1918最小元素法求解：最小元素法求解：x11=1，x14=1，x15=3，x21=2，x32=3，x33=2，x34=1，总费，总费用用=1314302233281541销地产地B1B2B3B4B5产量A13 32 76405A221 41 3202A3431 82 53 06销量33223 2022-4-1919西北角法求解：西北角法求解：x11=3，x12=2，x22=1，x23=1，x33=2，x34=2，x35=2，总费，

13、总费用用=3327141318253048销地产地B1B2B3B4B5产量行罚数ui1234A1237643053111A2242320220A31433 0 825063111销量33223 2022-4-1920沃格尔法求解：沃格尔法求解：列罚数vj111320211323142141212022-4-1921x11=2，x15=3，x23=2，x31=1，x32=3，X33=0，x34=2，总费用，总费用=2306302314332535。在最小元素法中，总费用。在最小元素法中，总费用=41，在用，在用西北角法计算中，总费用西北角法计算中，总费用=56，因此用沃格尔法计算所，因此用沃格尔

14、法计算所需费用需费用=35是最小的，但不知是否最优，还要用对偶变是最小的，但不知是否最优，还要用对偶变量法（位势法）加以检验。如表量法（位势法）加以检验。如表3-30所示：所示：产地销地B1B2B3B4B5UiA1230A22A31302vj表3-30位势法检验表3-30位势法检验表3-30位势法检验表3-30位势法检验表3-30位势法检验表3-30位势法检验产地销地B1B2B3B4B5产量UiA12-1 3712=2 +1 613=-1414=03 050A2221=3422=2 2-1 3+1224=2025=52-4A31+14330 82-1 5 015=061销量33223vj3274-12022-4-1922表表3-30 位势法检验位势法检验由13=-1，故知z=35还不是最优