线性规划与单纯形法.pptx

第二章 线性规划与单纯形法第1节 线性规划问题及其数学模型第2节 图解法第3节 解第4节 单纯形法原理及其计算步骤第5节 人工变量法第6节 小结第1页/共100页第1节 线性规划问题及其数学模型一、规划如何合理地利用有限的人力、物力、财力等资源，以便得到最好的经济效果。第2页/共100页第1节 线性规划问题及其数学模型例1：用一块边长为a的正方形铁皮做一个容器，应该如何裁剪，使做成的容器的容积最大（如下图所示）。ax第3页/共100页第1节 线性规划问题及其数学模型例1：解：设在铁皮四个角上剪去四个边长各为x的正方形 V=(a-2x)(a-2x)xmax 满足 xa/2 x0第4页/共100页第1节 线性规划问题及其数学模型例2：某企业计划生产、两种产品，都要分别在A，B，C，D四种不同设备上加工。按工艺资料规定，生产每件产品需占用各设备分别为2，1，4，0（小时），生产每件产品需占用各设备分别为2，2，0，4（小时）。已知各设备计划期内用于生产这两种产品的能力分别为12，8，16，12（小时），又知每生产一件产品，企业能获利2元，每生产一件产品，企业能获利3元。问：该企业应如何安排生产两种产品各多少件，使企业的利润收入最大。第5页/共100页第1节 线性规划问题及其数学模型例2：解：设、两种产品在计划期内的产量分别为x1、x2 z=2x1+3x2max 2x1+2x212 x1+2x28 满足 4x116 4x212 x1，x20表示形式第6页/共100页第1节 线性规划问题及其数学模型二、数学规划研究在一些给定的条件下，求所考察函数在某种意义下的极值问题。第7页/共100页第1节 线性规划问题及其数学模型特征（1）决策变量（2）约束条件（3）目标函数第8页/共100页第1节 线性规划问题及其数学模型三、线性规划问题特征（三要素）（1）决策变量：问题中的未知量（2）目标函数：问题要达到的目标（最大或最小），表示为决策变量的线性函数（3）约束条件：表示为含决策变量的一组互不矛盾的线性等式或线性不等式的函数约束和决策变量的非负约束第9页/共100页第1节 线性规划问题及其数学模型V=(a-2x)(a-2x)xmax xa/2 x0z=2x1+3x2max 2x1+2x212 x1+2x28 4x116 4x212 x1，x20第10页/共100页第1节 线性规划问题及其数学模型线性规划问题数学模型的形式（1）一般形式第11页/共100页第1节 线性规划问题及其数学模型（2）简写形式（3）向量形式 （4）矩阵形式第12页/共100页第1节 线性规划问题及其数学模型例3：写出例2数学模型的一般形式和矩阵形式。一般形式 矩阵形式 max z=2x1+3x2 2x1+2x212 x1+2x28 4x116 4x212 x1，x20解第13页/共100页第1节 线性规划问题及其数学模型四、线性规划数学模型的标准形式（标准型）目标函数求最大值函数约束条件全为等式决策变量全为非负函数约束条件右端项全为非负第14页/共100页第1节 线性规划问题及其数学模型五、线性规划的非标准型如何转化为标准型目标函数求最小值：令z-z函数约束条件为不等式：在函数约束条件左端加非负的松弛变量 ：在函数约束条件左端减非负的松弛变量 松弛变量在目标函数中的系数全为0决策变量为负值：令xj-xj，xj0决策变量取值无约束：令xj xj-xj，xj0，xj0函数约束条件右端项（bi）为负值：函数约束条件两端同乘-1第15页/共100页第1节 线性规划问题及其数学模型要求：将下列线性规划问题转化为标准型。例4：min z=x1+2x2+3x3 -2x1+x2+x39 -3x1+x2+2x34 3x1-2x2-3x3=-6 x10，x20，x3取值无约束第16页/共100页第1节 线性规划问题及其数学模型例4：解：令 max z=x1-2x2-3x3+3x3+0 x4+0 x5 2x1+x2+x3-x3+x4=9 3x1+x2+2x3-2x3-x5=4 3x1+2x2+3x3-3x3=6 x1，x2，x3，x3，x4，x50第17页/共100页第1节 线性规划问题及其数学模型例5：min z=-x1+2x2-3x3 x1+x2+x37 x1-x2+x32 -3x1+x2+2x3=5 x1，x20，x3无约束第18页/共100页第1节 线性规划问题及其数学模型例5：解：令 max z=x1-2x2-3x3+3x3 x1+x2+x3-x3+x4=7 x1-x2+x3-x3-x5=2 -3x1+x2+2x3-2x3=5 x1，x2，x3，x3，x4，x50第19页/共100页第1节 线性规划问题及其数学模型例6：max z=2x1+3x2+5x3 x1+x2-x3-5 -6x1+7x2-9x3=16 19x1-7x25x313 x1，x20，x3无约束第20页/共100页第1节 线性规划问题及其数学模型例6：解：令 max z=2x1+3x2+5x3-5x3 -x1-x2+x3-x3+x4=5 -6x1+7x2-9x3+9x3=16 19x1-7x2+5x3-5x3+x5=13 -19x1+7x2-5x3+5x3+x6=13 x1，x2，x3，x3，x4，x5，x60第21页/共100页作业2-1作业2-1：将下列线性规划问题化为标准型。1、min z=5x1-2x2+4x3-3x4 -x1+2x2-x3+4x4=-2 -x1+3x2+x3+x414 2x1-x2+3x3-x42 x1无约束，x20，x3，x402、min z=x1+2x2+4x3 2x1+x2+3x320 3x1+x2+4x325 x1，x20，x30第22页/共100页第2节 解线性规划问题数学模型的标准型（以一般形式表示）第23页/共100页第2节 解一、线性规划问题解的概念可行解：满足函数约束条件和非负约束条件的解，全部可行解的集合称为可行域最优解：使目标函数达到最大值的可行解，对应的目标函数值称为最优值第24页/共100页第2节 解基：设A是约束方程组的mn阶系数矩阵，B是矩阵A中mm阶非奇异子矩阵，称B是线性规划问题的一个基基向量：基B中每一个列向量Pj非基向量：A中其余列向量Pj（不在B中）基变量：与基向量Pj对应的决策变量xj非基变量：与非基向量对应的决策变量基解基可行解：满足非负约束条件的基解可行基：对应于基可行解的基克莱姆法则非奇异矩阵解的关系第25页/共100页第2节 解非奇异矩阵：行列式不等于0的矩阵。克莱姆法则：如果线性方程组 a11x1+a12x2+a1mxm=b1 a21x1+a22x2+a2mxm=b2 am1x1+am2x2+ammxm=bm 的系数行列式不等于0，则方程组有唯一解。第26页/共100页第2节 解二、线性规划问题解的关系最优解第27页/共100页第2节 解例7：写出例2的标准型，并指出基、基变量、基解、基可行解和可行基。第28页/共100页第2节 解例7：标准型max z=2x1+3x2 2x1+2x212 x1+2x28 4x116 4x212 x1，x20 max z=2x1+3x2 2x1+2x2+x3=12 x1+2x2+x4=8 4x1+x5=16 4x2+x6=12 x1-60图解法第29页/共100页第2节 解例8：求下述线性规划的所有基解、基可行解及最优解。max z=3x1+x2+3x3 x1+x2+x32 x1+2x2+4x36 x1，x2，x30第30页/共100页作业2-2作业2-2：求下列线性规划的所有基解、基可行解及最优解。1、max z=2x1+3x2+4x3+7x4 2x1+3x2-x3-4x48 -x1+2x2-6x3+7x43 x1，x2，x3，x402、max z=-5x1+2x2-3x3+6x4 x1+2x2+3x3+4x47 2x1+x2+x3+2x43 x1，x2，x3，x40第31页/共100页第3节 图解法一、图解法适用条件：适用于求解只有两个决策变量的线性规划问题特点（1）不必将线性规划问题转化为标准型（2）直观性强，计算方便第32页/共100页第3节 图解法例9：用图解法求解下述线性规划问题。max z=2x1+3x2 x1+2x28 4x116 4x212 x1，x20第33页/共100页第3节 图解法例9：标出约束条件(0,0)(0,3)(2,3)(4,2)(4,0)第34页/共100页第3节 图解法例9：标出目标函数目标函数z唯一最优解第35页/共100页第3节 图解法二、图解法的求解步骤建立 二维坐标系将约束条件表示在坐标系中，以确立可行域画出每个函数约束的约束边界，用原点判断直线的哪一边是约束条件所允许的找出所有约束条件都同时满足的区域，即可行域将目标函数绘制在坐标系中，并标出变化的方向给定目标函数一个特定的值k，画出目标函数特定线，当k变化时，目标函数特定线将平行移动对于目标函数最大（小）化的问题，找出目标函数增加（减少）的方向，目标函数最后离开可行域的点是最优解确定最优解第36页/共100页第3节 图解法三、图解法解的类型唯一最优解：仅有一点使目标函数值取得最大（小）值无穷多（多重）最优解：线段（射线）上任意一点都使目标函数值取得相同的最大（小）值无界解：可行域无界，目标函数值可以增大到无穷大无可行解：可行域为空集无界解和无可行解统称为无最优解第37页/共100页第3节 图解法要求：用图解法求解下列线性规划问题。例10：max z=2x1+4x2 x1+2x28 4x116 4x212 x1，x20第38页/共100页第3节 图解法例10：目标函数 max z=2x1+4x2 z多重最优解第39页/共100页第3节 图解法例11：max z=2x1+3x2 4x116 x1，x20无界解第40页/共100页第3节 图解法例12：max z=2x1+3x2 2x1+2x212 x1+2x214 x1，x20无可行解第41页/共100页第3节 图解法四、图解法解的特点当可行域非空集时，可行域必是有界或无界凸多边形。（凸集：集合C中任意两个点a和b，其连线上所有点也必为集合C中的点。）若可行域有界，则目标函数一定可以在可行域的顶点上达到最优；若可行域无界，则可能无最优解，也可能有最优解，若有也必定在某顶点上达到。第42页/共100页第3节 图解法线性规划问题的每个基可行解对应可行域的一个顶点。线性规划问题的最优解在顶点上达到，则一定存在一个基可行解是最优解。若有唯一最优解，则一定在可行域的某个顶点处得到；若有两个顶点同时达到最优解，则两个顶点之间线段上的任意一点都是最优解，既有无穷多最优解。线性规划问题有最优解，则解题思路：找出可行域的顶点，计算顶点处的目标函数值，比较各顶点的目标函数值，值最大（小）的顶点为最优解的点或最优解的点之一。第43页/共100页第3节 图解法例13：下列哪一个图是凸集？A BC D凸多边形第44页/共100页第3节 图解法例9图解：目标函数z第45页/共100页第3节 图解法例10图解：目标函数 max z=2x1+4x2 z顶点最优第46页/共100页第3节 图解法要求：用图解法求解下列线性规划问题。例14：min z=2x1-x2 -2x1+x22 x1-2x21 x1，x20无界可行域第47页/共100页第3节 图解法例15：1、max z=x1+x2 -2x1+x24 x1-x22 x1，x20 2、max z=x1+2x2 x1+2x28 4x116 4x212 x1，x20第48页/共100页第3节 图解法例15：2、(0,0)(0,3)(2,3)(4,2)(4,0)第49页/共100页作业2-3作业2-3：用图解法求解下列线性规划问题。1、max z=50 x1+100 x2 x1+x2300 2x1+x2400 x2250 x1，x202、max z=4x1+8x2 2x1+2x210 -x1+x2 8 x1，x203、max z=3x1+9x2 x1+3x222 -x1+x24 x26 2x1-5x20 x1，x204、max z=2x1+2x2 x1-x2 -1 -0.5x1+x2 2 x1，x20第50页/共100页第4节 单纯形法原理及其计算步骤例16：求解下述线性规划问题。max z=2x1+3x2 x1+2x28 4x116 4x212 x1，x20第51页/共100页第4节 单纯形法原理及其计算步骤例16：解：方法一：图解法z*=2x1+3x2=14(0,3)(2,3)(4,0)(0,0)Q4Q3Q1X*第52页/共100页第4节 单纯形法原理及其计算步骤例16：解：方法二：确定所有基解、基可行解及最优解转化为标准型 max z=2x1+3x2 x1+2x2+x3=8 4x1+x4=16 4x2+x5=12 x1-50第53页/共100页第4节 单纯形法原理及其计算步骤例16：解：方法三：确定部分基可行解及最优解转化为标准型 max z=2x1+3x2 x1+2x2+x3=8 4x1+x4=16 4x2+x5=12 x1-50第54页/共100页第4节 单纯形法原理及其计算步骤一、单纯形法的解题思路从某一基可行解开始，转化到另一个相邻的基可行解，并且使相应的目标函数值有改进。即从可行域的一个顶点沿约束边界转换到可行域的另一个相邻的且使目标函数值有改进的顶点，直到目标函数值到达最优时的顶点为止。第55页/共100页第4节 单纯形法原理及其计算步骤两个基可行解相邻：在基变量集合中，除了一个基变量以外，其他基变量全是相同的，只是数值可能不相同而已。第56页/共100页第4节 单纯形法原理及其计算步骤二、单纯形法的含义单纯形法是一种迭代算法，首先找到一个初始基可行解，然后判断它是否为最优解，如果是就停止迭代，否则，按照一定的法则，再找到一个更好且与当前基可行解相邻的基可行解，再进行判断，直到找不到更好的基可行解或判断问题无解为止。第57页/共100页第4节 单纯形法原理及其计算步骤三、单纯形法的解题步骤1、找出初始可行基，确定初始基可行解，建立初始单纯形表。第58页/共100页第4节 单纯形法原理及其计算步骤例：线性规划问题数学模型的某种标准形式第59页/共100页第4节 单纯形法原理及其计算步骤初始单纯形表c1 cmcm+1cncBxBbx1 xmxm+1xnc1x1b110a1,m+1 a1,nc2x2b200a2,m+1a2,n cmxmbm01am,m+1am,n00第60页/共100页第4节 单纯形法原理及其计算步骤2、检验各非基变量xj（j=m+1，m+2，n）的检验数j，若j0，则已得最优解，停止计算，否则转入3。3、在j0（j=m+1，m+2，n）中，若有某个k对应的xk的系数列向量Pk0，则此线性规划问题存在无界解，停止计算，否则转入4。4、根据 ，确定xk为换入变量，通过 ，计算确定xl为换出变量，转入5。第61页/共100页第4节 单纯形法原理及其计算步骤5、以alk为主元素进行迭代（高斯消去法），把xk所对应的列向量 将xB列中xl的换为xk，得到新的单纯形表，重复25，直至终止。变换为单纯形法求解例16第62页/共100页第4节 单纯形法原理及其计算步骤高斯消去法的基本代数运算：一行乘以一个数一行乘上一个数加到另外一行中去第63页/共100页第4节 单纯形法原理及其计算步骤例16：解：方法四：单纯形法转化为标准型 max z=2x1+3x2 x1+2x2+x3=8 4x1+x4=16 4x2+x5=12 x1-50第64页/共100页第4节 单纯形法原理及其计算步骤例17：用单纯形法求解下述线性规划问题。max z=2x1+x2 5x215 6x1+2x224 x1+x25 x1，x20第65页/共100页第4节 单纯形法原理及其计算步骤例17：解：转化为标准型 max z=2x1+x2 5x2+x3=15 6x1+2x2+x4=24 x1+x2+x5=5 x1，x2，x3，x4，x50第66页/共100页作业2-4作业2-4：用单纯形法求解下列线性规划问题。1、max z=5x1+2x2+3x3-x4+x5 x1+2x2+2x3+x4=8 3x1+4x2+x3+x5=7 x1，x2，x3，x4，x502、min z=-5x1-4x2 x1+2x26 2x1-x24 5x1+3x215 x1，x20第67页/共100页第5节 人工变量法例18：求解下述线性规划问题。max z=-3x1+x3 x1+x2+x34 -2x1+x2-x31 3x2+x3=9 x1，x2，x30第68页/共100页第5节 人工变量法例18：解：标准型第69页/共100页第5节 人工变量法标准型人为构造单位矩阵第70页/共100页第5节 人工变量法例18：线性规划问题的最后形式第71页/共100页第5节 人工变量法一、人工变量法的解题思路线性规划问题中不存在现成的可行基，为了求一个初始可行基和初始基可行解，在每个约束方程中人为地加上一个变量（人工变量），使约束方程组的系数矩阵中产生初始基。第72页/共100页第5节 人工变量法二、人工变量法的含义为了确保引入人工变量以后新的线性规划问题与原线性规划问题求解的一致性：在最优解中人工变量取值必须为零；令人工变量的系数为-M（M0，表示充分大的数），“-M”称为“罚因子”，表示只要人工变量取值大于零，目标函数就不可能达到最大值。第73页/共100页第5节 人工变量法三、人工变量法的解题步骤将原问题转化为标准型对或的约束条件添加人工变量，直至构造出单位矩阵，且人工变量在目标函数中的系数为-M，建立初始单纯形表按照单纯形法的解题步骤25求解人工变量法求解例18第74页/共100页第5节 人工变量法例18：解：第75页/共100页第5节 人工变量法例19：用人工变量法求解下述线性规划问题。max z=2x1+x2 x1+x22 2x1+2x26 x1，x20第76页/共100页第5节 人工变量法例19：解：标准型并添加人工变量 max z=2x1+x2-Mx5 x1+x2+x3=2 2x1+2x2-x4+x5=6 x1，x2，x3，x4，x50第77页/共100页第5节 人工变量法小结（1）将线性规划化为标准型后，对或的约束条件添加人工变量（若约束条件系数矩阵A中已有k个单位列向量，只要引入m-k个人工变量，使它们与原来的k个单位列向量合成单位矩阵）（2）在最优解中，若人工变量大于0，则原问题无可行解第78页/共100页作业2-5作业2-5：用人工变量法求解下列线性规划问题。1、max z=3x1-x2-x3 x1-2x2+x311 -4x1+x2+2x33 2x1-x3=-1 x1，x2，x302、min z=-x1-3x2+x3 x1+x2+2x3+x4=4 -x1+x3-x5=4 x3-x6=3 x1，x2，x3，x4，x5，x60第79页/共100页第6节 小结第80页/共100页第6节 小结二、单纯形表中解的表示形式1、唯一最优解：最终单纯形表中，所有非基变量检验数j02、无穷多最优解：最终单纯形表中，某非基变量检验数j03、无界解：某检验数j0对应变量的系数列向量Pk04、无可行解：线性规划问题中添加人工变量后，最终单纯形表中，基变量中含有非零的人工变量（0）第81页/共100页第6节 小结5、退化现象：用规则确定换出变量时，出现两个以上相同的最小比值，使下一个单纯形表中出现一个或多个基变量等于零。退化基可行解：一个或几个基变量取值0的基可行解退化基可行解出现的原因：模型中存在多余的约束，使多个基可行解对应同一顶点第82页/共100页第6节 小结退化基可行解的处理规则：出现退化基可行解，可能导致从某个基开始，经过若干次迭代后又回到原来的基，即单纯形法出现了循环，永远达不到最优解，导致计算失败。为避免出现死循环，法则如下：选择换入变量时，若有几个正的检验数具有相同的最大值，则选择下标最小的对应的非基变量作为换入变量选择换出变量时，若按规则计算，有几个比值同时达到最小，则选择下标最小的对应的基变量作为换出变量第83页/共100页第6节 小结例20：下列表格是求线性规划问题的单纯形表，试说明解的情况。1、最终表 2 3 0 0 0CBxBb x1 x2 x3 x4 x5203x1x5x2442 1 0 0 1/4 0 0 0 -2 1/2 1 0 1 1/2 -1/8 0 0 0 -3/2 -1/8 0第84页/共100页第6节 小结2、最终表 3 2 -1 0 0 0CBxBb x1 x2 x3 x4 x5 x6023x4x2x129/56/521/5 0 0 -1 1 -1/5 8/5 0 1 1 0 1/5 -3/5 1 0 0 0 1/5 2/5 0 0 -3 0 -1 0第85页/共100页第6节 小结3、中间表（最终表）4 5 0 0 0CBxBb x1 x2 x3 x4 x5000 x3x4x5723 4 -1 1 0 0-1 -5 0 1 0 7 -3 0 0 1 4 5 0 0 0第86页/共100页第6节 小结4、中间表（最终表）4 3 0 0 0CBxBb x1 x2 x3 x4 x5000 x3x4x5723 4 -1 1 0 0-1 -5 0 1 0 7 -3 0 0 1 4 3 0 0 0第87页/共100页第6节 小结5、最初表 3 3 2 0 0CBxBb x1 x2 x3 x4 x500 x4x512-1 3 -1 1 0 2 -1 1 0 1 3 3 2 0 0第88页/共100页第6节 小结6、中间表 2 3 0 0 0 0CBxBb x1 x2 x3 x4 x5 x60203x3x1x5x22283 0 0 1 -2 0 1/2 1 0 0 1 0 -1/2 0 0 0 -4 1 2 0 1 0 0 0 1/4 0 0 0 -2 0 1/4第89页/共100页第6节 小结三、单纯形法对给定的线性规划问题，首先化为标准型，选取或构造一个单位矩阵作为基矩阵，求出初始基可行解并列出初始单纯形表。（若线性规划问题的标准型为目标函数最小化，则最优解判别规则为：所有检验数j0）第90页/共100页单纯形法计算步骤框图第91页/共100页第6节 小结例21：用单纯形法求解下述线性规划问题，并说明解的情况。max z=2.5x1+x2 3x1+5x215 5x1+2x210 x1，x20第92页/共100页第6节 小结例21：解：max z=2.5x1+x2 3x1+5x2+x3=15 5x1+2x2+x4=10 x1，x2，x3，x40第93页/共100页作业2-6作业2-6：求解下列线性规划问题，并说明解的情况。1、max z=6x1+4x2 -x1+2x24 3x1+2x214 2x1-x24 x1，x202、max z=2x1-x2+2x3 x1+x2+x36 -2x1+x32 2x2-x30 x1，x2，x30第94页/共100页第6节 小结例22：下表为求某最大化线性规划问题的最终单纯形表，其中x4，x5为松弛变量，试写出该问题的最优解。b x1 x2 x3 x4 x524 0 -1 1 3 1 1 -1 0 -1 0 0 -3 0 -3 -1第95页/共100页第6节 小结例23：某线性规划问题的标准型为 max z=CX AX=b X0其最终单纯形表如下表，其中x4，x5为对应于初始单位矩阵的松弛变量，且z8，试利用上表求c1，c2，c3，c4，c5。c1 c2 c3 c4 c5CBxBb x1 x2 x3 x4 x5c1c2x1x212 1 0 -1 3 -1 0 1 2 -1 1 0 0 -3 -3 -1第96页/共100页第6节 小结例24：在给出的某个求最大值线性规划问题的最终单纯形表中（如下表），当a1，a2，c1，c2，d为何值时，现有解为唯一最优解；现有解为最优解，并有无穷多最优解；存在可行解，但目标函数值无界。c1 c2 0 0 0 xBb x1 x2 x3 x4 x5x3x4x5d23 4 a1 1 0 0-1 -5 0 1 0 a2 -3 0 0 1第97页/共100页第6节 小结例25：某一最大线性规划问题在单纯形法计算时得到下表，其中a，b，c，d，e，f是未知数，原问题中要求各变量均非负。问a，b，c，d，e，f应满足什么条件，有下面各解成立？是非可行基解；是唯一最优解；有无穷多最优解；是退化基可行解；无界解；是可行解但非最优解，只有x1可以进基且出基变量必为第3个变量。xBb x1 x2 x3 x4 x5 x6x3x4x6f23 2 c 1 0 e 0-1 -5 0 1 -1 0 a -3 0 0 -4 1 b d 0 0 -3 0第98页/共100页作业2-7作业2-7：线性规划的目标函数是max z，在用单纯形法求解的过程中得到下表，其中a，b为常数，部分数据有缺失。要求：1、在所有？处填上适当的数（其中含参数a，b）；2、判断以下四种情况在什么时候成立，并简要说明理由：此解为最优解，试写出最优解和目标函数值；此解为最优解，且有无穷多最优解；此问题有无界解；此解不是最优解，且能用单纯形法得到下一个基可行解。2 5 8 0 0 0CBxBB x1 x2 x3 x4 x5 x6？x6x2x420b8 0？3？0？a？1/2？-2？-1？1？-2？第99页/共100页感谢您的观看！第100页/共100页