线性规划的部分.ppt

1、第二章线性规划的数学模型,教学重点： 1.学习经济管理数学模型建立的程序和方法 2.了解线性规划的图解法和解的几何意义。 3.了解线性规划问题解的概念。 教学难点： 线性规划问题解的概念：基、基本解、基本可行解。,第二章线性规划的数学模型,1.线性规划的数学模型 2.线性规划的图解法 3.线性规划的标准型 4.线性规划解的概念,线性规划的数学模型,1.每个问题都追求一个目标，称为目标函数； 2.问题中有若干个约束条件； 3.所有问题的变量都是非负的； 求一个线性函数的极大或极小值，它满足一组线性等式或不等式。,线性规划的一般形式:,max（或min）z = c1x1 + c2x2 + + cn

2、xn a11x1 + a12x2 + a1nxn （ = ）b1 a21x1 + a22x2 + a2nxn （ = ）b2 s.t. am1x1 + am2x2 + amnxn （ = ）bm xj 0 （j=1，2 n）,线性规划的图解法,只有两个决策变量的线性规划问题，这时可以通过图解的方法来求解。图解法具有简单、直观、便于初学者窥探线性规划基本原理和几何意义等优点。,线性规划的图解法,（1）有唯一的最优解；（在一个顶点） （2）有无穷多组最优解；（在两个顶点） （3）无界解（无有限最优解） （4）无可行解（可行域为空）,线性规划的图解法,步骤： （1）建立平面直角坐标系； （2）画出约

3、束条件，找出可行域（凸多边形） （3）画出目标函数等值线，并确定其变化方向； （4）根据目标函数等值线变化的方向得到最优解； （5）将最优解和最优目标函数值表示出。,线性规划的标准型:,Max z = c1x1 + c2x2 + + cnxn a11x1 + a12x2 + a1nxn = b1 a21x1 + a22x2 + a2nxn = b2 s.t. am1x1 + am2x2 + amnxn = bm xj 0 （j=1，2 n）,（1）和式,（2）向量式,（3）矩阵式,关于标准型解的若干基本概念,线性规划问题 ：,可行解：满足上述约束条件(2.2)，(2.3)的解 ， 称为线性规划

4、问题的可行解。全部可行解的集合称为可行域。 非可行解:满足约束条件（2.2）但不满足非负条件（2.3）的解 X 称为非可行解 最优解：使目标函数(2.1)达到最大值的可行解称为最优解。 基：设 A 为约束方程组(2.2)的 mn 阶系数矩阵，(设nm)， 其秩为m，B是矩阵A中的一个mm阶的满秩子系数矩阵，称B是线性 规划问题的一个基。,线性规划标准型问题解的关系,约束方程的 解空间,基解,可行解,非可行解,基 可行解,第三章 单纯型法,单纯形法迭代的基本思路是：先找出一个基可行解，判断其是否为最优解，如果为否，则转换到相邻的基可行解，并使目标函数值不断增大，一直找到最优解为止。,单纯形法的步

5、骤,（一）确定初始基本可行解 用松弛变量的列向量构成初始基； （二）进行最优检验 计算非基变量的检验数。 将基变量的检验数0也视为其检验数，,注意：xj 的检验数 是当z 表示为非基变量的函数时 目标函数中xj 的系数。基变量的检验数为零。,最优性判别定理： 若基可行解对应的检验数 0 ( j=1，2，,n) 则此解是最优解，否则不是最优解。,（三）基变换,求一个改进的、“相邻”的可行基，一个基变量,将变成非基变量（换出），一个非基变量将变成 基变,量（换入）。,(1),换入变量的确定,一般，当,|,0=,s,k,，取,x,k,为换入变量。,第k列为主元列。,L行为主元行，alk为主元素,（四

6、）旋转（迭代）运算 求新的可行基所对应的基可行解。 以alk为主元素，把Pk化成单位向量。,(1) 最优性判别定理 若基可行解对应的检验数 0 ( j=1，2，,n)，则此解是最优解，否则不是最优解。,结论,(4)当所有的 0，又对某个非基变量 ， 有 这表明可以找到另一顶点(基可行解)目标函数值也达到最大。由于该两点连线上的点也属可行域内的点，且目标函数值相等，即该线性规划问题有无穷多最优解。反之，当所有非基变量 的 O时，线性规划问题具有唯一最优解。,第四章 对偶问题和灵敏度分析,本章主要学习对偶问题的提出和形式、对偶理论、对偶单纯形法、影子价格和灵敏度分析。,23,一般的，原问题：max

7、 z = CX AX b X 0,对偶问题：min w = Yb YA C Y 0,比较： max z min w 决策变量为n个 约束条件为n个 约束条件为m个 决策变量为m个 “” “”,24,一般: max问题第i个约束取“”，则min问题第i个变量 0 ；, min问题第i个约束取“”，则max问题第i个变量 0 ；, 原问题第i个约束取等式，对偶问题第i个变量 无约束；, max问题第j个变量 0 ,则min问题第j个约束取“” ；, min问题第j个变量 0 ，则max问题第j个约束取“” ；, 原问题第j个变量无约束，对偶问题第j个约束取等式。,对偶理论,（1）对称性 对偶问题的

8、对偶为原问题。,26,推论： 推论(1) max问题任一可解的目标值为min问题最优目标值的一个下界； 推论(2)min问题任一可解的目标值为max问题最优目标值的一个上界 推论(3)若 min问题可行，但具有无界解，则对偶问题无可行解。 推论(4)若 max问题可行，但具有无界解，则对偶问题无可行解。 推论(5)若原问题可行，对偶问题不可行，则原问题具有无界解。,（3）最优性 设X*，Y*分别为原问题和对偶问题可行解，当CX*=Y*b时， X*，Y*分别为最优解。 （4）主对偶定理 若原问题有最优解，那么对偶问题也有最优解，且目标值相等。,（5）松弛性 若X*，Y*分别为原问题及对偶问题的可

9、行解，那么Ys*X*=0，Y*Xs*=0，当且仅当X*，Y*分别为最优解。 （6)检验数与解的关系 原问题非最优检验数的负值为对偶问题的一个基解(原问题最优检验数的负值为对偶问题的最优解)。,对偶单纯形法,对偶单纯形法的基本思路 根据对偶问题的对称性，若保证对偶问题的解可行（0），而在原问题非可行解的基础上，逐步达到基本可行解，也可以得到线性规划问题的最优解。 正则基： 满足0的基。,对偶单纯形法的计算方法,1.根据问题的标准型，找初始的正则基，列出初始单纯形表； 2.计算检验数（ 0 ）。进行最优检验，b列是否都大于零？是停止计算，否则进行下一步； 3.进行基变换 确定换出变量 确定换入变量

10、 4.进行迭代运算，再回到2.,对偶问题的经济含义影子价格及应用,对偶问题解的经济含义分析： 从单纯形法的矩阵描述中，目标函数取值 Z = CBB-1 b ，和检验数 CN - CBB-1N 中都有乘子 Y = CBB-1。 设B 是 max Z = CX | AX b，X 0 的最优基矩阵，由强对偶定理知 Z* =CX*= CBB-1b=Y*b=W* 由此, Z* b, Z* bi,（ Y*b） bi,= CBB-1= Y* 或,=,= yi*,第对偶问题的经济含义影子价格及应用,影子价格的定义 由上面分析对偶问题解中变量 yi* 的经济含义是在其他条件不变的情况下，单位第 i 种“资源”变

11、化所引起的目标函数最优值的变化。所以， yi* 描述了原始线性规划问题达到最优时（各种“资源”都处于最优的配置时），第 i 种“资源”的某种“价值”，故称其为第 i 种“资源”的影子价格。这正是经济学中机会价值的含义。,灵敏度分析,实际中所搜集数据不精确,有可能进行修改 ?,环境变化 数据发生变化,增加新的变量,增加新的约束,改变价值向量c,改变右端向量b,改变系数矩阵A,增加新的变量,增加新的等式约束,增加新的不等式约束,对已求解的LP, 遇到这些改变时,需要从头开始重新进行求解 ?,对解的影响 ?,如何有效修正现有的最优解 ?,灵敏度分析 (sensitivity analysis),优化

12、后分析 (post optimality analysis),第五节 灵敏度分析,线性规划问题的参数变化灵敏度分析 灵敏度（敏感性）分析 敏感性分析的重要性在于向决策者提供线性规划问题的最优解所能适应的环境条件变化的范围，环境条件变化时可能对经营状况带来何种影响，产生影响后的解决途径。 敏感性分析的类型： 1.模型中各个参数在什么范围变化时，最优基不发生改变。 2.模型中参数变化已经超出上述范围时，如何快速确定新的最优 基和最优解新的最优决策方案。 主要从两个角度考虑： 一是原最优解的最优性 二是原最优解的可行性,灵敏度分析,一、目标函数价值系数Cj的灵敏度分析 在最优解中，变量分为基变量和非基变量，因此对目标函数的价值系数也分为两部分考虑。 1.非基变量的目标函数价值系数Cj的灵敏度分析 2.基变量