资源描述：
《3最优化教案(对偶理论及灵敏性分析)》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。
1、第5章对偶原理及灵敏度分析§5.1线性规划中的对偶理论一、实际问题的提出：实际问题：甲工厂生产ⅠⅡ两种产品，这两种产品都要在A,B,C三种不同的设备上加工，按工艺资料规定：ABC2元Ⅰ2h4h0h3元Ⅱ2h0h5h已知各设备计划期内用于生产这两种产品的能力分别为12h，16h，15h。又知道企业生产一件Ⅰ产品获利2元，生产一件Ⅱ产品获利3元。问企业甲应如何安排生产这两种产品，能使总的利润收入最大？目标函数：maxZ=2x1+3x2约束：S.t.2x1+2x2≤12(a)4x1≤16(b)(LP1)5x2≤15(c)x1,x2≥0最优解(
2、x1,x2)=(3,3)现假设有乙工厂为扩大生产想租借甲工厂拥有的设备资源，问甲工厂分别以什么样的价格才愿意出租自己的设备？64设：A,B,C三种设备每小时出租价格分别为ω1，ω2，ω3，元。一般出租设备的条件是租金收入不低于自己组织生产时的获利收入。所以有2ω1+4ω2≥22ω1+5ω3≥3出租拥有的全部设备的总收入为12ω1+16ω2+15ω3对乙工厂来讲希望在满足上述两条件下，使支付的总的租金最少，因而可以建立另一个线型规划模型：min12ω1+16ω2+15ω32ω1+4ω2≥22ω1+5ω3≥3(LP2)ω1,ω2,ω3≥0最
3、优解(ω1,ω2,ω3)=(1,0,1/5)这是同样资源从不同角度考虑问题所得到的两个线性规划问题，（LP1)称为原问题，(LP2)就称为它的对偶问题。二、数学角度对（LP1)，每给出一个可行解，就给出了（LP1)问题的一个下界，如x(1)=(3,0)T,Z=6x(2)=(0,3)T,Z=9我们想寻求（LP1)的上界641/2（a）+1/4(b)+1(c)得到：2x1+6x2≤25而2x1+3x2≤2x1+6x2≤25即25是（LP1)的一个上界。怎样选择系数，找到（LP1)的上确界呢？设系数分别为ω1,ω2,ω3满足：ω1（a）+ω2
4、(b)+ω3（c）≤12ω1+16ω2+15ω3整理，得：（2ω1+4ω2）x1+（2ω1+5ω3）x2≤12ω1+16ω2+15ω3为了求目标函数的上界，要求满足2ω1+4ω2≥22ω1+5ω3≥3为求上确界，要求min12ω1+16ω2+15ω3这引出了另一个问题(LP2)minZ=12ω1+16ω2+15ω3S.t2ω1+4ω2≥22ω1+5ω3≥3ω1,ω2,ω3≥0与前面一样出现了原/对偶的成对的线型规划问题。总结前面的例题我们得到64原问题：maxf=∑cjxjS.t.∑aijxj≤bii=1…mXj≥0j=1…n对偶问题：
5、(LP2)minZ=∑biωiS.t∑aijωi≥cjj=1…nωi≥0i=1…m矩阵形式：maxcXminbωs.t.AX≤bs.t.ATω≥cX≥0ω≥0对偶问题的对偶是原问题。将(LP2)写成(LP1)的形式，有max∑-biωiS.t.∑-aijωi≤-cjj=1…nωi≥0i=1…m写出它的对偶形式：min∑-cjxjS.t∑-aijxj≥-bii=1…mXj≥0j=1…n64即为：max∑cjxjS.t.∑aijxj≤bii=1…mXj≥0j=1…n三对偶问题的一般形式线形规划中的对偶可以概括为三种形式：1.对称形式的对偶对
6、称形式的对偶定义如下：原问题：≥（5.1.1）≥0对偶问题：≤C（5.1.2）≥0根据对称对偶的定义，原问题中约束条件≥的个数，恰好等于对偶变量的个数；原问题中变量的个数，恰好等于对偶问题中约束条件≤的个数。64按照上述定义，很容易写出一个线性规划问题的对偶问题。例5.1.1设原问题是：≥5≥1≥0那么，上述问题的对偶问题是：≤1≤-1≥02.非对称形式的对偶考虑具有等式约束的线性规划问题：（5.1.3）64≥0为了利用对称对偶的定义给出（5.1.3）的对偶问题，先把（5.1.3）写成等价形式：≥≥≥0即≥（5.1.4）设对偶变量为u，
7、v根据对称对偶的定义，（5.1.4）的对偶问题是：≤≥0令，显然没有非负限制，于是得到：64≤（5.1.5）定义（5.1.5）为（5.1.3）的对偶问题。（5.1.3）和（5.1.5）构成的对偶与称对偶不同，前者原问题中有个等式约束，而且对偶问题中的个变量无正负号限制，它们称为非对称对偶。例5.1.2给定原问题：≥0它的对偶问题是：≤5≤4≤3643.一般情形实际中有许多线性规划问题同时含有“≥”，“≤”及“=”型几种约束条件。下面定义这类线性规划问题的对偶问题。设原问题是：≥=（5.1.6）≤≥0其中，是矩阵，是矩阵，是矩阵，，和分别
8、是维，和维列向量，是维列向量，是维列向量。现在，我们利用非对称对偶的表达式（5.1.3）和（5.1.5）给出（5.1.6）的对偶问题。为此先引入松弛变量，把（5.1.6）写成等价形式：64===≥0其中是由
