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

2020/1/191运筹学OPERATIONSRESEARCH2020/1/192第四章整数规划与分配问题（IntegerProgramming,IP)整数规划的有关概念及特点整数规划的求解方法：分枝定界法、割平面法指派问题及匈牙利解法整数规划的应用Page34.1整数规划的特点及应用整数规划（简称：IP）要求一部分或全部决策变量取整数值的规划问题称为整数规划。不考虑整数条件，由余下的目标函数和约束条件构成的规划问题称为该整数规划问题的松弛问题。若该松弛问题是一个线性规划，则称该整数规划为整数线性规划。整数线性规划数学模型的一般形式：11max(min)(1.2)0(j1.2n)njjjnijjijjZZcxaxbimx且部分或全部为整数或Page4整数规划的特点及应用整数线性规划问题的种类：纯整数线性规划：指全部决策变量都必须取整数值的整数线性规划。混合整数线性规划：决策变量中有一部分必须取整数值，另一部分可以不取整数值的整数线性规划。0-1型整数线性规划：决策变量只能取值0或1的整数线性规划。Page5一般形式11max(min)(1.2)..0(j1.2n)njjjnijjijjZZcxaxbimstx或且部分或全部为整数依照决策变量取整要求的不同，整数规划可分为纯整数规划、全整数规划、混合整数规划、0－1整数规划。4.1.1整数规划问题的数学模型2020/1/196纯整数规划：在整数规划中，如果所有的变量都为非负整数，则称为纯整数规划问题；混合整数规划：如果有一部分变量为非负整数，则称之为混合整数规划问题。0-1变量：在整数规划中，如果变量的取值只限于0和1，这样的变量我们称之为0-1变量。0-1规划：在整数规划问题中，如果所有的变量都为0-1变量，则称之为0-1规划。§1整数规划的有关概念及特点一、概念整数规划：要求决策变量取整数值的规划问题。（线性整数规划、非线性整数规划等）2020/1/197求整数解的线性规划问题，不是用四舍五入法或去尾法对性规划的非整数解加以处理就能解决的，用枚举法又往往会计算量太大，所以要用整数规划的特定方法加以解决。例：求解下列整数规划：二、整数规划的求解特点并取整数,0,5.45.01432.23max21212121xxxxxxtsxxz2020/1/1981x2x143221xx5.45.021xx2123xxz)5.2,25.3(分析：若当作一般线性规划求解，图解法的结果如下。1、非整数规划最优解显然不是整数规划的可行解。2、四舍五入后的结果也不是整数规划的可行解。)5.2,25.3()3,3(3、可行解是阴影区域交叉点，可比较这些点对应的函数值，找出最优。)1,4(Page9整数规划的特点及应用整数规划的典型例子例1工厂A1和A2生产某种物资。由于该种物资供不应求，故需要再建一家工厂。相应的建厂方案有A3和A4两个。这种物资的需求地有B1,B2,B3,B4四个。各工厂年生产能力、各地年需求量、各厂至各需求地的单位物资运费cij，见下表：B1B2B3B4年生产能力A12934400A28357600A37612200A44525200年需求量350400300150工厂A3或A4开工后，每年的生产费用估计分别为1200万或1500万元。现要决定应该建设工厂A3还是A4，才能使今后每年的总费用最少。Page10整数规划的特点及应用解：这是一个物资运输问题，特点是事先不能确定应该建A3还是A4中哪一个，因而不知道新厂投产后的实际生产物资。为此，引入0-1变量：)2,1(01iyi若不建工厂若建工厂再设xij为由Ai运往Bj的物资数量，单位为千吨；z表示总费用，单位万元。则该规划问题的数学模型可以表示为：Page11整数规划的特点及应用)2,1(1,0)4,3,2,1,(0200200600400150300400350.]15001200[min244434241134333231242322211413121144342414433323134232221241312111414121iyjixyxxxxyxxxxxxxxxxxxxxxxxxxxxxxxxxxxtsyyxcziijijijij混合整数规划问题Page12整数规划的特点及应用例2现有资金总额为B。可供选择的投资项目有n个，项目j所需投资额和预期收益分别为aj和cj（j＝1,2,..,n），此外由于种种原因，有三个附加条件：若选择项目1，就必须同时选择项目2。反之不一定项目3和4中至少选择一个；项目5,6,7中恰好选择2个。应该怎样选择投资项目，才能使总预期收益最大。Page13整数规划的特点及应用解：对每个投资项目都有被选择和不被选择两种可能，因此分别用0和1表示，令xj表示第j个项目的决策选择，记为：),...,2,1(01njjjxj不投资对项目投资对项目投资问题可以表示为：）（或者nxxxxxxxxBxatsxczjnjjjnjjj,2,1j1021.max765431211Page14整数规划的特点及应用例4.3指派问题或分配问题。人事部门欲安排四人到四个不同岗位工作，每个岗位一个人。经考核四人在不同岗位的成绩（百分制）如表所示，如何安排他们的工作使总成绩最好。工作人员ABCD甲85927390乙95877895丙82837990丁86908088Page15整数规划的特点及应用设工作时人做不分配第工作时人做分配第jijixij01数学模型如下：4443424134333231242322211413121188809086907983829578879590739285maxxxxxxxxxxxxxxxxxZ要求每人做一项工作，约束条件为：111144434241343332312423222114131211xxxxxxxxxxxxxxxxPage16整数规划的特点及应用每项工作只能安排一人，约束条件为：111144342414433323134232221241312111xxxxxxxxxxxxxxxx变量约束：4,3,2,110jixij、，或Page17例某人有一个背包可以装5公斤重、0.02m3的物品。他准备用来装A、B两种物品，每件物品的重量、体积和价值如表3-2所示。问两种物品各装多少件才能使所装物品的总价值最大？表Page18解：设A、B两种物品的装载件数分别为x1，x2，则该问题的数学模型为12121212max451.20.55..0.0030.00250.02,0,Zxxxxstxxxx且为整数假设此人还有一只旅行箱，最大载重量为10公斤，其体积是0.018m3。背包和行李箱只能选择其一，如果所需携带物品不变，问该如何装载物品，使所装物品价值最大？Page19解：引入0-1变量（或称逻辑变量）yi，令1,=1,20,iiiyi采用第种方式装载时不采用第种方式装载时则该整数规划数学模型为12122121212112max451.20.55100.0030.00250.020.018..1,0,i=iZxxxxyyxxyystyyxxy且为整数；=0或1，1,22020/1/1920§2应用举例一、逻辑变量在数学模型中的应用1、m个约束条件中只有k个起作用设有m个约束条件mibanjiij,...,2,1,1定义0-1整型变量：M是任意大正数。10iy第i个约束起作用第i个约束不起作用则原约束中只有k个真正起作用的情况可表示为：kmyyymiMybamnjiiij...,...,2,1,2112020/1/19212、约束条件右端项是r个可能值中的一个rnjijbbba或或,...,211则通过定义10iy约束条件右端项不是bi约束条件右端项是bi可将上述条件表示为1...,2111rnjriiiijyyyyba2020/1/19223、两组条件中满足其中一组例如表示条件：若，则；否则时则通过定义10iy第i组条件起作用，i=1，2第i组条件不起作用可将上述条件表示为,41x,32x,41x,12x又：M是任意大正数，134142122211211yyMyxMyxMyxMyx2020/1/1923定义4、表示含有固定费用的函数例如：表示产品j的生产数量，其生产费用函数为：jx目标函数：00,0,)(jjjjjjjxxxcKxC其中是与产量无关的生产准备费用jKnjjjxCz1)(min10jy0jx0jx则原问题可表示为)(min1njjjjjyKxcz100.或jjjyMyxtsPage24整数规划的特点及应用整数规划问题解的特征：整数规划问题的可行解集合是它松弛问题可行解集合的一个子集，任意两个可行解的凸组合不一定满足整数约束条件，因而不一定仍为可行解。整数规划问题的可行解一定是它的松弛问题的可行解（反之不一定），但其最优解的目标函数值不会优于后者最优解的目标函数值。Page25整数规划的特点及应用例4.3设整数规划问题如下且为整数0,13651914max21212121xxxxxxxxZ首先不考虑整数约束，得到线性规划问题（一般称为松弛问题）。0,13651914max21212121xxxxxxxxZPage26整数规划的特点及应用用图解法求出最优解为：x1＝3/2,x2=10/3，且有Z=29/6≈4.83现求整数解(最优解):如用舍入取整法可得到4个点即(1，3),(2，3),(1，4),(2，4)。显然，它们都不可能是整数规划的最优解。x1x2⑴⑵33(3/2,10/3)按整数规划约束条件，其可行解肯定在线性规划问题的可行域内且为整数点。故整数规划问题的可行解集是一个有限集，如右图所示。其中(2,2),(3,1)点的目标函数值最大，即为Z=4。Page27整数规划的特点及应用整数规划问题的求解方法：分支定界法和割平面法匈牙利法（指派问题）思考:应如何求解整数线性规划问题(IP)?枚举法2020/1/1928§4分枝定界法分枝定界法是求解整数规划的一种常用的有效的方法，它既能解决纯整数规划的问题，又能解决混合整数规划的问题。大多数求解整数规划的商用软件就是基于分枝定界法编制而成的。下面举例来说明分枝定界法的思想和步骤。2020/1/1929性质求MAX的问题：整数规划的最优目标函数值小于或等于相应的线性规划的最优目标函数值；求MIN的问题：整数规划的最优目标函数值大于或等于相应的线性规划的最优目标函数值。1、求解整数规划相应的一般线性规划问题（即先去掉整数约束）。易知：整数规划的可行域（小）包含于线性规划的可行域(大）。若线性规划的最优解恰是整数解，则其就是整数规划的最优解。否则该最优解，是整数规划最优解的上界或下界。2020/1/1930例：求解下列整数规划：并取整数,0x,x5.4x5.0x14x3x2t.sx2x3zmax212121210,5.45.01432.23max21212121xxxxxxtsxxz解：1、解对应的线性规划：其最优解为，显然不是整数规划的可行解。)5.2,25.3(L0：75.140z2020/1/19312、分枝与定界：将对应的线性规划问题分解成