《工程运筹学》教学案卷

《《工程运筹学》教学案卷》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、《工程运筹学》教学案卷对象：交通运输、农业工程、环境工程时间：2010/08-2011/01沈阳农业大学工程学院赵秀荣第6章整数规划6整数规划讲课4学时，实验2学时6-1整数规划数学模型6-2分枝定界法6-3“0—1型”整数规划的解法6-4指派问题为本章重点内容6/16/20216-1整数规划数学模型前面讨论了线性规划问题，其基变量的最优解可以是整数，也可以是分数或小数。实际生产中，很多问题的最优解必须是整数才有实际意义。比如，农机配备模型中，农业机械及拖拉机的台数；列车、飞机编组中的列数与架数；再如果树栽培的株数、劳动力分派的人数等等。只允许变量取整数最优解的线性规

2、划称为整数规划英文IntegerProgramming，简称IP为整数规划问题。整数规划是近三十年来发展起来的规划论中的一个分支。6/16/20216-1整数规划数学模型我们能不能把线性规划的非整数规划最优解经过“舍入化整”就行了呢？例1：某农场拟用甲、乙两种拖拉机运输农产品，每种拖拉机的耗油量和装卸、驾驶等用工时、油量、工人数限制量及利润见表，问两种拖拉机各用几台，才可获利最大？显然这是一个关于拖拉机配备的整数问题6/16/20216-1整数规划数学模型拖拉机用工数（人）耗油量（公斤）利润（百元）甲5220乙4510限制量2413我们首先设x1，x2分别为使用甲、乙

3、两种拖拉机的台数，则其数学模型为：6/16/20216-1整数规划数学模型最后的约束条件（5）这个模型和（LP）模型的区别仅在于？现在不考虑（5），解（1）--（4）显然不是整数，不符合要求。假如我们“舍入化整”代入方程（2），就破坏了人数约数。（以后我们称这样的问题为原问题相应的LP问题）利用单纯形法很容易就可解得：就满足约束条件，因而是可行解但不是最优解6/16/20216-1整数规划数学模型那么如何求解整数规划问题呢？我们首先想到的办法是穷举变量的所有可行的整数组合，再比较各组合的目标函数值，从中定出最优解。对于简单的问题来说，上述方法是可行的，对于复杂的大问题

4、，显然穷举法是不合适的。常用的整数规划解法有分枝定界法、割平面法。解0-1整数规划还有隐枚举法、指派匈牙利法等。下面介绍分枝定界法6/16/20216-2分枝定界法（BranchandBoundMethod）由于整数规划是在相应的线性规划问题的基础上，增加了变量为整数的约束条件。所以其可行域就会缩小，其最优解也就不会优越于相应的线性规划问题的最优解。对于求极大值问题来说，相应的线性规划目标函数值就成为其整数规划目标函数值得上界。6/16/20216-2分枝定界法（BranchandBoundMethod）分枝定界法就是利用该性质来求解的一种方法设最大化的整数规划问题A

5、，与它相对应的线性规划问题为B。先解问题B，若其最优解不符合A的整数条件，那么B的最优目标函数必是A的最优目标函数Z*的上界，记作ZBA任意可行解目标函数值将是Z*的一个下界ZA。6/16/20216-2分枝定界法（BranchandBoundMethod）例：求解下面整数规划问题解：（1）-（5）为问题A，不考虑条件（5）的（1）—（4），为B（即A相应的LP问题）解B得最优解为：该最优解不符整数条件，但是问题A的最优目标函数值的上界。6/16/20216-2分枝定界法（BranchandBoundMethod）分枝定界法首先注意一个非整数变量，如于是对问题分别增加

6、约束条件即将原问题分解为两个子问题B1，B2即两枝。给每一枝增加一个约束条件，如图6-1（这并不影响问题A的可行域）不考虑整数条件，解B1，B26/16/20216-2分枝定界法（BranchandBoundMethod）图6-2将B中的X1=4.81分成X1≥5或X1≤4不考虑整数条件，解B1，B2得最优解见表问题B1问题B2解B1，B2，将可行域D分成为D1，D2将B1中的X2=2.1再分成X2≥3或X2≤2，即1分解为B3，B4不考虑整数条件，解B3，B4236/16/20216-2分枝定界法（BranchandBoundMethod）解B3--符合整数条件解B

7、4--不合整数条件那么还有没有必要继续分解B4呢？没有，因为再分解B4，最后得到的目标函数值不会超过327，而327本身就小于340。6/16/20216-2分枝定界法（BranchandBoundMethod）但此时还不能认为B3的解就是整数最优解。因为问题B2的z=341>340，最优解可能在340~341之间有整数解，于是对B2分解即在条件下构成问题B5，B6，经过计算B5，B6对应的目标函数值都小于340。为最优整数解，最优值为综上，所以6/16/20216-2分枝定界法（BranchandBoundMethod）从以上解的过程可以总结出分枝