《3最优化教案(对偶理论及灵敏性分析).doc》由会员分享，可在线阅读，更多相关《3最优化教案(对偶理论及灵敏性分析).doc（64页珍藏版）》请在金锄头文库上搜索。
1、第5章对偶原理及灵敏度分析5.1线性规划中的对偶理论一、实际问题的提出：实际问题：甲工厂生产两种产品，这两种产品都要在A,B,C三种不同的设备上加工，按工艺资料规定：ABC2元2h4h0h3元2h0h5h已知各设备计划期内用于生产这两种产品的能力分别为12h，16h，15h。又知道企业生产一件产品获利2元，生产一件产品获利3元。问企业甲应如何安排生产这两种产品，能使总的利润收入最大？目标函数： max Z=2x1+3x2约束： S.t. 2x1 +2x2 12 (a) 4x1 16 (b) (LP1)5x215 (c)x1,x20最优解(x1,x2)=(3,3) 现假设有乙工厂为扩大生产想租借
2、甲工厂拥有的设备资源，问甲工厂分别以什么样的价格才愿意出租自己的设备？设：A,B,C三种设备每小时出租价格分别为1，2，3，元。一般出租设备的条件是租金收入不低于自己组织生产时的获利收入。所以有 21+42 2 21+ 533出租拥有的全部设备的总收入为121+162+153对乙工厂来讲希望在满足上述两条件下，使支付的总的租金最少，因而可以建立另一个线型规划模型：min 121+162+153 21+42 2 21+ 533 (LP2)1,2 ,30 最优解(1,2 ,3)=(1,0,1/5)这是同样资源从不同角度考虑问题所得到的两个线性规划问题，（LP1)称为原问题，(LP2)就称为它的对偶
3、问题。二、数学角度对（LP1)，每给出一个可行解，就给出了（LP1)问题的一个下界，如x(1)=(3,0)T, Z=6x(2)=(0,3)T, Z=9我们想寻求（LP1)的上界 1/2（a）+1/4(b)+1(c)得到： 2x1 +6x2 25而 2x1 +3x2 2x1 +6x2 25即25是（LP1)的一个上界。怎样选择系数，找到（LP1)的上确界呢？设系数分别为1,2 ,3满足：1（a）+2 (b)+3（c）121+162+153整理，得：（21+42）x1+（21+ 53）x2121+162+153为了求目标函数的上界，要求满足21+42 2 21+ 533为求上确界，要求min 12
4、1+162+153这引出了另一个问题(LP2) min Z=121+162+153 S.t 21+42 2 21+ 5331,2 ,30与前面一样出现了原/对偶的成对的线型规划问题。总结前面的例题我们得到原问题： max f=cjxj S.t. aij xj bi i=1mXj0 j=1n对偶问题：(LP2) min Z=bii S.t aijicj j=1ni0 i=1m矩阵形式：max cX min b s.t.AXb s.t. ATc X0 0对偶问题的对偶是原问题。将(LP2)写成(LP1)的形式，有max -bii S.t. -aiji -cj j=1ni0 i=1m写出它的对偶形式
5、：min - cjxj S.t -aijxj-bi i=1mXj0 j=1n即为： max cjxj S.t. aij xj bi i=1mXj0 j=1n三对偶问题的一般形式线形规划中的对偶可以概括为三种形式：1. 对称形式的对偶对称形式的对偶定义如下：原问题： （5.1.1） 0对偶问题： C （5.1.2） 0根据对称对偶的定义，原问题中约束条件的个数，恰好等于对偶变量的个数；原问题中变量的个数，恰好等于对偶问题中约束条件的个数。 按照上述定义，很容易写出一个线性规划问题的对偶问题。 例5.1.1 设原问题是： 5 1 0 那么，上述问题的对偶问题是： 1 -1 0 2.非对称形式的对偶
6、 考虑具有等式约束的线性规划问题： （5.1.3） 0 为了利用对称对偶的定义给出（5.1.3）的对偶问题，先把（5.1.3）写成等价形式： 0即 （5.1.4） 设对偶变量为u，v根据对称对偶的定义，（5.1.4）的对偶问题是： 0令，显然没有非负限制，于是得到： （5.1.5）定义（5.1.5）为（5.1.3）的对偶问题。（5.1.3）和（5.1.5）构成的对偶与称对偶不同，前者原问题中有个等式约束，而且对偶问题中的个变量无正负号限制，它们称为非对称对偶。 例5.1.2 给定原问题： 0它的对偶问题是： 5 4 3 3.一般情形 实际中有许多线性规划问题同时含有“”，“”及“=”型几种约束
7、条件。下面定义这类线性规划问题的对偶问题。 设原问题是： = （5.1.6） 0 其中，是 矩阵，是矩阵，是矩阵，和分别是维，和 维列向量，是维列向量，是维列向量。 现在，我们利用非对称对偶的表达式（5.1.3）和（5.1.5）给出（5.1.6）的对偶问题。为此先引入松弛变量，把（5.1.6）写成等价形式： = = = 0其中是由个松弛变量组成的维列向量，是由个松弛变量组成的维列向量。上述问题 （5.1.7）按照非对称对偶的定义，（5.1.7）的对偶问题是： 即 （5.1.8） 0 0 无限制其中，和分别是由变量组成的维，维，和维行向量。定义（5.1.8）为（5.1.6）的对偶问题。由（5.1
8、.8）可知，原问题中的约束所对应的对偶变量有非负限制，所对应的对偶变量无正负限制，所对应的对偶变量有非正限制。根据以上分析，我们可以总结出构成对偶规划的一般规则原问题（对偶问题） 对偶问题（原问题）目标函数：max 目标函数：min决策变量：n个 约束条件 n个 (0) () （0） （）无限制 （=）目标函数决策变量系数 约束条件右端项约束条件：m个 决策变量：m个 （） (0) () （0） （=） 无限制 例 25 2 （5.1.9） =3 0 -1 1 =1 0，0 5.1.2 对偶定理 下面研究对偶的基本性质。由于不同形式的对偶可以互相转化，因此我们仅叙述并证明关于对称对偶的几个重要定理，其结论对于其他形式的对偶仍成立。原问题： （5.1.1） 0对偶问题： C （5.1.2） 0定理 5.1.1 设和分别是（5.1.1）和（5.1.2）的可行解，则。证明：利用对偶定义很容易得出定理的结论。由于和0，则有 （5.1.10）由于和0，则有 （5.1.11）由（5.1.10）和（5.1.11）即知 证毕 上述定理表明，就原问题和对偶问题的可行解而言，对于对偶中的两个问题，每一个问题的任何一个可行解处的目标函数值都给出另一个问题的目标函数值的界。极小化问题给出极大化问题的目标函数值的上界；极大化问题给出极小化问题的目标函数值的下
