《运筹学复习题解答》PPT课件

运筹学复习 题及其解答,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 + 3x2 s.t. 2x1 + x2 16 x1 + 3x2 20 x1 + x2 = 10 x1, x2 0,解：化为标准形并加入人工变量为：,max z = 2x1 + 3x2 - Mx5 - Mx6 s.t. 2x1 + x2 + x4 = 16 x1 + 3x2 - x3 + x5 = 20 x1 + x2 + x6= 10 x1, x2 , x3 , x4 , x5 , x6 0,最优解为(0，10)T , 最优值为 z* = 30,4： 利用两阶段法计算下题： max z = 30 x1+40 x2100 x3 s.t. 4x1+3x2 x3=30 x1+3x2 x3=12 x1, x2 , x3 30,第一阶段：m in z = x4+ x5 s.t. 4x1+3x2 x3 + x4 =30 x1+3x2 x3 + x5 =12 x1, x2 , x3 , x4 , x5 30,第二阶段：,原规划最优解为： x1=6 , x2=2 , x3=0 , z =240,5：写出下面问题的对偶问题 max z =2x1 2x2 +2x3+x4 s. t . x1 +x2 + x3 + x4 12 2 x1 x2 +3 x3 = 7 x1 x3 + 4x4 3 x1 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 = 10 x1 + 6x2 + 4x3 s.t. x1 + x2 + x3100 10 x1 +4 x2 +5 x3600 2x1 +2 x2 +6 x3300 x1 , 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万元。,