《第一章 线性规划及单纯形法教材课程》由会员分享，可在线阅读，更多相关《第一章 线性规划及单纯形法教材课程（85页珍藏版）》请在金锄头文库上搜索。
1、第一章 线性规划及单纯形法,1.1 线性规划问题及其数学模型 1.2 图解法 1.3 单纯形法原理 1.4 单纯形法计算步骤 1.5 单纯形法进一步讨论 1.6 应用举例,本章学习要求,能建立实际问题的数学规划模型 理解线性规划模型的特点，标准型 掌握线性规划的图解法及其几何意义 掌握单纯形法原理 掌握运用单纯形表计算线性规划问题的步骤及解法 能用二阶段法和大M法求解线性规划问题。,1.1线性规划问题及其数学模型,一般线性规划问题及数学模型 线性规划数学模型的标准形式,美佳公司生产、两种家电，单件利润分别为2千元、1千元。两种产品生产过程中均要使用A 、B和C三种原材料，已知生产一件产品，消耗
2、A 、B和C分别为0、6、1个单位，已知生产一件产品 ，消耗A 、B和C分别为5、2、1个单位，而三种原材料每天的供应量分别为15、24、5个单位。请制定美佳公司的最佳生产方案，使该公司总利润最大。,例：美佳公司的生产计划问题,数学模型的建立,1、确定决策变量通常由目标问题分解 设x1代表生产种家电数量； x2代表生产种家电数量；,2、分析并表达限制条件，包括约束条件通常由等式或不等式表示。 0 x1+5x215 6x1+2x224 x1+ x2 5 x1 0,x20,3、分析目标是利润最大化 MaxZ=2x1+x2,二、线性规划模型标准形式,min(max) z=c1x1+c2x2+cnxn
3、 s.t. a11x1+a12x2+a1nxn (, )b1 a21x1+a22x2+a2nxn (, )b2 am1x1+am2x2+amnxn (, )bm x1, x2, , xn 0 (, Free),线性规划模型的目标函数必须是变量的线性函数，约束条件必须是变量的线性等式或不等式。如右的问题就不是线性规划问题：,1.一般形式,2.线性规划的标准形式,目标函数为极大化，约束条件全部为等号约束，所有变量全部是非负的，这样的线性规划模型称为标准形式 Max z=c1x1+c2x2+cnxn s.t. a11x1+a12x2+a1nxn b1 a21x1+a22x2+a2nxn b2 am1
4、x1+am2x2+amnxn bm x1, x2, , xn 0,3.线性规划模型用矩阵和向量表示,max z=c1x1+c2x2+cnxn s.t. a11x1+a12x2+a1nxn b1 a21x1+a22x2+a2nxn b2 am1x1+am2x2+amnxn bm x1, x2, , xn 0,价值系数,工艺系数矩阵,资源约束,线性规划模型用矩阵和向量表示（续）,因此，线性规划模型可以写成如下矩阵和向量的形式,MaxZ =CX s.t. AX=b X0,4.线性规划模型总结,线性规划模型的结构 目标函数 ：max，min 约束条件：,=, 变量符号：0, 0, Free 线性规划的
5、标准形式 目标函数：max 约束条件：= 变量符号：0,MaxZ =CX s.t. AX=b X0,5.线性规划问题的标准化,极小化目标函数转化为极大化 小于等于约束条件转化为等号约束 大于等于约束条件转化为等号约束 变量没有符号限制（Free）的标准化 变量小于等于0的标准化,min z=2x1-3x2+x3 令 z=-z，z=-2x1+3x2-x3 新的目标函数 max z=-2x1+3x2-x3 取得极小化的最优解时，这个最优解同时使原目标函数值取得最大化的最优解。但两个问题最优解的目标函数值相差一个负号。,极小化目标函数问题转化为极大化目标函数,例如，对于以下两个线性规划问题,Max
6、z=2x1+3x2 s.t. x1+x23 x21 (A) x1, x20,Min z=-2x1-3x2 s.t. x1+x23 x21 (B) x1, x20,它们的最优解都是x1=2, x2=1，但(A)的最大化的目标函数值为max z=7，(B)的最小化的目标函数值为min z=-7,2x1+3x2-4x35 引进松弛变量(Slack variable) x40 2x1+3x2-4x3+x4=5 如果有一个以上小于等于约束，要引进不同的松弛变量。例如： 2x1+3x2-4x35 3x1-2x2+5x38 在两个约束中分别引进松弛变量x4，x50 2x1+3x2-4x3+x4 =5 3x1
7、-2x2+5x3 +x5=8,小于等于约束条件转化为等号约束,大于等于约束条件转化为等号约束,将不等式约束变为等式约束。例如： 2x1+3x2-4x35 3x1-2x2+5x38 在两个约束的左边分别减去剩余变量x4，x50 2x1+3x2-4x3-x4 =5 3x1-2x2+5x3 -x5=8,没有符号限制的变量，用两个非负变量之差表示。例如： min z=x1+2x2-3x3 s.t. 2x1+3x2-4x35 3x1-2x2+5x38 x10, x2:free, x30 先将目标函数转化为极大化，并在约束中引进松弛变量，把不等式约束变为等式。 Max z=-x1-2x2+3x3 s.t.
8、 2x1+3x2-4x3+x4 =5 3x1-2x2+5x3 -x5=8 x10, x2:free, x3, x4, x50,变量没有符号限制(Free)的标准化,然后，令x2=x2-x2”，其中x2,x2”0。代入模型，消去x2 Max z=-x1-2(x2-x”2)+3x3 s.t. 2x1+3(x2-x”2)-4x3+x4 =5 3x1-2(x2-x”2)+5x3 -x5=8 x1, x2, x”2, x3, x4,x50 整理，得到标准形式： Max z=-x1-2x2+x”2+3x3 s.t. 2x1+3x2-3x”2-4x3+x4 =5 3x1-2x2+2x”2+5x3 -x5=8
9、 x1, x2, x”2, x3, x4,x50,min z=x1+2x2-3x3 s.t. 2x1+3x2-4x35 3x1-2x2+5x38 x10, x20, x30 max z=-x1-2x2+3x3 s.t. 2x1+3x2-4x3+x4 =5 3x1-2x2+5x3 -x5=8 x10, x20, x3, x4, x50 令 x2=-x2，x20, 代入模型 max z=-x1+2x2+3x3 s.t. 2x1-3x2-4x3+x4 =5 3x1+2x2+5x3 -x5=8 x10, x20, x3, x4, x50,变量小于等于0的的标准化,课堂习题 P38 1.6（a）,1.2
10、 图解法,相关概念和图解法步骤 线性规划问题图解法求解的几种结果 结论,模型中只有两个变量的线性规划问题，可以通过在平面上作图的方法求解。 可行解：一个线性规划问题有解，是指能找出一组xj(j=1,2,n)满足约束条件，称这组xj为问题的可行解。 可行域：通常线性规划问题总是含有多个可行解，全部可行解的集合为可行域。 最优解：可行域中使目标函数为最优的可行解为最优解。 图解法的步骤： 建立坐标系，确定比例尺； 画出各约束条件的边界，定出可行域； 画出目标函数的一根等值线，平移得出最优解； 算出目标函数最优值。,1.相关概念和图解法步骤,线性规划的图解,max z=x1+3x2 s.t. x1+
11、 x26 -x1+2x28 x1 0, x20,可行域,目标函数等值线,最优解,z=6,z=3,z=9,z=12,问题：1、线性规划的最优解是否可能位于可行域的内部？ 2、线性规划的最优解是否可能位于可行域的边界上？,唯一最优解 无穷多最优解 无界解（可行域无界） 无解（无可行解）,2.线性规划问题图解法求解的几种结果,1、唯一最优解（封闭）,2、多个最优解（封闭）,3、唯一最优解（开放）,4、多个最优解（开放）,5、目标函数无界（开放）,6、无可行解,线性规划问题解的形式:唯一最优解，无穷多最优解，无界解，无可行解； 若LP的可行域存在，即有可行解，则可行域是一个凸集； 若LP的最优解存在，
12、则一定可以在可行域的某个顶点达到，如果在某两个顶点上达到最优，则该LP有无穷多最优解； 用图解法求解LP时，如果可行域封闭，可比较可行域的顶点的目标函数值，得到最优解； 注意 用图解法如果可以得到封闭的可行域，则定有最优解存在； 如果可行域不封闭，则解的三种形式都可能出现，必须用目标函数等值线的平移来判断。,3.结论,1.maxZ=2x1+ x2 5x215 6x1+2x2 24 x1+ x2 5 x1, x20 唯一最优解 2. maxZ=x1+ x2 -2x1+x2 4 x1- x2 2 x1, x20 无界解,3.maxZ=3x1+9x2 x1+3x2 22 -x1+x2 4 x1, x
13、20 无穷多最优解,4.maxZ=x1+ x2 x1+x2 1 2x1+2x24 x1, x20 无解,举例：,课后作业 P37 1.3(a),1.3 单纯形法原理,LP解的相关概念 凸集及其顶点 几个基本定理 单纯形法迭代原理,x3=0,x4=0,max z=x1+2x2 s.t. x1+x23 x2 1 x1, x2 0,max z=x1+2x2 s.t. x1+x2+ x3 =3 x2 +x4=1 x1, x2 ,x3, x40,x1=0, x2=0 x3=3, x4=1,x1=0, x4=0 x2=1, x3=2,x2=0, x3=0 x1=3, x4=1,x3=0, x4=0 x1=
14、2, x2=1,x1=0, x3=0 x2=3, x4=-2,x2=0,x1=0,O,A,B,C,D,一.LP解的相关概念,1.可行域，可行解，最优解,LP问题数学模型,因此： 可行解：满足（1.7）（1.8）的解称为LP的可行解； 可行域：全部可行解的集合； 最优解：使目标函数(1.6)达到最大值的可行解,定义1：从n个变量中任取m个变量x1,x2,xm，若这m个变量对应的系数列向量P1,P2,Pm线性无关，即对应系数列向量行列式0， 则称B=(P1,P2,Pm )为基矩阵，简称基， x1,x2,xm为基变量，其余n-m变量为非基变量。 定义2：在约束方程(1.7)中，令所有非基变量为0，根
15、据克莱姆法则，则(1.7)有唯一解。令x1 1 ,x2 2,xm m，称为一组基解。 基可行解：满足（1.8）中的基解为基可行解，即基解中每一分量均非负。 可行基：基可行解对应的基。 退化解：基变量中有分量为0的解。 线性规划的基可行解就是可行域的顶点。,2.基，基变量，非基变量；基解，基可行解，可行基,max z=x1+2x2 s.t. x1+x23 x2 1 x1, x2 0,max z=x1+2x2 s.t. x1+x2+ x3 =3 x2 +x4=1 x1, x2 ,x3, x40,x1=0, x2=0 x3=3, x4=1 基可行解,x1=0, x4=0 x2=1, x3=2 基可行解,x2=0, x3=0 x1=3, x4=1 基可行解,x3=0, x4=0 x1=2, x2=1 基可行解,x1=0, x3=0 x2=3, x4=-2 是基解，但不是可行解,O,A,B,x3=0,x4=0,x2=0,x1=0,C,D,可行域,课本P10 例4,二 . 凸集和顶点,1.凸集 如果集合C中任意两点x1，x2，其连线上的所有点也都是集合C中的点，则称C为凸集，其中x1，x2的连线可以表示为： x1 （1）x2(01) 数学解析式为： x1 C， x2 C，有x1 （1）x2C (01) ，则C为凸集。 2.顶点 如果集合C中不
