资源描述：
《运筹学线性规划的对偶问题ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、§3线性规划的对偶问题的提出每个线性规划都有另一个线性规划(对偶问题)与它密切相关，对偶理论揭示了原问题与对偶问题的内在联系。0,0768940453643.3032max2121212121³³ïîïíì£+£+£++=xxxxxxxxtsxxz矩阵形式0.max³£=XbAXt.sCXz实际问题提出：某厂生产甲、乙两种产品，产量、利润、设备台时如下模型所示从另一个角度讨论这个问题：工厂决定转让设备收取租金，如何确定租价？设y1，y2，y3分别为出租单位设备台时的租价和出让单位原材料Ａ、Ｂ的附加额。为什么目标取最小？租金定的越高就不会有人来租，问题就
2、没有实际意义，工厂和接受者都愿意的条件为上述规划问题的解。其中Y=（y1，y2，y3）îíì³=+îíì³£==0,.0.maxmaxXbIXAXtsXbAXtsCXZCXZs理论上因为Y的上界为无限大,所以Ｙ只能有最小值。§4线性规划的对偶理论原问题与对偶问题的数学模型原问题标准形式：对偶问题标准形式：标准对偶问题标准形式下原问题与对偶问题的对应关系根据下表写出原问题与对偶问题的表达式xjyjx1x2by1y2y314020481612c23如果原问题约束条件是等式约束原问题中的价值向量与对偶问题中的资源向量对换（上下对换） 原问题:X在C和A的
3、右边;对偶问题:Y在b和A的左边（左右对换）对偶问题的基本性质和基本定理1.对称性定理：对偶问题的对偶是原问题证明：2.弱对偶性定理若X（0）和Y（0）分别是原问题和对偶问题的可行解，则有CX（0）≤Y（0）b3.若原问题（对偶问题）为无界解，则其对偶问题（原问题）无可行解。由弱对偶定理可证得证明:因为X（0）是原问题的可行解，故有AX（0）≤b。又因为Y(0)是对偶问题的可行解，则有Y（0）AX（0）≤Y（0）b,及Y（0）A≥C故CX（0）≤Y（0）AX（0）≤Y（0）b亦即CX（0）≤Y（0）b证毕4.最优性定理若X（0）和Y（0）分别是原问题和对
4、偶问题的可行解，且有CX（0）=Y（0）b,则X（0）和Y（0）分别是原问题和对偶问题的最优解。证明：设X是原问题任一可行解，Y（0）是对偶问题的可行解，根据弱对偶性定理，有CX≤Y（0）b因为CX（0）=Y（0）b，故CX≤CX（0），即X（0）是原问题的最优解。设Y为对偶问题的任一可行解，同理有Yb≥Y（0）b即Y（0）是对偶问题的最优解。5.对偶定理有一对对偶的线性规划问题，若其中有一个有最优解，则另一个也有最优解，且相应的目标函数值相等。证明：设X（0）是原问题的最优解，对应的基矩阵为B,非基变量的检验数为CN-CBB-1N≤0全体检验数C-CB
5、B-1A≤0，即C≤CBB-1A令Y（0）=CBB-1，则有Y（0）A≥C 即Y（0）是对偶问题的可行解。 由于z=CX（0）=CBXB（0）=CBB-1b=Y（0）b（目标值相等） 由最优性定理可知Y（0）为对偶问题的最优解。综上，一对对偶问题的解必然下列情况之一：1、原问题和对偶问题都有解，且目标函数值相等2、一个问题具有无界解，另一个问题无可行解3、一个问题无可行解,另一个问题或具有无界解或无可行解6.互补松弛定理若X（0）和Y（0）分别是原问题和对偶问题的可行解，则X（0）和Y（0）都是最优解的充要条件是Y（0）Xs=0和YsX（0）=0。 其中
6、Xs=(xs1,xs2,…,xsm)T，xs1,xs2,…,xsm是原问题的松弛变量.Ys=(ys1,ys2,…,ysn)T，ys1,ys2,…,ysn是对偶问题的剩余变量。松弛的含义是如果有某个原始最优解X(0)，使得对某个下标j，满足X(0)j>0(原问题是松的)，那么与之对应的对偶约束在最优的情况下为等式，即ysj=0(对偶问题是紧的)；如果原始约束在最优情况下对某个下标i满足x(0)si>0(原问题是松的)，那么，对偶最优解中与之对应的y(0)i=0(对偶问题是紧的)。证明:原问题对偶问题 maxz=CXminω=Yb AX+Xs=bYA-Ys=
7、C X,Xs≥0Y,Ys≥0 z=(YA-Ys)X=YAX-YsX ω=Y(AX+Xs)=YAX+YXs若Y(0)Xs=0和YsX(0)=0,则Y(0)b=Y(0)AX(0)=CX(0)，根据性质4可知 X(0),Y(0)为最优解。 反之,X(0),Y(0)为最优解,则CX(0)=Y(0)AX(0)=Y(0)b 可知必有Y(0)Xs=0和YsX(0)=0。证毕7.原问题的检验数对应对偶问题的一个基本解设B是原问题的一个可行基,有A=(B,N)maxz=CBXB+CNXNminω=YbBXB+NXN+XS=bYB-Ys1=CBXB,XN，Xs≥0YN-Ys
8、2=CNY,Ys1，Ys2≥0YS=（YS1，YS2）证明:原问题对偶问题 ma
