在整数规划建模中,经常会使用到0-1变量来辅助建模,将模型表述为IP模型或BIP模型,下面是一些常见的整数规划建模技巧
使用辅助0-1变量实现“非此即彼”约束
处理方式如下图,M是一个较大的数,当约束的右边加上M时,无论x1和x2在取在取值范围之内的任意值,式子都是成立的,即该约束无效,没有起到限制变量取值的作用。那么只需要让其中一个约束失效即可,通过在两个约束的右边分别添加M y 1和 My2,并让y 1 + y 2 = 1 来实现
保留N个约束中的K个
函数有N个可能的值
固定收费问题
二进制表示法代替整数变量
当一个模型存在大量0-1变量和少量整数变量时,无法直接使用高效的BIP算法,这时候可以使用二进制表示法将原有的整数变量分解成多个0-1变量。当一个整数x xx的范围为[0,u]时,可以参考下图的方式将其分解为N个0-1变量具体的案例如下图所示
分段函数建模
当一个函数是一个分段分数时,即处于不同区域的x xx,其对应的函数表达式f ( x ) f(x)f(x)是不同的,在处理这种问题的时候,建模的方式如下:
具体的案例如下图所示
分段函数建模
如果无法理解上面的模型处理方式的话,可以仔细理解下面的图片