资源描述：
《《整数线性规划问题》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第二章整数线性规划IntegerlinearProgramming整数线性规划问题的概念与数学模型割平面法分支定界法完全枚举法第一节整数线性规划问题整数线性规划（ILP）具有下述形式纯整数规划0-1整数线性规划模型混合整数线性规划整数规划（简称：IP）一个规划问题中要求部分或全部决策变量必须取整数，则该问题称为整数规划。如果模型是线性的，称为整数线性规划(ILP)。本章只讨论整数线性规划。（1）纯整数规划问题——合理下料问题设用某型号的圆钢下零件A1,A2,…,Am的毛坯。在一根圆钢上下料的方式有B1,B2,…Bn种，
2、每种下料方式可以得到各种零件的毛坯数以及每种零件的需要量，如表所示。问怎样安排下料方式，使得即满足需要，所用的原材料又最少？零件毛坯数个数型号方式数学模型表示为：设：xj表示用Bj(j=1.2…n)种方式下料根数（2）混合整数规划问题某公司计划在m个地点建厂，可供选择的地点有A1,A2…Am，他们的生产能力分别是a1,a2,…am（假设生产同一产品）。第i个工厂的建设费用为fi(i=1.2…m),又有n个地点B1,B2,…Bn需要销售这种产品，其销量分别为b1.b2…bn。从工厂运往销地的单位运费为Cij。试决定应在哪
3、些地方建厂，即满足各地需要，又使总建设费用和总运输费用最省？厂址生产能力建设费用销量单价销地设：xij表示从工厂i运往销地j的运量(i=1.2…m、j=1.2…n),1在Ai建厂又设yi＝（i=1.2…m）0不在Ai建厂模型：（3）0－1整数规划问题现有资金总额为B。可供选择的投资项目有n个，项目j所需投资额和预期收益分别为aj和cj（j＝1,2,..,n），此外由于种种原因，有三个附加条件：若选择项目1，就必须同时选择项目2。反之不一定项目3和4中至少选择一个；项目5,6,7中恰好选择2个。应该怎样选择投资项目，才能
4、使总预期收益最大？项目1项目j项目nx1xjxn设：对每个项目的选择都有2种，即选择与不选择，因此分别用0和1表示，令xj表示第j个项目的决策选择，记为：1对项目j投资Xj＝（j＝1,2,…,n）0对项目j不投资则问题的模型可以表示为：背包(knapsack)问题背景旅行背包：容量一定的背包里装尽可能的多的物品一位旅行者出发前准备在自己的背包里携带必需的物品,已知可供选择的物品有n种,第j种物品的重量为公斤,其价值为,若背包所带物品的总重量不得超过b公斤,问他应如何选择所带物品，以使总价值最大。物品12…j…n重量（公
5、斤/件）a1a2…aj…an每件使用价值c1c2…cj…cn解：设则背包问题的数学模型如下：实例某人出国留学打点行李，现有三个旅行包，容积大小分别为1000毫升、1500毫升和2000毫升，根据需要列出需带物品清单，其中必带物品共有7件，其体积大小分别为400、300、150、250、450、760、190（单位毫升）。尚有10件可带可不带物品，如果不带将在目的地购买，通过网络查询可以得知其在目的地的价格（单位美元）。这些物品的容量及价格分别见下表，试给出一个合理的安排方案把物品放在三个旅行包里。物品123456789
6、10体积200350500430320120700420250100价格1545100705075200902030解：变量—设变量为第i个物品是否放在第j个包裹中约束包裹容量限制必带物品限制选带物品限制目标函数—未带物品购买费用最小模型旅行售货员(货郎担)问题（TSP）20个城市哈密顿图：不重复的走遍所有的点再返回出发点。分析变量—是否从i第个城市（出）到第j个城市（进）约束—每个城市只能离开一次、到达一次目标—总费用最小数学模型每座城市恰好出一次每座城市恰好进一次直接从vi进入vj其它整数线性规划问题数学模型的一般
7、形式：标准形式松弛问题：不考虑整数条件，由余下的目标函数和约束条件构成的规划问题称为该整数规划问题的松弛问题整数线性规划松弛的线性规划整数规划问题的松弛问题（1）整数规划问题的可行解是松弛问题的可行解吗？（2）松弛问题的最优解就是整数规划问题的最优解吗？（否）（3）松弛问题的最优解经过整化处理后就是整数规划问题的最优解吗？整数规划问题的可行解集合是它的松弛问题可行解集合的一个子集,因此整数规划问题的可行解一定是它的松弛问题的可行解，反之不一定。整数规划问题的最优值不会优于它松弛问题最优值。例：设整数规划问题如下首先不考
8、虑整数约束，得到线性规划问题（一般称为松弛问题）。用图解法求出最优解为：x1＝3/2,x2=10/3，且有Z=29/6x1x2⑴⑵33(3/2,10/3)现求整数解（最优解）：如用“舍入取整法”可得到4个点即(1，3)(2，3)(1，4)(2，4)。显然，它们都不是整数规划的可行解,因而不是最优解。按整数规划约束条件，当可行解为有
