对偶理论第一讲线性规划的对偶模型,对偶性质.ppt

《对偶理论第一讲线性规划的对偶模型,对偶性质.ppt》由会员分享，可在线阅读，更多相关《对偶理论第一讲线性规划的对偶模型,对偶性质.ppt（25页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、3.1对偶线性规划问题对偶问题的提出原问题 对偶问题原问题 对偶问题原问题与对偶问题关系(1)原问题的约束个数(不含非负约束)等于对偶变量的个数(2)原问题的目标函数系数对应于对偶问题的右端项(3)原问题的右端项对应于对偶问题的目标函数系数(4)原问题的约束矩阵转置就是对偶问题系数矩阵(5)原问题求最小(最大)，对偶问题是求最大(最小)(6)原问题不等式约束符号为“”(“”,),对偶问题不等式约束符号为“”(“”)原问题 对偶问题原问题与对偶问题关系(1)原问题的约束个数(不含非负约束)等于对偶变量的个数(2)原问题的目标函数系数对应于对偶问题的右端项(3)原问题的右端项对应于对偶问题的目标函

2、数系数(4)原问题的约束矩阵转置就是对偶问题系数矩阵【例】写出下列线性规划的对偶问题【解】设Y=(y1，y2)(5)原问题求最小(最大)，对偶问题是求最大(最小)(6)原问题不等式约束符号为“”(“”,),对偶问题不等式约束符号为“”(“”)【例3.3】写出下列线性规划的对偶问题线性规划问题的规范形式(CanonicalForm或叫对称形式)：定义：目标函数求极大值时，所有约束条件为号，变量非负；目标函数求极小值时，所有约束条件为号，变量非负。注：(1)线性规划规范形式与标准型是两种不同形式，但可以相互转换。(2)规范形式的线性规划问题的对偶仍然是规范形式原问题(或对偶问题)对偶问题(或原问题

3、)目标函数max目标函数系数(资源限量)约束条件系数矩阵A(AT)目标函数min资源限量(目标函数系数)约束条件系数矩阵AT(A)变量n个变量第j个变量0第j个变量0第j个变量无约束约束n个约束第j个约束为第j个约束为第j个约束为=约束m个约束第i个约束第i个约束第i个约束为=变量m个变量第i个变量0第i个变量0第i个变量无约束问题：讨论一般形式的线性规划问题的对偶问题？方法：先将其转化为规范形式的线性规划问题，然后写出其对偶问题，适当将其进行化简。3.2对偶性质Dualproperty对偶问题是(记为DP)：这里A是mn矩阵,X是n1列向量,Y是1m行向量。【性质1】对称性:对偶问题的对偶是

4、原问题。设原问题是(记为LP)：3.2.1对偶性质【性质2】弱对偶性:设X*、Y*分别为LP(min)与DP(max)的可行解，则【性质2】弱对偶性:设X*、Y*分别为LP(mix)与DP(max)的可行解，则 由这个性质可得到下面几个结论：1)(DP)的任一可行解的目标值是(LP)的最优值下界；(LP)的任一可行解的目标是(DP)的最优值的上界；2)在互为对偶的两个问题中，若一个问题可行且具有无界解，则另一个问题无可行解；3)若原问题可行且另一个问题不可行，则原问题具有无界解。注意:上述结论(2)及(3)的条件不能少。一个问题无可行解时，另一个问题可能有可行解(此时具有无界解)也可能无可行解

5、。例如：无可行解而对偶问题有可行解有无界解【性 质3】最优准则定理:设X*与Y*分别是(LP)与(DP)的可行解，则X*、Y*是(LP)与(DP)的最优解当且仅当C X*=Y*b.【性 质4】对偶性：若互为对偶的两个问题其中一个有最优解，则另一个也有最优解，且最优值相同。另一结论：若(LP)与(DP)都有可行解，则两者都有最优解，若一个问题无最优解，则另一问题也无最优解。【性 质5】互补松弛定理:设X*、Y*分别为(LP)与(DP)的可行解，XS和YS分别是它们的松弛变量的可行解，则X*和Y*是最优解当且仅当YSX*=0和Y*XS=0【性 质5】互补松弛定理:设X*、Y*分别为(LP)与(DP

6、)的可行解，XS和YS分别是它们的松弛变量的可行解，则X*和Y*是最优解当且仅当YSX*=0和Y*XS=0可写成下式即已知一个问题的最优解时求另一个问题的最优解的方法可写成下式即已知一个问题的最优解时求另一个问题的最优解的方法【例3.5】已知线性规划的最优解是,求对偶问题的最优解。【解】对偶问题是因为x10，x20，所以对偶问题的第一、二个约束的松弛变量等于零，即解此线性方程组得y1=1,y2=1,从而对偶问题的最优解为Y=(1，1)，最优值w=26。【例3.6】已知线性规划的对偶问题的最优解为Y=(0，2)，求原问题的最优解。【解】对偶问题是解方程组得：x1=5,x3=1,所以原问题的最优解

7、为X=(5，0，1)T，最优值Z=12。因为y20，所以原问题第二个松弛变量=0，由y1=0、y2=2知，松弛变量故x2=0，则原问题的约束条件为线性方程组：【例3.7】证明该线性规划无最优解：【证】容易看出X=(4，0，0)是一可行解。将三个约束的两端分别相加得,而第二个约束有y21,矛盾，故对偶问题无可行解，因而原问题具有无界解，即无最优解。对偶问题【性 质6】LP(min)的检验数对应于DP(max)的一组基解。其中第j个决策变量xj的检验数对应于(DP)中第j个松弛变量的解，第i个松弛变量的检验数对应于第i个对偶变量yi的解。反之，(DP)的检验数(注意：乘负号)对应于(LP)的一组基

8、本解。注：应用性质6 的前提是线性规划为规范形式，而性质1-5则对所有形式线性规划有效。根据对偶性质；可将原问题与对偶问题解的对应关系列表如下：表36一个问题max 另一个问题min有最优解 有最优解性质4无 无最优解 无最优解性质4最优无界解(有可行解)无可行解性质2解 无可行解 无界解(有可行解)应用 已知最优解 通过解方程 求最优解性质5已知检验数检验数乘以求得基本解性质6【性 质6】LP(min)的检验数对应于DP(max)的一组基解。其中第j个决策变量xj的检验数对应于(DP)中第j个松弛变量的解，第i个松弛变量的检验数对应于第i个对偶变量yi的解。反之，(DP)的检验数(注意：乘负号)对应于(LP)的一组基本解。对偶单纯形法看看性质6的应用对偶单纯形法对偶单纯形法并不是求解对偶问题解的方法，而是利用对偶理论求解原问题的解的方法。找一个基，建立初始对偶单纯形表，检验数全部非负；若b列元素非负，则已经是最优基。否则下一步。确定换出变量 确定换入变量主元变换例3用对偶单纯形法求解线性规划问题：解：先将问题改写为：约束条件两端乘“1”，得例4 考虑线性规划问题