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

《对偶理论第一讲线性规划的对偶模型,对偶性质》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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

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

3、种不同形式，但可以相互转换。(2)规范形式的线性规划问题的对偶仍然是规范形式．原问题(或对偶问题)对偶问题(或原问题)目标函数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个变量无约束问题：讨论一般形式的线性规划问题的对偶问题？方法：先将其转化为规范形式的线性规划问题，

4、然后写出其对偶问题，适当将其进行化简。3.2对偶性质Dualproperty对偶问题是(记为DP)：这里A是m×n矩阵,X是n×1列向量,Y是1×m行向量。【性质1】对称性:对偶问题的对偶是原问题。设原问题是(记为LP)：3.2.1对偶性质【性质2】弱对偶性:设X*、Y*分别为LP(min)与DP(max)的可行解，则【性质2】弱对偶性:设X*、Y*分别为LP(mix)与DP(max)的可行解，则由这个性质可得到下面几个结论：1)(DP)的任一可行解的目标值是(LP)的最优值下界；(LP)的任一可行解的目标是(DP)的最优值的上界；2)在互为对

5、偶的两个问题中，若一个问题可行且具有无界解，则另一个问题无可行解；3)若原问题可行且另一个问题不可行，则原问题具有无界解。注意:上述结论(2)及(3)的条件不能少。一个问题无可行解时，另一个问题可能有可行解(此时具有无界解)也可能无可行解。例如：无可行解而对偶问题有可行解有无界解【性质3】最优准则定理:设X*与Y*分别是(LP)与(DP)的可行解，则X*、Y*是(LP)与(DP)的最优解当且仅当CX*=Y*b.【性质4】对偶性：若互为对偶的两个问题其中一个有最优解，则另一个也有最优解，且最优值相同。另一结论：若(LP)与(DP)都有可行解，则两

6、者都有最优解，若一个问题无最优解，则另一问题也无最优解。【性质5】互补松弛定理:设X*、Y*分别为(LP)与(DP)的可行解，XS和YS分别是它们的松弛变量的可行解，则X*和Y*是最优解当且仅当YSX*=0和Y*XS=0【性质5】互补松弛定理:设X*、Y*分别为(LP)与(DP)的可行解，XS和YS分别是它们的松弛变量的可行解，则X*和Y*是最优解当且仅当YSX*=0和Y*XS=0可写成下式即已知一个问题的最优解时求另一个问题的最优解的方法可写成下式即已知一个问题的最优解时求另一个问题的最优解的方法【例3.5】已知线性规划的最优解是,求对偶问题

7、的最优解。【解】对偶问题是因为x1≠0，x2≠0，所以对偶问题的第一、二个约束的松弛变量等于零，即解此线性方程组得y1=1,y2=1,从而对偶问题的最优解为Y=(1，1)，最优值w=26。【例3.6】已知线性规划的对偶问题的最优解为Y=(0，－2)，求原问题的最优解。【解】对偶问题是解方程组得：x1=－5,x3=－1,所以原问题的最优解为X=(－5，0，－1)T，最优值Z=－12。因为y2≠0，所以原问题第二个松弛变量=0，由y1=0、y2=2知，松弛变量故x2=0，则原问题的约束条件为线性方程组：【例3.7】证明该线性规划无最优解：【证】容易

8、看出X=(4，0，0)是一可行解。将三个约束的两端分别相加得,而第二个约束有y2≥1,矛盾，故对偶问题无可行解，因而原问题具有无界解，即无最优解。对偶