第4章 整数规划与分配问题-第1讲

1、2020/7/4,1,运筹学OPERATIONSRESEARCH,2020/7/4,2,第四章整数规划与分配问题（IntegerProgramming,IP),整数规划的有关概念及特点整数规划的求解方法：分枝定界法、割平面法指派问题及匈牙利解法整数规划的应用,4.1整数规划的特点及应用,整数规划（简称：IP）要求一部分或全部决策变量取整数值的规划问题称为整数规划。不考虑整数条件，由余下的目标函数和约束条件构成的规划问题称为该整数规划问题的松弛问题。若该松弛问题是一个线性规划，则称该整数规划为整数线性规划。,整数线性规划数学模型的一般形式：,整数规划的特点及应用,整数线性规划问题的种类：,纯整数

2、线性规划：指全部决策变量都必须取整数值的整数线性规划。混合整数线性规划：决策变量中有一部分必须取整数值，另一部分可以不取整数值的整数线性规划。0-1型整数线性规划：决策变量只能取值0或1的整数线性规划。,一般形式,依照决策变量取整要求的不同，整数规划可分为纯整数规划、全整数规划、混合整数规划、01整数规划。,4.1.1整数规划问题的数学模型,2020/7/4,6,纯整数规划：在整数规划中，如果所有的变量都为非负整数，则称为纯整数规划问题；混合整数规划：如果有一部分变量为非负整数，则称之为混合整数规划问题。0-1变量：在整数规划中，如果变量的取值只限于0和1，这样的变量我们称之为0-1变量。0-

3、1规划：在整数规划问题中，如果所有的变量都为0-1变量，则称之为0-1规划。,1整数规划的有关概念及特点,一、概念,整数规划：要求决策变量取整数值的规划问题。（线性整数规划、非线性整数规划等）,2020/7/4,7,求整数解的线性规划问题，不是用四舍五入法或去尾法对性规划的非整数解加以处理就能解决的，用枚举法又往往会计算量太大，所以要用整数规划的特定方法加以解决。例：求解下列整数规划：,二、整数规划的求解特点,2020/7/4,8,分析：若当作一般线性规划求解，图解法的结果如下。,1、非整数规划最优解显然不是整数规划的可行解。2、四舍五入后的结果也不是整数规划的可行解。,3、可行解是阴影区域交

4、叉点，可比较这些点对应的函数值，找出最优。,整数规划的特点及应用,整数规划的典型例子,例1工厂A1和A2生产某种物资。由于该种物资供不应求，故需要再建一家工厂。相应的建厂方案有A3和A4两个。这种物资的需求地有B1,B2,B3,B4四个。各工厂年生产能力、各地年需求量、各厂至各需求地的单位物资运费cij，见下表：,工厂A3或A4开工后，每年的生产费用估计分别为1200万或1500万元。现要决定应该建设工厂A3还是A4，才能使今后每年的总费用最少。,整数规划的特点及应用,解：这是一个物资运输问题，特点是事先不能确定应该建A3还是A4中哪一个，因而不知道新厂投产后的实际生产物资。为此，引入0-1变

5、量：,再设xij为由Ai运往Bj的物资数量，单位为千吨；z表示总费用，单位万元。则该规划问题的数学模型可以表示为：,整数规划的特点及应用,混合整数规划问题,整数规划的特点及应用,例2现有资金总额为B。可供选择的投资项目有n个，项目j所需投资额和预期收益分别为aj和cj（j1,2,.,n），此外由于种种原因，有三个附加条件：若选择项目1，就必须同时选择项目2。反之不一定项目3和4中至少选择一个；项目5,6,7中恰好选择2个。应该怎样选择投资项目，才能使总预期收益最大。,整数规划的特点及应用,解：对每个投资项目都有被选择和不被选择两种可能，因此分别用0和1表示，令xj表示第j个项目的决策选择，记为

6、：,投资问题可以表示为：,整数规划的特点及应用,例4.3指派问题或分配问题。人事部门欲安排四人到四个不同岗位工作，每个岗位一个人。经考核四人在不同岗位的成绩（百分制）如表所示，如何安排他们的工作使总成绩最好。,整数规划的特点及应用,设,数学模型如下：,要求每人做一项工作，约束条件为：,整数规划的特点及应用,每项工作只能安排一人，约束条件为：,变量约束：,例某人有一个背包可以装5公斤重、0.02m3的物品。他准备用来装A、B两种物品，每件物品的重量、体积和价值如表3-2所示。问两种物品各装多少件才能使所装物品的总价值最大？,表,解：设A、B两种物品的装载件数分别为x1，x2，则该问题的数学模型为

7、,假设此人还有一只旅行箱，最大载重量为10公斤，其体积是0.018m3。背包和行李箱只能选择其一，如果所需携带物品不变，问该如何装载物品，使所装物品价值最大？,解：引入0-1变量（或称逻辑变量）yi，令,则该整数规划数学模型为,2020/7/4,20,2应用举例,一、逻辑变量在数学模型中的应用,1、m个约束条件中只有k个起作用设有m个约束条件,定义0-1整型变量：M是任意大正数。,第i个约束起作用第i个约束不起作用,则原约束中只有k个真正起作用的情况可表示为：,2020/7/4,21,2、约束条件右端项是r个可能值中的一个,则通过定义,约束条件右端项不是bi约束条件右端项是bi,可将上述条件表

8、示为,2020/7/4,22,3、两组条件中满足其中一组例如表示条件：若，则；否则时,则通过定义,第i组条件起作用，i=1，2第i组条件不起作用,可将上述条件表示为,又：M是任意大正数，,2020/7/4,23,定义,4、表示含有固定费用的函数例如：表示产品j的生产数量，其生产费用函数为：,目标函数：,其中是与产量无关的生产准备费用,则原问题可表示为,整数规划的特点及应用,整数规划问题解的特征：,整数规划问题的可行解集合是它松弛问题可行解集合的一个子集，任意两个可行解的凸组合不一定满足整数约束条件，因而不一定仍为可行解。整数规划问题的可行解一定是它的松弛问题的可行解（反之不一定），但其最优解的

9、目标函数值不会优于后者最优解的目标函数值。,整数规划的特点及应用,例4.3设整数规划问题如下,首先不考虑整数约束，得到线性规划问题（一般称为松弛问题）。,整数规划的特点及应用,用图解法求出最优解为：x13/2,x2=10/3，且有Z=29/64.83,现求整数解(最优解):如用舍入取整法可得到4个点即(1，3),(2，3),(1，4),(2，4)。显然，它们都不可能是整数规划的最优解。,x1,x2,3,3,(3/2,10/3),按整数规划约束条件，其可行解肯定在线性规划问题的可行域内且为整数点。故整数规划问题的可行解集是一个有限集，如右图所示。其中(2,2),(3,1)点的目标函数值最大，即为

10、Z=4。,整数规划的特点及应用,整数规划问题的求解方法：,分支定界法和割平面法匈牙利法（指派问题）,思考:应如何求解整数线性规划问题(IP)?枚举法,2020/7/4,28,4分枝定界法,分枝定界法是求解整数规划的一种常用的有效的方法，它既能解决纯整数规划的问题，又能解决混合整数规划的问题。大多数求解整数规划的商用软件就是基于分枝定界法编制而成的。,下面举例来说明分枝定界法的思想和步骤。,2020/7/4,29,性质求MAX的问题：整数规划的最优目标函数值小于或等于相应的线性规划的最优目标函数值；求MIN的问题：整数规划的最优目标函数值大于或等于相应的线性规划的最优目标函数值。,1、求解整数规

11、划相应的一般线性规划问题（即先去掉整数约束）。易知：整数规划的可行域（小）包含于线性规划的可行域(大）。若线性规划的最优解恰是整数解，则其就是整数规划的最优解。否则该最优解，是整数规划最优解的上界或下界。,2020/7/4,30,例：求解下列整数规划：,解：1、解对应的线性规划：,其最优解为，显然不是整数规划的可行解。,L0：,2020/7/4,31,2、分枝与定界：将对应的线性规划问题分解成几个子问题，每个子问题就是一分枝，而所有子问题的解集之和要包含原整数规划的解集。求解每一分枝子问题：若其最优解满足整数约束，则它就是原问题的一个可行解（不一定是最优）；否则，就是该枝的上界或下界。若所有分

12、支的最优解都不满足整数条件（即不是原问题的可行解），则选取一个边界值最优的分支继续分解，直至找到一个原问题的可行解。若在同一级分枝中同时出现两个以上的原问题可行解，则保留目标值最优的一个，其余不再考虑。,从各分枝中找原问题可行解的目的是为下一步的比较与剪枝。,2020/7/4,32,将上述线性规划问题分为两枝，并求解。,解得,解得,L1：,L2：,显然两个分枝均非整数可行解，选边界值较大的L1继续分枝。,2020/7/4,33,将L1分为两枝，并求解。,解得,解得,L11：,L12：,两个分枝均是整数可行解，保留目标值较大的L12。,2020/7/4,34,3、比较与剪枝将各子问题的边界值与保

13、留下的整数可行解对应的目标值比较，将边界值劣于可行行解的分支减剪去。若比较剪枝后，只剩下所保留的整数可行解，则该解就是原整数规划的最优解；否则选取边界值最大的一个分枝继续分解，在其后的过程中出现新的整数可行解时，则与原可行解比较，保留较优的一个，重复第三步。,2020/7/4,35,L0：,X22,X23,X13,X14,用图表示上例的求解过程与求解结果,2020/7/4,36,5割平面法,一、基本思想,在整数规划的松弛问题中，依次引进新的约束条件（割平面），使问题的可行域逐步减小，但每次割去的只是部分非整数解，直到使问题的目标函数值达到最优的整数点成为缩小后的可行域的一个顶点，这样就可以用线

14、性规划的方法求得整数最优解。,2020/7/4,37,例：求解下列整数规划：,解：1、解对应的线性规划（松弛问题），并将约束条件的系数均化为整数：,2020/7/4,38,加入松弛变量后求解，得最终单纯形表：,如果上述求解结果是整数解，则结束；否则转下一步；,2、找出非整数解中分数部分最大的一个基变量，并将该行对应的约束方程所有常数（系数及常数项）分解成一个整数与一个正分数之和；将所有分式项移到等式右端。例如上例，取第一行约束,2020/7/4,39,易知，左端为整数，要是等式成立，右端也必为整数，且,将代入上式，得,2020/7/4,40,这就是一个割平面。将其添加到原约束中，得到新的可行域

15、如图所示。割去的只是部分非整数解。,2020/7/4,41,3、将新的约束添加到原问题中，得到一个新的线性规划问题，求解此问题，可用灵敏度分析的方法。4、重复上述的1-3步，直至求出整数最优解。,将反应到最终表中，得,2020/7/4,42,运用对偶单纯形法，解得,此解仍非整数解，将基变量对应的约束分解为：,得到新的约束,2020/7/4,43,此时已得整数最优解。,2020/7/4,44,约束,即为,分支定界法,1）求整数规划的松弛问题最优解；若松弛问题的最优解满足整数要求，得到整数规划的最优解,否则转下一步；2）分支与定界：任意选一个非整数解的变量xi，在松弛问题中加上约束：xixi和xi

16、xi+1组成两个新的松弛问题，称为分枝。新的松弛问题具有特征：当原问题是求最大值时，目标值是分枝问题的上界；当原问题是求最小值时，目标值是分枝问题的下界。3)剪枝检查所有分枝的解及目标函数值，若某分枝的解是整数并且目标函数值大于（max）等于其它分枝的目标值，则将其它分枝剪去不再计算，若还存在非整数解并且目标值大于(max)整数解的目标值，需要继续分枝，再检查，直到得到最优解。,分支定界法的解题步骤：,分支定界法,例用分枝定界法求解整数规划问题,解：首先去掉整数约束，变成一般线性规划问题(原整数规划问题的松驰问题),LP,IP,分支定界法,用图解法求松弛问题的最优解，如图所示。,x1,x2,3

17、,(18/11,40/11),2,1,1,2,3,x118/11,x2=40/11Z=218/11(19.8)即Z也是IP最小值的下限。,对于x118/111.64，取值x11，x12对于x2=40/113.64，取值x23，x24先将（LP）划分为（LP1）和（LP2）,取x11,x12,分支定界法,分支：,分别求出（LP1）和（LP2）的最优解。,分支定界法,先求LP1,如图所示。此时在B点取得最优解。x11,x2=3,Z(1)16找到整数解，问题已探明，此枝停止计算。,x1,x2,3,3,(18/11,40/11),1,1,B,A,C,同理求LP2,如图所示。在C点取得最优解。即:x12

18、,x2=10/3,Z(2)56/318.7Z(2)Z(1)16原问题有比16更小的最优解，但x2不是整数，故继续分支。,分支定界法,在IP2中分别再加入条件：x23,x24得下式两支：,分别求出LP21和LP22的最优解,分支定界法,x1,x2,3,3,(18/11,40/11),1,1,B,A,C,D,先求LP21,如图所示。此时D在点取得最优解。即x112/52.4,x2=3,Z(21)-87/5-17.4Z(1)=-16但x112/5不是整数，可继续分枝。即3x12。,求LP22，如图所示。无可行解，故不再分枝。,分支定界法,在（LP21）的基础上继续分枝。加入条件3x12有下式：,分别

19、求出（LP211）和（LP212）的最优解,分支定界法,x1,x2,3,3,(18/11,40/11),1,1,B,A,C,D,E,F,先求（LP211）,如图所示。此时在E点取得最优解。即x12,x2=3,Z(211)17找到整数解，问题已探明，此枝停止计算。,求（LP212），如图所示。此时F在点取得最优解。即x13,x2=2.5,Z(212)31/215.5Z(211)如对LP212继续分解，其最小值也不会低于15.5，问题探明,剪枝。,分支定界法,原整数规划问题的最优解为:x1=2,x2=3,Z*=17以上的求解过程可以用一个树形图表示如右：,LP1x1=1,x2=3Z(1)16,LPx1=18/11,x2=40/11Z(0)19.8,LP2x1=2,x2=10/3Z(2)18.5,LP21x1=12/5,x2=3Z(21)17.4,LP22无可行解,LP211x1=2,x2=3Z(211)17,LP212x1=3