5 整数规划模型

第5章整数规划（ILP、IP）模型5.1投资决策问题5.2背包问题5.3合理下料问题5.4生产组织与计划问题5.5工厂选址问题5.6设备购置和安装问题5.1投资决策问题问题某市在“十五”期间有b亿元资金可用于n个项目的投资。若对第i个项目投资，需资金bi亿元，可获利ci亿元，试确定一个投资方案，使该市利税收入最多。建数学模型,max1iniixcz建模令若对第i个项目投资，否则，,0,1ixni,,2,1nixi,,2,1,1或0,..1bxbtsinii对第i个项目投资,可获利ci亿元，利税达最大对第i个项目投资,需资金bi亿元，共有b亿元资金ILP0-1规划5.2背包问题问题设有一个容积为b的背包，有n个体积分别为bi，价值分别为ci的物品可以装入背包，问应选择哪几件物品装入背包，才能得到最大的使用价值。建数学模型,max1iniixcz建模令若装第i件物品，否则，,0,1ixni,,2,1nixi,,2,1,1或0,..1bxbtsinii装第i件物品，价值ci使价值达最大装第i件物品，体积为bi共有容积为bILP与投资决策问题模型相同0-1规划5.3合理下料问题问题设要利用某类钢板下m种零件的毛料。已知在一块钢板上，已设计出n种不同的下料方案，设在第j种下料方案中，可下得第i种零件的个数为aij，第i种零件的需要量为bi。问应如何下料，才能既满足需要，又使所用钢板总数最少。,min1njjxz建模njIxxjj,,2,1,,0mibxatsijnjij,,2,1,..1钢板总数达最小第i种零件总数不少于bi纯整数规划},2,1,0{I设采用第j种方案下料的钢板数为xj5.4生产组织与计划问题问题某工厂用m台机床：A1,A2,…,Am，加工n种零件：B1,B2,…,Bn。在一个生产周期内，已知第i台机床Ai只能工作ai个机时。工厂必须完成加工零件Bj的数量为bj个。机床Ai加工一个零件Bj所需的机时和成本分别为tij（机时/个）和cij（元/个）。问在这个生产周期，应如何安排机床的生产任务，才能既完成加工任务，又使总的加工成本最小。,min11minjijijxcz建模njmiIxxijij,,2,1,,,2,1,,0miaxttsiijnjij,,2,1,..1机床Ai加工各零件的机时不超过Ai能工作的机时各机床加工零件Bj的数目不少于Bj的需要数量纯整数规划},2,1,0{I设机床Ai在一生产周期内加工零件Bj的个数为xijnjbxjmiij,,2,1,15.5工厂选址问题问题设有n个需求点，有m个可供选择的建厂地址。每个地址至多可建一个工厂。在i地址建立工厂的生产能力为Di,在i地址经营工厂，单位时间的固定成本为ai（元）,需求点j的需求量为bj，从厂址i到需求点j的单位运费为cij（元/t）。问应如何选择厂址和安排运输计划，才能得到经济上花费最少的方案。若不在i地址建厂若在i地址建厂,,10iy建模njmiyxiij,,2,1,,,2,1,1或0,0miyDxtsiinjij,,2,1,..1i地址建工厂的生产能力Di需求点j的需求量为bj混合型整数规划设单位时间内，从厂址i运往需求点j物资数量为xij吨njbxjmiij,,2,1,1,min111miiiminjijijyaxcz5.6设备购置和安装问题问题某工厂需要m种设备：A1,A2,…,Am，设Ai的单价为pi元，该厂已有第i种设备ai台。今有资金M元，可用于购置这些设备。该厂有n处可安装这些设备，Bj处最多能安装bj台，将一台设备Ai安装在Bj处，经济效益为cij元，问应如何购置和安装这些设备，才能使总的经济效益最高。,max11minjijijxcz建模njmiIyxyxiijiij,,2,1,,,2,1,,,0,miayxtsiinjij,,2,1,..1安装的设备Ai数不超过已有的和购置的台数和Bj处最多能安装bj台纯整数规划},2,1,0{I设备Ai安装在Bj处的台数为xij，yi表示购置Ai的台数njbxjmiij,,2,1,1Mypmiii1有资金M元整数规划模型例题例1汽车厂生产计划例2混合泳接力队的选拔例3选课策略•如果生产某一类型汽车，则至少要生产80辆，那么最优的生产计划应作何改变？例1汽车厂生产计划汽车厂生产三种类型的汽车，已知各类型每辆车对钢材、劳动时间的需求，利润及工厂每月的现有量。小型中型大型现有量钢材（吨）1.535600劳动时间（小时）28025040060000利润（万元）234•制订月生产计划，使工厂的利润最大。设每月生产小、中、大型汽车的数量分别为x1,x2,x3321432xxxzMax600535.1..321xxxts60000400250280321xxx0,,321xxx汽车厂生产计划模型建立小型中型大型现有量钢材1.535600时间28025040060000利润234线性规划模型(LP)模型求解3）模型中增加条件：x1,x2,x3均为整数，重新求解。OBJECTIVEFUNCTIONVALUE1)632.2581VARIABLEVALUEREDUCEDCOSTX164.5161290.000000X2167.7419280.000000X30.0000000.946237ROWSLACKORSURPLUSDUALPRICES2)0.0000000.7311833)0.0000000.003226结果为小数，怎么办？1）舍去小数：取x1=64，x2=167，算出目标函数值z=629，与LP最优值632.2581相差不大。2）试探：如取x1=65，x2=167；x1=64，x2=168等，计算函数值z，通过比较可能得到更优的解。•但必须检验它们是否满足约束条件。为什么？IP可用LINDO直接求解整数规划(IntegerProgramming,简记IP)“gin3”表示“前3个变量为整数”，等价于：ginx1ginx2ginx3IP的最优解x1=64，x2=168，x3=0，最优值z=632max2x1+3x2+4x3st1.5x1+3x2+5x3600280x1+250x2+400x360000endgin3OBJECTIVEFUNCTIONVALUE1)632.0000VARIABLEVALUEREDUCEDCOSTX164.000000-2.000000X2168.000000-3.000000X30.000000-4.000000321432xxxzMax600535.1..321xxxts60000400250280321xxx为非负整数321,,xxx模型求解IP结果输出其中3个子模型应去掉，然后逐一求解，比较目标函数值，再加上整数约束，得最优解：80,0,0321xxx0,80,0321xxx80,80,0321xxx0,0,80321xxx0,80,80321xxx80,0,80321xxx80,80,80321xxx0,,321xxx方法1：分解为8个LP子模型汽车厂生产计划•若生产某类汽车，则至少生产80辆，求生产计划。321432xxxzMax600535.1..321xxxts60000400250280321xxxx1,x2,,x3=0或80x1=80，x2=150，x3=0，最优值z=610LINDO中对0-1变量的限定：inty1inty2inty3方法2：引入0-1变量，化为整数规划M为大的正数，可取1000OBJECTIVEFUNCTIONVALUE1)610.0000VARIABLEVALUEREDUCEDCOSTX180.000000-2.000000X2150.000000-3.000000X30.000000-4.000000Y11.0000000.000000Y21.0000000.000000Y30.0000000.000000•若生产某类汽车，则至少生产80辆，求生产计划。x1=0或80x2=0或80x3=0或80}1,0{,80,11111yyxMyx}1,0{,80,22222yyxMyx}1,0{,80,33333yyxMyx最优解同前NLP虽然可用现成的数学软件求解(如LINGO,MATLAB)，但是其结果常依赖于初值的选择。方法3：化为非线性规划非线性规划（Non-LinearProgramming，简记NLP）实践表明，本例仅当初值非常接近上面方法算出的最优解时，才能得到正确的结果。•若生产某类汽车，则至少生产80辆，求生产计划。x1=0或80x2=0或80x3=0或800)80(11xx0)80(22xx0)80(33xx丁的蛙泳成绩退步到1’15”2；戊的自由泳成绩进步到57”5,组成接力队的方案是否应该调整？如何选拔队员组成4100米混合泳接力队?例2混合泳接力队的选拔甲乙丙丁戊蝶泳1’06”857”21’18”1’10”1’07”4仰泳1’15”61’06”1’07”81’14”21’11”蛙泳1’27”1’06”41’24”61’09”61’23”8自由泳58”653”59”457”21’02”45名候选人的百米成绩穷举法：组成接力队的方案共有5!=120种。目标函数若选择队员i参加泳姿j的比赛，记xij=1,否则记xij=00-1规划模型cij(秒)~队员i第j种泳姿的百米成绩约束条件每人最多入选泳姿之一ciji=1i=2i=3i=4i=5j=166.857.2787067.4j=275.66667.874.271j=38766.484.669.683.8j=458.65359.457.262.44151jiijijxcZMin每种泳姿有且只有1人5,1,141ixjij4,1,151jxiij模型求解最优解：x14=x21=x32=x43=1,其它变量为0;成绩为253.2(秒)=4’13”2MIN66.8x11+75.6x12+87x13+58.6x14+……+67.4x51+71x52+83.8x53+62.4x54SUBJECTTOx11+x12+x13+x14=1……x41+x42+x43+x44=1x11+x21+x31+x41+x51=1……x14+x24+x34+x44+x54=1ENDINT20输入LINDO求解甲乙丙丁戊蝶泳1’06”857”21’18”1’10”1’07”4仰泳1’15”61’06”1’07”81’14”21’11”蛙泳1’27”1’06”41’24”61’09”61’23”8自由泳58”653”59”457”21’02”4甲~自由泳、乙~蝶泳、丙~仰泳、丁~蛙泳.丁蛙泳c43=69.675.2，戊自由泳c54=62.457.5,方案是否调整？敏感性分析？乙~蝶泳、丙~仰泳、丁~蛙泳、戊~自由泳IP规划一般没有与LP规划相类似的理论，LINDO输出的敏感性分析结果通常是没有意义的。最优解：x21=x32=x43=x51=1,成绩为4’17”7c43,c54的新数据重新输入模型，用LINDO求解指派(Assignment)问题：每项任务有且只有一人承担，每人只能承担一项，效益不同，怎样分派使总效益最大.讨论甲~自由泳、乙~蝶泳、丙~仰泳、丁~蛙泳.原方案为了选修课程门数最少，应学习哪些课程？例3选课策略要求至少选两门数学课、三门运筹学课和两门计算机课课号课名学分所属类别先修课要求1微积分5数学2线性代数4数学3最优化方法4数学；运筹学微积分；线性代数4数据结构3数学；计算机计算机编程5应用统计4数学；运筹学微积分；线性代数6计算机模拟3计算机；运筹学计算