资源描述：
《运筹学第二章对偶理论与灵敏度分析》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第二章对偶理论与灵敏度分析§2.1线性规划的对偶问题§2.2对偶问题的基本性质§2.3影子价格§2.4对偶单纯形法§2.5灵敏度分析第一章例1中：美佳公司利用自身资源生产两种家电产品，其线形规划问题表示为：maxz=2x1+x25x2≤15St.6x1+2x2≤24x1＋x2≤5x1、x2≥0现假定有某公司想把美佳公司的资源买过来，它至少应付出多大代价，才能使美佳公司愿意放弃生产活动，出让自己的资源。设y1、y2和y3代表单位时间设备A、设备B和调试工序的出让代价，则6y2＋y3≥2、5y1+2y2+y3≥1；另外要求，minz=15y1+24y2+5
2、y3，且y1、y2、y3≥0即minz=15y1+24y2+5y36y2＋y3≥25y1+2y2+y3≥1y1、y2、y3≥0St.§2.1线性规划的对偶问题对偶问题的提出maxz=2x1+x25x2≤156x1+2x2≤24x1+x2≤5x1、x2≥0St.minz=15y1+24y2+5y36y2+y3≥25y1+2y2+y3≥1y1、y2、y3≥0St.对称形式的对偶问题对称形式变量非负，求极大时约束条件取≤号、求极小时约束条件取≥号.Maxz=(2,1)x1x205211x1x2≤15245(x1x2)T≥0minw=(15,24,5)y1y2
3、y3061521y1y2y3≥21(y1y2y3)T≥0Maxz=CXAX≤bX≥0st.minw=YTbATY≥CTY≥0st.Maxz=c1x1+c2x2+…….+cnxna11x1+a12x2+……..+a1nxn≤b1a21x1+a22x2+……..+a2nxn≤b2…………………………………am1x1+am2x2+……..+amnxn≤bmx1,x2,……xn≥0Minw=b1y1+b2y2+…….+bmyma11y1+a21y2+……..+am1ym≥c1a12y1+a22y2+……..+am2ym≥c2…………………………………a1ny1
4、+a2ny2+……..+amnym≥cny1,y2,……ym≥0对称形式的对偶问题1,若原问题目标是求极大化，则对偶问题的目标是极小化，反之亦然。2,原问题的约束系数矩阵与对偶问题的约束系数矩阵互为转置矩阵。3,极大化问题的每个约束对应于极小化问题的一个变量，其每个变量对应于对偶问题的一个约束。4,原问题与对偶问题互为对偶问题。对偶问题的特点Maxz=CXAX≤bX≥0St.Minz'=-CX-AX≥-bX≥0st.Maxw'=-YTb-ATY≤-CTY≥0st.minw=YTbATY≥CTY≥0st.求对偶标准化求对偶标准化非对称形式的对偶问题max
5、z=2x1+x25x2≤156x1+2x2≤24x1+x2≤5x1、x2≥0St.minz=15y1+24y2+5y36y2+y3≥25y1+2y2+y3≥1y1、y2、y3≥0St.原问题对偶问题目标函数maxmin目标函数约束条件≤≥=≥≤无约束变量变量≥≤无约束≥≤=约束条件非对称形式的对偶问题若互为对偶的线性规划分别有可行解则其相应的目标函数值满足性质1弱对偶性§2.2对偶问题的基本性质推论1极大化问题的任意一个可行解所对应的目标函数值是其对偶问题最优目标函数值的一个下界。推论2极小化问题的任意一个可行解所对应的目标函数值是其对偶问题最优目标函
6、数值的一个上界。推论推论3若原始问题可行，则其目标函数无界的充要条件是对偶问题没有可行解。若X和Y分别是互为对偶的线性规划的可行解，且使CX=Yb，则X和Y分别是相应线性规划问题的最优解。性质2：最优性准则若原始问题和对偶问题两者均可行，则两者均有最优解，且此时目标函数值相同。若原问题最优基为B，则其对偶问题最优解Y*=CBB-1性质3：强对偶性（对偶定理）性质4：互补松弛性最优解中，如果对应某一约束条件的对偶变量值为非零，则该约束条件取严格等式；反之如果约束条件取严格不等式，则其对应的对偶变量一定为零。maxz=2x1+x25x2≤156x1+2x2
7、≤24x1+x2≤5x1、x2≥0St.最优解X*=(x1,x2,x3,x4,x5)＝(7/2,3/2,15/2,0,0)minz=15y1+24y2+5y36y2+y3≥25y1+2y2+y3≥1y1、y2、y3≥0St.最优解y*=(y1,y2,y3,y4,y5)＝(0,1/4,1/2,0,0)y1＝0y2＝1/4y3＝1/2x1＝7/2x2＝3/2§2.3影子价格maxz=2x1+x25x2≤156x1+2x2≤24x1+x2≤5x1、x2≥0St.minz=15y1+24y2+5y36y2+y3≥25y1+2y2+y3≥1y1、y2、y3≥0S
8、t.最优解X*=(x1,x2,x3,x4,x5)＝(7/2,3/2,15/20,0)，最优值:
