武汉科技大学本科历年运筹学试题.doc

2002级（A）参考答案1. 写出下述线性规划模型的标准型。 （10分） 解：令原问题标准化为： 2. 有线性规划模型： （10分） （1）用图解法求解； （2）用单纯形法求解； （3）指出每个单纯形表的可行域顶点。 解：（1）用图解法求解； X*=（1，1/2）T；Z*=35/2（2）用单纯形法求解； 原模型标准化为： 则求解过程为：Cj-10 -5 0 0bCBXBx1 x2 x3 x400x3x43 4 1 0 5* 2 0 198j-10 -5 0 000-10x3x10 14/5 1 -3/5 1 2/5 0 1/524/58/5j0 -1 0 216-5-10x2x10 1 5/14 -3/14 1 0 -1/7 2/73/21j0 0 5/14 25/1435/2T0T1T2 X*=（1，1/2）T；Z*=35/2（3）指出每个单纯形表的可行域顶点。 T0 表对应O点；T1 表对应B点；T2表对应A点，也是最优点。3. 求解： （10分） 解：原问题标准化为： 用对偶单纯形法求解为：Cj5 2 4 0 0bCBXBx1 x2 x3 x4 x500x4x5-3 -1 -2 1 0-6 -3* -5 0 1-4-10j5 2 4 0 0002x4x2-1* 0 -1/3 1 -1/32 1 5/3 0 -1/3-2/310/3j1 0 2/3 0 2/320/3-5-10x1x21 0 1/3 -1 1/30 1 1 2 -12/32j0 0 1/3 1 1/322/3 X*=（2/3，2，0）T；Z*=22/3（注：用大M法、两阶段法求解均可）4. 写出线性规划问题： 的对偶规划。 （10分）解：原问题的对偶规划为：5. 有一最小化指派问题的系数矩阵如下，试求其最优解。 （10分）解：用匈牙利算法求解为： 变换后：-5再变换为： 再变换： Z*=286. 写出函数的梯度和海赛矩阵，并判断其凹凸性。（10分）解：的梯度矩阵为：的海赛矩阵为：这里H矩阵的各阶主子式均大于0，所以为严格凸函数。7. 某厂有4台设备，拟分给3个用户（工厂）使用，各用户利用设备提供的盈利如下表。问如何分配设备才能使总盈利最大？试建立其动态规划求解模型（可不求解）。 （10分） 用户设备台数12301234046770256803578解：根据题意，原问题用动态规划求解模型为：（1） 按用户分为3阶段，K=（1，2，3，4），k=4为终了阶段；（2） xk：第k阶段初拥有待分配设备台数；x1=4，0x24，0x34，x4=0；（3） uk：第k阶段分配给第k用户的设备数，有：U1=0,1,2,3,4，U2=0,1,2,x2，U3=x3;（4） 状态转移方程：； （5） 阶段指标：见表，如： ；（6） 递推方程：（7） 边界条件：。v6v5v4v32,25,33,01,02,25,24,33,3v1v28. 证明下图所示v1至v6流为最大流。弧边数字为。 （10分）证明：对原流图用标号法找可扩充路有：v6v5v4v32,25,33,01,02,25,24,33,3v1v2(-，)(v1,3) 标号过程进行不下去，即不存在v1-v6的可扩充路，根据可扩充路定理，图示流即为最大流,maxQ=5。9.下图为求至的最小费用最大流时得到的某一流图，弧边数字为，试构造其费用有向图（流增量图）。 （10分）v1 4,4,1 v3 7,4,6 v58,5,4 3,0,2 2,0,3 5,5,2v2 v46,5,1解：由原流图可作出其费用有向图为： v1 -1 v3 6 v5 -6 -4 4 2 3 -2 -1 v2 1 v410. 某商行夏季订购一批西瓜，根据以往的经验，西瓜销售量可能为10000、15000、20000、25000kg。假定西瓜售价为0.35元/kg，商行支出成本为0.25元/kg。（1）建立益损矩阵； （3分）（2）分别用悲观法、乐观法、等可能法和后悔值法确定西瓜订购数量。 （7分）解: （1）原问题的益损矩阵为； i Sj10000 15000 20000 25000100001500020000250001000 1000 1000 1000-250 1500 1500 1500-1500 250 2000 2000-2750 -1000 750 2500 （2）悲观准则： 乐观准则： 等可能准则： 后悔值准则：后悔值矩阵为： 则 （答题毕）2002级（B） 参考答案1. 求解线性规划问题： 的最优解。 （15分）解：图解过程如下：4321432102. 写出下述线性规划的对偶规划。 （15分） ；无限制。解：对偶规划为 MaxZd=-7w1+14w2 +3w3s.t. w1 +6w2+28w3 5 2w1-3w2+17w3 -6-w1 +w2 -4w3 =7-w1-7w2-2w3 =4w1无限制，w2，w30。3. 某一求目标函数极小值的线性规划问题，用单纯形法求解时得到某一步的单纯形表如下。问a1、a2、a3、c、d各为何值以及变量x属哪一类性质变量时，（1）现有的解为唯一最优解； （2）现有解为最优，但最优解有无穷多个； （3）存在可行解，但目标函数无界； （4）此线性规划问题无可行解。 （15分）基变量x1 x2 x3 x4 x5bx3x4x5-1 3 1 0 0a1 4 0 1 0 a2 a3 0 0 141dcj-zj c 2 0 0 0解：（1）d0，c0， x3，x4，x5为非人工变量； （2） d0，c=0，a1，a2中至少一个大于零，x3，x4，x5为非人工变量； （3） d0，c0，a10，a20 ，x3，x4，x5均为非人工变量； （4） d0，c0，a10，a20 ，a3=0， x5为人工变量。4. 用黄金分割法求解单变量函数寻优问题时，每迭代一次，寻优区间缩小多少倍？若要将区间缩小至原区间的10%以下，则至少要多少次迭代？ （10分）解：用黄金分割法求解单变量函数寻优问题时，每迭代一次，寻优区间是原区间的0.618倍。经n次迭代后，区间长度为：sn=0.618ns0。若要将区间缩小至原区间的10%以下，即sn/s00.1，则迭代次数ln0.1/ln0.618=4.78。所以若要将区间缩小至原区间的10%以下，则至少要5次迭代。5. 某人外出旅行，需将五件物品装入包裹，但包裹总重量不超过13kg。物品重量及价值如表。问如何装这些物品使整个包裹价值最大？ （15分）（只建模，可不求解）物品重量（kg）价值（元）ABCDE7543194320.5 解：用动态规划求解时，其模型为：1. 按物品类别分为5阶段，K=（1,2,3,4,5,6），k=6为终了阶段；2. xk：k阶段的状态变量，即装第k项物品前剩余重量；有X1=13；X2=6,13；X3=1,3,6,8,13；X4=0,1,2,3,4,5,6,8,9,13；X5=0,1,2,3,4,5,6,7,8,9,10,134；X6=03. uk：k阶段的决策变量，即装第k类物品的数量；U1=0,1,x1/7；U2=0,1,2,x2/5；U3=0,1,2,x3/4；U4=0,1,x4/3；U5=0,1,2,x5/14. 状态转移方程：5. 阶段指标见表， ；6. 递推方程（逆推）：7. 边界条件：6. 证明下图所示s-t流为最大流。弧边数字为（） （15分）21, 2124, 2436, 027, 030，3054，3078，5712，1260，5445，3375，4533，042，3069，57 t s 证明：对原流图用标号法找增广链有 30，30 54，3024, 24 （+vs，12） 42，30 60，5427, 036, 0 （-，） s （+v4，12） t21, 21 75，45 69，57 33，0 45，33 （+vs，12） 78，57 （+v2，12）12，12标号过程进行不下去，即不存在s-t增广链，根据增广链定理，图示s-t流即为最大流。7. 已知某决策问题的收益矩阵D为： D= 分别用乐观法、悲观法、等可能法和后悔值法确定其最优决策。 （15分）解：乐观准则： 悲观准则： 等可能准则： 后悔值准则：后悔值矩阵为： 则 解题毕。2003级（A） 参考答案1. 某昼夜服务的公交线路每天各时间所需司机和乘务人员数如下表。设司机和乘务人员分别在各时间段一开始时上班，并连续工作8小时，问该公交线路怎样安排司机和乘务人员，既能满足工作需要，又使司机和乘务人员配备最少？试建立求解该问题的模型（可不求解）。 （10分）班次123456时间6:0010:0010:0014:0014:0018:0018:0022:0022:002:002:006:00所需人数607060502030解：设表示第班次开始上班的司机和乘务人员数（），则有： 2. 有线性规划模型： （1）用单纯形法求解； （10分）（2）写出其对偶问题； （5分）（3）求解对偶问题。 （5分）解：（1）用单纯形法求解： 原模型标准化为： 则求解过程为：Cj-3-2000bCBXBx1x2x3x4x50x3-1210040x432010120x51*-10013j-3-200000x30110170x405*01-33-3x11-10013j0-500390x3001-1/58/5*32/5-2x20101/5-3/53/5-3x11001/52/518/5j00010120x5005/8-1/814-2x2013/81/803-3x110-1/41/402j0001012 该问题有无穷多最优解 ；Z*=12（2）其对偶问题为： （3）用对偶单纯形法求解对偶问题有：Cj412300bCBYBy1y2y3y4y50y41-3-1*10-30y5-2-2101-2j41230000y3-131-1030y5-1-5*011-5j73030-90y3-8/501-2/53/50-2y21/510-1/5-1/51j32/50018/53/5-12 对偶问题最优解为 Y*=(0,1,0)T；W*=123. 线性规划的目标函数是，在用标准的单纯形法迭代过程中，得到下表，其中a，b是常数，部分数据有缺损。Cj -2-5-8000bCBXBx1x2x3x4x5x6x603020x2a1/2bx4-2-118j2（1）在所有的空格中填上适当的数（其中可含参数a、b）。 （5分）（2）判断在什么情况下此解为最优解？ （5分）解：（1）如下表Cj -2-5-8000bCBXBx1x2x3x4x5x60x600300120-5x2a1201/20b0x4-20-11108j-2+5a0205/20（2）当 时，表中解为最优解。4. 某房地产公司计划在一住宅小区建设5栋不同类型的楼房B1、B2、B3、B4、B5。由3家建筑公司A1、A2、A3进行投标，允许每家建筑公司可承建12栋楼，通过投标得出建筑公司Ai对新楼Bj的预算费用Cij如下表，求使总费用最少的分配方案。 （10分）B1B2B3B4B5A13871511A279101412A36913127解：设每家建筑公司承建2栋楼，虚设一栋楼B6，则有： 矩阵变换有： -1矩阵再变换有： 所以有： 或即：A1承建B1和B3楼；A2承建B2楼；A3承建B4和B5楼。总费用为38。5. 用最速下降法求 ，取初始点为。（迭代一次即可） （15分）解： 令 令 因此得 此时精度为：6. 某企业新来8名工人，拟分给3个作业班组，每个作业班组最多只分5名工人。各作业班组得到新工人后产量增加量如下表。问如何分配新工人才能使总产量增加最大？试建立其动态规划求解模型（可不求解）。 （10分） 增加人数作业班组012345第一班组第二班组第三班组0001610122514173016213217223317.522.5解：根据题意，原问题用动态规划求解模型为：（1）按作业班组分为3阶段，K=（1，2，3，4），k=4为终了阶段；（2）xk：第k阶段初拥有待分配新工人数；有：X1=8，X2=8,7,6,5,4,3，X3=5,4,3,2,1,0，X=0。（3）uk：第k阶段分配给第k作业班组的新工人数；有：U1=0,1,2,3,4,5，U2=0,1,2,x2( x25)；U2= x2-5,5( x25)，U3=x3。（4）状态转移方程：； （5）阶段指标：见表，如： ；（6）递推方程：（7）边界条件：。7. 写出求解网络最小费用最大流问题的算法步骤。 （15分）解：设分别表示（容量，流量，费用），最小费用最大流问题的算法步骤为：（1）给定初始可行流，迭代后得；（2）构造费用有向图（流增量图），设中弧得权为： ， 其中的弧可以去掉；（3）求中v1至vn的最小费用路（可扩充路）P；（4）在最小费用路（可扩充路）P上调整流量式中 （5）重复（2）（4）步，找不到v1至vn的最小费用路（可扩充路）P时，则得到最小费用最大流，迭代结束。8. 某农场需决定种植农作物的种类：A1、A2、A3 。种植不同作物的收益（元）主要取决于天气（见下表），要求：（1）用不确定型决策方法，决定种哪一种作物。 （5分）（2）如天气预报给出好天气的概率为0.3，中等天气的概率为0.4，坏天气的概率为0.3，用风险型决策方法决定种哪一种作物。 （5分） 自然状态策略收益好天气中等天气坏天气A1250001800010000A230000120008000A3200001600012000解：（1）用不确定型决策方法等可能准则： 乐观准则： 悲观准则： 后悔值准则：后悔值矩阵为： 则 （2）用风险型决策方法（最大期望收益）的决策树为：112000250001800010000300001200080002000016000好天气 0.3好天气 0.3好天气 0.3中等天气 0.4中等天气 0.4中等天气 0.4坏天气 0.3坏天气 0.3坏天气 0.3A1A2A316200177001600017700 ，（答题毕）2003级（B）参考答案1. 证明，若线性规划问题有两个不同的最优解，则它有无穷多最优解。 （10分）证明：设、是线性规划问题：的两个不同最优解，则有 ，从而，对有：，两式相加有：由此可知 是线性规划问题的可行解。而所以也是线性规划问题的最优解。故线性规划问题有无穷多最优解。2. 有甲、乙、丙三种类型的煤，每种煤的含硫量、发热量及价格如下表。现将三种煤混合使用，混合后要求每公斤煤的发热量不低于214.19103J，含硫量不超过0.025%，问如何混合才能使成本最低？试建立其数学模型。 （10分） 类 型含硫量（%）发热量（4.19103J/kg）价格（元/t）甲乙丙0.010.050.03202422201618.5解：设每吨混合煤分别使用甲、乙、丙三种煤吨，混合煤的成本为Z。 则有： 3. 某一极小化线性规划问题在单纯形法计算时得到下表，其中a，b，c，d，e，f是未知数，原问题中要求各变量均非负，问a，b，c，d，e，f应满足什么条件，有下面各解成立？ （10分）CBXBx1 x2 x3 x4 x5 x6 bx3x4x62 c 1 0 e 0-1 -5 0 1 -1 0a -3 0 0 -4 1f23j b d 0 0 3 0（1）是唯一最优解；（2）有无穷多最优解；（3）无界解；（4）是可行解但非最优解，只有x1可以进基且出基变量必为第3个变量。解：（1）当现行解为可行解，且对应的非基变量的检验数均大于0时，LP问题才有唯一最优解，即f0，b0，d0。x3，x4，x6非人工变量；a，c，e无限制。（2）当所有非基变量的检验数都大于等于0，且其中存在一个非基变量xj检验数等于0，而在xj的系数列向量中有大于0的分量时，有无穷多最优解。所以f0，b=0，d0或f0，b0，d=0，c0。x3，x4，x6非人工变量；a，e无限制。（3）当f0时现行解为基可行解，当b0，d0，c0时LP的目标函数无界，所以有f0，b0，d0，c0。x3，x4，x6非人工变量；a，e无限制。（4）因是可行解，所以有f0；非最优解且只有x1可以进基，所以有b0，d0；只有x6可以出基，所以有，故参数应满足：f0，b0，d0，。x3，x4，x6非人工变量；c，e无限制。4. 分别用图解法和单纯形法求解线性规划问题，并对照指出单纯形法的每步迭代相当于图解法中可行域的哪一个顶点。 （20分） 解：用图解法有：有；用表格单纯形法求解有：原模型标准化为： Cj-2-1000bCBXBx1x2x3x4x50x30110030x43*1010120x5110015j-2-100000x3011003-2 x111/301/304-1x502/3*0-1/311j0-1/302/30-80x30011/2-3/23/2-2x21001/2-1/27/2-1x1010-1/23/23/2j0001/21/2-17/2所以：；其中：表一对应图中O点；表二对应图中D点；表三对应图中C点。5. 写出求解整数规划（max型）的分枝定界法的基本方法步骤。 （10分）解：求解整数规划（max型）的分枝定界法的基本方法步骤有：（1）求解原问题的松弛问题，即不考虑整数约束的线性规划问题；（2）定界，一般令为松弛问题的目标函数值，为无穷大或明显的整数解的目标函数值；（3）分枝，选非整数解变量进行分枝，用两个线性规划问题同效表示一个线性规划问题；（4）求解并剪枝，求解分枝问题，对无解的问题或目标函数值小于的问题适时剪掉，不再进行分枝；（5）调整上、下界，将迄今为止最好的整数解对应的目标函数值作为，将迄今为止所有未被分枝的问题的目标函数值作为；（6）当所有分枝均已查明，有=时，即得到原问题的最优解，求解过程结束。6. 判断下述函数的凹凸性： （10分）解：因 ； 有： a11=0 ； A2=-40； A3=-80即函数的海赛矩阵为不定矩阵，故为非凸非凹函数。7. 写出建立动态规划求解模型的基本步骤。 （10分）解：建立动态规划求解模型的基本步骤为：（1）按问题内容划分阶段，K=（1，2，n），k=n为终了阶段；（2）确定状态变量xk和允许状态集合Xk；（3）确定决策变量uk和允许决策集合Uk；（4）写出状态转移方程：； （5）明确阶段指标； （6）确定递推方式和递推方程，如逆推方程为：（7）明确边界条件，如，或等。8. 根据市场预测，某企业其产品的需求量可能为100、150、200或250万t，产品生产成本为25元/t，而售价为35元/t。假设产品生产后不能外销其价值为零，要求：（1）写出该问题的益损值表； （10分）（2）分别用等可能准则、乐观准则、悲观准则、后悔值准则，确定企业最优生产数量。 （10分）解：（1）根据题意该问题的益损值表为： Sji1001502002501001502002501000-250-1500-275010001500250-10001000150020007501000150020002500 （2）等可能准则： 乐观准则： 悲观准则： 后悔值准则：后悔值矩阵为： 则 （答题毕）2004级（A）1 将线性规划问题 化为标准型。 （10分）解：原模型标准化为： 2 用图解法求解 （10分）解：用图解法有：（20/19,45/19）（2,0）3x1+5x2=15x2543210 1 2 3 4 5 x15x1+2x2=10该问题有无穷多最优解,联立 解得；联立 解得；所以 ；3 用单纯形法求解 （15分）解：原问题标准化为 用表格单纯形法求解有：Cj1-21000bCBXBx1x2x3x4x5x60x411-2100100x52-1401080x6-12-40014j1-2100000x43/20010-1/280x53/202011/210-2x2-1/21-2001/22j00-3001-40x43/20010-1/281x33/40101/21/45-2x211001112j9/40003/27/4-19所以有：X*=(x1,x2,x3,x4,x5,x6)T=(0,12,5,8,0,0)T；Z*=-19还原为原问题有：X*=(0,12,5,8)T；Z*=194 用对偶单纯形法求解线性规划问题： （15分）解：用对偶单纯形法求解有：Cj1100bCBXBx1x2x3x40x3-2-110-40x4-1-7*01-7j110000x3-13/7*01-1/7-31x21/710-1/71j6/7001/711x110-7/131/1321/131x2011/13-2/1310/13j006/131/1331/13 规划问题最优解为 X*=(21/13，10/13)T；Z*=31/135 用隐枚举法求解下列0-1规划问题s.t. 。 （10分）解：将原问题变量重新排列有：s.t. 。枚举过程如下表：序号X=(x2,x4,x3,x1)T阀值约束1约束2约束3目标函数0(0,0,0,0)T1(0,0,0,1)T2(0,0,1,0)T3(0,0,1,1)T4(0,1,0,0)T445(0,1,0,1)T6(0,1,1,0)T7(0,1,1,1)T8(1,0,0,0)T9(1,0,0,1)T10(1,0,1,0)T11(1,0,1,1)T12(1,1,0,0)T13(1,1,0,1)T14(1,1,1,0)T15(1,1,1,1)T所以：X*=(x2,x4,x3,x1)T=(0,1,0,0)T Z*=4还原有：X*=(x1,x2,x3,x4)T=(0,0,0,1)T Z*=46 用黄金分割法求解：的极小点。只要求迭代一步。 （10分）解：（1） 因 所以舍去区间（6.18，107 试建立求解问题： s.t. 均是非负整数。的动态规划模型（不必求解）。 （10分）解：原问题可改写为：s.t. 均是非负整数。用动态规划求解时，其模型为：（1）按变量分为3阶段，K=（1，2，3，4），k=4为终了阶段；（2）xk：各阶段得状态变量为：x1，x2，x3 ，设：x3 =u3 ，x2=x3+u2， x1=x2+u1=3即u3= x3，0u2x2 ，0u1x1=3有X3=0，1，2，3，X2=0，1，2，3，X1=3（3）uk：U3=x3，U2=0，1，2，x2，U1=0，1，2，3（4）状态转移方程：x2=x1-u1=3-u1 ，x3=x2-u2（5）阶段指标：，（6）递推方程：（7）边界条件：8 在图中用双标号法求从v1到其它顶点的最短路和最短距离，并指出对v1来说，哪些顶点是不可达的。弧边数字是该弧的长度。 （10分）1267634433v8v7v6v5v4v3v14v21解：标号过程如下：(7,v5)(4,v1)(3,v1)(1,v1)(0,v1)16176344323v8v7v6v5v4v3v14v2(10,v6)从v1到其它顶点的最短路和最短距离分别为：v1v2 最短路 v1v2 最短距离 4；v1v3 无最短路；v1v4 无最短路；v1v5 最短路 v1v5 最短距离 1；v1v6 最短路 v1v5v6 最短距离 7；v1v7 最短路 v1v7 最短距离 3；v1v8 最短路 v1v5v6v8 最短距离 10。对v1来说，顶点v3、v4是不可达的。9 某工厂要制定下年度产品的生产批量计划，根据市场调查和市场预测的结果，得到产品市场销路好、中、差三种自然状态的概率分别为0.3、0.5、0.2，工厂采用大批、中批、小批生产可能得到收益值也可以计算出来，见下表。现在要求通过决策分析，合理地确定生产批量，使企业获得的收益最大。 （10分） 自然状态sj方案di收益销路好s1销路中s2销路差s3p(s1)=0.3p(s2)=0.5p(s3)=0.2大批生产 d120