目标规划单纯形法课件

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,ppt课件完整,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,二级,三级,四级,五级,ppt课件完整,*,2.2.3 目标规划的图解法,例某企业生产两种产品，在单件利润等有关数据已知条件下，要求制定一个获利最大的生产计划：,目标，第一级：允许加班，加班时间每周不超过10小时；第二级：产品产量满足市场需求,产 品,限,量,销量（kg/件）,24,30,时间（h/件）,1,1,40,利润（元/件）,8,10,1,ppt课件完整,2.2.3 目标规划的图解法例某企业生产两种产品，在单件利润,2.2.3 目标规划的图解法,例，某电视机厂装配黑白和彩色电视，每装配一台占用装配线1小时，装配线每周计划开动40小时。预计市场每周彩色电视机的销售量为24台，每台获利80元，黑白电视机销售量30台，每台可获利40元，该厂目标为：,第一级：充分利用装配线每周开动40小时,第二级：允许装配加班，但每周尽量不超过10小时,第三级：允许装配电视机的数量尽量满足市需要，因彩色利润高，故其权系数为2,2,ppt课件完整,2.2.3 目标规划的图解法例，某电视机厂装配黑白和彩色电视,2.2.4 目标规划的基本概念,线性规划目标,可行解,可接受解与不可接受解,达成函数,最优解,多重最优解,无界解,3,ppt课件完整,2.2.4 目标规划的基本概念线性规划目标3ppt课件完整,2.2.5 目标规划的单纯形法,c,j,c,1,c,2,c,n+2m,C,B,X,B,b,x,1,x,2,x,n+2m,c,j1,x,j1,b,o1,e,11,e,12,e,1n+2m,c,j2,x,j2,b,o2,e,21,e,22,e,2n+2m,c,jm,x,jm,b,om,e,m1,e,m2,e,mn+2m,j,P,1,11,12,1n+2m,P,2,21,22,2n+2m,P,K,m1,m2,mn+2m,一般形式：,4,ppt课件完整,2.2.5 目标规划的单纯形法cj c1c2cn+2mCBX,2.2.5 目标规划的单纯形法,单纯形法的计算步骤,1、建立初始单纯形表,一般假定初始解在原点，即以约束条件中的所有负偏差变量或松弛变量为初始基变量，按目标优先等级从左至右分别计算出各列的检验数，填入表下半部的K行中，置 k=1。,5,ppt课件完整,2.2.5 目标规划的单纯形法单纯形法的计算步骤5ppt课件,2.2.5 目标规划的单纯形法,2、检验是否为满意解,若Pk这一行某些负检验数的同列上面（较高优先等级）没有正检验数，说明未得到满意解，应继续改进，转到第3步；若Pk这一行全部负检验数的同列上面（较高优先等级）都有正检验数，说明目标虽没达到，但已不能改进，故得满意解，转到第6步。,6,ppt课件完整,2.2.5 目标规划的单纯形法2、检验是否为满意解6ppt课,2.2.5 目标规划的单纯形法,3、确定进基变量,在Pk行，从那些上面没有正检验数的负检验数中，选绝对值最大者，对应的变量xs就是进基变量。若Pk行中有几个相同的绝对值最大者，则依次比较它们各列下部的检验数，取其绝对值最大的负检验数的所在列的xs为进基变量。假如仍无法确定，则选最左边的变量（变量下标小者）为进基变量，转第4步。否则，转第6步。,7,ppt课件完整,2.2.5 目标规划的单纯形法3、确定进基变量7ppt课件完,2.2.5 目标规划的单纯形法,4、确定出基变量,其方法同线性规划，即依据最小比值法则,故确定xr为出基变量，ers为主元素。若有几个相同的行可供选择时，选最上面那一行所对应得变量为xr。,8,ppt课件完整,2.2.5 目标规划的单纯形法4、确定出基变量8ppt课件完,2.2.5 目标规划的单纯形法,5、旋转变换（变量迭代）,以ers为主元素进行变换，得到新的单纯形表，获得一组新解，返回到第2步。,6、对求得的解进行分析,当k=K时，计算结束，停止运算；表中的解即为最终解。若不满意，需修改模型，即调整目标优先等级和权系数，或者改变目标值，重新进行第1步。否则置k=k+1，返回第2步。,9,ppt课件完整,2.2.5 目标规划的单纯形法5、旋转变换（变量迭代）9pp,例,用单纯形法求解下列目标规划问题,10,ppt课件完整,例 用单纯形法求解下列目标规划问题10ppt课件完整,c,j,0,0,P,1,0,0,P,3,0,2.5P,2,0,P,2,C,B,X,B,b,x,1,x,2,P,1,2500,30,12,1,1,0,0,0,0,0,0,0,140,2,1,0,0,1,1,0,0,0,0,0,60,1,0,0,0,0,0,1,1,0,0,0,100,0,1,0,0,0,0,0,0,1,1,j,P,1,30,12,0,1,0,0,0,0,0,0,P,2,0,0,0,0,0,0,0,2.5,0,1,P,3,0,0,0,0,0,1,0,0,0,0,=,min2500/30,140/2,60/1=60,故 为换出变量。,2.2.5 目标规划的单纯形法,11,ppt课件完整,cj00P100P302.5P20P2CBXBbx1x2P1,c,j,0,0,P,1,0,0,P,3,0,2.5P,2,0,P,2,C,B,X,B,b,x,1,x,2,P,1,700,0,12,1,1,0,0,30,30,0,0,0,20,0,1,0,0,1,1,2,2,0,0,0,x,1,60,1,0,0,0,0,0,1,1,0,0,0,100,0,1,0,0,0,0,0,0,1,1,j,P,1,0,12,0,1,0,0,30,30,0,0,P,2,0,0,0,0,0,0,0,2.5,0,1,P,3,0,0,0,0,0,1,0,0,0,0,=,min700/30,20/2,=10,故 为换出变量。,2.2.5 目标规划的单纯形法,12,ppt课件完整,cj 00P100P302.5P20P2CBXBbx1x2P,c,j,0,0,P,1,0,0,P,3,0,2.5P,2,0,P,2,C,B,X,B,b,x,1,x,2,P,1,400,0,-3,1,-1,-15,15,0,0,0,0,2.5P,2,10,0,1/2,0,0,1/2,-1/2,-1,1,0,0,0,x,1,70,1,1/2,0,0,1/2,-1/2,0,0,0,0,0,100,0,1,0,0,0,0,0,0,1,-1,j,P,1,0,3,0,1,15,-15,0,0,0,0,P,2,0,-5/4,0,0,-5/4,5/4,5/2,0,0,1,P,3,0,0,0,0,0,1,0,0,0,0,=,min400/15,=10,故 为换出变量。,2.2.5 目标规划的单纯形法,13,ppt课件完整,cj 00P100P302.5P20P2CBXBbx1x2P,c,j,0,0,P,1,0,0,P,3,0,2.5P,2,0,P,2,C,B,X,B,b,x,1,x,2,P,3,80/3,0,-1/5,1/15,-1/15,-1,1,0,0,0,0,2.5P,2,70/3,0,2/5,1/30,-1/30,0,0,-1,1,0,0,0,x,1,250/3,1,2/5,1/30,-1/30,0,0,0,0,0,0,0,100,0,1,0,0,0,0,0,0,1,1,j,P,1,0,0,1,0,0,0,0,0,0,0,P,2,0,-1,-1/12,1/12,0,0,2/5,0,0,1,P,3,0,1/5,-1/15,1/15,1,0,0,0,0,0,=,min,350/6,1250/6,100/1=75,故 为换出变量。,2.2.5 目标规划的单纯形法,14,ppt课件完整,cj 00P100P302.5P20P2CBXBbx1x2P,c,j,0,0,P,1,0,0,P,3,0,2.5P,2,0,P,2,C,B,X,B,b,x,1,x,2,P,3,115/3,0,0,1/12,-1/12,-1,1,-1/2,1/2,0,0,0,x,2,175/3,0,1,1/12,-1/12,0,0,-5/2,5/2,0,0,0,x,1,60,1,0,0,0,0,0,-1,1,0,0,0,125/3,0,0,-1/12,1/12,0,0,5/2,-5/2,1,1,j,P,1,0,0,1,0,0,0,0,0,0,0,P,2,0,0,0,0,0,0,0,5/2,0,1,P,3,0,0,-1/12,1/12,1,0,1/2,-1/2,0,0,表中P,3,行仍有负数,，,说明,P,3,优先等级目标没有实现，但已无法改进，得到满意解,x,1,60，,x,2,175/3，115/3，125/3。,2.2.5 目标规划的单纯形法,15,ppt课件完整,cj 00P100P302.5P20P2CBXBbx1x2P,课堂练习：,用单纯形法求解下列目标规划问题,16,ppt课件完整,课堂练习：用单纯形法求解下列目标规划问题16ppt课件完整,c,j,0,0,0,P,1,P,2,P,2,P,3,0,0,C,B,X,B,b,x,1,x,2,x,3,0,0,1,1,1,1,0,0,0,0,0,P,2,10,1,2,0,0,1,1,0,0,0,P,3,56,8,10,0,0,0,0,1,1,0,0,x,3,11,2,1,0,0,0,0,0,0,1,j,P,1,0,0,0,1,0,0,0,0,0,P,2,1,2,0,0,0,2,0,0,0,P,3,8,10,0,0,0,0,0,1,0,=,min,10/2,56/10,11/1=5,故 为换出变量。,2.2.5 目标规划的单纯形法,17,ppt课件完整,cj 000P1 P2 P2P3 00CBXBbx1x2,c,j,0,0,0,P,1,P,2,P,2,P,3,0,0,C,B,X,B,b,x,1,x,2,x,3,0,2,3/2,0,1,1,1/2,-1/2,0,0,0,0,x,2,5,1/2,1,0,0,1/2,-1/2,0,0,0,P,3,6,3,0,0,0,-5,5,1,1,0,0,x,3,6,3/2,0,0,0,-1/2,1/2,0,0,1,j,P,1,0,0,0,1,0,0,0,0,0,P,2,0,0,0,0,1,1,0,0,0,P,3,3,0,0,0,5,-5,0,1,0,=,min10/3,10,6/3,12/3=2,故 为换出变量。,2.2.5 目标规划的单纯形法,18,ppt课件完整,cj 000P1 P2 P2P3 00CBXBbx1x2,c,j,0,0,0,P,1,P,2,P,2,P,3,0,0,C,B,X,B,b,x,1,x,2,x,3,0,2,0,0,1,1,3,-3,-1/2,1/2,0,0,x,2,4,0,1,0,0,4/3,-4/3,-1/6,1/6,0,0,x,1,2,1,0,0,0,-5/3,5/3,1/3,-1/3,0,0,x,3,3,0,0,0,0,2,-2,-1/2,1/2,1,j,P,1,0,0,0,1,0,0,0,0,0,P,2,0,0,0,0,1,1,0,0,0,P,3,0,0,0,0,0,0,1,0,0,最优解为,x,1,2，,x,2,4。但非基变量 的检验数为零，故此题有无穷多最优解。,=,min4,24,6=4,故 为换出变量。,2.2.5 目标规划的单纯形法,19,ppt课件完整,cj 000P1 P2 P2P3 00CBXBbx1x2,c,j,0,0,0,P,1,P,2,P,2,P,3,0,0,C,B,X,B,b,x,1,x,2,x,3,0,4,0,0,2,-2,6,-6,-1,1,0,0,x,2,10/3,0,1,-1/3,1/3,1/3,-1/3,0,0,0,0,x,1,10/3,1,0,2/3,-2/3,1/3,-1/3,0,0,0,0,x,3,1,0,0,-1,1,-1,1,0,0,1,j,P,1,0,0,0,1,0,0,0,0,0,P,2,0,0,0,0,1,1,0,0,0,P,3,0,0,0,0,0,0,1,0