5.4 0-1 整数规划.ppt

《5.4 0-1 整数规划.ppt》由会员分享，可在线阅读，更多相关《5.4 0-1 整数规划.ppt（32页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、 如果线性规划中的所有决策变量的取值只能取如果线性规划中的所有决策变量的取值只能取 0 0、1 1，则这类线性规划问题是一种特殊的整数规划问题则这类线性规划问题是一种特殊的整数规划问题 称之为称之为0-10-1规划规划，把只能取，把只能取0 0或或1 1值的变量称为值的变量称为0-10-1变量变量。0-10-1变量是一种逻辑变量。变量是一种逻辑变量。在某些特殊的实际问题中，我们只需做是非选择，在某些特殊的实际问题中，我们只需做是非选择，如：是否采纳某方案，某任务是否可交给某人承担，如：是否采纳某方案，某任务是否可交给某人承担，集装箱是否装入某货物等，集装箱是否装入某货物等，对于这类问题的变量可

2、设置简化为对于这类问题的变量可设置简化为0 0或或1 1，x=1 1 是是0 0 否否决策变量只取决策变量只取0 0和和1 1的线性规划问题，的线性规划问题，其其数学模型数学模型如下：如下：其中其中x xj j为为0-10-1变量，也称二进制变量，逻辑变量。变量，也称二进制变量，逻辑变量。x xj j仅取值仅取值0 0或或1 1这个条件可由下述约束条件所代替。这个条件可由下述约束条件所代替。x xj j1,x1,xj j00，整数，整数它和一般整数线性规划的约束条件形式是一致的。它和一般整数线性规划的约束条件形式是一致的。v作用：作用：在实际问题中，如果引入在实际问题中，如果引入0-10-1变

3、量，变量，就可以把有各种情况需要分别讨论的就可以把有各种情况需要分别讨论的 线性规划问题统一在一个问题中讨论了。线性规划问题统一在一个问题中讨论了。在本节我们先介绍引入在本节我们先介绍引入0-1变量的变量的实际问题实际问题：投资场所（项目）的选定投资场所（项目）的选定相互排斥的约束条件相互排斥的约束条件关于固定费用的问题关于固定费用的问题 然后，再研究然后，再研究0-1规划问题的一般解法规划问题的一般解法-隐枚举法隐枚举法。一一一一.引入引入引入引入0-10-10-10-1变量的实际问题变量的实际问题变量的实际问题变量的实际问题1.1.投资场所的选定投资场所的选定相互排斥的计划相互排斥的计划例

4、例例例4:4:4:4:某公司拟在市东、西、南三区建立门市部。某公司拟在市东、西、南三区建立门市部。拟议中有拟议中有7 7个位置个位置(点点)A)Ai i(i=1(i=1，2 2，7)7)可供选择。可供选择。规定：规定：v在东区，由在东区，由A A1 1，A A2 2，A A3 3三个点中至多选两个；三个点中至多选两个；v在西区，由在西区，由A A4 4，A A5 5两个点中至少选一个；两个点中至少选一个；v在南区，由在南区，由A A6 6，A A7 7两个点中至少选一个。两个点中至少选一个。v如选用如选用A Ai i点，设备投资估计为点，设备投资估计为b bi i元，元，每年可获利润估计每年可

5、获利润估计为为c ci i元，元，但投资总额不能超过但投资总额不能超过B B元。元。问应选择哪几个点可使年利润为最大问应选择哪几个点可使年利润为最大?解题时先引入解题时先引入解题时先引入解题时先引入0-10-10-10-1变量变量变量变量x x x xi i i i (=1,2(=1,2(=1,2(=1,2，7)7)7)7)于是问题可列成：于是问题可列成：于是问题可列成：于是问题可列成：v在在东东区区，由由A A1 1，A A2 2，A A3 3三三个个点点中中至多选两个；至多选两个；v在在西西区区，由由A A4 4，A A5 5两两个个点点中中至至少少选一个；选一个；v在在南南区区，由由A

6、A6 6，A A7 7两两个个点点中中至至少少选一个。选一个。2.2.2.2.相互排斥的约束条件相互排斥的约束条件相互排斥的约束条件相互排斥的约束条件在本章开始的例在本章开始的例1(P114)1(P114)中，关于运货的中，关于运货的体积限制体积限制为为 5x5x1 1+4x+4x2 224 24 (5-9)(5-9)v今设运货有车运和船运两种方式，今设运货有车运和船运两种方式，上面的条件系用上面的条件系用车运时车运时的限制条件，的限制条件，如用如用船运船运时关于体积的限制条件为时关于体积的限制条件为 7x7x1 1+3x+3x2 245 45 (5-10)(5-10)v这两条件是互相排斥的。

7、这两条件是互相排斥的。为了统一在一个问题中，引入为了统一在一个问题中，引入0-10-1变量变量y y，令，令（1 1）两个约束条件中只有一个起作用）两个约束条件中只有一个起作用车运车运船运船运于是于是(5-9)(5-9)式和式和(5-10)(5-10)式可由式可由下述的条件下述的条件(5-11)(5-11)式和式和(5-12)(5-12)式式 来代替：来代替：5x5x1 1+4x+4x2 224+yM (5-11)24+yM (5-11)7x7x1 1+3x+3x2 245+(1-y)M (5-12)45+(1-y)M (5-12)其中其中MM是充分大的数是充分大的数 ,y,y是是0-10-1

8、变量。变量。v可以验证，当可以验证，当y=0y=0时，时，(5-11)(5-11)式就是式就是(5-9)(5-9)式，式，而而(5-12)(5-12)式自然成立，因而是多余的。式自然成立，因而是多余的。v当当y=1y=1时时,(5-12),(5-12)式就是式就是(5-10)(5-10)式，式，而而(5-11)(5-11)式是多余的。式是多余的。v引入的变量引入的变量y y不必出现在目标函数内，不必出现在目标函数内，即认为在目标函数式内即认为在目标函数式内y y的系数为的系数为0 0。5x5x1 1+4x+4x2 224 24 (5-9 )(5-9 )车运车运 7x 7x1 1+3x+3x2

9、245 45 (5-10)(5-10)船运船运v为了保证这为了保证这mm个约束条件只有一个起作用，个约束条件只有一个起作用，引入引入mm个个0-10-1变量变量y yi i(i(i=1,2,=1,2,，m)m)和一个充分大的常数和一个充分大的常数MM。（2 2）在）在mm个互相排斥的约束条件个互相排斥的约束条件(型型)：i1 i1x x1 1+i2i2x x2 2+ininx xn nbbi i，i=1i=1，2 2，,m,m 中只有一个起作用中只有一个起作用定义逻辑变量定义逻辑变量y yi i :MM为任意大为任意大 的正数，则有下式成立：的正数，则有下式成立：i1 i1x x+i2i2x

10、x2 2+ininx xn nbbi i+y+yi iMM，i=1,2,i=1,2,，m (5-13)m (5-13)y y1 1+y+y2 2+y ymm=m-1 (5-14)=m-1 (5-14)v这是因为，由于这是因为，由于(5-14)(5-14)式，式，mm个个y yi i中只有一个能取中只有一个能取0 0值，值，设设y yi i*=0*=0，代入，代入(5-13)(5-13)式，式，就只有就只有i=i*i=i*的约束条件起作用，的约束条件起作用，而别的式子都是多余的。而别的式子都是多余的。i1 i1x x+i2i2x x2 2+ininx xn nbbi i+y+yi iMM，i=1

11、,2,i=1,2,，m (5-13)m (5-13)y y1 1+y+y2 2+y ymm=m-1 (5-14)=m-1 (5-14)例：例：利用利用0 0 1 1变量对下列各题分别表示成变量对下列各题分别表示成 一般线性约束条件一般线性约束条件（a a）x x 1 1+x+x 2 2 2 2 或或 2 2x x 1 1+3x+3x 2 2 5;5;解：解：（b b）变量）变量 x x 只能取值只能取值0 0、3 3、5 5 或或 7 7 中的一个中的一个 ;（c c）变量）变量x x 或等于或等于 0 0，或，或 50;50;（d d）若）若 x x1 1 2 2，则，则 x x2 2 1

12、1，否则，否则x x2 2 4;4;（e e）以下四个约束条件中至少满足两个）以下四个约束条件中至少满足两个 x x1 1+x+x2 2 5 5，x x1 1 2 2，x x3 3 2 2，x x3 3+x+x4 4 6 .6 .3.3.3.3.关于固定费用的问题关于固定费用的问题关于固定费用的问题关于固定费用的问题v在讨论线性规划时，在讨论线性规划时，有些问题是要求使成本为最小。有些问题是要求使成本为最小。这时总假定固定成本为常数，这时总假定固定成本为常数，并在线性规划的模型中不必明显列出。并在线性规划的模型中不必明显列出。v但有些固定费用但有些固定费用(固定成本固定成本)的问题的问题 不能

13、用一般线性规划来描述，不能用一般线性规划来描述，但可改变为混合整数线性规划来解决，见下例。但可改变为混合整数线性规划来解决，见下例。例例例例5:5:5:5:某工厂为了生产某种产品，某工厂为了生产某种产品，有几种不同的生产有几种不同的生产 方式可供选择，方式可供选择，如选定投资高的生产方式如选定投资高的生产方式(选购自动化程度高的设备选购自动化程度高的设备)，由于产量大，因而分配到每件产品的变动成本就降低；由于产量大，因而分配到每件产品的变动成本就降低；反之，如选定投资低的生产方式，反之，如选定投资低的生产方式，将来分配到每件产品的变动成本可能增加，将来分配到每件产品的变动成本可能增加，所以必须

14、全面考虑。所以必须全面考虑。今设有三种方式可供选择，令今设有三种方式可供选择，令v x xj j表示采用第表示采用第j j种方式时的产量；种方式时的产量；v c cj j表示采用第表示采用第j j种方式时每件产品的变动成本；种方式时每件产品的变动成本；v k kj j表示采用第表示采用第j j种方式时的固定成本。种方式时的固定成本。为了说明成本的特点，暂不考虑其他约束条件。为了说明成本的特点，暂不考虑其他约束条件。问题的目标是使所有产品的总生产费用为最小问题的目标是使所有产品的总生产费用为最小.解：解：解：解：采用各种生产方式的总成本分别为：采用各种生产方式的总成本分别为：v在构成目标函数时，

15、为了统一在一个问题中讨论，在构成目标函数时，为了统一在一个问题中讨论，现引入现引入0-10-1变量变量y yj j，令，令于是目标函数于是目标函数min z=(kmin z=(k1 1y y1 1+c+c1 1x x1 1)+(k)+(k2 2y y2 2+c+c2 2x x2 2)+(k)+(k3 3y y3 3+c+c3 3x x3 3)(5-15)(5-15)式这个规定可由以下式这个规定可由以下式这个规定可由以下式这个规定可由以下3 3个线性约束条件表示：个线性约束条件表示：个线性约束条件表示：个线性约束条件表示：vx xj jyyj jMM，j=1,2,3 (5-16)j=1,2,3

16、(5-16)v其中其中MM是个充分大的常数。是个充分大的常数。v(5-16)(5-16)式说明，当式说明，当x xj j0 0时时y yj j必须为必须为1 1；v当当x xj j=0=0时只有时只有y yj j为为0 0时才有意义，时才有意义，v所以所以(5-16)(5-16)式完全可以代替式完全可以代替(5-15)(5-15)式式 二二二二 0-10-10-10-1型整数规划的一般解法型整数规划的一般解法型整数规划的一般解法型整数规划的一般解法-隐枚举法隐枚举法v解解0-10-1型整数规划最容易想到的方法，型整数规划最容易想到的方法，和一般整数线性规划的情形一样，就是穷举法，和一般整数线性

17、规划的情形一样，就是穷举法，v即检查变量取值为即检查变量取值为0 0或或1 1的每一种组合，的每一种组合，比较目标函数值以求得最优解，比较目标函数值以求得最优解，这就需要检查变量取值的这就需要检查变量取值的2 2n n个组合。个组合。v对于变量个数对于变量个数n n较大较大(例如例如n n10)10)，这几乎是不可能的。这几乎是不可能的。v而隐枚举法就是在此基础上改进的，而隐枚举法就是在此基础上改进的，通过加入一定的条件，就能较快的求得最优解。通过加入一定的条件，就能较快的求得最优解。v只检查变量取值的组合的一部分，只检查变量取值的组合的一部分，就能求到问题的最优解，就能求到问题的最优解，这样

18、的方法称为这样的方法称为隐枚举法隐枚举法(implicit enumeration)(implicit enumeration)，分枝定界法也是一种隐枚举法。分枝定界法也是一种隐枚举法。其其解题解题关键是寻找可行解，产生过滤条件关键是寻找可行解，产生过滤条件。过滤条件：过滤条件：是满足目标函数值优于计算过的可行解目标函数值是满足目标函数值优于计算过的可行解目标函数值的约束条件。的约束条件。v当然，对有些问题隐枚举法并不适用，当然，对有些问题隐枚举法并不适用，所以有时穷举法还是必要的。所以有时穷举法还是必要的。下面举例说明求解下面举例说明求解下面举例说明求解下面举例说明求解0-10-10-10-

19、1型整数规划的隐枚举法型整数规划的隐枚举法型整数规划的隐枚举法型整数规划的隐枚举法例例例例6:6:6:6:目标函数目标函数 max z=3xmax z=3x1 1-2x-2x2 2+5x+5x3 3约束条件：约束条件：v x x1 1+2x+2x2 2-x-x3 32 2 v x x1 1+4x+4x2 2+x+x3 34 (5-17)4 (5-17)v x x1 1+x+x2 23 3 v 4x 4x2 2+x+x3 36 6 v x x1 1，x x2 2，x x3 3=0=0或或1 1 解题时先通过试探的方法找一个可行解，解题时先通过试探的方法找一个可行解，容易看出容易看出(x(x1 1

20、，x x2 2，x x3 3)=(1)=(1，0 0，0)0)就是合于就是合于条件的，条件的，算出相应的目标函数值算出相应的目标函数值z=3z=3。v我们在求最优解时，我们在求最优解时，对于极大化问题，当然希望对于极大化问题，当然希望z3z3，于是增加一个约束条件：于是增加一个约束条件：3x3x1 1-2x-2x2 2+5x+5x3 333 后加的条件称为后加的条件称为过滤的条件过滤的条件(filtering constraint)(filtering constraint)。这样，原问题的线性约束条件就变成这样，原问题的线性约束条件就变成5 5个。个。用全部枚举的方法，用全部枚举的方法，3

21、3个变量共有个变量共有2 23 3=8=8个解，个解，原来原来4 4个约束条件，共需个约束条件，共需3232次运算。次运算。现在增加了过滤条件现在增加了过滤条件，如按下述方法进行，就可减少运算次数。如按下述方法进行，就可减少运算次数。将将5 5个约束条件按个约束条件按顺序排好顺序排好(表表5-5)5-5)，对每个解，依次代入约束条件左侧，求出数值，对每个解，依次代入约束条件左侧，求出数值，看是否适合不等式条件，看是否适合不等式条件，如某一条件不适合，同行以下各条件就不必再检查，如某一条件不适合，同行以下各条件就不必再检查，因而就减少了运算次数。因而就减少了运算次数。所以改进过滤条件，用所以改进

22、过滤条件，用3x3x1 1-2x-2x2 2+5x+5x3 35 5 代替代替，继续进行。继续进行。在计算过程中，若遇到在计算过程中，若遇到z z值已超过条件值已超过条件右边的值，应改变右边的值，应改变条件条件，使右边值为迄今为止最大者，使右边值为迄今为止最大者，然后继续作。然后继续作。例如，当检查点例如，当检查点(0(0，0 0，1)1)时，因时，因z=5(z=5(3)3)，这种对过滤条件的改进，更可以减少计算量。这种对过滤条件的改进，更可以减少计算量。v再改进过滤条件，用再改进过滤条件，用3x3x1 1-2x-2x2 2+5x+5x3 38 8 代替代替，再继续进行。再继续进行。v至至此此

23、，z z值值已已不不能能改改进进，即即得得到到最最优优解解，解解答答如如前前，但计算已简化。但计算已简化。v本例计算过程实际只作本例计算过程实际只作1616次运算。次运算。v即求得最优解即求得最优解(x(x1 1，x x2 2，x x3 3)=(1)=(1，0 0，1),max z=81),max z=8注意：注意：注意：注意：一般常重新排列一般常重新排列x xi i的顺序使目标函数中的顺序使目标函数中x xi i的系数的系数 是递增是递增(不减不减)的，在上例中，的，在上例中，改写改写 z=3xz=3x1 1-2x-2x2 2+5x+5x3 3=-2x=-2x2 2+3x+3x1 1+5x+

24、5x3 3v因为因为-2-2，3 3，5 5是递增的，变量是递增的，变量(x(x2 2，x x1 1，x x3 3)也按也按下述顺序取值：下述顺序取值：(0(0，0 0，0)0)，(0(0，0 0，1)1)，(0(0，1 1，0)0)，(0(0，1 1，1)1)，v这样，最优解容易比较早的发现。这样，最优解容易比较早的发现。再结合过滤条件的改进，更可使计算简化再结合过滤条件的改进，更可使计算简化再结合过滤条件的改进，更可使计算简化再结合过滤条件的改进，更可使计算简化步骤步骤：(1)(1)、用试探法，求出一个可行解，以它的目标值作、用试探法，求出一个可行解，以它的目标值作为当前最好值为当前最好值

25、Z Z0 0(2)(2)、增加过滤条件增加过滤条件Z Z Z Z0 0(3)(3)、将、将x xi i 按按c ci i由小由小大排列。最小化问题反之。大排列。最小化问题反之。maxZ=3x1-2x2+5x3x1+2x2-x3 2 x1+4x2+x3 4 x1+x2 3 4x2+x3 6 x1,x2,x3为为0或或1解：解：1.1.观察得解观察得解(x(x1 1,x,x2 2,x,x3 3)=(1,0,0)=(1,0,0)，Z Z0 0=3=3 2.2.过滤条件过滤条件：3x3x1 1-2x-2x2 2+5x+5x3 3 3 3 3.3.将将(x(x1 1 x x2 2 x x3 3)(x(x2 2 x x1 1 x x3 3)点点(x x2 2 x x1 1 x x3 3 )目标值目标值 Z Z0 0 当前最好值当前最好值 (0,0(0,0,0,0)0 3)0 5 (0,0,1)5 5 (0,1,0)3 (0,1,0)3 8)8 8 (1,0 (1,0,0,0)-2 )-2 (1,0,1)3 (1,0,1)3 (1,1,0)1 (1,1,0)1 (1,1 (1,1,1,1)6 )6 最优解最优解 x=(1,0,1)x=(1,0,1)T T Z=8Z=8maxZ=-2x2+3x1+5x3x1+2x2 -x3 2 x1+4x2+x3 4 x1+x2 3 4x2+x3 6