《运筹学 备课课件Ch3整数规划(1)》由会员分享，可在线阅读，更多相关《运筹学 备课课件Ch3整数规划(1)（49页珍藏版）》请在金锄头文库上搜索。
1、3.1整数规划数学模型MathematicalModelofIP3.2纯整数规划的求解SolvingPureIntegerProgramming3.301规划的求解SolvingBinaryIntegerProgrammingChapter3整数规划IntegerProgramming运筹学OperationsResearch3.1整数规划数学模型MathematicalModelofIPCh3整数规划IntegerProgramming 制作与教学 武汉理工大学管理学院 熊伟 Page 3 *一个规划问题中要求部分或全部决策变量是整数，则这个规划称为整数规划。当要求全部变量取整数值的，称为纯
2、整数规划；只要求一部分变量取整数值的，称为混合整数规划。如果模型是线性的，称为整数线性规划。本章只讨论整数线性规划。很多实际规划问题都属于整数规划问题1.变量是人数、机器设备台数或产品件数等都要求是整数2.对某一个项目要不要投资的决策问题，可选用一个逻辑变量x，当x=1表示投资，x=0表示不投资；3.人员的合理安排问题，当变量xij=1表示安排第i人去做j工作，xij=0表示不安排第i人去做j工作。逻辑变量也是只允许取整数值的一类变量。3.1整数规划的数学模型 Mathematical Model ofIPCh3整数规划IntegerProgramming 制作与教学 武汉理工大学管理学院 熊
3、伟 Page 4 *【例3-1】某人有一背包可以装10公斤重、0.025m3的物品。他准备用来装甲、乙两种物品，每件物品的重量、体积和价值如表3-1所示。问两种物品各装多少件，所装物品的总价值最大？表3-1【解】设甲、乙两种物品各装x1、x2件，则数学模型为：(3-1)3.1整数规划的数学模型 MathematicalModelofIP物品重量（公斤/每件）体积（m3/每件）价值(元/每件)甲乙1.20.80.0020.002543Ch3整数规划IntegerProgramming 制作与教学 武汉理工大学管理学院 熊伟 Page 5 *如果不考虑x1、x2取整数的约束（称为（3-1）的松弛问
4、题），线性规划的可行域如图3-1中的阴影部分所示。3.1整数规划的数学模型 Mathematical Model ofIP图3-1Ch3整数规划IntegerProgramming 制作与教学 武汉理工大学管理学院 熊伟 Page 6 *用图解法求得点B为最优解：X(3.57，7.14)，Z35.7。由于x1，x2必须取整数值，实际上整数规划问题的可行解集只是图中可行域内的那些整数点。用凑整法来解时需要比较四种组合，但（4，7）、（4，8）（3，8）都不是可行解，（3，7）虽属可行解，但代入目标函数得Z=33,并非最优。实际上问题的最优解是（5，5），Z=35。即两种物品各装5件，总价值35元
5、。由图31知，点（5，5）不是可行域的顶点，直接用图解法或单纯形法都无法求出整数规划问题的最优解，因此求解整数规划问题的最优解需要采用其它特殊方法。还有些问题用线性规划数学模型无法描述，但可以通过设置逻辑变量建立起整数规划的数学模型。3.1整数规划的数学模型 Mathematical Model ofIPCh3整数规划IntegerProgramming 制作与教学 武汉理工大学管理学院 熊伟 Page 7 *【例3-2 】在例3-1中，假设此人还有一只旅行箱，最大载重量为12公斤，其体积是0.02m3。背包和旅行箱只能选择其一，建立下列几种情形的数学模型，使所装物品价值最大。（1）所装物品不
6、变；（2）如果选择旅行箱，则只能装载丙和丁两种物品，价值分别是4和3，载重量和体积的约束为【解】此问题可以建立两个整数规划模型，但用一个模型描述更简单。引入01变量（或称逻辑变量）yi，令i=1,2分别是采用背包及旅行箱装载。3.1整数规划的数学模型 Mathematical Model ofIPCh3整数规划IntegerProgramming 制作与教学 武汉理工大学管理学院 熊伟 Page 8 *（1）由于所装物品不变，式(3-1)约束左边不变，整数规划数学模型为（2）由于不同载体所装物品不一样，数学模型为3.1整数规划的数学模型 Mathematical Model ofIPCh3整数
7、规划IntegerProgramming 制作与教学 武汉理工大学管理学院 熊伟 Page 9 *式中M为充分大的正数。从上式可知，当使用背包时(y1=1，y2=0)，式(b)和(d)是多余的；当使用旅行箱时(y1=0，y2=1)，式(a)和(c)是多余的。上式也可以令：同样可以讨论对于有m个条件互相排斥、有m（m、m）个条件起作用的情形。3.1整数规划的数学模型 Mathematical Model ofIPCh3整数规划IntegerProgramming 制作与教学 武汉理工大学管理学院 熊伟 Page 10 *（1)右端常数是k个值中的一个时，类似式(3-2)的约束条件为（2)对于m组
8、条件中有k（m）组起作用时，类似式(3-3)的约束条件写成这里yi=1表示第i组约束不起作用（如y1=1式(3-3b)、(3-3d)不起作用），yi=0表示第i个约束起作用。当约束条件是“”符号时右端常数项应为（3)对于m个条件中有k（m）个起作用时，约束条件写成3.1整数规划的数学模型 Mathematical Model ofIPCh3整数规划IntegerProgramming 制作与教学 武汉理工大学管理学院 熊伟 Page 11 *【例3-3】试引入01变量将下列各题分别表达为一般线性约束条件（1）x1+x26或4x1+6x210或2x1+4x220（2）若x15，则x20，否则x2
9、8（3）x2取值0，1，3，5，7【解】（1）3个约束只有1个起作用3.1整数规划的数学模型 Mathematical Model ofIP或Ch3整数规划IntegerProgramming 制作与教学 武汉理工大学管理学院 熊伟 Page 12 *（3）右端常数是5个值中的1个3.1整数规划的数学模型 Mathematical Model ofIP（2）两组约束只有一组起作用Ch3整数规划IntegerProgramming 制作与教学 武汉理工大学管理学院 熊伟 Page 13 *【例3-4】企业计划生产4000件某种产品，该产品可自己加工、外协加工任意一种形式生产已知每种生产的固定费用
10、、生产该产品的单件成本以及每种生产形式的最大加工数量（件）限制如表32所示，怎样安排产品的加工使总成本最小表32【解】设xj为采用第j（j=1,2,3）种方式生产的产品数量，生产费用为3.1整数规划的数学模型 Mathematical Model ofIP固定成本（元）变动成本（元件）最大加工数（件）本企业加工50081500外协加工80052000外协加工6007不限Ch3整数规划IntegerProgramming 制作与教学 武汉理工大学管理学院 熊伟 Page 14 *式中kj是固定成本，cj是单位产品成本设01变量yj，令数学模型为 3.1整数规划的数学模型 Mathematical
11、 Model ofIP（3-4）式（3-4）中是处理xj与yj一对变量之间逻辑关系的特殊约束，当xj0时yj=1,当xj0时，为使Z最小化，有yj=0。例3-4是混合整数规划问题用WinQSB软件求解得到：X(0，2000，2000)T，Y(0，1，1)T，Z=25400.Ch3整数规划IntegerProgramming 制作与教学 武汉理工大学管理学院 熊伟 Page 15 *作业：教材习题3.13.61.线性整数规划模型的特征2.什么是纯（混合）整数规划3.01规划模型的应用3.1整数规划的数学模型 Mathematical Model ofIP下一节：纯整数规划的求解3.2纯整数规划的
12、求解SolvingPureIntegerProgrammingCh3整数规划IntegerProgramming 制作与教学 武汉理工大学管理学院 熊伟 Page 17 *分枝定界法的步骤：1.求整数规划的松弛问题最优解；2.若松弛问题的最优解满足整数要求，得到整数规划的最优解，否则转下一步；3.任意选一个非整数解的变量xi，在松弛问题中加上约束xixi及xixi+1组成两个新的松弛问题，称为分枝。新的松弛问题具有特征：当原问题是求最大值时，目标值是分枝问题的上界；当原问题是求最小值时，目标值是分枝问题的下界；4.检查所有分枝的解及目标函数值，若某分枝的解是整数并且目标函数值大于（max）等于
13、其它分枝的目标值，则将其它分枝剪去不再计算,若还存在非整数解并且目标值大于（max）整数解的目标值，需要继续分枝，再检查，直到得到最优解。3.2.1求解纯整数规划的分枝定界法3.2纯整数规划的求解SolvingPureIntegerProgrammingCh3整数规划IntegerProgramming 制作与教学 武汉理工大学管理学院 熊伟 Page 18 *【例3-5】用分枝定界法求解例5.1【解】先求对应的松弛问题（记为LP0）：用图解法得到最优解X（3.57,7.14）,Z0=35.7,如下图所示。3.2纯整数规划的求解SolvingPureIntegerProgrammingCh3整
14、数规划IntegerProgramming 制作与教学 武汉理工大学管理学院 熊伟 Page 19 *8.3310松弛问题LP0的最优解X=(3.57,7.14),Z0=35.7x1x2oABC103.2纯整数规划的求解SolvingPureIntegerProgramming1010 x1x2oABCLP1LP234LP1:X=(3,7.6),Z1=34.8LP2:X=(4,6.5),Z2=35.51010 x1x2oABCLP1LP334LP3:X=(4.33,6),Z3=35.336LP1:X=(3,7.6),Z1=34.81010 x1x2oACLP1346LP4:X=(4,6),Z4
15、=34LP5:X=(5,5),Z5=355LP1:X=(3,7.6),Z1=34.8LP3LP5尽管LP1的解中x1不为整数，但Z5Z因此LP5的最优解就是原整数规划的最优解。上述分枝过程可用下图表示LP0:X=(3.57,7.14),Z0=35.7LP1:X=(3,7.6)Z1=34.8LP2:X=(4,6.5)Z2=35.5x13x14LP3:X=(4.33,6)Z3=35.33x26LP4:X=(4,6)Z4=34LP5:X=(5,5)Z5=35x14x15无可行解x27Ch3整数规划IntegerProgramming 制作与教学 武汉理工大学管理学院 熊伟 Page 24 *设纯整数
16、规划松弛问题的最优解设xi不为整数，3.2.2求解IP的割平面法3.2纯整数规划的求解SolvingPureIntegerProgrammingCh3整数规划IntegerProgramming 制作与教学 武汉理工大学管理学院 熊伟 Page 25 *将分离成一个整数与一个非负真分数之和：则有等式两边都为整数并且有3.2纯整数规划的求解SolvingPureIntegerProgrammingCh3整数规划IntegerProgramming 制作与教学 武汉理工大学管理学院 熊伟 Page 26 *加入松弛变量si得此式称为以xi行为源行（来源行）的割平面，或分数切割式，或R.E.Gomory(高莫雷)约束方程。将Gomory约束加入到松弛问题的最优表中，用对偶单纯形法计算，若最优解中还有非整数解，再继续切割，直到全部为整数解。则3.2纯整数规划的求解SolvingPureIntegerProgrammingCh3整数规划IntegerProgramming 制作与教学 武汉理工大学管理学院 熊伟 Page 27 *例如，x1行：移项：令加入
