资源预览内容
第1页 / 共66页
第2页 / 共66页
第3页 / 共66页
第4页 / 共66页
第5页 / 共66页
第6页 / 共66页
第7页 / 共66页
第8页 / 共66页
第9页 / 共66页
第10页 / 共66页
亲,该文档总共66页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述
第二章 线性规划与单纯形法(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,工厂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)为线性规划问题的可行解。,可行域:,所有可行解组成的集合称为可行域。,最优解:,使目标函数达到最大或最小的可行解称为最优解。,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,唯一最优解 无穷多最优解 无界解 无可行解,有最优解,无最优解,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是线性规划问题的一个基。 基B的列Pj称为基向量,与基向量对应的变量xj称为基变量,否则称为非基变量。 基解:令非基变量为零,由约束方程AX=b求得的解称为基解。 基可行解:满足非负条件的基解称为基可行解。 可行基: 对应于基可行解的基称为可行基。 注:基解的个数最多是Cnm个,基可行解的个数一般要小于基解的个数。,1 可行解与最优解:,最优解一定是可行解,但可行解不一定是最优解。,线性规划解之间的关系,基解不一定是可行解,可行解也不一定是基解。,2 可行解与基解:,3 可行解与基可行解:,基可行解一定是可行解,但可行解不一定是基解。,基可行解一定是基解, 但基解不一定是基可行解。,4 基解与基可行解:,5 最优解与基解:,最优解不一定是基解, 基解也不一定是最优解。,问题:最优解与基本可行解?,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)的凸组合。,顶点:设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. 如果目标函数在多个顶点上达到最优,则目标函数在这些顶点的凸组合上也达到最优。,2. 如果可行域为无界,则可能有最优解,也可能无最优解,若有最优解,则必在某个顶点上达到最优。,1.线性规划问题的所有可行解构成的集合可行域是凸集,也可能是无界域; 2.可行域有有限个顶点,线性规划问题的每个基可行解对应于可行域的一个顶点; 3.若线性规划问题有最优解,必在可行域的某顶点上达到。,线性规划问题的几何意义:,4.如果目标函数在多个顶点上达到最优,则目标函数在这些顶点的凸组合上也达到最优,即线性规划问题有无群多最优解。,3 单纯形法,单纯形法的基本思路:,X1 CX1,X2 CX2,X3 CX3,Xn CXn,*,*,1. 初始基B1及所对应基可行解X1的确定;,2. Xj 的最优性判定;,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 最优性检验与解的判别 检验数:目标函数用非基变量表达后,非基变量的系数称为检验数。 1. 最优解的判别定理:若X(0)是线性规划问题的一个基可行解,如果对应的非基变量的检验数都小于等于零,则X(0)为最优解。 2. 无穷多最优解的判别定理:若X(0)是线性规划问题的一个基可行解,如果对应的非基变量的检验数都小于等于零,又存在某个非基变量的检验数等于零,则线性规划问题有无穷多最优解。 3. 无界解判别定理:若X(0)是线性规划问题的一个基可行解,若存在一非基变量的检验数大于零,而该非基变量的系数向量小于等于零,则该线性规划问题有无界解。,3.4 基变换 1.换入变量的确定:所有大于等于零的检验数中最大的对应的变量为换入变量。但也可以任选。 2.换出变量的确定:用换入变量的系数去除对应的常数项得,的正分量中最小的对应的基变量为换出变量。 设换入变量为xk,换出变量为xl,则alk 称为主元素,它所在的列称为主元列,它所在的行称为主元行。,3.5 迭代 利用高斯消去法或矩阵的初等变换将主元素变为1主元列的其它元素变为零的过程称为迭代。 迭代的形式包括:约束方程组法,系数矩阵法和单纯表法。, ,4 单纯形法的计算步骤,4.1 单纯形表 为了便于理解计算关系,以系数矩阵法为基础设计一种计算表来实现迭代过程。这种计算表称为单纯形表。, ,4.2 单纯形法的计算步骤 1. 找出初始可行基,确定初始可行解,建立初始单纯形表。 2. 检验非基变量的检验数,如果所有非基变量的检验数都小于等于零,则已得到最优解,停止计算,否则,转入下一步。 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, , , ,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 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
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号