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

3.1与一般线性规划的数学模型相比，运输问题的数学模型具有什么特征？答：与一般线性规划的数学模型相比，运输问题的数学模型具有如下特征：1.运输问题不象一般线性规划问题那样，线性规划问题有可能有无穷多最优解，运输问题只有有限个最优。2.运输问题约束条件系数矩阵的元素等于0或1；且每一列有两个非零元素。3.运输问题的解的个数不可能大于(m+n-1)个。3.2运输问题的基可行解应满足什么条件?试判断形表3-26和表3-27中给出的调运方案是否作为表上作业法迭代时的基可行解?为什么?2024/5/12 周日1.销地产地B1B2B3B4产量A1A2A30515151015255销量5151510表表3-26解：表解：表3-26产地个数产地个数m=3，销地个数，销地个数n=4，m+n-1=3+4-1=6个，而表个，而表3-26中非零个数的分量为中非零个数的分量为5个个6个，所以表个，所以表3-26不不可作为表上作业法时的基可行解。可作为表上作业法时的基可行解。2024/5/12 周日2.销地产地B1B2B3B4B5产量A1A2A3A4A515090200210300250250805020400500300300100销量24041055033070表表3-27解：表解：表3-27产地个数产地个数m=5，销地个数，销地个数n=5，m+n-1=5+5-1=9个，而表个，而表3-27中非零个数的分量为中非零个数的分量为10个个9个，也不可作为表个，也不可作为表上作业法时的基可行解。上作业法时的基可行解。2024/5/12 周日3.3.3 试对给出运输问题初始基可行解的最小元素法和试对给出运输问题初始基可行解的最小元素法和Vogel法进行比较，分析给出的解之质量不同的原因。法进行比较，分析给出的解之质量不同的原因。解：解：对于任意给出运输问题初始基可行解的最小元素对于任意给出运输问题初始基可行解的最小元素法和法和Vogel法进行比较，分析给出的两种不同的方法求出法进行比较，分析给出的两种不同的方法求出的解确有不同的原因。初看起来，最小元素法十分合理。的解确有不同的原因。初看起来，最小元素法十分合理。但是，有时按某一最小单位运价优先安排物品调运时，但是，有时按某一最小单位运价优先安排物品调运时，却可能导致不得不采用运费很高的其他供销点时，从而却可能导致不得不采用运费很高的其他供销点时，从而使整个运输费用增加。我们称各销售地或供应地的单位使整个运输费用增加。我们称各销售地或供应地的单位运价中找出的最小单位运价和次小单位运价之差为罚数，运价中找出的最小单位运价和次小单位运价之差为罚数，若罚数的值不大，当不能按最小单位运价安排运输时造若罚数的值不大，当不能按最小单位运价安排运输时造成的运费损失不大；但如果罚数很大，不按最小运价组成的运费损失不大；但如果罚数很大，不按最小运价组织运输就会造成很大损失，故应尽量按最小运价安织运输就会造成很大损失，故应尽量按最小运价安2024/5/12 周日4.销地产地B1B2B3B4产量A141468A212508A337514销量656320排运输。这就是最小元素法和沃格尔法质量不同的原因。排运输。这就是最小元素法和沃格尔法质量不同的原因。3.7 表表3-28和表和表3-29分别给出了各产地和各销地的产量分别给出了各产地和各销地的产量和销量，以及各产地至各销地的单位运价，试用表上作业法和销量，以及各产地至各销地的单位运价，试用表上作业法求最优解。求最优解。表3-282024/5/12 周日5.销地产地B1B2B3B4产量A137645A224322A343856销量3332表3-29解：（解：（1）表）表3-28用三种方法计算，用闭回路法检验。用三种方法计算，用闭回路法检验。用最小元素法计算如下表所示用最小元素法计算如下表所示销地产地B1B2B3B4产量A137645A224322A343856销量3332销地产地B1B2B3B4产量A137645A224322A343856销量33322024/5/12 周日6.销地产地B1B2B3B4产量A14513468A25125308A31373514销量656320 最小元素法求解如下：最小元素法求解如下：从上表计算知：从上表计算知：x12=5，x13=3，x21=5，x24=3，x31=1，x33=3。总费用。总费用=513451301335=402024/5/12 周日7.销地产地B1B2B3B4产量A16421468A21325508A33715314销量656320西北解法计算如下：西北解法计算如下：从上表计算知：从上表计算知：x11=6，x12=2，x22=3，x23=5，x33=1，x34=3。总费用。总费用=642132551531=652024/5/12 周日8.销地产地B1B2B3B4产量ui1234A14 513468302A231225308115A3371514224销量6563 用沃格尔法求解如下：用沃格尔法求解如下：列罚数vj121112211311412024/5/12 周日9.从上表计算知：从上表计算知：x12=5，x13=3，x21=3，x23=2，x24=3，x33=1。总费用。总费用=513431253015=35，在上述三种计算方法中，这种方法计算所需运输费用是在上述三种计算方法中，这种方法计算所需运输费用是最省的。但还不知是否最优。现用闭回路法检验如下：最省的。但还不知是否最优。现用闭回路法检验如下：闭回路法检验如下：闭回路法检验如下：2024/5/12 周日10.产地销地B1B2B3B4产量A14513468A231 2 25308A3371514销量6563第一个闭回路第一个闭回路11，走，走4154线路线路11=4-1+5-4=42024/5/12 周日11.产地销地B1B2B3B4产量A14513468A231 2 25308A3371514销量6563第二闭回路第二闭回路14，走，走6054线路线路14=6-0+5-4=72024/5/12 周日12.产地销地B1B2B3B4产量A14513468A231 2 25308A3371514销量6563第三个闭回路第三个闭回路22，走，走2145线路线路22=2-1+4-5=02024/5/12 周日13.产地销地B1B2B3B4产量A14513468A231 2 25308A3371514销量6563第四个闭回路31，走3155线路31=3-1+5-5=22024/5/12 周日14.产地销地B1B2B3B4产量A14513468A231 2 25308A3371514销量6563第五个闭回路32，走7145线路32=7-1+4-5=22024/5/12 周日15.产地销地B1B2B3B4产量A14513468A231 2 25308A3371514销量6563第六个闭回路第六个闭回路34，走，走1550线路线路34=1-5+5-0=1，至此，六个闭回路全部计算完，至此，六个闭回路全部计算完，11=4，14=2，22=0，31=2，32=2，34=1，即全部检验数，即全部检验数均大于或等于均大于或等于0。即用上述三种方法计算中，用沃格尔法。即用上述三种方法计算中，用沃格尔法计算所得结果计算所得结果z*=35为最优解。为最优解。2024/5/12 周日16.解：（解：（2）表）表3-29用三种方法计算，用位势法检验。因用三种方法计算，用位势法检验。因为总产量为总产量=13，总销量，总销量=10，所以该题的总产量总销，所以该题的总产量总销量，所以该题是产销不平衡的问题，故假设一销地量，所以该题是产销不平衡的问题，故假设一销地B5用最小元素法计算如下表所示用最小元素法计算如下表所示销地产地B1B2B3B4产量A137645A224322A343856销量3322表3-292024/5/12 周日17.销地产地B1B2B3B4B5产量A1137614305A22243202A3433281506销量33223最小元素法求解：最小元素法求解：x11=1，x14=1，x15=3，x21=2，x32=3，x33=2，x34=1，总费，总费用用=13143022332815412024/5/12 周日18.销地产地B1B2B3B4B5产量A133276405A221413202A3431825306销量33223西北角法求解：西北角法求解：x11=3，x12=2，x22=1，x23=1，x33=2，x34=2，x35=2，总费，总费用用=33271413182530482024/5/12 周日19.销地产地B1B2B3B4B5产量行罚数ui1234A1237643053111A2242320220A314330825063111销量33223沃格尔法求解：沃格尔法求解：列罚数vj111320211323142141212024/5/12 周日20.x11=2，x15=3，x23=2，x31=1，x32=3，X33=0，x34=2，总费用，总费用=2306302314332535。在最小元素法中，总费用。在最小元素法中，总费用=41，在用西北角，在用西北角法计算中，总费用法计算中，总费用=56，因此用沃格尔法计算所需费用，因此用沃格尔法计算所需费用=35是最小的，但不知是否最优，还要用对偶变量法是最小的，但不知是否最优，还要用对偶变量法（位势法）加以检验。如表（位势法）加以检验。如表3-30所示：所示：产地销地B1B2B3B4B5UiA1230A22A31302vj表3-30位势法检验表3-30位势法检验表3-30位势法检验表3-30位势法检验表3-30位势法检验表3-30位势法检验2024/5/12 周日21.产地销地B1B2B3B4B5产量UiA12-13712=2+1613=-1414=03050A2221=3422=22-13+1224=2025=52-4A31+1433082-15015=061销量33223vj3274-1表表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*=1316301312243315362024/5/12 周日22.经过调整和检验，得到最后一表经过调整和检验，得到最后一表3-30才是本问题的最优解即才是本问题的最优解即z*=36。经检查，沃格尔法计算所得结果经检查，沃格尔法计算所得结果z=35虽然不是最优解，虽然不是最优解，但是比较接近最优解。但是比较接近最优解。2024/5/12 周日23.