整数规划与matlab.ppt

该【整数规划与matlab 】是由【1485173816】上传分享，beplayapp体育下载一共【90】页，该beplayapp体育下载可以免费在线阅读，需要了解更多关于【整数规划与matlab 】的内容，可以使用beplayapp体育下载的站内搜索功能，选择自己适合的beplayapp体育下载，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此beplayapp体育下载到您的设备，方便您编辑和打印。整数规划与matlab设:xj表示用Bj(j=…n)种方式下料根数模型:整数规划的模型例三、机床分配问题设有m台同类机床,要加工n种零件。已知各种零件的加工时间分别为a1,a2,…an,问如何分配,使各机床的总加工任务相等,或者说尽可能平衡。整数规划的模型设:1分配第i台机床加工第j种零件;xij=(i=1,2,…,m;j=1,2,…,n)0相反。于是,第i台机床加工各种零件的总时间为:因此,求xij,使得又由于一个零件只能在一台机床上加工,所以有整数规划的模型整数规划一般形式依照决策变量取整要求的不同,整数规划可分为纯整数规划、全整数规划、混合整数规划、0-1整数规划。整数规划的数学模型部分或者全部为整数纯整数规划:所有决策变量要求取非负整数(这时引进的松弛变量和剩余变量可以不要求取整数)。全整数规划:除所有决策变量要求取非负整数外,系数aij和常数bi也要求取整数(这时引进的松弛变量和剩余变量也必须是整数)。混合整数规划:只有一部分的决策变量要求取非负整数,另一部分可以取非负实数。0-1整数规划:所有决策变量只能取0或1两个整数。整数规划的数学模型从数学模型上看整数规划似乎是线性规划的一种特殊形式,求解只需在线性规划的基础上,通过舍入取整,寻求满足整数要求的解即可。但实际上两者却有很大的不同,通过舍入得到的解(整数)也不一定就是最优解,有时甚至不能保证所得倒的解是整数可行解。整数规划与线性规划的关系例:设整数规划问题如下首先不考虑整数约束,得到线性规划问题(一般称为松弛问题)。整数规划与线性规划的关系且为整数用图解法求出最优解x1=3/2,x2=10/3且有Z=29/6x1x2⑴⑵33(3/2,10/3)现求整数解(最优解):如用“舍入取整法”可得到4个点即(1,3),(2,3),(1,4),(2,4)。显然,它们都不可能是整数规划的最优解。按整数规划约束条件,其可行解肯定在线性规划问题的可行域内且为整数点。故整数规划问题的可行解集是一个有限集,如图所示。整数规划与线性规划的关系