第一章 线性规划及单纯形法

第 1页广西工学院财政经济系广西工学院财政经济系冯金丽冯金丽第一章 线性规划及单纯形法1.1 线性规划问题及其数学模型1.2 图解法1.3 单纯形法原理1.4 单纯形法计算步骤1.5 单纯形法进一步讨论1.6 应用举例第 2页广西工学院财政经济系广西工学院财政经济系冯金丽冯金丽本章学习要求n能建立实际问题的数学规划模型n理解线性规划模型的特点，标准型n掌握线性规划的图解法及其几何意义n掌握单纯形法原理n掌握运用单纯形表计算线性规划问题的步骤及解法n能用二阶段法和大 M法求解线性规划问题。第 3页广西工学院财政经济系广西工学院财政经济系冯金丽冯金丽1.1线性规划问题及其数学模型n一般线性规划问题及数学模型n线性规划数学模型的标准形式第 4页广西工学院财政经济系广西工学院财政经济系冯金丽冯金丽一、 一般线性规划问题及数学模型一般线性规划问题见教材 P6:例 1、例 2第 5页广西工学院财政经济系广西工学院财政经济系冯金丽冯金丽美佳公司生产美佳公司生产 、 两种家电，单件利润分别两种家电，单件利润分别为为 2千元、千元、 1千元。两种产品生产过程中均要使用千元。两种产品生产过程中均要使用 A 、B和和 C三种原材料，已知生产一件产品三种原材料，已知生产一件产品 ，消耗，消耗 A 、 B和和 C分别为分别为 0、 6、 1个单位，已知生产一件产品个单位，已知生产一件产品 ，消耗消耗 A 、 B和和 C分别为分别为 5、 2、 1个单位，而三种原材料个单位，而三种原材料每天的供应量分别为每天的供应量分别为 15、 24、 5个单位。请制定美佳个单位。请制定美佳公司的最佳生产方案，使该公司总利润最大。公司的最佳生产方案，使该公司总利润最大。例：美佳公司的生产计划问题第 6页广西工学院财政经济系广西工学院财政经济系冯金丽冯金丽数学模型的建立1、确定决策变量 通常由目标问题分解设设 x1代表生产 种家电数量；x2代表生产 种家电数量；2、分析并表达限制条件，包括约束条件 通常由等式或不等式表示。0x1+5x2156x1+2x224x1+ x2 5x1 0,x20决策 变 量 x1 x2 限制条件0 5 15约 束条件 6 2 241 1 5目 标 函数 2 1 max3、分析目标 是利润最大化MaxZ=2x1+x2第 7页广西工学院财政经济系广西工学院财政经济系冯金丽冯金丽二、线性规划模型标准形式min(max) z=c1x1+c2x2+cnxns.t. a11x1+a12x2+a1nxn (, )b1a21x1+a22x2+a2nxn (, )b2am1x1+am2x2+amnxn (, )bmx1, x2, , xn 0 (, Free)线性规划模型的目标函数必须是变量的线性函数，约束条件必须是变量的线性等式或不等式。如右的问题就不是线性规划问题：1.一般形式第 8页广西工学院财政经济系广西工学院财政经济系冯金丽冯金丽2.线性规划的标准形式目标函数为极大化，约束条件全部为等号约束，所有变量全部是非负的，这样的线性规划模型称为标准形式Max z=c1x1+c2x2+cnxns.t. a11x1+a12x2+a1nxn b1a21x1+a22x2+a2nxn b2am1x1+am2x2+amnxn bmx1, x2, , xn 0 第 9页广西工学院财政经济系广西工学院财政经济系冯金丽冯金丽3.线性规划模型用矩阵和向量表示max z=c1x1+c2x2+cnxns.t. a11x1+a12x2+a1nxn b1a21x1+a22x2+a2nxn b2am1x1+am2x2+amnxn bmx1, x2, , xn 0 价值系数工艺系数矩阵资源约束第 10页广西工学院财政经济系广西工学院财政经济系冯金丽冯金丽线性规划模型用矩阵和向量表示（续）因此，线性规划模型可以写成如下矩阵和向量的形式MaxZ =CXs.t. AX=bX0 第 11页广西工学院财政经济系广西工学院财政经济系冯金丽冯金丽4.线性规划模型总结线性规划模型的结构n目标函数 ： max， minn约束条件： ,=,n变量符号： 0, 0, Free线性规划的标准形式n目标函数： maxn约束条件 ： =n变量符号 ： 0MaxZ =CXs.t. AX=b X0 第 12页广西工学院财政经济系广西工学院财政经济系冯金丽冯金丽5.线性规划问题的标准化 极小化目标函数转化为极大化 小于等于约束条件转化为等号约束 大于等于约束条件转化为等号约束 变量没有符号限制（ Free）的标准化 变量小于等于 0的标准化第 13页广西工学院财政经济系广西工学院财政经济系冯金丽冯金丽min z=2x1-3x2+x3令 z=-z， z=-2x1+3x2-x3新的目标函数max z=-2x1+3x2-x3取得极小化的最优解时，这个最优解同时使原目标函数值取得最大化的最优解。但两个问题最优解的目标函数值相差一个负号。 极小化目标函数问题转化为极大化目标函数极小化目标函数问题转化为极大化目标函数例如，对于以下两个线性规划问题Max z=2x1+3x2s.t. x1+x23x21 (A)x1, x20Min z=-2x1-3x2s.t. x1+x23x21 (B)x1, x20它们的最优解都是 x1=2, x2=1，但 (A)的最大化的目标函数值为 max z=7， (B)的最小化的目标函数值为 min z=-7第 14页广西工学院财政经济系广西工学院财政经济系冯金丽冯金丽2x1+3x2-4x35引进 松弛变量松弛变量 (Slack variable) x40 2x1+3x2-4x3+x4=5如果有一个以上小于等于约束，要引进不同的松弛变量。例如：2x1+3x2-4x353x1-2x2+5x38在两个约束中分别引进松弛变量 x4， x502x1+3x2-4x3+x4 =53x1-2x2+5x3 +x5=8 小于等于约束条件转化为等号约束小于等于约束条件转化为等号约束第 15页广西工学院财政经济系广西工学院财政经济系冯金丽冯金丽 大于等于约束条件转化为等号约束大于等于约束条件转化为等号约束 将不等式约束变为等式约束。例如： 2x1+3x2-4x35 3x1-2x2+5x38 在两个约束的左边分别减去 剩余变量 x4， x50 2x1+3x2-4x3-x4 =5 3x1-2x2+5x3 -x5=8第 16页广西工学院财政经济系广西工学院财政经济系冯金丽冯金丽没有符号限制的变量，用 两个非负变量之差两个非负变量之差 表示。例如：min z=x1+2x2-3x3s.t. 2x1+3x2-4x353x1-2x2+5x38x10, x2:free, x30先将目标函数转化为极大化，并在约束中引进松弛变量，把不等式约束变为等式。Max z=-x1-2x2+3x3s.t. 2x1+3x2-4x3+x4 =53x1-2x2+5x3 -x5=8x10, x2:free, x3, x4, x50 变量没有符号限制变量没有符号限制 (Free)的标准化的标准化第 17页广西工学院财政经济系广西工学院财政经济系冯金丽冯金丽然后，令 x2=x2-x2”，其中 x2,x2”0。代入模型，消去 x2Max z=-x1-2(x2-x”2)+3x3s.t. 2x1+3(x2-x”2)-4x3+x4 =53x1-2(x2-x”2)+5x3 -x5=8x1, x2, x”2, x3, x4,x50整理，得到标准形式：Max z=-x1-2x2+x”2+3x3s.t. 2x1+3x2-3x”2-4x3+x4 =53x1-2x2+2x”2+5x3 -x5=8x1, x2, x”2, x3, x4,x50第 18页广西工学院财政经济系广西工学院财政经济系冯金丽冯金丽min z=x1+2x2-3x3s.t. 2x1+3x2-4x353x1-2x2+5x38x10, x20, x30max z=-x1-2x2+3x3s.t. 2x1+3x2-4x3+x4 =53x1-2x2+5x3 -x5=8x10, x20, x3, x4, x50令 x2=-x2， x20, 代入模型max z=-x1+2x2+3x3s.t. 2x1-3x2-4x3+x4 =53x1+2x2+5x3 -x5=8x10, x20, x3, x4, x50 变量小于等于变量小于等于 0的的标准化的的标准化第 19页广西工学院财政经济系广西工学院财政经济系冯金丽冯金丽课堂习题P38 1.6（ a）第 20页广西工学院财政经济系广西工学院财政经济系冯金丽冯金丽1.2 图解法n相关概念和图解法步骤n线性规划问题图解法求解的几种结果n结论第 21页广西工学院财政经济系广西工学院财政经济系冯金丽冯金丽模型中只有两个变量的线性规划问题，可以通过在平面上作图的方法求解。 可行解可行解 ：一个线性规划问题有解，是指能找出一组xj(j=1,2,n) 满足约束条件，称这组 xj为问题的可行解。 可行域：可行域： 通常线性规划问题总是含有多个可行解，全部可行解的集合为可行域。 最优解：最优解： 可行域中使目标函数为最优的可行解为最优解。 图解法的步骤：图解法的步骤： 建立坐标系，确定比例尺； 画出各约束条件的边界，定出可行域； 画出目标函数的一根等值线，平移得出最优解； 算出目标函数最优值。1.相关概念和图解法步骤第 22页广西工学院财政经济系广西工学院财政经济系冯金丽冯金丽线性规划的图解max z=x1+3x2s.t. x1+ x26-x1+2x28x1 0, x20可行域目标函数等值线最优解6543211 2 3 4 5 6-8 -7 -6 -5 -4 -3 -2 -1 0x1x2z=6z=3z=9z=12问题： 1、线性规划的最优解是否可能位于可行域的内部？2、线性规划的最优解是否可能位于可行域的边界上？第 23页广西工学院财政经济系广西工学院财政经济系冯金丽冯金丽 唯一最优解唯一最优解 无穷多最优解无穷多最优解 无界解（无界解（ 可行域无界）可行域无界） 无解（无可行解）无解（无可行解）2.线性规划问题图解法求解的几种结果1、唯一最优解（封闭）、唯一最优解（封闭） 2、多个最优解（封闭）、多个最优解（封闭） 3、唯一最优解（开放）、唯一最优解（开放）4、多个最优解（开放）、多个最优解（开放） 5、目标函数无界（开放）、目标函数无界（开放） 6、无可行解、无可行解第 24页广西工学院财政经济系广西工学院财政经济系冯金丽冯金丽 线性规划问题解的形式 :唯一最优解，无穷多最优解，无界解，无可行解； 若 LP的可行域存在，即有可行解，则可行域是一个凸集； 若 LP的最优解存在，则一定可以在可行域的某个顶点达到，如果在某两个顶点上达到最优，则该 LP有无穷多最优解； 用图解法求解 LP时，如果可行域封闭，可比较可行域的顶点的目标函数值，得到最优解； 注意注意 用图解法如果可以得到封闭的可行域，则定有最优解存在； 如果可行域不封闭，则解的三种形式都可能出现，必须用目标函数等值线的平移来判断。3.结论第 25页广西工学院财政经济系广西工学院财政经济系冯金丽冯金丽1.maxZ=2x1+ x25x2156x1+2x2 24x1+ x2 5x1, x20唯一最优解2. maxZ=x1+ x2-2x1+x2 4x1- x2 2x1, x20无界解3.maxZ=3x1+9x2x1+3x2 22 -x1+x2 4 x1, x20无穷多最优解 4.maxZ=x1+ x2x1+x2 12x1+2x24x1, x20无解举例：第 26页广西工学院财政经济系广西工学院财政经济系冯金丽冯金丽课后作业P37 1.3(a)第 27页广西工学院财政经济系广西工学院财政经济系冯金丽冯金丽1.3 单纯形法原理nLP解的相关概念n凸集及其顶点n几个基本定理n单纯形法迭代原理第 28页广西工学院财政经济系广西工学院财政经济系冯金丽冯金丽x3=0x4=0max z=x1+2x2s.t. x1+x23x2 1x1, x2 0max z=x1+2x2s.t. x1+x2+ x3 =3x2 +x4=1x1, x2 ,x3, x40x1=0, x2=0x3=3, x4=1x1=0, x4=0 x2=1, x3=2x2=0, x3=0x1=3, x4=1x3=0, x4=0 x1=2, x2=1x1=0, x3=0 x2=3, x4=-2x2=0x1=0OABCD一 .LP解的相关概念1.可行域，可行解，最优解第 29页广西工学院财政经济系广西工学院财政经济系冯金丽冯金丽LP问题数学模型因此：可行解可行解 ：满足（ 1.7）（ 1.8）的解称为 LP的可行解；可行域可行域 ：全部可行解的集合；最优解最优解 ：使目标函数 (1.6)达到最大值的可行解第 30页广西工学院财政经济系广西工学院财政经济系冯金丽冯金丽定义定义 1：从 n个变量中任取 m个变量 x1,x2,xm，若这 m个变量对应的系数列向量 P1,P2,Pm线性无关，即对应系数列向量行列式0， 则