第三章 习题解第章 习题解.doc

第三章 运输问题习题解答 3.1 与一般线性规划的数学模型相比，运输问题的数学模型具有什么特征？ 答：（1）约束条件系数矩阵的元素只有0或1； （2）约束条件系数矩阵的每一列有两个非零元素。这对应于每一个变量在前m个约束方程中出现一次，在后n个约束方程中出现一次； （3）所有约束条件都是等式约束； （4）各产地产量之和等于各销地销量之和。 3.2运输问题的基可行解应满足什么条件？将其填入运输表中时有什么体现？并说明在迭代计算过程中对它的要求。 答：（1）基可行解中非零分量xij的数目不能大于（m+n-1）个，原因是运输问题中虽有（m+n）个约束条件，但由于总产量等于总销量，故只有（m+n-1）个约束条件是线性独立的。 （2）将其填入运输表中，有数字的格子的个数为（m+n-1）个。 （3）在迭代过程中，始终保持数字格的个数为（m+n-1）个。 3.3 试对给出运输问题初始基可行解的西北角法、最小元素法和vogel法进行比较，分析给出的解之质量不同的原因。 答：三种方法给出的初始基可行解，以沃格尔法给出的解的目标函数值最小，质量最好；最小元素法次之，西北角法解的目标函数值最大，质量最差。 西北角法优先满足运输表中西北角（即左上角）上空格的供销需求，一般不能得到最优解，目标函数值较大；最小元素法优先考虑单位运价最小的供销业务，最大限度地满足其供销量。但是，有时按某一最小单位运价优先安排物品调运时，可能导致不得不采用运费很高的供销点，从而使整个运输费用增加。而沃格法是按罚安排运输的，优先保证罚数大的供销业务，避免了罚数的值很大，不按最小运价组织运输造成的大损失。 3.4详细说明用位势法（对偶变量法）求检验数的原理。3.5用表上作业法求解运输问题时，在什么情况下会出现退化解？当出现退化解时应如何处理？ 答：（1）当某产地的量和，与某销地的销量和相等时，在迭代过程中有可能在某个格填入一个运量时需同时去运输表的一行和一列，这就出现了退化解。 （2）为了使表上作业法的迭代工作能顺利进行，退化时应在同时划去的一行一列中的某个格中填入数字，表示这个格中的变量是取值为的基变量，使迭代过程中基变量个数恰为（m+n-1）个。 3.6一般线性规划问题具备什么特征才能将其转化为运输问题，请举例说明。（见教材103页例6，略） 3.7答：表3-30和表3-31给出的调运方案都不是基可行解。 表3-30中基变量个数少一个，应该是6。 表3-31中，基变量个数多一个，应该是9个。 3.8 （1）解：根据西北角法得该问题初始调运方案如下： 销 产 B1 B2 B3 B4 产量 A1 6 1 6 4 6 8 A2 1 2 3 5 0 8 A3 3 7 5 1 1 3 4 销量 6 5 6 3 20 根据闭回路法得其各检验数如下： ∵均小于0，故表1中的解不是最优解调整如下： 销 产 B1 B2 B3 B4 产量 A1 3 1 5 4 6 8 A2 1 3 2 5 5 0 8 A3 3 7 5 1 1 3 4 销量 6 5 6 3 20 ∵，故表2中的解仍非最优解，再调整。 销 产 B1 B2 B3 B4 产量 A1 1 5 4 3 6 8 A2 1 6 2 5 2 0 8 A3 3 7 5 1 1 3 4 销量 6 5 6 3 20 ∵，故表3中的解仍不是最优解。 销 产 B1 B2 B3 B4 产量 A1 1 5 4 3 6 8 A2 1 6 2 5 0 2 8 A3 3 7 5 3 1 1 4 销量 6 5 6 3 20 ∵此时所有检验数均大于0，故表4中的解为最优解，最优值z*=39。 （2）根据西北角法求该问题最初调运方案： 销 产 B1 B2 B3 B4 产量 A1 0 1 3 4 6 3 A2 1 1 2 5 2 0 3 A3 3 7 5 0 1 5 5 销量 1 3 2 5 11 根据闭回路法得其各检验数如下： ∵，故表1中的解不是最优解。 销 产 B1 B2 B3 B4 产量 A1 0 3 3 8 7 3 A2 4 1 9 4 2 5 3 A3 5 0 7 6 2 5 5 销量 1 3 2 5 11 ∵，故表2中的解不是最优解。 销 产 B1 B2 B3 B4 产量 A1 3 3 8 0 7 3 A2 4 1 9 4