运筹学(整数规划).pptVIP

整数规划( Integer Programming ) 整数规划的特点及应用 整数规划（简称：IP） 要求一部分或全部决策变量取整数值的规划问题称为整数规划。不考虑整数条件，由余下的目标函数和约束条件构成的规划问题称为该整数规划问题的松弛问题。若该松弛问题是一个线性规划，则称该整数规划为整数线性规划。 整数规划的特点及应用 整数线性规划问题的种类： 线性整数规划模型 一般整数规划模型 0-1整数规划模型 混合整数规划模型 一般整数规划模型 0-1整数规划模型 混合整数规划模型 整数规划的特点及应用 整数规划的典型例子 整数规划的特点及应用 解：这是一个物资运输问题，特点是事先不能确定应该建A3还是A4中哪一个，因而不知道新厂投产后的实际生产物资。为此，引入0-1变量： 整数规划的特点及应用 整数规划的特点及应用 例2 现有资金总额为B。可供选择的投资项目有n个，项目j所需投资额和预期收益分别为aj和cj（j＝1,2,..,n），此外由于种种原因，有三个附加条件： 若选择项目1，就必须同时选择项目2。反之不一定 项目3和4中至少选择一个； 项目5,6,7中恰好选择2个。 应该怎样选择投资项目，才能使总预期收益最大。 整数规划的特点及应用 解：对每个投资项目都有被选择和不被选择两种可能，因此分别用0和1表示，令xj表示第j个项目的决策选择，记为： 整数规划的特点及应用 例3 指派问题或分配问题。人事部门欲安排四人到四个不同岗位工作，每个岗位一个人。经考核四人在不同岗位的成绩（百分制）如表所示，如何安排他们的工作使总成绩最好。 整数规划的特点及应用 整数规划的特点及应用 每项工作只能安排一人，约束条件为： 背包问题 背景 案例 模型 背 景 邮递包裹 把形状可变的包裹用尽量少的车辆运走 旅行背包 容量一定的背包里装尽可能的多的物品 实 例 某人出国留学打点行李，现有三个旅行包，容积大小分别为1000毫升、1500毫升和2000毫升，根据需要列出需带物品清单，其中一些物品是必带物品共有7件，其体积大小分别为400、300、150、250、450、760、190、（单位毫升）。尚有10件可带可不带物品，如果不带将在目的地购买，通过网络查询可以得知其在目的地的价格（单位美元）。这些物品的容量及价格分别见下表，试给出一个合理的安排方案把物品放在三个旅行包里。 实 例 问题分析 变量—对每个物品要确定是否带同时要确定放在哪个包裹里，如果增加一个虚拟的包裹把不带的物品放在里面，则问题就转化为确定每个物品放在哪个包裹里。如果直接设变量为每个物品放在包裹的编号，则每个包裹所含物品的总容量就很难写成变量的函数。为此我们设变量为第i个物品是否放在第j个包裹中 约束条件 目标函数—未带物品购买费用最小 模 型 整数规划的特点 整数规划的特点 整数规划的特点 整数规划的特点及应用 整数规划问题解的特征： 与线性规划的关系 整数规划的特点及应用 例4 设整数规划问题如下 整数规划的特点及应用 用图解法求出最优解为：x1＝3/2, x2 = 10/3，且有Z = 29/6 注 释 最优解不一定在顶点上达到 最优解不一定是放松问题最优解的邻近整数解 整数可行解远多余于顶点，枚举法不可取 整数规划的特点及应用 整数规划问题的求解方法： 分支定界算法 算法思想 算法步骤 算例 注释 算 法 思 想 隐枚举法 求解放松问题 分支定界法 1）求整数规划的松弛问题最优解； 若松弛问题的最优解满足整数要求，得到整数规划的最优解,否则转下一步； 2）分支与定界： 任意选一个非整数解的变量xi，在松弛问题中加上约束： xi≤[xi] 和 xi≥[xi]+1 组成两个新的松弛问题，称为分枝。新的松弛问题具有特征：当原问题是求最大值时，目标值是分枝问题的上界；当原问题是求最小值时，目标值是分枝问题的下界。 检查所有分枝的解及目标函数值，若某分枝的解是整数并且目标函数值大于（max）等于其它分枝的目标值，则将其它分枝剪去不再计算，若还存在非整数解并且目标值大于(max)整数解的目标值，需要继续分枝，再检查，直到得到最优解。 分支定界法 例5 用分枝定界法求解整数规划问题 分支定界法 用图解法求松弛问题的最优解，如图所示。 分支定界法 分支： 分支定界法 先求LP1,如图所示。此时在B点取得最优解。 x1＝1, x2 =3, Z(1)＝－16 找到整数解，问题已探明，此枝停止计算。 分支定界法 在IP2中分别再加入条件： x2≤3, x2≥4 得下式两支： 分支定界法 分支定界法 在（LP21）的基础上继续分枝。加入条件3≤x1≤2有下式： 分支定界法 分支定界法 原整数规划问题的最优解为: x