【大学】工程运筹学教学案卷.ppt

《【大学】工程运筹学教学案卷.ppt》由会员分享，可在线阅读，更多相关《【大学】工程运筹学教学案卷.ppt（42页珍藏版）》请在三一办公上搜索。

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

2、，简称IP为整数规划问题。整数规划是近三十年来发展起来的规划论中的一个分支。,6-1 整数规划数学模型,我们能不能把线性规划的非整数规划最优解经过“舍入化整”就行了呢？例1：某农场拟用甲、乙两种拖拉机运输农产品，每种拖拉机的耗油量和装卸、驾驶等用工时、油量、工人数限制量及利润见表，问两种拖拉机各用几台，才可获利最大？显然这是一个关于拖拉机配备的整数问题,6-1 整数规划数学模型,我们首先设 x1，x2 分别为使用甲、乙两种拖拉机的台数，则其数学模型为：,6-1 整数规划数学模型,最后的约束条件（5）,这个模型和（LP）模型的区别仅在于？现在不考虑（5），解（1）-（4）,显然不是整数，不符合要

3、求。假如我们“舍入化整”,代入方程（2），就破坏了人数约数。,（以后我们称这样的问题为原问题相应的LP问题）,利用单纯形法很容易就可解得：,就满足约束条件，因而是可行解,但不是最优解,6-1 整数规划数学模型,那么如何求解整数规划问题呢？我们首先想到的办法是穷举变量的所有可行的整数组合，再比较各组合的目标函数值，从中定出最优解。对于简单的问题来说，上述 方法是可行的，对于复杂的大问题，显然穷举法是不合适的。常用的整数规划解法有分枝定界法、割平面法。解0-1整数规划还有隐枚举法、指派匈牙利法等。下面介绍分枝定界法,6-2 分枝定界法（Branch and Bound Method）,由于整数规划

4、是在相应的线性规划问题的基础上，增加了变量为整数的约束条件。所以其可行域就会缩小，其最优解也就不会优越于相应的线性规划问题的最优解。对于求极大值问题来说，相应的线性规划目标函数值就成为其整数规划目标函数值得上界。,6-2 分枝定界法（Branch and Bound Method）,分枝定界法就是利用该性质来求解的一种方法 设最大化的整数规划问题A，与它相对应的线性规划问题为B。先 解问题B，若其最优解不符合A的整数条件，那么B的最优目标函数必是A的最优目标函数 Z*的上界，记作 ZB A任意可行解目标函数值将是 Z*的一个下界 ZA。,6-2 分枝定界法（Branch and Bound M

5、ethod）,例：求解下面整数规划问题解：（1）-（5）为问题A，不考虑条件（5）的（1）（4），为B（即A相应的LP问题）解B得最优解为：该最优解不符整数条件，但 是问题 A 的最优目标函数值 的上界。,6-2 分枝定界法（Branch and Bound Method）,分枝定界法首先注意一个非整数变量，如 于是对问题分别增加约束条件即将原问题分解为两个子问题 B1，B2 即两枝。给每一枝增加一个约束条件，如图6-1（这并不影响问题A的可行域）不考虑整数条件，解 B1，B2,6-2 分枝定界法（Branch and Bound Method）,图6-2,将B中的X1=4.81分成X15或X

6、1 4不考虑整数条件，解B1，B2得最优解见表,解B1，B2，将可行域D分成为D1，D2,将B1中的X2=2.1再分成X23或X22，即1分解为B3，B4 不考虑整数条件，解B3，B4,2,3,6-2 分枝定界法（Branch and Bound Method）,解 B3-符合整数条件 解 B4-不合整数条件,那么还有没有必要继续分解 B4 呢？,没有，因为再分解 B4，最后得到的目标函数值不会超过327，而327本身就小于340。,6-2 分枝定界法（Branch and Bound Method）,但此时还不能认为 B3的解就是整数最优解。因为问题 B2的z=341340，最优解可能在34

7、0341之间有整数解，于是对 B2分解即在 条件下构成问题 B5，B6，经过计算 B5，B6 对应的目标函数值都小于340。为最优整数解，最优值为,综上，所以,6-2 分枝定界法（Branch and Bound Method）,从以上解的过程可以总结出分枝定界法求解整数规划（最大化）问题的步骤如下：（1）称原问题（整数规划）为问题A，称其相应不考虑整数条件的线性规划问题为B，解B。（2）如B没有可行解则止，说明A也无可行解。（3）如B有最优解，判断是否符合整数条件，如符合则它就是A的最优解，否则进行下一步。,6-2 分枝定界法（Branch and Bound Method）,（4）在问题B

8、中，任选一个不符合整数条件的变量，如果 X j 的值是 b j，进行如下分枝，它们就是对问题B各个增加一个约束条件：小于 b j的最大整数；大于 b j的最小整数。（5）不考虑整数条件，解这两个后续问题。在还没有分解出的后继问题的各可行问题中，选目标函数最大的问题，重新称这个问题为B，回到步骤（3）重复进行。,6-3“01型”整数规划的解法,“01型”整数规划是整数规划中的特殊情形，规划中只限定决策变量取0或1两个数值，把 X j 称为“01”变量。“01”规划多用于选择投资场所，确定新上工程项目，指派工作任务等实际问题。,6-3“01型”整数规划的解法,例：某矿泉水公司拟在市东、西、南、北四

9、个区设立门市部，有9个位置点 可供选择。同时考虑实际情况规定：东区的点 中至少选两个；西区的点 中至少选一个；南区的点 中至少选一个；北区 点全选 如果 点被选中，设备投资 元，每年获利 元。但所有点投资总额不超过B元，问应该选择哪些点才可使年利润最大？,6-3“01型”整数规划的解法,解：先引入“01”变量，令 求满足前述约束条件：,此例即为“01”型整数规划，那么解决这样问题，最容易想的就是穷举法，即检查变量取值0或1的每一个组合，并比较目标函数求得最优解。这就需要检查变量取值的 2 的 n次方个组合。,当n很大时，几乎是不可能的。因此设计一些方法，只检查变量取值的组合的一部分，就能够求得

10、问题的最优解。,这样的方法称为隐枚举法，分枝定界法实际上也是一种隐枚举法。,6-3“01型”整数规划的解法,下面举例说明一种解0-1型整数规划的隐枚举法,6-3“01型”整数规划的解法,先通过试换的方法找出一个可行解。容易看出,得z=3。由于是求极大值问题，当然希望,于是增加一个约束条件（0）：,是符合（1）（4）条件的可行解,下面举例说明一种解0-1型整数规划的隐枚举法,条件（0）称为过滤条件（Filtering Constraint）。,这样原问题的线性条件就变成了5个。,原题如果用全部的枚举法，3个变量共有23=8个解，加上4个约束条件，共需32次运算。,按照（0）（4）的顺序排好。对每

11、个解，依次代入约束方程左侧，求出数值，如下表1。看是否符合不等式条件，如果不符合，同行以下各条件就不必检查，因而就减少了运算次数。,6-3“01型”整数规划的解法,0,5,-1,1,0,1,5,-2,如此检查下去，结果见下个幻灯片,6-3“01型”整数规划的解法,经过24次运算求得最优解：,，,6-3“01型”整数规划的解法,0,5,5,-2,在计算过程中，若遇到z值已超过条件（0）右边值，应改变条件（0），使右边为迄今为止的最大者，然后继续运算。,如当检查点（0，0，1）时，因z=53，改之为新的过滤条件，可减少更多的计算量。,3,3,8,0,2,1,1,1,6,2,6,8,如当检查点（1，

12、0，1）时，因z=85，改之为新的过滤条件，还可减少更多的计算量。此处略。,6-3“01型”整数规划的解法,为了使最优解比较早出现，一般重新排列X j的顺序，使目标函数中X j的系数是递增的。那么本例可改为：,约束方程与变量取值均按照顺序：,、,按照前面方法求解会更快取得最优解。共计算16次。,6-4 指派问题,在实际工作中，常常会碰到这样的问题，要指派几个人去完成几项不同的任务，每个人必须完成其中一项，而且仅仅一项。但由于各个人的专长不同，任务的难易程度也不一样，所以完成不同任务的效率就不同。那么，应该指派哪个人去完成哪项任务才能使总的效率最高（或需要总的时间最少）呢？这就是典型的指派问题。

13、例1：今欲指派赵、钱、孙、李四人加工A、B、C、D四种不同的零件，每人加工四种零件所需时间如下表，问应该指派谁加工何种零件可使总的花费时间最少？,6-4 指派问题,零件,人员,表6-4-1：(单位：工时),在类似的问题中，都必须给出像表6-4-1的数表称为效率矩阵或系数矩阵，其元素 表示指派第i人去完成第j项任务的效率。,6-4 指派问题,求解这类问题时，通常引入01变量，对于极小化问题，指派问题数学模型为：,约束条件（2）说明第j项任务只能由1人去完成；约束条件（3）说明第i人只能去完成一项任务。,极小问题,6-4 指派问题,指派问题是01规划的特例，也是运输问题的特例。即可以用01规划又可

14、以用运输问题的求解方法。这样做是不合算的。根据指派问题的特殊结构，我们有更为简便的方法，即匈牙利法（匈牙利人康尼格D.Koning发明）。指派问题的最优解性质：如果将指派问题的效率矩阵 C ij 的每一行（列）的各元素都减去该行（列）的最小元素，得到一个新的矩阵b ij，那么以（b ij）为系数矩阵求得的最优解和原问题相同。,6-4 指派问题,利用前述性质，可使原系数矩阵变为含有很多个0元素的新系数矩阵，而最优解保持不变。如果能在新的效率矩阵中找到n个不同行的且不同列的零元素；则令解矩阵 X ij 中对应的几个独立的零元素的元素取值为1，其它元素为0。将其代入目标函数得：Zb，它一定是最小。这

15、就是以 b ij为系数矩阵的指派问题的最优解。也就得到了原问题的最优解。下面以书中例题来说明指派问题的解法：,6-4 指派问题,第一步：变换效率矩阵，使各行各列都出现0元素：（1）效率矩阵每一行都减该行的最小元素；（2）效率矩阵每列都减该列最小元素。第二步：试指派，即找出不同行且不同列的0元素：（1）给只有一个0元素的行中的0画上圈，记作0，并划去与其同列的其余0元素（行搜索）记作；（2）给只有一个0元素的列中画0，并划去与其同行的其余0元素，记作；（列搜索）（3）反复进行（1）、（2），直至所有的0都被圈出为止；,6-4 指派问题,（4）若仍有没有画圈的0元素，且同行（列）的0元素至少有两个

16、（表示对这人可以从两项任务中指派其一），这可用不同方案去试探。从剩余的0元素最少的行（列）开始，比较这行各0元素加圈的数目，选择0元素少的那列（行）的这个0元素加圈（表示选择性多的要礼让选择性少的）。然后，划掉同行同列的其它0元素，反复进行，直到所有0元素都已被圈出为止。（5）若0元素的数目m等于矩阵的阶数n，那么该指派问题的最优解已经找到，若mn，转下一步。,6-4 指派问题,第三步：用最少直线覆盖效率矩阵中的0元素：（1）对没有0圈的行打“”；（2）对已打“”的行中的0元素所在列打“”；（3）对打“”列中的“0”所在行打“”；（4）重复、直至打不出新的“”；（5）对没有打“”的行画一横线，

17、对打“”的列画垂线。则效率矩阵中所有0元素被这些直线所覆盖。,6-4 指派问题,第四步：调整效率矩阵，使出现新的0元素：（1）找出未被划去的元素中最小元素，以其作为调整量；（2）矩阵中打“”的行各元素（不包括0和）都减，打“”列元素都加上。然后，去掉所有标记，转第二步。,6-4 指派问题,例2：（见效率矩阵）按上述步骤计算如下：,由于m=n=4，所以得最优这表示：安排由甲译俄文、乙译日文、丙译英文、丁译德文，所需总时间最少为：,为所求,每行都减去该行最小元素,每列都减去该列最小元素,试指派：给只有一个零元素的行的零元素划圈，并给其同列的零元素划,试指派：给只有一个零元素的列的零元素划圈，并给其

18、同行的零元素划,划圈的零元素所在位置指派为1，其余位置为零,6-4 指派问题,例3：求下表中所示效率矩阵的指派问题的最优解：,6-4 指派问题,，所以还没有解完，按第三步进行：1）对没有圈0的行打“”；2）对已打“”的行中的0元素所在列打“”；3）对打“”列中的“0”所在行打“”；4）重复直至打不出新的“”；5）对没有打“”的行画一横线，对打“”的列画垂线。,每一行都减该行的最小元素；,每一列都减该列的最小元素；,由于每一列都已经有零元素，不用再计算,先进行搜索，即对只有一个零元素的行的零元素画圈,进行列搜索，即对只有一个零元素的列的零元素画圈,6-4 指派问题,在没有被直线所覆盖的元素中找出

19、最小元素（2）对没有打“”的各行元素分别减2，（“0”除外）给打“”的列各元素分别加上2，（“0”除外）得到新阵（*）后，并按照前述第二步继续：,6-4 指派问题,m=n=5具有n个独立的0元素，这就得到了最优解，画出相应解矩阵，由解矩阵得最优指派方案：甲B、乙C、丙E、丁D、戊A,所需总时间为：,试指派：行搜索,试指派：列搜索,重复行、列搜索,对剩下的“0”元素，选择“0”最少的行或列中的“0”划圈，表示选择性多的礼让少的。,本题有多重解,6-4 指派问题,从以上讨论限于极小化问题，对极大化问题，（其中M是足够大的常数，通常选C ij 中最大的元素=M即可）。这时，系数矩阵变为：,即求：,可令：,6-4 指派问题,前述变换后，符合匈牙利法的条件，目标函数经变换后，即解,因为n M 为常数，所以当 取最小值时，,便为最大。,