习题五5.1 试将下述非线性的0－1规划问题转换为线性的0－1规划问题
max z ＝x 12＋x 2x 3－x 33
st. －2x 1＋3x 2＋x 3 ≤3
x j ＝0或1（j ＝1,2,3）
5.2 某钻井队要从以下10个可供选择的井位中确定5个钻井探油，使总的钻探费用为最小。若10个井位的代号为s 1，s 2，…，s 10，相应的钻探费用为c 1，c 2，…，c 10，并且井位选择上要满足下列限制条件：
（1） 或选择s 1和s 7，或选择钻探s 8；
（2） 选择了s 3或s 4就不能选s 5，或反过来也一样；
（3） 在s 5，s 6，s 7，s 8中最多只能选两个。
试建立此问题的整数规划模型。
5.3 用分枝定界法求解下列整数规划问题
(1) max z ＝x 1＋x 2
st. x 9
1＋14x 51
2 ≤14
－2x 1
1 ＋x 2 ≤3
x 1，x 2≥0且为整数
(2) max z ＝2x 1＋3x 2
st. 5x 1＋7x 2≤35
4x 1＋9x 2≤36
x 1，x 2≥0且为整数
5.4 用割平面法求解下列整数规划问题
(1) max z ＝7x 1＋9x 2
st. －x 1＋3 x2 ≤6
7x 1 ＋ x 2 ≤35
x 1，x 2≥0且为整数
(2) min z ＝4x 1＋5x 2
st. 3x 1＋2x 2≥7
x 1＋4x 2≥5
3x 1＋ x 2≥2
x 1, x2≥0且为整数
5.5 用隐枚举法求解0－1整数规划问题
max z ＝ 3x 1＋2x 2－5x 3－2x 4＋3x 5
st. x 1＋ x 2 ＋ x 3＋2x 4＋ x 5≤ 4
7x 1 ＋3x 3－4x 4＋3x 5≤ 8
11x 1－6x 2 ＋3x 4－3x 5≥ 3
１２９
x j ＝0或1（j ＝1，…，5）
5.6 请用解0－1整数规划的隐枚举法求解下面的两维0－1背包问题：
max f = 2x1+2x2+3x3
s.t. x 1+2x2+2x3≤4
2x 1+x2+3x3≤5
x j =0或1，j=1,2,3
5.7
用匈牙利法求解如下效率矩阵的指派问题
7 9 10 12
13 12 16 17
15 16 14 15
11 12 15 16
5.8 分配甲、乙、丙、丁四人去完成五项任务。每人完成各项任务时间如下表所示。由于任务数多于人数，故规定其中有一个人可兼完成两项任务，其余三人每人完成一项。试确定总花费时间为最少的指派方案。
A B C D E
甲 25 29 31 42 37
乙 39 38 26 20 33
丙 34 27 28 40 32
丁 24 42 36 23 45
5.9 已知下列五人各种姿势的游泳成绩（各为50米），试问如何进行指派，从中5.10. 运筹学中著名的旅行商贩（货郎担）问题可以叙述如下：某旅行商贩从某一城市出发，到其它几个城市去推销商品，规定每个城市均须到达而且只到达一次，然后回到原出发城市。已知城市i 和j 之间的距离为d ij ，问该商贩应选择一条什么样的路线顺序旅行，使总的旅程为最短。试对此问题建立整数规划模型。
5.11. 有三个不同的产品要在三台机床上加工，每个产品必须首先在机床1上加工，然后依次在机床2，3上加工。在每台机床上加工三个产品的顺序应保持一样，假定用t ij 表示在第j 机床上加工第i 个产品的时间，问应如何安排，使三个产品总的加工周期为最短。试建立此问题的整数规划模型。
１３０
习题五5.1 试将下述非线性的0－1规划问题转换为线性的0－1规划问题
max z ＝x 12＋x 2x 3－x 33
st. －2x 1＋3x 2＋x 3 ≤3
x j ＝0或1（j ＝1,2,3）
5.2 某钻井队要从以下10个可供选择的井位中确定5个钻井探油，使总的钻探费用为最小。若10个井位的代号为s 1，s 2，…，s 10，相应的钻探费用为c 1，c 2，…，c 10，并且井位选择上要满足下列限制条件：
（1） 或选择s 1和s 7，或选择钻探s 8；
（2） 选择了s 3或s 4就不能选s 5，或反过来也一样；
（3） 在s 5，s 6，s 7，s 8中最多只能选两个。
试建立此问题的整数规划模型。
5.3 用分枝定界法求解下列整数规划问题
(1) max z ＝x 1＋x 2
st. x 9
1＋14x 51
2 ≤14
－2x 1
1 ＋x 2 ≤3
x 1，x 2≥0且为整数
(2) max z ＝2x 1＋3x 2
st. 5x 1＋7x 2≤35
4x 1＋9x 2≤36
x 1，x 2≥0且为整数
5.4 用割平面法求解下列整数规划问题
(1) max z ＝7x 1＋9x 2
st. －x 1＋3 x2 ≤6
7x 1 ＋ x 2 ≤35
x 1，x 2≥0且为整数
(2) min z ＝4x 1＋5x 2
st. 3x 1＋2x 2≥7
x 1＋4x 2≥5
3x 1＋ x 2≥2
x 1, x2≥0且为整数
5.5 用隐枚举法求解0－1整数规划问题
max z ＝ 3x 1＋2x 2－5x 3－2x 4＋3x 5
st. x 1＋ x 2 ＋ x 3＋2x 4＋ x 5≤ 4
7x 1 ＋3x 3－4x 4＋3x 5≤ 8
11x 1－6x 2 ＋3x 4－3x 5≥ 3
１２９
x j ＝0或1（j ＝1，…，5）
5.6 请用解0－1整数规划的隐枚举法求解下面的两维0－1背包问题：
max f = 2x1+2x2+3x3
s.t. x 1+2x2+2x3≤4
2x 1+x2+3x3≤5
x j =0或1，j=1,2,3
5.7
用匈牙利法求解如下效率矩阵的指派问题
7 9 10 12
13 12 16 17
15 16 14 15
11 12 15 16
5.8 分配甲、乙、丙、丁四人去完成五项任务。每人完成各项任务时间如下表所示。由于任务数多于人数，故规定其中有一个人可兼完成两项任务，其余三人每人完成一项。试确定总花费时间为最少的指派方案。
A B C D E
甲 25 29 31 42 37
乙 39 38 26 20 33
丙 34 27 28 40 32
丁 24 42 36 23 45
5.9 已知下列五人各种姿势的游泳成绩（各为50米），试问如何进行指派，从中5.10. 运筹学中著名的旅行商贩（货郎担）问题可以叙述如下：某旅行商贩从某一城市出发，到其它几个城市去推销商品，规定每个城市均须到达而且只到达一次，然后回到原出发城市。已知城市i 和j 之间的距离为d ij ，问该商贩应选择一条什么样的路线顺序旅行，使总的旅程为最短。试对此问题建立整数规划模型。
5.11. 有三个不同的产品要在三台机床上加工，每个产品必须首先在机床1上加工，然后依次在机床2，3上加工。在每台机床上加工三个产品的顺序应保持一样，假定用t ij 表示在第j 机床上加工第i 个产品的时间，问应如何安排，使三个产品总的加工周期为最短。试建立此问题的整数规划模型。
１３０