《最优化教案(对偶理论及灵敏性分析)》由会员分享，可在线阅读，更多相关《最优化教案(对偶理论及灵敏性分析)（64页珍藏版）》请在金锄头文库上搜索。
1、1第第 5 章对偶原理及灵敏度分析章对偶原理及灵敏度分析 5.15.1 线性规划中的对偶理论线性规划中的对偶理论 一、实际问题的提出：一、实际问题的提出： 实际问题：甲工厂生产实际问题：甲工厂生产两种产品，这两种产品都两种产品，这两种产品都 要在要在 A,B,CA,B,C 三种不同的设备上加工，按工艺资料规定：三种不同的设备上加工，按工艺资料规定：A AB BC C 2 2 元元2h2h4h4h0h0h 3 3 元元2h2h0h0h5h5h 已知各设备计划期内用于生产这两种产品的已知各设备计划期内用于生产这两种产品的 能力分别为能力分别为 12h12h，16h16h，15h15h。又知道企业生
2、。又知道企业生 产一件产一件产品获利产品获利 2 2 元，生产一件元，生产一件产品获产品获 利利 3 3 元。问企业甲应如何安排生产这两种产元。问企业甲应如何安排生产这两种产 品，能使总的利润收入最大？品，能使总的利润收入最大？ 目标函数：目标函数： maxmax Z=2xZ=2x1 1+3x+3x2 2 约束：约束： S.t.S.t. 2x2x1 1 +2x+2x2 2 1212 (a)(a)4x4x1 1 1616 (b)(b) (LP1)(LP1) 5x5x2 21515 (c)(c) x x1 1,x,x2 200 最优解最优解(x(x1 1,x,x2 2)=(3,3)=(3,3)现假
3、设有乙工厂为扩大生产想租借甲工厂拥有的设现假设有乙工厂为扩大生产想租借甲工厂拥有的设 备资源，问甲工厂分别以什么样的价格才愿意出租自备资源，问甲工厂分别以什么样的价格才愿意出租自2己的设备？己的设备？ 设：设：A,B,CA,B,C 三种设备每小时出租价格分别为三种设备每小时出租价格分别为 1 1，2 2，3 3，元。一般出租设备的条件是租金收入不元。一般出租设备的条件是租金收入不 低于自己组织生产时的获利收入。所以有低于自己组织生产时的获利收入。所以有221 1+4+42 2 22221 1+ + 553 333 出租拥有的全部设备的总收入为出租拥有的全部设备的总收入为12121 1+16+1
4、62 2+15+153 3 对乙工厂来讲希望在满足上述两条件下，使支付的总对乙工厂来讲希望在满足上述两条件下，使支付的总 的租金最少，因而可以建立另一个线型规划模型：的租金最少，因而可以建立另一个线型规划模型：minmin 12121 1+16+162 2+15+153 3221 1+4+42 2 22221 1+ + 553 333 (LP2)(LP2) 1 1,2 2 , ,3 300最优解最优解(1 1,2 2 , ,3 3)=(1,0,1/5)=(1,0,1/5) 这是同样资源从不同角度考虑问题所得到的两个线这是同样资源从不同角度考虑问题所得到的两个线 性规划问题，性规划问题， （LP
5、1)LP1)称为原问题，称为原问题，(LP2)(LP2)就称为它的对就称为它的对 偶问题。偶问题。 二、数学角度二、数学角度 对（对（LP1)LP1)，每给出一个可行解，就给出了（，每给出一个可行解，就给出了（LP1)LP1)问题问题 的一个下界，如的一个下界，如 x x(1)(1)=(3,0)=(3,0)T T, , Z=6Z=6x x(2)(2)=(0,3)=(0,3)T T, , Z=9Z=93我们想寻求（我们想寻求（LP1)LP1)的上界的上界1/21/2（a a）+1/4(b)+1(c)+1/4(b)+1(c) 得到：得到： 2x2x1 1 +6x+6x2 2 2525 而而 2x2
6、x1 1 +3x+3x2 2 2x2x1 1 +6x+6x2 2 2525 即即 2525 是（是（LP1)LP1)的一个上界。怎样选择系数，找到的一个上界。怎样选择系数，找到 （LP1)LP1)的上确界呢？设系数分别为的上确界呢？设系数分别为 1 1,2 2 , ,3 3 满足：满足： 1 1（a a）+2 2 (b)+(b)+3 3（c c）12121 1+16+162 2+15+153 3 整理，得：整理，得： （221 1+4+42 2）x x1 1+ +（221 1+ + 553 3）x x2 212121 1+16+162 2+15+153 3 为了求目标函数的上界，要求满足为了求
7、目标函数的上界，要求满足221 1+4+42 2 22221 1+ + 553 333 为求上确界，要求为求上确界，要求minmin 12121 1+16+162 2+15+153 3 这引出了另一个问题这引出了另一个问题(LP2)(LP2) minmin Z=12Z=121 1+16+162 2+15+153 3S.tS.t 221 1+4+42 2 22221 1+ + 553 333 1 1,2 2 , ,3 300 与前面一样出现了原与前面一样出现了原/ /对偶的成对的线型规划问题。对偶的成对的线型规划问题。4总结前面的例题我们得到总结前面的例题我们得到 原问题：原问题： maxmax
8、 f=cf=cj jx xj jS.t.S.t. a aijij x xj j bbi i i=1mi=1m X Xj j00 j=1nj=1n 对偶问题：对偶问题：(LP2)(LP2) minmin Z=bZ=bi ii iS.tS.t aaijiji iccj j j=1nj=1n i i00 i=1mi=1m矩阵形式：矩阵形式：maxmax cXcX minmin bbs.t.AXbs.t.AXb s.t.s.t. A AT TccX0X0 00对偶问题的对偶是原问题对偶问题的对偶是原问题。 将将(LP2)(LP2)写成写成(LP1)(LP1)的形式，有的形式，有maxmax -b-bi
9、 ii iS.t.S.t. -a-aijiji i -c-cj j j=1nj=1n i i00 i=1mi=1m 写出它的对偶形式：写出它的对偶形式：minmin - c cj jx xj jS.tS.t -a-aijijx xj j-b-bi i i=1mi=1m X Xj j00 j=1nj=1n5即为：即为： maxmax ccj jx xj jS.t.S.t. a aijij x xj j bbi i i=1mi=1m X Xj j00 j=1nj=1n 三对偶问题的一般形式三对偶问题的一般形式 线形规划中的对偶可以概括为三种形式：线形规划中的对偶可以概括为三种形式： 1.1.对称形
10、式的对偶对称形式的对偶 对称形式的对偶定义如下：对称形式的对偶定义如下：原问题：原问题： mincx （5.1.15.1.1）ts.Axb0x对偶问题：对偶问题：maxwbCC （5.1.25.1.2）ts.wA00w根据对称对偶的定义，原问题中约束条件根据对称对偶的定义，原问题中约束条件的个的个xAiib数，恰好等于对偶变量的个数；数，恰好等于对偶变量的个数； 原问题中变量的个数，恰好等于对偶问题中约束条件原问题中变量的个数，恰好等于对偶问题中约束条件6的个数。的个数。jwpic按照上述定义，很容易写出一个线性规划问题的对按照上述定义，很容易写出一个线性规划问题的对 偶问题。偶问题。例例 5
11、.1.1.1.1 设原问题是：设原问题是：min21xx 55ts.21xx 11212xx 0021,xx那么，上述问题的对偶问题是：那么，上述问题的对偶问题是：max215ww 11ts.21ww -1-1212ww 0021,ww2.2.非对称形式的对偶非对称形式的对偶考虑具有等式约束的线性规划问题：考虑具有等式约束的线性规划问题：mincx7（5.1.3.1.3）ts.bAx 0x为了利用对称对偶的定义给出（为了利用对称对偶的定义给出（5.1.3.1.3）的对偶问题，）的对偶问题， 先把（先把（5.1.3.1.3）写成等价形式：）写成等价形式：mincxts.AxbAxb0x即即min
12、cx （5.1.4.1.4） ts.xAA bb设对偶变量为设对偶变量为 u u，v v 根据对称对偶的定义，根据对称对偶的定义， （5.1.4.1.4）的对偶问题是：）的对偶问题是：maxvbub ts.vAuAc80vu,令令，显然，显然没有非负限制，于是得到：没有非负限制，于是得到：vuwwmaxwb （5.1.5.1.5）ts.wAc定义（定义（5.1.5.1.5）为（）为（5.1.3.1.3）的对偶问题。）的对偶问题。 （5.1.3.1.3）和）和 （5.1.5.1.5）构成的对偶与称对偶不同，前者原问题中）构成的对偶与称对偶不同，前者原问题中有有个等式约束，而且对偶问题中的个等式约
13、束，而且对偶问题中的个变量无正个变量无正mm负号限制，它们称为非对称对偶。负号限制，它们称为非对称对偶。例例 5.1.25.1.2 给定原问题：给定原问题：min321345xxxts.4321xxx523321xxx0321,xxx它的对偶问题是：它的对偶问题是：max2154ww 5ts.213ww 94212ww 321ww 3. .一般情形一般情形实际中有许多线性规划问题同时含有实际中有许多线性规划问题同时含有“”“” ， “”“”及及“=”“=”型几种约束条件。下面定义这类线型几种约束条件。下面定义这类线 性规划问题的对偶问题。性规划问题的对偶问题。设原问题是：设原问题是：mincxts.xA11b= = （5.1.65.1.6）xA22bxA33b0 x其中，其中，是是 矩阵，矩阵，是是矩阵，矩阵，1Anm 12Anm 2是是矩阵，矩阵，和和分别是分别是维，维，3Anm 31b2b3b1m和和 维列向量，维列向量，是是维列向量，维列向量，是是2m3mcnx维
