例1 背包问题 有n件物品,编号为 1,2,…,n。第 件重为 kg,价值为 元。今一装包者欲将这些物品装入一包,其质量不能超过 kg,问应装入哪几件价值最大?.ppt
《例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 项任务时的效率
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 例1 背包问题 有n件物品,编号为 1,2,n。第 件重为 kg,价值为 元。今一装包者欲将这些物品装入一包,其质量不能超过 kg,问应装入哪几件价值最大? 背包 问题 物品 编号 kg 价值 今一装包者欲将
链接地址:https://www.31doc.com/p-3107463.html