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

12002级（A）参考答案1.写出下述线性规划模型的标准型。（10分）zyxwmax..ts1yx32zx解：令zzzyyyxxx,,原问题标准化为：zzyyxxwmax..ts1uyyxx322zzxx0,,,,,zzyyxx2.有线性规划模型：21510maxxxz（10分）..ts94321xx82521xx0,021xx（1）用图解法求解；（2）用单纯形法求解；（3）指出每个单纯形表的可行域顶点。解：（1）用图解法求解；01234x11234x25x+2x=8123x+4x=921A:x=(1,3/2)*TBC∴X*=（1，1/2）T；Z*=35/2（2）用单纯形法求解；原模型标准化为：21510minxxz..ts32143xxx92125xx84x0,0,0,04321xxxx则求解过程为：Cj-10-500b2T0T1T2∴X*=（1，1/2）T；Z*=35/2（3）指出每个单纯形表的可行域顶点。T0表对应O点；T1表对应B点；T2表对应A点，也是最优点。3.求解：321425minxxxz（10分）..ts423321xxx10536321xxx0,,321xxx解：原问题标准化为：321425minxxxz..ts432123xxxx4321536xxx105x0,,,,54321xxxxx用对偶单纯形法求解为：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.写出线性规划问题：543215746maxxxxxxzCBXBx1x2x3x400x3x434105*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/2325873..54321xxxxxts6923254321xxxxx为自由变量5);4,3,2,1(0xjxj的对偶规划。（10分）解：原问题的对偶规划为：2162minyyw623..21yyts4721yy13821yy72521yy5921yy为自由变量21,yy5.有一最小化指派问题的系数矩阵如下，试求其最优解。（10分）9131541116141381441579102C解：用匈牙利算法求解为：9131541116141381441579102C41142变换后：59110053241001157801C-5再变换为：5411000324501152802C2再变换：329000344501330602C∴0001100000100100*XZ*=286.写出函数22212132)(xxxxXf的梯度和海赛矩阵，并判断其凹凸性。（10分）解：22212132)(xxxxXf的梯度矩阵为：TTxxxxxXfxXfXf)62,22())(,)(()(212121422212132)(xxxxXf的海赛矩阵为：6222)()()()()(2221222122122xXfxxXfxxXfxXfXfH这里H矩阵的各阶主子式均大于0，所以22212132)(xxxxXf为严格凸函数。7.某厂有4台设备，拟分给3个用户（工厂）使用，各用户利用设备提供的盈利如下表。问如何分配设备才能使总盈利最大？试建立其动态规划求解模型（可不求解）。（10分）用户设备台数12301234046770256803578解：根据题意，原问题用动态规划求解模型为：（1）按用户分为3阶段，K=（1，2，3，4），k=4为终了阶段；（2）xk：第k阶段初拥有待分配设备台数；x1=4，0≤x2≤4，0≤x3≤4，x4=0；（3）uk：第k阶段分配给第k用户的设备数，有：U1={0,1,2,3,4}，U2={0,1,2,…,x2}，U3={x3};（4）状态转移方程：kkkuxx1；（5）阶段指标：见表，如：5)2,3(2d；3)1,2(3d；（6）递推方程：)(),(max)(11kkkkkUukkxfuxdxfkk（7）边界条件：0)(44xf。8.证明下图所示v1至v6流为最大流。弧边数字为),(ijijfc。（10分）证明：对原流图用标号法找可扩充路有：(-，∞)v6v5v4v32,25,33,01,02,25,21,04,33,3v1v2v6v5v4v32,25,33,01,02,25,21,04,33,3v1v25标号过程进行不下去，即不存在v1-v6的可扩充路，根据可扩充路定理，图示流即为最大流,maxQ=5。9.下图为求1v至5v的最小费用最大流时得到的某一流图，弧边数字为),,(ijijijafc，试构造其费用有向图（流增量图）)(kijfW。（10分）v14,4,1v37,4,6v58,5,43,0,22,0,35,5,2v2v46,5,1解：由原流图可作出其费用有向图)(kijfW为：v1-1v36v5-6-4423-2-1v21v410.某商行夏季订购一批西瓜，根据以往的经验，西瓜销售量可能为10000、15000、20000、25000kg。假定西瓜售价为0.35元/kg，商行支出成本为0.25元/kg。（1）建立益损矩阵；（3分）（2）分别用悲观法、乐观法、等可能法和后悔值法确定西瓜订购数量。（7分）解:（1）原问题的益损矩阵为；αiSj10000150002000025000100001500020000250001000100010001000-250150015001500-150025020002000-2750-10007502500（2）悲观准则：ijjdminmax10002750,1500,2501000max，∴1*乐观准则：ijjdmaxmax25002500,2000,1500,1000max∴4*(v1,3)6等可能准则：ndjijmax5.1062125,5.687,5.1062,1000max∴2*后悔值准则：后悔值矩阵为：0125025003750500012502500100050001250150010005000则ijjdmaxmin12503750,2500,1250,1500min∴2*（答题毕）2002级（B）参考答案1.求解线性规划问题：2134xxMaxZ..ts124321xx4221xx22321xx0,21xx的最优解。（15分）解：图解过程如下：2x1x43214321022321xxTA)512,54(4221xx124321xxTX)512,54(*552*Z72.写出下述线性规划的对偶规划。（15分）43214765xxxxMinZ..ts724321xxxx147364321xxxx32417284321xxxx0,21xx；43,xx无限制。解：对偶规划为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）价值（元）8解：用动态规划求解时，其模型为：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.状态转移方程：kkkuxx15.阶段指标见表，kkkkkucuxv),(；5.0;2;3;4;954321ccccc6.递推方程（逆推）：)(),(max)(11kkkkkUukkxfuxvxfkk7.边界条件：0)(66xf6.证明下图所示s-t流为最大流。弧边数字为（ijijfc,）（15分）证明：对原流图用标号法找增广链有30，3054，30（+vs，12）①③⑤42，3060，54（-，∞）s（+v4，12）⑥t75，4569，5733，045，33（+vs，12）②④⑦78，57（+v2，12）12，12标号过程进行不下去，即不存在s-t增广链，根据增广链定理，图示s-t流即为最大流。7.已知某决策问题的收益矩阵D为：ABCDE7543194320.521,2124,2436,027,030，3054，3078，5712，1260，5445，3375，4533，042，3069，57①③②⑥④⑦⑤ts21,2124,2436,027,09D=0210197320145129814317601015分别用乐观法、悲观法、等可能法和后悔值法确定其最优决策。（15分）解：乐观准则：2019,20,14,17maxmaxmax*ijjid：∴3*悲观准则：20,3,2,6maxminmax*ij