规划应用背景.ppt

《规划应用背景.ppt》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

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规划的隐枚举法，指派问题中的匈牙利法，背包问题则可以用动态规划的方法求解。0－

3、1规划解法隐枚举法(ImplicitEnumeration)基本上此法可以从所有变量等于零出发（初始点），然后依次指定一些变量取值为1，直到获得一个可行解，于是把第一个可行解记作迄今为止最好的可行解，再重复，依次检查变量为0，1的各种组合，对迄今为止最好的可行解加以改进，直到获得最优解。例5-9求下列问题：MaxZ=3x1-2x2+5x3s.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，对Ma

4、xZ来说，希望Z3,所以增加约束条件：Z=3x1-2x2+5x33(0)称为过滤性条件。初看起来，增加约束条件需增加计算量，实际减少了计算量。循环(X1,X2,X3)s.t.0s.t.1s.t.2s.t.3s.t.4满足Z值1(0,0,0)0no2(0,0,1)5-1101yes53(0,1,0)-2no4(0,1,1)315no5(1,0,0)31110yes36(1,0,1)80211yes87(1,1,0)1no8(1,1,1)626no最优解（1，0，1）Z=8增加约束条件（0）（Z3)后实际做了24次

5、运算，而原问题需要计算23*4=32次运算（3个变量，4个约束条件）。注意：改进过滤性条件，在计算过程中随时调整右边常数。价值系数按递增排列。以上两种方法可减少计算量。循环(X2,X1,X3)s.t.0s.t.1s.t.2s.t.3s.t.4满足Z值1(0,0,0)0no2(0,0,1)5-1101yes5改进过滤性条件Z5(0’)循环(X2,X1,X3)s.t.0’s.t.1s.t.2s.t.3s.t.4满足Z值3(0,1,0)3no4(0,1,1)80211yes8改进过滤性条件Z8(0’’)循环(X2,X1

6、,X3)s.t.0’’s.t.1s.t.2s.t.3s.t.4满足Z值5(1,0,0)-2no6(1,0,1)3no7(1,1,0)1no8(1,1,1)6no最优解(X2,X1,X3)=（0，1，1）Z=8实际只计算了16次例5-10求下列问题：MaxZ=3x1+4x2+5x3+6x4s.t.2x1+3x2+4x3+5x415xj0且为整数解：先变换xj为0-1变量x=y0+2y1+22y2+….2kyk解：先变换xj为0-1变量x=y0+2y1+22y2+….2kykx17x1=y01+2y11+22y21

7、x25x2=y02+2y12+22y22x33x3=y03+2y13x43x4=y04+2y14代入原问题，得到：MaxZ=3y01+6y11+12y21+4y02+8y12+16y22+5y03+10y13+6y04+12y14s.t.2y01+4y11+8y21+3y02+6y12+12y22+4y03+8y13+5y04+10y1415yij=0或=1用隐枚举法可得到：y11=y21=y02=1其他全为零最优解（6，1，0，0）Z=22指派问题（分配问题）(AssignmentProblem)例有一份中

8、文说明书，需翻译成英、日、德、俄四种文字，分别记作E、J、G、R，现有甲、乙、丙、丁四人，他们将中文说明书翻译成英、日、德、俄四种文字所需时间如下，问应该如何分配工作，使所需总时间最少？任务人员EJGR甲215134乙1041415丙9141613丁78119类似有：有n项加工任务，怎样分配到n台机床上分别完成；有n条航线，怎样指定n艘船分别去