运筹学第五章试题及答案

运筹学第五章试题及答案

一、单项选择题（每题2分，共20分）1.用割平面法求解整数规划时，构造的割平面会（）A.增加可行域B.减少可行域C.不改变可行域D.无法确定2.以下不属于整数规划求解方法的是（）A.分支定界法B.匈牙利法C.割平面法D.单纯形法3.整数规划中，纯整数规划是指（）A.决策变量全部是整数B.部分决策变量是整数C.决策变量取0-1值D.目标函数值是整数4.求解0-1规划的一种常用方法是（）A.隐枚举法B.分枝界定法C.割平面法D.运输法5.指派问题的数学模型属于（）A.线性规划B.非线性规划C.动态规划D.整数规划6.若原整数规划的松弛问题无可行解，则原整数规划（）A.有可行解B.无可行解C.可能有可行解D.以上都不对7.用分支定界法求解整数规划问题，是将原问题分支为若干子问题，通过（）来逐步缩小搜索范围。A.定界和剪枝B.增加约束条件C.减少约束条件D.改变目标函数8.在求解整数规划时，若不考虑整数约束条件，得到的解是整数解，则该解（）A.一定是原整数规划的最优解B.不一定是原整数规划的最优解C.一定不是原整数规划的最优解D.无法判断9.对于指派问题，若系数矩阵的某一行元素都加上一个常数k，则最优解（）A.改变B.不变C.可能改变D.无法确定10.整数规划问题中，变量的取值要求是（）A.实数B.整数C.正实数D.正整数答案：1-5BDAAD；6-10BAABB二、多项选择题（每题2分，共20分）1.整数规划的类型包括（）A.纯整数规划B.混合整数规划C.0-1整数规划D.线性整数规划2.下列关于分支定界法的说法正确的有（）A.分支的目的是缩小解的搜索范围B.定界是确定目标函数值的上下界C.该方法可用于求解纯整数规划和混合整数规划D.每次分支后得到的子问题的可行域比原问题的可行域小3.0-1规划的应用场景有（）A.分配问题B.投资决策问题C.背包问题D.生产计划问题4.求解整数规划的方法有（）A.分支定界法B.割平面法C.隐枚举法D.匈牙利法5.指派问题的特点有（）A.目标函数是求最小化B.系数矩阵是方阵C.决策变量为0-1变量D.所有约束条件都是等式约束6.割平面法的步骤包括（）A.求解原整数规划的松弛问题B.从松弛问题的最优解中找出非整数分量C.构造割平面方程并加入到松弛问题中D.重复求解新的线性规划问题，直到得到整数解7.线性规划与整数规划的关系有（）A.整数规划的可行域是线性规划可行域的子集B.线性规划的最优解一定是整数规划的最优解C.整数规划的最优解不一定是线性规划的最优解D.整数规划的目标函数值一般优于线性规划的目标函数值8.以下关于0-1变量说法正确的是（）A.表示“是”或“否”的决策B.只能取0或1C.用于解决逻辑选择问题D.在指派问题中经常使用9.用匈牙利法求解指派问题时，需要（）A.对系数矩阵进行变换B.找出独立零元素C.确定初始可行解D.进行试指派10.整数规划在实际中的应用领域有（）A.物流配送B.人员安排C.项目选址D.资源分配答案：1.ABC；2.ABCD；3.ABCD；4.ABCD；5.BCD；6.ABCD；7.AC；8.ABCD；9.ABD；10.ABCD三、判断题（每题2分，共20分）1.整数规划的可行解一定是对应线性规划可行解的一部分。（）2.分支定界法只能用于求解纯整数规划问题。（）3.0-1规划是一种特殊的整数规划。（）4.割平面法通过增加约束条件来逐渐缩小可行域，最终得到整数解。（）5.指派问题是一种特殊的线性规划问题，其最优解一定是整数解。（）6.若线性规划问题的最优解是整数解，则该解也是对应整数规划问题的最优解。（）7.在分支定界法中，剪掉的分支一定不包含原问题的最优解。（）8.0-1变量在实际问题中只能表示两种状态选择。（）9.匈牙利法只能求解目标函数为最小化的指派问题。（）10.整数规划的最优目标函数值一定小于或等于其松弛问题的最优目标函数值。（）答案：1.√；2.×；3.√；4.√；5.√；6.√；7.√；8.√；9.×；10.√四、简答题（每题5分，共20分）1.简述整数规划与线性规划的区别与联系。答：联系：整数规划可行域是对应线性规划可行域子集，线性规划是整数规划基础。区别：线性规划决策变量可为任意实数，整数规划部分或全部变量须取整，整数规划求解更复杂，可行解是离散的。2.简述分支定界法的基本思路。答：先求解原整数规划的松弛问题，若解非整数，将其分支为子问题。通过定界确定目标函数上下界，剪掉不可能含最优解的分支，不断缩小搜索范围，直至找到最优整数解。3.0-1规划有哪些常见应用场景？答：常见应用场景有投资决策，决定是否投资某项目；分配问题，如人员任务分配；背包问题，决定是否装入物品；生产计划，确定是否生产某产品。4.简述割平面法的主要步骤。答：先求解整数规划松弛问题，若解非整数，从解中找非整数分量，构造割平面方程加入松弛问题，形成新线性规划，再求解，重复此过程直到得整数解。五、讨论题（每题5分，共20分）1.讨论在实际问题中，整数规划相较于线性规划的优势和局限性。答：优势：能准确描述变量取整的实际问题，如人员、设备数量。局限性：求解复杂，计算量大，当问题规模大时，求解时间长甚至难求解，且建模时对整数约束考量易使问题变复杂。2.分支定界法在求解整数规划时，如何有效地进行分支和定界，提高求解效率？答：分支时可优先选择对目标函数影响大、非整数程度高的变量分支。定界可利用松弛问题解及问题特性确定合理上下界，还可结合启发式算法快速找到可行解更新界，减少搜索范围。3.0-1规划在项目选择决策中的应用及意义。答：应用：可决定是否选择某项目，综合考虑资源、收益等约束。意义：能科学规划项目组合，