若某钻井队要从以下10个可供选择的井位中确定5个钻井探油。使总的钻探费⽤为最⼩。若10个井位的代号为S 1,S 2．…，S 10相应的钻探费⽤为C 1 ,C 2 ,… C 10，并且井位选择要满⾜下列限制条件： (1)在s 1，s 2，S 4中⾄多只能选择两个；（2）在S 5，s 6中⾄少选择⼀个；（3）在s 3，s 6，S 7，S 8中⾄少选择两个。试建⽴这个问题的整数规划模型 解：设x j （j=1,…,10）为钻井队在第i 个井位探油 minZ=j j j x c ∑=10
1
背包问题：⼀个登⼭队员，他需要携带的物品有：⾷品、氧⽓、冰镐、绳索、帐篷、照相器材、通信器材等。每种物品的重量合重要性系数如表所⽰。设登⼭队员可携带的最⼤重量为25kg，试选择该队员所应携带的物品。
解：引⼊0—1变量x i , x i =1表⽰应携带物品i ，,x i =0表⽰不应携带物品I
==≤++++++++++++=7
,...,2,1,102542126255104814181520765432176
54321i x x x x x x x x x x x x x x x naxz i 或
集合覆盖和布点问题
某市消防队布点问题。该市共有6个区，每个区都可以建消防站，市政府希望设置的消防站最少，但必须满⾜在城市任何地区发⽣⽕警时，消防车要在15min 内赶到现场。据实地测定，各区之间消防车⾏驶的时间见表，请制定⼀个布点最少的计划。 解：引⼊0—1变量x i , x i =1表⽰在该区设消防站，,x i =0表⽰不设
=≥++≥++≥++≥+≥++≥++++++=0
1111111min 65
2
654
543
436
冰川运动
2
121654321或i x x x x x x x x x x x x x x x x x x x x x x x z
解得： X*=(0,1,0,1,0,0)’ Z*=2
某公司现有5个项⽬被列⼊投资计划，各项⽬的投资额和期望的投资收益如下表所⽰：
该公司只有600万元资⾦可⽤于投资，由于技术上的原因，投资受到以下条件的
约束：（1）在项⽬1、2和3中必须有⼀项被选中，（2）项⽬3和项⽬4只能选中⼀项，（3）项⽬5被选中的前提是项⽬1必须被选中。试就这⼀问题建⽴运筹学研究模型。
5.2某市为⽅便学⽣上学，拟在新建的居民⼩区增设若⼲所⼩学。已知备选校址代号及其能覆盖的居民
⼩区编号如表5–2所⽰，问为覆盖所有⼩区⾄少应建多少所⼩学，要求建模并求解。烯烃复分解
所⽰，现货物2、4中优先运2，货物1、5不能混装，试建⽴运费收⼊最多的运输⽅案。
5.11 运筹学中著名的旅⾏商贩（货朗担）问题可以叙述如下：某旅⾏商贩从某⼀城市出发，到其他⼏个城市推销商品，规定每个城市均需到达且只到达⼀次，然后回到原出发城市。已知城市i和城市j之间的距离为d ij问商贩应选择⼀条什么样的路线顺序旅⾏，使总的旅程最短。试对此问题建⽴整数规划模型。
有⼀组物品S，共有9件，其中第i件重i w，价值i v，从S中取出⼀些物品
⼯程上马的决策问题
某部门三年内有四项⼯程可以考虑上马，每项⼯程的期望收益和年度费⽤（千元）如下表所⽰：假定每⼀项已选定的⼯程要在三年内完成，是确定应该上马哪些⼯程，⽅能使该部门可能的期望收益最⼤。
为解决污⽔对河流的污染问题，某城市拟建污⽔处理站，备选的站址有A 、B 、C
物2，构建⼀个整数规划模型，在满⾜环保要求的前提下使投资和运⾏费⽤最少。1231231231
23112233123123min 50040030050080010008050408000060405060000 800500400,,0;,,0,1z y y y x x x x x x x x x x y x y x y x x x y y y =+++++++≥??++≥??≤??≤??≤?≥??为变量
为解决污⽔对河流的污染问题，某城市拟建污⽔处理站，备选的站址有A 、B 、
物2，构建⼀个整数规划模型，在满⾜环保要求的前提下使投资和运⾏费⽤最少。
第五章整数规划习题
5.1 考虑下列数学模型
)()(min 2211x f x f z += 且满⾜约束条件
（1）或101≥x ，或102≥x ；（2）下列各不等式⾄少有⼀个成⽴：
≥+≥+≥+15
21515221
2121x x x x x x
（3）021=-x x 或5或10 （4）01≥x ，02≥x 其中
)(11x f =??
=>+0,0
0,520111x x x 如如 =)(22x f ??
=>+0,0
0,612222x x x 如如
将此问题归结为混合整数规划的模型。
解：2211612510min x y x y z +++=
=≥≥=+++++-+-=-≤++-≥+-≥+-≥+?--≥?-≥?≤?≤），，＝（或
，）（）（）（；）（11.110;00)4(1
11105503215215152)1(1010102111
1098711109872165462152142132312211i y x x y y y y y y y y y y x x y y y M y x x M y x x M y x x M y x M y x M y x M y x i 5.2 试将下述⾮线性的0-1规划问题转换成线性的0-1规划问题
热休克蛋白3
3
3221max x x x x z -+= ??
senv
==≤++-）
，（或3,2,110332321j x x x x j
解：令=y ==否则，当,01132x x
故有y x x =32，⼜21x ，3
1x 分别与1x ，3x 等价，因此题中模型可转换为
31max x y x z -+=
-+≤+≤≤≤++-变量均为10,,,1
3323213
23
2321y x x x y x x x y x y x x x
5.3 某科学实验卫星拟从下列仪器装置中选若⼲件装上。有关数据资料见表5-1
要求：（1）装⼊卫星的仪器装置总体积不超过V ，总质量不超过W ；（2）A 1与A 3中最多安装⼀件；（3）A 2与A 4中⾄少安装⼀件；（4）A 5同A 6或者都安上，或者都不安。总的⽬的是装上取的仪器装置使该科学卫星发挥最⼤的实验价值。试建⽴这个问题的数学模型。解：
j
j j x c z ∑==6
1
max
==≥+≤+≤≤∑∑==否则
仪器安装,0,111
654231
6
1
6
二甲基砜
1j j j j j j j j A x x x x x x x W x w V x v
5.4 某钻井队要从以下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，中最多只能选两个；试建⽴这个问题的整数规划模型。解：
∑==10
1
min j j
j x c z
=≤+++≤+=+≤+=+=∑=，否则井位选择钻探第0s ,12
11115j 8
7655487538110
1
j x x x x x x x x x x x x x x j
5.5 ⽤割平⾯法求解下列整数规划问题（a ）2197max x x z +=
≥≤+≤+-且为整数0,,35
763212121x x x x x x （b ）215x 4x minz +=
≥≥+≥+≥+且为整数0x ,x 2x 3x 54x x 72x 3x 21212121 （c ）321264max x x x z ++=
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议