运筹学重修辅导习题

运筹学重修辅导习题 一、判断题 1. 线性规划问题的每一个基本解对应可行域的一个顶点。 ( ) 2. 如果一个线性规划问题有两个不同的最优解，则它有无穷多个 最优解。 ( ) 3. 对于线性规划问题和对偶问题，若其中一个有最优解，另一个 也有最优解。( ) 4. 对有转运的运输问题，就把每一个产地、每一个销地、每一个 中转站都看成是既是产地，又是销地。 ( ) 5. 整数规划的最优目标函数值一定不优于其松弛线性规划的最优 目标函数值。( ) 二、选择题 1. 在利用图解法求解最大利润问题中中，通过各极点作与目标函数直线斜率相同的平行 线，这些平行线称之为 。 ( ) A.可行解 B.可行域 C.等利润线 D.等成本线 2. 用单纯形法求解线性规划问题时引入的松弛变量在目标函数中 的系数为 。( ) A.0 B.很大的正数 C.很大的负 数 D.1 3. 以下关系中，不是线性规划与其对偶问题的对应关系的是 。 ( ) A约束条件组的系数矩阵互为转置矩阵 B一个约束条件组的常数列为另一个目标函数的系数行向量 C两个约束条件组中的方程个数相等 D约束条件组的不等式反向 4. 需求量大于供应量的运输问题需要做的是 。 ( ) A.虚设一个需求点 B.删去一个供应点 C.虚设一个供应点，取虚设供应量为恰当值 D.令供应点到虚设的需求点的单位运费为0 5. 对一个求目标函数最大的混合整数规划问题，以下命题中不正 确的是 。 （ ） A.其线性规划松弛问题的最优解可能是该整数规划问题的最优 解。 B.该问题可行解的个数一定是有限的； C.任一可行解的目标函数值不可能大于其线性规划松弛问题的 目标函数值； D.该问题可行解中可能存在不取整数值的变量。 三、简答题 1. 什么是人工变量、大M法？ 2. 写出下列线性规划问题的标准形 3. 写出下列线性规划问题的对偶模型 四、解答题 1. 某工厂在计划期内要安排生产、两种产品，这些产品分别 需要在A、B、C、D四种不同的设备上加工。有关数据见下表。 问应如何安排生产计划，才能得到利润最多? 设备 产品 ABCD利润 2 2 1 2 4 0 0 4 2元 3元 有效台时1281612 2. 已知线性规划问题（P）： 的一个单纯形表如下。 Cj23300 cBXBbX1X2X3X4X5 2X1110-14/3-1/3 3X22012-1/31/3 Cj-zj00-1-5/3-1/3 （1） 写出(P)此时的基本可行解，并判断该解是否为最优解； （2） 在什么范围内变化时，最优解不变； 3. 已知线性规划问题： 的最优解为X*=(2,2,4,0)，根据对偶理论求出对偶问题最优解。 4. 用最小元素法或Vogel法求下列运输问题的近似最优解，并检查 其是否为最优解。 销地 运价 产地 产量 3113127 19284 741059 销量3656 5. 有五项工作分给五个人去完成，各人完成每项工作的收效如下 表，求完成所有工作总收益最大的方案。 工作 工人 12345 1382103 287297 364275 484235 54106910 五、建模题（只要建立数学模型，不用求解） 1. 现有一批某种型号的圆钢长8米,需要截取2.5米长的毛坯120根,长 1.3米的毛坯240根.如何才能既满足需要,又能使总的用料最少， 试建立数学模型。 2. 某造船厂根据合同从当年起连续三年末各提供四条规格相同的 大型客货轮。已知该厂这三年内生产大型客货轮的能力及每艘 客货轮成本如下表所示： 年度 正常生产时间内可 完成的客货轮数 加班生产时间内可 完成的客货轮数 正常生产时每艘 成本（万元） 1 3 3 500 2 5 2 600 3 2 3 500 已知加班生产时,每艘客货轮成本比较正常时高出60万元；又知造出来 的客货轮若当年不交货,每艘每年积压一年造成损失为30万元。在签定