《整数线性规划问题》PPT课件.ppt

《《整数线性规划问题》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《整数线性规划问题》PPT课件.ppt（50页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第二章第二章 整数线性规划整数线性规划Integer linear Programming整数线性规划问题的概念与数学模型整数线性规划问题的概念与数学模型割平面法割平面法分支定界法分支定界法完全枚举法完全枚举法第一节第一节 整数线性规划问题整数线性规划问题整数线性规划（整数线性规划（ILPILP）具有下述形式）具有下述形式纯整数规划纯整数规划0-10-1整数线性规划模型整数线性规划模型混合整数线性规划混合整数线性规划整数规划（简称：整数规划（简称：IPIP）一个规划问题中要求部分或全部决策变一个规划问题中要求部分或全部决策变量必须取整数，则该问题称为整数规划。如量必须取整数，则该问题称为整数规

2、划。如果模型是线性的，称为整数线性规划果模型是线性的，称为整数线性规划(ILP)(ILP)。本章只讨论整数线性规划。本章只讨论整数线性规划。（1 1）纯整数规划问题）纯整数规划问题合理下料问题合理下料问题设用某型号的圆钢下零件设用某型号的圆钢下零件A1,A2,Am 的毛坯。在一根圆钢上的毛坯。在一根圆钢上下料的方式有下料的方式有B1,B2,Bn 种，每种下料方式可以得到各种零件的种，每种下料方式可以得到各种零件的毛坯数以及每种零件的需要量，如表所示。问怎样安排下料方式，毛坯数以及每种零件的需要量，如表所示。问怎样安排下料方式，使得即满足需要，所用的原材料又最少？使得即满足需要，所用的原材料又最

3、少？零 件毛坯数 个数 型号方式数学模型表示为：数学模型表示为：设：设：xj 表示用表示用Bj(j=1.2n)种方式下料根数种方式下料根数（2 2）混合整数规划问题）混合整数规划问题某公司计划在某公司计划在m个地点建厂，可供选择的个地点建厂，可供选择的地点有地点有A1,A2Am，他们的生产能力分别是他们的生产能力分别是a1,a2,am（假设生产同一产品）。第（假设生产同一产品）。第i i个工厂个工厂的建设费用为的建设费用为fi(i=1.2m),又有又有n个地点个地点B1,B2,Bn 需要销售这种产品，其销量分别需要销售这种产品，其销量分别为为b1.b2bn。从工厂运往销地的单位运费为。从工厂运

4、往销地的单位运费为Cij。试决定应在哪些地方建厂，即满足各地。试决定应在哪些地方建厂，即满足各地需要，又使总建设费用和总运输费用最省？需要，又使总建设费用和总运输费用最省？厂址生产能力建设费用销量单价销地 设：设：xij 表示从工厂表示从工厂i i 运往销地运往销地j j 的运量的运量(i=1.2m、j=1.2n),),1 1 在在Ai 建厂建厂 又设又设 yi （i=1.2m）0 0 不在不在Ai 建厂建厂 模型：模型：（3 3）0 01 1整数规划问题整数规划问题现有资金总额为现有资金总额为B B。可供选择的投资项目有。可供选择的投资项目有n n个，项个，项目目j j所需投资额和预期收益分

5、别为所需投资额和预期收益分别为a aj j和和c cj j（j j1,2,.,n1,2,.,n），此外由于种种原因，有三个附加条件：），此外由于种种原因，有三个附加条件：若选择项目若选择项目1 1，就必须同时选择项目，就必须同时选择项目2 2。反之不一定。反之不一定 项目项目3 3和和4 4中至少选择一个；中至少选择一个；项目项目5,6,75,6,7中恰好选择中恰好选择2 2个。个。应该怎样选择投资项目，才能使总预期收益最大？应该怎样选择投资项目，才能使总预期收益最大？项目项目1项目项目j项目项目nx1xjxn设：对每个项目的选择都有设：对每个项目的选择都有2 2种，即选择与不选择，因种，即选

6、择与不选择，因此分别用此分别用0 0和和1 1表示，令表示，令x xj j表示第表示第j j个项目的决策选择，记个项目的决策选择，记为：为：1 1 对项目对项目j j投资投资 X Xj j （j j1,2,n1,2,n）0 0 对项目对项目j j不投资不投资 则问题的模型可以表示为：则问题的模型可以表示为：背包背包(knapsack)问题背景问题背景旅行背包：容量一定的背包里装尽可能的多的物品 一位旅行者出发前准备在自己的背包里一位旅行者出发前准备在自己的背包里携带必需的物品携带必需的物品,已知可供选择的物品有已知可供选择的物品有n n种种,第第j j种物品的重量为种物品的重量为 公斤公斤,其

7、价值为其价值为 ,若若背包所带物品的总重量不得超过背包所带物品的总重量不得超过b b公斤公斤,问他问他应如何选择所带物品，以使总价值最大。应如何选择所带物品，以使总价值最大。物品物品 1 2 j n重量（重量（公斤公斤/件件）a1 a2 aj an每件使用价值每件使用价值 c1 c2 cj cn解：设解：设则背包问题的数学模型如下：则背包问题的数学模型如下：实 例例 某人出国留学打点行李，某人出国留学打点行李，现有三个旅行包，容有三个旅行包，容积大小分大小分别为1000毫升、毫升、1500毫升和毫升和2000毫升，根据需毫升，根据需要列出需要列出需带物品清物品清单，其中必，其中必带物品共有物品

8、共有7件，其体件，其体积大小分大小分别为400、300、150、250、450、760、190（单位毫升）。尚有位毫升）。尚有10件可件可带可不可不带物品，如果物品，如果不不带将在目的地将在目的地购买，通，通过网网络查询可以得知其在目可以得知其在目的地的价格（的地的价格（单位美元）。位美元）。这些物品的容量及价格分些物品的容量及价格分别见下表，下表，试给出一个合理的安排方案把物品放在三出一个合理的安排方案把物品放在三个旅行包里。个旅行包里。物品物品12345678910体积体积200350500430320120700420250100价格价格1545100705075200902030解：解

9、：变量变量设变量为第设变量为第i个物品是否放在第个物品是否放在第j个包裹中个包裹中约束束包裹容量限制包裹容量限制必带物品限制必带物品限制选带物品限制选带物品限制目目标函数函数未未带物品物品购买费用最小用最小模模 型型旅行售货员旅行售货员(货郎担郎担)问题（问题（TSPTSP）20个城市个城市哈密顿图：不重复的走遍所有的点再返回出发点哈密顿图：不重复的走遍所有的点再返回出发点哈密顿图：不重复的走遍所有的点再返回出发点哈密顿图：不重复的走遍所有的点再返回出发点。分析分析变量变量是否从是否从i i 第个城市（出）到第第个城市（出）到第j j个城市（进）个城市（进）约束约束每个城市只能离开一次、到达一

10、次每个城市只能离开一次、到达一次目标目标总费用最小总费用最小数学模型数学模型每座城市恰好出一次每座城市恰好出一次每座城市恰好进一次每座城市恰好进一次直接从直接从vi进入进入vj 其它其它整数线性规划问题数学模型的一般形式：整数线性规划问题数学模型的一般形式：标准形式标准形式 松弛问题：不考虑整数条件，由余下的目标函松弛问题：不考虑整数条件，由余下的目标函数和约束条件构成的规划问题称为该整数规划数和约束条件构成的规划问题称为该整数规划问题的松弛问题问题的松弛问题整数线性规划整数线性规划松弛的线性规划松弛的线性规划整数规划问题的松弛问题整数规划问题的松弛问题（1）整数规划问题的可行解是松弛问题的可

11、行）整数规划问题的可行解是松弛问题的可行解吗？解吗？（2）松弛问题的最优解就是整数规划问题的最）松弛问题的最优解就是整数规划问题的最优解吗？（否）优解吗？（否）（3）松弛问题的最优解经过整化处理后就是整）松弛问题的最优解经过整化处理后就是整数规划问题的最优解吗？数规划问题的最优解吗？整数规划问题的可行解集合是它的松弛整数规划问题的可行解集合是它的松弛问题可行解集合的一个子集问题可行解集合的一个子集,因此因此整数整数规划划问题的可行解一定是它的可行解一定是它的松弛问题的松弛问题的可行的可行解，反之不一定。解，反之不一定。整数规划问题的整数规划问题的最最优值不会不会优于于它松弛它松弛问题问题最最优

12、值。例：设整数规划问题如下例：设整数规划问题如下 首先不考虑整数约束，得到线性规划问题（一般称首先不考虑整数约束，得到线性规划问题（一般称为为松弛问题松弛问题）。）。用图解法求出最优解为：用图解法求出最优解为：x13/2,x2=10/3，且有，且有Z=29/6x1x233(3/2,10/3)现求整数解（最优解）：如用现求整数解（最优解）：如用“舍入取整法舍入取整法”可得到可得到4个点即个点即(1，3)(2，3)(1，4)(2，4)。显然，它。显然，它们都不是整数规划的可行解们都不是整数规划的可行解,因而不因而不是最优解。是最优解。按整数规划约束条件，当按整数规划约束条件，当可行解为有界集时，其

13、可行解可行解为有界集时，其可行解肯定在线性规划问题的可行域肯定在线性规划问题的可行域内且为整数点（格点）。故整内且为整数点（格点）。故整数规划问题的可行解集是一个数规划问题的可行解集是一个有限集，如图所示。有限集，如图所示。因此，可将集合内的整数点一一找出，其因此，可将集合内的整数点一一找出，其最大目标函数的值为最优解，此法为完全枚举最大目标函数的值为最优解，此法为完全枚举法。如上例：其中（法。如上例：其中（2 2，2 2）（）（3 3，1 1）点为最大）点为最大值值点，值值点，Z=4Z=4。1.1.整数规划的最优解不一定在其松弛问题可行整数规划的最优解不一定在其松弛问题可行域的顶点上达到域的顶点上达到.2.2.最优解不一定是松弛问题最优解的邻近整数最优解不一定是松弛问题最优解的邻近整数解解.3.3.整数可行解远多余于顶点，枚举法不可取整数可行解远多余于顶点，枚举法不可取.注意注意:整数规划问题的求解方法：整数规划问题的求解方法：目前，常用的求解整数规划的方法有：目前，常用的求解整数规划的方法有：割平面法、分支定界法和完全枚举法割平面法、分支定界法和完全枚举法