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

.z.2002级〔A〕参考答案写出下述线性规划模型的标准型。〔10分〕解：令原问题标准化为：2.有线性规划模型：〔10分〕〔1〕用图解法求解；〔2〕用单纯形法求解；〔3〕指出每个单纯形表的可行域顶点。解：〔1〕用图解法求解；∴X*=〔1，1/2〕T；Z*=35/2〔2〕用单纯形法求解；原模型标准化为：那么求解过程为：Cj-10-500bCBXBx1x2x3x400x3x434105*20198σj-10-50000-10x3x1014/51-3/512/501/524/58/5σj0-10216-5-10x2x1015/14-3/1410-1/72/73/21σj005/1425/1435/2T0T1T2∴X*=〔1，1/2〕T；Z*=35/2〔3〕指出每个单纯形表的可行域顶点。T0表对应O点；T1表对应B点；T2表对应A点，也是最优点。3.求解：〔10分〕解：原问题标准化为：用对偶单纯形法求解为：Cj52400bCBXBx1x2x3x4x500x4x5-3-1-210-6-3*-501-4-10σj52400002x4x2-1*0-1/31-1/3215/30-1/3-2/310/3σj102/302/320/3-5-10x1x2101/3-11/30112-12/32σj001/311/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解：根据题意，原问题用动态规划求解模型为：按用户分为3阶段，K=〔1，2，3，4〕，k=4为终了阶段；xk：第k阶段初拥有待分配设备台数；x1=4，0≤x2≤4，0≤x3≤4，x4=0；uk：第k阶段分配给第k用户的设备数，有：U1={0,1,2,3,4}，U2={0,1,2,…,x2}，U3={x3};状态转移方程：；阶段指标：见表，如：；；递推方程：边界条件：。v6v5v4v3v6v5v4v32,25,33,01,02,25,24,33,3v1v2证明：对原流图用标号法找可扩大路有：vv6v5v4v32,25,33,01,02,25,24,33,3v1v2(-，(-，∞)(v(v1,3)标号过程进展不下去，即不存在v1-v6的可扩大路，根据可扩大路定理，图示流即为最大流,maxQ=5。9.以下图为求至的最小费用最大流时得到的某一流图，弧边数字为，试构造其费用有向图〔流增量图〕。〔10分〕v14,4,1v37,4,6v58,5,43,0,22,0,35,5,2v2v46,5,1解：由原流图可作出其费用有向图为：v1-v3v5-6-4423-2-1v2v410.某商行夏季订购一批西瓜，根据以往的经历，西瓜销售量可能为10000、15000、20000、25000kg。假瓜售价为0.35元/kg，商行支出本钱为0.25元/kg。〔1〕建立益损矩阵；〔3分〕〔2〕。〔7分〕解:〔1〕原问题的益损矩阵为；αiSj10000150002000025000100001500020000250001000100010001000-250150015001500-150025020002000-2750-10007502500〔2〕悲观准那么：∴乐观准那么：∴等可能准那么：∴懊悔值准那么：懊悔值矩阵为：那么∴〔答题毕〕2002级〔B〕参考答案1.求解线性规划问题：的最优解。〔15分〕解：图解过程如下：44321432102.写出下述线性规划的对偶规划。〔15分〕；无限制。解：对偶规划为MaxZd=-7w1+14w2+3w3s.t.w1+6w2+28w3≤52w1-3w2+17w3≤-6-w1+w2-4w3=7-w1-7w2-2w3=4w1无限制，w2，w3≥0。3.某一求目标函数极小值的线性规划问题，用单纯形法求解时得到某一步的单纯形表如下。问a1、a2、a3、c、d各为何值以及变量x属哪一类性质变量时，〔1〕现有的解为唯一最优解；〔2〕现有解为最优，但最优解有无穷多个；〔3〕存在可行解，但目标函数无界；〔4〕此线性规划问题无可行解。〔15分〕基变量x1x2x3x4x5bx3x4x5-13100a14010a2a300141dcj-zjc2000解：〔1〕d≥0，c＞0，x3，x4，x5为非人工变量；〔2〕d≥0，c=0，a1，a2中至少一个大于零，x3，x4，x5为非人工变量；〔3〕d≥0，c＜0，a1≤0，a2≤0，x3，x4，x5均为非人工变量；〔4〕d＞0，c＞0，a1＞0，a2≤0，a3=0，x5为人工变量。4.用黄金分割法求解单变量函数寻优问题时，每迭代一次，寻优区间缩小多少倍？假设要将区间缩小至原区间的10%以下，那么至少要多少次迭代？〔10分〕解：用黄金分割法求解单变量函数寻优问题时，每迭代一次，寻优区间是原区间的0.618倍。经n次迭代后，区间长度为：sn=0.618ns0。假设要将区间缩小至原区间的10%以下，即sn/s0≤0.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={0}3.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/1]}4.状态转移方程：5.阶段指标见表，；6.递推方程〔逆推〕：7.边界条件：6.证明以下图所示s-t流为最大流。弧边数字为〔〕〔15分〕21,2121,2124,2436,027,030，3054，3078，5712，1260，5445，3375，4533，042，3069，57①③②⑥④⑦⑤ts证明：对原流图用标号法找增广链有30，3054，3024,24〔+vs，12〕①③⑤24,2442，3060，5427,036,027,036,0〔-，∞〕s〔+v4，12〕⑥t21,2175，4521,2169，57 33，045，33〔+vs，12〕②④⑦78，57〔+v2，12〕12，12标号过程进展不下去，即不存在s-t增广链，根据增广链定理，图示s-t流即为最大流。7.某决策问题的收益矩阵D为：D=分别用乐观法、悲观法、等可能法和懊悔值法确定其最优决策。〔15分〕解：乐观准那么：∴悲观准那么：∴等可能准那么：∴懊悔值准那么：懊悔值矩阵为：那么∴解题毕。2003级〔A〕参考答案1.某昼夜效劳的公交线路每天各时间所需司机和乘务人员数如下表。设司机和乘务人员分别在各时间段一开场时上班，并连续工作8小时，问该公交线路怎样安排司机和乘务人员，既能满足工作需要，又使司机和乘务人员配备最少？试建立求解该问题的模型〔可不求解〕。〔10分〕班次123456时间所需人数607060502030解：设表示第班次开场上班的司机和乘务人员数〔〕，那么有：2.有线性规划模型：〔1〕用单纯形法求解；〔10分〕〔2〕写出其对偶问题；〔5分〕〔3〕求解对偶问题。〔5分〕解：〔1〕用单纯形法求解：原模型标准化为：那么求解过程为：Cj-3-2000bCBXBx1x2x3x4x50x3-1210040x432010120x51*-10013σj-3-200000x30110170x405*01-33-3x11-10013σj0-500390x3001-1/58/5*32/5-2x20101/5-3/53/5-3x11001/52/518/5σj00010120x5005/8-1/814-2x2013/81/803-3x110-1/41/402σj0001012∴该问题有无穷多最优解；Z*=12〔2〕其对偶问题为：〔3〕用对偶单纯形法求解对偶问题有：Cj412300bCBYBy1y2y3y4y50y41-3-1*10-30y5-2-2101-2σj41230000y3-131-1030y5-1-5*011-5σj73030-90y3-8/501-2/53/50-2y21/510-1/5-1/51σj32/50018/53/5-12∴对偶问题最优解为Y*=(0,1,0)T；W*=123.线性规划的目标函数是，在用标准的单纯形法迭代过程中，得到下表，其中a，b是常数，局部数据有缺损。Cj-2-5-8000bCBXBx1x2x3x4x5x6x603020x2a1/2bx4-2-118σj2〔1〕在所有的空格中填上适当的数〔其中可含参数a、b〕。〔5分〕〔2〕判断在什么情况下此解为最优解？〔5分〕解：〔1〕如下表Cj-2-5-8000bCBXBx1x2x3x4x5x60x600300120-5x2a1201/20b0x4-20-11108σj-2+5a0205/20〔2〕当时，表中解为最优解。4.某房地产公司方案在一住宅小区建立5栋不同类型的楼房B1、B2、B3、B4、B5。由3家建筑公司A1、A2、A3进展投标，允许每家建筑公司可承建1~2栋楼，通过投标得出建筑公司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}(x2>5)，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〕用风险型决策方法〔最大期望收益〕的决策树为：eq\o\ac(○,2)1eq\o\ac(○,4)eq\o\ac(○,3)△12000△25000△18000△10000△30000△12000△8000△20000△16000好天气0.3好天气0.3好天气0.3中等天气0.4中等天气0.4中等天气0.4坏天气0.3坏天气0.3坏天气0.3A1A2A316200177001600017700∴，〔答题毕〕2003级〔B〕参考答案1.证明，假设线性规划问题有两个不同的最优解，那么它有无穷多最优解。〔10分〕证明：设、是线性规划问题：的两个不同最优解，那么有，从而，对有：，两式相加有：由此可知是线性规划问题的可行解。而所以也是线性规划问题的最优解。故线性规划问题有无穷多最优解。2.有甲、乙、丙三种类型的煤，每种煤的含硫量、发热量及价格如下表。现将三种煤混合使用，混合后要求每公斤煤的发热量不低于21×4.19×103J，含硫量不超过0.025%，问如何混合才能使本钱最低？试建立其数学模型。〔10分〕类型含硫量〔%〕发热量〔4.19×103J/kg〕价格〔元/t〕甲乙丙0.010.050.03202422201618.5解：设每吨混合煤分别使用甲、乙、丙三种煤吨，混合煤的本钱为Z。那么有：3.某一极小化线性规划问题在单纯形法计算时得到下表，其中a，b，c，d，e，f是未知数，原问题中要求各变量均非负，问a，b，c，d，e，f应满足什么条件，有下面各解成立？〔10分〕CBXBx1x2x3x4x5x6bx3x4x62c10e0-1-501-10a-300-41f23σjbd0030〔1〕是唯一最优解；〔2〕有无穷多最优解；〔3〕无界解；〔4〕是可行解但非最优解，只有x1可以进基且出基变量必为第3个变量。解：〔1〕当现行解为可行解，且对应的非基变量的检验数均大于0时，LP问题才有唯一最优解，即f≥0，b＞0，d＞0。x3，x4，x6非人工变量；a，c，e无限制。〔2〕当所有非基变量的检验数都大于等于0，且其中存在一个非基变量xj检验数等于0，而在xj的系数列向量中有大于0的分量时，有无穷多最优解。所以f≥0，b=0，d≥0或f≥0，b≥0，d=0，c＞0。x3，x4，x6非人工变量；a，e无限制。〔3〕当f≥0时现行解为基可行解，当b＞0，d＜0，c＜0时LP的目标函数无界，所以有f≥0，b＞0，d＜0，c＜0。x3，x4，x6非人工变量；a，e无限制。〔4〕因是可行解，所以有f≥0；非最优解且只有x1可以进基，所以有b＜0，d≥0；只有x6可以出基，所以有，故参数应满足：f≥0，b＜0，d≥0，。x3，x4，x6非人工变量；c，e无限制。4.分别用图解法和单纯形法求解线性规划问题，并对照指出单纯形法的每步迭代相当于图解法中可行域的哪一个顶点。〔20分〕解：用图解法有：有；用表格单纯形法求解有：原模型标准化为：Cj-2-1000bCBXBx1x2x3x4x50x30110030x43*1010120x5110015σj-2-100000x3011003-2x111/301/304-1x502/3*0-1/311σj0-1/302/30-80x30011/2-3/23/2-2x21001/2-1/27/2-1x1010-1/23/23/2σj0001/21/2-17/2所以：；其中：表一对应图中O点；表二对应图中D点；表三对应图中C点。5.写出求解整数规划〔max型〕的分枝定界法的根本方法步骤。〔10分〕解：求解整数规划〔max型〕的分枝定界法的根本方法步骤有：〔1〕求解原问题的松弛问题，即不考虑整数约束的线性规划问题；〔2〕定界，一般令为松弛问题的目标函数值，为无穷大或明显的整数解的目标函数值；〔3〕分枝，选非整数解变量进展分枝，用两个线性规划问题同效表示一个线性规划问题；〔4〕求解并剪枝，求解分枝问题，对无解的问题或目标函数值小于的问题适时剪掉，不再进展分枝；〔5〕调整上、下界，将迄今为止最好的整数解对应的目标函数值作为，将迄今为止所有未被分枝的问题的目标函数值作为；〔6〕当所有分枝均已查明，有=时，即得到原问题的最优解，，求解过程完毕。6.判断下述函数的凹凸性：〔10分〕解：因；有：a11=0；A2==-4﹤0；A3==-8﹤0即函数的海赛矩阵为不定矩阵，故为非凸非凹函数。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〕根据题意该问题的益损值表为：Sjαi1001502002501001502002501000-250-1500-275010001500250-10001000150020007501000150020002500〔2〕等可能准那么：乐观准那么：悲观准那么：懊悔值准那么：懊悔值矩阵为：那么〔答题毕〕2004级〔A〕1将线性规划问题化为标准型。〔10分〕解：原模型标准化为：2用图解法求解〔10分〕解：用图解法有：〔20/19,45/19〕〔20/19,45/19〕〔2,0〕3x1+5x2=15x254321012345x15x1+2x2=10该问题有无穷多最优解,联立解得；联立解得；所以；3用单纯形法求解〔15分〕解：原问题标准化为用表格单纯形法求解有：Cj1-21000bCBXBx1x2x3x4x5x60x411-2100100x52-1401080x6-1[2]-40014σj1-2100000x43/20010-1/280x53/20[2]011/210-2x2-1/21-2001/22σj00-3001-40x43/20010-1/281x33/40101/21/45-2x211001112σj9/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-7σj110000x3-13/7*01-1/7-31x21/710-1/71σj6/7001/711x110-7/131/1321/131x2011/13-2/1310/13σj006/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)T√×1(0,0,0,1)T×2(0,0,1,0)T√×3(0,0,1,1)T×4(0,1,0,0)T4√√√45(0,1,0,1)T×6(0,1,1,0)T×7(0,1,1,1)T×8(1,0,0,0)T×9(1,0,0,1)T×10(1,0,1,0)T×11(1,0,1,1)T×12(1,1,0,0)T×13(1,1,0,1)T×14(1,1,1,0)T×15(1,1,1,1)T×所以：X*=(x2,x4,x3,x1)T=(0,1,0,0)TZ*=4复原有：X*=(x1,x2,x3,x4)T=(0,0,0,1)TZ*=46用黄金分割法求解：的极小点。只要求迭代一步。〔10分〕解：〔1〕因所以舍去区间〔6.18，10]7试建立求解问题：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，0≤u2≤x2，0≤u1≤x1=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分〕11267634433v8v7v6v5v4v3v14v21解：标号过程如下：(7,(7,v5)(4,v1)(3,v1)(1,v1)(0,v1)16176344323v8v7v6v5v4v3v14v2(10,v6)从v1到其它顶点的最短路和最短距离分别为：v1→v2最短路v1→v2最短距离4；v1→v3无最短路；v1→v4无最短路；v1→v5最短路v1→v5最短距离1；v1→v6最短路v1→v5→v6最短距离7；v1→v7最短路v1→v7最短距离3；v1→v8最短路v1→v5→v6→v8最短距离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大批生产d120128中批生产d2161610小批生产d3121212解：〔1〕最大可能准那么由表可以看出，自然状态s2的概率p(s2)=0.5最大，因此产品的市场销路中(s2)的可能性也就最大。于是就考虑按照这种市场销路决策，通过比拟可知，企业采取中批生产收益最大，所以d2是最优决策方案。∴〔2〕最大期望值准那么自然状态sj方案di收益E(di)销路好s1销路中s2销路差s3p(s1)=0.3p(s2)=0.5p(s3)=0.2大批生产d12012813.6中批生产d216161014.8小批生产d312121212.0∴〔3〕决策树法决策树如下图：决策决策△12△20△12△8△16△16△10△12△12销路好0.3销路中0.5销路差0.2大批量生产14.813.612.014.8d1d2d3销路好0.3销路好0.3销路中0.5销路中0.5销路差0.2销路差0.2中批量生产小批量生产∴2004级〔B〕1用图解法求解〔10分〕解：用图解法有：〔10,0〕〔10,0〕x1+x2=1x2=4x1+2x2=10x254321012345678910x1联立解得；2用表格单纯形法求解〔15分〕解：原问题标准化为:用单纯形表格迭代有：Cj-2.5-100bCBXBx1x2x3x40x33510150x4[5]20110σj-2.5-10000x30[19/5]13/59-2.5x112/501/52σj0001/2-5-1x2015/193/1945/19-2.5x110-2/1913/9520/19σj0001/2-5所以；3写出线性规划问题：的对偶规划。〔10分〕解：原问题的对偶规划为：或4用大M法求解：为自由变量。〔15分〕解：原问题标准化为：为自由变量。用表格迭代有Cj-5-3-6600MbCBXBx1x2x3x4x5x6x70x5121-1100180x621[3]-301016Mx7111-100110σj-5-M-3-M-6-M6+M00010M0x51/35/3001-1/3038/3-6x32/31/31-101/3016/3Mx71/3[2/3]000-1/3114/3σj-1-M/3-1-2M/30002+M/30-32+14M/30x5-1/200011/2-5/21-6x3[1/2]01-101/2-1/23-3x21/21000-1/23/27σj-1/200003/2-390x5001-1114-5x1102-2016-3x201-1[1]0-14σj001-102-420x50100108-5x112000-1146x401-110-14σj010001-46所以有：X*=(x1,x2,x3,x4,x5,x6,x7)T=(14,0,0,4,8,0,0)T；Z′*=-46复原为原问题有：X*=(14,0,-4)T；Z*=465求解整数规划问题：s.t.且为整数。〔10分〕解：原问题用图解法求解过程为：00426486x18x22∴X*=(0,5)T；Z*=406判断函数：的凹凸性。〔10分〕解：的海赛矩阵为：==，当时，所以为凸函数。7有100台机器分四期使用，每期有两种任务：任务一高负荷工作，报废率1/3，收益10；任务二低负荷工作，报废率1/10，收益7。试建立其动态规划模型〔不必求解〕。〔10分〕解：(1)按机器使用周期分为5个阶段，第5阶段为完毕阶段，即K={1，2，3，4，5}；(2)选xk为k阶段初完好的机器数，有：x1=1000≤x2≤1000≤x3≤1000≤x4≤100(3)选uk为k阶段投入高负荷工作的机器数，那么投入低负荷工作的机器数为xk-uk，有：0≤u1≤x10≤u2≤x20≤u3≤x30≤u4≤x4(4)状态转移方程：(5)阶段指标函数：(6)递推方程：(7)边界条件：8以下图为求vs至vt的最小费用最大流时得到的某一流图，弧边数字为，试构造其费用有向图。〔10分〕4,4,64,4,63,3,83,3,33,2,72,0,33,0,62,1,32,2,32,2,22,0,34,2,44,4,24,4,24,4,2vtv6v5v4v3v2vsv1解：由原流图可作出其费用有向图为：-4-4-7-3-6-8-37363-3-234-2-2-2vtv6v5v4v3v2vsv19某企业拟利用剩余生产能力开发新产品。现有四种品种可供选择，市场销路有好、中、差三种情况，销售状态概率及每一品种在不同状态下的收益见下表，试用最大可能法、最大期望收益法和决策树法进展方案选择。〔10分〕销路品种收益(万元)销路好销路中销路差p(θ1)=0.3p(θ2)=0.5p(θ3)=0.2A1141412A2221410A3181610A420128解：〔1〕最大可能准那么由表可以看出，销路中的概率p=0.5最大，因此产品的市场销路中的可能性也就最大。因max(14,14,16,12)=16∴〔2〕最大期望值准那么因max(E(A1),E(A2),E(A3),E(A4))=max(13.6,15.6,15.4,13.6)=15.6∴〔3〕决策树法决策树如下图：决策决策品种A115.6△14△14△12销路好0.3销路中0.5销路差0.213.6A1△22△14△1015.6A2销路好0.3销路中0.5销路差0.2△18△16△1015.4A3销路好0.3销路中0.5销路差0.2△20△12△813.6A4销路好0.3销路中0.5销路差0.2品种A2品种A3品种A4∴2005级〔A〕1用图解法求解以下线性规划问题，并指出问题具有惟一最优解、无穷多最优解、无界解还是无可行解。〔10分〕解：图解过程见以下图012012x1x221有：该问题有无穷多最优解。2将以下线性规划问题化为标准形式，并列出初始单纯形表。〔10分〕解：原问题标准化为：其初始单纯形表为：Cj-3-11-20000Xjx1x/2x//2x/3x4x5x6x7000x4x6x7128524331-1-3-114-2-31000-10010001cj-zj-3-11-200003某线性规划问题用单纯形法迭代时得到中间某两步的单纯形表如表所示，试将表中空白处数字填上。〔10分〕354000x1x2x3x4x5x6500x2x5x68/314/329/32/3-4/35/31000541/3-2/3-2/3010001cj-zj-1/304-5/300┇┇543x2x3x150/4162/4189/4100110001015/41-6/41-2/418/415/41-12/41-10/414/4115/41cj-zj000-45/41-24/41-11/414线性规划问题：试应用对偶理论证明上述线性规划问题最优解为无界。〔10分〕解：原问题的对偶问题为：由约束条件可知，其对偶问题无解；又因是原问题的可行解。由对偶定理可知原线性规划问题最优解为无界。5东兴煤炭公司下属桔祥、平安、双福三个煤矿，年生产能力分别为120、160、100万t。公司同3个城市签订了下年度的供货合同：城市1-110万t，城市2-150万t，城市3-70万t，但城市3表示愿购置剩余的全部煤炭。另有城市4虽未签订合同，但也表示只要公司有剩余煤炭，愿全部收购。从各矿至4个城市的煤炭单位运价见表。将此问题归结为运输问题，列出相应的产销平衡表与单位运价表。〔10分〕单位运价表单位：元/t城市煤矿1234桔祥平安双福856724513235解：该问题的运输问题产销平衡表与单位运价表为城市煤矿1233/4/产量桔祥平安双福虚设矿山856M724M513M5130235012016010050销量1101507050506以下五名运发动各种姿势的游泳成绩(各为50m，单位：s)如表所示。试问如何从中选拔一个4×50m混合泳的接力队，使预期的比赛成绩为最好。〔10分〕钱王周仰泳蛙泳蝶泳自由泳37.743.433.329.232.933.128.526.438.842.238.929.637.034.730.428.535.441.833.631.1解：原问题用匈牙利算法求解为：变换后：再变换为：再变换：再变换为：∴Z*=127.87分别用破圈法和避圈法求以下图的最小局部树。〔10分〕22222222233335514解：用破圈法求最小局部树为：W〔Tmin〕=18注意有多重解22222222233335514用避圈法求最小局部树为：W〔Tmin〕=18222222222333355148用标号法求以下图中v1至各点的最短路。〔10分〕vv1v6v5v7v3v2198v42857410373解：标号过程如下图：vv1v6v5v7v3v2198v42857410373〔0,v1〕〔14,v4〕〔13,v5〕〔11,v2〕〔10,v2〕〔9,v1〕〔8,v1〕由图可得：v1→v2L=9v1→v3L=8v1→v2→v4L=11v1→v2→v5L=10v1→v2→v4→v6L=14v1→v2→v5→v7L=139现有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}(x2>5)，U3={x3}。〔4〕状态转移方程：；〔5〕阶段指标：见表，如：；；〔6〕递推方程：〔7〕边界条件：。10某书店希望订购最新出版的图书出售。根据以往经历，新书的销售量可能为50、100、150或200本。假定每本书的订购价为4元，销售价为6元，剩书处理价为每本2元。分别依据悲观主义、乐观主义、等可能性、最小时机损失决策准那么决定该书店应订购新书的数量。〔10分〕解：〔1〕根据题意该问题的益损值表为：Sjαi50100150200501001502001000-100-2001002001000100200300200100200300400〔2〕悲观准那么：∴乐观准那么：∴等可能准那么：∴最小时机损失准那么：损失矩阵为：那么∴答题毕2005级〔B〕1用图解法求解以下线性规划问题，并指出问题具有惟一最优解、无穷多最优解、无界解还是无可行解。〔10分〕解：图解过程见以下图0123401234x1x2321由图可见，该问题具有无界解。2将以下线性规划问题化为标准形式，并列出初始单纯形表。〔10分〕解：原问题标准化为：其初始单纯形表为：Cj-3-5-110000Xjx1x2x/3x//3x4x5x6x7000x5x6x761610121211135-1-3-5-100100010001cj-zj-3-5-1100003写出以下线性规划问题的对偶问题。〔10分〕解：原问题的对偶规划为：4用对偶单纯形法求解以下线性规划问题。〔10分〕解：用对偶单纯形法求解有：Cj-5-2-400bCBXBx1x2x3x4x50x4-3-1-210-40x5-6-3*-501-10σj-5-2-4000x4-1*0-1/31-1/3-2/32x2215/30-1/310/3σj-10-2/30-2/320/35x1101/3-11/32/32x20112-12σj00-1/3-1-1/322/3∴规划问题最优解为X*=(2/3，2，0)T；Z*=22/35运输问题的产销平衡表与单位运价表如表所示，试用Vogel法求出其近似最优解。〔10分〕销地产地B1B2B3B4产量A1A2A3A491081081091012121111131412121824612销量614355解：该问题用Vogel法求其近似最优解为：销地414414224475B1B2B3B4产量A1A2A3A49108108109101212111113141212182461210103231-231-211销量61435511001-002-00--006求解整数规划问题：〔10分〕解：用图解法有：00426486x18x22●●●∴X*=(5，0)T或X*=(4，1)T或X*=(3，2)T；Z*=57用单纯形求解下述目标规划问题：〔10分〕解：用单纯形法求解有000P2P30P4P11.5P4P1基x1x2d1-d1+d2-d2+d3-d3+d4-d4+0P3P41.5P4d1-d2-d3-d4-40100301511[1]011011000-100001000-100001000-100001000-1P10000000101P20001000000P3-1-100010000P4-1-1.500000101.50P301.5P4d1-d2-x1-d4-107030150010[1]1011000-100001000-100-1-11011-100001000-1P10000000101P20001000000P30-100011100P40-1.500001001.50P301.5P4x2d2-x1-d4-1060305001010001-10-1-110[1]01000-100-101110-1-10001000-1P10000000101P20001000000P3001-1011100P4001.5-1.500-0.51.501.50P30P2x2d2-x1-d1+155530500101000000-1000101000-1000-11[1]01-1-11-101-110-1P10000000101P2001000-11-11P30000011-11-1P4000000101.500P30P4x2d2-x1-d3-1560255001010000-11-101-1101000-1000001000-110-11-101-1P10000000101P20001000000P3001-1010000P4001-100010.51∴X*=(25，15)T8用Ford-Fulkerson的标号算法求以下图中所示各容量网络中从vs到vt的最大流。图中各弧旁数字为容量cij，括弧中为流量fij。〔10分〕vvsv5v4v3v2v1vt3(3)3(2)5(5)6(4)3(3)2(0)4(4)2(2)5(4)2(0)6(6)8(6)解：用Ford-Fulkerson方法求解。〔1〕根据初始流，那么寻找可扩大路〔增广链〕的标号过程如下：vvsv5v4v3v2v1vt3(3)3(2)5(5)6(4)3(3)2(0)4(4)2(2)5(4)2(0)6(6)8(6)〔-，∞〕〔+vs，2〕〔-v5，1〕〔+v2，1〕〔-v3，1〕〔+v1，1〕〔+v4，1〕〔2〕调整流量，继续标号有：vvsv5v4v3v2v1vt3(2)3(3)5(5)6(5)3(3)2(0)4(4)2(1)5(5)2(0)6(6)8(7)〔+vs，1〕〔-，∞〕〔3〕由图所示，标号过程进展不下去，即不存在vs-vt的可扩大路〔增广链〕，根据可扩大路〔增广链〕定理，图示流即为最大流，maxQ=13。9某项工程有三个设计方案。据现有条件，这些方案不能按期完成的概率分别为0.40，0.60，0.80，即三个方案均完不成的概率为0.40×0.60×0.80=0.192。为使这三个方案中至少完成一个的概率尽可能大，决定追加2万元投资，当使用追加投资后，上述方案完不成的概率见下表。问应如何分配追加投资，使其中至少有一个方案完成的概率为最大。〔只建模型〕〔10分〕追加投资〔万元〕各方案完不成的概率1230120.400.200.150.600.400.200.800.500.30解：(1)阶段：每个设计方案为一阶段，K={1,2,3,4}，k=4为完毕阶段。(2)状态变量sk：k阶段初待分派的资金；S1={2}、S2={0,1,2}、S3={0,1,2}。(3)决策变量xk：k阶段分派给k设计方案的资金；D1(s1)={0,1,2}、D2(s2)={0,1,2}、D3(s3)={s3}。(4)状态转移方程：sk+1=sk-xk(5)阶段指标函数：vk(sk,xk)见表所示。(6)递推方程：(采用逆推法)(7)边界条件：10有一块海上油田进展勘探和开采的招标。根据地震资料的分析，找到大油田的概率为0.3，开采期可赚取20亿元；找到中油田的概率为0.4，开采期可赚取10亿元；找到小油田的概率为0.2，开采期可赚取3亿元；油田无工业开采价值的概率为0.1，按招标规定，开采前的勘探等费用均由中标者负担，预期需1.2亿元，以后不管油田规模多大，开采期赚取的利润中标者分成30%。有A、B、C三家公司，其效用函数分别为：A公司U(M)=(M+1.2)0.9-2B公司U(M)=(M+1.2)0.8-2C公司U(M)=(M+1.2)0.6-2试根据效用值，并用期望值法确定每家公司对投标的态度。〔10分〕解：决策树见以下图：4.84.80-1.2-0.31.80.10.20.40.3中油田小油田无开采价值大油田不投标或未中标投标并中标计算效用期望值见下表。大油田中油田小油田无开采价值EMV0.30.40.20.1A公司3.01580.6872-1.0905-20.7615B公司2.19300.4089-1.0802-20.4054C公司0.9302-0.0668-1.0613-2-0.1560结论为A公司和B公司愿参加投标，C公司不参加投标。答题毕2006级〔A〕1用图解法求解以下线性规划问题。〔10分〕解：图解过程见以下图0510152005101520x1x22015105由得有：。该问题具有唯一最优解。2.求解：〔10分〕解：原问题标准化为：用对偶单纯形法求解为：Cj52400bCBXBx1x2x3x4x500x4x5-3-1-210-6-3*-501-4-10σj52400002x4x2-1*0-1/31-1/3215/30-1/3-2/310/3σj102/302/320/3-5-10x1x2101/3-11/30112-12/32σj001/311/322/3∴X*=〔2/3，2，0〕T；Z*=22/3〔注：用大M法、两阶段法求解均可〕3线性规划问题如下，原问题最优解为，，试根据对偶理论，直接求出对偶问题的最优解。〔10分〕解：其对偶问题为：∵原问题的最优解为，设对偶问题的松弛变量分别为y5，y6，y7，y8，原问题的松弛变量为x5，x6，x7，x8。将最优解代入原问题约束条件中得：x5=0，x6=0，x7=0，x8≠0根据互补松弛性知：x*ws=0∴x1*y5=x2*y6=x3*y7=x4*y8=0∴y5=y6=y7=0，y8≠0即有：再由互补松弛性知：y*zs=0即：y1*x5=y2*x6=y3*x7=y4*x8=0因x8≠0，所以y4*=0，那么有：解得：∴对偶问题的最优解为，4某厂生产A、B、C三种产品，其所需劳动力，材料等有关数据见表，该问题的最优单纯形表如下。现如果设计一种新产品D，单件劳动力消耗为8单位，材料消耗为2单位，每件可获利3元，问该种产品是否值得生产。〔10分〕产产品消耗定额资源ABC可用量〔单位〕劳动力材料6334554530产品利润〔元/件〕314Cj31400bCBXBx1x2x3x4x534x1x310-1/31011/3-1/5-1/32/553σj0-20-1/5-3/527解：由题意有：，那么由于，需继续迭代。有Cj314300bCBXBx1x2x3x4x534x1x310-1/3101[2]-4/51/3-1/5-1/32/553σj0-201/5-1/5-3/52734x4x31/22/5-1/613/1501101/6-1/15-1/64/155/25σj-1/10-59/3000-7/30-17/3027.5即：此线性规划问题的解为：x*=(0，0，5，5/2)T,z*=27.5由此可见该产品是值得生产的。5某钻井队要从以下10个可供选择的井位中确定5个钻井探油，目的使总的钻探费用最小，假设10个井位代号为S1，S2，…，S10，相应的钻探费用为C1，C2，…，C10，并且井位的选择上要满足以下条件：①或选择S2和S7，或选择钻探S9；②选择了S3或S4就不能选择S5，或反过来也一样。③在S1，S6，S8，S10中最多只能选两个。试建立这个问题的数学模型。〔10分〕解:设钻井队是否选择某个钻井的事件为xi(i=1,2,…,10)∴建立的数学模型如下：6运输问题的产销平衡表、最优运方案及单位运价表分别如下表所示，试分析：从A至B的单位运价C在什么围变化时，最优调运方案不变。〔10分〕产销平衡表及最优方案销地产地B1B2B3B4产量A151015A20101525A355销量5151510单位运价表销地产地B1B2B3B4A11012011A2127920A32141618解：当C22变化时,最优方案不变即应使各检验数大于等于零。可得：即当从A2至B2的单位运价C22在3至10之间变时，上述最优调运方案不变。7用破圈法和避圈法求以下图中的最小局部树。〔10分〕4467985545V7V53V3V1V4V2V66解：最小局部树为：44679855645V7V53V3V2V1V4V6所以：MinW〔T〕=268证明以下图中v1至v5流为最小费用最大流。弧边数字为〔cij，fij，aij〕〔10分〕(5,5,2)(5,5,2)(2,0,3)(6,5,1)(3,0,2)(8,5,4)(7,4,6)(4,4,1)V5V4V3V2V1证明：由原流图可作出其费用有向图为：而费用有向图中不存在从v1至v5的费用最短路，所以原图所示为最小费用最大流。其最大流为9，最小费用为。9有600万元资金用于三个工厂的更新改造，投资数以百万元为单位取整数，工厂Ⅱ的投资不超过300万元，工厂Ⅰ和Ⅲ的投资均不少于100万元，又不超过400万元，各工厂投资更新改造后，每年可增加的效益如下表所示：效益投资工厂0100200300400Ⅰ361114Ⅱ051012Ⅲ481115试建立动态规划求解其预期效益最大的投资分配方案模型。〔10分〕解：〔1〕按工厂划分阶段，有k=1，2，3，4〔4表示资金分配完毕阶段〕〔2〕取状态变量sk为第k阶段初待分配资金，有，，，〔3〕取决策变量xk为第k阶段分配给k工厂的资金，有，，〔4〕状态转移方程为：〔5〕阶段指标见表，如，〔6〕递推方程为：〔7〕边界条件：10某工程队承当一桥梁的施工任务，由于该地区夏季多雨，由三个月时间不能施工，在不施工期，该工程队可将施工机械搬走或留在原处，假设搬走，需花搬迁费1800元，如果留在原处，一种方案是花500元筑一护堤，防止河水上涨发生高水位侵袭；假设不筑护堤，发生高水位侵袭时将损失10000元，又假设下暴雨发生洪水，那么不管是否修护堤，施工机械留在原处都将受到60000元的损失，如果预测在这三个月中，高水位的发生率是25%，洪水的发生率为2%，试依据决策树的方法来分析该施工队要不要把施工机械搬走及要不要修筑护堤。〔10分〕解：该问题的决策树如下：由此可见，该施工队需选择施工机械不搬走，且要修筑护堤。答题毕2006级〔B〕1分别用图解法和单纯形法求解线性规划问题，并对照指出单纯形法的每步迭代相当于图解法中可行域的哪一个顶点。〔10分〕解：用图解法有：有；用表格单纯形法求解有：原模型标准化为：Cj-2-1000bCBXBx1x2x3x4x50x30110030x43*1010120x5110015σj-2-100000x3011003-2x111/301/304-1x502/3*0-1/311σj0-1/302/30-80x30011/2-3/23/2-2x21001/2-1/27/2-1x1010-1/23/23/2σj0001/21/2-17/2所以：；其中：表一对应图中O点；表二对应图中D点；表三对应图中C点。2某工厂生产Ⅰ、Ⅱ、Ⅲ三种产品，都分别经A、B两道工序加工，设A工序可分别在设备A1或A2上完成，有B1、B2、B3三种设备可用于完成B工序，产品Ⅰ可在A、B任何一种设备上加工；产品Ⅱ可在任何规格的A设备上加工，但完成B工序时，只能在B1设备上加工；产品Ⅲ只能在A2与B2设备上加工，加工单位产品所需工序时间及其他各项数据见下表，试安排最优生产方案，使该厂获利最大。〔只建模型〕〔10分〕设备产品设备有效台时设备加工费ⅠⅡⅢA151060000.05A27912100000.03B16840000.06B241170000.11B3740000.05原料费〔元/件〕0.250.350.5售价〔元/件〕1.252.002.803写出以下线性规划问题的对偶问题。〔10分〕解:上述问题转化为标准形式为：4线性规划问题其最优单纯形表如下，分析两个约束的右端项分别在什么围变化，该问题的最优基不变。〔10分〕Cj2-1100bCBXBx1x2x3x4x520x1x51013111101610σj0-3-1-2012解：因为最优基不变的条件是：所以：，代入原问题有：，时该问题的最优基不变。5运输问题的产销平衡表与单位运价表如下表所示，试用表上作业法求各题最优解，同时用Vogel法求出各题的近似最优解。〔10分〕销地产地B1B2B3B4产量A1102201115A212792025A321416185销量5151510解：销地产地B1B2B3B4产量A1051015A2101525A355销量5151510调运方案的总费用为：5×2+5×2+10×7+15×9+10×11=3356分配问题的效率矩阵如下，试用匈牙利法求出最优解。〔10分〕解：用匈牙利法求解有：，7造船厂生产用于河运输的客货两用船，下年度各季的合同交货量、各季度正常及加班时间的生产能力及相应每条船在正常及加班时间生产出来的本钱见下表季度合同交货数正常生产加班生产能力每条本钱〔百万元〕能力每条本钱〔百万元〕116125.076.0217135.176.4315145.376.7418155.577.0该厂确定安排生产方案的优先级目标为：P1：按时完成合同交货数；P2：每季度末库存不超过2条〔年初无库存〕；P3：完成全年合同的总本钱不超过355万元。要求建立相应的目标规划模型。〔10分〕解：设xi为i季度正常生产的船只，yi为i季度加班生产时间生产的船只，si为i季度末库存数〔s0=0〕。那么有：8八口海上油井，相互间距离如下表所示。1号井离海岸最近为5海里。问从海岸经1号井铺设油管将油井连接起来，应如何铺设使输油管线长度最短。〔为便于计量和检修，油管只准在各井位处分叉〔10分〕表1各油井间距离到从234567811.32.10.90.71.82.01.520.91.81.22.62.31.132.61.72.51.91.040.71.61.50.950.91.10.860.61.070.5解：用避圈法求其最短长度，如图。2238541760.61.00.90.80.70.70.5最短输油管线长度为：L*=5+0.7+0.7+0.8+0.5+0.6+1.0+0.9=10.2海里。9建立求解以下规划问题的动态规划模型。〔10分〕解：〔1〕按变量划分阶段，有k=1，2，3，4〔4表示完毕阶段〕〔2〕sk：各阶段得状态变量为：s1，s2，s3，设：s1=s2+2x1≤3，s2=s3+x2，s3=x3〔3〕xk为决策变量，有：0≤x1≤3/2；0≤x2≤s2；0≤x3≤s3〔4〕状态转移方程：s3=s2-x2，s2=s1-2x1，〔5〕阶段指标：，，〔6〕递推方程：〔7〕边界条件：10某书店希望订购最新出版的图书出售。根据以往经历，新书的销售量可能为50、100、150或200本。假定每本书的订购价为4元，销售价为6元，剩书处理价为每本2元。书店统计过去销售新书数量的规律如下表：销售量50100150200占得比率〔%〕20403010试用最大期望收益值准那么〔EMV〕决定订购数量；假设书店负责人能确切掌握新书