运筹学08-整数规划

null第八章 整数 规划 污水管网监理规划下载职业规划大学生职业规划个人职业规划职业规划论文 第八章 整数规划8.1 整数规划问题及其数学模型 8.2 分支定界法 8.3 割平面法 8.4 0-1整数规划 8.5 指派问题 8.1 整数规划问题及其数学模型8.1 整数规划问题及其数学模型一、整数规划问题的特征 变量取值范围是离散的，经典连续数学中的理论和方法一般无法直接用来求解整数规划问题。 例 某公司 计划 项目进度计划表范例计划下载计划下载计划下载课程教学计划下载 在m个地点建厂，可供选择的地点有A1,A2…Am ，他们的生产能力分别是a1,a2,…am（假设生产同一产品）。第i个工厂的建设费用为fi (i=1.2…m),又有n个地点B1,B2, … Bn 需要销售这种产品，其销量分别为b1.b2…bn 。从工厂运往销地的单位运费为Cij。试决定应在哪些地方建厂，即满足各地需要，又使总建设费用和总运输费用最省？nullnull二、整数规划的数学模型 纯整数规划：所有决策变量为非负整数； 全整数规划：所有变量、系数和常数均为整数； 混合整数规划：只有一部分决策变量为非负整数，其余变量可为非负实数； 0-1整数规划：所有决策变量只能取0获1两个整数。null三、整数规划与线性规划的关系 从数学模型上看整数规划似乎是线性规划的一种特殊形式，求解只需在线性规划的基础上，通过舍入取整，寻求满足整数要求的解即可。但实际上两者却有很大的不同，通过舍入得到的解（整数）也不一定就是最优解，有时甚至不能保证所得倒的解是整数可行解。 目前，常用的求解整数规划的方法有： 分支定界法和割平面法； 对于特别的0－1规划问题采用隐枚举法和匈牙利法。null例：设整数规划问题如下 首先不考虑整数约束，得到线性规划问题（一般称为松弛问题）。null用图解法求出最优解 x1＝3/2, x2 = 10/3 且有z = 29/6x1x2⑴⑵33(3/2,10/3)现求整数解（最优解）：如用“舍入取整法”可得到4个点，即 (1，3) (2，3) (1，4) (2，4)。显然，它们都不可能是整数规划的最优解。按整数规划约束条件，其可行解肯定在线性规划问题的可行域内且为整数点。故整数规划问题的可行解集是一个有限集，如图所示。因此，可将集合内的整数点一一找出，其最大目标函数的值为最优解，此法为完全枚举法。 8.2 分支定界法 基本思路 null 1、先不考虑整数约束，解( IP )的松弛问题( LP )，可能得到以下情况之一： ⑴.若( LP )没有可行解，则( IP )也没有可行解，停止计算。 ⑵.若( LP )有最优解，并符合( IP )的整数条件，则( LP )的最优解即为( IP )的最优解，停止计算。 ⑶.若( LP )有最优解，但不符合( IP )的整数条件，转入下一步。 为讨论方便，设( LP )的最优解为： null2、定界： 记( IP )的目标函数最优值为Z* ,以Z(0) 作为Z* 的上界，记为 ＝ Z(0) 。再用观察法找的一个整数可行解 X′，并以其相应的目标函数值 Z′作为Z* 的下界，记为Z＝ Z′，也可以令Z＝－∞，则有： Z ≤ Z* ≤3、分枝： 在( LP )的最优解 X(0)中，任选一个不符合整数条件的变量，例如xr= （不为整数），以 表示不超过 的最大整数。构造两个约束条件 xr≤ 和 xr ≥ ＋1null如此反复进行，直到得到 Z ＝ Z* ＝ 为止，即得最优解X* 。 将这两个约束条件分别加入问题( IP ) ，形成两个子问题( IP1)和( IP2 ) ，再解这两个问题的松弛问题( LP1)和( LP2) 。4、修改上、下界：按照以下两点规则进行。 ⑴.在各分枝问题中，找出目标函数值最大者作为新的上界； ⑵.从已符合整数条件的分枝中，找出目标函数值最大者作为新的下界。5、比较与剪枝 ： 各分枝的目标函数值中，若有小于Z 者，则剪掉此枝，表明此子问题已经探清，不必再分枝了;否则继续分枝。 null分支定界法是一种隐枚举方法（implicit enumeration）或部分枚举方法，它不是一种有效的算法，是枚举方法基础上的改进。其关键是分支和定界。 例—— Max Z = X1 + X2 14X1 + 9X2 ≤ 51 - 6X1 + 3X2 ≤ 1 X1 ， X2 ≥ 0 X1 ， X2 取整数s.t.null分支定界法图解整数规划松弛问题 Max Z = X1 + X2 14X1 + 9X2 ≤ 51 - 6X1 + 3X2 ≤ 1 X1 ， X2 ≥ 0该整数规划松弛问题的解为： （X1 ，X2 ）= （3/2 ，10/3） Z0 = 29/6null松弛问题 Max Z = X1 + X2 14X1 + 9X2 ≤ 51 - 6X1 + 3X2 ≤ 1 X1 ， X2 ≥ 0（3/2 ，10/3） Z0 = 29/6LP1 Max Z = X1 + X2 14X1 + 9X2 ≤ 51 - 6X1 + 3X2 ≤ 1 X1 ≥ 2 X1 ， X2 ≥ 0LP2 Max Z = X1 + X2 14X1 + 9X2 ≤ 51 - 6X1 + 3X2 ≤ 1 X1 ≤ 1 X1 ， X2 ≥ 0LP2：解 （1，7/3 ）Z2 = 10/3LP1：解 （2，23/9 ） Z1 = 41/9null（3/2 ，10/3） Z0 = 29/6LP1 Max Z = X1 + X2 14X1 + 9X2 ≤ 51 - 6X1 + 3X2 ≤ 1 X1 ≥ 2 X1 ， X2 ≥ 0LP2：解 （1，7/3 ） Z2 = 10/3LP1：解 （2，23/9 ） Z1 = 41/9LP11 Max Z = X1 + X2 14X1 + 9X2 ≤ 51 - 6X1 + 3X2 ≤ 1 X1 ≥ 2 X2 ≥ 3 X1 ， X2 ≥ 0LP12 Max Z = X1 + X2 14X1 + 9X2 ≤ 51 - 6X1 + 3X2 ≤ 1 X1 ≥ 2 X2 ≤ 2 X1 ， X2 ≥ 0LP12：解 （33/14，2 ） Z12 = 61/14null（3/2 ，10/3） Z0 = 29/6LP2：解 （1，7/3 ） Z2 = 10/3LP12 Max Z = X1 + X2 14X1 + 9X2 ≤ 51 - 6X1 + 3X2 ≤ 1 X1 ≥ 2 X2 ≤ 2 X1 ， X2 ≥ 0LP12：解 （33/14，2 ） Z12 = 61/14LP121 Max Z = X1 + X2 14X1 + 9X2 ≤ 51 - 6X1 + 3X2 ≤ 1 X1 ≥ 3 X2 ≤ 2 X1 ， X2 ≥ 0LP122 Max Z = X1 + X2 14X1 + 9X2 ≤ 51 - 6X1 + 3X2 ≤ 1 X1 ≤ 2 X2 ≤ 2 X1 ， X2 ≥ 0LP121：解 （3，1 ） Z121 = 4LP122：解 （2，2 ） Z122 = 4LP1：解 （2，23/9 ） Z1 = 41/9null#####分支搜索法流程null#分支定界法流程例 用分支定界法求解整数规划问题（单纯形法） 解:用单纯形法解对应的(LP)问题,如表所示,获得最优解。初始表最终表例 用分支定界法求解整数规划问题（单纯形法） null x1=13/4 x2=5/2 Z(0) =59/4≈14.75 选 x2 进行分枝，即增加两个约束，2 ≥ x2 ≥3 有下式： 分别在(LP1)和(LP2)中引入松弛变量x5和x6 ，将新加约束条件加入上表计算。即 x2+ x5= 2 , －x2+x6=－3 得下表:nullx1=7/2, x2=2 Z(1) =14.5 继续分枝，加入约束 3≥ x1 ≥4LP1nullLP2x1=5/2, x2=3 Z(2) =13.5 ∵ Z(2) < Z(1) ∴先不考虑分枝null接(LP1)继续分枝，加入约束 4 ≤ x1≤ 3，有下式：分别引入松弛变量x7 和 x8 ，然后进行计算。nullx1=3, x2=2 Z(3) =13 找到整数解，问题已探明，停止计算。LP3nullx1=4 x2=1 Z(4) =14 找到整数解，问题已探明，停止计算。LP4null树形图如下：LP1 x1=7/2, x2=2 Z(1)＝29/2=14.5LP x1=13/4, x2=5/2 Z(0) ＝59/4=14.75LP2 x1=5/2, x2=3 Z(2)＝27/2=13.5LP3 x1=3, x2=2 Z(3) ＝13LP4 x1=4, x2=1 Z(4) ＝14x2≤2x2≥3x1≤3x1≥4###8.3 割平面法8.3 割平面法null二、计算步骤 1、用单纯形法求解( IP )对应的松弛问题( LP )： ⑴.若( LP )没有可行解，则( IP )也没有可行解，停止计算。 ⑵.若( LP )有最优解，并符合( IP )的整数条件，则( LP )的最优解即为( IP )的最优解，停止计算。 ⑶.若( LP )有最优解，但不符合( IP )的整数条件，转入下一步。 null3、将所得的割平面方程作为一个新的约束条件置于最优单纯形表中（同时增加一个单位列向量），用对偶单纯形法求出新的最优解，返回1。null例：用割平面法求解整数规划问题解：增加松弛变量x3和x4 ，得到(LP)的初始单纯形表和最优单纯形表：null此题的最优解为：X＊ (1 , 3/2) Z = 3/2 但不是整数最优解，引入割平面。以x2 为源行生成割平面，由于 1/4=0+1/4, 3/2=1+1/2, 我们已将所需要的数分解为整数和分数，所以，生成割平面的条件为: 也即：nullnull现将生成的割平面条件加入松弛变量，然后加到表中：null用上表的约束解出x4 和s1 ，将它们带入上式得到等价的割平面条件：x1 ≥ x2 ，见图：null将生成的割平面条件加入松弛变量，然后加到表中：null 至此得到最优表，其最优解为 X＊= (1 , 1) , Z = 1, 这也是原问题的最优解。 有以上解题过程可见，表中含有分数元素且算法过程中始终保持对偶可行性，因此，这个算法也称为分数对偶割平面算法。null例：用割平面法求解数规划问题初 始 表最优表null在松弛问题最优解中，x1, x2 均为非整数解，由上表有：将系数和常数都分解成整数和非负真分数之和 null以上式子只须考虑一个即可，解题经验表明，考虑式子右端最大真分数的式子，往往会较快地找到所需割平面约束条件。以上两个式子右端真分数相等，可任选一个考虑。现选第二个式子，并将真分数移到右边得： 引入松弛变量s1 后得到下式，将此约束条件加到上表中，继续求解。 null﹡得到整数最优解，即为整数规划的最优解，而且此整数规划有两个最优解： X＊= (0, 4), Z = 4, 或 X＊= (2, 2), Z = 4。 8.4 0-1整数规划8.4 0-1整数规划null例 求解下列0－1 规划问题null解：对于0－1 规划问题，由于每个变量只取0，1两个值，一般会用穷举法来解，即将所有的0，1 组合找出，使目标函数达到极值要求就可求得最优解。但此法太繁琐，工作量相当大。而隐枚举法就是在此基础上，通过加入一定的条件，就能较快的求得最优解。null由上表可知，问题的最优解为 X*=( x1 =1 x2=0 x3=1 ) 由上表可知： x1 =0 x2=0 x3=1 是一个可行解，为尽快找到最优解，可将3 x1－2 x2＋5 x3 ≥5 作为一个约束，凡是目标函数值小于5 的组合不必讨论，如下表。null以下讨论一般形式的0－1规划如何化为 标准 excel标准偏差excel标准偏差函数exl标准差函数国标检验抽样标准表免费下载红头文件格式标准下载 形式：null例 求解下列0－1 规划问题解：令 y1=x5, y2=x4, y3=x2, y4=x3, y5=x1 得到下式null所以， Y*= （0.0.0.1.0），原问题的最优解为： X* ＝（0.0.1.0.0），Z* =8null例 求解下列0－1 规划问题解：由于目标函数中变量x1, x2 , x4 的系数均为负数，可作如下变换： 令 x1 ＝1－ x1′ , x2 =1- x2′, x3= x3′, x4 =1- x4′带入原题中，但需重新调整变量编号。令 x3′ = x1′, x4′ = x2′得到下式。null 可以从( 1.1.1.1 )开始试算， x′(3)＝( 1.1.0.1 )最优解。 ∴ x(3)＝( 1.0.1.0 )是原问题的最优解，Z* =-28.5 指派问题8.5 指派问题nullnullnullnull二、解题步骤： 指派问题是0-1 规划的特例，也是运输问题的特例，当然可用整数规划，0-1 规划或运输问题的解法去求解，这就如同用单纯型法求解运输问题一样是不合算的。利用指派问题的特点可有更简便的解法，这就是匈牙利法，即系数矩阵中独立 0 元素的最多个数等于能覆盖所有 0 元素的最少直线数。 第一步：变换指派问题的系数矩阵（cij）为(bij)，使在(bij)的各行各列中都出现0元素，即 (1) 从（cij）的每行元素都减去该行的最小元素； (2) 再从所得新系数矩阵的每列元素中减去该列的最小元素。null 第二步：进行试指派，以寻求最优解。 在(bij)中找尽可能多的独立0元素，若能找出n个独立0元素，就以这n个独立0元素对应解矩阵(xij)中的元素为1，其余为0，这就得到最优解。找独立0元素，常用的步骤为： (1)从只有一个0元素的行(列)开始，给这个0元素加圈，记作◎ 。然后划去◎ 所在列(行)的其它0元素，记作Ø ；这表示这列所代表的任务已指派完，不必再考虑别人了。 (2)给只有一个0元素的列(行)中的0元素加圈，记作◎；然后划去◎ 所在行的0元素，记作Ø ． (3)反复进行(1)，(2)两步，直到尽可能多的0元素都被圈出和划掉为止。null (4)若仍有没有划圈的0元素，且同行(列)的0元素至少有两个，则从剩有0元素最少的行(列)开始，比较这行各0元素所在列中0元素的数目，选择0元素少的那列的这个0元素加圈(表示选择性多的要“礼让”选择性少的)。然后划掉同行同列的其它0元素。可反复进行，直到所有0元素都已圈出和划掉为止。 （5）若◎ 元素的数目m 等于矩阵的阶数n，那么这指派问题的最优解已得到。若m < n, 则转入下一步。 第三步：作最少的直线覆盖所有0元素。 (1)对没有◎的行打√号； (2)对已打√号的行中所有含Ø元素的列打√号； (3)再对打有√号的列中含◎ 元素的行打√号； null (4)重复(2)，(3)直到得不出新的打√号的行、列为止； (5)对没有打√号的行画横线，有打√号的列画纵线，这就得到覆盖所有0元素的最少直线数 l 。l 应等于m，若不相等，说明试指派过程有误，回到第二步(4)，另行试指派；若 l＝m < n，须再变换当前的系数矩阵，以找到n个独立的0元素，为此转第四步。 第四步：变换矩阵(bij)以增加0元素。 在没有被直线覆盖的所有元素中找出最小元素，然后打√各行都减去这最小元素；打√各列都加上这最小元素（以保证系数矩阵中不出现负元素）。新系数矩阵的最优解和原问题仍相同。转回第二步。 null例 有一份中文说明书，需译成英、日、德、俄四种文字，分别记作A、B、C、D。现有甲、乙、丙、丁四人，他们将中文说明书译成不同语种的说明书所需时间如下表所示，问如何分派任务，可使总时间最少？ null求解过程如下： 第一步，变换系数矩阵：－5第二步，试指派： ◎◎◎ØØ找到 3 个独立零元素 但 m = 3 < n = 4null第三步，作最少的直线覆盖所有0元素： ◎◎◎ØØ√√√独立零元素的个数m等于最少直线数l，即l＝m=3