运筹学第10讲：整数规划(一).ppt

《运筹学第10讲：整数规划(一).ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。

1、第10讲整数规划(一)浙江工业大学经贸管理学院曹柬一、整数规划的概念及其应用整数规划(IntegerProgram)：决策变量取整数的LP问题，简称IP问题纯整数规划(PureIP)：全部整数取整0-1规划(Zero-OneIP)：变量只能取0或1混合整数规划(MixedIP)：部分整数取整运筹学第10讲：整数规划(一)篮球队需要选择5名队员组成出场阵容参加比赛。8名队员的身高以及擅长的位置如下表所示。队员12345678身高(m)1.921.901.881.861.851.831.801.78位置中

2、锋中锋前锋前锋前锋后卫后卫后卫出场阵容应满足以下条件：只能有一名中锋上场；至少有一名后卫；如1号和4号均上场，则6号不出场；2号和8号至少有一个不在场。问应选择哪5名队员上场，使队员身高最高。例10-1规划问题解：设0-1变量xi表示第i个队员是否上场，当xi＝0时表示该队员不上场；当xi=1时表示该队员上场，建立如下的线性规划模型：目标函数：min∑cixi(ci为第i位队员的身高)约束条件：s.t.x1+x2＝1x6+x7+x8≥1x1+x4+x6≤2x2+x8≤1∑xi=5xi=0或1,i=1,

3、2,…,8最优值:9.32最优解：x2=x3=x4=x5=x6=1其余xi=0.例2工厂A1和A2生产某种物资。由于该物资供不应求，故需再建一家工厂。相应的建厂方案有A3和A4两个。这种物资的需求地有B1,B2,B3和B4四个。各厂年生产能力、各地年需求量、各厂到各需求地的单位物资运费如下表所示。BjB1B2B3B4生产能力(kt/年)AiA12934400A28357600A37612200A44525200需求量(kt/年)350400300150运费工厂A3或A4开工后，每年的生产费用估计分别为

4、1200万元或1500万元。现要决定应该建设工厂A3还是A4，才能使今后每年的总费用（即全部物资运费和新工厂生产费用之和）最少。混合整数规划问题二、Ip问题的求解松弛问题(slackproblem)：去掉整数性约束的LP问题，或称原问题的LP问题例：maxz=6x1+5x2(1)—目标函数s.t.2x1+x2≤9(2)5x1+7x2≤35(3)x1,x2≥0(4)—非负条件x1,x2为整数(5)—整数性约束LP约束运筹学第10讲：整数规划(一)上述IP问题的LP问题的解为：，当松弛问题的所有非整变量值

5、都较大时，例如xj≥100，圆整LP问题的方法是有效的运筹学第10讲：整数规划(一)maxz=6x1+5x2s.t.2x1+x2≤9，5x1+7x2≤35x1,x2≥0，x1,x2为整数图解法5x1+7x2=352x1+x2=9ABA为该问题的松弛问题的最优解B为该问题的最优解，x1*=4,x2*=1,z*=29x1x2993366z=6x1+5x2三、0-1规划问题的求解将各变量按系数绝对值由大到小的顺序进行排列，并令系数为负的变量xj＝1－xj’；在max型中，从变量最大值开始求算；在min型中，

6、从变量最小值开始求算，并验证约束条件是否成立maxZ=4x1－3x2+6x3s.t.x1+2x2－x3≤2x1+4x2+x3≤4x1+x2≤34x2+x3≤62x1+2x2+x3≤5x1,x2,x3=0或1例4minZ=3x1+7x2－x3+x4s.t.例5注意可行域是否存在！运筹学第10讲：整数规划(一)案例5：华南公司投资方案华南投资公司在实施“九五”后三年以及“十五”初期发展规划时，决定投资兴办产业，以增强发展后劲，投资总额为800万元，其中第一年350万元，第二年300万元，第三年150万元。

7、投资方案有：A1：建立彩色印刷厂。第一、二年年初分别投入220万元和220万元，第二年年底可获利120万元，第三年起每年获利140万元。A2：投资离子镀膜基地。第一年投资70万元，第二年起每年获利28万元。A3：投资参股F企业，第二年投入180万元设备，第三年起每年可获利65万元。A4：投资D企业，每年年底可获投资额的25％利润，但第一年最高投资额为80万元，以后每年递增不超过15万元。A5：建立超细骨粉生产线。第三年投入320万元，第四年起每年可获利180万元。A6：投资所属中北机电设备公司。年底回

8、收本利120％。但每年投资额不低于60万元。A7：投资所属澳得技术公司，年底回收本利115％。投资期为5年，需从上述7个方案中选择最优投资组合，使得5年末时资金总额为最大。综上所述，该问题的数学模型为：＝0或1，＝0或1，，，，L为足够小的正数，，，，M为足够大的正数max140y1+28y2+65y3+0.25x54+180y5+1.2x56+1.15x57st220y1+70y2+x14+x16+x17=350220y1+180y3+x24+x26+