对偶理论第一讲线性规划的对偶模型,对偶性质.ppt
3.1 对偶线性规划问题,对偶问题的提出,原问题,对偶问题,原问题,对偶问题,原问题与对偶问题关系,(1)原问题的约束个数(不含非负约束)等于对偶变量的个数,(2)原问题的目标函数系数对应于对偶问题的右端项,(3)原问题的右端项对应于对偶问题的目标函数系数,(4)原问题的约束矩阵转置就是对偶问题系数矩阵,(5)原问题求最小(最大)，对偶问题是求最大(最小),(6)原问题不等式约束符号为“”(“”,),对偶问题不等式约束符号为“”(“”),原问题,对偶问题,原问题与对偶问题关系,(1)原问题的约束个数(不含非负约束)等于对偶变量的个数,(2)原问题的目标函数系数对应于对偶问题的右端项,(3)原问题的右端项对应于对偶问题的目标函数系数,(4)原问题的约束矩阵转置就是对偶问题系数矩阵,【例】写出下列线性规划的对偶问题,【解】设Y=(y1，y2),(5)原问题求最小(最大)，对偶问题是求最大(最小),(6)原问题不等式约束符号为“”(“”,),对偶问题不等式约束符号为“”(“”),【例3.3】写出下列线性规划的对偶问题,线性规划问题的规范形式(Canonical Form 或叫对称形式)：,定义：目标函数求极大值时，所有约束条件为号，变量非负；目标函数求极小值时，所有约束条件为号，变量非负。,注：(1)线性规划规范形式与标准型是两种不同形式，但可以相互转换。,(2)规范形式的线性规划问题的对偶仍然是规范形式,问题：讨论一般形式的线性规划问题的对偶问题？,方法：先将其转化为规范形式的线性规划问题，然后写出其对偶问题，适当将其进行化简。,3.2 对偶性质Dual property,对偶问题是(记为DP)：,这里A是mn矩阵,X是n1列向量,Y是1m行向量。,【性质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)在互为对偶的两个问题中，若一个问题可行且具有无界解，则另一个问题无可行解；,3)若原问题可行且另一个问题不可行，则原问题具 有无界解。,注意:上述结论(2)及(3)的条件不能少。一个问题无可行解时，另一个问题可能有可行解(此时具有无界解)也可能无可行解。,例如：,无可行解,而对偶问题,有可行解,有无界解,【性质3】最优准则定理:设X*与Y*分别是(LP)与(DP)的可行解，则X*、Y*是(LP)与(DP)的最优解当且仅当C X*=Y*b.,【性质4】对偶性：若互为对偶的两个问题其中一个有最优解，则另一个也有最优解，且最优值相同。,另一结论：若(LP)与(DP)都有可行解，则两者都有最优解，若一个问题无最优解，则另一问题也无最优解。,可写成下式,即,已知一个问题的最优解时求另一个问题的最优解的方法,可写成下式,即,已知一个问题的最优解时求另一个问题的最优解的方法,【解】对偶问题是,因为x10，x20，所以对偶问题的第一、二个约束的松弛变量等于零，即,解此线性方程组得y1=1,y2=1,从而对偶问题的最优解为Y=(1，1)，最优值w=26。,【解】对偶问题是,解方程组得：x 1=5,x 3=1,所以原问题的最优解为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)的一组基本解。,注：应用性质6 的前提是线性规划为规范形式，而性质1-5则对所有形式线性规划有效。,根据对偶性质；可将原问题与对偶问题解的对应关系列表如下：,表36,【性质6】LP(min)的检验数对应于DP(max)的一组基解。其中第j个决策变量xj的检验数对应于(DP)中第j个松弛变量 的解，第i个松弛变量 的检验数对应于第i个对偶变量yi的解。反之，(DP)的检验数(注意：乘负号)对应于(LP)的一组基本解。,对偶单纯形法,看看性质6的应用,对偶单纯形法,对偶单纯形法并不是求解对偶问题解的方法，而是利用对偶理论求解原问题的解的方法。,找一个基，建立初始对偶单纯形表，检验数全部非负；若b列元素非负，则已经是最优基。否则下一步。确定换出变量 确定换入变量 主元变换,例3 用对偶单纯形法求解线性规划问题：,解：先将问题改写为：,约束条件两端乘“1”，得,例4 考虑线性规划问题,
