运筹学chap4 整数规划

Chapter4整数规划(IntegerProgramming)整数规划的特点及应用分配问题与匈牙利法分支定界法割平面法本章主要内容：Page2这样的问题称为整数线性规划(integerlinearprogramming)，简称ILP.线性规划问题的最优解可能是分数或小数，但对于某些问题，常要求解必须是整数(称为整数解)。例如，所求解是机器的台数、完成工作的人数或装货的车数等。整数规划的特点及应用Page3整数规划的特点及应用整数规划（简称：IP）要求一部分或全部决策变量取整数值的规划问题称为整数规划。不考虑整数条件，由余下的目标函数和约束条件构成的规划问题称为整数规划的松弛问题。若松弛问题是一个线性规划，则称整数规划为整数线性规划。Page4整数规划的特点及应用整数线性规划的一般形式：且部分或全部为整数或n)1.2(j0)2.1()min(max11jnjijijnjjjxmibxaxcZZPage5整数规划的特点及应用整数线性规划问题的种类：纯整数线性规划：指全部决策变量都必须取整数值的整数线性规划。为整数xxbAxtsxc,0..minPage6整数规划的特点及应用整数线性规划问题的种类：0-1型整数线性规划：决策变量只能取值0或1的整数线性规划。nixbAxtsxci,...,2,1;1,0..minPage7整数规划的特点及应用整数线性规划问题的种类：混合整数线性规划：决策变量中有一部分必须取整数值，另一部分可以不取整数值的整数线性规划。pixxbAxtsxci,...,2,1,0..min为整数Page8整数规划的典型例子例4.1工厂A1和A2生产某种物资。由于该种物资供不应求，故需要再建一家工厂。相应的建厂方案有A3和A4两个。这种物资的需求地有B1,B2,B3,B4四个。各工厂年生产能力、各地年需求量、各厂至各需求地的单位物资运费cij，见下表：B1B2B3B4年生产能力A12934400A28357600A37612200A44525200年需求量350400300150工厂A3或A4开工后，每年的生产费用估计分别为1200万或1500万元。现要决定应该建设工厂A3还是A4，才能使今后每年的总费用最少。Page9整数规划的特点及应用解：这是一个物资运输问题，特点是事先不能确定应该建A3还是A4中哪一个，因而不知道新厂投产后的实际生产物资。)2,1(01iyi若不建工厂若建工厂再设xij为由Ai运往Bj的物资数量，单位为千吨；z表示总费用，单位万元。则该规划问题的数学模型可以表示为：为此，引入0-1变量：Page10整数规划的特点及应用)2,1(1,0)4,3,2,1,(0200200600400150300400350.]15001200[min244434241134333231242322211413121144342414433323134232221241312111414121iyjixyxxxxyxxxxxxxxxxxxxxxxxxxxxxxxxxxxtsyyxcziijijijij混合整数规划问题Page11整数规划的特点及应用例4.2现有资金总额为B。可供选择的投资项目有n个，项目j所需投资额和预期收益分别为aj和cj（j＝1,2,..,n），此外由于种种原因，有三个附加条件：若选择项目1，就必须同时选择项目2。反之不一定项目3和4中至少选择一个；项目5,6,7中恰好选择2个。应该怎样选择投资项目，才能使总预期收益最大。Page12整数规划的特点及应用解：对每个投资项目都有被选择和不被选择两种可能，因此分别用0和1表示，令xj表示第j个项目的决策选择，记为：),...,2,1(01njjjxj不投资对项目投资对项目投资问题可以表示为：）（或者nxxxxxxxxBxatsxczjnjjjnjjj,2,1j1021.max765431211Page13整数规划的特点及应用例4.3指派问题或分配问题。人事部门欲安排四人到四个不同岗位工作，每个岗位一个人。经考核四人在不同岗位的成绩（百分制）如表所示，如何安排他们的工作使总成绩最好。工作人员ABCD甲85927390乙95877895丙82837990丁86908088Page14整数规划的特点及应用设工作时人做不分配第工作时人做分配第jijixij01数学模型如下：4443424134333231242322211413121188809086907983829578879590739285maxxxxxxxxxxxxxxxxxZ要求每人做一项工作，约束条件为：111144434241343332312423222114131211xxxxxxxxxxxxxxxxPage15整数规划的特点及应用每项工作只能安排一人，约束条件为：111144342414433323134232221241312111xxxxxxxxxxxxxxxx变量约束：4,3,2,110jixij、，或Page16整数规划的特点及应用例设整数规划问题如下且为整数0,13651914max21212121xxxxxxxxZ松弛0,13651914max21212121xxxxxxxxZ整数规划怎么求解？线性规划问题的最优解可能是分数或小数，为满足整数解的要求，似乎可以把已得到的带有分数或小数的解“舍入化整”。这种方法可行吗？Page17整数规划的特点及应用用图解法求出最优解为：x1＝3/2,x2=10/3，且有Z=29/6现求整数解(最优解):如用舍入取整法可得到4个点即(1,3),(2,3),(1,4),(2,4)。显然，它们都不可能是整数规划的最优解。x1x2⑴⑵33(3/2,10/3)按整数规划约束条件，其可行解肯定在线性规划问题的可行域内且为整数点。故整数规划问题的可行解集是一个有限集，如右图所示。其中(2,2),(3,1)点的目标函数值最大，即为Z=4。Page18整数规划的特点及应用整数规划问题解的特征：最优点不一定在顶点处取到最优解不一定是松弛问题最优解的邻近整数解整数可行解远多余于顶点，枚举法不可取可行解是其松弛问题的可行解，反之不一定，但如果松弛问题的最优解还满足整数约束条件，是整数规划的最优解。由上例看出，将线性规划的最优解经过“化整”来解原整数线性规划，虽是最容易想到的，但常常得不到整数线性规划的最优解，甚至根本不是可行解。x1x2⑴⑵33(3/2,10/3)Page19整数规划的特点及应用整数规划问题的求解方法：匈牙利法（指派问题）分支定界法割平面法Page20分配问题与匈牙利法典型的分配问题（又称为指派问题）：某单位需完成n项任务，恰有n个人可以承担，由于每个人的专长不同，各人完成任务的效率不同，各人完成一项任务的同时，不能同时去做其它任务，如何分配任务会使所需的时间最小或成本最低。Page21分配问题与匈牙利法分配问题的标准形式：n个人，n件工作，已知第i个人去做第j件工作的效率（时间或费用）为Cij(i=1,2,…,n,j=1,2,…,n)并假设Cij≥0。确定人和事之间一一对应的指派方案，问应如何分配才能使总效率（时间或费用）最高？效率矩阵或系数矩阵C=(cij)n×n=c11c12…c1nc21c22…c2n………………cn1cn2…cnnPage22标准指派问题的数学模型：设决策变量),...,2,1,(ji0ji1njixij件事个人做第不指派第件事个人做第指派第ninjijijxcZ11minniijx11njijx11j=1,2,…,ni=1,2,…,nxij=1或0Page23解矩阵：满足约束条件的可行解也可以写成表格或矩阵的形式，称为解矩阵。例：每行的和以及每列的和都是1X=(xij)4×4=0100000110000010标准指派问题的数学模型：ninjijijxcZ11minniijx11njijx11xij=1或0Page24匈牙利法解分配问题的匈牙利法是从这样一个明显的事实出发的：如果效率矩阵的所有元素非负，而其中存在一组位于不同行不同列的零元素，则只要令对应于这些零元素位置的xii=1,其他的xij=0，则对应的目标函数值就是最优值。关键问题是如何产生并寻找这组位于不同行不同列的零元素。匈牙利数学家克尼格（Konig）给出了两个关键的定理，基于这两个关键事实建立起来的解分配问题的计算方法称为匈牙利法。Page25匈牙利法克尼格定理:如果从分配问题效率矩阵(cij)的每一行元素中分别减去(或加上)一个常数ui，从每一列中分别减去(或加上)一个常数vj，得到一个新的效率矩阵(bij)，其中bij=aij-ui-vj,则以(bij)为效率矩阵的分配问题与以(cij)为效率矩阵的分配问题具有相同的最优解。Page26匈牙利法(bij)、(cij)为效率矩阵的分配问题具有相同的最优解。AB甲35乙42AB甲02乙20每行减去最小值甲完成B比完成A多2个单位乙完成A比完成B多2个单位甲完成A，乙完成BPage27匈牙利法(bij)、(cij)为效率矩阵的分配问题具有相同的最优解。AB甲35乙42AB甲03乙10每列减去最小值乙完成A比甲完成A多1个单位甲完成B比乙完成B多3个单位甲完成A，乙完成BPage28C=(cij)n×n=2151341041415914161378119匈牙利法：这个定理是通过构造等价效率矩阵来产生零元素。若从系数矩阵(cij)的一行(列)各元素中分别减去该行(列)的最小元素，得到新矩阵(bij)，那么以(bij)为系数矩阵求得的最优解和用原系数矩阵求得的最优解相同。Page29(bij)n×n=01370606905320100匈牙利法：每行减去最小值每列减去最小值C=(cij)n×n=2151341041415914161378119Page30匈牙利法：利用这个性质，可使原系数矩阵变换为含有很多0元素的新系数矩阵，而最优解保持不变，在系数矩阵(bij)中，我们关心位于不同行不同列的0元素，以下简称为独立的0元素。若能在系数矩阵(bij)中找出n个独立的0元素；则令解矩阵(xij)中对应这n个独立的0元素的元素取值为1，其他元素取值为0。将其代入目标函数中得到zb=0，它一定是最小。这就是以(bij)为系数矩阵的指派问题的最优解。也就得到了原问题的最优解。Page31匈牙利法：克尼格定理:若矩阵A的元素可分为0和非0两部分，则覆盖0元素的最小直线数等于位于不同行和不同列的0元素（独立0元素）的个数。当覆盖0元素的最小直线数小于n时，就要从行和列结合的角度进一步产生等价的效率矩阵，并产生更多0元。从而找出n个位于不同行和不同列的0元素集合。找出n个位于不同行和不同列的0元素集合，也就是要使得覆盖矩阵的所有0元素的直线是n条。Page32匈牙利法---指派问题的求解步骤1)变换指派问题的系数矩阵(cij)为(bij)，使在(bij)的各行各列中都出现0元素，即从(cij)的每行元素都减去该行的最小元素；再从所得新系数矩阵的每列元素中减去该列的最小元素。若某行(列)已有0元素，那就不必再减了。2151341041415=914161378119ijcmin2497013112601011057401420042min01370606905320100Page33分配问题与匈牙利法例4.6有一份中文说明书，需译成英、日、