整数规划方法课件.ppt

1、1 整数规划的一般模型；整数规划的一般模型；整数规划解的求解方法；整数规划解的求解方法；整数规划的整数规划的软件求解方法；软件求解方法；0-10-1规划的模型与求解方法；规划的模型与求解方法；整数规划的应用案例分析。整数规划的应用案例分析。2 1.问题的提出问题的提出:固定资源分配问题固定资源分配问题3 4 在这个问题中，所求解均是整数，初看起来，在这个问题中，所求解均是整数，初看起来，似乎只要把已得到的带有分数或小数的解经过似乎只要把已得到的带有分数或小数的解经过“舍入化整舍入化整”就可以了，实际上这常常是不行的，就可以了，实际上这常常是不行的，因为化整后不见得是可行解，或虽是可行解但不因为

2、化整后不见得是可行解，或虽是可行解但不一定是最优解。这种求最优整数解的问题就是整一定是最优解。这种求最优整数解的问题就是整数规划。数规划。整数规划中如果所有的变量都限制为（非负）整数规划中如果所有的变量都限制为（非负）整数，称为纯整数规划；如果仅一部分变量限制整数，称为纯整数规划；如果仅一部分变量限制为整数，称为混合整数规划；整数规划一种特殊为整数，称为混合整数规划；整数规划一种特殊的情形是的情形是0-1规划，它的变量取值仅限于规划，它的变量取值仅限于0和和1。5 2.整数规划模型的一般形式整数规划模型的一般形式 问题是如何求解整数规划问题呢？问题是如何求解整数规划问题呢？能否设想先略去决策变

3、量整数约束，即变为线性能否设想先略去决策变量整数约束，即变为线性规划问题求解，再对其最优解进行取整处理呢？规划问题求解，再对其最优解进行取整处理呢？实际上，可借鉴这种思想来解决整数规划问题实际上，可借鉴这种思想来解决整数规划问题6 1.分枝定界法的基本思想分枝定界法的基本思想 7 1.分枝定界法的基本思想分枝定界法的基本思想 继续求解定界，重复下去，直到得到最优解为继续求解定界，重复下去，直到得到最优解为止止。8 2.分枝定界法一般步骤分枝定界法一般步骤 问题问题(B)(B)无可行解，则无可行解，则(A)(A)也无可行解，停止；也无可行解，停止；9 2.分枝定界法一般步骤分枝定界法一般步骤 1

4、0 2.分枝定界法一般步骤分枝定界法一般步骤 11 2.分枝定界法一般步骤分枝定界法一般步骤 分枝定界法分枝定界法.ppt12 3.割平面法的思想割平面法的思想 将原整数规划问题将原整数规划问题(A)(A)去掉整数约束变为线性规去掉整数约束变为线性规划问题划问题(B)(B)，引入线性约束条件，引入线性约束条件(称为称为GomoryGomory约束约束，几何术语割平面几何术语割平面)使问题使问题(B)(B)的可行域逐步缩小的可行域逐步缩小.每次切割掉的是问题非整数解的一部分，不切每次切割掉的是问题非整数解的一部分，不切掉任何整数解，直到最后使目标函数达到最优的整掉任何整数解，直到最后使目标函数达

5、到最优的整数解成为可行域的一个顶点时，即问题最优解。数解成为可行域的一个顶点时，即问题最优解。利用线性规划的求解方法逐步缩小可行域，最利用线性规划的求解方法逐步缩小可行域，最后找到整数规划的最优解。后找到整数规划的最优解。考虑纯整数规划问题：考虑纯整数规划问题：取整数jjinjjijnjjjxnjxmibxaxcz,2,10,1max11设其中设其中aij和和bi皆为整数（若不为整数时，可乘上一个倍数化皆为整数（若不为整数时，可乘上一个倍数化为整数）。为整数）。割平面法是割平面法是R.E.Gomory于于1958年提出的一种方法，它主要年提出的一种方法，它主要用于求解纯用于求解纯ILP。割平面

6、法是用增加新的约束来切割可行域，增加的新约束割平面法是用增加新的约束来切割可行域，增加的新约束称为割平面方程或切割方程。其称为割平面方程或切割方程。其基本思路为：基本思路为：若其松弛问题的最优解若其松弛问题的最优解X*不满足整数约束，则从不满足整数约束，则从X*的的非整分量中选取一个，用以构造一个线性约束条件，将其非整分量中选取一个，用以构造一个线性约束条件，将其加入原松弛问题中，形成一个新的线性规划，然后求解之加入原松弛问题中，形成一个新的线性规划，然后求解之。若新的最优解满足整数要求，则它就是整数规划的最优。若新的最优解满足整数要求，则它就是整数规划的最优解；否则重复上述步骤，直到获得整数

7、最优解为止。解；否则重复上述步骤，直到获得整数最优解为止。为最终获得整数最优解，每次增加的线性约束条件应当两为最终获得整数最优解，每次增加的线性约束条件应当两个基本性质：个基本性质：（1）已获得的不符合整数要求的）已获得的不符合整数要求的LP最优解不满足该线性最优解不满足该线性约束条件，从而不可能在以后的解中出现；约束条件，从而不可能在以后的解中出现；（2）凡整数可行解均满足该线性约束条件，因而整数最优）凡整数可行解均满足该线性约束条件，因而整数最优解始终被保留在每次剩余的线性规划可行域中。解始终被保留在每次剩余的线性规划可行域中。是整数2121212121,0,431.maxxxxxxxxx

8、tsxxz例例1 用割平面法求解整数规划问题用割平面法求解整数规划问题0,431.max432142132121xxxxxxxxxxtsxxz步骤步骤1：标准化其松弛问题：标准化其松弛问题B0Cj1100CBXBbx1x2x3x411x2x17/43/401103/41/41/41/4cj-zj001/21/2引进一个割平面来缩小可行域，割平面要切去松弛问题的非整引进一个割平面来缩小可行域，割平面要切去松弛问题的非整数最优解而又不要切去问题的的任一个整数可行解。数最优解而又不要切去问题的的任一个整数可行解。步骤步骤2：求一个割平面方程：求一个割平面方程（1）在最终表上任选一个含有不满足整数条件

9、基变量的）在最终表上任选一个含有不满足整数条件基变量的约束方程。如选约束方程。如选x1，则含，则含x1的约束方程为的约束方程为)3(434141431xxx（2）将所选择的约束方程中非基变量的系数及常数项进行）将所选择的约束方程中非基变量的系数及常数项进行拆分处理。具体规则是：将上述系数和常数项均拆分成一个拆分处理。具体规则是：将上述系数和常数项均拆分成一个整数加上一个非负真分数（纯小数）之和。则（整数加上一个非负真分数（纯小数）之和。则（3）式变为）式变为：)4(430410431431xxx很明显，（很明显，（5）左端为整数，右端）左端为整数，右端=b(i););for(arrange(j

10、):x(j)=0;);for(arrange(j):BIN(x(j););END 11min(1,2,)01(1,2,)njjjnijjijjzc xa xb imxorjn34 1.问题的提出问题的提出35实验室开放时间为上午实验室开放时间为上午8:008:00至晚上至晚上10:00;10:00;开放时间内须有且仅段一名学生值班开放时间内须有且仅段一名学生值班;规定大学生每周值班不少于规定大学生每周值班不少于8 8小时小时;研究生每周值班不少于研究生每周值班不少于7 7小时小时;每名学生每周值班不超每名学生每周值班不超3 3次次;每次值班不少于每次值班不少于2 2小时小时;每天安排值班的学生不超过每天安排值班的学生不超过3 3人，且其中必须人，且其中必须有一名研究生有一名研究生.试为该实验室安排一张人员的值班表，使总试为该实验室安排一张人员的值班表，使总支付的报酬这最少。支付的报酬这最少。1.问题的提出问题的提出36 2.模型的建立与求解模型的建立与求解37问问题题的的数数学学模模型型：3839Mathematical modeling cannot be learned by reading books or listening to lectures,but only by doing!-Practice!Thanks！