油气储运最优化第4章-线性整数规划

1、第四章 线性整数规划,Liner Integer Programming,4.1 线性整数规划的概念,一、什么是线性整数规划 在一些实际问题的数学规划模型中，往往要求某些变量必须取整数值，例如人数、设备台数、零部件个数、泵站数、活动次数等，这类问题称为整数规划问题。如果问题中的变量都要求取整数值，则称之为纯整数规划问题；如果只要求一部分变量取整数值，则称之为混合整数规划问题。 对应于连续变量的线性规划和非线性规划，整数规划又可分为线性整数规划和非线性整数规划。这一章仅介绍线性整数规划。,线性整数规划的概念,二、线性整数规划的数学模型 在线性规划模型：,中，若增加自变量取整数约束条件，则可得到线

2、性整数规划的数学模型：,线性整数规划的概念,例：用集装箱装运甲、乙两种货物，每种货物每包的体积、重量和收益见下表。集装箱体积为24m3，允许的最大重量13吨，问每个集装箱应装两种货物各多少包才能使收益最大?,线性整数规划的概念,解：设xl、x2为甲、乙两种货物的装箱包数，则其数学模型为：,这个问题怎么求解呢？大家很自然地会想到从线性规划出发。将上述模型中的整数约束去掉，得到原问题的松弛问题：,线性整数规划的概念,该松弛问题的最优解为x1*4.8，x2*0，S*9600元。,一般来说，原问题的最优解总在其松弛问题的最优解附近，其最优解为：x1*4，x2*1，S*9000元。,由此可见，由于原问题

3、比松弛问题多了整数约束，缩小了可行域的范围，因此其目标函数的最优值总是不优于其松弛问题的最优值，这是一个重要的基本规律。,由于对变量的整数约束限制了通常的连续型方法的应用，因此，人们在刚接触整数规划问题时，往往会产生两种原始的求解设想： 因为纯整数规划的可行解是有限的，因此，可采用一一比较的方法(穷举法)找出最优解； 先不考虑整数约束，解相应的连续型问题(松弛问题)，然后用“四舍五入”的办法凑得一个较好的整数解作为最优解。 这两种设想往往是行不通的。穷举法效率太低，只有当可行解较少时才能行得通，当可行解很多时，需要花很长的时间。凑整法不一定能得到问题的最优解。,三、整数规划的解法概述,线性整数

4、规划的概念,因此，解整数规划问题比解相应的松弛问题要困难得多。目前整数规划是数学规划中较弱的一个分支，即使对线性整数规划也没有找到一种象线性规划单纯形法那样有效的通用算法。目前求解线性整数规划的方法有：分枝定界法、隐枚举法和割平面法。,4.2 分枝定界法,一、基本思想 1、几个术语 分枝：将原问题分成几个无整数约束的子问题； 定界：每一个子问题可以给原问题划出一个边界； 探测：判断子问题的可行解是否包含原问题的最优解。 2、基本思路 按某种原则将原问题分成若干个子问题，相应地原问题的可行解集合分解为若干个互不相交的子集，然后分别在各个子集中探寻原问题的最优解。当所有子集都己探寻过以后，获得的具

5、有最好目标函数值的子问题的最优解即为原问题的最优解。,分枝定界法,3、线性整数规划解的特点 原问题的最优解不会优于松弛问题的最优解； 若松弛问题的最优解满足原问题的整数约束，则它是原问题的最优解,二、解法步骤 首先以一个例子说明分枝定界法的解题步骤。,分枝定界法,例：,解：解原问题的松弛问题P0：,分枝定界法,可用图解法求解。最优解为xl=4.809，x2=1.817，S=355.89,将P0分解为两个子问题Pl和P2(分枝),根据松弛问题的最优解可以确定原问题的目标函数值的上界为 =355.89或 =355，下界为 =0（由于目标函数的系数均为整数且大于0）。,分枝定界法,Pl的最优解为x1

6、=4，x2=2.1，S=349，则P1的目标函数上界为： =349。,P2的最优解为x1=5，x2=1.571，S341，,分枝定界法,因P1、P2未得到整数解，故应继续分枝。,将P1分解为两个子问题P3和P4,P3和P4的数学模型为：,分枝定界法,P4的最优解为x1=1.428，x2=3，S327.12，,P3的最优解为x1=4，x2=2，S=340，因已得到一个整数解，即原问题的一个可行解，故原问题目标函数下界为：S=340。,分枝定界法,而P3的解已为整数解，故P3、P4两个分枝都已“查明”了。,将P2分解为两个子问题P5和P6,分枝定界法,P5和P6的数学模型为：,分枝定界法,P6无可

7、行解， P6已“查明”。,P5的最优解为x1=5.444，x2=1，S=307.76， =307。,分枝定界法,分枝定界法求解整数规划的一般步骤(对max问题)： 1、求解原问题P的松弛问题P0,若P0的最优解满足原问题的整数条件，则该最优解就是原问题的最优解，计算结束。,2、分枝：设要分枝的问题为A，在A的最优解中任选一个不满足整数约束的变量xjbj作为分枝变量，将A分解为两个子问题B1和B2：,bj为bj的整数部分的值。,分枝定界法,3、分别求解子问题B1和B2。设所求解的子问题为B，根据求解结果，有三种可能情况： B无可行解，此时B已查明，应剪枝; 有满足原问题整数条件的最优解。如果SB

8、*S，令 S=SB*，转4。如果SB*S，此时B已查明，应剪枝；,B的解不满足原问题的整数约束。若 S ，则B已 查明应剪枝，转4；若 S ，转4。,分枝定界法,分枝时，一般首先选择上界最大的子问题进行分枝，这样可以加快解题的速度，减少计算步骤。,4.3 0-1线性规划的隐枚举法及应用,一、什么是0-1线性规划 自变量的取值只能取0和1两个值的线性规划称为0-1线性规划。这是一类特殊的整数规划问题,在绝大多数情况下，0-1变量为逻辑变量。,例1加油站的布局问题 某市有如下地点可建加油站： 东区： 3个点A1、A2、A3，最多建2个； 南区： 2个点A4、A5，至少建1个； 西区： 2个点A6、

9、A7，至少建1个。,0-1线性规划的隐枚举法及其应用,设总投资为B万元，各点建站的投资为bi(i=17)万元，各点的利润为ci(i=17) 万元，应在各区建多少个加油站使总利润最大?,该问题属于0-1规划问题，0-1变量xj为逻辑变量。,0-1线性规划的隐枚举法及其应用,例2油井与计量站间管网的最优布局问题,该问题既是一个产大于销的运输问题，又是一个0-1线性规划问题。,这个问题在运输问题的应用一节中已经讲过，其数学模型为：,0-1线性规划的隐枚举法及其应用,有n项任务，指派n个人分别去完成。n项任务分别是A1、A2、An , n个人分别为B1、B2、Bn，每个人完成每项任务的效率不同，问应如

10、何指派任务才能使总效率最高?,解：设Bi人完成Aj任务所需的工时为cij，S为完成n项任务所需的总工时，引入0-1变量：,例3指派问题,0-1线性规划的隐枚举法及其应用,则该问题的数学模型为：,由数学模型知，它既是一个产销平衡的运输问题，又是一个特殊的0-1线性规划问题。,0-1线性规划的隐枚举法及其应用,某泵站有m台离心泵串联工作，假定该泵站与管路匹配的工作点为(Q, H)，根据泵特性知，当泵的排量为Q时，提供的扬程及配套电机功率分别为Hj、cj，j=1m。试确定应由哪几台泵串联运行才能既满足匹配要求又使总功率最小?,解：引入0-1变量：,例4泵站内最优泵组合问题：,0-1线性规划的隐枚举法

11、及其应用,则该问题的数学模型为：,0-1线性规划的隐枚举法及其应用,为了采用一种通用的系统化算法求解0-1线性规划问题，首先需要把这类问题统一成标准形式。0-1线性规划的标准型为：,二、0-1线性规划的标准型,0-1线性规划的隐枚举法及其应用,通过下列转换，可把任何一个0-1线性规划问题化为标准型：,0-1线性规划的隐枚举法及其应用,0-1线性规划的隐枚举法及其应用,思考题：为什么不能将其转化为2k个不等式约束？,(如果转化为2k个不等式约束，将有k-1个约束条件线性相关),三、0-1线性规划的隐枚举法,隐枚举法是组合最优化中一大类方法的总称，它是相对于穷举法(完全枚举法)而言的，其基本特征是

12、只需要考察问题中自变量的一部分组合就可以得到最优解。因而这种方法又称为部分枚举法。 本节只介绍一种求解0-1线性规划的隐枚举法。,0-1线性规划的隐枚举法及其应用,(一）基本概念 为了便于介绍和理解隐枚举法，首先介绍一下隐枚举法的基本概念。,1、枚举：即检查问题中自变量值组合是否满足可行性条件和最优性条件。 2、明显枚举和隐枚举：如果直接检查问题中的某一变量值组合，则称该组合被明显枚举；如果只需利用问题本身提供的或在求解过程中获得的信息就可以间接判断某一变量值组合的可行性和最优性，则称该组合被隐含地枚举或隐枚举。,0-1线性规划的隐枚举法及其应用,3、穷举法与隐枚举法的区别：穷举法必须对问题中

13、变量值的所有可能组合做明显枚举，而隐枚举法只需明显枚举一部分变量值组合，其余的组合则被隐含地枚举。,4、枚举过程和搜索：在枚举法中按某种规则对问题中的变量值组合进行明显枚举或隐枚举的过程称为枚举过程。因为枚举的目的是为了达到最优解，故枚举过程也称为搜索。 5、枚举策略或搜索策略：在枚举过程中所采用的对问题的变量值组合进行枚举的具体规则称为枚举策略或搜索策略。各种枚举算法的区别就在于所采取的搜索策略不同。,0-1线性规划的隐枚举法及其应用,6、启发性信息和启发性原则：所谓启发性信息是指那些可用于引导枚举过程使之尽快达到最优解的信息。 一般来说，在枚举过程中可供利用的启发性信息越多，隐枚举法的效率

14、就越高。隐枚举法之所以比穷举法有较高的效率，正是因为它利用了某些启发性信息。 在枚举过程中利用启发性信息可建立一些关于可行性或最优性的判别条件以及引导枚举过程的规则，这些判别条件和规则称为启发性原则。,0-1线性规划的隐枚举法及其应用,隐枚举法的启发性信息来自两个方面：,问题本身蕴含的启发性信息。对于线性规划来说，这些信息通常体现在目标函数和约束条件的系数中。目标函数的系数可以提供有关最优性的信息，约束条件的系数可以提供有关可行性的信息。 随着枚举过程的进行获得的启发性信息。这类信息主要是指在枚举过程中确定的最优目标函数值的“界”。隐枚举法的“界”是动态的，即在枚举过程中“界”是不断更新的。在

15、枚举过程的任一时刻，我们感兴趣的“界”是指“当前界”。,0-1线性规划的隐枚举法及其应用,7、枚举终止准则：用于判断枚举过程是否应该终止的条件称为枚举终止准则。在以下三种情况下，枚举过程应该终止：,已确认得到了问题的最优解； 已确认问题无可行解； 已确认问题无有界最优解。 8、二元搜索树：考虑到0-1规划中每一个变量只能取0-1两个值，我们引入一种树状结构图来形象地描述0-1规划问题的枚举过程。这种树状图通常称为搜索树或枚举树。由于这种树的每一个分枝点刚好分出两个分枝，故称为二元搜索树。,0-1线性规划的隐枚举法及其应用,下图为有三个变量xl、x2、x3的0-1规划问题的二元搜索树：,0-1线

16、性规划的隐枚举法及其应用,节点：搜索树中的每个小圆圈称为节点。,树枝：搜索树中节点间的连线称为树枝。 树根：处于搜索树中最顶层的节点称为树根；树根的特征是它只与两根树枝相关联。 树叶：处于搜索树中最底层的节点称为树叶；树叶的特征是它只与一根树枝相关联。 内点：除树根和树叶外的其它节点称为内点；内点的特征是它与三根树枝相关联。,0-1线性规划的隐枚举法及其应用,9、0-1线性规划解的概念：,完全解(全解)：若X=(xl，x2，xn)T中的n个分量均已赋值，则称X为问题的完全解。这里X是由问题中的所有自变量构成的向量。 部分解：若X=(xl，x2，xn)T中只有一部分变量已赋值，则称X为问题的部分

17、解。 自由变量：部分解中尚未赋值的分量称为自由变量。 非自由变量：部分解中已赋值的分量称为非自由变量。 相应于部分解的完全解：令部分解中的所有自由变量均等于0，则可得到一个完全解，此完全解称为相应于给定部分解的完全解。,0-1线性规划的隐枚举法及其应用,10、二元搜索树与0-1问题之间的关系：,搜索树的树根和每一个内点对应一个0-1变量； 树根和每个内点的两个分枝分别表示其相应的变量取值。通常规定左分枝代表1，右分枝代表0； 每个树叶节点对应问题的一个完全解，其中各分量的取值分别对应于从树根到达该树叶所经过的n个分枝所代表的变量的值。 每个内点对应问题的一个部分解，其中非自由变量的值分别对应于

18、从树根到达该内点所经过的所有分枝所代表的值。 树根对应于所有分量均为自由变量的部分解。,0-1线性规划的隐枚举法及其应用,由此可见，树根和内点有两层含义：它一方面对应问题中的变量，另一方面又对应问题的部分解。,(二) 基本思路,0-1规划隐枚举法的基本思路是：寻找启发性信息、最优性和可行性判别条件，沿二元搜索树“前进”和“后退”搜索，逐渐向最优解靠近，直到满足枚举终止准则，求解过程结束。,0-1线性规划的隐枚举法及其应用,前进：沿着搜索树的分枝由上一层节点走到下一层节点叫前进，每走过一个分枝叫前进一步。如果从解的概念来理解，前进意味着将部分解中的某些自由变量变为非自由变量。 后退：沿着搜索树的

19、分枝由下一层节点退到上一层节点叫后退，每走过一个分枝叫后退一步。从解的概念来理解，后退意味着将部分解或完全解中的某些非自由变量变为自由变量。,几个术语：,0-1线性规划的隐枚举法及其应用,深度优先原则：在搜索树上，节点的深度定义为从树根到达该节点所经过的树枝数目。所谓深度优先原则是指在当前节点不满足算法后退条件的情况下，枚举过程总是从该节点走到下一层的某个节点，直到到达某个满足后退条件的节点时才停止前进。深度优先原则的本质是使枚举过程尽快地到达树叶。,后退条件：在枚举过程中，当己到达某个节点时，如果可以判定从该节点出发不可能得到问题的最优解，则称该节点为没有希望的节点或已查明的节点。显然枚举过

20、程一旦遇到没有希望的节点就应后退。为了及时判断当前节点是否为没有希望的节点，就需要建立一些有效的判断条件，这些条件称为后退判别条件或后退条件。,0-1线性规划的隐枚举法及其应用,后进先出原则：在后退过程中，总是将最后进入的变量先退出来，这一原则称为后进先出原则，这是0-1规划问题隐枚举算法中经常采用的一种原则。从搜索树上看， “后进先出”体现为后退时应沿前进时的原路线逆向而行。,(三) 0-1线性规划问题的隐枚举法,对于有n个变量的0-1线性规划问题，变量的可能组合共有2n，当n较大时，显然不宜用穷举法求解。下面将要介绍的适用于标准型0-1线性规划问题的隐枚举算法，由于其充分利用了问题本身提供

21、的和在求解过程中获得的各种启发性信息，是一种效率较高的算法。,0-1线性规划的隐枚举法及其应用,为了便于理解这种算法的思路和步骤，我们先来看一个简单的例子。,例：用隐枚举法求解下列0-1线性规划问题：,0-1线性规划的隐枚举法及其应用,解：化标准型：,0-1线性规划的隐枚举法及其应用,在用隐枚举法求解该问题之前，先引入几个需要用到的符号：, FREE：表示当前解中自由变量的下标集合。, NFREE：表示当前解中非自由变量的下标集合。为了表明各个非自由变量的取值，对NFREE中的下标分别冠以“+”或“-”号， “+”表示相应的变量取值为1， “-”表示相应的变量取值为0。例如： NFREE=-1

22、,2,-3，FREE=4,5，表示xl=0，x2=1，x3=0，x4=0，x5=0。,0-1线性规划的隐枚举法及其应用, VC：表示当前解X不满足的约束条件的序号集。例如VC=(1),(3)表示当前解X不满足约束条件Q1(X)0和Q3(X)0。,如果当前解是部分解，则此时的当前解实际上是指相应于该部分解的完全解。,求解步骤如下：,0-1线性规划的隐枚举法及其应用,在搜索树上，NFREE=对应树根。令所有自由变量都等于0，则得到相应于NFREE=的完全解X=(0,0,0,0,0)T，S=0。 将当前解代入约束条件式得：,X不满足Q1(X)0和Q3(X)0，故X不是可行解。,0-1线性规划的隐枚举

23、法及其应用,2、VC=(1),(3)。令T表示满足下列两个条件的自由变量的下标集合：,在目标函数中的系数小于,至少在VC中的一个约束条件中具有正系数(可行性)。,则对应于当前解X和VC有：T=1,3,4,5,在VC中的每个约束条件中，令T中系数为正的变量等于1，其余变量等于0，得到： Q1(X)=-2+3+1+1=30 Q3(X)=-1+3+1+1=40,0-1线性规划的隐枚举法及其应用,两个约束条件均能得到满足，说明该问题可能有可行解。如果有一个约束条件不满足，则问题无可行解。,3、从T中选择一个自由变量，使之成为非自由变量,选择自由变量的原则是使新的解尽可能达到或接近可行解。即若令NFRE

24、E中的变量等于规定值，所选择的那个自由变量等于1，其它自由变量都等于0，则所得的完全解离可行解的距离应该最小，这一原则称为可行性优先原则。,任一完全解X离可行解的距离定义为：,0-1线性规划的隐枚举法及其应用,这一距离实质上就是解X的可行性测度。显然距离越大表示解的可行性程度越差，当距离等于0时，X就是可行解。,下面来逐个考察T中的自由变量： 对于xl：令x1=1，其它自由变量均为0，得： Q1(X)=1，Q2(X)=1，Q3(X)=-2，距离=0+0+2=2 对于x3：令x3=1，其它自由变量均为0，得：距离=1+1+0=2 对于x4：令x4=1，其它自由变量均为0，得：距离1+2+03 对

25、于x5：令x5=1，其它自由变量均为0，得：距离=4+0+04,按可行性优先原则，应选xl或x3作为新的非自由变量，我们不妨选x1，则NFREE=+1，FREE=2,3,4,5。,0-1线性规划的隐枚举法及其应用,从搜索树上看，这一步相当于从树根O沿树枝xl=1前进到节点1。,0-1线性规划的隐枚举法及其应用,4、与NFREE=+1对应的完全解为X=(1,0,0,0,0)T,S=5。代入约束条件式得：,X不满足Q3(X)0，故X不是可行解。,5 、确定相应于当前解X的VC和T。 由上一步知VC=(3)，而T可按第2步的两个条件确定： T=3,4,5。,0-1线性规划的隐枚举法及其应用,在VC中

26、的每个约束中，令NFREE中的变量等于规定值(即x1=1)，T中系数为正的变量等于1，其余变量等于0，得到Q3(X)=-1-1+3+1+1=30，这说明从当前的部分解NFREE=+1出发有可能得到目标函数值小于 的可行解。,6、按可行性优先原则从T中选择一个自由变量使之变成非自由变量。由于NFREE=+1，故令x1=1，然后对T中的各个自由变量作试探性检查：,0-1线性规划的隐枚举法及其应用,对于x3：令x3=1，其它自由变量均为0，得：距离=0+0+0=0 对于x4：令x4=1，其它自由变量均为0，得：距离0+1+12 对于x5：令x5=1，其它自由变量均为0，得：距离=1+0+12,故将x

27、3变为非自由变量,NFREE=+1,+3,FREE=2, 4,5，这一步相应于从搜索树上的节点1前进到节点2。,0-1线性规划的隐枚举法及其应用,7、相应于NFREE=+1,+3的完全解为 X=(1,0,1,0,0)T S=12,由上一步知, 当前解离可行解的距离为0, 即X是可行解。,8、因当前解已是可行解，且原问题中目标函数的系数均大于0，故在当前NFREE中再增加新的变量将导致目标函数值增大，即从当前NFREE=+1,+3出发不可能得到目标函数值小于 的可行解。按照后进先出原则，应将最后进入NFREE的非自由变量x3的值由1变为0，此时：,0-1线性规划的隐枚举法及其应用,NFREE=+

28、1,-3，FREE=2,4,5,从搜索树上看，节点2是没有希望的节点，故应从此节点后退到节点1。因节点1的另一个分枝x3=0尚未考察，故应从节点1前进到节点3。,0-1线性规划的隐枚举法及其应用,9、相应于NFREE=+1,-3的完全解为：X=(1,0,0,0,0)T， S=5。代入约束条件式得：,Q1(X)=10, Q2(X)=10 , Q3(X)=-2 0, 故VC= (3),根据第2步中的两个条件确定T：,x2在Q3中无正系数，而x4、x5在目标函数中的系数分别为8和9，故T=。这说明从当前的部分解NFREE=+1,-3出发不可能得到目标函数值小于 的可行解，应将最后进入NFREE的非自

29、由变量x3退出，这意味着节点3是没有希望的节点，应从该节点开始后退。,0-1线性规划的隐枚举法及其应用,NFREE=-1, FREE=2,3,4,5,相应于NFREE=-1的完全解为：X=(0,0,0,0,0)T，S=0,0-1线性规划的隐枚举法及其应用,将X代入约束条件式得：,Q1(X)=-20，Q2(X)=0，Q3(X)=-10 故VC=(1),(3)，T=3,4,5,在VC的每个约束中，令x1=0，T中约束系数为正的变量等于1，其余自由变量等于0，得Q1=0，Q3=40，这说明从当前的部分解NFREE=-1出发有可能得到目标函数值小于 的可行解。,11、从T中选择一个自由变量变为非自由变

30、量：,对于x3：令x3=1，其它自由变量均为0，得：距离=1+1+0=2 对于x4：令x4=1，其它自由变量均为0，得：距离1+2+03 对于x5：令x5=1，其它自由变量均为0，得：距离=4+0+04,0-1线性规划的隐枚举法及其应用,故将x3变为非自由变量，此时NFREE=-1,+3，FREE=2,4,5，在搜索树上，这一步相当于从节点4前进到节点5。,0-1线性规划的隐枚举法及其应用,12、相应于NFREE=-1,+3的完全解为：X=(0,0,1,0,0)T, S=7，将X代入约束条件式中得：,Ql(X)=-10, 故VC=(1),(2),3个自由变量x2、x4、x5在目标函数中的系数均

31、大于Bound，所以T=。故节点5是没有希望的节点，应从节点5后退。,0-1线性规划的隐枚举法及其应用,NFREE=-1,-3, FREE=2,4,5,相应的完全解为：X=(0,0,0,0,0)T，S=0,0-1线性规划的隐枚举法及其应用,将X代入约束条件式中得：,Ql(X)=-20，Q2(X)=0，Q3(X)=-10, 故VC=(1),(3),根据T的定义知T=4,5。在VC的每个约束条件中令x1=x3=0，然后令T中约束系数为正的变量等于1，其余自由变量等于0，得到 Ql(X)=-10。,因为Ql(X)0仍未得到满足，故从NFREE=-1,-3出发不可能得到目标函数值小于当前 的可行解，即

32、节点6是没有希望的节点，应从节点6后退。,0-1线性规划的隐枚举法及其应用,此时已无路可走，故该问题的最优解为：,0-1线性规划的隐枚举法及其应用,由此可以看出，原问题的变量组合有25=32种，而隐枚举法只枚举了4种组合便得到了最优解，因此隐枚举法比穷举法效率高得多。,0-1线性规划的隐枚举法及其应用,(四) 0-1线性规划问题隐枚举法的一般步骤,3、对于相应于NFREE的完全解X，计算每个约束Qi(X) (i=1,2,n)的值。如果每个约束都得到满足，则X是可行解。,0-1线性规划的隐枚举法及其应用,4、如果VC=(空集)，转第12步，否则转第5步。,6、构造自由变量下标集合T。T中元素对应

33、的变量必须同时满足以下两个条件：, 至少在VC中的一个约束条件中有正系数(可行性)。,7、若T=，转第11步，否则转第8步。,0-1线性规划的隐枚举法及其应用,8、对VC中的每个约束，分别令非自由变量等于规定值，VC中系数为正的变量等于1，其余自由变量等于0。,9、检验这些约束条件是否被满足。若还有一些约束没有得到满足，转第11步；否则转第10步。,10、按可行性优先原则从T中选出一个自由变量，把它从FREE中去掉并添加到NFREE的元素列的最右边(注意添进的元素前应冠以“+”号)，具体过程如下：,10A、对T中的每个变量，令其值等于1，NFREE中的变量等于规定值，并令其余自由变量等于0，计

34、算每个约束Qi(X)的值(i=1,2,m)。,0-1线性规划的隐枚举法及其应用,10B、对第10A步所得的负数求和，令ASUM为总和的绝对值，每个负数结果的绝对值是使相应的约束增加到可行所必需的数值(离可行性的总距离)。,10C、从FREE中消去T中离可行性有最小总距离(即最小的ASUM)的变量，并把该变量加到NFREE的元素列的最右边。转第2步。,11、若NFREE=，转第21步, 否则从当前NFREE出发不可能得到目标函数值小于 的可行解，故应后退，为此转第16步。,0-1线性规划的隐枚举法及其应用,12、NFREE中的变量用其规定值，并令FREE中的变量为0，共同组成一个完全解。转第13

35、步。,14、更新最优目标函数值上界 ，令 ，并记录当前NFREE的完全解X，记为X*，然后转第15步。,15、后退。若NFREE=，则X=(0,0,0,0)T即为最优解，因而转第20步；否则转第16步。,16、若NFREE中排在最右边的元素带“-”号，转第18步；否则，转第17步。,17、将NFREE中最右边的那个元素的符号由“+”变为“-”，转第2步。,0-1线性规划的隐枚举法及其应用,18、若NFREE中所有元素均带“-”号，则与当前 对应的完全解即为最优解，因此，转第20步；否则，转第19步。,19、将NFREE中最右边的一个“+”元素变为“-”元素，并按后进先出的原则去掉这个元素右边所

36、有“-”元素，相应地把它们放到FREE中，然后转第2步。,21、该问题没有可行解，停止。,20、若得不到可行解，转第21步；否则与当前 对应的完全解即为最优解，打印计算结果，停止。,0-1线性规划的隐枚举法及其应用,四、泵组合问题的隐枚举算法,为了使泵与管路的匹配有足够的灵活性，以适应管道在不同输量下运行的要求，一般长输管道的泵站上都设有几台不同规格的离心泵。因此，在管道运行中经常会遇到所谓站内最优泵组合问题：当总排量和总扬程给定后，如何确定哪几台泵投入运行才能使总运行费用最低？这里说的费用是指与泵的运行有关的消耗，例如耗电量或电费等。,0-1线性规划的隐枚举法及其应用,站内泵组合的基本方式有

37、串联和并联两种，其最优泵组合问题的数学模型如下：,0-1线性规划的隐枚举法及其应用,cj：第j号泵运行时的耗电量或电费(在串联方式下假设每台泵的排量为给定值，在并联泵方式下假设每台泵的扬程为给定值)；,aj：第j号泵的扬程(串联时)或排量(并联时)；,b：所需提供的总扬程(串联时)或总排量(并联时)；,n：泵站内可供选择的泵台数。,0-1线性规划的隐枚举法及其应用,该数学模型有两个特点：,只有一个不等式约束； 不等式约束中变量的系数aj0 ( j=1n)。,根据这些特点所提供的启发性信息，可以对前面提出的0-1线性规划问题的隐枚举法做适当改进，从而得到一种针对最优泵组合问题的特殊算法。这种算法

38、的一个明显特点是：事先按各变量在约束条件中的系数由大到小的顺序将所有变量排列起来，在枚举过程中，只要所考察的变量进入NFREE将满足最优性方面的要求，则按以上顺序逐个进入NFREE。容易证明，这种搜索顺序与按“可行性优先”原则确定的顺序完全一致。,0-1线性规划的隐枚举法及其应用,例：某油库泵房设置有7台离心泵可供并联运行。设泵与管路匹配的工作点为：Q900m3/h，H=200m。当H=200m时，每台泵的排量及电费如下：,要求确定一个最优泵组合与管路匹配以使电费最低。,0-1线性规划的隐枚举法及其应用,解：对泵Pj引入0-1变量xj ( j=17),总电费为S，该问题的数学模型如下：,按约束

39、条件中的系数由大到小的顺序将相应的变量排列起来：,0-1线性规划的隐枚举法及其应用,用隐枚举法求解此模型的步骤如下：,枚举树上,枚举树上,返回,0-1线性规划的隐枚举法及其应用,枚举树上,枚举树上,从这一步可以获得启发性信息：每一个可行的泵组合中至少应有4台泵。这一信息可以加速后面的枚举过程。,0-1线性规划的隐枚举法及其应用,5、因已得到可行解，故应将NFREE中的+7变为-7，则,枚举树上,6、因c6=9Bound，故将+6进入NFREE,枚举树上,0-1线性规划的隐枚举法及其应用,枚举树上,8、因c5=9=Bound，c3=8.5Bound，故将+3进入NFREE,枚举树上,0-1线性规

40、划的隐枚举法及其应用,9、由于x3是搜索顺序中排在最后的一个变量，故在NFREE中x3的下标始终只能排在最右边，因此必须从上一步得到的NFREE开始做多步后退(将x3从NFREE中去掉)，然后从后退终止点(其有分枝尚未搜索的点)开始做多步前进以满足有4台泵的要求，即,枚举树上,0-1线性规划的隐枚举法及其应用,枚举树上,11、因c5=9=Bound，c3=8.5Bound，故将+3进入NFREE,枚举树上,0-1线性规划的隐枚举法及其应用,枚举树上,枚举树上,0-1线性规划的隐枚举法及其应用,14、因c3=8.5Bound，故将+3进入NFREE,枚举树上,15、因上一步NFREE中最右边的元

41、素为+3，其相应于搜索顺序中的最后一个变量x3，故此时应后退。按一般0-1线性规划问题的算法，只要后退到+6这个元素就应该停止后退，但受变量搜索顺序的启发，后退过程可以一直持续到+2这个元素。这是因为：若后退到+6，则将+6变为-6后至多将原NFREE中的-5变为+5，但P5的排量小于P6的排量，故不会再得到可行解。,0-1线性规划的隐枚举法及其应用,从上一步一直后退到+2，将+2变为-2后开始前进3步(为了满足至少开4台泵的要求)，得,枚举树上,枚举树上,0-1线性规划的隐枚举法及其应用,17、因c5=9=Bound，c3=8.5Bound，故将+3进入NFREE,枚举树上,枚举树上,0-1

42、线性规划的隐枚举法及其应用,枚举树上,19、因c3=8.5Bound，故应后退,0-1线性规划的隐枚举法及其应用,枚举树上,20、因c3=8.5Bound，故应后退,0-1线性规划的隐枚举法及其应用,枚举树上,21、因c5=9Bound， c3=8.5Bound，故应后退,0-1线性规划的隐枚举法及其应用,枚举树上,22、因c3=8.5Bound，故将+3进入NFREE,0-1线性规划的隐枚举法及其应用,从当前的NFREE可以看出，此时虽然还可以后退，但无论退到哪一个“+”元素，将该元素变为“-”后均不可能再得到可行解。因此枚举过程结束，相应于 的可行解即为最优解：,0-1线性规划的隐枚举法及

43、其应用,最优泵组合为Pl,P3,P5,P6,P7，总排量刚好为900m3/h，每小时的电费为48.5元。,此问题共有27128种可能泵组合，但上述求解过程实际上只明显枚举了13种。该问题的搜索树如下：,4.4 隐枚举法的FORTRAN程序,程序中设定的变量个数最多为10个，约束条件最多为15个，当所要求解的问题的变量个数超过10个或约束条件超过15个时，需将程序中前三句INTEGER语句中的有关维数作相应的修改。,本程序可用于求解任意的0-1整数规划问题。所要求解的问题可以按原来的数学模型输入，而程序中经过A、B、C、D即可将原来的形式转换为隐枚举法要求的数学模型的形式。,隐枚举法的FORTR

44、AN语言程序,本程序要求所输入的目标函数和约束条件中的系数都必须是整数，当不是整数时，可以在目标函数和约束条件两端乘以10、100、1000、.，使其变为整数。求解完后，最优目标函数值再除以相应的倍数即可得到原问题的最优目标函数值，对决策变量的值无影响。,隐枚举法的FORTRAN语言程序,数据文件的格式如下： 第1行：问题名称 第2行：M,N,NLET,NGET,NET,NTYPE 第3行：CODE(1),B(1),A(1,1),A(1,2),A(1,3),.,A(1,M) . 第N+2行：CODE(N),B(N),A(N,1),A(N,2),A(N,3),.,A(N,M) 第N+3行：C(1

45、),C(2),.,C(M),其中： M变量个数； N约束条件个数； NLET“ ”的约束条件个数； NGET“ ”的约束条件个数； NET“=”的约束条件个数； NTYPE对于min问题，NTYPE=0；对于max问题，NTYPE=1；,CODE(I) 第I个约束的约束形式代码， 对于“”约束，CODE(I)=0 对于“”约束，CODE(I)=1 对于“=”约束， CODE(I)=2 B(I) 第I个约束条件中的右端常数项 A(I,J) 第I个约束条件中第J个变量的系数 C(J) 目标函数表达式中第J个变量的系数,隐枚举法的FORTRAN语言程序,求解结果输出到数据文件中。输出内容包括：原来的

46、约束系数、目标函数系数、化成标准型后的约束系数、求解过程中各步的结果、最优解和最优目标函数值。 为了便于程序阅读，在程序中利用注释语句标出了求解过程的各步。其中STEP A、STEP B、STEP C、STEP D的任务与4.3二中所述相同，用于划标准型；STEP 1STEP 21的任务与4.3三(四)中所述相同。,隐枚举法的FORTRAN语言程序,C 0-1线性规划的隐枚举算法程序(数据输入与输出部分) INTEGER CCS(10),X(11),Y(11),FLAG(10),CODE(15) INTEGER FREE(10),VC(16),C(10),B(16),A(15,10),Q(16

47、,11) INTEGER ASUM(10),NFREE(10),T(10),LAST(10) INTEGER SMIN,S,BOUND,SUM,ZFLAG,CSUM CHARACTER*50 NAME OPEN(21,FILE=0-1.IN) READ(21,*) NAME READ(21,*) M,N,NLET,NGET,NET,NTYPE DO 25 I=1,N READ(21,*)CODE(I),B(I),(A(I,J),J=1,M) 25CONTINUE READ(21,*) (C(J),J=1,M) CLOSE(21) OPEN(21,FILE=0-1.OUT),隐枚举法的FORTR

48、AN语言程序,WRITE(21,41) NAME 41FORMAT(25X,A) WRITE(21,40) 40 FORMAT(/1X,1、原始约束系数/3x, 1 （代码=0表示“=约束”，, 1 代码=2表示“=约束”）/) WRITE(21,55) 55FORMAT(4X,序号 代码 常数项 ai1 ai2 ai3 ai4 ai5 ai6 , 1 ai7 ai8) DO 45 I=1,N WRITE(21,51) I,CODE(I),B(I),(A(I,J),J=1,M) 51FORMAT(4X,I2,1X,I4,1X,I6,1x,8(1X,I4) 45CONTINUE IF(NTYPE

49、.NE.0) GOTO 35 WRITE(21,36) 36FORMAT(/1X,2、最小化问题原始目标函数系数为：),隐枚举法的FORTRAN语言程序,GOTO 37 35WRITE(21,38) 38FORMAT(/1X,2、最大化问题原始目标函数系数为：) 37WRITE(21,39) (C(J),J=1,M) 39FORMAT(3X,10I6),隐枚举法的FORTRAN语言程序,WRITE(21,2025) 2025FORMAT(/1X,5、最优解为：) DO 2030 I=1,M WRITE(21,2040) I,LAST(I) 2040FORMAT(5X,X(,I2,)=,I5)

50、2030CONTINUE NEWMIN=SMIN+CSUM IF(NTYPE.EQ.0)GOTO 2035 NEWMIN=-NEWMIN 2035WRITE(21,2050) NEWMIN 2050FORMAT(/1X,6、最优目标函数值为：,I8) GOTO 2000 2100WRITE(21,2110) 2110 FORMAT(/1X,5、该问题无可行解！) 2000 CLOSE(21) STOP END,隐枚举法的FORTRAN语言程序,例：用程序求解上一节的泵站内最优泵组合问题。 数据输入文件格式为： 泵站内泵组合问题 7,1,0,1,0,0 1,900,225,255,135,300

51、,165,180,195 120,135,85,180,90,90,100 为了满足整数要求，将目标函数的系数均乘以10，求解完后再将最优目标函数值除以10即可。 程序的输出如下：,隐枚举法的FORTRAN语言程序,泵站内泵组合问题 1、原始约束系数 （代码=0表示“=约束”，代码=2表示“=约束”） 序号 代码 常数项 ai1 ai2 ai3 ai4 ai5 ai6 ai7 ai8 1 1 900 225 255 135 300 165 180 195 2、最小化问题原始目标函数系数为： 120 135 85 180 90 90 100 3、变换后的约束条件 序号 常数项 ai1 ai2 ai3 ai4 ai5 ai6 ai7 ai8 1 -900 225 255 135 300 165 180 195 4、各步的部分解(NFREE)为：,隐枚举法的FORTRAN语言程序,序号 目标函数上界 NFREE中变量下标集合 - 0 1000000 0 0 0 0 0 0 0 1 1000000 4 0 0 0 0 0 0 2 1000000 4 2 0 0 0 0 0 3 1000000 4 2 1 0