运筹学复习题库WORD版

第 1 页 共 8 页 第 2 页 共 8 页填空题1线性规划问题中，如果在约束条件中出现等式约束，我们通常用增加_的方法来产生初始可行基。 2线性规划模型有三种参数，其名称分别为价值系数、_和_。3原问题的第 1 个约束方程是“=”型，则对偶问题相应的变量是_变量。4求最小生成树问题，常用的方法有：避圈法和 _。 5排队模型 MM2 中的 M，M，2 分别表示到达时间为_分布，服务时间服从负指数分布和服务台数为 2。6如果有两个以上的决策自然条件，但决策人无法估计各自然状态出现的概率，那么这种决策类型称为_型决策。7在风险型决策问题中，我们一般采用_来反映每个人对待风险的态度。8目标规划总是求目标函数的_信，且目标函数中没有线性规划中的价值系数，而是在各偏差变量前加上级别不同的_。判断题： 1、在互为对偶的一对原问题与对偶问题中，不管原问题是求极大还是极小，原问题可行解的目标函数值一定超过其对偶问题可行解的目标函数值。 （ ）2、如线性规划问题存在可行域，则可行域一定包含坐标的原点。 （ ）3、含 n 个变量 m 个约束的标准型线性规划问题，基解数恰好为 个。 （ ）mCn4、若 , 分别是某一线性规划的最优解，则 也是该线性规划问题的最1X2 21)(XX优解，其中 。 （ ）05、如果线性规划的原问题存在可行解，则其对偶问题也一定存在可行解。 （ ）6、任何线性规划问题具有唯一的对偶问题。 （ ）7、单纯形法计算中选取最大正检验数 对应的变量 作为换入基的变量，将使迭代后的目标函kkx数得到最快的增长。 （ ）8、如果线性规划的对偶问题无可行解，则原问题也一定无可行解。 （ ）9、原问题求最大值，第 i 个约束是 “”约束，则该约束条件对应的对偶变量 yi 0 。 （ ）10、对取值无约束的变量 xj，通常令 ，其中 ，在用单纯形法求jjxj 0,jjx得的最优解中，有可能同时出现 （ ）0,jjx11、线性规划问题标准形式的数学模型的目标函数是求最小值。 （ ）2、如线性规划问题存在可行域，则可行域是一个凸集。 （ ）3、对偶单纯形法就是求解对偶问题的单纯形法。 （ ）4、构成运输问题初始方案的基变量的个数是 m 个。 （ ）5、如果线性规划的原问题存在可行解，则其对偶问题也一定存在可行解。 （ ）6、运输问题中的非基变量的闭回路是存在而且是唯一的。 （ ）7、在互为对偶的一对原问题与对偶问题中，如果一问题的变量取值非 0，则其对偶问题的约束条件取严格的不等式。 （ ）8、分配问题效率表中某一行元素分别加上（减去）一个常数，则最优解不变。 （ ）9、原问题求最大值，某约束是“” 约束，则该约束条件对应的对偶变量 0。 （ ）10、目标规划问题中的约束条件有刚性约束和柔性约束。 （ ）单项选择题： 1、互为对偶的两个线性规划问题的解存在关系 （ ）A、原问题具有无界解，则对偶问题无可行解 B、对偶问题无可行解，原问题具有无界解C、若最优解存在，则最优解相同D、一个问题无可行解，则另一个问题也无可行解2、线性规划具有唯一最优解是指 （ ）A、最优表中存在常数项为零 B、最优表中非基变量检验数全部非零C、最优表中存在非基变量的检验数为零 D、可行解集合有界3、原问题有 6 个变量 4 个约束，其对偶问题 （ ）A、有 4 个变量 6 个约束 B、有 6 个变量 4 个约束C、有 6 个变量 6 个约束 D、有 4 个变量 4 个约束4、具有 n 个顶点的树的边数恰好为 （ ）A、(n-1) 条 B、n 条C、(n+1)条 D、(n+2) 条第 3 页 共 8 页 第 4 页 共 8 页5、有 4 个产地 5 个销地的平衡运输问题模型具有特征 （ ）A、有 9 个变量 B、有 20 个约束C、有 8 约束 D、有 8 个基变量6、X 是线性规划的基本可行解则有 （ ）A、X 中的基变量非零，非基变量为零 B、X 不一定满足约束条件C、X 中的基变量非负，非基变量为零 D、X 是最优解1、互为对偶的两个线性规划问题的变量存在关系 （ ）A、在一个问题中是变量，则在另一问题中也是变量B、在一问题中是基变量，则在另一问题中也是基变量C、在一问题中是非基变量，则在另一问题中也是非基变量D、在一问题中是基解变量，则在另一问题中是非基解变量2、线性规划具有多个最优解是指 （ ）A、最优表中存在常数项为零 B、最优表中非基变量检验数全部非零C、最优表中存在非基变量的检验数为零 D、可行解集合有界3、原问题有 5 个变量 4 个约束，其对偶问题 （ ）A、有 4 个变量 4 个约束 B、有 5 个变量 5 个约束C、有 4 个变量 5 个约束 D、有 5 个变量 4 个约束4、 是关于可行流 f 的一条增广链，则在 上有 （ ）A、对任意 B、对任意C、对任意 D、.对任意 0,),(ijfji有5、关于树的性质，不正确的有 （ ）A、树图是连通图 B、具有 n 个顶点的树图的边数恰好为（n-1）条C、具有 n 个顶点的树图的边数恰好为 n 条 D、任何树图中必存在次为 1 的点6、有 4 个产地 4 个销地的平衡运输问题模型具有特征 （ ）A、有 8 个变量 B、有 16 个约束C、有 4 个约束 D、有 7 个基变量7、互为对偶的两个线性规划若存在最优解，则存在关系 （ ）A、Z W B、Z = WC、Z W D、ZW8、线性规划的约束条件为则初始基可行解为 （ ）A、(0, 2, 3, 2) B、(3, 0, -1, 0)C、(0, 0, 5, 6) D、(2, 0, 1, 2)9、 （ ）A、无可行解 B、有唯一最优解 C、有多重最优解 D、有无界解10、X 是线性规划的基本可行解则有 （ ）A、X 中的基变量非零，非基变量为零 B、X 不一定满足约束条件C、X 中的基变量非负，非基变量为零 D、X 是最优解9使用人工变量法求解极大化线性规划问题时，当所有的检验数 在基变量中仍含有非零的人工变量，表明该线性规划问题 【 】A有唯一的最优解 B有无穷多最优解C为无界解 D无可行解10对偶单纯形法解最大化线性规划问题时，每次迭代要求单纯形表中 【 】Ab 列元素不小于零 B检验数都大于零C检验数都不小于零 D检验数都不大于零 11已知某个含 10 个结点的树图，其中 9 个结点的次为 1，1，3，1，1，1，3，1，3，则另一个结点的次为 【 】A3 B2 C1 D以上三种情况均有可能12如果要使目标规划实际实现值不超过目标值。则相应的偏离变量应满足【 】13在运输方案中出现退化现象，是指数字格的数目 【 】A等于 m+n B等于 m+n-1第 5 页 共 8 页 第 6 页 共 8 页C小于 m+n-1 D大于 m+n-116关于线性规划的原问题和对偶问题，下列说法正确的是 【 】A若原问题为元界解，则对偶问题也为无界解B若原问题无可行解，其对偶问题具有无界解或无可行解c若原问题存在可行解，其对偶问题必存在可行解D若原问题存在可行解，其对偶问题无可行解18下列说法正确的是 【 】A线性规划问题的基本解对应可行域的顶点也必是该问题的可行解D单纯形法解标准的线性规划问题时，按最小比值原则确定换出基变量是为了保证迭代计算后的解仍为基本可行解简答题：1、 简述单纯形法的基本思路。2、简述对偶单纯形法的基本思路。3、简述运输问题求解的基本思路。4、写出下列线性规划问题的对偶问题。5、将下列线性规划问题化为标准形式四、计算题：1、有份说明书，要分别译成英、日、德、俄四种文字，交给甲、乙、丙、丁四个人去完成，应如何分配，使四个人分别完成这四项任务总的时间为最小？人 工作 甲 乙 丙 丁译英 2 10 9 7译日 15 4 14 8译德 13 14 16 11译俄 4 15 13 92、请用破圈法或避圈法求下图的最小部分树。3、 已知线性规划（20 分）MaxZ=3X1+4X2X1+X2 52X1+4X2123X1+2X28X1,X20其最优解为：基变量 X1 X2 X3 X4 X5X3 3/2 0 0 1 -1/8 -1/4X2 5/2 0 1 0 3/8 -1/4X1 1 1 0 0 -1/4 1/2j 0 0 0 -3/4 -1/21） 写出该线性规划的对偶问题。2） 若 C2 从 4 变成 5，最优解是否会发生改变，为什么？3） 若 b2 的量从 12 上升到 15，最优解是否会发生变化，为什么？4） 如果增加一种产品 X6，其 P6=(2,3,1)T，C 6=4 该产品是否应该投产？为什么？4、已知运输问题的调运和运价表如下，求最优调运方案和最小总费用。0,1562.3211xtsxMaxZ0，y35224.tsy16MinW121第 7 页 共 8 页 第 8 页 共 8 页销地产地B1 B2 B3 产量A1 5 9 2 15A2 3 1 7 11A3 6 2 8 20销量 18 12 164、 、某公司要把 4 个有关能源工程项目承包给 4 个互不相关的外商投标者，规定每个承包商只能且必须承包一个项目，试在总费用最小的条件下确定各个项目的承包者，总费用为多少？各承包商对工程的报价如表 2 所示： 项目投标者A B C D甲 15 18 21 24乙 19 23 22 18丙 26 17 16 19丁 19 21 23 175、求解下列线性规划问题。6、用匈牙利法求解下列分配问题。7、用标号法算法求下图中 s 至