运筹学课件第二章线性规划的对偶理论与灵敏度分析

第二章线性规划的对偶理论与灵敏度分析1可编辑ppt一、对偶问题的提出1、

对偶思想举例周长一定的矩形中，以正方形面积最大；面积一定的矩形中，以正方形周长最小；第一节LP的对偶问题2可编辑ppt对偶问题？......对偶理论是线性规划中最重要的理论之一，是深入了解线性规划问题结构的重要理论基础。同时，由于问题提出本身所具有的经济意义，使得它成为对线性规划问题系统进行经济分析和敏感性分析的重要工具。那么，对偶问题是怎样提出的，为什么会产生这样一种问题呢？……3线性规划的对偶理论引例——俩家具制造商间的对话：唉!我想租您的木工和油漆工一用。咋样？价格嘛……好说，肯定不会让您兄弟吃亏讪。

王老板做家具赚了大钱，可惜我老李有高科技产品，却苦于没有足够的木工和油漆工咋办？只有租咯。Hi：王老板，听说近来家具生意很好，也帮帮兄弟我哦!家具生意还真赚钱，但是现在的手机生意这么好，不如干脆把我的木工和油漆工租给他，又能收租金又可做生意。价格嘛……好商量，好商量。只是…...

家具-王总李总桌子椅子能力木工43120漆工2150价格50304可编辑ppt线性规划的对偶理论王老板的家具生产模型：x1、

x2是桌、椅生产量。Z是家具销售总收入（总利润）。maxZ=50x1+30x2s.t.4x1+3x2

≤120（木工）2x1+x2

≤50（油漆工）

x1，x2

≥0原始线性规划问题，记为（P）王老板的资源出租模型：y1、y2单位木、漆工出租价格。W是资源出租租金总收入。minW=120y1+50y2s.t.4y1+2y2

≥503y1+y2

≥30y1，y2

≥0对偶线性规划问题，记为（D）桌子椅子能力木工43120漆工2150价格50305可编辑ppt线性规划的对偶理论王老板按（D）的解y1、y2出租其拥有的木、漆工资源，既保证了自己不吃亏（出租资源的租金收入并不低于自己生产时的销售收入），又使得出租价格对李老板有极大的吸引力（李老板所付出的总租金W最少）。按时下最流行的一个词，叫什么来着————6可编辑ppt对偶问题Minw=YbT=YTbs.t. ATY≥CT Y≥0原始问题maxz=CXs.t.AX≤bX≥0≤maxbACCTATbT≥minmnmn7可编辑ppt

2、

换个角度审视生产计划问题例

要求制定一个生产计划方案，在设备A,B和调试三种资源限制下，使得产品的总利润最大。

maxZ=2x1+x25x2≤156x1+2x2≤24x1+x2≤5x1,x2≥0st.8可编辑ppt转换思路:投资人:如果某投资公司准备购买该工厂，它至少应付出多大的代价，才能使工厂自己放弃生产产品Ⅰ、Ⅱ，而将可利用的资源都出让。被兼并人:该工厂的底线：最低可接受价格，指按这种价格转让资源比自己生产产品Ⅰ、Ⅱ合算的价格。设y1,y2，y3为代表单位时间这三种资源的出让价格，为了使工厂出让资源合算，显然应该使出让原来生产一件产品Ⅰ的资源所得收入不低于自己生产产品Ⅰ的利润，即0y1+6y2+1y3≥2

对于产品Ⅱ，同样可以建立类似的约束条件5y1+2y2+1y3≥1项目产品Ⅰ产品Ⅱ每天可用能力设备A(h)设备B(h)调试工序(h)06152115245利润(元)21y1y2y39可编辑ppt

当原问题和对偶问题都取得最优解时，这一对线性规划对应的目标函数值是相等的：Zmax=Wmin显然在满足这两个约束的前提下，价格越高，该工厂越合算，但价格太高，投资人方面又不会愿意购买。因此，我们需要确定的价格是使工厂合算的最低价格，故应建立目标函数：minw=15y1+24y2+5y3

项目产品Ⅰ产品Ⅱ每天可用能力设备A(h)设备B(h)调试工序(h)06152115245利润(元)2110可编辑ppt

考察原问题和对偶问题的解，给作决策的管理者另一个自由度；

怎样通过增加更多的资源来增加利润？

怎样使用不同类型的资源来增加利润？

对应第一个约束条件对应第二个约束条件（P）maxZ=2X1+X2

5X2

≤15对应第一个对偶变量y1

6X1+2X2

≤24对应第二个对偶变量y2

X1+X2

≤5对应第三个对偶变量y3

X1，X2

≥0（D）minw=15y1+24y2+5y3

6y2+y3

≥25y1+2y2+y3

≥1y1，y2，y3

≥011可编辑ppt二、原问题和对偶问题的关系1、对称形式的对偶关系（1）定义：若原问题是

12可编辑ppt则定义其对偶问题为这两个式子之间的变换关系称为“对称形式的对偶关系”。

13可编辑ppt14可编辑ppt（2）对称形式的对偶关系的矩阵描述（D）（L）

（3）从原问题写出其对偶问题按照定义；记忆法则：“上、下”交换，换后矩阵转置。不等式变号，“极大”变“极小”15可编辑ppt例写出下面线性规划的对偶问题：

16可编辑ppty2=y2’-y2’’y3=-y3’2、非对称形式的对偶关系：（1）原问题对偶问题17可编辑ppt（2）怎样写出非对称形式的对偶问题？把一个等式约束写成两个不等式约束，再根据对称形式的对偶关系定义写出；按照原-对偶表直接写出；（3）原-对偶表18可编辑ppt项目原问题（对偶问题）对偶问题（原问题）目标函数类型maxmin目标函数系数与右边项的对应关系目标函数各变量系数对应约束条件右边项的系数右边项的系数对应目标函数系数变量个数与约束条件个数的对应关系变量个数n约束条件个数m约束条件个数n变量个数m原问题变量类型与对偶问题约束条件类型的对应关系≥0(对称)变量类型≤0(非对称)自由≥(对称)约束条件类型≤(非对称)=原问题约束条件类型与对偶问题变量类型的对应关系≥(非对称)约束条件类型≤(对称)=≤(非对称)变量类型≥(对称)自由19可编辑ppt例题：写出下面线性规划的对偶规划：20可编辑ppt（原问题是极小化问题，因此应从原-对偶表的右边往左边查！）√

×

项目原问题（对偶问题）对偶问题（原问题）目标函数类型maxmin原问题变量类型与对偶问题约束条件类型的对应关系≥0(对称)变量类型≤0(非对称)自由≥(对称)约束条件类型≤(非对称)=原问题约束条件类型与对偶问题变量类型的对应关系≥(非对称)约束条件类型≤(对称)=≤(非对称)变量类型≥(对称)自由21可编辑ppt第二节对偶问题的基本性质原问题对偶问题为对称形式的线性规划问题22可编辑ppt

一、单纯形法的矩阵描述进一步讨论修正单纯形法便于理论推导（如对偶定理的证明）二、矩阵描述关键——写出两个基本的表达式。

2.1单纯形法的矩阵描述23可编辑ppt1、准备工作：（1）标准型的矩阵形式——

（2）将式中矩阵写成分块矩阵形式

24可编辑ppt2、将分块形式代入矩阵形式标准型，得出两个基本表达式：（1）由约束条件

可得用非基变量表示基变量的表达式：25可编辑ppt项目非基变量基变量XBXNXS0XSbBNICj-ZjCBCN0项目基变量非基变量XBXNXSCBXBB-1bIB-1NB-1

Cj-Zj0CN-CBB-1N-CBB-1

迭代后的单纯形表初始单纯形表对应初始单纯形表中的单位阵I，迭代后为B-1基变量的变换：初始XS=b；迭代后XB=B-1b约束系数矩阵的变化：[A,I]=[B,N,I]；[B-1A,B-1I]=[B-1B,B-1N,B-1I]=[I,B-1N,B-1].约束系数矩阵的向量变化：PjT=B-1PjCBCN026可编辑ppt检验数：CN-CBB-1N≤0(1);-CBB-1≤0;

令:CB-CBI=0(2)(1)+(2)得到CN-CBB-1N

+CB-CBI=CN-CBB-1N

+CB-CBB-1B=CB+CN-CBB-1(B+N)=C-CBB-1A≤0-CBB-1≤0;令YT=CBB-1

单纯形乘子

ATY≥CT;

Y≥0Wmin=YTb=CBB-1b=ZmaxC-YTA≤0C≤

YTACT≤(YTA)T检验数的相反数为其对偶问题的一个可行解27可编辑ppt例原问题、对偶问题之间的关系28可编辑ppt项目原问题变量原问题松弛变量x1x2x3x4x5X315/2X17/2X23/200100115/4-15/20¼-1/20-1/43/2-Cj+zj000¼1/2DUAL剩余变量DUAL变量y4y5y1y2y3项目dual变量dual剩余变量y1y2y3y4y5y21/4y31/2-5/41015/201-1/4¼½-3/2Cj-zj

15/2007/23/2原问题松弛变量原问题变量x3x4x5x1x229可编辑ppty1yiymym+1ym+jyn+m

x1xjxn

xn+1xn+ixn+m

对偶问题的变量对偶问题的松弛变量原始问题的变量原始问题的松弛变量xjym+j=0 yixn+i=0 (i=1,2,…,m;j=1,2,…,n)在一对变量中，其中一个大于0，另一个一定等于030可编辑ppt二、对偶问题的基本性质对偶基本性质揭示原问题的解与对偶问题的解之间关系

补充:对称性定理对偶问题的对偶是原问题。31可编辑ppt定理1

弱对偶定理——若一对对称形式的对偶线性规划（L）

和（D）

均有可行解，分别为和，则C≤b。证明思路：由（L）

左乘，得由（D）

右乘，得32可编辑ppt该结论对非对称形式的对偶问题同样成立。•推论:关于“界”的结果；极小化问题有下界——推论1原问题

(极大化问题)的任意一个可行解所对应的目标函数值是其对偶问题目标函数值的一个下界。33可编辑ppt•极大化问题有上界——推论1

对偶问题(极小化问题)的任意一个可行解所对应的目标函数值是其原问题目标函数值的一个上界。•关于最优解无界情况与对偶问题的关系；推论2

若原问题可行，则其目标函数无界的充要条件是对偶问题没有可行解。34可编辑ppt推论3原问题可行，且目标函数值无界==>对偶问题不可行对偶问题可行，且目标函数值无界==>原问题不可行若对偶问题不可行，其原问题或没有可行解或无界解。

原问题有可行解而其对偶问题没有可行解，则原问题的目标函数无界；对偶问题有可行解而其原问题没有可行解，则对偶问题的目标函数无界；35可编辑ppt定理

2最优性定理

若、