《运筹学建模例题和判断题.doc》由会员分享，可在线阅读，更多相关《运筹学建模例题和判断题.doc（23页珍藏版）》请在三一文库上搜索。
1、【例1-2】某商场决定：营业员每周连续工作 5天后连续休息2天，轮流休息根据统计，商场每天需要的营业员如表1-2所示表1-2营业员需要量统计表星期需要人数星期需要人数-一一300五480二二二300六600-三350日550四400min Z x1 x2 x3 x4 x5 x6 x7x1x4x 5x6x7300x1x2x 5x6x7300x1x2x 3x6x7350x1x2x 3x4x 7400x1x2x 3x4x 5480X2X3X4X5X6600X3X4X5X6X7550Xj 0, j 1,2,7(2 )在例1.2中，如果设Xj(j=1 , 2，7)为工作了 5天后星期一到星期日开始休息的
2、营 业员，该模型如何变化.min Z x1 x2 x3 x4 x5 x6 x7X2X3X4X5X6300X 3X4X5X6X 7300XI X4X 5X6X7350x1x2x 5x6x7400x1x2x 3x6x7480x1x2x 3x4x 7600x1x2x 3x4x 5550xj 0, j 1,2, 7例 1-3 】合理用料问题。某汽车需要用甲、乙、丙三种规格的轴各一根，这些 轴的规格分别是 1.5 ，1，0.7（ m ），这些轴需要用同一种圆钢来做，圆钢长度为4 m 。现在要制造 1000 辆汽车， 最少 要用多少圆钢来生产这些轴？10min Z x jj12x12x2x3x 4 x51
3、000x12x3x44x63x7x22x 4 3x 5x7xj0, j1,2，10如果要求余料最少，数学模型如何变化；min Z0.3x20.5 x30.1 x 40.42x12x2x3x 4 x51000x12x3x44x63x7x22x 4 3x 5x7xj0, j1,2，102x8x910002x84x95x101000x50.3 x 70.6 x 80.2 x 90.5 x102x8x910002x84x95x 101000【例 1-4 】配料问题。某钢铁公司生产一种合金，要求的成分规格是：锡不少于28% ，锌不多于 15% ，铅恰好 10% ，镍要界于 35%55% 之间，不允许有其
4、他 成分。钢铁公司拟从五种不同级别的矿石中进行冶炼， 每种矿物的成分含量和价 格如表 1-4 所示。矿石杂质在治炼过程中废弃，现要求 每吨合金成本最低min Z340 x1260 x2180 x3230 x4190 x50.25 x10.4 x20.2 X40.08X50.280.1 x10.15 x30.2 X40.05X50.150.1 x10.05 x 30.15 x50.10.25 x10.3 x20.2 X30.4 x40.17 x50.550.25 x10.3 x 20.2 X30.4 X40.17 x50.350.7 x10.7 x20.4 X30.8 x40.45 x51Xj
5、0, j 1,2, |,5在例1.4中，若允许含有少量杂质，但杂质含量不超过1 %，模型如何变化.min Z340 x1260 x2180 x3230 x4190 x50.25 x10.4 x20.2 X40.08 x50.280.1 x10.15 x30.2 X40.05 x50.150.1 x10.05 x3015 x50.10.25 x10.3 x20.2 X30.4 x40.17 x50.550.25 x10.3 x 20.2 x 30.4 X40.17 x50.350.7 x10.7 x20.4 X30.8 X40.45 x50.9xj0,j 1,2,5【例1-5】投资问题。某投资公
6、司拟将5000万元的资金用于国债、地方国债及 基金三种类型证券投资，每类各有两种。每种证券的评级、到期年限及每年税后 收益率见表1-5所示。序号证券类型评级到期年限每年税后收益率（）1国债1183.22国债21103.83地方债券1244.34地方债券2364.75基金1434.26基金2544.6决策者希望：国债投资额不少于1000万，平均到期年限不超过5年，平均评级 不超过2。问每种证券各投资多少使总收益最大。max Z0.256 x10.38 x20.172 x30.282 x40.126 x50.184 x6x1x1X1 3x1 Xjx2x3x4x5x65000x21000X2X4决3
7、x605X2X3 x42X5X600, j 12 |,6【例1-6】均衡配套生产问题。某产品由2件甲、3件乙零件组装而成。两种零 件必须经过设备A、B上加工，每件甲零件在A、B上的加工时间分别为5分钟 和9分钟，每件乙零件在A、B上的加工时间分别为4分钟和10分钟。现有2 台设备A和3台设备B，每天可供加工时间为8小时。为了保持两种设备均衡 负荷生产，要求一种设备每天的加工总时间不超过另一种设备总时间1小时。怎样安排设备的加工时间使每天产品的产量最大max Zs.t.y x12 11y x2325x14x29609x110 x214404x16x2604x16x260x1, x2, y0在例1
8、.6中，假定同种设备的加工时间均匀分配到各台设备上,要求一种设备每台每天的加max Zys.t.1y2x11y3X25x14x29609X110x214405x14x29x110 x223工时间不超过另一种设备任一台加工时间1小时，模型如何变化.605x1 4x2 + 9x110x223x1? x2, y 060【例1-13】将下例线性规划化为标准型max Z | x1 | x2 |x1 x25X14x1> x2unrx1, X 1XiXiX2, X 2X2X2I Xi IXiI X2 IX2X1，xi0Xi0，xi0X2,X20X20，X200, x10X1x1, x100, x20x
9、2x2, x20max Z（Xix1 x1X2x1 x1X4xj （X2 X2）x2X354XbXnXSbXBBNIbCj-ZjCBCN00X1' xx2、x2、x3、x40XBXNXSbXBIB 1NB 1B 1b入0CN - CBB1N-cbb 1-CrB 1 b【例3-2】在例3-1中，假设此人还有一只旅行箱，最大载重量为 12公斤， 其体积是0.02m 3。背包和旅行箱只能选择其一，建立下列几种情形的数学模型， 使所装物品价值最大。（1）所装物品不变；（2） 如果选择旅行箱，则只能装载丙和丁两种物品，价值分别是4和3，载重量和体积的约束为1.8 x10.6x212般线性约束条件
10、1.5 x12x220物品重量（公斤/每件）体积（m3/每件）价值（元/每件）丙1.80.00154丁0.60.0023约束120.020max Z4x13x21.2x10.8x210y1+12y22X12.5 x225y120y2y1y2 1Xi0, andint eger,yi0或 1imax Z4x13x21.2x10.8x210 + My 2(a)1.8x10.6x212My1(b)2x12.5 x225My2(c)1.5x1 2x220My1(d )y1y2 1xi0, andint eger,yi0 或 1i(1)1,2(2)1,2【例3-3】试引入变量将下列各题分别表达为0 1(
11、1)x +x?話 或 4x +6 x? >10 或 2x+4 x?<20(2)若x1 W5,则x2>0，否则*2 =8(3)x2 取值 0, 1 , 3, 5,X14x12x1y1 y jx266x24X2y2 y30 或 1, jyN10 y2M20ysM2(31)1, 2,3x14x12x1x26x24x2(11020y2y310 或1, jyJM(1y2)M(1y3)M1,2,3x15yMx15(1y)M X2 yMx28(1y )My0 或1X2yi 3y2 5y3 ly, yi y2 y3 y,1yj0或1, j1,2,3, 4【例3-4】企业计划生产4000件某种
12、产品，该产品可自己加工、外协加工任意 一种形式生产.已知每种生产的固定费用、生产该产品的单件成本以及每种生产 形式的最大加工数量（件）限制如表 3-2所示，怎样安排产品的加工使总成本最小.固定成本（元）变动成本（元/件）最大加工数（件）本企业加工50081500外协加工I80052000外协加工U600l不限min Z(500 y18x1)(800 y25x2)(600 y37X3)XjMyj0 j1,2,3x1x2X34000X11500,x22000Xj0, y1 或0，j1,2,3用分枝-隐枚举法求解下列BIP问题min Z x 3x2 6x3 2x4 4x56xi2x2 X37x4 X
13、512(3 11a)Xi4x25x3X43x510(3 11b)Xj 0或1, j 1,2,3,4解(1)令x2=1 x'2及x5=1 x'5，代入模型后整理得10不可行 不可行 不可行2不可行 不可行 不可行 1-可行52min ZX13x26x32X44X576x1%X37X4X59(311 a)X14x25X3X43x 53(311b)Xj0或1,j1,2,3,4min ZX12x43x24X56X376x17X42x2x 5-X39(311a)X1x4 4x2 3x55x33(311b)Xi0或1,j1,2,3,4【例4-1】某企业在计划期内计划生产甲、乙、丙三种产品。
14、这些产品分别需要 要在设备A、B上加工，需要消耗材料 C、D，按工艺资料规定，单件产品在不设备的加工能力各为200台时，可供材料分别为360、300公斤；假定市场需 求无限制。现在决策者根据企业的实际情况和市场需求，需要重新制定经营目标，其目标的优先顺序是：(1) 利润不少于3200元(2) 产品甲与产品乙的产量比例尽量不超过 1.5(3) 提高产品丙的产量使之达到 30件(4) 设备加工能力不足可以加班解决，能不加班最好不加班(5) 受到资金的限制，只能使用现有材料不能再购进(不能变化)问企业如何安排生产计划才能到达经营目标。min zpd1pd2l3d3d5)40 x1 30X250x3d
15、1d13200X11.5 x2d2d20X3d3d3303x1 x22X3d4d42002x12x24 X 3d 5d52004x15x2X33602x13x25x3300x10, x20, X30andint eger , dj、dj0, j12 |5【例4-2】某企业集团计划用1000万元对下属5个企业进行技术改造，各企业 单位的投资额已知，考虑2种市场需求变化、现有竞争对手、替代品的威胁等影 响收益的4个因素，技术改造完成后预测单位投资收益率(单位投资获得利润/ 单位投资额)X 100 %)如表4 2所示.集团制定的目标是:（1）希望完成总投资额又不超过预算 1000万元;（2）总期望收
16、益率达到总投资的 30% ；（3）投资风险尽可能最小；（4）保证企业5的投资额占20%左右.集团应如何作出投资决策.企业1企业2企业3企业4企业5单位投资额（万元）1210151320单位投市场需求14.3255.845.26.56资收益市场需求23.523.045.084.26.24率预测现有竞争对手3.162.23.563.284.08rij替代品的威胁2.243.122.62.23.24期望（平均）收益率3.313.344.273.725.036min ZP©d1 )Pd2P(dii 3di )P4(d7d7 )12x110x2'15X313x420X5d1d11000
17、0.29x10.34x20.23 x30.18 x40.97 x5d2d2 =01.01 x11.66 x21.57 x31.48 x41.53 x5da d300.21 x“0.3 x20.81 x30.48 x41.21 x5 d4d400.15x11.14x20.71 x30.44 x40.95 x5d5d501.07x10.22X21.67 x31.52 x41.79 x5d6d602.4 x72x23X32.6 x416X5d7d70Xj0, di、di0；i 1,2,7 ； j12 III®【例4-3】车间计划生产甲、乙两种产品，每种产品均需经过 A、B、C,3道工序加工
18、工艺资料如表所示.工序产品产品甲产品乙每天加工能力（小时）A22120B12100C2.20.890产品售价（元/件）5070产品利润（元/件）108（1）车间如何安排生产计划，使 产值和利润都尽可能高（2）如果认为利润比产值重要，怎样决策min Z d1d250 x170 x2d1d1380010 x18x2d2d25402x12x2120x12x21002.2 x10.8 x290Xj、dj、dj 0, j 1,2【例4-4】企业计划生产甲、乙两种产品，这些产品需要使用两种材料，要在两种不同设备上加工工艺资料如表 4-4所示.产品资源产品甲产品乙现有资源材料13012(kg)材料II041
19、4(kg)设备A2212(h)设备B5315(h)产品利润（元/件）2040企业怎样安排生产计划，尽可能满足下列目标:（1）力求使利润指标 不低于80元（2）考虑到市场需求，甲、乙两种产品的生产量需 保持1:1的比例（3）设备A既要求充分利用，又尽可能不加班设备B必要时可以加班，但加班时间尽可能少（5）材料不能超用min zPd1P(d2d2)P(d3d3 )P3d3x112(1)4x214(2)20 x140 x2d1d180(3)x1X2d2d20(4)2x12x2d3d312(5)5x13x2d4d415(6)x1,X2, di,di0 (ih ,4)【例5-13】DF公司在接下来的三个
20、月内每月都要按照销售合同生产出两种产 品。表5-24中给出了在正常时间（Regular Time，缩写为RT）和加班时间（OverTime，缩写为OT）内能够生产这两种产品的总数月最大生产总量产品1/产品2销售产品1/产品2单位生产成本（1000 元 / 件）单位储存成本（1000 元 / 件）RTOTRTOT11035/315/1618/201/22823/517/1520/182/131034/419/1722/22(1)对这个问题进行分析，描述成一个运输问题的产销平衡表，使之可用运输单纯形法求解.(2)建立总成本最小的数学模型并求出最优解ij123456生产能力ai1月1 月(2)2(1
21、)2(2)3(1)3(2)11月RTx11x12x13x14x15x161021月0Tx21x22x23x24x25x26332月RTx33x34x35x36842月0Tx43x44x45x46253月RTx55x561063月0Tx65x663需要量bj5335441月(1)1 月(2)2(1)2(2)3(1)3(2)剩余能力生产能力1月RT1516161818190101月OT182019222123032月RTMM17151916082月OTMM20182219023月RTMMMM19170103月0TMMMM222203需要里5335441236min ZCj x”i 1 j 1训Q训
22、,61川66xij aiij 16xj b ji 1Xij 0 i, j【例5-17】某商业集团计划在市内四个点投资四个专业超市，考虑的商品有电器、服装、食品、家俱及计算机等5个类别通过评估，家具超市不能放在第 3 个点，计算机超市不能放在第4个点，不同类别的商品投资到各点的年利润 （万 元）预测值见表5-31 该商业集团如何作出投资决策使年 利润最大。表 5-31地点商品1234电器120300360400服装80350420260食品150160380300家具90200一180计算机220260270一【例6-8】设备更新问题。企业在使用某设备时，每年年初可购置新设备，也可以使用一年或几
23、年后卖掉重新购置新设备。已知4年年初购置新设备的价格分别 为2.5、2.6、2.8和3.1万元。设备使用了 14年后设备的残值分别为2、1.6、 1.3和1.1万元，使用时间在14年内的维修保养费用分别为0.3、0.8、1.5和 2.0万元。试确定一个设备更新策略，在下例两种情形下使4年的设备购置和维护总费用最小。(1) 第4年年末设备一定处理掉；(2) 第4年年末设备不处理。1.4 -1.31.1 (1,3,4)1.41,4)0.9653于-2.3(1,2,4)(1,2).81.41.9第一年丨第一年第三年第四年1.4 -【例6-9】服务网点设置问题。在交通网络中建立一个快速反应中心，应选择
24、哪 一个城市最好。类似地，在一个网络中设置一所学校、医院、消防站、购物中心, 还有厂址选择、总部选址、公司销售中心选址等问题都属于最佳服务网点设置问【解】 对于不同的问题，寻求最佳服务点有不同的标准。只有两点间的距离，可以采用“使最大服务距离达到最小”为标准，计算步骤如下。第一步：利用Floyd算法求出任意两点之间的最短距离表。第二步：计算最短距离表中 每行的最大距离的最小值，即L min max Ljji jnj【例6-13】某市政工程公司在未来 58月份内需完成4项工程：A.修建一条 地下通道、B.修建一座人行天桥、C.新建一条道路及D.道路维修。工期和所需劳 动力见表6-11。该公司共有
25、劳动力120人，任一项工程在一个月内的劳动力投 入不能超过80人，问公司如何分配劳动力完成所有工程，是否能按期完成工期需要劳动力（人月）A.地下通道57月100B.人行天桥67月80C.新建道路58月200D.道路维修8月80【例6-14】某电动汽车公司与学校合作,拟定在校园内开通无污染无噪音的“绿色交通”路线。图6 - 34是某大学教学楼和学生宿舍楼的分布图，其中 C、F之间是两条单向通道，边上的数字为汽车通过两点间的正常时间(分钟)。电动汽 车公司如何设计一条路线，使汽车通过每一处教学楼和宿舍楼一次后总时间最【例7-6】项目工序的正常时间、应急时间及对应的费用见表7-6。表中正常成本是在正
26、常时间完成工序所需要的成本，应急成本是在采取应急措施时完成工序的成本。每天的应急成本是工序缩短一天额外增加的成本(1) 绘制项目网络图，按正常时间计算完成项目的总成本和工期。(2) 按应急时间计算完成项目的总成本和工期。(3) 按应急时间的项目完工期，调整计划使总成本最低。(4) 已知项目缩短1天额外获得奖金5万元，减少间接费用1万元，求总成本 最低的项目完工期，也称为最低成本日程。工序紧前工序时间（天）成本（万兀）时间的最大缩里（天）应急增加成本（万元/天）正常应急正常应急A1915528047BA21196290214CB2422243023DB25233860211EB2624182624FC25238810227GD,E2823193954HF232330300一IG,H27264055115JI1814172141KI3530253552LJ28253060310MK3026455743NL2520182852总成本506713B,191,2612 M,26D,23G,237128K,30F,23H,23L,25N,20J,14 / 131£8-79-p,°