《Chapter 5 整数规划99975263.ppt》由会员分享，可在线阅读，更多相关《Chapter 5 整数规划99975263.ppt（60页珍藏版）》请在金锄头文库上搜索。
1、,5.1 整数规划数学模型 Mathematical Model of IP 5.2 纯整数规划的求解 Solving Pure Integer Programming 5.3 01规划的求解 Solving Binary Integer Programming,Chapter 5 整数规划 Integer Programming,运筹学 Operations Research,5.1 整数规划数学模型 Mathematical Model of IP,2019年5月23日星期四,整数线性规划,实际生产中的整数规划问题：,1. 变量是人数、机器设备台数或产品件数等都要求是整数 2. 对某一个项
2、目要不要投资的决策问题，可选用一个逻辑变量 x，当x=1表示投资，x=0表示不投资； 3. 人员的合理安排问题，当变量xij=1表示安排第i人去做j工作，xij=0表示不安排第i人去做j工作。逻辑变量也是只允许取整数值的一类变量。,3.1 整数规划的数学模型 Mathematical Model of IP,一个规划问题,纯整数规划,混合整数规划,线性模型,2019年5月23日星期四,【例5.1 】某人有一背包可以装10公斤重、0.025m3的物品。他准备用来装甲、乙两种物品，每件物品的重量、体积和价值如表3-1所示。问两种物品各装多少件，所装物品的总价值最大？,表5-1,【解】设甲、乙两种物
3、品各装x1、x2件，则数学模型为：,(5.1),3.1 整数规划的数学模型 Mathematical Model of IP,2019年5月23日星期四,如果不考虑x1、x2取整数的约束（称为（5.1）的松弛问题），线性规划的可行域如图5-1中的阴影部分所示。,3.1 整数规划的数学模型 Mathematical Model of IP,图5-1,整数规划问题的可行解集只是图中可行域内的那些整数点。 用凑整法来解时需要比较四种组合，但（4,7）、（4,8）、（3,8）都不是可行解，（3,7）虽属可行解，但代入目标函数得Z=33,并非最优。 问题的最优解是（5,5），Z=35。即两种物品各装5件
4、，总价值35元。,2019年5月23日星期四,由图5-1知，点（5,5）不是可行域的顶点，直接用图解法或单纯形法都无法求出整数规划问题的最优解，因此求解整数规划问题的最优解需要采用其它特殊方法。 还有些问题用线性规划数学模型无法描述，但可以通过设置逻辑变量建立起整数规划的数学模型。,3.1 整数规划的数学模型 Mathematical Model of IP,2019年5月23日星期四,【例5.2 】在例5.1中，假设此人还有一只旅行箱，最大载重量为12公斤，其体积是0.02m3。背包和旅行箱只能选择其一，建立下列几种情形的数学模型，使所装物品价值最大。 （1）所装物品不变； （2）如果选择旅
5、行箱，则只能装载丙和丁两种物品，价值分别是4和3，载重量和体积的约束为,【解】此问题可以建立两个整数规划模型，但用一个模型描述更简单。引入0-1变量（或称逻辑变量）yi，令,i=1,2分别是采用背包及旅行箱装载。,3.1 整数规划的数学模型 Mathematical Model of IP,2019年5月23日星期四,（1） 由于所装物品不变，式(5.1)约束左边不变，整数规划数学模型为,（2）由于不同载体所装物品不一样，数学模型为,3.1 整数规划的数学模型 Mathematical Model of IP,式中M为充分大的正数。 从上式可知，当使用背包时(y1=1，y2=0)，式(b)和(
6、d)是多余的； 当使用旅行箱时(y1=0，y2=1)，式(a)和(c)是多余的。上式也可以令：,2019年5月23日星期四,同样可以讨论对于有m个条件互相排斥、有k（m、m）个条件起作用的情形。 （1）右端常数是k个值中的一个时，类似式（5.2）的约束条件为,3.1 整数规划的数学模型 Mathematical Model of IP,（2）对于m组条件中有k（m）组起作用时，类似式(5.3)的约束条件写成,这里yi=1表示第i组约束不起作用（如y1=1式(5.3b)、(5.3d)不起作用），yi=0表示第i个约束起作用。当约束条件是“”符号时右端常数项应为,2019年5月23日星期四,（3）
7、对于m个条件中有k（m）个起作用时，约束条件写成,3.1 整数规划的数学模型 Mathematical Model of IP,【例5.3】试引入01变量将下列各题分别表达为一般线性约束条件 （1）x1+x26或4x1+6x210或2x1+4x220 （2）若x15，则x20，否则x28 （3）x2取值0，1，3，5，7,【解】 （1）3个约束只有1个起作用,或,2019年5月23日星期四,（3）右端常数是5个值中的1个,3.1 整数规划的数学模型 Mathematical Model of IP,（2）两组约束只有一组起作用,题：（1）x1+x26或4x1+6x210或2x1+4x220 （
8、2）若x15，则x20，否则x28 （3）x2取值0，1，3，5，7,2019年5月23日星期四,【例5.4】企业计划生产4000件某种产品，该产品可自己加工、外协加工任意一种形式生产已知每种生产的固定费用、生产该产品的单件成本以及每种生产形式的最大加工数量（件）限制如表52所示，怎样安排产品的加工使总成本最小,表52,【解】设xj为采用第j（j=1,2,3）种方式生产的产品数量，生产费用为,3.1 整数规划的数学模型 Mathematical Model of IP,2019年5月23日星期四,式中kj是固定成本，cj是单位产品成本设01变量yj，令,数学模型为,3.1 整数规划的数学模型
9、Mathematical Model of IP,（5.4）,式（5.4）中 是处理xj与yj一对变量之间逻辑关系的特殊约束，当xj0时yj=1, 当xj0时，为使Z最小化，有yj=0。 例5.4是混合整数规划问题用WinQSB软件求解得到： X(0，2000，2000)T，Y(0，1，1)T，Z=25400.,2019年5月23日星期四,作业：教材P75 1, 2，3，4，5，6,1.线性整数规划模型的特征 2.什么是纯（混合）整数规划 3.01规划模型的应用,3.1 整数规划的数学模型 Mathematical Model of IP,下一节：纯整数规划的求解,5.2 纯整数规划的求解 S
10、olving Pure Integer Programming,2019年5月23日星期四,分枝定界法的步骤： 1. 求整数规划的松弛问题最优解； 2. 若松弛问题的最优解满足整数要求，得到整数规划的最优解，否则转下一步； 3.任意选一个非整数解的变量xi，在松弛问题中加上约束xixi及xixi+1组成两个新的松弛问题，称为分枝。 新的松弛问题具有特征：当原问题是求最大值时，目标值是分枝问题的上界；当原问题是求最小值时，目标值是分枝问题的下界； 4. 检查所有分枝的解及目标函数值，若某分枝的解是整数并且目标函数值大于（max）等于其它分枝的目标值，则将其它分枝剪去不再计算,若还存在非整数解并且
11、目标值大于（max）整数解的目标值，需要继续分枝，再检查，直到得到最优解。,5.2.1求解纯整数规划的分枝定界法,3.2 纯整数规划的求解 Solving Pure Integer Programming,2019年5月23日星期四,【例5.5 】用分枝定界法求解例5.1,【解】先求对应的松弛问题（记为LP0）：,用图解法得到最优解X（3.57,7.14）,Z0=35.7,如下图所示。,3.2 纯整数规划的求解 Solving Pure Integer Programming,2019年5月23日星期四,8.33,10,松弛问题LP0的最优解X=(3.57,7.14),Z0=35.7,x1,x
12、2,o,A,B,C,10,5.2 纯整数规划的求解 Solving Pure Integer Programming,10,10,x1,x2,o,A,B,C,LP1,LP2,3,4,LP1:X=(3,7.6),Z1=34.8,LP2:X=(4,6.5),Z2=35.5,10,10,x1,x2,o,A,B,C,LP1,LP3,3,4,LP3:X=(4.33,6),Z3=35.33,6,LP1:X=(3,7.6),Z1=34.8,10,10,x1,x2,o,A,C,LP1,3,4,6,LP4:X=(4,6),Z4=34,LP5:X=(5,5),Z5=35,5,LP1:X=(3,7.6),Z1=34
13、.8,LP3,LP5,尽管LP1的解中x1不为整数，但Z5Z因此LP5的最优解就是原整数规划的最优解。,上述分枝过程可用下图表示,LP0:X=(3.57,7.14),Z0=35.7,LP1:X=(3,7.6) Z1=34.8,LP2:X=(4,6.5) Z2=35.5,x13,x14,LP3:X=(4.33,6) Z3=35.33,x26,LP4:X=(4,6) Z4=34,LP5:X=(5,5) Z5=35,x14,x15,无可行解,x27,2019年5月23日星期四,设纯整数规划,松弛问题,松弛问题的最优解为：,设xi不为整数，,5.2.2 求解IP的割平面法,5.2 纯整数规划的求解 S
14、olving Pure Integer Programming,2019年5月23日星期四,将 分离成一个整数与一个非负真分数之和：,则有,等式两边都为整数并且有：,3.2 纯整数规划的求解 Solving Pure Integer Programming,则,加入松弛变量si得：,此式称为以xi行为源行（来源行）的割平面，或分数切割式，或R.E.Gomory(高莫雷)约束方程。,2019年5月23日星期四,x1行：,移项：,令,加入松弛变量s1得：,同理，对于x2行有：,5.2 纯整数规划的求解 Solving Pure Integer Programming,将Gomory约束加入到松弛问
15、题的最优表中，用对偶单纯形法计算，若最优解中还有非整数解，再继续切割，直到全部为整数解。例如,2019年5月23日星期四,【例5.6】 用割平面法求解下列IP问题,【解】放宽变量约束，对应的松弛问题是,5.2 纯整数规划的求解 Solving Pure Integer Programming,加入松弛变量x3及x4后，用单纯形法求解，得到最优表：,最优解X(0)(5/2，15/4),不是IP的最优解。选择第一行(也可以选第二行)为源行。,2019年5月23日星期四,5.2 纯整数规划的求解 Solving Pure Integer Programming,分离系数后改写成,加入松弛变量x5得到
16、高莫雷约束方程,将高莫雷约束方程添加到最优单纯形表中，用对偶单纯形法计算，如下表所示 。,2019年5月23日星期四,最优解X(1)(3，3)，最优值Z21。所有变量为整数，X(1)就是IP的最优解。如果不是整数解，需要继续切割，重复上述计算过程。 如果在对偶单纯形法中原切割方程的松弛变量仍为基变量，则此松弛变量所在列化为单位向量后就可以去掉该行该列，再切割。,5.2 纯整数规划的求解 Solving Pure Integer Programming,表54,2019年5月23日星期四,作业：教材P76 T 7，8,1.理解分枝与定界的含义 2.选择合适的“枝”生“枝” 3.掌握何时停止生“枝” 4.领会割平面法的基本原理 5.分离源行，求出Gomory约束 6.在最优表中增加Gom
