运筹学 北京邮电大学 课件ch5-1学习资料

运筹学OperationsResearch1.整数规划数学模型MathematicalModelof

IP2.分枝定界法BranchandBoundMethod3.割平面法cutting-plane

Method4.0－1规划

BinaryIntegerProgramming5.指派问题AssignmentProblemChapter5整数规划IntegerProgramming4/8/2025一个规划问题中要求部分或全部决策变量是整数，则这个规划称为整数规划。当要求全部变量取整数值的，称为纯整数规划；只要求一部分变量取整数值的，称为混合整数规划。如果模型是线性的，称为整数线性规划。本章只讨论整数线性规划。很多实际规划问题都属于整数规划问题.例如1.变量是人数、机器设备台数或产品件数等都要求是整数2.对某一个项目要不要投资的决策问题，可选用一个逻辑变量x，当x=1表示投资，x=0表示不投资；3.人员的合理安排问题，当变量xij=1表示安排第i人去做j工作，xij=0表示不安排第i人去做j工作。逻辑变量也是只允许取整数值的一类变量。4/8/2025【例5.1】某人有一背包可以装10公斤重、0.025m3的物品。他准备用来装甲、乙两种物品，每件物品的重量、体积和价值如表5－1所示。问两种物品各装多少件，所装物品的总价值最大？表5—1物品重量（公斤/每件）体积（m3/每件）价值(元/每件)甲乙1.20.80.0020.002543【解】设甲、乙两种物品各装x1、x2件，则数学模型为：(5.1)4/8/2025如果不考虑x1、x2取整数的约束（称为（5.1）的松弛问题），线性规划的可行域如图5—1中的阴影部分所示。图5－14/8/2025用图解法求得点B为最优解：X＝(3.57，7.14)，Z＝35.7。由于x1，x2必须取整数值，实际上整数规划问题的可行解集只是图中可行域内的那些整数点。用凑整法来解时需要比较四种组合，但（4，7）、（4，8）（3，8）都不是可行解，（3，7）虽属可行解，但代入目标函数得Z=33,并非最优。实际上问题的最优解是（5，5），Z=35。即两种物品各装5件，总价值35元。由图5－1知，点（5，5）不是可行域的顶点，直接用图解法或单纯形法都无法求出整数规划问题的最优解，因此求解整数规划问题的最优解需要采用其它特殊方法。还有些问题用线性规划数学模型无法描述，但可以通过设置逻辑变量建立起整数规划的数学模型。4/8/2025【例5.2】在例5.1中，假设此人还有一只旅行箱，最大载重量为12公斤，其体积是0.02m3。背包和旅行箱只能选择其一，建立下列几种情形的数学模型，使所装物品价值最大。（1）

所装物品不变；（2）

如果选择旅行箱，载重量和体积的约束为解：此问题可以建立两个整数规划模型，但用一个模型描述更简单。引入0－1变量（或称逻辑变量）yi，令i=1,2分别是采用背包及旅行箱装载。4/8/2025（1）

由于所装物品不变，式(8.1)约束左边不变，整数规划数学模型为（2）

由于不同载体所装物品不一样，数学模型为4/8/2025式中M为充分大的正数。从上式可知，当使用背包时(y1=1，y2=0)，式(b)和(d)是多余的；当使用旅行箱时(y1=0，y2=1)，式(a)和(c)是多余的。上式也可以令：同样可以讨论对于有m个条件互相排斥、有m（≤m、≥m）个条件起作用的情形。4/8/2025【例5.3】企业计划生产2000件某种产品，该种产品可利用Ａ、Ｂ、Ｃ设备中的任意一种加工。已知每种设备的生产准备结束费用、生产该产品时的单件成本以及每种设备限定的最大加工数量（件）如下表所示，试建立总成本最小的数学模型。设备生产准备结束费（元）生产成本（元／件）限定最大加工数（件）Ａ１００１０６００Ｂ３００２８００Ｃ２００５１２００4/8/2025【解】设xj表示在第j（j=1,2,3）种设备上加工的产品数量，其生产费用为：式中Kj是同产量无关的生产准备费用（即固定费用），cj是单位产品成本。设0－1变量yj，令目标函数为4/8/2025式中是一个特殊的约束条件，显然当xj>0时，yj=1,当xj＝0时，为使Z极小化，只有yj=0才有意义。用QSB软件求解得到：X＝（0，800，1200），Y＝（0，1，1），Z=8100.如果问题的所有变量取0或1，此问题称为0－1整数规划问题，简称0－1规划。4/8/2025【例5.4】指派问题或分配问题。人事部门欲安排四人到四个不同岗位工作，每个岗位一个人。经考核四人在不同岗位的成绩（百分制）如表5－3所示，如何安排他们的工作使总成绩最好。表5－3工作人员ABCD甲85927390乙95877895丙82837990丁869080884/8/2025【解】此工作分配问题可以采用枚举法求解，即将所有分配方案求出，总分最大的方案就是最优解。本例的方案有4！＝4×3×2×1＝24种，当人数和工作数较多时，方案数是人数的阶乘，计算量非常大。用0－1规划模型求解此类分配问题显得非常简单。设数学模型如下：目标函数为要求每人做一项工作，约束条件为4/8/202