华北理工大学：《运筹学》课程教学课件（讲稿）第5章 整数规划（Integer Programming）

整数规划(Integer Programming)整数规划的模型分枝定界法割平面法0-1整数规划指派问题

整 数 规划 (Integer Programming) 整数规划的模型 分枝定界法 割平面法 0－1 整数规划 指派问题

4.1整数规划问题的提出及其特点在线性规划与非线性规划模型中，变量的取值是在实数范围或在正实数范围。但是，在很多管理与经济活动中，要求所探讨的问题变量只能取整数值或取整数值中的一部分。如人数、机器台数、投资项目个数等，这时的非整数解就没有意义。如果一个规划模型中的变量有整数要求，则该规划模型就是整数规划模型

4.1 整数规划问题的提出及其特点

要求所有X，的解为整数，称为纯整数规划要求部分×的解为整数，称为混合整数规划要求x，只能取值0或1，称为0一1型整数规划对应没有整数解要求的线性规划称之为松弛问题整数规划的解是可数个的，最优解不一定发生在极点日整数规划的最优解不会优于其松弛问题的最优解nmax(min)f(x)=Ec,xj-1[24, (-,2),。 =-1,, ms.t.j-1且为整数，i=1,2nX,≥0

† 要求所有 xj 的解为整数，称为纯整数规划 † 要求部分 xj 的解为整数，称为混合整数规划 † 要求xj 只能取值 0 或 1，称为 0 — 1型整数规划 † 对应没有整数解要求的线性规划称之为松弛问题 † 整数规划的解是可数个的，最优解不一定发生在极点 † 整数规划的最优解不会优于其松弛问题的最优解 ⎪ ⎩ ⎪ ⎨ ⎧ ≥ = ≤ = ≥ = = ∑ ∑ = = x j n a x b i m s t f x c x j n j ij j i n j j j 0 , 1,2, , ( , ) , 1,2, , . . max(min) ( ) 1 1 L L 且为整数

整数规划问题的提出例5.1某公司拟建设A、B两种类型的生产基地若干个，两种类型的生产基地每个占地面积，所需经费，建成后生产能力及现有资源情况如表5-1所示问A、B类型基地各建设多少个，可使总生产能力最大？BA资源限制占地（m2）20005000130005424费用（万元）生产能力（百件2010/年）

一、整数规划问题的提出 † 例5.1 某公司拟建设A 、 B两种类型的生产基地若 干个，两种类型的生产基地每个占地面积，所需经 费，建成后生产能力及现有资源情况如表5-1所示。 问 A 、 B类型基地各建设多少个，可使总生产能力 最大？ 20 10 生产能力（百件 /年） 13000 24 5000 4 2000 5 占地（ m 2 ） 费用（万元） A B 资源限制

解设A、B两种类型基地各建设X，X个则其模型为：max z=20x,+10x,2x+5x≤135x+4x,≤24≥0,x≥0且为整数

† 解 设A、B两种类型基地各建设x1, x2个， 则其模型为： max 20 10 1 2 z = x x + 1 2 1 2 1 2 2 5 13 5 4 24 0, 0 x x x x x x + ≤ + ≤ ≥ ≥ ⎧⎪⎨⎪⎩ 且为整数

例52某服务部门各时段（每两小时为一时段）需要服务员人数见表5-2，按规定服务员连续连续8小时（即四个时段）为一班，现要求安排服务员的工作时间，使服务部门服务员总数最小。12567834时段7952810612服务员最少数目

† 例5.2 某服务部门各时段（每两小时为一时段） 需要服务员人数见表5-2，按规定服务员连续连 续8小时（即四个时段）为一班，现要求安排服 务员的工作时间，使服务部门服务员总数最小。 服务员最少 8 10 7 6 9 12 5 2 数目 时段 1 2 3 4 5 6 7 8

解：设在第i时段开始上班的服务员人数为x，由于第i时段开始时上班的服务员将在第i+3时段结束时下班，故决策变量只考虑，X2，X3，X4，Xminz=x+x,+x+x+x≥8X≥10X+X2≥7X+x+x≥6X+x+x+x≥9X+x+x+x≥12X+x+x≥5X+xs≥2Xs且取整数x≥0,j-1,2,345

解：设在第 j 时段开始上班的服务员人数为 j x ，由 于第 j 时段开始时上班的服务员将在第 j+3 时段结 束时下班，故决策变量只考虑 1 x ， 2 x ， 3 x ， 4 x ， 5 x min 12345 z = xxxxx ++++ 1 1 2 123 1234 234 5 34 5 4 5 5 8 10 7 6 9 12 5 2 0, 1,2,3, 4,5 j x x x xxx xxxx xxxx xxx x x x x j ⎧ ≥ ⎪ ⎪ + ≥ ⎪ ++ ≥ ⎪ ⎪ +++ ≥ ⎪⎪ ⎨ ++ + ≥ ⎪ ++ ≥ ⎪ ⎪ + ≥ ⎪ ⎪ ≥ ⎪ ⎪ ≥ = ⎩ 且取整数

例5.3某公司计划在m个地点建厂，可供选择的地点有A,A..A㎡，他们的生产能力分别是aj,a2.am（假设生产同一产品）。第工厂的建设费用为f,(i=1.2...m),又有n个地点B,B2，….B，需要销售这种产品，其销量分别为b,,b2..bn。从工厂运往销地的单位运费为Ci。试决定应在哪些地方建厂，即满足各地需要，又使总建设费用和总运输费用最省？

例5.3 某公司计划在m个地点建厂，可供选择 的地点有A1,A2.Am ，他们的生产能力分别 是a1,a2,.am（假设生产同一产品）。第i个 工厂的建设费用为fi (i=1.2.m),又有n个地 点B1,B2, . Bn 需要销售这种产品，其销量 分别为b1,b2.bn 。从工厂运往销地的单位 运费为Cij。试决定应在哪些地方建厂，即 满足各地需要，又使总建设费用和总运输 费用最省？

单生产销地建设BnB1B2K厂址.能力费用J1A1C /2aC 11Cin+A2:C 22C 21C2naα 2...............:..JAcC m1ca·:m 2mmnmmb销量b1b2...n

销量 建设 费用 生产 能力 单 销地 厂址 价 n m m m mn m m n n b b b A c c c a f A c c c a f A c c c a f B B Bn 1 2 1 2 2 21 22 2 2 2 1 11 12 1 1 1 1 2 L L M M M M M M L L L

设：x来表示从工厂运往销地的运量(i=1.2...mj=1.2... n),[1 在A,建又设(i=1.2...m )Y;=0 不在A,建厂模型：mmnZcx, +EfiyminZ二i=l j=li=1.Zx≤a,y, (i=1.2...m) j=1mZx, ≥b, (i =1...n)i=1X, ≥0. y, =0 或 1(i=1,2,.., m; j=1,2,.., n)

设： xij 表示从工厂运往销地的运量(i=1.2.m 、 j=1.2.n), 1 在 A i建厂 又设 Yi＝ （i=1.2.m ） 0 不在 A i建厂 模型： 11 1 1 1 min ( 1.2 ) (j 1.2 n) 0, 0 1 (i 1 2 m j 1 2 n) mn m ij ij i i ij i n ij i i j m ij j i ij i Z cx fy x ay i m x b x y == = = = = + ⎧ ≤ = ⎪ ⎪ ⎪ ⎨ ≥ = ⎪ ⎪ ≥= = = ⎪ ⎩ ∑∑ ∑ ∑ ∑ L L 或 ， ， ； ， ， L L