1、1线性规划部分1. 试述线性规划问题的可行解、基础解、基可行解、最优解的概念及其相互关系2. 对偶问题和对偶变量(即影子价值 )的经济意义是什么? 什么是资源的影子价格? 它与相应的市场价格有什么区别?3. 如何根据原问题和对偶问题之间的对应关系,找出两个问题变量之间、解及检验数之间的关系?4. 试述整数规划分枝定界法的思路5.线性规划具有无界解是指 (C) A.可行解集合无界 B.有相同的最小比值 C.存在某个检验数 0,(12,)kikamD.最优表中所有非基变量的检验数非零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.一定有最优解
3、B.一定有可行解 C.可能无可行解 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.
4、标准型要求变量非负规则 D.按检验数最大的变量进基规则15.线性规划标准型的系数矩阵 Amn， 要求 (B)A.秩(A)=m 并且 m W BZ = WCZW DZW32.互为对偶的两个线性规划问题的解存在关系 （B）A原问题无可行解，对偶问题也无可行解B对偶问题有可行解，原问题可能无可行解C若最优解存在，则最优解相同D一个问题无可行解，则另一个问题具有无界解33.已知最优基 ，C B=（3，6) ，则对偶问题的最优解是（ 3，0 ）12734.在资源优化的线性规划问题中，某资源有剩余，则该资源影子价格等于（ 0 ）35.将目标函数 转化为求极小值是（-Z=-x1+5x2）12max5z36.
5、原问题有 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 个 销 地 的 平 衡 运 输 问 题 模 型 的 对 偶 模 型 具 有 特 征 （ D） A 有 12 个 变 量 B 有 42 个 约 束 C. 有
6、13 个 约 束 D 有 13 个 基 变 量2.有 5 个 产 地 4 个 销 地 的 平 衡 运 输 问 题 （D） m+n-1A.有 9 个 变 量 B.有 9 个 基 变 量 C. 有 20 个 约 束 D 有 8 个 基 变 量3.m+n1 个变量构成一组基变量的充要条件是 (B)A.m+n1 个变量恰好构成一个闭回路 B.m+n1 个变量不包含任何闭回路C.m+n1 个变量中部分变量构成一个闭回路 D.m+n1 个变量对应的系数列向量线性相关 4.运输问题 (A)4A.是线性规划问题 B.不是线性规划问题 C.可能存在无可行解 D.可能无最优解5.若运输问题已求得最优解，此时所求出
7、的检验数一定是全部（D） 目标函数最小化问题 A小于或等于零 B大于零 C小于零 D大于或等于零 6.对于 m 个发点、n 个收点的运输问题，叙述错误的是 ( D )A该问题的系数矩阵有 mn 列 B该问题的系数矩阵有 m+n 行C该问题的系数矩阵的秩必为 m+n-1 D该问题的最优解必唯一5.下列结论正确的有 （A）A 运输问题的运价表第 r 行的每个 cij 同时加上一个非零常数 k，其最优调运方案不变B 运输问题的运价表第 p 列的每个 cij 同时乘以一个非零常数 k，其最优调运方案不变 C.运输问题的运价表的所有 cij 同时乘以一个非零常数 k, 其最优调运方案变化 D 不平衡运输
8、问题不一定存在最优解6.在运输问题模型中， 个变量构成基变量的充要条件 m+n1 个变量不包含任何1mn闭回路。7.在求运费最少的调度运输问题中，如果某一非基变量的检验数为 4，则说明如果在该空格中增加一个运量，运费将增加 4 。8设运输问题求最大值，则当所有检验数（ 小于等于 0 ）时得到最优解。9.用表上作业法求解下表中的运输问题： 销 地 加 工 厂 B1 B2 B3 产量 A1 2 A3 5 23 1 46 8 17 124 销 量 9101 目标规划1.要求不超过第一目标值、恰好完成第二目标值，目标函数是 （B） A. )(min221dpdZB. )(min221dpdZC.D.2
9、.目标函数 的含义是 （A）123i()zPA. 首先第一和第二目标同时不低于目标值，然后第三目标不低于目标值 B.第一、第二和第三目标同时不超过目标值 C.第一和第二目标恰好达到目标值，第三目标不超过目标值 D.首先第一和第二目标同时不超过目标值，然后第三目标不超过目标值3.下列线性规划与目标规划之间错误的关系是 （B）A.线性规划的目标函数由决策变量构成，目标规划的目标函数由偏差变量构成B.线性规划模型不包含目标约束，目标规划模型不包含系统约束C.线性规划求最优解，目标规划求满意解D.线性规划模型只有系统约束，目标规划模型可以有系统约束和目标约束E.线性规划求最大值或最小值，目标规划只求最
10、小值55.某计算机公司生产 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 种电脑的纯利润分配
11、不同的加权系数;第三目标:限制装配线加班时间 ,最好不超过 200 小时;第四目标:满足各种型号电脑的销售目标 ,A,B,C 3 种型号分别为 100 台、120 台、100台,再根据 3 种电脑的纯利润分配不同的加权系数;第五目标:装配线加班时间尽可能少。请列出相应的目标规划模型,并用 LINGO 软件求解。6.已知 3 个工厂生产的产品供应给 4 个客户,各工厂生产量、用户需求量及从各工厂到用户的单位产品的运输费用如表所示。由于总生产量小于总需求量,上级部门经研究后,制定了调配方案的 8 个目标,并规定了重要性的次序。表 工厂产量用户需求量及运费单价单位:元/单位用户工厂 用户 1 用户
12、2 用户 3 用户 4 生产量工厂 1 5 2 6 7工厂 2 3 5 4 6工厂 3 4 5 2 3需求量(单位) 200 100 450 250第一目标:用户 4 为重要部门 ,需求量必须全部满足;第二目标:供应用户 1 的产品中 ,工厂 3 的产品不少于 100 个单位;第三目标:每个用户的满足率不低于 80%;第四目标:应尽量满足各用户的需求 ;第五目标:新方案的总运费不超过原运输问题 (线性规划模型)的调度方案的 10%;第六目标:因道路限制,工厂 2 到用户 4 的路线应尽量避免运输任务;第七目标:用户 1 和用户 3 的满足率应尽量保持平衡 ;第八目标:力求减少总运费。请列出相应
13、的目标规划模型,并用 LINGO 软件求解。7.已知条件如表所示。产品型号工 序A B每周可用生产时间( 小时)(小时/台 ) 5 6 200(小时/台 ) 3 3 85利润 (元/台 ) 310 455如果工厂经营目标的期望值和优先等级如下:P1:每周总利润不得低于 10 000 元;P2:因合同要求,A 型机每周至少生产 15 台,B 型机每周至少生产 20 台;P3:希望工序的每周生产时间正好为 200 小时,工序的生产时间最好用足 ,甚至可适6当加班。试建立这个问题的目标规划模型,并用 LINGO 软件求解。整数规划部分1.下列说法正确的是 （D）A.整数规划问题最优值优于其相应的线性
14、规划问题的最优值B.用割平面法求解整数规划问题，构造的割平面有可能切去一些不属于最优解的整数解 C.用分枝定界法求解一个极大化的整数规划时，当得到多于一个可行解时，通常可任取其中一个作为下界，再进行比较剪枝D.分枝定界法在处理整数规划问题时，借用线性规划单纯形法的基本思想，在求相应的线性模型解的同时，逐步加入对各变量的整数要求限制，从而把原整数规划问题通过分枝迭代求出最优解。 2.分枝定界法中 （B）a.最大值问题的目标值是各分枝的下界 b.最大值问题的目标值是各分枝的上界c.最小值问题的目标值是各分枝的上界 d.最小值问题的目标值是各分枝的下界e.以上结论都不对A. a,b B. b,d C
15、. c,d D. e3.有 4 名职工,由于各人的能力不同,每个人做各项工作所用的时间不同,所花费时间如表所示。单位:分钟时间 任务人员 A B C D甲 15 18 21 24乙 19 23 22 18丙 26 17 16 19丁 19 21 23 17问指派哪个人去完成哪项工作,可使总的消耗时间最少?4.某部门一周中每天需要不同数目的雇员:周一到周四每天至少需要 50 人,周五至少需要 80人,周六周日每天至少需要 90 人,现规定应聘者需连续工作 5 天,试确定聘用方案,即周一到周日每天聘用多少人,使在满足需要的条件下聘用总人数最少。5.离散性选址问题。某一城区设有 7 个分销网点,它们
16、之间的交通路线情况如图 所示。7求出各分销商之间的最短距离如表 1 所示。表 1 各分销商之间的最短距离矩阵A B C D E F GA 0 3 5 5 7 8 10B 3 0 3 2 4 5 7C 5 3 0 5 6 7 9D 5 2 5 0 2 3 5E 7 4 6 2 0 1 3F 8 5 7 3 1 0 2G 10 7 9 5 3 2 0(1)现规划一座仓库,覆盖这 7 个区域的需求,试用中心法确定仓库选址 ,使得运送路径最短。(2)如果又已知各区的每周销售能力如表 2 列示,公司希望设立一个仓储中心,向各区销售商发送产品,试寻求网络重心,使总运输成本最低。表 2 各区的每周销售能力区
17、域 A B C D E F G周销售能力 400 350 450 300 250 350 500网络优化部分1. 是关于可行流 f 的一条增广链，则在 上有 “D“A.对一切 ，有 B.对一切 ，有 (i,j)ijijfc(i,j)ijijfcC.对一切 ，有 D.对一切 ，有 ijij0ij2.下列说法正确的是 A.割集是子图 B.割量等于割集中弧的流量之和 C.割量大于等于最大流量 D.割量小于等于最大流量 3.下列错误的结论是 A.容量不超过流量 B.流量非负 C.容量非负 D.发点流出的合流等于流入收点的合流4.下列正确的结论是 A.最大流等于最大流量 B.可行流是最大流当且仅当存在发
18、点到收点的增广链 C.可行流是最大流当且仅当不存在发点到收点的增广链 D.调整量等于增广链上点标号的最大值5.下列正确的结论是 A.最大流量等于最大割量 B.最大流量等于最小割量C.任意流量不小于最小割量 D.最大流量不小于任意割量6.连通图 G 有 n 个点，其部分树是 T，则有 A.T 有 n 个点 n 条边 B.T 的长度等于 G 的每条边的长度之和 C.T 有 n 个点 n1 条边 D.T 有 n1 个点 n 条边87.若 P 为网络 G 的一条流量增广链，则 P 中所有正向弧都为 G 的（ ） A对边 B饱和边 C邻边 D不饱和边 8.在图论方法中，通常用_表示人们研究的对象，用_表
19、示对象之间的某联系。9.在图的网络中,弧旁的数字表示距离,试用狄克斯特拉标号法求 vs 到 vt 的最短路径和最短路长。10.在图的网络中,弧旁的数字分别表示(容量,流量) 和单位流费用 ,试问: 所给流是否是可行流?目前的网络流方案是否合理(是否需要进行调整)? 如果需要进行调整,应如何调整改进?图 6311.对下图中的网络，分别用破圈法和避圈法求最短树。决策分析部分91.某公司为促进其产品的销售,拟筹办一次产品展销会。为此,可利用公司的一处空地露天展销,这样免花场地费,然而展销中一旦遇雨,将要损失 10 万元;也可租借展览馆在室内展销,这样可避免遇雨损失,但需要付租金 7 万元。无论在何处
20、举办展销会,都另需会务费 3 万元(见表)。试用不确定性决策准则进行决策。表 单位:万元自然状态决策方案 1(有雨) 2(无雨)S1(露天) 13 3S2(租馆) 10 102.某书店希望订购新出版的一部图书。据以往经验,新书的销售量可能为 80,120,180 或 240本。已知每本新书订购价为 5 元,零售价为 8 元,剩书的处理价为 1 元。试分别用最大最小准则、最小最大准则、折中准则和后悔值准则确定图书的订购量。3.某公司对其供应商进行评价,考虑其产品价格低廉性 U1、质量合格率 U2、按时交货率U3、交货提前期 U4 四方面。 (1)组织采购人员讨论,将评价指标两两相比较,构造判断矩
21、阵如下 ,试用方根法进行层次单排序,计算指标权重(当矩阵维数 n=4,R.I.=0.92)。目标 O U1 U2 U3 U4U1 1 2 3 5U2 1/2 1 2 3U3 1/3 1/2 1 2U4 1/5 1/3 1/2 1(2)为了定量评判供应商,组织了三组专家对其中一家供应商的履约绩效进行打分，如果按 9 分制打分，假设评价等级标准为“好，良，中，较差，差” ，评价等级集合为C=（ 9,7,5,3,1） ，三组专家对评价对象的评价数据如表所示。评价指标 专家组 1 专家组 2 专家组 3价格低廉性 U1 5 6 5质量合格率 U2 8 7 9按时交货率 U3 9 9 9交货提前期 U4 7 8 6试运用模糊综合评价方法将评价指标进行排序,并给出该供应商的评价建议。
