运筹学复习题

1运筹学复习题第一阶段练习题一、填空题1．某足球队要从1、2、3、4号五名队员中挑选若干名上场，令号不上场第号上场第iixi014,,1i，请用xi的线性表达式表示下列要求：(1)若2号被选中，则4号不能被选中：_________________；(2)只有1名队员被选中，3号才被选中：___________________。2．线性规划的对偶问题约束的个数与原问题____________的个数相等。因此，当原问题增加一个变量时，对偶问题就增加一个____________。这时，对偶问题的可行域将变_______________(大、小还是不变？)，从而对偶目标值将可能变____________(好还是坏？)。3．将非平衡运输问题化为平衡运输问题，在表上相当于增加一个虚设的，在模型中相当于增加若干个变量。二、某厂生产Ⅰ，Ⅱ，Ⅲ三种产品。产品Ⅰ依次经A、B设备加工，产品Ⅱ经A、C设备加工，产品Ⅲ经C、B设备加工。已知有关数据如下表所示，请为该厂制定一个最优的生产计划。产品机器生产率（件/小时）原料成本产品价格ABCⅠⅡⅢ102020510201525105010045机器成本（元/小时）200100200每周可用小时数504560三、某厂准备生产A、B、C三种产品，它们都消耗劳动力和材料，有关数据见下表所示：ABC拥有量（单位）劳动力材料6334554530单位产品利润（元）314（1）确定获利最大的产品生产计划；（2）产品A的利润在什么范围内变动时，上述最优计划不变；（3）如设计一种新产品D，单件劳动力消耗为8单位，材料消耗为2单位，每产品消耗定额资源2件可获利3元，问该种产品是否值得生产？（4）如劳动力数量不变，材料不足时可从市场购买，每单位0.4元，问该厂要不要购进原材料扩大生产，购多少为宜？四、已知某运输问题的产销平衡表和单价运价表如下表所示：B1B2B3B4B5B6产量A1A2A3A424341252324234213442541250406031销量305020403011求：（1）求最优的运输调拨方案；（2）单位运价表中的c12，c35，c41分别在什么范围内变化时，上面求出的最优调拨方案不变。五、某彩色电视机组装工厂，生产A、B、C三种规格电视机。装配工作在同一生产线上完成，三种产品装配时的工时消耗分别为6小时，8小时和10小时。生产线每月正常工作时间为200小时；三种规格电视机销售后，每台可获利分别为500元，650元和800元。每月销量预计为12台、10台、6台。该厂经营目标如下：1p：利润指标定为每月4106.1元；2p：充分利用生产能力；3p：加班时间不超过24小时；4p：产量以预计销量为标准；为确定生产计划，试建立该问题的目标规划模型。答案：一、填空题1．0;13142xxxx2．变量个数，约束条件，小，坏3．产地或销地，松弛（或剩余）销地产地3二、答：用jx表示第j种产品的生产数量，使该厂获利最大的线性规划模型为：321321)2020010100()5020020200()2010020200()1045()25100()1550(maxxxxxxxz三、答：（1）建立线性规划模型，模型中321,,xxx，分别代表A、B、C产品的产量，用单纯形法求解得最优计划的单纯形表如下：1x2x3x4x5x1x53x310-1/31011/3-1/5-1/32/5jjzc0-20-1/5-3/5（2）产品A利润在（544,522）范围内变化时，最优计划不变。（3）安排生产新产品D是合算的（4）材料市场价格低于影子价格，故购进是合算的。用参数规划计算确定购15单位为最适宜。四、答：（1）最优的运输调拨方案如下表所示：B1B2B3B4B5B6产量A1A2A3A42010302020391301150406031销量3050204030113,2,1,060203524510320150202101jjxxxxxxx4（2）保持最优调拨方案不变的cij变化范围为：c12≥1；c35≥3；c41≥2五、答：设生产电视机A型为1x台，B型为2x台，C型为3x台，该问题的目标规划模型为：)(min6655444332211ddddddpdpdpdpz第二阶段练习题一、某汽车公司制定5年内购买汽车的计划，下面给出一辆新汽车的价格（如表1所示）以及一辆汽车的使用维修费用（万元，如表2所示）。使用网络分析中最短路方法确定公司可采用的最优策略。表1年号12345价格22.12.32.42.6表2汽车使用年龄0～11～22～33～44～5维修费用0.71.11.522.5二、某项工程有关资料如表3所示，工序紧前工序平均工序时间(周)估计的工序时间方差2A—21.05)6,,1(0,;0,,61012242001086106.180065050032166355244133222321411321iddxxxddxddxddxdddddxxxddxxxii5B—32.25CB2.54.34DB63.70EA、C204.95FD、E44.66GF24.05(1)画出工程网络图，确定关键工序及完工期；(2)求工程在30周内完成的概率。三、某工厂正在考虑是现在还是明年扩大生产的规模。由于可能出现的市场需求情况不一样，预期利润也不同。已知市场需求为高（1E）、中（2E）、低（3E）的概率及不同方案的预期利润（单位：万元），如表4所示。对该厂来说，损失1万元的效用值为0，获利10万元效用值为100，对以下事件效用值无差别：①肯定得8万元或0.9概率得10万和0.1概率失去1万；②肯定得6万或0.8概率得10万和0.2概率失去1万；③肯定得1万或0.25概率得10万和0.75概率失去1万。表41E2E3E2.0)(1EP5.0)(2EP3.0)(3EP现在扩大明年扩大10886-11要求：（1）建立效用值表（2）分别根据实际盈利额和效用值按期望值法确定最优决策。四、某工厂在一年进行了A、B、C三种新产品试制，由于资金不足，估计在年内这三种新产品研制不成功的概率分别是0.40、0.60、0.80，因而都研制不成功的概率为0.40×0.60×0.80=0.192。为了促进三种新产品的研制，决定增拨2万元的研制费，并要资金集中使用，以万元为单位分配。其增拨研制费与新产品不成功的概率如表5所示。试问如何分配费用，使这三种新产品都研制不成功的概率为最小。表5不成功概率ABC010.400.200.600.400.800.50事件概率方案新产品研制费S620.150.200.30五、分配甲、乙、丙、丁、戊五个人去完成A、B、C、D、E五项工作，每个人完成各项任务的时间如下表所示。(表中单位：小时)任务人数ABCDE甲乙丙丁戊25283141384038262633352728403224423723453029262032已知甲不可能完成任务D，丁只可以完成任务B、C，试确定最优分配方案，使完成任务的总时间为最少。答案:1．0→2→5，即第一年年初购新车，第三年年初购新车。2．（1）T=31.5（2）37.07%3．结论：按实际盈利额选存的扩建方案；如按效用值选明年的扩建方案。4．1-0-1,1f=0.065、答：解：25283138036251340382626331412007352728403280113542373750373730292620321096012MMMMMMMM(0)36258141200228(0)1130375(0)37421096(0)7(0)16256141000(0)10(0)3150373(0)37441076(0)5MkMMMMMMM7即：甲——A；乙——E；丙——B；丁——C；戊——DMinZ=25+33+27+37+20=142小时第三阶段练习题一、填空题1．在矩阵对策),,(***EDSG中，（),**YX是*G解的条件是。2．在标准的M/M/1排队系统中，设顾客到达率为，服务率为，则队长sL____________，它表示系统中的____________，排队长qL____________，它表示系统中的____________，qsLL____________。3．若由一种情况转换至另外一种情况的过程具有转移概率，而且此种转移概率又可以依据紧接的前项情况推算出来，则这种过程称为___________________。二、（1）某基建项目的活动明细表如下，编绘该项目的箭线式网络图。活动明细表活动名称ABCDEF紧前活动无AABCC，D（2）求以下箭线式网络图的关键路线及工程完工期(时间单位：天)三、已知某工程有六项活动，有关数据如下表：活动正常时间极限时间正常直接费用极限直接费用a(0——1)b(1——2)c(1——3)d(2——3)e(2——4)f(3——4)1477841354525000800014000100008000750050001400020000150001300016000（1）画出箭线式网络图；（2）如果要求赶工期，在12周内完成，请给出优化方案。8四、求下图的网络最大流，并写出最小割集。V14V487645Vs9V23V53Vt155287V37V6五、某书店希望订购最新出版的好图书出售。根据以往经验，新书的销售量可能为50本，100本，150本或200本。假定每本书的订购价为4元，销售价为6元，剩余处理价为每本2元。试求：（1）建立损益矩阵；（2）分别用悲观法、乐观法及等可能发决定该书店应订购的新书数量；（3）建立后悔矩阵，并用后悔值法决定书店应订购的新书数。答案:一、填空题1．),(max*min*),(min*max*)*,*(yxESxDyyxEDySxyxE2．，平均顾客数，，排队等待的平均顾客数，3．马尔科夫过程二、工程完工期：T=22(天)三、活动活动节点赶工期直接费用增长率活动时间活动费用a*b*cd*e*0——11——21——32——32——4000310.0000.0000.0005000.0001666.667147475000.0008000.00014000.00015000.0009666.6679f*3——414250.000311750.000*：关键路径活动整个工程周期：12直接费用总额：63416.667四、解：找增广链：tsVVVV4141ftsVVVV5232ftsVVVV6373f(Vs,4)V1(4,4)V4(8,4)764(5,4)Vs(9,3)V2(V1,4)(3,3)V5(3,3)Vt(15,7)528(7,7)V3(7,7)V6(Vs,8)最小割集为：V*={（V3，V6），（V2，V5），（V1，V4）}C*（V，V）=14且V*（f）=14五、答：（1）损益矩阵50100150200501001001001001000200200200销售数量益损值（元）订购数量10150-100100300300200-2000200400（2）悲观法：50，乐观法：200，等可能法：100或150（3）后悔矩阵：50100150200Max500100200300300100100010020020015020010001002002003002001000300故按后悔值法决策为200。运筹学第四阶段练习题一、填空题1．除图解法外，常用的求解线性规划问题的方法是。2．在矩阵对策),,(***EDSG中，（),**YX是*G解的条件是。3．设P为概率矩阵，则当n时，nP称作P的______________