运筹学复习题解答市公开课一等奖百校联赛优质课金奖名师赛课获奖课件.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,本资料仅供参考，不能作为科学依据。谢谢。本资料仅供参考，不能作为科学依据。本资料仅供参考，不能作为科学依据。谢谢。本资料仅供参考，不能作为科学依据。,运筹学复习,题及其解答,1/43,1：,某药厂生产A、B、C三种药品，可供选择原料有甲、乙、丙、丁，四种原料成本分别是5元，6元，7元，8元。每千克不一样原料所能提取各种药品数量（单位：克/千克）见下表,药厂要求天天生产A药恰好100克，B药最少530克，C药不超出160克，要求选配各种原料数量既满足生产需要，又使总成本最小，试建立此问题数学模型。,2/43,药名,原料,A,B,C,成本（元/kg）,甲,1,5,2,5,乙,1,4,1,6,丙,1,5,1,7,丁,1,6,2,8,生产量,恰好100克,最少530克,不超出160克,3/43,解：,设,x,1,x,2,x,3,x,4,分别为原料甲、乙、丙、丁选配数量（单位：千克），则有,min z,=5,x,1,+6,x,2,+7,x,3,+8,x,4,s.t.,x,1,+,x,2,+,x,3,+,x,4,=100,5,x,1,+4,x,2,+5,x,3,+6,x,4,530,2,x,1,+,x,2,+,x,3,+2,x,4,160,x,1,x,2,x,3,x,4,0,4/43,2：,用单纯形法求解线性规划问题,解：,化为标准形为,5/43,C,2,1,1,0,0,0,C,B,X,B,B,-1,b,x,1,x,2,x,3,x,4,x,5,x,6,0,x,4,60,3,1,1,1,0,0,0,x,5,10,1,1,2,0,1,0,0,x,6,20,1,1,1,0,0,1,0,2,1,1,0,0,0,20,10,20,0,x,4,60,3,1,1,1,0,0,2,x,1,10,1,1,2,0,1,0,0,x,6,20,1,1,1,0,0,1,0,2,1,1,0,0,0,0,30,4,-5,-3,0,10,2,-3,-1,0,1,-3,-2,20,7.5,5,0,x,4,30,0,4,5,1,3,0,2,x,1,10,1,1,2,0,1,0,-1,x,2,10,0,2,3,0,1,1,1,5,-1.5,-0.5,0.5,15,0,0.5,0.5,0.5,10,0,1,-1,-2,25,0,0,0,-1.5,-1.5,-0.5,所以，所求最优解为,x,1,=15,x,2,=5,x,3,=0,x,4,=10,x,5,=,x,6,=0,最优值为：,z,*=25,6/43,3：,用大M法计算以下线性规划,max z,=2,x,1,+3,x,2,s.t,.2,x,1,+,x,2,16,x,1,+3,x,2,20,x,1,+,x,2,=10,x,1,x,2,0,7/43,解：,化为标准形并加入人工变量为：,max z,=2,x,1,+3,x,2,-M,x,5,-M,x,6,s.t,.2,x,1,+,x,2,+,x,4,=,16,x,1,+3,x,2,-,x,3,+,x,5,=,20,x,1,+,x,2,+,x,6,=10,x,1,x,2,x,3,x,4,x,5,x,6,0,8/43,9/43,c,j,2,3,0,0,-M,-M,C,B,X,B,B,-1,b,x,1,x,2,x,3,x,4,x,5,x,6,0,x,4,6,1,0,0,1,0,-1,3,x,2,10,2,1,0,0,0,1,0,x,3,10,1,0,1,0,-1,3,j,30,-1,0,0,0,-M,-M-3,最优解为(0，10),T,最优值为,z,*=30,10/43,4：,利用两阶段法计算下题：,max z,=30,x,1,+40,x,2,100,x,3,s.t.4,x,1,+3,x,2,x,3,=30,x,1,+3,x,2,x,3,=12,x,1,x,2,x,3,30,第一阶段：,m in z,=,x,4,+,x,5,s.t.4,x,1,+3,x,2,x,3,+,x,4,=30,x,1,+3,x,2,x,3,+,x,5,=12,x,1,x,2,x,3,x,4,x,5,30,11/43,C,0,0,0,1,1,C,B,X,B,b,x,1,x,2,x,3,x,4,x,5,1,x,4,30,4,3,1,1,0,10,1,x,5,12,1,3,1,0,1,4,j,42,5,6,2,0,0,1,x,4,18,3,0,0,1,1,6,0,x,2,4,1/3,1,1/3,0,1/3,12,j,18,6,0,0,0,1,0,x,1,6,1,0,0,1/3,1/3,0,x,2,2,0,1,1/3,1/9,4/9,j,18,0,0,0,1,1,12/43,第二阶段：,C,30,40,100,C,B,X,B,b,x,1,x,2,x,3,30,x,1,6,1,0,0,40,x,2,2,0,1,1/3,j,240,0,0,260/3,原规划最优解为：,x,1,=6,x,2,=2,x,3,=0,z,=240,13/43,5：,写出下面问题对偶问题,max z,=2,x,1,2,x,2,+2,x,3,+,x,4,s.t.,x,1,+,x,2,+,x,3,+,x,4,12,2,x,1,x,2,+3,x,3,=7,x,1,x,3,+4,x,4,3,x,1,0,x,3,0,x,2,x,4,无约束,14/43,6,:求解以下产销平衡运输问题，下表中,列出为产地到销地之间运价。,销地,产地,B,1,B,2,B,3,B,4,产量,A,1,3,11,3,12,7,A,2,1,9,2,8,4,A,3,7,4,10,5,9,销量,3,6,5,6,20,15/43,解：,由差额法得初始运输方案,销,产,B,1,B,2,B,3,B,4,产量,B,1,B,2,B,3,B,4,A,1,7,3,11,3,12,A,2,4,1,9,2,8,A,3,9,7,4,10,5,销量,3,6,5,6,20,0,1,1,2,5,1,3,差额,差,额,4,6,0,1,2,5,3,2,1,4,8,3,1,1,2,5,16/43,销,产,B,1,B,2,B,3,B,4,A,1,3,11,3,12,A,2,1,9,2,8,A,3,7,4,10,5,最优性检验,u,i,v,j,3,0,0,1,7,-2,6,2,7,2,1,9,12,17/43,全部非基变量检验数都大于零。所以所,得运输方案为最优方案，最少运费为：,Z,*=2,3+5 3+1 1+3 8+6 4+3 5=85,7：,求解以下运费最少运输问题,销地,产地,B,1,B,2,B,3,B,4,产量,A,1,10,5,6,7,25,A,2,8,2,7,6,25,A,3,9,3,4,8,50,销量,15,20,30,35,100,18/43,销,产,B,1,B,2,B,3,B,4,产量,B,1,B,2,B,3,B,4,A,1,25,10,5,6,7,A,2,25,8,2,7,6,A,3,50,9,3,4,8,销量,15,20,30,35,100,由伏格法（差额法）得：,差额,差额,1,4,1,1,1,2,1,2,20,1,1,4,4,30,3,2,1,7,25,1,2,6,5,5,15,19/43,最优性检验：由位势法得,销地,产地,B,1,B,2,B,3,B,4,A,1,10,5,6,7,A,2,8,2,7,6,A,3,9,3,4,8,u,i,v,j,6,1,0,2,2,2,7,1,2,3,1,5,-1,从表中能够看出，,a,32,检验数小于零，,20/43,需要进行调整，得,销地,产地,B,1,B,2,B,3,B,4,A,1,25,A,2,20,5,A,3,15,30,5,+5,5,+5,5,新运输方案为,21/43,销地,产地,B,1,B,2,B,3,B,4,A,1,25,A,2,15,10,A,3,15,5,30,重新进行检验得：,22/43,销地,产地,B,1,B,2,B,3,B,4,A,1,10,5,6,7,A,2,8,2,7,6,A,3,9,3,4,8,u,i,v,j,6,1,0,2,1,3,8,1,2,2,0,4,1,z,*=25,7+15 2+10 6+15 9+5 3+30 4=535,23/43,8:,用对偶单纯形法求解以下问题,Max,z,=2,x,1,2,x,2,+3,x,3,s.t.,x,1,+,4,x,2,+3,x,3,8,x,1,+,2,x,2,+2,x,3,6,x,1,x,2,x,3,0,+,x,4,=,8,+,x,5,=,x,4,x,5,0,24/43,c,j,2,2,3,0,0,C,B,X,B,B,-1,b,x,1,x,2,x,3,x,4,x,5,0,x,4,8,1,4,3,1,0,8,0,x,5,6,(1),2,2,0,1,6,j,2,2,3,0,0,0,x,4,2,0,2,(,1),1,1,2,x,1,6,1,2,2,0,1,j,0,6,1,0,2,3,2,3,x,3,2,0,2,1,1,1,2,x,1,2,1,2,0,2,3,j,0,4,0,1,3,25/43,9:,某厂生产甲、乙、丙3种产品，分别经过A、B、,C三种设备加工，已知生产单位产品所需设备台时,数、设备现有加工能力及每件产品利润见下表：,甲,乙,丙,设备能力/台时,A,1,1,1,100,B,10,4,5,600,C,2,2,6,300,单位产品利润/元,10,6,4,（1）建立线性规划模型，求该厂赢利最大生产计划；,26/43,（2）产品丙每件利润增加到多少时才值得安排,生产？如产品丙每件利润增加到50/6，求,最优生产计划。,（3）产品甲利润在什么范围内改变时，原最优,计划保持不变？,（4）设备A能力如为100+10,，确定保持原最优,基不变 改变范围。,（5）如有一个新产品丁，加工一件需设备A、B、,C台时各为 1h，4h，3h，预期每件利润,27/43,为8元，是否值得安排生产？,（6）如协议要求该厂最少生产10件产品丙，试确定,最优生产计划。,解：,设甲、乙、丙产量分别为,x,1,x,2,x,3,，则,max z,=10,x,1,+6,x,2,+4,x,3,s.t.,x,1,+,x,2,+,x,3,100,10,x,1,+4,x,2,+5,x,3,600,2,x,1,+2,x,2,+6,x,3,300,x,1,x,2,x,3,0,28/43,C,10,6,4,0,0,0,C,B,X,B,B,-1,b,x,1,x,2,x,3,x,4,x,5,x,6,0,x,4,100,1,1,1,1,0,0,100,0,x,5,600,10,4,5,0,1,0,60,0,x,6,300,2,2,6,0,0,1,300,j,0,10,6,4,0,0,0,0,x,4,40,0,0.6,0.5,1,0.1,0,200/3,10,x,1,60,1,0.4,0.5,0,0.1,0,150,0,x,6,180,0,1.2,5,0,0.2,1,150,j,0,0,2,1,0,1,0,6,x,2,200/3,0,1,5/6,5/3,1/6,0,10,x,1,100/3,1,0,1/6,-2/3,1/6,0,0,x,6,100,0,0,4,-2,0,1,j,0,0,0,8/3,-,10/3,2/3,0,29/43,（2）对,c,3,作灵敏度分析：因为,x,3,为非基变量,当丙每件利润增加到50/6时，有,C,10,6,50/6,0,0,0,C,B,X,B,B,-1,b,x,1,x,2,x,3,x,4,x,5,x,6,6,x,2,200/3,0,1,5/6,5/3,1/6,0,80,10,x,1,100/3,1,0,1/6,-2/3,1/6,0,200,0,x,6,100,0,0,4,-2,0,1,25,j,2200/3,0,0,5/3,-10/3,2/3,0,6,x,2,275/6,0,1,0,15/12,1/6,-5/24,10,x,1,175/6,1,0,0,-7/12,1/6,-1/24,50/6,x,3,25,0,0,1,-1/2,0,1/4,j,0,0,0,-5/3,2/3,-5/12,30/43,（3）产品甲利润范围为：,即当甲利润在6，15之间改变时，最优计划不变。,（4）对设备A工时作灵敏度分析：,（5）因为产品丁影子（机会）成本为：,31/43,产品丁影子价格小于其利润，故该产品值得安,排生产。,（6）协议要求最少生产10件产品丙,x,3,必须,大于等于10,目标值下降;下降程度可用,x,3,检,验数进行计算：,32/43,10.,下表中给出某求极大化问题单纯形表，问表中,a,1,a,2,c,1,c,2,d,为何值时，以及表中变量属于哪,种类型时有：,(,a,)表中解为唯一最优解；,(,b,)表中解为无穷多最优解之一；,(,c,)表中解为退化可行解；,(,d,)下一步迭代将以,x,1,替换基变量,x,5,；,(,e,)该线性规划问题含有没有界解；,(,d,)该线性规划无可行解。,33/43,x,1,x,2,x,3,x,4,x,5,x,3,d,4,a,1,1,0,0,x,4,2,1,5,0,1,0,x,5,3,a,2,3,0,0,1,c,j,z,j,c,1,c,2,0,0,0,解：,中最少有一个为0。,34/43,为人工变量，且,35/43,11.,求A到E以下最短路线及其长度。,A,B,1,B,2,B,3,C,1,C,2,D,1,D,2,D,3,E,3,2,1,4,4,3,1,3,3,5,3,2,5,3,1,4,2,3,1,5,36/43,解：,图形改变为,A,B,1,B,2,B,3,C,1,C,2,D,1,D,2,D,3,E,3,2,1,4,4,3,1,3,3,5,3,2,5,3,1,4,2,3,1,5,0,0,C,3,C,0,0,3,1,5,5,3,5,4,8,6,7,8,最短路线,AB,2,C,1,D,1,E,，其长度为 8。,37/43,12.,某工厂购进100台机器，准备生产,p,1,p,2,两种产,品。若生产产品,p,1,，每台机器每年可收入45万,元，损坏率为65%；若生产产品,p,2,，每台机器,每年可收入35万元，损坏率为35%；预计三年后,将有新 机器出现，旧机器将全部淘汰。试,问每年应怎样安排生产，使在三年内收入最多？,解：,首先结构这个问题动态规划模型。,1.,变量设置,(1),设阶段变量,k,表示年度，所以，阶段总数,n,=3。,38/43,(2),状态变量,s,k,表示第,k,年度初拥有完好机床台数，,同时也是第,k,1,年度末时完好机床数量。,(3),决议变量,u,k,，,表示第,k,年度中分配于,生产产品,p,1,机器台数。于是,s,k,u,k,便为该年度中分配于,生,产产品,p,1,机器台数,2.,状态转移方程为,k,=1，2，3,4,3,允许决议集合,在第,k,段为,39/43,4目标函数。,设,g,k,(,s,k,u,k,),为第,k,年度产量，则,g,k,(,s,k,u,k,)=45,u,k,+35(,s,k,u,k,),所以，目标函数为,5,条件最优目标函数递推方程。,k,1,2,3.,令,f,k,(,s,k,),表示由第,k,年状态,s,k,出发，采取最优分配方,案到第,3,年度结束这段时间产品产量，依据最优化,原理有以下递推关系：,k,=1,2,3。,40/43,6.,边界条件为,下面采取逆序递推计算法,从第,3,年度开始递推计算。,k,=3,时有,当,u,3,*,=,s,3,时,f,3,(,s,3,),有最大值,对应有,f,3,(,s,3,)=45,s,3,k,=,2,时有,41/43,所以，当,u,2,*,=0,时，有最大值,f,2,(,s,2,)=64.25,s,2,k,=1,时有,42/43,当取,u,1,*,=0,时,f,1,(,s,1,),有最大值，即,f,1,(,s,1,)=76.7625,s,1,因为,s,1,=100,故,f,1,(,s,1,)=7676.25,万元,得最优决议为：,第一年将,100,台机器全部生产产品,p,2,，第二年把余下机器继续生产产品,p,2,，第三年,把余下机器全部生产产品,p,1,。三年总收入为,7676.25,万元。,43/43,