《整数规划模型》由会员分享，可在线阅读，更多相关《整数规划模型（51页珍藏版）》请在金锄头文库上搜索。
1、第3章 整数规划模型3.1 投资决策问题问题分析 目标：利税收入； 决策量：由于每个项目投资数额已定 ，只是投与不投，我们选择0-1变量 ； 约束：总资金b亿元.模型建立3.2 背包问题模型建立 令 设装入物品的总价值为z，则上述背包问 题的数学模型为3.3 合理下料问题需求量3米长长 3个 2个 0个 5根4米长长 0个 1个 2个 5根余料量 1米 0米 2米所用钢钢 筋数最 少方案每根原料下 管根数规格模型建立 设 为采用方案 所用钢 筋数， 为所用钢筋总数练习:现有长度为500cm的钢 管，要截98cm,78cm的两种 钢管，各要1000根，2000根 。问：怎样截，用原料最少 ？B1
2、B2B3B4B5B6需求 量 A15432101000 根 A20123562000 根方案规格每根 下料 数模型的建立模型建立 设 为采用方案 下料所用钢板 的数量， 为所用钢板总数问题: 如何下料最节省 ? 例3 钢管下料 原料钢管:每根19米 4米50根 6米20根 8米15根 客户需求节省的标准是什么？按照客户需要在一根原料钢管上安排切割的一种组合。 切割模式余料1米 4米1根 6米1根 8米1根 余料3米 4米1根 6米1根 6米1根 合理切割模式的余料应小于客户需要钢管的最小尺寸余料3米 8米1根 8米1根 钢管下料 为满足客户需要，按照哪些种合理模式，每种模式 切割多少根原料钢管
3、，最为节省？合理切割模式2. 所用原料钢管总根数最少 模式 4米钢管根数6米钢管根数8米钢管根数余料(米) 14003 23101 32013 41203 51111 60301 70023钢管下料问题1 两种 标准1. 原料钢管剩余总余量最小xi 按第i 种模式切割的原料钢管根数(i=1,2,7) 约束满足需求 决策变量 目标1（总余量）按模式2切割12根,按模式5切割15根，余料27米 模 式4米 根数6米 根数8米 根数余 料 14003 23101 32013 41203 51111 60301 70023需 求502015最优解：x2=12, x5=15, 其余为0； 最优值：27整
4、数约束： 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.对于一维（钢管、钢筋等）
5、下料问题，当所需要 的规格数量不多时，可采用枚举法求解。3.4 生产组织与计划问题问题分析 决策量：机床 加工 的数量 ，共 个 约束：机床 工作能力 ；对零件 需求 数量 个 目标：总成本 (元)模型建立工件机时（小时 ）加工费车床机时 限制（小 时）甲0.4 1.1 1.013 9 10800乙0.5 1.2 1.3 11 12 8900 需求量400 600 500总加工费 用最小车床B1 B2 B3B1 B2 B33.5 工厂选址问题问题分析 决策量：确定是否选择 建厂； 到 运送 量 目标：总花费=固定成本费+产品运输费 约束：建厂地点要求，生产能力，需求量 要 求 运费运送量连续变
6、量在 建厂或不建用0或1表示构成了混合整 数规划模型建立问题分析 目标：求最大利润 决策变量：是否在 点建立门市部，0-1 变量 约束： 满足选点规定 ；投资总额 约定符号： 模型建立3.6 指派问题模型建立任 务英 日 德 俄 甲 215134乙 1041415丙 9141613丁 78119人如何选拔队员组成4100米混合泳接力队?3.7 混合泳接力队的选拔 甲乙丙丁戊蝶泳106”857”2118”110”107”4 仰泳115”6106”107”8114”2111” 蛙泳127”106”4124”6109”6123”8 自由泳58”653”59”457”2102”45名候选人的百米成绩穷
7、举法：组成接力队的方案共有5!=120种。目标 函数若选择队员i参加泳姿j 的比赛，记xij=1, 否则记xij=0 0-1规划模型 cij(秒)队员i 第j 种泳姿的百米成绩约束 条件每人最多入选泳姿之一 ciji=1i=2i=3i=4i=5 j=166.857.2787067.4 j=275.66667.874.271 j=38766.484.669.683.8 j=458.65359.457.262.4每种泳姿有且只有1人 模型求解 最优解：x14 = x21 = x32 = x43 = 1, 其它变量为0;成绩为253.2(秒)=413”2 MIN 66.8x11+75.6x12+87
8、x13+58.6x14+ +67.4x51+71 x52+83.8x53+62.4x54 SUBJECT TOx11+x12+x13+x14 =1 x41+x42+x43+x44 =1x11+x21+x31+x41+x51 =1 x14+x24+x34+x44+x54 =1 END INT 20 甲乙丙丁戊蝶泳106”857”2118”110”107”4 仰泳115”6106”107”8114”2111” 蛙泳127”106”4124”6109”6123”8自由泳58”653”59”457”2102”4甲 自由泳、乙 蝶泳、 丙 仰泳、丁 蛙泳.为了选修课程门数最少，应学习哪些课程 ？ 3.8
9、 选课策略要求至少选两门数学课、三门运筹学课和两门计算机课 课号课名学分所属类别先修课要求1微积分5数学 2线性代数4数学 3最优化方法4数学；运筹学微积分；线性代数 4数据结构3数学；计算机计算机编程 5应用统计4数学；运筹学微积分；线性代数 6计算机模拟3计算机；运筹学计算机编程 7计算机编程2计算机 8预测理论2运筹学应用统计 9数学实验3运筹学；计算机微积分；线性代数选修课程最少，且学分尽量多，应学习哪些课程 ？ 0-1规划模型 决策变量 目标函数 xi=1 选修课号i 的 课程（xi=0 不选） 选修课程总数最少 约束条件最少2门数学课， 3门运筹学课， 2门计算机课。 课号课名所属
10、类别1微积分数学 2线性代数数学 3最优化方法数学；运筹学 4数据结构数学；计算机 5应用统计数学；运筹学 6计算机模拟计算机；运筹学 7计算机编程计算机 8预测理论运筹学 9数学实验运筹学；计算机先修课程要求最优解： x1 = x2 = x3 = x6 = x7 = x9 =1, 其它为0；6门课程，总学分21 0-1规划模型 约束条件x3=1必有x1 = x2 =1模型求解 课号课名先修课要求1微积分 2线性代数 3最优化方法微积分；线性代数 4数据结构计算机编程 5应用统计微积分；线性代数 6计算机模拟计算机编程 7计算机编程 8预测理论应用统计 9数学实验微积分；线性代数学分最多多目标
11、优化的处理方法：化成单目标优化。两目标(多目标)规划 讨论：选修课程最少，学分尽量多，应学习哪些课程？ 课程最少 以学分最多为目标，不管课程多少。 以课程最少为目标，不管学分多少。最优解如上，6门课 程，总学分21 。最优解显然是选修所 有9门课程 。多目标规划 对学分数和课程数加权形成一个目标，如三七开。 最优解： x1 = x2 = x3 = x4 = x5 = x6 = x7 = x9 =1， 其它为0；总学分28。课号课名学分1微积分5 2线性代数4 3最优化方法4 4数据结构3 5应用统计4 6计算机模拟3 7计算机编程2 8预测理论2 9数学实验3 讨论与思考最优解与1=0，2=1
12、的结果相同学分最多多目标规划 最优解与1=1，2=0的结果相同课程最少3.9 招聘服务员问题 1. 某储蓄所每天的营业时间是上午9：00 17:00.根据经验，每天不同时段所需要的服 务员数量如下：时 段9- 1010- 1111- 1212- 1313- 1414- 1515- 1616- 17 数 量434656882.储蓄所可以雇佣全时和半时两类服务员。全 时服务员报酬100元/天，从上午9：00-17： 00工作，但是中午12：00-14：00之间必须 安排1小时的午餐时间。 3.储蓄所每天可以雇佣不超过3名的半时服务 员，每个半时服务员必须连续工作4小时， 报酬40元/天。 该储蓄所应如何雇佣这两类服务员，使总的 费用最少？ 若不能雇佣半时服务员，每天至少增加多少 费用？ 若雇佣半时服务员的数量没有限制，每天可 以减少多少费用？问题分析
