胡运权习题及答案习题解答(3).doc

习题解答（3） 试判断表1和表2中给出的调运方案可否作为表上作业法迭代时的基可行解？为什么？ 表1 销地产地产量0151515102555销量5151510表2 销地产地产量15025040020030050025050300902103008020100销量24041055033070解：表1给出的调运方案不能作为基可行解。不满足存在个数字格。表2给出的调运方案不能作为基可行解。不满足存在个数字格。 表3示出一个运输问题及它的一个解，试问：（1）表中给出的解是否为最优解？请用位势法进行检验。（2）若价值系数由1变为3，所给的解是否仍为最优解？若不是，请求出最优解。（3）若所有价值系数均增加1，最优解是否改变？为什么？（4）若所有价值系数均乘以2，最优解是否改变？为什么？（5）写出该运输问题的对偶问题，并给出其对偶问题的最优解。销地产地产量451 346 8 8126 21 1037 35 11 4销量8 5 6 3 22 解：（1）各空格（非基变量的）检验数以 在下表中表出，因它们均，故原给出的解就是最优解，且最优值为。销地产地产量 4451 34 66 8 81 02 16 21 10 23 57 35 11 4销量8 5 6 3 22 （2）当时，用位势法算出各行各列的位势，并在下表中填入相应的值。计算出的各空格的检验数也以 在下表中给出销地产地产量 6451 34 66 8 81 2 6 23 10 43 57 35 11 4 销量8 5 6 3 因，从而为换入变量，作闭回路，且偶数顶点处的最小运输量为故为换出变量，同上算出各行各列的位势以及各空格的检验数，并在下表中给出。销地产地 4431 54 66 81 22 6 23 23 57 15 31 因各空格的检验数均，故此表给出的解即为时的最优解，且最优值为 （3）、（4）的最优解均不变。因为在此两种情况下，各空格的检验数的非负性未改变，但目标函数值即总运费增加。 （5）原问题为： st. 其中 故对偶问题为： st. 因原问题的最优函数值 而 是对偶问题的一个可行解，且，故即为所求对偶问题的最优解。1，2，3三个城市每年需分别供应电力320，1，2，3三个城市每年需分别供应电力320，250和350单位，由，两个电站提供，它们的最大可供电量分别为400个单位和450个单位，单位费用（元）如下表所示。由于需要量大于可供量，决定城市1的供应量可减少0单位30单位，城市2的供应量不变，城市3的供应量不能少于270单位，试求总费用最低的分配方案（将可供电量用完）。 城市电站123151822212516解：最大需求量为320+250+350=920个单位，供应量为400+450=850个单位，此题为需大于求，故虚拟一个电站，其可供电量为920-850=70个单位，其单位运价如下表所示。123供应151518222240021212616164500070需求29030250270 用伏格尔法求出初始解，用位势法求出所有非基变量的检验数，并用 表示，见下表：1供应15015515250181222122240001402152112527016401645