习题三
3.1某公司今后三年内有五项工程可以考虑投资。每项工程的期望收入和年度费用(万元)如表3-10所示。
表3-10
工 程 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=110万元，即选择项目1、2、3、5时总收入最大。
3.2址问题。以汉江、长江为界将武汉市划分为汉口、汉阳和武昌三镇。某商业银行计划投资9000万元在武汉市备选的12个点考虑设立支行，如图3-10所示。每个点的投资额与一年的收益见表3－10。计划汉口投资2～3个支行，汉阳投资1～2个支行，武昌投资3～4个支行。
如何投资使总收益最大，建立该问题的数学模型，说明是什么模型，可以用什么方法求解。 图3-10
表3-11
地址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 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吨，载货有效空间是8×3.5×2 m。现有六件货物可供选择运输，每件货物的重量、体积及收入如表表3-12。另外，在货物4和5中先运货物5，货物1和2不能混装，怎样安排货物运输使收入最大，建立数学模型。
表3-12
货 物 号 重量（T） 体积（m3） 收入（百元） 1 6 3 5 2 5 7 8 3 4 4 3 4 5 6 4 5 7 6 7 6 2 2 3 【解】设xj为装载第j件货物的状态，xj=1表示装载第j件货物，xj=0表示不装载第j件货物，有
maxZ?5x1?8x2?4x3?6x4?7x5?3x6?6x1?5x2?3x3?4x4?7x5?2x6?20??3x1?7x2?4x3?5x4?6x5?2x6?56 ??x4?x5?0?x?x?12?1??xj?0或13.4 女子体操团体赛规定：（1）每个代表队由5名运动员组成，比赛项目是高低杠、平衡
木、鞍马及自由体操。（2）每个运动员最多只能参加3个项目并且每个项目只能参赛一次；（3）每个项目至少要有人参赛一次，并且总的参赛人次数等于10；（4）每个项目采用10分制记分，将10次比赛的得分求和，按其得分高低排名，分数越高成绩越好。已知代表队5名运动员各单项的预赛成绩如表3-13所示。
表3-13
甲 乙 丙 丁 戊
高低杠 平衡木 鞍马
自由体操
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
怎样安排运动员的参赛项目使团体总分最高，建立该问题的数学模型。
【解】设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利用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)M122?j??2
???y?0或1?yj?0或1，j?1,2,36．考虑下列数学模型
minZ?f(x1)?g(x2)
其中
?10?6x1,若x1?0?15?10x2,若x2?0 f(x1)??,g(x2)??0,若x?00,若x?012??满足约束条件
（1）x1≥8或x2≥6 （2）|x1－x2|=0，4或8
（3）x1+2x2≥20、2x1+x2≥20及x1+x2≥20 三个约束中至少一个满足 （4）x1≥0，x2≥0
将此问题归结为混合整数规划的数学模型。
minZ?10y1?6x1?15y2?10x2?x1?y1M;x2?y2M?x?8?yM3?1?x2?6?(1?y3)M??x1?x2?0y4?4y5?4y6?8y7?8y8【解】??y4?y5?y6?y7?y8?1??x1?2x2?20?y9M?2x1?x2?20?y10M??x1?x2?20?y11M?y?y?y?21011?911??x1?0,x2?0;yj?0或1，j?1,2,?，
7．用分枝定界法求解下列IP问题
条件（1）条件（2）条件（3）
条件（4）maxZ?x1?x2minZ?x1?2x2??x1?x2?10?3x1?2x2?7（1）? （2）?
10x?2x?502x?4x?5?1?122?x,x?0且为整数?x,x?0且为整数?12?12【解】(1)X=(1,2),或X＝（0,3）Z=3 (2) X=(5,0),Z=5
8．用割平面法求解下列IP问题
maxZ?2x1?3x2minZ?2x1?3x2?x1?2x2?9?x1?2x2?9（1）? （2）?
2x?x?102x?x?10?1?122?x,x?0且为整数?x,x?0且为整数?12?12【解】(1)X=(3,3),Z=15 (2)X=(5,2),Z=16
9．用隐枚举法求解下列BIP问题
相关推荐：
loading