线性规划求解方法法.ppt

《线性规划求解方法法.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、线性规划授课教师：王淑华运筹学课件可行区域与基本可行解图解法可行域的几何结构基本可行解与基本定理♂返回运筹学课件线性规划图解法运筹学课件线性规划例运筹学课件线性规划运筹学课件线性规划注释线性规划解的的情况：可行域是空集（问题无解）无界最优解存在且唯一，则一定在可行域顶点上达到存在无穷多最优解，一定存在可行域的顶点是最优解注：如果线性规划有最优解且最优解不唯一，则一定有无穷多个最优解♂返回运筹学课件线性规划可行域的几何结构基本假设凸集可行域的凸性♂返回运筹学课件线性规划基本假

2、设♂返回运筹学课件线性规划凸集♂返回运筹学课件线性规划问题♂返回运筹学课件线性规划基本可行解与基本定理定义基本定理问题♂返回运筹学课件线性规划♂返回运筹学课件线性规划基本可行解定义基本可行解定义运筹学课件线性规划♂返回运筹学课件线性规划基本定理♂返回运筹学课件线性规划说明♂返回运筹学课件线性规划§图解法的灵敏度分析灵敏度分析：建立数学模型和求得最优解后，研究线性规划的一个或多个参数（系数）ci,aij,bj变化时，对最优解产生的影响。例:Maxz=50x1+100x2s.t.x1+x2

3、≤300(A)2x1+x2≤400(B)x2≤250(C)x1≥0(D)x2≥0(E)得到最优解：x1=50，x2=250最优目标值z=27500x1x2z=20000=50x1+100x2z=27500=50x1+100x2z=0=50x1+100x2z=10000=50x1+100x2CBADE线性规划的标准化：——引入松驰变量（含义是资源的剩余量）例中引入s1，s2，s3模型化为目标函数：Maxz=50x1+100x2+0s1+0s2+0s3约束条件：s.t.x1+x2+s1=3002x1+x2+s2=400x

4、2+s3=250x1,x2,s1,s2,s3≥0对于最优解x1=50x2=250，s1=0s2=50s3=0说明：生产50单位Ⅰ产品和250单位Ⅱ产品将消耗完所有可能的设备台时数及原料B，但对原料A则还剩余50千克。灵敏度分析目标函数中的系数ci的灵敏度分析：ci的变化只影响目标函数等值线的斜率，目标函数z=50x1+100x2在250=x2(x2=z斜率为0)300=x1+x2(x2=-x1+z斜率为-1)之间时，原最优解x1=50，x2=100仍是最优解。一般情况：z=c1x1+c2x2写成斜截式x2=-(c1/

5、c2)x1+z/c2目标函数等值线的斜率为-(c1/c2)，当-1-(c1/c2)0（*）时，原最优解仍是最优解。假设产品Ⅱ的利润100元不变，即c2=100，代到式（*）并整理得0c1100假设产品Ⅰ的利润50元不变，即c1=50，代到式（*）并整理得50c2+假若产品Ⅰ、Ⅱ的利润均改变，则可直接用式（*）来判断。假设产品Ⅰ、Ⅱ的利润分别为60元、55元，则-2-(60/55)-1那么，最优解为300=x1+x2和400=2x1+x2的交点x1=100，x2=200。§3图解法的灵敏度分析假设产品

6、Ⅱ的利润100元不变，即c2=100，代到式（*）并整理得0c1100假设产品Ⅰ的利润50元不变，即c1=50，代到式（*）并整理得50c2+假若产品Ⅰ、Ⅱ的利润均改变，则可直接用式（*）来判断。假设产品Ⅰ、Ⅱ的利润分别为60元、55元，则-2-(60/55)-1那么，最优解为300=x1+x2和400=2x1+x2的交点x1=100，x2=200。§3图解法的灵敏度分析2约束条件中右边系数bj的灵敏度分析当约束条件中右边系数bj变化时，线性规划的可行域发生变化，可能引起最优解的变化。考虑上例的情况：假

7、设设备台时增加10个台时，即b1变化为310，这时可行域扩大，最优解为x2=250和x1+x2=310的交点x1=60，x2=250。变化后的总利润-变化前的总利润=增加的利润(50×60+100×250)-(50×50+100×250)=500，500/10=50元说明在一定范围内每增加（减少）1个台时的设备能力就可增加（减少）50元利润，称为该约束条件的对偶价格。假设原料A增加10千克时，即b2变化为410，这时可行域扩大，但最优解仍为x2=250和x1+x2=300的交点x1=50，x2=250。此变化对总利润

8、无影响，该约束条件的对偶价格为0。解释：原最优解没有把原料A用尽，有50千克的剩余，因此增加10千克值增加了库存，而不会增加利润。在一定范围内，当约束条件右边常数增加1个单位时（1）若约束条件的对偶价格大于0，则其最优目标函数值得到改善（变好）；（2）若约束条件的对偶价格小于0，则其最优目标函数值受到影响（变坏）；（3）若约束条件的对偶价格等于