第二章--整数规划

第二章 整数规划

§1 概论

1.1 定义

规划中的变量（部分或全部）限制为整数时，称为整数规划。若在线性规划模型中，变量限制为整数，则称为整数线性规划。目前所流行的求解整数规划的方法，往往只适用于整数线性规划。目前还没有一种方法能有效地求解一切整数规划。

1.2 整数规划的分类

如不加特殊说明，一般指整数线性规划。对于整数线性规划模型大致可分为两类： 1o 变量全限制为整数时，称纯（完全）整数规划。

2o 变量部分限制为整数的，称混合整数规划。

1.2 整数规划特点

（i ） 原线性规划有最优解，当自变量限制为整数后，其整数规划解出现下述情况： ①原线性规划最优解全是整数，则整数规划最优解与线性规划最优解一致。 ②整数规划无可行解。

例1 原线性规划为

21m in x x z +=

0,0,

5422121≥≥=+x x x x 其最优实数解为：4

5min ,45,021===z x x 。 ③有可行解（当然就存在最优解），但最优解值变差。

例2 原线性规划为

21m in x x z += 0,0,

6422121≥≥=+x x x x 其最优实数解为：2

3min ,23,021===z x x 。 若限制整数得：2m in ,1,121===z x x 。

（ii ） 整数规划最优解不能按照实数最优解简单取整而获得。

1.3 求解方法分类：

（i ）分枝定界法—可求纯或混合整数线性规划。

（ii ）割平面法—可求纯或混合整数线性规划。

（iii ）隐枚举法—求解“0-1”整数规划：

①过滤隐枚举法；

②分枝隐枚举法。

（iv ）匈牙利法—解决指派问题（“0-1”规划特殊情形）。

（v ）蒙特卡洛法—求解各种类型规划。

下面将简要介绍常用的几种求解整数规划的方法。

§2 分枝定界法

对有约束条件的最优化问题（其可行解为有限数）的所有可行解空间恰当地进行系统搜索，这就是分枝与定界内容。通常，把全部可行解空间反复地分割为越来越小的子集，称为分枝；并且对每个子集内的解集计算一个目标下界（对于最小值问题），这称为定界。在每次分枝后，凡是界限超出已知可行解集目标值的那些子集不再进一步分枝，

这样，许多子集可不予考虑，这称剪枝。这就是分枝定界法的主要思路。

分枝定界法可用于解纯整数或混合的整数规划问题。在本世纪六十年代初由Land Doig 和Dakin 等人提出的。由于这方法灵活且便于用计算机求解，所以现在它已是解整数规划的重要方法。目前已成功地应用于求解生产进度问题、旅行推销员问题、工厂选址问题、背包问题及分配问题等。

设有最大化的整数规划问题A ，与它相应的线性规划为问题B ，从解问题B 开始，若其最优解不符合A 的整数条件，那么B 的最优目标函数必是A 的最优目标函数*z 的上界，记作z ；而A 的任意可行解的目标函数值将是*z 的一个下界z 。分枝定界法就是将B 的可行域分成子区域的方法。逐步减小z 和增大z ，最终求到*z 。现用下例来说明：

例3 求解下述整数规划

219040Max x x z +=

?????≥≥+≤+且为整数0,7020756792

12121x x x x x x

解 （i ）先不考虑整数限制，即解相应的线性规划B ，得最优解为：

355.8779,8168.1,8092.421===z x x

可见它不符合整数条件。这时z 是问题A 的最优目标函数值*

z 的上界，记作z 。而

0,021==x x 显然是问题A 的一个整数可行解，这时0=z ，是*z 的一个下界，记作z ，即3560*

≤≤z 。

（ii ）因为21,x x 当前均为非整数，故不满足整数要求，任选一个进行分枝。设选1x 进行分枝，把可行集分成2个子集：

44.8092][1=≤x ，514.8092][1=+≥x

因为4与5之间无整数，故这两个子集的整数解必与原可行集合整数解一致。这一步称为分枝。这两个子集的规划及求解如下：

问题1B ： 219040Max x x z += ??

???≥≤≤≥+≤+0,40702075679212121x x x x x x

最优解为：349,1.2,0.4121===z x x 。

问题2B ： 219040Max x x z +=

?????≥≥≥+≤+0,570207567921

2121x x x x x x

最优解为：4.341,57.1,0.5121===z x x 。

再定界：3490*

≤≤z 。

（iii ）对问题1B 再进行分枝得问题11B 和12B ，它们的最优解为 340,2,4:112111===z x x B

327.14,00.3x 1.43,:122112===z x B

再定界：341340*

≤≤z ，并将12B 剪枝。

（iv ）对问题2B 再进行分枝得问题21B 和22B ，它们的最优解为 083,00.1x 5.44,:222121===z x B

22B 无可行解。

将2221,B B 剪枝。

于是可以断定原问题的最优解为：

340,2,4*21===z x x

从以上解题过程可得用分枝定界法求解整数规划（最大化）问题的步骤为： 开始，将要求解的整数规划问题称为问题A ，将与它相应的线性规划问题称为问题B 。

（i ）解问题B 可能得到以下情况之一：

（a ）B 没有可行解，这时A 也没有可行解，则停止．

（b ）B 有最优解，并符合问题A 的整数条件，B 的最优解即为A 的最优解，则停止。

（c ）B 有最优解，但不符合问题A 的整数条件，记它的目标函数值为z 。

（ii ）用观察法找问题A 的一个整数可行解，一般可取n j x j ,,1,0Λ==，试探，求得其目标函数值，并记作z 。以*

z 表示问题A 的最优目标函数值；这时有 z z z ≤≤*

进行迭代。

第一步：分枝，在B 的最优解中任选一个不符合整数条件的变量j x ，其值为j b ，以][j b 表示小于j b 的最大整数。构造两个约束条件 ][j j b x ≤ 和 1][+≥j j b x

将这两个约束条件，分别加入问题B ，求两个后继规划问题1B 和2B 。不考虑整数条件求解这两个后继问题。

定界，以每个后继问题为一分枝标明求解的结果，与其它问题的解的结果中，找出最优目标函数值最大者作为新的上界z 。从已符合整数条件的各分支中，找出目标函数值为最大者作为新的下界z ，若无作用0=z 。 第二步：比较与剪枝，各分枝的最优目标函数中若有小于z 者，则剪掉这枝，即以后不再考虑了。若大于z ，且不符合整数条件，则重复第一步骤。一直到最后得到z z =*为止。得最优整数解n j x j ,,1

,*Λ=。

§3 10-型整数规划

10-型整数规划是整数规划中的特殊情形，它的变量j x 仅取值0或1。这时j x 称为10-变量，或称二进制变量。j x 仅取值0或1这个条件可由下述约束条件： 10≤≤j x ，整数

所代替，是和一般整数规划的约束条件形式一致的。在实际问题中，如果引入 10-变量，就可以把有各种情况需要分别讨论的线性规划问题统一在一个问题中讨论了。我们

先介绍引入10-变量的实际问题，再研究解法。

3.1 引入10-变量的实际问题

3.1.1 投资场所的选定——相互排斥的计划

例 4 某公司拟在市东、西、南三区建立门市部。拟议中有7个位置（点）)7,,2,1(Λ=i A i 可供选择。规定

在东区。由321,,A A A 三个点中至多选两个；

在西区。由54,A A 两个点中至少选一个；

在南区，由76,A A 两个点中至少选一个。

如选用i A 点，设备投资估计为i b 元，每年可获利润估计为i c 元，但投资总额不能超过B 元。问应选择哪几个点可使年利润为最大？

解题时先引入10-变量)7,,2,1(Λ=i x i

令

?

??=.0,1点没被选中当点被选中当，，i A i A i x 7,,2,1Λ=i . 于是问题可列写成：

i i i x c z ∑==7

1Max

?????????=≥+≥+≤++≤∑=10,

112

7654

3217

1或i i i i x x x x x x x x B

x b

3.1.2 相互排斥的约束条件

有两个相互排斥的约束条件

244521≤+x x 或 453721≤+x x 。 为了统一在一个问题中，引入10-变量y ，则上述约束条件可改写为：

??

???=-+≤++≤+10)1(453724452121或y M y x x yM x x

其中M 是充分大的数。

约束条件

01=x 或 8005001≤≤x

可改写为

?

??=≤≤108005001或y y x y 如果有m 个互相排斥的约束条件：

m i b x a x a i n in i ,,2,111ΛΛ=≤++

为了保证这m 个约束条件只有一个起作用，我们引入m 个10-变量),,2,1(m i y i Λ=和一个充分大的常数M ，而下面这一组1+m 个约束条件

m i M y b x a x a i i n in i ,,2,111ΛΛ=+≤++ （1）

11-=++m y y m Λ （2） 就合于上述的要求。这是因为，由于（2），m 个i y 中只有一个能取0值，设0*=i y ，代入（1），就只有*

i i =的约束条件起作用，而别的式子都是多余的。

3.1.3 关于固定费用的问题（Fixed Cost Problem ）

在讨论线性规划时，有些问题是要求使成本为最小。那时总设固定成本为常数，并在线性规划的模型中不必明显列出。但有些固定费用（固定成本）的问题不能用一般线性规划来描述，但可改变为混合整数规划来解决，见下例。

例5 某工厂为了生产某种产品，有几种不同的生产方式可供选择，如选定的生产方式投资高（选购自动化程度高的设备），由于产量大，因而分配到每件产品的变动成本就降低；反之，如选定的生产方式投资低，将来分配到每件产品的变动成本可能增加。所以必须全面考虑。今设有三种方式可供选择，令

j x 表示采用第j 种方式时的产量； j c 表示采用第j 种方式时每件产品的变动成本；

j k 表示采用第j 种方式时的固定成本。

为了说明成本的特点，暂不考虑其它约束条件。采用各种生产方式的总成本分别为 ???=>+= 0 ,00

,j j i i i i x x x c k P 当当 3,2,1=j .

在构成目标函数时，为了统一在一个问题中讨论，现引入10-变量j y ，令

??

???==>.00,0,1时种生产方式，即当不采用第时，

种生产方式，即当采用第j x j j x j j y （3） 于是目标函数

)()()(m in 333322221111x c y k x c y k x c y k z +++++=

（3）式这个规定可表为下述3个线性约束条件：

3,2,1,=≤j M y x j j （4） 其中M 是个充分大的常数。（4）式说明，当0>j x 时j y 必须为1；当0=j x 时只有j y 为0时才有意义，所以（4）式完全可以代替（3）式。

3.2 10-型整数规划解法之一（过滤隐枚举法）

解10-型整数规划最容易想到的方法，和一般整数规划的情形一样，就是穷举法，即检查变量取值为0或1的每一种组合，比较目标函数值以求得最优解，这就需要检查变量取值的n

2个组合。对于变量个数n 较大（例如10>n ），这几乎是不可能的。因此常设计一些方法，只检查变量取值的组合的一部分，就能求到问题的最优解。这样的方法称为隐枚举法（Implicit Enumeration ），分枝定界法也是一种隐枚举法。当然，对有些问题隐枚举法并不适用，所以有时穷举法还是必要的。

下面举例说明一种解10-型整数规划的隐枚举法。

例6 321523Max x x x z +-=

?????????=≤+≤+≤++≤-+1

0,,643442232132

21321321或x x x x x x x x x x x x x

求解思路及改进措施：

（i ） 先试探性求一个可行解，易看出)0,0,1(),,(321=x x x 满足约束条件，故为一个可行解，且3=z 。

（ii ） 因为是求极大值问题，故求最优解时，凡是目标值3

（iii ） 改进过滤条件。

（iv ） 由于对每个组合首先计算目标值以验证过滤条件，故应优先计算目标值z

大的组合，这样可提前抬高过滤门槛，以减少计算量。

§4 蒙特卡洛法（随机取样法）

前面介绍的常用的整数规划求解方法，主要是针对线性整数规划而言，而对于非线性整数规划目前尚未有一种成熟而准确的求解方法，因为非线性规划本身的通用有效解法尚未找到，更何况是非线性整数规划。

然而，尽管整数规划由于限制变量为整数而增加了难度；然而又由于整数解是有限个，于是为枚举法提供了方便。当然，当自变量维数很大和取值范围很宽情况下，企图用显枚举法（即穷举法）计算出最优值是不现实的，但是应用概率理论可以证明，在一定的计算量的情况下，完全可以得出一个满意解。

例7 已知非线性整数规划为： 5

432125

242322212328 243Max x x x x x x x x x x z -----++++=

?????????≤++≤++≤++++≤++++=≤≤200520062800622400)5,,1(990543321

5432154321x x x x x x x x x x x x x x x x i x i Λ

对该题，目前尚无有效方法求出准确解。如果用显枚举法试探，共需计算

10510)100(=个点，其计算量非常之大。然而应用蒙特卡洛去随机计算610个点，便可找到满意解，那么这种方法的可信度究竟怎样呢？

下面就分析随机取样采集6

10个点计算时，应用概率理论来估计一下可信度。 不失一般性，假定一个整数规划的最优点不是孤立的奇点。

假设目标函数落在高值区的概率分别为0.01，0.00001，则当计算610个点后，有任一个点能落在高值区的概率分别为 多位）100(9999.099.011000000Λ≈-，

999954602.099999.011000000≈-。

解 （i ）首先编写M 文件mente.m 定义目标函数f 和约束向量函数g ，程序如下：

function [f,g]=mengte(x);

f=x(1)^2+x(2)^2+3*x(3)^2+4*x(4)^2+2*x(5)-8*x(1)-2*x(2)-3*x(3)...

-x(4)-2*x(5);

g(1)=sum(x)-400;

g(2)=x(1)+2*x(2)+2*x(3)+x(4)+6*x(5)-800;

g(3)=2*x(1)+x(2)+6*x(3)-200;

g(4)=x(3)+x(4)+5*x(5)-200;

（ii ）编写如下程序求问题的解：

rand('state',sum(clock));

p0=0;

tic

for i=1:10^5

x=99*rand(5,1);

x1=floor(x);x2=ceil(x);

[f,g]=mengte(x1);

if sum(g<=0)==4

if p0<=f

x0=x1;p0=f;

end

end

[f,g]=mengte(x2);

if sum(g<=0)==4

if p0<=f

x0=x2;p0=f;

end

end

end

x0,p0

toc

§5 整数规划的计算机解法

整数规划问题的求解可以使用Lingo 等专用软件。对于一般的整数规划规划问题，无法直接利用Matlab 的函数，必须利用Matlab 编程实现分枝定界解法和割平面解法。但对于指派问题等特殊的10-整数规划问题或约束矩阵A 是幺模矩阵时，有时可以直接利用Matlab 的函数linprog 。

例8 求解下列指派问题，已知指派矩阵为

???????

?????????10961095324

85724679278310283 解：编写Matlab 程序如下：

c=[3 8 2 10 3;8 7 2 9 7;6 4 2 7 5

8 4 2 3 5;9 10 6 9 10];

c=c(:);

a=zeros(10,25);

for i=1:5

a(i,(i-1)*5+1:5*i)=1;

a(5+i,i:5:25)=1;

end

b=ones(10,1);

[x,y]=linprog(c,[],[],a,b,zeros(25,1),ones(25,1))

求得最优指派方案为151********=====x x x x x ，最优值为21。

习 题 二

1. 用分枝定界法解：

21Max x x z +=

????

?????≥≤+-≤+整数

21212121,,0,3121451149x x x x x x x x 2. 试将下述非线性的10-规划问题转换成线性的10-规划问题

3211m ax x x x x z -+=

???==≤++-)

3,2,1(10332321j x x x x j ，或

3. 某钻井队要从以下10个可供选择的井位中确定5个钻井探油，使总的钻探费用为最小。若10个井位的代号为1021,,,s s s Λ，相应的钻探费用为1021,,,c c c Λ，并且井位选择上要满足下列限制条件：

（1） 或选择1s 和7s ，或选择钻探9s ；

（2） 选择了3s 或4s 就不能选5s ，或反过来也一样；

（3） 在8765,,,s s s s 中最多只能选两个；试建立这个问题的整数规划模型。

MATLAB求解线性规划含整数规划和01规划问题.pdf

MATLAB 求解线性规划（含整数规划和0-1规划）问题 线性规划是数学规划中的一类最简单规划问题，常见的线性规划是一个有约束的，变量范围为有理数的线性规划。如： max 712z x y =+ 9430045200s.t 310300,0 x y x y x y x y +≤??+≤??+≤??≥? 对于这类线性规划问题，数学理论已经较为完善，可以有多种方法求解此类问题。但写这篇文章的目的并不是为了介绍数学理论，我们这里主要讲解如果利用工具求解这一类线性规划问题。 最著名，同时也是最强大的数学最优化软件是LINGO/LINDO 软件包，它能够求解多种的数学规划问题，同时还提供了多种的分析能力。但LINGO 软件并不容易上手，同时，应用LINGO 的场合一般是大规模的线性规划问题，小小的线性规划完全可以不使用它。一个更受科研人员欢迎的数学软件是MATLAB ，它以功能强大而称著，并有数学软件中的“航空母舰”之称。我们这里就是要学习使用MATLAB 软件求解线性规划（含整数规划和0-1规划）问题。 为了使得不熟悉MATLAB 的人员也能够使用MATLAB 进行线性规划问题求解，本文将对MATALB 中使用到的函数和过程以及结果进行详细的分析，最后会对每一个问题都给出一个可以完全“套用”的MATLAB 程序。 我们首先从上面的线性规划问题开始，为了便于表达，将上面的式子写成矩阵形式： max 712z x y =+ 9430045200s.t 310300,0x y x y ???????? ? ??≤? ? ? ???? ? ???????≥? 于是约束就表达为了一个Ax b ≤不等式。 求解MATLAB 线性规划时，最常用的函数是linprog 函数，下面来介绍一下这个函数的使用。 打开MATLAB 帮助文档（PS:帮助文档的内容是最全的，只要你的英文过了专业8级），可以看到linprog 函数求解的是具有如下标准形式的线性规划：

第五章整数规划

第五章 整数规划 主要内容：1、分枝定界法； 2、割平面法； 3、0－1型整数规划； 4、指派问题。 重点与难点：分枝定界法和割平面法的原理、求解方法，0－1型规划模型的建立及求解步骤，用匈牙利法求解指派问题的方法和技巧。 要 求：理解本章内容，熟练掌握求解整数规划的方法和步骤，能够运用这些方法解决实际问题。 §1 问题的提出 要求变量取为整数的线性规划问题，称为整数规则问题（简称IP ）。如果所有的变量都要求为（非负）整数，称之为纯整数规划或全整数规划；如果仅一部分变量要求为整数，称为混合整数规划。 例1 求解下列整数规划问题 211020m ax x x z += ????? ? ?≥≤+≤+为整数2 1212121,0,13522445x x x x x x x x 如果不考虑整数约束，就是一个线性规划问题（称这样的问题为原问题相应的线性规划问题），很容易求得最优解为： 96m ax ,0,8.421===z x x 。

用图解法将结果表示于图中画“+”号的点都是可行的整数解，为满足要求，将等值线向原点 方向移动，当第一次遇到“+”号点（1,421==x x ）时得最优解为1,421==x x ， 最优值为z=90。 由上例可看出，用枚举法是容易想到的，但常常得到最优解比较困难，尤其是遇到变量的取值更多时，就更困难了。下面介绍几种常用解法。 §2 分枝定界法 分枝定界法可用于解纯整数或混合的整数规划问题。基本思路：设有最大化的整数规划问题A ，与之相应的线性规划问题B ，从解B 开始，若其最优解不符合A 的整数条件，那么B 的最优值必是 A 的最优值 * z 的上界，记为 z ；而A 的任意可行解的目标函数值是* z 的一个下界 z ，采 取将B 的可行域分枝的方法，逐步减少z 和增大z ，最终求得*z 。现举例说明： 例2 求解A 219040m ax x x z += ?????? ?≥≤+≤+为整数 21212121,0 ,7020756 79x x x x x x x x 解：先不考虑条件⑤，即解相应的线性规划B （①--④），得最优解 =1x 4.81, =2x 1.82, ① ② ③ ④ ⑤

01型整数规划模型

甲乙公司不合作即竞争下所争取到的不同名专业推广者所建立的不同动态规划模 型的组合方案如下：其中X 为可能竞争到的专业推广者人数，即动态规划模型中第一天的

专业推广者推 广能力的份数，Y 为第二天需要的专业推广者推广能力的份数，即第三天安排从事推广 工作的专业推广者的人数；Z 为第三天需要的专业推广者推广能力的份数，即第三天安排从事推广工作的专业推广者的人数；a 为x 名专业推广者累计从事培训工作出来的兼职推广者的批数（每批20 人），其中，有多种组合方案；甲公司雇佣这些兼职推广者均工作一天，从事推广工作，第二天辞退a ?b 批兼职推广员，其余的b 批继续从事推广工作一天后辞退，即兼职宣传员总共最多雇佣2 天；cost 为花费的成本，即资金的使用数量；F 为不同方案下所达到的总推广效益。上表可以提供给甲公司做决策依据，根据效益的大小甲公司可以决策的目标方向顺序是从①--⑧，即不合作的情况下甲公司可以尽量争取到9 人，如若 不行，考虑争取4 人。 §5.4 0—1型整数规划模型 1、 0—1型整数规划模型概述 整数规划指的是决策变量为非负整数值的一类线性规划，在实际问题的应用中，整数规划模型对应着大量的生产计划或活动安排等决策问题，整数规划的解法主要有分枝定界解法及割平面解法（这里不作介绍，感兴趣的读者可参考相关书籍）。在整数规划问题中，0—1型整数规划则是其中较为特殊的一类情况，它要求决策变量的取值仅为0或1，在实际问题的讨论中，0—1型整数规划模型也对应着大量的最优决策的活动与安排讨论，我们将列举一些模型范例，以说明这个事实。 0—1型整数规划的的数学模型为： 目标函数 n n x c x c x c z M i n M a x +++= 2211)( 约束条件为： ???? ?? ?==≥≤++=≥≤++=≥≤++1 | 0 ) ,() ,() ,(2211222221211 1212111n m n mn m m n n n n x x x b x a x a x a b x a x a x a b x a x a x a , , ,21 这里，0 | 1表示0或1。 2、0—1型整数规划模型的解法

运筹学[第五章整数规划]山东大学期末考试知识点复习

第五章整数规划 1．整数规划的特点 (1)整数规划：决策变量要求取整数的线性规划。 (2)整数规划可分为纯整数规划和混合整数规划。 (3)整数规划的可行域为离散点集。 2．整数规划的建模步骤 整数规划模型的建立几乎与线性规划模型的建立完全一致，只是变量的部分或全体必须限制为整数。 3．求解整数规划的常用方法 1)分支定界法 没有最大化的整数规划问题A，与它相应的线性规划问题为问题B，从解问题B开始，若其最优解不符合A的整数条件，那么B的最优目标函数必是A的最优目标函数z*的上界，记作，而A的任意可行解的目标函数值将是z*的一个 下界，分支定界法就是将B的可行域分成子区域的方法，逐步减小和增大， 最终求得z*。 将要求解的整数规划问题称为问题A，将与它相应的线性规划问题称为问题B。 (1)解与整数规划问题A相应的线性规划问题B，可能得到以下几种情况之一： ①B没有可行解，A也没有可行解，停止计算。 ②B有最优解，并符合问题A的整数条件，则此最优解即为A的最优解，停止计算。 ③B有最优解，但不符合A的整数条件，记它的目标函数值为。

(2)用观察法找问题A的一个整数可行解，求得其目标函数值，并记作。 以z*表示问题A的最优目标数值，则≤z*≤。 下面进行迭代。 分支，在B的最优解中任选一个不符合整数条件的变量x i ，其值为b i 。 构造两个约束条件 x j ≤[b j ] ① 和 x j ≥[b j ]+1 ② 其中[b j ]为不超过b j 的最大整数。 将这两个约束条件分别加入问题B，求两个后继规划问题B1和B2。不考虑整数约束条件求解这两个后继问题。 定界，以每个后继问题为一分支标明求解的结果。 第一步：先不考虑整数约束，变成一般的线性规划问题，用图解法或单纯形法求其最优解，记为 ) ； 第二步：若求得的最优解，刚好就是整数解，则该整数就是原整数规划的最优解，否则转下步； 第三步：对原问题进行分支寻求整数最优解。 第四步：对上面两个子问题按照线性规划方法求最优解。若某个子问题的解是整数解，则停止该子问题的分支，并且把它的目标值与上一步求出的最优整数解相比较以决定取舍；否则，对该子问题继续进行分支。

第五章 整数规划练习题答案

第五章 整数规划练习题答案 一. 判断下列说法是否正确 1. 用分枝定界法求解一个极大化的整数规划问题时，任何一个可行整数解的目标函数值是 该问题目标函数值的下界。() 2. 用割平面法求解整数规划时，构造的割平面有可能切去一些不属于最优解的整数解。() 3. 用割平面法求解纯整数规划时，要求包括松弛变量在内的全部变量必须取整数值。() 4. 指派问题数学模型的形式与运输问题十分相似，故也可以用表上作业法求解。() 二. 设有五项工作要分派给五个工人，每人的作业产值如下表所示，为了使总产值最大，问 应如何分配这五项工作，并求得最大产值。 工作 工人 A & B C D E 甲 9 4 6 8 5 \ 乙 8 5 9 10 6 丙 9 7 3 ' 5 8 丁 4 8 6 9 5 戊 10 ； 5 3 6 3 答案： 设原矩阵为A ，因求极大问题，令B=[M-a ij ]，其中M=Max {a ij }=10，则： 16425105 3140 42 13251042510424003B 1 3752102 64 10 154062415151 3045 020305 7470574704646111-?????? ? ? ? ? ? ? ? ? ? =→→- ? ? ?- ? ? ? ? ? ??????? --- m 4n 5l m 4 4 21342132432431541545235234 6 4 64 6 4 6=<===? ??? ? ??? ? ? ? ?→→????→?? ? ??? ? ? ? ???? ? ? ? 031023 4003115406020303535?? ? ? ? ? ? ?? ? 31234311546233 5 3 5? ?? ?? ? ?→ ?? ? ?? ? m=5=n ，得最优解。解矩阵*0001000100X 0000101 00010000?? ? ? ?= ? ? ??? 。

整数规划

整数规划

若某钻井队要从以下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,试选择该队员所应携带的物品。 序号 1 2 3 4 5 6 7 物品 食品 氧气 冰镐 绳索 帐篷 照相器材 通信设备 重量/Kg 5 5 2 6 12 2 4 重要性系数 20 15 18 14 8 4 10 解：引入0—1变量x i , x i =1表示应携带物品i ，,x i =0表示不应携带物品I ?? ?==≤++++++++++++=7 ,...,2,1,10254212625510481418152076543217654321i x x x x x x x x x x x x x x x naxz i 或 集合覆盖和布点问题 某市消防队布点问题。该市共有6个区，每个区都可以建消防站，市政府希望设置的消防站最少，但必须满足在城市任何地区发生火警时，消防车要在15min 内赶到现场。据实地测定，各区之间消防车行驶的时间见表，请制定一个布点最少的计划。 地区1 地区2 地区3 地区4 地区5 地区6 地区1 地区2 地区3 地区4 地区5 地区6 0 10 16 28 27 20 10 0 24 32 17 10 16 24 0 12 27 21 28 32 12 0 15 25 27 17 27 15 0 14 20 10 21 25 14 0

第5章-整数规划(割平面法)

割平面法 求解整数规划问题： Max Z=3x1+2x2 2x1+3x214 4x1+2x218 x1,x20，且为整数 解：首先，将原问题的数学模型标准化，这里标准化有两层含义：（1）将不等式转化为等式约束，（2）将整数规划中所有非整数系数全部转化为整数，以便于构造切割平面。从而有： Max Z=3x1+2x2 2x1+3x2+x3=14 2x1+x2+x4=9 x1,x20，且为整数 利用单纯形法求解，得到最优单纯形表，见表1： 表1 C B X B b 3 2 0 0

j 最优解为：x1=13/4, x2=5/2, Z=59/4 根据上表，写出非整数规划的约束方程，如：x2+1/2x3-1/2x4=5/2 (1) 将该方程中所有变量的系数及右端常数项均改写成“整数与非负真分数之和”的形式，即： (1+0)x2+(0+1/2)x3+(-1+1/2)x4=2+1/2 把整数及带有整数系数的变量移到方程左

边，分数及带有分数系数的变量称到方程右边，得： x2 - x4-2 =1/2-(1/2x3+1/2x4) (2) 由于原数学模型已经“标准化”，因此，在整数最优解中，x2和x4也必须取整数值，所以(2)式左端必为整数或零，因而其右端也必须是整数。又因为x3,x40，所以必有： 1/2-(1/2x3+1/2x4)<1 由于(2)式右端必为整数，于是有： 1/2-(1/2x3+1/2x4)0 (3) 或 x3+x4 1 (4) 这就是考虑整数约束的一个割平面约束方程，它是用非基变量表示的，如果用基变量来表示割平面约束方程，则有： 2x1+2x211 (5) 从图1中可以看出，(5)式所表示的割平面约束仅割去线性规划可行域中不包含整数可行解的部分区域，使点E，2)成为可行域的一个极点。

01型整数规划模型

§5.4 0—1型整数规划模型 1、 0—1型整数规划模型概述 整数规划指的是决策变量为非负整数值的一类线性规划，在实际问题的应用中，整数规划模型对应着大量的生产计划或活动安排等决策问题，整数规划的解法主要有分枝定界解法及割平面解法（这里不作介绍，感兴趣的读者可参考相关书籍）。在整数规划问题中，0—1型整数规划则是其中较为特殊的一类情况，它要求决策变量的取值仅为0或1，在实际问题的讨论中，0—1型整数规划模型也对应着大量的最优决策的活动与安排讨论，我们将列举一些模型范例，以说明这个事实。 0—1型整数规划的的数学模型为： 目标函数 n n x c x c x c z Min Max +++=ΛΛ2211)( 约束条件为： ???? ?? ?==≥≤++=≥≤++=≥≤++1 | 0 ) ,() ,() ,(2211222221211 1212111n m n mn m m n n n n x x x b x a x a x a b x a x a x a b x a x a x a , , ,2 1ΛΛΛΛΛΛΛΛΛΛΛΛ 这里，0 | 1表示0或1。 2、0—1型整数规划模型的解法 0—1型整数规划模型的解法一般为穷举法或隐枚举法，穷举法指的是对决策变量 n x x x , , ,21ΛΛ的每一个0或1值，均比较其目标函数值的大小，以从中 求出最优解。这种方法一般适用于决策变量个数n 较小的情况，当n 较大时，由于n 个0、1的可能组合数为n 2，故此时即便用计算机进行穷举来求最优解，也 几乎是不可能的。隐枚举法是增加了过滤条件的一类穷举法，该法虽能减少运算次数，但有的问题并不使用。此时，就只能用穷举法了。 3. 应用实例 例1 工程上马的决策问题

第五章 整数规划练习题答案

第五章 整数规划练习题答案 一. 判断下列说法是否正确 1. 用分枝定界法求解一个极大化的整数规划问题时，任何一个可行整数解的目标函数值是 该问题目标函数值的下界。() 2. 用割平面法求解整数规划时，构造的割平面有可能切去一些不属于最优解的整数解。() 3. 用割平面法求解纯整数规划时，要求包括松弛变量在内的全部变量必须取整数值。() 4. 指派问题数学模型的形式与运输问题十分相似，故也可以用表上作业法求解。() 二. 设有五项工作要分派给五个工人，每人的作业产值如下表所示，为了使总产值最大，问 应如何分配这五项工作，并求得最大产值。 工作 工人 A B C D E 甲 9 4 6 8 5 乙 8 5 9 10 6 丙 9 7 3 5 8 丁 4 8 6 9 5 戊 10 5 3 6 3 答案： 设原矩阵为A ，因求极大问题，令B=[M-a ij ]，其中M=Max {a ij }=10，则： 16425105 3140 42 13251042510424003B 1 3752102 6410 1540 62 415151 3045 020305 7470574704646111-?????? ? ? ? ? ? ? ? ? ? =→→- ? ? ?- ? ? ? ? ? ??????? --- m 4n 5l m 4 4 21342132432431541545235234 6 4 64 6 4 6=<===? ??? ? ??? ? ? ? ?→→????→?? ? ??? ? ? ? ???? ? ? ? 031023 4003115406020303535?? ? ? ? ? ? ???

第02章 整数规划

-16- 第二章 整数规划 §1 概论 1.1 定义 规划中的变量（部分或全部）限制为整数时，称为整数规划。若在线性规划模型中，变量限制为整数，则称为整数线性规划。目前所流行的求解整数规划的方法，往往只适用于整数线性规划。目前还没有一种方法能有效地求解一切整数规划。 1.2 整数规划的分类 如不加特殊说明，一般指整数线性规划。对于整数线性规划模型大致可分为两类： 1o 变量全限制为整数时，称纯（完全）整数规划。 2o 变量部分限制为整数的，称混合整数规划。 1.2 整数规划特点 （i ） 原线性规划有最优解，当自变量限制为整数后，其整数规划解出现下述情况： ①原线性规划最优解全是整数，则整数规划最优解与线性规划最优解一致。 ②整数规划无可行解。 例1 原线性规划为 21min x x z += 0,0, 5422121≥≥=+x x x x 其最优实数解为：4 5 min ,45,021===z x x 。 ③有可行解（当然就存在最优解），但最优解值变差。 例2 原线性规划为 21min x x z += 0,0, 6422121≥≥=+x x x x 其最优实数解为：2 3 min ,23,021===z x x 。 若限制整数得：2min ,1,121===z x x 。 （ii ） 整数规划最优解不能按照实数最优解简单取整而获得。 1.3 求解方法分类： （i ）分枝定界法—可求纯或混合整数线性规划。 （ii ）割平面法—可求纯或混合整数线性规划。 （iii ）隐枚举法—求解“0-1”整数规划： ①过滤隐枚举法； ②分枝隐枚举法。 （iv ）匈牙利法—解决指派问题（“0-1”规划特殊情形）。 （v ）蒙特卡洛法—求解各种类型规划。 下面将简要介绍常用的几种求解整数规划的方法。 §2 分枝定界法 对有约束条件的最优化问题（其可行解为有限数）的所有可行解空间恰当地进行系统搜索，这就是分枝与定界内容。通常，把全部可行解空间反复地分割为越来越小的子集，称为分枝；并且对每个子集内的解集计算一个目标下界（对于最小值问题），这称为定界。在每次分枝后，凡是界限超出已知可行解集目标值的那些子集不再进一步分枝，

第2章 整数规划

第二章 整数规划 §1 概论 1.1 定义 规划中的变量（部分或全部）限制为整数时，称为整数规划。若在线性规划模型中，变量限制为整数，则称为整数线性规划。目前所流行的求解整数规划的方法，往往只适用于整数线性规划。目前还没有一种方法能有效地求解一切整数规划。 1.2 整数规划的分类 如不加特殊说明，一般指整数线性规划。对于整数线性规划模型大致可分为两类： 1o 变量全限制为整数时，称纯（完全）整数规划。 2o 变量部分限制为整数的，称混合整数规划。 1.3 整数规划特点 （i ） 原线性规划有最优解，当自变量限制为整数后，其整数规划解出现下述情况： ①原线性规划最优解全是整数，则整数规划最优解与线性规划最优解一致。 ②整数规划无可行解。 例1 原线性规划为 21m i n x x z += 0,0, 5422121≥≥=+x x x x 其最优实数解为：4 5 min ,45,021===z x x 。 ③有可行解（当然就存在最优解），但最优解值变差。 例2 原线性规划为 21m i n x x z += 0,0, 6422121≥≥=+x x x x 其最优实数解为：2 3 min ,23,021===z x x 。 若限制整数得：2min ,1,121===z x x 。 （ii ） 整数规划最优解不能按照实数最优解简单取整而获得。 1.4 求解方法分类： （i ）分枝定界法—可求纯或混合整数线性规划。 （ii ）割平面法—可求纯或混合整数线性规划。 （iii ）隐枚举法—求解“0-1”整数规划： ①过滤隐枚举法； ②分枝隐枚举法。 （iv ）匈牙利法—解决指派问题（“0-1”规划特殊情形）。 （v ）蒙特卡洛法—求解各种类型规划。 下面将简要介绍常用的几种求解整数规划的方法。 §2 分枝定界法 对有约束条件的最优化问题（其可行解为有限数）的所有可行解空间恰当地进行系统搜索，这就是分枝与定界内容。通常，把全部可行解空间反复地分割为越来越小的子

第五章整数规划【模板】

第五章整数规划 §1整数规划的数学模型及特点 要求一部分或全部决策变量必须取整数值得规划问题称为整数规划。 其模型为： Max(或min)z= s.t 若要求决策变量只能取值0或1的整数规划称为0-1型整数线性规划。 §5 指派问题 一．指派问题的标准形式及数学模型 在现实生活中，有各种性质的指派问题。例如，有若干项工作需要分配给若干人（或部门）来完成；有若干项合同需要选择若干个投标者来承包；有若干班级需要安排在各教室上课等等。诸如此类的问题，它们的基本要求是在满足特定的指派要求条件下，使指派方案的总体效果最佳。由于指派问题的多样性，有必要定义指派问题的标准形式。 指派问题的标准形式（以人和事为例）是：有n个人和n件事，已知第i个人作第j件事的费用为，要求确定人和事之间的一一对应的指派方案，是完成这n件事的总费用最少。 为了建立标准指派问题的数学模型，引入个0-1变量： 这样，问题的数学模型可写成 （5.1） s.t （5.3） 其中，（5.1）表示每件事必优且只有一个人去做，（5.2）表示每个人必做且只做一件事。 注：○1指派问题是产量（）、销量（）相等，且==1，i，j=1,2,…n的运输问题。 ○2有时也称为第i个人完成第j件工作所需的资源数，称之为效率系数（或价值系数）。并称矩阵 C= =（5.5） 为效率矩阵（或价值系数矩阵）。 并称决策变量排成的n×n矩阵 X== （5.6） 为决策变量矩阵。 (5.6)的特征是它有n个1，其它都是0。这n个1位于不同行、不同列。每一种情况为指派问题的一个可行解。共n!个解。 其总的费用 z =C⊙X 这里的⊙表示两矩阵对应元素的积，然后相加。 问题是：把这n个1放到X的个位置的什么地方可使耗费的总资源最少？（解最优）例1已知效率矩阵 C= 则 X（1）=，X（2）= 都是指派问题的最优解 例12/P-149：某商业公司计划开办五家新商店。为了尽早建成营业，商业公司决定由

整数规划

第五章整数规划 一、填空题 1．用分枝定界法求极大化的整数规划问题时，任何一个可行解的目标函数值是该问题目标函数值的（）。 2．在分枝定界法中，若选Xr=4／3进行分支，则构造的约束条件应为（）。 3．已知整数规划问题P0，其相应的松驰问题记为P0’，若问题P0’无可行解，则问题P。（）。 4．在0 - 1整数规划中变量的取值可能是（）或（）。 5．对于一个有n项任务需要有n个人去完成的分配问题，其解中取值为1的变量数为（）个。 6．分枝定界法和割平面法的基础都是用（）求解整数规划。 7．若在对某整数规划问题的松驰问题进行求解时，得到最优单纯形表中，由X。所在行得X1+1／7x3+2／7x5=13／7，则以X1行为源行的割平面方程为（）。 8．在用割平面法求解整数规划问题时，要求全部变量必须都为（）。 9．用（）求解整数规划问题时，若某个约束条件中有不为整数的系数，则需在该约束两端扩大适当倍数，将全部系数化为整数。 10．求解纯整数规划的方法是割平面法。求解混合整数规划的方法是（）。 11．求解0—1整数规划的方法是隐枚举法。求解分配问题的专门方法是（）。 12．在应用匈牙利法求解分配问题时，最终求得的分配元应是（）。 13.分枝定界法一般每次分枝数量为（）个. 二、单选题 1．整数规划问题中，变量的取值可能是（）。 A．整数B．0或1C．大于零的非整数D．以上三种都可能 2．在下列整数规划问题中，分枝定界法和割平面法都可以采用的是A（）。 A．纯整数规划B．混合整数规划C．0—1规划D．线性规划 3．下列方法中用于求解分配问题的是（）。 A．单纯形表B．分枝定界法C．表上作业法D．匈牙利法 三、多项选择

第二章 整数规划

第二章 整数规划 §1 概论 1.1 定义 规划中的变量（部分或全部）限制为整数时，称为整数规划。若在线性规划模型中，变量限制为整数，则称为整数线性规划。目前所流行的求解整数规划的方法，往往只适用于整数线性规划。目前还没有一种方法能有效地求解一切整数规划。 1.2 整数规划的分类 如不加特殊说明，一般指整数线性规划。对于整数线性规划模型大致可分为两类： 1o 变量全限制为整数时，称纯（完全）整数规划。 2o 变量部分限制为整数的，称混合整数规划。 1.2 整数规划特点 （i ） 原线性规划有最优解，当自变量限制为整数后，其整数规划解出现下述情况： ①原线性规划最优解全是整数，则整数规划最优解与线性规划最优解一致。 ②整数规划无可行解。 例1 原线性规划为 21m in x x z += 0,0, 5422121≥≥=+x x x x 其最优实数解为：4 5 min ,45,021===z x x 。 ③有可行解（当然就存在最优解），但最优解值变差。 例2 原线性规划为 21m in x x z += 0,0, 6422121≥≥=+x x x x 其最优实数解为：2 3 min ,23,021===z x x 。 若限制整数得：2m in ,1,121===z x x 。 （ii ） 整数规划最优解不能按照实数最优解简单取整而获得。 1.3 求解方法分类： （i ）分枝定界法—可求纯或混合整数线性规划。 （ii ）割平面法—可求纯或混合整数线性规划。 （iii ）隐枚举法—求解“0-1”整数规划： ①过滤隐枚举法； ②分枝隐枚举法。 （iv ）匈牙利法—解决指派问题（“0-1”规划特殊情形）。 （v ）蒙特卡洛法—求解各种类型规划。 下面将简要介绍常用的几种求解整数规划的方法。 §2 分枝定界法 对有约束条件的最优化问题（其可行解为有限数）的所有可行解空间恰当地进行系统搜索，这就是分枝与定界内容。通常，把全部可行解空间反复地分割为越来越小的子集，称为分枝；并且对每个子集内的解集计算一个目标下界（对于最小值问题），这称为定界。在每次分枝后，凡是界限超出已知可行解集目标值的那些子集不再进一步分枝，

第二章整数规划

第二章整数规划 （部分或全部）限制为整数时，称为整数规划。若在线性规划模型中， 则称为整数线性规划。 目前所流行的求解整数规划的方法， 往往只适 目前还没有一种方法能有效地求解一切整数规划。 1.2 整数规划的分类 如不加特殊说明，一般指整数线性规划。对于整数线性规划模型大致可分为两类: 1。 变量全限制为整数时，称纯（完全）整数规划。 2。 变量部分限制为整数的，称混合整数规划。 1.2整数规划特点 （i ）原线性规划 有最优解， ① 原线性规划最优解全是整数， ② 整数规划无可行解。 例1原线性规划为 min § 2分枝定界法 对有约束条件的最优化问题（其可行解为有限数）的所有可行解空间恰当地进行系 统搜索，这就是分枝与定界内容。通常，把全部可行解空间反复地分割为越来越小的子 集，称为分枝；并且对每个子集内的解集计算一个目标下界（对于最小值问题） ，这称 为定界。在每次分枝后，凡是界限超出已知可行解集目标值的那些子集不再进一步分枝， §1概论 1.1定义 规划中的变量 变量限制为整数， 用于整数 线性规划。 当自变量限制为整数后， 其整数规划解出现下述情况: 则整数规划最优解与线性规划最优解一致。 4X 2 5, X 1 c 5 . X 1 0,x 2 -,mi nz 4 ③有可行解（当然就存在最优解） 例2原线性规划为 min 2X 2x i 其最优实数解为: 0, X 2 0 5 O 4 ，但最优解值变差。 其最优实数解为: X 1 X i 6, X 2 0,X 2 X i 0, 3 . —,mi X 2 3 O 2 2 若限制整数得： （ii ）整数规划最优解不能按照实数最优解简单取整而获得。 1. 3 求解 方法分类： （i ）分枝定界法一可求纯或混合整数线性规划。 （ii ） 割平面法一可求纯或混合整数线性规划。 （iii ） 隐枚举法一求解“ 0-1 ”整数规划： ① 过滤隐枚举法； ② 分枝隐枚举法。 （iv ） 匈牙利法一解决指派问题（“ 0-1 ”规划特殊情形）。 （V ）蒙特卡洛法一求解各种类型规划。 下面将简要介绍常用的几种求解整数规划的方法。 X i 1,X 2 1,min z z X-I X 2

第二章 整数规划

第二章 整数规划 一、 整数规划模型介绍 规划中的变量（部分或全部）限制为整数时，称为整数规划。若在线性规划模型中，变量限制为整数，则称为整数线性规划。对于整数线性规划模型大致可分为三类： （1）变量全限制为整数时，称纯（完全）整数线性规划。 （2）变量部分限制为整数的，称混合整数线性规划。 （3）变量只能取0或1时，称之为0-1线性规划。 整数线性规划特点 （i ） 原线性规划有最优解，当自变量限制为整数后，其整数规划解会出现下述情况： （1）原线性规划最优解全是整数，则整数线性规划最优解与线性规划最优解一致。 （2）整数线性规划无可行解。 （3）有可行解（当然就存在最优解），但最优解值一定不会优于原线性规划的最优值。 （ii ） 整数规划最优解不能按照实数最优解简单取整而获得。 二、整数规划的求解法之一（分枝定界法） 2.1 分枝定界法的思想 对有约束条件的最优化问题（其可行解为有限数）的可行解空间恰当地进行系统搜索，这就是分枝与定界内容。通常，把全部可行解空间反复地分割为越来越小的子集，称为分枝；并且对每个子集内的解集计算一个目标上(下)界（对于最大(小)值问题），这称为定界。在每次分枝后，凡是界限不优于已知可行解集目标值的那些子集不再进一步分枝，这样，许多子集可不予考虑，这称剪枝。这就是分枝定界法的主要思路。现用下例来说明： 例1 求解下述整数规划 219040Max x x z += s.t. ??? ??≥≥+≤+且为整数0,7020756 792 12121x x x x x x (2.1) 解 （i ）先不考虑整数限制，即作为一般线性规划问题求解，得最优解为： 355.8779,8168.1,8092.421===z x x

0-1整数规划

5.4 0—1型整数规划模型 1. 0—1型整数规划模型概述 整数规划指的是决策变量为非负整数值的一类线性规划，在实际问题的应用中，整数规划模型对应着大量的生产计划或活动安排等决策问题，整数规划的解法主要有分枝定界解法及割平面解法（这里不作介绍，感兴趣的读者可参考相关书籍）。在整数规划问题中，0—1型整数规划则是其中较为特殊的一类情况，它要求决策变量的取值仅为0或1，在实际问题的讨论中，0—1型整数规划模型也对应着大量的最优决策的活动与安排讨论，我们将列举一些模型范例，以说明这个事实。 0—1型整数规划的的数学模型为： 目标函数 n n x c x c x c z Min Max +++= 2211)( 约束条件为：???? ?? ?==≥≤++=≥≤++=≥≤++1 | 0 ) ,() ,() ,(22112222212111212111n m n mn m m n n n n x x x b x a x a x a b x a x a x a b x a x a x a , , ,21 这里，0 | 1表示0或1。 2. 0—1型整数规划模型的解法 0—1型整数规划模型的解法一般为穷举法或隐枚举法，穷举法指的是对决策变量n x x x , , ,21 的每一个0或1值，均比较其目标函数值的大小，以从中求出最优解。这种方法一般适用于决策变量个数n 较小的情况，当n 较大时，由于n 个0、1的可能组合数为n 2，故此时即便用计算机进行穷举来求最优解，也几乎是不可能的。隐枚举法是增加了过滤条件的一类穷举法，该法虽能减少运算次数，但有的问题并不使用。此时，就只能用穷举法了。 3. 应用实例 例1 工程上马的决策问题 1）问题的提出 某部门三年内有四项工程可以考虑上马，每项工程的期望收益和年度费用（千元）如下表所示：假定每一项已选定的工程要在三年内完成，是确定应该上马哪些工程，方能使该部门可能的期望收益最大。

整数规划

若某钻井队要从以下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,试选择该队员所应携带的物品。 序号 1 2 3 4 5 6 7 物品 食品 氧气 冰镐 绳索 帐篷 照相器材 通信设备 重量/Kg 5 5 2 6 12 2 4 重要性系数 20 15 18 14 8 4 10 解：引入0—1变量x i , x i =1表示应携带物品i ，,x i =0表示不应携带物品I ?? ?==≤++++++++++++=7 ,...,2,1,10254212625510481418152076543217654321i x x x x x x x x x x x x x x x naxz i 或 集合覆盖和布点问题 某市消防队布点问题。该市共有6个区，每个区都可以建消防站，市政府希望设置的消防站最少，但必须满足在城市任何地区发生火警时，消防车要在15min 内赶到现场。据实地测定，各区之间消防车行驶的时间见表，请制定一个布点最少的计划。 地区1 地区2 地区3 地区4 地区5 地区6 地区1 地区2 地区3 地区4 地区5 地区6 0 10 16 28 27 20 10 0 24 32 17 10 16 24 0 12 27 21 28 32 12 0 15 25 27 17 27 15 0 14 20 10 21 25 14 0

第二章整数规划

第二章整数规划 §1 概论 1.1定义 规划中的变量（部分或全部）限制为整数时，称为整数规划。若在线性规划模型中，变量限制为整数，则称为整数线性规划。目前所流行的求解整数规划的方法，往往只适用于整数线性规划。目前还没有一种方法能有效地求解一切整数规划。 1.2 整数规划的分类 如不加特殊说明，一般指整数线性规划。对于整数线性规划模型大致可分为两类： 1。变量全限制为整数时，称纯（完全）整数规划。 2。变量部分限制为整数的，称混合整数规划。 1.2整数规划特点 （i）原线性规划有最优解，当自变量限制为整数后，其整数规划解出现下述情况： ①原线性规划最优解全是整数，则整数规划最优解与线性规划最优解一致。 ②整数规划无可行解。 例1原线性规划为 min z x-i x2 2x1 4X25, x10, x20 5 5 其最优实数解为：X1 0,X2,mi nz 4 4 ③有可行解（当然就存在最优解），但最优解值变差。 例2原线性规划为 min z X-I X2 2X14X26, X1 0, X2 0 其最优实数解为：X1 0,X2 - ,min z 3 。 2 2 若限制整数得：X1 1,X21,min z2。 （ii）整数规划最优解不能按照实数最优解简单取整而获得。 1.3求解方法分类： （i ）分枝定界法一可求纯或混合整数线性规划。 （ii）割平面法一可求纯或混合整数线性规划。 （iii）隐枚举法一求解“ 0-1 ”整数规划： ①过滤隐枚举法； ②分枝隐枚举法。 （iv）匈牙利法一解决指派问题（“ 0-1 ”规划特殊情形）v）蒙特卡洛法一求解各种类型规 划。 下面将简要介绍常用的几种求解整数规划的方法。 § 2分枝定界法 对有约束条件的最优化问题（其可行解为有限数）的所有可行解空间恰当地进行系统搜索，这就是分枝与定界内容。通常，把全部可行解空间反复地分割为越来越小的子集，称为分枝；并且对每个子集内的解集计算一个目标下界（对于最小值问题），这称为定界。在每次分枝后，凡是界限超出已知可行解集目标值的那些子集不再进一步分枝，

整数规划习题

第五章 整数规划习题 5.1 考虑下列数学模型 )()(m in 2211x f x f z += 且满足约束条件 （1）或101≥x ，或102≥x ； （2）下列各不等式至少有一个成立： ??? ??≥+≥+≥+15 215152212121x 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 如如 将此问题归结为混合整数规划的模型。 解：2211612510m in 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 -+=

?? ?==≤++-） ，（或3,2,110332321j x x x x j 解：令=y ???==否则，当,01132x x 故有y x x =32，又21x ，3 1x 分别与1x ，3x 等价，因此题中模型可转换为 31m ax x y x z -+= ? ???? ?? ??-+≤+≤≤≤++-变量均为10,,,1 3 323213 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 1max ??? ?? ?????????????==≥+≤+≤≤∑∑==否则 仪器安装,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