线性规划与单纯形法.ppt

第二章 线性规划与单纯形法,第二章 线性规划与单纯形法,第1节 线性规划问题及其数学模型 第2节 图解法 第3节 解 第4节 单纯形法原理及其计算步骤 第5节 人工变量法 第6节 小结,第1节 线性规划问题及其数学模型,一、规划 如何合理地利用有限的人力、物力、财力等资源，以便得到最好的经济效果。,第1节 线性规划问题及其数学模型,例1：用一块边长为a的正方形铁皮做一个容器，应该如何裁剪，使做成的容器的容积最大（如下图所示）。,例1： 解：设在铁皮四个角上剪去四个边长各为x的正方形 V=(a-2x)(a-2x)xmax 满足 xa/2 x0,第1节 线性规划问题及其数学模型,例2：某企业计划生产、两种产品，都要分别在A，B，C，D四种不同设备上加工。按工艺资料规定，生产每件产品需占用各设备分别为2，1，4，0（小时），生产每件产品需占用各设备分别为2，2，0，4（小时）。已知各设备计划期内用于生产这两种产品的能力分别为12，8，16，12（小时），又知每生产一件产品，企业能获利2元，每生产一件产品 ，企业能获利3元。问：该企业应如何安排生产两种产品各多少件，使企业的利润收入最大。,第1节 线性规划问题及其数学模型,例2： 解：设、两种产品在计划期内的产量分别为x1、x2 z =2x1+3x2max 2x1+2x212 x1+2x28 满足 4x116 4x212 x1，x20,表示形式,第1节 线性规划问题及其数学模型,二、数学规划 研究在一些给定的条件下，求所考察函数在某种意义下的极值问题。,第1节 线性规划问题及其数学模型,特征 （1）决策变量 （2）约束条件 （3）目标函数,第1节 线性规划问题及其数学模型,三、线性规划问题 特征（三要素） （1）决策变量：问题中的未知量 （2）目标函数：问题要达到的目标（最大或最小），表示为决策变量的线性函数 （3）约束条件：表示为含决策变量的一组互不矛盾的线性等式或线性不等式的函数约束和决策变量的非负约束,第1节 线性规划问题及其数学模型,V=(a-2x)(a-2x)xmax xa/2 x0 z =2x1+3x2max 2x1+2x212 x1+2x28 4x116 4x212 x1，x20,第1节 线性规划问题及其数学模型,线性规划问题数学模型的形式 （1）一般形式,第1节 线性规划问题及其数学模型,（2）简写形式 （3）向量形式 （4）矩阵形式,第1节 线性规划问题及其数学模型,例3：写出例2数学模型的一般形式和矩阵形式。 一般形式 矩阵形式 max z =2x1+3x2 2x1+2x212 x1+2x28 4x116 4x212 x1，x20,解,第1节 线性规划问题及其数学模型,四、线性规划数学模型的标准形式（标准型） 目标函数求最大值 函数约束条件全为等式 决策变量全为非负 函数约束条件右端项全为非负,第1节 线性规划问题及其数学模型,五、线性规划的非标准型如何转化为标准型 目标函数求最小值：令z-z 函数约束条件为不等式： ：在函数约束条件左端加非负的松弛变量 ：在函数约束条件左端减非负的松弛变量 松弛变量在目标函数中的系数全为0 决策变量为负值：令xj-xj， xj0 决策变量取值无约束： 令xj xj- xj，xj0， xj0 函数约束条件右端项（bi）为负值：函数约束条件两端同乘-1,第1节 线性规划问题及其数学模型,要求：将下列线性规划问题转化为标准型。 例4：min z =x1+2x2+3x3 -2x1+x2+x39 -3x1+x2+2x34 3x1-2x2-3x3=-6 x10，x20，x3取值无约束,第1节 线性规划问题及其数学模型,例4： 解：令 max z=x1-2x2-3x3+3x3+0x4+0x5 2x1+x2+x3-x3+x4=9 3x1+x2+2x3-2x3-x5=4 3x1+2x2+3x3-3x3=6 x1，x2，x3，x3，x4，x50,第1节 线性规划问题及其数学模型,例5： min z =-x1+2x2-3x3 x1+x2+x37 x1-x2+x32 -3x1+x2+2x3=5 x1，x20，x3无约束,第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,第1节 线性规划问题及其数学模型,例6： max z =2x1+3x2+5x3 x1+x2-x3-5 -6x1+7x2-9x3=16 19x1-7x25x313 x1，x20，x3无约束,第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,作业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，x40 2、 min z =x1+2x2+4x3 2x1+x2+3x320 3x1+x2+4x325 x1，x20，x30,第2节 解,线性规划问题数学模型的标准型（以一般形式表示）,第2节 解,一、线性规划问题解的概念 可行解：满足函数约束条件和非负约束条件的解，全部可行解的集合称为可行域 最优解：使目标函数达到最大值的可行解，对应的目标函数值称为最优值,第2节 解,基：设A是约束方程组的mn阶系数矩阵，B是矩阵A中mm阶非奇异子矩阵，称B是线性规划问题的一个基 基向量：基B中每一个列向量Pj 非基向量：A中其余列向量Pj（不在B中） 基变量：与基向量Pj对应的决策变量xj 非基变量：与非基向量对应的决策变量 基解 基可行解：满足非负约束条件的基解 可行基：对应于基可行解的基,克莱姆法则,非奇异矩阵,解的关系,第2节 解,非奇异矩阵：行列式不等于0的矩阵。 克莱姆法则：如果线性方程组 a11x1+a12x2+a1mxm=b1 a21x1+a22x2+a2mxm=b2 am1x1+am2x2+ammxm=bm 的系数行列式不等于0，则方程组有唯一解。,第2节 解,二、线性规划问题解的关系,第2节 解,例7：写出例2的标准型，并指出基、基变量、基解、基可行解和可行基。,第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,图解法,第2节 解,例8：求下述线性规划的所有基解、基可行解及最优解。 max z =3x1+x2+3x3 x1+x2+x32 x1+2x2+4x36 x1，x2，x30,作业2-2,作业2-2：求下列线性规划的所有基解、基可行解及最优解。 1、 max z =2x1+3x2+4x3+7x4 2x1+3x2-x3-4x48 -x1+2x2-6x3+7x43 x1，x2，x3，x40 2、 max z =-5x1+2x2-3x3+6x4 x1+2x2+3x3+4x47 2x1+x2+x3+2x43 x1，x2，x3，x40,第3节 图解法,一、图解法 适用条件：适用于求解只有两个决策变量的线性规划问题 特点 （1）不必将线性规划问题转化为标准型 （2）直观性强，计算方便,第3节 图解法,例9：用图解法求解下述线性规划问题。 max z =2x1+3x2 x1+2x28 4x116 4x212 x1，x20,第3节 图解法,例9： 标出 约束 条件,第3节 图解法,例9： 标出 目标 函数,唯一最优解,第3节 图解法,二、图解法的求解步骤 建立 二维坐标系 将约束条件表示在坐标系中，以确立可行域 画出每个函数约束的约束边界，用原点判断直线的哪一边是约束条件所允许的 找出所有约束条件都同时满足的区域，即可行域 将目标函数绘制在坐标系中，并标出变化的方向 给定目标函数一个特定的值k，画出目标函数特定线，当k变化时，目标函数特定线将平行移动 对于目标函数最大（小）化的问题，找出目标函数增加（减少）的方向，目标函数最后离开可行域的点是最优解 确定最优解,第3节 图解法,三、图解法解的类型 唯一最优解：仅有一点使目标函数值取得最大（小）值 无穷多（多重）最优解：线段（射线）上任意一点都使目标函数值取得相同的最大（小）值 无界解：可行域无界，目标函数值可以增大到无穷大 无可行解：可行域为空集 无界解和无可行解统称为无最优解,第3节 图解法,要求：用图解法求解下列线性规划问题。 例10： max z =2x1+4x2 x1+2x28 4x116 4x212 x1，x20,第3节 图解法,例10：,多重最优解,第3节 图解法,例11： max z =2x1+3x2 4x116 x1，x20,无界解,第3节 图解法,例12： max z =2x1+3x2 2x1+2x212 x1+2x214 x1，x20,无可行解,第3节 图解法,四、图解法解的特点 当可行域非空集时，可行域必是有界或无界凸多边形。 （凸集：集合C中任意两个点a和b，其连线上所有点也必为集合C中的点。） 若可行域有界，则目标函数一定可以在可行域的顶点上达到最优；若可行域无界，则可能无最优解，也可能有最优解，若有也必定在某顶点上达到。,第3节 图解法,线性规划问题的每个基可行解对应可行域的一个顶点。线性规划问题的最优解在顶点上达到，则一定存在一个基可行解是最优解。若有唯一最优解，则一定在可行域的某个顶点处得到；若有两个顶点同时达到最优解，则两个顶点之间线段上的任意一点都是最优解，既有无穷多最优解。 线性规划问题有最优解，则解题思路：找出可行域的顶点，计算顶点处的目标函数值，比较各顶点的目标函数值，值最大（小）的顶点为最优解的点或最优解的点之一。,第3节 图解法,例13：下列哪一个图是凸集？ A B C D,凸多边形,第3节 图解法,例9 图解：,z,第3节 图解法,例10 图解：,顶点最优,第3节 图解法,要求：用图解法求解下列线性规划问题。 例14： min z =2x1-x2 -2x1+x22 x1-2x21 x1，x20,无界可行域,第3节 图解法,例15：1、 max z =x1+x2 -2x1+x24 x1-x22 x1，x20 2、 max z =x1+2x2 x1+2x28 4x116 4x212 x1，x20,第3节 图解法,例15： 2、,作业2-3,作业2-3：用图解法求解下列线性规划问题。 1、 max z =50x1+100x2 x1+x2300 2x1+x2400 x2250 x1，x20 2、 max z =4x1+8x2 2x1+2x210 -x1+x2 8 x1，x20,3、max z =3x1+9x2 x1+3x222 -x1+x24 x26 2x1-5x20 x1，x20 4、max z =2x1+2x2 x1-x2 -1 -0.5x1+x2 2 x1，x20,第4节 单纯形法原理及其计算步骤,例16：求解下述线性规划问题。 max z =2x1+3x2 x1+2x28 4x116 4x212 x1，x20,第4节 单纯形法原理及其计算步骤,例16：解： 方法一： 图解法,第4节 单纯形法原理及其计算步骤,例16：解： 方法二：确定所有基解、基可行解及最优解 转化为标准型 max z =2x1+3x2 x1+2x2+x3=8 4x1+x4=16 4x2+x5=12 x1-50,第4节 单纯形法原理及其计算步骤,例16：解： 方法三：确定部分基可行解及最优解 转化为标准型 max z =2x1+3x2 x1+2x2+x3=8 4x1+x4=16 4x2+x5=12 x1-50,第4节 单纯形法原理及其计算步骤,一、单纯形法的解题思路 从某一基可行解开始，转化到另一个相邻的基可行解，并且使相应的目标函数值有改进。即从可行域的一个顶点沿约束边界转换到可行域的另一个相邻的且使目标函数值有改进的顶点，直到目标函数值到达最优时的顶点为止。,第4节 单纯形法原理及其计算步骤,两个基可行解相邻： 在基变量集合中，除了一个基变量以外，其他基变量全是相同的，只是数值可能不相同而已。,第4节 单纯形法原理及其计算步骤,二、单纯形法的含义 单纯形法是一种迭代算法，首先找到一个初始基可行解，然后判断它是否为最优解，如果是就停止迭代，否则，按照一定的法则，再找到一个更好且与当前基可行解相邻的基可行解，再进行判断，直到找不到更好的基可行解或判断问题无解为止。,第4节 单纯形法原理及其计算步骤,三、单纯形法的解题步骤 1、找出初始可行基，确定初始基可行解，建立初始单纯形表。,第4节 单纯形法原理及其计算步骤,例：线性规划问题数学模型的某种标准形式,第4节 单纯形法原理及其计算步骤,初始单纯形表,第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。,第4节 单纯形法原理及其计算步骤,5、以alk为主元素进行迭代（高斯消去法），把xk所对应的列向量 将xB列中xl的换为xk，得到新的单纯形表，重复25，直 至终止。,单纯形法求解例16,第4节 单纯形法原理及其计算步骤,高斯消去法的基本代数运算： 一行乘以一个数 一行乘上一个数加到另外一行中去,第4节 单纯形法原理及其计算步骤,例16：解： 方法四：单纯形法 转化为标准型 max z =2x1+3x2 x1+2x2+x3=8 4x1+x4=16 4x2+x5=12 x1-50,第4节 单纯形法原理及其计算步骤,例17：用单纯形法求解下述线性规划问题。 max z =2x1+x2 5x215 6x1+2x224 x1+x25 x1，x20,第4节 单纯形法原理及其计算步骤,例17：解：转化为标准型 max z =2x1+x2 5x2+x3=15 6x1+2x2+x4=24 x1+x2+x5=5 x1，x2，x3，x4，x50,作业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，x50 2、 min z =-5x1-4x2 x1+2x26 2x1-x24 5x1+3x215 x1，x20,第5节 人工变量法,例18：求解下述线性规划问题。 max z =-3x1+x3 x1+x2+x34 -2x1+x2 -x31 3x2+x3=9 x1，x2，x30,第5节 人工变量法,例18： 解：标准型,第5节 人工变量法,第5节 人工变量法,例18：线性规划问题的最后形式,第5节 人工变量法,一、人工变量法的解题思路 线性规划问题中不存在现成的可行基，为了求一个初始可行基和初始基可行解，在每个约束方程中人为地加上一个变量（人工变量），使约束方程组的系数矩阵中产生初始基。,第5节 人工变量法,二、人工变量法的含义 为了确保引入人工变量以后新的线性规划问题与原线性规划问题求解的一致性： 在最优解中人工变量取值必须为零； 令人工变量的系数为-M（M0，表示充分大的数），“-M”称为“罚因子”，表示只要人工变量取值大于零，目标函数就不可能达到最大值。,第5节 人工变量法,三、人工变量法的解题步骤 将原问题转化为标准型 对或的约束条件添加人工变量，直至构造出单位矩阵，且人工变量在目标函数中的系数为-M，建立初始单纯形表 按照单纯形法的解题步骤25求解,人工变量法求解例18,第5节 人工变量法,例18： 解：,第5节 人工变量法,例19：用人工变量法求解下述线性规划问题。 max z =2x1+x2 x1+x22 2x1+2x26 x1，x20,第5节 人工变量法,例19： 解：标准型并添加人工变量 max z =2x1+x2-Mx5 x1+x2+x3=2 2x1+2x2-x4+x5=6 x1，x2 ，x3 ，x4，x50,第5节 人工变量法,小结 （1）将线性规划化为标准型后，对或的约束条件添加人工变量（若约束条件系数矩阵A中已有k个单位列向量，只要引入m-k个人工变量，使它们与原来的k个单位列向量合成单位矩阵） （2）在最优解中，若人工变量大于0，则原问题无可行解,作业2-5,作业2-5：用人工变量法求解下列线性规划问题。 1、 max z =3x1-x2-x3 x1-2x2+x311 -4x1+x2+2x33 2x1-x3=-1 x1，x2，x30,2、min z =-x1-3x2+x3 x1+x2+2x3+x4=4 -x1+x3-x5=4 x3-x6=3 x1，x2，x3，x4，x5，x60,第6节 小结,第6节 小结,二、单纯形表中解的表示形式 1、唯一最优解：最终单纯形表中，所有非基变量检验数j0 2、无穷多最优解：最终单纯形表中，某非基变量检验数j0 3、无界解：某检验数j0对应变量的系数列向量Pk0 4、无可行解：线性规划问题中添加人工变量后，最终单纯形表中，基变量中含有非零的人工变量（0）,第6节 小结,5、退化现象：用规则确定换出变量时，出现两个以上相同的最小比值，使下一个单纯形表中出现一个或多个基变量等于零。 退化基可行解：一个或几个基变量取值0的基可行解 退化基可行解出现的原因：模型中存在多余的约束，使多个基可行解对应同一顶点,第6节 小结,退化基可行解的处理规则： 出现退化基可行解，可能导致从某个基开始，经过若干次迭代后又回到原来的基，即单纯形法出现了循环，永远达不到最优解，导致计算失败。 为避免出现死循环，法则如下： 选择换入变量时，若有几个正的检验数具有相同的最大值，则选择下标最小的对应的非基变量作为换入变量 选择换出变量时，若按规则计算，有几个比值同时达到最小，则选择下标最小的对应的基变量作为换出变量,第6节 小结,例20：下列表格是求线性规划问题的单纯形表，试说明解的情况。 1、最终表,第6节 小结,2、最终表,第6节 小结,3、中间表（最终表）,第6节 小结,4、中间表（最终表）,第6节 小结,5、最初表,第6节 小结,6、中间表,第6节 小结,三、单纯形法 对给定的线性规划问题，首先化为标准型，选取或构造一个单位矩阵作为基矩阵，求出初始基可行解并列出初始单纯形表。 （若线性规划问题的标准型为目标函数最小化，则最优解判别规则为：所有检验数j0）,单纯形法计算步骤框图,第6节 小结,例21：用单纯形法求解下述线性规划问题，并说明