第六章整数规划

《第六章整数规划》由会员分享，可在线阅读，更多相关《第六章整数规划（7页珍藏版）》请在装配图网上搜索。

1、第五章整数规划一、填空题1用分枝定界法求极大化的整数规划问题时，任何一个可行解的目标函数值是该问题目标 函数值的（ ）。2. 在分枝定界法中，若选Xr=4 / 3进行分支，则构造的约束条件应为（）。3. 已知整数规划问题P0，其相应的松驰问题记为P0,若问题P0 无可行解，则问题P。（ ）。4. 在0 - 1整数规划中变量的取值可能是（）或（）。5. 对于一个有n项任务需要有n个人去完成的分配问题，其解中取值为1的变量数为（） 个。6. 分枝定界法和割平面法的基础都是用（）求解整数规划。7. 若在对某整数规划问题的松驰问题进行求解时，得到最优单纯形表中，由X。所在行得X1+1 / 7x3+2

2、/ 7x5=13 / 7,则以X1行为源行的割平面方程为（）。8. 在用割平面法求解整数规划问题时，要求全部变量必须都为（）。9. 用（）求解整数规划问题时，若某个约束条件中有不为整数的系数，则需在该约束两端扩大适当倍数，将全部系数化为整数。10. 求解纯整数规划的方法是割平面法。求解混合整数规划的方法是（）。11. 求解01整数规划的方法是隐枚举法。求解分配问题的专门方法是（）。12. 在应用匈牙利法求解分配问题时，最终求得的分配元应是（）。13. 分枝定界法一般每次分枝数量为（）个.二、单选题1. 整数规划问题中，变量的取值可能是（）。A. 整数B 0或1C.大于零的非整数D.以上三种都可

3、能2. 在下列整数规划问题中，分枝定界法和割平面法都可以采用的是A （）。A. 纯整数规划B混合整数规划C. 01规划D.线性规划3. 下列方法中用于求解分配问题的是（ ）。A.单纯形表B.分枝定界法C.表上作业法D.匈牙利法三、多项选择1下列说明不正确的是（ ）。A. 求解整数规划可以采用求解其相应的松驰问题，然后对其非整数值的解四舍五入的方法 得到整数解。B. 用分枝定界法求解一个极大化的整数规划问题，当得到多于一个可行解时，通常任取其 中一个作为下界。C. 用割平面法求解整数规划时，构造的割平面可能割去一些不属于最优解的整数解。D. 用割平面法求解整数规划问题时，必须首先将原问题的非整数

4、的约束系数及右端常数化 为整数。2在求解整数规划问题时，可能出现的是（ ）。A唯一最优解B.无可行解C多重最佳解D.无穷多个最优解 3关于分配问题的下列说法正确的是_ ABD。A. 分配问题是一个高度退化的运输问题B. 可以用表上作业法求解分配问题C. 从分配问题的效益矩阵中逐行取其最小元素，可得到最优分配方案D. 匈牙利法所能求解的分配问题，要求规定一个人只能完成一件工作，同时一件工作也只 给一个人做。4. 整数规划类型包括（）A 线性规划 B 非线性规划 C 纯整数规划 D 混合整数规划E 01规划5. 对于某一整数规划可能涉及到的解题内容为（）A 求其松弛问题B 在其松弛问题中增加一个约

5、束方程C应用单形或图解法D割去部分非整数解E多次切割四、名词1、纯整数规划2、01规划问题3、混合整数规划五、下列整数规划问题Max Z=20X +10X +10X123f 2X +20X +4X W15123S.t 6X +20X +4X =20123, 乂拯2拯3三0且为整数说明能否用先求解相应的线性规划问题然后四舍五入的办法来求得该整数规划的一个可行 解。六、某运输公司在春运期间需要24小时昼夜加班工作，需要的人员数量如下表所示：起运时间服务员数264610810 1410141871822122224每个工作人员连续工作八小时，且在时段开始时上班，问如何安排，使得既满足以上要求又使上班

6、人数最少?七、某畜产品公司计划在市区的东、西、南、北四区建立销售门市部，拟议中有10个位置 Ai(i = l, 2, 3,，10)可供选择，考虑到各地区居民的消费水平及居民居住密集度，规定: 在东区由Al, A2, A3三个点中至少选择两个；在西区由A4, A5两个点中至少选一个；在南区由A6, A7两个点中至少选一个；在北区由A8, A9, A10三个点中至多选两个。Ai 各点的设备投资及每年可获利润由于地点不同都是不一样的,预测情况见下表(单 位:万元)所示。A1 A2A3A4A5A6A7A8A9A10投资额110130160908010090150170190利润3135 4517152

7、520435356但投资总额不能超过820万元,问应选择哪几个销售点,可使年利润为最大?建立上述问题的整数规划模型。八、考虑下述规划问题：min Z = fi(I” f2(3)120 + 5 x其中，4（叮1约束条件为：if x 01if x = 0112 + 6 x20ififx 02 。模型的约束x =02 或者x 10，或者x 15 1 2 下列各不等式至少有一个成立：1x + x 1512x + 2 x 15121 x1 - x2 或5 或 I。； x 0 ， x 0 12试建立此问题的整数线性规划模型。九、用分枝定界法求解max z = x + x129,51x + x 114 21

8、4st 1 -2x + x 0且为整数12十、用割平面法求解max z = x + x122 x + x 61 24x + 5x 012x , x g Z12十一、一个登山队员，他需要携带的物品有：食品、氧气、冰镐、绳索、帐篷、照 相器材、通信器材等，每种物品的重量及重要性系数见表所示，能携带的最大重量 为25 kg ,试选择该队员所应携带的物品。序号1234567物品食品氧气冰镐绳索帐篷照相器材通信设 备重量kg55251023重要性系数201516148149十二、用隐枚举法求解max z = 4x + 3x +2x,123加一5叭十十眄十先q 3 a1耳囂也屯=0或1十三、用割平面法求解下面整数规划。maKZ=7x14-9jc 一兔十空珏M虚 M 丁五十比35 耳帀邛且为整数（下表为最优表）7900bCXxX、X.97x20121037/22 1/221/223/227/29/2c zjj100 28/11 15/11十四、用割平面法求解2 + Xj 64x.+5i,20sl.乓斗0勺1100b巧15/3105/6 1/618/301 2/31/300 1/6 1/6