整数规划问题优秀课件.ppt

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第四章 整数规划与分配问题,数学模型,割平面法,分枝定界法,0-1整数规划,分配问题,整数规划,Integer Linear Programming,1,简述,LP,虽然用途广泛，但经常地，客观上要求,L.P.,最优解中不能含有非整数值（如股票的购买之解答），,整数规划就是专门用来求解这类问题的有效工具,重点掌握,：0-1,规划灵活应用、,分枝定界法。,2,提出问题,某厂生产,A1，A2,两种品牌电视，用,B1，B2,两种原料，具体数据如下，求如何安排生产使利润最大,整数规划,3,数学模型,若所有,x,j,的解为整数，称为纯整数规划,pure integer linear programming,若部分,x,j,的解为整数，称为混合整数规划,mixed integer linear programming,若,x,j,只取0或1，成为0-1整数规划,zero-one integer linear programming,松弛问题,整数规划,整数规划的最优解不会优于其松弛问题的最优解,4,注 释,最优解不一定在顶点上达到,最优解不一定是松弛问题最优解的邻近整数解,整数可行解远多于顶点，枚举法不可取,5,整数规划问题的求解方法,分枝定界法,branch and bound method,分枝定界法是一种隐枚举方法（,implicit enumeration）,或部分枚举方法，是枚举方法基础上的改进，几乎所有的计算机计算都用此算法。其关键是分支和定界。,例,Max Z=X,1,+X,2,14X,1,+9X,2,51,-6X,1,+3X,2,1,X,1,，X,2,0,X,1,，X,2,取整数,s.t.,6,分支定界法,思路与解题步骤,只解松弛问题,1、在全部可行域上解松弛问题,若松弛问题最优解为整数解，则其也是整数规划的最优解,2、分枝过程,若松弛问题最优解中某个,x,k,=,b,k,不是整数，令,b,k,为,b,k,的整数部分,构造两个新的约束条件,x,k,b,k,和,x,k,b,k,+1，,分别加于原松弛问题，形成两个新的整数规划,3、求解分枝的松弛问题 定界过程,设两个分枝的松弛问题分别为问题 1 和问题 2，它们的最优解有如下情况,整数规划,7,分支问题解可能出现的情况,情况 2,4,5 找到最优解,情况 3 在缩减的域上继续分枝定界法,情况 6 问题 1 的整数解作为,界,被保留，用于以后与问题 2 的后续分枝所得到的解进行比较，结论如情况 4或5,整数规划,8,分支定界法图解整数规划,松弛问题,Max Z=X,1,+X,2,14X,1,+9X,2,51,-6X,1,+3X,2,1,X,1,，X,2,0,该整数规划松弛问题的解为：,（,X,1,，X,2,）=（,3/2,10/3,）,Z1=29/6,14X,1,+9X,2,51,-6X,1,+3X,2,1,51/14,1/3,9,整数规划,Integer Programming（IP）,分支定界法图解整数规划,松弛问题,Max Z=X,1,+X,2,14X,1,+9X,2,51,-6X,1,+3X,2,1,X,1,，X,2,0,（3/2，10/3）,Z1=29/6,B1 Max Z=X,1,+X,2,14X,1,+9X,2,51,-6X,1,+3X,2,1,X,1,2,X,1,，X,2,0,B2 Max Z=X,1,+X,2,14X,1,+9X,2,51,-6X,1,+3X,2,1,X,1,1,X,1,，X,2,0,B2：,解,（1,7/3,）,Z21=17/3,B1：,解,（2,23/9,）,Z11=41/9,1,2,B1,B2,10,整数规划,Integer Programming（IP）,整数规划问题的求解方法,分支定界法图解整数规划,（3/2,10/3,）,Z1=29/6,B1 Max Z=X,1,+X,2,14X,1,+9X,2,51,-6X,1,+3X,2,1,X,1,2,X,1,，X,2,0,B2：,解,（1,7/3,）,Z21=17/3,B1：,解,（2,23/9,）,Z11=41/9,B11 Max Z=X,1,+X,2,14X,1,+9X,2,51,-6X,1,+3X,2,1,X,1,2,X,2,3,X,1,，X,2,0,B12 Max Z=X,1,+X,2,14X,1,+9X,2,51,-6X,1,+3X,2,1,X,1,2,X,2,2,X,1,，X,2,0,B12：,解,（33/14,2,）,Z12=61/14,1 2,X=2,X=3,11,整数规划,Integer Programming（IP）,整数规划问题的求解方法,分支定界法图解整数规划,（3/2，10/3）,Z1=29/6,B2：,解,（1,7/3,）,Z21=17/3,B12 Max Z=X,1,+X,2,14X,1,+9X,2,51,-6X,1,+3X,2,1,X,1,2,X,2,2,X,1,，X,2,0,B12：,解,（33/14,2,）,Z12=61/14,B121 Max Z=X,1,+X,2,14X,1,+9X,2,51,-6X,1,+3X,2,1,X,1,3,X,2,2,X,1,，X,2,0,B122 Max Z=X,1,+X,2,14X,1,+9X,2,51,-6X,1,+3X,2,1,X,1,2,X,2,2,X,1,，X,2,0,B121：,解,（3，1）,Z121=4,B122：,解,（2，2）,Z122=4,B1：,解,（2，23/9）,Z11=41/9,1 2 3,12,割平面法,cutting plane approach,割平面法求解整数规划问题时，若其松驰问题的最优解,X*,不满足整数要求时，则从,X*,的非整分量中选取一个，用以构造一个线性约束条件（,Gomory,割平面），将其加入原松驰问题中，形成一个新的线性规划，然后求解之。其关键在于新增加的这个线性约束条件将切割掉部分非整数解，至少将当前松驰问题的非整数最优解切割掉了，而,不会切割掉问题的任何整数解,。,13,整数规划,Integer Programming（IP）,整数规划问题的求解方法,割平面法,cutting plane approach,构造切割方程的步骤：,1、令,x,i,是相应松驰问题的最优解中为非整数值的一个基变量，由单纯形表最终表得：,x,i,+a,ik,x,k,=b,i,（1,式）,其中,i Q（Q,指基变量下标集）,k K（K,指非基变量下标集）,14,整数规划,Integer Programming（IP）,整数规划问题的求解方法,割平面法,cutting plane approach,构造切割方程的步骤：,2、将,b,i,和,a,ik,都分解成整数部分,N（,不超过,b,的最大整数）与非负真分数部分,f,之和，即：,b,i,=N,i,+f,i,，,其中 0,f,i,1 （2,式）,a,ik,=N,ik,+f,ik,，,其中 0,f,ik,1,例如：若,b=2.35，,则,N=2，f=0.35；,若,b=-1.45，,则,N=-2，f=0.55,15,整数规划,Integer Programming（IP）,割平面法,cutting plane approach,构造切割方程的步骤：,2、将（2 式）代入（1 式）得：,x,i,+N,ik,x,k,-N,i,=f,i,-f,ik,x,k,（3,式）,3、提出变量为整（当然含非负）的条件：,由于（3 式）中等式左边需整，而 0,f,i,1，,故有,f,i,-f,ik,x,k,0,（4,式）,此即为所需切割方程。,16,整数规划,Integer Programming（IP）,割平面法,cutting plane approach,构造切割方程的步骤：,（1）切割方程,f,i,-f,ik,x,k,0,真正进行了切割，至少把非整数最优解这一点切割掉了。,证明：（反证法）假设松驰问题的最优解,X*,未被切割掉，则由,f,i,-f,ik,x*,k,0，,又因为,x*,k,=0,，（,因,x*,k,为非基变量）,有,f,i,0，,这与,f,i,0,矛盾。,（2）不会切割掉任何整数解，因为切割方程是由变量为整的条件提出的。,17,整数规划,Integer Programming（IP）,割平面法,cutting plane approach,例求解,IP,Max Z=X,1,+X,2,-X,1,+X,2,1,3X,1,+X,2,4,X,1,，X,2,0,X,1,，X,2,整数,LP,Max Z=X,1,+X,2,-X,1,+X,2,1,3X,1,+X,2,4,X,1,，X,2,0,18,1、求解,LP,得到非整数最优解：,X=（3/4，7/4，0，0），Max Z=5/2,求解步骤：,19,整数规划,Integer Programming（IP）,求解步骤,：,2、构造切割方程：,由,B,表,中的第 2 个方程,X,2,+3/4 X,3,+1/4 X,4,=7/4,有,b,2,=7/4=1+3/4,a,23,=3/4=0+3/4，a,24,=1/4=0+1/4,因此，切割方程为,3/4 3/4,X,3,1/4 X,4,0,增加松弛变量,X,5,，,并将如下方程的约束条件添加到,B,表中。,-3,X,3,-1 X,4,+X,5,=-3,X,5,0,20,整数规划,Integer Programming（IP）,求解步骤：,3、求解新的松弛问题,21,0-1整数规划问题,0-1 变量及其应用,0-1变量作为逻辑变量（,Logical variable），,常常被引用来表示系统是否处于某个特定的状态，或者决策变量是否取某个特定的方案。,x,j,=,1 当决策取方案,P,j,时,0 当决策不取方案,P,j,时,22,0-1整数规划,一、项目选定(选址）问题,整数规划,在,经济全球化,的时代，许多公司为在全球范围内,最优地配置资源,（如获取廉价劳动力或原料等），要在不同地方建厂或仓库及其他服务设施，这些都要进行项目或地址的选择。在选址之前，许多侯选地点要进行分析和比较，而每个决策都涉及到一个,选,还是,不选,的问题。,23,案例一,某销售公司打算通过在武汉或长春设立分公司（也许两个城市都设）增加市场份额，管理层同时也计划在新设分公司的城市最多建一个配送中心，当然也可以不建配送中心。经过计算，每种选择对公司收益的净现值、所需费用列在下表中，总预算投资费用不得超过20万。如何决策使总净现值最大,24,设,x,j,=,10,-决策,j,问题的答案是“是”,-决策,j,问题的答案是“否”,max z=18x,1,+10 x,2,+12x,3,+8x,4,12,x,1,+6 x,2,+10 x,3,+,4x,4,20,x,3,+,x,4,1 （,建1个配送中心）,x,3,x,1,x,4,x,2,x,j,=0,或1(,j=1,2,3,4),最优解,x,1,=1，x,2,=1,25,案例练习,例1：某油田在10个有油气构造处要选择若干个钻探采油，设第,j,个构造开采时需投资,a,j,元，投产后预计年收净益为,c,j,元，若该油田投资的总限额为,b,元，问：应选择哪几个构造开采最为有利？,设,x,j,=,10,-选择开采第,j,个构造 -不选择开采第,j,个构造,max z=c,j,x,j,j=1,10,a,j,x,j,b,x,j,0,或1 (,j=1,2,-,10),j=1,10,-年总收益,-投资额限制,1、表示选择性决策,若在开采时还需满足下述条件：,（,a）,若开采8号，则必须同时开采6号；（,b）,若开采5号，则不许开采3号；（,c）2,号和4号至少开采一个；（,d）8,号与7号必须同时开采；（,e）1,号、4号、6号、9号开采时不能超过两个，试表示上述约束条件。,26,设,x,j,=,10,-选择开采第,j,个构造 -不选择开采第,j,个构造,max z=c,j,x,j,j=1,10,a,j,x,j,b,x,j,0,或1 (,j=1,2,-,10),j=1,10,-年总收益,-投资额限制,27,（,a）,当,x,8,=1,x,6,=1，x,6,0,当,x,8,=0,x,6,=1，x,6,=0,x,8,x,6,（,b）,当,x,5,=1,x,3,=0，x,3,1,当,x,5,=0,x,3,=0，x,3,=1,x,5,+x,3,1,（,c）x,2,+x,4,1,（,d）x,8,=x,7,（,e）x,1,+x,4,+x,6,+x,9,2,28,在生产或经营过程中，某一个业务活动开展通常伴随着固定成本的发生，比如添置或起用设备，新采购材料时产生的差旅费，对工人必要培训的费用等，这些构成产品的固定成本。这时，业务活动的总成本就包括与活动数量大小相关的,变动成本,和起动活动的,固定成本,。,二 固定费用（成本）问题,29,案例,某工厂近期接到一批订单，要安排生产甲、乙、丙、丁四种产品，每件产品分别需要原料,A、B、C,中的一种或几种中的若干单位，合同规定要在15天内完成，但数量不限。由于四种产品都在同一种设备上生产，且一台设备同一时间只能加工一件产品。目前，工厂只有一台正使用中的这种设备（设备1），合同期内可挤出3天来生产订单，但会产生150元的机会成本损失；还有一台长期未用的设备（设备2）可以启用，启用时要做必要的检查和修理，费用1000元；公司还考虑向邻厂租用2台（设备3，4），由于对方也在统筹使用，租期分别只能7和12天，租金分别2000和3100，工厂可以决定租一台或两台，也可以一台不租。另外，每种产品如果生产会有固定成本和变动成本，具体如下表，假设每天工作8小时，工厂最多使用3台设备，问：工厂如何生产和利用设备，利润最大,241205696,150100020003100,30,31,例 应用 0-1 变量解决含互斥约束条件问题,设：工序,B,有两种方式完成,方式（1）的工时约束为 0.3,X,1,+0.5X,2,150,方式（2）的工时约束为 0.2,X,1,+0.4X,2,120,问题是完成工序,B,只能从两种方式中任选一种，如何将这两个互斥的约束条件统一在一个线性规划模型中呢？,三 互相排斥问题,32,例 7 应用 0-1 变量解决含互斥约束条件问题,引入 0-1 变量,y,1,=,0 若工序,B,采用方式（1）完成,1 若工序,B,不采用方式（1）完成,y,2,=,0 若工序,B,采用方式（2）完成,1 若工序,B,不采用方式（2）完成,三 互相排斥问题,33,例 7 应用 0-1 变量解决含互斥约束条件问题,于是前面两个互斥的约束条件可以统一为如下三个约束条件：,0.3,X,1,+0.5X,2,150+M,1,y,1,0.2X,1,+0.4X,2,120+M,2,y,2,y,1,+y,2,=1,其中,M,1,，M,2,都是足够大的正数。,三 互相排斥问题,34,案例,因为资金和管理水平的限制，某公司想以相同的价格和不同的租期（工时）租赁另一公司甲、乙、丙、丁四个车间中的,两个,，来生产五种新开发的产品（,A、B、C、D、E）,中的最多,三种,。由于车间的机床和工人的经验不同，生产不同产品的效率也不同，导致不同产品（任一阶段）在不同的车间生产所用的工时数不同（根据生产部的初步实验和经验判断估计出的数据见下表）另外，根据公司市场部的预测，每种产品的单位利润和在租期内最大的销售量以及各车间在租期内的总工时数等也见表）,35,取,M=1000，,得,X1=20，X3=23，X4=2，Z=434,36,0-1整数规划的解法,枚举法,隐枚举法,整数规划,37,指派,(,分配）问题,例：有一份中文产品说明书需译成英、日、德、俄四种语言，现有甲、乙、丙、丁四人都可以胜任，他们译成不同语言所需时间不同，如下表。求如何分配使所需总时间最少（每人只译一种）,整数规划,38,指派问题的标准形式及其数学模型,指派问题的标准形式（以人和事为例）是：,有,n,个人和,n,件事，已知第,i,人做第,j,事的费用为,C,ij,（i，j=1，2，n），,要求确定人和事之间的一一对应的指派方案，使完成这件事的总费用最少。如,指派问题（,assignment problem）,例：有一份中文产品说明书需译成英、日、德、俄四种语言，现有甲、乙、丙、丁四人都可以胜任，他们译成不同语言所需时间不同，如下表。求如何分配使所需总时间最少（每人只译一种）,39,建立模型：,设,x,ij,=,1,0,译英文：,x,11,+x,12,+x,13,+x,14,=1,译日文：,x,21,+x,22,+x,23,+x,24,=1,译德文：,x,31,+x,32,+x,33,+x,34,=1,译俄文：,x,41,+x,42,+x,43,+x,44,=1,甲：,x,11,+x,21,+x,31,+x,41,=1,乙：,x,12,+x,22,+x,32,+x,42,=1,丙：,x,13,+x,23,+x,33,+x,43,=1,丁：,x,14,+x,24,+x,34,+x,44,=1,x,ij,=0,或1 (,i=1,2,3,4;j=1,2,3,4),Min z=,a,ij,x,ij,(a,ij,-,效率),i=1j=1,4 4,若第,i,项工作交与第,j,个人完成,若第,i,项工作不交与第,j,个人完成,40,一般模型,指派问题的标准形式，令,1 当指派第,i,人完成第,j,项任务,0 当不指派第,i,人完成第,j,项任务,x,ij,=,min z=c,ij,x,ij,x,ij,=1，j=1，2，n,x,ij,=1，i=1，2，n,x,ij,=1,或 0,41,匈牙利解法,标准的指派问题是一类特殊的 0-1 整数规划问题，可以用多种相应的解法来求解。但是，这些方法都没有充分利用指派问题的特殊性质来有效减少计算量。1955年，库恩（,W.W.Kuhn）,利用匈牙利数学家康尼格（,D.Knig）,的关于矩阵中独立零元素的定理，提出了指派问题的一种解法，由此，习惯上称之为匈牙利解法。,42,匈牙利解法的关键是利用了指派问题最优解的如下,性质：,若从指派问题的系数矩阵,C=（c,ij,）nn,的某行（或某列）各元素分别,减去一个常数,k,，,得到一个新的系数矩阵,C=（c,ij,）,则以,C,和,C,为系数矩阵的两个指派问题有,相同的最优解,。,匈牙利解法,43,步骤一：变换系数矩阵。使其每行及每列至少有一个零元素，同时不出现负元素。,步骤二：进行试指派，即确定独立零元素。,步骤三：继续变换系数矩阵，然后返回步骤二。,匈牙利解法的一般步骤,44,以上例说明步骤,2 15 13 4,10 4 14 15,9 14 16 13,7 8 11 9,0 13 11 2,6 0 10 11,0 5 7 4,0 1 4 2,2,4,9,7,min,（,c,ij,）=,匈牙利解法的一般步骤,45,指派问题（,assignment problem）,匈牙利解法的一般步骤,以上例说明步骤,0 13 11 2,6 0 10 11,0 4 7 4,0 1 4 2,0 0 4 2,min,0 13 7 0,6 0 6 9,0 5 3 2,0 1 0 0,=（,c,ij,）,指派问题（,assignment problem）,46,以上例说明步骤,0 13 7 0,6 0 6 9,0 5 3 2,0 1 0 0,此时加圈 0 元素的个数,m=n=4，,所以得到最优解,指派问题（,assignment problem）,47,匈牙利解法的一般步骤,以上例说明步骤,0 0 0 1,0 1 0 0,1 0 0 0,0 0 1 0,（,x,ij,）=,指派问题（,assignment problem）,48,匈牙利解法的一般步骤,例,指派问题（,assignment problem）,49,匈牙利解法的一般步骤,12 7 9 7 9,8 9 6 6 6,7 17 12 14 9,15 14 6 6 10,4 10 7 10 9,7,6,7,6,4,5 0 2 0 2,2 3 0 0 0,0 10 5 7 2,9 8 0 0 4,0 6 3 6 5,指派问题（,assignment problem）,50,匈牙利解法的一般步骤,5 0 2 0 2,2 3 0 0 0,0 10 5 7 2,9 8 0 0 4,0 6 3 6 5,此时加圈 0 元素的个数,m=4，,而,n=5，,所以解题没有完成。独立零元素（加圈零元素）少于,n,个，表示还不能确定最优,指派方案。此时需确定能覆盖所有,零元素的最少直线数目的直线集合。方法如下：,指派问题（,assignment problem）,51,匈牙利解法的一般步骤,对没有加圈零元素的行打号；,对所有打号行的所有含零元素的列打号；,再对已打号的列中含零元素的行打号；,重复2）和3），直到再也不能找到可以打号行或列为止；,对没有打号的行画一横线，对打号的列画一竖线，这样就得到,能覆盖所有,零元素的最少直线数目的直线集合。,指派问题（,assignment problem）,52,匈牙利解法的一般步骤,5 0 2 0 2,2 3 0 0 0,0 10 5 7 2,9 8 0 0 4,0 6 3 6 5,指派问题（,assignment problem）,53,匈牙利解法的一般步骤,继续变换系数矩阵。其方法是在未被直线覆盖的元素中找出一个最小元素。然后在打号,行,各元素都,减,去这一最小元素，而在打号,列,的各元素都,加,上这一最小元素，以保证原来的 0 元素不变。这样得到新系数矩阵（其最优解和原问题相同）。若得到,n,个独立的 0 元素，则已得最优解，否则重复该步骤继续变换系数矩阵。,指派问题（,assignment problem）,54,匈牙利解法的一般步骤,5 0 2 0 2,2 3 0 0 0,0 10 5 7 2,9 8 0 0 4,0 6 3 6 5,最小元素=2,7 0 2 0 2,4 3 0 0 0,0 8 3 5 0,11 8 0 0 4,0 4 1 4 3,指派问题（,assignment problem）,55,匈牙利解法的一般步骤,7 0 2 0 2,4 3 0 0 0,0 8 3 5 0,11 8 0 0 4,0 4 1 4 3,此时加圈 0 元素的个数,m=5，,而,n=5，,独立零元素（加圈零元素）等于,n,个，,此时已得到最优解，其解矩阵为,指派问题（,assignment problem）,56,匈牙利解法的一般步骤,（,x,ij,）=,0,1,0 0 0,0 0,1,0 0,0 0 0 0,1,0 0 0,1,0,1,0 0 0 0,最优指派：,甲,B,乙,C,丙,E,丁,D,戊,A,指派问题（,assignment problem）,57,在实际应用中，常会遇到各种非标准形式的制派问题。一般的处理方法是先将其转化为标准形式，然后再用匈牙利法求解。,最大化指派问题,设最大化指派问题系数矩阵,C=（,c,ij,），,其中最大元素为,m。,令矩阵,B=（,b,ij,）=（m-,c,ij,），,则以,B,为系数矩阵的最小化指派问题和以,C,为系数矩阵的最大化指派问题有相同最优解。,人数和事数不等的指派问题,若,人少事多,，则添加一些虚拟的“人”，其费用系数取 0，若,人多事少,，则添加一些虚拟的“事”，其费用系数取 0。,非标准形式的指派问题,58,非标准形式的指派问题,一个人可做几件事的指派问题,若某个人可以做几件事，则将该人化作几个“人”来接受指派。这几个“人”做同一件事的费用系数当然都一样。,某事一定不能由某人做的指派问题,若某事一定不能由某人做，则可将相应的费用系数取为足够大的数,M。,非标准形式的指派问题,59,非标准指派问题,例：分派甲、乙、丙、丁四人完成五项任务，每人完成任务的时间如下表，请就以下要求分别求解分配情况。,1）要求每人只完成一项,2,）甲完成两项，其他人每人完成一项,3,）丁因某种原因不能承担,A,工作，其他每人一项，,E,必须承担任务,整数规划,60,1）要求每人只完成一项,61,2,）甲完成两项，其他人每人完成一项,62,3,）丁因某种原因不能承担,A,工作，其他每人一项，,E,必须承担任务,63,案例练习,红豆服装厂利用三种专用设备生产衬衣，短袖衫和休闲装，已知数据如下表,已知该厂每周可用工量为150单位，可用料量为160单位，生产这三种产品的三种专用设备固定费用分别为2000，1500和1000，要求为该厂作一个周生产计划，使其获利最大？（只建模）,整数规划,64,模型,65,建模练习,1、某公司生产,A、B、C3,种产品，售价分别为12元、7元、6元。生产每件,A,需1,h,技术服务、10,h,直接劳动、3,kg,材料；生产每件,B,需2,h,技术服务、4,h,直接劳动、2,kg,材料；生产每件,C,需1,h,技术服务、5,h,直接劳动、1,kg,材料。现在最多能提供100技术服务、700,h,直接劳动、400,kg,材料。生产成本如下表，求建立一个总利润最大的生产计划数学模型。,66,67,2、如图所示，有4个用户，每年需求量分别为,D,1,、D,2、,D,3,、D,4,，,拟在3个允许最大容量为,A,1,、A,2,、A,3,的备选地点建立两处仓库，箭头指向为若在该处建仓库后可供应的用户，,Cij,为从,i,仓库至,j,用户单位物资调运费，设三处仓库的建设投资分别为,K,1,、K,2,、K,3,，,投资均匀分摊到10年回收，不计利息。单位物资在各仓库周转保管费分别为,P,1,、P,2、,P,3,。,问应选哪两处仓库，使每年各项费用和最少。（建模）,D,2,A,1,A,2,A,3,D,3,D,1,D,4,68,69,