运筹学题库第一章

1求解下述线性规划问题2设某种动物每天至少需要700g蛋白质、30g矿物质、100mg维生素，现有五种饲料可供选择，每种饲料每公斤营养成分的含量及单价如表所示。试建立既满足动物生长需要，又使费用最省的选用饲料方案的线性规划模型。饲料蛋白质/g矿物质/g维生素/mg价格/（元/kg）1310.50.2220.510.7310.20.20.446220.35180.50.80.83某医院昼夜24h各时段内需要的护士数量如下：2：00—6：0010人，6：00—10：0015人，10：00—14：0025人，14：00—18：0020人，18：00—22：0018人，22：00—2：0012人。护士分别于2：00，6：00，10：00，14：00，18：00，22：00分6批上班，并连续工作8小时。试建立模型，要求既满足值班需要，又使护士人数最少。4某人有一笔30万元的资金，在今后三年内有以下投资项目：（1）三年内的每年年初均可投资，每年获利为投资额的20%，其本利可以起用于下一年投资；（2）只允许第一年年初投入，第二年年末可收回，本利合计为投资额的150%，但此类投资限额不超过15万元；（3）于三年内第二年初允许投资，可于第三年末收回，本利合计为投资额的160%，这类投资限额20万元。（4）于三年内的第三年初允许投资，一年回收，可获利40%，投资限额为10万元。试为该人确定一个使第三年末本利和为最大的投资计划。网上下载部分：某厂准备生产A、B、C三种产品，它们都消耗劳动力和材料，如下表：产品名称耗用设备（台时/件）耗用材料（kg/件）利润（元/件）A633B341C554资源量45（台时）30（kg）试建立能获得最大利润的产品生产计划的线性规划模型，并列出初始单纯形表。某航空公司为满足客运量日益增长的需要，正考虑购置一批新的远程、中程、短程的喷气式客机。每架远程的喷气式客机价格670万元，每架中程的喷气式客机价格500万元，每架短程的喷气式客机价格350万元。该公司现有资金15000万元可以用于购买飞机。根据估计年净利润每架远程客机42万元，每架中程客机30万元，每架短程客机23万元。设该公司现有熟练驾驶员可用来配备30架新的飞机。维修设备足以维修新增加40架短程的喷气式客机，每架中程客机的维修量相当于4/3架短程客机，每架远程客机的维修量相当于5/3架短程客机。为获得最大利润，该公司应购买各类飞机各多少架？(建立模型，不需求解)下表1是某求极大化线性规划问题计算得到的单纯形表。表中无人工变量，为待定常数，。试说明这些常数分别取何值时，以下结论成立。（1）表中解为惟一最优解；（2）表中解为最优解，但存在无穷多最优解；（3）该线性规划问题具有无界解；（4）表中解非最优，为对解改进，换入变量为，换出变量为表1基41002-1-301-103-500-4100-301.根据以下条件建立线性规划数学模型某工厂生产A、B、C三种产品，每种产品的原材料消耗量、机械台时消耗量以及这些资源的限量，单位产品的利润如下表所示：单位产品消耗资源ABC资源限量原材料1.01.54.02000机械台时2.01.21.01000单位利润101412根据客户订货，三种产品的最低月需要量分别为200，250和100件，最大月销售量分别为250，280和120件。月销售分别为250，280和120件，问如何安排生产计划，使总利润最大？解：设X1,X2,X3分别设代表三种产品的产量，则线性规划模型为maxZ=10X1+14X2+12X3s·tX1+1.5X2+4X3≤20002X1+1.2X2+X3≤1000200≤X1≤250250≤X1≤280X1，X2，X3≥02.把下列线性规划问题化成标准形式：答：maxZ’=－5x1+2x23.把下列线性规划问题化成标准形式：minZ=2x1-x2+2x3答：5.根据所给条件建立线性规划模型。某建筑工地有一批长度为10米的相同型号的钢筋，今要截成长度为3米的钢筋90根，长度为4米的钢筋60根，问怎样下料，才能使所使用的原材料最省?答：将10米长的钢筋截为3米和种种类长度ⅠⅡⅢ34021120设X1，X2，X3分别表示采用Ⅰ、Ⅱ、Ⅲ种下料方式的钢筋数，则线性规划模型可写成：minZ=X1+X2+X3s·t2X2+3X3≥902X1+X2≥60X1，X2，X3≥01.下表为用单纯形法计算时某一步的表格。已知该线性规划的目标函数为maxZ=5x1+3x2，约束形式为“≤”，X3，X4为松驰变量，表中解代入目标函数后得Z=10XlX2X3X4－10b-1fgX32CO11／5Xlade01（1）求表中a～g的值（2）表中给出的解是否为最优解?解：（1）a=2b=0c=0d=1e=4/5f=0g=－5（2）表中给出的解为最优解2.用单纯形法求解下列线性规划问题：maxZ=3x1+5x2x1≤15s·t 2x2≤123x1+2x2≤18x1，x2≥0解：化为标准形式maxZ=3x1＋5x2＋x3＋0x4＋0x5s·tx1+x3=152x2+x5=123x1+2x2+x5=18xj≥0（j=1,……，5）cj35000CBxBbx1x2x3x4x50x3150x4120x518101000（2）01032001cj－zj350000x3150x460x56101000101/20（3）00－11cj－zj300－5/200x3135x263x120011/3－1/30101/20100－1/31/2cj－zj000－3/2－1最优解X﹡=（2，6，13，0，0）TZ﹡=363.用大M法求解下列线性规划问题解：化为标准形式maxZ=x1+2x2+3x3－x4－mx5－mx6s·tx1+2x2+3x3+x5=152x1+x2+5x3+x6=20x1+2x2+x3+x4=10xj≥0（j=1,……，6）cj123–1–M–MCBxBbx1x2x3x4x5x6－Mx515－Mx620－1x4101230102150011（2）1100cj－zj4M+15M+29M+3000－Mx55－Mx6152x25002-110（3/2）04/2-1/2011/211/21/200cj－zjM0M+2-M+200－Mx551x1102x2000（2）-110103-1/302/30112/30-1/3cj－zj002M+2-M-20-M3x15/21x15/22x25/2001-1/21/201007/6-3/22/301011/2-1/3cj－zj000-7/2-M-1-Mx*=（，，，0，0，0）T，z*=154.用单纯形法求解线性规划问题minZ=－2x1+x2+x3s·t3x1+x2+x3≤60x1－x2+2x3≤10x1+x2－x3≤20xj≥0（j=1,2，3）解：化为标准形式maxZ’=2x1－x2＋x3s·t3x1+x2+x3+x4=60x1－x2+2x3+x5=10x1+x2－x3+x6=20xj≥0（j=1,……，6）cj2－11000CBxBbx1x2x3x4x5x60x4600x5100x620311100（1）－1201011－1001cj－zj2－110000x4300x1100x61004－51－301－120100（2）－30－11cj－zj01－30－200x4102x115－1x250011－1－2101/201/21/201－3/20－1/21/2cj－zj00－5/20－1/2－1/2最优解X﹡=（15，5，0，10，0，0）TZ﹡=－25福安商场是个中型的百货商场，它对售货人员的需求经过统计分析如下表所示，为了保证售货人员充分休息，售货人员每周工作五天，休息两天，并要求休息的两天是连续的，问该如何安排售货人员的休息，既满足了工作需要，又使配备的售货人员的人数最少，请列出此问题的数学模型。时间所需售货人员数时间所需售货人员数星期一28星期五19星期二15星期六3l星期三24星期日28星期四25．加入人工变量，化原问题为标准形最优单纯形表如下：三、（15分）某厂生产甲、乙两种产品，这两种产品均需要A、B、C三种资源，每种产品的资源消耗量及单位产品销售后所能获得的利润值以及这三种资源的储备如下表所示：ABC甲94370乙46101203602003001）建立使得该厂能获得最大利润的生产计划的线性规划模型；（5分）2）用单纯形法求该问题的最优解。（10分）解：1）建立线性规划数学模型：设甲、乙产品的生产数量应为x1、x2，则x1、x2≥0，设z是产品售后的总利润，则maxz=70x1+120x2s.t.2）用单纯形法求最优解：加入松弛变量x3，x4，x5，得到等效的标准模型：maxz=70x1+120x2+0x3+0x4+0x5s.t.列表计算如下：CBXBb70120000θLx1x2x3x4x50x336094100900x420046010100/30x53003（10）001300000070120↑0000x324039/5010-2/5400/130x420（11/5）001-3/5100/11120x2303/101001/1010036120001234↑000－120x31860/11001－39/1119/1170x1100/111005/11-3/11120x2300/11010-3/222/11701200170/1130/11000-170/11－30/11∴X*=（，，，0，0）T∴maxz=70×+120×=用大M法或对偶单纯形法求解如下线性规划模型：minz=5x1＋2x2＋4x3解：用大M法，先化为等效的标准模型：maxz/=－5x1－2x2－4x3s.t.增加人工变量x6、x7，得到：maxz/=－5x1－2x2－4x3－Mx6－Mx7s.t大M法单纯形表求解过程如下：CBXBb－5－2－400－M－MθLx1x2x3x4x5x6x7－Mx64（3）12－10104/3－Mx7106350－1015/3－9－4－7MM－M－M9M－54M7M－M－M00－5x14/311/32/3－1/301/30——－Mx72011（2）－1－211－5-M－5/3-M－10/3-2M2M-M0M－1/3M－2/32M－5/3－M－3M0－5x15/311/25/60－1/601/610/30x410（1/2）1/21－1/2－11/22－5－5/2－25/605/60－5/601/2↑1/60－5/6－M－M+5/6－5－2x12/3101/3－11/31－1/3x220112－1－21－－5－2－11/311/3－1－1/300－1/3－1－1/3－M+1－M+1/3∴x*=（，2，0，0，0）T最优目标函数值minz=－maxz/=－（－）=一家工厂制造甲、乙、丙三种产品，需要三种资源——技术服务、劳动力和行政管理。每种产品的资源消耗量、单位产品销售后所能获得的利润值以及这三种资源的储备量如下表所示：技术服务劳动力行政管理单位利润甲110210乙1426丙1564资源储备量1006003001）建立使得该厂能获得最大利润的生产计划的线性规划模型；（5分）2）用单纯形法求该问题的最优解。（10分）解：1）建立线性规划数学模型：设甲、乙、丙三种产品的生产数量应为x1、x2、x3，则x1、x2、x3≥0，设z是产品售后的总利润，则maxz=10x1+6x2+4x3s.t.2）用单纯形法求最优解：加入松弛变量x4，x5，x6，得到等效的标准模型：maxz=10x1+6x2+4x3+0x4+0x5+0x6s.t.列表计算如下：CBXBb1064000θLx1x2x3x4x5x60x41001111001000x5600（10）45010600x630022600115000000010↑640000x4400（3/5）1/21－1/100200/310x16012/51/201/1001500x618006/550－1/51150104501002↑－10－106x2200/3015/65/3－1/6010x1100/3101/6－2/31/600x6100004－20110620/310/32/3000－8/3－10/3－2/30∴X*=（，，0，0，0，100）T∴maxz=10×+6×=化为标准型minZ=2x1+x2-2x3-x1+x2+x3=4-x1+x2-x3≤6x1≤0，x2≥0,x3无约束某厂生产甲、乙、丙三种产品，已知有关数据如下表所示：消耗产品原料甲乙丙原料量A63545B34530单件利润415求使该厂获利最大的生产计划。目标函数为maxZ=28x4+x5+2x6，约束形式为“≤”，且x1，x2，x3为松弛变量，表中的解代入目标函数中得Z=14，求出a~g的值，并判断是否最优解。Cj0002812CBXBbx1x2x3x4x5x62x6a30-14/30110x256d205/2028x400ef100Cj-Zjbc00-1g一、分别用人工变量法和两阶段法求解下列线性规划问题maxz=-2x1-3x2-x3x1+4x2+2x3>=83x1+2x2>=6x1,x2,x3>=0三、某文教用品厂利用原材料白坯纸生产原稿纸、日记本和练习本三种产品。该厂现有工人100人，每天白坯纸的供应量为30000千克。如单独生产各种产品时，每个工人每天可生产原稿纸30捆，或日记本30打，或练习本30箱。已知原材料消耗为：每捆原稿纸用白坯纸10/3千克，每打日记本用白坯纸40/3千克，每箱练习本用白坯纸80/3千克。已知生产各种产品的盈利为:每捆原稿纸1元，每打日记本两元，每箱练习本3元。试决定：（1）在现有生产技术条件下，使该厂盈利最大的方案。（2）如白坯纸供应量不变，而工人的数量不足时可从市场上招收临时工，临时工费用为每人每天15元。问该厂应否招收临时工及招收多少人为宜。3、某饲养场需饲养动物，设每头动物每天至少需700g蛋白质、30g矿物质、100mg维生素。现有五种饲料可供选用，各种饲料每kg营养成分含量及单价如表1-8所示。

要求确定既满足动物生长的营养需要,又使费用最省的选用饲料的方案。列解模型(40分)某灌区的开发，涉及三种主要的限制资源，可能安排的作物有三种，种植各种作物每亩所需要的资源及其净收益见表1。资源名称单位可利用资源数各种作物所需资源数玉米水稻棉花土地亩100111肥料100公斤50000.5水10080120各种作物每亩净收益304012试列出使灌区的总收益最大的线性规划模型。应用单纯形法求解该模型。4．（15分）某农场生产四种农作物，每种农作物的成本和利润如下：农作物肥料（公斤/亩）杀虫剂（公斤/亩）利润（元）萝卜4250包心菜2940洋葱5210土豆0320目前农场有400公斤肥料和500公斤杀虫剂，问每种农作物种植多少亩才使利润最大？）某公司生产甲、乙两种产品，生产所需原材料、工时和零件等有关数据如下：甲乙可用量原材料（吨/件）工时（工时/件）零件（套/件）2252.513000吨4000工时500套产品利润（元/件）43要求：⑴建立使利润最大的生产计划的数学模型；⑵将数学模型化为标准形式；⑶用表解形式的单纯形法求解；⑷求最大利润。解：⑴设甲、乙两种产品的生产数量为x1、x2，∵x1、x2≥0设z为产品售后总利润，则maxz=4x1+3x2s.t.⑵加入松弛变量x3，x4，x5，得到等效的标准形式：maxz=4x1+3x2+0x3+0x4+0x5s.t.⑶用表解形式的单纯形法求解，列表计算如下：CBXBb43000θLx1x2x3x4x50x33000221003000/2=15000x4400052.50104000/5=8000x5500（1）0001500/1=500000004↑30000x320000210-22000/2=10000x415000（2.5）01-51500/2.5=6004x150010001——4000403↑00-40x3800001-0.8（2）800/2=4003x26000100.4-2——4x150010001500/1=5004301.2-2000-1.22↑0x5400000.5-0.413x21400011-0.404x110010-0.50.4046004310.4000-1-0.40据上表，X*=（100，1400，0，0，400）T⑷最大利润maxz=4×100+3×1400=4600（元）33.一家昼夜服务的饭店，24小时中需要的服务员数如题33表：题33表起迄时间服务员的最少人数2∶00—6∶0046∶00—10∶00810∶00—14∶001014∶00—18∶00718∶00—22∶001222∶00—2∶004每个服务员每天连续工作8小时，且在时段时上班。问题的目标是求满足以上要求的最少上班人数，试对这个问题建立线性规划模型。34.求出线性规划问题：的最优解。1、消费者购买某一时期需要的营养物（如大米、猪肉、牛奶等），希望获得其中的营养成分（如：蛋白质、脂肪、维生素等）。设市面上现有这3种营养物，其分别含有各种营养成分数量，以及各营养物价格和根据医生建议消费者这段时间至少需要的各种营养成分的数量（单位都略去）见下表。营养物营养成分营养物营养成分甲乙丙至少需要的营养成分数量A462080B11265C10370D21735450价格252045问：消费者怎么购买营养物，才能既获得必要的营养成分，而花钱最少？只建立模型，不用计算。解：设购买甲、乙、丙三种营养物的数量分别为则根据题意可得如下线性规划模型：2.将下列线性规划化为标准形式(1)3．用单纯形法求解下列线性规划6某投资人现有下列四种投资机会,三年内每年年初都有3万元（不计利息）可供投资：方案一：在三年内投资人应在每年年初投资，一年结算一次，年收益率是20％，下一年可继续将本息投入获利；方案二：在三年内投资人应在第一年年初投资，两年结算一次，收益率是50％，下一年可继续将本息投入获利，这种投资最多不超过2万元；方案三：在三年内投资人应在第二年年初投资，两年