运筹学练习题

运筹学练习题填空题1.运输问题中，当总供应量小于总需求量时，求解时需虚设一个点，此点的供应量(或需求量)应为。2．线性规划中，任何基对应的决策变量称为。整数规划(是或不是)线性规划。3．用单纯法求解目标函数是最大化的线性规划问题时，为一基本可行解，有一个检验数，并且对其中是其的系数向量，那么该线性规划问题具有解，若所有的检验数非正，且存在某个非基变量的检验数为零，则线性规划问题有解。4．在用图论解决问题时，常用表示研究的对象，对象之间的关系用表示。5．在双代号网络图中，虚工作只表示相邻工作之间的，不占用。6．用对偶单纯型法求解线性规划问题时，得到了检验数为则对偶问题的最优解为，假若此原问题为无界解，则其对偶问题可行解（存在或不存在）。7．在资源受限制时，时间与资源优化的方法之一，是先将有限的资源从活动调往活动，以便均衡地使用资源8.决策分析的基本原则为，系统原则，,信息对称、准全原则.9在一个工厂中，有一个厂址选择的决策，这属于，生产品合格标准选择属于。10.决策的一般过程为目标确定，，，方案选优，决策。11.在决策中，人们只知道可能的情况是什么，但不知道各情况出现的可能性大小，有一个实力相对来说很小的企业，它应该采取原则。如果知道了各情况的可能性，这属于。12在决策中，，，损益函数是决策的三要素。13有4个人要做4件事，每人做而且只能做一件事，现得到了最优指派方案，则最小可以用条线覆盖所有的0元素，此指派问题有个独立0元素。14在一个求最小值得运输问题中，有4个销售地，5个生产地，则系数矩阵中有个独立行向量，如果检验数有9个大于0，其他三个x1,x2,x3为-5，-2，-3，则变为基变量的是。15在存储问题中，人员外出采购等的费用属于，停工待料的损失属于。16在网络流中，与链同向的弧称为，在增广链上，与链同向的弧是。17用闭合回路法寻求改进运输方案时，首先应对每一空格求出

和

。18在用单纯形法的计算极大值过程中，如果，并且存在，则可以判定线性规划问题存在无穷多最优解。19在用人工变量法求得最优解中含有人工变量非0，则原问题，若两阶段法中第一阶段的目标函数值为0，则原问题。20现有一求最小值的线性规划问题，有m个等式约束，n个小于0的变量，则对偶问题有m个，n个。二选择题1．在线性规划模型中，没有非负约束的变量称为()。A．多余变量B．松弛变量C．自由变量D．人工变量2．在双代号网络图中，下列叙述正确的是()。A．可以有两个起始点B．可以出现回路C．可以有两个终点D．相邻结点只能有一条连线3．对于m个发点、n个收点的运输问题，叙述错误的是(

)。A．该问题的系数矩阵有m+n行B．该问题的系数矩阵的秩必为m+n-1

C．该问题的系数矩阵有m×n列

D．该问题的最优解必唯一4．在动态规划中，如果某阶段状态给定后，则在这阶段以后过程的发展不受这阶段以前各状态点的影响，这个性质称为：()。A.动态性B.阶段性C.无后效性D.优先性5．在树图中，()不正确。A.若树T有n个点，则其边数为n-1B.树中若多出一边，必出现圈C.树中点与点可以不连通D.树中若除去一边，必不连通6.对有m个产地n个销地的运输问题，有下列命题①任意一个运输问题都有最优解，②产量与销量均为整数时必有整数最优解，③m+n-1个变量构成基变量的充要条件是它不包含任何闭回路，④表上作业法的条件是产销平衡问题，其中正确的个数为()A.1B.2C.3D.47．下列哪项不属于按决策性质的重要性分类A序贯分类B战略决策C执行决策D管理控制8下列哪些条件可得出线性规划问题无可行解①可行域无界②用大M法求解时，最优解中还有非零的人工变量，③两阶段法中第一阶段目标函数值大于0④非基变量变为基变量时，其列向量分量非正，A②③④B①②③C①②④D①③④9.瞬时供货且允许缺货的经济批量模型中，若订货费，存储费和缺货费同时增加n倍，则经济订货批量A.为原来的C为原来的倍，D不变10在相同的单位时间内，允许缺货的订货次数比不允许缺货时的订货次数A．一样多B多C少D无法确定11某个常数b波动，最优表中引起变化的有ABCD12目标函数为求最大值，为保持最优基不变，的波动值可由解不等式（）求得ABCD13原问题与对偶问题都有可行解，则A原问题有最优解，对偶问题可能没有最优解B原问题与对偶问题可能都没有最优解C可能一个有最优解，另一个有无界解D两个问题都有最优解14下列说法正确的是A截集是子图B截量等于截集中弧的流量之和C截量不小于最大流D截量不超过最大流15在目标函数求最大值的对偶单纯形法中，如果在某一步迭代过程中出现了基变量某一分量小于0,其他都大于0，其对应系数行向量全是正数，所有检验数小于0，则A原问题有可行解B原问题没有可行解C对偶问题没有可行解D对偶问题可能有无界解16允许缺货，备货时间短的存储模型属于At0存储策略B（s,S）策略C（t,s,S）策略D其他策略17下列属于生产费的是A手续费B货物的成本费C材料费与加工费D缴纳的罚款18在网络计划图中的时间-费用优化中，下列哪一项是间接费用A公司电话费B项目使用的材料费C工人的工资D购买大型设备的费用19下列说法哪一个是正确的A次序列（3，2，4，1，0）的点不能构成一个图；B对偶问题最优解是原问题检验数的相反数；C运输问题与指派问题都有最优解；D在图论中求最短路的Dijkstra算法可以广泛使用。20对偶单纯形法的最小比值规则是为了保证A使原问题可行B使对偶问题保持可行C逐步消除原问题的不可行性D逐步消除对偶问题的不可行性21目标函数的含义是A第一和第二目标恰好到达目标值，第三目标不超过目标值B第一、第二、第三目标同时不超过目标值C首先第一和第二目标同时不超过目标值，然后第三目标不超过目标值D首先第一和第二目标同时不低于目标值，然后第三目标不低于目标值三计算题1.已知线性规划问题MAXZ=2X1+4X2+X3+X4X1+3X2+X4<=82X1+X2<=6X2+X3+X4<=6X1+X2+X3<=9X1、X2、X3、X4>=0（1）写出其对偶问题；（2）已知原问题最优解为X=（2，2，4，0）试根据对偶理论，直接求出对偶问题的最优解。2．有四个工人，要分别指派他们完成四项不同的工作，即每人只做一件事，每件事只由一人做。每人做各项工作所需成本如下，问应如何指派工作，才能使他们的总成本最小？单位：百元。工作所需成本工人ABCD甲10743乙95610丙4131411丁75343.下表给出了工序的正常、应急的时间和成本工序紧前工序时间（天）成本时间的最大缩量（天）应急增加成本（万元/天）正常应急正常应急ABCDEFG-AAB、CDCE、F151212107413111410161310850651001208089609040524560608432324325103153512（1）绘制网络图，按正常时间计算完成项目的总成本和工期；（2）按应急时间计算完成项目的总成本和工期；（3）按应急时间的项目完工期，调整计划使总成本最低;(4)已知项目缩短一天额外获得奖金4万元，减少间接费用2.5万元，求总成本最低的项目完工期4S、A、B、C、D、E、T代表七个村镇，它们之间的连线表明各村现有道路交通情况，连线旁的数字代表村和村之间的距离，要求沿图中道路架设电线，使各村镇全部通上电。现知架线成本为10000元/公里，问应如何架线，使总的架线成本为最小？（单位：公里）（10分）AA227TDBS555TDBS17EC413EC45.若一求极大线性规划问题的某步单纯形表为Cj23000b基变量x1x2x3x4x52x11010-1/220x400-41283x201001/43Zj2320-1/413Cj-Zj00-201/4该表是否为最优单纯形表?若是，请说明理由。若不是，则继续迭代直至达到其单纯形终表，并写出该问题的最优解。6．某地方书店希望订购最新出版的图书，根据以往经验，新书的销售量可能是50,100,150,200。假定每本新书订购价为4元，销售价为6元，剩书的处理价为2元。（1）分别用悲观法、乐观法及等可能法就该书店应订购的新书做决策；（2）建立后悔值矩阵，用后悔值法决定应订购的新书数；（3）书店根据以往的统计资料新书销售的规律见下表，分别用期望值法与后悔值法决定订购数量；（4）如果某市场调查部门能帮助书店调查销售量的确切数字，该书店愿意付出多大的调查费用。需求数50100150200比例（%）204030107某企业每月生产某零件的生产量为800件，该零件月需求量为500件，每次准备成本为50元，每件存储费为10元，缺货费为8元，求最优生产批量与生产周期8教材P431.69P993.410下表是某项作业的明细表，解答表后问题工序紧前工序工序时间工序紧前工序工序时间A--6GAB10B--9HEF12CA13IDH8DC5JI17EC16KDHG20FA.B12LG25求工序H，K的工作总时差与工作自由时差求出项目的完工时间。11某工厂正在考虑明年还是现在扩大生产规模。由于可能出现的市场需求情况不一样，预期利润也不同，已知市场需求的概率及不同方案时的预期利润如下表所示。对该厂来说损失1万元效用值为0，获利10万元为1，对以下事件效用值无差别：（1）肯定得8万元或以0.9的概率得10万和0.1的概率失去1万；（2）肯定得6万或0.8概率得10万和0.2失去1万元；（3）肯定得1万或以0.25概率得10万和0.75概率失去1万。（a）建立效用值表（b）分别根据实际盈利额和效用值按期望值法确定最优决策12一软件公司需要在自主开发一种会计软件和接受委托进行办公自动化软件开发二者之间进行抉择。若自主开发，根据过去的开发经验，开发一个会计软件需要投资20万元。若开发得成功（功能好于市场上已存在的任何类似产品）的概率为20%，能以100万元的价格卖给一个大的软件公司；若比较成功（好于部分市场产品）的概率为60%，则价格降为50万元；若不成功（概率20%），则公司无法卖出该产品。公司若决策接受委托开发软件，则可获得20万元的软件开发费。该软件公司还可以出2万元聘请一个咨询公司就该产品的开发问题进行咨询，根据以往统计，该咨询公司准确性的概率如下表所示P(咨询意见|成功状态)成功状态很成功成功不成功咨询意见可以自主开发不可自主开发0.90.50.60.10.50.4（1）画出完整的决策树，并根据最大期望值方法找出最优决策路线；（2）是否请咨询公司进行咨询，其咨询意见的样本信息期望值是多少？13某食品公司考虑是否参加为某运动会服务的投标，以取得饮料或面包二者之间的供应特许权。二者中任何一项投标被接受的概率为40%。公司的获利情况取决于天气。若获得的是饮料供应特许权，则当晴天时可获利2000元；雨天时要损失2000元。若获得的是面包供应特许权，则不论天气如何，都可获利1000元。已知天气晴好的可能性为70%。问：（1）公司是否可参加投标？若参加，为哪一项投标？（2）若再假定饮料投标，公司可选择供应冷饮或咖啡。如供应冷饮，则晴天可获利2000元，雨天损失2000元；若供应咖啡，则雨天可获利2000元，晴天1000元，公司是否应参加投标？参加哪一项投标？14某项工作有五个岗位，甲、乙、丙、丁、戊5人去操作，由于每人专长不同，各个工人在不同岗位上生产效率不一样，具体见下表（件/分钟），问如何分配，使这项工作的效率最高？IIIIIIIVV甲乙丙丁戊234173425625341523253762415（1）求下图各点间的最短路（2）若从点1到点8分别有货物100，150，80,90,120,115,140，80吨需要集中在一起存储，问应存储中心建在何处恰当？112354678101010561314547459四建模题1某医药公司现有两个制药厂A1和A2，三个销售点B1、B2和B3。由于供不应求，公司打算由两个拟建的制药厂A3和A4中选择一个来兴建新厂。新厂投产后，估计每月的固定成本：A3是100万元，A4是120万元。各销售点每月药品需求量、各制药厂每月药品产量和每箱药品运费见下。在两个拟建的制药厂中，应当选择哪个，使总成本最低（建立数学模型）？制药厂产量(万箱/月)运资(元/箱)B1B2B3A150323A2701058A3201310A420453销售点需求量（万箱/月）B150B260B3302一个农民需要决定在他的20亩菜地与30亩小麦地中使用肥料，农业技术员通过对土壤的分析已经建议每亩菜地最少需要施6千克氮，2千克磷和1.5千克钾，每亩小麦地最少需要施8千克氮、1千克