2-运筹学整数规划案列.ppt

背包问题应用（作业） 要把7种规格的包装箱装到两辆铁路平板车上去，包装箱的宽和高相同，但厚度和重量不同，见下表： 每辆车有10.2m长的地方可以用来装箱（类似面包片），载重为40吨。C5， C6 ， C7 ，三类包箱所占总空间（厚度）不超过302.7cm，试建立数学模型，尽量将这些包装箱装到平板车上去，使浪费的空间最小。 5. 指派问题 在生活中经常遇到这样的问题，某单位需要完成n项任务，恰好有n个人可以承担这些任务，由于每个人的专长不同，个人完成不同任务的效率（时间、费用等）也不同。 于是产生了指派哪个人去完成哪项任务，使总效率最高，称为指派问题（Assignment Problem）。 已知上面5名运动员各种姿势游泳成绩（50m），试问如何从中选拔一个200m混合泳的接力队，使预期比赛成绩最好。（列出整数规划模型） * * 整数规划建模 应用最广泛的整数规划问题是各种类型的决策问 题，决策者希望模型能回答诸如：是否要执行某些项 目（或某些活动），在什么时候或什么地点执行等决 策问题，回答这类“是—否”或“有—无”问题可借助整 数规划中的0-1整数变量。 0-1整数变量只有两个选择，0由于它在数学上的 特性可以很好的代表“无”或“否”，而1则可以很好地代 表“有”或“是”。0-1变量由于它的特殊性也被称为二进 制变量、决策变量或逻辑变量。 0-1变量的作用 1. xj＝ 1…方案j被选中 0…方案j未被选中 2. 从n个方案中必须选中一个： 3. 从n个方案中最多选中m个： 4. 方案i只有在方案j选中时，才可能被选中： 5. 方案i与方案j是否选中是同时的： 与0－1变量相关的几个实际问题 1. 投资问题 现有总额为b的资金可用于投资，共有n个项目可 供投资者选择，已知项目j所需投资额为aj，投资后可 得利润cj（j ＝ 1，2，…，n），不妨设b，aj，cj 均是 整数，试问为使所得利润最大，应选取那些项目进行 投资？ 先引入0－1变量xj，令 xj＝ 1…对项目j投资 0…否则 则可得到如下整数规划问题： 例1：华美公司有5个项目被列入投资计划，各项目的投 资额和期望的投资收益见下表： 180 260 5 80 130 4 60 100 3 210 300 2 150 210 1 投资收益（万元） 投资额（万元） 项目 该公司只有600万元资金可用于投资，由于技术上 的原因，投资受到以下约束：①在项目1、2和3中必须 有一项被选中；②项目3和4只能选一项；③项目5被选 中的前提是项目1必须被选中。问如何在上述条件下选 择一个最好的投资方案，使投资收益最大。 令0-1变量为决策变量，即xi＝1表示选中项目i， 否则xi＝0表示项目i未被选中。则模型可以表示为： 解： 2. 背包问题 背包问题由来以久，它是从旅行者如何选择放在 背包中的用品引出的。 旅行者可背负的重量有限，但旅行者需要携带的 物品很多，如：食品、水、衣物、帐篷、急救用品等 等，旅行者不可能将所有想携带的物品都统统背上， 他只能选择那些最重要的物品随身携带，又不超过他 可能负担的最大重量，为解决这个问题，旅行者可给 每种物品指定一个重要性系数，他的目标是在小于一 定重量的前提下，使所携带的物品的重要性系数之和 最大。 例2 ：一登山队员做登山准备，他需要携带的物品有： 食品、氧气、冰镐、绳索、帐篷、照相机和通讯设备 每种物品的重要系数和重量如下表所示，假定登山队 员可携带的最大重量为25千克。问他如何抉择？ 10 4 8 14 18 15 20 重要系数 4 2 12 6 2 5 5 重量 （千克） 通讯设备 照相器材 帐篷 绳索 冰镐 氧气 食品 物品 7 6 5 4 3 2 1 序号 令xi＝1表示登山队员携带物品i，xi＝0表示 不带物品i。则问题可写为： Max z =20x1+15x2+18x3 +14x4+8x5+4x6+10x7 s.t. 5x1+ 5x2 + 2x3 +6x4+12x5+2x6+4x7≤25 xi=1或0，i=1,2,…,7 解： 例3.一公司考虑在四个城市：北京、上海、广州和武汉设立库房。 这些库房负责向三个地区：华北、华中和华南地区发运货物，每 个库房每月可处理货物1000件。在北京设库房每月的成本为4.5万 元。上海为5万元，广州为7万元，武汉为4万元。每个地