对偶问题及对偶单纯形法完整课件.ppt

《对偶问题及对偶单纯形法完整课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

DualityTheory线性规划的对偶问题对偶问题的经济解释——影子价格对偶单纯形法第四章线性规划的对偶理论灵敏度分析对偶问题的基本性质 线性规划的对偶问题DualityTheory对偶问题的经济解释——影子价格对偶单纯形法灵敏度分析对偶问题的基本性质第四章线性规划的对偶理论 例如：平面中矩形的面积与周长的关系周长一定面积最大的矩形是正方形:面积一定周长最短的矩形是正方形一、对偶问题的提出对同一问题从不同角度考虑，有两种对立的描述。例1、应如何安排生产计划，使一天的总利润最大？某企业生产甲、乙两种产品，要用A、B、C三种不同的原料。每生产1吨甲产品，需耗用三种原料分别为1，1，0单位；生产1吨乙产品，需耗用三种原料分别为1，2，1单位。每天原料供应的能力分别为6，8，3单位。又知道每生产1吨甲产品企业利润为300元，每生产1吨乙产品企业利润为400元。 例1、应如何安排生产计划，使一天的总利润最大？maxx1≥0,x2≥0s.t.x1+x2≤6z=3x1+4x2x1+2x2≤8x2≤3设xj表示第j种产品每天的产量假设该企业决策者决定不生产甲、乙产品，而是将厂里的现有资源外售。决策者应怎样制定每种资源的收费标准才合理？ 例1、应怎样制定收费标准才合理？设yj表示第j种原料的收费单价分析问题：1、出让每种资源的收入不能低于自己生产时的可获利润；2、定价不能太高，要使对方能够接受。把生产一吨甲产品所用的原料出让，所得净收入应不低于生产一吨甲产品的利润：乙产品同理：把企业所有原料出让的总收入：只能在满足≥所有产品的利润的条件下,其总收入尽可能少,才能成交.s.t. 一、对偶问题的提出任何一个求极大的线性规划问题都有一个求极小的线性规划问题与之对应，反之亦然.把其中一个叫原问题，则另一个就叫做它的对偶问题，这一对互相联系的两个问题就称为一对对偶问题。s.t.LP1s.t.LP2原问题（P）对偶问题（D） 二、原问题与对偶问题的对应关系s.t.Ps.t.Dyj表示对第j种资源的估价矩阵形式：s.t.s.t.maxz=CXs.t.AX≤bX≥0minw=bTYs.t.ATY≥CTY≥0 (一)对称型对偶问题其中yi≥0（i=1,2,…,m）称为对偶变量。变量均具有非负约束，且约束条件：当目标函数求极大时均取“≤”号，当目标函数求极小时均取“≥”号。maxz=c1x1+c2x2+…+cnxns.t.a11x1+a12x2+…+a1nxn≤b1a21x1+a22x2+…+a2nxn≤b2(P)……am1x1+am2x2+…+amnxn≤bmxj≥0（j=1,2,…,n）minw=b1y1+b2y2+…+bmyms.t.a11y1+a21y2+…+am1ym≥c1a12y1+a22y2+…+am2ym≥c2(D)……a1ny1+a2ny2+…+amnym≥cnyi≥0（i=1,2,…,m）maxz=CXs.t.AX≤bX≥0minw=bTYs.t.ATY≥CTY≥0 (二)非对称型对偶问题分析：化为对称形式。maxx1≥0,x2≤0,x3无约束s.t.a11x1+a12x2+a13x3≤b1z=c1x1+c2x2+c3x3a31x1+a32x2+a33x3≥b3a21x1+a22x2+a23x3=b2令maxs.t. (二)非对称型对偶问题maxs.t.对偶变量mins.t.对偶问题： (二)非对称型对偶问题mins.t.令mins.t.mins.t. 3个≥≤=约束条件变量(二)非对称型对偶问题mins.t.原问题对偶问题目标函数max目标函数min目标函数的系数约束条件右端常数约束条件右端常数目标函数的系数3个≤≥=3个≥0≤0无符号限制约束条件变量3个≥0≤0无符号限制原问题（对偶问题）对偶问题（原问题） 3个≥≤=约束条件变量(一)对称型对偶问题原问题（对偶问题）对偶问题（原问题）目标函数max目标函数min目标函数的系数约束条件右端常数约束条件右端常数目标函数的系数3个≤≥=3个≥0≤0无符号限制约束条件变量3个≥0≤0无符号限制s.t.s.t.2个2个 二、原问题与对偶问题的对应关系 例2、写出下述线性规划问题的对偶问题解：设对偶变量为maxs.t.mins.t.则对偶问题为 例3、写出下述线性规划问题的对偶问题解：设对偶变量为mins.t.maxs.t.则对偶问题为 练习、写出下述线性规划问题的对偶问题maxs.t.mins.t. 对偶问题的基本性质DualityTheory线性规划的对偶问题对偶问题的经济解释——影子价格对偶单纯形法灵敏度分析第二章线性规划的对偶理论 对偶问题的基本性质对称性弱对偶性无界性最优性原问题与对偶问题单纯形表间的性质互补松弛性强对偶性 对偶问题的基本性质maxz=CXs.t.AX≤bX≥0minw=bTYs.t.ATY≥CTY≥0s.t.（P）s.t.（D） 对偶问题1、对称性定理：对偶问题的对偶是原问题。对偶问题maxz=CXs.t.AX≤bX≥0maxw=－bTYs.t.－ATY≤－CTY≥0minw=bTYs.t.ATY≥CTY≥0minz=－CXs.t.－AX≥－bX≥0 2、弱对偶性定理：设和分别是原问题（P）和其对偶问题（D）的可行解，则恒有 2、弱对偶性定理：设和分别是原问题（P）和其对偶问题（D）的可行解，则恒有推论：原问题任一可行解的目标函数值是其对偶问题目标函数值的下界；反之，对偶问题任一可行解的目标函数值是其原问题目标函数值的上界。 3、无界性定理：在互为对偶的两个问题中，若一个问题具有无界解，则另一个问题无可行解。原问题有可行解但目标函数值无界对偶问题无可行解对偶问题有可行解但目标函数值无界原问题无可行解推论：原问题任一可行解的目标函数值是其对偶问题目标函数值的下界；反之，对偶问题任一可行解的目标函数值是其原问题目标函数值的上界。 3、无界性定理：在互为对偶的两个问题中，若一个问题具有无界解，则另一个问题无可行解。原问题有无界解对偶问题无可行解推论：原问题任一可行解的目标函数值是其对偶问题目标函数值的下界；反之，对偶问题任一可行解的目标函数值是其原问题目标函数值的上界。可能是无可行解推论1：在互为对偶的两个问题中，若一个问题无可行解，则另一个问题或具有无界解或无可行解。 3、无界性定理：在互为对偶的两个问题中，若一个问题具有无界解，则另一个问题无可行解。推论1：在互为对偶的两个问题中，若一个问题无可行解，则另一个问题或具有无界解或无可行解。推论2：在互为对偶的两个问题中，若一个问题有可行解，另一个问题无可行解，则可行的问题无界。无界解无可行解无可行解无界解对偶问题原问题 例1、利用对偶理论证明问题无界（无最优解）解：设对偶变量为maxs.t.mins.t.则对偶问题为由知，第一个约束可知对偶问题无条件不成立，可行解。易知(0,0,0)T是原问题的一个可行解，故原问题可行。由无界性定理可知，原问题有无界解，即无最优解。对偶问题不可行原问题无界或不可行无界不可行 练习、证明下列线性规划问题无最优解mins.t.maxs.t.对偶问题原问题的一个可行解：……对偶问题不可行：找矛盾 4、最优性定理：设和分别是原问题（P）和其对偶问题（D）的可行解，且有则和分别是原问题（P）和其对偶问题（D）的最优解。设和分别是P和D的最优解：因此 5、互补松弛性定理：设和分别是原问题和其对偶问题的最优解，若对偶变量，则原问题相应的约束条件若约束条件，则相应的对偶变量 5、互补松弛性定理：设和分别是原问题和其对偶问题的最优解，若对偶变量，则原问题相应的约束条件若约束条件，则相应的对偶变量 5、互补松弛性定理：设和分别是原问题和其对偶问题的最优解，若对偶变量，则原问题相应的约束条件若约束条件，则相应的对偶变量若，则若，则若，则若，则 例2、利用互补松弛定理求最优解maxs.t.已知原问题的最优解是求对偶问题的最优解。解：设对偶变量为mins.t.则对偶问题为设对偶问题的最优解为因由互补松弛性知解方程组得故对偶问题的最优解为 例3、利用互补松弛定理求最优解已知原问题的最优解是maxs.t.求对偶问题的最优解。对偶变量为mins.t.则对偶问题为设对偶问题的最优解为将代入原问题约束条件得解：由互补松弛性知又故对偶问题的最优解为得 例4、利用互补松弛定理求最优解已知其对偶问题的最优解是mins.t.求原问题的最优解。对偶问题为设原问题的最优解为解：mins.t.将代入原问题约束条件得：(2)、(3)、(4)为严格不等式由互补松弛性知又因由互补松弛性知得故原问题最优解为 6、强对偶性（对偶定理）定理：若原问题有最优解，则其对偶问题也一定具有最优解，且目标函数的最优值相等。s.t.用单纯形法求原问题的最优解： s.t. 非基变量基变量XsXIA0C基变量基变量基可系数行解0XsbXBXNBNCBCN XBI0CBCNBNXBXN单纯形法计算的矩阵描述非基变量基变量XsI0基变量基变量基可系数行解0Xsb基变量非基变量XB基变量基变量基可系数行解CN－CBB-1NB-1NB-1XNXsB-1bCB进行初等行变换－CBB-1若CN－CBB-1N≤0－CBB-1≤0最优解X*=B-1bB-1存在 6、强对偶性（对偶定理）minw=bTYs.t.ATY≥CTY≥0若CN－CBB-1N≤0－CBB-1≤0最优解X*=B-1b令YT=CBB-1，则有CN－YTN≤0，Y≥0因CB－YTB=0，故C－YTA≤0，即ATY≥CT，说明Y是D的可行解maxz=CXs.t.AX≤bX≥0此时目标函数值w=bTY=YTb=CBB-1b原问题的最优值z＊=CB-1b=CBB-1b由最优性定理知，Y是D的最优解。定理：若原问题有最优解，则其对偶问题也一定具有最优解，且目标函数的最优值相等。 6、强对偶性（对偶定理）推论：若一对对偶问题都有可行解，则它们都有最优解，且目标函数的最优值必相等。定理：若原问题有最优解，则其对偶问题也一定具有最优解，且目标函数的最优值相等。互为对偶的两个问题，只会出现以下三种关系：①都有最优解，且最优值相等②一个有无界解，另一个无可行解；③两个都无可行解。 判断下列说法是否正确，为什么？1、如果线性规划问题存在可行解，则其对偶问题也一定存在可行解。2、如果线性规划问题的对偶问题无可行解，则原问题也一定无可行解。3、如果线性规划问题的原问题和对偶问题都具有可行解，则该线性规划一定具有有限最优解。 对偶问题的基本性质一个问题max另一问题min应用有最优解有最优解强对偶性无界解（有可行解）无可行解无界性（证无最优解）无可行解无界解（有可行解）已知最优解求最优解互补松弛性 7、原问题与对偶问题单纯形表间的性质？XBI0CBCNBNXBXN非基变量基变量XsI0基变量基变量基可系数行解0Xsb基变量非基变量XB基变量基变量基可系数行解CN－CBB-1NB-1NB-1XNXsB-1bCBYT=CBB-1－CBB-1 DualityTheory线性规划的对偶问题对偶问题的经济解释——影子价格对偶单纯形法灵敏度分析对偶问题的基本性质第二章线性规划的对偶理论 第一步：找到一个满足最优检验的初始基本解；第二步：检验当前解是否可行。若可行，已得到最优，否则转入下一步。第三步：选择b最小一行的变量作为换出变量第四步：换入变量min{cj-zj/aij}(负数和零不参与比较)第五步：迭代运算，到第二步。对偶单纯形法 对偶单纯形法Maxz=-6x1-3x2-2x3例： cj-6-3-2000cBxBbx1x2x3x4x5x60x4-20-1-1-11000x5-6-1/2-1/2-1/40100x6-10-2-1-1001zj000000cj-zj-6-3-2000对偶单纯形法找到一个满足最优检验的初始基本解检验当前解不可行，选择b最小一行的变量作为换出变量；换入变量min{cj-zj/aij} cj-6-3-2000cBxBbx1x2x3x4x5x6-2x320111-1000x5-1-1/4-1/40-1/4100x610100-101zj-2-2-2200cj-zj-4-10-200对偶单纯形法检验当前解不可行，选择b最小一行的变量作为换出变量；换入变量min{cj-zj/aij} cj-6-3-2000cBxBbx1x2x3x4x5x6-2x316001-240-3x241101-400x610-100-101zj-3-3-2140cj-zj-300-1-40对偶单纯形法 对偶问题的经济解释——影子价格DualityTheory线性规划的对偶问题对偶单纯形法灵敏度分析对偶问题的基本性质第二章线性规划的对偶理论 bi代表第i种资源的拥有量；yi*代表在资源最优利用条件下对第i种资源的单位估价。这种估价不是资源的市场价格，而是根据资源在生产中作出的贡献而作的估价。一、影子价格的概念设xj表示第j种产品每天的产量设yj表示第j种原料的收费单价由对偶定理知当P问题求得最优解X*时，D问题也得到最优解Y*，且有影子价格 若，则若，则当某个右端常数bibi+1时一、影子价格的概念由得说明的值相当于在资源得到最优利用的生产条件下，每增加一个单位时目标函数z的增量边际价格说明若某资源未被充分利用，则该种资源的影子价格为0；若某资源的影子价格不为0，则说明已有资源在已消耗完毕。 二、在经营管理中的应用y1*=2y2*=1y3*=0Y*T=CBB-1－CBB-1 二、在经营管理中的应用y1*=2y2*=1y3*=0若原料A增加1单位，该厂按最优计划安排生产可多获利200元；若原料B增加1单位，可多获利100元;原料C本已剩余，再增加不会带来收益。1、指示企业内部挖潜的方向影子价格能说明增加哪种资源对增加经济效益最有利 二、在经营管理中的应用y1*=2y2*=1y3*=02、在企业经营决策中的作用当某种资源的影子价格高于市场价格时：当某种资源的影子价格低于市场价格时：企业经营决策者可通过把本企业资源的影子价格与当时的市场价格进行比较，决定资源的买卖，以获取较大利润。买进卖出特别是影子价格为零时 二、在经营管理中的应用y1*=2y2*=1y3*=03、在新产品开发决策中的应用利用影子价格，通过分析新产品使用资源的经济效果，以决定新产品是否应该投产。假设该企业计划生产一类新产品，单件消耗三种原料的数量为（2,3,2），则新产品的单位利润必须大于2×2+1×3+0×2=7（百元）才能增加公司的收益，否则生产是不合算的。 二、在经营管理中的应用y1*=2y2*=1y3*=04、分析现有产品价格变动对资源紧缺情况的影响若甲产品提价，单位利润增至4，则影子价格改变，由Y*T=CBB-1说明如果甲产品提价的话，资源A将变得更紧俏. 二、在经营管理中的应用y1*=2y2*=1y3*=05、分析工艺改变后对资源节约的收益若企业革新技术，改进工艺过程后使资源A能节约2%，则带来的经济收益每天将是2×6×2%=0.24（百元） 二、在经营管理中的应用y1*=2y2*=1y3*=0注意:1、以上分析都是在最优基不变的条件下进行的2、应对影子价格有更为广义的理解若增加产量约束x1+x2≤40：产量不超过市场需求量若y4*较大，则说明扩大销路能比增加资源带来更大的经济效益Y*T=CBB-1 DualityTheory线性规划的对偶问题对偶问题的经济解释——影子价格对偶单纯形法灵敏度分析对偶问题的基本性质第二章线性规划的对偶理论