《第二章线性规划与单纯形法知识课件》由会员分享，可在线阅读，更多相关《第二章线性规划与单纯形法知识课件（66页珍藏版）》请在金锄头文库上搜索。
1、第二章 线性规划与单纯形法（Linear Programming，简称LP）,1 线性规化问题及其数学模型 2 线性规化问题的几何意义 3 单纯形法 4 单纯形法的计算步骤 5 单纯形法的进一步讨论 6 应用案例,1线性规化问题及其数学模型,1.1 问题的提出 例1：某工厂在计划期内要安排生产、两种产品，已知生产单位产品所需的设备台时及A、B两种原材料的消耗如下表，该工厂每生产一件产品可获利2元，每生产一件产品可获利3元，问应如何安排生产计划使该工厂获利最多？,x1,x2,1线性规化问题及其数学模型,max,目标函数,约束条件,1.1 问题的提出,x1,x2,z,500万m3,200万m3,工
2、厂1,工厂2,2万m3 1000元/万m3,1.4万m3 800元/万m3,小于0.2%,自然净化20%,min,目标函数,约束条件,特征： 每一个问题都用一组决策变量（ x1， x2， ，xn ）表示某一个方案； 存在一定的约束条件，这些约束条件可以用一组线性等式或线性不等式来表示； 都有一个要求达到的目标，它可以用决策变量的线性函数来表示，按问题的不同，要求目标函数实现最大化或最小化。,min,线性规划问题的数学模型的一般形式为：,目标函数,约束条件,线性规划问题解的概念,可行解：,若（x1，x2，xn）满足上述约束条件，则称（x1，x2，xn）为线性规划问题的可行解。,可行域：,所有可行
3、解组成的集合称为可行域。,最优解：,使目标函数达到最大或最小的可行解称为最优解。,1.2 图解法,Q(4, 2),Z=14,X*= (4，2) Z*=14,线性规划图解法解题步骤,4 将最优解代入目标函数，求出最优目标函数值。,1 在直角平面坐标系中画出所有的约束等式，并找出所有约束条件的公共部分，即可行域，可行域中的点即为可行解。,2 标出目标函数值增加的方向。,3 若求最大（小）值，则令目标函数等值线沿（逆）目标函数值增加的方向平行移动，找与可行域最后相交的点，该点就是最优解。,X2,4 3 2 1,X2,4 3 2 1,无穷多最优解,无界解,A,B,唯一最优解 无穷多最优解 无界解 无可
4、行解,有最优解,无最优解,1.3 线性规化问题的标准型式,目标函数,约束条件,标准型的其它表示形式,如何化标准型 目标函数求最小minz = CX 。可化为： max (-z) = -CX。 约束条件为不等式。对于“”不等式，在不等式的左边加上非负松驰变量后变为等式；对于 “”不等式，在不等式的左边减去非负剩余变量后变为等式。 3. 变量 xk 无约束。可令 xk = xk -xk,例：,1.4 线性规化问题的基可行解,例：,基,*,*,1.4 线性规化问题的基可行解 基：设A是约束方程组的mn阶系数矩阵，其秩为m，B是矩阵A中mm阶非奇异子矩阵（|B|0），则称B是线性规划问题的一个基。 基
5、B的列Pj称为基向量，与基向量对应的变量xj称为基变量，否则称为非基变量。 基解：令非基变量为零，由约束方程AX=b求得的解称为基解。 基可行解：满足非负条件的基解称为基可行解。 可行基: 对应于基可行解的基称为可行基。 注：基解的个数最多是Cnm个，基可行解的个数一般要小于基解的个数。,1 可行解与最优解：,最优解一定是可行解，但可行解不一定是最优解。,线性规划解之间的关系,基解不一定是可行解，可行解也不一定是基解。,2 可行解与基解：,3 可行解与基可行解：,基可行解一定是可行解，但可行解不一定是基解。,基可行解一定是基解， 但基解不一定是基可行解。,4 基解与基可行解：,5 最优解与基解
6、：,最优解不一定是基解， 基解也不一定是最优解。,问题：最优解与基本可行解？,X1,X2,X1,X2,X1,X2,2 线性规化问题的几何意义,2.1 基本概念,2. 凸组合：,3. 顶点：,1.凸集：,凸集：设K是n维欧氏空间的一个点集，若任意两点X(1)， X(2)K的连线上的一切点X=X(1)+(1-)X(2) K ，（0 1），则称K为凸集。,凸组合：设X(1) ，X(2) X(k) 是n维欧氏空间的k个点，若存在1，2 k， 且 0 i 1， i=1，2 k， i =1，使 X=1 X(1) + 2 X(2) + +k X(k) 则称X为X(1) ， X(2) ， X(k)的凸组合。,
7、顶点：设K是一凸集， XK，若X不能表示成K中不同两点X(1) ， X(2)的凸组合 X=X(1)+(1-)X(2) （01） 则X称为K的顶点或极点。,2.2 基本定理 定理1：若线性规划问题存在可行域，则可行域一定是凸集。,引理1 线性规划问题的可行解X为基可行解的是充要条件是X的正分量所对应的系数列向量是线性独立的。 引理2 若K是有界凸集，则任何一点X K可表示为 K的顶点的凸组合。,定理2 线性规化问题的基可行解对应于可行域的顶点。,定理 若可行域有界，线性规划的目标函数一定可以在其可行域的顶点上达到最优,1. 如果目标函数在多个顶点上达到最优，则目标函数在这些顶点的凸组合上也达到最
8、优。,2. 如果可行域为无界，则可能有最优解，也可能无最优解，若有最优解，则必在某个顶点上达到最优。,1.线性规划问题的所有可行解构成的集合可行域是凸集，也可能是无界域； 2.可行域有有限个顶点，线性规划问题的每个基可行解对应于可行域的一个顶点； 3.若线性规划问题有最优解，必在可行域的某顶点上达到。,线性规划问题的几何意义：,4.如果目标函数在多个顶点上达到最优，则目标函数在这些顶点的凸组合上也达到最优,即线性规划问题有无群多最优解。,3 单纯形法,单纯形法的基本思路：,X1 CX1,X2 CX2,X3 CX3,Xn CXn,*,*,1. 初始基B1及所对应基可行解X1的确定；,2. Xj
9、的最优性判定；,4. 求下一个顶点 Xj+1 。,3.1 实例分析 例：,4,/,3,*,*, ,4,/,3,*,*, ,2,4,/,*,*,1,2,4,/,*,*,1,/,4,12,*,*, ,/,4,12,*,*, ,1,2,Q2 (4, 2),Q1(4, 0),Q3(2, 3),Q4(0, 3),O,Q4,Q2,Q3,*,*,3.2 初始可行解的确定 1.观察法：通过观察确定初始可行解，例如下列线性规划问题：,化为标准型,则初始可行解为,2.人造基法：每个约束条件加上一个非负人工变量后组成一个人造基。具体方法下节讨论。,3.3 最优性检验与解的判别 检验数：目标函数用非基变量表达后，非基
10、变量的系数称为检验数。 1. 最优解的判别定理：若X(0)是线性规划问题的一个基可行解，如果对应的非基变量的检验数都小于等于零，则X(0)为最优解。 2. 无穷多最优解的判别定理：若X(0)是线性规划问题的一个基可行解，如果对应的非基变量的检验数都小于等于零，又存在某个非基变量的检验数等于零，则线性规划问题有无穷多最优解。 3. 无界解判别定理：若X(0)是线性规划问题的一个基可行解，若存在一非基变量的检验数大于零，而该非基变量的系数向量小于等于零，则该线性规划问题有无界解。,3.4 基变换 1.换入变量的确定：所有大于等于零的检验数中最大的对应的变量为换入变量。但也可以任选。 2.换出变量的
11、确定：用换入变量的系数去除对应的常数项得，的正分量中最小的对应的基变量为换出变量。 设换入变量为xk，换出变量为xl，则alk 称为主元素，它所在的列称为主元列，它所在的行称为主元行。,3.5 迭代 利用高斯消去法或矩阵的初等变换将主元素变为1主元列的其它元素变为零的过程称为迭代。 迭代的形式包括：约束方程组法，系数矩阵法和单纯表法。, ,4 单纯形法的计算步骤,4.1 单纯形表 为了便于理解计算关系，以系数矩阵法为基础设计一种计算表来实现迭代过程。这种计算表称为单纯形表。, ,4.2 单纯形法的计算步骤 1. 找出初始可行基，确定初始可行解，建立初始单纯形表。 2. 检验非基变量的检验数，如
12、果所有非基变量的检验数都小于等于零，则已得到最优解，停止计算，否则，转入下一步。 3. 确定换入变量或确定是否为无界解。 4. 计算，确定换出变量。 5. 迭代，即利用高斯消去法或矩阵初等变换，把主元素变成1，主元列的其他元素变成0。 6.重复26步。,8 1 2 1 0 0,16 4 0 0 1 0,12 0 4 0 0 1,0 2 3 0 0 0,2 1 0 1 0 -1/2,16 4 0 0 1 0,3 0 1 0 0 1/4,-9 2 0 0 0 -3/4,2 1 0 1 0 -1/2,8 0 0 -4 1 2,3 0 1 0 0 1/4,-13 0 0 -2 0 1/4, , , ,
13、2 1 0 1 0 -1/2,8 0 0 -4 1 2,3 0 1 0 0 1/4,-13 0 0 -2 0 1/4,4 1 0 1 1/4 0,4 0 0 -2 1/2 1,2 0 1 1/2 -1/8 0,-14 0 0 -3/2 -1/8 0, ,5 单纯形法的进一步讨论,5.1 人工变量法,1.大M法,例,例,4M 3-6M -1+M -1+3M 0 -M 0 0,11 1 -2 1 1 0 0 0,3 -4 1 2 0 -1 1 0,1 -2 0 1 0 0 0 1,10 3 -2 0 1 0 0 -1,1 0 1 0 0 -1 1 -2,1 -2 0 1 0 0 0 1,12 3
14、0 0 1 -2 2 -5,1 -2 -2 1 0 0 0 1,1 0 1 0 0 -1 1 -2,1+M 1 -1+M 0 0 -M 0 1-3M,2 1 0 0 0 -1 1-M -1-M, , , ,12 3 0 0 1 -2 2 -5,1 -2 0 1 0 0 0 1,1 0 1 0 0 -1 1 -2,2 1 0 0 0 -1 1-M -1-M, ,4 1 0 0 1/3 -2/3 2/3 -5/3,9 0 0 1 2/3 -4/3 4/3 7/3,1 0 1 0 0 -1 1 -2,-2 0 0 0 -1/3 -1/3 1/3-M 2/3-M,2. 两阶段法 第一阶段：,第二阶段：,第一阶段的最终单纯形表,4 -6 1 3 0 -1 0 0,11 1 -2 1 1 0 0 0,3 -4 1 2 0 -1 1 0,1 -2 0 1 0 0 0 1,10 3 -2 0 1
