运筹学习题课2017.doc

运筹学习题课一、选择题1.用图解法解线性规划时，以下几种情况中不可能出现的是（ ）。A.可行域有界，无有限最优解 B.可行域无界，有唯一最优解C.可行域是空集，无可行解 D. 可行域有界，有多重最优解2.根据线性规划的互补松弛定理，安排生产的产品机会成本一定（ ）利润.A.小于B.等于C.大于D.大于等于3.已知某个含10个结点的树图，其中9个结点的次为1，1，3，1，1，1，3，1，3，则另一个结点的次为（ ）。A.3B.2C.1D.以上三种情况均有可能4.在求解整数规划问题时，不可能出现的是（ ）。A.唯一最优解B.无可行解C.多重最佳解D.无穷多个最优解5.个变量构成一组基变量的充要条件是（ ）。A.个变量恰好构成一个闭回路B.个变量对应的系数列向量线性相关C.个变量中部分变量构成一个闭回路D.个变量不包含任何闭回路6.线性规划具有唯一最优解是指（ ）。A.最优表中存在常数项为零 B.可行解集合有界C.最优表中存在非基变量的检验数为零 D.最优表中非基变量检验数全部非零7.有6 个产地4个销地的产销平衡运输问题模型具有特征（ ）。A.有10个变量24个约束 B.有24个变量10个约束C.有24个变量9约束 D.有9个基变量10个非基变量8.下列关于网络最大流的说法中，不正确的是（ ）。A.可行流是最大流，当且仅当网络中存在关于的增广链B.用标号法求解最大流问题，同时可得到一个最小截集C.最小截集的容量的大小影响网络总的输送量的提高D.网络的最大流需满足容量条件和平衡条件9.如果一个线性规划问题有个变量，个约束方程，系数矩阵的行数为，则基可行解的个数最为（ ）。A.B.C.D.10.在一个网络中，如果图形是连通且不含圈的，则这种图形称之为（ ）。A.点B.线C.树D.最小支撑树11.用表上作业法求解3个产地4个销地的运输问题，若某步求得空格的检验数为-2，下列说法中正确的是（ ）。A.增加空格处的运输量将使总成本降低B.当前方案是最优运输方案C.由至的运输量增加1个单位，可使总运费增加2D.为使总运费更小，应使至的运输量减少212.若某线性规划问题存在基可行解，则该问题（ ）。A.一定有最优解B.具有无界解C.有非空的可行域D.可能无可行解13.若是关于可行流的一条增广链，则在上有（ ）。A.对一切，有B.对一切，有C.对一切，有D.对一切，有14.设线性规划的约束条件为，则基本可行解为（ ）。A.(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.到达时间间隔和服务时间是相互独立的D.单个队列，先到先服务，且对队长没有限制17.下列说法不正确的是（ ）。A.顾客相继到达的时间间隔独立同负指数分布等价于输入过程为泊松流B.标准的M/M/1模型中，顾客在系统中的逗留时间服从负指数分布C.在M/M/1/N/模型中，当排队等待的顾客数为N-1时，再来的顾客将被拒绝进入系统D.单服务台的排队模型中，排队长的期望值与队长的期望值相差118.在排队系统中，系统的状态概率Pi是指（ ） A系统中有i个顾客在等待服务 B系统可容纳的最大顾客数为i C系统中有i个顾客的可能性 D系统中有i个顾客19.在库存决策问题中，所谓存储策略是指（ ）A决定补充的间隔时间 B决定需求和补充的数量C决定补充的最小费用 D决定补充的间隔时间和每次补充的数量20.假设顾客的到达形成强度为的泊松流，则对于充分小的，下列哪项说法是不正确的？（ ）A在内最多只能有1个顾客到达B在内有2个以上顾客到达的概率为 C在内有2个顾客到达的概率为 D在内恰有1个顾客到达的概率为21.下列关于标准M/M/1排队模型中的描述，那一项是不正确的？（ ）A它能刻画系统的繁忙程度 B为保证排队长度有限，需满足C它是平均到达率和平均服务率之比 D它表示系统的服务强度22.线性规划问题的解的情况为（ ）。A.无可行解 B.有唯一最优解C.有多重最优解D.有无界解23.关于线性规划模型的可行域，下面_B_的叙述正确（ ）。A.可行域内必有无穷多个点B.可行域必有界C.可行域内必然包括原点D.可行域必是凸的24.表上作业法的基本思想和步骤与单纯形法类似，因而初始调运方案的给出就相当于找到一个（ ）。 A.基B.可行解C.初始基本可行解D.最优解25.关于最小支撑树，以下叙述正确的是（ ）。A.最小支撑树是一个网络中连通所有点而边数最少的图B.最小支撑树是一个网络中连通所有的点，而权数最少的图C.一个网络中的最大权边必不包含在其最小支撑树内D.一个网络的最小支撑树一般是不唯一的二、判断题1.对于线性规划的原问题和其对偶问题，若其中一个有最优解，另一个也一定有最优解。2.一个图G 是树的充分必要条件是该图为边数最少的无孤立点的图。（ ）3.对于对偶单纯形法，其初始解必须是可行的。（ ）4.设图G=(V,E)是一个树，p(G)，则中至少有两个悬挂点。（ ）5.用图解法解线性规划问题，若在两个顶点同时得到最优解，则它们的连线上任意点都是最优解。（ ）6.在树中不相邻的两个点间添上一条边，则恰好得到一个圈。（ ）7.线性规划可行域无界,则具有无界解。（ ）8.任意可行流的流量不小于最小割量。（ ）9.网络最大流量是网络起点至终点的一条增广链上的最大流量。（ ）10.可行解集有界非空时,则在顶点上至少有一点达到最优值。（ ）11.按最小元素法求得运输问题的初始方案, 从任一非基格出发都存在唯一一个闭回路。12.运输问题中用位势法求得的检验数不唯一。（ ）13.假如一个线性规划问题含有6个变量和4个约束,则用动态规划方法求解时将划分为4个阶段,每个阶段的状态将由一个6维的向量组成。 ( )14.动态规划中,定义状态时应保证在各个阶段中所做决策的相互独立性。( )15.在机器发生故障的概率及工人修复一台机器的时间分布不变的条件下，由1名工人看管5台机器与由3名工人联合看管15台机器相比，机器因故障等待工人维修的平均时间不变。 ( )16.订货费用包括订购费用和货物的成本费用。前者与订货数量有关，而与订货次数无关。( )17.对同一个动态规划问题,应用顺推解法和逆推解法一定会得到相同的最优解。( )18.在单时期的随机存贮模型中,计算时都不包括订货费用这一项。原因是该项费用通常很小可忽略不计。( )19.报童问题中损失最小的期望值和赢利最大的期望值是不同的，所以两者确定的Q值也不相同。 ( )20.相继到达的间隔时间是独立且相同的负指数分布，与输入过程为泊松流是等价的。 ( )三、填空题1.用表上作业法求解个产地个销地的平衡运输问题，其方案表上数字格的个数为 个；若已计算出某空格的检验数为-3，若从该空格出发进行调整，设调整量为2，则调整后可使总运费下降 。2.设线性规划问题有最优解，且最优解值；如果和分别被所乘，则改变后的问题 （也有、不一定有）最优解；若有最优解，其最优解 (大于、小于、等于)。3.设有线性规划问题，有一可行基B（为A中的前m列），记相应基变量为，价格系数为CB，相应于非基变量为XN，价格系数为CN，则相应于B的基本可行解为X= ；B为最优基的条件是 。4.线性规划问题如果有无穷多最优解，则单纯形计算表的终表中必然有_ 个非基变量的检验数为_ _。5.线性规划问题中，如果在约束条件中出现等式约束，通常用增加_ _的方法来产生初始可行基。6.求最小支撑树问题，常用的方法有：避圈法和 _ _。7.下图给出某城市部分道路的分布情况，现要沿道路铺埋输水管，为了使铺设的管线最短，要求按道路分布图的最小支撑树来设计管线，则所铺设管线的最小总长度应该是 。8.某钻井队要从编号为1、2、3、4、5的五个井位中选择若干钻井探油，则“要么选择钻井2，要么选择钻井5” 可用的线性表达式表示为 ，其中选择第号钻井时，否则，。9.已知下表是制订生产计划问题的一张LP最优单纯形表（Max型问题，约束条件均为“”型），其中为松驰变量。300-2134/310-1/302/310100-100-50-23则= ；对偶问题的最优解 。 10.在单纯形迭代中，可以根据最终表中 变量不为零判断线性规划问题无解。11.若某种资源的影子价格等于，在其他条件不变的情况下(假设原问题的最佳基不变)，当该种资源增加3个单位时，相应的目标函数值将增加 。12.线性规划的原问题的约束条件系数矩阵为，则其对偶问题的约束条件系数矩阵为 。13.在表上作业法所得到的调运方案中，从某空格出发的闭回路的转角点所对应的变量必为 。14.已知下表是制定生产计划问题的一张LP最优单纯形表（极大化问题，约束条件均为“”型），其中为松弛变量。21102012/300110410-20116000-40-9则 ，对偶问题的最优解 。15.若分别是线性规划的原问题和对偶问题的可行解，则有 ；又若成立，则和分别是线性规划的原问题和对偶问题的 。16.用标号法求解网络最大流问题，当求的最大流的同时，也得到了最小截集，它是由 点集和 点集构成的点集切割中 （正还是反）向弧组成。17.在完全市场经济的条件下，当某种资源的市场价格低于影子价格时，企业应 该资源，而当某种资源的市场价格高于影子价格时，则企业应 该资源，可见影子价格对市场有调节作用。18.若运输问题的产销平衡表中有个产地和个销地，则其决策变量有 个，其数值格有 个。19.某工程公司拟从四个项目中选择若干项目。若令，请用的线性表达式表示下列要求：若项目2被选中，则项目4不能被选中： ；只有项目1被选中，项目3才能被选中： 。20.表上作业法求解运输问题，若已计算出某空格的检验数为-1，现从该空格出发进行调整，设调整量为2，则调整后可使总运费下降 。21.设线性规划问题有最优解和影子价格，则线性规划问题的最优解= ，影子价格= 。22.如图所示，该网络的最小支撑树的权和为 。23.可行流应满足两个限制条件，即容量限制条件和 。24.线性规划模型包括 、约束条件和目标函数三个要素。25.在运输问题模型中，个变量构成基变量的充要条件是 。26.线性规划问题的所有可行解构成的集合是 ，线性规划问题的每个基可行解对应可行域的 。27.用大M法求解Max型的线性规划时，人工变量在目标中的系数均为 ，若最优解的 中含有人工变量，则原问题无可行解。28.已知最优基，则对偶问题的最优解是 。29.将非平衡运输问题化为平衡运输问题，在表上相当于增加一个虚设的 ，在模型中相当于增加若干个 变量。30.在资源优化的线性规划问题中，某资源有剩余，则该资源影子价格等于 。31.若、分别是线性规划的原问题和对偶问题的可行解，则有 （）。32.请在下图所示的最短路问题求解过程中进行一步：下一步给 节点标号，标号为 。33.动态规划模型中，状态变量的选择要满足两个条件：能描述问题的过程； 。34.动态规划问题的研究对象是 问题。35.一般的排队系统有三个基本组成部分，即 、排队规则和服务机构。36.当顾客的到达形成强度为的泊松流时，对于充分小的，在时间区间内有1个顾客到达的概率= 。37.在排队模型中，设顾客平均到达率为，则被拒绝排队的顾客的平均数为 。38.在允许缺货、生产需要一定时间的确定型存储模型中，最优单位费用记为C0，记不允许缺货，而其他参数不变的情况下的最优单位费用为C1，则C1 C0（选大于还是小于）。39.已知报童每日售出报纸份数的概率为，每售出一份报纸赚元；如报纸未能售出，每份赔元。则该报童应准备的报纸最佳数量应满足的条件是： 。40.某厂每年需某种元件1000个，每次订购费元，存储费每年每件元，不允许缺货。又若元件单价随着采购数量的不同而不同：。则此时的最佳订购数量= 个。41.在模型中，设顾客平均到达率为，则该排队系统的有效到达率 ；而在模型中系统的有效到达率 ；42.某蛋糕房的顾客到达服从人/分钟的泊松分布，则某一刻钟内无顾客到达的概率为 ，在4分钟内有3名以上顾客到达的概率为 。四、计算题1.（20分）某建材厂生产四种型号的特用构件：型、型、型、型。各型号每件所需组装时间、检验时间、销售收入及该厂组装调试能力如表1所示。型型型型工厂生产能力（h）组装时间(h)81012152000检验时间（h）2245500售价（百元）46810但现在因为某种特型材料比较紧张，每月最多只能进货180只（每件构件用一只），其中型、型用到的不超过100只。令依次表示各型号每月计划产量。现工厂拟定使目标总销售收入为最大的生产计划。（1）写出该问题的数学模型，对于约束条件依下列顺序：组装时间、检验时间、特种材料数、型、型用到的特种材料数，并引入松弛变量使之成为等式。（5分）（2）用单纯型法求解的终表入下表。468100000050-0.200.200.1-0.50161250.51000.25-0.7500050.300.20-0.150.251010500.200.81-0.10.500-1000-0.5-0.500依据上表，分别回答下列问题：最优生产计划是什么？是否还有其他的最优生产计划？ 为什么？ （4分）组装时间的影子价格是多少？ （1分）若外厂可调剂增加80h的检验时间，但每小时需付0.4百元，这样的调剂值得吗？ 能增加多少收入？ （4分）设型构件售价由4百元增加到4.5百元，最优计划要改变吗？如果增加到5.5百元呢？说明理由。 （2分）写出本问题的对偶模型，并指出其最优解。 （4分）2（20分）某企业利用三种资源生产两种产品的最优计划问题归结为下列线性规划已知最优表如下。540000250012-55351001-1410010-12000-1-3（1）确定x2的系数c2的变化范围，使原最优解保持最优； （3分）（2）若c2=6，求新的最优计划； （5分）（3）b3在什么范围内变化，原最优基不变？ （2分）（4）若b3=55，求出新的最优解； （5分）（5）设企业研制了一种新产品，对三种资源的消耗系数列向量以P6表示，。问它的价值系数c6符合什么条件才必须安排它的生产？设c6=3，新的最优生产计划是什么？ （5分）3. (20分)某电冰箱厂生产单、双门两种冰箱，每台所需组装时间、调试时间、销售收入及该厂的组装、调试能力如下表，电机每月进货最多50个（每台冰箱用1台电机），令分别为单、双门冰箱的月产量。现工厂需拟订使总收入为最大的生产计划。单门双门月生产能力组装时间（h）10151000调试时间（h）25270销售收入（元）10001300（1）写出此问题的数学模型（约束条件依次为组装时间、调试时间、电机数）；（3分）（2）下面是用单纯形法求解此问题过程中的一个不完全表，请将表格补充完整；（4分）10001300000-510-15-301-51001（3）上表是否为终表，为什么？若是，写出最优生产计划和电机的影子价格；在执行这一计划后，哪种资源有剩余，剩余多少？（5分）（4）写出上述规划的对偶规划模型及其最优解；（4分）（5）现又设计出三门冰箱，每台组装时间20h，调试时间10h，销售收入1600元，问是否应考虑生产三门冰箱？请说明理由。（4分）4. (15分)下图网络弧上的数字为容量，括弧内的数字为该弧的流量。（1）在括号内填上适当的数字，使构成一个可行流。(2分)（2）在下表中填出截集与截量。(3分)、（3）用标号法解此网络最大流，并指出最小截集。（10分）5.（15分）某照相机厂生产A、B、C三种型号的产品，每架均需经机身制造、零件装配和检验包装三道工序。各型号产品所需工时数、每月工时限量及销售利润见下表。根据市场情况，C型每月产量应控制在150架以内。现工厂需拟定使总利润最大的生产计划。A型B型C型工时限量(h)机身制造时间(h)1272500零件装配时间(h)23.513500检验包装时间(h)1231500销售利润(元/架)102050（1）写出此问题的数学模型（变量分别表示A、B、C型产品的月产量，约束条件依次为：机身制造时间、零件装配时间、检验包装时间及C型产量）（2分）（2）下表是用单纯形法解此问题过程中的一个不完全表，请将表完成；（4分）10205000004000010-1-41512.50001-1.754.2552510000.5-1.5150010001检验数（3）上表是否为终表？若是，请写出最优生产计划及检验包装时间的影子价格；（3分）（4）写出此问题的对偶问题数学模型，并指出其最优解；（3分）（5）现又设计出D型产品，每架需机身制造、零件装配和检验包装时间分别为6、2、2(h)，销售利润为30元/架，问是否应考虑生产D型产品？为什么？（3分）6.考虑非线性整数规划，其中，现拟用动态规划方法解此问题（用通常的逆推解法），要求：（1）写出以下表达式或集合的具体内容：本问题的状态转移方程 递推方程 第1阶段的状态集合第2阶段状态为5时的允许决策的集合= ；7.有模型，平均服务率为，平均到达率，问：（1）有效到达率和服务台的服务强度；（2）系统中的平均顾客数；（3）系统的满员率；（4）服务台应从哪些方面改进工作？理由是什么？8.设某公司利用塑料作原料制成产品出售，对原料需求的