第3篇线性规划模型-题目

1第3篇线性规划模型线性规划通常研究资源的最优利用问题.例如，在任务确定的条件下，如何用最少的资源（如资金、原材料、人工、时间、设备等）去完成确定的任务；在资源一定的条件下，如何组织生产，使得成本最小，或者利润最大，等等.线性规划可以分为连续规划、整数规划和0-1规划.3.1生产计划问题例3.1一个奶制品加工厂用牛奶生产1A、2A两种奶制品，1桶牛奶可以在甲车间用12小时加工成3千克1A，或者在乙车间用8小时加工成4千克2A.根据市场需求，生产出的1A、2A能够全部售出，且每千克1A获利24元，每千克2A获利16元.现在加工厂每天能得到50桶牛奶的供应，每天正式工人总的劳动时间为480小时，并且甲车间的设备每天至多能加工100千克1A，乙车间的设备的加工能力可以认为没有上限限制，（即加工能力足够大），试为该厂制订一个生产计划，使得每天的获利最大.3.2零件配套问题例3.2某产品由2件甲零件和3件乙零件组装而成。两种零件必须在设备A、B上加工，每件甲零件在A、B上的加工时间分别为5分钟和9分钟，每件乙零件在A、B上的加工时间分别为4分钟和10分钟。现有2台设备A和3台设备B，每天可供加工时间为8小时。为了保持两种设备均衡负荷生产，要求一种设备每天的加工总时间不超过另一种设备总时间1小时。怎样安排设备的加工时间使得每天加工的产品的产量最大？3.3背包问题例3.3一个旅行者的背包最多只能装20千克物品.现有4件物品的重量分别为4千克、6千克、6千克、8千克，4件物品的价值分别为1000元，1500元,900元,2100元.这位旅行者应携带哪些物品使得携带物品的总价值最大?3.4选择加工方式问题2例3.4企业计划生产4000件某种产品，该产品可自己加工、外协加工任意一种形式生产．已知每种生产的固定成本、生产该产品的单件成本以及每种生产形式的最大加工数量如表3-1所示，怎样安排产品的加工使总成本最小．3.5灵敏度分析在线性规划模型（3-6）中，对于价值系数jc、资源系数ib和工艺系数ija，当其中的某些参数发生微小的变化时，最优解和最优值的变化情况怎样？这就是线性规划的灵敏度分析.具体来说，灵敏度分析主要分析以下2个方面：1.系数变化时，最优解有什么变化；2.系数在什么范围内变化时，原最优解不变.我们以例3.1为例来说明灵敏度分析的方法.2.5.1对价值系数jc进行灵敏度分析在模型（3-6）中，假设每千克1A获利由24元提高到25元，那么目标函数为127564fxx.模型的其余部分都不变，使用lingo软件求解，程序和结果见附录9.从求解结果来看，最优解没有变化，仍然是*(20,30)Tx.当然由于价格变大了，最优值必然会增加的（增加了60元）.反复实验，可以发现，只要价格在[21,31]内，最优解都是不变的.这说明最优生产方案对于奶制品1A的价格变化不是很敏感.类似地可以分析奶制品2A对价格的敏感性.2.5.2对资源系数ib进行灵敏度分析在模型（3-6）中，假设每天能得到51桶牛奶的供应，那么，原料供应约束为1251xx.3其余部分都不变，使用lingo软件求解，程序和结果见附录10.从求解结果来看，最优解发生了变化，是*(18,33)Tx.最优值增加了48元.这说明最优生产方案对于牛奶的供应量的变化是非常敏感的.我们把48元叫做1桶牛奶的影子价格，它记录在“DualPrice”一栏.影子价格的功能是，如果购买1桶牛奶的成本低于48元，就可以扩大购买量来扩大生产规模，因为这样可以增加利润；如果购买1桶牛奶的成本高于48元，就可以卖掉牛奶来压缩生产规模，因为这样也可以增加利润；其实，有关资源系数的灵敏度分析可以直接根据原模型（3-6）的求解结果“DualPrice”一栏的数据进行，而不必重新建模.比如，对于劳动时间约束，每增加1小时，总收入增加2元.而对于设备甲的加工能力约束，就完全没有敏感性了，因为此时还剩余46小时没有用完.2.5.3对工艺系数ija进行灵敏度分析在模型（3-6）中，假设1桶牛奶可以在甲车间用13小时加工成3千克1A（加工时间增加了1小时），劳动时间约束变为12138480xx.其余部分都不变，使用lingo软件求解，程序和结果见附录11.从求解结果来看，最优解发生了变化，是*(16,34)Tx.生产奶制品1A的牛奶减少4桶，而生产奶制品2A的牛奶增加4桶，这说明最优生产方案对于1A的工艺系数是非常敏感的.由于生产效率降低了，所以应该减少奶制品1A的生产规模.并不是对每个系数都要进行灵敏度分析.比如，在本例中，工艺系数在一定时期内是相对固定的，除非企业要进行技术改造，因此对工艺系数就没有必要进行灵敏度分析.3.6两辆铁路平板车的装货问题例3.5有7种规格的包装箱要装到两辆平板车上去，包装箱的宽和高是一样的，但厚度t（以厘米计）及重量w（以千克计）是不同的。表2-2给出了4每种包装箱的厚度，重量以及数量，每辆平板车有10.2米长的地方可用来装包装箱（象面包片那样，如图1所示），载重为40吨，由于地区货运的限制，对C5、C6、C7类包装箱的总数有一个特别的限制：这三类箱子所占的总空间（厚度）不能超过302.7厘米.请设计一种装车方案，使剩余的空间最小（1988年美国数学建模竞赛B题）.表3-2已知数据信息表包装箱类型C1C2C3C4C5C6C7厚度t（厘米）48.75261.37248.75264重量w（千克）200030001000500400020001000件数8796648图1平板车装箱示意图习题1．某水泥厂有三个仓库，供应四个建设工地的需要,仓库储存量,工地需求量以及每吨水泥的运费由表3-3给出,问如何安排调运方案使总运费最少?表3-3已知数据信息表工地1工地2工地3工地4供应量仓库1311610700仓库21928400仓库374105900需求量30060050060020002.某钢铁公司生产一种合金，要求的成分规格是：锡不少于28%，锌不多于15%，铅恰好10%，镍要界于35%～55%之间，不允许有其他成分.钢铁公司拟从五种不同级别的矿石中进行冶炼，每种矿物的成分含量和价格如表3-4所示.矿石杂质在冶炼过程中废弃，现要求每吨合金成本最低的矿物数量.假设矿石在冶炼过程中，合金含量没有发生变化.5表3-4已知数据信息表合金矿石锡%锌%铅%镍%杂质费用（元/t）1251010253034024000303026030155206018042020040202305851517551903.国内某手机生产商考虑生产甲、乙、丙、丁型号的四款手机，每款手机都需要依次经过A、B、C三个车间加工完成。假设每款手机需要各车间加工的工时（单位：时）、各车间的最大生产能力以及每款手机预期的利润都已知，具体数据参见表3-5.表3-5已知数据信息表甲乙丙丁车间最大生产能力A1.53131200小时B8203123000小时C38352400小时单位利润200元1200元100元400元如果你是主管，应该投产哪几款手机，各生产多少，才能获得尽可能多的利润？4.某商场决定：营业员每周连续工作5天后连续休息2天，轮流休息。根据统计，商场每天需要的营业员如表3-6所示。商场人力资源部应如何安排每天的上班人数，使商场总的营业员最少。表3-6已知数据信息表星期需要人数星期需要人数一300五480二300六600三350日550四4005.某游泳队准备选用甲、乙、丙、丁四名运动员组成一个4×100米混合泳接力队，参加今年的锦标赛。他们的100米自由泳、蛙泳、蝶泳、仰泳的成绩如表所示。甲、乙、丙、丁四名运动员各自游什么姿势，才有可能取得好成绩？6表3-7已知数据信息表自由泳（秒）蛙泳（秒）蝶泳（秒）仰泳（秒）甲56746163乙63696571丙57776367丁557662626.某公司准备投资100万元在甲乙两座城市修建健身中心，经过多方考察，最后选定A1，A2，A3，A4，A5五个位置，并且决定在甲城市的A1，A2，A3三个位置中最多投建两个，在乙城市的A4，A5两个位置中最少投建一个，如果已知各点的投资金额和年利润如表3-8所示，问：投建在哪些位置才会使总的年利润最大？表3-8已知数据信息表A1A2A3A4A5投资总额投资金额（万元）2030254045100年利润（万元）10252025307.假定一个成年人每天需要从食物中获取3000卡路里热量，55克蛋白质和800毫克钙。如果市场上只有四种食品可供选择，它们每千克所含热量和营养成份以及市场价格如表3-9所示。问如何选择才能使在满足营养的前提下使购买食品的总费用最小？表3-9已知数据信息表序号食品名称热量(卡路里)蛋白质(克)钙(毫克)价格(元)1猪肉100050400102鸡蛋8006020063大米9002030034白菜2001050028.某公司经调研分析知，在今后三年内有四种投资机会。第Ⅰ种方案是在三年内每年年初投资，年底可获利15%，并可将本金收回；第Ⅱ种是在第一年的年初投资，第二年的年底可获利45%，并将本金收回，但该项投资不得超过2万元；第Ⅲ种是在第二年的年初投资，第三年的年底可获利65%，并将本金收回，但该项投资不得超过1.5万元；第Ⅳ种是在第三年的年初投资，年底收回本金，且可获利35%，但该项投资不得超过1万元。现在本公司准备拿出3万元来投资，问如何计划可使到第三年年末本利和最大？79.要用一批长度为7.4米的园钢做100套钢架，每套钢架由2.9米、2.1米、1.5米的园钢各一根组成，问：应如何下料才能使所用的原料最省？10.捷运公司拟在下一年度的1-4月的4个月内需租用仓库堆放物资.已知各月份所需仓库面积数列于表3-10中.仓库租借费用随合同期而定,期限越长,折扣越大,具体数字见表2.租借仓库的合同每月初都可办理,每份合同具体规定租用面积数和期限.因此该厂可根据需要,在任何一个月初办理租借合同.每次办理时可签一份,也可签若干份租用面积和租借期限不同的合同,试确定该公司签订租借合同的最优决策,目的是使所付租借费用最小.表3-10已知数据信息表月份1234所需仓库面积(100m2)15102012表3-11已知数据信息表合同租借期限1个月2个月3个月4个月所需仓库面积(元/100m2)280045006000730011.某糖果厂用原料A,B,C加工成三种不同牌号的糖果甲,乙,丙.已知各种牌号糖果中A,B,C含量,原料成本,各种原料的每月限制用量,三种牌号糖果的单位加工费及售价如表3-12所示.问该厂每月生产这三种牌号糖果各多少时,使该厂获利最大.试建立这个问题的线性规划模型.表3-12已知数据信息表甲乙丙原料成本(元/kg)每月限制量(kg)A60%30%2.002000B1.502500C20%50%60%1.001200加工费(元/kg)0.500.400.30售价(元/kg)3.402.852.2512.一家企业制造三种产品，需三种资源：技术服务、劳力、行政管理.表3-13列出了三种产品每单位数量对每种资源的需要量.（1）问如何安排生产，可使利润最大？（2）若劳力资源增加到800小时，问最优计划是否要改变，若要改变，应如何改变？（3）若有一种原材料，如今受到限制，限制条件为8123325400xxx，问最优计划是否受到影响？表3-13已知数据信息表产品ABC资源限量技术服务111100劳力1045600行政管理226300单位利润1064