教学 要求 ：第一章 线性规划和单纯形法 掌握线性规划的基本建模法和单纯形法基本原理 会在不同条件下运用单纯形法求解线性规划问题了解线性规划在经济和管理中的基本应用方法目 录p线性规划实例与模型p线性规划的图解法p单纯形法原理p改进单纯形法p应用目 录p线性规划实例与模型实用举例某公司通过市场调研，决定生产高中档新型拉杆箱。 某分销商决定买进该公司3个月内的全部产品。拉杆箱生产 需经过原材料剪裁、缝合、定型、检验和包装4过程。通过分析生产过程，得出：生产中档拉杆箱需要用 7/10小时剪裁、5/10小时缝合、1小时定型、1/10小时检验 包装；生产高档拉杆箱则需用1小时剪裁、5/6小时缝合、 2/3小时定型、1/4小时检验包装。由于公司生产能力有限， 3月内各部的最大生产时间为剪裁部630小时、缝合部600小 时、定型部708小时、检验包装部135小时。通过市场调研部和会计部的调查核算得出结论：生产 中档拉杆箱的利润是10元，高档拉杆箱的利润是9元。公司 应各生产多少中档和高档拉杆箱才能使公司利润最大？实用举例某公司通过市场调研，决定生产高中档新型拉杆箱。 某分销商决定买进该公司3个月内的全部产品。拉杆箱生产 需经过原材料剪裁、缝合、定型、检验和包装4过程。通过分析生产过程，得出：生产中档拉杆箱需要用 7/10小时剪裁、5/10小时缝合、1小时定型、1/10小时检 验包装；生产高档拉杆箱则需用1小时剪裁、5/6小时缝合、 2/3小时定型、1/4小时检验包装。由于公司生产能力有限 ，3月内各部的最大生产时间为剪裁部630小时、缝合部 600小时、定型部708小时、检验包装部135小时。通过市场调研部和会计部的调查核算得出结论：生产 中档拉杆箱的利润是10元，高档拉杆箱的利润是9元。公司 应各生产多少中档和高档拉杆箱才能使公司利润最大？可以通过线性规划求解！线性规划模型的建立 设生产中、高档拉杆箱数量分别为： 称为决策变量 。目标函数约束条件一般线性规划模型Max z = c1x1 + c2x2 + + cnxns.t. a11x1+ a12x2 + + a1nxn = b1 ( 0)a21x1+ a22x2 + + a2nxn = b2 ( 0):am1x1+ am2x2 + + amnxn= bm( 0)x1,x2 , ,xn 0s.t. 为约束限制 （Subject to） 的缩写(LP)x1 . . xnb1 . . bma11 a1n am1 amnx =b =A = c1 . . cnc =其中c=(c1,c2,cn)，称为价值系数向量；称为资源限制向量 X=(x1,x2,xn)T 称为决策变量向量称为技术系数矩阵(也 称消耗系数矩阵)一般线性规划模型线性规划模型的标准形式Max Z = c1x1 + c2x2 + + cnxnSubject to (s.t.)a11x1 + a12x2 + + a1nxn = b1 a21x1 + a22x2 + + a2nxn = b2 am1x1 + am2x2 + + amnxn= bmx1 0, x2 0, , xn 0 为了讨论方便，把最大化、等式约束型的线性规划称为线 性规划的标准型，即标准化原问题问题标标准化方法 目标标函 数Max f(x)Max f(x)Min f(x)Max f(x)约约束条 件引入松弛变量和人工变量引入松弛变量,不变变变量 不变对某个对某个是任意的 线性规划模型的标准化 例:将如下线性规划模型标准化：min z= x1 + 5 x2 - 8 x3 - x4 s.t. 2 x1 - 3 x2 + x3 + x4 20x1+ 2 x2 + 3 x3 - x4 302x2 + 2 x3 +3 x4- 50x1 , x3 , x4 0，x2取值无约束。 max z1=-x1-5 x2+8 x3 +x4 s.t. 2 x1 - 3 x2 + x3 + x4 20x1+ 2 x2 + 3 x3 - x4 302x2 + 2 x3 +3 x4- 50x1 , x3 , x4 0，x2取值无约束。 目标优化标准化线性规划模型的标准化Max z2 =-x1-5y2+5y3+8x3+x4 s.t. 2 x1 - 3 y2+3y3 + x3 + x4 20-x1- 2 y2 +2y3 - 3 x3 + x4 -30 -2y2 +2y3 - 2 x3 -3 x4 50x1 , x3 , x4 ,y2,y3 0 决策变量的标准化:y2 - y3 = x2max z1=-x1-5 x2+8 x3 +x4 s.t. 2 x1 - 3 x2 + x3 + x4 20x1+ 2 x2 + 3 x3 - x4 30 2x2 + 2 x3 +3 x4- 50x1 , x3 , x4 0，x2取值无约束 线性规划模型的标准化Max z2 =-x1-5y2+5y3+8x3+x4 s.t. 2 x1 - 3 y2+3y3 + x3 + x4 +x5 =20-x1- 2 y2 +2y3 - 3 x3 + x4 +x6 = -30 -2y2 +2y3 - 2 x3 -3 x4 +x7 = 50x1 , x3 , x4 , x5, x6, x7, y2, y3 0约束关系标准化Max z2 =-x1-5y2+5y3+8x3+x4 s.t. 2 x1 - 3 y2+3y3 + x3 + x4 20-x1- 2 y2 +2y3 - 3 x3 + x4 -30 -2y2 +2y3 - 2 x3 -3 x4 50x1 , x3 , x4 ,y2,y3 0 p可行解:满足所有约束条件的解x=（x1，x2，.，xn），所有可 行解的集合称为可行域。p基：设A是约束方程组的mn阶系数矩阵，秩为m， 是A中阶非奇异子矩阵（即 ），则称是线性规划问题的一 个基矩阵，简称基。B中的列向量称为基向量，与基向量对应的变 量x称为基变量，其它变量称为非基变量。 p基本解：令非基变量值为0，由Ax=b可求出一个解，这个解x称 为基本解。p基本可行解：满足非负条件的基本解称为基本可行解。p最优解：使目标函数达到最优值的可行解称为最优解。 线性规划的解 可行解、基本解、基本可行解的关 系可行解 基本解 基本可行解目 录p线性规划实例与模型p线性规划的图解法与基本性质线性规划的图解法当只有两个决策变量 时，可用图解法求解！例：用图解法求解以下线形规划问题 。max z=4x1+3x2 s.t. x162x282x1+3x218x10，x20x1 x2 L3：2x1+3x2=18可行域L1：x1=6L2：x2=4最优解B4x1+3x2解的特殊情况多个最优解解的特殊情况无可行解解的特殊情况无界解线性规划的基本性质 X可行域内部的点 可行解? 是 最优解? 不若线性规划有最 优解，则最优解必在可行 域的顶点上达到。凸集的概念 p凸集是线性规划中一个很重要的概念，凸集的一般定义为 ：如果在集合C中任意取两个点x1，x2，其连线上的所有点也 都在集合C中，则称集合C为凸集合。用数学解析式表达为： 对任意 ，均有 ，则称C是凸 集合。非凸集非凸集凸集线性规划的基本性质定理2.1：线性规划的可行域：是凸集（凸多面体）。引理2.1：线性规划的可行解 为基本可行解的 充分必要条件是x的正分量所对应的系数列向量是线性无关的， 即每个正分量都是一个基变量。 定理2.2：线性规划问题的基本可行解x对应于可行域的顶点 定理2.3：若线性规划有最优解，则最优解必在可行域的顶点上 达到。目 录p线性规划实例与模型p线性规划的图解法p单纯形法原理一、初始基本可行解的确定p考虑如下形式的线性规划问题 max z=c1x1+c2x2+.+cnxns.t. a11x1+a12x2+a1nxnb1a21x1+a22x2+a2nxnb2 (2.17）.am1x1+am2x2+ +amnxnbmx1，x2，.，xn0 （2.18） 对每个不等式约束引入一个非负松弛变量，得标准形式： max z=c1x1+c2x2+.+cn xn s.t. a11x1+a1nxn+xn+1 =b1a21x1+a2nxn +xn+2 =b2 （2.19）.am1x1+amn xn +xn+m =bm x1，x2，.，xn，xn+1，xn+m0是线性规划(2.19)的一个可行基。令 得由此得到一个初始基本可行解为二、最优性检验 p定理2.4：在最大化问题中，对于某个基本可行解，如果所有的 ，则这个基本可行解是最优解。在最小化问题中，对于某个基本可行解，如果所有 的 ，则这个基本可行解是最优解。单纯形法求解步骤p将所给问题化为标准形p找出一个初始可行基,建立初始单纯形表p检查所有检验数(若全为非负,则已得到最优解,计 算停止.否则继续下一步)p考察是否无解(若是,计算停止,否则继续下一步)p确定入基变量,出基变量p对初始单纯形表进行单纯形变换单纯形方法的一般步骤确定一个初始可行角点根据某种法则进行角点 的最优性判断不是最优角点是最优角点考察与当前角点相邻的 “更好”的 一个角点，并置为当前角点。根据某种法则进行LP的无 界或不可行判断无界或不可行还不能做出判断求 解 结 束单纯形法举例解：引进松驰变量x3, x4，化为标准形得：4 3 0 0 CBXBb x1 x2 x3 x4 b/y00x3x424262 3 1 0 24/2 3 2 0 1 26/30 4 3 0 04=4（03+02）；3=3（02+03）4 3 0 0 CBXBbx1 x2 x3 x4 b/y04x3x120/326/30 5/ 3 1 -2/31 2/3 0 1/3-104/3 0 1/3 0 -4/34 3 0 0CBXBb x1 x2 x3 x434x2x1460 1 3/5 -2/51 0 -2/5 3/536 0 0 -1/5