《武汉科技大学本科历年运筹学试题》由会员分享，可在线阅读，更多相关《武汉科技大学本科历年运筹学试题（71页珍藏版）》请在金锄头文库上搜索。
1、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/1
2、4 -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-10
3、x1x21 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个用户（工厂）使用，各用户利用设备提供的盈
4、利如下表。问如何分配设备才能使总盈利最大？试建立其动态规划求解模型（可不求解）。 （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,2
5、5,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
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
7、 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
