资源描述：
《matlab学习系列26-整数规划》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、26.整数规划全部变量限制为整数的规划问题，称为纯整数规划；部分变量限制为整数的规划问题，称为混合整数规划；变量只取0或1的规划问题，称为0・1整数规划。整数规划问题，建议使用Lingo软件求解。常用的整数规划问题解法有：（1）分枝定界法：可求纯或混合整数线性规划；（2）割平面法：可求纯或混合整数线性规划；（3）隐枚举法：用于求解0・1整数规划，有过滤法和分枝法；（4）匈牙利法：解决指派问题（0・1规划特殊情形）；（5）蒙特卡罗法：求解各种类型规划。一、分枝定界法分支定界法的基本思想是：设有最大化的整数规划问题
2、A,先解与之相应的线性规划问题B,若B的最优解不符合A的整数条件，那么B的最优目标函数必是A的最优目标函数z*的上界，记作z2,而A的任意可行解的冃标函数值将是z*的一个下界zl,分支定界法就是将B的可行域分成子区域（称为分支）的方法，逐步减小z2和增大zl,最终求到Z*。例1分枝定界法原理示例：maxz=5X]+8x2S-1.x,+x2<65兀]+9x2<45x.>0,x.gZ(i=1,2)Pimaxs.t.maxs.t.maxs.t.Z=5xx+8x2x1+x2<65xx+9x2<45Xj>0,x,>4Z=
3、5町+8x2Ar】+占V65y+9x2V45yn0,x2<>3Z=5y+Sx2xx+a：2<65xx+9x2<45Xj>2,x2>4maxz=5Xj+8ys.t.Xj+*2<65巧+9x2<45<1,x2>4（巧）（耳）用Lingo软件求解:maxz=5xx+8x2MXj+x2<65“i+9x2<45Xj<1,a:2<4maxz=5Xj+8x2s.t.+x2<65xx+9x2<45xY<1,x2>5代码:max5xl+8x2stxl+x2<=65xl+9x2<=45endgin2运行结果：Globaloptim
4、alsolutionfound.Objectivevalue:40.00000Objectivebound:40•00000Infeasibilities:0.000000Extendedsolversteps:0Totalsolveriterations:0VariableValueReducedCostX20.0000005.000000-5.000000-8.000000RowSlackorSurplusDualPrice140.000001.00000021.0000000.00000030.00000
5、00.000000二、0・1整数规划变量易只能取值0,1,该约束条件可表示为:Xi(1-xz)=00<%/<1,兀岸N或1.隐枚举法例2求解下列0・1规划问题：maxz=3x,-2x2+5x3s.t.X]+2x2-x3<2(a)x}+4x2<4(b)%!+x2<3(c)化+心弘(d)求解思路：(1)先试探性地求一个可行解，易看Hd(xl,x2zx3)=(l,0,0)满足约束条件，故是一个可行解，相应的目标函数值为z=3・(2)由于是求极大值，故目标值zv3的解，不必检验是否满足约束条件即可删除，于是可增加一个约
6、束条件(称为过滤条件)：3西一2兀2+5x3>3(e)(3)用全部枚举法，3个变量共23=8种可能的组合，用过滤条件(并计算目标函数值，不断改进过滤条件)筛选每个可能的组合,最终得到问题的最优解。(X1,X2,X3)目标值约束条件过滤条件(a)(b)(c)(d)(e)(0,0,0)0X(1,0,0)3JJJJV3xi-2x2+x3^3(04,0)・2X(0,0,1)5JJVJV3xi-2x2+x3^5(1,1,0)1X(l,0zl)8JJVVJ3xi-2x2+x35:8(1,1,1)6X(0,1,1)3X从而得
7、到最优解为⑴0,1),最优值为z*=8.用Lingo软件求解：代码：max3x1-2x24-5x3stxl+2x2-x3<=2xl+4x2+x3<=4xl+x2<=34x2+x3<=6endint3运行结果:Globaloptimalsolutionfound.Objectivevalue:Objectivebound:Infeasibilities:8.0000008.0000000.000000Extendedsolversteps:VariableXIX2X3Value1.0000000.0000001.
8、000000ReducedCost-3.0000002.000000-5.000000Totalsolveriterations:DualPrice1.0000000.0000000.0000000.0000000.000000RowSlackorSurplus18.00000022.00000032.00000042.00000055.0000001.指派问题某公司准备分派〃个工人X
