运筹学Ch3整数规划ppt课件

3.1 整数规划数学模型整数规划数学模型 Mathematical Model of IP3.2 纯整数规划的求解纯整数规划的求解 Solving Pure Integer Programming 3.3 01规划的求解规划的求解 Solving Binary Integer Programming Chapter 3 整数规划整数规划Integer Programming运筹学运筹学Operations ResearchOperations Research3.1 整数规划数学模型整数规划数学模型 Mathematical Model of IP Ch3 整数规划整数规划 Integer Programming 制作与教学 武汉理工大学管理学院 熊伟 Page 3 一个规划问题中要求部分或全部决策变量是整数，那么一个规划问题中要求部分或全部决策变量是整数，那么这个规划称为整数规划。当要求全部变量取整数值的，称为纯这个规划称为整数规划。当要求全部变量取整数值的，称为纯整数规划；只需求一部分变量取整数值的，称为混合整数规划。整数规划；只需求一部分变量取整数值的，称为混合整数规划。假设模型是线性的，称为整数线性规划。本章只讨论整数线性假设模型是线性的，称为整数线性规划。本章只讨论整数线性规划。规划。很多实践规划问题都属于整数规划问题很多实践规划问题都属于整数规划问题 1.变量是人数、机器设备台数或产品件数等都要求是整数变量是人数、机器设备台数或产品件数等都要求是整数2.对某一个工程要不要投资的决策问题，可选用一个逻辑变对某一个工程要不要投资的决策问题，可选用一个逻辑变量量 x，当，当x=1表示投资，表示投资，x=0表示不投资；表示不投资；3.人员的合理安排问题，当变量人员的合理安排问题，当变量xij=1表示安排第表示安排第i人去做人去做j任任务，务，xij=0表示不安排第表示不安排第i人去做人去做j任务。逻辑变量也是只允许取任务。逻辑变量也是只允许取整数值的一类变量。整数值的一类变量。3.1 整数规划的数学模型整数规划的数学模型 Mathematical Model of IP Ch3 整数规划整数规划 Integer Programming 制作与教学 武汉理工大学管理学院 熊伟 Page 4【例【例3.1】某人有一背包可以装】某人有一背包可以装10公斤重、公斤重、0.025m3的物品。他预的物品。他预备用来装甲、乙两种物品，每件物品的分量、体积和价值如表备用来装甲、乙两种物品，每件物品的分量、体积和价值如表3-1所示。问两种物品各装多少件，所装物品的总价值最大？所示。问两种物品各装多少件，所装物品的总价值最大？表表3-1【解】设甲、乙两种物品各装【解】设甲、乙两种物品各装x1、x2件，那么数学模型为：件，那么数学模型为：且均取整数,0,255.22108.02.134max21212121xxxxxxxxZ(3.1)3.1 整数规划的数学模型整数规划的数学模型 Mathematical Model of IP 物品物品重量重量（公斤（公斤/每件）每件）体积体积（m3/每件）每件）价值价值(元元/每件每件)甲甲乙乙1.20.80.0020.002543 Ch3 整数规划整数规划 Integer Programming 制作与教学 武汉理工大学管理学院 熊伟 Page 5 假设不思索假设不思索x1、x2取整数的约束称为取整数的约束称为3.1的松弛问题，的松弛问题，线性规划的可行域如图线性规划的可行域如图3-1中的阴影部分所示。中的阴影部分所示。3.1 整数规划的数学模型整数规划的数学模型 Mathematical Model of IP 图图3-1 Ch3 整数规划整数规划 Integer Programming 制作与教学 武汉理工大学管理学院 熊伟 Page 6 用图解法求得点用图解法求得点B为最优解：为最优解：X(3.57，7.14)，Z35.7。由于由于x1，x2必需取整数值，实践上整数规划问题的可行解集必需取整数值，实践上整数规划问题的可行解集只是图中可行域内的那些整数点。用凑整法来解时需求比较只是图中可行域内的那些整数点。用凑整法来解时需求比较四种组合，但四种组合，但4，7、4，83，8都不是可行解，都不是可行解，3，7虽属可行解，但代入目的函数得虽属可行解，但代入目的函数得Z=33,并非最优。实并非最优。实践上问题的最优解是践上问题的最优解是5，5，Z=35。即两种物品各装。即两种物品各装5件，件，总价值总价值35元。元。由图由图31知，点知，点5，5不是可行域的顶点，直接用图解不是可行域的顶点，直接用图解法或单纯形法都无法求出整数规划问题的最优解，因此求解整法或单纯形法都无法求出整数规划问题的最优解，因此求解整数规划问题的最优解需求采用其它特殊方法。数规划问题的最优解需求采用其它特殊方法。还有些问题用线性规划数学模型无法描画，但可以经过设还有些问题用线性规划数学模型无法描画，但可以经过设置逻辑变量建立起整数规划的数学模型。置逻辑变量建立起整数规划的数学模型。3.1 整数规划的数学模型整数规划的数学模型 Mathematical Model of IP Ch3 整数规划整数规划 Integer Programming 制作与教学 武汉理工大学管理学院 熊伟 Page 7【例【例3.2】在例】在例3.1中，假设此人还有一只游览箱，最大载分量中，假设此人还有一只游览箱，最大载分量为为12公斤，其体积是公斤，其体积是0.02m3。背包和游览箱只能选择其一，建。背包和游览箱只能选择其一，建立以下几种情形的数学模型，使所装物品价值最大。立以下几种情形的数学模型，使所装物品价值最大。1所装物品不变；所装物品不变；2假设选择游览箱，那么只能装载丙和丁两种物品，价值假设选择游览箱，那么只能装载丙和丁两种物品，价值分别是分别是4和和3，载分量和体积的约束为，载分量和体积的约束为2025.1126.08.12121xxxx【解】此问题可以建立两个整数规划模型，但用一个模型描画【解】此问题可以建立两个整数规划模型，但用一个模型描画更简单。引入更简单。引入01变量或称逻辑变量变量或称逻辑变量yi，令，令2,10,1iiiyi种方式装载时不采用第，种方式装载时采用第i=1,2分别是采用背包及游览箱装载。分别是采用背包及游览箱装载。3.1 整数规划的数学模型整数规划的数学模型 Mathematical Model of IP Ch3 整数规划整数规划 Integer Programming 制作与教学 武汉理工大学管理学院 熊伟 Page 8 1 由于所装物品不变，式由于所装物品不变，式(3.1)约束左边不变，整数规划数学约束左边不变，整数规划数学模型为模型为2,110,0120255.2212108.02.134max212121212121iyxyyyyxxyyxxxxZii或且取整数2 由于不同载体所装物品不一样，数学模型为由于不同载体所装物品不一样，数学模型为121221211221211212max431.20.810()1.80.612()22.525()1.5220()1,0,01ZxxxxMyaxxMybxxMycxxMydyyx xy且均取整数或3.1 整数规划的数学模型整数规划的数学模型 Mathematical Model of IP Ch3 整数规划整数规划 Integer Programming 制作与教学 武汉理工大学管理学院 熊伟 Page 9 式中式中M为充分大的正数。从上式可知，当运用背包时为充分大的正数。从上式可知，当运用背包时(y1=1，y2=0)，式，式(b)和和(d)是多余的；当运用游览箱时是多余的；当运用游览箱时(y1=0，y2=1)，式式(a)和和(c)是多余的。上式也可以令：是多余的。上式也可以令：yyyy1,21 同样可以讨论对于有同样可以讨论对于有m个条件相互排斥、有个条件相互排斥、有mm、m个个条件起作用的情形。条件起作用的情形。3.1 整数规划的数学模型整数规划的数学模型 Mathematical Model of IP Ch3 整数规划整数规划 Integer Programming 制作与教学 武汉理工大学管理学院 熊伟 Page 10 1)右端常数是右端常数是k个值中的一个时，类似式个值中的一个时，类似式(3.2)的约束条件为的约束条件为1111kiikiiinjjijyybxa，2)2)对于对于m m组条件中有组条件中有k kmm组起作用时，类似式组起作用时，类似式(3.3)(3.3)的的约束条件写成约束条件写成111kiiiinjjijyMybxa，这里这里yi=1yi=1表示第表示第i i组约束不起作用如组约束不起作用如y1=1y1=1式式(3.3b)(3.3b)、(3.3d)(3.3d)不起作用，不起作用，yi=0yi=0表示第表示第i i个约束起作用。当约束条件是个约束起作用。当约束条件是“符号时右端常数项应为符号时右端常数项应为iibMy3)对于对于m个条件中有个条件中有km个起作用时，约束条件写成个起作用时，约束条件写成kmyMybxakiiiinjjij11，3.1 整数规划的数学模型整数规划的数学模型 Mathematical Model of IP Ch3 整数规划整数规划 Integer Programming 制作与教学 武汉理工大学管理学院 熊伟 Page 11【例【例3.3】试引入】试引入01变量将以下各题分别表达为普通线性约变量将以下各题分别表达为普通线性约束条件束条件1x1+x26或或4x1+6x210或或2x1+4x220 2假设假设x15，那么，那么x20，否那么，否那么x283x2取值取值0，1，3，5，7【解】【解】13个约束只需个约束只需1个起作用个起作用1211221231236461024202011,2,3jxxy Mxxy Mxxy Myyyyj或，3.1 整数规划的数学模型整数规划的数学模型 Mathematical Model of IP 3,2,1101)1(2042)1(1064)1(6321321221121jyyyyMyxxMyxxMyxxj，或或或 Ch3 整数规划整数规划 Integer Programming 制作与教学 武汉理工大学管理学院 熊伟 Page 12 3右端常数是右端常数是5个值中的个值中的1个个4,3,2,1101753432143211jyyyyyyyyyxj，或10)1(8)1(552211或yMyxyMxMyxyMx3.1 整数规划的数学模型整数规划的数学模型 Mathematical Model of IP 2两组约束只需一组起作用两组约束只需一组起作用 Ch3 整数规划整数规划 Integer Programming 制作与教学 武汉理工大学管理学院 熊伟 Page 13【例【例3.4】企业方案消费】企业方案消费4000件某种产品，该产品可本人加工、件某种产品，该产品可本人加工、外协加工恣意一种方式消费知每种消费的固定费用、消费该外协加工恣意一种方式消费知每种消费的固定费用、消费该产品的单件本钱以及每种消费方式的最大加工数量件限制产品的单件本钱以及每种消费方式的最大加工数量件限制如表如表32所示，怎样安排产品的加工使总本钱最小所示，怎样安排产品的加工使总本钱最小表表32【解】设【解】设xj为采用第为采用第jj=1,2,3种方式消费的产品数量，消种方式消费的产品数量，消费费用为费费用为)0(0)0()(jjjjjjjxxxckxC3.1 整数规划的数学模型整数规划的数学模型 Mathematical Model of IP 固定成本固定成本（元）（元）变动成本变动成本（元件）（元件）最大加工数最大加工数（件）（件）本企业加工本企业加工50081500外协加工外协加工80052000外协加工外协加工6007不限不限 Ch3 整数规划整数规划 Integer Programming 制作与教学 武汉理工大学管理学院 熊伟 Page 14 式中式中kj是固定本钱，是固定本钱，cj是单位产品本钱设是单位产品本钱设01变量变量yj，令，令101,2,300jjjjxyjjx采用第 种加工方式，时不采用在第 种加工方式，时)7600()5800()8500(min332211xyxyxyZ数学模型为数学模型为 3,2,101,02000,150040003,2,1021321jyxxxxxxjMyxjjjj，或3.1 整数规划的数学模型整数规划的数学模型 Mathematical Model of IP 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.0jjMyx Ch3 整数规划整数规划 Integer Programming 制作与教学 武汉理工大学管理学院 熊伟 Page 15 作业：教材作业：教材P75 1,2，3，4，5，6 1.线性整数规划模型的特征线性整数规划模型的特征2.什么是纯混合整数规划什么是纯混合整数规划3.01规划模型的运用规划模型的运用3.1 整数规划的数学模型整数规划的数学模型 Mathematical Model of IP 下一节：纯整数规划的求解下一节：纯整数规划的求解3.2 纯整数规划的求解纯整数规划的求解Solving Pure Integer Programming Ch3 整数规划整数规划 Integer Programming 制作与教学 武汉理工大学管理学院 熊伟 Page 17 分枝定界法的步骤：分枝定界法的步骤：1.求整数规划的松弛问题最优解；求整数规划的松弛问题最优解；2.假设松弛问题的最优解满足整数要求，得到整数规划的最假设松弛问题的最优解满足整数要求，得到整数规划的最优解，否那么转下一步；优解，否那么转下一步；3.恣意选一个非整数解的变量恣意选一个非整数解的变量xi，在松弛问题中加上约束，在松弛问题中加上约束xixi及及xixi+1组成两个新的松弛问题，称为分枝。新的松弛组成两个新的松弛问题，称为分枝。新的松弛问题具有特征：当原问题是求最大值时，目的值是分枝问题的问题具有特征：当原问题是求最大值时，目的值是分枝问题的上界；当原问题是求最小值时，目的值是分枝问题的下界；上界；当原问题是求最小值时，目的值是分枝问题的下界；4.检查一切分枝的解及目的函数值，假设某分枝的解是整数检查一切分枝的解及目的函数值，假设某分枝的解是整数并且目的函数值大于并且目的函数值大于max等于其它分枝的目的值，那么将等于其它分枝的目的值，那么将其它分枝剪去不再计算其它分枝剪去不再计算,假设还存在非整数解并且目的值大于假设还存在非整数解并且目的值大于max整数解的目的值，需求继续分枝，再检查，直到得到最整数解的目的值，需求继续分枝，再检查，直到得到最优解。优解。3.2.1求解纯整数规划的分枝定界法求解纯整数规划的分枝定界法3.2 纯整数规划的求解纯整数规划的求解Solving Pure Integer Programming Ch3 整数规划整数规划 Integer Programming 制作与教学 武汉理工大学管理学院 熊伟 Page 18【例【例3.5】用分枝定界法求解例】用分枝定界法求解例5.1【解】先求对应的松弛问题记为【解】先求对应的松弛问题记为LP0：0,255.22108.02.1:034max21212121xxxxxxLPxxZ用图解法得到最优解用图解法得到最优解X3.57,7.14,Z0=35.7,如以下图所如以下图所示。示。且均取整数,0,255.22108.02.134max21212121xxxxxxxxZ3.2 纯整数规划的求解纯整数规划的求解Solving Pure Integer Programming Ch3 整数规划整数规划 Integer Programming 制作与教学 武汉理工大学管理学院 熊伟 Page 19 8.3310108.02.121xx255.2221xx松弛问题LP0的最优解X=(3.57,7.14),Z0=35.7x1x2oABC103.2 纯整数规划的求解纯整数规划的求解Solving Pure Integer Programming 1010 x1x2oABC0,3255.22108.02.1:134max211212121xxxxxxxLPxxZLP1LP234LP1:X=(3,7.6),Z1=34.8LP2:X=(4,6.5),Z2=35.50,4255.22108.02.1:234max211212121xxxxxxxLPxxZ得到两个线性规划及增加约束4311xx1010 x1x2oABCLP1LP334LP3:X=(4.33,6),Z3=35.330,64255.22108.02.1:334max2121212121xxxxxxxxLPxxZ，不可行，得到线性规划，显然及进行分枝，增加约束选择目标值最大的分枝7762222xxxLP6不可行72xLP1:X=(3,7.6),Z1=34.81010 x1x2oACLP134可行域是一条线段即，,40,464255.22108.02.1:434max121121212121xxxxxxxxxxLPxxZ：及，到线性规划及进行分枝，增加约束，选择由于545431113LPLPxxLPZZ60,65255.22108.02.1:534max2121212121xxxxxxxxLPxxZ，LP4:X=(4,6),Z4=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无可行解无可行解x27 Ch3 整数规划整数规划 Integer Programming 制作与教学 武汉理工大学管理学院 熊伟 Page 24 设纯整数规划设纯整数规划njxbxaxcZjinjjijnjjj,10max11且为整数，松弛问题松弛问题njxbxaxcZjinjjijnjjj,10max11，的最优解的最优解TmTbbbbBbbBX),()0,(2111设设xi不为整数，不为整数，为非基变量kkkikiixxabx3.2.2 求解求解IP的割平面法的割平面法3.2 纯整数规划的求解纯整数规划的求解Solving Pure Integer Programming Ch3 整数规划整数规划 Integer Programming 制作与教学 武汉理工大学管理学院 熊伟 Page 25 将将 分别成一个整数与一个非负真分数之和：分别成一个整数与一个非负真分数之和：ikiab及 10,10,ikiikikikiiifffaafbb那么有那么有kkikkkijiiixfxafbxkkikikkijiixffxabx等式两边都为整数并且有等式两边都为整数并且有1ikkikifxff3.2 纯整数规划的求解纯整数规划的求解Solving Pure Integer Programming Ch3 整数规划整数规划 Integer Programming 制作与教学 武汉理工大学管理学院 熊伟 Page 26 参与松弛变量参与松弛变量si得得ikkikifxfs此式称为以此式称为以xi行为源行来源行的割平面，或分数切割式，行为源行来源行的割平面，或分数切割式，或或R.E.Gomory(高莫雷高莫雷)约束方程。约束方程。将将Gomory约束参与到松弛问题的最优表中，用对偶单纯约束参与到松弛问题的最优表中，用对偶单纯形法计算，假设最优解中还有非整数解，再继续切割，直到形法计算，假设最优解中还有非整数解，再继续切割，直到全部为整数解。全部为整数解。0kkikixff那么那么3.2 纯整数规划的求解纯整数规划的求解Solving Pure Integer Programming Ch3 整数规划整数规划 Integer Programming 制作与教学 武汉理工大学管理学院 熊伟 Page 27 324313322354613651xxxxxx例如，例如，3246536511)1(xxxx1行：行：移项：移项：46536532411xxxx令令046536532xx参与松弛变量参与松弛变量s1得得324653651xxs同理，对于同理，对于x2行有：行有：324313312xxs3.2 纯整数规划的求解纯整数规划的求解Solving Pure Integer Programming Ch3 整数规划整数规划 Integer Programming 制作与教学 武汉理工大学管理学院 熊伟 Page 28【例【例3.6】用割平面法求解以下用割平面法求解以下IP问题问题且为整数0,102304634max21212121xxxxxxxxZ【解】【解】放宽变量约束，对应的松弛问题是放宽变量约束，对应的松弛问题是 0,102304634max21212121xxxxxxxxZ3.2 纯整数规划的求解纯整数规划的求解Solving Pure Integer Programming Ch3 整数规划整数规划 Integer Programming 制作与教学 武汉理工大学管理学院 熊伟 Page 29 参与松弛变量参与松弛变量x3及及x4后，用单纯形法求解，得到最优表后，用单纯形法求解，得到最优表3-3。最优解最优解X(0)(5/2，15/4),不是不是IP的最优解。选择表的最优解。选择表3-3的第一行的第一行(也可以选第二行也可以选第二行)为源行为源行252141431xxx3.2 纯整数规划的求解纯整数规划的求解Solving Pure Integer Programming Cj4300bCBXBx1x2x3x443x1x210011/41/81/23/45/215/4j005/81/4表表3-3 Ch3 整数规划整数规划 Integer Programming 制作与教学 武汉理工大学管理学院 熊伟 Page 30 分别系数后改写成分别系数后改写成212)211(41431xxx021412124341xxxx参与松弛变量参与松弛变量x5得到高莫雷约束方程得到高莫雷约束方程22543xxx将式将式(3.8)作为约束条件添加到表作为约束条件添加到表33中，用对偶单纯形法中，用对偶单纯形法计算，如表计算，如表34所示所示 3.2 纯整数规划的求解纯整数规划的求解Solving Pure Integer Programming Ch3 整数规划整数规划 Integer Programming 制作与教学 武汉理工大学管理学院 熊伟 Page 31 Cj43000bCBXBx1x2x3x4x5430 x1x2x51000101/41/811/23/42 0015/215/42j005/81/40430 x1x2x41000101/21/21/2001 1/43/81/2331j001/201/8最优解最优解X(1)(3，3)，最优值，最优值Z21。一切变量为整数，。一切变量为整数，X(1)就就是是IP的最优解。假设不是整数解，需求继续切割，反复上述计的最优解。假设不是整数解，需求继续切割，反复上述计算过程。算过程。3.2 纯整数规划的求解纯整数规划的求解Solving Pure Integer Programming 表表34 假设在对偶单纯形法中原切割方程的松弛变量仍为基变量，那么此松假设在对偶单纯形法中原切割方程的松弛变量仍为基变量，那么此松弛变量所在列化为单位向量后就可以去掉该行该列，再切割。弛变量所在列化为单位向量后就可以去掉该行该列，再切割。Ch3 整数规划整数规划 Integer Programming 制作与教学 武汉理工大学管理学院 熊伟 Page 32 作业：教材作业：教材P76 T 7，8 1.了解分枝与定界的含义了解分枝与定界的含义2.选择适宜的选择适宜的“枝生枝生“枝枝3.掌握何时停顿生掌握何时停顿生“枝枝4.领会割平面法的根本原理领会割平面法的根本原理5.分别源行，求出分别源行，求出Gomory约束约束6.在最优表中添加在最优表中添加Gomory约束，用约束，用 对偶单纯形法迭代对偶单纯形法迭代3.2 纯整数规划的求解纯整数规划的求解Solving Pure Integer Programming 下一节：下一节：01规划的求解规划的求解3.3 01规划的求解规划的求解Solving BIP Ch3 整数规划整数规划 Integer Programming 制作与教学 武汉理工大学管理学院 熊伟 Page 34 3.3.1 求解求解01整数规划的隐枚举法整数规划的隐枚举法隐枚举法的步骤：隐枚举法的步骤：1.找出恣意一可行解，目的函数值为找出恣意一可行解，目的函数值为Z0 2.原问题求最大值时，那么添加一个约束原问题求最大值时，那么添加一个约束1 1220(*)nnc xc xc xZ当求最小值时，上式改为小于等于约束当求最小值时，上式改为小于等于约束 3.列出一切能够解，对每个能够解先检验式列出一切能够解，对每个能够解先检验式*，假设满足，假设满足再检验其它约束，假设不满足式再检验其它约束，假设不满足式*，那么以为不可行，假设，那么以为不可行，假设一切约束都满足，那么以为此解是可行解，求出目的值一切约束都满足，那么以为此解是可行解，求出目的值 4.目的函数值最大最小的解就是最优解目的函数值最大最小的解就是最优解 3.3 01规划的求解规划的求解Solving BIP Ch3 整数规划整数规划 Integer Programming 制作与教学 武汉理工大学管理学院 熊伟 Page 35【例3.7】用隐枚举法求解以下BIP问题4,3,2,11010542324653103245326max43214321432143214321jxxxxxxxxxxxxxxxxxxxxxZj，或【解】【解】1不难看出，当一切变量等于不难看出，当一切变量等于0或或1的恣意组合时，的恣意组合时，第一个约束满足，阐明第一个约束没有约束力，是多余的，第一个约束满足，阐明第一个约束没有约束力，是多余的，从约束条件中去掉。还能经过察看得到从约束条件中去掉。还能经过察看得到X0(1，0，0，1)是一是一个可行解，目的值个可行解，目的值Z011是是BIP问题的下界，构造一个约问题的下界，构造一个约束：束：，原，原BIP问题变为问题变为1153264321xxxx3.3 01规划的求解规划的求解Solving BIP Ch3 整数规划整数规划 Integer Programming 制作与教学 武汉理工大学管理学院 熊伟 Page 36)9.3()9.3()9.3()9.3(4,3,2,110105423246531153265326max43214321432143214321dcbajxxxxxxxxxxxxxxxxxxxxxZj，或(2)列出变量取值列出变量取值0和和1的组合，共的组合，共2416个，分别代入约束条件个，分别代入约束条件判别能否可行。首先判别式判别能否可行。首先判别式3.9a能否满足，假设满足，接下能否满足，假设满足，接下来判别其它约束，否那么以为不可行，计算过程见表来判别其它约束，否那么以为不可行，计算过程见表37所示。所示。3.3 01规划的求解规划的求解Solving BIP Ch3 整数规划整数规划 Integer Programming 制作与教学 武汉理工大学管理学院 熊伟 Page 37 jXj3.9a3.9b3.9c3.9dZjjXj3.9a3.9b3.9c3.9dZj1(0,0,0,0)9(1,0,0,0)2(0,0,0,1)10(1,0,0,1)113(0,0,1,0)11(1,0,1,0)4(0,0,1,1)12(1,0,1,1)145(0,1,0,0)13(1,1,0,0)6(0,1,0,1)14(1,1,0,1)137(0,1,1,0)15(1,1,1,0)8(0,1,1,1)16(1,1,1,1)表表35(3)由表由表3-5知，知，BIP问题的最优解：问题的最优解：X1，0，1，1，最，最优值优值Z143.3 01规划的求解规划的求解Solving BIP Ch3 整数规划整数规划 Integer Programming 制作与教学 武汉理工大学管理学院 熊伟 Page 38 选择不同的初始可行解，计算量会不一样。普通地，当目选择不同的初始可行解，计算量会不一样。普通地，当目的函数求最大值时，首先思索目的函数系数最大的变量等于的函数求最大值时，首先思索目的函数系数最大的变量等于1，如例如例3.8。当目的函数求最小值时，先思索目的函数系数最大。当目的函数求最小值时，先思索目的函数系数最大的变量等于的变量等于0。在表在表37的计算过程中，当目的值等于的计算过程中，当目的值等于14时，将其下界时，将其下界11改改为为14，可以减少计算量。，可以减少计算量。3.3.2 分枝隐枚举法求解分枝隐枚举法求解BIP问题问题将分枝定界法与隐枚举法结合起来用，得到分枝隐枚举法。计将分枝定界法与隐枚举法结合起来用，得到分枝隐枚举法。计算步骤如下：算步骤如下：1将将BIP问题的目的函数的系数化为非负，如问题的目的函数的系数化为非负，如332max,132max212221xxZxxxxZ令3.3 01规划的求解规划的求解Solving BIP Ch3 整数规划整数规划 Integer Programming 制作与教学 武汉理工大学管理学院 熊伟 Page 39 当变量作了代换后，约束条件中的变量也相应作代换。当变量作了代换后，约束条件中的变量也相应作代换。3求主枝：目的函数是求主枝：目的函数是max方式时令一切变量等于方式时令一切变量等于1，得到，得到目的值的上界；目的函数是目的值的上界；目的函数是min方式时令一切变量等于方式时令一切变量等于0，得，得到目的值的下界；假设主枝的解满足一切约束条件那么得到最到目的值的下界；假设主枝的解满足一切约束条件那么得到最优解，否那么转下一步；优解，否那么转下一步；4分枝与定界：从第一个变量开场依次取分枝与定界：从第一个变量开场依次取“1或或“0，求，求极大值时其后面的变量等于极大值时其后面的变量等于“1，求极小值时其后面的变量等，求极小值时其后面的变量等于于“0，用分枝定界法搜索可行解和最优解。，用分枝定界法搜索可行解和最优解。分枝隐枚举法是从非可行解中进展分枝搜索可行解，第分枝隐枚举法是从非可行解中进展分枝搜索可行解，第1步到第步到第3步用了隐枚举法的思绪，第步用了隐枚举法的思绪，第4步用了分枝定界步用了分枝定界法的思绪。法的思绪。3432max,1432max4213224321xxxxZxxxxxxZ令3.3 01规划的求解规划的求解Solving BIP (2)变量重新排序：变量根据目的函数系数值按升排序；变量重新排序：变量根据目的函数系数值按升排序；Ch3 整数规划整数规划 Integer Programming 制作与教学 武汉理工大学管理学院 熊伟 Page 40 停顿分枝和需求继续分枝的原那么：停顿分枝和需求继续分枝的原那么：1当某一子问题是可行解时那么停顿分枝并保管；当某一子问题是可行解时那么停顿分枝并保管；2不是可行解但目的值劣于现有保管分枝的目的值时停顿分枝并剪枝；不是可行解但目的值劣于现有保管分枝的目的值时停顿分枝并剪枝；3后续分枝变量无论取后续分枝变量无论取“1或或“0都不能得到可行解时停顿分枝并剪枝；都不能得到可行解时停顿分枝并剪枝；4当某一子问题不可行但目的值优于现有保管分枝的一切目的值，那么当某一子问题不可行但目的值优于现有保管分枝的一切目的值，那么要继续分枝。要继续分枝。【例【例3.8】用分枝隐枚举法求解以下】用分枝隐枚举法求解以下BIP问题问题)10.3()10.3()10.3(4,3,2,110105423246535326max4321432143214321cbajxxxxxxxxxxxxxxxxxZj，或3.3 01规划的求解规划的求解Solving BIP Ch3 整数规划整数规划 Integer Programming 制作与教学 武汉理工大学管理学院 熊伟 Page 41 解解 1目的函数系数全部非负，直接对变量重新排序目的函数系数全部非负，直接对变量重新排序)10.3()10.3()10.3(4,3,2,110105423243656532max1432143214321432cbajxxxxxxxxxxxxxxxxxZj，或2求主枝：令求主枝：令X(1，1，1，1)得到主枝得到主枝1，检查约束条件知，检查约束条件知(3.10c)不不满足，那么进展分枝。满足，那么进展分枝。3令令x2=0同时令同时令x3=0及及x3=1得到分枝得到分枝2和分枝和分枝3，X2和和X3是可行解，是可行解，分枝停顿并保管，如表分枝停顿并保管，如表3-8及图及图3-8所示。所示。3.3 01规划的求解规划的求解Solving BIP Ch3 整数规划整数规划 Integer Programming 制作与教学 武汉理工大学管理学院 熊伟 Page 42 表表3.8 令令x2=1同时令同时令x3=0得到分枝得到分枝4，X4是可行解，分枝停顿并保管。是可行解，分枝停顿并保管。令令x2=1、x3=1，x4取取“0和和“1得到分枝得到分枝5和和6，分枝，分枝5不可行不可行并且并且Z511小于小于Z3和和 Z4，分枝停顿并剪枝。留意到分枝，分枝停顿并剪枝。留意到分枝6，x41时只需时只需x10 x11就是主枝，就是主枝，X6不可行并且不可行并且Z610小小于于Z3和和 Z4，分枝停顿并剪枝，分枝过程终了。整个计算过程，分枝停顿并剪枝，分枝过程终了。整个计算过程可用图可用图32和表和表3.8表示。表示。分分枝枝(x2,x3,x4,x1)3.10a3.10b3.10cZj可可行行性性1(1,1,1,1)16不不可可行行2(0,0,1,1)11可可行行3(0,1,1,1)14可可行行4(1,0,1,1)13可可行行5(1,1,0,1)11不不可可行行6(1,1,1,0)10不不可可行行3.3 01规划的求解规划的求解Solving BIP Ch3 整数规划整数规划 Integer Programming 制作与教学 武汉理工大学管理学院 熊伟 Page 43 搜索到搜索到3个可行解，个可行解，3个目的值中个目的值中Z3最大，因此最大，因此X3是最优解，转是最优解，转换到原问题的最优解为换到原问题的最优解为X1，0，1，1，最优值，最优值Z14，计，计算终了。算终了。图图323.3 01规划的求解规划的求解Solving BIP Ch3 整数规划整数规划 Integer Programming 制作与教学 武汉理工大学管理学院 熊伟 Page 44【例【例3.9】用分枝隐枚举法求解以下】用分枝隐枚举法求解以下BIP问题问题)11.3()11.3(4,3,2,11010354127264263min543215432154321bajxxxxxxxxxxxxxxxxZj，或解解 1令令x2=1x2及及x5=1x5，代入模型后整理得，代入模型后整理得)11.3()11.3(4,3,2,1103354972674263min543215432154321bajxxxxxxxxxxxxxxxxZj，或3.3 01规划的求解规划的求解Solving BIP Ch3 整数规划整数规划 Integer Programming 制作与教学 武汉理工大学管理学院 熊伟 Page 45 2目的函数系数按升序将对应的变量重新陈列得到模型目的函数系数按升序将对应的变量重新陈列得到模型)11.3()11.3(4,3,2,1103534927676432min352413524135241bajxxxxxxxxxxxxxxxxZj，或3求主枝。由于目的函数求最小值，令一切变量等于零，求主枝。由于目的函数求最小值，令一切变量等于零，得到主枝的解得到主枝的解X10，0，0，0，0，Z17，检验约束条，检验约束条件知件知X1不可行，进展分枝。不可行，进展分枝。4取取x1=1和和x1=0，分别其它变量等于，分别其它变量等于“1和和“0分枝，判分枝，判别可行性，计算过程参见表别可行性，计算过程参见表36及图及图33。3.3 01规划的求解规划的求解Solving BIP Ch3 整数规划整数规划 Integer Programming 制作与教学 武汉理工大学管理学院 熊伟 Page 46 分枝分枝j上一上一分枝分枝Xj=(x1,x4,x2,x5,x3)3.11a3.11bZj可行性可行性12345主枝主枝1111(0,0,0,0,0)(0,1,0,0,0)(0,0,1,0,0)(0,0,0,1,0)(0,0,0,0,1)75431不可行不可行不可行不可行不可行不可行不可行不可行可行可行67891016666(1,0,0,0,0)(1,1,0,0,0)(1,0,1,0,0)(1,0,0,1,0)(1,0,0,0,1)64320不可行不可行不可行不可行不可行不可行不可行不可行可行可行表表363.3 01规划的求解规划的求解Solving BIP Ch3 整数规划整数规划 Integer Programming 制作与教学 武汉理工大学管理学院 熊伟 Page 47 由表由表36知，分枝知，分枝5和分枝和分枝10两个问题可行，分枝两个问题可行，分枝5优于分枝优于分枝10，其它不可行子问题虽然目的值优于分枝其它不可行子问题虽然目的值优于分枝5，由约束，由约束(3.11b)知，继知，继续分枝不能够得到其它可行解，因此停顿分枝，计算终了。分枝续分枝不能够得到其它可行解，因此停顿分枝，计算终了。分枝5的解的解X5(x1,x4,x2,x5,x3)0，0，0，0，1，原，原BIP的最的最优解为优解为X(x1,x2,x3,x4,x5)(0，1，1，0，1),最优值最优值Z1。图图333.3 01规划的求解规划的求解Solving BIP Ch3 整数规划整数规划 Integer Programming 制作与教学 武汉理工大学管理学院 熊伟 Page 48 在分枝隐枚举法的计算过程中，由于变量曾经按目的在分枝隐枚举法的计算过程中，由于变量曾经按目的函数系数从小到大重新排序，因此在选择子问题分枝的函数系数从小到大重新排序，因此在选择子问题分枝的原那么是按排序后的变量顺序分枝，但变量较多时搜索原那么是按排序后的变量顺序分枝，但变量较多时搜索可行解的过程能够非常漫长。针对转换后的目的函数特可行解的过程能够非常漫长。针对转换后的目的函数特征，极大值问题的解中征，极大值问题的解中“1越多越优，极小值问题的解越多越优，极小值问题的解中中“0越多越优，因此在选择变量分枝时尽能够采用避越多越优，因此在选择变量分枝时尽能够采用避“0或或“1的方法，请察看表的方法，请察看表38及及36.3.3 01规划的求解规划的求解Solving BIP Ch3 整数规划整数规划 Integer Programming 制作与教学 武汉理工大学管理学院 熊伟 Page 49 作业：作业：P76 T 9，101.用隐枚举法求用隐枚举法求0-1规划的最优解规划的最优解2.用分枝隐枚举法求解用分枝隐枚举法求解0-1规划的最优解规划的最优解3.3 01规划的求解规划的求解Solving BIP The End of Chapter 3 3,2,11072462534max321321321jxxxxxxxxxxZj，或4,3,2,1107423422335434min4321432143214321jxxxxxxxxxxxxxxxxxZj，或3.9(1)3.9(2)