运筹学习题课2017

运筹学习题课一、选择题.用图解法解线性规划时，以下几种情况中不可能出现的是（ ）。A.可行域有界，无有限最优解 B.可行域无界，有唯一最优解C.可行域是空集，无可行解 D.可行域有界，有多重最优解.根据线性规划的互补松弛定理，安排生产的产品机会成本一定（ ）利润.A.小于B.等于C.大于D.大于等于.已知某个含10个结点的树图，其中9个结点的次为1，1，3,1，1，1，3,1，3,则另一个结点的次为（）。A.3B.2C.1D.以上三种情况均有可能.在求解整数规划问题时，不可能出现的是（ ）。A.唯一最优解B.无可行解 C.多重最佳解D,无穷多个最优解.m+n-1个变量构成一组基变量的充要条件是（ ）。m+n-1个变量恰好构成一个闭回路m+n-1个变量对应的系数列向量线性相关m+n-1个变量中部分变量构成一个闭回路m+n-1个变量不包含任何闭回路TOC\o"1-5"\h\z.线性规划具有唯一最优解是指（ ）。A.最优表中存在常数项为零 B. 可行解集合有界C.最优表中存在非基变量的检验数为零 D. 最优表中非基变量检验数全部非零.有6个产地4个销地的产销平衡运输问题模型具有特征（ ）。A.有10个变量24个约束B.有24个变量10个约束C.有24个变量9约束D.有9个基变量10个非基变量.下列关于网络最大流的说法中，不正确的是（ ）。可行流f*是最大流，当且仅当网络中存在关于f*的增广链用标号法求解最大流问题，同时可得到一个最小截集最小截集的容量的大小影响网络总的输送量的提高网络的最大流需满足容量条件和平衡条件.如果一个线性规划问题有n个变量，m个约束方程（m<n），系数矩阵的行数为m，则TOC\o"1-5"\h\z基可行解的个数最为（ ）。A.m B.n C.Cm D. Cnn m.在一个网络中，如果图形是连通且不含圈的，则这种图形称之为（ ）。A.点B.线C.树D.最小支撑树.用表上作业法求解3个产地4个销地的运输问题，若某步求得空格4B2的检验数为-2,下列说法中正确的是（ ）。A.增加空格4B2处的运输量将使总成本降低B.当前方案是最优运输方案C.由A至B的运输量增加1个单位，可使总运费增加23 2D.为使总运费更小，应使A至B的运输量减少232.若某线性规划问题存在基可行解，则该问题（ ）。A.一定有最优解B.具有无界解C.有非空的可行域D.可能无可行解.若从是关于可行流f的一条增广链，则在N上有（ ）。A.对一切3#)£N+，有fVCij jjA.B对一切3#)£N+，有f>c.ij ijijC对一切(V,V)£^-，有f>c.ij ijijD对一切(V,V)£^-，有f>0.TOC\o"1-5"\h\zij ij'X+x2+x3=3.设线性规划的约束条件为｛2x1+2x2+x4=4，则基本可行解为( )。x，:x>014A.(0,0,4,3)B.(2,0,1,0)C.(3,4,0,0)D.(3,0,4,0).关于动态规划问题的下列命题中错误的是（ ）。A.动态规划分阶段顺序不同，则结果不同B.状态对决策有影响C.动态规划中，定义状态时应保证在各个阶段中所做决策的相对独立性D.动态规划的求解过程都可以用列表形式实现16.关于标准的M/M/1排队模型，下列说法错误的是（ ）。A.顾客源是有限的，且到达过程是平稳的B.各顾客的服务时间相互独立，且服从相同的负指数分布C.到达时间间隔和服务时间是相互独立的D.单个队列，先到先服务，且对队长没有限制17.下列说法不正确的是（ ）。A.顾客相继到达的时间间隔独立同负指数分布等价于输入过程为泊松流B.标准的M/M/1模型中，顾客在系统中的逗留时间服从负指数分布C.在乂/乂/1/旷8模型中，当排队等待的顾客数为N-1时，再来的顾客将被拒绝进入系统D.单服务台的排队模型中，排队长的期望值与队长的期望值相差1.在排队系统中，系统的状态概率Pj是指（ ）A.系统中有i个顾客在等待服务 B.系统可容纳的最大顾客数为iC.系统中有i个顾客的可能性 D.系统中有i个顾客.在库存决策问题中，所谓存储策略是指（）A.决定补充的间隔时间 B.决定需求和补充的数量C.决定补充的最小费用 D.决定补充的间隔时间和每次补充的数量.假设顾客的到达形成强度为九的泊松流，则对于充分小的At，下列哪项说法是不正确的？（ ）A.在［t,t+At）内最多只能有1个顾客到达B.在［t,t+At）内有2个以上顾客到达的概率为o（At）C.在［t,t+At）内有2个顾客到达的概率为1—九At+o（At）D.在［t,t+At）内恰有1个顾客到达的概率为九At+o（At）TOC\o"1-5"\h\z.下列关于标准M/M/1排队模型中P的描述，那一项是不正确的？（ ）A.它能刻画系统的繁忙程度 B.为保证排队长度有限，需满足P>1C.它是平均到达率和平均服务率之比D.它表示系统的服务强度.线性规划问题minZ=3q+4x2,q+x2>4,2q+x2<2,q、x2>0的解的情况为（ ）。A.无可行解 B.有唯一最优解C.有多重最优解 D.有无界解.关于线性规划模型的可行域，下面_8_的叙述正确（ ）。A.可行域内必有无穷多个点B.可行域必有界C.可行域内必然包括原点 D.可行域必是凸的.表上作业法的基本思想和步骤与单纯形法类似，因而初始调运方案的给出就相当于找到一个（ ）。A.基B.可行解C.初始基本可行解D.最优解.关于最小支撑树，以下叙述正确的是（ ）。A.最小支撑树是一个网络中连通所有点而边数最少的图B.最小支撑树是一个网络中连通所有的点，而权数最少的图一个网络中的最大权边必不包含在其最小支撑树内一个网络的最小支撑树一般是不唯一的二、判断题.对于线性规划的原问题和其对偶问题，若其中一个有最优解，另一个也一定有最优解。TOC\o"1-5"\h\z.一个图G是树的充分必要条件是该图为边数最少的无孤立点的图。（ ）.对于对偶单纯形法，其初始解必须是可行的。（ ）.设图G=（V,E）是一个树，p（G）三2,则G中至少有两个悬挂点。（ ）.用图解法解线性规划问题，若在两个顶点同时得到最优解，则它们的连线上任意点都是最优解。（ ）.在树中不相邻的两个点间添上一条边，则恰好得到一个圈。（ ）.线性规划可行域无界，则具有无界解。（ ）.任意可行流的流量不小于最小割量。（ ）.网络最大流量是网络起点至终点的一条增广链上的最大流量。 （ ）.可行解集有界非空时,则在顶点上至少有一点达到最优值。（ ）.按最小元素法求得运输问题的初始方案，从任一非基格出发都存在唯一一个闭回路。.运输问题中用位势法求得的检验数不唯一。 （ ）.假如一个线性规划问题含有6个变量和4个约束,则用动态规划方法求解时将划分为4个阶段，每个阶段的状态将由一个6维的向量组成。 （ ）.动态规划中,定义状态时应保证在各个阶段中所做决策的相互独立性。 （ ）.在机器发生故障的概率及工人修复一台机器的时间分布不变的条件下，由1名工人看管5台机器与由3名工人联合看管15台机器相比，机器因故障等待工人维修的平均时间不变。（ ）.订货费用包括订购费用和货物的成本费用。前者与订货数量有关，而与订货次数无关。（ ）.对同一个动态规划问题，应用顺推解法和逆推解法一定会得到相同的最优解。（ ）.在单时期的随机存贮模型中,计算时都不包括订货费用这一项。原因是该项费用通常很小可忽略不计。 （ ）.报童问题中损失最小的期望值和赢利最大的期望值是不同的，所以两者确定的Q值也不相同。（ ）.相继到达的间隔时间是独立且相同的负指数分布，与输入过程为泊松流是等价的。（ ）三、填空题.用表上作业法求解m个产地n个销地的平衡运输问题，其方案表上数字格的个数为个；若已计算出某空格的检验数为-3,若从该空格出发进行调整，设调整量为2,则调整后可使总运费下降 。.设线性规划问题max:{cx|Ax<b,x>0）有最优解，且最优解值z>0；如果c和b分别被v>1所乘，则改变后的问题（也有、不一定有）最优解；若有最优解，其最优解 （大于、小于、等于）z。.设有线性规划问题[min]f=CX,XeR={XIAX=b,X>。}，有一可行基B（为A中的前m列），记相应基变量为X冗，价格系数为CB，相应于非基变量为XN，价格系数为CN，则相应于B的基本可行解为X=；B为最优基的条件是 。.线性规划问题如果有无穷多最优解，则单纯形计算表的终表中必然有个非基变量的检验数为。.线性规划问题中，如果在约束条件中出现等式约束，通常用增加 的方法来产生初始可行基。.求最小支撑树问题，常用的方法有：避圈法和 。.下图给出某城市部分道路的分布情况，现要沿道路铺埋输水管，为了使铺设的管线最短，要求按道路分布图的最小支撑树来设计管线，则所铺设管线的最小总长度应该是。.某钻井队要从编号为1、2、3、4、5的五个井位中选择若干钻井探油，则“要么选择钻井2,要么选择钻井5”可用X,的线性表达式表示为,其中选择第i号钻井时X=1，否则X=0，i=1….,5。i i.已知下表是制订生产计划问题的一张LP最优单纯形表（Max型问题，约束条件均为“W”则B-1=；对偶问题的最优解『:。.在单纯形迭代中，可以根据最终表中变量不为零判断线性规划问题无解。.若某种资源的影子价格等于k，在其他条件不变的情况下（假设原问题的最佳基不变），当该种资源增加3个单位时，相应的目标函数值将增加 。.线性规划的原问题的约束条件系数矩阵为 A，则其对偶问题的约束条件系数矩阵为。

.在表上作业法所得到的调运方案中，从某空格出发的闭回路的转角点所对应的变量必为。.已知下表是制定生产计划问题的一张LP最优单纯形表（极大化问题，约束条件均为“W”型），其中x4,%,x6为松弛变量。Xbxxxxxx;2 1 2 3 4 5 6 x12/300110410-201165c-z000-40-9jj，对偶问题的最优解『二.若X,y分别是线性规划的原问题和对偶问题的可行解，则有 CXYb；又若CX=Yb成立，则X和Y分别是线性规划的原问题和对偶问题的 。.用标号法求解网络最大流问题，当求的最大流的同时，也得到了最小截集，它是由点集和点集构成的点集切割中（正还是反）向弧组成。.在完全市场经济的条件下，当某种资源的市场价格低于影子价格时，企业应 该资源，而当某种资源的市场价格高于影子价格时，则企业应 该资源，可见影子价格对市场有调节作用。.若运输问题的产销平衡表中有m个产地和n个销地，则其决策变量有个，其数值格有个。第i第i•个项目被选中注第i•个项目未选中,请用xi1,.某工程公司拟从四个项目中选择若干项目。若令x.=，i0,的线性表达式表示下列要求：①若项目2被选中，则项目4不能被选中：；②只有项目1被选中，项目3才能被选中：。.表上作业法求解运输问题，若已计算出某空格的检验数为-1,现从该空格出发进行调整，设调整量为2,则调整后可使总运费下降。.设线性规划问题max:{CX|Ax=b,X>0}有最优解X*和影子价格Y*,则线性规划问题max:{2CX|Ax=b,X>0}的最优解二，影子价格=.如图所示，该网络的最小支撑树的权和为23.可行流应满足两个限制条件，即容量限制条件和24.线性规划模型包括23.可行流应满足两个限制条件，即容量限制条件和24.线性规划模型包括、约束条件和目标函数三个要素。25.在运输问题模型中，m+n-1个变量构成基变量的充要条件26.线性规划问题的所有可行解构成的集合是26.线性规划问题的所有可行解构成的集合是，线性规划问题的每个基可行解对应可行域的27.用大M可行域的27.用大M法求解Max型的线性规划时，人工变量在目标中的系数均为，若最优解中含有人工变量，则原问题无可行解。28.已知最优基28.已知最优基B=，CB=(3,6)，则对偶问题的最优解是.将非平衡运输问题化为平衡运输问题，在表上相当于增加一个虚设的，在模型中相当于增加若干个 变量。.在资源优化的线性规划问题中，某资源有剩余，则该资源影子价格等于。.若X、r分别是线性规划的原问题和对偶问题的可行解，则有 CXYb.请在下图所示的最短路问题求解过程中进行一步：下一步给节点标号，标号

.动态规划模型中，状态变量的选择要满足两个条件：①能描述问题的过程；②。.动态规划问题的研究对象是 问题。.一般的排队系统有三个基本组成部分，即 、排队规则和服务机构。.当顾客的到达形成强度为九的泊松流时，对于充分小的At，在时间区间［t,t+At］内有1个顾客到达的概率P（t,t+At）=。1.在M/M/1/N/8排队模型中，设顾客平均到达率为九，则被拒绝排队的顾客的平均数为。.在允许缺货、生产需要一定时间的确定型存储模型中，最优单位费用记为Co,记不允许缺货，而其他参数不变的情况下的最优单位费用为C/则C1Co（选大于还是小于）。.已知报童每日售出报纸份数厂的概率为P（r），每售出一份报纸赚k元；如报纸未能售出，每份赔h元。则该报童应准备的报纸最佳数量°应满足的条件存储费每年每件q=20存储费每年每件q=20元,不K（Q）」40（元）“<150⑵一138（元），Q>150。.某厂每年需某种元件1000个，每次订购费C3=100元,允许缺货。又若元件单价K随着采购数量的不同而不同:则此时的最佳订购数量Q*=个。.在M/M/1/N/8模型中，设顾客平均到达率为九，则该排队系统的有效到达率九二；而在M/M/18/m模型中系统的有效到达率e九二 . 9e.某蛋糕房的顾客到达服从九二1人/分钟的泊松分布，则某一刻钟内无顾客到达的概率为，在4分钟内有3名以上顾客到达的概率为。四、计算题1.（20分）某建材厂生产四种型号的特用构件：1型、11型、111型、”型。各型号每件所需组装时间、检验时间、销售收入及该厂组装调试能力如表1所示。1型11型111型“型工厂生产能力（h）组装时间（h）81012152000检验时间（h）2245500售价（百元）46810但现在因为某种特型材料比较紧张，每月最多只能进货180只（每件构件用一只），其中0型、”型用到的不超过100只。令q,x2,弋,x4依次表示各型号每月计划产量。现工厂拟定使目标总销售收入z为最大的生产计划。（1）写出该问题的数学模型，对于约束条件依下列顺序：组装时间、检验时间、特种材料数、、111型、"型用到的特种材料数，并引入松弛变量使之成为等式。（5分）（2）用单纯型法求解的终表入下表。CBXBB-ib468100000xxxxxxxx0x50 1—-0.2 2 0 3 0.2 4 0 5 0.1 6 -0.5 7 0 8 16 8 x1250.51000.25-0.75000 2 x50.300.20-0.150.2510107x500.200.81-0.10.5004c-z-1000-0.5-0.500jj依据上表，分别回答下列问题：TOC\o"1-5"\h\z①最优生产计划是什么？是否还有其他的最优生产计划？为什么？ （4分）②组装时间的影子价格是多少？ （1分）③若外厂可调剂增加80h的检验时间，但每小时需付0.4百元，这样的调剂值得吗？能增加多少收入？ （4分）④设1型构件售价由4百元增加到4.5百元，最优计划要改变吗？如果增加到5.5百元呢？说明理由。（2分）⑤写出本问题的对偶模型，并指出其最优解。 （4分）2.（20分）某企业利用三种资源生产两种产品的最优计划问题归结为下列线性规划maxZ=5x+4x2'x+3x<90X1+x2<80

“x/+x2<45产jx2>0已知最优表如下。c.54000

CXB-ibxxxxxx250124-55x351001-14110010-122c-z000-1-3JJ（1）确定x2的系数c2的变化范围，使原最优解保持最优；（3分）（2）若c2=6,求新的最优计划；（5分）（3）b3在什么范围内变化，原最优基不变？ （2分）（4）若b3=55,求出新的最优解； （5分）（5）设企业研制了一种新产品，对三种资源的消耗系数列向量以P6表示，P6=（3/211/2＞。问它的价值系数c6符合什么条件才必须安排它的生产？设c6=3,新的最优生产计划是什么？（5分）.（20分）某电冰箱厂生产单、双门两种冰箱，每台所需组装时间、调试时间、销售收入及该厂的组装、调试能力如下表，电机每月进货最多50个（每台冰箱用1台电机），令'x2分别为单、双门冰箱的月产量。现工厂需拟订使总收入Z为最大的生产计划。单门双门月生产能力组装时间（h）10151000调试时间（h）25270销售收入（元）10001300（1）写出此问题的数学模型（约束条件依次为组装时间、调试时间、电机数）（3分）（2）下面是用单纯形法求解此问题过程中的一个不完全表，请将表格补充完整；（4分）C10001300000CXB-ibxxxxx B—-5 2 3—4--15x-301-5x10012O（3）上表是否为终表，为什么？若是，写出最优生产计划和电机的影子价格；在执行这一计划后，哪种资源有剩余，剩余多少？（5分）（4）写出上述规划的对偶规划模型及其最优解；（4分）（5）现又设计出三门冰箱，每台组装时间20h，调试时间10h，销售收入1600元，问是否

应考虑生产三门冰箱？请说明理由。（4分）.（15分）下图网络弧上的数字为容量，括弧内的数字为该弧的流量。（1）在括号内填上适当的数字，使构成一个可行流。（2分）（2）在下表中填出截集与截量。（3分）江1aV1）C（V15V1）①、②、③④、⑤、⑥（3）用标号法解此网络最大流，并指出最小截集。（10分）.（15分）某照相机厂生产A、B、C三种型号的产品，每架均需经机身制造、零件装配和检验包装三道工序。各型号产品所需工时数、每月工时限量及销售利润见下表。根据市场情况，C型每月产量应控制在150架以内。现工厂需拟定使总利润z最大的生产计划。A型B型C型工时限量（h）机身制造时间（h）1272500零件装配时间（h）23.513500检验包装时间（h）1231500销售利润（元/架）102050（1）写出此问题的数学模型（变量\,x2,5分别表示A、B、C型产品的月产量，约束条件依次为：机身制造时间、零件装配时间、检验包装时间及C型产量）（2分）（2）下表是用单纯形法解此问题过程中的一个不完全表，请将表完成；（4分）CT1020500000C B—X B—B-1bx 1-x—2—x—3—x 4-x 5-x―6 x——7 4000010-1-41512.50001-1.754.2552510000.5-1.5150010001

检验数。,（3）上表是否为终表？若是，请写出最优生产计划及检验包装时间的影子价格；（3分）（4）写出此问题的对偶问题数学模型，并指出其最优解；（3分）（5）现又设计出D型产品，每架需机身制造、零件装配和检验包装时间分别为6、2、2（h），销售利润为30元/架，问是否应考虑生产D型产品？为什么？（3分）.考虑非线性整数规划maxznxj检验数。,（3）上表是否为终表？若是，请写出最优生产计划及检验包装时间的影子价格；（3分）（4）写出此问题的对偶问题数学模型，并指出其最优解；（3分）（5）现又设计出D型产品，每架需机身制造、零件装配和检验包装时间分别为6、2、2（h），销售利润为30元/架，问是否应考虑生产D型产品？为什么？（3分）x+xx+x+x=20W]X>0且为整数i=1,2,3l-i3号04于3现拟用动态规划方法解此问题（用通常的逆推解法）,其中g(X)=b3<X<10现拟用动态规划方法解此问题（用通常的逆推解法）,3333—x10<x<20、103 3要求：（1）写出以下表达式或集合的具体内容：①本问题的状态转移方程s二k+1‘斗sk）= ②递推方程〈f（s）=k44 ③第1阶段的状态集合S[={ }④第2阶段状态为5时的允许决策x2的集合D2（5）={ }；7.有M/M/1/5/8模型，平均服务率为N=10，平均到达率九二15，问：（1）有效到达率和服务台的服务强度；（2）系统中的平均顾客数；（3）系统的满员率；（4）服务台应从哪些方面改进工作？理由是什么？.设某公司利用塑料作原料制成产品出售，对原料需求的概率如下表所示：需求量厂/箱2030405060概率P(r)(ZP(r)=1)0.10.20.30.30.1已知每箱塑料购买价为400元，每次订购费03=50。元，存储费每箱C「50元，缺货费每箱C2=600元。该厂希望制定（s,S）型存储策略，试求S及S的值。.某一售票窗口，已知顾客按平均为2分30秒的时间间隔的负指数分布到达,顾客在售票窗口的服务时间平均为2分钟。（1）若服务时间也服从负指数分布,求顾客为售票所需的平均逗留时间和等待时间。（2）若八，、Ie-y+iy>1经过调查，顾客在售票口前至少占用1分钟,其概率密度为f（y）=\M।，求顾客[0y<1为售票所需的平均逗留时