资源描述：
《matlab学习系列26.-整数规划》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、26.整数规划全部变量限制为整数的规划问题，称为纯整数规划；部分变量限制为整数的规划问题，称为混合整数规划；变量只取0或1的规划问题，称为0-1整数规划。整数规划问题，建议使用Lingo软件求解。常用的整数规划问题解法有：（1）分枝定界法：可求纯或混合整数线性规划；（2）割平面法：可求纯或混合整数线性规划；（3）隐枚举法：用于求解0-1整数规划，有过滤法和分枝法；（4）匈牙利法：解决指派问题（0-1规划特殊情形）；（5）蒙特卡罗法：求解各种类型规划。一、分枝定界法分支定界法的基本思想是：设有最大化的整数规划问题A，先解与之相应的线性规划问题B，若B的最优解不符
2、合A的整数条件，那么B的最优目标函数必是A的最优目标函数z*的上界，记作z2,而A的任意可行解的目标函数值将是z*的一个下界z1,分支定界法就是将B的可行域分成子区域（称为分支）的方法，逐步减小z2和增大z1,最终求到z*。例1分枝定界法原理示例：用Lingo软件求解：代码：max5x1+8x2stx1+x2<=65x1+9x2<=45endgin2运行结果：Globaloptimalsolutionfound.Objectivevalue:40.00000Objectivebound:40.00000Infeasibilities:0.000000Exten
3、dedsolversteps:0Totalsolveriterations:0VariableValueReducedCostX10.000000-5.000000X25.000000-8.000000RowSlackorSurplusDualPrice140.000001.00000021.0000000.00000030.0000000.000000二、0-1整数规划变量xi只能取值0,1，该约束条件可表示为：0≤xi≤1,xi∈N或xi(1-xi)=01.隐枚举法例2求解下列0-1规划问题：求解思路：（1）先试探性地求一个可行解，易看出(x1,x2,x3
4、)=(1,0,0)满足约束条件，故是一个可行解，相应的目标函数值为z=3.（2）由于是求极大值，故目标值z<3的解，不必检验是否满足约束条件即可删除，于是可增加一个约束条件（称为过滤条件）：(e)（3）用全部枚举法，3个变量共23=8种可能的组合，用过滤条件（并计算目标函数值，不断改进过滤条件）筛选每个可能的组合，最终得到问题的最优解。(x1,x2,x3)目标值约束条件过滤条件(a)(b)(c)(d)(e)(0,0,0)0×(1,0,0)3√√√√√3x1-2x2+x3≥3(0,1,0)-2×(0,0,1)5√√√√√3x1-2x2+x3≥5(1,1,0)1×
5、(1,0,1)8√√√√√3x1-2x2+x3≥8(1,1,1)6×(0,1,1)3×从而得到最优解为(1,0,1),最优值为z*=8.用Lingo软件求解：代码：max3x1-2x2+5x3stx1+2x2-x3<=2x1+4x2+x3<=4x1+x2<=34x2+x3<=6endint3运行结果：Globaloptimalsolutionfound.Objectivevalue:8.000000Objectivebound:8.000000Infeasibilities:0.000000Extendedsolversteps:0Totalsolverite
6、rations:0VariableValueReducedCostX11.000000-3.000000X20.0000002.000000X31.000000-5.000000RowSlackorSurplusDualPrice18.0000001.00000022.0000000.00000032.0000000.00000042.0000000.00000055.0000000.0000002.指派问题某公司准备分派n个工人X1,…,Xn做n件工作Y1,…,Yn,但由于任务性质和各人专长不同，因此各人完成每件工作的效率也就不同，于是产生一个问题：应指派哪
7、个人去完成哪件工作，使得工作效率最高？用效率矩阵表示：其中，元素cij≥0（i,j=1,…,n）表示指派第i人去完成第j项任务时的效率（或时间、成本等）。令则指派问题的一般数学模型为：对于上述问题，其实通俗来说，就是n×n矩阵中，选取n个元素，每行每列各1个元素，使得和最小。根据指派问题的特点，可以使用匈牙利算法来进行求解。匈牙利算法原理（匈牙利数学家狄·康尼格证明的两个定理）：定理1如果从指派问题效率矩阵[cij]的每一行元素中分别减去（或加上）一个常数ui（称为该行的位势），从每一列分别减去（或加上）一个常数vj（称为该列的位势），得到一个新的效率矩阵[b
8、ij],若其中bij=cij-ui-v
