运筹学资料4整数规划

《运筹学资料4整数规划》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、0-1规划的解法0-1规划在线性整数规划中具有重要地位。定理：任何整数规划都可以化成0-1规划。一般地说，可把整数x变成(k+1)个0-1变量公式为：x=y0+2y1+22y2+….2kyk若x上界为U，则对0

2、解。例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，对MaxZ来说，希望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,

3、0)31110yes36(1,0,1)80211yes87(1,1,0)1no8(1,1,1)626no最优解（1，0，1）Z=8增加约束条件（0）（Z3)后实际做了24次运算，而原问题需要计算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

4、满足Z值3(0,1,0)3no4(0,1,1)80211yes8改进过滤性条件Z8(0’’)循环(X2,X1,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+….2k

5、ykx17x1=y01+2y11+22y21x2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=220-1规划应用华美公司有5个项目被列入投资计划，各项目的投资额和期望的投资收益见下表：

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

7、nmentProblem)例5-11有一份中文说明书，需翻译成英、日、德、俄四种文字，分别记作E、J、G、R，现有甲、乙、丙、丁四人，他们将中文说明书翻译成英、日、德、俄四种文字所需时间如下，问应该如何分配工作，使所需总时间最少？任务人员EJGR甲215134乙1041415丙9141613丁78119类似有：有n项加工任务，怎样分配到n台机床上分别完成；有n条航线，怎样指定n艘船分别去航行…..等。表中数据称为效率矩阵或系数矩阵，其元素大于零，表示分配第i人去完成第j项任务时的