第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 分枝定界法

对有约束条件的最优化问题（其可行解为有限数）的所有可行解空间恰当地进行系统搜索，这就是分枝与定界内容。通常，把全部可行解空间反复地分割为越来越小的子

集，称为分枝；并且对每个子集内的解集计算一个目标下界（对于最小值问题），这称为定界。在每次分枝后，凡是界限超出已知可行解集目标值的那些子集不再进一步分枝，这样，许多子集可不予考虑，这称剪枝。这就是分枝定界法的主要思路。

分枝定界法可用于解纯整数或混合的整数规划问题。在本世纪六十年代初由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

1

Max

?????

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

11

2

765

43217

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 可改写为

??

?=≤≤1

08005001或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） 于是目标函数

)()()(min 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 321523M a x x x x z +-=

?????

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

0,,6

4344223213

221321321或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 已知非线性整数规划为：

543212

5

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

?????

????≤++≤++≤++++≤++++=≤≤200

5200

62800622400)5,,1(9905433

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

10510)100(=个点，其计算量非常之大。然而应用蒙特卡洛去随机计算610个点，便可

找到满意解，那么这种方法的可信度究竟怎样呢？

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

10个点计算时，应用概率理论来估计一下可信度。

不失一般性，假定一个整数规划的最优点不是孤立的奇点。

10个点后，有假设目标函数落在高值区的概率分别为0.01，0.00001，则当计算6

任一个点能落在高值区的概率分别为

99

.0

11000000

.0

(

100

99

99

多位）

-，

≈

11000000≈

-。

.0

99999

.0

999954602

解（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编程实现分枝定界解法和割平面解法。但对

0-整数规划问题或约束矩阵A是幺模矩阵时，有时可以直接利于指派问题等特殊的1

用Matlab的函数linprog。

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

???????

????

??

???109

6

10

9532485724

679278310

283 解：编写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-规划问题 3211max x x x x z -+=

??

?==≤++-)3,2,1(103

32321j 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 中最多只能选两个；试建立这个问题的整数规划模型。

第五章整数规划

第五章 整数规划 主要内容：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, ① ② ③ ④ ⑤

第二章 人力资源规划答案

第二章计划 一、名词解释 1、人力资源规划 是根据组织的战略目标，科学预测组织在未来环境变化中的人力资源供给与需求状况，制定必要的人力资源获取、利用、保持和开发策略，确保组织在数量上和质量上的需求，使组织和个人获得长远利益。 2、德尔菲法 是获得专家对影响组织发展的某一问题的一致意见的程序化方法。 一、选择题 1. A 2B 3. C 4. B 5．A 6 B 7 D 二、判断题 1.错误。劳动力构成的重大转变要求管理人员更多地关注人力资源计划，因为这些变化不仅影响员工的招募，而且影响员工选拔、训练、薪酬、激励的方法。 2.错误。在平衡人力资源供给和需求的过程中，不可能是单一的供不应求或者供大于求，企业人力资源还常常出现结构失衡。 3.错误。人力资源计划过程的三个步骤：评价现有的人力资源；预估将来需要的人力资源；制定满足未来人力资源需要的行动方案。 4.正确5．正确。6．正确。 7．错误。人力资源计划的主要内容即预测组织未来人力资源的供需状况，以及考虑这两者之间的匹配 8. 错，不是当前是长久 三、简答题 1. 简述对组织外部人力资源供给进行预测的时候，考虑的主要影响因素有哪些？ 对组织外部人力资源供应进行预测的时候，考虑的主要影响因素有：（1）影响组织外部人力资源供给的全国乃至全球性因素，（2）影响组织外部人力资源供给的地区性因素；（3）政府的方针、政策和法规；（4）劳动力市场发育状况；（5）人口发展趋势；（6）科学技术的发展；（7）劳动力就业意识和择业心理；（8）外部人力资源供给渠道；（9）工会。 2. 组织人力资源需求大于供给时有哪些平衡方法？各种方法分别有什么利弊？

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

第五章整数规划 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。不考虑整数约束条件求解这两个后继问题。 定界，以每个后继问题为一分支标明求解的结果。 第一步：先不考虑整数约束，变成一般的线性规划问题，用图解法或单纯形法求其最优解，记为 ) ； 第二步：若求得的最优解，刚好就是整数解，则该整数就是原整数规划的最优解，否则转下步； 第三步：对原问题进行分支寻求整数最优解。 第四步：对上面两个子问题按照线性规划方法求最优解。若某个子问题的解是整数解，则停止该子问题的分支，并且把它的目标值与上一步求出的最优整数解相比较以决定取舍；否则，对该子问题继续进行分支。

第2章 人力资源规划

第2章人力资源规划 学习目标 通过本章学习，我们需要达到以下目标： 1．了解企业战略的基本形态及战略的层次 2．掌握人力资源战略的定义及分类 3．掌握人力资源战略实施流程 4．熟悉人力资源规划的内容和程序 5．掌握人力资源供给与需求预测方法 2.1 企业战略 2.1.1 战略的定义及在企业的延伸 在现代，“战略”一词被引申至政治和经济领域，其涵义演变为泛指统领性的、全局性的、左右胜败的谋略、方案和对策。 2.1.2 企业战略形态 1．拓展型战略 （1）市场渗透战略 （2）多元化经营战略 （3）联合经营战略 2．稳健型战略 3．收缩型战略 2.1.3企业战略特征及层次 1．企业战略的特征 企业战略是设立远景目标并对实现目标的轨迹进行的总体性、指导性谋划，属宏观管理范畴，具有指导性、全局性、长远性、竞争性、系统性、风险性六大主要特征。 2．企业战略的层次

2.2 人力资源战略 2.2.1人力资源战略及其定义 人力资源战略可以定义为：适应企业内外部环境的、基于提升人力资源核心竞争力的、企业人力资源管理的策略和规划。 2.2.2 人力资源战略的分类 1．按照企业对员工本身的基本假设 2．根据企业变革的程度分类 3．根据对企业对人力资源发展对企业贡献的时间长短分类 4．根据人力资源获取、发展及维护的方式分类 2.2.3 人力资源战略的实施 人力资源战略的实施步骤如图2.1所示。 图2.1 人力资源战略的实施步骤 2.3 人力资源规划 2.3.1人力资源规划的含义 所谓人力资源规划（Human Resource Planning, HRP）是指企业从战略规划和发展目标出发，根据其内外部环境的变化，预测企业未来发展对人力资源的需求，以及为满足这种需求提供人力资源的活动过程。

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

第五章 整数规划练习题答案 一. 判断下列说法是否正确 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?? ? ? ?= ? ? ??? 。

第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)成为可行域的一个极点。

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

第五章 整数规划练习题答案 一. 判断下列说法是否正确 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、掌握人力需求预与供应预测的方法； 2、掌握人力资源计划的制定。 难点： 掌握人力资源计划的制定。 ★教学手段： 借助多媒体。 ★教学方法： 面授，启发讨论式，小组探究。 ★教学过程： 复习导入（略） 讲授新课 第一节人力资源计划概述 一、什么是人力资源计划 人力资源计划（HRP）是指为了达到企业的战略目标与战术目标，根据企业目前的人力资源状况，为了满足未来一段时间内企业的人力资源质量和数量方面的需要，决定引进、保持、提高、流出人力资源的所作的预测和相关事项。 （一）人力资源计划的类型 1、人事计划 2、人力资源计划 3、战略人力资源计划 4、战术人力资源计划 （二）谁负责制定人力资源计划 制定人力资源计划涉及：高层管理人员、人力资源部人员、其他职能部门管理人员以及相关管理专家。 （三）何时制定人力资源计划 时间并不固定，一般三年修改一次。 二、人力资源计划的模型 （一）人力资源计划的内容模型 人力资源计划内容： ?职位晋升 ?补充人员 ?培训开发 ?职业规划

（二）人力资源计划的步骤模型

三、人力资源计划的意义及其影响因素 （一）人力资源计划的意义 1、在人力资源方面确保实施企业的目标； 2、具体规定了在人力资源方面需要做哪些事项； 3、对企业需要的人力资源作适当的储备； 4、对企业紧缺的人力资源发出引进与培训的预警； 5、使管理层与员工对要达到的人力资源开发与管理的目标更加清晰。 （二）影响人力资源计划的因素 １．宏观经济剧变； ２．企业管理层更变； ３．政府的政策法规——劳动合同法； ４．技术创新换代——护理专业、轨道交通专业； ５．企业的经营状况； ６．企业的人力资源部门人员的素质。 第二节人力资源需求与供应的预测一、人力资源需求预测 经验预测法 德尔非法（专家法） （一）总体需求结构分析预测法 NHR＝P＋C－T （二）人力资源成本分析预测法 （三）人力资源发展趋势分析预测法 NHR＝a·[1＋（b%－c%）·T] （四）人力资源学习曲线分析预测法 １．生产率预测法 ２．进步指数预测法 见书P23图表

第五章整数规划【模板】

第五章整数规划 §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

整数规划

若某钻井队要从以下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