nullnull运 筹 学 课 件Integer Linear Programming整 数 规 划整 数 规 划整数
规划
污水管网监理规划下载职业规划大学生职业规划个人职业规划职业规划论文
问题与模型
整数规划算法
计算软件
应用案例整数规划问题整数规划问题实例
特点
模型分类应用案例应用案例投资组合问题
旅游售货员问题
背包问题投资组合问题投资组合问题背 景
实 例
模 型背 景背 景证券投资:把一定的资金投入到合适的有价证券上以规避风险并获得最大的利润。
项目投资:财团或银行把资金投入到若干项目中以获得中长期的收益最大。案 例案 例某财团有 万元的资金,经出其考察选中 个投资项目,每个项目只能投资一个。其中第 个项目需投资金额为 万元,预计5年后获利 ( )万元,问应如何选择项目使得5年后总收益最大?模 型模 型变量—每个项目是否投资
约束—总金额不超过限制
目标—总收益最大null旅游售货员问题旅游售货员问题背景
案例
模型背 景背 景旅游线路安排
预定景点走且只走一次
路上时间最短
配送线路—货郎担问题
送货地到达一次
总路程最短案 例案 例有一旅行团从 出发要遍游城市
,已知从 到 的旅费为 ,问应如何安排行程使总费用最小?模 型模 型变量—是否从i第个城市到第j个城市
约束
每个城市只能到达一次、离开一次null避免出现断裂
每个点给个位势 除了初始点外要求前点比后点大null目标—总费用最小null背包问题背包问题背景
案例
模型背 景背 景邮递包裹
把形状可变的包裹用尽量少的车辆运走
旅行背包
容量一定的背包里装尽可能的多的物品实 例实 例某人出国留学打点行李,现有三个旅行包,容积大小分别为1000毫升、1500毫升和2000毫升,根据需要列出需带物品
清单
安全隐患排查清单下载最新工程量清单计量规则下载程序清单下载家私清单下载送货清单下载
,其中一些物品是必带物品共有7件,其体积大小分别为400、300、150、250、450、760、190、(单位毫升)。尚有10件可带可不带物品,如果不带将在目的地购买,通过网络查询可以得知其在目的地的价格(单位美元)。这些物品的容量及价格分别见下表,试给出一个合理的安排方案把物品放在三个旅行包里。 null问题分析问题分析变量—对每个物品要确定是否带同时要确定放在哪个包裹里,如果增加一个虚拟的包裹把不带的物品放在里面,则问题就转化为确定每个物品放在哪个包裹里。如果直接设变量为每个物品放在包裹的编号,则每个包裹所含物品的总容量就很难写成变量的函数。为此我们设变量为第i个物品是否放在第j个包裹中null约束包裹容量限制必带物品限制选带物品限制null目标函数—未带物品购买费用最小模 型模 型null特征—变量整数性要求
来源
问题本身的要求
引入的逻辑变量的需要
性质—可行域是离散集合null线性整数规划模型线性整数规划模型一般整数规划模型
0-1整数规划模型
混合整数规划模型一般整数规划模型一般整数规划模型0-1整数规划模型0-1整数规划模型混合整数规划模型混合整数规划模型算 法算 法与线性规划的关系
分支定界算法
割平面算法
近似算法与线性规划的关系与线性规划的关系可行解是放松问题的可行解最优值大于等于放松问题的最优值nullnull注 释注 释最优解不一定在顶点上达到
最优解不一定是放松问题最优解的邻近整数解
整数可行解远多余于顶点,枚举法不可取分支定界算法分支定界算法算法思想
算法步骤
算例
注释
圣经注释小学小古文100篇及注释小古文100篇及注释简短小古文100篇及注释译文小古文100篇及注释
算 法 思 想算 法 思 想隐枚举法
求解放松问题最优值比界坏分 支边 界分 支舍 弃分支的方法分支的方法nullnull定 界定 界当前得到的最好整数解的目标函数值
分支后计算放松的线性规划的最优解
整数解且目标值小于原有最好解的值则替代原有最好解
整数解且目标值大于原有最好解的值则 删除该分支其中无最优解
非整数解且目标值小于原有最好解的值则继续分支
非整数解且目标值大于等于原有最好解的值则删除该分支其中无最优解nullnull算 例算 例nullnullnull注 释注 释求解混合整数规划问题,只对整数变量分支,对非整数变量不分支。null对0-1整数规划分支时割平面算法割平面算法算法思想
算法步骤
算例算 法 思 想算 法 思 想由放松问题的可行域向整数规划的可行域逼近
方法—利用超平面切除
要求
整数解保留
放松问题最优值增加割平面生成方法割平面生成方法条件--保留整数解删除最优解null整数可行解最优基可行解nullnullnullnullnullnull算 法 步 骤算 法 步 骤算 例算 例nullnullnullnullnullnull计 算 软 件计 算 软 件整数变量定义
LinDo
一般整数变量:GIN
0-1整数变量: INT
LinGo
一般整数变量: @GIN( variable_name);
0-1整数变量:@BIN( variable_name);
算例算 例算 例 max 3 x1+5 x2+4 x3
subject to
2 x1+3 x2<=1500
2 x2+4 x3<=800
3 x1+2 x2 +5 x3<=2000
end
gin x1
gin x3应用案例分析应用案例分析人力资源分配问题
应急设施选址问题人力资源分配问题人力资源分配问题某个中型百货商场对售货人员(周工资200元)的需求经统计如下表
为了保证销售人员充分休息,销售人员每周工作5天,休息2天。问应如何安排销售人员的工作时间,使得所配售货人员的总费用最小?模型假设模型假设每天工作8小时,不考虑夜班的情况;
每个人的休息时间为连续的两天时间;
每天安排的人员数不得低于需求量,但可以超过需求量问题分析问题分析因素 不可变因素:需求量、休息时间、单位费用;
可变因素:安排的人数、每人工作的时间、总费用;
方案 确定每天工作的人数,由于连续休息2天,当确定每个人开始休息的时间就等于知道工作的时间,因而确定每天开始休息的人数就知道每天开始工作的人数,从而求出每天工作的人数。
变量 每天开始休息的人数
约束条件
1.每人休息时间2天,自然满足。
nullnull目标函数:总费用最小,总费用与使用的总人数成正比。由于每个人必然在且仅在某一天开始休息,所以总人数等于模 型模 型注 解注 解该问题本质上是个整数规划问题,放松的线性规划的最优解是个整数解,所以两规划等价。
定义整数变量用函数@gin(x1)……
@gin(x7);
0-1整数变量为@bin(x1)应急选址问题应急选址问题 某城市要在市区设置k个应急服务中心,经过初步筛选确定了m个备选地,现已知共有n个居民小区,各小区到个备选地的距离为 为了使得各小区能及时得到应急服务,要求各小区到最近的服务中心的距离尽可能的短,试给出中心选址方案。问题分析问题分析 该问题与传统的选址问题的主要区别在于其目标不再是要求费用最小,而是要求最长距离最短。也就是离服务中心距离最远的小区离最近的服务中心距离最小。
变量:当中心的位置确定下来后,各小区对应的最近中心也就确定,所以真正的变量也就是小区的位置。设 问题分析问题分析 为了便于说明问题引入间接变量,第i小区是否由第j个中心服务
以及最远的距离
约束条件
小区服务约束问 题 分 析问 题 分 析最远距离约束
中心个数约束
目标函数:最远距离 最小模 型模 型