《第3章整数规划模型.ppt》由会员分享，可在线阅读，更多相关《第3章整数规划模型.ppt（51页珍藏版）》请在三一办公上搜索。
1、第3章 整数规划模型,3.1 投资决策问题,问题分析,目标：利税收入；决策量：由于每个项目投资数额已定，只是投与不投，我们选择0-1变量；约束：总资金b亿元.,模型建立,3.2 背包问题,模型建立,令设装入物品的总价值为z，则上述背包问题的数学模型为,3.3 合理下料问题,方案,每根原料下管根数,规格,模型建立,设 为采用方案 所用钢筋数，为所用钢筋总数,练习:现有长度为500cm的钢管，要截98cm,78cm的两种 钢管，各要1000根，2000根。问：怎样截，用原料最少？,方案,规格,每根下料数,模型的建立,模型建立,设 为采用方案 下料所用钢板的数量，为所用钢板总数,问题:如何下料最节省
2、?,例3 钢管下料,节省的标准是什么？,按照客户需要在一根原料钢管上安排切割的一种组合。,切割模式,合理切割模式的余料应小于客户需要钢管的最小尺寸,钢管下料,为满足客户需要，按照哪些种合理模式，每种模式切割多少根原料钢管，最为节省？,合理切割模式,2.所用原料钢管总根数最少,钢管下料问题1,两种标准,1.原料钢管剩余总余量最小,xi 按第i 种模式切割的原料钢管根数(i=1,2,7),约束,满足需求,决策变量,目标1（总余量）,按模式2切割12根,按模式5切割15根，余料27米,最优解：x2=12,x5=15,其余为0；最优值：27,整数约束：xi 为整数,1.当余料没有用处时，通常以总根数最
3、少为目标,目标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 生产组织与计
4、划问题,问题分析,决策量：机床 加工 的数量，共 个约束：机床 工作能力；对零件 需求数量 个目标：总成本(元),模型建立,车床,B1 B2 B3,B1 B2 B3,3.5 工厂选址问题,问题分析,决策量：确定是否选择 建厂；到 运送量目标：总花费=固定成本费+产品运输费约束：建厂地点要求，生产能力，需求量要 求运费运送量连续变量 在 建厂或不建用0或1表示,构成了混合整数规划,模型建立,问题分析,目标：求最大利润决策变量：是否在 点建立门市部，0-1变量约束：满足选点规定；投资总额约定符号：,模型建立,3.6 指派问题,模型建立,人,如何选拔队员组成4100米混合泳接力队?,3.7 混合泳接
5、力队的选拔,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.4x54SUBJECT TO x11+x12+x13+x14=1 x41+x42+x43+x44=1 x11
6、+x21+x31+x41+x51=1 x14+x24+x34+x44+x54=1END 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
7、=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元/天。该储蓄所应如何雇佣这两类服务员，使总的费用最少？若不能雇佣半时服务员，每天至少增加多少费用？若雇佣半时服务员的数量没有限制，每天可以减少多少费用？,问题分析,
