运筹学第五章-整数规划课件.ppt

1、5.1 整数规划实例及一般模型整数规划实例及一般模型5.2 分支定界法分支定界法5.3 0-1整数规划整数规划5.4 指派问题指派问题 例例5.15.1某公司拟用集装箱托运甲、乙两种货物，这两种货物每某公司拟用集装箱托运甲、乙两种货物，这两种货物每件的体积、重量、可获利润以及托运所受限制如下表所示。件的体积、重量、可获利润以及托运所受限制如下表所示。货物货物每件体积每件体积/立方英尺立方英尺每件重量每件重量/百千克百千克每件利润每件利润/百元百元甲甲19542乙乙273403托运限制托运限制1365140甲种货物至多托运甲种货物至多托运4 4件，问两种货物各托运多少件，可使获得利润最大？件，问

2、两种货物各托运多少件，可使获得利润最大？解解 设设x x1 1、x x2 2分别为甲、乙两种货物托运的件数，建立模型分别为甲、乙两种货物托运的件数，建立模型为整数21211212121,0,41404041365273195.32maxxxxxxxxxxtsxxz3整数规划问题的松弛问题整数规划问题的松弛问题 )n,2,1j(0 x)m,2,1i(b),(xa.stxczmax(min)jn1jijijn1jjjxj部分或全部取整数部分或全部取整数5.1.2 整数规划的一般模型整数规划的一般模型整数规划的类型整数规划的类型纯整数规划：纯整数规划：xj全部是整数全部是整数混合整数规划：混合整数规

3、划：xj部分是整数部分是整数0-1型整数规划：型整数规划：xj=0或或1 )n,2,1j(0 x)m,2,1i(b),(xa.stxczmax(min)jn1jijijn1jjjxj部分或全部取整数部分或全部取整数11max(min)(,)(1,2,).0(1,2,)njjjnijjijjzc xa xb imstxjn 整数规划问题的可行解集合是它的松弛问题可整数规划问题的可行解集合是它的松弛问题可行解集合的一个子集行解集合的一个子集;整数规划问题的最优解的目标函数值不会优于整数规划问题的最优解的目标函数值不会优于松弛问题的最优解的目标函数值松弛问题的最优解的目标函数值.且取整数0,8233

4、24max21212121xxxxxxxxz松弛问题最优解整数规划最优解不能通过舍入取整地方不能通过舍入取整地方法，由松弛问题的解得法，由松弛问题的解得到整数规划的最优解到整数规划的最优解0-1变量变量（逻辑变量（逻辑变量 Logical variable）：只能取：只能取值值0或或1的变量。的变量。0-1变量也称为逻辑变量。它常用变量也称为逻辑变量。它常用来表示决策时是否取某个特定方案，或者表示系来表示决策时是否取某个特定方案，或者表示系统是否处于某个特定状态，或者表示两个选项中统是否处于某个特定状态，或者表示两个选项中非此即彼的选择。非此即彼的选择。xj=1 当决策取方案当决策取方案 P

5、j 时时0 当决策不取方案当决策不取方案 Pj 时时例例5.5 广州某食品公司计划在市区的东、西、南、北四广州某食品公司计划在市区的东、西、南、北四区建立销售门市部，目前有区建立销售门市部，目前有10个位置可供选择，考虑个位置可供选择，考虑到各地区居民的消费水平及居民居住密集程度，规定：到各地区居民的消费水平及居民居住密集程度，规定：在东区由三个点中最多选择两个；在东区由三个点中最多选择两个；在西区由两个点中至少选择一个；在西区由两个点中至少选择一个；在南区由两个点中至少选择一个；在南区由两个点中至少选择一个；在北区由三个点中至少选择两个。在北区由三个点中至少选择两个。投资总额不能超过投资总额

6、不能超过720万元，问应该选择哪几个销售点，万元，问应该选择哪几个销售点，可使年利润为最大？可使年利润为最大？109876 5432161584825302022504036maxxxxxxxxxxxz.10,.,3,2,110021127201801501201001098765432110321ixxxxxxxxxxxxxxxxii变量，为且s.t.在东区由三个点中最多选择两个在西区由两个点中至少选择一个在南区由两个点中至少选择一个在北区由三个点中至少选择两个解解:设设 xj=1 当当A i点被选用点被选用;0 当当Ai点不被选用点不被选用2、0-1型变量常用来表示是否处于某个特定状态型变

7、量常用来表示是否处于某个特定状态l例例5.6 有三种资源被用于生产三种产品，资源量、产有三种资源被用于生产三种产品，资源量、产品单件可变费用及售价、资源单耗量及组织三种产品品单件可变费用及售价、资源单耗量及组织三种产品生产的固定费用见下表。要求制定一个生产计划，使生产的固定费用见下表。要求制定一个生产计划，使总收益最大。总收益最大。产品产品1产品产品2产品产品3a11机床机床1a13机床机床3a14机床机床4a21机床机床1a22机床机床2a24机床机床4a32机床机床2a33机床机床31 同一同一件产品件产品在不同在不同机床上机床上的加工的加工顺序顺序同一件产品在下一台机床上加工的开始时间不

8、得早同一件产品在下一台机床上加工的开始时间不得早于在上一台机床上加工的结束时间于在上一台机床上加工的结束时间xij表示第表示第i种产品在第种产品在第j台机床上加工的开始时间。台机床上加工的开始时间。产品产品1：x11+a11 x13 及及 x13+a13 x14产品产品2：x21+a21 x22 及及 x22+a22 x24产品产品3：x32+a32 x33l例例5.7 5.7 用用4 4台机床加工台机床加工3 3件产品。各产品的机床加工顺序，以及产品在机件产品。各产品的机床加工顺序，以及产品在机床上的加工工时见下表，且要求工件二的总工时不超过床上的加工工时见下表，且要求工件二的总工时不超过d

9、 d。现要求确定。现要求确定各件产品在机床上的加工方案各件产品在机床上的加工方案,使在最短的时间内加工完全部产品使在最短的时间内加工完全部产品.两个选项中非此即彼的选择两个选项中非此即彼的选择2 每台机每台机床对不同床对不同产品的加产品的加工顺序约工顺序约束束一台机床在工作中，若已开始的加工还未结束，则一台机床在工作中，若已开始的加工还未结束，则不能开始加工另一产品。不能开始加工另一产品。注意到每台机床可以加工两种产品。因此可以用注意到每台机床可以加工两种产品。因此可以用0-1变量变量yi表示第表示第i台机床加工产品的顺序。具体表示台机床加工产品的顺序。具体表示y1y2y3y40先加工先加工产

10、品产品11先加工先加工产品产品20先加工先加工产品产品21先加工先加工产品产品30先加工先加工产品产品11先加工先加工产品产品30先加工先加工产品产品11先加工先加工产品产品2机床机床1 x11+a11 x21+My1 及及 x21+a21 x11+M(1-y1)机床机床2 x22+a22 x32+My2 及及 x32+a32 x22+M(1-y2)机床机床3 x13+a13 x33+My3 及及 x33+a33 x13+M(1-y3)机床机床4 x14+a14 x24+My4 及及 x24+a24 x14+M(1-y4)互斥的互斥的约束条件约束条件3 产品产品2的加工总的加工总时间约束时间约

11、束产品产品2加工开始的时间是加工开始的时间是x21，结束加工的时间是，结束加工的时间是x24+a24，于是，于是x24+a24 x21 d4 目标函目标函数的建立数的建立设全部产品加工结束时间为设全部产品加工结束时间为W。由于三件产品的加工结束时间分别为由于三件产品的加工结束时间分别为x14+a14,x24+a24,x33+a33 故故W=max(x14+a14,x24+a24,x33+a33)根据问题的要求，目标函数为根据问题的要求，目标函数为min z=W满足满足W x14+a14W x24+a24W x33+a33从而最后得到从而最后得到p140的混合整数线性规划模型的混合整数线性规划模

12、型l例例5.3 某企业在某企业在A1地已有一个工厂，其产品的生产能力为地已有一个工厂，其产品的生产能力为30千箱，为千箱，为了扩大生产，打算在了扩大生产，打算在A2，A3，A4，A5地中再选择几个地方建厂，已知地中再选择几个地方建厂，已知在在A2地建厂的固定成本为地建厂的固定成本为175千元，在千元，在A3地建厂的固定成本为地建厂的固定成本为300千元，千元，在在A4地建厂的固定成本为地建厂的固定成本为375千元，在千元，在A5地建厂的固定成本为地建厂的固定成本为500千元，千元，另外，在另外，在A1的产量，的产量，A2，A3，A4，A5建成厂的产量，那时销地的销建成厂的产量，那时销地的销量以

13、及产地到销地的单位运价（每千箱运费）如下表量以及产地到销地的单位运价（每千箱运费）如下表5-3所示。问应所示。问应该在哪几个地方建厂，在满足销量的前提下，使得其总的固定成本和该在哪几个地方建厂，在满足销量的前提下，使得其总的固定成本和总的运输费用之和最小？总的运输费用之和最小？如果A2和A3两地必须有且只有一个建厂，怎么办？枚举法：列出变量取值为枚举法：列出变量取值为0或或1的可能的组合（若有的可能的组合（若有n个变量则有个变量则有2n个组合），再逐一验证它们是否满足约束个组合），再逐一验证它们是否满足约束条件，然后对满足约束条件的可行解计算目标函数值，条件，然后对满足约束条件的可行解计算目标

14、函数值，其中目标函数值最优的就是最优解其中目标函数值最优的就是最优解方法的改进：若已发现一个可行解，则根据它的目标方法的改进：若已发现一个可行解，则根据它的目标函数值可以产生一个过滤条件函数值可以产生一个过滤条件（filtering constraint），），对于目标函数值比它差的变量组合就不必再去检验它的对于目标函数值比它差的变量组合就不必再去检验它的可行性。只要发现某个变量组合不满足其中一个约束条可行性。只要发现某个变量组合不满足其中一个约束条件，就不必再去检验其他约束条件是否可行。件，就不必再去检验其他约束条件是否可行。隐枚举法隐枚举法解解 为提高搜索效率，减少运算量，先按照目标函数中

15、为提高搜索效率，减少运算量，先按照目标函数中各变量系数的大小顺序重新排列各变量。各变量系数的大小顺序重新排列各变量。排为排为x3,x2,x1。(x3,x2,x1)z值值约束条件约束条件过滤条件过滤条件abcd0，0，00，0，10，1，00，1，11，0，01，0，11，1，01，1，100z22z1不检验3不检验-1不检验1不检验0不检验2不检验max z=-x3+x2+2x1所以最优解是（所以最优解是（x1,x2,x3）T=(1,0,0)T,max z=2n项不同的任务，需要项不同的任务，需要n个人分别完成其中的一项，但由于个人分别完成其中的一项，但由于任务的性质和每个人的专长不同，因此，

16、每个人去完成不任务的性质和每个人的专长不同，因此，每个人去完成不同的任务的效率（或花费的时间、费用）也就不同，于是同的任务的效率（或花费的时间、费用）也就不同，于是产生了一个问题，应指派哪个人去完成哪项任务，使完成产生了一个问题，应指派哪个人去完成哪项任务，使完成n项任务的总效率最高（或所需时间最短、费用最少）。项任务的总效率最高（或所需时间最短、费用最少）。这类问题称为这类问题称为指派问题指派问题。应该指派哪个人应该指派哪个人完成哪个任务？完成哪个任务？如何将如何将n n个零件分配个零件分配到到n n台设备进行加工台设备进行加工？指派问题的标准形式为：今分配指派问题的标准形式为：今分配n n

17、个人去完个人去完成成n n项任务，每个人只能完成一项任务，每项项任务，每个人只能完成一项任务，每项任务只能由一个人来完成，第任务只能由一个人来完成，第i i个人来完成第个人来完成第j j项任务的费用或时间为项任务的费用或时间为 ，问如何安排才能使，问如何安排才能使总费用或总时间最小？总费用或总时间最小？ijcl例例5.9 有四个工人，要分别指派他们完成四项不同的工作，有四个工人，要分别指派他们完成四项不同的工作，每人做各项工作所消耗的时间每人做各项工作所消耗的时间(我们称之为消耗系数矩阵、我们称之为消耗系数矩阵、效率矩阵或系数矩阵效率矩阵或系数矩阵)如表如表5-6所示，问应如何分配任务，所示，

18、问应如何分配任务，才能使总的消耗时间最少？才能使总的消耗时间最少？ABCD甲甲15172124乙乙19232218丙丙26171619丁丁192123171 若指派第若指派第i 人做第人做第j 事事0 若不指派第若不指派第i 人做第人做第j 事事 解：令解：令 xij=（i,j=1,n）满足约束条件的可行解满足约束条件的可行解也可写成矩阵形式，称也可写成矩阵形式，称为为解矩阵解矩阵。如例。如例5.95.9的一的一个可行解矩阵是个可行解矩阵是:1000000101000010)(ijx 每个人只能完每个人只能完成一项任务成一项任务每项任务只能由每项任务只能由一个人来完成一个人来完成数学模型：数学

19、模型：1 若指派第若指派第i 人做第人做第j 事事0 若不指派第若不指派第i 人做第人做第j 事事 令令 xij=（i,j=1,n）n,2,1j,i10 xn,2,1i1xn,2,1j1xxczminijn1jijn1iijn1in1jijij 或或st.标准形式指派问题的数学模型标准形式指派问题的数学模型指派问题是一类特殊的整数规划问题。指派问题是运指派问题是一类特殊的整数规划问题。指派问题是运输问题的特例，也是线性规划（输问题的特例，也是线性规划（0 1规划）的特例，规划）的特例，当然可用求运输问题、整数规划或当然可用求运输问题、整数规划或0-1规划的解法去规划的解法去求解。这就如同用单纯

20、形法求运输问题一样是不合算求解。这就如同用单纯形法求运输问题一样是不合算的。利用指派问题的特点可有更简便的解法的。利用指派问题的特点可有更简便的解法。1955年，库恩（年，库恩（W.W.Kuhn）提出了求解指派问题）提出了求解指派问题的一种算法，习惯上称之为匈牙利算法。的一种算法，习惯上称之为匈牙利算法。定理定理5.1:如果对系数矩阵如果对系数矩阵C=(cij)nn的任一行的任一行（列）各元素减去该行（列）的最小元素，得（列）各元素减去该行（列）的最小元素，得到新矩阵到新矩阵B=(bij)nn，则以，则以B为系数矩阵的指为系数矩阵的指派问题的最优解也是原问题的最优解。派问题的最优解也是原问题的

21、最优解。匈牙利算法的步骤匈牙利算法的步骤l步骤步骤1：变换指派问题的系数矩阵：变换指派问题的系数矩阵l步骤步骤2：试指派：试指派l步骤步骤3：判断最优性：判断最优性l步骤步骤4：调整后返回步骤：调整后返回步骤215172124192322182617161919212317C每行减该行最小数每行减该行最小数02691540101032460每列减该列最小数每列减该列最小数01691440100032360步骤步骤1：变换指派问题的系数矩阵（：变换指派问题的系数矩阵（cij）为）为(bij)，使在，使在(bij)的各行各列中都出现的各行各列中都出现0元素，即元素，即 (1)从（从（cij）的每行

22、元素都减去该行的最小元素；）的每行元素都减去该行的最小元素；(2)再从所得新系数矩阵的每列元素中减去该列的最再从所得新系数矩阵的每列元素中减去该列的最小元素小元素01691440100032360此时独立零元素有此时独立零元素有3个，第四行没有，故转入步骤个，第四行没有，故转入步骤4。步骤步骤2：试指派：试指派 将只有一个将只有一个0元素的行（列）的元素的行（列）的0最先画圈，称其为独立零最先画圈，称其为独立零元素。然后将其所在列（行）其它的元素。然后将其所在列（行）其它的0划掉。然后继续寻找，划掉。然后继续寻找，直到尽可能多的直到尽可能多的0元素都被圈出和划掉为止。元素都被圈出和划掉为止。若

23、仍有没有划圈的若仍有没有划圈的0元素，且同行同列的元素，且同行同列的0元素至少有两个，元素至少有两个，则从剩有则从剩有0元素最少的行元素最少的行(列列)开始，比较这行各开始，比较这行各0元素所在列中元素所在列中0元素的数目，选择元素的数目，选择0元素少的那列的这个元素少的那列的这个0元素加圈元素加圈(表示选择表示选择性多的要性多的要“礼让礼让”选择性少的选择性少的)。然后划掉同行同列的其它。然后划掉同行同列的其它0元元素。可反复进行，直到所有素。可反复进行，直到所有0元素都已圈出和划掉为止。元素都已圈出和划掉为止。步骤步骤3：判断最优性：判断最优性如果独立零元素的个数等于如果独立零元素的个数等

24、于n计算停止，计算停止，按照独立零元素对应的位置进行指派即可。按照独立零元素对应的位置进行指派即可。否则进入下一步进行调整。否则进入下一步进行调整。步骤步骤4：调整：调整 任意选择一个没有独立零元素的行，将该行所有元素任意选择一个没有独立零元素的行，将该行所有元素减去该行除减去该行除0外的最小数外的最小数(m)；然后该行的；然后该行的0将会变为负数，将会变为负数，为了将负数删除，我们将该行为了将负数删除，我们将该行0所对应的列的所有元素都所对应的列的所有元素都加上加上m；则原来的所在的列中的则原来的所在的列中的0会被变为正数。为了使会被变为正数。为了使0所在行能够找到新的所在行能够找到新的0，

25、须让该行所有元素再减去除，须让该行所有元素再减去除0外的外的最小数。如果此时没有出现负数，调整结束；否则继续使最小数。如果此时没有出现负数，调整结束；否则继续使负数所在列加上一个常数，继续循环。负数所在列加上一个常数，继续循环。直到系数矩阵中直到系数矩阵中没有负数，此时调整结束，重新回到没有负数，此时调整结束，重新回到step2。01691440100032360l第四行没有独立零元素，所第四行没有独立零元素，所以让该行减以让该行减2l第四行第四列的第四行第四列的0变为变为-2，所以让第四列再加所以让第四列再加2l第四列的独立零元素被破坏，第四列的独立零元素被破坏，所以让第二行再减所以让第二行

26、再减1-2-1016110331100050140+2+2016110331100050140此时独立零元素还是只有此时独立零元素还是只有3个，第二行没有，故转个，第二行没有，故转入步骤入步骤5。l第二行没有独立零元素，第二行没有独立零元素，所以让该行减所以让该行减1l第二行第一列的第二行第一列的0变为变为-1，所以让第一列再加所以让第一列再加1l第一列的独立零元素被破第一列的独立零元素被破坏，所以让第一行再减坏，所以让第一行再减1-1-1016110331100050140005100220110051140+1+1005100220110051140此时找到了此时找到了4个独立零元素，所以

27、最优方案为：个独立零元素，所以最优方案为：01001000*00100001X6917161917*z 65325746798596811练习题：练习题：1723211919161726182223192421181519*Z 70*Z 5.6(1)1615121115141615171612131210974410002144014320-1+1+1-13300002244023210-3-3-2+3+30000005511021021Z=481、最大化指派问题：目标函数求、最大化指派问题：目标函数求max nn2n1nn22221n11211cccccccccC nn2n1nn22221n

28、11211cmcmcmcmcmcmcmcmcmB最大元素：最大元素：m将原系数矩阵将原系数矩阵C转换为转换为B有有5个工人，要指派去做个工人，要指派去做5项工作，每人做各项工作的项工作，每人做各项工作的能力见下表。应如何指派，才能使总的得分最大？能力见下表。应如何指派，才能使总的得分最大？J1J2J3J4J5S1S2S3S4S51551712511012931313080853912106812工人工作12989128130127651301108131151203515C367637215389102151457241031512100m-cij03430501316780131235028

29、31512100034205013067801212350183151290-3+3-10041080162975011123200831212801000001000001000001000001*X64*z2、人数、人数事数事数人数人数事数：添加虚拟事数：添加虚拟“事事”，c=03、一个人可以做几件事、一个人可以做几件事将一人化为相同的多个人来接受指派，这多个人做将一人化为相同的多个人来接受指派，这多个人做同一件事的费用相同同一件事的费用相同4、某事不能由某人来做、某事不能由某人来做 将相应的费用系数取无穷大将相应的费用系数取无穷大M例例5.12 某大型工程共由某大型工程共由5个项目个项目

30、A、B、C、D、E组成，现有三个公司甲、乙、丙分别来投标，各组成，现有三个公司甲、乙、丙分别来投标，各自给出的报价如下表所示。这里甲乙丙三家公司自给出的报价如下表所示。这里甲乙丙三家公司实力均比较雄厚，可以同时进行两个项目的施工，实力均比较雄厚，可以同时进行两个项目的施工，请给出最优施工分配方案。请给出最优施工分配方案。ABCDE甲甲151791218乙乙1418101116丙丙12191213151517912180151791218014181011 16014181011 1601219121315012191213150C*010000001000000100000001000010100000X15131219121611101814181291715C一人做两事一人做两事1513121912151312191216111018141611101814181291715181291715C人多事少人多事少