《北邮运筹学ch5-1 整数规划数学模型》由会员分享，可在线阅读，更多相关《北邮运筹学ch5-1 整数规划数学模型（15页珍藏版）》请在金锄头文库上搜索。
1、运筹学 Operations Research1.整数规划数学模型Mathematical Model of IP 2 .分枝定界法 Branch and Bound Method 3. 割平面法 cutting-plane Method 4. 01规划 Binary Integer Programming 5. 指派问题 Assignment ProblemChapter 5 整数规划 Integer ProgrammingDate运筹学 北京邮电大学5.1 整数规划数学模型Mathematical Model of IP Ch5 Integer Programming Page 2 of
2、15一个规划问题中要求部分或全部决策变量是整数，则这个规划称为整数规划。当要求全部变量取整数值的，称为纯整数规划；只 要求一部分变量取整数值的，称为混合整数规划。如果模型是线性 的，称为整数线性规划。本章只讨论整数线性规划。 很多实际规划问题都属于整数规划问题.例如 1. 变量是人数、机器设备台数或产品件数等都要求是整数2. 对某一个项目要不要投资的决策问题，可选用一个逻辑 变量 x，当x=1表示投资，x=0表示不投资；3. 人员的合理安排问题，当变量xij=1表示安排第i人去做j 工作，xij=0表示不安排第i人去做j工作。逻辑变量也是只允许取整数值的一类变量。Date运筹学 北京邮电大学5
3、.1 整数规划数学模型Mathematical Model of IP Ch5 Integer Programming Page 3 of 15【例5.1 】某人有一背包可以装10公斤重、0.025m3的物品。他准备 用来装甲、乙两种物品，每件物品的重量、体积和价值如表51所 示。问两种物品各装多少件，所装物品的总价值最大？ 表51物品重量 （公斤/每件）体积 （m3/每件）价值 (元/每件)甲 乙1.2 0.80.002 0.00254 3【解】设甲、乙两种物品各装x1、x2件，则数学模型为：(5.1)Date运筹学 北京邮电大学5.1 整数规划数学模型Mathematical Model
4、of IP Ch5 Integer Programming Page 4 of 15如果不考虑x1、x2取整数的约束（称为（5.1）的松弛问题），线性 规划的可行域如图51中的阴影部分所示。图51Date运筹学 北京邮电大学5.1 整数规划数学模型Mathematical Model of IP Ch5 Integer Programming Page 5 of 15用图解法求得点B为最优解：X(3.57，7.14)，Z35.7。由于 x1，x2必须取整数值，实际上整数规划问题的可行解集只是图中可行 域内的那些整数点。用凑整法来解时需要比较四种组合，但（4，7 ）、（4，8）（3，8）都不是可
5、行解，（3，7）虽属可行解，但代 入目标函数得Z=33,并非最优。实际上问题的最优解是（5，5）， Z=35。即两种物品各装5件，总价值35元。由图51知，点（5，5）不是可行域的顶点，直接用图解法或单纯形法都无法求出整数规划问题的最优解，因此求解整数规划问 题的最优解需要采用其它特殊方法。还有些问题用线性规划数学模型无法描述，但可以通过设置逻辑变量建立起整数规划的数学模型。Date运筹学 北京邮电大学5.1 整数规划数学模型Mathematical Model of IP Ch5 Integer Programming Page 6 of 15【例5.2 】在例5.1中，假设此人还有一只旅行
6、箱，最大载重量为12 公斤，其体积是0.02m3。背包和旅行箱只能选择其一，建立下列几 种情形的数学模型，使所装物品价值最大。（1） 所装物品不变； （2） 如果选择旅行箱，载重量和体积的约束为解：此问题可以建立两个整数规划模型，但用一个模型描述更简单 。 引入01变量（或称逻辑变量）yi，令i=1,2分别是采用背包及旅行箱装载。Date运筹学 北京邮电大学5.1 整数规划数学模型Mathematical Model of IP Ch5 Integer Programming Page 7 of 15（1） 由于所装物品不变，式(8.1)约束左边不变，整数规划数学 模型为（2） 由于不同载体所
7、装物品不一样，数学模型为Date运筹学 北京邮电大学5.1 整数规划数学模型Mathematical Model of IP Ch5 Integer Programming Page 8 of 15式中M为充分大的正数。从上式可知，当使用背包时(y1=1，y2=0)，式(b)和(d)是多余的；当使用旅行箱时(y1=0，y2=1)，式(a)和(c)是多余的。上式也可以令：同样可以讨论对于有m个条件互相排斥、有m（m、m）个条件 起作用的情形。Date运筹学 北京邮电大学5.1 整数规划数学模型Mathematical Model of IP Ch5 Integer Programming Pag
8、e 9 of 15【例5.3 】企业计划生产2000件某种产品，该种产品可利用、 、设备中的任意一种加工。已知每种设备的生产准备结束费用、 生产该产品时的单件成本以及每种设备限定的最大加工数量（件） 如下表所示，试建立总成本最小的数学模型。设备生产准备结束 费（元）生产成本 （元件 ）限定最大加工 数（件）Date运筹学 北京邮电大学5.1 整数规划数学模型Mathematical Model of IP Ch5 Integer Programming Page 10 of 15【解】设xj表示在第j（j=1,2,3）种设备上加工的产品数量，其生产 费用为：式中Kj是同产量无关的生产准备费用（
9、即固定费用），cj是单位产 品成本。设01变量yj，令目标函数为Date运筹学 北京邮电大学5.1 整数规划数学模型Mathematical Model of IP Ch5 Integer Programming Page 11 of 15式中 是一个特殊的约束条件，显然当xj0时，yj=1, 当xj 0时，为使Z极小化，只有yj=0才有意义。用QSB软件求解得到：X（0，800，1200），Y（0，1，1）， Z=8100.如果问题的所有变量取0或1，此问题称为01整数规划问题，简称 01规划。Date运筹学 北京邮电大学5.1 整数规划数学模型Mathematical Model of I
10、P Ch5 Integer Programming Page 12 of 15【例5.4 】指派问题或分配问题。人事部门欲安排四人到四个不同 岗位工作，每个岗位一个人。经考核四人在不同岗位的成绩（百分 制）如表53所示，如何安排他们的工作使总成绩最好。 表53工作 人员ABCD甲85927390乙95877895丙82837990丁86908088Date运筹学 北京邮电大学5.1 整数规划数学模型Mathematical Model of IP Ch5 Integer Programming Page 13 of 15【解】此工作分配问题可以采用枚举法求解，即将所有分配方案 求出，总分最大的
11、方案就是最优解。本例的方案有 4！432124种，当人数和工作数较多时，方案数是人数的阶 乘，计算量非常大。用01规划模型求解此类分配问题显得非常简 单。设 数学模型如下： 目标函数为要求每人做一项工作，约束条件为Date运筹学 北京邮电大学5.1 整数规划数学模型Mathematical Model of IP Ch5 Integer Programming Page 14 of 15每项工作只能安排一人，约束条件为变量约束： Date运筹学 北京邮电大学5.1 整数规划数学模型Mathematical Model of IP Ch5 Integer Programming Page 15 of 15分枝定界法作业：教材P134 T5.4 5.5Exit1.线性整数规划模型的特征 2.什么是纯（混合）整数规划 3.01规划模型的应用 4.指派模型的特征及其应用Date运筹学 北京邮电大学
