第二 对偶问题学习教案

1、会计学1第二第二 对偶对偶(du u)问题问题第一页，共17页。 上述两个LP问题的数学模型是在同一企业的资源状况和生产条件下产生的，且是同一个问题从不同角度考虑所产生的，因此两者密切相关。称这两个LP问题是互为对偶(du u)的两个LP问题。其中一个是另一个问题的对偶(du u)问题。 0,345432.2624min21212121yyyyyyyytsW0,26432452.34max21212121xxxxxxxxtsZ第1页/共17页第二页，共17页。 一般地对于一般地对于(duy)任何一个线性规划问题都有一个与任何一个线性规划问题都有一个与之相对应的对偶问题。原问题与对偶问题的一般形

2、式为：之相对应的对偶问题。原问题与对偶问题的一般形式为：0. .max221122222121112121112211xbxaxaxabxaxaxabxaxaxaxcxcxcjmnmnmmnnnnnnt sZ0. .min221122222112112211112211ycyayayacyayayacyayayaybybybinmmnnnmmmmmmtsW 原问题(wnt)（LP） 对偶问题(wnt)（DP）相应(xingyng)的矩阵形式为：0XbAX.t .sCXZmax0YCYA.t .sYbWmin第2页/共17页第三页，共17页。原问题Max（对偶问题）对偶问题Min（原问题）约束条

3、件数=m 变量个数=m第i个约束条件为“”第i个约束条件为“”第i个约束条件为“=” 第i个变量0 第i个变量0 第i个变量无限制变量个数=n 约束条件个数=n第i个变量0第i个变量0第i个变量无限制 第i个约束条件为“” 第i个约束条件为“” 第i个约束条件为“=”第i个约束条件的右端项目标函第i个变量的系数 目标函数第i个变量的系数 第i个约束条件的右端顶 归纳对称形式归纳对称形式(xngsh)(xngsh)与非对称形式与非对称形式(xngsh)(xngsh)的对偶的对偶, ,原问题与对偶问题之间的关系如下表所示：原问题与对偶问题之间的关系如下表所示：第3页/共17页第四页，共17页。无约

4、束xxxxxxxxxxxxxxxtsZ321321321321321,0,5348321043.422min 例例1 1、写出下列、写出下列(xili)(xili)线性规划问题的对偶问题线性规划问题的对偶问题第4页/共17页第五页，共17页。例例2 2 求解求解(qi ji)(qi ji)下列线性规划问题：下列线性规划问题：)4, 3 ,2, 1( ,01 25246 .52415min32132321itsZyyyyyyyyyi2. 2. 对偶对偶(du u)(du u)单纯形法单纯形法)4 , 3 , 2 , 1( , 01 25246 . .52415ax5321432321/itsZm

5、yyyyyyyyyyyi)4 , 3 , 2 , 1( , 01 25-246- . .52415ax5321432321/itsZmyyyyyyyyyyyi第5页/共17页第六页，共17页。第6页/共17页第七页，共17页。第7页/共17页第八页，共17页。迭代终止条件(tiojin)：所有的Bi非负。第8页/共17页第九页，共17页。第9页/共17页第十页，共17页。3.1 3.1 分析价值分析价值(jizh)(jizh)系数的变化系数的变化3 灵敏度分析(fnx) 在单纯形表中，价值系数的变化仅仅(jnjn)影响到检验数的变化，只需要对检验数进行最优性检验，判断是否需要继续迭代即可。第1

6、0页/共17页第十一页，共17页。 CCBCNCSbXBXNXSCBB-1bIB-1NB-1ZC BB-1b0C BB-1N-CNCB B-1 CCBCNCSbXBXNXSCsbBNIZCBCN03.2 3.2 分析资源系数分析资源系数(xsh)(xsh)的变化的变化资源系数(xsh)的变化对最优单纯形标的b列有影响。第11页/共17页第十二页，共17页。1 1/4- 01/2- 1/4 0 15/2- 5/4 1B Ixxx1543，则对应，在初始单纯形表中，第12页/共17页第十三页，共17页。例题(lt) P652/12/112/35532151 1/4- 01/2- 1/4 0 15/

7、2- 5/4 1bBb 1/第13页/共17页第十四页，共17页。 CCBCNCSbXBXNXSCBB-1bIB-1NB-1ZC BB-1b0C BB-1N-CNCB B-1 CCBCNCSbXBXNXSCsbBNIZCBCN03.3 3.3 增加增加(zngji)(zngji)变量的变化变量的变化1计算该列技术(jsh)系数。2技术(jsh)该列检验数。第14页/共17页第十五页，共17页。207-2431 1/4- 01/2- 1/4 0 15/2- 5/4 1PBP 61/6 例题：投产新产品(chnpn)，所需原料和设备分别为3、4、2单位，利润为3单位，问最优生产计划如何变化？1120207-3 6207- 第15页/共17页第十六页，共17页。3.4 技术系数(xsh)aij的变化 例题：如果乙