运筹学(fuxi).ppt

运筹学,绪论第一章线性规划与单纯形法第二章线性规划的对偶理论与灵敏度分析第三章运输问题第四章目标规划第五章整数规划第八章图与网络分析,第一章线性规划与单纯形法,三要素组成:1.变量:决策变量(x1,x2xn)2.目标函数:决策变量的函数,系统要达到的目标3.约束条件:对决策变量的限制,若：决策变量的取值是连续的,且目标和约束条件为决策变量的线性函数和线性等式或不等式,则该类规划问题为线性规划问题。,解决问题的共同点:在现有各项资源条件限制下,如何确定方案,使预期目标达到最优,（1）线性规划问题的数学模型一般可表示为：,max(min)z=c1x1+c2x2+cnxn,a11x1+a12x2+a1nxn(或=，)b1,a21x1+a22x2+a2nxn(或=，)b2,am1x1+am2x2+amnxn(或=，)bm,x1,x2,xn0,设线性规划中有n个决策变量,用xj(j-=1,2,n);目标函数中xj(j-=1,2,n)的系数为cj(j-=1,2,n);用bi表示第i(i=1,2,m)种资源限制;aij表示决策变量xj取值为1个单位时消耗的第i种资源量。,（2）一般模型的简写形式,（3）数学模型的向量形式：,（4）数学模型的矩阵形式：,max(min)z=CX,AX(或=,)bX0,线性规划的应用条件,1、要解决的问题的目标可以用数值指标反应；2、对于要实现的目标有多种方案可选择；3、有影响决策的若干约束条件。,规定线性规划问题的标准形式如下：,（4）变量无约束，或称为自由变量。对于自由变量，通常引入两个新的非负变量，比如，令xj=xjxj，其中，xj，xj0（5）如果x0，则令x=-x，显然，x0,对不符合上述标准形式的线性规划问题，进行标准化处理：（1）目标函数为求极小值。因为求minz等价于求max(z),所以，可以令z=-z，求maxz即可。（2）右端常数项小于零。只需将不等式或等式两边同乘1。（3）约束条件为不等式。对于“”符号的不等式约束，左边减去一个非负变量变为等式约束，新变量称为剩余变量，或松弛变量；对于“”符号的约束，左边加上一个非负变量变为等式，新变量称为松弛变量。,（1）minz=x1+2x2+3x3令Z=-ZminZ=min（-z）=maxz,则minz=x1+2x2+3x3,则maxz=-x1-2x2-3x3,（2）2x1+x2+x39,2x1+x2+x3+x4=9,3x1+x2+2x34,3x1+x2+2x3x5=4,4x12x23x3=6,-4x1+2x2+3x3=6,（3）x10,x20,x3无约束,令x1=-x1,x3=x3-x3”,解的概念(1)可行解:满足所有约束条件（1-2，1-3）的解称为线性规划问题的可行解。(2)最优解:使目标函数（1-1）达到最大值的可行解称为最优解。(3)基：满秩子矩阵(4)基解:在约束方程组中，令所有非基变量xj(j=m+1n)取零值。因为子矩阵B是满秩的，根据克莱姆法则,由m个约束方程可以解出m个基变量xi(i=1m)的唯一解,XB=(x1,x2,xm)T。我们把X=(x1,x2,xm，0，0)T称为基解(5)基可行解:满足非负性约束条件(1-3)的基解称为基可行解。(6)可行基:对应于基可行解的基称为可行基.(7)退化解:如果基变量某些分量取零值，则称该解为退化解。,x1=4/5x2=11/5,x1=14x3=-11,x2=7/3x3=2/3,图解法,图解法的结局1）唯一最优解。2）无穷多最优解。3）无界解。可行域无界所致。说明建立数学模型时遗漏了某些必要的资源约束。4）无可行解。无可行域,约束之间互相矛盾。图解法的启示1）如果线性规划问题的可行域存在，则可行域是一个凸集。2）如果线性规划问题存在最优解，则最优解（或之一）在凸集的顶点上达到。,用图解法求解线性规划时，各种求解结果与各种类型的可行域之间的对应关系可以用下图加以描述：,定理1：若线性规划问题存在可行解，那么，问题的可行域是凸集。引理1：线性规划问题的可行解X=(x1,x2,xn)T为基可行解的充要条件是X的正分量对应的系数列向量是线性独立。定理2：线性规划问题的基可行解X对应于线性规划问题可行域（凸集）的顶点。定理3：若线性规划问题有最优解，一定存在一个基可行解是最优解。,几个定理,上述基本定理给出一条清晰的思路：,线性规划问题的最优解在可行域的顶点上达到；线性规划问题的每个基可行解对应可行域的一个顶点；基可行解是基解与可行解的交集；基解的数目不超过组合数,所以，可以通过基解、顶点寻找线性规划问题的最优解。,可行域,可行解,几何概念,代数概念,约束直线,满足一个等式约束的解,约束半平面,满足一个不等式约束的解,约束半平面的交集：凸多边形,满足一组不等式约束的解,约束直线的交点,基解,可行域的顶点,基可行解,目标函数等值线：一组平行线,目标函数值等于一个常数的解,将基可行解X（0）和X（1）代入目标函数，得,检验数：,判别定理：（1）当所有的检验数都j0时，新基可行解X（1）的目标函数值小于X（0）的目标函数值，这说明，目前的基可行解（顶点）就是最优解。,最优性检验和解的判断,（2）当所有的检验数j0时，又有某一个非基变量的检验数等于零，表明新基可行解与原来的基可行解有相同的目标函数值，则问题具有无穷多最优解。（3）与之相应，如果所有非基变量的检验数j0，则线性规划问题具有唯一最优解。（4）如果某个非基变量的检验数j0，而它所对应的系数列向量Pj0，则线性规划问题具有无界解。,*注意，在X（1）的各个分量,无限增大时，目标函数值无限增加，所以，线性规划问题具有无界解。,由于Pj0，对任意的,单纯形法计算步骤,1.求初始基可行解，列出单纯形表,2.最优性检验,3.基变换（从一个基转换到另一个基）,4.重复步骤2和3，求出最优解,备注：单纯形表中必须有m个基变量，以及和它们对应的m个单位列向量单位方阵。,1求初始基可行解，列出单纯形表,从表中可以看出：（1）所有基变量对应的检验数都为零。（2）所有非基变量的检验数都是按特定的公式计算的，即,对于求极大化问题，如果所有的检验数0，则已获得最优解，计算结束。如果某个非基变量的检验数0，且它所对应的系数列向量0，则问题具有无界解，结束计算。其他情况下，转下一步骤。,2最优性检验,3基变换,（1）确定换入基的变量。只要非基变量的检验数大于零，都可以作为换入变量。但是，当有一个以上检验数大于零时，人们习惯选择检验数最大的变量xk作为换入变量。,（2）确定换出基的变量。如果选择xk作为换入变量，则按下面的规则确定换出基的变量xl,(3)用xk代替xl，进行基变换。,旋转运算方法步骤如下：1）选择主元素。主元素在第l行，第k列。也即xk在第l个方程中的系数alk。2)第l个方程(行）中的每一个系数都除以主元素alk。bl=bl/alkalj=alj/alk3)把新得到的第l个方程(行）中的每一个系数分别乘以aik后加到第i行。这样做的目的是，把变量xk的系数列向量变为单位列向量。bi=bi(bl/alk)aikaij=aij(alj/alk)aik(il),XB,原始数据区,初始基可行解数据区,检验数,换出变量,4)计算检验数:计算检验数可采用两种方法：一是利用计算检验数的公式；另一种是把检验数行当作一个约束方程，与其它行一样，用消元法进行计算。,大M法(人工变量法)的具体实施步骤：,对于标准形式的线性规划问题：,设A中不含单位矩阵，在约束方程中引入人工变量Xa，在目标函数中增加惩罚项MXa，其中M是一个任意大的正数，我们得到一个新的线性规划问题。,如果系数矩阵A中没有单位矩阵，还可以采用两阶段法求解。,阶段1:构造目标函数中只包含人工变量的线性规划问题。目的是寻找初始基可行解。,如果=0，则原线性规划问题有可行解,转入第二阶段；如果0，则原线性规划问题没有可行解，停止计算。,两阶段法,阶段2:去掉人工变量，得到只包含原来变量的约束方程组。与原来的目标函数一起，形成最初要解决的线性规划问题。,其中，A中包含有单位矩阵。,（1）目标函数求极小值时的最优性判据。,与求极大值时相反，如果所有非基变量的检验数都0，则当前的解就是最优解。人们习惯于把检验数最负的变量作为换入变量。（2）退化。基可行解中出现一个或者多个基变量取零值的解称为退化解。当存在退化解时，单纯形法计算有可能会出现循环。这里遵循：当存在多个检验数大于零时，始终选择下标值为最小的变量作为换入变量；当出现两个以上相同的最小比值时，始终选择下标值为最小的变量作为换出变量。（3）无可行解判别。检验数满足最优性条件时，人工变量是基变量且不等于零，则线性规划问题无可行解。,单纯形法计算中的几个问题,第二章线性规划对偶理论与灵敏度分析,第一节线性规划的对偶问题第二节对偶问题的基本性质第三节影子价格第四节对偶单纯形法第五节灵敏度分析,对称形式的原始-对偶关系对称形式的条件：（1）变量全部具有非负约束；（2）目标函数求极大值时，约束不等式符号全部为；目标函数为求极小值时，约束不等式的符号全部为。,变量行与参数行相乘组成原始问题的约束条件和目标函数；变量列与参数列相乘组成对偶问题的约束条件和目标函数。,原始-对偶关系一览表,minz=x1+4x2+3x3,2x1+3x2+x323x1x21x1+x2+x3=4x10,x20,x3自由变量。,st.,maxw=2y1+y2+4y3,st.,2y1+3y2+y313y1y2+y34y1+y3=3y10,y20,y3自由变量.,以对称形式的原始-对偶问题为讨论的基础,单纯形法计算的矩阵描述,原问题通过加入松弛变量Xs可以化为标准形式：,其中，I是对应于松弛变量的单位方阵。,单纯形法计算时，总是选择I为初始可行基，松弛变量作为初始基变量的。由于松弛变量作为基变量意味着资源没有被利用，所以，单纯形法迭代若干步后，松弛变量会被置换出基变量集合。,项目,0Xsb,非基变量,基变量,XBXN,Xs,BN,I,检验数,CBCN,0,设新的基变量组合为XB，在初始单纯形表中的系数矩阵为B，价值系数为CB。A去掉B的若干列后，剩余的列向量组成子矩阵N，对应的变量组合记为XN，价值系数记为CN。,B1b,B1N,B1,(CNCBB1N),-CBB1,推论：（1）原问题任一可行解的目标函数值是对偶问题目标函数值的下界；反之，对偶问题任一可行解的目标函数值是原问题目标函数值的上界（2）如果原问题有可行解且目标函数值无界（无界解），则对偶问题无可行解；反之，对偶问题有可行解且目标函数值无界，则原问题无可行解。(注意：本性质的逆不成立。因为当对偶不可行时，要么原问题无界，要么原问题无可行解。)（3）如果原问题有可行解，对偶问题无可行解，则原问题目标函数值无界；反之，对偶问题有可行解，原问题无可行解，则对偶问题的目标函数值无界。,maxZ,原问题可行解,minW,对偶可行解,对偶问题的基本性质,性质1.弱对偶性。如果X0，Y0分别是原始问题和对偶问题的可行解，则CX0Y0b,用途：判断线性规划问题有无最优解。因为原始和对偶问题可行解的目标函数值分别是对偶、原始的下、上界，所以，只要找到原始、对偶的可行解，就可断定原始、对偶问题有无最优解。,可以看出，原问题有可行解，比如X=（1，1，1，1）T，对偶问题有可行解Y=（1，1），所以，原线性规划问题有最优解。,性质2.最优性如果X0，Y0分别是原始问题和对偶问题的可行解，且有CX0=Y0b，则X0，Y0分别是原始问题和对偶问题的最优解。,性质3强对偶性（或对偶定理）如果原始问题和对偶问题都有可行解，则两者都有最优解，并且目标函数值相同。,性质4.互补松弛性（或松紧定理）。在线性规划问题的最优解中，如果对应于某一约束条件的对偶变量值不为零，则该约束条件取严格的等式符号；反之，如果约束条件取严格不等式符号，则其对应的对偶变量一定取零值。,根据上述的对偶性质（理论），不难看出原问题和对偶问题的解存在有如下关系。,其对偶问题的最优解为y1=4/5，y2=3/5。试确定原问题的最优解。,将对偶问题最优解代入对偶约束中可知，第2、3、4约束为严格不等式，x2=x3=x4=0。,对偶问题的解大于零，所以，原问题的约束条件在最优时取等号，即x1+3x5=42x1+x5=3,X=（1，0，0，0，1）T。,求解后得，x1=1，x5=1。,影子价格的概念、定义,从对偶问题的基本性质可以看出，当线性规划原问题求得最优解时，其对偶问题也得到了最优解，且目标函数值相同，即Z=CBXB=CBB1b=Yb=w,由于b是线性规划原问题约束条件的右端常数项，表示企业对资源的拥有量，如果Z是企业所创造的总收益的话，Y就是资源在生产中作用和贡献的有效性估价。为区别于资源的市场价格，称Y为影子价格。,影子价格也叫经济价格，它有广泛的含义。一般认为，凡用各种方法计算出来的非自然形成的价格，以及由国际市场引进的价格，只要不在现实生活中发生作用，都可以称为影子价格。,重点：影子价格的特点和应用,使用对偶单纯形法必须满足两个条件：（1）单纯形表中的所有检验数必须符合最优性要求,即对偶可行.（2）右端常数项列向量必须有负分量（如果原问题可行，则直接用单纯形法）,对偶单纯形法：,（1）把线性规划问题化为标准形式，找出对偶问题的初始可行基，列出单纯形表。表的格式与第一章的单纯形表完全相同。,（2）确定换出基的变量。这一点与单纯形法正好相反，那里是先确定换入变量。因为常数项有负分量，所以令br=minbi,第i行对应的基变量xr作为换出变量。,对偶单纯形法的计算步骤,（3）确定换入基的变量。这里要注意：单纯形法确定换出变量时用的是换入变量列向量与常数项列的最小比值；对偶单纯形法确定换入变量时则用检验数行与换出变量所在行的系数最小比值。如果所有的arj0，则原问题没有可行解。停止计算。如果存在arj0，则计算最小比值。,(4)选择ars为主元素，把该列向量变为单位列向量。,（5）重复步骤（2）-（4），直至原问题变为可行解为止。,灵敏度分析的概念：是指对系统或事物因周围环境条件发生变化所表现出来的敏感程度的分析。,灵敏度分析及其步骤,(2)检查原问题是否仍可行：基变量的取值是否仍全部0；,（3）检查对偶问题是否仍可行：检验数行是否仍满足最优性条件,（4）按下表所列情况得出结论，即决定继续计算的步骤。,灵敏度分析内容：,例：某工厂生产A，B，C三种产品，若设分别为A，B，C三种产品的产量，为制定最优生产计划建立如下所示模型：,（1）用表格单纯形法求出最优生产计划（2）在所得最优表格基础上，分别就以下情况进行分析。由于市场需求变化，产品B的单位利润可能改变，试求出保持最优生产计划不需改变的产品B单位利润的变化范围；若产品B单位利润由2变为5，求相应最优生产计划。由于原材料市场变化，原材料1的供应从100单位降低至50个单位，此时是否会影响最优生产计划？若影响，求其最优生产计划？由于生产技术改进，产品C的单位利润消耗原材料1，2及工时由原来的4，6，2依次变为2，2，1，求相应的最优生产计划？,3,4x100/311/3201/30,0k32000-40-11,0k1100/304/301-2/30,05/3-50-4/30,4/3,3y250103/4-1/20,4x25102-1/41/20,0k32000-40-11,00-5-5/4-1/20,由于市场需求变化，产品B的单位利润可能改变，试求出保持最优生产计划不需改变的产品B单位利润的变化范围；若产品B单位利润由3变为5，求相应最优生产计划。,3+u,3+u,3=-5,4=0-3/4（3+u）+1,5=0+1/2（3+u）-2,-5/3u1,4/3c24,5,5,3=-5,4=0-3/4*5+1=-11/4,5=0+1/2*5-2=1/2,00-5-11/41/20,1/2,0k250204-1/210,5y501121/200,0k370200-1/201,-10-7-5/200,由于原材料市场变化，原材料1的供应从100单位降低至50个单位，此时是否会影响最优生产计划？若影响，求其最优生产计划？,B1b=,=,-25/275/220,-25/275/220,-1/2,4x251121/200,0k2500-20-3/210,0k3700-2-4-3/201,0-1-5-200,由于生产技术改进，产品C的单位利润消耗原材料1，2及工时由原来的4，6，2依次变为2，2，1，求相应的最优生产计划？,B1P3=,=,1/21/2-1,-1/2,产销平衡运输问题的数学模型为：,前m个等式约束表示：由某一个产地运往各个销地的物品数量之和等于该地的产量；中间的n个等式约束表示：各个产地运往某个销地的物品数量之和应该等于该销地的销量。注意，这些结论仅限于产销平衡运输问题。,第三章:运输问题,设xij为由产地Ai(i=1,2,m)向销地Bj(j=1,2,n)运送的物品数量，则该问题可以用运输表直观表示出来，有时，表中只列出单位运价，称其为运价表。,1.运输问题是线性规划问题的一种形式,2.运输问题都有有限的最优解,3.运输问题约束条件的系数矩阵A为稀疏矩阵,运输问题数学模型的特点：（1）约束条件系数矩阵的元素是0或者1；（2）在系数矩阵A的每一个列向量中，只有两个非零元素1，说明每一个变量xij在约束方程中只出现两次，它们分别位于第i个分量（方程）处和第m+j个分量（方程）处；（3）所有约束条件都为等式约束；（4）各产地产量之和等于各销地销量之和；（5）前m个方程之和减去后n个方程之和等于0，说明系数列向量是线性相关的，换言之，约束条件中存在多余方程。,1、按某种规则确定初始解（初始调运方案或初始基可行解）2、最优性判别。如果为最优解，停止迭代；否则，在运输表上进行调整，得到一个新解3、再判断，再改进，直至得到最优解为止。注意：如果用单纯形法求解运输问题，需要先去掉一个等式约束；而用表上作业法时，不必写出数学模型，只要画出产销平衡的运输表即可。,表上作业法主要步骤包括：,3、沃格尔法,沃格尔法把最小运价与次最小运价的差叫罚数。罚数越小，不按最小运价运输所造成的损失不大；反之，损失会很大。为了避免造成大的损失，应该对具有最大罚数的供应地（或销地）以最小运价先行安排，使其得到满足。,确定初始调运方案,1、最小元素法为减少运费，应优先考虑单位运价最小的（或运距最短的）供销业务，最大限度地予以满足。,2、西北角法（左上角法）西北角法与最小元素法的不同点是，它优先选择运输表西北角（左上角）空格处的变量作为基变量。,解的最优性检验（求极小值，检验数非负；求极大值，检验数非正）,1.闭回路法（1）以任意一个非基变量(空格为起点寻找闭回路。除起点为非基变量外，闭回路上的其它顶点都是基变量(数字格)。*非基变量的检验数唯一，闭回路也是唯一的。否则，多个闭回路通过非基变量连成一个更大的闭回路，说明基变量集合是线性相关的。*闭回路上的顶点个数为偶数。（2）在闭回路上，以非基变量为起点，奇数顶点单位运价乘+1，偶数顶点单位运价乘1，然后相加，即可得到非基变量的检验数。（3）按照上述步骤计算所有非基变量的检验数。,2.对偶变量法（位势法）:,由于运输问题有m+n个约束，m+n个对偶变量，所以，方程组的解不是唯一的。对此，可以任意选择一个变量作为自由变量，然后求解方程组。方程组的解称为位势。,解的改进,（1）把检验数最负的非基变量选为换入变量，找出它在运输表中的闭回路；（2）以换入变量为闭回路的起点（第一个奇数顶点），为其它顶点依次编号；（3）在闭回路上的所有偶数顶点中，找出运输量最小的顶点。该顶点处的基变量作为换出变量，即变为非基变量；（4）以该最小运输量为调整量，将闭回路上，所有奇数顶点处的运输量都加上这一数值，偶数顶点处的运输量都减去该数值。,注意：当换出变量变为非基变量时，其数值“0”不能填入运输表中，否则，容易被认为是基变量。,在得到新的基可行解之后，需要对其进行最优性检验。如果满足最优性条件，则停止计算；否则，重复上述步骤，继续改进，直到得出最优解为止。,几点说明,如果运输问题的基可行解有多个非基变量的检验数为负，在继续迭代时，取它们中的任一变量为换入变量均可使目标函数值得到改善，但是，通常选择检验数最负的变量作为换入变量。当检验数满足最优性条件时，如果某个非基变量的检验数等于0，说明该运输问题具有无穷多最优解。在制定初始运输方案时，或者在调整运输方案时，往往会遇到产销量相同，或者偶数顶点的最小调整量有几个的情况。这时就出现了退化解（参阅线性规划中退化解的概念）。如果是确定初始方案（用最小元素法等），则需要在划去一行一列的同时，在该行列的某个格子里填入数字“0”；如果是调整方案，则需要在最小调整量的偶数顶点处，选择一个非基变量，其余变量处填入数字“0”。（4）最小调整量可以是“0”。,运输问题的进一步讨论-产销不平衡的运输问题,1.产量大于销量为借助产销平衡的表上作业法求解，可以设想存在一个“销地”Bn+1。由于它并不存在，所以，产地调运到这个“销地”的物品数量xi，n+1实际上是产地的库存量。既然是就地保存，所以运价ci，n+1=0。2.供不应求的情况供不应求时，一些销地的需求不能满足。为了使用表上作业法，可以虚设一个“产地”,“产地”的产量为,由于没有物品可以运输，所以，该产地的单位运价cm+1，j=0。,第四章目标规划,目标规划是一种数学方法：用于解决目标数目在两个或两个以上的多目标决策问题。由于是多目标问题，所以必须考虑：（1）目标分类一类是必须达到的目标，另一类是希望实现的目标；（2）目标分层希望实现的目标根据轻重缓急的要求来分出层次；同一层次的目标属性应是独立的。,目标规划的基本概念（1）绝对约束和目标约束（2）偏差变量（3）优先因子（P1P2PL）和权系数wk（4）目标规划中的目标函数a、要求不低于目标值。minf(d-)b、要求不超过目标值。minf(d+)c、要求恰好达到目标值。minf(d-+d+),求解目标规划问题常用的有两种方法。图解法：形象直观，但只适用于只有两个决策变量。单纯形法：目标规划的数学模型与线性规划的数学模型本质上是一致的，故可以利用单纯形方法求解目标规划问题,A点坐标为（0，5.2），C点坐标为（0.6，4.7)故满意解集合为,解：（1）对于第一优先级，要求不足部分尽可能的小，所以，确定出AB线以上的半平面。（2）对于第二优先级，存在两目标，且权重不一样。通常的做法是：先考虑权数大的目标。因此，在AB线的右上方部分，GE线及其以下为第三目标可取部分，即GEB。然后，考虑第二目标。它也要求正偏差尽可能的小，在GEB区域，只有E点满足此要求。（3）第三优先级在E点自动满足。,A,B,G,解目标规划的单纯形法,利用单纯形法求解目标规划时,需要注意以下几点：1、偏差变量与决策变量、松弛变量一样看待。一般可以利用偏差变量、松弛变量作为初始基变量，常常不需（或需较少的）人工变量；2、目标规划是求极小化的目标函数，满意判别准则是所有检验数cj-zj03、某一变量整体检验数正负取决于第一优先因子的系数,如果为正,则大于零,否则,小于零。只有当第一优先因子的检验数为零时，该变量的整体检验数的正负取决于第二优先因子的系数,依此类推。,4、在整体检验数小于零的变量中选择进基变量时，应按第一优先因子选择检验数mincj-zj/cj-zj0对应的变量为进基变量；只有当第一优先因子的检验数均为0时，按第二优先因子选择检验数mincj-zj15时，这几乎是不可能的。所以，有人提出了隐枚举法。,0-1型整数规划的解法隐枚举法,、先找一个可行解,如（0,0,0)，并将其目标函数值Z=0作为下界。,、由上步得出过滤性约束条件,、对某种变量的组合，检验其是否满足上述过滤条件，若满足且又是可行解，则修改过滤条件，重复（）。,隐枚举法步骤,注意:上述计算步骤还可以进一步得到改善，即对极大化问题，若将目标函数中xj的价值系数按递增（不减）的次序排列（求极小，价值系数按照递减的次序排列）。即,则可知(0,0,1)的目标值一定不小于(0,1,0)及(1,0,0)的目标值。同样(0,1,1)的目标值一定不小于(1,1,0)与(1,0,1)的目标值。故若(0,0,0)、(0,0,1)、(0,1,1)、(1,1,1)都为可行解，则其他变量的组合可不必考虑。,分支定界法,1分支假设松弛问题的最优解不是整数解，则选择一个非整数分量构造两个约束条件：,分别加入松弛问题中，得到两个子问题LP1与LP2,即后继问题，并求解之。,2定界（以求极大值为例）以最优目标函数值中最大者（针对没有分支的线性规划问题而言）