运筹学(第3版) 习题答案 41
第3章 整数规划
3.1某公司今后三年内有五项工程可以考虑投资。每项工程的期望收入和年度费用(万元)如表3-8所示。
表3-8
工 程 1 2 3 4 5 资金拥有量 费 用 第一年 第二年 第三年 5 1 8 4 7 2 5 9 6 7 5 2 8 6 9 30 25 30 收 入 30 40 20 15 30 每项工程都需要三年完成，应选择哪些项目使总收入最大，建立该问题的数学模型。 【解】设xj???1投资j项目?0不投资j项目maxZ?30x1?40x2?20x3?15x4?30x5?5x1?4x2?5x3?7x4?8x5?30?x?7x?9x?5x?6x?252345?1??8x1?2x2?6x3?2x4?9x5?30?xj＝0或1,j?1,,5?
，模型为
最优解X＝(1,1,1,0,1)，Z=120万元，即选择项目1、2、3、5时总收入最大。
3.2选址问题。以汉江、长江为界将武汉市划分为汉口、汉阳和武昌三镇。某商业银行计划投资9000万元在武汉市备选的12个点考虑设立支行，如图3-8所示。每个点的投资额与一年的收益见表3－9。计划汉口投资2～3个支行，汉阳投资1～2个支行，武昌投资3～4个支行。
如何投资使总收益最大，建立该问题的数学模型，说明是什么模型，可以用什么方法求解。 图3-8
表3-9
地址i 1 2 3 4 5 6 7 8 9 10 11 12 投资额(万元) 900 1200 1000 750 680 800 720 1150 1200 1250 850 1000 收益（万元） 400 500 450 350 300 400 320 460 500 510 380 400 【解】设xj为投资第j个点的状态，xj=1或0，j=1,2,…,12 运筹学(第3版) 习题答案 42
maxZ?400x1?500x2?450x3??400x12?900x1?1200x2?1000x3??850x11?1000x12?9000?44771212 ?x?2,x?3,x?1,x?2,x?3,x?4??j?????jjjjjj?1j?5j?5j?8j?8?j?1?x?1或0，j?1,,12?j最优解：x1＝x5=x12=0，其余xj=1,总收益Z=3870万元，实际完成投资额8920万元。
3.3 一辆货车的有效载重量是20吨，载货有效空间是8m×2m×1.5m。现有六件货物可供选择运输，每件货物的重量、体积及收入如表表3-10。另外，在货物4和5中优先运货物5，货物1和2不能混装，货物3和货物6要么都不装要么同时装。怎样安排货物运输使收入最大，建立数学模型。
表3-10
货 物 号 重量（T） 体积（m3） 收入（百元） 1 6 3 3 2 5 7 7 3 4 2 3 4 5 5 4 5 7 6 8 6 2 2 3 【解】设xj为装载第j件货物的状态，xj=1表示装载第j件货物，xj=0表示不装载第j件货物，有
maxZ?3x1?7x2?2x3?5x4?8x5?3x6?6x1?5x2?3x3?4x4?7x5?2x6?20?3x?7x?4x?5x?6x?2x?2423456?1??x4?x5?0??x1?x2?1?x3?x6?0???xj?0或1,j?1,2,,6
3.4 女子体操团体赛规定：（1）每个代表队由5名运动员组成，比赛项目是高低杠、平衡
木、鞍马及自由体操。（2）每个运动员最多只能参加3个项目并且每个项目只能参赛一次；（3）每个项目至少要有人参赛一次，并且总的参赛人次数等于10；（4）每个项目采用10分制记分，将10次比赛的得分求和，按其得分高低排名，分数越高成绩越好。已知代表队5名运动员各单项的预赛成绩如表3-11所示。
表3-11
甲 乙 丙 丁 戊
高低杠 平衡木 鞍马
自由体操
8.6 9.2 8.8 8.5 8.0
9.7 8.3 8.7 7.8 9.4
8.9 8.5 9.3 9.5 8.2
9.4 8.1 9.6 7.9 7.7
怎样安排运动员的参赛项目使团体总分最高，建立该问题的数学模型。
运筹学(第3版) 习题答案 43
【解】设xij（i=1，2，…，5；j＝1，2，3，4）为第i人参赛j项目的状态，即
?1xij???0第i人参赛j项目
第i人不参赛j项目54记第i人参赛j项目的成绩为Cij,，目标函数
maxZ???Cijxij
i?1j?1每个运动员最多只能参加3个项目并且每个项目只能参赛一次,约束条件：
xi1?xi2?xi3?xi4?3i?1,2,?,5 每个项目至少要有人参赛一次，并且总的参赛人次数等于10，约束条件：
x1j?x2j?x3j?x4j?x5j?1j?1,2,3,4
??xi?1j?154ij?10
数学模型为
maxZ???Cijxiji?1j?154?xi1?xi2?xi3?xi4?3i?1,2,,5?x?x?x?x?x?1j?1,2,3,4 2j3j4j5j?1j?54????xij?10?i?1j?1??xij?1或0,i?1,2,,5;j?1,2,3,43.5某电子系统由3种元件组成，为了使系统正常运转，每个元件都必须工作良好，如一个
或多个元件安装几个备用件将提高系统的可靠性，已知系统运转可靠性为各元件可靠性的乘积，而每一元件的可靠性是备用件数量的函数，具体如表3－12所示。
表3－12 备用件数 0 1 2 3 4 元件可靠性 1 0.5 0.6 0.75 0.9 1.0 2 3 0.7 0.9 1.0 1.0 1.0 0.6 0.8 0.9 1.0 1.0 3种元件的价格分别为30、40和50元/件，重量分别为2、4和6kg/件。而全部备用件的费用预算限制为220元，重量限制为20kg，问每种元件各安装多少个备用件，使系统可靠性最大。试建立该问题的整数（非线性）规划数学模型。
【解】设x1、x2、x3分别为元件1、2、3的备件数，由可靠性知x2?3、x3?2
设y1、y2、y3、y4、y5为元件1备件数的状态变量，yi?1（备件数为j件，j＝0，1?，
运筹学(第3版) 习题答案 44
4）或yi?0（备件数为0件，i＝1，2，?，5）
设y6、y7、y8、y9为元件2备件数0、1、2、3件时的状态变量，yi?1或0（i＝6、7、8、9）
设y10、y11、y12为元件3备件数0、1、2件时的状态变量，yi?1或0（i＝10、11、12） 数学模型为：
maxz?(0.5y1?0.6y2?0.75y3?0.9y4?y5)?(0.6y6?0.8y7?0.9y8?y9)?(0.7y10?0.9y11?y12)?30x1?40x2?50x3?220?2x?4x?6x?2023?1?y1?y2?y3?y4?y5?1??y6?y7?y8?y9?1?y?y?y?1?101112 ?x?y?2y?3y?4y2345?1?x2?y7?2y8?3y9??x3?y11?2y12?x、x、x?0并且为整数?123??yi?1或0，i?1,2,,12
注意：如果去掉第6、7、8个约束，因目标函数中没有x，则x与y之间就没有逻辑关系。
3.6利用0－1变量对下列各题分别表示成一般线性约束条件
（1）x1+2x2≤8、4x1+x2≥10及2x1+6x2≤18 三个约束中至少两个满足 （2）若x1≥5，则x2≥10，否则x2≤8 （3）x1取值2，4，6，8中的一个
?x1?2x2?8?y1M?x1?5?yM??x?5?(1?y)M?x1?2y1?4y2?6y3?8y4?4x1?x2?10?y2M1???【解】(1)?2x1?6x2?18?y3M (2)?x?10?yM(3)?y1?y2?y3?y4?1?2?y?y?y?1?y?0或1，j?1,2,3,4?x?8?(1?y)M1222?j??
???y?0或1?yj?0或1，j?1,2,33.7考虑下列数学模型
minZ?f(x1)?g(x2)
其中