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