第2章789对偶理论.ppt

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

1、1,第2章 线性规划问题,2.5 对偶理论,2,本节研究、解决三个问题：1、如何写出对偶问题；2、原问题与对偶问题之间的关系；3、对偶单纯形法（解线性规划问题的第4种方法）,3,2.5.1 对偶问题的提出,例1生产计划问题 某厂生产两种产品，需要三种资源，已知各产品的利润、各资源的限量和各产品的资源消耗系数如下表：,4,例1模型,问题：如何安排生产计划，使得获利最多？步骤：1、确定决策变量：设生产A产品x1kg，B产品x2kg2、确定目标函数：max Z=70X1+120X23、确定约束条件：人力约束 9X1+4X2360 设备约束 4X1+5X2 200 原材料约束3X1+10X2 300

2、非负性约束X10 X20,5,例1另一角度分析：成本角度,利润大的另一方面是什么：成本越小！因此，我们可以试着从成本角度来分析生产决策者的心态！现在资源的数量已经定了，那么我们可以从价格来着手！,6,目 标 分 析,设劳动力每个工时收费Y1元，设备台时费用Y2元，原材料附加费Y3元。现在我们的目标变成下面这个式子：min w=360y1+200y2+300y3那么约束条件是什么呢？,7,约束条件分析,单个因素的收入最大：即投入于产品A的资源收入要大于A的销售收入，投入于产品B的资源收入要大于B的销售收入，即 9y1+4y2+3y3 70 4y1+5y2+10y3 120从整个问题来看，1、总的

3、投入最低，2、投入品的价值也要得到合理体现！综合起来得到问题模型！,8,问题模型,Min w=360y1+200y2+300y3s.t.9y1+4y2+3 y3 70 4y1+5y2+10y3 120 y1，y2，y3 0,这个线性规划问题称为例1的（称为原问题）对偶问题。,9,一般形式的线性规划问题，写出其对偶问题的规则是什么？课堂讲解第44页；要求：看到原问题，能立即写出其对偶形式；,10,原问题与对偶问题比较,原问题：对偶问题：maxZ=70X1+120X2 min=360y1+200y2+300y3 9X1+4X2360 9y1+4y2+3y3 70(1)4X1+5X2 200 4y1

4、+5y2+10y3 120(2)3X1+10X2 300 X10 X20 y1 0,y2 0,y3 0,11,2.5.2 对偶问题表示,根据上述例题可见，对于形如如下形式的线性规划问题：,我们可以马上得出它的对偶问题：,其中：AT、bT 分别是原LP中的约束条件矩阵 A的转置矩阵与约束条件中右端向量的转置(即为行向量)。,12,线性规划问题与其对偶问题的相关性,原问题的约束条件的个数 m 就是对偶问题的变量的个数；原问题的变量的个数 n 就是对偶问题的约束条件的个数；若原问题的目标函数是 Max 型，则对偶问题的目标函数必是 Min 型。它们二者的最优目标函数值相等。,13,2.5.3 一般L

5、P的对偶问题（书本P45定义 2.5.1）,原问题（P）：对偶问题（D）：min cTx max bTys.t.aiTx=bi i=1,p s.t.y 0 aiTx bi i=p+1,m y 0 xj 0 j=1,q AjTy c xj 0 j=q+1,n AjTy=c,14,对偶规则,原问题有m个约束条件对偶问题有m个变量原问题有n个变量 对偶问题有n个约束条件原问题的价值系数对偶问题的右端项原问题的右端项对偶问题的价值系数原问题的系数矩阵转置后为对偶问题系数矩阵,15,对偶规则,16,2.5.4 对偶问题的基本性质,对偶定理2.5.1：若一个LP问题有最优解，则它的对偶问题也有最优解，且目

6、标函数值相等。对称性：对偶问题与原问题互为对偶。无界性：原问题无界，对偶问题无可行解原问题与对偶问题：,17,2.5.5 对偶变量的经济解释,对偶变量yi在经济上表示原问题第i种资源的边际贡献，即当第i种资源增加一个单位时，相应的目标值z的增量。对偶问题的最优解yi*是原问题第i种资源的影子价格应用:1.出租资源或设备时，租金价格的设定(至少 高于该资源在企业内的影子价格)2.企业内资源 I的存量设定(当资源 I的影子价 格市场价格时，可买进该资源；否则卖出)3.调整资源的分配量以增加利润,18,2.5（1）对偶问题,要求：了解LP对偶问题的实际意义掌握对偶问题的建立规则与基本性质 了解对偶最优解的计算及其经济解释,19,第2章 线性规划问题,2.5（2）对偶单纯形法,20,对偶理论,证明：定理2.5.1（黑板讲解）对偶单纯形法（黑板讲解）,21,求解LP问题的四种方法,图解法单纯形法 两阶段法对偶单纯形法,22,对偶单纯形法,黑板讲解,23,2.6 灵敏度分析,黑板讲解,