整数规划.pptVIP

第八章 整 数 规 划 整数规划 整数规划问题的定义 整数规划问题与模型 整数规划算法 计算软件 应用案例 整数规划的基本含义: 在线性规划问题中,求得的最优解有时可能是整数,也有可能不是整数,对于某些实际问题,要求必须是整数,象这种要求结果是整数解的,称为整数规划问题.若结果要求是0-1整数结果,则称为0-1规划问题. 整数规划问题 实例 特点 模型分类 应用案例 投资组合问题 旅游售货员问题 背包问题 投资组合问题 背 景 实 例 模 型 背景 证券投资：把一定的资金投入到合适的有价证券上以规避风险并获得最大的利润 项目投资：财团或银行把资金投入到若干项目中以获得中长期的收益最大。 案例 某财团有 万元的资金，经出其考察选中 个投资项目，每个项目只能投资一个。其中第 个项目需投资金额为 万元，预计5年后获利 万元 ，问应如何选择项目使得5年后总收益最大？ 模型 变量—每个项目是否投资 约束—总金额不超过限制 目标—总收益最大 旅游售货员问题 背景 案例 模型 背景 旅游线路安排 预定景点走且只走一次 路上时间最短 配送线路—货郎担问题 送货地到达一次 总路程最短 案例 有一旅行团从 出发要遍游城市 ，已知从 到 的旅费为 ，问应如何安排行程使总费用最小？ 模型 变量—是否从i第个城市到第j个城市 约束 每个城市只能到达一次、离开一次 目标—总费用最小 背包问题 背景 案例 模型 背景 邮递包裹 把形状可变的包裹用尽量少的车辆运走 旅行背包 容量一定的背包里装尽可能的多的物品 实例 某人出国留学打点行李，现有三个旅行包，容积大小分别为1000毫升、1500毫升和2000毫升，根据需要列出需带物品清单，其中一些物品是必带物品共有7件，其体积大小分别为400、300、150、250、450、760、190、（单位毫升）。尚有10件可带可不带物品，如果不带将在目的地购买，通过网络查询可以得知其在目的地的价格（单位美元）。这些物品的容量及价格分别见下表，试给出一个合理的安排方案把物品放在三个旅行包里。 问题分析 变量—对每个物品要确定是否带同时要确定放在哪个包裹里，如果增加一个虚拟的包裹把不带的物品放在里面，则问题就转化为确定每个物品放在哪个包裹里。如果直接设变量为每个物品放在包裹的编号，则每个包裹所含物品的总容量就很难写成变量的函数。为此我们设变量为第i个物品是否放在第j个包裹中 约束 包裹容量限制 必带物品限制 选带物品限制 目标函数—未带物品购买费用最小 模型 线性整数规划模型 一般整数规划模型 0-1整数规划模型 混合整数规划模型 一般整数规划模型 0-1整数规划模型 混合整数规划模型 算 法 与线性规划的关系 分支定界算法 割平面算法 近似算法 与线性规划的关系 注释 最优解不一定在顶点上达到 最优解不一定是放松问题最优解的邻近整数解 整数可行解远多余于顶点，枚举法不可取 §1 整数规划的图解法 例1 某公司拟用集装箱托运甲乙两种货物，货物体积、重量，获利及若干限制事下表，且甲种货物至多托运4件，问两种货物各托运多少件，可使获得利润最大？ 性质1：任何求最大目标函数值的纯整数规划或混合整数规划的最大目标函数值小于或等于相应的线性规划的最大目标函数值，任何求最小目标函数值的纯整数规划或混合整数规划的最小目标函数值大于或等于相应的线性规划的最小目标数值。 §2 整数规划的计算机求解 §2 整数规划的计算机求解 §2 整数规划的计算机求解 §2 整数规划的计算机求解 整数规划 例3 求解下面的混合整数规划问题： Max z=3x1+x2+3x3 S.t. -x1+2x2+x3=4 4x1-3x2=2 X1-3x2+2x3=3 X3=1 X1,x2,x3 =0, x1,x3为整数 整数规划 例3 求解下面的混合整数规划问题： 源程序代码： Max 3x1+x2+3x3 S.t. -x1+2x2+x3=4 4x2-3x3=2 X1-3x2+2x3=3 X3=1 end Gin x1 int x3 整数规划 OBJECTIVE FUNCTION VALUE 1) 16.25000 VARIABLE VALUE REDUCED COST X1 4.000000 -3.000000 X3 1.000000