1、3.1 整数规划数学模型 Mathematical Model of IP3.2 纯整数规划的求解 Solving Pure Integer Programming 3.3 0 1规划的求解 Solving Binary Integer Programming Chapter 3 整数规划Integer Programming运筹学Operations ResearchDate3.1 整数规划数学模型Mathematical Model of IPDateCh3 整数规划Integer Programming 制作与教学武汉 理工大学 管理学院 熊伟 Page 3 一个规划问题中要求部分或全部
2、决策变量是整数，则这个规划称为整数规划。当要求全部变量取整数值的，称为纯整数规划；只要求一部分变量取整数值的，称为混合整数规划。如果模型是线性的，称为整数线性规划。本章只讨论整数线性规划。 很多实际规划问题都属于整数规划问题1. 变量是人数、机器设备台数或产品件数等都要求是整数2. 对某一个项目要不要投资的决策问题，可选用一个逻辑变量 x，当 x=1表示投资， x=0表示不投资；3. 人员的合理安排问题，当变量 xij=1表示安排第 i人去做 j工作， xij=0表示不安排第 i人去做 j工作。逻辑变量也是只允许取整数值的一类变量。3.1 整数规划的数学模型Mathematical Model
3、 of IP DateCh3 整数规划Integer Programming 制作与教学武汉 理工大学 管理学院 熊伟 Page 4 【 例 3-1 】 某人有一背包可以装 10公斤重、 0.025m3的物品。他准备用来装甲、乙两种物品，每件物品的重量、体积和价值如表 3-1所示。问两种物品各装多少件，所装物品的总价值最大？表 3-1【 解 】 设甲、乙两种物品各装 x1、 x2件，则数学模型为：(3-1)3.1 整数规划的数学模型Mathematical Model of IP 物品 重量（公斤 /每件） 体 积（ m3/每件） 价 值(元 /每件 )甲乙1.20.80.0020.00254
4、3DateCh3 整数规划Integer Programming 制作与教学武汉 理工大学 管理学院 熊伟 Page 5 如果不考虑 x1、 x2取整数的约束（称为（ 3-1）的松弛问题），线性规划的可行域如图 3-1中的阴影部分所示。3.1 整数规划的数学模型Mathematical Model of IP 图 3-1DateCh3 整数规划Integer Programming 制作与教学武汉 理工大学 管理学院 熊伟 Page 6 用图解法求得点 B为最优解： X (3.57， 7.14)， Z 35.7。由于 x1， x2必须取整数值，实际上整数规划问题的可行解集只是图中可行域内的那些
5、整数点。用凑整法来解时需要比较四种组合，但（ 4， 7）、（ 4， 8）（ 3， 8）都不是可行解，（ 3， 7）虽属可行解，但代入目标函数得 Z=33,并非最优。实际上问题的最优解是（ 5， 5）， Z=35。 即两种物品各装 5件，总价值 35元。由图 3 1知，点（ 5， 5）不是可行域的顶点，直接用图解法或单纯形法都无法求出整数规划问题的最优解，因此求解整数规划问题的最优解需要采用其它特殊方法。还有些问题用线性规划数学模型无法描述，但可以通过设置逻辑变量建立起整数规划的数学模型。3.1 整数规划的数学模型Mathematical Model of IP DateCh3 整数规划Inte
6、ger Programming 制作与教学武汉 理工大学 管理学院 熊伟 Page 7 【 例 3-2 】 在例 3-1中，假设此人还有一只旅行箱，最大载重量为 12公斤，其体积是 0.02m3。 背包和旅行箱只能选择其一，建立下列几种情形的数学模型，使所装物品价值最大。（ 1）所装物品不变；（ 2）如果选择旅行箱，则只能装载丙和丁两种物品，价值分别是 4和 3，载重量和体积的约束为【 解 】 此问题可以建立两个整数规划模型，但用一个模型描述更简单。引入 0 1变量（或称逻辑变量） yi，令i=1,2分别是采用背包及旅行箱装载。3.1 整数规划的数学模型Mathematical Model o
7、f IP DateCh3 整数规划Integer Programming 制作与教学武汉 理工大学 管理学院 熊伟 Page 8 （ 1） 由于所装物品不变，式 (3-1)约束左边不变，整数规划数学模型为（ 2） 由于不同载体所装物品不一样，数学模型 为3.1 整数规划的数学模型Mathematical Model of IP DateCh3 整数规划Integer Programming 制作与教学武汉 理工大学 管理学院 熊伟 Page 9 式中 M为充分大的正数。从上式可知，当使用背包时 (y1=1，y2=0)， 式 (b)和 (d)是多余的；当使用旅行箱时 (y1=0， y2=1)，
8、式(a)和 (c)是多余的。上式也可以令：同样可以讨论对于有 m个条件互相排斥、有 m（ m、 m） 个条件起作用的情形。3.1 整数规划的数学模型Mathematical Model of IP DateCh3 整数规划Integer Programming 制作与教学武汉 理工大学 管理学院 熊伟 Page 10 （ 1)右端常数是 k个值中的一个时，类似式 (3-2)的约束条件为（ 2)对于 m组 条件中有 k（ m）组起作用时， 类似式 (3-3)的约束条件写成这里 yi=1表示第 i组约束不起作用（如 y1=1式 (3-3b)、 (3-3d)不起作用）， yi=0表示第 i个约束起作用。当约束条件是 “” 符号时右端常数项应为（ 3) 对于 m个 条件中有 k（ m）个起作用时，约束条件写成3.1 整数规划的数学模型Mathematical Model of IP Date
