线性规划图解法和单纯形法课件.ppt

第1页，此课件共88页哦Chapter1 线性规划线性规划(Linear Programming)(Linear Programming)LP的数学模型的数学模型 图解法图解法 单纯形法单纯形法 单纯形法的进一步讨论人工变量法单纯形法的进一步讨论人工变量法 LP模型的应用模型的应用本章主要内容：本章主要内容：本章主要内容：本章主要内容：第2页，此课件共88页哦线性规划问题的数学模型线性规划问题的数学模型1.规划问题规划问题生产和经营管理中经常提出如何合理安排，使人力、物力生产和经营管理中经常提出如何合理安排，使人力、物力等各种资源得到充分利用，获得最大的效益，这就是规划等各种资源得到充分利用，获得最大的效益，这就是规划问题。问题。线性规划通常解决下列两类问题：线性规划通常解决下列两类问题：线性规划通常解决下列两类问题：线性规划通常解决下列两类问题：（1 1）当任务或目标确定后，如何统筹兼顾，合理安排，用最少的）当任务或目标确定后，如何统筹兼顾，合理安排，用最少的资源资源 （如资金、设备、原标材料、人工、时间等）去完成确定的任（如资金、设备、原标材料、人工、时间等）去完成确定的任务或目标务或目标（2 2）在一定的资源条件限制下，如何组织安排生产获得最好）在一定的资源条件限制下，如何组织安排生产获得最好的经济效益（如产品量最多的经济效益（如产品量最多 、利润最大、利润最大.）第3页，此课件共88页哦线性规划问题的数学模型线性规划问题的数学模型例例1.1 如图所示，如何截取如图所示，如何截取x使铁皮所围成的容积最使铁皮所围成的容积最大？大？x xa a第4页，此课件共88页哦线性规划问题的数学模型线性规划问题的数学模型例例1.2 某厂生产两种产品，下某厂生产两种产品，下表给出了单位产品所需资源及单表给出了单位产品所需资源及单位产品利润位产品利润 问：应如何安排生产计划，才能使问：应如何安排生产计划，才能使总利润最大？总利润最大？解：解：1.决策变量：设产品决策变量：设产品I、II的产量的产量分别为分别为x1、x22.目标函数：设总利润为目标函数：设总利润为z，则有：，则有：max z=2 x1+x23.约束条件：约束条件：5x2 15 6x1+2x2 24 x1+x2 5 x1，x20 x1=3.8,x2=1.2,z=22.8第5页，此课件共88页哦线性规划问题的数学模型线性规划问题的数学模型例例1.3 已知资料如下表所示，问已知资料如下表所示，问如何安排生产才能使利润最大如何安排生产才能使利润最大？或如何考虑利润大，产品好？或如何考虑利润大，产品好销。销。设备产品 A B C D利润（元）2 1 4 0 2 2 2 0 4 3 有效台时12 8 16 12解：解：1.决策变量：设产品决策变量：设产品I、II的产量分别为的产量分别为x1、x22.目标函数：设总利润为目标函数：设总利润为z，则有：，则有：max z=2 x1+x23.约束条件：约束条件：x1 0,x2 0 2x1+2x2 12 x1+2x2 8 4x1 16 4x2 12第6页，此课件共88页哦线性规划问题的数学模型线性规划问题的数学模型例例1.4 某厂生产三种药物，这些某厂生产三种药物，这些药物可以从四种不同的原料中提药物可以从四种不同的原料中提取。下表给出了单位原料可提取取。下表给出了单位原料可提取的药物量的药物量 解：解：要求：生产要求：生产A种药物至少种药物至少160单单位；位；B种药物恰好种药物恰好200单位，单位，C种种药物不超过药物不超过180单位，且使原料单位，且使原料总成本最小。总成本最小。1.决策变量：设四种原料的使用决策变量：设四种原料的使用量分别为：量分别为：x1、x2、x3、x42.目标函数：设总成本为目标函数：设总成本为z min z=5 x1+6 x2+7 x3+8 x43.约束条件：约束条件：x1+2x2+x3+x4 160 2x1 +4 x3+2 x4 200 3x1 x2+x3+2 x4 180 x1、x2、x3、x4 0第7页，此课件共88页哦 例例1.5 某航运局现有船只种类、数量以及计划期内各条航线的货运量、某航运局现有船只种类、数量以及计划期内各条航线的货运量、货运成本如下表所示：货运成本如下表所示：航线号船队类型编队形式货运成本（千元队）货运量（千吨）拖轮A型驳船B型驳船1112362521436202322472404142720船只种类船只数拖轮30A型驳船34B型驳船52航线号合同货运量12002400问：应如何编队，才能既完成合同任务，又使总货运成本为最小？问：应如何编队，才能既完成合同任务，又使总货运成本为最小？线性规划问题的数学模型线性规划问题的数学模型第8页，此课件共88页哦 解：解：设：设：xj为第为第j号类型船队的队数（号类型船队的队数（j=1，2，3，4），），z 为总货运成本为总货运成本则：则：minz=36x1+36x2+72x3+27x4x1+x2+2x3+x4302x1+2x3344x2+4x3+4x45225x1+20 x220040 x3+20 x4400 xj0（j=1,2,3,4）线性规划问题的数学模型线性规划问题的数学模型第9页，此课件共88页哦线性规划问题的数学模型线性规划问题的数学模型2.2.2.2.线性规划的数学模型由三个要素构成线性规划的数学模型由三个要素构成线性规划的数学模型由三个要素构成线性规划的数学模型由三个要素构成决策变量决策变量决策变量决策变量 Decision variables Decision variables 目标函数目标函数目标函数目标函数 Objective functionObjective function约束条件约束条件约束条件约束条件 ConstraintsConstraints其特征是：其特征是：其特征是：其特征是：（1 1 1 1）问题的目标函数是多个决策变量的）问题的目标函数是多个决策变量的）问题的目标函数是多个决策变量的）问题的目标函数是多个决策变量的线性线性线性线性函数，通常是函数，通常是函数，通常是函数，通常是求最大值或最小值；求最大值或最小值；求最大值或最小值；求最大值或最小值；（2 2 2 2）问题的约束条件是一组多个决策变量的）问题的约束条件是一组多个决策变量的）问题的约束条件是一组多个决策变量的）问题的约束条件是一组多个决策变量的线性线性线性线性不等式或等不等式或等不等式或等不等式或等式。式。式。式。怎样辨别一个模型是线性规划模型？怎样辨别一个模型是线性规划模型？怎样辨别一个模型是线性规划模型？怎样辨别一个模型是线性规划模型？第10页，此课件共88页哦线性规划问题的数学模型线性规划问题的数学模型3.3.3.3.建模条件建模条件建模条件建模条件(1)(1)优化条件优化条件优化条件优化条件：问题所要达到的目标能用线型函数描述，且能：问题所要达到的目标能用线型函数描述，且能：问题所要达到的目标能用线型函数描述，且能：问题所要达到的目标能用线型函数描述，且能够用极值够用极值够用极值够用极值 （max max 或或或或 minmin）来表示；）来表示；）来表示；）来表示；(2)(2)限定条件（约束条件）限定条件（约束条件）限定条件（约束条件）限定条件（约束条件）：达到目标受到一定的限制，且这些限制：达到目标受到一定的限制，且这些限制：达到目标受到一定的限制，且这些限制：达到目标受到一定的限制，且这些限制能够用决策变量的能够用决策变量的能够用决策变量的能够用决策变量的 线性等式或线性不等式表示；线性等式或线性不等式表示；线性等式或线性不等式表示；线性等式或线性不等式表示；(3)(3)选择条件选择条件选择条件选择条件：有多种可选择的方案供决策者选择，以便找出最优：有多种可选择的方案供决策者选择，以便找出最优：有多种可选择的方案供决策者选择，以便找出最优：有多种可选择的方案供决策者选择，以便找出最优方案。方案。方案。方案。第11页，此课件共88页哦线性规划问题的数学模型线性规划问题的数学模型4.4.4.4.建模步骤建模步骤建模步骤建模步骤(1)(1)确定决策变量确定决策变量确定决策变量确定决策变量：即需要我们作出决策或选择的量。一般情况下，：即需要我们作出决策或选择的量。一般情况下，：即需要我们作出决策或选择的量。一般情况下，：即需要我们作出决策或选择的量。一般情况下，题目问什么就设什么为决策变量；题目问什么就设什么为决策变量；题目问什么就设什么为决策变量；题目问什么就设什么为决策变量；(2)(2)找出所有限定条件找出所有限定条件找出所有限定条件找出所有限定条件：即决策变量受到的所有的约束；：即决策变量受到的所有的约束；：即决策变量受到的所有的约束；：即决策变量受到的所有的约束；(3)(3)写出目标函数写出目标函数写出目标函数写出目标函数：即问题所要达到的目标，并明确是：即问题所要达到的目标，并明确是：即问题所要达到的目标，并明确是：即问题所要达到的目标，并明确是max max 还是还是还是还是 minmin。第12页，此课件共88页哦线性规划问题的数学模型线性规划问题的数学模型目标函数：目标函数：目标函数：目标函数：约束条件：约束条件：约束条件：约束条件：5.5.5.5.线性规划数学模型的一般形式线性规划数学模型的一般形式线性规划数学模型的一般形式线性规划数学模型的一般形式简写为：简写为：第13页，此课件共88页哦线性规划问题的数学模型线性规划问题的数学模型向量形式：向量形式：向量形式：向量形式：其中：其中：第14页，此课件共88页哦线性规划问题的数学模型线性规划问题的数学模型矩阵形式：矩阵形式：矩阵形式：矩阵形式：其中：其中：第15页，此课件共88页哦线性规划问题的数学模型线性规划问题的数学模型6.线性规划问题的标准形式线性规划问题的标准形式特点：特点：(1)目标函数求最大值（有时求最小值）目标函数求最大值（有时求最小值）(2)约束条件都为等式方程，且右端常数项约束条件都为等式方程，且右端常数项bi都大于或等于零都大于或等于零(3)决策变量决策变量xj为非负。为非负。第16页，此课件共88页哦线性规划问题的数学模型线性规划问题的数学模型（2 2 2 2）如何化标准形式）如何化标准形式）如何化标准形式）如何化标准形式 目标函数的转换目标函数的转换 如果是求极小值即如果是求极小值即 ，则可将目标函数乘以，则可将目标函数乘以(-1)，可化为求极大值问题。，可化为求极大值问题。也就是：令也就是：令 ，可得到上式。，可得到上式。即即 若存在取值无约束的变量若存在取值无约束的变量 ，可令，可令 其中：其中：变量的变换变量的变换第17页，此课件共88页哦线性规划问题的数学模型线性规划问题的数学模型 约束方程的转换：由不等式转换为等式。约束方程的转换：由不等式转换为等式。称为松弛变量称为松弛变量称为剩余变量称为剩余变量 常量常量 bi0 的变换的变换:约束方程两边乘以约束方程两边乘以（1）第18页，此课件共88页哦线性规划问题的数学模型线性规划问题的数学模型例例1.6 将下列线性规划问题化为标准形式将下列线性规划问题化为标准形式用用 替换替换 ，且，且 解解:（）因为（）因为x3无符号要求无符号要求，即，即x3取正值也可取负值，标准取正值也可取负值，标准型中要求变量非负，所以型中要求变量非负，所以第19页，此课件共88页哦线性规划问题的数学模型线性规划问题的数学模型(2)第一个约束条件是第一个约束条件是“”号，在号，在“”左端加入松驰变量左端加入松驰变量x4，x40,化为等式；化为等式；(3)第二个约束条件是第二个约束条件是“”号，在号，在“”左端减去剩余变量左端减去剩余变量x5，x50；(4)第第3个约束方程右端常数项为个约束方程右端常数项为-5，方程两边同乘以，方程两边同乘以(-1),将右端常数将右端常数项化为正数；项化为正数；(5)目标函数是最小值，为了化为求最大值，令目标函数是最小值，为了化为求最大值，令z=-z,得到得到max z=-z，即当，即当z达到最小值时达到最小值时z达到最大值，反之亦然达到最大值，反之亦然;第20页，此课件共88页哦线性规划问题的数学模型线性规划问题的数学模型标准形式如下：标准形式如下：第21页，此课件共88页哦 例例1.7 将下列线性规划问题化为标准形式将下列线性规划问题化为标准形式为无约束（无非负限制）为无约束（无非负限制）线性规划问题的数学模型线性规划问题的数学模型第22页，此课件共88页哦 解解:用用替换替换，且，且，将第将第3个约束方程两边乘以（个约束方程两边乘以（1）将极小值问题反号，变为求极大值将极小值问题反号，变为求极大值标准形式如下：标准形式如下：引入变量引入变量线性规划问题的数学模型线性规划问题的数学模型第23页，此课件共88页哦 例例1.8 将线性规划问题化为标准型将线性规划问题化为标准型解：解：线性规划问题的数学模型线性规划问题的数学模型第24页，此课件共88页哦 例例1.9 将线性规划问题化为标准型将线性规划问题化为标准型解：解：Minf=-3x1+5x2+8x3-7x4s.t.2x1-3x2+5x3+6x4284x1+2x2+3x3-9x4396x2+2x3+3x4-58x1,x3 ,x40；x2无约束 Maxz=3x15x2+5x2”8x3+7x4s.t.2x13x2+3x2”+5x3+6x4+x5=284x1+2x2-2x2”+3x3-9x4-x6=39-6x2+6x2”-2x3-3x4-x7=58x1,x2,x2”,x3,x4,x5,x6,x70线性规划问题的数学模型线性规划问题的数学模型第25页，此课件共88页哦线性规划问题的数学模型线性规划问题的数学模型7.7.线性规划问题的解线性规划问题的解线性规划问题线性规划问题求解线性规划问题，就是从满足约束条件求解线性规划问题，就是从满足约束条件(2)、(3)的方程组中找出的方程组中找出一个解，使目标函数一个解，使目标函数(1)达到最大值。达到最大值。第26页，此课件共88页哦线性规划问题的数学模型线性规划问题的数学模型 可行解可行解：满足约束条件：满足约束条件、的解为可行解。所有可行解的集合为可的解为可行解。所有可行解的集合为可行域。行域。最优解最优解：使目标函数达到最大值的可行解。：使目标函数达到最大值的可行解。基：基：设设A为约束条件为约束条件的的mn阶系数矩阵阶系数矩阵(mn)，其秩为，其秩为m，B是矩是矩阵阵A中中m阶满秩子方阵（阶满秩子方阵（B 0），称），称B是规划问题的一个基。设：是规划问题的一个基。设：称称 B中每个列向量中每个列向量Pj(j=1,2,m)为基向量。与基向量为基向量。与基向量Pj 对应的变量对应的变量xj 为为基变量基变量。除基变量以外的变量为。除基变量以外的变量为非基变量非基变量。第27页，此课件共88页哦线性规划问题的数学模型线性规划问题的数学模型 基解：基解：某一确定的基某一确定的基B，令非基变量等于零，由约束条件，令非基变量等于零，由约束条件方程方程解出基变量，称这组解为基解。在基解中变量取非零解出基变量，称这组解为基解。在基解中变量取非零值的个数不大于方程数值的个数不大于方程数m，基解的总数不超过，基解的总数不超过 基可行解：基可行解：满足变量非负约束条件的基本解，简称基可满足变量非负约束条件的基本解，简称基可行解。行解。可行基：可行基：对应于基可行解的基称为可行基。对应于基可行解的基称为可行基。非可行解非可行解可可行行解解基解基解基可行解基可行解第28页，此课件共88页哦线性规划问题的数学模型线性规划问题的数学模型例例1.10 求线性规划问题的所有基矩阵。求线性规划问题的所有基矩阵。解解:约束方程的系数矩阵为约束方程的系数矩阵为25矩阵矩阵 r(A)=2，2阶子矩阵有阶子矩阵有10个，其中基矩阵只有个，其中基矩阵只有9个，即个，即第29页，此课件共88页哦图解法图解法线性规划问题的求解方法线性规划问题的求解方法一一 般般 有有两种方法两种方法图图 解解 法法单纯形法单纯形法两个变量、直角坐标两个变量、直角坐标三个变量、立体坐标三个变量、立体坐标适用于任意变量、但必需将适用于任意变量、但必需将一般形式变成标准形式一般形式变成标准形式下面我们分析一下简单的情况下面我们分析一下简单的情况 只有两个决策变量的只有两个决策变量的线性规划问题，这时可以通过图解的方法来求解。图解线性规划问题，这时可以通过图解的方法来求解。图解法具有简单、直观的优点，便于初学者窥探线性规划基法具有简单、直观的优点，便于初学者窥探线性规划基本原理和几何意义。本原理和几何意义。第30页，此课件共88页哦 解题步骤解题步骤4 将最优解代入目标函数，求出最优值。将最优解代入目标函数，求出最优值。1 在直角平面坐标系中画出所有的在直角平面坐标系中画出所有的约束等式约束等式，并找出所有，并找出所有约束条件的公共部分，称为可行域，可行域中的点即约束条件的公共部分，称为可行域，可行域中的点即为可行解。为可行解。2 标出标出目标函数目标函数值增加或者减小的方向。值增加或者减小的方向。3 若求最大（小）值，则令目标函数等值线沿（逆）目标若求最大（小）值，则令目标函数等值线沿（逆）目标函数值增加的方向函数值增加的方向平行移动平行移动，找与可行域最后相交的点，该，找与可行域最后相交的点，该点就是最优解。点就是最优解。图解法图解法第31页，此课件共88页哦图解法图解法max Z=2X1+X2 X1+1.9X2 3.8 X1 -1.9X2 3.8s.t.X1+1.9X2 10.2 X1 -1.9X2 -3.8 X1 ，X2 0例例1.11 用图解法求解线性规划问题用图解法求解线性规划问题第32页，此课件共88页哦图解法图解法x1x2oX1-1.9X2=3.8()X1+1.9X2=3.8()X1-1.9X2=-3.8()X1+1.9X2=10.2()4=2X1+X2 20=2X1+X2 17.2=2X1+X2 Lo：0=2X1+X2（7.6，2）Dmax Zmin Z此点是唯一最优解，且最优目标函数值max Z=17.2可行域可行域max Z=2X1+X2第33页，此课件共88页哦图解法图解法max Z=3X1+5.7X2x1x2oX1-1.9X2=3.8()X1+1.9X2=3.8()X1-1.9X2=-3.8()X1+1.9X2=10.2()（7.6，2）DL0：0=3X1+5.7X2 max Z（3.8，4）34.2=3X1+5.7X2 蓝色线段上的所有点都是最优解这种情形为有无穷多最优解，但是最优目标函数值max Z=34.2是唯一的。可行域可行域第34页，此课件共88页哦图解法图解法min Z=5X1+4X2x1x2oX1-1.9X2=3.8()X1+1.9X2=3.8()X1+1.9X2=10.2()DL0：0=5X1+4X2 max Z min Z 8=5X1+4X2 43=5X1+4X2（0，2）可行域可行域此点是唯一最优解第35页，此课件共88页哦图解法图解法246x1x2246无界解无界解(无最优解无最优解)maxZ=x1+2x2例例1.6x1+x2=4()x1+3x2=6()3x1+x2=6()max Z min Z第36页，此课件共88页哦x1x2O10203040102030405050无可行解无可行解(即无最优解即无最优解)max Z=3x1+4x2例例1.7第37页，此课件共88页哦 由图解法得到的几种情况由图解法得到的几种情况 根据以上例题，进一步分析讨论可知线性规划的可行域和最根据以上例题，进一步分析讨论可知线性规划的可行域和最优解有以下几种可能的情况：优解有以下几种可能的情况：1.可行域为封闭的有界区域可行域为封闭的有界区域 (a)有唯一的最优解；有唯一的最优解；(b)有无穷多个最优解；有无穷多个最优解；2.可行域为封闭的无界区域可行域为封闭的无界区域 (c)有唯一的最优解；有唯一的最优解；(d)有无穷多个最优解；有无穷多个最优解；(e)目标函数无界目标函数无界(即虽有可行解，但在可行域中，目标函数可以无限即虽有可行解，但在可行域中，目标函数可以无限增大或无限减少增大或无限减少)，因而没有有限最优解。，因而没有有限最优解。3.可行域为空集可行域为空集 (f)没有可行解，原问题无最优解没有可行解，原问题无最优解图解法图解法第38页，此课件共88页哦 由图解法得到的启示由图解法得到的启示(1)线性规划问题解的情况：线性规划问题解的情况：唯一最优解；无穷多最优解；无界解；无可行解唯一最优解；无穷多最优解；无界解；无可行解(2)线性规划问题的可行域是凸集（凸多边形）线性规划问题的可行域是凸集（凸多边形）图解法图解法第39页，此课件共88页哦图解法图解法x1x2oX1-1.9X2=3.8()X1+1.9X2=3.8()X1-1.9X2=-3.8()X1+1.9X2=10.2()17.2=2X1+X2 Lo：0=2X1+X2（7.6，2）Dmax Zmin Z可行域可行域max Z=2X1+X2(3)最优解一定是在凸集的某个顶点最优解一定是在凸集的某个顶点第40页，此课件共88页哦 解题思路解题思路 先找出凸集的任一顶点，计算其目标函数值，再与周围顶点先找出凸集的任一顶点，计算其目标函数值，再与周围顶点的目标函数值比较，如不是最大（或最小），继续比较，直到的目标函数值比较，如不是最大（或最小），继续比较，直到找出最大（或最小）为止。找出最大（或最小）为止。图解法图解法第41页，此课件共88页哦图解法图解法学习要点：学习要点：1.通过图解法了解线性规划有几种解的形式通过图解法了解线性规划有几种解的形式（唯一最优解；无穷多最优解；无界解；无可行解）（唯一最优解；无穷多最优解；无界解；无可行解）2.作图的关键有三点：作图的关键有三点：(1)可行解区域要画正确可行解区域要画正确(2)目标函数增加的方向不能画错目标函数增加的方向不能画错(3)目标函数的直线怎样平行移动目标函数的直线怎样平行移动第42页，此课件共88页哦 连接几何形体中任意两点的线段仍完全在该几何形体之中。连接几何形体中任意两点的线段仍完全在该几何形体之中。有限个凸集的交集仍然是凸集。有限个凸集的交集仍然是凸集。单纯形法基本原理单纯形法基本原理凸集凸集第43页，此课件共88页哦单纯形法基本原理单纯形法基本原理凸集：如果集合凸集：如果集合C中任意两个点中任意两个点X1、X2，其连线上的所有点也都是，其连线上的所有点也都是集合集合C中的点，称中的点，称C为凸集。为凸集。凸集凸集凸集凸集不是凸集不是凸集第44页，此课件共88页哦单纯形法基本原理单纯形法基本原理凸集凸集凸集凸集顶顶 点点 顶点：如果凸集顶点：如果凸集C中不存在任何两个不同的点中不存在任何两个不同的点X1，X2，使，使X成为成为这两个点连线上的一个点这两个点连线上的一个点第45页，此课件共88页哦单纯形法基本原理单纯形法基本原理定理定理定理定理1 1：若线性规划问题存在可行解，则该问题的可行域是凸集。：若线性规划问题存在可行解，则该问题的可行域是凸集。：若线性规划问题存在可行解，则该问题的可行域是凸集。：若线性规划问题存在可行解，则该问题的可行域是凸集。定理定理定理定理2 2：线性规划问题的基可行解：线性规划问题的基可行解：线性规划问题的基可行解：线性规划问题的基可行解X X对应可行域对应可行域对应可行域对应可行域(凸集凸集凸集凸集)的顶点。的顶点。的顶点。的顶点。定理定理定理定理3 3：若问题存在最优解，一定存在一个基可行解是最优解。：若问题存在最优解，一定存在一个基可行解是最优解。：若问题存在最优解，一定存在一个基可行解是最优解。：若问题存在最优解，一定存在一个基可行解是最优解。（即在某个顶点取得）（即在某个顶点取得）（即在某个顶点取得）（即在某个顶点取得）第46页，此课件共88页哦几个基本定理的证明几个基本定理的证明定理定理1 若线性规划问题存在可行解，则问题的可行域是凸集若线性规划问题存在可行解，则问题的可行域是凸集。思路：若满足线性规划约束条件的所有点组成的几何图形C是凸集，根据凸集的定义，C内任意两点X1,X2连线上的点也必然在C内。【证】设为C 内任意两点，即，将X1,X2代入约束条件有X1,X2连线上任意一点可以表示为：第47页，此课件共88页哦将(1.9)代入约束条件并由式(1.8)得：所以。由于集合内任意两点连线上的点均在集合内，所以C为凸集。第48页，此课件共88页哦一个引理引理引理线性规划问题的可行解线性规划问题的可行解 为基可行解的的充要条件是为基可行解的的充要条件是X的正分量所对的正分量所对应的系数列向量是线性独立的。应的系数列向量是线性独立的。【证】必要性由基可行解的定义是显然的。充分性：若向量P1,P2,Pk是线性独立的，则必有km。1)当k=m时，它们恰好构成一个基，从而相应的基可行解为2)当k0得第60页，此课件共88页哦式(1.15)+式(1.17)，并经过整理后有由上式找到满足约束方程组的另外一个点：其中是的第j个坐标的值。要使是一个基可行解，因 0，故应对所有i=1,.,m存在且这m个不等式中至少有一个等号成立，因为当时，上式显然成立。第61页，此课件共88页哦这样中正分量最多有m个，容易证明m个向量线性无关，故只需按式(1.20)来确定 的值，就是一个新的基可行解。令第62页，此课件共88页哦基本可行解和可行基的变换基本可行解和可行基的变换基本可行解：基本可行解：可行基：可行基：换出基换入基第63页，此课件共88页哦STEP3 最优性检验和解的判别最优性检验和解的判别将基可行解分别代入目标函数得因0为给定，所以只要有通常简写为，它是对线性规划问题的解进行最优性检验的标志。第64页，此课件共88页哦1.当所有的时，表明现有顶点（基可行解）的目标函数值比起相邻各顶点（基可行解）的目标函数值都大，现有顶点对应的基可行解即为最优解最优解。2.当所有时，对某个非基变量xj 有，且按公式(1.20)可找到0，这表明可以找到另一顶点（基可行解）目标函数也达到最大。由于该两点连线上的点也属可行域内的点，且目标函数值相等，即该线性规划问题有无穷多最优解有无穷多最优解。3.如果存在某个又Pj向量的所有分量aij0。换基时对任意0,恒有因取值可无限大，在由X(0)换到X(1)时目标函数值也可无限大，则线性规划问题存在无界解存在无界解。第65页，此课件共88页哦引例：引例：求解线性规划问题LP规划问题的最优解可从基可行解（顶点）中找到图解法有局限性；枚举法计算量大；第66页，此课件共88页哦解：第一第一:将该问题化成标准形第二第二:找初始可行解(即一个顶点)。系数矩阵A=(P1P2P3P4P5)矩阵形式第67页，此课件共88页哦因为P3，P4，P5线性独立，故B=(P3,P4,P5)构成一个基，其对应的基变量x3，x4，x5，解出来为（用用非非基变量表示基变量基变量表示基变量）x3=8-x1-2x2x4=16-4x1(1)x5=12-4x2XB=B-1b B-1NXN将(1)代入目标函数中得z=0+2x1+3x2令非基变量x1=x2=0，则有z=0。这时得到一个基可行解：X(0)=(0,0,8,16,12)T-原点第68页，此课件共88页哦第三第三:判别从目标函数z=0+2x1+3x2中得知，非基变量x1和x2的系数为正，因此，将非基变量换入基后可使目标函数增大，转入第四步第四：第四：换基(旋转迭代)确定换入变量：由于非基变量x2的系数（正）贡献最大，故需换入的基变量为x2。换入变量已定，必须从x3，x4，x5换出一个，并且要保证其余均是非负的，即x3，x4，x50。当x1=0时，有x3=8-2x20 x4=160 x5=12-4x20 x2换入基，x1未换入，还是非基变量第69页，此课件共88页哦只要选择x2=min(8/2，-，12/4)=3，对应基变量x5=0，从而确定用x2和和x5对换对换，即将x5换出，（用非基变量表用非基变量表示基变量示基变量）2x2+x3=8-x1x4=16-4x14x2=12-x5用高斯消去法（行变换），得x3=2-x1+1/2x5x4=16-4x1x2=3-1/4x5（2）将上式代入原目标函数中得z=9+2x1-3/4x5（1）第70页，此课件共88页哦返回第三步：从z=9+2x1-3/4x5，非基变量x1的系数是正的，还可增大。重复上述步骤。由于x1的系数是正的，则x1为转入变量，再由当x5=0时x3=2-x10 x4=16-4x10 x2=30只要选x1=min2，16/4，-=2上式就成立，因为x1=2时，基变量x3=0，从而由由x1换出换出x3令非基变量x1和x5为零有z=9，又得到另一个基可行解X(1)=(0,3,2,16,0)T顶点Q4第71页，此课件共88页哦x1+2x2=8-x34x1+x4=16(3)4x2=12-x5高斯消去法（行变换）得x1=2-x3+1/2x50 x4=8-2x5+4x30 x2=3-1/4x50代入目标函数中，得z=13-2x3+1/4x5令非基变量x3=x5=0有z=13，又得到另一个基可行解X(2)=(2,3,0,8,0)T顶点Q3;（2）用非基变量表示基变量用非基变量表示基变量第72页，此课件共88页哦同理，返回第三步，再迭代，x5作为转入变量只要取x5=min-，8/2，12=4就有上式成立。x5=4时，x4=0，故用x5换换x4x1=4-1/4x4x5=4-1/2x4+2x3x2=2+1/8x41/2x3令x3=0，有 x1=2+1/2x50 x4=8-2x50 x2=3-1/4x50（3）+高斯第73页，此课件共88页哦0Q4Q3Q2Q11123234X1X2x1+2x2=84x1=164x2=12代入得z=14-3/2x3-1/8x4，令x3=x4=0得z=14。新的基可行解为 X(3)=(4,2,0,0,4)T顶点Q2(最优解)最优目标值z=14。(0,3,2,16,0)(0,0,8,16,12)(2,3,0,8,0)(4,2,0,0,4)第74页，此课件共88页哦单纯形法的计算步骤单纯形法的计算步骤单纯形表单纯形表确确定定换换出出基基确定换确定换入基入基第75页，此课件共88页哦单纯形法的计算步骤单纯形法的计算步骤例例1.12 用单纯形法求下列线性规划的最优解用单纯形法求下列线性规划的最优解解：解：1）将问题化为标准型，加入松驰变量将问题化为标准型，加入松驰变量x3、x4则标准型为则标准型为:第76页，此课件共88页哦单纯形法的计算步骤单纯形法的计算步骤2）求出线性规划的初始基可行解，列出初始单纯形表。）求出线性规划的初始基可行解，列出初始单纯形表。cj3400icB基bx1x2x3x40 x34021100 x43013013400检验数检验数第77页，此课件共88页哦单纯形法的计算步骤单纯形法的计算步骤3）进行最优性检验）进行最优性检验如果表中所有检验数如果表中所有检验数 ，则表中的基可行解就是问题的最，则表中的基可行解就是问题的最优解，计算停止。否则继续下一步。优解，计算停止。否则继续下一步。4）从一个基可行解转换到另一个目标值更大的基可行解，列）从一个基可行解转换到另一个目标值更大的基可行解，列出新的单纯形表出新的单纯形表确定换入基的变量。选择确定换入基的变量。选择 ，对应的变量，对应的变量xj作为换入变量，当作为换入变量，当有一个以上检验数大于有一个以上检验数大于0时，一般选择最大的一个检验数，即：时，一般选择最大的一个检验数，即：，其对应的，其对应的xk作为作为换入变量换入变量。确定换出变量。根据下式计算并选择确定换出变量。根据下式计算并选择，选最小的选最小的对应基变量作对应基变量作为为换出变量换出变量。主元素第78页，此课件共88页哦单纯形法的计算步骤单纯形法的计算步骤用换入变量用换入变量xk替换基变量中的换出变量，得到一个新的基。对替换基变量中的换出变量，得到一个新的基。对应新的基可以找出一个新的基可行解，并相应地可以画出一个应新的基可以找出一个新的基可行解，并相应地可以画出一个新的单纯形表。新的单纯形表。5）重复）重复3）、）、4）步直到计算结束为止。）步直到计算结束为止。在新表中的基仍应该是单位矩阵在新表中的基仍应该是单位矩阵，则应将主元素所对应的列，则应将主元素所对应的列(换换入基入基)变成单位向量，包括约束条件的系数矩阵，基对应的值，检变成单位向量，包括约束条件的系数矩阵，基对应的值，检验数等验数等换入变量换入变量xk的检验数应为的检验数应为0高斯变换高斯变换第79页，此课件共88页哦单纯形法的计算步骤单纯形法的计算步骤cj3400iCB基变量bx1x2x3x40 x34021100 x430130134000 x34x23x14x2换入列bi/ai2，ai204010换出行将3化为15/311801/301/3101-1/3 303005/30-4/3乘以1/3后得到103/5-1/51801-1/5 2/5400-1-1第80页，此课件共88页哦单纯形法的计算步骤单纯形法的计算步骤例例1.13 用单纯形法求解用单纯形法求解解：将数学模型化为标准形式：解：将数学模型化为标准形式：不难看出不难看出x4、x5可作为初始基变量，列单纯形表计算。可作为初始基变量，列单纯形表计算。第81页，此课件共88页哦单纯形法的计算步骤单纯形法的计算步骤cj12100iCB基变量bx1x2x3x4x50 x4152-32100 x5201/31501121000 x42x220 x x2 221/3150120753017131/309022560 x x1 111017/31/31250128/9-1/92/335/300-98/9-1/9-7/3第82页，此课件共88页哦变成标准型变成标准型单纯形法的计算步骤单纯形法的计算步骤例例1.14 用单纯形法求解用单纯形法求解第83页，此课件共88页哦约束方程的系数矩阵约束方程的系数矩阵 为基变量为基变量为非基变量为非基变量I 为单位矩阵且线性独立为单位矩阵且线性独立单纯形法的计算步骤单纯形法的计算步骤第84页，此课件共88页哦第85页，此课件共88页哦第86页，此课件共88页哦第87页，此课件共88页哦单纯形法的计算步骤单纯形法的计算步骤学习要点：学习要点：1.线性规划解的概念以及线性规划解的概念以及3个基本定理个基本定理2.熟练掌握线性规划问题的标准化熟练掌握线性规划问题的标准化 3.熟练掌握单纯形法的解题思路及求解步骤熟练掌握单纯形法的解题思路及求解步骤第88页，此课件共88页哦