《《工程运筹学》教学案卷》由会员分享，可在线阅读，更多相关《《工程运筹学》教学案卷（42页珍藏版）》请在金锄头文库上搜索。
1、工程运筹学教学案卷对象：交通运输、农业工程、环境工程时间：2010/08-2011/01沈阳农业大学 工程学院 赵 秀 荣* *Operations Research by Associate Prof Xiurong Zhao , Operations Research by Associate Prof Xiurong Zhao , Shenyang Agriculture University ,ChinaShenyang Agriculture University ,China第6章* *Operations Research by Associate Prof Xiurong Zh
2、ao , Operations Research by Associate Prof Xiurong Zhao , Shenyang Agriculture University ,ChinaShenyang Agriculture University ,China08级本科适用6 整数规划n 讲课4学时 ，实验2学时n6-1 整数规划数学模型n6-2 分枝定界法n6-3 “01型”整数规划的解法n6-4 指派问题为本章重点内容DateDate08级本科适用6-1 整数规划数学模型n 前面讨论了线性规划问题，其基变量的最优解可以是整 数，也可以是分数或小数。n实际生产中，很多问题的最优解必须
3、是整数才有实际意义。n比如，农机配备模型中，农业机械及拖拉机的台数；n列车、飞机编组中的列数与架数；再如果树栽培的株数、劳 动力分派的人数等等。n 只允许变量取整数最优解的线性规划称为整数规划n英文 Integer Programming，简称IP为整数规划问题。n整数规划是近三十年来发展起来的规划论中的一个分支。 DateDate08级本科适用6-1 整数规划数学模型n 我们能不能把线性规划的非整数规划最 优解经过“舍入化整”就行了呢？n例1：某农场拟用甲、乙两种拖拉机运输农 产品，每种拖拉机的耗油量和装卸、驾驶等 用工时、油量、工人数限制量及利润见表， 问两种拖拉机各用几台，才可获利最大？
4、n显然这是一个关于拖拉机配备的整数问题 DateDate08级本科适用6-1 整数规划数学模型拖拉 机用工 数（ 人）耗油量 （公斤 ）利润（ 百元）甲5220乙4510限制 量2413 我们们首先设设 x1 ，x2 分别为 使用甲、乙两种拖拉机的台 数，则其数学模型为： DateDate08级本科适用6-1 整数规划数学模型最后的约束条件（5）这个模型和（LP）模型的区别仅在于？ 现在不考虑（5），解（1）-（4）显然不是整数，不符合要求。假如我们显然不是整数，不符合要求。假如我们“ “舍入化整舍入化整” ”代入方程（2），就破坏了人数约数。 （以后我们称这样的问题为原问题相应的LP问题）利
5、用单纯形法很容易就可解得：就满足约束条件，因而是可行解 但不是最优解 DateDate08级本科适用6-1 整数规划数学模型n那么如何求解整数规划问题呢？n 我们首先想到的办法是穷举变量的所有可行的整数组合，再比较各组合的目标函数值，从中定出最优解。n 对于简单的问题来说，上述 方法是可行的，n 对于复杂的大问题，显然穷举法是不合适的。n常用的整数规划解法有分枝定界法、割平面法。n解0-1整数规划还有隐枚举法、指派匈牙利法等。n下面介绍分枝定界法 DateDate08级本科适用6-2 分枝定界法（Branch and Bound Method）n 由于整数规划是在相应的线性规划问题的基础上，增
6、加了变量为整数的约束条件。n所以其可行域就会缩小，其最优解也就不会优越于相应的线性规划问题的最优解。n对于求极大值问题来说，相应的线性规划目标函数值就成为其整数规划目标函数值得上界。DateDate08级本科适用6-2 分枝定界法（Branch and Bound Method）n 分枝定界法就是利用该性质来求解的一种方法n 设最大化的整数规划问题A，与它相对应的线性规划问题为B。n先 解问题B，若其最优解不符合A的整数条件，那么B的最优目标函数必是A的最优目标函数 Z* n 的上界，记作 ZB nA任意可行解目标函数值将是 Z*的一个下界 ZA 。DateDate08级本科适用6-2 分枝定
7、界法（Branch and Bound Method）n例：求解下面整数规划问题n解：（1）-（5）为问题A ，不考虑条件（5）的 （1）（4），为B（即A相应的LP问题）n解B得最优解为：n该最优解不符整数条件，但 是问题 A 的最优目标函数值 的上界。 DateDate08级本科适用6-2 分枝定界法（Branch and Bound Method）n分枝定界法首先注意一个非整数变量，如n 于是对问题分别增加约束条件n即将原问题分解为两个子问题 B1 ，B2 即两枝。n给每一枝增加一个约束条件，如图6-1（这并不影响问题A的可行域）n不考虑整数条件，解 B1 ，B2 DateDate08级
8、本科适用6-2 分枝定界法（Branch and Bound Method）图图6-26-2将B中的X1=4.81分成X15或X1 4 不考虑虑整数条件，解B1 ，B2 得最优解见表问 题 B1 问 题 B2解B1 ，B2，将可行域D分成 为为D1，D2将B1中的X2=2.1再分成X23或X22，即1 分解为为B3 ，B4 不考虑虑整数条件，解B3 ， B423DateDate08级本科适用6-2 分枝定界法（Branch and Bound Method）n解 B3 - 符合整数条件 n解 B4 - 不合整数条件n n那么还有没有必要继续分解那么还有没有必要继续分解B B4 4呢？呢？n n
9、没有，因为再分解没有，因为再分解 B B4 4，最后得到的目标函数值不会，最后得到的目标函数值不会 超过超过327327，而，而327327本身就小于本身就小于340340。DateDate08级本科适用6-2 分枝定界法（Branch and Bound Method）n但此时还不能认为 B3的解就是整数最优解。n因为问题 B2的z=341340，最优解可能在 340341之间有整数解，n于是对 B2分解即在 条件下构成问 题 B5 ，B6 ，经过计算 B5 ，B6 对应的目标函 数值都小于340。n为最优整数解，最优值为综上，所以DateDate08级本科适用6-2 分枝定界法（Branc
10、h and Bound Method）n从以上解的过程可以总结出分枝定界法求解整数 规划（最大化）问题的步骤如下：n （1）称原问题（整数规划）为问题A，称其相应不考虑整数条件的线性规划问题为B，解B。n （2）如B没有可行解则止，说明A也无可行解。n（3） 如B有最优解，判断是否符合整数条件，n如符合则它就是A的最优解，否则进行下一步。DateDate08级本科适用6-2 分枝定界法（Branch and Bound Method）n（4）在问题B中，任选一个不符合整数条件的变 量，如果 X j 的值是 b j ，进行如下分枝，它 们就是对问题B各个增加一个约束条件：n 小于 b j的最大整
11、数；n 大于 b j的最小整数。n（5）不考虑整数条件，解这两个后续问题。n 在还没有分解出的后继问题的各可行问题中，n选目标函数最大的问题，重新称这个问题为B，n回到步骤（3） 重复进行。DateDate08级本科适用6-3 “01型”整数规划的解法“01型”整数规划是整数规划中的特殊情形，规划中只限定决策变量取0或1两个数值，把 X j 称为“01”变量。“01”规划多用于选择投资场所，确定新上工程项目，指派工作任务等实际问题。DateDate08级本科适用6-3 “01型”整数规划的解法n例：某矿泉水公司拟在市东、西、南、北四个区设立 门市部，有9个位置点 可供选择。同 时考虑实际情况规
12、定：n 东区的点 中至少选两个；n 西区的点 中至少选一个；n 南区的点 中至少选一个； 北区 点全选 n如果 点被选中，设备投资 元，每年获利 n 元。但所有点投资总额不超过B元，问应该选择哪些点才可使年利润最大？ DateDate08级本科适用6-3 “01型”整数规划的解法n解：先引入“01”变量 ， 令n n 求满足前述约束条件：n n此例即为此例即为“ “01”01”型整数规划，型整数规划， 那么解决这样问题，最容易想的那么解决这样问题，最容易想的 就是穷举法，即检查变量取值就是穷举法，即检查变量取值0 0 或或1 1的每一个组合，并比较目标的每一个组合，并比较目标 函数求得最优解。
13、这就需要检查函数求得最优解。这就需要检查 变量取值的变量取值的 2 2 的的 n n次方次方个组合。个组合。 当当n n很大时，几乎是不可能的很大时，几乎是不可能的 。因此设计一些方法，只检查。因此设计一些方法，只检查 变量取值的组合的一部分，就变量取值的组合的一部分，就 能够求得问题的最优解。能够求得问题的最优解。n n这样的方法称为隐枚举法，这样的方法称为隐枚举法， 分枝定界法实际上也是一种隐分枝定界法实际上也是一种隐 枚举法。枚举法。 DateDate08级本科适用6-3 “01型”整数规划的解法下面举例说明一种解0-1型整数规划的隐枚举法DateDate08级本科适用6-3 “01型”
14、整数规划的解法先通过试换过试换 的方法找出一个可行解。容易看出得z=3。由于是求极大值问题值问题 ，当然希望于是增加一个约约束条件（0）： 是符合（1）（4）条件的可行解下面举例说明一种解0-1型整数规划的隐枚举法条件（0）称为过滤为过滤 条件（Filtering Constraint）。 这样这样 原问题问题 的线线性条件就变变成了5个 。 原题题如果用全部的枚举举法，3个变变量共有23=8个解，加上4 个约束条件，共需32次运算。 按照（0）（4）的顺序排好。对每个解，依次代入约束 方程左侧，求出数值，如下表1 。看是否符合不等式条件 ，如果不符合，同行以下各条件就不必检查，因而就减少 了运算次数。DateDate08级本科适用6-3 “01型”整数规划的解法约 束 条 件满足条件 否 是Z值（0）（1）（2）（3）（4）05-11015-2如此检查检查 下去，结结果见见下个幻灯片 DateDate08级本科适用6-3 “01型”整数规划的解法约 束 条 件满足条件 否 是Z值（0）（1）（2）（3）（4）0 5 -2 3 3 8 1 6-11 1 0215 1 2600 110 1 53 8经过经过 24次运算求得最优优解：，DateDate08级本科适用6-3 “01型”整数规划的解法约
