运筹学资料4整数规划.ppt

《运筹学资料4整数规划.ppt》由会员分享，可在线阅读，更多相关《运筹学资料4整数规划.ppt（74页珍藏版）》请在装配图网上搜索。

1、0-1规划的解法 0-1 规划在线性整数规划中具有重要地位。 定理：任何整数规划都可以化成0-1规划。 一般地说，可把整数x变成(k+1)个0-1变量公式为：x=y0+2y1+22y2+.2kyk 若x上界为U，则对0xU,要求k满足2k+1 U+1. 由于这个原因，数学界曾纷纷寻找“背包问题”解的方法，但进展缓慢。,隐枚举法(Implicit Enumeration) 基本上此法可以从所有变量等于零出发（初始点），然后依次指定一些变量取值为1，直到获得一个可行解，于是把第一个可行解记作迄今为止最好的可行解，再重复，依次检查变量为0，1的各种组合，对迄今为止最好的可行解加以改进，直到获得最优解

2、。,例5-9 求下列问题： Max Z=3x1- 2x2 + 5x3 s.t. x1+2x2 - x3 2 (1) x1+4x2 + x3 4 (2) x1 + x2 3 (3) 4x2 + x3 6 (4) xj 0或1 (5),解： 容易看出(1,0,0)满足约束条件，对应Z=3，对Max Z来说，希望Z 3,所以增加约束条件： Z=3x1- 2x2 + 5x3 3 (0) 称为过滤性条件。初看起来，增加约束条件需增加计算量，实际减少了计算量。,最优解（1，0，1） Z=8,增加约束条件（0）（Z 3)后实际做了24次运算，而原问题需要计算23*4=32次运算（3个变量，4个约束条件）。,

3、注意： 改进过滤性条件，在计算过程中随时调整右边常数。 价值系数按递增排列。 以上两种方法可减少计算量。,改进过滤性条件Z 5 (0),改进过滤性条件Z 8 (0),最优解(X2,X1,X3) =（0，1，1） Z=8 实际只计算了16次,例5-10 求下列问题： Max Z=3x1+ 4x2 + 5x3 + 6x4 s.t. 2x1+ 3x2 + 4x3 + 5x4 15 xj 0且为整数 解：先变换xj为0-1变量 x=y0+2y1+22y2+.2kyk,解：先变换xj为0-1变量 x=y0+2y1+22y2+.2kyk x1 7 x1=y01+2y11+22y21 x2 5 x2=y02

4、+2y12+22y22 x3 3 x3=y03+2y13 x4 3 x4=y04+2y14 代入原问题，得到：,Max Z= 3 y01+6y11+12y21 + 4y02+8y12+16y22 + 5 y03+10y13 + 6 y04+12y14 s.t. 2y01+4y11+8y21 +3y02+6y12 +12y22 + 4 y03+8y13 + 5 y04 +10y14 15 yij=0或=1,用隐枚举法可得到： y11=y21 =y02 =1 其他全为零 最优解（6，1，0，0） Z=22,0-1规划应用 华美公司有5个项目被列入投资计划，各项目的投资额和期望的投资收益见下表：,该

5、公司只有600万元资金可用于投资，由于技术原因，投资受到以下约束： 在项目1、2和3中必须有一项被选中； 项目3和4只能选中一项； 项目5被选中的前提是项目1必须被选中。 如何在上述条件下，选择一个最好的投资方案，使收益最大。,解：令 1 选中该项目 0 未选中该项目,xi=,Max Z=150 x1 + 210 x2 + 60 x3 +80 x4 + 180 x5 s.t. 210 x1 + 300 x2 +100 x3 +130 x4 + 260 x5 600 x1 + x2 + x3 =1 x3 + x4 1 x5 x1 xi=1或0,5 指派问题（分配问题）(Assignment Pr

6、oblem) 例5-11 有一份中文说明书，需翻译成英、日、德、俄四种文字，分别记作E、J、G、R，现有甲、乙、丙、丁四人，他们将中文说明书翻译成英、日、德、俄四种文字所需时间如下，问应该如何分配工作，使所需总时间最少？,类似有：有n项加工任务，怎样分配到n台机床上分别完成；有n条航线，怎样指定n艘船分别去航行. 等。 表中数据称为效率矩阵或系数矩阵，其元素大于零，表示分配第i人去完成第j 项任务时的效率（或时间、成本等）。,引入0-1变量xij=1分配第i人去完成第j 项任务，xij=0不分配第i人去完成第j 项任务。 分配问题的数学模型： Min Z= cijxij xij =1 (j=1

7、,2n) xij =1 (i=1,2n) xij 0或1 (i=1,2.m; j=1,2n), xij =1 (j=1,2n)表示 第j 项任务只能由一人去完成。 xij =1 (i=1,2n) 第i人只能完成一项任务。 满足约束条件的解称为可行解可写成矩阵形式：,X=,0 1 0 0 0 0 1 0 0 0 0 0 0 0 1,称为解矩阵其各行各列元素之和为1。,匈牙利算法基本思想： 对同一工作i来说，所有机床的效率都提高或降低同一常数，不会影响最优分配；同样，对同一机床j来说,做所有工作的效率都提高或降低同一常数，也不会影响最优分配。,分配问题性质： 分配问题的最优解有这样的性质，若从系数

8、矩阵C的一行（列）各元素中分别减去该行（列）的最小元素得到的新矩阵B，那么B为系数矩阵求得的最优解和用原来的系数矩阵C求得的最优解相同。,匈牙利算法： 系数矩阵中独立0元素的最多个数等于能覆盖所有0元素的最少直线数。,例5-11 有一份中文说明书，需翻译成英、日、德、俄四种文字，分别记作E、J、G、R，现有甲、乙、丙、丁四人，他们将中文说明书翻译成英、日、德、俄四种文字所需时间如下，问应该如何分配工作，使所需总时间最少？,匈牙利算法的步骤： 第一步：使分配问题的系数矩阵经变换，在各行各列中都出现0元素： 从系数矩阵的每行元素减去该行的最小元素。 再从所得系数矩阵的每列元素减去该列的最小元素。

9、若某行已经有0元素，就不必再减了。,(cij)=,2 15 13 4 4 14 15 9 14 16 13 7 8 11 9,2 4 9 7,0 13 11 2 6 0 10 11 0 5 7 4 0 1 4 2,4 2,0 13 7 0 6 0 6 9 0 5 3 2 0 1 0 0,第二步：进行试分配，以寻找最优解。 从只有一个0元素的行（或列）开始，给这个0元素加圈，记，然后划去所在的列（或行）的其他0元素，记作。 给只有一个0元素的列（或行）的0元素加圈，记，然后划去所在的行（或列）的其他0元素，记作。 反复进行上述两步，直到所有的0元素都被圈出和划掉为止。,若还有没有划圈的0元素，且

10、同行（或列）的0元素至少有二个，从剩有0元素最少的行（或列）开始，比较这行各0元素所在列中0元素的数目，选择0元素少的那列的0元素加圈，然后划掉同行同列的其他0元素，可反复进行，直到所有的0元素都被圈出和划掉为止。 若元素的数目m等于矩阵阶数n，那么这分配问题的最优解已得到。若mn，则转下一步。,0 13 7 0 6 6 9 0 5 3 2 0 1 0 0,从只有一个0元素的行（或列）开始，给这个0元素加圈，记。,0 13 7 0 6 6 9 5 3 2 0 1 0 0,从只有一个0元素的行（或列）开始，给这个0元素加圈，记，, 13 7 0 6 6 9 5 3 2 1 0 0,然后划去所在的

11、列的其他0元素，记作。, 13 7 0 6 6 9 5 3 2 1 0,给只有一个0元素的列的0元素加圈，记。, 13 7 0 6 6 9 5 3 2 1 ,然后划去所在的行的其他0元素，记作, 13 7 6 6 9 5 3 2 1 ,给最后一个0元素加圈，记。,0 0 0 1 0 1 0 0 1 0 0 0 0 0 1 0,可见m=n=4,得到最优解。,即甲译俄文、乙译日文、丙译英文、丁译德文所需时间最少。Z=28小时,例5-12 分配问题效率矩阵,7 6 7 6 4,从只有一个0元素的行开始，给这个0元素加圈，记,然后划去所在的列的其他0元素，记作。,从只有一个0元素的列开始，给这个0元素

12、加圈，记,然后划去所在的行的其他0元素，记作。,从只有一个0元素的列开始，给这个0元素加圈，记,然后划去所在的行的其他0元素，记作。,从只有一个0元素的列开始，给这个0元素加圈，记,然后划去所在的行的其他0元素，记作。,的个数m=4,而n=5, mn，转下一步。,第三步：作最少的直线覆盖所有的0元素，以确定该系数矩阵中能找到最多的独立元素数。 对没有的行，打； 对已打行中所有含0元素的列打； 再对打列中含0元素的行打； 重复上述两步，直到得不出新的打行列为止。 对没有打行画横线，有打列画纵线，就得到覆盖所有0元素的最少直线数。,对没有的行，打,对已打行中所有含0元素的列打,再对打列中含0元素的

13、行打,对没有打行画横线,有打列画纵线,第四步：在没有被直线覆盖的部分中找出最小元素，然后在打行各元素都减去这最小元素，而在打列中各元素都加上这最小元素，以保证原来0元素不变，这样得到新的系数矩阵（它的最优解和原问题相同）。若得到n个独立的0元素，则已经得到最优解。否则回到第三步重复进行。,没有被直线覆盖的最小元素为2,在打行各元素都减去这最小元素2。,在打列中各元素都加上这最小元素2。,重复第二步，寻找独立0元素。,从只有一个0元素的行开始，给这个0元素加圈，记,然后划去所在的列的其他0元素，记作。,从只有一个0元素的行开始，给这个0元素加圈，记,然后划去所在的列的其他0元素，记作。,从只有一个0元素的列开始，给这个0元素加圈，记,然后划去所在的行的其他0元素，记作。,下面有二种分配方案：,下面有二种分配方案：第一种,最优解如下：Z=32,分配问题结果如下：Z=32,下面有二种分配方案：第二种,最优解如下：Z=32,分配问题结果如下：Z=32,