管理运筹学讲义 第4章-整数规划4学时

1,第四章整数规划,Subtitle,学习要点,了解整数规划的含义及类型掌握分支定界的原理和步骤熟悉割平面法的原理和步骤能够正确引入0-1变量建型了解指派问题的求解思路熟悉整数规划的应用实例,2,第一节整数规划问题引言,线性规划的决策变量取值可以是任意非负实数，但许多实际问题中，只有当决策变量的取值为整数时才有意义。例如，产品的件数、机器的台数、装货的车数、完成工作的人数等，分数或小数解显然是不合理的。要求部分或全部决策变量是整数的线性规划问题，则称为整数规划(IntegerProgramming)。当要求全部决策变量的取值都为非负整数的，则称为纯整数规划或全整数规划(PureIP)；仅要求部分决策变量的取值为整数，而另一部分不一定要求取整数，则称为混合整数规划(MixedIP)要求决策变量只取0或1值，则称为0-1规划(0-1Programming),3,第一节整数规划问题引言,一、整数线性规划数学模型的一般形式,4,例5-1：纯整数规划某人有一背包可以装10公斤重、25cm3的物品。他准备用来装甲、乙两种物品，每件物品的重量、体积和价值如表51所示。问两种物品各装多少件，所装物品的总价值最大？,二、整数规划例子,第一节整数规划问题引言,1.20.8,表5-1,解：设甲、乙两种物品各装x1、x2件，则数学模型为：,(5-1),5,如果不考虑x1、x2取整数的约束,则称该式为5.1的松弛问题，该松弛问题的可行域如图5-1中的阴影部分所示。,第一节整数规划问题引言,二、整数规划例子例5-1：纯整数规划,图4-1,6,例5-1：纯整数规划用图解法求得点B为最优解：X(3.57，7.14)，Z35.7。由于x1，x2必须取整数值，实际上整数规划问题的可行解集只是图中可行域内的那些整数点。用化整法来解时需要比较四种组合，但（4，7）、（4，8）（3，8）都不是可行解，（3，7）虽属可行解，但代入目标函数得Z=33,并非最优值。实际上问题的最优解是（5，5），Z=35。即两种物品各装5件，总价值35元。由图51知，点（5，5）不是可行域的顶点，直接用图解法或单纯形法都无法求出整数规划问题的最优解，因此求解整数规划问题的最优解需要采用其它特殊方法。还有些问题用线性规划数学模型无法描述，但可以通过设置逻辑变量建立起整数规划的数学模型。,二、整数规划例子,第一节整数规划问题引言,(5-1),7,第一节整数规划问题引言,登山队员可携带最大重量为25公斤。问都带哪些物品的重要性最大。,解：对于每一种物品无非有两种状态，带或者不带，不妨设,0-1规划的模型：,二、整数规划例子,例5-2：0-1规划,表5-2,8,第一节整数规划问题引言,例5-3：混合整数规划,某产品有n个区域市场，各区域市场的需求量为bj吨/月；现拟在m个地点中选址建生产厂，一个地方最多只能建一家工厂；若选i地建厂，生产能力为ai吨/月，其运营固定费用为F元/月；已知址i至j区域市场的运价为cij元/吨。如何选址和安排调运，可使总费用最小？,解：选址建厂与否是个0-1型决策变量，假设yi=1，选择第i址建厂，yi=0，不选择第i址建厂；计划从i址至区域市场j的运输运量xij为实数型决策变量。,二、整数规划例子,9,1、整数规划的松弛问题不考虑整数约束则是一个LP问题,称为原整数规划的松弛问题，如例5-4。,第一节整数规划问题引言,三、整数规划解的特点,如果先不考虑整数条件，得到如下松弛问题)：,对于这个问题，很容易用图解法得到松弛问题在B点的最优解。,图4-2,10,2、舍入化整法,为了满足整数解的要求，自然想到“舍入”或“截尾”处理，以得到与最优解相近的整数解。这样做除少数情况外，一般不可行，因为化整后的解有可能超出了可行域，成为非可行解；或者虽是可行解，却不是最优解。,对于例5-4的数学模型，不考虑整数约束的最优解：x1=2，x2=9/5，Z=11。,再考虑整数条件，进行舍入化整：x1=2，x2=2，Z=-，点(2.2)落在可行域外，不是可行解；x1=2，x2=1，Z=7，满足约束条件，是可行解，但不是最优解；x1=0，x2=2，Z=10，满足约束条件，是可行解，且为最优解。,三、整数规划解的特点,因此不能企图简单的将松弛问题的最优解圆整(例如四舍五入)就能得到整数规划的最优解。,第一节整数规划问题引言,11,3、完全枚举法,第一节整数规划问题引言,三、整数规划解的特点,从图4-2可知，整数规划问题的可行解集是相应的线性规划问题的可行域内的整数格子点，它是一个有限集。显然，我们还有另一种方法，即将所有的可行解依次代入目标函数，比较所得的目标函数的大小，从而得到最优解。这个方法称为完全枚举法。如上例有整数可行解有个，所以得到最优解（0，2），最优值为10。对于决策变量较少，可行的整数解又较少时，这种穷举法有时是可行的，并且也是有效的。但对于大型的整数规划问题，可行的整数解数量很多，用穷举法求解是不可能的。因此，如何巧妙构造枚举过程是必须研究的问题，目前用得较多的是将完全枚举法变成部分枚举法。常用的求解整数规划的方法有分枝定界法和割平面法，对于特别的0-1规划问题的求解，可以采用隐枚举法和匈牙利法。下面分别介绍。,12,第二节求解纯整数规划的割平面法,一、割平面法原理,设纯整数规划为：,其松弛问题为,的最优解,设xi不为整数，从最终单纯行表中可得第m个约束方程可表示为：,将分离成一个整数（正或负）与一个非负真分数之和：,13,则有,等式两边都为整数并且有：,第二节求解纯整数规划的割平面法,一、割平面法原理,加入松弛变量si得：,则,14,第二节求解纯整数规划的割平面法,此式称为以xi行为源行（来源行）的割平面，或分数切割式，或R.E.Gomory(高莫雷)约束方程。将Gomory约束加入到松弛问题的最优表中，用对偶单纯形法计算，若最优解中还有非整数解，再继续切割，直到全部为整数解。,一、割平面法原理,15,第二节求解纯整数规划的割平面法,二、割平面法例子,例5-5：已知整数规划,解:不考虑整数约束，松弛问题的最优表如下：,16,第二节求解纯整数规划的割平面法,二、割平面法例子,最优解X=(13/4，5/2，0，0)T，x1、x2不满足整数要求，选择x2行进行分割：,添加松弛变量得Gomory约束,添加到最优表中，得：,表5-3松弛问题的最优单纯形表,17,第二节求解纯整数规划的割平面法,二、割平面法例子,x1行：,Gomory约束,添加到最优表中，得,18,第二节求解纯整数规划的割平面法,二、割平面法例子,19,第二节求解纯整数规划的割平面法,二、割平面法例子,得到整数最优解：X(4，1)，Z14,注1：,Gomory约束可写为:,注2：Gomory约束只是割去线性规划可行域的一部分，保留了全部整数解。,用图解法表示：,松弛问题,4,1,x1+x25,第二次切割,20,1、领会割平面法的基本原理；1、分离源行，求出Gomory约束；2、在最优表中增加Gomory约束，用对偶单纯形法迭代。,第二节求解纯整数规划的割平面法,二、割平面法例子,21,第三节分支定界法,一、分支定界法原理,不考虑整数限制，先求出相应线性规划的最优解，若求得的最优解符合整数要求，则是原IP的最优解；若不满足整数条件，则任选一个不满足整数条件的变量来构造新的约束，在原可行域中剔除部分非整数解。依次在缩小的可行域中求解新构造的线性规划的最优解，直到获得原整数规划的最优解。定界的含义：IP是在相应的LP基础上增加整数约束IP的最优解不会优于相应LP的最优解对MaxZ，相应LP的Z*是原IP的上界,22,第三节分支定界法,二、分支定界法举例,例5-6：用分枝定界法求解,解：不考虑整数约束，求出相应松弛问题LP0的最优解：,23,第三节分支定界法,二、分支定界法举例,24,10,10,x1,x2,o,A,B,C,LP1,LP2,3,4,LP1:X=(3,7.6),Z1=34.8,LP2:X=(4,6.5),Z2=35.5,25,10,10,x1,x2,o,A,B,C,LP1,LP3,3,4,LP3:X=(4.33,6),Z3=35.33,6,26,10,10,x1,x2,o,A,C,LP1,3,4,6,LP4:X=(4,6),Z4=34,LP5:X=(5,5),Z5=35,5,LP3,27,LP1的解中x2不为整数，且Z5Z,因此LP5的最优解就是原整数规划的最优解。,第三节分支定界法,二、分支定界法举例,28,x1,第三节分支定界法,二、分支定界法举例,29,第三节分支定界法,三、分枝定界法的步骤,1.求整数规划的松弛问题最优解；2.若松弛问题的最优解满足整数要求，得到整数规划的最优解，否则转下一步；3.任意选一个非整数解的变量xi，在松弛问题中加上约束xixi及xixi+1组成两个新的松弛问题，称为分枝。新的松弛问题具有特征：当原问题是求最大值时，目标值是分枝问题的上界；当原问题是求最小值时，目标值是分枝问题的下界；4.检查所有分枝的解及目标函数值，若某分枝的解是整数并且目标函数值大于（max）等于其它分枝的目标值，则将其它分枝剪去不再计算，若还存在非整数解并且目标值大于（max）整数解的目标值，需要继续分枝，再检查，直到得到最优解。,30,1.理解分枝与定界的含义2.选择合适的“枝”生“枝”3.掌握何时停止生“枝”,第三节分支定界法,31,第四节求解01整数规划的隐枚举法,一、隐枚举法的步骤,1、找出任意一可行解，目标函数值为Z0；2、原问题求最大值时，则增加一个约束:,当求最小值时，上式改为小于等于约束；3、列出所有可能解，对每个可能解先检验式（1），若满足再检验其它约束，若不满足式（1），则认为不可行，若所有约束都满足，则认为此解是可行解，求出目标值；4、目标函数值最大（最小）的解就是最优解。,(1),32,第四节求解01整数规划的隐枚举法,二、隐枚举法举例,例5-7：用隐枚举法求下列01整数规划的最优解。,解：容易求得X(1,0,0)是一可行解，Z06。加一个约束:,由于3个变量每个变量取0或1，共有8种组合，用列表的方法检验每种组合解是否可行解，满足约束打上记号“”，不满足约束打上记号“”，计算如表53所示。,33,第四节求解01整数规划的隐枚举法,二、隐枚举法举例,表5-4变量组合一览表,由表5-4知，X（1，0，1）是最优解，最优值Z9。,34,第四节求解01整数规划的隐枚举法,二、隐枚举法举例,例5-8：求解0-1整数规划问题,35,第四节求解01整数规划的隐枚举法,二、隐枚举法举例,解:列出变量取值0和1的组合，共23=8个,36,第四节求解01整数规划的隐枚举法,二、隐枚举法举例,例5-9：求解0-1整数规划问题,解：（1）第一个约束没有约束力，可以去掉。再按目标函数中各变量系数的大小重新排列各变量（求最小值时目标函数系数从小到大排序）。,37,(2)列出变量取值0和1的组合，共24=16个,第四节求解01整数规划的隐枚举法,二、隐枚举法举例,38,第五节指派（分派）问题,一、指派问题引例,例5-10：指派问题或分配问题。人事部门欲安排四人到四个不同岗位工作，每个岗位一个人。经考核四人在不同岗位的成绩（百分制）如表55所示，如何安排他们的工作使总成绩最好？,表5-5四人在不同岗位的成绩,39,解：,目标函数为：,要求每人做一项工作，约束条件为:,第五节指派（分派）问题,一、指派问题引例,每项工作只能安排一人，约束条件为：,变量约束：,40,第五节指派（分派）问题,二、一般指派问题的标准数学模型,指派问题的标准形式（以人和事为例）：有n个人和n件事，已知第i个人做第j事的费用为cij（ij=1,2,n）,要求确定人和事之间的一一对应得指派方案，使完成这n件事的总费用最少。,则问题的数学模型可写为：,41,第五节指派（分派）问题,三、求解指派问题的方法：匈牙利算法,1、匈牙利算法的条件假设问题求最小值、人数与工作数相等，即n个人恰好做n项工作、第i个人做第j项工作的效率为cij，效率矩阵为cij，为非负(标准形式)。匈牙利算法是匈牙利数学家克尼格（Konig）证明了下面两个基本定理，为计算指派问题奠定了基础。因此，基于这两个定理基础上建立起来的解指派问题的计算方法被称为匈牙利法。,【定理1】指派（分派）问题最优解的性质:假定C=cij为分派问题的价值系数矩阵。现将它的某一行（或某一列）的各个元素都减去一个常数k，得到一新矩阵C=cij。若以C代替C作为原问题的价值系数矩阵，而构成一新的分派问题，则这个新的分派问题的最优解与原问题的最优解相同。【定理2】若矩阵A的元素可分成“0”与非“0”两部分，则覆盖“0”元素的最少直线数等于位于不同行不同列的“0”元素（称为独立元素）的最大个数。如果最少直线数等于m，则存在m个独立的“0”元素，令这些零元素对应的xij等于1，其余变量等于0，得到最优解。定理1告诉我们如何将效率表中的元素转换为有零元素，定理2告诉我们效率表中有多少个独立的“0”元素。,42,第五节指派（分派）问题,四、求解指派问题的方法：匈牙利算法,2、匈牙利算法的求解步骤,设已给定一个初始的nn价值系数矩阵c=(cij)，运用匈牙利法求最优分派的步骤如下：,(1)变换系数矩阵，先对各行再对各列减去个该行该列最小的元素，使其每行每列都至少出现一个0元素；(2)画圈，寻找独立0元素：从只有一个0元素的行(列)开始，给这个0元素加圈，记作。然后，划去该所在列的其它0元素，记作。给只有一个0元素列(行)的0元素加圈，记作。然后，划去该所在行的其它0元素，记作。反复进行（1）、（2）操作，直到所有0元素都被圈出和划掉为止。若每行每列均只有一个时，即的个数等于方阵阶数n，得最优解，否则转到步骤3。若出现0元素闭回路，则任选一个0画破闭回路，并划去同行与同列其它0元素，得最优解。,43,第五节指派（分派）问题,四、求解指派问题的方法：匈牙利算法,2、匈牙利算法的求解步骤,a、对没有的行打；b、对已打的行中所有划去的0元素所对应的列打；c、再对已打的列中有的元素所对应的行打；d、重复b、c，直到得不出新的打的行和新的打的列为止；e、对没有打的行画一横线，打的列画一竖线，得m条直线。,（3）的个数少于n，用尽可能少的m条直线覆盖所有0元素。,（4）从未被m条直线覆盖的元素中找出最小元素，从所有未被覆盖的元素中将它减去，并将这个最小元素加在所有位于水平覆盖线和竖直覆盖线相交处的元素上，而其它被覆盖的元素保持不变。这样便得一新的简约化价值系数矩阵，然后转回第2步。,44,第五节指派（分派）问题,四、匈牙利算法求解举例,例5-11：已知四人分别完成四项工作所需时间如下表，求最优分配方案。,解：最优分配方案是怎样安排四人的工作，使得完成工作总时间最少，是求最小值问题。,45,第五节指派（分派）问题,四、匈牙利算法求解举例,第一步：找出效率矩阵每行的最小元素，并分别从每行中减去最小元素，有,Min,第二步：找出矩阵每列的最小元素，再分别从每列中减去，有,Min3408,46,第五节指派（分派）问题,四、匈牙利算法求解举例,第三步：用最少的直线覆盖所有“0”，得,第四步：这里直线数等于3（等于4时停止运算），要进行下一轮计算。,（1）从矩阵未被直线覆盖的数字中找出一个最小的数k，表中k3。,（2）直线相交处的元素加上k，未被直线覆盖的元素减去k，被直线覆盖而没有相交的元素不变，得到下列矩阵：,47,第五节指派（分派）问题,四、匈牙利算法求解举例,回到第三步:用最少的直线覆盖所有“0”，得：,未被直线覆盖元素中最小元素k=2，直线相交处的元素加上2，未被直线覆盖的元素减去2，被直线覆盖而没有相交的元素不变，得到下列矩阵：,48,第五节指派（分派）问题,四、匈牙利算法求解举例,画线，最少直线数等于4。,第五步：确立独立元素，进行最优分配,最优解：,最优值Z73878288330,49,第五节指派（分派）问题,五、非标准形式的指派（分派）问题,(1)当人数m大于工作数n时，加上mn项工作，例如,1、不平衡的指派问题(人数和事数不等),(2)当人数m小于工作数n时，加上nm个人，例如,50,2、求最大值的指派问题,匈牙利法的条件是：模型求最小值、效率cij0,令,则,与,的最优解相同。,设C=(cij)mm对应的模型是求最大值,第五节指派（分派）问题,五、非标准形式的指派（分派）问题,将其变换为求最小值,3、一个人可做几件事的指派问题。,4、某事一定不能由某人做的指派问题,将该人看作是几个“人”来接受指派，这几个人做同一件事的费用系数一致。,某事一定不能由某人做，则可将相应的费用系数取为足够大的数M。,51,例5-12：某人事部门拟招聘4人任职4项工作，对他们综合考评的得分如下表（满分100分），应如何安排工作使总分最多。,解：M95，令,第五节指派（分派）问题,五、非标准形式的指派（分派）问题,52,第五节指派（分派）问题,五、非标准形式的指派（分派）问题,用匈牙利法求解：,最优解：,即甲安排做第二项工作、乙做第三项、丙做第四项、丁做第三项。总分为：Z92959080357。,53,第六节整数规划应用,一、生产基地规划,例：某公司拟建设A、B两种类型的生产基地若干个，两种类型的生产基地每个占地面积，所需经费，建成后生产能力及现有资源情况如下表所示。问A、B类型基地各建设多少个，可使总生产能力最大？,解：设A、B两类基地各建设个，则其模型为：,54,第六节整数规划应用,二、人员安排规划,某服务部门各时段(每2小时为一时段)需要的服务人数如表：,解：设第j时段开始时上班的服务员人数为xj第j时段来上班的服务员将在第j+3时段结束时下班，故决策变量有x1,x2,x3,x4,x5。,按规定，服务员连续工作8小时(4个时段)为一班。请安排服务员的工作时间，使服务员总数最少.,55,第六节整数规划应用,三、项目投资选择,有600万元投资5个项目，收益如表，求利润最大的方案？,56,第六节整数规划应用,四、互斥约束问题,例如关于煤资源的限制，其约束条件为：企业也可以考虑采用天然气进行加热处理：这两个条件是互相排斥的。引入01变量y，令互斥问题可由下述的条件来代替，其中M是充分大的数。,57,第六节整数规划应用,五、租赁生产问题,服装公司租用生产线拟生产T恤、衬衫和裤子。每年可用劳动力8200h，布料8800m2。,假设：yj=1，要租用生产线jyi=0，不租用生产线j第j种服装生产量xj,58,第六节整数规划应用,六、任务指派问题,甲、乙、丙、丁四个人，A、B、C、D四项任务，不同的人做不同的工作效率不同，如何指派不同的人去做不同的工作使效率最高，即花费的总时间最短？,解：对于这个问题，