运筹学-线性规划习题解析(课堂PPT).ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,帅青红 网上支付与电子银行,1,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,帅青红 网上支付与电子银行,1,管理运筹学,第一章 线性规划,第一章 线性规划,1,、某化工厂生产某项化学产品，每单位标准重量为,1000,克，由,A,、,B,、,C,三种化学物混合而成。产品组成成分是每单位产品中,A,不超过,300,克，,B,不少于,150,克，,C,不少于,200,克。,A,、,B,、,C,每克成本分别为,5,元、,6,元、,7,元。问如何配置此化学产品，才能使成本最低？,1,帅青红 网上支付与电子银行,min S=min(5x,1,+6x,2,+7x,3,),x,1,+x,2,+x,3,=1000,x,1,300,x,2,150,x,3,200,x,1,x,2,x,3,0,解：,设配制此化学产品所需,A,、,B,、,C,三种化学物分别为,x,1,，,x,2,，,x,3,克，成本为,S,元，则由题意可得本题的线性规划模型为,：,1,帅青红 网上支付与电子银行,第一章 线性规划,2,、某产品重量为,150,千克，用,A,、,B,两种原料制成。每单位,A,原料成本为,2,元，每单位,B,原料成本为,8,元。该产品至少需要含,14,单位,B,原料，最多含,20,单位,A,原料。每单位,A,、,B,原料分别重,5,千克、,10,千克，为使成本最小，该产品中,A,、,B,原料应各占多少？,1,帅青红 网上支付与电子银行,min S=min(2x,1,+8x,2,),5x,1,+10 x,2,=150,x,1,20,x,2,14,x,1,x,2,0,解：,由题意可设该产品中,A,、,B,原料分别为,x,1,，,x,2,千克，总成本为,S,，则本题线性规划模型为：,1,帅青红 网上支付与电子银行,第一章 线性规划,3,、设某工厂有甲、乙、丙、丁四台机床，生产,A,、,B,、,C,、,D,、,E,、,F,六种产品。加工每一件产品所需要时间和每一件产品的单价如下表所示：,表中没有,填数的表示这,台机床不参加,生产这种产品。,现假设在某一,时间内，甲、,乙、丙、丁四台机床的最大工作能力分别为,850,、,700,、,600,、,900,工时，问这一时段内，每种产品各应生产多少，才能使该厂总收入最大？,1,帅青红 网上支付与电子银行,max S=max(40 x,1,+28x,2,+32x,3,+72x,4,+64x,5,+80 x,6,),x,1,+x,2,+x,3,+3x,4,+3x,5,+3x,6,850,2x,1,+5x,4,700,2x,2,+5x,4,600,3x,3,+8x,6,900,x,1,，,x,2,x,6,0,解：,由题意可设产品,A,、,B,、,C,、,D,、,E,、,F,分别生产,x,1,，,x,2,，,x,3,，,x,4,，,x,5,，,x,6,单位，总收入为,S,元，则本题的线性规划模型为：,1,帅青红 网上支付与电子银行,第一章 线性规划,4,、一家玩具公司制造三种玩具，每一种要求不同的制造技术。高级的一种需要,17,个小时加工装配，,8,小时检测，每台利润,30,元；中级的需,2,小时加工装配，半小时检测，每台利润,5,元；低级的需半小时加工装配，,10,分钟检测，每台利润,1,元。现公司可供利用的加工装配时间为,500,小时，检测时间,100,小时。市场预测显示，对高级、中级、低级玩具的需求量分别不超过,10,台、,30,台、,100,台，试制定一个能够使总利润最大的生产计划。,1,帅青红 网上支付与电子银行,解：,由题意设生产高级、中级、低级玩具各为,x,1,，,x,2,，,x,3,台，总利润为,S,元，则由题意可得本题的线性规划模型为：,由题意可得下表条件约束：,1,帅青红 网上支付与电子银行,max S=max(30 x,1,+5x,2,+x,3,),17x,1,+2x,2,+1/2x,3,500,8x,1,+1/2x,2,+1/6x,3,100,x,1,10,x,2,30,x,3,100,x,1,x,2,x,3,0,1,帅青红 网上支付与电子银行,第一章 线性规划,5,、现有,300cm,长的钢管,500,根，需截成,70cm,长和,80cm,长两种规格的成套材料。每套由,70cm,的,3,根，,80cm,的,12,根组成。问如何截管，可以使余料最少，套数最多,？,1,帅青红 网上支付与电子银行,解：由题设条件可得到,1,根,300cm,长的钢管有,以下几种分割方法：,1,帅青红 网上支付与电子银行,设,x,1,、,x,2,、,x,3,、,x,4,分别代表四种方法,分割,300cm,的钢管的根数，,S,表示废料的总长度,x,1,+x,2,+x,3,+x,4,=500,可以截得,80cm,钢管（,3x,1,+2x,2,+x,3,）根,，,70cm,钢管（,2x,2,+3x,3,+4x,4,）根,，,共有废料（,60 x,1,+10 x3+20 x,4,）,cm,则,可得：,(,3x,1,+2x,2,+x,3,):(,2x,2,+3x,3,+4x,4,)=12:3,化,简的：,3,x,1,-6x,2,-11x,3,-16x,4,=0,min S=min(60 x,1,+10 x,2,+20 x,3,),x,1,+x,2,+x,3,+x,4,=500,3x,1,-6x,2,-11x,3,-16x,4,=0,x,1,，,x,2,，,x,3,x,4,0,1,帅青红 网上支付与电子银行,第一章 线性规划,6,、某皮革厂生产甲、乙两种皮带，生产甲、乙皮带每条可获利分别为,4,元、,3,元。但生产一条甲皮带是生产一条乙皮带所需工时的,2,倍，如果全部生产乙皮带，该厂每天可生产,1000,条，但皮革供应只够日产,800,条（甲、乙两种皮带合计），甲、乙皮带所用皮扣（一条一扣）每天分别只能供应,400,个、,700,个。问如何安排生产，可使该厂获利最大？,1,帅青红 网上支付与电子银行,max S=max(4x,1,+3x,2,),2x,1,+x,2,1000,x,1,+x,2,800,x,1,400,x,2,700,x,1,、,x,2,0,解：由题设条件设生产甲、乙两种皮带分别为,x,1,、,x,2,根,交点：,x,1,=200,x,2,=600,1,帅青红 网上支付与电子银行,第一章 线性规划,7,、某厂用甲、乙两种原料生产,A,、,B,两种产品，制造,A,、,B,产品每吨所需要的各种原料、可得利润以及工厂现有的各种原料数如下表所示：,1,帅青红 网上支付与电子银行,（,1,）在现有原料条件下，如何组织生产才能使利润最大,max S=max(7x,1,+5x,2,),x,1,+2x,2,28,4x,1,+x,2,42,x,1,，,x,2,0,解：设生产,A,、,B,两种产品分别为,x,1,、,x,2,单位,1,帅青红 网上支付与电子银行,（,1,）在现有原料条件下，如何组织生产才能使,利润最大,图解：,x,2,x,1,14,28,42,10.5,4x,1,+x,2,=42,X,1,+2x,2,=28,k=-7/5,4x,1,+x,2,=42,X,1,+2x,2,=28,解得：,x,1,=8,x,2,=10,K,1,=-4,k,2,=-1/2,1,帅青红 网上支付与电子银行,（,2,）如果原料甲增加到,42,吨，原最优解是否改变？,图解：,x,2,x,1,21,42,42,10.5,4x,1,+x,2,=42,X,1,+2x,2,=42,k=-7/5,4x,1,+x,2,=42,X,1,+2x,2,=42,解得：,x,1,=6,x,2,=18,1,帅青红 网上支付与电子银行,(3),如果每吨,B,产品的利润增加到,15,万元，原最优解,是否改变？,图解：,x,2,x,1,14,28,42,10.5,4x,1,+x,2,=42,X,1,+2x,2,=28,k=-7/15,最优解是,x,1,+2x,2,=28,与,x,2,轴的交点（,0,14,）,1,帅青红 网上支付与电子银行,（,4,）每吨,B,产品的利润在什么范围内变化，原最优,解才不会改变？,图解：,x,2,x,1,14,28,42,10.5,4x,1,+x,2,=42,X,1,+2x,2,=28,-4k-1/2,k,1,=-4,k,2,=-1/2,可得：,-4k-1/2,目标函数：,7x,1,+bx,2,k=-7/b,7/4b14,1,帅青红 网上支付与电子银行,复习,条件：,满足前约束,满足后约束,无非零分量，或有非零分量但其非零分量对应的,A,的列向量线性无关,使目标函数最大,解类型,基础解,可行解,基可行解,最优解,基最优解,满足条件,1,帅青红 网上支付与电子银行,第一章 线性规划,10,、已知线性规划问题为：,min S=min(x,1,+2x,2,-3x,3,+4x,4,),5x,2,+x,3,+3x,4,=5,x,1,+4x,2,+x,3,+4x,4,=7,x,i,(i=1,2,3,4),判断下述各点：,X,1,=,（,8,2,7,，,-4,）,T,，,X,2,=,（,1,，,0,2,1,）,T,，,X,3,=,（,2,0,5,0,）,T,，,X,4,=,（,0,0,，,-1,2,）,T,，,X,5,=,（,3,1,0,0,）,T,是不是该问题的可行解、基础解、基可行解。试从中找出最优的一个解。,1,帅青红 网上支付与电子银行,第一章 线性规划,X,1,不是基础解（满足前约束但非零分量对应的列向量线性相关），不是可行解（不满足后约束），不是基可行解。,X,2,不是基础解（非零分量对应的列变量线性相关），是可行解（满足前后约束），不是基可行解。,X,3,是基础解（非零分量对应的列变量线性无关）、可行解，因此也是基可行解。,X,4,是基础解，不是可行解，因此也不是基可行解。,X,5,是基础解、可行解，因此也是基可行解。,将,X,3,和,X,5,带入目标函数可得：,S,3,S,5,，所以,X,3,是最优解。,1,帅青红 网上支付与电子银行,第一章 线性规划,11,、已知,X,0,=,（,2,3,0,）,T,是某线性规划问题的最优解，能否判断：,（,1,）,X,0,一定是基础解；,（,2,）,X,0,一定是可行解；,（,3,）,X,0,一定是基可行解；,（,4,）,X,0,一定是基最优解。,错,对,错,错,1,帅青红 网上支付与电子银行,第一章 线性规划,12,、已知,X,0,=,（,2,0,，,-1,）,T,是某已化成满秩标准形的，具有,3,个变量的线性规划问题的一组值，能否判定：,（,1,）,X,0,一定不是基础解；,（,2,）,X,0,一定不是可行解；,（,3,）,X,0,一定不是基可行解；,（,4,）,X,0,一定不是最优解；,（,5,）,X,0,一定不是基最优解。,错,对,对,对,对,1,帅青红 网上支付与电子银行,第一章 线性规划,13,、已知线性规划问题,max S=max(x,1,+x,2,-x,3,),ax,1,+9x,2,+7x,3,+9x,4,+x,5,=1,5x,1,+bx,2,-7x,3,+x,5,=-3,x,i,0(i=1,2,5),a,b,为任意常数,X,0,=,（,9,0,7,0,6,）,T,是其变量的一组值。能否判定：,（,1,）,X,0,一定不是基础解；,（,2,）,X,0,一定不是可行解；,（,3,）,X,0,一定不是基可行解；,（,4,）,X,0,一定不是最优解；,（,5,）,X,0,一定不是基最优解。,对,1,帅青红 网上支付与电子银行,第一章 线性规划,评讲完啦,谢谢大家,1,帅青红 网上支付与电子银行,