论文部分内容阅读
摘 要 本文讨论了线性规划模型在增加或减少约束条件时的灵敏度分析问题， 给出了一个简明有效的方法步骤。
关键词 灵敏度分析 约束条件 对偶问题
中图分类号：0221.1 文献标识码：A
在讨论实际问题的线性规划模型时，一些数据有的是已知常数，有的并不很精确，实际上这些数据往往是一些估计和预测的数字，而情况总是在不断变化的，有可能增加或减少新的变量或新的约束条件。当我们已求解了一个线性规划后遇到上面这些变动时，一种处理方法是根据新的数据从头开始计算，可以求出新的最优解，另一种比较好的办法是对原最优单纯形表进行适当的修改，继续迭代求解，或用对偶问题解决，这就是所谓的灵敏度分析，或优化后分析。
考虑到论述目的及篇幅，这里以一个简单的线性规划模型为例。可以预见，对于大型的线性规划模型，这种处理方法更有效。
设某经济问题的数学模型是如下线性规划问题：
maxZ= 5x1+8x2+6x3
用单纯形方法求解如下：
再增加一个新的约束条件
2x1+x2+2x3≤7，为了节省计算量，直接在上表中增加新的一行和一列，计算如下
利用两次对偶单纯形方法，迭代得：
最优解：x1=0，x2=7，x3=0，对应最优解为maxZ=56。
这个方法是利用原来单纯形表中最优基一栏，新增一个约束方程，即多加一行，多加一列需使原来最优基，再添入一个松弛变量后，仍是一个可行基，不然的话，要用对偶单纯形方法换基迭代。这个方法相对于从新开始要方便一些，但是还是略显复杂，而该问题借助对偶理论来做就显得简单的多，计算如下：
原问题的对偶问题为：ming=-12y1-20y2-7y3
根据对偶原理：最优解：x1=0，x2=7，x3=0，對应最优解为maxZ=56。
原问题增加一个约束条件，对偶问题只增加一个变量，这在计算上并没有增加太多的麻烦，所以，对偶理论用的恰当，可以大大减少计算量。
同理，去掉某个约束条件，也可根据实际情况采取类似方法解决。□
（作者单位：三峡大学理学院）
参考文献：
[1]李 德，钱颂迪.运筹学 [M].北京：清华大学出版社，1996.
[2]魏国华， 傅家良， 周仲良.实用运筹学 [ M].上海： 复旦大学出版社， 1987 .
关键词 灵敏度分析 约束条件 对偶问题
中图分类号：0221.1 文献标识码：A
在讨论实际问题的线性规划模型时，一些数据有的是已知常数，有的并不很精确，实际上这些数据往往是一些估计和预测的数字，而情况总是在不断变化的，有可能增加或减少新的变量或新的约束条件。当我们已求解了一个线性规划后遇到上面这些变动时，一种处理方法是根据新的数据从头开始计算，可以求出新的最优解，另一种比较好的办法是对原最优单纯形表进行适当的修改，继续迭代求解，或用对偶问题解决，这就是所谓的灵敏度分析，或优化后分析。
考虑到论述目的及篇幅，这里以一个简单的线性规划模型为例。可以预见，对于大型的线性规划模型，这种处理方法更有效。
设某经济问题的数学模型是如下线性规划问题：
maxZ= 5x1+8x2+6x3
用单纯形方法求解如下：
再增加一个新的约束条件
2x1+x2+2x3≤7，为了节省计算量，直接在上表中增加新的一行和一列，计算如下
利用两次对偶单纯形方法，迭代得：
最优解：x1=0，x2=7，x3=0，对应最优解为maxZ=56。
这个方法是利用原来单纯形表中最优基一栏，新增一个约束方程，即多加一行，多加一列需使原来最优基，再添入一个松弛变量后，仍是一个可行基，不然的话，要用对偶单纯形方法换基迭代。这个方法相对于从新开始要方便一些，但是还是略显复杂，而该问题借助对偶理论来做就显得简单的多，计算如下：
原问题的对偶问题为：ming=-12y1-20y2-7y3
根据对偶原理：最优解：x1=0，x2=7，x3=0，對应最优解为maxZ=56。
原问题增加一个约束条件，对偶问题只增加一个变量，这在计算上并没有增加太多的麻烦，所以，对偶理论用的恰当，可以大大减少计算量。
同理，去掉某个约束条件，也可根据实际情况采取类似方法解决。□
（作者单位：三峡大学理学院）
参考文献：
[1]李 德，钱颂迪.运筹学 [M].北京：清华大学出版社，1996.
[2]魏国华， 傅家良， 周仲良.实用运筹学 [ M].上海： 复旦大学出版社， 1987 .