线性规划求解方法法.ppt

线性规划,授课教师：王淑华,运筹学课件,可行区域与基本可行解,图解法可行域的几何结构基本可行解与基本定理,返回,运筹学课件,线性规划,图解法,运筹学课件,线性规划,例,运筹学课件,线性规划,运筹学课件,线性规划,注释,线性规划解的的情况：可行域是空集（问题无解）无界最优解存在且唯一，则一定在可行域顶点上达到存在无穷多最优解，一定存在可行域的顶点是最优解注：如果线性规划有最优解且最优解不唯一，则一定有无穷多个最优解,返回,运筹学课件,线性规划,可行域的几何结构,基本假设凸集可行域的凸性,返回,运筹学课件,线性规划,基本假设,返回,运筹学课件,线性规划,凸集,返回,运筹学课件,线性规划,问题,返回,运筹学课件,线性规划,基本可行解与基本定理,定义基本定理问题,返回,运筹学课件,线性规划,返回,运筹学课件,线性规划,基本可行解定义,基本可行解定义,运筹学课件,线性规划,返回,运筹学课件,线性规划,基本定理,返回,运筹学课件,线性规划,说明,返回,运筹学课件,线性规划,图解法的灵敏度分析,灵敏度分析：建立数学模型和求得最优解后，研究线性规划的一个或多个参数（系数）ci,aij,bj变化时，对最优解产生的影响。例:Maxz=50 x1+100 x2s.t.x1+x2300(A)2x1+x2400(B)x2250(C)x10(D)x20(E)得到最优解：x1=50，x2=250最优目标值z=27500,线性规划的标准化：引入松驰变量（含义是资源的剩余量）例中引入s1，s2，s3模型化为目标函数：Maxz=50 x1+100 x2+0s1+0s2+0s3约束条件：s.t.x1+x2+s1=3002x1+x2+s2=400 x2+s3=250 x1,x2,s1,s2,s30对于最优解x1=50 x2=250，s1=0s2=50s3=0说明：生产50单位产品和250单位产品将消耗完所有可能的设备台时数及原料B，但对原料A则还剩余50千克。,灵敏度分析,目标函数中的系数ci的灵敏度分析：ci的变化只影响目标函数等值线的斜率，目标函数z=50 x1+100 x2在250=x2(x2=z斜率为0)300=x1+x2(x2=-x1+z斜率为-1)之间时，原最优解x1=50，x2=100仍是最优解。一般情况：z=c1x1+c2x2写成斜截式x2=-(c1/c2)x1+z/c2目标函数等值线的斜率为-(c1/c2)，当-1-(c1/c2)0（*）时，原最优解仍是最优解。,假设产品的利润100元不变，即c2=100，代到式（*）并整理得0c1100假设产品的利润50元不变，即c1=50，代到式（*）并整理得50c2+假若产品、的利润均改变，则可直接用式（*）来判断。假设产品、的利润分别为60元、55元，则-2-(60/55)-1那么，最优解为300=x1+x2和400=2x1+x2的交点x1=100，x2=200。,3图解法的灵敏度分析,假设产品的利润100元不变，即c2=100，代到式（*）并整理得0c1100假设产品的利润50元不变，即c1=50，代到式（*）并整理得50c2+假若产品、的利润均改变，则可直接用式（*）来判断。假设产品、的利润分别为60元、55元，则-2-(60/55)-1那么，最优解为300=x1+x2和400=2x1+x2的交点x1=100，x2=200。,3图解法的灵敏度分析,2约束条件中右边系数bj的灵敏度分析当约束条件中右边系数bj变化时，线性规划的可行域发生变化，可能引起最优解的变化。考虑上例的情况：假设设备台时增加10个台时，即b1变化为310，这时可行域扩大，最优解为x2=250和x1+x2=310的交点x1=60，x2=250。变化后的总利润-变化前的总利润=增加的利润(5060+100250)-(5050+100250)=500，500/10=50元说明在一定范围内每增加（减少）1个台时的设备能力就可增加（减少）50元利润，称为该约束条件的对偶价格。,假设原料A增加10千克时，即b2变化为410，这时可行域扩大，但最优解仍为x2=250和x1+x2=300的交点x1=50，x2=250。此变化对总利润无影响，该约束条件的对偶价格为0。解释：原最优解没有把原料A用尽，有50千克的剩余，因此增加10千克值增加了库存，而不会增加利润。在一定范围内，当约束条件右边常数增加1个单位时（1）若约束条件的对偶价格大于0，则其最优目标函数值得到改善（变好）；（2）若约束条件的对偶价格小于0，则其最优目标函数值受到影响（变坏）；（3）若约束条件的对偶价格等于0，则最优目标函数值不变。,注释,1.对偶价格表示其对应的资源每增加一个单位，将改进多少个单位的最优值。2.当约束条件中的常数项增加一个单位时，最优目标函数值增加的数量称之为影子价格。在求目标函数最大时，当约束条件中的常数项增加一个单位时，目标函数值增加的数量就为改进的数量，所以影子价格等于对偶价格；在求目标函数值最小时，改进的数量就是减少的数量，所以影子价格即为负的对偶价格。,单纯形法,单纯形法的基本思路：从可行域中某一个顶点(即基本可行解)开始，判断此顶点是否是最优解，如不是,则再找另一个使得其目标函数值更优的顶点，称之为迭代，再判断此点是否是最优解。直到找到一个顶点(基本可行解)为其最优解，就是使得其目标函数值最优的解，或者能判断出线性规划问题无最优解为止。,算例,运筹学课件,线性规划,初始单纯形表,运筹学课件,线性规划,迭代1,运筹学课件,线性规划,迭代2,运筹学课件,线性规划,返回,运筹学课件,线性规划,计算软件,LinGomatlab,返回,Matlab求解线性规划基本模型函数调用格式：,