第2章789对偶理论.ppt

《第2章789对偶理论.ppt》由会员分享，可在线阅读，更多相关《第2章789对偶理论.ppt（23页珍藏版）》请在优知文库上搜索。

1、1第第2章章 线性规划问题线性规划问题2.5 对偶理论对偶理论2n本节研究、解决三个问题：n1、如何写出对偶问题；n2、原问题与对偶问题之间的关系；n3、对偶单纯形法（解线性规划问题的第4种方法）32.5.1 对偶问题的提出对偶问题的提出n例例1生产计划问题生产计划问题 某厂生产两种产品，需要三种资源，已知某厂生产两种产品，需要三种资源，已知各产品的利润、各资源的限量和各产品的资源各产品的利润、各资源的限量和各产品的资源消耗系数如下表：消耗系数如下表：产品产品A产品产品B资源限量资源限量劳动力劳动力设设 备备原材料原材料9434510360200300利润利润（元（元/kg）701204例例1

2、模型模型n问题：如何安排生产计划，使得获利最多？问题：如何安排生产计划，使得获利最多？n步骤：步骤：1、确定决策变量：设生产、确定决策变量：设生产A产品产品x1kg，B产品产品x2kg2、确定目标函数：、确定目标函数：max Z=70X1+120X23、确定约束条件：人力约束、确定约束条件：人力约束 9X1+4X2360 设备约束设备约束 4X1+5X2 200 原材料约束原材料约束3X1+10X2 300 非负性约束非负性约束X10 X205例例1另一角度分析：成本另一角度分析：成本角度角度n 利润大的另一方面是什么：成本越小！因此，我们可利润大的另一方面是什么：成本越小！因此，我们可以试着

3、从成本角度来分析生产决策者的心态！现在资源的以试着从成本角度来分析生产决策者的心态！现在资源的数量已经定了，那么我们可以从价格来着手！数量已经定了，那么我们可以从价格来着手！产品产品A产品产品B资源限制资源限制劳动力劳动力设备设备原材料原材料 9 4 3 4 5 10 360 200 300单位利润单位利润 701206目目 标标 分分 析析n设劳动力每个工时收费设劳动力每个工时收费Y1元，设备台时费元，设备台时费用用Y2元，原材料附加费元，原材料附加费Y3元。元。n现在我们的目标变成下面这个式子：现在我们的目标变成下面这个式子：min w=360y1+200y2+300y3n那么约束条件是什

4、么呢？那么约束条件是什么呢？7约束条件分析约束条件分析n单个因素的收入最大：即投入于产品单个因素的收入最大：即投入于产品A的资源收入的资源收入要大于要大于A的销售收入，投入于产品的销售收入，投入于产品B的资源收入要的资源收入要大于大于B的销售收入，即的销售收入，即 9y1+4y2+3y3 70 4y1+5y2+10y3 120从整个问题来看，从整个问题来看，1、总的投入最低，、总的投入最低，2、投入品的、投入品的价值也要得到合理体现！综合起来得到问题模型！价值也要得到合理体现！综合起来得到问题模型！8问题模型问题模型Min w=360y1+200y2+300y3s.t.9y1+4y2+3 y3

5、 70 4y1+5y2+10y3 120 y1，y2，y3 0这个线性规划问题称为例这个线性规划问题称为例1 1的（称为原问的（称为原问题）题）对偶问题对偶问题。9n一般形式的线性规划问题，写出其对偶问题的规则是什么？n课堂讲解第44页；n要求：看到原问题，能立即写出其对偶要求：看到原问题，能立即写出其对偶形式；形式；10原问题与对偶问题比较原问题与对偶问题比较原问题：原问题：对偶问题：对偶问题：maxZ=70X1+120X2 min=360y1+200y2+300y3 9X1+4X2360 9y1+4y2+3y3 70(1)4X1+5X2 200 4y1+5y2+10y3 120 (2)3X

6、1+10X2 300 X10 X20 y1 0,y2 0,y3 0112.5.2 对偶问题表示对偶问题表示根据上述例题可见，对于形如如下形式的线根据上述例题可见，对于形如如下形式的线性规划问题：性规划问题：0.xbAxtsxcZMaxT我们可以马上得出我们可以马上得出它的对偶问题：它的对偶问题：0.ycyAtsybwMinTT其中：其中：AT、bT 分别是原分别是原LP中的约束条件矩阵中的约束条件矩阵 A的转的转置矩阵与约束条件中右端向量的转置置矩阵与约束条件中右端向量的转置(即为行向量即为行向量)。12线性规划问题与其对偶问题的相关性线性规划问题与其对偶问题的相关性n原问题的约束条件的个数原

7、问题的约束条件的个数 m 就是对偶问就是对偶问题的变量的个数；题的变量的个数；n原问题的变量的个数原问题的变量的个数 n 就是对偶问题的就是对偶问题的约束条件的个数；约束条件的个数；n若原问题的目标函数是若原问题的目标函数是 Max 型，则对偶型，则对偶问题的目标函数必是问题的目标函数必是 Min 型。型。它们二者它们二者的最优目标函数值相等。的最优目标函数值相等。132.5.3 一般一般LP的对偶问题的对偶问题（书本（书本P45定义定义 2.5.1）原问题（原问题（P）：）：对偶问题（对偶问题（D）：）：min cTx max bTys.t.aiTx=bi i=1,p s.t.y 0 aiT

8、x bi i=p+1,m y 0 xj 0 j=1,q AjTy c xj 0 j=q+1,n AjTy =c14对偶规则对偶规则n原问题有原问题有m个约束条件个约束条件对偶问题有对偶问题有m个变量个变量n原问题有原问题有n个变量个变量 对偶问题有对偶问题有n个约束条件个约束条件n原问题的价值系数原问题的价值系数对偶问题的右端项对偶问题的右端项n原问题的右端项原问题的右端项对偶问题的价值系数对偶问题的价值系数n原问题的系数矩阵转置后为对偶问题系数矩阵原问题的系数矩阵转置后为对偶问题系数矩阵15对偶规则对偶规则对偶问题对偶问题原问题原问题目标函数目标函数 max min 目标函数目标函数约束条件

9、约束条件 =变量变量 无约束无约束 变量变量 无约束无约束 约束条件约束条件=162.5.4 对偶问题的基本性质对偶问题的基本性质n对偶定理对偶定理2.5.1：若一个：若一个LP问题有最优解，问题有最优解，则它的对偶问题也有最优解，且目标函数值则它的对偶问题也有最优解，且目标函数值相等。相等。n对称性：对偶问题与原问题互为对偶。对称性：对偶问题与原问题互为对偶。n无界性：原问题无界，对偶问题无可行解无界性：原问题无界，对偶问题无可行解n原问题与对偶问题：原问题与对偶问题：原始原始 对偶对偶有最优解有最优解问题无界问题无界无可行解无可行解有最优解有最优解1XX问题无界问题无界XX3无可行解无可行

10、解X32172.5.5 对偶变量的经济解释对偶变量的经济解释n对偶变量对偶变量yi在经济上表示原问题第在经济上表示原问题第i种资源的边际贡种资源的边际贡献，即当第献，即当第i种资源增加一个单位时，相应的目标值种资源增加一个单位时，相应的目标值z的增量。的增量。n对偶问题的最对偶问题的最优解优解yi*是原问题第是原问题第i种资源的种资源的影子价影子价格格n应用应用:1.出租资源或设备时，租金价格的设定出租资源或设备时，租金价格的设定(至少至少 高于该资源在企业内的影子价格高于该资源在企业内的影子价格)2.企业内资源企业内资源 I的存量设定的存量设定(当资源当资源 I的影子价的影子价 格格 市场价

11、格时，可买进该资源；否则卖出市场价格时，可买进该资源；否则卖出)3.调整资源的分配量以增加利润调整资源的分配量以增加利润182.5（1）对偶问题对偶问题要求：要求：n了解了解LP对偶问题的实际意义对偶问题的实际意义n掌握对偶问题的建立规则与基本性质掌握对偶问题的建立规则与基本性质n 了解对偶最优解的计算及其经济解释了解对偶最优解的计算及其经济解释 19第第2章章 线性规划问题线性规划问题2.5（2）对偶单纯形法对偶单纯形法20对偶理论对偶理论n证明：定理证明：定理2.5.1（黑板讲解）（黑板讲解）n对偶单纯形法（黑板讲解）对偶单纯形法（黑板讲解）21求解求解LP问题的四种方法问题的四种方法1.图解法图解法2.单纯形法单纯形法 3.两阶段法两阶段法4.对偶单纯形法对偶单纯形法22对偶单纯形法黑板讲解232.6 灵敏度分析黑板讲解