5.4_0-1_整数规划.ppt

1、第4节0-1整数规划，这一节的安排，如果线性规划中所有的决策变量只能取0和1，那么这类线性规划问题就是一个特殊的整数规划问题叫做0-1规划，而只能取0或1的变量叫做0-1变量。0-1变量是一个逻辑变量。在一些特殊的实际问题中，我们只需要做出正确和错误的选择，比如是否采用某个方案，某个任务是否可以移交给某人，某个集装箱是否装载了某个货物等等。对于这样的问题，变量可以简化为0或1，决策变量只取0和1。数学模型如下：其中xj是0-1变量，也称为二元变量和逻辑变量。xj只取0或1的条件可以由以下约束条件代替。Xj1，xj0，整数，这与一般整数线性规划的约束形式是一致的。函数：在实际问题中，如果引入0-

2、1个变量，需要在不同情况下讨论的线性规划问题可以统一为一个问题。在这一节中，我们首先介绍了引入0-1变量的实际问题：投资场所(项目)选择互斥约束下的固定成本问题，然后研究了0-1规划问题的一般解法隐式枚举法。1.引入0-1变量1的实际问题。投资场所的选择4 : A公司计划在城市的东、西、南部设立销售办事处。有七个位置(点)可供选择。规定：在东区，从A1、A2、A3三个点中选择两个以上；在西方，至少选择A4和A5点中的一个；在南区，从A6和A7中选择至少一个点。如果选择艾点，设备投资估算为人民币，年利润估算为人民币，但总投资不能超过人民币。应该选择哪些点来使年利润最大化？0-1变量xi (=1，

3、2，7)是在解问题时首先引入的，所以问题可以列如下：在东区，从A1，A2，A3再多两个选择；在西方，至少选择A4和A5点中的一个；在南区，从A6和A7中选择至少一个点。2。互斥约束，在本章开头的示例1 (P114)中，装运的体积限制是5x1 4x224 (5-9)。今天，有两种运输方式，即卡车运输和海运。上述条件是汽车运输时的限制条件。例如，装运时的体积限制是7x1 3x245 (5-10)，这是相互排斥的。为了统一一个问题，引入了0-1变量Y，因此(1)两个约束条件中只有一个有效，即汽车运输和船舶运输，所以表达式(5-9)和(5-10)可以用下面的条件表达式(5-11)和(5-12)代替：5

4、x14x224ym可以证明，当y=0时，等式(5-11)是等式(5-9)，而等式(5-12)是自然建立的，因此是多余的。当y=1时，(5-12)是(5-10)，而(5-11)是冗余的。引入的变量y不必出现在目标函数中，也就是说，目标函数公式中的系数y被认为是0。5x1 4x224 (5-9)，7x1 3x245 (5-10)，为了确保这些m个约束中只有一个有效，引入了m 0-1变量yi(i=1，2，m)和足够大的常数m。(2)在M个互斥约束(类型)中：i1xi2x2inxnbi，i=1，2，M，只有一个起作用，定义逻辑变量yi:并且M是一个任意大的正数，那么下面的公式成立：i1x i2x2 i

5、nxnbi yiM，I=1，2，m (5-)这是因为(5-14)，只有一个M YIs可以取0值。假设yi *=0，代入(5-13)，只有i=i*的约束条件起作用，而其他公式是多余的。例如，i1x i2x2 inxnbi yiM，i=1，2，m (5-13) y1 y2 ym=m-1 (5-14)，下列问题用0 1变量表示为一般线性约束(a) x1x2或2x 1 3x 2 5；(b)变量x只能取0、3、5或7中的一个；(c)变量x等于0或50；(d)如果x1 2，x2 1，否则x2 4；(e)在以下四个约束中，至少满足两个x1 x2 5、x1 2、x3 2、X3X4 6。3.关于固定成本，当讨论

6、线性规划时，需要一些问题来最小化成本。此时，总是假设固定成本是恒定的，并且不需要在线性规划模型中明确列出。然而，一些固定成本问题不能用一般的线性规划来描述，但可以用混合整数线性规划来解决，如下例所示。为了生产某种产品，一个工厂有几种不同的生产方法可供选择，如选择一种投资高的生产方法(购买自动化程度高的设备)，由于产量大，分配给每种产品的可变成本降低；相反，如果选择低投资的生产模式，分配给每种产品的可变成本在未来可能会增加，因此必须综合考虑。今天，有三种方式可供选择，所以当第一种j方式被采用时，xj指示输出；Cj表示采用第j种方法时每种产品的可变成本；Kj表示采用jth方法时的固定成本。为了解释

7、成本的特性，暂时不考虑其他约束条件。问题的目标是使所有产品的总生产成本最小化。解决方案：采用各种生产方法的总成本分别为：在构造目标函数时，在一个问题中引入0-1变量yj进行统一讨论，使目标函数minz=(k1y1c 1 x 1)(K2y2c 2 x 2)(K3y3c 3)，(5-15)指定为(5-16)表明当xj0时yj必须为1；当xj=0时，只有当yj为0时才有意义，所以公式(5-16)可以完全代替公式(5-15)。隐式枚举法是求解0-1整数规划最简单的方法，也是穷举方法，就像一般的整数线性规划一样，即检查变量的每一个0或1的组合。对于大量的变量n(如n10)，这几乎是不可能的。在此基础上对

8、隐式枚举法进行了改进。通过增加一定的条件，可以快速得到最优解。通过只检查变量值组合的一部分，可以得到问题的最优解。此方法称为隐式枚举，分支定界方法也是隐式枚举方法。解决问题的关键是找到可行的解决方案并生成过滤条件。过滤条件：目标函数值优于可行解的计算目标函数值的约束条件。当然，隐式枚举法不适用于某些问题，所以有时穷举法是必要的。下面是一个例子来说明求解0-1整数规划的隐式枚举方法。示例6 :目标函数最大值Z=3x1-2x2x3约束：x1 2x 2-x32x 1 4x 2 x34(5-17)x1 x23 4x 2 x36 x1，x2，x3=0或1。在求解问题时，通过试算法找到一个可行的解，这很容

9、易看出(x1，x2)当我们寻求最优解时，我们当然希望z3为最大化问题，所以我们增加了一个约束条件：在3x1-2x2x33之后增加的条件称为滤波约束。这样，原来问题的线性约束变成了五个。用全枚举法，三个变量有23=8个解，原来的四个约束条件需要32次运算。现在，添加了过滤条件。如果使用以下方法，可以减少操作次数。按顺序排列五个约束(表5-5)，依次将每个解代入约束的左侧，计算数值，看是否适合不等式条件。如果某个条件不合适，就没有必要检查以下条件，从而减少操作次数。因此请改善过滤条件，并用3x1-2x2 5x35替换它们。在计算过程中，如果z值已经超过了条件的正确值，则应该改变条件，使正确值是迄今

10、为止最大的，然后继续。例如，当检查点(0，0，1)时，因为z=5(3)，过滤条件的这种改进可以减少计算量。然后改善过滤条件，改用3x1-2x2x38，然后继续。到目前为止，z值还不能提高，即得到了最优解，而且解还是和以前一样，但是计算已经简化了。在这种情况下，在计算过程中实际上只执行了16个操作。也就是说，获得了最优解(x1，x2，x3)=(1，0，1)和最大z=8。注：一般来说，xi的顺序是重新排列的，因此目标函数中的xi系数是增加的(而不是减少的)。在上面的例子中，z=3x1 -2x2x5x3=-2x3x1x5x3被重写，因为-2、3和5正在增加。结合滤波条件的改善，可以简化计算。步骤：(1)采用启发式方法，找到一个可行解，将其目标值作为当前最佳值Z0 (2)，增加过滤条件Z0 (3)，并按ci从小到大排列xi。将问题最小化，反之亦然。解决方案：1 .观测解(x1，x2，x3 )=(