用对偶单纯形法求对偶问题的最优解

《用对偶单纯形法求对偶问题的最优解》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、用对偶单纯形法求对偶问题的最优解摘要：在线性规划的应用中，人们发现一个线性规划问题往往伴随着与之配对的另一个线性规划问题.将其中一个称为原问题，另一个称为对偶问题.对偶理论深刻揭示了原问题与对偶问题的内在联系.由对偶问题引申出来的对偶解有着重要的经济意义.本文主要介绍了对偶问题的基本形式以及用对偶单纯形法求解对偶问题的最优解.关键词：线性规划；对偶问题；对偶单纯形UsingDualSimplexMethodToGetTheOptimalSolutionOfTheDualProblemAbstract：Intheapplicationofthelinearprogr

2、amming，peoplefindthatalinearprogrammingproblemisoftenaccompaniedbyanotherpairedlinearprogrammingproblem.Oneiscalledoriginalproblem.Anotheriscalledthedualproblem.Dualitytheoryrevealstheinternalrelationsbetweenthedualproblemandtheoriginalproblem.Thesolutionofthedualproblemisofagreatecon

3、omicsignificance.Inthispaper，wemainlydiscussthebasicformofthedualproblemandhowtousedualsimplexmethodtogettheoptimalsolutionofthedualproblem.Keywords:linearprogramming；dualproblem；dualsimplexmethod显示对应的拉丁字符的拼音 字典-查看字典详细内容1.代词1.another显示对应的拉丁字符的拼音 字典-查看字典详细内容1引言首先我们先引出什么是线性规划中的对偶问题.任何一个

4、求极大化的线性规划问题都有一个求极小化的线性规划问题与之对应，反之亦然，如果我们把其中一个叫原问题，则另一个就叫做它的对偶问题，并称这一对互相联系的两个问题为一对对偶问题.每个线性规划都有另一个线性规划(对偶问题)与它密切相关，对偶理论揭示了原问题与对偶问题的内在联系.下面将讨论线性规划的对偶问题的基本形式以及用对偶单纯形法求最优解.在一定条件下，对偶单纯形法与原始单纯形法相比有着显著的优点.2对偶问题的形式对偶问题的形式主要包括对称形对偶问题和非对称性对偶问题.2.1对称形对偶问题设原线性规划问题为Max7（2.1）则称下列线性规划问题Max（2.2）为其对偶问

5、题，其中称其为对偶变量，并称（2.1）和（2.2）式为一对对称型对偶问题.原始对偶问题（2.1）和对偶问题（2.2）之间的对应关系可以用表2-1表示.表2-1…原始约束MinW对偶约束MaxZ这个表从横向看是原始问题，从纵向看使对偶问题.用矩阵符号表示原始问题（2.1）和对偶问题（2.2）为原问题（2.3）对偶问题（2.4）其中是一个行向量.2.2 非对称对偶问题7线性规划有时以非对称形式出现，那么如何从原始问题写出它的对偶问题，我们从一个具体的例子来说明这种非对称形式的线性规划问题的对偶问题的建立方法.例1写出下列原始问题的对偶问题解：第一约束不等式等价与下面两

6、个不等式约束第二个约束不等式照写第三个不等式变成以分别表示这四个不等式约束对应的对偶变量，则对偶问题为令，则上式的对偶问题变为：一般可以证明，若原问题中的某个变量无非负限制，则对偶问题中的相应约束为等式.3对偶单纯形法7对偶问题求解具有重要的意义，有多种方法解决对偶问题.下面介绍用对偶单纯形法来解决线性规划的对偶问题.先介绍以下几个线性规划的基本概念：基：已知是约束条件的系数矩阵，其秩为.若是中阶非奇异子矩阵（即可逆矩阵），则称是线性规划问题中的一个基.基向量：基中的一列即称为一个基向量.基中共有个基向量.非基向量：在中除了基B之外的一列则称之为基的非基向量.基变

7、量：与基向量相应的变量叫基变量，基变量有个.非基变量：与非基向量相应的变量叫非基变量，非基变量有个.由线性代数的知识知道，如果我们在约束方程组系数矩阵中找到一个基，令这个基的非基变量为零，再求解这个元线性方程组就可得到唯一的解了，这个解我们称之为线性规划的基本解.首先重新回顾一下单纯形法的基本思想，其迭代的基本思路是：先找出一个基可行解，判断其是否为最优解，如果不是，则转换到另一更优的基可行解，并使目标函数值不断优化，直到找到最优解为止.我们可以用另一种思路，使在单纯形法每次迭代的基本解都满足最优检验，但不一定满足非负约束，迭代时使不满足非负约束的变量个数逐步减少

8、.当全部基