第二-对偶问题.pptx

解解:1)1)决策变量：决策变量：设设y y1 1,y,y2 2分别表示收购单位原分别表示收购单位原材料和单位工时的价格。材料和单位工时的价格。3)3)约约束束条条件件:工工厂厂决决策策者者考考虑虑出出售售原原材材料料和和出出租租设设备备应应不不少少于于自自己己生生产产产产品品的的获获利利，否否则则不不如自己生产为好。因此有如自己生产为好。因此有 2 2）目标函数：）目标函数：客户的收购成本为客户的收购成本为W=24yW=24y1 1+26y+26y2 2,目标函数为：目标函数为：Min W=24yMin W=24y1 1+26y+26y2 2 上述两个LP问题的数学模型是在同一企业的资源状况和生产条件下产生的，且是同一个问题从不同角度考虑所产生的，因此两者密切相关。称这两个LP问题是互为对偶的两个LP问题。其中一个是另一个问题的对偶问题。一般地对于任何一个线性规划问题都有一个与之相一般地对于任何一个线性规划问题都有一个与之相对应的对偶问题。原问题与对偶问题的一般形式为：对应的对偶问题。原问题与对偶问题的一般形式为：原问题（原问题（LPLP）对偶问题（对偶问题（DPDP）相应的矩阵形式为：原问题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个约束条件的右端顶 归纳对称形式与非对称形式的对偶归纳对称形式与非对称形式的对偶,原问题与对偶问原问题与对偶问题之间的关系如下表所示：题之间的关系如下表所示：例例1 1、写出下列线性规划问题的对偶问题、写出下列线性规划问题的对偶问题例例2 2 求解下列线性规划问题：求解下列线性规划问题：2.2.对偶单纯形法对偶单纯形法迭代终止条件：所有的Bi非负。3.1 3.1 分析价值系数的变化分析价值系数的变化3 灵敏度分析 在单纯形表中，价值系数的变化仅仅影响到检验数的变化，只需要对检验数进行最优性检验，判断是否需要继续迭代即可。CCBCNCSbXBXNXSCBB-1bIB-1NB-1ZC BB-1b0C BB-1N-CNCB B-1 CCBCNCSbXBXNXSCsbBNIZCBCN03.2 3.2 分析资源系数的变化分析资源系数的变化资源系数的变化对最优单纯形标的b列有影响。例题 P65 CCBCNCSbXBXNXSCBB-1bIB-1NB-1ZC BB-1b0C BB-1N-CNCB B-1 CCBCNCSbXBXNXSCsbBNIZCBCN03.3 3.3 增加变量的变化增加变量的变化1计算该列技术系数。2技术该列检验数。例题：投产新产品，所需原料和设备分别为3、4、2单位，利润为3单位，问最优生产计划如何变化？3.4 技术系数aij的变化 例题：如果乙产品所需原材料和设备分别为8、4、1单位，利润为3单位，问最优生产计划的变化？1重新计算该产品在最优单纯形表中的技术系数。2重新计算该产品的检验数。