资源预览内容
第1页 / 共43页
第2页 / 共43页
第3页 / 共43页
第4页 / 共43页
第5页 / 共43页
第6页 / 共43页
第7页 / 共43页
第8页 / 共43页
第9页 / 共43页
第10页 / 共43页
亲,该文档总共43页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述
运筹学复习 题及其解答,1:某药厂生产A、B、C三种药物,可供选择的原料有甲、乙、丙、丁,四种原料的成本分别是5元,6元,7元,8元。每公斤不同原料所能提取的各种药物的数量(单位:克/公斤)见下表药厂要求每天生产A药恰好100克,B药至少530克,C药不超过160克,要求选配各种原料的数量既满足生产需要,又使总成本最小,试建立此问题的数学模型。,解:设 x1 , x2 , x3 , x4 分别为原料甲、乙、丙、丁的选配数量(单位:公斤),则有,min z =5x1+6x2+7x3+8x4,s . t . x1+ x2+ x3+ x4 = 100,5x1+4 x2+5 x3+ 6 x4 530,2x1+ x2+ x3+ 2 x4 160,x1 , x2 , x3 , x4 0,2:用单纯形法求解线性规划问题,解:化为标准形为,20,10,20,0,30,4,-5,-3,0,10,2,-3,-1,0,1,-3,-2,20,7.5,5,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,所以,所求最优解为, x1=15 , x2=5 , x3=0 , x4=10 , x5=x6=0最优值为:z*=25,3 : 用大M法计算下列线性规划,max z = 2x1 + 3x2s.t. 2x1 + x2 16x1 + 3x2 20x1 + x2 = 10x1, x2 0,解:化为标准形并加入人工变量为:,max z = 2x1 + 3x2 - Mx5 - Mx6 s.t. 2x1 + x2 + x4 = 16x1 + 3x2 - x3 + x5 = 20x1 + x2 + x6= 10x1, x2 , x3 , x4 , x5 , x6 0,最优解为(0,10)T , 最优值为 z* = 30,4: 利用两阶段法计算下题:max z = 30x1+40x2100x3s.t. 4x1+3x2 x3=30x1+3x2 x3=12x1, x2 , x3 30,第一阶段:m in z = x4+ x5s.t. 4x1+3x2 x3 + x4 =30x1+3x2 x3 + x5 =12x1, x2 , x3 , x4 , x5 30,第二阶段:,原规划最优解为:x1=6 , x2=2 , x3=0 , z =240,5:写出下面问题的对偶问题max z =2x1 2x2 +2x3+x4s. t . x1 +x2 + x3 + x4 122 x1 x2 +3 x3 = 7x1 x3 + 4x4 3x1 0 ,x3 0 , x2, x4 无约束,6 : 求解下列产销平衡的运输问题,下表中列出的为产地到销地之间的运价。,解:由差额法得初始运输方案,差额,差 额,4,6,5,3,8,3,1,1,2,5,最优性检验,3,0,0,1,7,-2,6,2,7,2,1,9,12,所有的非基变量的检验数都大于零。所以所 得运输方案为最优方案,最少运费为:,Z* = 23+5 3+1 1+3 8+6 4+3 5 = 85,7:求解下列运费最少的运输问题,由伏格法(差额法)得:,差额,差额,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,最优性检验:由位势法得,6,1,0,2,2,2,7,1,2,3,1,5,-1,从表中可以看出,a32 的检验数小于零,,需要进行调整,得,+5, 5,+5,5,新的运输方案为,重新进行检验得:,6,1,0,2,1,3,8,1,2,2,0,4,1,z *= 257+15 2+10 6+15 9+5 3+30 4=535,8: 用对偶单纯形法求解下列问题,Max z = 2x1 2x2 + 3x3,s.t. x1 + 4x2 + 3 x3 8,x1 + 2x2 + 2 x3 6,x1 , x2 , x3 0,+x4,= 8,+x5,=, x4 , x5 0,9:某厂生产甲、乙、丙3种产品,分别经过A、B、 C三种设备加工,已知生产单位产品所需的设备台时 数、设备的现有加工能力及每件产品的利润见下表:,(1)建立线性规划模型,求该厂获利最大的生产计划;,(2)产品丙每件的利润增加到多少时才值得安排生产?如产品丙每件的利润增加到50/6,求最优生产计划。 (3)产品甲的利润在什么范围内变化时,原最优计划保持不变? (4)设备A的能力如为100+10,确定保持原最优基不变的 的变化范围。 (5)如有一种新产品丁,加工一件需设备A、B、C的台时各为 1h ,4h,3h,预期每件的利润,为8元,是否值得安排生产? (6)如合同规定该厂至少生产10件产品丙,试确定最优生产计划。,解:设甲、乙、丙的产量分别为 x1 , x2 , x3 ,则max z = 10x1 + 6x2 + 4x3s.t. x1 + x2 + x310010x1 +4 x2 +5 x36002x1 +2 x2 +6 x3300x1 , x2 , x3 0,(2)对c3 作灵敏度分析:因为x3为非基变量,当丙每件的利润增加到50/6时,有,(3)产品甲的利润的范围为:,即当甲的利润在6,15之间变化时,最优计划不变。,(4)对设备A的工时作灵敏度分析:,(5)因为产品丁的影子(机会)成本为:,产品丁的影子价格小于其利润,故该产品值得安 排生产。,(6)合同要求至少生产10件产品丙 x3 必须 大于等于10 目标值下降; 下降程度可用 x3 的检 验数进行计算:,10. 下表中给出某求极大化问题的单纯形表,问表中a1 , a2 , c1 , c2 , d 为何值时,以及表中变量属于哪种类型时有: (a) 表中解为唯一最优解; (b)表中解为无穷多最优解之一; (c) 表中解为退化的可行解; (d) 下一步迭代将以 x1 替代基变量 x5 ; (e) 该线性规划问题具有无界解; (d) 该线性规划无可行解。,解:,中至少有一个为0。,为人工变量,且,11. 求A到E的下列最短路线及其长度。,解:图形变化为,0,3,1,5,5,3,5,4,8,6,7,8,最短路线 AB2C1D1E,其长度为 8 。,12. 某工厂购进100台机器,准备生产 p1 , p2 两种产品。若生产产品 p1 ,每台机器每年可收入45万元,损坏率为65%;若生产产品 p2 ,每台机器每年可收入35万元,损坏率为35%;估计三年后将有新 的机器出现,旧的机器将全部淘汰。试问每年应如何安排生产,使在三年内收入最多?,解:首先构造这个问题的动态规划模型。1. 变量设置(1)设阶段变量k表示年度,因此,阶段总数n=3。,(2)状态变量sk表示第k年度初拥有的完好机床台数,同时也是第 k1 年度末时的完好机床数量。 (3)决策变量uk,表示第k年度中分配于生产产品 p1的机器台数。于是sk uk便为该年度中分配于生产产品 p1的机器台数 2. 状态转移方程为,k = 1,2,3, 4,3允许决策集合,在第 k 段为,4目标函数。设gk(sk,uk)为第k年度的产量,则gk(sk,uk) = 45uk + 35(skuk) , 因此,目标函数为,5条件最优目标函数递推方程。,k 1 , 2 , 3.,令fk(sk)表示由第k年的状态sk出发,采取最优分配方 案到第3年度结束这段时间的产品产量,根据最优化 原理有以下递推关系:,k =1 , 2 , 3 。,6.边界条件为,下面采用逆序递推计算法,从第3年度开始递推计算。,k =3 时有,当 u3*=s3 时,f3(s3) 有最大值,相应的有f3(s3)= 45s3,k =2时有,因此,当 u2*=0 时,有最大值 f2(s2) = 64.25 s2,k = 1 时有,当取u1*=0时, f1(s1)有最大值,即f1(s1)=76.7625s1 , 因为s1=100 , 故 f1(s1) = 7676 . 25 万元 得最优决策为:第一年将100台机器全部生产产品 p2,第二年把余下的机器继续生产产品p2,第三年 把余下的机器全部生产产品p1。三年的总收入为 7676.25万元。,
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号