第5 章整数规划 本章内容要点 .整数规划相关概念; .整数规划问题的一般特点; .分支定界法求解过程; .割平面法求解过程; .0-1规划的求解方法; .指派问题法求解过程。 本章核心概念 整数规划(g); . integerprogrammin .分支定界方法(branchandboundalgorithmmethod); .割平面方法(cutingplanemethod); .匈牙利方法(Hungarianmethod); .0-1规划(0-1programming); .指派问题(asignmentproblem )。 ■ 案例 经济管理当中经常存在人员指派问题,企业中有4个人可以胜任4项不同工作的任意 一项,但是完成工作的效率有所不同,如表5-1所示。 表5- 1 案例工作时间表 任务甲乙丙丁 A B C D 10 15 15 20 12 10 15 15 13 15 14 13 15 22 17 16 为了使得企业获得最好的经济效益,应该如何指派这4个人完成4项不同工作? 用单纯形法求解线性规划问题,其最优解往往是分数或小数。但对于某些实际问题,常要 求全部或部分变量的最优解必须是整数。例如,所求的解是人数,机器台数或工厂个数等;又 如决策某个方案的取与舍,电路的连通与切断,逻辑运算中涉及的是与非等;再如某种机器有 限种运行方式的选择,人员配备的若干组合方案的选取等。这些涉及用整数值来作为取值范 围,由于它们的求解过程中的特殊性而构成数学规划的一个分支,称之为整数规划。 在一个线性规划问题中,若要求全部变量取整数值,称为纯整数规划问题。若要求部分 变量取整数值,称为混合整数规划问题。有一类整数规划问题,其决策变量只取0或1值, ·99· 由于计算上的特殊性,称之为0-1规划。 整数规划具有广泛的应用领域,如管理决策、人员组织、生产调度、区域布局、资本预算、 资源规划等。在工程和科学计算方面,计算机设计、系统可靠性、编码系统设计等也都提出 不少整数规划的问题。 本章介绍整数规划建模中常使用的一些处理方法及最基本的整数规划解法。在最后一 节,将介绍一个特殊的整数规划问题———指派问题的解法。 5.1 整数规划问题的提出 5.1.1 问题特征 整数规划问题的一个明显特征是它的变量是离散的,因而在经典连续数学中的理论和 基本方法一般无法直接用于求解整数规划问题。 求解整数规划问题,初看起来好像很简单,比如把带有分数或小数的解进行“收尾”或 “去尾”处理就可以了。事实上,这样处理有时行得通,有时却行不通。例如,某公司根据市 场需要,用线性规划的方法得到一个方案是增加甲产品的工厂3.7个,乙产品的工厂1.5个。 如果用凑整方法求其解,则有4个近似方案:(4,1)、(4,2)、(3,1)、(3,2),显然,这4个方案 之间差别很大。对原线性规划问题来说,它们有的是可行解,有的则不是可行解;或虽是可 行解,但不一定是最优解。因此,对求最优整数解的问题,有必要另行研究。 5.1.2 整数规划建模中常用的处理方法 对于整数规划问题,除考虑到它的某些或全部决策变量有整数限制外,没有特殊的建模 难点。比较特殊的是0-1变量的使用,它可以把一些不易用数学公式表示的条件,处理成易 于表达的数学式。下面介绍一个关于投资问题的数学规划背景及几个0-1变量设置问题。 1.资本预算问题 决策者要对若干潜在的投资方案作出选择,决定是取还是舍。 设共有n 个投资方案,cj(j=1,2,…,n)为第j 个投资方案的投资收益,整个投资过程 共分为m 个阶段,bi 为第i 阶段的投资总量,aij为第i 阶段第j 项投资方案所需要的资金。 目标是在各阶段资金限制下使整个投资的总收益最大。 这类问题是典型的决策问题。设决策变量xj 为对第j 个方案的取(xj =1)或舍(xj = 0),可得到下列整数规划问题(0-1规划)。 maxS =Σn j=1 cjxj Σn j=1 aijxj ≤bi,i=1,2,…,m xj =0或1, j=1,2,…,n ì . í .. .. (5-1) ·100· 式(5-1)的约束Σn j=1 aijxj ≤bi(i=1,2,…,m )反映了第i 个时期资金增长量的平衡。 这里aij代表第i 时期内第j 项投资的净资金流量: ①aij>0,表示需附加资金; ②aij<0,表示该项投资在第i 时期内产生资金。 右端项bi 表示第i 时期外源资金流量的增长量: ①bi>0,表示有附加资金的数量; ②bi<0,表示要抽回资金的数量。 2.指示变量 指示变量常用于指示不同情况的出现。例如,某产品生产涉及两类成本:一类为产品 的边际成本费用c1,即再生产一个单位的产品需有c1 费用的投入;另一类为固定成本费用 c2,如装配线的固定投资等,它与生产产品的数量无关,只要生产就必须全数投入。设x 为 产品数量,c 为总成本费用,于是成本费用如下: 当x=0时,c=0; 当x>0时,c=c1x+c2。 显然,变成了一个非线性的分段函数,为了便于计算,可以引入指标变量y,即 y = 0, x >0 1, x =0 { 于是得到线形函数c=c1x+c2y。 例5.1 仓库位置问题:有m 个仓库,经营者需要决定动用哪些仓库才能满足n 个客 户的需求,还要进一步决定从各仓库分别向不同客户运送货物的数量,使总的费用最少。 设fi 表示动用仓库i 的固定运营费,cij表示从仓库i 到客户j 运送单位货物量的费用 (i=1,2,…,m ;j=1,2,…,n)。设置变量xij 为从仓库i 向客户j 运送货物的数量,指示 变量 yi = 1, 表示动用仓库i 0, 表示不动用仓库i { 规定约束条件: (1)每个客户对货物的需求量dj,必须从各动用仓库中得到满足。 (2)不动用的仓库不能对任何客户供货。 这里,第(2)个约束的处理可用下面的不等式: Σn j=1 xij ≤yiMi 其中,Mi 为可能从仓库i 中取出货物的上限数,一个较简单的取法为 Mi =Σn j=1 dj, i=1,2,…,m 可以看出,当yi=0时,即不动用仓库i,xij≤0,j=1,2,…,n,又由于xij≥0,故这时从 第i 个仓库到第j 个客户的运量必有xij=0;当yi=1时,即动用仓库i,运量不会在这里受 ·101· 到限制。 根据上述分析,容易得到下列数学模型: minΣm i=1Σn j=1 cijxij + Σm i=1 fiyi Σm i=1 xij =dj, j=1,2,…,n Σn j=1 xij -yiΣn j=1 dj ≤0,i=1,2,…,m xij ≥0, i=1,2,…,m ,j=1,2,…,n yi =0或1, i=1,2,…,m ì . í .... .... 3.线性规划模型的附加条件 在许多实际问题中,线性规划模型中的约束条件允许一定范围的放宽或对个别因素有 进一步限制时,常可通过引入0-1变量来处理。下面分3种情况介绍建模思路。 (1)不同时成立的约束条件。设某个模型问题中的约束条件不必同时成立,有m 个线 性不等式约束: Σn j=1 aijxj ≤bi, i=1,2,…,m (5-2) 对每个约束进入一个指示变量yi,并得到每个约束左端的一个上界Mi(i=1,2,…,n),建 立下列不等式: Σn j=1 aijxj +Miyi ≤bi +Mi, i=1,2,…,m (5-3) 显然,当yi=1时,式(5-2)与式(5-3)等价;当yi=0时,式(5-3)是恒成立,相当于除去了这 个限制。 在实际问题中,如果至少有k 个约束成立时,只需附加下列约束: Σm i=1 yi ≥k (2)最优解中非零分量个数的限制。在许多实际问题中,对最优解中的非零分量个数 有所限制。类似上述分析可对每个决策变量xi 找到其上界Mi,并引入指示变量yi。附加 式(5-4)为 xi -Miyi ≤0, i=1,2,…,n (5-4) Σm i=1 yi ≤k (5-5) 可以看出,式(5-4)等价于 xi >0.yi =1 xi =0.yi =0 式(5-5)说明,非零分量至多有k 个。 (3)离散的资源变化。实际问题中常出现下列情况:不等式约束: ·102· Σn j=1 ajxj ≤bi, i=1,2,…,k (5-6) 表示右端的值可以有k 个等级的违背,而b0