线性规划中原问题与对偶问题的讨论

论文总字数：7761字

摘 要

关键词：线性规划，原问题，对偶问题

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)转化为原来的对称形式，即

(4)

然后通过原问题与对偶问题的对称形式写出问题(4)的对偶问题，即

　 　 (5)

令,则问题(3)的对偶问题为

　 　 　 (6)

不考虑变量的字母形式，可以将问题(6)直接写为

(7)

形式二　如果将问题(1)决策变量改为非正，即

　　 (8)

则问题(8)的对偶问题是什么？

仍然将问题(8)决策变量都转化成非负的形式，即为

　 (9)

令，则问题(9)可以表示成

　 (10)

那么根据形式一的情况，则问题(10)的对偶问题为

　　 (11)

将约束条件左右两端的负号消掉，即得

　 　 (12)

不考虑变量的字母形式，可以直接将问题(8)的对偶问题写为

　 　 (13)

形式三　如果问题(1)的约束条件中的不等式改为等式 ，即

　　　　　　　　　　　　　 (14)

则此时该线性规划问题的对偶问题是什么？

当原问题的约束条件为等式时，先将该约束条件化为两个不等式，此时的问题(14)变为

　 (15)

对于符号为的约束条件，参考形式一将问题(15)的约束条件全部化为原来的对称形式，即变为

　 　 　 (16)

剩余内容已隐藏，请支付后下载全文，论文总字数：7761字