整数0-1规划

c7x7b1x1+b2x2+…+b7x7≤Bx1+x2+x3≤2x4+x5≥1x6+x7≥1xi=0或1,i=1,2,…,7于是建立下列模型:0-1规划的解法1、枚举法适用于变量个数n比较少书P112,例42、隐枚举法对于变量个数n比较大,枚举法不可取。因此常设计一些方法,只检查变量取值的组合的一部分,就能得到问题的最优解。当然,对于有些问题隐枚举法并不适用,所以有时枚举法还是必要的。例求解0-1型整数规划问题Maxz=8x1+2x2-4x3-7x4-5x53x1+3x2+x3+2x4+3x5≤45x1+3x2-2x3-x4+x5≤4xj=0或1,j=1,2,…,5变成标准型,要求如下:⑴目标函数求极大化。对于目标函数为Minz的极小化问题,令z′=-z,使其变为目标函数为Maxz′的极大化问题。⑵目标函数中所有变量的系数都为正数。如果目标函数中变量xj的系数为负数,令xj′=1-xj,把模型中的xj用xj′代换。⑶变量的排列顺序按变量在目标函数中的系数值从小到大排列。求解0-1型整数规划,可使用分枝定界法。下面用实例说明:x2=x3′=x5′=x4′=x1=1,z=10,不可行z=6,不可行z=5,不可行z=3,不可行z=2,不可行x2=0x1=0z=4,可行x3′=0x3′=0z=8,不可行x5′=0x5′=0z=1z=-2x4′=0x4′=0最优解为x2=0,x3′=0,x5′=1,x4′=1,x1=1。于是,原问题的最优解为z*=4,x1*=1,x2*=0,x3*=1-0=1,x4*=1-1=0,x5*=1-1=0令x3′=1-x3,x4′=1-x4,x5′=1-x5,得Maxz=2x2+4x3′+5x5′+7x4′+8x1-163x2-x3′-3x5′-2x4′+3x1≤-2①3x2+2x3′-x5′+x4′+5x1≤6②x2,x3′,x5′,x4′,x1=0或1