IE10_OR06 CH2 线性规划的对偶理论与灵敏度分析1.ppt

《IE10_OR06 CH2 线性规划的对偶理论与灵敏度分析1.ppt》由会员分享，可在线阅读，更多相关《IE10_OR06 CH2 线性规划的对偶理论与灵敏度分析1.ppt（47页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第第1页页西南科技大学制造科学与工程学院工业工程与设计系西南科技大学制造科学与工程学院工业工程与设计系 石宇强石宇强运筹学运筹学第第6 6讲讲 目目 录录 第一章第一章 软件运用补充、总结、习题讲解软件运用补充、总结、习题讲解CH2 CH2 线性规划的对偶理论与灵敏度分析线性规划的对偶理论与灵敏度分析|2.1 2.1 线性规划的对偶问题线性规划的对偶问题|2.2 2.2 对偶问题的基本性质对偶问题的基本性质|2.3 2.3 影子价格影子价格|2.4 2.4 对偶单纯形法对偶单纯形法|2.5 2.5 灵敏度分析灵敏度分析|2.6 2.6 参数线性规划参数线性规划第第2页页西南科技大学制造科学与工

2、程学院工业工程与设计系西南科技大学制造科学与工程学院工业工程与设计系 石宇强石宇强运筹学运筹学软件运用补充软件运用补充用软件求解线性规划问题用软件求解线性规划问题(演示演示)lLindoLindolExcel SolverExcel Solverl北理工软件北理工软件第第1章章 线性规划与单纯形法线性规划与单纯形法 （小结）（小结）n n1.线性规划的概念线性规划的概念（1）线性规划模型的构成）线性规划模型的构成 决策变量决策变量 目标函数目标函数：max(min)Z(是决策变是决策变量的线性函数）量的线性函数）约束条件约束条件：s.t.（满足于含决策变（满足于含决策变量的线性等式或不等式）量

3、的线性等式或不等式）（2）一般形式：）一般形式：vmax=cmax=c1x x1 1+c+c2x x2 2+c+cnx xn n s.t.a s.t.a1111x x1 1+a+a1212x x2 2+a a1n1nx xn n=b=b1 1 v a a2121x x1 1+a+a2222x x2 2+a a2n2nx xn n=b=b2 2v v a am1m1x x1 1+a+am2m2x x2 2+a amnmnx xn n=b=bm mv xj0;j=1,2,n,nv b bi i0;i=0;i=1,2,m,mv(3)标准形式标准形式v 线线性性规规划划的的标标准准形形式式有有如如下下

4、四四个个特特点：点：v 目标最大化；目标最大化；v 约束为线性等式；约束为线性等式；v 决策变量均非负；决策变量均非负；v 右端项非负。右端项非负。v(4)剩余变量、松驰变量及意义剩余变量、松驰变量及意义2.有关线性规划解的概念有关线性规划解的概念n n(1)概念：凸集、可行解、可行域、最概念：凸集、可行解、可行域、最优解、最优值、基、基变量、基解、基优解、最优值、基、基变量、基解、基可行解、可行基、最优基。可行解、可行基、最优基。n n(2)可行域、基解、基可行解、最优基可行域、基解、基可行解、最优基的关系。的关系。3.图解法图解法n n图解法的步骤：图解法的步骤：(1)建立直角坐标系建立直

5、角坐标系(2)图示约束条件、找出可行解图示约束条件、找出可行解(3)图示代表目标函数的直线及目标函数图示代表目标函数的直线及目标函数值增加（或减小）的方向值增加（或减小）的方向(4)找出最优解找出最优解4.单纯形法单纯形法(1)理论基础理论基础n n定理定理若若LP问题可行域存在，则可行问题可行域存在，则可行域是凸集合域是凸集合n n定理定理 LP问题的基可行解与可行域顶问题的基可行解与可行域顶点一一对应点一一对应n n定理定理若若LP问题存在最优解，则一定问题存在最优解，则一定存在一个基可行解是最优解存在一个基可行解是最优解(2)单纯形法计算步骤单纯形法计算步骤线性规划求解流程图线性规划求解

6、流程图5.大大M法与二阶段法法与二阶段法n n(1)大大M法法人工变量在目标函数中的系数确定：人工变量在目标函数中的系数确定：若目标函数为若目标函数为maxZmaxZ，则系数为，则系数为-M-M；否则；否则为为M M计算方法：单纯形法计算方法：单纯形法(2)二阶段法二阶段法第一阶段第一阶段：求解一个目标函数仅含人工变量，：求解一个目标函数仅含人工变量，且为极小化的线性规划问题，其最优表有两且为极小化的线性规划问题，其最优表有两种情况：种情况：目标函数最优值为目标函数最优值为0 0则去掉人工则去掉人工变量转为第二阶段变量转为第二阶段目标函数最优值不为目标函数最优值不为0 0则原问题则原问题无可行

7、解，停止计算无可行解，停止计算第二阶段第二阶段：去掉第一阶段中的人工变量，将第：去掉第一阶段中的人工变量，将第一阶段得到的最优解作为初始基可行解，利一阶段得到的最优解作为初始基可行解，利用单纯形法继续进行迭代，直至求出原问题用单纯形法继续进行迭代，直至求出原问题最优解最优解v第第14页页西南科技大学制造科学与工程学院工业工程与设计系西南科技大学制造科学与工程学院工业工程与设计系 石宇强石宇强运筹学运筹学习题习题1.7 1.7(2)(2)(4)(4)第第15页页西南科技大学制造科学与工程学院工业工程与设计系西南科技大学制造科学与工程学院工业工程与设计系 石宇强石宇强运筹学运筹学2.1 2.1 线

8、性规划的对偶问题线性规划的对偶问题|一、问题的提出一、问题的提出 例例1 1 某工厂可生产甲、乙两种产品，需消耗煤、电、某工厂可生产甲、乙两种产品，需消耗煤、电、油三种资源。现将有关数据列表如下：油三种资源。现将有关数据列表如下：试拟订使总收入最大的生产方案。试拟订使总收入最大的生产方案。资源单耗资源单耗 产品产品资源资源甲甲 乙乙资源限量资源限量煤煤电电油油9 44 5 3 10360200300单位产品价格单位产品价格 7 12第第16页页西南科技大学制造科学与工程学院工业工程与设计系西南科技大学制造科学与工程学院工业工程与设计系 石宇强石宇强运筹学运筹学资源单耗资源单耗 产品产品资源资源

9、甲甲 乙乙资源限量资源限量煤煤电电油油9 44 5 3 10360200300单位产品价格单位产品价格 7 12第第17页页西南科技大学制造科学与工程学院工业工程与设计系西南科技大学制造科学与工程学院工业工程与设计系 石宇强石宇强运筹学运筹学 例例2 2 这时有另一家厂商提出要购买其煤、电、这时有另一家厂商提出要购买其煤、电、油全部资源，并希望花费尽量少。试建立购买者油全部资源，并希望花费尽量少。试建立购买者的线性规划模型。的线性规划模型。例例2 2称为例称为例1 1的的对偶问题对偶问题，记为（，记为（D D），），例例1 1称为例称为例2 2的的原问题原问题,记为（记为（P P）。）。资源单

10、耗资源单耗 产品产品资源资源甲甲 乙乙资源限量资源限量煤煤电电油油9 44 5 3 10360200300单位产品价格单位产品价格 7 12第第18页页西南科技大学制造科学与工程学院工业工程与设计系西南科技大学制造科学与工程学院工业工程与设计系 石宇强石宇强运筹学运筹学例例2 2称为例称为例1 1的的对偶问题对偶问题，记，记为（为（D D），例），例1 1称为例称为例2 2的的原原问题问题,记为（记为（P P）。）。第第19页页西南科技大学制造科学与工程学院工业工程与设计系西南科技大学制造科学与工程学院工业工程与设计系 石宇强石宇强运筹学运筹学 LP OPTIMUM FOUND AT STEP

11、 1 OBJECTIVE FUNCTION VALUE 1)428.0000 VARIABLE VALUE REDUCED COST X1 20.000000 0.000000 X2 24.000000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2)84.000000 0.000000 3)0.000000 1.360000 4)0.000000 0.520000 NO.ITERATIONS=1v LP OPTIMUM FOUND AT STEP 1v OBJECTIVE FUNCTION VALUEv 1)428.0000VARIABLE VALUE

12、 REDUCED COSTv Y1 0.000000 84.000000v Y2 1.360000 0.000000v Y3 0.520000 0.000000 ROW SLACK OR SURPLUS DUAL PRICESv 2)0.000000 -20.000000v 3)0.000000 -24.000000v NO.ITERATIONS=1第第20页页西南科技大学制造科学与工程学院工业工程与设计系西南科技大学制造科学与工程学院工业工程与设计系 石宇强石宇强运筹学运筹学2.1 2.1 线性规划的对偶问题线性规划的对偶问题|二、对称形式下对偶问题的一般形式二、对称形式下对偶问题的一般形式

13、 （P）（D）第第21页页西南科技大学制造科学与工程学院工业工程与设计系西南科技大学制造科学与工程学院工业工程与设计系 石宇强石宇强运筹学运筹学这是最常见的对偶模型形式，称为这是最常见的对偶模型形式，称为对称式对偶模型对称式对偶模型。二者间具有十分对称的对应关系：二者间具有十分对称的对应关系：原问题（原问题（P P）对偶问题对偶问题 （D D）目标目标maxmax型型 目标目标minmin型型 有有n n个变量（非负）个变量（非负）有有n n个约束（大于等于）个约束（大于等于）有有m m个约束个约束 （小于等于）（小于等于）有有m m个变量（非负）个变量（非负）价格系数价格系数 资源向量资源向

14、量 资源向量资源向量 价格系数价格系数 技术系数矩阵技术系数矩阵 技术系数矩阵的转置技术系数矩阵的转置第第22页页西南科技大学制造科学与工程学院工业工程与设计系西南科技大学制造科学与工程学院工业工程与设计系 石宇强石宇强运筹学运筹学对称形式：对称形式：互为对偶互为对偶 (LP)Max (LP)Max z z=c cT T x x (DP)Min (DP)Min f f=b bT T y y s.t.s.t.AxAx b b s.t.s.t.A AT T y y c cT T x x 0 0 y y 0 0 “Max-Max-”“Min-Min-”minbACTCATbTmaxmnmn第第23页

15、页西南科技大学制造科学与工程学院工业工程与设计系西南科技大学制造科学与工程学院工业工程与设计系 石宇强石宇强运筹学运筹学2.1 2.1 线性规划的对偶问题线性规划的对偶问题|三、非对称形式下的原三、非对称形式下的原-对偶问题关系对偶问题关系 原问题（原问题（P P）对偶问题对偶问题 （D D）第第i个约束为等式约束个约束为等式约束 第第i个变量为自由变量个变量为自由变量 第第j个变量为自由变量个变量为自由变量 第第j个约束为等式约束个约束为等式约束 参考参考P52 表表2-2第第24页页西南科技大学制造科学与工程学院工业工程与设计系西南科技大学制造科学与工程学院工业工程与设计系 石宇强石宇强运

16、筹学运筹学原问题Max（对偶问题）对偶问题Min（原问题）约束条件数=m 变量个数=m第i个约束条件为“”第i个约束条件为“”第i个约束条件为“=”第i个变量0 第i个变量0 第i个变量无限制变量个数=n 约束条件个数=n第i个变量0第i个变量0第i个变量无限制 第i个约束条件为“”第i个约束条件为“”第i个约束条件为“=”第i个约束条件的右端项目标函第i个变量的系数 目标函数第i个变量的系数 第i个约束条件的右端顶归纳对称形式与非对称形式的对偶归纳对称形式与非对称形式的对偶,原问题与对偶问题之间原问题与对偶问题之间的关系如下表所示的关系如下表所示例例3：写出下面线性规划的对偶规划模型：写出下

17、面线性规划的对偶规划模型：例4 写出下面线性规划的对偶规划模型 再根据非对称形式的对应关系，直接写出对偶规划解 先将约束条件变形为“”形式第第29页页西南科技大学制造科学与工程学院工业工程与设计系西南科技大学制造科学与工程学院工业工程与设计系 石宇强石宇强运筹学运筹学2.2 2.2 对偶问题的基本性质对偶问题的基本性质一、单纯形法的矩阵描述一、单纯形法的矩阵描述 max=CX s.t.AX=b X0 A=B,N,C=(CB,CN),X=则有则有:max=CBXB+CNXN x.t.BXB+NXN=b XB,XN0 XB=B-1b-B-1NXN =CB(B-1b-B-1NXN)+CNXN =CB

18、B-1b+(CN-CBB-1N)XNXBXN第第30页页西南科技大学制造科学与工程学院工业工程与设计系西南科技大学制造科学与工程学院工业工程与设计系 石宇强石宇强运筹学运筹学 单纯形表单纯形表 Z XB XN 0 I B-1N B-1b 1 0 CN-CBB-1N -CBB-1b 第第31页页西南科技大学制造科学与工程学院工业工程与设计系西南科技大学制造科学与工程学院工业工程与设计系 石宇强石宇强运筹学运筹学补充：矩阵形式的单纯形表补充：矩阵形式的单纯形表加入松驰变量加入松驰变量化为标准形化为标准形设设C=（CB,CN),A=(B,N),代入代入(2)得得:(2)第第32页页西南科技大学制造科

19、学与工程学院工业工程与设计系西南科技大学制造科学与工程学院工业工程与设计系 石宇强石宇强运筹学运筹学将基变量从目标函数中消除将基变量从目标函数中消除建立对应于基建立对应于基B B的矩阵形式的单纯形表的矩阵形式的单纯形表T T（B B）：）：第第33页页西南科技大学制造科学与工程学院工业工程与设计系西南科技大学制造科学与工程学院工业工程与设计系 石宇强石宇强运筹学运筹学 CCBCNCSbXBXNXSXBB-1bIB-1NB-1Z-C BB-1b0CN-C BB-1NCB B-1B-1AC-CBB-1AbXXBB-1bB-1AZ-C BB-1bC-C BB-1A化简为如下简单的表格形式化简为如下简

20、单的表格形式:v第第34页页西南科技大学制造科学与工程学院工业工程与设计系西南科技大学制造科学与工程学院工业工程与设计系 石宇强石宇强运筹学运筹学2.2 2.2 对偶问题的基本性质对偶问题的基本性质1.1.对称性对称性 （P P）与（）与（D D）互为对偶。）互为对偶。|对偶问题的对偶问题是原问题对偶问题的对偶问题是原问题v（P）v（D）v二、对偶问题的基本性质二、对偶问题的基本性质v第第35页页西南科技大学制造科学与工程学院工业工程与设计系西南科技大学制造科学与工程学院工业工程与设计系 石宇强石宇强运筹学运筹学2 2 弱弱对偶定理对偶定理 对偶问题对偶问题(min)(min)的任何可行解的任

21、何可行解Y Y0 0，其目标函数其目标函数值总是不小于原问题值总是不小于原问题(max)(max)任何可行解任何可行解X X0 0的目的目标函数值标函数值v几何意义：几何意义：vCXvYbv第第36页页西南科技大学制造科学与工程学院工业工程与设计系西南科技大学制造科学与工程学院工业工程与设计系 石宇强石宇强运筹学运筹学 弱弱对偶定理推论对偶定理推论|maxmax问题的任何可行解目标函数值是其对偶问题的任何可行解目标函数值是其对偶minmin问题目标函数值的下限；问题目标函数值的下限；minmin问题的任问题的任何可行解目标函数值是其对偶何可行解目标函数值是其对偶maxmax问题目标问题目标函数

22、值的上限函数值的上限|如果原如果原max(min)max(min)问题为无界解，则其对偶问题为无界解，则其对偶min(max)min(max)问题无可行解问题无可行解|如果原如果原max(min)max(min)问题有可行解，其对偶问题有可行解，其对偶min min(max)(max)问题无可行解，则原问题为无界解问题无可行解，则原问题为无界解v第第37页页西南科技大学制造科学与工程学院工业工程与设计系西南科技大学制造科学与工程学院工业工程与设计系 石宇强石宇强运筹学运筹学3 3 3 3 最优解判别最优解判别最优解判别最优解判别定理定理定理定理 若原问题的某个可行解若原问题的某个可行解X X0

23、 0的目标函数值的目标函数值与对偶问题某个可行解与对偶问题某个可行解Y Y0 0的目标函数值的目标函数值相等，则相等，则X X0 0,Y Y0 0分别是相应问题的最优解分别是相应问题的最优解.证：由弱对偶定理推论证：由弱对偶定理推论1 1，结论是显然的。，结论是显然的。即即CXCX0 0 =Y Y0 0b b CXCX,Y Y0 0b b=CXCX0 0 YbYb 。证毕。证毕。v第第38页页西南科技大学制造科学与工程学院工业工程与设计系西南科技大学制造科学与工程学院工业工程与设计系 石宇强石宇强运筹学运筹学 4 4 主对偶主对偶定理定理 如果原问题和对偶问题都有可行解，则如果原问题和对偶问题

24、都有可行解，则它们都有最优解，且它们的最优解的目它们都有最优解，且它们的最优解的目标函数值相等。标函数值相等。5.5.对偶定理对偶定理 若（若（P P）有最优解，则（有最优解，则（D D）也也有最优解，有最优解，且最优值相同。且最优值相同。v证：对（证：对（P P）增加松弛变量）增加松弛变量XsXs，化为，化为v设其最优基为设其最优基为B B，终表为，终表为v其检验数为其检验数为问题：问题：问题：问题：(1)(1)由性质由性质由性质由性质5 5可知，对偶问题最优解的表达式可知，对偶问题最优解的表达式可知，对偶问题最优解的表达式可知，对偶问题最优解的表达式 Y*Y*=？v(2)求求Y*是否有必要

25、重新求解（是否有必要重新求解（D）？）？v CBB-1v 不必。可以从原问题（不必。可以从原问题（P）的单纯形终表获得。的单纯形终表获得。v例如，已知例如，已知v的终表的终表为为v请指出其对偶问题的最优解和最优请指出其对偶问题的最优解和最优值。值。v第第41页页西南科技大学制造科学与工程学院工业工程与设计系西南科技大学制造科学与工程学院工业工程与设计系 石宇强石宇强运筹学运筹学v 6.6.互补松驰性互补松驰性(松紧定理松紧定理)：若：若X X，分别分别是是(P),(D)(P),(D)问题的可行解，那么问题的可行解，那么X,X,为最优解的为最优解的充要条件是：充要条件是：v XXS S=0,Y=

26、0,YS SX=0X=0v (即若即若 A Ai iXbX =i i=0=0v A Ai iX=bX=bi i =0 0 v P Pj j=C=Cj j =X 00v P Pj jCCj j=X=Xj j=0)=0)v v v v v v v v例例 已知线性规划问题已知线性规划问题 v已知其对偶问题的最优解为已知其对偶问题的最优解为 用对偶理论求原问题的最优解。用对偶理论求原问题的最优解。v解解 先写出它的对偶问题先写出它的对偶问题minv将将 代代入入对对偶偶问问题题的的约约束束条条件件，得得第第2,3,4个个约约束束条条件件为为严严格格不不 等等 式式，第第 1、5个个 约约 束束 条条

27、 件件 为为 严严 格格 等等 式式，由由 互互 补补 松松 驰驰 性性 得得 ；又因又因 ，原问题的两个约束条件应取等式，故有，原问题的两个约束条件应取等式，故有maxv v 求解后得求解后得 ；故原问题的最优解为故原问题的最优解为 v第第44页页西南科技大学制造科学与工程学院工业工程与设计系西南科技大学制造科学与工程学院工业工程与设计系 石宇强石宇强运筹学运筹学|7.7.原问题单纯形表的检验数行对应其对偶问原问题单纯形表的检验数行对应其对偶问题的一个基解题的一个基解.v其对应关系见表：其对应关系见表：v X XB B X XN N X XS Sv 0 C0 CN N-C-CB BB B-1

28、-1N -CN -CB BB B-1 1v Y YS1S1 Y YS2S2 -Y -YvY YS1S1为对应原问题中基变量为对应原问题中基变量X XB B的剩余的剩余变量，变量，Y YS2S2是对应原问题中非基变量是对应原问题中非基变量X XN N的剩余变量的剩余变量v第第45页页西南科技大学制造科学与工程学院工业工程与设计系西南科技大学制造科学与工程学院工业工程与设计系 石宇强石宇强运筹学运筹学|设设B B是原问题的一个基本可行基，则是原问题的一个基本可行基，则A=(B,N)A=(B,N)max=C max=CB BX XB B+C+CN NX XN N BX BXB B+NX+NXN N+

29、X+XS S=b=b X XB B,X,XN N,X,XS S00相应地对偶问题可表示为相应地对偶问题可表示为 min=Ybmin=Yb YB-Y YB-YS1S1=C=CB B YN-Y YN-YS2S2=C=CN N Y,Y Y,YS1S1,Y,YS2S200v令令Y=CBB-1，则，则v YS1=0v -YS2=CN-CBB-1Nv 例例.max=x1+4x2+3x3v s.t.2x1+2x2+x34v x1+2x2+2x36v xj0v对偶问题为对偶问题为v min=4y1+6y2v s.t.2y1+y21v 2y1+2y24 v y1+2y23v y1,y20 v v初始单纯形表为初始单纯形表为v 4 2 2 1 1 0 v 6 1 2 2 0 1 v 0 1 4 3 0 0v 对偶问题的基本解为对偶问题的基本解为y1=0,y2=0，ys1=-1，ys2=-4，ys3=-3v其最终表为其最终表为v1 3/2 1 0 1 -1/2v2 1 0 1 1 1v-10 2 0 0 1 -1v 由原问题的最终表可知，由原问题的最终表可知，y1=1,y2=1(最优解最优解)，ys1=2vmax=x1+4x2+3x3v s.t.2x1+2x2+x34v x1+2x2+2x36v xj0