运筹学中期复习.ppt

,运筹学OperationsResearch,中期复习,Chap1线性规划Chap2线性规划的对偶理论Chap3整数规划Chap4运输与指派问题,Chap1线性规划,线性规划的一般模型一般地，假设线性规划数学模型中，有m个约束，有n个决策变量xj,j=1,2,n，目标函数的变量系数用cj表示,cj称为价值系数。约束条件的变量系数用aij表示，aij称为工艺系数。约束条件右端的常数用bi表示，bi称为资源限量。则线性规划数学模型的一般表达式可写成,为了书写方便，上式也可写成：,1.1线性规划的数学模型MathematicalModelofLP,在实际中一般xj0,但有时xj0或xj无符号限制。,1.1线性规划的数学模型MathematicalModelofLP,图解法的步骤：,1.求可行解集合（可行域）。；,2.绘制目标函数图形。,3.求最优解。,一般地，将目标函数直线放在可行域中：求最大值时直线沿着矢量方向移动求最小值时沿着矢量的反方向移动,1.2图解法TheGraphicalMethod,线性规划的解有4种形式：,1.有唯一最优解,2.有多重解,3.有无界解,4.无可行解,1、2情形为有最优解3、4情形为无最优解,1.2图解法TheGraphicalMethod,在用单纯法求解线性规划问题时，为了讨论问题方便，需将线性规划模型化为统一的标准形式。,1.3线性规划的标准型StandardformofLP,线性规划问题的标准型为:1目标函数求最大值（或求最小值）2约束条件都为等式方程3变量xj非负4常数bi非负,max(或min)Z=c1x1+c2x2+cnxn,1.3线性规划的标准型StandardformofLP,注：本教材默认目标函数是max,或写成下列形式：,或用矩阵形式,1.3线性规划的标准型StandardformofLP,通常X记为：，称A为约束方程的系数矩阵，m是约束方程的个数，n是决策变量的个数，一般情况mn，且r()m。,其中:,1.3线性规划的标准型StandardformofLP,设线性规划的标准型maxZ=CX（1.1）AX=b（1.2）X0（1.3）式中A是mn矩阵，mn并且r(A)=m，显然A中至少有一个mm子矩阵B，使得r(B)=m。,1.4基本概念BasicConcepts,基(basis)A中mm子矩阵B并且有r(B)=m，则称B是线性规划的一个基（或基矩阵basismatrix）。当m=n时，基矩阵唯一，当m0且aik（i=1，2,m）则线性规划具有无界解(见例1-18)；（c）若存在k0且aik(i=1,m)不全非正，则进行换基。,1.5单纯形法SimplexMethod,第个比值最小，选最小比值对应行的基变量为出基变量，若有相同最小比值，则任选一个。aLk为主元素；,(c）求新的基可行解：用初等行变换方法将aLk化为,k列其它元素化为零（包括检验数行）得到新的可行基及基本可行解，再判断是否得到最优解。,（b）选出基变量，求最小比值：,1.5单纯形法SimplexMethod,3.换基：（a）选进基变量设k=maxj|j0,xk为进基变量,唯一最优解的判断：最优表中所有非基变量的检验数小于零,则线性规划具有唯一最优解。多重最优解的判断:最优表中存在非基变量的检验数为零,则线则性规划具有多重最优解。无界解的判断:某个k0且aik（i=1，2,m）则线性规划具有无界解退化基本可行解的判断:存在某个基变量为零的基本可行解。,1.5单纯形法SimplexMethod,在实际问题中有些模型并不含有单位矩阵，为了得到一组基向量和初基可行解，在约束条件的等式左端加一组虚拟变量，得到一组基变量。这种人为加的变量称为人工变量，构成的可行基称为人工基，用大M法或两阶段法求解，这种用人工变量作桥梁的求解方法称为人工变量法。,1.大M单纯形法,1.5.2大M和两阶段单纯形法,1.5单纯形法SimplexMethod,两阶段单纯形法与大M单纯形法的目的类似，将人工变量从基变量中换出，以求出原问题的初始基本可行解。将问题分成两个阶段求解，第一阶段的目标函数是,约束条件是加入人工变量后的约束方程，当第一阶段的最优解中没有人工变量作基变量时，得到原线性规划的一个基本可行解，第二阶段就以此为基础对原目标函数求最优解。当第一阶段的最优解w0时，说明还有不为零的人工变量是基变量，则原问题无可行解。,1.5单纯形法SimplexMethod,2.两阶段单纯形法,解的判断,唯一最优解的判断：最优表中所有非基变量的检验数小于零,则线规划具有唯一最优解,多重最优解的判断:最优表中存在非基变量的检验数为零,则线则性规划具有多重最优解。,无界解的判断:某个k0且aik（i=1，2,m）则线性规划具有无界解,退化基本可行解的判断:存在某个基变量为零的基本可行解。,无可行解的判断：(1)当用大M单纯形法计算得到最优解并且存在Ri0时，则表明原线性规划无可行解。(2)当第一阶段的最优值w0时，则原问题无可行解。,1.5单纯形法SimplexMethod,Chap2线性规划的对偶理论,在线性规划问题中，存在一个有趣的问题，即每一个线性规划问题都伴随有另一个线性规划问题，称它为对偶线性规划问题。,【例21】某企业用四种资源生产三种产品，工艺系数、资源限量及价值系数如下表：,建立总收益最大的数学模型。,2.1线性规划的对偶模型DualModelofLP,【解】设x1，x2，x3分别为产品A，B，C的产量，则线性规划数学模型为：,现在从另一个角度来考虑企业的决策问题。假如企业自己不生产产品，而将现有的资源转让或出租给其它企业，那么资源的转让价格是多少才合理？合理的价格应是对方用最少的资金购买本企业的全部资源，而本企业所获得的利润不应低于自己用于生产时所获得的利润。这一决策问题可用下列线性规划数学模型来表示。,2.1线性规划的对偶模型DualModelofLP,设y1，y2，y3及y4分别表示四种资源的单位增值价格（售价成本增值），总增值最低可用,minw=500y1+450y2+300y3+550y4,表示。企业生产一件产品A用了四种资源的数量分别是9，5，8和7个单位，利润是100,企业出售这些数量的资源所得的利润不能少于100，即,同理，对产品B和C有,价格不可能小于零，即有yi0,i=1,4.从而企业的资源价格模型为,2.1线性规划的对偶模型DualModelofLP,这是一个线性规划数学模型，称这一线性规划模型是前面生产计划模型的对偶线性规划模型,这一问题称为对偶问题。生产计划的线性规划问题称为原始线性规划问题或原问题。,2.1线性规划的对偶模型DualModelofLP,上面两种形式的线性规划称为规范形式。,原问题和对偶问题是互为对偶的两个线性规划问题，已知一个问题就可写出另一个问题。,规范形式（CanonicalForm）的定义：目标函数求极大值时，所有约束条件为号，变量非负；目标函数求极小值时，所有约束条件为号，变量非负。规范形式的线性规划的对偶问题亦是规范形式。,以上是依据经济问题推导出对偶问题，还可以用代数方法推导出对偶问题。,2.1线性规划的对偶模型DualModelofLP,表2-2,表23,2.1线性规划的对偶模型DualModelofLP,设线性规划模型是式（2.1）的规范形式由表2-3知，当检验数,时得到最优解，是的检验数，由和得,在两边有乘b,则有,又因Y0无上界,从而只存在最小值，得到另一个线性规划问题,2.1线性规划的对偶模型DualModelofLP,即是原线性规划问题式（2.1）的对偶线性规划问题，反之，式（2.3）的对偶问题是式（2.1）原问题和对偶问题是互为对偶的两个线性规划问题，规范形式的线性规划的对偶仍然是规范形式，参数矩阵的对应关系参看表2-4因此已知一个规范形式问题就可写出另一个对偶问题,2.1线性规划的对偶模型DualModelofLP,表2-4,2.1线性规划的对偶模型DualModelofLP,【例2-3】写出下列线性规划的对偶问题,【解】目标函数求最小值，应将表24的右边看作原问题，左边是对偶问题，原问题有3个约束4个变量，则对偶问题有3个变量4个约束，对照表21的对应关系，对偶问题为：,2.1线性规划的对偶模型DualModelofLP,=,y10，,y20，,y3无约束,对偶问题是（记为DP）：,这里A是mn矩阵X是n1列向量，Y是1m行向量。假设Xs与Ys分别是（LP）与（DP）的松驰变量。,【性质1】对称性对偶问题的对偶是原问题。,设原问题是（记为LP）：,2.2对偶性质DualProperty,2.2.1对偶性质,【性质2】弱对偶性设X、Y分别为LP(max)与DP(min)的可行解，则,这一性质说明了两个线性规划互为对偶时，求最大值的线性规划的任一目标值都不会大于求最小值的线性规划的任一目标值，不能理解为原问题的目标值不超过对偶问题的目标值。,2.2对偶性质DualProperty,由这个性质可得到下面几个结论：,（1）（LP）的任一可行解的目标值是（DP）的最优值下界；（DP）的任一可行解的目标是（LP）的最优值的上界；,（2）在互为对偶的两个问题中，若一个问题可行且具有无界解，则另一个问题无可行解；,（3）若原问题可行且另一个问题不可行，则原问题具有无界解。,2.2对偶性质DualProperty,【性质3】最优准则定理设X0与Y0分别是（LP）与（DP）的可行解，则当X0、Y0是（LP）与（DP）的最优解当且仅当CX0=Y0b.,2.2对偶性质DualProperty,【性质4】若互为对偶的两个问题其中一个有最优解，则另一个也有最优解，且最优值相同。,【性质5】互补松弛定理设X0、Y0分别为（LP）与（DP）的可行解，XS和YS是它的松弛变量的可行解，则X0和Y0是最优解当且仅当,YSX0=0和Y0XS=0,2.2对偶性质DualProperty,性质5告诉我们已知一个问题的最优解时求另一个问题的最优解的方法，即已知Y*求X*或已知X*求Y*。,Y*XS=0和YSX*=0,两式称为互补松弛条件。将互补松弛条件写成下式,由于变量都非负，要使求和式等于零，则必定每一分量为零，因而有下列关系：,2.2对偶性质DualProperty,(1)当yi*0时，,反之当时yi*=0；,利用上述关系，建立对偶问题（或原问题）的约束线性方程组，方程组的解即为最优解。性质5的结论和证明都是假定（P）与（D）为对称形式，事实上对于非对称形式，性质5的结论仍然有效。,2.2对偶性质DualProperty,【性质6】LP(max)的检验数的相反数对应于DP(min)的一组基本解.其中第j个决策变量xj的检验数的相反数对应于（DP）中第j个松弛变量的解，第i个松弛变量的检验数的相反数对应于第i个对偶变量yi的解。反之，（DP）的检验数（注意：不乘负号）对应于（LP）的一组基本解。,2.2对偶性质DualProperty,本节介绍六个对偶性质；这些性质是研究原问题与对偶问题解的对应关系；表26列举了这些性质。,表26,2.2对偶性质DualProperty,2.3对偶单纯形法DualSimplexMethod,设原问题是（记为LP）：,对偶问题是（记为DP）：,根据对偶性质6，可以构造一个求线性规划的另一种方法，即对偶单纯形法。,对偶单纯形法的计算步骤：,对偶单纯形法的条件是：初始表中对偶问题可行，即极大化问题时j0，极小化问题时j0。,2.3对偶单纯形法DualSimplexMethod,(1)将线性规划的约束化为等式，求出一组基本解，因为对偶问题可行，即全部检验数j0（max）或j0（min）,当基本解可行时，则达到最优解；若基本解不可行，即有某个基变量的解bi0，则进行换基计算；,(2)先确定出基变量。l行对应的变量x出基；,(3)再选进基变量。求最小比值,(4)求新的基本解，用初等变换将主元素alk化为l,k列其它元素化为零，得到新的基本解，转到第一步重复运算。,2.3对偶单纯形法DualSimplexMethod,应当注意：,（1）用对偶单纯形法求解线性规划是一种求解方法，而不是去求对偶问题的最优解；,（2）初始表中一定要满足对偶问题可行，也就是说检验数满足最优判别准则；,（3）最小比值中的绝对值是使得比值非负，在极小化问题时j0，分母aij0这时必须取绝对值。在极大化问题中，j0分母aijZ因此LP5的最优解就是原整数规划的最优解。,上述分枝过程可用下图表示,LP0:X=(3.57,7.14),Z0=35.7,LP1:X=(3,7.6)Z1=34.8,LP2:X=(4,6.5)Z2=35.5,x13,x14,LP3:X=(4.33,6)Z3=35.33,x26,LP4:X=(4,6)Z4=34,LP5:X=(5,5)Z5=35,x14,x15,无可行解,x27,设纯整数规划,松弛问题,的最优解,设xi不为整数，,3.2.2求解IP的割平面法,3.2纯整数规划的求解SolvingPureIntegerProgramming,将分离成一个整数与一个非负真分数之和：,则有,等式两边都为整数并且有,3.2纯整数规划的求解SolvingPureIntegerProgramming,加入松弛变量si得,此式称为以xi行为源行（来源行）的割平面，或分数切割式，或R.E.Gomory(高莫雷)约束方程。,将Gomory约束加入到松弛问题的最优表中，用对偶单纯形法计算，若最优解中还有非整数解，再继续切割，直到全部为整数解。,则,3.2纯整数规划的求解SolvingPureIntegerProgramming,例如，,x1行：,移项：,令,加入松弛变量s1得,同理，对于x2行有：,3.2纯整数规划的求解SolvingPureIntegerProgramming,【例3-6】用割平面法求解下列IP问题,【解】放宽变量约束，对应的松弛问题是,3.2纯整数规划的求解SolvingPureIntegerProgramming,加入松弛变量x3及x4后，用单纯形法求解，得到最优表3-3。,最优解X(0)(5/2，15/4),不是IP的最优解。选择表3-3的第一行(也可以选第二行)为源行,3.2纯整数规划的求解SolvingPureIntegerProgramming,表3-3,分离系数后改写成,加入松弛变量x5得到高莫雷约束方程,将式(3-8)作为约束条件添加到表33中，用对偶单纯形法计算，如表34所示,3.2纯整数规划的求解SolvingPureIntegerProgramming,最优解X(1)(3，3)，最优值Z21。所有变量为整数，X(1)就是IP的最优解。如果不是整数解，需要继续切割，重复上述计算过程。,3.2纯整数规划的求解SolvingPureIntegerProgramming,表34,3.3.1求解01整数规划的隐枚举法,隐枚举法的步骤：,1.找出任意一可行解，目标函数值为Z0,2.原问题求最大值时，则增加一个约束,当求最小值时，上式改为小于等于约束,3.列出所有可能解，对每个可能解先检验式（*），若满足再检验其它约束，若不满足式（*），则认为不可行，若所有约束都满足，则认为此解是可行解，求出目标值,4.目标函数值最大（最小）的解就是最优解,3.301规划的求解SolvingBIP,【例3-7】用隐枚举法求解下列BIP问题,【解】（1）不难看出，当所有变量等于0或1的任意组合时，第一个约束满足，说明第一个约束没有约束力，是多余的，从约束条件中去掉。还能通过观察得到X0(1，0，0，1)是一个可行解，目标值Z011是BIP问题的下界，构造一个约束：，原BIP问题变为,3.301规划的求解SolvingBIP,(2)列出变量取值0和1的组合，共2416个，分别代入约束条件判断是否可行。首先判断式（3-9a）是否满足，如果满足，接下来判断其它约束，否则认为不可行，计算过程见表37所示。,3.301规划的求解SolvingBIP,表35,(3)由表3-5知，BIP问题的最优解：X（1，0，1，1），最优值Z14,3.301规划的求解SolvingBIP,选择不同的初始可行解，计算量会不一样。一般地，当目标函数求最大值时，首先考虑目标函数系数最大的变量等于1，如例3-8。当目标函数求最小值时，先考虑目标函数系数最大的变量等于0。在表37的计算过程中，当目标值等于14时，将其下界11改为14，可以减少计算量。,3.3.2分枝隐枚举法求解BIP问题,将分枝定界法与隐枚举法结合起来用，得到分枝隐枚举法。计算步骤如下：（1）将BIP问题的目标函数的系数化为非负，如,3.301规划的求解SolvingBIP,当变量作了代换后，约束条件中的变量也相应作代换。,（3）求主枝：目标函数是max形式时令所有变量等于1，得到目标值的上界；目标函数是min形式时令所有变量等于0，得到目标值的下界；如果主枝的解满足所有约束条件则得到最优解，否则转下一步；（4）分枝与定界：从第一个变量开始依次取“1”或“0”，求极大值时其后面的变量等于“1”，求极小值时其后面的变量等于“0”，用分枝定界法搜索可行解和最优解。分枝隐枚举法是从非可行解中进行分枝搜索可行解，第（1）步到第（3）步用了隐枚举法的思路，第（4）步用了分枝定界法的思路。,3.301规划的求解SolvingBIP,(2)变量重新排序：变量依据目标函数系数值按升排序；,停止分枝和需要继续分枝的原则：（1）当某一子问题是可行解时则停止分枝并保留；（2）不是可行解但目标值劣于现有保留分枝的目标值时停止分枝并剪枝；（3）后续分枝变量无论取“1”或“0”都不能得到可行解时停止分枝并剪枝；（4）当某一子问题不可行但目标值优于现有保留分枝的所有目标值，则要继续分枝。,【例3-8】用分枝隐枚举法求解下列BIP问题,3.301规划的求解SolvingBIP,解（1）目标函数系数全部非负，直接对变量重新排序,（2）求主枝：令X(1，1，1，1)得到主枝1，检查约束条件知(3-10c)不满足，则进行分枝。（3）令x2=0同时令x3=0及x3=1得到分枝2和分枝3，X2和X3是可行解，分枝停止并保留，如表3-8及图3-8所示。,3.301规划的求解SolvingBIP,表3-8,令x2=1同时令x3=0得到分枝4，X4是可行解，分枝停止并保留。令x2=1、x3=1，x4取“0”和“1”得到分枝5和6，分枝5不可行并且Z511小于Z3和Z4，分枝停止并剪枝。注意到分枝6，x41时只有x10（x11就是主枝），X6不可行并且Z610小于Z3和Z4，分枝停止并剪枝，分枝过程结束。整个计算过程可用图32和表3-8表示。,3.301规划的求解SolvingBIP,搜索到3个可行解，3个目标值中Z3最大，因此X3是最优解，转换到原问题的最优解为X（1，0，1，1），最优值Z14，计算结束。,图32,3.301规划的求解SolvingBIP,【例3-9】用分枝隐枚举法求解下列BIP问题,解（1）令x2=1x2及x5=1x5，代入模型后整理得,3.301规划的求解SolvingBIP,（2）目标函数系数按升序将对应的变量重新排列得到模型,（3）求主枝。由于目标函数求最小值，令所有变量等于零，得到主枝的解X1（0，0，0，0，0），Z17，检验约束条件知X1不可行，进行分枝。（4）取x1=1和x1=0，分别其它变量等于“1”和“0”分枝，判断可行性，计算过程参见表36及图33。,3.301规划的求解SolvingBIP,表36,3.301规划的求解SolvingBIP,由表36知，分枝5和分枝10两个问题可行，