第三章习题解

27第三章运输问题习题解答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）当某产地的供应量之和，与某销地的销量之和相等时，在迭代过程中28有可能在某个格填入一个运量时，需同时划去运输表的一行和一列，这时就出现了退化解。（2）为了使表上作业法的迭代工作能够顺利进行，发生退化解时应在同时划去的一行或一列中的某个适当格子中填入数字0，表示这个格子中的变量是取值为0的基变量，使迭代过程中基变量个数恰好为（m+n-1）个。3.6一般线性规划问题具备什么特征才能将其转化为运输问题，请举例说明。（见教材103页例6，略）3.7答：表3-30和表3-31给出的调运方案都不是基可行解。表3-30中基变量个数少一个，应该是6个。表3-31中，基变量个数多一个，应该是9个。3.8（1）解：根据西北角法得该问题初始调运方案如下：表一根据闭回路法得其各检验数如下：131441250;6125516212412144;0551131323552142;75525∵212431,,均小于0，故表1中的解不是最优解。调整如下：销产B1B2B3B4产量A14315468A21325508A33751134销产B1B2B3B4产量A14616468A2123508A33751134销量656320表二29销量656320重新计算各检验数，有131444154;64103222421414;05511313235512;7551419∵1324,0，故表2中的解仍非最优解，再调整。销产B1B2B3B4产量A14154368A21625208A33751134销量656320111444514;64516222425410;05511313235512;75415∵2410,，故表3中的解仍不是最优解。销产B1B2B3B4产量A14154368A21625028A33753114销量65632011314451013;3101122322015411;75415231455101;4516b∵此时所有检验数均大于0，故表4中的解为最优解，最优值z*=39。表三表四30（2）根据西北角法求该问题最初调运方案如下表：销产B1B2B3B4产量A14013463A21125203A33750155销量132511根据闭回路法得其各检验数如下：311356441;8944114227944622;949311243254625;7644937∵1331,0，故表1中的解不是最优解。销产B1B2B3B4产量A19033873A24194253A35076255销量132511131489441;795212224939411;54524323373958;64451∵130，故表2中的解不是最优解。销产B1B2B3B4产量A19338073A24194253表一表二表三31A35076255销量132511111498441;78445222224948310;5452432337544837;64451此时所有检验数均大于0，故表3为最优解，z*=31。3.9解：由于总产量13大于总销量10，需增加一假想销地B5，使其销量为3，此时产销平衡。根据元素差法得初始基可行解，如表1：销产B1B2B3B4B5产量A1376042035A224032202A343338506销量3322313由位势法求其各检验数：37○6○4○0-50○0○0○02○4○320→-3○0○013○4○3850○0○0654∵1110，故表1中的解不是最优解，以11x为换入变量，调整如下：销产B1B2B3B4B5产量A13076042035A22432202A343338506销量3322313由位势法求其各检验数：○37○6○4○0○05○0○0○024○320→25○013○4○3850○0○010-1∵350，故表2中的解不是最优解。对表2调整得表3：销产B1B2B3B4B5产量A1337604205表一表二32A22432002A3403385036销量3322313根据位势法求其各检验数：37○6○4○005○0○0124○320→25○013○4○385○0○0○010○0∵所有检验数均大于0，故此时为最优解。所以，最优解如表三所示，z*=32。3.11解：（1）用位势法进行检验4○1○464○0○06126○1○0○01○037○5○125○0○0此时检验数均＞0，故表中给出的解为最优解。（2）当C24由1变为3时，用位势法进行检验如下：4○1○466○0○06○126○3○0-2-1○037○5○145○0○0∵有检验数小于0，故应调整。调整结果如下：B1B2B3B4产量A14134568A218226310A33751134销量856322调整后的结果用位势法进行检验如下：4○1○464○0○06○1○263→○0○01237○5○125○0○0∴最优解如上表所示，目标函数最优值为z*=3×1+5×4+8×1+2×2+1×5+3×1=43（3）所有价值系数均增加1，最优解不变。因为根据解的最优性检验方法中的闭回路法和位势法原理易知，所有价值系数增加1时检验数的大小和符号均不会发生变化，故最优解不发生变化。（4）所有价值系数均乘以2，最优解不变。因为根据解的最优性检验方法中的表三33闭回路法和位势法原理知，价值系数乘以2可使检验数的绝对值大小变为原来的2倍，但检验数符号亦然保持不变，故最优解不会改变。3.12解：根据题意，该问题的运输平衡如下表所示：11′233′供应量Ⅰ1515182222400Ⅱ2121251616450ⅢM0MM070需求量2903025027080920西亚斯国际学院工商管理系编印（版权所有，违者必究）2006年12月