整数规划(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 + ≤ + ≤ ≥ ≥ ⎧⎪⎨⎪⎩ 且为整数