《混合整数线性规划培训讲学.ppt》由会员分享，可在线阅读，更多相关《混合整数线性规划培训讲学.ppt（50页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、混合整数线性规划 设：设：xj 表示用表示用Bj(j=1.2n)种方式下料根数种方式下料根数 模型：模型：例二、例二、某公司计划在某公司计划在m个地点建厂，可供选择的地点有个地点建厂，可供选择的地点有A1,A2Am，他们的生产能力分别是他们的生产能力分别是a1,a2,am（假设生（假设生产同一产品）。第产同一产品）。第i i个工厂的建设费用为个工厂的建设费用为fi(i=1.2m),又有又有n个地点个地点B1,B2,Bn 需要销售这种产品，其销量分需要销售这种产品，其销量分别为别为b1.b2bn。从工厂运往销地的单位运费为。从工厂运往销地的单位运费为Cij。试。试决定应在哪些地方建厂，即满足各地
2、需要，又使总建决定应在哪些地方建厂，即满足各地需要，又使总建设费用和总运输费用最省？设费用和总运输费用最省？单 销地厂址 价生产能力建设费用销量 设：设：xij 表示从工厂运往销地的运量表示从工厂运往销地的运量(i=1.2m、j=1.2n),1),1 在在Ai建厂建厂 又设又设 Yi （i=1.2m）0 0 不在不在Ai建厂建厂 模型：模型：（二）、整数规划的数学模型（二）、整数规划的数学模型一般形式一般形式 依照决策变量取整要求的不同，整数规划可分为纯整依照决策变量取整要求的不同，整数规划可分为纯整数线性规划、混合整数线性规划、数线性规划、混合整数线性规划、0 01 1整数线性规划。整数线性
3、规划。纯整数线性规划：纯整数线性规划：所有决策变量要求取非所有决策变量要求取非负整数。负整数。混合整数规划：混合整数规划：只有一部分的决策变量要只有一部分的决策变量要求取非负整数，另一部分可以取非负实数。求取非负整数，另一部分可以取非负实数。01整数规划：整数规划：所有决策变量只能取所有决策变量只能取 0 或或 1 两个整数两个整数。（三）、整数规划与线性规划的关系（三）、整数规划与线性规划的关系 从数学模型上看整数规划似乎是线从数学模型上看整数规划似乎是线性规划的一种特殊形式，求解只需在线性规划的一种特殊形式，求解只需在线性规划的基础上，通过舍入取整，寻求性规划的基础上，通过舍入取整，寻求满
4、足整数要求的解即可。但实际上两者满足整数要求的解即可。但实际上两者却有很大的不同，通过舍入得到的解却有很大的不同，通过舍入得到的解（整数）也不一定就是最优解，有时甚（整数）也不一定就是最优解，有时甚至不能保证所得到的解是整数可行解。至不能保证所得到的解是整数可行解。举例说明。举例说明。例：设整数规划问题如下例：设整数规划问题如下 首先不考虑整数约束，得到线性规划问题（一般称首先不考虑整数约束，得到线性规划问题（一般称为松弛问题）。为松弛问题）。用用 解法求出最优解解法求出最优解x13/2,x2=10/3且有且有Z=29/6x1x233(3/2,10/3)现求整数解（最优解）：现求整数解（最优解
5、）：如用如用“舍入取整法舍入取整法”可得可得到到4个点即个点即(1，3)(2，3)(1，4)(2，4)。显然，它。显然，它们都不可能是整数规划的们都不可能是整数规划的最优解。最优解。按整数规划约束条件，其可行解肯定在线性规划问题按整数规划约束条件，其可行解肯定在线性规划问题的可行域内且为整数点。故整数规划问题的可行解集的可行域内且为整数点。故整数规划问题的可行解集是一个有限集，如图所示。是一个有限集，如图所示。图图 因此，可将集合内的整数点一一找出，其最因此，可将集合内的整数点一一找出，其最大目标函数的值为最优解，此法为完全枚举法。大目标函数的值为最优解，此法为完全枚举法。如上例：其中如上例：
6、其中（2，2）（）（3，1）点为最点为最大值，大值，Z=4。目前，常用的求解整数规划的方法有：目前，常用的求解整数规划的方法有：割平面法和分支定界法；割平面法和分支定界法；对于特别的对于特别的0 01 1规划问题采用隐枚举法和匈规划问题采用隐枚举法和匈牙利法。牙利法。（一）、基本思路（一）、基本思路 考虑纯整数问题：考虑纯整数问题：整数问题的松弛问题：整数问题的松弛问题：二、分支定界法二、分支定界法 1、先不考虑整数约束，解、先不考虑整数约束，解(IP)的松弛问题的松弛问题(LP)，可能得到以下情况之一：可能得到以下情况之一：.若若(LP)没有可行解，则没有可行解，则(IP)也没有可行解，停止
7、也没有可行解，停止计算。计算。.若若(LP)有最优解，并符合有最优解，并符合(IP)的整数条件，则的整数条件，则(LP)的最优解即为的最优解即为(IP)的最优解，停止计算。的最优解，停止计算。.若若(LP)有最优解，但不符合有最优解，但不符合(IP)的整数条件，转的整数条件，转入下一步。为讨论方便，设入下一步。为讨论方便，设(LP)的最优解为：的最优解为：2、定界：、定界：记记(IP)的目标函数最优值为的目标函数最优值为Z*,以以Z(0)作为作为Z*的上界，的上界，记为记为 Z(0)。再用观察法找的一个整数可行解。再用观察法找的一个整数可行解 X，并以其相应的目标函数值并以其相应的目标函数值
8、Z作为作为Z*的下界，记为的下界，记为Z Z，也可以令，也可以令Z，则有：，则有：Z Z*3、分枝：分枝：在在(LP)的最优解的最优解 X(0)中，任选一个不符合整数条件中，任选一个不符合整数条件的变量，例如的变量，例如xr=（不为整数），以（不为整数），以 表示不超过表示不超过 的最大整数。构造两个约束条件的最大整数。构造两个约束条件 xr 和和xr 1 1如此反复进行，直到得到如此反复进行，直到得到ZZ*为止，即得最优解为止，即得最优解 X*。将这两个约束条件分别加入问题将这两个约束条件分别加入问题(IP)，形成两个子，形成两个子问题问题(IP1)和和(IP2)，再解这两个问题的松弛问题，
9、再解这两个问题的松弛问题(LP1)和和(LP2)。4、修改上、下界：按照以下两点规则进行。修改上、下界：按照以下两点规则进行。.在各分枝问题中，找出目标函数值最大者作为在各分枝问题中，找出目标函数值最大者作为新的上界；新的上界；.从已符合整数条件的分枝中，找出目标函数值从已符合整数条件的分枝中，找出目标函数值最大者作为新的下界。最大者作为新的下界。5、比较与剪枝比较与剪枝：各分枝的目标函数值中，若有小于各分枝的目标函数值中，若有小于Z 者，则剪掉此者，则剪掉此枝，表明此子问题已经探清，不必再分枝了枝，表明此子问题已经探清，不必再分枝了;否则继续否则继续分枝。分枝。例一：用分枝定界法求解整数规划
10、问题（用图解法计算）例一：用分枝定界法求解整数规划问题（用图解法计算）记为（记为（IP）解：首先去掉整数约束，变成一般线性规划问题解：首先去掉整数约束，变成一般线性规划问题记为（记为（LP）（二）、例题（二）、例题用图解法求用图解法求（LP）的最的最优解，如图所示。优解，如图所示。x1x233(18/11,40/11)对于对于x118/111.64，取值取值x1 1，x1 2对于对于x2=40/11 3.64，取值取值x2 3，x2 4先将先将（LP）划分为（）划分为（LP1）和（）和（LP2）,取取x1 1,x1 2 x118/11,x2=40/11 Z(0)=218/11(19.8)即即Z
11、 也是也是（IP）最小值的下最小值的下限。限。有下式：有下式：现在只要求出（现在只要求出（LP1）和（）和（LP2）的最优解即可。）的最优解即可。x1x233(18/11,40/11)先求先求（LP1）,如图所示。如图所示。此时此时B 在点取得最优解。在点取得最优解。x11,x2=3,Z(1)16找到整数解，问题已探找到整数解，问题已探明，此枝停止计算。明，此枝停止计算。11同理求同理求（LP2）,如图所示。如图所示。在在C 点取得最优解。点取得最优解。即即x12,x2=10/3,Z(2)56/318.7 Z2 Z116 原问题有比原问题有比（16）更小的最优解，但）更小的最优解，但 x2 不
12、是整数，故利用不是整数，故利用 x23,x24 加入条件。加入条件。BAC加入条件：加入条件：x23,x24 有下式：有下式：只要求出（只要求出（LP3）和（）和（LP4）的最优解即可。）的最优解即可。x1x233(18/11,40/11)11BAC先求先求（LP3）,如图所示。如图所示。此时此时D 在点取得最优解。在点取得最优解。即即 x112/52.4,x2=3,Z(3)-87/5-17.4 Z(5)F 如对如对 Z(6)继续分解，其最小值也不会低于继续分解，其最小值也不会低于15.5 ，问题探明问题探明,剪枝。剪枝。至此，原问至此，原问题（题（IP）的最优）的最优解为：解为：x1=2，x
13、2=3,Z*=Z(5)17以上的求解过程以上的求解过程可以用一个树形可以用一个树形图表示如右：图表示如右：LP1x1=1,x2=3Z(1)16LPx1=18/11,x2=40/11Z(0)19.8LP2x1=2,x2=10/3Z(2)18.5LP3x1=12/5,x2=3Z(3)17.4LP4无可无可行解行解LP5x1=2,x2=3Z(5)17LP6x1=3,x2=5/2Z(6)15.5x11x12x23x24x12x13 01 整数规划是一种特殊形式的整数规划，这时的整数规划是一种特殊形式的整数规划，这时的决策变量决策变量xi 只取两个值只取两个值0或或1，一般的解法为隐枚举法。，一般的解法
14、为隐枚举法。例一、求解下列例一、求解下列01 规划问题规划问题三、三、0 01 1 整数规划整数规划 解：对于解：对于01 规划问题，由于每个变量只取规划问题，由于每个变量只取0，1两个两个值，一般会用穷举法来解，即将所有的值，一般会用穷举法来解，即将所有的0，1 组合找出，组合找出，使目标函数达到极值要求就可求得最优解。但此法太使目标函数达到极值要求就可求得最优解。但此法太繁琐，工作量相当大。而隐枚举法就是在此基础上，繁琐，工作量相当大。而隐枚举法就是在此基础上，通过加入一定的条件，就能较快的求得最优解。通过加入一定的条件，就能较快的求得最优解。x1.x2.x3约束条件约束条件满足条件满足条
15、件Z 值值 (1)(2)(3)(4)是是 否否(0.0.0 )0 0 0 00(0.0.1)1 1 0 15(0.1.0)2 4 1 42(1.0.0)1 1 1 03(0.1.1)1 5(1.0.1)0 2 1 18(1.1.0)3(1.1.1)2 6 由上表可知，问题的最优解为由上表可知，问题的最优解为 X*=(x1=1 x2=0 x3=1)由上表可知：由上表可知：x1=0 x2=0 x3=1 是一个可行解，为尽快是一个可行解，为尽快找到最优解，可将找到最优解，可将3 x12 x25 x3 5 作为一个约束，作为一个约束，凡是目标函数值小于凡是目标函数值小于5 的组合不必讨论，如下表。的组
16、合不必讨论，如下表。x1.x2.x3约束条件约束条件满足条件满足条件Z 值值(0)(1)(2)(3)(4)是是 否否(0.0.0 )0 0 0 0 00(0.0.1)5 1 1 0 15(0.1.0)-2(0.1.1)3(1.0.0)3(1.0.1)8 0 2 1 18(1.1.0)1(1.1.1)4 例二、求解下列例二、求解下列01 规划问题规划问题 解：由于目标函数中变量解：由于目标函数中变量x1,x2,x4 的系数均为负数，可的系数均为负数，可作如下变换：作如下变换：令令 x1 1 x1,x2=1-x2,x3=x3,x4=1-x4带入原题带入原题中，但需重新调整变量编号。令中，但需重新调
17、整变量编号。令 x3=x1,x4=x2得到下式。得到下式。可以从可以从(1.1.1.1)开始试算，开始试算，x(3)(1.1.0.1)最优解。最优解。x(3)(1.0.1.0)是原问题的最优解，是原问题的最优解，Z*=2例三、求解下列例三、求解下列01 规划问题规划问题令令 y1=x5,y2=x4,y3=x2,y4=x3,y5=x1 得到下式得到下式y1.y2.y3.y4.y5约束条件约束条件满足条件满足条件Z 值值 (1)(2)是是 否否(0.0.0.0.0 )0 0(1.0.0.0.0)1 -1(0.1.0.0.0)-1 1(0.0.1.0.0)-2 1(0.0.0.1.0)4 -48(0
18、.0.0.0.1)3 -2 所以，所以，Y*=（0.0.0.1.0），原问题的最优解为：），原问题的最优解为：X*（0.0.1.0.0），），Z*=8（0.1.1.0.0）练习：用隐枚举法求解练习：用隐枚举法求解0 01 1规划问题规划问题 在实际中经常会遇到这样的问题，有在实际中经常会遇到这样的问题，有n 项不同的任务，项不同的任务，需要需要n 个人分别完成其中的一项，但由于任务的性质和个人分别完成其中的一项，但由于任务的性质和各人的专长不同，因此各人去完成不同的任务的效率各人的专长不同，因此各人去完成不同的任务的效率（或花费的时间或费用）也就不同。于是产生了一个（或花费的时间或费用）也就不
19、同。于是产生了一个问题，应指派哪个人去完成哪项任务，使完成问题，应指派哪个人去完成哪项任务，使完成 n 项任项任务的总效率最高（或所需时间最少），这类问题称为务的总效率最高（或所需时间最少），这类问题称为指派问题或分派问题。指派问题或分派问题。（一）、指派问题的数学模型（一）、指派问题的数学模型 设设n 个人被分配去做个人被分配去做n 件工作，规定每个人只做一件件工作，规定每个人只做一件工作，每件工作只有一个人去做。已知第工作，每件工作只有一个人去做。已知第i个人去做第个人去做第j 件工作的的效率（件工作的的效率（时间或费用）为时间或费用）为Cij(i=1.2n;j=1.2n)并假设并假设Ci
20、j 0。问应如何分配才。问应如何分配才能使总效率（能使总效率（时间或费用）最高？时间或费用）最高？四、指派问题四、指派问题设决策变量设决策变量 1 分配第分配第i 个人去做第个人去做第j 件工作件工作 xij=0 相反相反 (I,j=1.2.n)其数学模型为：其数学模型为：（二）、解题步骤：（二）、解题步骤：指派问题是指派问题是0-1 规划的特例，当然可用整数规划，规划的特例，当然可用整数规划，0-1 规划的解法去求解，但是利用指派问题的特点可规划的解法去求解，但是利用指派问题的特点可有更简便的解法，这就是匈牙利法。有更简便的解法，这就是匈牙利法。第第一一步步：变变换换指指派派问问题题的的系系
21、数数矩矩阵阵（cij）为为(bij)，使使在在(bij)的各行各列中都出现的各行各列中都出现0元素，即元素，即 (1)从（从（cij）的每行元素都减去该行的最小元素；）的每行元素都减去该行的最小元素；(2)再再从从所所得得新新系系数数矩矩阵阵的的每每列列元元素素中中减减去去该该列列的的最最小元素。小元素。第二步：进行试指派，以寻求最优解。第二步：进行试指派，以寻求最优解。在在(bij)中中找找尽尽可可能能多多的的独独立立0元元素素，若若能能找找出出n个个独独立立0元元素素，就就以以这这n个个独独立立0元元素素对对应应解解矩矩阵阵(xij)中中的的元元素素为为1，其其余余为为0，这这就就得得到到
22、最最优优解解。找找独独立立0元元素素，常常用的步骤为：用的步骤为：(1)从从只只有有一一个个0元元素素的的行行(列列)开开始始，给给这这个个0元元素素加加圈圈，记记作作。然然后后划划去去 所所在在列列(行行)的的其其它它0元元素素，记记作作；这这表表示示这这列列所所代代表表的的任任务务已已指指派派完完，不不必必再再考考虑别人了。虑别人了。(2)给给只只有有一一个个0元元素素的的列列(行行)中中的的0元元素素加加圈圈，记记作作；然后划去；然后划去 所在行的所在行的0元素，记作元素，记作 (3)反反复复进进行行(1)，(2)两两步步，直直到到尽尽可可能能多多的的0元元素素都都被圈出和划掉为止。被圈
23、出和划掉为止。(4)若若仍仍有有没没有有划划圈圈的的0元元素素，且且同同行行(列列)的的0元元素素至至少少有有两两个个，则则从从剩剩有有0元元素素最最少少的的行行(列列)开开始始，比比较较这这行行各各0元元素素所所在在列列中中0元元素素的的数数目目，选选择择0元元素素少少的的那那列列的的这这个个0元元素素加加圈圈(表表示示选选择择性性多多的的要要“礼礼让让”选选择择性性少少的的)。然然后后划划掉掉同同行行同同列列的的其其它它0元元素素。可可反反复复进进行行，直直到所有到所有0元素都已圈出和划掉为止。元素都已圈出和划掉为止。（5）若）若 元素的数目元素的数目m 等于矩阵的阶数等于矩阵的阶数n，那
24、么这指，那么这指派问题的最优解已得到。若派问题的最优解已得到。若m n,则转入下一步。则转入下一步。第三步：作最少的直线覆盖所有第三步：作最少的直线覆盖所有0元素。元素。(1)对没有对没有的行打的行打号；号；(2)对已打对已打号的行中所有含号的行中所有含元素的列打元素的列打号；号；(3)再对打有再对打有号的列中含号的列中含 元素的行打元素的行打号；号；(4)重复重复(2)，(3)直到得不出新的打直到得不出新的打号的行、列为止；号的行、列为止；(5)对对没没有有打打号号的的行行画画横横线线，有有打打号号的的列列画画纵纵线线，这这就就得得到到覆覆盖盖所所有有0元元素素的的最最少少直直线线数数 l。
25、l 应应等等于于m，若若不不相相等等，说说明明试试指指派派过过程程有有误误，回回到到第第二二步步(4)，另另行行试试指指派派；若若 lm n，须须再再变变换换当当前前的的系系数数矩矩阵阵，以以找到找到n个独立的个独立的0元素，为此转第四步。元素，为此转第四步。例一：例一：任务任务人员人员ABCD甲甲215134乙乙1041415丙丙9141613丁丁78119249742第四步：变换矩阵第四步：变换矩阵(bij)以增加以增加0元素。元素。在没有被直线覆盖的所有元素中找出最小元素，然后在没有被直线覆盖的所有元素中找出最小元素，然后打打各行都减去这最小元素；打各行都减去这最小元素；打各列都加上这最
26、小元各列都加上这最小元素（以保证系数矩阵中不出现负元素）。新系数矩阵素（以保证系数矩阵中不出现负元素）。新系数矩阵的最优解和原问题仍相同。转回第二步。的最优解和原问题仍相同。转回第二步。有一份中文说明书，需译成英、日、德、俄四种有一份中文说明书，需译成英、日、德、俄四种文字，分别记作文字，分别记作A、B、C、D。现有甲、乙、丙、丁四。现有甲、乙、丙、丁四人，他们将中文说明书译成不同语种的说明书所需时人，他们将中文说明书译成不同语种的说明书所需时间如下表所示，问如何分派任务，可使总时间最少？间如下表所示，问如何分派任务，可使总时间最少？任务任务人员人员ABCD甲甲67112乙乙4598丙丙311
27、04丁丁5982例二、例二、求解过程如下：求解过程如下：第一步，变换系数矩阵：第一步，变换系数矩阵：5第二步，试指派：第二步，试指派：找到找到 3 3 个独立零元素个独立零元素 但但 m m=3 3 n=4 第三步，作最少的直线覆盖所有第三步，作最少的直线覆盖所有0 0元素：元素：独立零元素的个数独立零元素的个数m等于最少直线数等于最少直线数l，即，即lm=3n=4；第四步，变换矩阵第四步，变换矩阵(bij)以增加以增加0 0元素：没有被直线覆元素：没有被直线覆盖的所有元素中的最小元素为盖的所有元素中的最小元素为1 1，然后打，然后打各行都减去各行都减去1 1；打；打各列都加上各列都加上1 1
28、，得如下矩阵，并转第二步进行，得如下矩阵，并转第二步进行试指派：试指派：000 0 00得到得到4 4个独个独立零元素，立零元素，所以最优解所以最优解矩阵为：矩阵为：15练习：用分枝定界法求解整数规划问题练习：用分枝定界法求解整数规划问题 （图解法）（图解法）LP1x1=1,x2=7/3Z(1)10/3LPx1=3/2,x2=10/3Z(0)29/6LP2x1=2,x2=23/9Z(2)41/9x11x12LP5x1=1,x2=2Z(5)3LP6无可无可行解行解x22x23LP3x1=33/14,x2=2Z(3)61/14LP4无可无可行解行解x22x23LP7x1=2,x2=2Z(7)4LP8x1=3,x2=1Z(8)4x12x13LP1x1=1,x2=7/3Z(1)10/3LPx1=2/3,x2=10/3Z(0)29/6LP2x1=2,x2=23/9Z(2)41/9LP3x1=33/14,x2=2Z(3)61/14LP4无可无可行解行解LP7x1=2,x2=2Z(7)4LP8x1=3,x2=1Z(8)4x11x12x22x23x12x13此课件下载可自行编辑修改，仅供参考！此课件下载可自行编辑修改，仅供参考！感谢您的支持，我们努力做得更好！谢谢感谢您的支持，我们努力做得更好！谢谢