线性规划与单纯形方法.ppt

1,第一章 线性规划与单纯形法,本章重点内容 线性规划模型与解的主要概念 线性规划的单纯形法，线性规划多解分析 线性规划的应用建模,2,第一节 线性规划问题及数学模型,一、实例 二、线性规划问题（LP问题）的共同特征 三、两变量线性规划问题的图解法 四、线性规划问题的标准型 五、标准型LP问题解的概念 六、可行解、基解和基可行解举例,3,一、实例,例1 生产计划问题,Step 1:明确问题，设定决策变量 设I、II两种产品的产量分别为x1, x2 。,Step 2: 确定约束条件,问应如何安排生产 使该厂获利最多？,4,说明：OBJ 表示Objective; s.t. 表示Subject to,Step 3: 给出目标函数,Step 4: 整理数学模型,5,例2 现要做100套钢架，每套需2.9米、2.1米和1.5米的元钢各一根。已知原料长7.4米，问如何下料，使余料最少？ 设I, II, III, IV, V分别代表五种不同的原料用量方案, x1, x2 , x3, x4 , x5分别代表采用各方案下料的元钢的根数。,解：,6,7,LP(Linear Programming)是数学规划的一个重要分支，数学规划着重解决资源的优化配置，一般可以表达成以下两个问题中的一个： （1）当资源给定时，要求完成的任务最多； （2）当任务给定时，要求为完成任务所消耗的资源最少。 若上述问题的目标约束都能表达成变量的线性关系，则这类优化问题称LP问题。 LP是一种解决在线性约束条件下追求最大或最小的线性目标函数的方法。,8,目标函数用决策变量的线性函数来表示。按问题的不同，要求目标函数实现最大化和最小化。,每一个问题变量都用一组决策变量（x1, x2, , xn）表示某一方案，这组决策变量的值代表一个具体方案，这些变量是非负且连续的。,存在一定的约束条件，这些约束条件可以用一组线性等式或线性不等式来表示。,结论：线性规划是研究在一组线性不等式或线性等式约束下，使得某一线性目标函数取最大或最小的极值问题。,二、线性规划问题（LP问题）的共同特征,9,Max(Min) Z=c1x1+c2x2+cnxn (1) a11x1+a12x2+a1nxn ( =, ) b1 a21x1+a22x2+a2nxn ( =, ) b2 s.t. (2) am1x1+am2x2+amnxn ( =, ) bm xj0, j=1,2, ，n (3) (1)目标函数；(2)约束条件；(3)决策变量非负 n变量个数； m约束行数； cj价值系数； bi右端项或限额系数； aij技术系数； xj决策变量,线性规划模型的一般形式为：,10,线性规划模型的紧缩形式,n变量个数； m约束行数； cj价值系数； bi右端项或限额系数； aij技术系数； xj决策变量,11,练习题：是否为线性规划模型？,12,1.线性不等式的几何意义 半平面,作出LP问题的可行域 作出目标函数的等值线 移动等值线到可行域边界得到最优点,2.图解法步骤,三、两变量线性规划问题的图解法,13,4x1=16,4x2=12,x1+2x2=8,x1,x2,4,8,Q1 4,Q4 3,0,例1,Q2(4,2),Z=2x1+3x2,做目标函数2x1+3x2的等值线，与阴影部分的边界相交于Q2(4,2)点，表明最优生产计划为：生产I产品4件，生产II产品2件。,Q3,14,目标函数z=ax1+bx2的值递增的方向与系数a、b有关,a0, b0,a0,X1,X2,a0, b0,a0, b0,z=ax1+bx2 目标函数等值线：ax1+bx2=k 移项 x2=-a/bx1+k/b 目标函数等值线在纵轴上的截距为k/b,15,例4,Z=36,16,例 用图解法求解线性规划问题,4x1=16,4x2=12,x1+2x2=8,x1,x2,4,8,Q1 4,Q4 3,0,Q2(4,2),Z=2x1+4x2,当Z值由小变大时，将与Q2Q3重合 Q2Q3上任意一点都是最优解 有无穷多最优解（多重解）,Q3(2,3),17,例 用图解法求解线性规划问题,可行域无界无界解 （ “无有限最优解”或“最优解无界”） 约束条件过分宽松 注意：可行域不闭合不一定就会出现无界解，这要看目标函数的性质。若目标函数是min，则有最优解。无论有无最优解，一定有可行解。,18,例 用图解法求解线性规划问题,可行域无界唯一最优解X*=(1,0)，对应于点A,19,例 用图解法求解线性规划问题,可行域无界无穷多最优解对应于点B沿着OB向右上方发出的射线上的所有点,x2,x1,x1-x2=1,B(2,1),A(1,0),-x1+2x2=0,0,20,例 用图解法求解线性规划问题,无可行解（可行域为空）,-2x1+x2=4,无最优解,21,3.图解法的作用,能解决少量问题,揭示了线性规划问题的若干规律,解的类型,可行域类型,唯一最优解,无穷多最优解,最优解无界 （无有限最优解）,无解 （不存在可行域）,非空有界,无界,空集,规律1：,22,规律2：,线性规划问题的可行域为凸集 线性规划问题凸集的顶点个数是有限的 最优解可在凸集的某顶点处达到,23,小结：图解法的基本步骤： 1在直角坐标系作出可行域S的区域 （一般是一个凸多边形） 2令目标函数值取一个已知的常数k，作等值线：c1x1+c2x2=k 3对于max问题，让目标函数值k由小变大，即让等值线进行平移，若它与可行域S最后交于一个点（一般是S的一个顶点），则该点就是所求的最优点，若与S的一条边界重合，此时边界线上的点均是最优点 4将最优点所在的两条边界线所代表的方程联立求解，即得最优解X*，把最优解X*带入目标函数，得最优值Z*=CX* 注意：若是求目标函数最小值，等值线向反方向移动,24,四、线性规划问题的标准型,1.标准型,（1）目标函数：max,（2）约束条件：等式,（3）变量约束：非负 xj0,（4）资源限量：非负bi 0,标准型的构成要素,25,2.线性规划标准型的紧缩形式,26,3.线性规划标准型的向量和矩阵表达式,矩阵式: Max Z=CTX s.t. AX=b X0,n 向量式: Max Z= cjxj j=1 n s.t. Pjxj=b j=1 xj 0, j=1,2, . ,n,27,4.所有LP问题均可化为标准型,（1）最小转换成最大,28,（2）不等式约束条件转换成等式约束条件,（3）变量约束转换,（4）把bi0转换成bi0,29,例5 化标准型,可化为,1.处理决策变量 2.处理约束条件右端 常数项 3.约束条件不等式 4.处理目标函数,30,例6 化标准型,1.处理决策变量 2.处理约束条件右端 常数项 3.约束条件不等式 4.处理目标函数,31,Max Z =x1+2x2+3x4-3x5+0x6+0x7 s.t. x1 - x2 + x4 - x5+x6 = 7 x1+x2 + x4 - x5 - x7 = 2 -3x1 -x2+3x4 -3x5 = 5 x20 , xj0, j=1,4,5,6,7,Max Z =x1+2x2+3(x4-x5)+0x6+0x7 s.t. x1 - x2 +(x4 - x5 ) +x6 = 7 x1+x2 +(x4 - x5 ) - x7 = 2 -3x1 -x2+3(x4 -x5) = 5 x20 , xj0, j=1,4,5,6,7,最终结果,中间结果,32,课堂练习,33,五、标准型LP问题解的概念,34,（1）,（2）,（3）,约束系数矩阵：,x1,x2,x3,x4,x5,例：,35,约束系数矩阵：,可能的基矩阵是A中任意三个列的组合，共10个。,36,令B = =( P1 , P2 , , Pm ) 且| B | 0 ，则称Pj (j=1,2,m) 为基向量。 与基向量Pj对应的变量xj称为基变量， 记为XB = ( x1 , x2 , , xm )T，其余的变量称为非基变量，记为XN = ( xm+1 , xm+2 , , xn ) T 。,37,38,39,B1=(P1,P2)：基,令：,XB1=(x1,x2),x1=0， x2=2,X=(0, 2, 0, 0),XB1=(0, 2),对应于B1的基解为,40,线性规划标准型问题解的关系,约束方程的 解空间,基解,可行解,非可行解,基可 行解,41,例7 Max Z =2x1+3x2 s.t. x1+ 2x28 4x1 16 4x2 12 x1, x2 0,六、可行解、基解和基可行解举例,4x1=16,4x2=12,x1+2x2=8,x1,x2,0,Z=2x1+3x2,A,B,C,D,E,F,G,H,标准型,42,例8,43,第二节 LP问题的基本理论,一、基本概念,44,判断以下图形哪些是凸集，哪些不是凸集？,返回,45,定理1 LP问题的可行域为一凸集。,二、基本定理,46,引理 线性规划问题的可行解X=(x1, x2, , xn)T是基可行解的充要条件为X的正分量所对应的系数列向量是线性独立的。,47,定理2 线性规划问题的基可行解对应于可行域的顶点。,（即：若X是LP问题的可行解，则“X是LP问题的基可行解”等价于“X是LP问题可行域顶点”）,设X是基可行解，则其对应的向量组a1,a2, ,am线性无关(mm时，有xj=xj(1)= xj(2)= 0.,48,49,50,51,定理3 若可行域有界，则LP问题的目标函数一定可以在其可行域的顶点上达到最优。,引理 若S是有界凸集，则任何一点XS可表示为S的顶点的凸组合。,52,线性规划问题的可行域是凸集(定理1)；凸集的顶点对应于基可行解(定理2)，基可行解(顶点)的个数是有限的；若线性规划有最优解，必在可行域某顶点上达到(定理3)。因此,我们可以在有限个基可行解中寻找最优解。,由线性代数知，对标准形LP问题，用枚举法可以求出所有基解，再通过观察找出其中的可行解（基可行解），进而找出最优解。但如果变量和方程较多，比如m=50，n=100，所有基解有可能达1029个，即使计算机每秒能求解1亿个这样的方程组，也需要30万亿年！因此，必须寻求有效的算法。,为加快计算速度，算法必须具有两个功能，一是每得到一个解，就来检验是否已经最优，若是停止。二是若不是最优，要保证下一步得到的解不劣于当前解。这就是线性规划的单纯形法。,53,第三节 单纯形法,基本思想,检验解的 最优性,结束,Y,旋转运算（消元运算） 确定另一个基本可行解,N,化LP问题为标准型， 确定一个初始基本可行解,化LP问题为标准型，从可行域的某个基可行解（一个顶点）开始，转换到另一个基可行解（另一个顶点），并使目标函数值得到改善，如此反复，从而求得问题的最优解。其实质是逐步迭代（逼近）法。,54,一、确定初始基可行解,Max Z=CX s.t. AX=b X0,我们首先介绍求初始基可行解的方法。 1.若给定问题标准化后（且 ）系数矩阵A中存在m个线性无关的单位列向量，则以这m个单位列向量构成的单位子矩阵作为初始基B，则 ，其余xj=0是基可行解。 2.大M法（人工变量法）,55,以x2为主元素,以x1为主元素,例 2x1+ x2+ 2x3=10 (1) 3x1+ 3x2+ x3= 6 (2),x1+ 0x2+ 5/3x3= 8 (1) 0x1+ x2 - 4/3x3= -6 (2),(2) 2/3 , (1)-(2) /2,二、旋转运算,56,三、检验数的意义,结论：如果LP问题通过单纯形法迭代到某步时，所有检验数0,则该LP问题已得到最优解。,Max Z=CX s.t. AX=b X0,若cj-CBB-1Pj=j0, 则ZZ0, Z0即为最优解. (基变量的检验数必为0),令A=(B,N), X= XB ,C=(CB,CN) XN,57,单纯形法举例,化为标准型,58,约束方程的系数矩阵,对应于B的变量x3，x4，x5为基变量，,（1）,将（1）代入目标函数后得到z=0+2x1+3x2， 令非基变量x1=x2=0.得到z=0，及一个基可行解X(0)=(0,0,8,16,12)T,59,x2=3， x5为换出变量,（3）,将（3）代入目标函数后得到z=9+2x13/4x5， 令非基变量x1=x5=0.得到z=9，及一个基可行解 X(1)=(0,3,2,16,0)T,当将x2定为换入变量后，必须从x3，x4，x5中确定一个换出变量，并保证x3，x4，x50， 当x1=0时，由（1）式得到,（2）,用高斯消元法，将x2的系数列向量变换为单位列向量，得到,60,这时目标函数的表达式是z=141.5x30.125x4，,当将x1定为换入变量后，继续利用上述方法确定换出变量，继续迭代，再得到一个基可行解X(2)=(2,3,0,8,0)T,再经过一次迭代，再得到一个基可行解X(3)=(4,2,0,0,4)T,61,对于线性规划问题：Max Z=CTX AX=b，X0，可用如下三个判别定理来判别线性规划问题是否已经获得最优解或为无界解。,判别定理1 设X为线性规划的一个基可行解，且对于一切jJ（J为非基变量的下标集）有j0，则X为线性规划的最优解。 判别定理2 设X为线性规划的一个基可行解，且对于一切jJ（J为非基变量的下标集）有j 0，同时有某个非基变量的检验数k=0( kJ)，则该线性规划有无穷多最优解。 判别定理3 设X为线性规划的一个基可行解，若有k0 ( kJ) ，且pk0，即aik 0（i=1,m），则该线性规划问题具有无界解（无最优解）。,62,一、步骤,Step 1. 化LP问题为标准型,建立初始单纯形表; Step 2. 若所有检验数0,则最优解已达到。 否则,计算 , 选取k 所对应的变量xk 为换入变量（进基变量）;最大（检验数）规则 Step 3. 计算 ,选取l 所对应的变量xl 为换出变量（出基变量）;最小比值规则 Step 4. 以alk为主元素进行旋转运算,转Step 2;,第四节 单纯形法的步骤,63,基可行解： x1=b1, x2=b2, , xm=bm , xm+1=xm+2= =xn= 0,1.初始单纯形表,c1 c2 cm cm+1 cn,c1 x1 c2 x2 cm xm,b1 b2 bm,1 0 0 a1, m+1 a1n 0 1 0 a2, m+1 a2n 0 0 1 am, m+1 amn,0 0 0 m+1 n,-CBTB-1b,64,对于上述单纯形表： （1）一个基对应一个单纯形表，且单纯形表中必须有一个初始单位基。 （2）从单纯形表中，可立即得到一个基可行解： x1=b1, x2=b2, , xm=bm , xm+1=xm+2= =xn= 0 （3）用检验数的计算公式很容易计算检验数，并可根据三个判别定理判别上述基可行解是否为最优解或线性规划问题无最优解。,65,2.换入变量（进基变量）的选择,选取 所对应的变量xk 为换入变量。,66,3.换出变量（出基变量）的选择,选取 所对应的变量xl 为换出变量。,67,4.旋转运算,ck xk,bl /alk,0 1/alk 0 al, m+1/alk1 aln/alk,b1,1 -a1k/alk 0 a1, m+1 0 a1n,bm,0 -amk/alk1 am, m+1 0 amn,68,二、实例,化为标准型,69,单纯形表算法,以4为主元素进行旋转运算，x2为换入变量，x5为换出变量,以1为主元素进行运算，x1为换入变量， x3为换出变量,0 x3 0 x4 0 x5,2 3 0 0 0,8 16 12,1 2 1 0 0 4 0 0 1 0 0 4 0 0 1,2 3 0 0 0,0,4 - 3,70,以2为主元素进行运算，x5为换入变量， x4为换出变量,此时达到最优解：X*=(4, 2)T, Max Z=14。,71,4x1=16,4x2=12,x1+2x2=8,x1,x2,4,8,4,O,三、单纯形表与图解法的对应关系,Q1,Q2,Q,Q3,图解法：,单纯形表算法：,72,对于极小化问题，其最优解的判定定理和进基变量的选取和极大化问题刚好相反，如下所示：,判别定理1 设X为线性规划的一个基可行解，且对于一切jJ（J为非基变量的下标集）有j0，则X为线性规划的最优解。 判别定理2 设X为线性规划的一个基可行解，且对于一切jJ（J为非基变量的下标集）有j0，同时有某个非基变量的检验数k=0( kJ)，则该线性规划有无穷多最优解。 判别定理3 设X为线性规划的一个基可行解，若有k0 ( kJ) ，且pk0，即aik 0（i=1,m），则该线性规划问题具有无界解（无最优解）。 在进基可行解的转换过程中，进基变量的选取原则是：minj |j 0=k，则可以确定xk为换入变量。 出基变量的选取原则不变。,73,一、人工变量法,第五节 LP问题的进一步讨论,1.大M法 2.两阶段法(了解),74,人工变量法（大M法）,Max Z=CX s.t. AX=b X0,若给定问题标准化后（b0）系数矩阵中不存在m个线性无关的单位列向量，则在某些约束条件的左端加一个非负变量Xn+i(人工变量)使得变化后的系数矩阵中恰有m个线性无关的单位列向量，并且在目标函数中减去这些人工变量与M的乘积（M是相当大正数）。对于变化后的问题，取这m个单位列向量构成的单位子矩阵为初始基，该基对应的解一定是基可行解。,75,1.大M法,加入人工变量xn+1, xn+2 ,xn+m,问题A,问题B,76,1.大M法（M为任意大的正数）,加入人工变量x6, x7,加入松弛变量x4和剩余变量x5,77,1) 人工变量的识别,2) 目标函数的处理,3) 计算(单纯形法),78,注意：本例是求最小值，所以用所有 来判别目标函数是否实现了最小化。因而换入变量xk的选取标准为,79,结果得: X*=(4,1,9,0,0,0,0) Z*=-2,（接上表）,80,1.大M法,例 用单纯形法（大M法）求解下列线性规划,加入松弛变量x3, 剩余变量x4， 人工变量x5,81,用单纯形法计算，其过程如下表所示：,虽然检验数均小于等于0，但基变量中含有非零的人工变量x5=4，所以原问题无可行解,82,1.大M法,大M法的几点结论 （1）问题B要实现极大化，必须将人工变量从基变量中换出，否则目标函数不可能实现最优； （2）若在求解问题B的过程中，已将人工变量从基变量中换出，则已得到问题A的一个基可行解，可继续求解，以获得问题A的最优解； （3）若求解问题B已得到最优解，但最优解的基变量中含有不为零的人工变量，则问题A无可行解； （4）若求解问题B已得到最优解，且最优解的基变量中不含有人工变量，则问题B的最优解就是问题A的最优解。,83,两阶段法 (将LP问题分成两个阶段来考虑),第I 阶段: 不考虑原问题是否存在可行解，给原LP问题加入人工变量，并构造仅含人工变量的目标函数和要求最小化；然后用单纯形法求解，若得W=0，则进行第二阶段计算，否则无可行解。,第II 阶段：将第一阶段得到的最终表除去人工变量，将目标函数行的系数换为原问题的系数，作为第二阶段的初始表。,84,加入松弛变量x4;剩余变量x5;人工变量x6,x7,用单纯形法求解第一阶段的结果得：,85,此时，达到第一阶段的最优解，W=0,86,由于人工变量x6 =x7=0,所以(0, 1, 1, 12, 0)T 是该线性规划问题的基可行解。于是转入第二阶段运算：,此时达到该LP问题的最优解：x1=4, x2=1, x3=9; 目标函数值Z= -2。,87,1.存在两个以上相同的最大正检验数。选择任何变量（对应最大正检验数）作为进基变量。,2.存在两个以上相同的最小比值。在下一次迭代中就有一个或几个基变量等于零。,二、单纯形法中存在的问题,如果在一个基本可行解的基变量中至少有一个分量为0，则称此基本可行解是退化的基本可行解，这样的线性规划问题称为退化的线性规划问题。,88,89,选取 x1 为换入变量；选取下标最小的 x5 为换出变量，得下表：,此时换出变量为x1，换入变量为x4，迭代后目标函数值不变。这时不同的基表示为同一顶点。,90,当线性规划问题出现退化时，用单纯形法计算就会出现所谓的循环，即多次迭代，而基从B1,B2,又返回到B1，即出现计算过程的循环，永远达不到最优解。 1955年，Beale给出了如下退化与循环的例子，即,用单纯形法求解，经过6次转换，又回到初始基可行解上，其基变量的转换次序为:(x5,x6,x7) (x1,x6,x7) (x1,x2,x7) (x3,x2,x7) (x3,x4,x7) (x5,x4,x7) (x5,x6,x7),91,解决退化的方法有： “摄动法”