运筹学建模例题和判断题

x4x5x6x7550（2）在例1.2中，如果设xj(j=1，2，…，7)为工作了5天后星期一到星期日开始休息的营业员，该模型如何变化．

minZx1x2x3x4x5x6x7x2x3x1x1x1x1x1xjx3x4x5x6300x4x5x6x7300

x4x5x6x7350x2x5x6x7400x2x3x6x7480x2x3x4x7600x2x3x4x55500,j1,2,,7

【例1-3】合理用料问题。某汽车需要用甲、乙、丙三种规格的轴各一根，这些轴的规格分别是1.5，1，0.7（m），这些轴需要用同一种圆钢来做，圆钢长度为4 m。现在要制造1000辆汽车，最少要用多少圆钢来生产这些轴？

minZxjj1102x12x2x3x4x51000 x2xx4x3x2xx100013467x22x43x5x72x84x95x101000xj0,j1,2，10如果要求余料最少，数学模型如何变化；

minZ0.3x20.5x30.1x40.4x50.3x70.6x80.2x90.5x102x12x2x3x4x510002x3x44x63x72x8x91000x1x22x43x5x72x84x95x101000xj0,j1,2，10

【例1-4】配料问题。某钢铁公司生产一种合金，要求的成分规格是：锡不少于28%，锌不多于15%，铅恰好10%，镍要界于35%~55%之间，不允许有其他成分。钢铁公司拟从五种不同级别的矿石中进行冶炼，每种矿物的成分含量和价格如表1-4所示。矿石杂质在治炼过程中废弃，现要求每吨合金成本最低

minZ340x1260x2180x3230x4190x50.25x10.4x20.2x40.08x50.280.1x10.15x30.2x40.05x50.150.1x0.05x0.15x0.1135 0.25x10.3x20.2x30.4x40.17x50.550.25x0.3x0.2x0.4x0.17x0.35123450.7x10.7x20.4x30.8x40.45x51x0,j1,2,,5j在例1.4中，若允许含有少量杂质，但杂质含量不超过1％，模型如何变化．

minZ340x1260x2180x3230x4190x50.25x10.4x20.2x40.08x50.280.1x10.15x30.2x40.05x50.150.1x0.05x0.15x0.1135 0.25x0.3x0.2x0.4x0.17x0.55123450.25x0.3x0.2x0.4x0.17x0.35123450.7x10.7x20.4x30.8x40.45x50.9x0,j1,2,,5j

【例1-5】投资问题。某投资公司拟将5000万元的资金用于国债、地方国债及基金三种类型证券投资，每类各有两种。每种证券的评级、到期年限及每年税后收益率见表1-5所示。 序号 证券类型 评级 到期年限 每年税后收益率(%) 1 国债1 1 8 3.2 2 国债2 1 10 3.8 3 地方债券1 2 4 4.3 4 地方债券2 3 6 4.7 5 基金1 4 3 4.2 6 基金2 5 4 4.6 决策者希望：国债投资额不少于1000万，平均到期年限不超过5年，平均评级不超过2。问每种证券各投资多少使总收益最大。

maxZ0.256x10.38x20.172x30.282x40.126x50.184x6

xxxxxx5000234561x1x21000x1x2x42x53x603x5xxx2xx0234561xj0,j1,2,,6

【例1-6】均衡配套生产问题。某产品由2件甲、3件乙零件组装而成。两种零件必须经过设备A、B上加工，每件甲零件在A、B上的加工时间分别为5分钟和9分钟，每件乙零件在A、B上的加工时间分别为4分钟和10分钟。现有2台设备A和3台设备B，每天可供加工时间为8小时。为了保持两种设备均衡负荷生产，要求一种设备每天的加工总时间不超过另一种设备总时间1小时。怎样安排设备的加工时间使每天产品的产量最大

maxZys.t.y1x121yx235x14x2960

－4x1－6x2609x110x214404x16x260x1，x2，y0在例1.6中，假定同种设备的加工时间均匀分配到各台设备上，要求一种设备每台每天的加工时间不超过另一种设备任一台加工时间1小时，模型如何变化．

maxZys.t.y1x211yx235x14x29609x110x21440

5x14x29x110x2－60235x14x29x110x2+6023x1，x2，y0

【例1-13】将下例线性规划化为标准型 maxZ|x1||x2|x1x25x14x、xunr21

|x1|x1x1,x1x1x1x2,x2x2x2|x2|x2x1x2，x20x20，x20x1，x10，x10，x10x200，x2x2，x20

0，x10－x1，x10x2)maxZ(x1x1)(x2x2x35x1x1x2x1x1x44x、x、x2、x2、x3、x4011

XB XB Cj-Zj XN N CN XN B－1N CN－CBB－1N XS B－1 XS I 0 b b 0 B CB XB I 0 b B－1b －CBB－1b XB λ －CBB－1 【例3-2 】在例3-1中，假设此人还有一只旅行箱，最大载重量为12公斤，其体积是0.02m3。背包和旅行箱只能选择其一，建立下列几种情形的数学模型，使所装物品价值最大。 （1）所装物品不变；

（2）如果选择旅行箱，则只能装载丙和丁两种物品，价值分别是4和3，载重量和体积的约束为

1.8x10.6x2121.5x12x220物品 丙 丁 约束

体积 （m3/每件） 0.0015 0.002 0.020 价值 (元/每件) 4 3 重量 （公斤/每件） 1.8 0.6 12 maxZ4x13x2（1）

1.2x10.8x210y1＋12y22x12.5x225y120y2

y1y21xi0,andinteger,yi0或1i1,2

maxZ4x13x21.2x10.8x210＋My22x12.5x225My2(a)(b)(c)(d)1.8x10.6x212My1（2）

1.5x12x220My1y1y21xi0,andinteger,yi0或1i1,2【例3-3】试引入0－1变量将下列各题分别表达为一般线性约束条件 （1）x1+x2≤6或4x1+6x2≥10或2x1+4x2≤20 （2）若x1≤5，则x2≥0，否则x2≤8 （3）x2取值0，1，3，5，7

xx6yM2114x16x210y2M2x14x220y3Myyy2(31)231yj0或1，j1,2,3

xx6(1y)M2114x16x210(1y2)M2x14x220(1y3)Myyy1231yj0或1，j1,2,3x15yMx15(1y)M(2)x2yM

x8(1y)M2y0或1xy3y5y7y12342(3)y1y2y3y41

y0或1，j1,2,3,4j

【例3-4】企业计划生产4000件某种产品，该产品可自己加工、外协加工任意一种形式生产．已知每种生产的固定费用、生产该产品的单件成本以及每种生产形式的最大加工数量（件）如表3－2所示，怎样安排产品的加工使总成本最小． 固定成本（元） 变动成本 最大加工数 （元／件） （件） 本企业加工 500 8 1500 外协加工Ⅰ 800 5 2000 外协加工Ⅱ 600 7 不限

minZ(500y18x1)(800y25x2)(600y37x3)xjx1x1xjMyj0j1,2,3x2x34000

1500,x220000,yj1或0，j1,2,3用分枝－隐枚举法求解下列BIP问题

minZx13x26x32x44x56x12x2x37x4x512x14x25x3x43x510x0或1，j1,2,3,4j(311a)(311b)

解 （1）令x2=1－x'2及x5=1－x'5，代入模型后整理得

7minZx13x26x32x44x56x2xx7xx9234513x14x25x3x43x5x0或1，j1,2,3,4j(311a)(311b)

6x37minZx12x43x24x56x7x2xx－x9425315x33x1x4－4x2－3x5x0或1，j1,2,3,4j(311a)(311b)

【例4-1】某企业在计划期内计划生产甲、乙、丙三种产品。这些产品分别需要要在设备A、B上加工，需要消耗材料C、D，按工艺资料规定，单件产品在不同设备上加工及所需要的资源、每件产品利润如表4－1所示。已知在计划期内设备的加工能力各为200台时，可供材料分别为360、300公斤；假定市场需求无

。

现在决策者根据企业的实际情况和市场需求，需要重新制定经营目标，其目标的优先顺序是：

（1）利润不少于3200元

（2）产品甲与产品乙的产量比例尽量不超过1.5 （3）提高产品丙的产量使之达到30件

（4）设备加工能力不足可以加班解决，能不加班最好不加班

（5）受到资金的，只能使用现有材料不能再购进（不能变化） 问企业如何安排生产计划才能到达经营目标。

minzPdP2d2P3d3P4(d4d5)1140x130x250x3d1d13200x1－1.5x2d2d20xdd303333x1x22x3d4d42002x12x24x3d5d52004x15x2x33602x13x25x3300x0,x0,x0andinteger,d、d0,j1,2,23jj1

5

【例4-2】某企业集团计划用1000万元对下属5个企业进行技术改造，各企业单位的投资额已知，考虑2种市场需求变化、现有竞争对手、替代品的威胁等影响收益的4个因素，技术改造完成后预测单位投资收益率(（单位投资获得利润/单位投资额）×100％)如表4－2所示． 集团制定的目标是：

（1）希望完成总投资额又不超过预算1000万元； （2）总期望收益率达到总投资的30%； （3）投资风险尽可能最小；

（4）保证企业5的投资额占20%左右． 集团应如何作出投资决策． 企业1 企业2 企业3 企业4 企业5 单位投资额(万元) 12 10 15 13 20 单位投市场需求1 4.32 5 5.84 5.2 6.56 资收益市场需求2 3.52 3.04 5.08 4.2 6.24 率预测现有竞争对手 3.16 2.2 3.56 3.28 4.08 rij 替代品的威胁 2.24 3.12 2.6 2.2 3.24 期望(平均)收益率％ 3.31 3.34 4.27 3.72 5.03 6minZP1(dd)PdP3(didi)P4(d7d7)i312x110x215x313x420x5d1d110000.29x10.34x20.23x30.18x40.97x5d2d2＝01.01x1.66x1.57x1.48x1.53xdd01234533 0.21x0.3x0.81x0.48x1.21xdd0123440.15x1.14x0.71x0.44x0.95xdd012345551.07x0.22x1.67x1.52x1.79xdd012345662.4x12x23x32.6x416x5d7d70x0,d、d0；i1,2,,7；j1,2,,5iij【例4-3】车间计划生产甲、乙 两种产品，每种产品均需经过A、B、C,3道工序加工．工艺资料如表所示． 产品 产品甲 产品乙 每天加工能力(小时) 工序 1122A B 2 1 2 2 0.8 70 120 100 90 C 2.2 产品售价(元/件) 50 产品利润(元/件) 10 8 （1）车间如何安排生产计划，使产值和利润都尽可能高 （2）如果认为利润比产值重要，怎样决策

minZd1d210x18x2d2d202x12x212050x170x2d1d13800

x12x21002.2x10.8x290xj、dj、dj0,j1,2【例4-4】企业计划生产甲 、乙 两种产品，这些产品需要使用两种材料，要在两种不同设备上加工．工艺资料如表4－4所示． 产品 产品甲 产品乙 现有资源 资源 材料I 3 0 12(kg) 材料II 0 4 14(kg) 设备A 2 2 12(h) 设备B 5 3 15(h) 产品利润 (元/件) 20 40 企业怎样安排生产计划，尽可能满足下列目标： (1)力求使利润指标不低于80元

(2)考虑到市场需求,甲、乙两种产品的生产量需保持1:1的比例 (3)设备A既要求充分利用，又尽可能不加班

(4) 设备B必要时可以加班，但加班时间尽可能少 (5)材料不能超用。

minzP1d1P（dd)P(dd)Pd222333343x14x220x40xdd1211x1x2d2d22x2xdd12335x13x2d4d4x,x,d,d12ii121480012150(i1,(1)(2)(3)(4)(5)(6),4)

【例5-13】DF公司在接下来的三个月内每月都要按照销售合同生产出两种产品。

表5-24中给出了在正常时间（Regular Time，缩写为RT）和加班时间（Over Time，缩写为OT）内能够生产这两种产品的总数。 产品1/产品2 最大生产总量 单位生产成本(1000月 销售 单位储存成本元/件) 产品1/产品2 （1000元/件） RT OT RT OT 1 10 3 5/3 15/16 18/20 1/2 2 8 2 3/5 17/15 20/18 2/1 3 10 3 4/4 19/17 22/22 （1）对这个问题进行分析，描述成一个运输问题的产销平衡表，使之可用运输单纯形法求解．

（2）建立总成本最小的数学模型并求出最优解 j 1 2 3 4 5 6 生产能力 i ai 1月(1) 1月(2) 2(1) 2(2) 3(1) 3(2) 1 2 3 4 5 1月RT 1月OT 2月RT 2月OT 3月RT x11 x21 x12 x22 x13 x23 x33 x43 x14 x24 x34 x44 x15 x25 x35 x45 x55 x16 x26 x36 x46 x56 10 3 8 2 10 6 3月OT 5 3 3 5 x65 4 x66 4 3 需要量bj 1月RT 1月OT 2月RT 2月OT 3月RT 3月OT 需要量 61月1月(2) 2(1) (1) 15 18 M M M M 5 62(2) 18 22 15 18 M M 5 3(1) 18 21 19 22 19 22 4 3(2) 剩余能力 生产能力 19 23 16 19 17 22 4 0 0 0 0 0 0 12 10 3 8 2 10 3 36 16 20 M M M M 3 16 19 17 20 M M 3 minZCijxijij116i1,,6xijaij1 6j1,,6xijbii1xij0i,j1,,6

【例5-17】某商业集团计划在市内四个点投资四个专业超市，考虑的商品有电器、服装、食品、家俱及计算机等5个类别．通过评估，家具超市不能放在第3个点，计算机超市不能放在第4个点，不同类别的商品投资到各点的年利润（万元）预测值见表5-31．该商业集团如何作出投资决策使年利润最大。 表5-31 地点 1 商品 电器 服装 食品 家具 120 80 150 90 2 300 350 160 200 260 3 360 420 380 － 270 4 400 260 300 180 － 计算机 220 【例6-8】设备更新问题。企业在使用某设备时，每年年初可购置新设备，也可以使用一年或几年后卖掉重新购置新设备。已知4年年初购置新设备的价格分别为2.5、2.6、2.8和3.1万元。设备使用了1～4年后设备的残值分别为2、1.6、1.3和1.1万元，使用时间在1～4年内的维修保养费用分别为0.3、0.8、1.5和2.0万元。试确定一个设备更新策略，在下例两种情形下使4年的设备购置和维护总费用最小。

（1）第4年年末设备一定处理掉； （2）第4年年末设备不处理。

1.4 1.3 3.8 2 (1,3) 1.1 (1,3,4) 1.4 6 ① 1.1 (1,2,3,4) 1.4 0.9 0.8 1.9 (1,2,32.3 (1,2) (1,2,4) 1.4 ) 3.9 (1,4) 第一年 第二年 第三年 第四年 ⑤

【例6-9】服务网点设置问题。在交通网络中建立一个快速反应中心，应选择哪一个城市最好。类似地，在一个网络中设置一所学校、医院、消防站、购物中心，还有厂址选择、总部选址、公司销售中心选址等问题都属于最佳服务网点设置问题。

【解】 对于不同的问题，寻求最佳服务点有不同的标准。只有两点间的距离，可以采用“使最大服务距离达到最小”为标准，计算步骤如下。 第一步：利用Floyd算法求出任意两点之间的最短距离表。 第二步：计算最短距离表中每行的最大距离的最小值，即

LminmaxLij

ij【例6-13】某市政工程公司在未来5～8月份内需完成4项工程：A.修建一条地下通道、B.修建一座人行天桥、C.新建一条道路及D.道路维修。工期和所需劳动力见表6-11。该公司共有劳动力120人，任一项工程在一个月内的劳动力投入不能超过80人，问公司如何分配劳动力完成所有工程，是否能按期完成 工期 需要劳动力（人月） A. 地下通道 B. 人行天桥 C. 新建道路 D. 道路维修 5～7月 6～7月 5～8月 8月 100 80 200 80 (20) A5 80 ⑤ (100) 120 80 (20) A 100 (100) B 80 (80) 200 C (200) 80 (80) D ⑥ s 120 (120) 120 ⑦ 80 (80) C5 80 (80) (80) 80 A 680 (0) (80) 80 (40) B 80 (40) 80 (80) 6C6 80 780 (80) A80 (40) 80 (0) 80 (80) t (120) 120 (120) ⑧ (0) 80 C7 (40) 80 (40) 80 B7 80 (40) C8 80 (80) (80) 80 D8 【例6-14】某电动汽车公司与学校合作，拟定在校园内开通无污染无噪音的“绿色交通”路线。图6－34是某大学教学楼和学生宿舍楼的分布图，其中C、F之间是两条单向通道，边上的数字为汽车通过两点间的正常时间（分钟）。电动汽车公司如何设计一条路线，使汽车通过每一处教学楼和宿舍楼一次后总时间最少。

【例7-6】项目工序的正常时间、应急时间及对应的费用见表7-6。表中正常成本是在正常时间完成工序所需要的成本，应急成本是在采取应急措施时完成工序的成本。每天的应急成本是工序缩短一天额外增加的成本

（1）绘制项目网络图，按正常时间计算完成项目的总成本和工期。 （2）按应急时间计算完成项目的总成本和工期。

（3）按应急时间的项目完工期，调整计划使总成本最低。

（4）已知项目缩短1天额外获得奖金5万元，减少间接费用1万元，求总成本最低的项目完工期，也称为最低成本日程。 紧前工时间(天) 成本(万元) 时间的最大应急增加成本工序 序 (万元/天) 正常 应急 正常 应急 缩量(天) A B C D E F G H A B B B C D,E F 19 21 24 25 26 25 28 23 15 19 22 23 24 23 23 23 52 62 24 38 18 88 19 30 80 90 30 60 26 102 39 30 4 2 2 2 2 2 5 0 7 14 3 11 4 7 4 － I J K L M N G,H I I J K L 27 18 35 28 30 25 26 14 30 25 26 20 40 17 25 30 45 18 506 55 21 35 60 57 28 713 1 4 5 3 4 5 15 1 2 10 3 2 总成本 ④ 0 19 40 40 ③ F,25 ⑥ H,23 112157 185 185 157 ⑩ 11 0 0 ① 0 C,24 A,19 ② 19 B,21 D,25 40 59 66 84 ⑧ 112 ⑦ ⑨ 66 84 O,0 G,28 I,27 139 139 L,28 N,25 J,18 145 K,35 12 M,30 139 174 180 210 210 13 40 58 E,26 ⑤ 142 167 167 142 ⑩ 11 102

④ 56 56 0 F,23 ⑥ 79 79 H,23 34 34 ② 15 15 B,19 0 0 ① 0 C,22 A,15 ③ D,23 34 56 58 79 ⑧ 102 ⑦ ⑨ G,23 I,26 128 128 L,25 N,20 J,14 131 K,30 12 M,26 128 158 161 187 187 13 58 79 34 55 E,24 O,0 ⑤