武汉城市规划-客户经理英文

第4章 整数规划

判断
04100011 正确
04100021 正确
04100031正确
04100041正确
04100051正确
04100061错误。整数规划的可行域通常小于对应线性规划的可行域。
04100071错误。割平面法切割掉的只有非整数解。
04100081错误。应该选择目标函数最大的一个作为边界值，再比较剪枝。
04100091正确
04100101正确
04100111正确。放松变量的符号限制，即能转化为运输问题数学模型
04100121正确。分配问题数学模型使特殊的0－1规划模型

简答
04200011 略
04200021 略
04200031 略
04200041 略

计算题
04301012

L
0

X
(0)
(
3
,
10
)
T
，
z
(0)

29

236
x
1
1

L
1

x
1
2

L
2

X
(1)(1,
7
)
T
，
z
(1)
349

3
X
(2)
(2,
23
)
T
，
z
(2)

41

99
x
2
2

L
3

x
2
3

L
4


（无可行解）

X
(3)
(
33
, 2)
T
，
z
(3)

61

1414
x
1
2

L
5

x
1
3

L
6

X
(5)(2,2)
T
，
z
(5)
4

X
(6)
(3,1)
T
，
z
(6)
4




04301022
L
0

X
(0)
(
13
,
5
)
T
，
z
(0)< br>
59

424
x
1
3

L
1

x
1
4

L
2

X
(1)
(3,
8
)
T
，
z
( 1)

43

33
X
(2)
(4,1)
T
，
z
(2)
14

x
2
2

L
4

x
2
3

L
3

X
(3)
(
5
,3)
T
，
z
( 3)

27

22
04301032
X
(4)
(3,2)
T
，
z
(4)
13

L
0

X
(0)
(5.3,3，3.3)
T
，
z
(0)
136.7

x
1
5

L
1

x
1
6

L
2


无可行解

X
(1)
(5,2.9，3.2)
T
，
z(1)
129

x
2
2

L
3

x
2
3

L
4


无可行解

X
(3)
(5,2，2)
T，
z
(3)
120



04301041
L
0

X
(0)
(
9
,
7
)
T
，
z
(0)
63

22
x
1
4

L
1

x
1
5

L
2

X
(1)(4,
10
)
T
，
z
(1)
58

3
X
(2)
(5,0)
T
，
z
(2)< br>35


故最优解为：
X

04301053 < br>(1)
(4,
10
)
T
，
z
(1)
58

3

L
0

10
)
T
，
z
(0)
29

X
(0)
(
16
,3，
33
x
1
5
L
1
x
1
6

L
2


无可行解

5
X
(1)
(5,
20
,
23
)
T
，
z
(1)
27

77
7
x
3
3

L
3

x
3
4

L
4


无可行解

T
X
(3)
(5,
11
T
3,3)
，
z
(3)
26

44


（2，2），Z4；
04301062最优解
X
及最优解
Z
分别为：
X

（3，1），Z15；< br>04301072最优解
X
及最优解
Z
分别为：
X

（5，1），Z11；
04301082最优解
X
及最优解
Z分别为：
X

（2，2），Z18；
04301092最优解
X
及最优解
Z
分别为：
X

043011011 解：最优值为14
04301111 解：最优解为
x
1
2,x
2
2
或者是
x
1
3, x
2
1
，最优值为
z
max
＝4
隐枚举法
*T
04302011 最优解为
X(1,1,1)
，最优值为
maxZ9
；
*T
04302022 最优解为
X(1,1,1,1,1)
，最优值为
maxZ35
；
*T
04302031最优解为
X(1,0,1)
，最优值为
maxZ 8
；
*T
04302041最优解为
X(0,0,1)
，最优值 为
maxZ2
；
*T
04302052最优解为
X(1,0, 1)
，最优值为
maxZ8
；
*T
04302062最优解为< br>X(1,0,0,1,1)
，最优值为
maxZ4
；
*T
04302072最优解为
X(0,1,1,0)
，最优值为
maxZ11。
*
*
*
*
*
*
*

 T

T

T
04302091 无可行解
***
04302102最优解为：
x
1
1,x
2
0,x
3
0,
目标函数最优值为：
Z2

*

'''
04302113 解：令
x
1
1x
1
，将模型化为标准形式。
,x2
1x
2
,x
5
1x
5

1


1


*
最后可得最优解为
X< br>
0

，最优值为5


0



0


指派问题
04303011最优指派方案为< br>x
13
x
22
x
34
x
41
1
，最优值为48；
04303021最优指派方案为
x
15
 x
23
x
32
x
44
x
51
1< br>，最优值为21。

0

1

04303032最优指派方案为：

0


0


0

0001

0000


0010

< br>
0100

1000



0

0


1
04303042最优指派方案为：


0

0


0
00010

10 000


00000



01000

00100


00001


0
< br>1
04303051最优指派方案为


0

0

0

0


1
04303062 最优指派方案为


0

0


0
0
0
1
0
0
0
0
0
1
0
0
0
0

0



0


1

010

100


000


000

000


001


04303072 由下列运动员组成混合接力队：张游仰泳，王游蛙泳，钱游蝶泳，赵游自由泳，预期总成绩为126.2秒。

04303083 加工假设的第五个人是戊，他完成各 项工作时间取甲、乙、丙、丁中最少者，构

造如下表：

甲
乙
丙
丁
戊
A
25
39
34
24
24
B
29
38
27
42
27
C
31
26
28
36
26
D
42
20
40
23
20
E
37
33
32
45
32
对上表再用匈牙利法求解 ，得最优分配方案为甲－B，乙－B和C，丙－E，丁－A，总计需
要131小时。

04303092 用匈牙利法求解，得最优分配方案为
A
1
B
1
,A
2
B
3
,A
3
B
2
, A
4
B
4
最大产值
为22。
04303102 用匈 牙利法求解，得最优承包方案为
甲－A，乙－D，丙－C，丁－B
或
甲－B，乙－A， 丙－C，丁－D
，最小承包费为70。
04303112 最优方案为第一个工厂担任第三 种任务，第二个工厂担任第二种任务，第三个工
厂担任第一种任务，第六个工厂担任第四种任务，最小费 用为8。

04303123这是一个非平衡的 分配问题，而且每个工厂可担任1至2项任 务，因而将4个工
厂看成8个工厂，虚添2项任务，化为平衡分配问题，其系数矩阵如下：

3

6


2

6
C
'



3


6

2



6
7
1
7
4
7
1
7
4
3
8
5
8
3
8
5
8
6
4
3
7
6
4
3
7
5
2
4
3
5
2
4
3
5
7
6
2
5
7
6
2
0
0
0
0
0
0
0
0
0

0


0


0



0

0

0


0


用匈牙利算法求得最优方案为：第一个工厂担任第三项任务，第二个工 厂担任第二、五项任
务，第三个工厂担任第一、四项任务，第四个工厂担任第六项任务。最小总费用为1 3。

04303132应当选择设计任务3，4和5。
04303142应当分 派业务员1去处理业务4；业务员2去处理业务2；业务员3去处理业务1；
业务员4去处理业务3。
04303152应当分派：
A
1
做
B
1
；
A
2
做
B
3
；
A
3
做
B
4
；
A
4
做
B
5
；
A
5
做
B
2

0430316解：这是人数域工作数不等的分配问题。若采用牙利法求解，首先需要做一下处理。
(1) 由于任务数多于人数，所以需要假想一人为戊。效率矩阵如下：

甲
A B C D E
25 29 31 42 37

乙
丙
丁
39
34
24
0
38
27
42
0
26
28
36
0
20
40
23
0
33
32
45
M
戊


最后求得 最优解为甲—
B，乙—D，丙—E，丁—A，C放弃。最少时间为105小时。
(2) 效率矩阵如下：

甲
乙
丙
丁
A B C D E
25
39
34
24
24
29
38
27
42
27
31
26
28
36
26
42
20
40
23
20
37
33
32
45
32
戊


最后求得 最优解为甲—
B，乙—C，丙—E，丁—A。最少时间为131小时。


04303171解:最优解是
X

束条件.

04303181解:
minz
n
*

10

,0,0

,取整后得到
X
*


3,0 ,0

.取整后不满足第二个约

3


cx
jj
j1
n

ax
ij
j1

j
1,i1,2,.....,n

x
j
0or1,j1,2,.....,n
04303192解:
X

0,6,2

maxz12
,这是一个整数解.
*
04303202解:这个问题的整数规划模型为:
maxz4x
1< br>7x
2
6x
3
5x
4
4x
5

5x
1
8x
2
3x
3
2x
4< br>7x
5
112
x
1
8x
2
6x3
5x
4
4x
5
104

x
1
,x
2
,x
3
,x
4
,x
5
是非 负的整数
最优解为
X

15,0,1,17,0

,z=151
*

04303212解:这个问题表示0-1规划如下:

maxz20x
1
40x
2
20x
3
15x
4
30x
5

5x
1
4x
2
3x
3
7x
4
8x
5
25
x
1
7x
2
9x
3
4x
4
6x
5
2 5
8x
1
10x
2
2x
3
x
41x
5
25
x
1
,x
2
,x
3< br>,x
4
,x
5
0or1
最优解为
X
*

1,1,1,1,0

maxz95




数学模型 建模

04304012 设在
A
j
处建住宅
x
j
幢（j=1,2,…,n）。 MaxZ

x
j
j1
n

n
d< br>j
x
j
D


数学模型为
j1


s..t

0x
j
a
j< br>j1,2,

,n


x
j
是整数，j1,2,

,n



设截取长为
aj
的毛坯
x
j
根（j=1,2,…,n）,使圆钢残料最少的下料问题数 学模型为：
Minz
1
l

a
j
X
j
j1
n











n


a
j
x
j
l
j1


s..t

x
j
0j1,2

,n

j1,2

,n
x
j
是整数,



由于z
2
lz
1


a
j
x
j
是实际 用料总长，故问题的目标函数等价于
j1
n
Maxz
2


a
j
x
j
j1
n

如果要求毛坯总根 数最多，则可将目标函数改为
Maxz
3


x
j
j1
n

l

04304021设
x
j
根
l
米长的圆钢用来截取
a
j
米的毛坯，（ j=1,2,…,n）。设
s
j


为每根


a
j


l
米长的圆钢用来截取
a
j< br>米长毛坯时可以得到的最多段数。数学模型为：
Minz

x
j< br>j1
n

s
j
x
j
m
j
j1,2,

,n

s..tj

x
j
0j1,2,

,n



x
j
是 整数，
j1,2,

,n
04304032

0,队员 j不出场
设x
j


j1,2,

,8数学模型 为：

1，队员j不出场
1
MaxZ(1.92x
1
1 .90x
2
1.88x
3
1.86x
4
1.85x< br>5
1.83x
6
1.80x
7
1.78x
8< br>8

x
1
x
2
1

xxx 1

678


x
1
x
4
 x
6
2
s..t


x
2
x
6
1

x
1
x
2
x
3
x
4
x
5
x
6
x
7
x
8< br>5



x
j
0或1，j1,2,

,8
最优解为：x
1
x
3
x
4
x< br>5
x
7
1，x
2
x
6
x
8
0；目标函数最优值为：1.862

04304041


0,不带物品i
设x
i


i1,2,
,m.数学模型为：

1,带物品i
m

M axZ

c
i
s
i
i1


m

a
i
x
i
a

i1
.. t

m
s


b
i
x
i
b

i1


x
i
0或1，i1,2,< br>
,m

04304053设产品A的产量为
x
1
， 且
y


0，其他
11
0x


1，
1
40
y

0，其他
13


，100x


1
1
150
设产品B的产量为
x
2
，且：
y


0，其他
21



1，0x
2
50
y


0，其他
23

1，x
2
100

设产品C产量为
x
3
，且：

y

0， 其他
31



1，0x

3
100
设总利润为：y





y

0，
12



1，
y
0，
14



1，
y

0，
22



1，
y

0，
3 2



1，
其他
40x100

1
其他
x
1
150

其他
50x
2
100
其他
x

3
100

Maxy

12(10y
11
9y
12
8y
13
7y
14
)

x
1


7(6y
21
4y
22
3y
23
)

x
2


6(5y
31
4y
32
)

x
3
< br>x
1
x
2
x
3
100,10x
142x
2
5x
3
700,3x
1
2x
2
x
3
400


y
11
y
12
y
13
y
14
1,y
21
y
22
y
23
1,y
31
y
32
1


0x
1
y
11
40,40x
1
y
12
100,100x
1
y
13
150
s..t

xy150,0x
2
y
21
50,50 x
2
y
22
100,

114

x3
y
23
100,0x
3
y
31
100 ,x
3
y
32
100,x
j
0(j1,2,3)


y
1j
0或1(j1,2,3)，y
2j< br>0或1(j1,2,3)，y
3j
0或1(j1,2)



04304063解：设
x
j
0
或
1
，其中
x
j
0
代表
S
j
点未入选，
x< br>j
1
代表
S
j
点入选；
于是可构造如下数学模型：

maxz

Cx

jj
j1
10
x
1
x
8
1
x
7
x
8
1
x
3
x
5
1
x
4
x
5
1
x
5
x
6
x
7
x
8
 2
10


x
j1
j
5

x
j
0or1

j1,2,10
