5.4 0-1 整数规划

《5.4 0-1 整数规划》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第四节0-1型整数规划本节内容的安排引入0-1变量的实际问题0-1型整数规划的解法如果线性规划中的所有决策变量的取值只能取0、1，则这类线性规划问题是一种特殊的整数规划问题称之为0-1规划，把只能取0或1值的变量称为0-1变量。0-1变量是一种逻辑变量。在某些特殊的实际问题中，我们只需做是非选择，如：是否采纳某方案，某任务是否可交给某人承担，集装箱是否装入某货物等，对于这类问题的变量可设置简化为0或1，x=1是0否决策变量只取0和1的线性规划问题，其数学模型如下：其中xj为0-1变量，也称二进制变量，逻

2、辑变量。xj仅取值0或1这个条件可由下述约束条件所代替。xj≤1,xj≥0，整数它和一般整数线性规划的约束条件形式是一致的。作用：在实际问题中，如果引入0-1变量，就可以把有各种情况需要分别讨论的线性规划问题统一在一个问题中讨论了。在本节我们先介绍引入0-1变量的实际问题：①投资场所（项目）的选定②相互排斥的约束条件③关于固定费用的问题然后，再研究0-1规划问题的一般解法---隐枚举法。一.引入0-1变量的实际问题1.投资场所的选定——相互排斥的计划例4:某公司拟在市东、西、南三区建立门市部。拟议中有7

3、个位置(点)Ai(i=1，2，…，7)可供选择。规定：在东区，由A1，A2，A3三个点中至多选两个；在西区，由A4，A5两个点中至少选一个；在南区，由A6，A7两个点中至少选一个。如选用Ai点，设备投资估计为bi元，每年可获利润估计为ci元，但投资总额不能超过B元。问应选择哪几个点可使年利润为最大?解题时先引入0-1变量xi(=1,2，…，7)于是问题可列成：在东区，由A1，A2，A3三个点中至多选两个；在西区，由A4，A5两个点中至少选一个；在南区，由A6，A7两个点中至少选一个。2.相互排斥的约束条

4、件在本章开始的例1(P114)中，关于运货的体积限制为5x1+4x2≤24(5-9)今设运货有车运和船运两种方式，上面的条件系用车运时的限制条件，如用船运时关于体积的限制条件为7x1+3x2≤45(5-10)这两条件是互相排斥的。为了统一在一个问题中，引入0-1变量y，令（1）两个约束条件中只有一个起作用车运船运于是(5-9)式和(5-10)式可由下述的条件(5-11)式和(5-12)式来代替：5x1+4x2≤24+yM(5-11)7x1+3x2≤45+(1-y)M(5-12)其中M是充分大的数,y

5、是0-1变量。可以验证，当y=0时，(5-11)式就是(5-9)式，而(5-12)式自然成立，因而是多余的。当y=1时,(5-12)式就是(5-10)式，而(5-11)式是多余的。引入的变量y不必出现在目标函数内，即认为在目标函数式内y的系数为0。5x1+4x2≤24(5-9)车运7x1+3x2≤45(5-10)船运为了保证这m个约束条件只有一个起作用，引入m个0-1变量yi(i=1,2,…，m)和一个充分大的常数M。（2）在m个互相排斥的约束条件(≤型)：αi1x1+αi2x2+…+αinxn≤bi，

6、i=1，2，…,m中只有一个起作用定义逻辑变量yi:M为任意大的正数，则有下式成立：αi1x１+αi2x2+…+αinxn≤bi+yiM，i=1,2,…，m(5-13)y1+y2+…+ym=m-1(5-14)这是因为，由于(5-14)式，m个yi中只有一个能取0值，设yi*=0，代入(5-13)式，就只有i=i*的约束条件起作用，而别的式子都是多余的。αi1x１+αi2x2+…+αinxn≤bi+yiM，i=1,2,…，m(5-13)y1+y2+…+ym=m-1(5-14)例：利用0–1变量对下列各题分

7、别表示成一般线性约束条件（a）x1+x22或2x1+3x2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，x3+x46.3.关于固定费用的问题在讨论线性规划时，有些问题是要求使成本为最小。这时总假定固定成本为常数，并在线性规划的模型中不必明显列出。但有些固定费用(固定成本)的问题不能用一般线性规划来描述，但可改变为混合整数线性规划来解决，见下例。例

8、5:某工厂为了生产某种产品，有几种不同的生产方式可供选择，如选定投资高的生产方式(选购自动化程度高的设备)，由于产量大，因而分配到每件产品的变动成本就降低；反之，如选定投资低的生产方式，将来分配到每件产品的变动成本可能增加，所以必须全面考虑。今设有三种方式可供选择，令xj表示采用第j种方式时的产量；cj表示采用第j种方式时每件产品的变动成本；kj表示采用第j种方式时的固定成本。为了说明成本的特点，暂不考虑其他约束条件。问题的目标是使所有产品