matlab学习系列26.-整数规划

matlab学习系列26.-整数规划

ID:15461431

大小:207.23 KB

页数:17页

时间:2018-08-03

matlab学习系列26.-整数规划_第1页
matlab学习系列26.-整数规划_第2页
matlab学习系列26.-整数规划_第3页
matlab学习系列26.-整数规划_第4页
matlab学习系列26.-整数规划_第5页
资源描述:

《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

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。