《运筹学》整数规划方法与应用考试

《运筹学》整数规划方法与应用考试考试时长：120分钟满分：100分一、单选题（总共10题，每题2分，总分20分）1.在整数规划问题中，若变量x只能取0或1，则称该变量为（）A.连续变量B.整数变量C.0-1变量D.离散变量2.对于整数规划模型，若松弛变量或剩余变量在最优单纯形表中仍为正，则该解（）A.必为整数解B.必为非整数解C.可能是整数解D.无法判断3.割平面法在求解整数规划问题时，每次迭代会（）A.增加一个约束条件B.删除一个约束条件C.修改目标函数系数D.调整变量取值范围4.分支定界法适用于（）A.线性规划问题B.整数规划问题C.非线性规划问题D.动态规划问题5.若整数规划的原问题最优解为非整数解，则其松弛问题最优解的值（）A.必然大于原问题目标函数值B.必然小于原问题目标函数值C.与原问题目标函数值无关D.无法确定6.在分支定界法中，若某分支节点被证明不可行，则该分支（）A.需要继续搜索B.可以被舍弃C.需要重新定义约束D.必然是最优解7.若整数规划问题中所有变量均要求为整数，则该问题属于（）A.混合整数规划B.纯整数规划C.0-1规划D.二进制规划8.在分支定界法中，最优解的搜索过程是（）A.自顶向下B.自底向上C.交替进行D.随机选择9.若整数规划问题中存在多个变量需要取整数，则该问题属于（）A.单纯形法问题B.割平面法问题C.分支定界法问题D.整数规划问题10.整数规划问题的解法中，（）A.唯一最优解B.多重最优解C.无解D.以上均有可能二、填空题（总共10题，每题2分，总分20分）1.整数规划问题中，若变量只能取0或1，则称为______变量。2.分支定界法中，每次分支会将问题分解为______个子问题。3.割平面法的基本思想是通过添加______来逐步逼近整数解。4.若整数规划的原问题最优解为非整数解，则松弛问题最优解的值______原问题目标函数值。5.整数规划问题的解法中，______法适用于纯整数规划问题。6.分支定界法中，若某分支节点被证明不可行，则该分支______。7.整数规划问题中，若所有变量均要求为整数，则该问题属于______规划。8.整数规划问题的解法中，______法适用于混合整数规划问题。9.整数规划问题的解法中，______法适用于0-1规划问题。10.整数规划问题的解法中，______法适用于二进制规划问题。三、判断题（总共10题，每题2分，总分20分）1.整数规划问题的解法中，单纯形法可以直接求解整数解。（×）2.分支定界法适用于所有类型的整数规划问题。（√）3.割平面法在每次迭代中都会增加一个约束条件。（√）4.若整数规划问题的最优解为非整数解，则松弛问题最优解的值必然大于原问题目标函数值。（×）5.整数规划问题的解法中，唯一最优解。（×）6.分支定界法中，每次分支会将问题分解为两个子问题。（√）7.整数规划问题的解法中，割平面法适用于纯整数规划问题。（×）8.整数规划问题的解法中，分支定界法适用于混合整数规划问题。（√）9.整数规划问题的解法中，0-1规划法适用于纯整数规划问题。（×）10.整数规划问题的解法中，二进制规划法适用于0-1规划问题。（×）四、简答题（总共4题，每题4分，总分16分）1.简述整数规划问题的基本概念及其与线性规划问题的区别。2.简述分支定界法的基本步骤及其优缺点。3.简述割平面法的基本思想及其适用条件。4.简述0-1规划问题的特点及其应用场景。五、应用题（总共4题，每题6分，总分24分）1.某公司生产两种产品A和B，每件产品A的利润为3元，每件产品B的利润为5元。生产每件产品A需要1小时，生产每件产品B需要2小时，公司每天最多有8小时的生产时间。此外，产品A的产量不能超过产品B的产量。若产品A和B的产量均要求为整数，求公司每天的最大利润。2.某投资组合包含三种股票，股票X的预期收益率为10%，股票Y的预期收益率为15%，股票Z的预期收益率为20%。投资组合的风险限制为不超过30%。若投资组合的总投资额为100万元，且每种股票的投资比例均要求为整数，求投资组合的最大预期收益率。3.某工厂生产两种零件P和Q，每件零件P的利润为2元，每件零件Q的利润为3元。生产每件零件P需要1个单位的原材料A，生产每件零件Q需要2个单位的原材料A。工厂每天最多有100个单位的原材料A。此外，零件P的产量不能超过零件Q的产量。若零件P和Q的产量均要求为整数，求工厂每天的最大利润。4.某公司需要决定是否投资三个项目，项目1的投资额为10万元，预期收益率为12%；项目2的投资额为20万元，预期收益率为15%；项目3的投资额为30万元，预期收益率为18%。公司的总投资额限制为50万元。若投资决策变量只能取0或1，求公司的最大预期收益率。【标准答案及解析】一、单选题1.C2.B3.A4.B5.A6.B7.B8.A9.D10.D二、填空题1.0-12.两3.割平面4.大于5.割平面6.可以被舍弃7.纯整数8.分支定界9.0-1规划10.二进制规划三、判断题1.×2.√3.√4.×5.×6.√7.×8.√9.×10.×四、简答题1.整数规划问题的基本概念是指在一定约束条件下，目标函数的取值或部分变量的取值要求为整数的问题。与线性规划问题的区别在于，线性规划问题允许变量取任意实数，而整数规划问题要求部分或全部变量取整数。2.分支定界法的基本步骤包括：-求解松弛问题，得到最优解和目标函数值；-若松弛问题最优解为整数解，则停止；否则，选择一个非整数解的变量进行分支；-对每个分支进行松弛问题的求解，并记录最优解和目标函数值；-若某个分支的最优解优于当前最优解，则更新最优解；否则，舍弃该分支；-重复上述步骤，直到所有分支都被处理完毕。优点是可以保证找到整数最优解，缺点是计算量可能较大。3.割平面法的基本思想是通过添加一个约束条件（割平面）来逐步逼近整数解。具体步骤包括：-求解松弛问题，得到最优解和目标函数值；-若最优解为整数解，则停止；否则，选择一个非整数解的变量，构造一个割平面；-将割平面添加到松弛问题中，重新求解；-重复上述步骤，直到找到整数最优解。适用条件是松弛问题有最优解，且最优解中存在非整数解。4.0-1规划问题的特点是指所有变量的取值只能为0或1，常用于决策问题。应用场景包括投资组合、资源分配、项目选择等。五、应用题1.设产品A和B的产量分别为x和y，则整数规划模型为：maxz=3x+5ys.t.x+2y≤8x≤yx,y≥0,且为整数解：-当x=0时，y=4，z=20；-当x=1时，y=3，z=18；-当x=2时，y=3，z=19；-当x=3时，y=3，z=24；-当x=4时，y=4，z=32；最大利润为32元，对应解为x=4,y=4。2.设投资比例为x,y,z，则整数规划模型为：maxz=0.1x+0.15y+0.2zs.t.x+y+z=1x,y,z≥0,且为整数解：-当x=0,y=0,z=1时，z=0.2；-当x=0,y=1,z=0时，z=0.15；-当x=1,y=0,z=0时，z=0.1；最大预期收益率为0.2，对应解为x=0,y=0,z=1。3.设零件P和Q的产量分别为x和y，则整数规划模型为：maxz=2x+3ys.t.x+2y≤100x≤yx,y≥0,且为整数解：-当x=0时，y=50，z=150；-当x=1时，y=49，z=145；-当x=2时，y=49，z=148；-当x=3时，y=49，z=151；-当x=4时，y=50，z=152；最大利润为152元，对应解为x=4,y=50。4.设投资决策变量为x1,x2,x3，则整数规划模型为：maxz=0.12x1+0.