《例1 背包问题 有n件物品，编号为 1，2，…，n。第 件重为 kg，价值为 元。今一装包者欲将这些物品装入一包，其质量不能超过 kg，问应装入哪几件价值最大？.ppt》由会员分享，可在线阅读，更多相关《例1 背包问题 有n件物品，编号为 1，2，…，n。第 件重为 kg，价值为 元。今一装包者欲将这些物品装入一包，其质量不能超过 kg，问应装入哪几件价值最大？.ppt（78页珍藏版）》请在三一文库上搜索。
1、例1 背包问题 有n件物品，编号为 1，2，n。第 件重为 kg，价值为 元。今一装包者欲将这些物品装入一包，其质量不能超过 kg，问应装入哪几件价值最大？,0-1规划应用背景,解 引入变量 将 物品装包 不将 物品装包 于是得问题的模型为 取0或1，i=1，2，n 背包问题看似简单，但应用很广，例如某些投资问题即可归入背包问题模型。此类问题可以,描述为：设有总额为 元的资金，投资几项事业，第 项副业需投资 元，利润为 元,问应选择哪些项总利润为最大？ 例2 某钻井队要从以下10个可供选择的井位中确定5个钻井探油，使总的钻探费用为最小。若10个井位的代号为 ，相应的钻探费用为 ，并且井位选择要
2、满足下列限制条件： （1）或选 和 ，或选 ； （2）选择了 或 就不能选 ，反之亦然； （3）在 中最多只能选两个。 试建立其数学模型：,解 引入变量 选择 不选择 于是以上问题的数学模型为：,例3 指派问题。有 项任务，由 个人来完成，每人只能干一件，第 个人完成第 项任务需要的时间为 小时，问怎样安排能使总用时最少？ 解 引入0-1型变量 人完成 任务 人不去完成 任务 于是该问题的数学模型为,S.t.,0-1规划模型因其特殊性，不同于整数规划的解法。如一般0-1规划的隐枚举法，指派问题中的匈牙利法，背包问题则可以用动态规划的方法求解。,01规划解法,隐枚举法(Implicit Enum
3、eration) 基本上此法可以从所有变量等于零出发（初始点），然后依次指定一些变量取值为1，直到获得一个可行解，于是把第一个可行解记作迄今为止最好的可行解，再重复，依次检查变量为0，1的各种组合，对迄今为止最好的可行解加以改进，直到获得最优解。,例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- 2x
4、2 + 5x3 3 (0) 称为过滤性条件。初看起来，增加约束条件需增加计算量，实际减少了计算量。,最优解（1，0，1） Z=8,增加约束条件（0）（Z 3)后实际做了24次运算，而原问题需要计算23*4=32次运算（3个变量，4个约束条件）。,注意： 改进过滤性条件，在计算过程中随时调整右边常数。 价值系数按递增排列。 以上两种方法可减少计算量。,改进过滤性条件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 + 4
5、x3 + 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+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
6、+ 5 y04 +10y14 15 yij=0或=1,用隐枚举法可得到： y11=y21 =y02 =1 其他全为零 最优解（6，1，0，0） Z=22,指派问题（分配问题）(Assignment Problem) 例 有一份中文说明书，需翻译成英、日、德、俄四种文字，分别记作E、J、G、R，现有甲、乙、丙、丁四人，他们将中文说明书翻译成英、日、德、俄四种文字所需时间如下，问应该如何分配工作，使所需总时间最少？,类似有：有n项加工任务，怎样分配到n台机床上分别完成；有n条航线，怎样指定n艘船分别去航行 等。 表中数据称为效率矩阵或系数矩阵，其元素大于零，表示分配第i人去完成第j 项任务时的效率
7、（或时间、成本等）。,引入0-1变量xij=1分配第i人去完成第j 项任务，xij=0不分配第i人去完成第j 项任务。 分配问题的数学模型： Min Z= cijxij xij =1 (j=1,2n) xij =1 (i=1,2n) xij 0或1 (i=1,2m; 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来说，所
8、有机床的效率都提高或降低同一常数，不会影响最优分配；同样，对同一机床j来说,做所有工作的效率都提高或降低同一常数，也不会影响最优分配。,分配问题性质： 分配问题的最优解有这样的性质，若从系数矩阵C的一行（列）各元素中分别减去该行（列）的最小元素得到的新矩阵B，那么B为系数矩阵求得的最优解和用原来的系数矩阵C求得的最优解相同。,匈牙利算法： 系数矩阵中独立0元素的最多个数等于能覆盖所有0元素的最少直线数。,例 有一份中文说明书，需翻译成英、日、德、俄四种文字，分别记作E、J、G、R，现有甲、乙、丙、丁四人，他们将中文说明书翻译成英、日、德、俄四种文字所需时间如下，问应该如何分配工作，使所需总时间
9、最少？,匈牙利算法的步骤： 第一步：使分配问题的系数矩阵经变换，在各行各列中都出现0元素： 从系数矩阵的每行元素减去该行的最小元素。 再从所得系数矩阵的每列元素减去该列的最小元素。 若某行已经有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元素，
10、记作。 给只有一个0元素的列（或行）的0元素加圈，记，然后划去所在的行（或列）的其他0元素，记作。 反复进行上述两步，直到所有的0元素都被圈出和划掉为止。,若还有没有划圈的0元素，且同行（或列）的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元素加圈，记。,
11、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,然后划去所在的列的其他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=2
12、8小时,分配问题效率矩阵,7 6 7 6 4,从只有一个0元素的行开始，给这个0元素加圈，记,然后划去所在的列的其他0元素，记作。,从只有一个0元素的列开始，给这个0元素加圈，记,然后划去所在的行的其他0元素，记作。,从只有一个0元素的列开始，给这个0元素加圈，记,然后划去所在的行的其他0元素，记作。,从只有一个0元素的列开始，给这个0元素加圈，记,然后划去所在的行的其他0元素，记作。,的个数m=4,而n=5, mn，转下一步。,第三步：作最少的直线覆盖所有的0元素，以确定该系数矩阵中能找到最多的独立元素数。 对没有的行，打； 对已打行中所有含0元素的列打； 再对打列中含0元素的行打； 重复上
13、述两步，直到得不出新的打行列为止。 对没有打行画横线，有打列画纵线，就得到覆盖所有0元素的最少直线数。,对没有的行，打,对已打行中所有含0元素的列打,再对打列中含0元素的行打,对没有打行画横线,有打列画纵线,第四步：在没有被直线覆盖的部分中找出最小元素，然后在打行各元素都减去这最小元素，而在打列中各元素都加上这最小元素，以保证原来0元素不变，这样得到新的系数矩阵（它的最优解和原问题相同）。若得到n个独立的0元素，则已经得到最优解。否则回到第三步重复进行。,没有被直线覆盖的最小元素为2,在打行各元素都减去这最小元素2。,在打列中各元素都加上这最小元素2。,重复第二步，寻找独立0元素。,从只有一个0元素的行开始，给这个0元素加圈，记,然后划去所在的列的其他0元素，记作。,从只有一个0元素的行开始，给这个0元素加圈，记,然后划去所在的列的其他0元素，记作。,从只有一个0元素的列开始，给这个0元素加圈，记,然后划去所在的行的其他0元素，记作。,下面有二种分配方案：,下面有二种分配方案：第一种,最优解如下：Z=32,分配问题结果如下：Z=32,下面有二种分配方案：第二种,最优解如下：Z=32,分配问题结果如下：Z=32,