整数规划

若某钻井队要从以下10个可供选择的井位中确定5个钻井探油。使总的钻探费用为最小。若10个井位的代号为S1,S2．…，S10相应的钻探费用为C1 ,C2 ,… C10，并且井位选择要满足下列限制条件： (1)在s1，s2，S4中至多只能选择两个； （2）在S5，s6中至少选择一个；（3）在s3，s6，S7，S8中至少选择两个。 试建立这个问题的整数规划模型

解：设xj（j=1,…,10）为钻井队在第i个井位探油 minZ=?cjxj

j?110

背包问题：一个登山队员，他需要携带的物品有：食品、氧气、冰镐、绳索、帐篷、照相器材、通信器材等。每种物品的重量合重要性系数如表所示。设登山队员可携带的最大重量为25kg,试选择该队员所应携带的物品。

序号 1 2 3 4 5 6 7 物品 食品 氧气 冰镐 绳索 帐篷 照相器材 通信设备 重量/Kg 5 5 2 6 12 2 4 重要性系数 20 15 18 14 8 4 10

解：引入0—1变量xi, xi=1表示应携带物品i，,xi=0表示不应携带物品I

naxz?20x1?15x2?18x3?14x4?8x5?4x6?10x7?5x1?5x2?2x3?6x4?12x5?2x6?4x7?25??xi?0或1,i?1,2,...,7

集合覆盖和布点问题

某市消防队布点问题。该市共有6个区，每个区都可以建消防站，市政府希望设置的消防站最少，但必须满足在城市任何地区发生火警时，消防车要在15min内赶到现场。据实地测定，各区之间消防车行驶的时间见表，请制定一个布点最少的计划。 地区1 地区2 地区3 地区4 地区5 地区6 地区1 0 10 16 28 27 20 地区2 10 0 24 32 17 10 地区3 16 24 0 12 27 21 地区4 28 32 12 0 15 25 地区5 27 17 27 15 0 14 地区6 20 10 21 25 14 0

1

解：引入0—1变量xi, xi=1表示在该区设消防站，,xi=0表示不设

minz?x1?x2?x3?x4?x5?x6?x1?x?1?????????x2?x2x3x3x2xi?1或0?x4?x4x4?x5?x5?x5?x6?x6?x6?1?1?1?1?1?1

解得： X*=(0,1,0,1,0,0)’ Z*=2

某公司现有5个项目被列入投资计划，各项目的投资额和期望的投资收益如下表所示：

项目编号 1 2 3 4 5

该公司只有600万元资金可用于投资，由于技术上的原因，投资受到以下条件的约束：（1）在项目1、2和3中必须有一项被选中，（2）项目3和项目4只能选中一项，（3）项目5被选中的前提是项目1必须被选中。试就这一问题建立运筹学研究模型。

5.2某市为方便学生上学，拟在新建的居民小区增设若干所小学。已知备选校址代号及其能覆盖的居民小区编号如表5–2所示，问为覆盖所有小区至少应建多少所小学，要求建模并求解。

表5–12 备选校址代号 覆盖的居民小区编号

2

投资额（万元） 210 300 100 130 260 投资收益（万元） 150 210 60 80 180 1，5，7 1，2，5 C 1，3，5 D 2，4，5 E 3，6， F 4，6， 5.3一货船，有效载重量为24吨，可运输货物重量及运费收入如表5-13所示，现货物2、4中优先运2，货物1、5不能混装，试建立运费收入最多的运输方案。

表5-13 货物 1 2 3 4 5 6 重量（吨） 5 9 8 7 10 23 收入（万1 4 4 3 5 7 元）

5.11 运筹学中著名的旅行商贩（货朗担）问题可以叙述如下：某旅行商贩从某一城市出发，到其他几个城市推销商品，规定每个城市均需到达且只到达一次，然后回到原出发城市。已知城市i和城市j之间的距离为dij问商贩应选择一条什么样的路线顺序旅行，使总的旅程最短。试对此问题建立整数规划模型。

A B 有一组物品S，共有9件，其中第i件重wi，价值vi，从S中取出一些物品出来装背包，使总价值最大，而不超过总重量的给定上限30kg。 i 1 2 3 4 5 6 7 8 9 wi(kg) 2 1 1 2.5 10 6 5 4 3 vi(元) 10 45 30 100 150 90 200 180 300

工程上马的决策问题

某部门三年内有四项工程可以考虑上马，每项工程的期望收益和年度费用（千元）如下表所示：假定每一项已选定的工程要在三年内完成，是确定应该上马哪些工程，方能使该部门可能的期望收益最大。

工 程 第1年 1 2 3 第2年 第3年 20 40 20 5 1 8 4 7 10 3 9 2 费 用 期望收益 3

4 可用资金

8 6 10 18 22 24 30 为解决污水对河流的污染问题，某城市拟建污水处理站，备选的站址有A、B、C三个，其投资等技术经济参数如下表： 投资（万元） 处理能力水处理成本水处理指标（吨∕万吨） （万吨∕（元∕万污染物1 污染物2 年） 吨） A 500 800 500 80 60 B 400 500 800 50 40 C 300 400 1000 40 50 按环保部门的要求，每年至少要从污水中清除8万吨的污染物1和6万吨的污染物2，构建一个整数规划模型，在满足环保要求的前提下使投资和运行费用最少。

minz?500y1?400y2?300y3?500x1?800x2?1000x3?80x1?50x2?40x3?80000?60x?40x?50x?6000023?1??x1?800y1??x2?500y2?x3?400y3???x1,x2,x3?0;y1,y2,y3为0,1变量

为解决污水对河流的污染问题，某城市拟建污水处理站，备选的站址有A、B、C三个，其投资等技术经济参数如下表： 投资（万元） 处理能力水处理成本水处理指标（吨∕万吨） （万吨∕（元∕万污染物1 污染物2 年） 吨） A 500 800 500 80 60 B 400 500 800 50 40 C 300 400 1000 40 50 按环保部门的要求，每年至少要从污水中清除8万吨的污染物1和6万吨的污染物2，构建一个整数规划模型，在满足环保要求的前提下使投资和运行费用最少。

第五章 整数规划习题

5.1 考虑下列数学模型

minz?f1(x1)?f2(x2) 且满足约束条件

（1）或x1?10，或x2?10； （2）下列各不等式至少有一个成立：

4

（3）x1?x2?0或5或10 （4）x1?0，x2?0 其中

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

?20?5x1,如x1?0?,如x1?0 f(x) 11=?0?12?6x2,如x2?0?,如x2?0 f2(x2)??0

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

解：minz?10y1?5x1?12y2?6x2

（?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?y?y?y?y?y?17891011??（1i＝1，.???，11） ?(4)x1?0，x2?0;yi?0或

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

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

?1，当x2?x3?1?y??0,否则解：令

23xx?yxx23故有，又1，1分别与x1，x3等价，因此题中模型可转换为

maxz?x1?y?x3

5

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