运筹学复习题解答

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,运筹学复习,题及其解答,1：,某药厂生产A、B、C三种药物，可供选择的原料有甲、乙、丙、丁，四种原料的成本分别是5元，6元，7元，8元。每公斤不同原料所能提取的各种药物的数量（单位：克/公斤）见下表,药厂要求每天生产A药恰好100克，B药至少530克，C药不超过160克，要求选配各种原料的数量既满足生产需要，又使总成本最小，试建立此问题的数学模型。,药名,原料,A,B,C,成本（元/kg）,甲,1,5,2,5,乙,1,4,1,6,丙,1,5,1,7,丁,1,6,2,8,生产量,恰好100克,至少530克,不超过160克,解：,设,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,2：,用单纯形法求解线性规划问题,解：,化为标准形为,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,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,解：,化为标准形并加入人工变量为：,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,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,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,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,第二阶段：,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,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,无约束,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,解：,由差额法得初始运输方案,销,产,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,销,产,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,所有的非基变量的检验数都大于零。所以所,得运输方案为最优方案，最少运费为：,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,销,产,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,最优性检验：由位势法得,销地,产地,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,的检验数小于零，,需要进行调整，得,销地,产地,B,1,B,2,B,3,B,4,A,1,25,A,2,20,5,A,3,15,30,5,+5,5,+5,5,新的运输方案为,销地,产地,B,1,B,2,B,3,B,4,A,1,25,A,2,15,10,A,3,15,5,30,重新进行检验得：,销地,产地,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,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,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,9:,某厂生产甲、乙、丙3种产品，分别经过A、B、,C三种设备加工，已知生产单位产品所需的设备台时,数、设备的现有加工能力及每件产品的利润见下表：,甲,乙,丙,设备能力/台时,A,1,1,1,100,B,10,4,5,600,C,2,2,6,300,单位产品利润/元,10,6,4,（1）建立线性规划模型，求该厂获利最大的生产计划；,（2）产品丙每件的利润增加到多少时才值得安排,生产？如产品丙每件的利润增加到50/6，求,最优生产计划。,（3）产品甲的利润在什么范围内变化时，原最优,计划保持不变？,（4）设备A的能力如为100+10,，确定保持原最优,基不变的 的变化范围。,（5）如有一种新产品丁，加工一件需设备A、B、,C的台时各为 1h，4h，3h，预期每件的利润,为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,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,（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,（3）产品甲的利润的范围为：,即当甲的利润在6，15之间变化时，最优计划不变。,（4）对设备A的工时作灵敏度分析：,（5）因为产品丁的影子（机会）成本为：,产品丁的影子价格小于其利润，故该产品值得安,排生产。,（6）合同要求至少生产10件产品丙,x,3,必须,大于等于10,目标值下降;下降程度可用,x,3,的检,验数进行计算：,10.,下表中给出