资源描述：
《苏大 张芳华 运筹学课件第二章 对偶理论.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第二章对偶线性规划对偶的定义对偶问题的性质对偶单纯形法对偶的经济解释灵敏度分析第二章对偶线性规划原始问题minz=CTXs.t.AX≥bX≥0对偶问题Maxw=bTys.t.ATy≤Cy≥0≥minbACTCATbT≤maxmnmn一、对偶的定义第二章对偶线性规划对偶的定义当原问题为求极小值时，对偶问题为求极大值。原始问题中目标函数的系数变成对偶问题中约束条件的右端；原始问题中约束条件的右端变成对偶问题中目标函数的系数。原始问题约束条件系数矩阵的转置对应对偶问题中约束条件的系数矩阵。原始问题的约束条件个数决定对偶问题变量
2、的个数；原始问题变量个数，决定对偶问题的约束个数。原始问题的约束方程的匹配形式决定对偶问题变量的符号；原始问题决策变量的符号决定所对应对偶问题的约束方程的匹配形式。第二章对偶线性规划原始问题（prime)与对偶问题之间的关系极小化问题（min)极大化问题（max)变量Xj≥0约束∑aijwj≤biXj:unr∑aijwj=biXj≤0∑aijwj≥bi约束∑aijxj≥bi变量wj≥0∑aijxj=biwj:unr∑aijxj≤biwj≤0第二章对偶线性规划对偶问题的形成minz=2x1+4x2-x3s.t.3x1-x2
3、+2x36-x1+2x2-3x3122x1+x2+2x38x1+3x2-x315maxw=6y1+12y2+8y3+15y4s.t.3y1-y2+2y3+y42-y1+2y2+y3+3y442y1-3y2+2y3-y4-1y10,y2,y30,y40≤≥=≥unr≤≥≥=≤≥x1≥0x2≤0x3:unr原始问题变量的个数(3)等于对偶问题约束条件的个数(3)；原始问题约束条件的个数(4)等于对偶问题变量的个数(4)。原始问题变量的性质影响对偶问题约束条件的性质，用表示原始问题约束条件的性质影响对偶问题变量的性质，用表示第
4、二章对偶线性规划对偶问题的解p84当原始问题有最优解时，对偶问题也有最优解，而且两者相等；原问题的最优解和对偶问题的最优解构成互补松弛关系；原问题最优表中松弛变量的检验数的反号就是对偶问题的最优解；对偶问题最优表中松弛变量的检验数的反号就是原问题的最优解。第二章对偶线性规划1、对偶的对偶就是原始问题maxz’=-CTXs.t.-AX≤-bX≥0Minw’=-bTys.t.-ATy≥-Cy≥0maxw=bTys.t.ATy≤Cy≥0minz=CTXs.t.AX≥bX≥0对偶的定义对偶的定义二、对偶问题的性质第二章对偶线性规
5、划2、可行解的目标函数值之间的关系设XF、yF分别是原始问题和对偶问题的可行解z=CTXF≥yTAXF≥yTb=w3、最优解的目标函数值之间的关系设Xo、yo分别是原始问题和对偶问题的最优解z=CTXo=yoTAXo=yoTb=w第二章对偶线性规划4、原始问题和对偶问题最优解之间的互补松弛关系minz=CTXs.t.AX-u=bX,u≥0maxw=bTys.t.ATy+v=Cy,v≥0minz=CTXs.t.AX≥bX≥0maxw=bTys.t.ATy≤Cy≥0对偶引进松弛变量引进松弛变量XTv=0yTu=0互补松弛关系
6、X，uy，v第二章对偶线性规划minz=CTXs.t.AX-u=bX,u≥0maxw=bTys.t.ATy+v=Cy,v≥0XTv=0yTu=0mn=yvATICn=Au-IbnmmX原始问题和对偶问题变量、松弛变量的维数第二章对偶线性规划y1yiymvm+1vm+jvn+mx1xjxnun+1un+iun+m对偶问题的变量对偶问题的松弛变量原始问题的变量原始问题的松弛变量xjvm+j=0yiun+i=0(i=1,2,…,m;j=1,2,…,n)在一对变量中，其中一个大于0，另一个一定等于0第二章对偶线性规划1、单纯形表
7、最优基必须同时满足两个条件右端列中的所有Ъi≥0可行性条件全部检验数σj≤0最优性条件（1）（2）三、对偶单纯形法第二章对偶线性规划单纯形法的迭代过程Ъi≤0σj≤0Ъi≥0σj≥0Ъi≥0σj≤0对偶单纯形法的迭代过程Ъi≥0σj≤0第二章对偶线性规划2、对偶单纯形法例题1minω=15y1+5y2+11y3s.t.3y1+2y2+2y3≥55y1+y2+2y3≥4y1，y2，y3≥0解:将每个不等式两边乘以-1,再引入松驰变量S1和S2,则上述问题化为:直接写成标准式时有-S1和-S2,则无法有初始基,因此乘个-1m
8、inω=15y1+5y2+11y3s.t.-3y1-2y2-2y3+S1=-5-5y1-y2-2y3+S2=-4y1，y2，y3,S1,S2,≥0第二章对偶线性规划对偶单纯形法2建立该问题的初始单纯形表y1y2y3s1s2右端ω-15-5-11000s1-3-2-210-5s2-5-1-201-4由表知β1的两个基变
