0-1变量及应用

四、0-1变量及应用

如前所述，若变量只能取值0或1，则称其为0-1变量.

0-1变量作为逻辑变量，常被用来表示系统是否处于某个特定状态，或者决策时是否取某个特定方案.例如，

当问题含有多项要素，而每项要素皆有两种选择时，可用一组0-1变量来描述.一般地，设问题有有限项要素，E1，E2，…，En，其中每项Ej有两种选择Aj和，则可令

那么，向量（x1，x2，…，xn）T就描述了问题的特定状态或方案.

在应用中，有时会遇到变量可以取多个整数值的问题.这时，利用0-1变量是二进制变量的性质，可以用一组0-1变量来取代该变量.例如，变量x可取0到9之间的任意整数时，可令

其中x0，x1，x2，x3，皆为0-1变量.

例4 （含有相互排斥的约束条件的问题）

设工序B的每周工时的约束条件为

现在假设工序B还有一种新的加工方式，相应的每周工时约束变成

如果工序B只能从两种加工方式中选择一种，那么，（a）和（b）就成为两个相互排斥的约束条件.为了统一在一个问题中引入0-1变量

于是，相互排斥的约束条件（a）和（b）可用下列三个约束条件统一起来：

其中M1和M2都是充分大的数.由（e），y1和y2中必定有一个是1，另一个是0.若y1=1而y2=0，即采用新加工方式，此时（d）就是（b），而（c）自然成立，因是多余的；反之，若y1=0，y2=1，即采用原加工方式，此时（c）就是（a），而（d）自然成立，因而是多余的.

一般地，若需要从p个约束条件

中恰好选择q个约束条件，则可以引入p个0-1变量

那么，约束条件组

就可以达到这个目的.上述约束条件组保证了在P个0-1变量中有一个p-q个为1，q个为0.凡取0值的yi对应的约束条件即为原约束条件；而取1的值的yi对应的约束条件将自然满足，因而是多余的.

在实际问题中，各xi的取值范围往往可以根据他们的意思进行估计.为各个约束条件选取的足够大的数Mi必须保证恒成立.有时为了方便，可以用一个共同的数M来代替各个Mi.此时，M≥max（M1，M2，…，MP）.

例5 （固定费用问题）有三种资源被用于生产三种产品，资源量、产品单件可变费用及售价、资源单耗量及组织三种产品生产的固定费用如表8-12所示.要求指定一个生产计划，使总收益最大.

解 总收益等于销售收入减去上述产品的固定费用和可变费用之和.建模碰到的困难主要是实现不能确切知道某种产品是否生产，因而不能确定相应的固定费用是否发生.下面借助0-1变量解决这个困难.

设xj是第j种产品的产量，j=1，2，3；再设

该问题的整数规划模型是

其中Mj为xj的某个上界.

例如，根据第3个约束条件，可取M1=100，M2=50，M3=34.

如果生产第j种产品，则其量xj＞0.此时，由约束条件xj≤Mjyj，知y1=1.因此，相应的固定费用在目标函数中将被考虑.如果不生产第j种产品，则产量xj=0.此时，由xj≤Mjyj可知，yj可以是0，也可以是1.但yj=1，不利于目标函数z的最大化，因而在问题的最优解中必然是yj=0，从而相应的固定费用在目标函数中将不被考虑.

例6 （工件排序问题）用4台机床加工3件产品.各产品的机床加工顺序及产品i机床j上的加工工时aij如表8-13所示.

由于某种原因，产品2的加工总时间不得超过d.现要求确定各件产品在机床上的加工方案，使得在最短的时间内加工完全部产品.

解 设xij（i=1，2，3；j=1，2，3）表示第i种产品在第j机床上加工的开始时间.

（1）同一件产品在不同的机床上的加工顺序约束

对于同一件产品，在下一台机床上加工的开始时间不得早于在上一台机床加工的结束时间，故因有

产品1 x11+a11≤x13及x13+a13≤x14，

产品2 x21+a21≤x22及x22+a22≤x24，

产品3 x32+a32≤x33.

（2）每一台机床对不同产品的加工顺序约束

一台机床在工作中，如已开始的加工还没有结束，则不能开始另一件产品的加工.对于机床1，有两种加工顺序.或先加工产品1，后加工产品2；或反之.对于其他3台机床，情况也类似.为了容纳两种相互排斥的约束条件，对于每台机床，分别引入0-1变量：

那么，每台机床上加工产品的顺序可用下列四组约束条件来保证：

机床1：x11+a11≤x21+My1及x21+a21≤x11+M（1-y1），

机床2：x22+a22≥x32+My2及x32+a32≤x22+M（1-y2），

机床3：x13+a13≤x33+My3及x33+a33≤x13+M（1-y3），

机床4：x14+a14≤x24+My4及x24+a24≤x14+M（1-y4）.

其中M是一个足够大的数.

各yj的意义是明显的.如当y1=0时，表示机床1先加工产品1，后加工产品2；当y1=1时，表示机床1先加工产品2，后加工产品1.y2，y3，y4的意义类似.

（3）产品2的加工总时间约束

产品的开始加工时间是x21，结束加工时间是x24+a24，故应有x24+a24-x21≤d.

（4）目标函数的建立

设全部产品加工完毕的结束时间为W.

由于三件产品的加工结束时间分别为x14+a14，x24+a24，x33+a33，故全部产品的实际加工结束时间为

因此，目标函数z的线性表达式为

综上所述，例6的整数规划模型为