整数规划模型

1、第5章 整数规划（ILP、IP）模型,5.1 投资决策问题 5.2 背包问题 5.3 合理下料问题 5.4 生产组织与计划问题 5.5 工厂选址问题 5.6 设备购置和安装问题,5.1 投资决策问题,问题,某市在“十五” 期间有 b 亿元资金可用于 n 个项目的投资。若对第 i 个项目投资，需资金 bi 亿元，可获利 ci 亿元，试确定一个投资方案，使该市利税收入最多。建数学模型,建模,令 若对第 i 个项目投资， 否则，,对第 i 个项目投资, 可获利 ci 亿元， 利税达最大,对第 i 个项目投资, 需资金 bi 亿元， 共有b 亿元资金,ILP,0-1规划,5.2 背包问题,问题,设有一

2、个容积为 b 的背包，有 n 个体积分别为 bi ，价值分别为 ci 的物品可以装入背包，问应选择哪几件物品装入背包，才能得到最大的使用价值。建数学模型,建模,令 若装第 i 件物品， 否则，,装第 i 件物品，价值ci 使价值达最大,装第 i 件物品，体积为 bi 共有容积为 b,ILP,与投资决策问题模型相同,0-1规划,5.3 合理下料问题,问题,设要利用某类钢板下m 种零件的毛料。已知在一块钢板上，已设计出 n 种不同的下料方案，设在第 j 种下料方案中，可下得第 i 种零件的个数为 aij ，第 i 种零件的需要量为 bi 。问应如何下料，才能既满足需要，又使所用钢板总数最少。,建模

3、,钢板总数达最小,第 i 种零件总数不少于bi,纯整数规划,设采用第 j 种方案下料的钢板数为xj,5.4 生产组织与计划问题,问题,某工厂用 m 台机床：A1,A2,Am，加工 n 种零件：B1,B2,Bn 。在一个生产周期内，已知第 i 台机床Ai 只能工作ai 个机时。工厂必须完成加工零件Bj 的数量为bj 个。机床Ai 加工一个零件Bj 所需的机时和成本分别为 tij（机时/个）和cij（元/个）。问在这个生产周期，应如何安排机床的生产任务，才能既完成加工任务，又使总的加工成本最小。,建模,机床Ai 加工各零件的机时 不超过Ai能工作的机时,各机床加工零件Bj 的数目 不少于Bj的需要

4、数量,纯整数规划,设机床Ai在一生产周期内加工零件Bj的个数为xij,5.5 工厂选址问题,问题,设有 n 个需求点，有 m 个可供选择的建厂地址。每个地址至多可建一个工厂。在 i 地址建立工厂的生产能力为Di,在 i 地址经营工厂，单位时间的固定成本为ai （元）,需求点 j 的需求量为bj，从厂址i 到需求点 j 的单位运费为cij（元/t）。问应如何选择厂址和安排运输计划，才能得到经济上花费最少的方案。,建模,i 地址建工厂的生产能力Di,需求点 j 的需求量为bj,混合型整数规划,设单位时间内， 从厂址i 运往需求点 j 物资数量为xij 吨,5.6 设备购置和安装问题,问题,某工厂需

5、要 m 种设备：A1,A2,Am，设Ai的单价为 pi元，该厂已有第 i 种设备ai台。今有资金M元，可用于购置这些设备。该厂有n 处可安装这些设备，Bj处最多能安装 bj台，将一台设备Ai安装在Bj处，经济效益为cij元，问应如何购置和安装这些设备，才能使总的经济效益最高。,建模,安装的设备Ai数不超过 已有的和购置的台数和,Bj处最多能安装 bj台,纯整数规划,设备Ai安装在Bj处的台数为xij ，yi 表示购置Ai的台数,有资金M元,整数规划模型例题,例1 汽车厂生产计划 例2 混合泳接力队的选拔 例3 选课策略,如果生产某一类型汽车，则至少要生产80辆， 那么最优的生产计划应作何改变？

6、,例1 汽车厂生产计划,汽车厂生产三种类型的汽车，已知各类型每辆车对钢材、劳动时间的需求，利润及工厂每月的现有量。,制订月生产计划，使工厂的利润最大。,设每月生产小、中、大型汽车的数量分别为x1, x2, x3,汽车厂生产计划,模型建立,线性规划模型(LP),模型求解,3） 模型中增加条件：x1, x2, x3 均为整数，重新求解。,OBJECTIVE FUNCTION VALUE 1) 632.2581 VARIABLE VALUE REDUCED COST X1 64.516129 0.000000 X2 167.741928 0.000000 X3 0.000000 0.946237 R

7、OW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 0.731183 3) 0.000000 0.003226,结果为小数，怎么办？,1）舍去小数：取x1=64，x2=167，算出目标函数值z=629，与LP最优值632.2581相差不大。,2）试探：如取x1=65，x2=167；x1=64，x2=168等，计算函数值z，通过比较可能得到更优的解。,但必须检验它们是否满足约束条件。为什么？,IP可用LINDO直接求解,整数规划(Integer Programming,简记IP),“gin 3”表示“前3个变量为整数”，等价于： gin x1 gin x2 g

8、in x3,IP 的最优解x1=64，x2=168，x3=0，最优值z=632,max 2x1+3x2+4x3 st 1.5x1+3x2+5x3600 280 x1+250 x2+400 x360000 end gin 3,OBJECTIVE FUNCTION VALUE 1) 632.0000 VARIABLE VALUE REDUCED COST X1 64.000000 -2.000000 X2 168.000000 -3.000000 X3 0.000000 -4.000000,模型求解,IP 结果输出,其中3个子模型应去掉，然后逐一求解，比较目标函数值，再加上整数约束，得最优解：,方

9、法1：分解为8个LP子模型,汽车厂生产计划,若生产某类汽车，则至少生产80辆，求生产计划。,x1,x2, x3=0 或 80,x1=80，x2= 150，x3=0，最优值z=610,LINDO中对0-1变量的限定： int y1 int y2 int y3,方法2：引入0-1变量，化为整数规划,M为大的正数，可取1000,OBJECTIVE FUNCTION VALUE 1) 610.0000 VARIABLE VALUE REDUCED COST X1 80.000000 -2.000000 X2 150.000000 -3.000000 X3 0.000000 -4.000000 Y1 1

10、.000000 0.000000 Y2 1.000000 0.000000 Y3 0.000000 0.000000,若生产某类汽车，则至少生产80辆，求生产计划。,x1=0 或 80,最优解同前,NLP虽然可用现成的数学软件求解(如LINGO, MATLAB)，但是其结果常依赖于初值的选择。,方法3：化为非线性规划,非线性规划（Non- Linear Programming，简记NLP）,实践表明，本例仅当初值非常接近上面方法算出的最优解时，才能得到正确的结果。,若生产某类汽车，则至少生产80辆，求生产计划。,x1=0 或 80,丁的蛙泳成绩退步到115”2；戊的自由泳成绩进步到57”5,

11、组成接力队的方案是否应该调整？,如何选拔队员组成4100米混合泳接力队?,例2 混合泳接力队的选拔,5名候选人的百米成绩,穷举法：组成接力队的方案共有5!=120种。,目标函数,若选择队员i参加泳姿j 的比赛，记xij=1, 否则记xij=0,0-1规划模型,cij(秒)队员i 第j 种泳姿的百米成绩,约束条件,每人最多入选泳姿之一,每种泳姿有且只有1人,模型求解,最优解：x14 = x21 = x32 = x43 = 1, 其它变量为0; 成绩为253.2(秒)=413”2,MIN 66.8x11+75.6x12+87x13+58.6x14 + +67.4x51+71 x52+83.8x53

12、+62.4x54 SUBJECT TO x11+x12+x13+x14 =1 x41+x42+x43+x44 =1 x11+x21+x31+x41+x51 =1 x14+x24+x34+x44+x54 =1 END INT 20,输入LINDO求解,甲 自由泳、乙 蝶泳、丙 仰泳、丁 蛙泳.,丁蛙泳c43 =69.675.2，戊自由泳c54=62.4 57.5, 方案是否调整？,敏感性分析？,乙 蝶泳、丙 仰泳、丁 蛙泳、戊 自由泳,IP规划一般没有与LP规划相类似的理论，LINDO输出的敏感性分析结果通常是没有意义的。,最优解：x21 = x32 = x43 = x51 = 1, 成绩为41

13、7”7,c43, c54 的新数据重新输入模型，用LINDO求解,指派(Assignment)问题：每项任务有且只有一人承担，每人只能承担一项，效益不同，怎样分派使总效益最大.,讨论,为了选修课程门数最少，应学习哪些课程 ？,例3 选课策略,要求至少选两门数学课、三门运筹学课和两门计算机课,选修课程最少，且学分尽量多，应学习哪些课程 ？,0-1规划模型,决策变量,目标函数,xi=1 选修课号i 的课程（xi=0 不选）,选修课程总数最少,约束条件,最少2门数学课，3门运筹学课， 2门计算机课。,先修课程要求,最优解： x1 = x2 = x3 = x6 = x7 = x9 =1, 其它为0；6门课程，总学分21,0-1规划模型,约束条件,x3=1必有x1 = x2 =1,模型求解（LINDO）,学分最多,多目标优化的处理方法：化成单目标优化。,两目标(多目标)规划,讨论：选修课程最少，学分尽量多，应学习哪些课程？,课程最少,以学分最多为目标，不管课程多少。,以课程最少为目标，不管学分多少。,多目标规划,在课程最少的前提下以学分最多为目标。,最优解： x1 = x2 = x3 = x5 = x7