(精品)运筹学复习题解答.ppt
运筹学复习运筹学复习运筹学复习运筹学复习题及其解答题及其解答题及其解答题及其解答1：某药厂生产某药厂生产A、B、C三种药物，可供选择的原料三种药物，可供选择的原料有甲、乙、丙、丁，四种原料的成本分别是有甲、乙、丙、丁，四种原料的成本分别是5元，元，6元，元，7元，元，8元。每公斤不同原料所能提取的各种药元。每公斤不同原料所能提取的各种药物的数量（单位：克物的数量（单位：克/公斤）见下表公斤）见下表 药厂要求每天生产药厂要求每天生产A药恰好药恰好100克，克，B药药至少至少530克，克，C药不超过药不超过160克，要求选配各种原料的数克，要求选配各种原料的数量既满足生产需要，又使总成本最小，试建立此问量既满足生产需要，又使总成本最小，试建立此问题的数学模型。题的数学模型。药名药名原料原料ABC成本（元成本（元/kg）甲甲1525乙乙1416丙丙1517丁丁1628生产量生产量恰好恰好100克克至少至少530克克不超过不超过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 02：用单纯形法求解线性规划问题用单纯形法求解线性规划问题解：解：化为标准形为化为标准形为C211000 CBXBB-1bx1x2x3x4x5x60 x4603111000 x5101 120100 x62011 1001 02110002010200 x4603111002x1101 120100 x62011 1001 02110000304-5-30102-3-101-3-2207.550 x43004 51302x1101 12010-1x21002 3011 15-1.5-0.50.51500.50.50.51001-1-225000-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-Mx6s.t.2x1+x2 +x4 =16 x1+3x2 -x3 +x5 =20 x1+x2 +x6=10 x1,x2,x3,x4,x5,x6 0cj2300-M-MCBXBB-1bx1x2x3x4x5x60 x4610010-13x2102100010 x3101010-13 j30-1000-M-M-3最优解为最优解为(0，10)T,最优值为最优值为 z*=304：利用两阶段法计算下题：利用两阶段法计算下题：max z=30 x1+40 x2 100 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 30C000 1 1 CBXBbx1x2x3x4x5 1x43043 11010 1x51213 1014 j 4256200 1x4183001 160 x241/31 1/301/312 j 186000 10 x161001/3 1/30 x2201 1/3 1/94/9 j 18000 1 1第二阶段：第二阶段：C3040 100 CBXBbx1x2x330 x1610040 x2201 1/3 j24000 260/3原规划最优解为：原规划最优解为：x1=6,x2=2,x3=0,z=2405：写出下面问题的对偶问题写出下面问题的对偶问题 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:求解下列产销平衡的运输问题，下表中求解下列产销平衡的运输问题，下表中 列出的为产地到销地之间的运价。列出的为产地到销地之间的运价。销地销地产地产地B1B2B3B4产量产量A13113127A219284A3741059销量销量365620解：解：由差额法得初始运输方案由差额法得初始运输方案 销销产产B1B2B3B4产产量量B1B2B3B4A17311312A241928A3974105销量销量3656200112513差额差额差差额额4601253214831125 销销产产B1B2B3B4A1311312A21928A374105最优性检验最优性检验uivj30017-262721912所有的非基变量的检验数都大于零。所以所所有的非基变量的检验数都大于零。所以所得运输方案为最优方案，最少运费为：得运输方案为最优方案，最少运费为：Z*=2 3+5 3+1 1+3 8+6 4+3 5=857：求解下列运费最少的运输问题求解下列运费最少的运输问题 销地销地产地产地B1B2B3B4产量产量A11056725A2827625A3934850销量销量15203035100 销销产产B1B2B3B4产产量量B1B2B3B4A125 10567A2258276A3509348销量销量15 20 30 35100由由伏格法（差额法）得：伏格法（差额法）得：差额差额差差额额14111212201144303217251265515最优性检验：由位势法得最优性检验：由位势法得 销地销地产地产地B1B2B3B4A110567A28276A39348uivj610222712315-1从从表中可以看出，表中可以看出，a32 的检验数小于零，的检验数小于零，需要进行调整，得需要进行调整，得 销地销地产地产地B1B2B3B4A125A2205A315305+5 5+55新的运输方案为新的运输方案为 销地销地产地产地B1B2B3B4A125A21510A315530重新进行检验得：重新进行检验得：销地销地产地产地B1B2B3B4A110567A28276A39348uivj6102138122041z*=25 7+15 2+10 6+15 9+5 3+30 4=5358:用对偶单纯形法求解下列问题用对偶单纯形法求解下列问题Max z=2x1 2x2+3x3s.t.x1+4x2+3 x3 8 x1+2x2+2 x3 6 x1,x2,x3 0+x4=8+x5=,x4,x5 0cj2 2300 CBXBB-1 bx1x2x3x4x50 x4 81431080 x56(1)22016 j2 23000 x4 20 2(1)112x1612201 j06102 323x32021112x1212023 j040139:某厂生产甲、乙、丙某厂生产甲、乙、丙3种产品，分别经过种产品，分别经过A、B、C三种设备加工，已知生产单位产品所需的设备台时三种设备加工，已知生产单位产品所需的设备台时数、设备的现有加工能力及每件产品的利润见下表：数、设备的现有加工能力及每件产品的利润见下表：甲甲乙乙丙丙设备能力设备能力/台时台时A111100B1045600C226300单位产品利润单位产品利润/元元1064（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+x3 100 10 x1+4 x2+5 x3 600 2x1+2 x2+6 x3 300 x1,x2,x3 0C1064000 CBXBB-1bx1x2x3x4x5x60 x41001111001000 x56001045010600 x6300226001300 j010640000 x44000.60.51 0.10200/310 x16010.40.500.101500 x618001.250 0.21150 j00210 106x2200/3015/65/3 1/6010 x1100/3101/6-2/31/600 x6100004-201 j0008/3-10/3 2/30（2）对）对c3 作灵敏度分析：因为作灵敏度分析：因为x3为非基变量为非基变量当丙每件的利润增加到当丙每件的利润增加到50/6时，有时，有C10650/6000 CBXBB-1bx1x2x3x4x5x66x2200/3015/65/3 1/608010 x1100/3101/6-2/31/602000 x6100004-20125 j2200/3005/3-10/3 2/306x2275/601015/12 1/6-5/2410 x1175/6100-7/121/6-1/2450/6x325001-1/201/4 j000-5/3 2/3-5/12（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)该线性规划无可行解。该线性规划无可行解。x1x2x3x4x5x3d4a1100 x4215010 x53a23001cj zjc1c2000解：解：中中至少有一个为至少有一个为0。为为人工变量，且人工变量，且11.求求A到到E的下列最短路线及其长度。的下列最短路线及其长度。AB1B2B3C1C2D1D2D3E32144313353253142315解：解：图形变化为图形变化为AB1B2B3C1C2D1D2D3E3214431335325314231500C3C0031553548678最短路线最短路线 AB2C1D1E，其长度为其长度为 8。12.某工厂购进某工厂购进100台机器，准备生产台机器，准备生产 p1,p2 两种产两种产 品。若生产产品品。若生产产品 p1，每台机器每年可收入每台机器每年可收入45万万 元，损坏率为元，损坏率为65%；若生产产品；若生产产品 p2，每台机器每台机器 每年可收入每年可收入35万元，损坏率为万元，损坏率为35%；估计三年后；估计三年后 将有新将有新 的机器出现，旧的机器将全部淘汰。试的机器出现，旧的机器将全部淘汰。试 问每年应如何安排生产，使在三年内收入最多？问每年应如何安排生产，使在三年内收入最多？解：解：解：解：首先构造这个问题的动态规划模型。首先构造这个问题的动态规划模型。1.变量设置变量设置 (1)设阶段变量设阶段变量k表示年度，因此，阶段总数表示年度，因此，阶段总数n=3。(2)状态变量状态变量sk表示第表示第k年度初拥有的完好机床台数，年度初拥有的完好机床台数，同时也是第同时也是第 k1 年度末时的完好机床数量。年度末时的完好机床数量。(3)(3)决策变量决策变量uk，表示第表示第k年度中分配于年度中分配于生产产品生产产品 p1 的的机器台数。于是机器台数。于是sk uk便为该年度中分配于便为该年度中分配于生生 产产品产产品 p1的的机器台数机器台数2.状态转移方程为状态转移方程为 k=1，2，3,43允许决策集合允许决策集合,在第在第 k 段为段为4 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)=45s3k=2时有时有因此，当因此，当 u2*=0 时，有最大值时，有最大值 f2(s2)=64.25 s2k=1 时有时有当当取取u1*=0时时,f1(s1)有有最最大大值值，即即f1(s1)=76.7625s1,因为因为s1=100,故故 f1(s1)=7676.25 万元万元得最优决策为：得最优决策为：第一年将第一年将100台机器全部生产产品台机器全部生产产品p2，第二年把余下的机器继续生产产品第二年把余下的机器继续生产产品p2，第三年第三年把余下的机器全部生产产品把余下的机器全部生产产品p1。三年的总收入为三年的总收入为7676.25万元。万元。
