第3章整数规划模型.ppt
第3章 整数规划模型,§3.1 投资决策问题,问题分析,目标：利税收入； 决策量：由于每个项目投资数额已定，只是投与不投，我们选择0-1变量； 约束：总资金b亿元.,模型建立,§3.2 背包问题,模型建立,令 设装入物品的总价值为z，则上述背包问题的数学模型为,§3.3 合理下料问题,方案,每根原料下管根数,规格,模型建立,设 为采用方案 所用钢筋数， 为所用钢筋总数,练习: 现有长度为500cm的钢管，要截98cm,78cm的两种 钢管，各要1000根，2000根。问：怎样截，用原料最少？,方案,规格,每根下料数,模型的建立,模型建立,设 为采用方案 下料所用钢板的数量， 为所用钢板总数,问题: 如何下料最节省 ?,例3 钢管下料,节省的标准是什么？,按照客户需要在一根原料钢管上安排切割的一种组合。,切割模式,合理切割模式的余料应小于客户需要钢管的最小尺寸,钢管下料,为满足客户需要，按照哪些种合理模式，每种模式切割多少根原料钢管，最为节省？,合理切割模式,2. 所用原料钢管总根数最少,钢管下料问题1,两种标准,1. 原料钢管剩余总余量最小,xi 按第i 种模式切割的原料钢管根数(i=1,2,7),约束,满足需求,决策变量,目标1（总余量）,按模式2切割12根,按模式5切割15根，余料27米,最优解：x2=12, x5=15, 其余为0； 最优值：27,整数约束： xi 为整数,1.当余料没有用处时，通常以总根数最少为目标,目标2（总根数）,约束条件不变,最优解：x2=15, x5=5, x7=5, 其余为0； 最优值：25。,xi 为整数,按模式2切割15根，按模式5切割5根，按模式7切割5根，共25根，余料35米,虽余料增加8米，但减少了2根,与目标1的结果“共切割27根，余料27米” 相比,2.在需求的规格数量不多的情况下，可采用“列 举法”，确定可行的、合理的切割模式。当规格数量=4时，列举工作量就很大了。 3.下料问题建模，由两部分构成 确定下料可行、合理的模式-无通用的方法 构造优化模型选择合适的目标 4.对于一维（钢管、钢筋等）下料问题，当所需要的规格数量不多时，可采用枚举法求解。,§3.4 生产组织与计划问题,问题分析,决策量：机床 加工 的数量 ， 共 个 约束：机床 工作能力 ；对零件 需求数量 个 目标：总成本 (元),模型建立,车床,B1 B2 B3,B1 B2 B3,§3.5 工厂选址问题,问题分析,决策量：确定是否选择 建厂； 到 运送量 目标：总花费=固定成本费+产品运输费 约束：建厂地点要求，生产能力，需求量要 求 运费运送量连续变量 在 建厂或不建用0或1表示,构成了混合整数规划,模型建立,问题分析,目标：求最大利润 决策变量：是否在 点建立门市部，0-1变量 约束： 满足选点规定 ；投资总额 约定符号：,模型建立,§3.6 指派问题,模型建立,人,如何选拔队员组成4100米混合泳接力队?,§3.7 混合泳接力队的选拔,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+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,甲 自由泳、乙 蝶泳、丙 仰泳、丁 蛙泳.,为了选修课程门数最少，应学习哪些课程 ？,§3.8 选课策略,要求至少选两门数学课、三门运筹学课和两门计算机课,选修课程最少，且学分尽量多，应学习哪些课程 ？,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,模型求解,学分最多,多目标优化的处理方法：化成单目标优化。,两目标(多目标)规划,讨论：选修课程最少，学分尽量多，应学习哪些课程？,课程最少,以学分最多为目标，不管课程多少。,以课程最少为目标，不管学分多少。,多目标规划,对学分数和课程数加权形成一个目标，如三七开。,最优解： x1 = x2 = x3 = x4 = x5 = x6 = x7 = x9 =1， 其它为0；总学分28。,讨论与思考,最优解与1=0，2=1的结果相同学分最多,多目标规划,最优解与1=1，2=0的结果相同课程最少,§3.9 招聘服务员问题,1. 某储蓄所每天的营业时间是上午9：0017:00.根据经验，每天不同时段所需要的服务员数量如下：,2.储蓄所可以雇佣全时和半时两类服务员。全时服务员报酬100元/天，从上午9：00-17：00工作，但是中午12：00-14：00之间必须安排1小时的午餐时间。 3.储蓄所每天可以雇佣不超过3名的半时服务员，每个半时服务员必须连续工作4小时，报酬40元/天。 该储蓄所应如何雇佣这两类服务员，使总的费用最少？ 若不能雇佣半时服务员，每天至少增加多少费用？ 若雇佣半时服务员的数量没有限制，每天可以减少多少费用？,问题分析,
