1、3.1 整数规划数学模型 Mathematical Model of IP3.2 整数规划的求解Solving Integer Programming 3.3 0 1规划的求解 Solving Binary Integer Programming 第 3章 整 数 规 划Integer Programming1第 3章整数规划线性规划的决策变量取值可以是任意非负实数，但许多实际问题中，只有当决策变量的取值为整数时才有意义。例如，产品的件数、机器的台数、装货的车数、完成工作的人数等，分数或小数解显然是不合理的。对某一个项目要不要投资的决策问题，可选用一个逻辑变量 x，当 x=1表示投资， x=0
2、表示不投资。3.1 整数规划的数学模型 纯整数规划 (IP)： xj全部取整数混合整数规划 (MIP)： xj部分取整数0-1整数规划 (BIP)：整数变量只能取 0或 1分类2第 3章整数规划【 例 3-1 】 某人有一背包可以装 10公斤重、 0.025m3的物品。他准备用来装甲、乙两种物品，每件物品的重量、体积和价值如表 3-1所示。问两种物品各装多少件，才能使所装物品的总价值最大？ 表 3-1【 解 】 设甲、乙两种物品各装 x1、 x2件，则数学模型为：(3-1)物品 重量（公斤 /件） 体 积 （ m3/件） 价 值 (元 /件 )甲乙1.20.80.0020.0025433.1
3、整数规划的数学模型 3第 3章整数规划【 补充例 】 投资决策问题。某公司有 5个项目被列入投资计划，各项目的投资额和期望的投资收益如下表3.1 整数规划的数学模型 该公司只有 600万元资金可用于投资，由于技术上的原因，投资受到以下约束：（ 1）在项目 1、 2和 3中必须且只有一项被选中；（ 2）项目 3和项目 4最多只能选中一项；（ 3）项目 5被选中的前提是项目 1必须被选中。如何在上述条件下选择一个最好的投资方案，使投资收益最大？项 目 投 资额 （万元） 投 资 收益（万元）1 210 1602 300 2103 150 604 130 805 260 1804第 3章整数规划【
4、解 】 设 xj 为选择第 j（ j=1,2,3,4,5)个项目的决策3.1 整数规划的数学模型 5第 3章整数规划【 例 3-2 】 在例 3-1中，假设此人还有一只旅行箱，最大载重量为 12公斤，其体积是 0.02m3。 背包和旅行箱只能选择其一，建立下列几种情形的数学模型，使所装物品价值最大。（ 1）所装物品不变；（ 2）如果选择旅行箱，则只能装载丙和丁两种物品，每件物品的重量、体积和价值如下表所示3.1 整数规划的数学模型 物品 重量（公斤 /件）体 积 （ m3/件） 价 值 (元 /件 )丙丁1.80.60.00150.002436第 3章整数规划【 解 】 （ 1）引入 0 1变
5、量 yj，令j=1,2分别是采用背包及旅行箱装载。3.1 整数规划的数学模型 (3-2)此问题也可以建立两个整数规划模型。7第 3章整数规划（ 2）由于不同载体所装物品不一样，数学模型为3.1 整数规划的数学模型 其中 M为充分大的正数。当使用背包时 ( y1=1, y2=0 )， 式 (b)和 (d)是多余的；当使用旅行箱时 ( y1=0, y2=1 )， 式 (a)和 (c)是多余的。背包约束旅行箱约束8第 3章整数规划（ 1）右端常数是 k个值中的一个时，类似式 (3-2)的约束条件为3.1 整数规划的数学模型 同样可以讨论对于有 m个条件互相排斥、有 m（ m、 m） 个条件起作用的情形。9第 3章整数规划（ 2）对于 m 个（组） 条件中有 k（ m）个（组）起作用时， 类似式 (3-3)的 约束条件写成这里 yi=1表示第 i 组约束不起作用（如 y1=1式 (3-3b)、(3-3d)不起作用）， yi=0表示第 i个约束起作用。当约束条件是 “” 符号时右端常数项应为3.1 整数规划的数学模型 10
