第7讲-整数规划.ppt

Matlab与数学建模计算机科学与信息工程系软件工程教研室许晓华xuxiaohua@tjau.edu.cn第7讲整数规划7.1线性整数规划问题7.2一般非线性整数规划问题7.30-1规划问题MATLAB不能直接进行整数规划，新版的MATLAB也只能进行0-1规划。解决整数规划需要下载新的基于Matlab优化工具箱的程序,如Iplsv_mex()%线性整数混合规划和线性0-1规划问题求解bnb20()%一般整数混合规划和0-1规划问题求解7.1线性整数规划例：f=-[21431];A=[02142;345-1-1];intlist=ones(5,1);B=[54;62];ctype=[-1;-1];xm=[0,0,3.32,0.678,2.57];xM=inf*ones(5,1);[res,b]=ipslv_mex(f,A,B,intlist,xM,xm,ctype)%因为返回的b=0，表示优化成功res=1904105b=07.2一般非线性整数规划Bnb20函数采用分枝定界法err字符串为空，则返回最优解。该函数尚有不完全之处，其解有时不是精确整数，可用下面语句将其化成整数。X=19.000004.000010.00005.00007.30-1规划问题求解使用该函数时，matlab7.0可能会出现如下的提示Theelementtypenamemustbeterminatedbythematchingend-tag/name.Couldnotparsethefile:d:\matlab7\toolbox\ccslink\ccslink\info.xml.解决方法是：找到d:\matlab7\toolbox\ccslink\ccslink\info.xml这个文件,用写字板打开，找到第5行nameLinkforCodeComposerStudio?/name把/name改成/name,保存。

例：f=[-3,2,-5];A=[12-1;141;110;041];B=[2;4;5;6];x=bintprog(f,A,B,[],[])f=[-3,2,-5];xm=[0;0;0];xM=[1;1;1];intlist=[1;1;1];A=[12-1;141;110;041];B=[2;4;5;6];ctype=-1*ones(4,1);[res,b]=ipslv_mex(f,A,B,intlist,xM,xm,ctype)res=101b=0*什么是整数规划在工程设计和企业管理中，常会遇到求决策变量取离散的非负整数值的线性规划问题。例如，最优调度的车辆数，设置的销售网点数，指派工作的人数等。这类问题在形式上与线性规划类似，只是比线性规划增加了某些约束条件，来限制全部或部分决策变量必须取离散的非负整数值。我们称之为整数线性规划问题，也经常简称为整数规划问题。引例：生产组织计划问题与选址问题引例（生产组织计划问题）某工厂在一个计划期内拟生产甲、乙两种大型设备。除了A、B两种部件需要外部供应且供应受到严格限制之外，该厂有充分的能力来加工制造这两种设备所需的其余零件，并且所需原材料和能源也可满足供应。每种设备所用部件数量和部件的供应限额以及设备的利润由表3.2.1给出。问该厂在本计划期内如何安排甲、乙设备的生产数量，才能获取最大利润？1025部件的最大供应量2034乙1516甲利润（百万）BA部件设备设x1，x2分别为该计划期内甲、乙设备的生产数量，Z为生产这两种设备可获得的总利润。数学模型为：maxZ=15x1?20x2s.t.6x1?4x2?25x1?3x2?10xi?{0,1,2,…}这是一个纯整数规划问题。引例（选址问题）某商业连锁集团拟在n个连锁店所在城市中建立m个配货中心