一般的整数规划模型的建立与求解课件.ppt

1、1数学建模理论与实践数学建模理论与实践 基于整数规划的数学建模基于整数规划的数学建模2基于整数规划的数学建模基于整数规划的数学建模n一、一般的整数规划模型的建立与求解一、一般的整数规划模型的建立与求解n二、二、0-1规划模型的建立与求解规划模型的建立与求解n三、指派模型的建立与求解三、指派模型的建立与求解3一、一般的整数规划模型的建立与求解一、一般的整数规划模型的建立与求解问题的提出：问题的提出：一般的一般的整数规划整数规划是指线性规划中的一类特殊的问题，其特是指线性规划中的一类特殊的问题，其特点是点是决策变量决策变量只取只取整数整数。建立整数规划模型如同建立一般线性规划模型一样，要确建立整数

2、规划模型如同建立一般线性规划模型一样，要确定决策变量、目标函数和约束条件。所不同的是，这里的可定决策变量、目标函数和约束条件。所不同的是，这里的可行解中各变量只取整数。如果只有行解中各变量只取整数。如果只有两个决策变量两个决策变量，可行解只，可行解只可能是可能是平面上坐标是整数的点平面上坐标是整数的点。因而在各决策变量有界的条。因而在各决策变量有界的条件下，可行解只可能是有限多个。这个特点使我们有可能用件下，可行解只可能是有限多个。这个特点使我们有可能用一些特殊方法求解整数规划模型。一些特殊方法求解整数规划模型。特别说明：对比整数规划问题，非整数规划问题的可行特别说明：对比整数规划问题，非整数

3、规划问题的可行解通常构成平面上的一个多边形，可行解有无穷多个。解通常构成平面上的一个多边形，可行解有无穷多个。4一、一般的整数规划模型的建立与求解一、一般的整数规划模型的建立与求解解下列整数规划模型：解下列整数规划模型：1212121212max64s.t.2413 27 ,0 ,Zxxxxxxxxxx为整数5一、一般的整数规划模型的建立与求解一、一般的整数规划模型的建立与求解（一）（一）模型解法之一：使用线性松弛模型模型解法之一：使用线性松弛模型（二）（二）模型解法之二：穷举法模型解法之二：穷举法（三）（三）模型解法之三：割平面法模型解法之三：割平面法（四）（四）模型解法之四：分支定界法模型

4、解法之四：分支定界法6一、一般的整数规划模型的建立与求解一、一般的整数规划模型的建立与求解（一）（一）模型解法之一：使用线性松弛模型模型解法之一：使用线性松弛模型线性松弛模型的定义：线性松弛模型的定义：去掉整数规划中的去掉整数规划中的整数要求整数要求后得到的非整数后得到的非整数规划问题称为原整数规划的线性松弛模型。规划问题称为原整数规划的线性松弛模型。注意，这里线性松弛模型的可行解的区域注意，这里线性松弛模型的可行解的区域（多边形）包含了整数规划的可行解的集合（多（多边形）包含了整数规划的可行解的集合（多边形内的整数点），因而线性松弛模型的解要边形内的整数点），因而线性松弛模型的解要优优于于整

5、数规划的解。整数规划的解。7一、一般的整数规划模型的建立与求解一、一般的整数规划模型的建立与求解整数规划模型：整数规划模型：1212121212max64s.t.2413 27 ,0 ,Zxxxxxxxxxx为整数12121212max64s.t.2413 27 ,0Zxxxxxxxx松弛模型：松弛模型：解为（2.5,2）8一、一般的整数规划模型的建立与求解一、一般的整数规划模型的建立与求解（二）（二）模型解法之二：穷举法模型解法之二：穷举法 先忽略整数的限制，求解其松弛模型。自然要先忽略整数的限制，求解其松弛模型。自然要求松弛模型的可行解是一个求松弛模型的可行解是一个有界区域有界区域；否则没

6、办法；否则没办法进行穷举求解。进行穷举求解。如同求解一般线性规划，先画出由诸不等式约如同求解一般线性规划，先画出由诸不等式约束确定的多边形。但是这里的可行解由在该多边区束确定的多边形。但是这里的可行解由在该多边区域内的域内的有限多个整数点有限多个整数点构成。构成。9一、一般的整数规划模型的建立与求解一、一般的整数规划模型的建立与求解122413xx1227xx10一、一般的整数规划模型的建立与求解一、一般的整数规划模型的建立与求解 整数规划的可行解应该含在松弛模型的可行解内部，整数规划的可行解应该含在松弛模型的可行解内部，并仅仅由在该多边区域内的有限多个整数点构成。并仅仅由在该多边区域内的有限

7、多个整数点构成。图中显示，共有图中显示，共有12个可行解，依次代入目标函数，得到个可行解，依次代入目标函数，得到一系列函数值：一系列函数值：整数点(0,0)(0,1)(0,2)(0,3)(1,0)(1,1)目标函数值04812610整数点(1,2)(2,0)(2,1)(2,2)(3,0)(3,1)目标函数值141216181822A、B两种机器分别购买两种机器分别购买3台和台和1台，产值最多增加台，产值最多增加22万元。万元。11一、一般的整数规划模型的建立与求解一、一般的整数规划模型的建立与求解（三）（三）模型解法之三：割平面法模型解法之三：割平面法 割平面法的思想及过程：在整数规划对应的割

8、平面法的思想及过程：在整数规划对应的线性松弛模型中逐次增加一个新约束（即割平线性松弛模型中逐次增加一个新约束（即割平面），割去原可行域中一部分不含整数解的区域，面），割去原可行域中一部分不含整数解的区域，逐次切割直至最终得到松弛问题可行域的一个最逐次切割直至最终得到松弛问题可行域的一个最优解顶点为整数解为止。优解顶点为整数解为止。特别说明：由线性规划的特点，最优解一定特别说明：由线性规划的特点，最优解一定能在可行解区域的某个顶点达到。能在可行解区域的某个顶点达到。新增约束必须满足的条件：新增约束必须满足的条件：(1)不能割去满足条件的整数点；不能割去满足条件的整数点；(2)必须将前一次模型的最

9、优解割去。必须将前一次模型的最优解割去。12一、一般的整数规划模型的建立与求解一、一般的整数规划模型的建立与求解整数规划模型：整数规划模型：1212121212max64s.t.2413 27 ,0 ,Zxxxxxxxxxx为整数12121212max64s.t.2413 27 ,0Zxxxxxxxx松弛模型：松弛模型：1212121212max64s.t.2413 27 4 ,0Zxxxxxxxxxx13一、一般的整数规划模型的建立与求解一、一般的整数规划模型的建立与求解（四）（四）模型解法之四：分支定界法模型解法之四：分支定界法详细参见文件：详细参见文件：分支定界法原理简介分支定界法原理简

10、介.pdf 分支定界法分支定界法是一种广义搜索算法，人工使用非常繁琐，但由于计算机的运算速度快的特点，这种算法十分适合计算机进行。分支定界分支定界法法是计算机最擅长的广义搜索穷举算法。14一、一般的整数规划模型的建立与求解一、一般的整数规划模型的建立与求解三种方法（穷举法、割平面法、分支定界法）小结与三种方法（穷举法、割平面法、分支定界法）小结与对照如下：对照如下：1、穷举法解整数规划问题的原理及算法：求出所有的可行解，代入目标函数比较求得最优解。2、割平面法的思想及过程：在整数规划的线性松弛模型中逐次增加一个新约束（即割平面），割去原可行域中一部分不含整数点的区域。逐次切割直至最终所得线性松

11、弛模型可行域的一个最优解顶点为整数解为止。新增约束必须满足的条件：(1)不能割去满足条件的整数点；(2)必须将前一次松弛模型的最优解（非整数解）割去。15一、一般的整数规划模型的建立与求解一、一般的整数规划模型的建立与求解三种方法（穷举法、割平面法、分支定界法）小结与三种方法（穷举法、割平面法、分支定界法）小结与对照如下：对照如下：3、分支定界法的一般原理及基本步骤：分支定界法思想就是不断降低上界，提高下界，最后使得上下界相等，即求得最优解。基本步骤：寻找替代问题并求解（放宽或取消原问题某些约束，并求解，一般取消整数约束）；分支与定界；剪支。16二、二、0-10-1规划模型的建立与求解规划模型

12、的建立与求解 1.0-1规划含义规划含义 0-1规划是整数规划中的特殊情况，此时决策变量只取0或1值。只取0或1值的变量称为0-1变量，决策变量为0-1变量的线性规划称为0-1规划。2.0-1规划模型典型解法：隐枚举法规划模型典型解法：隐枚举法 由于0-1规划是特殊的整数规划，显然可以使用整数规划的一切方法（如上述的线性松弛模型、穷举法、割平面法、分支定界法等方法）求解0-1规划。对一个有n个决策变量的0-1规划模型，其所要考虑的情况最多有2n种。如果变量不多，可以用穷举法来求解。隐枚举法的本质是穷举法，但是应用隐枚举法可以更快地得到最优解。详细参见文件：详细参见文件：隐枚举法简介隐枚举法简介

13、.pdf17三、指派模型的建立与求解三、指派模型的建立与求解1.指派模型含义指派模型含义 指派模型是一种特殊的指派模型是一种特殊的0-1规划模型，当然也是一种特殊规划模型，当然也是一种特殊的整数规划模型。毋庸置疑，其更是一种特殊的线性规划模的整数规划模型。毋庸置疑，其更是一种特殊的线性规划模型。型。在指派问题中假设：在指派问题中假设：（1）被指派的人数与任务的数目相等。）被指派的人数与任务的数目相等。（2）每个被指派的人员只完成一项任务，而且每项任务必有）每个被指派的人员只完成一项任务，而且每项任务必有一人去完成。一人去完成。（3）第）第i i个被指派的人去完成第个被指派的人去完成第j j项任

14、务的费用为项任务的费用为ci,j.矩阵矩阵(ci,j)称为效益矩阵。称为效益矩阵。18三、指派模型的建立与求解三、指派模型的建立与求解19三、指派模型的建立与求解三、指派模型的建立与求解2.指派模型的典型解法：指派模型的典型解法：匈牙利解法匈牙利解法 由于指派模型是特殊的由于指派模型是特殊的0-1规划模型，显然可以使用整数规划模型，显然可以使用整数规划的一切方法（如上述的线性松弛模型、穷举法、割平面规划的一切方法（如上述的线性松弛模型、穷举法、割平面法、分支定界法等方法），以及前述的隐枚举法来求解指派法、分支定界法等方法），以及前述的隐枚举法来求解指派模型。模型。对于指派模型，还有非常著名的典

15、型解法：匈牙利解法。对于指派模型，还有非常著名的典型解法：匈牙利解法。由于篇幅限制以及还要补充若干数学背景知识的原因，我们由于篇幅限制以及还要补充若干数学背景知识的原因，我们这里忽略讲解匈牙利解法。这里忽略讲解匈牙利解法。有兴趣的同学可以自学下列的有关内容。有兴趣的同学可以自学下列的有关内容。详细内容参见文件：详细内容参见文件：匈牙利解法简介匈牙利解法简介.pdf可参照的程序见下页可参照的程序见下页20三、指派模型的建立与求解三、指派模型的建立与求解附件：附件：匈牙利法求解指派问题的所有最优解的程序匈牙利法求解指派问题的所有最优解的程序 程序的特点描述：程序的特点描述：（A）是）是Matlab

16、程序；用到递归方法求方阵的积和式函数程序；用到递归方法求方阵的积和式函数per.m（小于（小于10阶可用函数阶可用函数perj.m求方阵的积和式）；求方阵的积和式）；（B）文件）文件zhipaic.m可求解指派问题的所有最优解；可求解指派问题的所有最优解；（C）但代入下例）但代入下例C则会死循环，原因待查！可能是个反例，则会死循环，原因待查！可能是个反例，说明该方法不适当。说明该方法不适当。C=6 29 13 9 20 3;29 19 36 32 4 32;27 30 16 20 1 10;8 35 24 34 5 30;6 5 32 1 17 36;17 21 23 36 12 11 21三

17、、指派模型的建立与求解三、指派模型的建立与求解 实际应用中，我们一般用计算机软件实际应用中，我们一般用计算机软件MATLAB/LINDO/LINGO来求解指派模型。但一个来求解指派模型。但一个严酷的事实严酷的事实是：是：MATLAB/LINDO/LINGO 软件一般仅仅求出其中的软件一般仅仅求出其中的一个解一个解。对于可能有多解的指派模型，如果要求出全部的解，应该对于可能有多解的指派模型，如果要求出全部的解，应该掌握好掌握好匈牙利解法匈牙利解法。但这个算法非常难以理解，编程也有难。但这个算法非常难以理解，编程也有难度，这在前面已经看到。度，这在前面已经看到。为了可以求解指派模型而又不采用匈牙利

18、解法，这里推为了可以求解指派模型而又不采用匈牙利解法，这里推荐采用荐采用穷举法穷举法求解求解小型的指派模型小型的指派模型。详细可参照下页的详细可参照下页的穷举法穷举法程序程序22三、指派模型的建立与求解三、指派模型的建立与求解 附件：附件：穷举法求解指派问题的所有最优解的程序穷举法求解指派问题的所有最优解的程序 程序的特点描述：程序的特点描述：（A）是）是Matlab程序；用到函数文件程序；用到函数文件zhipai.m；（B）文件）文件zhipai.m中调用中调用0-1整数线性规划函数整数线性规划函数bintprog求求解；解；（C）仅仅利用）仅仅利用zhipai.m的效果类似于的效果类似于LINDO/LINGO求解求解-仅求出一个解；仅求出一个解；（D）而利用）而利用穷举法穷举法以及上述函数以及上述函数zhipai.m可求解指派问题可求解指派问题的的所有最优解。所有最优解。23教材教材 P62 第第 1、2、3 题题要求：要求：1）解答题，写出具体解法；）解答题，写出具体解法；2）程序设计题，写出用有关软件实现的、）程序设计题，写出用有关软件实现的、并且是调试通过的程序。并且是调试通过的程序。书面作业书面作业