运筹学讲稿.ppt

《运筹学讲稿.ppt》由会员分享，可在线阅读，更多相关《运筹学讲稿.ppt（37页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、关于运筹学运筹学1/36第一页，讲稿共三十七页哦运筹学2/363.4 3.4 影子价格和灵敏度分析影子价格和灵敏度分析原问题是利润最大化的生产计划问题原问题是利润最大化的生产计划问题单位产品的利润（元/件）产品产量（件）总利润（元）资源限量（吨）单位产品消耗的资源（吨/件）剩余的资源（吨）消耗的资源（吨）第二页，讲稿共三十七页哦运筹学3/36对偶问题对偶问题资源限量（吨）资源价格（元/吨）总利润（元）对偶问题是资源定价问题，对偶问题的最优解对偶问题是资源定价问题，对偶问题的最优解w1、w2、.、wm称为称为m种资源的种资源的影子价格（影子价格（Shadow Price）原始和对偶问题都取得最优

2、解时，原始和对偶问题都取得最优解时，最大利润最大利润 max z=min y第三页，讲稿共三十七页哦运筹学4/36 定义：在一对定义：在一对 P 和和 D 中，若中，若 P 的某个约束条件的的某个约束条件的右端项常数右端项常数bi 增加一个单位时，所引起的目标函数最增加一个单位时，所引起的目标函数最优值优值Z*的改变量的改变量y*i 称为第称为第 i 个约束条件的影子价格，个约束条件的影子价格，又称为边际价格。又称为边际价格。一、影子价格的概念一、影子价格的概念第四页，讲稿共三十七页哦运筹学5/36 设：设：B是问题是问题 P的最优基，由前表可知，的最优基，由前表可知，Z*=CB B-1b=Y

3、*b =y*1b1+y*2b2+.+y*Ibi+.+y*mbm 当当bi 变为变为bi+1 时时(其它条件不变），其它条件不变），CCBCN0CBXBbXBXNXSCBXBB-1bIB-1NB-1ZCB B-1b0CB B-1N CNCB B-1第五页，讲稿共三十七页哦运筹学6/36 目标函数最优值变为：目标函数最优值变为：Z*=y*1b1+y*2b2+.+y*I（bi+1）+.+y*mbm 所以所以 Z*=Z*Z*=y*i 也可以写成：也可以写成：即即y*i 表示表示Z*对对 bi的变化率。的变化率。其经济意义是：在其它条件不变的情况下，单位资源变其经济意义是：在其它条件不变的情况下，单位资

4、源变化所引起的目标函数的最优值的变化。即对偶变量化所引起的目标函数的最优值的变化。即对偶变量yi 就是就是第第 i 个约束条件的影子价格。个约束条件的影子价格。也可以理解为目标函数最优值对资源的一阶偏导数（但问也可以理解为目标函数最优值对资源的一阶偏导数（但问题中所有其它数据都保持不变）。题中所有其它数据都保持不变）。第六页，讲稿共三十七页哦运筹学7/36考虑具有三种资源的优化问题：考虑具有三种资源的优化问题：302010由图示可知最优点为由图示可知最优点为由图示可知最优点为由图示可知最优点为B B（3535，1010），最优值为），最优值为），最优值为），最优值为215215。例例14 影子

5、价格的图解法影子价格的图解法x18060402020406080100Bx2第七页，讲稿共三十七页哦运筹学8/362010 由图示可知最优点为由图示可知最优点为由图示可知最优点为由图示可知最优点为B(35,10),B(35,10),最优值为最优值为最优值为最优值为215215。故资源故资源故资源故资源A A的影子价格为的影子价格为的影子价格为的影子价格为0 0。假设资源假设资源A增加增加1个单位，其它条件不变：个单位，其它条件不变：8060402020406080 x1100Bx2第八页，讲稿共三十七页哦运筹学9/36302010由图示可知最优点为由图示可知最优点为由图示可知最优点为由图示可知

6、最优点为B B（3636，9 9），最优值为），最优值为），最优值为），最优值为216216。故资源故资源故资源故资源B B的影子价格为的影子价格为的影子价格为的影子价格为1 1。8060402020406080 x1100Bx2假设资源假设资源B增加增加1个单位，其它条件不变：个单位，其它条件不变：第九页，讲稿共三十七页哦运筹学10/362010由图示可知最优点为由图示可知最优点为由图示可知最优点为由图示可知最优点为B(34B(34，1212），最优值为），最优值为），最优值为），最优值为218218，故故故故C C的影子价格为的影子价格为的影子价格为的影子价格为3 3。8060402020

7、406080 x1100Bx2假设资源假设资源C增加增加1个单位，其它条件不变：个单位，其它条件不变：第十页，讲稿共三十七页哦运筹学11/36 若第若第i 种资源的单位市场价格为种资源的单位市场价格为mi，当，当yi mi 时，时，企业愿意购进这种资源，单位纯利为企业愿意购进这种资源，单位纯利为yimi，则有利，则有利可图；如果可图；如果yi 0，则应投产则应投产,若若n+1=Cn+1CBB-1Pn+10，则不应投产则不应投产。即即新新产产品品的的机机会会成成本本小小于于目目前前的的市市场场价价格格时时，应应投投产产否否则则不不应投产。应投产。第三十一页，讲稿共三十七页哦运筹学32/36 在企

8、业生产过程中，经常有新情况发生，造成原本不在企业生产过程中，经常有新情况发生，造成原本不紧缺的某种资源变成为紧缺资源，对生产计划造成影响，紧缺的某种资源变成为紧缺资源，对生产计划造成影响，如水、电和资源的供应不足等，对生产过程提出了新约如水、电和资源的供应不足等，对生产过程提出了新约束等。束等。对增加新约束条件的分析方法步骤是：对增加新约束条件的分析方法步骤是：五、对增加新约束条件的分析五、对增加新约束条件的分析 第第一一步步：将将目目前前的的最最优优解解代代入入新新增增加加的的约约束束，若若能能满满足足约约束束条条件件，则则说说明明新新增增约约束束对对目目前前的的最最优优解解（即即最最优优生

9、生产产方方案案）不不构构成成影影响响（称称此此约约束束为为不不起起作作用用约约束束），可可暂暂时时不不考考虑虑新新增约束条件。否则转下一步；增约束条件。否则转下一步；第三十二页，讲稿共三十七页哦运筹学33/36第第二二步步：把把新新增增约约束束添添加加到到原原问问题题最最终终表表中中，并并作作初初等等行行变变换换，构构成成对对偶偶可可行行的的单单纯纯形形表表，并并用用对对偶偶单单纯纯形形法法迭迭代代，求求出出新新的的最最优解。优解。例例18 对于生产计划问题（例对于生产计划问题（例10），设增加电力约束，生产），设增加电力约束，生产1单单位甲产品需耗电位甲产品需耗电3个单位，生产个单位，生产1

10、单位乙产品需耗电单位乙产品需耗电4个单位，且个单位，且每天供电量不超过每天供电量不超过30单位。试分析此时最优解的变化情况单位。试分析此时最优解的变化情况。第三十三页，讲稿共三十七页哦运筹学34/36 解：将最优解解：将最优解x1=6,x2=4代入约束条件代入约束条件 ，不不满足，说明约束条件起作用。满足，说明约束条件起作用。将约束条件加入松驰变量，化为等式将约束条件加入松驰变量，化为等式 加入最优单纯形表中。加入最优单纯形表中。C 4 3 0 0 0 CBXBb x1 x2 x3 x4 x5340 x2x1x54630 0 1 3/5 -2/5 0 1 0 2/5 3/5 0 3 4 0 0

11、 1 Z36 0 0 -1/5 -6/5 0在这个表中，由于在这个表中，由于x1,x2是基变量，其系数必须为单位向量，因是基变量，其系数必须为单位向量，因此将此将p1,p2化为单位向量得化为单位向量得:第三十四页，讲稿共三十七页哦运筹学35/36C 4 3 0 0 0 CBXBb x1 x2 x3 x4 x5340 x2x1x546-4 0 1 3/5 -2/5 0 1 0 2/5 3/5 0 0 0 -6/5 -1/5 1 Z36 0 0 -1/5 -6/5 0再用对偶单纯形法求得新的最优表如下：再用对偶单纯形法求得新的最优表如下：C 4 3 0 0 0 CBXBb x1 x2 x3 x4 x5340 x2x1x3222/310/3 0 1 0 -1/2 1/2 1 0 0 2/3 -1/3 0 0 1 1/6 -5/6 Z106/3 0 0 0 -6/7 -1/6第三十五页，讲稿共三十七页哦运筹学36/36作业作业1.复习：影子价格和灵敏度分析；复习：影子价格和灵敏度分析；2.预习：线性规划进一步讨论预习：线性规划进一步讨论3.书面作业：书面作业：4.P76-79：习题：习题3.11，3.13，3.15。第三十六页，讲稿共三十七页哦运筹学37/36感感谢谢大大家家观观看看第三十七页，讲稿共三十七页哦