运筹学课后习题三

习题三

3.1某公司今后三年内有五项工程可以考虑投资。每项工程的期望收入和年度费用(万元)如表3-10所示。

表3-10

【解】设xj

1投资j项目

0不投资j项目

maxZ 30x1 40x2 20x3 15x4 30x5

5x1 4x2 5x3 7x4 8x5 30 x 7x 9x 5x 6x 25

2345 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

jj

maxZ 400x1 500x2 450x3 400x12

900x1 1200x2 1000x3 850x11 1000x12 9000 4

4771212

x 2,x 3,x 1,x 2,x 3,x 4 j jjjjj

j 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

【解jjjj件货物，有

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 1

2

1 xj 0或1

3.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项目

5

4

记第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

x

i 1j 1

54

ij

10

数学模型为

maxZ Cijxij

i 1j 1

54

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,4

3.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,3

6．考虑下列数学模型

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 yM

3 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 2

1011

9

11 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问题

x1 x2 4x3 5x4 3

5x1 2x2 x3 6 （1） （2） 3x1 x2 2x3 2x4 4

4x1 2x2 x3 7

x1 3x2 2x3 4x4 7 x 0或1，j 1,2,3

j xj 0或1，j 1,2,3,4

【解】(1)X=(1,1,1),Z=8 (2)X=(1,1,1,0),Z=4

10．用分枝定界－隐枚举法求解下列BIP问题

maxZ 4x1 3x2＋x3

minZ 4x1 x2 x3 3x4

maxZ 4x1 x2 x3 3x4

x1 x2 4x3 5x4 8

x1 5x2 x3 2x4 x5 8 3x x 2x 2x 4

（1） 1 （2） 234

2x1 2x2 3x3 2x4 x5 4x 3x 2x 4x 7234 1 x 0或1，j 1, ,5

j xj 0或1，j 1,2,3,4

【解】(1)X=(1,0,1,1),Z=8 (2)X=(1,1,0,0,0),Z=－2

minZ 3x1 x2 2 …… 此处隐藏：3966字，全部文档内容请下载后查看。喜欢就下载吧 ……