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

数学建模理论与实践——基于整数规划的数学建模1数学建模理论与实践——基于整数规划的数学建模1基于整数规划的数学建模一、一般的整数规划模型的建立与求解二、0-1规划模型的建立与求解三、指派模型的建立与求解2基于整数规划的数学建模一、一般的整数规划模型的建立与求解2一、一般的整数规划模型的建立与求解问题的提出：一般的整数规划是指线性规划中的一类特殊的问题，其特点是决策变量只取整数。建立整数规划模型如同建立一般线性规划模型一样，要确定决策变量、目标函数和约束条件。所不同的是，这里的可行解中各变量只取整数。如果只有两个决策变量，可行解只可能是平面上坐标是整数的点。因而在各决策变量有界的条件下，可行解只可能是有限多个。这个特点使我们有可能用一些特殊方法求解整数规划模型。

特别说明：对比整数规划问题，非整数规划问题的可行解通常构成平面上的一个多边形，可行解有无穷多个。3一、一般的整数规划模型的建立与求解问题的提出：一一、一般的整数规划模型的建立与求解解下列整数规划模型：

4一、一般的整数规划模型的建立与求解解下列整数规划模型：4一、一般的整数规划模型的建立与求解（一）模型解法之一：使用线性松弛模型（二）模型解法之二：穷举法

（三）模型解法之三：割平面法

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

松弛模型：

解为（2.5,2）7一、一般的整数规划模型的建立与求解整数规划模型：松弛模型：一、一般的整数规划模型的建立与求解（二）模型解法之二：穷举法

先忽略整数的限制，求解其松弛模型。自然要求松弛模型的可行解是一个有界区域；否则没办法进行穷举求解。如同求解一般线性规划，先画出由诸不等式约束确定的多边形。但是这里的可行解由在该多边区域内的有限多个整数点构成。8一、一般的整数规划模型的建立与求解（二）模型解法之二：穷举法一、一般的整数规划模型的建立与求解9一、一般的整数规划模型的建立与求解9一、一般的整数规划模型的建立与求解

整数规划的可行解应该含在松弛模型的可行解内部，并仅仅由在该多边区域内的有限多个整数点构成。图中显示，共有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万元。10一、一般的整数规划模型的建立与求解整数规划的可行解应该一、一般的整数规划模型的建立与求解（三）模型解法之三：割平面法

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

松弛模型：

12一、一般的整数规划模型的建立与求解整数规划模型：松弛模型：一、一般的整数规划模型的建立与求解（四）模型解法之四：分支定界法详细参见文件：分支定界法原理简介.pdf

分支定界法是一种广义搜索算法，人工使用非常繁琐，但由于计算机的运算速度快的特点，这种算法十分适合计算机进行。分支定界法是计算机最擅长的广义搜索穷举算法。13一、一般的整数规划模型的建立与求解（四）模型解法之四：分支定一、一般的整数规划模型的建立与求解三种方法（穷举法、割平面法、分支定界法）小结与对照如下：1、穷举法解整数规划问题的原理及算法：求出所有的可行解，代入目标函数比较求得最优解。2、割平面法的思想及过程：在整数规划的线性松弛模型中逐次增加一个新约束（即割平面），割去原可行域中一部分不含整数点的区域。逐次切割直至最终所得线性松弛模型可行域的一个最优解顶点为整数解为止。新增约束必须满足的条件：(1)不能割去满足条件的整数点；(2)必须将前一次松弛模型的最优解（非整数解）割去。14一、一般的整数规划模型的建立与求解三种方法（穷举法、割平面法一、一般的整数规划模型的建立与求解三种方法（穷举法、割平面法、分支定界法）小结与对照如下：3、分支定界法的一般原理及基本步骤：分支定界法思想就是不断降低上界，提高下界，最后使得上下界相等，即求得最优解。基本步骤：⑴寻找替代问题并求解（放宽或取消原问题某些约束，并求解，一般取消整数约束）；⑵分支与定界；⑶剪支。15一、一般的整数规划模型的建立与求解三种方法（穷举法、割平面法二、0-1规划模型的建立与求解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规划模型，其所要考虑的情况最多有2^n种。如果变量不多，可以用穷举法来求解。隐枚举法的本质是穷举法，但是应用隐枚举法可以更快地得到最优解。详细参见文件：隐枚举法简介.pdf16二、0-1规划模型的建立与求解1.0-1规划三、指派模型的建立与求解1.指派模型含义指派模型是一种特殊的0-1规划模型，当然也是一种特殊的整数规划模型。毋庸置疑，其更是一种特殊的线性规划模型。在指派问题中假设：（1）被指派的人数与任务的数目相等。（2）每个被指派的人员只完成一项任务，而且每项任务必有一人去完成。（3）第i个被指派的人去完成第j项任务的费用为ci,j

.矩阵(ci,j)称为效益矩阵。17三、指派模型的建立与求解1.指派模型含义17三、指派模型的建立与求解18三、指派模型的建立与求解18三、指派模型的建立与求解2.指派模型的典型解法：匈牙利解法由于指派模型是特殊的0-1规划模型，显然可以使用整数规划的一切方法（如上述的线性松弛模型、穷举法、割平面法、分支定界法等方法），以及前述的隐枚举法来求解指派模型。对于指派模型，还有非常著名的典型解法：匈牙利解法。由于篇幅限制以及还要补充若干数学背景知识的原因，我们这里忽略讲解匈牙利解法。有兴趣的同学可以自学下列的有关内容。详细内容参见文件：匈牙利解法简介.pdf可参照的程序见下页19三、指派模型的建立与求解2.指派模型的典型解法：匈牙利解法三、指派模型的建立与求解附件：匈牙利法求解指派问题的所有最优解的程序

程序的特点描述：

（A）是Matlab程序；用到递归方法求方阵的积和式函数per.m（小于10阶可用函数perj.m求方阵的积和式）；

（B）文件zhipaic.m可求解指派问题的所有最优解；

（C）但代入下例C则会死循环，原因待查！可能是个反例，说明该方法不适当。

C=[629139

203;

291936324

32;

273016201

10;

83524345

30;

6

532

11736;

172123361211]

20三、指派模型的建立与求解附件：匈牙利法求解指派问题的所有最优三、指派模型的建立与求解实际应用中，我们一般用计算机软件MATLAB/LINDO/LINGO来求解指派模型。但一个严酷的事实是：MATLAB/LINDO/LINGO软件一般仅仅求出其中的一个解。对于可能有多解的指派模型，如果要求出全部的解，应该掌握好匈牙利解法。但这个算法非常难以理解，编程也有难度，这在前面已经看到。为了可以求解指派模型而又不采用匈牙利解法，这里推荐采用穷举法求解小型的指派模型。详细可参照下页的穷举法程序21三、指派模型的建立与求解实际应用中，我们一般用计三、指派模型的建立与求解附件：穷举法求解指派问题的所有最优解的程序

程序的特点描述：

（A）是Matlab程序；用到函数文件zhipai.m；

（B）文件zhipai.m中调用0-1整数线性规划函数bintprog求解；

（C）仅仅利用zhipai.m的效果类似于LINDO/LINGO求解---仅求出一个解；

（D）而利用穷举法以及上述函数zhipai.m可求解指派问题的所有最优解。22三、指派模型的建立与求解附件：穷举法求解指派问题的所有最优教材P62第1、2、3题要求：1）解答题，写出具体解法；

2）程序设计题，写出用有关软件实现的、并且是调试通过的程序。书面作业23教材P62第1、2、3题书面作业23数学建模理论与实践——基于整数规划的数学建模24数学建模理论与实践——基于整数规划的数学建模1基于整数规划的数学建模一、一般的整数规划模型的建立与求解二、0-1规划模型的建立与求解三、指派模型的建立与求解25基于整数规划的数学建模一、一般的整数规划模型的建立与求解2一、一般的整数规划模型的建立与求解问题的提出：一般的整数规划是指线性规划中的一类特殊的问题，其特点是决策变量只取整数。建立整数规划模型如同建立一般线性规划模型一样，要确定决策变量、目标函数和约束条件。所不同的是，这里的可行解中各变量只取整数。如果只有两个决策变量，可行解只可能是平面上坐标是整数的点。因而在各决策变量有界的条件下，可行解只可能是有限多个。这个特点使我们有可能用一些特殊方法求解整数规划模型。

特别说明：对比整数规划问题，非整数规划问题的可行解通常构成平面上的一个多边形，可行解有无穷多个。26一、一般的整数规划模型的建立与求解问题的提出：一一、一般的整数规划模型的建立与求解解下列整数规划模型：

27一、一般的整数规划模型的建立与求解解下列整数规划模型：4一、一般的整数规划模型的建立与求解（一）模型解法之一：使用线性松弛模型（二）模型解法之二：穷举法

（三）模型解法之三：割平面法

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

松弛模型：

解为（2.5,2）30一、一般的整数规划模型的建立与求解整数规划模型：松弛模型：一、一般的整数规划模型的建立与求解（二）模型解法之二：穷举法

先忽略整数的限制，求解其松弛模型。自然要求松弛模型的可行解是一个有界区域；否则没办法进行穷举求解。如同求解一般线性规划，先画出由诸不等式约束确定的多边形。但是这里的可行解由在该多边区域内的有限多个整数点构成。31一、一般的整数规划模型的建立与求解（二）模型解法之二：穷举法一、一般的整数规划模型的建立与求解32一、一般的整数规划模型的建立与求解9一、一般的整数规划模型的建立与求解

整数规划的可行解应该含在松弛模型的可行解内部，并仅仅由在该多边区域内的有限多个整数点构成。图中显示，共有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万元。33一、一般的整数规划模型的建立与求解整数规划的可行解应该一、一般的整数规划模型的建立与求解（三）模型解法之三：割平面法

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

松弛模型：

35一、一般的整数规划模型的建立与求解整数规划模型：松弛模型：一、一般的整数规划模型的建立与求解（四）模型解法之四：分支定界法详细参见文件：分支定界法原理简介.pdf

分支定界法是一种广义搜索算法，人工使用非常繁琐，但由于计算机的运算速度快的特点，这种算法十分适合计算机进行。分支定界法是计算机最擅长的广义搜索穷举算法。36一、一般的整数规划模型的建立与求解（四）模型解法之四：分支定一、一般的整数规划模型的建立与求解三种方法（穷举法、割平面法、分支定界法）小结与对照如下：1、穷举法解整数规划问题的原理及算法：求出所有的可行解，代入目标函数比较求得最优解。2、割平面法的思想及过程：在整数规划的线性松弛模型中逐次增加一个新约束（即割平面），割去原可行域中一部分不含整数点的区域。逐次切割直至最终所得线性松弛模型可行域的一个最优解顶点为整数解为止。新增约束必须满足的条件：(1)不能割去满足条件的整数点；(2)必须将前一次松弛模型的最优解（非整数解）割去。37一、一般的整数规划模型的建立与求解三种方法（穷举法、割平面法一、一般的整数规划模型的建立与求解三种方法（穷举法、割平面法、分支定界法）小结与对照如下：3、分支定界法的一般原理及基本步骤：分支定界法思想就是不断降低上界，提高下界，最后使得上下界相等，即求得最优解。基本步骤：⑴寻找替代问题并求解（放宽或取消原问题某些约束，并求解，一般取消整数约束）；⑵分支与定界；⑶剪支。38一、一般的整数规划模型的建立与求解三种方法（穷举法、割平面法二、0-1规划模型的建立与求解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规划模型，其所要考虑的情况最多有2^n种。如果变量不多，可以用穷举法来求解。隐枚举法的本质是穷举法，但是应用隐枚举法可以更快地得到最优解。详细参见文件：隐枚举法简介.pdf39二、0-1规划模型的建立与求解1.0-1规划三、指派模型的建立与求解1.指派模型含义指派模型是一种特殊的0-1规划模型，当然也是一种特殊的整数规划模型。毋庸置疑，其更是一种特殊的线性规划模型。在指派问题中假设：（1）被指派的人数与任务的数目相等。（2）每个被指派的人员只完成一项任务，而且每项任务必有一人去完成。（3）第i个被指派的人去完成第j项任务的费用为ci,j

.矩阵(ci,j)称为效益矩阵。40三、指派模型的建立与求解1.指派模型含义17三、指派模型的建立与求解41三、指派模型的建立与求解18三、指派模型的建立与求解2.指派模型的典型解法：匈牙利解法由于指派模型是特殊的0-1规划模型，显然可以使用整数规划的一切方法（如上述的线性松弛模型、穷举法、割平面法、分支定界法等方法），以及前述的隐枚举法来求解指派模型。对于指派模型，还有非常著名的典型解法：匈牙利解法。由于篇幅限制以及还要补充若干数学背景知识的原因，我们这里忽略讲解匈牙利解法。有兴趣的同学可以自学下列的有关内容。详细内容参见文件：匈牙利解法简介.pdf可参照的程序见下页42三、指派模型的建立与求解2.指派模型的典型解法：匈牙利解法三、指派模型的建立与求解附件：匈牙利法求解指派问题的所有最优解的程序

程序的特点描述：

（A）是Matlab程序；用到递归方法求方阵的积和式函数per.m（小于10阶可用函数perj.m求方阵的积和式）；

（B）文件zhipaic.m可求解指派问题的所有最优解；

（C）但代入下例C则会死循环，原因待查！可能是个反例，说明该方法不适当。

C=[62913