论文部分内容阅读
【中图分类号】F224
1. 问题的提出
运输问题是运筹学中的一类重要模型。针对运输问题所开发的求解方法和计算软件，一般都是用来解决产销平衡运输问题的。当然，大部分运输模型是不满足产销平衡条件的，其中有一类问题就是需求无上限运输问题。
对于需求无上限这种特殊的运输问题，一般的求解方法如下：首先，确定需求无上限这个特殊销地的最高需求量，即将所有产地的供应量之和与除去需求无上限这个销地之外所有销地的最低需求量之和的差值作为该销地的最高需求量。然后，增加一个虚拟的产地，并令该虚拟产地的供应量等于所有销地的最高需求量之和与所有产地的供应量之和的差值。这样，原问题就转换为产销平衡的运输问题。最后，运用数学方法或者计算软件求出该产销平衡运输问题的最优解，即得到原需求无上限运输问题的最优解。
但是，同学们认为，既然某一销地的需求无上限，只要赋予这个销地的最高需求量为大于等于该销地最低需求量的一个任意值，然后进行产销平衡转换，就可以直接求解产销平衡运输问题了。但是，经过验证可以发现这样的求解思路是错误的，即当需求无上限这个销地的最高需求量发生变化时，有时会引起该运输问题的最优解发生改变。因此，本文将探讨在什么条件下，需求无上限运输问题的最优解会发生变化？
2. 算例分析
以如下需求无上限运输问题为例，对该问题的最优解与需求无上限这个特殊销地的最高需求量的关系进行探讨。
假设有甲、乙、丙三个煤矿供应A、B、C、D四个电厂。各煤矿的供应量（万吨）、各电厂的煤炭需求量（万吨）、以及煤矿到电厂的单位运输成本（千元/万吨）如表1所示。试求运输成本最小的煤炭调拨方案。（以下省略数据单位）
表1. 煤矿到电厂的单位运输成本
按照前述一般求解方法，首先确定销地D的最高需求量=（500+600+500） -（250+700）=650。然后，增加一个虚拟的产地丁，该虚拟产地丁的供应量=（520+700 +300+650）-（500+600+500）=570。这样就可以得到如表2所示的产销平衡运价表。
此外，表2中每个销地的最低需求必须得到满足，因此把虚拟产地到相应销地的运费取为大 M ，而最高需求与最低需求的差值允许按实际产量进行安排，因此把虚拟产地到相应销地的运费取为 0 。
基于表2数据，我们利用计算软件进行求解，可以得到该问题的最优运输方案如表3所示，此时的最小运输费用为24200。
表2. 产销平衡运价表 表3. 最优运输方案
由表3可以看出，销地A、B、C、D的最低需求量都得到满足。但是由于表3中产地丁到各销地的运输量都是虚拟的，在现实中根本不存在，因此，该最优运输方案实际只满足销地A的500的需求，与其最高需求还差20；销地B的700的需求完全得到满足；销地C的实际接收量为0；销地D在其最低需求100的基础上多接收了300。
现在来探讨该最优解与需求无上限这个特殊销地的最高需求量之间的关系。既然销地D的需求无上限，而最低需求为100，不妨假设，销地D的最高需求分别为100、200、300、400、500、600、1000，相应地，表2中销地D2的需求量分别为0、100、200、300、400、500、900。为了给出产销平衡运价表，虚拟产地丁的产量也随之调整为20、120、220、320、420、520、920。最后运用计算软件分别求出每个问题的最优解，可以发现：
（1） 当销地D的最高需求大于等于400时，所求最优解与表3 给出的最优运输方案保持一致。
（2） 当销地D的最高需求分别等于100、200或者300时，所求最优解如表4所示，最小运输费用分别为25620、25120和24620。显然，这三组最优解与表3给出的最优运输方案不一致，也就是说最优解发生了根本性的改变。
表4 销地D的最高需求分别等于100、200、300时的最优解
由此例可以看出，虽然销地D的需求是无上限的，但是确实存在一个最小临界值，当D的需求量超过这个最小临界值时，最优解恒保持一致，而当D的需求量小于这个最小临界值时，最优解会发生根本性的变化。下面我们就给出寻找这一临界值的方法。
由表3给出的最优运输方案可知，销地D接受了650的供应量，其中有400的供应量是由产地乙提供的，不仅满足了其最低需求100，而且在最低需求基础上多提供了300的供应量；其余250的供应量是由假想产地丁提供的。也就是说，实际产地的供应量在满足各销地的最低需求后，还有多余的供应量300去满足最高需求无上限的销地，但此时，其他有需求上限销地的最高需求没有得到满足，譬如A和C地。所以，当销地D的最高需求减少时，也就是表2中D2的需求量减少，只要这个减少量低于250，那么，为了保持产销平衡所需要减少的供应量首先就是在假想产地丁中减少的。即，假如销地D2的需求量减少100，则其需求变为450，此时假想产地丁的供应量也相应减少100，即供应量变为470以使产销平衡，此时最优结果中假想产地丁给D2的供应量就减少为150。若继续减少销地D2的需求量，譬如，减少250，则销地D2的需求量变为300，此时假想产地丁的供应量也相应减少250，即供应量变为320以使产销平衡，则此时最优结果中假想产地丁给D2的供应量就减少到0。当销地D的最高需求继续减少时，也就是说D2的需求量减少到300以下，此时，根据表3可知，假想产地丁给销地D的供应量为0，而销地D的其他需求是由真实的产地甲、乙、丙供给的。所以当D2的需求量减少到300以下时，这时真实产地给销地D的供应量就会减少，相应地，产地甲、乙、丙的供应量将会分配给最高需求量没有得到满足的其他几个销地，如此例中的销地A和C。在表4 中，可以看出，当销地D的最高需求量分别减少到100、200、300时，销地D的最高需求不仅得到满足，而且产地甲、乙、丙的供应量也相应地向销地A和C转移，即销地A的最高需求量都得到了满足，而销地C的实际接收量也由原来的0分别提高到280、180和80，此时，与表3所给最优运输方案相比，最优解完全发生了变化。
由上述分析可以看出，使最优解发生变化的关于D的需求量上限的最小临界值为400，即表3中由实际产地提供给销地D的供应量，也就是销地D的实际接收量。
3. 结论
由此例可见，对于需求无上限的运输问题，一定存在一个关于需求上限的最小临界值，若是需求上限值小于这个最小临界值，则最优运输方案会发生改变。而这一临界值的确定方法是先将无上限需求销地的最高需求量的数值定为供应量和最低需求量的差，然后求出产销平衡运输问题的最优解，最后根据最优解，将这个销地的需求上限的最小临界值确定为由实际产地提供给该销地的供应量。若改变需求无上限的销地的最高需求，让它低于这个最小临界值，这时，最优运输方案就会发生变化；反之，若高于这个最小临界值，最优运输方案就不会发生变化。其实，这一问题的本质就是对运输问题进行的灵敏度分析。
1. 问题的提出
运输问题是运筹学中的一类重要模型。针对运输问题所开发的求解方法和计算软件，一般都是用来解决产销平衡运输问题的。当然，大部分运输模型是不满足产销平衡条件的，其中有一类问题就是需求无上限运输问题。
对于需求无上限这种特殊的运输问题，一般的求解方法如下：首先，确定需求无上限这个特殊销地的最高需求量，即将所有产地的供应量之和与除去需求无上限这个销地之外所有销地的最低需求量之和的差值作为该销地的最高需求量。然后，增加一个虚拟的产地，并令该虚拟产地的供应量等于所有销地的最高需求量之和与所有产地的供应量之和的差值。这样，原问题就转换为产销平衡的运输问题。最后，运用数学方法或者计算软件求出该产销平衡运输问题的最优解，即得到原需求无上限运输问题的最优解。
但是，同学们认为，既然某一销地的需求无上限，只要赋予这个销地的最高需求量为大于等于该销地最低需求量的一个任意值，然后进行产销平衡转换，就可以直接求解产销平衡运输问题了。但是，经过验证可以发现这样的求解思路是错误的，即当需求无上限这个销地的最高需求量发生变化时，有时会引起该运输问题的最优解发生改变。因此，本文将探讨在什么条件下，需求无上限运输问题的最优解会发生变化？
2. 算例分析
以如下需求无上限运输问题为例，对该问题的最优解与需求无上限这个特殊销地的最高需求量的关系进行探讨。
假设有甲、乙、丙三个煤矿供应A、B、C、D四个电厂。各煤矿的供应量（万吨）、各电厂的煤炭需求量（万吨）、以及煤矿到电厂的单位运输成本（千元/万吨）如表1所示。试求运输成本最小的煤炭调拨方案。（以下省略数据单位）
表1. 煤矿到电厂的单位运输成本
按照前述一般求解方法，首先确定销地D的最高需求量=（500+600+500） -（250+700）=650。然后，增加一个虚拟的产地丁，该虚拟产地丁的供应量=（520+700 +300+650）-（500+600+500）=570。这样就可以得到如表2所示的产销平衡运价表。
此外，表2中每个销地的最低需求必须得到满足，因此把虚拟产地到相应销地的运费取为大 M ，而最高需求与最低需求的差值允许按实际产量进行安排，因此把虚拟产地到相应销地的运费取为 0 。
基于表2数据，我们利用计算软件进行求解，可以得到该问题的最优运输方案如表3所示，此时的最小运输费用为24200。
表2. 产销平衡运价表 表3. 最优运输方案
由表3可以看出，销地A、B、C、D的最低需求量都得到满足。但是由于表3中产地丁到各销地的运输量都是虚拟的，在现实中根本不存在，因此，该最优运输方案实际只满足销地A的500的需求，与其最高需求还差20；销地B的700的需求完全得到满足；销地C的实际接收量为0；销地D在其最低需求100的基础上多接收了300。
现在来探讨该最优解与需求无上限这个特殊销地的最高需求量之间的关系。既然销地D的需求无上限，而最低需求为100，不妨假设，销地D的最高需求分别为100、200、300、400、500、600、1000，相应地，表2中销地D2的需求量分别为0、100、200、300、400、500、900。为了给出产销平衡运价表，虚拟产地丁的产量也随之调整为20、120、220、320、420、520、920。最后运用计算软件分别求出每个问题的最优解，可以发现：
（1） 当销地D的最高需求大于等于400时，所求最优解与表3 给出的最优运输方案保持一致。
（2） 当销地D的最高需求分别等于100、200或者300时，所求最优解如表4所示，最小运输费用分别为25620、25120和24620。显然，这三组最优解与表3给出的最优运输方案不一致，也就是说最优解发生了根本性的改变。
表4 销地D的最高需求分别等于100、200、300时的最优解
由此例可以看出，虽然销地D的需求是无上限的，但是确实存在一个最小临界值，当D的需求量超过这个最小临界值时，最优解恒保持一致，而当D的需求量小于这个最小临界值时，最优解会发生根本性的变化。下面我们就给出寻找这一临界值的方法。
由表3给出的最优运输方案可知，销地D接受了650的供应量，其中有400的供应量是由产地乙提供的，不仅满足了其最低需求100，而且在最低需求基础上多提供了300的供应量；其余250的供应量是由假想产地丁提供的。也就是说，实际产地的供应量在满足各销地的最低需求后，还有多余的供应量300去满足最高需求无上限的销地，但此时，其他有需求上限销地的最高需求没有得到满足，譬如A和C地。所以，当销地D的最高需求减少时，也就是表2中D2的需求量减少，只要这个减少量低于250，那么，为了保持产销平衡所需要减少的供应量首先就是在假想产地丁中减少的。即，假如销地D2的需求量减少100，则其需求变为450，此时假想产地丁的供应量也相应减少100，即供应量变为470以使产销平衡，此时最优结果中假想产地丁给D2的供应量就减少为150。若继续减少销地D2的需求量，譬如，减少250，则销地D2的需求量变为300，此时假想产地丁的供应量也相应减少250，即供应量变为320以使产销平衡，则此时最优结果中假想产地丁给D2的供应量就减少到0。当销地D的最高需求继续减少时，也就是说D2的需求量减少到300以下，此时，根据表3可知，假想产地丁给销地D的供应量为0，而销地D的其他需求是由真实的产地甲、乙、丙供给的。所以当D2的需求量减少到300以下时，这时真实产地给销地D的供应量就会减少，相应地，产地甲、乙、丙的供应量将会分配给最高需求量没有得到满足的其他几个销地，如此例中的销地A和C。在表4 中，可以看出，当销地D的最高需求量分别减少到100、200、300时，销地D的最高需求不仅得到满足，而且产地甲、乙、丙的供应量也相应地向销地A和C转移，即销地A的最高需求量都得到了满足，而销地C的实际接收量也由原来的0分别提高到280、180和80，此时，与表3所给最优运输方案相比，最优解完全发生了变化。
由上述分析可以看出，使最优解发生变化的关于D的需求量上限的最小临界值为400，即表3中由实际产地提供给销地D的供应量，也就是销地D的实际接收量。
3. 结论
由此例可见，对于需求无上限的运输问题，一定存在一个关于需求上限的最小临界值，若是需求上限值小于这个最小临界值，则最优运输方案会发生改变。而这一临界值的确定方法是先将无上限需求销地的最高需求量的数值定为供应量和最低需求量的差，然后求出产销平衡运输问题的最优解，最后根据最优解，将这个销地的需求上限的最小临界值确定为由实际产地提供给该销地的供应量。若改变需求无上限的销地的最高需求，让它低于这个最小临界值，这时，最优运输方案就会发生变化；反之，若高于这个最小临界值，最优运输方案就不会发生变化。其实，这一问题的本质就是对运输问题进行的灵敏度分析。