资源描述
单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,上堂课主要内容,:,线性规划的对偶问题,:,对称型线性规划:,形如:,b,i,无正负限制,或:,1,、对称型对偶问题:,2,、,标准型的对偶问题,:,则,对偶问题(,D,),为:,原问题,对偶问题,目标函数,max,目标函数,min,目标函数系数,约束方程常数列,约束方程常数列,目标函数系数,变量个数,n,约束方程个数,n,约束方程个数,m,变量个数,m,约束方程,变量,0,0,=,无符号约束,变量,0,约束方程,0,无符号约束,=,系数矩阵,A,3,、混合型对偶问题,2.2 对偶线性规划 解的理论,定理,2.1,对偶问题的对偶就是原问题。,(即互为对偶规划),一、对称定理:,二、弱对偶性定理:,推论,1,:,若(,P,),有可行解,但无上界,则(,D,)无,可行解。若(,D,),有可行解,但无下界,则,(,P,)无可行解,推论,2,、若原问题(,P,)和其,对偶问题,(,D,),都存在,可行解,则(,P,),和(,D,),都存在最优解,定理,2.3,原线性规划(,P,),与其对偶规划(,D,)存,在以下对应关系:,(,1,)(,P,),有最优解的,充要条件,是(,D,),有最优解,(,2,)若,X,*,和,Y,*,分别是(,P,),和(,D,),的可行解,,则,X,*,和,Y,*,分别是(,P,),和(,D,),的最优解的充,要条件是:,CX,*,=,Y,*,b,三、对偶性定理:,2,、若(,P,),存在最优解,X,*,,,B,是对应的最优基,,则(,D,),一定存在最优解,Y*,,且,1,、原问题(,P,)与其对偶问题(,D,)最优值相同,说明,:,只需求出(,P,)或,(D),中一个的最优解和最优值,,即可得另一个的最优解和最优值,推论,3*,:,若(,P,)(,D,)为对称型对偶问题,且(,P,),存在最优解,X,*,,,则(,D,),一定存在最优解,Y*,,,且(,-1,),Y*,是(,P,)的标准型的最优单纯形表,检验行中松弛变量的系数,四、互补松弛定理:,定理,2.4,设,X*,和,Y*,分别是(,P,)和(,D,)的可行解,,则,X*,和,Y*,分别是(,P,)和(,D,)的最优解的,充要条件是方程组,证明,:,充分性,已知,X*,和,Y*,分别是(,P,)和(,D,)的,可行解,且,所以,X*,和,Y*,分别是(,P,)和(,D,)的最优解,一个数,0,0,0,0,0,0,0,0,0,0,0,0,互补松弛定理,:,设,X*,和,Y*,分别是(,P,)和(,D,)的可行解,则,X*,和,Y*,分别是(,P,)和(,D,)的最优解,的充要条件是方程组 成立,把,X*,代入(,P,)的第,i,个方程时为等式,松约束,紧约束,定理,2.4,设,X*,和,Y*,分别是(,P,)和(,D,)的可行解,则,X*,和,Y*,分别是(,P,)和(,D,)的最优解的充,要条件,是方程组 成立,对任一种形式的对偶问题成立,互补松弛定理,:,0,求对偶问题最优解的方法归纳:,1,、对任一种形式的对偶问题:,设,B,是原问题(,P,)的最优基,则,是对偶问题(,D,)的最优解,2,、对对称形的对偶问题:,(,-1,)原问题(,P,)的最优单纯形表上松弛变量的检验数,对偶问题(,D,)的最优解,=,3,、对任一种形式的对偶问题,,利用互补松弛定理,设已求得原问题(,P,)的最优解,则,练习:,
展开阅读全文