线性规划习题(11)

2．在求解整数规划问题时，可能出现的是 ABC。 A．唯一最优解 B．无可行解 C．多重最佳解 D．无穷多个最优解 3．关于分配问题的下列说确的是_ ABD。 A．分配问题是一个高度退化的运输问题 B．可以用表上作业法求解分配问题 C．从分配问题的效 益矩阵中逐行取其最小元素，可得到最优分配方案 D．匈牙利法所能求解的分配问题，要求规定一个人只 能完成一件工作，同时一件工作也只给一个人做。 4.整数规划类型包括（ CDE ） A 线性规划 B 非线性规划 C 纯整数规划 D 混合整数规划 E 0—1 规划 5.对于某一整数规划可能涉及到的解题内容为（ ABCDE ） A 求其松弛问题 B 在其松弛问题中增加一个约束方程 C 应用单形或图解法 D 割去部分 非整数解 E 多次切割 三、名词 1、纯整数规划：如果要求所有的决策变量都取整数，这样的问题成为纯整数规划问题。 2、0—1 规划问题：在线性规划问题中，如果要求所有的决策变量只能取 0 或 1，这样的问题称为 0—1 规 划。 3、混合整数规划：在线性规划问题中，如果要求部分决策变量取整数，则称该问题为混合整数规划。 四、用分枝定界法求解下列整数规划问题：(提示:可采用图解法) maxZ=40x1+90x2

五、用割平面法求解

六、下列整数规划问题

说明能否用先求解相应的线性规划问题然后四舍五入的办法来求得该整数规划的一个可行解。 答：不考虑整数约束，求解相应线性规划得最优解为 x1=10/3，x2=x3=0，用四舍五人法时，令 x1=3， x2=x3=0，其中第 2 个约束无法满足，故不可行。 七、若某钻井队要从以下 10 个可供选择的井位中确定 5 个钻井探油。使总的钻探费用为最小。若 10 个井 位的代号为 S1,S2．?，S10 相应的钻探费用为 C1 ,C2 ,? C10，并且井位选择要满足下列限制条件： (1)在 s1，s2，S4 中至多只能选择两个； (2)在 S5，s6 中至少选择一个；(3)在 s3，s6，S7，S8 中至少选

择两个；

试建立这个问题的整数规划模型

八、有四项工作要甲、乙、丙、丁四个人去完成．每项工作只允许一人去完成。每个人只完成其中一项工 作，已知每个人完成各项工作的时间如下表。问应指派每个人完成哪项工作，使总的消耗时间最少? 工作 人 甲 乙 丙 丁 15 19 6 19 18 23 7 21 2l 22 16 23 24 18 19 17 I Ⅱ Ⅲ Ⅳ

第八章

图与网络分析

一、填空题 1．图的最基本要素是点、点与点之间构成的边 2．在图论中，通常用点表示，用边或有向边表示研究对象，以及研究对象之间具有特定关系。 3．在图论中，通常用点表示研究对象，用边或有向边表示研究对象之间具有某种特定的关系。 4．在图论中，图是反映研究对象_之间_特定关系的一种工具。 5．任一树中的边数必定是它的点数减 1。 6．最小树问题就是在网络图中，找出若干条边，连接所有结点，而且连接的总长度最小。 7．最小树的算法关键是把最近的未接_结点连接到那些已接结点上去。 8．求最短路问题的计算方法是从 0≤fij≤cij 开始逐步推算的，在推算过程中需要不断标记平衡和最短路线。 二、单选题 1、关于图论中图的概念，以下叙述(B)正确。 A 图中的有向边表示研究对象，结点表示衔接关系。 B 图中的点表示研究对象，边表示点与点之间的关 系。C 图中任意两点之间必有边。 D 图的边数必定等于点数减 1。 2．关于树的概念，以下叙述(B)正确。 A 树中的点数等于边数减 1 B 连通无圈的图必定是树 C 含 n 个点的树是唯一的 D 任一树中， 去掉一条边仍为树。 3．一个连通图中的最小树(B)，其权(A)。