大学精品课件：第五章(整数规划).ppt

1、2023-3-1浙江科技学院经济管理学院管工系1第五章第五章 整数规划整数规划5.1 5.1 整数规划数学模型和解的特点整数规划数学模型和解的特点5.2 5.2 割平面法割平面法5.3 5.3 分支定界法分支定界法5.4 0-15.4 0-1整数规划整数规划5.5 5.5 指派问题指派问题2023-3-1浙江科技学院经济管理学院管工系2本章学习要求本章学习要求p熟悉分支定界法和割平面法的原理及其应用熟悉分支定界法和割平面法的原理及其应用p掌握求解掌握求解0-1规划问题的建模及隐枚举法规划问题的建模及隐枚举法p掌握求解指派问题的匈牙利法掌握求解指派问题的匈牙利法2023-3-1浙江科技学院经济管

2、理学院管工系35.1整数规划数学模型和解的特点整数规划数学模型和解的特点n整数规划的类型整数规划的类型n整数规划的数学模型实例整数规划的数学模型实例n整数规划解的特点整数规划解的特点2023-3-1浙江科技学院经济管理学院管工系41.整数线性规划（整数线性规划（ILP）的类型）的类型2023-3-1浙江科技学院经济管理学院管工系5背包问题背包问题一只背包最大装载重量为一只背包最大装载重量为50公斤。现有三种物品，每公斤。现有三种物品，每种物品数量无限。每种物品每件的重量、价格如下表：种物品数量无限。每种物品每件的重量、价格如下表：物品物品1物品物品2物品物品3重量（公斤重量（公斤/件）件）10

3、4120价值（元价值（元/件）件）177235求背包中装入每种物品各多少件，使背包中物品总价值求背包中装入每种物品各多少件，使背包中物品总价值最高。最高。2.整数线性规划（整数线性规划（ILP）实例）实例2023-3-1浙江科技学院经济管理学院管工系6设三种物品的件数各为设三种物品的件数各为x1，x2，x3件，总价值为件，总价值为z。max z=17x1+72x2+35x3s.t.10 x1+41x2+20 x350 x1，x2，x30 x1，x2，x3为整数为整数这是一个整数规划问题（这是一个整数规划问题（Integer Programming）。）。这个问题的最优解为：这个问题的最优解为：

4、x1=1件，件，x2=0件，件，x3=2件，最高价值件，最高价值z=87元元物品物品1物品物品2物品物品3重量（公斤重量（公斤/件）件）104120价值（元价值（元/件）件）1772352023-3-1浙江科技学院经济管理学院管工系7再如：线性规划模型再如：线性规划模型max z=x1+4x2s.t.14x1+42x2196 -x1+2x2 5 x1,x20整数规划模型整数规划模型max z=x1+4x2s.t.14x1+42x2196 -x1+2x2 5 x1,x20 x1,x2 为整数为整数0 1 2 3 4 5 6 7 84321A(2.6,3.8)B(5,3)2023-3-1浙江科技学

5、院经济管理学院管工系8线性规划的最优解线性规划的最优解A(x1,x2)=(2.6,3.8)不是整数解，不是整数解，目标函数值为目标函数值为z=17.8。整数规划的最优解。整数规划的最优解B(x1,x2)=(5,3)目标函数值为目标函数值为z=17。线性规划最优解。线性规划最优解A(2.6,3.8)四舍五入得到的解为四舍五入得到的解为(3,4)，不是可行解；舍去尾数，不是可行解；舍去尾数取整的解为取整的解为(2,3)，目标函数值，目标函数值z=14。因此整数规划的最优解一般不能由线性规划的最优解因此整数规划的最优解一般不能由线性规划的最优解通过简单的取整得到。通过简单的取整得到。0 1 2 3

6、4 5 6 7 84321A(2.6,3.8)B(5,3)2023-3-1浙江科技学院经济管理学院管工系93.整数线性规划（整数线性规划（ILP）解的特点）解的特点2023-3-1浙江科技学院经济管理学院管工系105.2 割平面法割平面法2023-3-1浙江科技学院经济管理学院管工系11先不考虑整数要求求得对应先不考虑整数要求求得对应LP问题的最优解如下：问题的最优解如下：二、例：二、例：maxZ=4x1+3x2 4x1+5x220 2x1+x26 x1,x20，且为整数，且为整数cj4300CBXBB-1bx1x2x3x43x28/3011/3-2/34x15/310-1/65/6 j00-

7、1/3-4/3maxZ=4x1+3x2 4x1+5x220 2x1+x26 x1,x20，求得割平面方程：求得割平面方程：x3+x42，将其加入到原最终表中，将其加入到原最终表中，求新解。求新解。2023-3-1浙江科技学院经济管理学院管工系12cj4300CBXBB-1bX1X2X3X43x28/3011/3-2/34x15/310-1/65/6 j00-1/3-4/3 jX5X500-200-1-11 1000X2X1X33402001-112010-11/321001-1/6000-1-1/32023-3-1浙江科技学院经济管理学院管工系131、设原、设原ILP问题为问题为A，其相应，其

8、相应LP问题为问题为B，解，解B，B的最终表的最终表Xi为非整数，为非整数，xi+aijxj=bi2、选切割方程来源行、选切割方程来源行bi=Ni+fi aij=Nij+fij(其中其中Ni,Nij为整数，为整数，fi,fij(0,1),则则maxfi为切割方程来源行。为切割方程来源行。3、确定切割方程：、确定切割方程：fi fij xj04、将切割方程加到、将切割方程加到B的最终表上去，用对偶单纯形法求解，的最终表上去，用对偶单纯形法求解，如得到整数解，停止，否则，转如得到整数解，停止，否则，转2j=m+1nj=m+1n2023-3-1浙江科技学院经济管理学院管工系145.3 分支定界法分支

9、定界法2023-3-1浙江科技学院经济管理学院管工系15松弛问题没有可行解，松弛问题没有可行解，ILP也没有可行解，停止计算。也没有可行解，停止计算。松弛问题有最优解，并符合松弛问题有最优解，并符合ILP的整数条件，则此最优解即为的整数条件，则此最优解即为ILP的最优解，停止计算。的最优解，停止计算。松弛问题有最优解，但不符合松弛问题有最优解，但不符合ILP的整数条件，记它的目标函数值的整数条件，记它的目标函数值为为 ；ZZZZZ*2023-3-1浙江科技学院经济管理学院管工系16(11/4,9/4),Z=31/4(3,3/2),Z=15/2(2,2),Z=6无解无解无解无解例：例：且为整数0

10、,21260522121212121xxxxxxxxxxMaxZ(11/4,9/4)x12x13(2,2)(3,3/2)x21x22(19/6,1),Z=22/3(3,1),Z=7(19/6,1)x13x142023-3-1浙江科技学院经济管理学院管工系175.4 0-1整数规划整数规划一、问题的提出一、问题的提出n厂址选择问题厂址选择问题n多决策问题多决策问题n固定费用问题固定费用问题2023-3-1浙江科技学院经济管理学院管工系181.厂址选择模型厂址选择模型在在5个备选地点中选择个备选地点中选择3处建设生产同一产品的工厂，处建设生产同一产品的工厂，每个地点建厂所需投资，占用农田，建成以后

11、的生产能每个地点建厂所需投资，占用农田，建成以后的生产能力如下。总投资不超过力如下。总投资不超过800万元，占有农田不超过万元，占有农田不超过60亩。如何选择厂址，使总生产能力最大。亩。如何选择厂址，使总生产能力最大。建厂备选地点建厂备选地点12345所需投资（万元）所需投资（万元）320280240210180占有农田（亩）占有农田（亩）201815118生产能力（万吨）生产能力（万吨）7055422811设设5个个01变量变量x1，x2，x3，x4，x5，）（地建厂在地不建厂在54321ii1i0 xi,2023-3-1浙江科技学院经济管理学院管工系19max z=70 x1+55x2+4

12、2x3+28x4+11x5s.t.320 x1+280 x2+240 x3+210 x4+180 x5800 20 x1+18x2+15x3+11x4+8x5 60 x1+x2+x3+x4+x5=3x1，x2，x3，x4，x5 为为 01变量变量这个这个01规划问题的最优解为：规划问题的最优解为：x1=1，x2=0，x3=1，x4=1，x5=0，max z=140即在地点即在地点1、3和和4建建3个厂，总生产能力最大，可以达到个厂，总生产能力最大，可以达到140万吨。万吨。2023-3-1浙江科技学院经济管理学院管工系202.多决策问题多决策问题一个工厂用一个工厂用3种设备生产种设备生产5种产

13、品，三种设备的能力种产品，三种设备的能力（小时），生产每种产品需要占有的各种设备的能力（小时），生产每种产品需要占有的各种设备的能力（小时（小时/件）以及件）以及5种产品的利润（元种产品的利润（元/件）如下：件）如下：产品产品12345设备能力设备能力设备设备A5.01.03.02.04.01800设备设备B3.04.01.05.02500设备设备C3.02.01.03.02.02200利润利润2418211722求使总利润最大的生产计划。求使总利润最大的生产计划。2023-3-1浙江科技学院经济管理学院管工系21max z=24x1+18x2+21x3+17x4+22x5s.t.5.0 x1

14、+1.0 x2+3.0 x3+2.0 x4+4.0 x5 180 3.0 x2+4.0 x3+1.0 x4+5.0 x52500 3.0 x1+2.0 x2+1.0 x3+3.0 x4+2.0 x52200 x1，x2，x3，x4，x50 x1，x2，x3，x4，x5为整数为整数设五种产品产量之间有以下逻辑关系：设五种产品产量之间有以下逻辑关系：p五种产品中，安排生产的产品不能超过五种产品中，安排生产的产品不能超过3种种p每一种产品如果安排生产，最小批量为每一种产品如果安排生产，最小批量为50件件p如果产品如果产品1安排生产，产品安排生产，产品2就不能生产就不能生产p如果产品如果产品4生产，产

15、品生产，产品5必须生产，而且至少生产必须生产，而且至少生产50件件）（生产产品不生产产品5,4,3,2,110iiiyi设设5个个01变量变量y1，y2，y3，y4，y52023-3-1浙江科技学院经济管理学院管工系22max z=24x1+18x2+21x3+17x4+22x5s.t.5.0 x1+1.0 x2+3.0 x3+2.0 x4+4.0 x5 180 3.0 x2+4.0 x3+1.0 x4+5.0 x52500 3.0 x1+2.0 x2+1.0 x3+3.0 x4+2.0 x52200 y1+y2+y3+y4+y5 3 50y1x1My1 50y2x2My2 50y3x3My3

16、 50y4x4My4 50y5x5My5 y1+y21 y4y5 x1，x2，x3，x4，x50 x1，x2，x3，x4，x5为整数为整数 y1，y2，y3，y4，y5为为01变量变量2023-3-1浙江科技学院经济管理学院管工系233.固定费用问题固定费用问题即生产成本和产量成线性关系。如果产品不生产，不即生产成本和产量成线性关系。如果产品不生产，不发生任何成本，如果产品生产，则产量增加一倍，成本也发生任何成本，如果产品生产，则产量增加一倍，成本也增加一倍。这样的成本称为变动成本。增加一倍。这样的成本称为变动成本。在实际问题中，除了变动成本以外，还有固定成本。在实际问题中，除了变动成本以外，

17、还有固定成本。如果产品不生产，固定成本为如果产品不生产，固定成本为0，如果产品生产，就发生，如果产品生产，就发生固定成本，而且固定成本是一个常数，与产品产量无关。固定成本，而且固定成本是一个常数，与产品产量无关。有固定成本的最小化目标函数的表达式为有固定成本的最小化目标函数的表达式为njjjxcz1min一般的成本最小化目标函数表达式为一般的成本最小化目标函数表达式为0 xdxc0 x0jjjjjj种产品的成本第2023-3-1浙江科技学院经济管理学院管工系24产量产量成本成本固定成本固定成本变动成本变动成本产量产量成本成本变动成本变动成本设设n种设备，第种设备，第j种设备的产量为种设备的产量

18、为xj，设备运行的变动成本，设备运行的变动成本为为cj，设备开工的固定成本为，设备开工的固定成本为dj。引进。引进0-1变量变量y1，y2，yn，yj=0表示设备表示设备j不生产，不生产，yj=1表示设备表示设备j生产。生产。考虑变动成本和固定成本，使总成本最小化的目标函数为考虑变动成本和固定成本，使总成本最小化的目标函数为njjjnjjjydxcz11min设备开工与否与产量的逻辑关系，用以下约束条件表示设备开工与否与产量的逻辑关系，用以下约束条件表示xjMyj其中其中M为一个足够大的正数。为一个足够大的正数。2023-3-1浙江科技学院经济管理学院管工系25具有固定成本的最小生产费用问题具

19、有固定成本的最小生产费用问题炼焦厂以原煤为原料生产焦炭，同时得到焦炉煤气和煤炼焦厂以原煤为原料生产焦炭，同时得到焦炉煤气和煤焦油。有焦油。有4台炼焦炉，有关的数据为台炼焦炉，有关的数据为炼焦炉炼焦炉ABCD产产品品焦炭（吨焦炭（吨/吨原煤）吨原煤）0.640.680.710.73煤气（煤气（m3/吨原煤）吨原煤）23252728煤焦油（吨煤焦油（吨/吨原煤）吨原煤）0.120.150.170.19成成本本固定成本（元）固定成本（元）400120026003100变动成本（元变动成本（元/吨原煤）吨原煤）85817876要求焦炭产量不低于要求焦炭产量不低于280吨，煤气产量不低于吨，煤气产量不低

20、于10000m3，煤焦油产量不低于煤焦油产量不低于60吨，编制使总成本最低的生产计划。吨，编制使总成本最低的生产计划。2023-3-1浙江科技学院经济管理学院管工系26不考虑固定成本，使变动成本最小化不考虑固定成本，使变动成本最小化min z=85x1+81x2+78x3+76x4s.t.0.64x1+0.68x2+0.71x3+0.73x4280 23x1+25x2+27x3+28x410000 0.12x1+0.15x2+0.17x3+0.19x460 x1，x2，x3，x40最优解为：最优解为：x1=x2=0，x3=137.32，x4=250，max z=29711.272023-3-1

21、浙江科技学院经济管理学院管工系27考虑变动成本和考虑变动成本和固定成本固定成本，使总成本最小化。，使总成本最小化。Min z=85x1+81x2+78x3+76x4 +400y1+1200y1+2600y3+3100y4s.t.0.64x1+0.68x2+0.71x3+0.73x4280 23x1+25x2+27x3+28x4100000.12x1+0.15x2+0.17x3+0.19x460 x1My1x2My2x3My3x4My4x1，x2，x3，x40，y1，y2，y3，y4：0-1变量变量最优解为：最优解为：y1=0，y2=1，y3=0，y4=1 x1=0，x2=143.38，x3=0

22、，x4=250，max z=34913.972023-3-1浙江科技学院经济管理学院管工系28 例：某工厂接受某项产品定货，需求量为每日例：某工厂接受某项产品定货，需求量为每日3500公公斤，现有三种生产过程可供选择，各生产过程所需投斤，现有三种生产过程可供选择，各生产过程所需投资（成本）、生产成本、最大日产量如表所示如示，资（成本）、生产成本、最大日产量如表所示如示，工厂需要决定采用哪种生产过程和日产量多少公斤，工厂需要决定采用哪种生产过程和日产量多少公斤，才能既保证按合同交货，又使总成本最小，试建立这才能既保证按合同交货，又使总成本最小，试建立这个问题的数学模型。个问题的数学模型。生产过生

23、产过程种类程种类固定成本固定成本生产成本生产成本（元（元/公斤）公斤）最大日产量最大日产量甲甲100052000乙乙200043000丙丙3000340002023-3-1浙江科技学院经济管理学院管工系29设设Xj为第为第j 种生产过程的日产量种生产过程的日产量yj=1,采用第采用第j 种生产过程种生产过程 0，不采用第，不采用第j 种生产过程种生产过程Minz=5x1+4x2+3x3+1000y1+2000y2+3000y3 x1+x2+x3=3500 x12000y1 x23000y2 x34000y3 Xj 0,yj=1或或0，j=1,2,3生产过程生产过程种类种类固定成本固定成本生产成

24、本（元生产成本（元/公斤）公斤）最大日产量最大日产量甲甲100052000乙乙200043000丙丙3000340002023-3-1浙江科技学院经济管理学院管工系30二、0-1规划问题的解法规划问题的解法1、穷举法：、穷举法：例举变量取值为例举变量取值为0或或1的每一个组合，的每一个组合，比较目标函数值的大小以求得最有解。比较目标函数值的大小以求得最有解。例：例：max z=3x1+5x2-2x3s.t.x1-x2+2x32 x1+x2+4x34 x1 +x33 x2+4x36 xi=0,1，2023-3-1浙江科技学院经济管理学院管工系31（1,0,1)（1,0,0)（1,1,0)（0,1

25、,0)（0,0,1)（0,1,1)（0,0,0)（1,1,1)满足满足条条 件件约约 束束(x1,x2,x3)zmax z=3x1+5x2-2x3s.t.x1-x2+2x32 x1+x2+4x34 x1 +x33 x2+4x36 xi=0,1，0-2538*2023-3-1浙江科技学院经济管理学院管工系322、只检查变量取值组合的一部只检查变量取值组合的一部分，就能求得问题的最优解的方法。分，就能求得问题的最优解的方法。步骤：步骤：如求极大化问题，根据目标函数中变量系数如求极大化问题，根据目标函数中变量系数Cj的递增的递增顺序，对目标函数和约束不等式中的变量重新排序，找一顺序，对目标函数和约束

26、不等式中的变量重新排序，找一个可行解，其目标函数值定为过滤值。个可行解，其目标函数值定为过滤值。考察各变量的组合，若产生考察各变量的组合，若产生Z劣于此时的过滤值，则不劣于此时的过滤值，则不考虑，继续下一个组合，若优于此时的过滤值，则逐个考考虑，继续下一个组合，若优于此时的过滤值，则逐个考察是否满足约束条件，只要有一个不满足，则该组合为不察是否满足约束条件，只要有一个不满足，则该组合为不可行解，继续下一个组合；如果满足所有约束，则产生新可行解，继续下一个组合；如果满足所有约束，则产生新的过滤值，继续下一个组合。的过滤值，继续下一个组合。2023-3-1浙江科技学院经济管理学院管工系33例：例：

27、3,2,11064344225233221321321321jxxxxxxxxxxxxxxMaxZj，或(x2,x1,x3)Z值值约束约束条件条件Z过滤值过滤值（0,0,0)（0,0,1)（0,1,0)（1,0,0)（0,1,1)（1,0,1)（1,1,0)（1,1,1)3,2,110643434225323212312312312jxxxxxxxxxxxxxxMaxZj，或0055385-231658888所以，该问题的最有解为（所以，该问题的最有解为（0，1，1），最优值为，最优值为82023-3-1浙江科技学院经济管理学院管工系345.5 指派问题指派问题n标准指派问题的数学模型标准指派

28、问题的数学模型n匈牙利法步骤匈牙利法步骤n实例实例n非标准指派问题非标准指派问题2023-3-1浙江科技学院经济管理学院管工系35一一.标准指派问题的数学问题标准指派问题的数学问题 njixnixnjxxCMinZijnjijniijnjniijij,1,10,1,1,1,11111，或2023-3-1浙江科技学院经济管理学院管工系36二、匈牙利法原理二、匈牙利法原理 定理定理1：若效率矩阵（：若效率矩阵（cij）的每一行（列）各元的每一行（列）各元素中减去该行（列）的最小元素，得到新矩阵素中减去该行（列）的最小元素，得到新矩阵（cij），则以（，则以（cij）为效率矩阵求得指派问题）为效率矩

29、阵求得指派问题的最优解等同于以的最优解等同于以（cij）为效率矩阵的最优解。）为效率矩阵的最优解。独立独立0元素：不同行不同列的元素：不同行不同列的0元素元素 定理定理2：效率矩阵中独立：效率矩阵中独立 0元素的最多个数等于能元素的最多个数等于能覆盖所有覆盖所有0元素的最少直线数。元素的最少直线数。2023-3-1浙江科技学院经济管理学院管工系37三、匈牙利法步骤三、匈牙利法步骤2023-3-1浙江科技学院经济管理学院管工系38487151279171410691287671461069121060431180210730362101804036400000031202075311720483

30、14000010201010363106103831500010001000100000001000001372023-3-1浙江科技学院经济管理学院管工系39四四.非标准指派问题非标准指派问题2023-3-1浙江科技学院经济管理学院管工系40例：最大化指派问题例：最大化指派问题max=cijxij s.t.xij=1 i=1,5xij=1 j=1,5j=15i=15i=15j=15Xij=0,1 i=1,5,j=1,5B1B2B3B4B5A194685A2859106A397358A448695A51043682023-3-1浙江科技学院经济管理学院管工系41例：现有三个人可以完成五件工作，效率矩阵如下例：现有三个人可以完成五件工作，效率矩阵如下表，如允许一个人完成两件工作，且表，如允许一个人完成两件工作，且B5不允许由不允许由A1来完成，问如何指派？来完成，问如何指派？B1B2B3B4B5A14871512A279171410A3691287B1B2B3B4B5A1A2A3A1A2A3B648715M048715M079171410079171410069128706912870