运筹学总复习题

1、线性规划部分1 .试述线性规划问题的可行解、基础解、基可行解、最优解的概念及其相互关系2 .对偶问题和禺变量（即影子价值）的经济意义是什么？什么是资源的影子价格 ？它与相 应的市场价格有什么区别 ？3 .如何根据原问题和对偶问题之间的对应关系，找出两个问题变量之间、解及检验数之间的关系？4 .试述整数规划分枝定界法的思路5 .线性规划具有无界解是指（C）A.可行解集合无界B.有相同的最小比值C.存在某个检验数k 0,永 0,（i 1,2,L ,m）D.最优表中所有非基变量的检验数非零6 .线性规划具有唯一最优解是指（A）A.最优表中非基变量检验数全部非零B.不加入人工变量就可进行单纯形法计算C

2、.最优表中存在非基变量的检验数为零D.可行解集合有界7 .线性规划具有多重最优解是指（B）A.目标函数系数与某约束系数对应成比例B.最优表中存在非基变量的检验数为零C.可行解集合无界D.基变量全部大于零8 .线性规划的退化基可行解是指（B）A.基可行解中存在为零的非基变量B.基可行解中存在为零的基变量C.非基变量的检验数为零D.所有基变量不等于零9 .线性规划无可行解是指（C）A.第一阶段最优目标函数值等于零B.进基列系数非正C.用大M法求解时，最优解中还有非零的人工变量D.有两个相同的最小比值10 .若线性规划不加入人工变量就可以进行单纯形法计算（B）A. 一定有最优解B. 一定有可行解C.

3、可能无可行解D.全部约束是小于等于的形式11 .线性规划可行域的顶点-一定是（A）A. 可行解B.非基本解 C.非可行D.是最优解12 .X是线性规划的基本可行解则有（A）A.X中的基变量非负，非基变量为零B.X中的基变量非零，非基变量为零C. X不是基本解D.X不一定满足约束条件13 .下例错误的说法是（C）A.标准型的目标函数是求最大值B.标准型的目标函数是求最小值C.标准型的常数项非正D.标准型的变量一定要非负14 .为什么单纯形法迭代的每一个解都是可行解？答：因为遵循了下列规则（A）A.按最小比值规则选择出基变量B.先进基后出基规则C.标准型要求变量非负规则D.按检验数最大的变量进基规

4、则15 .线性规划标准型的系数矩阵A mx n,要求 （B）A.秩（A）=m 并且 m<nB. 秩（A）=m 并且 m<=nC.秩（A）=m 并且 m=n D. 秩（A）=n 并且 n<m16 .下例错误的结论是（D）A.检验数是用来检验可行解是否是最优解的数B.检验数是目标函数用非基变量表达的系数C.不同检验数的定义其本验标准也不同D.检验数就是目标函数的系数17 .对偶单纯形法的最小比值规划则是为了保证（B）A.使原问题保持可行B.使对偶问题保持可行C.逐步消除原问题不可行性D.逐步消除对偶问题不可行性18 .互为对偶的两个线性规划问题的解存在关系（A）A. 一个问题具有

5、无界解，另一问题无可行解B原问题无可行解，对偶问题也无可行解C.若最优解存在，则最优解相同D.一个问题无可行解，则另一个问题具有无界解19 .原问题与对偶问题都有可行解，则（D）A.原问题有最优解，对偶问题可能没有最优解B.原问题与对偶问题可能都没有最优解C.可能一个问题有最优解，另一个问题具有无界解D.原问题与对偶问题都有最优解20 .某个常数bi波动时，最优表中引起变化的有（A）一 一 _ 1 一“一”A.B 1b B. Cn CbB NC. B 1D. B 1N21 .当基变量Xi的系数Ci波动时，最优表中引起变化的有（B）A.最优基B B.所有非基变量的检验数C.第i列的系数Ni D.

6、基变量Xb22 .当非基变量Xj的系数Cj波动时，最优表中引起变化的有（C ）A.00单纯形乘子B.目标值 C.非基变量的检验数D. 常数项23 .若线性规划问题的最优解同时在可行解域的两个顶点处达到，那么该线性规划问题最优 解为（C ）A.两个B.零个C.无穷多个D.有限多个24 .原问题与对偶问题的最优（B ）相同。A.解B.目标值C.解结构D.解的分量个数25 .若原问题中为为自由变量，那么禺问题中的第i个约束一定为（A ）A.等式约束B . “W型约束 C . 约束 D .无法确定26 .线性规划中，满足非负条件的基本解，称为基本可行解 ,对应的基称为 可行基。27 .线性规划的目标函

7、数的系数是其对偶问题的最右边；而若线性规划为最大化问题，则对偶问题为 最小化。28 .考虑线性规划问题：max z 2x1 4x2 3x33% 4x2 2x3 602为 x2 2x3 40s.t. x1 3x2 2x380为区供 0（a）：写出其对偶问题；（b）：用单纯形方法求解原问题；（c）：用对偶单纯形方法求解其对偶问题；（d）：比较（b） （c）计算结果。29.试述单纯形法的计算步骤，并说明如何在单纯形表上判断问题是具有唯一最优解、无穷多最优解和无有限最优解。30.设线性规划的约束条件为x1x2x32x12x2 x44x1,L , x40则基本可行解为A (0, 0, 4, 3)B (3

8、, 4, 0, 0)C (2, 0, 1, 0)D (3, 0, 4, 0)C）31 互为对偶的两个线性规划 maxz CX,AX b,X 0, 及 minw Yb,YA C,Y 0,对任意可行解X和Y,存在关系（D）A Z > W B Z = WC. Z> W D. ZWW32 .互为对偶的两个线性规划问题的解存在关系 （ B ）A 原问题无可行解，对偶问题也无可行解B 对偶问题有可行解，原问题可能无可行解C 若最优解存在，则最优解相同D 一个问题无可行解，则另一个问题具有无界解1233 .已知最优基B， CB=（ 3 ， 6） ，则对偶问题的最优解是（3， 0 ）3734.在资

9、源优化的线性规划问题中，某资源有剩余，则该资源影子价格等于（0 ）35.将目标函数 max z x1 5x2转化为求极小值是（-Z=-x1+5x2 ）36 .原问题有5个变量 3 个约束，其对偶问题 （ A）A 有 3 个变量 5 个约束B 有 5 个变量 3 个约束C.有5个变量5个约束 D.有3个变量3个约束37 .互为对偶的两个问题存在关系（ D ）A 原问题无可行解，对偶问题也无可行解B 对偶问题有可行解，原问题也有可行解C 原问题有最优解解，对偶问题可能没有最优解D 原问题无界解，对偶问题无可行解38 .对偶变量的最优解就是（影子）价格运输问题部分1.有 6 个产地 7 个销地的平衡

10、运输问题模型的对偶模型具有特征（ D ）A 有 12 个变量B 有 42 个约束2.有 5 个产地 4 个销地的平衡运输问题A.有9个变量B.有9个基变量C. 有 13 个约束（ D）m+n-1C. 有 20 个约束D 有 13 个基变量D 有8 个基变量3.m+n 1 个变量构成一组基变量的充要条件是A.m+n 1 个变量恰好构成一个闭回路（B）B.m+n 1 个变量不包含任何闭回路性相关4.运输问题C.m+n1 个变量中部分变量构成一个闭回路D.m+n 1 个变量对应的系数列向量线(A)A.是线性规划问题B.不是线性规划问题C.可能存在无可行解D.可能无最优解 5.若运输问题已求得最优解，

11、此时所求出的检验数一定是全部（ D） 目标函数最小化问 题 A .小于或等于零B.大于零C.小于零D.大于或等于零6.对于m个发点、n个收点的运输问题，叙述错误的是（D ）A .该问题的系数矩阵有 mxn列B.该问题的系数矩阵有 m+n行C.该问题的系数矩阵的秩必为m+n-1D.该问题的最优解必唯一5.下列结论正确的有（A）A运输问题的运价表第 r行的每个cj同时加上一个非零常数 k,其最优调运方案不变 B运输问题的运价表第 p列的每个cj同时乘以一个非零常数 k,其最优调运方案不变 C.运输问题的运价表的所有 cj同时乘以一个非零常数 k,其最优调运方案变化 D .不平衡运输问题不一定存在最

12、优解 6.在运输问题型中，m n 1个变量构成基变量的充要条件m+n 1个变量不包含任何闭回路。 7.在求运费最少的调度运输问题中，如果某一非基变量的检验数为4,则说明如果在该空格中增加一个运量，运费将增加4 Q8 .设运输问题求最大值，则当所有检验数（小于等于0 ）时得到最优解。9 .用表上作业法求解下表中的运输问题：、肖地 加工产BiBB产 量Ai51812A24114A361 74销量91011目标规划(B)1.要求不超过第一目标值、恰好完成第二目标值，目标函数是A. min Zp1dP2(d2d2)c min Zp1d1p2(d2d2)min ZpRip?(d2d2)D min Zp4

13、p2(d2 d2)2.目标函数min zP1(d1d2）Bd3的含义是(A)A.首先第一和第二目标同时不低于目标值，然后第三目标不低于目标值B.第一、第二和第三目标同时不超过目标值C.第一和第二目标恰好达到目标值，第三目标不超过目标值D.首先第一和第二目标同时不超过目标值，然后第三目标不超过目标值3.下列线性规划与目标规划之间错误的关系是（B）A.线性规划的目标函数由决策变量构成，目标规划的目标函数由偏差变量构成B.线性规划模型不包含目标约束，目标规划模型不包含系统约束C.线性规划求最优解，目标规划求满意解D.线性规划模型只有系统约束，目标规划模型可以有系统约束和目标约束E.线性规划求最大值或

14、最小值，目标规划只求最小值5 .某计算机公司生产 A,B,C 3种型号的笔记本电脑。这3种笔记本电脑需要在复杂的装配线上生产，生产一台A,B,C型号的笔记本电脑分别需要5小时、8小时、12小时。公司装配线正常的生产时间是每月 1 700小时，公司营业部门估计 A,B,C 3种笔记本电脑每台的利润分别 是1 000元、1 440元、2 520元，而公司预测这个月生产的笔记本电脑能够全部售出。公司经理考虑以下目标。第一目标：充分利用正常的生产能力，避免开工不足；第二目标：优先满足老客户的需求，A,B,C 3种型号的电脑各为 50台、50台、80台，同时 根据3种电脑的纯利润分配不同的加权系数 ；第

15、三目标：限制装配线加班时间，最好不超过200小时；第四目标：满足各种型号电脑的销售目标 ，A,B,C 3种型号分别为100台、120台、100台, 再根据3种电脑的纯利润分配不同的加权系数；第五目标：装配线加班时间尽可能少。请列出相应的目标规划模型，并用LINGO软件求解。6 .已知3个工厂生产的产品供应给 4个客户，各工厂生产量、用户需求量及从各工厂到用户的 单位产品的运输费用如表所示。由于总生产量小于总需求量，上级部门经研究后，制定了调配方案的8个目标，并规定了重要性的次序。工厂1用户表，厂产量一用户需求量及运费单价 单位：兀/单位用户15用户22用户36用户4生产量7工厂23546工厂3

16、4523需求量（单位）200100450250第一目标：用户4为重要部门，需求量必须全部满足；第二目标：供应用户1的产品中，工厂3的产品不少于100个单位；第三目标：每个用户的满足率不低于 80%；第四目标：应尽量满足各用户的需求；第五目标：新方案的总运费不超过原运输问题（线性规划模型）的调度方案的10%；第六目标：因道路限制，工厂2到用户4的路线应尽量避免运输任务；第七目标：用户1和用户3的满足率应尽量保持平衡；第八目标：力求减少总运费。请列出相应的目标规划模型，并用LINGO软件求解。7 .已知条件如表所示。工序产品型号ABI （小时/台）56n （小时/台）33利润（元/台）310455

17、每周可用生产时间（小时）20085如果工厂经营目标的期望值和优先等级如下：P1 :每周总利润不得低于10 000元；P2：因合同要求，A型机每周至少生产15台,B型机每周至少生产 20台；P3：希望工序I的每周生产时间正好为200小时，工序n的生产时间最好用足，甚至可适当加班。试建立这个问题的目标规划模型，并用LINGO软件求解。整数规划部分1 .下列说法正确的是(D)A.整数规划问题最优值优于其相应的线性规划问题的最优值B.用割平面法求解整数规划问题，构造的割平面有可能切去一些不属于最优解的整数解C.用分枝定界法求解一个极大化的整数规划时, 其中一个作为下界，再进行比较剪枝当得到多于一个可行

18、解时，通常可任取D.分枝定界法在处理整数规划问题时，借用线性规划单纯形法的基本思想,在求相应的线性模型解的同时, 代求出最优解。2 .分枝定界法中逐步加入对各变量的整数要求限制，从而把原整数规划问题通过分枝迭(B)a.最大值问题的目标值是各分枝的下界 c.最小值问题的目标值是各分枝的上界 e.以上结论都不对b.最大值问题的目标值是各分枝的上界 d.最小值问题的目标值是各分枝的下界A. a,bB. b,dC.c,dD. e3 .有4名职工，由于各人的能力不同 示。,每个人做各项工作所用的时间不同，所花费时间如表所ABCD15182124192322182617161919212317单位:分钟，

19、可使总的消耗时间最少？问指派哪个人去完成哪项工作50人,周五至少需要 804.某部门一周中每天需要不同数目的雇员：周一到周四每天至少需要人，周六周日每天至少需要 90人，现规定应聘者需连续工作5天,试确定聘用方案，即周一到周日每天聘用多少人，使在满足需要的条件下聘用总人数最少。5.离散性选址问题。某一城区设有 7个分销网点，它们之间的交通路线情况如图所示。求出各分销商之间的最短距离如表1所示。表 1 各分销商之间的最短距离矩阵ABCDEFGA03557810B3032457C5305679D5250235E7462013F8573102G10795320(1)现规划一座仓库,覆盖这 7 个区域

20、的需求,试用中心法确定仓库选址 ,使得运送路径最短。(2)如果又已知各区的每周销售能力如表2 列示,公司希望设立一个仓储中心,向各区销售商发送产品,试寻求网络重心,使总运输成本最低。区域ABCDEF周销售能力400350450300250350表 2 各区的每周销售能力G500网络优化部分1平是关于可行流f的一条增广链，则在科上有"D"A. 对一切 (i, j) ，有 fijcijB.对一切(i, j) ,有 fijCijC.对一切(i, j) ,有 fijCijD.对一切(i, j) ，有 fij02 . 下列说法正确的是A.割集是子图B.割量等于割集中弧的流量之和C.割

21、量大于等于最大流量D.割量小于等于最大流量3 .下列错误的结论是A. 容量不超过流量B. 流量非负C.容量非负D.发点流出的合流等于流入收点的合流4 .下列正确的结论是A. 最大流等于最大流量B.可行流是最大流当且仅当存在发点到收点的增广链C.可行流是最大流当且仅当不存在发点到收点的增广链D. 调整量等于增广链上点标号的最大值5 .下列正确的结论是A.最大流量等于最大割量B.最大流量等于最小割量C.任意流量不小于最小割量D.最大流量不小于任意割量6 .连通图 G 有 n 个点，其部分树是T ，则有A.T 有 n 个点 n 条边 B.T 的长度等于G 的每条边的长度之和C.T 有 n 个点 n 1 条边 D.T 有 n 1 个点 n 条边7 .若 P 为网络 G 的一条流量增广链，则 P 中所有正向弧都为 G 的( )A.对边B.饱和边8.在图论方法中，通常用C.邻边D.不饱和边表示人们研究的对象，用 表示对象之间的某目前的网络流方案是否合理 （是否需要进行调整）敦口果需要进行调整，应如何调整改进？联系。9.在图的网络中，弧旁的数字表示距离，试用狄克斯特拉标号法求 vs到vt的最短路径和最短路11.对下图中的网络，分别用破圈法和避圈法求最短树。决策分析部分1.