历年运筹学考研试题及答案试题：一、单项选择题（每题2分，共10分）1. 线性规划问题的标准形式是：A. 所有变量非负B. 目标函数为最小化C. 约束条件为等式D. 所有变量非负，约束条件为等式和不等式2. 在单纯形法中，如果某个非基变量的检验数为负，则：A. 该变量不能进入基B. 该变量可以进入基C. 该变量必须进入基D. 以上都不对3. 对于运输问题，当供应量等于需求量时，我们称其为：A. 平衡运输问题B. 不平衡运输问题C. 线性运输问题D. 非线性运输问题4. 在动态规划中，最优子结构性质意味着：A. 问题的最优解包含子问题的最优解B. 问题的所有解都包含子问题的最优解C. 问题的一个解包含子问题的最优解D. 以上都不对5. 网络最大流问题中，Ford-Fulkerson算法的核心思想是：A. 寻找增广路径B. 寻找最短路径C. 寻找最长路径D. 寻找最小割二、简答题（每题10分，共20分）1. 简述线性规划的几何意义及其在实际问题中的应用。
2. 解释什么是灵敏度分析，并说明其在解决线性规划问题中的作用。
三、计算题（每题15分，共30分）1. 假设有以下线性规划问题：Max Z = 3x + 4ySubject to:2x + y ≤ 6x + 2y ≤ 7x, y ≥ 0请用图解法找到该问题的最优解。
2. 给定一个网络流问题，网络中有三个节点A, B, C，以及三条边(A,B), (B, C), (A, C)，每条边的容量分别为10, 5, 8。
要求从节点A到节点C的最大流量。
使用Ford-Fulkerson算法求解。
四、论述题（每题20分，共20分）1. 论述动态规划与分治法在解决组合优化问题时的异同，并给出一个适合使用动态规划法解决的实际问题例子。
答案：一、单项选择题1. D2. C3. A4. A5. A二、简答题1. 线性规划的几何意义是在n维空间中寻找一个多边形的顶点，这个多边形由约束条件定义，而目标函数则定义了一个目标方向。
运筹学考研真题及答案运筹学考研真题及答案一、选择题1. 在线性规划中，若最优化问题的对偶问题有最优解，则原始问题也有最优解。
（正确）解析：线性规划理论中对偶定理：“若原始问题的对偶问题有可行解，且存在最优解，则原始问题也有最优解。
”2. 若在线性规划的单纯形法中，某一回路上的所有非基变量（非基变量为0）均为0，则这一问题无有限最优解。
（错误）解析：所有非基变量为0时，相应的基变量可以任意非负，问题有无穷多最优解。
3. 在线性规划中，若某元组在原始问题和对偶问题下都是可行解，则该元组是原始问题和对偶问题的最优解。
（错误）解析：若某元组在原始问题和对偶问题下都是可行解，则该元组满足原始问题的可行性和对偶问题的可行性，但并不一定是最优解。
4. 线性规划的最优性条件是原始问题的可行解和对偶问题的可行解所对应的目标函数值相等。
（正确）解析：线性规划理论中最优性条件：“若原始问题的可行解与对偶问题的可行解所对应的目标函数值相等，则解是原始问题和对偶问题的最优解。
”5. 线性规划的可行性要求约束条件为不等式约束。
（错误）解析：线性规划的可行性要求是所有约束条件都满足，包括等式约束和不等式约束。
二、填空题1. 与线性规划的相对论证法相对应的是（单纯形法）。
解析：线性规划的相对论证法和单纯形法是互为相对的两种求解方法。
2. 在线性规划中，若最优差异为0，则最优解是（非唯一）。
解析：最优差异为0意味着最优解是非唯一的，有多个最优解。
3. 线性规划的最优性条件是（对偶定理）与最优条件相对应。
解析：线性规划的最优性条件是对偶定理，而最优条件是原始问题的可行解和对偶问题可行解所对应的目标函数值相等。
4. 在线性规划中，若一个可行解在原始问题和对偶问题下都是最优解，则称为（互补性）条件。
解析：若一个可行解在原始问题和对偶问题下都是最优解，则满足互补性条件。
三、应用题1.某公司生产两种产品A和B，每个产品的制造工序及所需时间如下表，在一天内，公司有8小时的工时可用，每个工序只能由一名员工负责完成。
运筹学考试试卷及答案一、选择题（每题2分，共20分）1. 线性规划问题的标准形式是：A. 所有变量都非负B. 目标函数是最大化C. 所有约束条件都是等式D. 所有约束条件都是不等式答案：A2. 单纯形法中，如果某个变量的检验数为负数，那么：A. 该变量可以增大B. 该变量可以减小C. 该变量保持不变D. 该变量不能进入基答案：A3. 在运输问题中，如果某种资源的供应量大于需求量，那么应该：A. 增加供应量B. 减少需求量C. 增加需求量D. 减少供应量答案：C4. 动态规划的基本原理是：A. 递归B. 迭代C. 回溯D. 分解答案：D5. 决策树中，每个节点代表：A. 一个决策B. 一个状态C. 一个结果D. 一个概率答案：A6. 排队论中，M/M/1队列的特点是：A. 到达时间服从泊松分布，服务时间服从指数分布，且只有一个服务台B. 到达时间服从指数分布，服务时间服从泊松分布，且只有一个服务台C. 到达时间服从泊松分布，服务时间服从指数分布，且有两个服务台D. 到达时间服从指数分布，服务时间服从泊松分布，且有两个服务台答案：A7. 网络流问题中，最大流最小割定理说明：A. 最大流等于最小割B. 最大流小于最小割C. 最大流大于最小割D. 最大流与最小割无关答案：A8. 整数规划问题中，分支定界法的基本思想是：A. 将问题分解为多个子问题B. 将问题转化为线性规划问题C. 将问题转化为非线性规划问题D. 将问题转化为动态规划问题答案：A9. 在多目标决策中，如果目标之间存在冲突，通常采用的方法是：A. 目标排序B. 目标加权C. 目标合并D. 目标替换答案：B10. 敏感性分析的目的是：A. 确定最优解的稳定性B. 确定最优解的唯一性C. 确定最优解的可行性D. 确定最优解的最优性答案：A二、填空题（每题2分，共20分）1. 线性规划问题的可行域是由所有_________约束条件构成的集合。
答案：可行2. 在单纯形法中，如果目标函数的系数都是正数，则该问题为_________问题。
10/11（二）浙江工业大学运筹学考试试卷学院： 班级： 姓名： 学号：一、填空题（共30分）1. 如果把约束方程⎩⎨⎧≥+≤+552432121x x x x 标准化为⎩⎨⎧=+-+=++552435421321x x x x x x x 时, 3x 是______变量，4x 是______变量，5x 是______变量. 2. 右图对应于某线性规划问题的约束集合，则其基解为 __________, 基可行解为____________.3. 设原问题为⎩⎨⎧≥==0max X b AX CXz ， 则其对偶问题为__________________; 若对偶问题为无界解,则其原问题为__________.4. 线性规划中，影子价格1Y -=CB 是原问题的__________, 也是对偶问题的___________. 5. 某工程拟从4个项目中选择若干项目，若令⎩⎨⎧=，个项目未被选中第，个项目被选中第 i 0 i ,1i x 4,3,2,1=i . 则用i x 的线性表达式表示下列要求：(1) 4个项目中有且仅有一个被选中_____________________________;(2) 4个项目中有三个项目被选中_______________________________.6. 作为动态规划的状态变量，应具有___________性; 贝尔曼提出的最优性原理是____________________, 它是判断一个策略最优的______________条件.7. 已知某线性规划问题的最优单纯形表如表1所示，表中54,x x 为松弛变量，问题的约束为≤形式，写出原线性规划问题____________________.8. 指派问题中效益矩阵的独立零元个数___________效益矩阵的阶数时，就得到了最优解. 9. 运输问题的运价矩阵C 是n m ⨯的，则C 的秩为______________; 在____________和_____________过程中可以出现退化现象.10. 某一求目标函数极大值的线性规划问题，用单纯形法求解得到最终表如表2，其中常数αααα，，，321和1σ未知，且不含人工变量. 问应如何限制这些参数，使得下列结论成立： (1) 当____________________, 有唯一最优解； (2) 当____________________, 有无穷多最优解； (3) 当____________________, 有无界解.二、选择题（共30分）1. 若某线性规划有可行解，则________一定不是其可行域.C2. 某线性规划问题有3个变量，5个约束方程，则其基可行解个数不可能是_________ A. 6 B. 8 C. 10 D . 123. 用大M 法求解⎪⎩⎪⎨⎧≥≥+-≥-+=0,3232..42max 21212121x x x x x x t s x x z 的单纯形最终表如表3, 则原问题______________A. 有唯一最优解B. 有无界解C. 无可行解D. 有无穷多最优解4. 一对对偶问题中，___________一定不可能出现.A. 两个都有最优解B. 一个有无界解，另一个无可行解C. 两个都无可行解D. 一个有最优解，另一个有无可行解5. 线性规划可行域的顶点一定____________A. 不是基解B. 是最优解C. 不是最优解D. 不能表示成任意其他两个可行解的凸组合6. 线性规划可行域非空无界，则_____________A. 其对偶问题无可行解B. 该线性规划无最优解C. 该线性规划一定有最优解D. 该线性规划存在基可行解表37. 下列序列可能是某个简单图的次的次序_______________A. 7,6,5,4,3,2B. 6,6,5,4,3,2,1C. 6, 5, 5, 4,3,2,1D. 3,3,3,3,3,3,48. 表4是整数规划问题的相应线性规划问题的单纯形表终表. 为了使用割平面法，那么______A. 3/26/56/543-≤--x xB. 3/26/16/543-≤+x xC. 3/23/13/143≤--x xD. 3/23/13/143-≤-x x9. 满足树条件的图______________A. B. C. D.10. 下列图中的流是可行流的____________A.B.C.D.三、计算题（共40分）A BC D EF 13(8)9(9)6(5) 6(6)7(1)5(5)4(0)11(10)12(7)A BCD EF 8(5) 5(4)5(3) 6(5)6(1)5(1)4(2)11(8)7(6)A BCD EF 13(8)9(9)6(5) 6(6)7(1)5(5)4(3) 11(10)12(7)A BCD EF 13(11)9(9)5(5) 6(6)5(4)5(5)4(0) 10(11)10(10)表41. 设5件工件需要先后在A 、B 两台机器上加工, 已知各自所需的加工时间如表5所示, 试2. 考虑下列原线性规划⎪⎩⎪⎨⎧≥≥≥=++≤++++=0,0,01243252..32max 321321321321x x x x x x x x x t s x x x z (1) 写出其对偶问题；(2) 已知 (3, 2, 0) 是上述原问题的最优解，根据互补松弛定律，求出对偶问题的最优解； (3) 如果上述线性规划中的第一个约束为资源约束，写出这种资源的影子价格.3. 求图中从A 到各点的最短路.4. 已知某工厂计划生产I 、II 、III 三种产品，各产品需要在A 、B 、C 设备上加工. 结合给出的该线性规划的Lindo 输出结果，回答以下问题。
