资源描述：
《05-第三章 线性规划及其原始-对偶算法-2(第4次课)》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第三章线性规划及其原始－对偶算法（II）3.5线性规划的对偶理论先从一个简单的例子谈起。例子：某工厂在计划期内要安排生产I、II两种产品，已知生产单位产品所需要的设备台时及A、B两种原材料的消耗，如下表：III设备128台时原材料A4016原材料B0412该工厂每生产一件产品I可获利2，每生产一件产品II可获利3。问应该如何安排生产计划使该工厂获利最大？设x、x分别表示I、II的产量，则该问题的数学模型为：12maxz=2x+3x12s.t.x+2x≤8124x≤1614x≤122x,x≥012用单纯形方法可以求得最优解为：x*=,4x*=2
2、，最优值为z*=14。12假设：该工厂的决策者决定不生产产品I、II，而将其所有资源出租或外售。这时工厂的决策者就要考虑给每种资源定价的问题。设用y,y,y分别表示出租123单位设备台时的租金和出让单位原材料A，B的附加额，则minω=8y+16y+12y123s.t.y+4y≥2122y+4y≥313y≥,0i=3,2,1i31也可以用单纯形方法求得最优解为：y*=,y*=,y*=0，最优值为12328ϖ*=14。显然：8(−x*−2x*)=0且y*>0，即8(−x*−2x*)y*=0——原始约束紧，对偶变121121量松(16−4x*)=
3、0且y*>0，即(16−4x*)y*=0——原始约束紧，对偶变量松12121(12−4x*)>0且y*=0，即(12−4x*)y*=0——原始约束松，对偶变量紧2323同样，对称的，(y*+4y*−)2=0x*>0且12，即x*⋅(y*+4y*−)2=0——原始变量松，对偶1112约束紧x*>0且2(y*+4y*−)3=0，即x*⋅2(y*+4y*−)3=0——原始变量松，对213213偶约束紧最终达到平衡，原始－对偶目标函数取值相等，得到原始－对偶最优解。这就是所谓的“互补松弛性”互补松弛性原始与对偶规划之间存在者拉锯式争夺：一个问题里的某
4、个约束越紧，另一个问题中对应的变量就越松；最终的平衡表示式，就是x和y是原始－对偶问题最优解的充分必要条件，这就是所谓的互补松弛性条件定理3.13（互补松弛性条件）x和y分别为原始－对偶可行解，则它们分别是原始－对偶最优解⇔对一切i和j有：Tu=y(ax−b)=0iiiiTv=(c−Ay)x=0jjjj证明：显然，对一切i和j有：u≥,0v≥0。定义iju=∑ui,v=∑vjij则u=0⇔u=0（对一切）iiv=0⇔v=0（对一切j）jTT而u+v=cx−by所以，u=0（对一切i）且v=0（对一切j）⇔u=0且v=0ijTT⇔u+v=0⇔c
5、x−by=0⇔x和是原始－对偶问题最优解。y2注：上述定理隐含着下述事实：ò对最优解x和y，如果对偶中一个约束取严格等式，则原始规划中对应的变量取值必须为0；ò对称地，如果一个非负变量取值为正值，则其对应的约束必取等式。所以，称之为互补松弛性。Farkas引理nFarkas引理描述了R中向量间的一种基本关系。在某种意义下，它反映了对偶的本质。n给定一组向量a∈R(i=,2,L,m)由这组向量{a}生成的锥记为C(a)：iiimnC(ai)={x∈R:x=∑yiai,yi≥,0i=,2,1L,m}i=1{a}即i非负线性组合。x2a1由a1和a
6、2生成的锥a2x13n给定向量的一个集合{a}及另外一个向量c∈R，“如果对一切向量ii=,2,1L,kny∈R，若y在{a}有非负投影，那么y在c上也有非负投影”ii=,2,1L,kFarkas引理断言C在锥C(a)里inn定理3.14（Farkas引理）给定一组向量a∈R(i=,2,L,m)及向量c∈R，则有：iTTay≥,0i=,2,1Lm⇒cy≥0⇔c∈C(a)iinn证明：“⇐”给定一组向量a∈R(i=,2,L,m)及向量c∈R且c∈C(a)，要证明：iinTT对于y∈R，若ay≥,0i=,2,1Lm，则必有cy≥0⇔c∈C(a)。
7、事实上,iimTQc∈C(ai),∴∃yi≥(0i=,2,1L,m)使得c=∑yiai。由已知aiy≥,0i=,2,1Lm，i=1mTT则cy=∑yiaiy≥0。i=14nn“⇒”给定一组向量a∈R(i=,2,L,m)及向量c∈R，满足：对于inTTy∈R，若ay≥,0i=,2,1Lm，则一定有cy≥0⇔c∈C(a)，要证明必有：iic∈C(a)。事实上，可考察下述线性规划问题：iTmincyTay≥,0i=,2,1L,m(LP)iy无限制TT∴Qy＝0是一个可行解，∴(LP)可行。又Qay≥,0i=,2,1L,m及cy≥0，(LP)i有界，
8、∴(LP)的对偶问题：max0TAx=c,j=,2,1L,n(LP)jjx≥0其中T⎛a11a12La1n⎞⎛a1⎞⎜⎟⎜⎟T⎜a21a22La2n⎟⎜a2⎟()A
