摘要:原问题与对偶问题的互化在实际生产生活中有着广泛的应用.本文主要证明原问题与对偶问题互化的结论,运用系数矩阵的初等行变换,对偶问题的强对偶性来分析原问题的变化对对偶问题解的影响.74165
毕业论文关键词:线性规划,原问题,对偶问题
Abstract: It was used commonly in actual production and life that the mutual transformation between the original problem and its dual problem.The conclusion was proved that the mutual transformation between the original problem and its dual problem.It was used by the elementary row transformation of coefficient matrix to analyze the influence of the change of the original problem to the solution of the dual problem.It was also used by the strong duality of dual problem to analyze the same result.
Keywords: linear programming, the original problem, the dual problem
目 录
1 引言4
2 线性规划原问题与对偶问题的互化…4
2。1 原问题与对偶问题的对称形式 …4
2。2 原问题与对偶问题的非对称形式…4
3 原问题的变化对对偶问题解的影响10
3。1 对偶问题的解变为原来的 …10
3。2 对偶问题解的某个分量变为原来的 11
3。3 对偶问题解的两个分量对换12
3。4 对偶问题解的某个分量是其它分量的线性组合13
结论 17
参考文献18
致谢 19
1 引言
原问题与对偶问题之间的互化在教材中只有简短的总结,并未给出具体证明,原问题与对偶问题之间的互化是两者模型上的互相转化,然而两者之间还存在其他的联系,如当原问题产生变化时会对对偶问题的解产生影响.在本文中主要证明原问题与对偶问题的互化以及探讨原问题约束条件的变化对对偶问题解的影响.
2 线性规划原问题与对偶问题的互化
线性规划问题是目标函数、约束条件都是线性等式或者不等式的数学规划问题.根据线性规划的对偶理论[1],一个线性规划问题的数学模型,必然对应另外一个线性规划模型,两者之间互为对偶问题.因此两者之间的一一对应关系说明了两者可以互相转化.文献综述
2.1 原问题与对偶问题的对称形式
对于线性规划问题:
(1)
根据文献[1]得到该线性规划的对偶问题为
(2)
对于这种形式的原问题与对偶问题,一般称其为原问题与对偶问题的对称形式,两者之间可以互化.
2.2 原问题与对偶问题的非对称形式
如果原问题与对偶问题存在对称形式的互化,那么原问题与对偶问题肯定还存在非对称形式的互化[2-4].那原问题与对偶问题的非对称形式如何互化,可以从原问题与对偶问题对称形式的互化推导出来.
形式一 如果我们将问题(1)中约束条件的符号变为 ,即
(3)
则此时该线性规划问题的对偶问题是什么?
将问题(3)的约束条件符号 改为 后,将问题(3)和问题(1)比较,可先将问题(3)转化为原来的对称形式,即