1、运筹学习题课一、选择题1.用图解法解线性规划时，以下几种情况中不可能出现的是（ ） 。A. 可行域有界，无有限最优解 B. 可行域无界，有唯一最优解C. 可行域是空集，无可行解 D. 可行域有界，有多重最优解2.根据线性规划的互补松弛定理，安排生产的产品机会成本一定（ ）利润.A. 小于 B. 等于 C. 大于 D. 大于等于3.已知某个含 10 个结点的树图，其中 9 个结点的次为 1，1，3，1，1，1，3，1，3，则另一个结点的次为（ ）。A. 3 B. 2 C. 1 D. 以上三种情况均有可能4.在求解整数规划问题时，不可能出现的是（ ） 。A. 唯一最优解 B. 无可行解 C. 多重
2、最佳解 D. 无穷多个最优解5. 个变量构成一组基变量的充要条件是（ ）。mnA. 个变量恰好构成一个闭回路1B. 个变量对应的系数列向量线性相关C. 个变量中部分变量构成一个闭回路D. 个变量不包含任何闭回路n6.线性规划具有唯一最优解是指（ ） 。A. 最优表中存在常数项为零 B. 可行解集合有界C. 最优表中存在非基变量的检验数为零 D. 最优表中非基变量检验数全部非零7.有 6 个产地 4 个销地的产销平衡运输问题模型具有特征（ ） 。A. 有 10 个变量 24 个约束 B. 有 24 个变量 10 个约束C. 有 24 个变量 9 约束 D. 有 9 个基变量 10 个非基变量8.
3、下列关于网络最大流的说法中，不正确的是（ ） 。A. 可行流 是最大流，当且仅当网络中存在关于 的增广链*f *fB. 用标号法求解最大流问题，同时可得到一个最小截集C. 最小截集的容量的大小影响网络总的输送量的提高D. 网络的最大流需满足容量条件和平衡条件9.如果一个线性规划问题有 个变量， 个约束方程 ，系数矩阵的行数为 ，则nm()nm基可行解的个数最为（ ） 。A. mB. C. mnCD. nmC10.在一个网络中，如果图形是连通且不含圈的，则这种图形称之为（ ） 。A. 点 B. 线 C. 树 D. 最小支撑树11.用表上作业法求解 3 个产地 4 个销地的运输问题，若某步求得空格
4、 的检验数为-32AB2，下列说法中正确的是（ ） 。A. 增加空格 处的运输量将使总成本降低32ABB. 当前方案是最优运输方案C. 由 至 的运输量增加 1 个单位，可使总运费增加 232D. 为使总运费更小，应使 至 的运输量减少 23A2B12.若某线性规划问题存在基可行解，则该问题（ ） 。A. 一定有最优解 B. 具有无界解C. 有非空的可行域 D. 可能无可行解13.若 是关于可行流 的一条增广链，则在 上有（ ） 。fA. 对一切 ，有(,)ijvijijfcB. 对一切 ，有ijijijC. 对一切 ，有(,)ijvijijfcD. 对一切 ，有ij0ij14.设线性规划的约
5、束条件为 ，则基本可行解为 （ ） 。1234,0xA. (0, 0, 4, 3) B. (2, 0, 1, 0) C. (3, 4, 0, 0) D. (3, 0, 4, 0)15.关于动态规划问题的下列命题中错误的是（ ） 。A. 动态规划分阶段顺序不同，则结果不同B. 状态对决策有影响C. 动态规划中，定义状态时应保证在各个阶段中所做决策的相对独立性D. 动态规划的求解过程都可以用列表形式实现16.关于标准的 M/M/1 排队模型，下列说法错误的是（ ） 。A. 顾客源是有限的，且到达过程是平稳的B. 各顾客的服务时间相互独立，且服从相同的负指数分布C. 到达时间间隔和服务时间是相互独立
6、的D. 单个队列，先到先服务，且对队长没有限制17.下列说法不正确的是（ ） 。A. 顾客相继到达的时间间隔独立同负指数分布等价于输入过程为泊松流B. 标准的 M/M/1 模型中，顾客在系统中的逗留时间服从负指数分布C. 在 M/M/1/N/模型中，当排队等待的顾客数为 N-1 时，再来的顾客将被拒绝进入系统D. 单服务台的排队模型中，排队长的期望值与队长的期望值相差 118.在排队系统中，系统的状态概率 Pi是指（ ）A系统中有 i 个顾客在等待服务 B系统可容纳的最大顾客数为 iC系统中有 i 个顾客的可能性 D系统中有 i 个顾客19.在库存决策问题中，所谓存储策略是指（ ）A决定补充的
7、间隔时间 B决定需求和补充的数量C决定补充的最小费用 D决定补充的间隔时间和每次补充的数量20.假设顾客的到达形成强度为 的泊松流，则对于充分小的 ，下列哪项说法是不正确t的？（ ）A在 内最多只能有 1 个顾客到达,tB在 内有 2 个以上顾客到达的概率为 ()otC在 内有 2 个顾客到达的概率为 ,t D在 内恰有 1 个顾客到达的概率为()t21.下列关于标准 M/M/1 排队模型中 的描述，那一项是不正确的？（ ）A它能刻画系统的繁忙程度 B为保证排队长度有限，需满足 1C它是平均到达率和平均服务率之比 D它表示系统的服务强度22.线性规划问题 的解的情况为（ 1211212min3
8、4,0Zxxx、） 。A. 无可行解 B. 有唯一最优解 C. 有多重最优解 D. 有无界解23.关于线性规划模型的可行域，下面_B_的叙述正确（ ） 。A. 可行域内必有无穷多个点 B. 可行域必有界C. 可行域内必然包括原点 D. 可行域必是凸的24.表上作业法的基本思想和步骤与单纯形法类似，因而初始调运方案的给出就相当于找到一个（ ） 。 A. 基 B. 可行解 C. 初始基本可行解 D. 最优解25.关于最小支撑树，以下叙述正确的是（ ） 。A. 最小支撑树是一个网络中连通所有点而边数最少的图B. 最小支撑树是一个网络中连通所有的点，而权数最少的图C. 一个网络中的最大权边必不包含在其
9、最小支撑树内D. 一个网络的最小支撑树一般是不唯一的二、判断题1.对于线性规划的原问题和其对偶问题，若其中一个有最优解，另一个也一定有最优解。2.一个图 G 是树的充分必要条件是该图为边数最少的无孤立点的图。 （ ）3.对于对偶单纯形法，其初始解必须是可行的。 （ ）4.设图 G=(V,E)是一个树，p(G)，则中至少有两个悬挂点。 （ ）5.用图解法解线性规划问题，若在两个顶点同时得到最优解，则它们的连线上任意点都是最优解。 （ ）6.在树中不相邻的两个点间添上一条边，则恰好得到一个圈。 （ ）7.线性规划可行域无界,则具有无界解。 （ ）8.任意可行流的流量不小于最小割量。 （ ）9.网络
10、最大流量是网络起点至终点的一条增广链上的最大流量。 （ ）10.可行解集有界非空时,则在顶点上至少有一点达到最优值。 （ ）11.按最小元素法求得运输问题的初始方案, 从任一非基格出发都存在唯一一个闭回路。12.运输问题中用位势法求得的检验数不唯一。 （ ）13.假如一个线性规划问题含有 6 个变量和 4 个约束,则用动态规划方法求解时将划分为 4个阶段,每个阶段的状态将由一个 6 维的向量组成。 ( )14.动态规划中,定义状态时应保证在各个阶段中所做决策的相互独立性。 ( )15.在机器发生故障的概率及工人修复一台机器的时间分布不变的条件下，由 1 名工人看管5 台机器与由 3 名工人联合
11、看管 15 台机器相比，机器因故障等待工人维修的平均时间不变。( )16.订货费用包括订购费用和货物的成本费用。前者与订货数量有关，而与订货次数无关。( )17.对同一个动态规划问题,应用顺推解法和逆推解法一定会得到相同的最优解。 ( )18.在单时期的随机存贮模型中,计算时都不包括订货费用这一项。原因是该项费用通常很小可忽略不计。 ( )19.报童问题中损失最小的期望值和赢利最大的期望值是不同的，所以两者确定的 Q 值也不相同。 ( )20.相继到达的间隔时间是独立且相同的负指数分布，与输入过程为泊松流是等价的。 ( )三、填空题1.用表上作业法求解 个产地 个销地的平衡运输问题，其方案表上
12、数字格的个数为 mn个；若已计算出某空格的检验数为-3，若从该空格出发进行调整，设调整量为 2，则调整后可使总运费下降 。2.设线性规划问题 有最优解，且最优解值 ；如果 和 分别ax:,0cAbx0zcb被 所乘，则改变后的问题1v（也有、不一定有）最优解；若有最优解，其最优解 (大于、小于、等于) 。z3.设有线性规划问题 ，有一可行基 B（为 Amin,|,0fCXRAXb中的前 m 列） ，记相应基变量为 ，价格系数为 CB，相应于非基变量为 XN，价格系数为CN，则相应于 B 的基本可行解为 X= ；B 为最优基的条件是 。4.线性规划问题如果有无穷多最优解，则单纯形计算表的终表中必
13、然有_ 个非基变量的检验数为_ _。5.线性规划问题中，如果在约束条件中出现等式约束，通常用增加_ _的方法来产生初始可行基。6.求最小支撑树问题，常用的方法有：避圈法和 _ _。7.下图给出某城市部分道路的分布情况，现要沿道路铺埋输水管，为了使铺设的管线最短，要求按道路分布图的最小支撑树来设计管线，则所铺设管线的最小总长度应该是 。8.某钻井队要从编号为 1、2、3、4、5 的五个井位中选择若干钻井探油，则“要么选择钻井 2，要么选择钻井 5” 可用 的线性表达式表示为 ，其中选ix择第 号钻井时 ，否则 ， 。i=ix0i15,9.已知下表是制订生产计划问题的一张 LP 最优单纯形表（Ma
14、x 型问题，约束条件均为“”型） ，其中 为松驰变量。345,BXb1x23x45x4x3 0 0 -2 1 314/3 1 0 -1/3 0 2/321 0 1 0 0 -1jjcz0 0 -5 0 -23则 = ；对偶问题的最优解 。 1B *Y10.在单纯形迭代中，可以根据最终表中 变量不为零判断线性规划问题无解。11.若某种资源的影子价格等于 ，在其他条件不变的情况下(假设原问题的最佳基不变)，k当该种资源增加 3 个单位时，相应的目标函数值将增加 。12.线性规划的原问题的约束条件系数矩阵为 ，则其对偶问题的约束条件系数矩阵为 A。13.在表上作业法所得到的调运方案中，从某空格出发的
15、闭回路的转角点所对应的变量必为 。14.已知下表是制定生产计划问题的一张 LP 最优单纯形表（极大化问题，约束条件均为“”型） ，其中 为松弛变量。456,xBXb12x34x56x1x2 1 1 0 2 0 132/3 0 0 1 1 0 451 0 -2 0 1 1 6jjcz0 0 0 -4 0 -9则 ，对偶问题的最优解 。1B*Y15.若 分别是线性规划的原问题和对偶问题的可行解，则有 ；又若,XY CXYb成立，则 和 分别是线性规划的原问题和对偶问题的 。Cb16.用标号法求解网络最大流问题，当求的最大流的同时，也得到了最小截集，它是由 点集和 点集构成的点集切割中 （正还是反）
16、向弧组成。17.在完全市场经济的条件下，当某种资源的市场价格低于影子价格时，企业应 该资源，而当某种资源的市场价格高于影子价格时，则企业应 该资源，可见影子价格对市场有调节作用。18.若运输问题的产销平衡表中有 个产地和 个销地，则其决策变量有 个，其数mn值格有 个。19.某工程公司拟从四个项目中选择若干项目。若令 ，请用1, 0 iix第 个 项 目 被 选 中第 个 项 目 未 选 中的线性表达式表示下列要求：ix若项目 2 被选中，则项目 4 不能被选中： ；只有项目 1 被选中，项目 3 才能被选中： 。20.表上作业法求解运输问题，若已计算出某空格的检验数为-1，现从该空格出发进行
17、调整，设调整量为 2，则调整后可使总运费下降 。21.设线性规划问题 有最优解 和影子价格 ，则线性规划max:,0CXAb*X*Y问题 的最优解= ，影子价格= 。a:,22.如图所示，该网络的最小支撑树的权和为 。23.可行流应满足两个限制条件，即容量限制条件和 。24.线性规划模型包括 、约束条件和目标函数三个要素。25.在运输问题模型中， 个变量构成基变量的充要条件是 1mn。26.线性规划问题的所有可行解构成的集合是 ，线性规划问题的每个基可行解对应可行域的 。27.用大 M 法求解 Max 型的线性规划时，人工变量在目标中的系数均为 ，若最优解的 中含有人工变量，则原问题无可行解。
18、28.已知最优基 ， ，则对偶问题的最优解是 。1237B(3,6)BC29.将非平衡运输问题化为平衡运输问题，在表上相当于增加一个虚设的 ，在模型中相当于增加若干个 变量。30.在 资 源 优 化 的 线 性 规 划 问 题 中 ， 某 资 源 有 剩 余 ， 则 该 资 源 影 子 价 格 等 于 。31.若 、 分别是线性规划的原问题和对偶问题的可行解，则有 （XY CXYb） 。,=或32.请在下图所示的最短路问题求解过程中进行一步：下一步给 节点标号，标号为 。33.动态规划模型中，状态变量的选择要满足两个条件：能描述问题的过程； 。34.动态规划问题的研究对象是 问题。35.一般的
19、排队系统有三个基本组成部分，即 、排队规则和服务机构。36.当顾客的到达形成强度为 的泊松流时，对于充分小的 ，在时间区间 内有t,t1 个顾客到达的概率 = 。1(,)Pt37.在 排队模型中，设顾客平均到达率为 ，则被拒绝排队的顾客的平均/MN数为 。38.在允许缺货、生产需要一定时间的确定型存储模型中，最优单位费用记为 C0，记不允许缺货，而其他参数不变的情况下的最优单位费用为 C1，则 C1 C0（选大于还是小于） 。39.已知报童每日售出报纸份数 的概率为 ，每售出一份报纸赚 元；如报纸未能售r()Prk出，每份赔 元。则该报童应准备的报纸最佳数量 应满足的条件是： hQ。40.某厂
20、每年需某种元件 1000 个，每次订购费 元，存储费每年每件 元，310C120C不允许缺货。又若元件单价 随着采购数量的不同而不同：K。则此时的最佳订购数量 = 个。40150()38QK(元 )，元 ， Q41.在 模型中，设顾客平均到达率为 ，则该排队系统的有效到达率/MN；而在 模型中系统的有效到达率 e/1/Mme；42.某蛋糕房的顾客到达服从 人/分钟的泊松分布，则某一刻钟内无顾客到达的概率1为 ，在 4 分钟内有 3 名以上顾客到达的概率为 。四、计算题1.（20分）某建材厂生产四种型号的特用构件：型、型、型、型。各型号每件所需组装时间、检验时间、销售收入及该厂组装调试能力如表1
21、所示。型 型 型 型 工厂生产能力（h）组装时间(h) 8 10 12 15 2000检验时间（h） 2 2 4 5 500售价（百元） 4 6 8 10但现在因为某种特型材料比较紧张，每月最多只能进货180只（每件构件用一只） ，其中型、型用到的不超过100只。令 依次表示各型号每月计划产量。现工厂拟定1234,x使目标总销售收入 为最大的生产计划。z（1）写出该问题的数学模型，对于约束条件依下列顺序：组装时间、检验时间、特种材料数、 、 型、型用到的特种材料数，并引入松弛变量使之成为等式。 （5分）（2）用单纯型法求解的终表入下表。4 6 8 10 0 0 0 0BCX1b1x23x45x
22、67x80 8x50 -0.2 0 0.2 0 0.1 -0.5 0 16 2125 0.5 1 0 0 0.25 -0.75 0 00 75 0.3 0 0.2 0 -0.15 0.25 1 010 4x50 0.2 0 0.8 1 -0.1 0.5 0 0jjcz-1 0 0 0 -0.5 -0.5 0 0依据上表，分别回答下列问题：最优生产计划是什么？是否还有其他的最优生产计划？ 为什么？ （4分）组装时间的影子价格是多少？ （1 分）若外厂可调剂增加80h 的检验时间，但每小时需付0.4百元，这样的调剂值得吗？ 能增加多少收入？ （4分）设型构件售价由4百元增加到4.5百元，最优计划要改变吗？如果增加到5.5百元呢？说明理由。 （2分）写出本问题的对偶模型，并指出其最优解。 （4 分）2 （20 分）某企业利用三种资源生产两种产品的最优计划问题归结为下列线性规划 0,45 8293 max2112xxZ已知最优表如下。 jc5 4 0 0 0BCBX1b1x23x45x0 3x25 0 0 1 2 -5
