整数规划习题

第五章 整数规划习题

5.1 考虑下列数学模型 min且满足约束条件

z?f1(x1)?f2(x2)

（1）或x1?10，或x2?10；

（2）下列各不等式至少有一个成立：

?2x1?x2?15??x1?x2?15?x?2x?152 ?1

（3）

x1?x2?0或5或10

?0（4）x1其中

?0，x2

?20?5x1,如x1?0?,如x1?0f1(x1)?0=

将此问题归结为混合整数规划的模型。 解：min

z?10y1?5x1?12y2?6x2?12?6x2,如x2?0?,如x2?0f2(x2)??0

5.2 试将下述非线性的0-1规划问题转换成线性的0-1规划问题

maxz?x1?x2x3?x323（?0）x1?y1?M；x2?y2?M?（1）x1?10?y3?M??x2?10?(1?y3)?M?（?2）x1?x2?15?y4M?x1?x2?15?y5M??x1?2x2?15?y6M??y4?y5?y6?2?（?3）x1?x2?0y7?5y8?5y9?10y10?11y11?y7?y8?y9?y10?y11?1??1i＝1，.???，11）?(4)x1?0，x2?0;yi?0或（

??2x1?3x2?x3?3?x?0或1，（j?1,2,3） ?j

解：令故有

?1，当x2?x3?1?y??0,否则

x2x3?y，又

x12，

x13分别与x1，

x3等价，因此题中模型可转换为

maxz?x1?y?x3

5.3 某科学实验卫星拟从下列仪器装置中选若干件装上。有关数据资料见表5-1 表 5-1 仪器装置代号 体积 重量 实验中的价值 A1 v1 w1 c1 A2 v2 w2 c2 A3 v3 w3 c3 A4 v4 w4 c4 A5 v5 w5 c5 A6 v6 w6 c6 要求：（1）装入卫星的仪器装置总体积不超过V，总质量不超过W；（2）A1与A3中最多安装一件；（3）A2与A4中至少安装一件；（4）A5同A6或者都安上，或者都不安。总的目的是装上取的仪器装置使该科学卫星发挥最大的实验价值。试建立这个问题的数学模型。 解：

6??2x1?3x2?x3?3?y?x2???y?x3?x?x?y?13?2??x1,x2,x3,y均为0?1变量maxz??cj?1jxj

?6??vjxj?V?j?1?6??wjxj?W?j?1??x1?x3?1?x?x?124??x5?x6??1,安装Aj仪器?x???j?0,否则 ?

5.4 某钻井队要从以下10个可供选择的井位中确定5个钻井探油，使总的钻探费用最小。若10个井位的代号为s1 ，s2,…s10,相应的钻探费用为c1 ，c2,…,c10,并且井位选择上要满足下列限制条件：

（1）或选择s1和s7，或选择钻探s8；

（2）选择了s3或s4就不能选择s5，或反过来也一样；

（3）在s5,s6,s7,s8,中最多只能选两个；试建立这个问题的整数规划模型。 解：

10minz?

?10??xj??j?1?x?x8?1??x7?x8?x?x6?5??1?x????0??cj?1jxj

5?1?1x3?x5?1x4?x5?1?x7?x8?2,选择钻探第，否则sj井位

5.5 用割平面法求解下列整数规划问题 （a）maxz?7x1?9x2

??x1?3x2?6??7x1?x2?35?x,x,?0且为整数 ?12 （b）minz?4x1?5x 2

max （c）

?3x1?2x2?7??x1?4x2?5??3x1?x2?2?x,x?0且为整数?12

z?4x1?6x2?2x3 （d）max?4x1?4x2?5???x1?6x2?5??x1?x2?x3?5??x,x,x,?0且为整数?123

z?11x1?4x2

解：（a）不考虑整数约束，用单纯形法求解相应线性给华问题得最终单纯形表，见表5A-1。

??x1?2x2?14??5x1?2x2?16??2x1?x2?4?x,x,?0且为整数?12

表5A-1 x2 7/2 x1 9/2 cj-zj 从表中第1行得

x1 0 1 0 x2 1 0 0 x3 7/22 -1/22 -28/11 x4 1/22 3/22 -15/11 由此

x2?722x3?12?1122722x4?x3?72122

x4?01x2?3??7

222 即 22将此约束加上，并用对偶单纯形法求解得表5A-2。 表5A-2 x1 x2 x3 x2 7/2 0 1 7/22 x1 9/2 1 0 -1/22 s1 -1/2 0 0 [-7/22] cj-zj 0 0 -28/11 x2 3 0 1 0 x1 32/7 1 0 0 x3 11/7 0 0 1 cj-zj 0 0 0 由表5A-2的x行可写出 x3?x4?s1??x4 1/22 3/22 -1/22 -15/11 0 1/7 1/7 -1 )s1 0 0 1 0 1 -1/7 -22/7 -8 又得到一个新的约束

x1?(0?176)x4?(?1?674)s1?(4?47

77 7再将此约束加上，并用对偶单纯形法求解得表5A-3。 表5A-3 x1 x2 x3 x4 x2 3 0 1 0 0 x1 32/7 1 0 0 1/7 x3 11/7 0 0 1 1/7 s2 -4/7 0 0 0 [-1/7] cj-zj 0 0 0 -1 x2 3 0 1 0 0 x1 4 1 0 0 0 x3 1 0 0 1 0 ?1x4?s1?s2??s1 1 -1/7 -22/7 -6/7 -8 1 -1 -4 s2 0 0 0 1 0 0 1 1 x4 4 cj-zj 0 0 0 0 0 0 1 0 6 -2 -7 -7

因此本题最优解为 x1=4，x2=3，z=55 （b）本题最优解为x1=2，x2=1，z=13

（c）本题最优解为x1=2，x2=1，x3=6，z=26 （d）本题最优解为x1=2，x2=3，z=34

5.6 分配甲、乙、丙、丁四个人去完成五项任务。每人完成各项任务时间如表5-2所。由于任务数多于人数，故规定其中有一个人可兼完成两项任务，其余三人每人完成一项。试确定总花费时间为最少的指派方案。 表5-2 任务 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 解： 加工假设的第五个人是戊，他完成各项工作时间去甲、乙、丙、丁中最小者，构造表为5A-4 表5A-4 任务 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 戊 24 27 26 20 32 对表5A-4再用匈牙利法求解，得最优分配方案为甲-B，乙-D和C，丙-E，丁-A，总计需要131小时。

5.7 某航空公司经营A，B，C三个城市之间的航线，这些航线每天班机起飞与到达时间如表5-3所示。 表5-3 航班号 起飞城市 起飞时间 到达城市 到达时间 101 A 9：00 B 12：00 102 A 10：00 B 13：00 103 A 15：00 B 18：00 104 A 20：00 C 24：00 105 A 22：00 C 2：00 106 B 4：00 A 7：00 107 B 11：00 A 14：00

承担第4项任务。在满足上述条件下，如何分配工作，使完成四项工作总的花费时间为最少。 表5-9 人 甲 乙 丙 丁 戊 工作 1 10 2 3 15 9 2 5 10 15 2 4 3 15 5 14 7 15 4 20 15 13 6 8 解：先增加一种假想工作5，再据题中给的条件列出表5A-9 表5A-8 人 甲 乙 丙 丁 戊 工作 1 10 2 3 15 9 2 5 10 15 2 4 3 15 5 14 7 15 4 20 15 13 ∞ 8 5 ∞ 0 0 0 0 对表5A-9用匈牙利法求解得最优分配方案为：甲-2，乙-3，丙-1，戊-4，对丁不分配工作。

5-18 设有m个某种物资的生产点，其中第i个点（i=1，…，m）的产量为ai。该种物资销往n个需求点，其中第j个需求点所需量为bj（j=1，…，n）。已知。已知。又知从各生产点往需求点发运时，均需经过p个中间编组站之一转运，若启用第k个中间编组站，不管转运量多少，均发生固定费用f，而第k个中间编组站转运最大容量限制为qk（k=1，…，p）。用cik和ckj分别表示从i到k和从k 到j的单位物资的运输费用，试确定一个使总费用为最小的该种物资的调运方案。

ij?ai??bj解： 设

则问题的数学模型可表述为：

minz??1yk???0,启用第k个编组站，否则

ik

?kfk?yk???cik?xik???ckjkjxkj

???k???k????i????i???xik?aixkj?bjxik?qkxik?(i?1,...,m)(j?1,...,n)(k?1,...,p)xkj(k?1,...,p)(k?1,...,p)?jxik?M?yk?i??xik?0,xkj?0yk?0或1

本文来源：https://www.bwwdw.com/article/en48.html