线性规划及其对偶问题.pptVIP

2.1.1 线性规划问题的数学模型 （一）、问题的提出 （二）、数学模型  1、 2、线性规划数学模型的一般形式 3、规划类型 2.1.2 线性规划问题解的概念 （一）、求解方法 （二）、线性规划问题的解 2.1.3 求解线性规划问题的图解法 例、 2.1.4 求解线性规划问题的单纯形法 （三）、单纯形法 其步骤总结如下： （四）、单纯形表 练习 2.1.5 单纯形法的进一步讨论 ⑵.两阶段法： （二）、线性规划小结 课堂练习 2.1.6 线性规划模型的应用 例题1： 例题2： 例题3： 对偶单纯形法的基本思想 从原规划的一个基本解出发，此基本解不一定可行，但它对应着一个对偶可行解（检验数非正），所以也可以说是从一个对偶可行解出发；然后检验原规划的基本解是否可行，即是否有负的分量，如果有小于零的分量，则进行迭代，求另一个基本解，此基本解对应着另一个对偶可行解（检验数非正）。 2.2.4 对偶单纯形法 如果得到的基本解的分量皆非负则该基本解为最优解。也就是说，对偶单纯形法在迭代过程中始终保持对偶解的可行性（即检验数非正），使原规划的基本解由不可行逐步变为可行，当同时得到对偶规划与原规划的可行解时，便得到原规划的最优解。 对偶单纯形法 应用前提：有一个基，其对应的基满足: ① 单纯形表的检验数行全部非正（对偶可行）； ② 变量取值可有负数（非可行解）。 注：通过矩阵行变换运算，使所有相应变量取值均为非负数即得到最优单纯形表。 (1)建立初始对偶单纯形表,对应一个基本解,所有检验数均非正,转2； (2)若b’≥0,则得到最优解,停止;否则,若有bk0则选k行的基变量为出基变量,转3 (3)若所有akj’≥0( j = 1,2,…,n )，则原问题无可行解,停止;否则,若有akj’0 则选 ?=min{?j’ / akj’┃akj’0}=?r’/akr’ 那么 xr 为进基变量,转4； (4)以akr’为转轴元,作矩阵行变换使其变为1,该列其他元变为0,转2。 对偶单纯形法求解线性规划问题过程： 例2.11：求解线性规划问题： 解：标准化： max z = - 2x1 - 3x2 - 4x3 s.t. -x1-2x2-x3+x4= -3 -2x1+x2-3x3+x5= -4 x1,x2,x3,x4,x5 ≥ 0 min f = 2x1 + 3x2 + 4x3 s.t. x1 + 2x2 + x3 ≥ 3 2x1 - x2 + x3 ≥ 4 x1 , x2 , x3 ≥ 0 表格对偶单纯形法 单纯形法和对偶单纯形法步骤 是 是 是 是 否 否 否 否 所有 所有 得到 最优解 计算 计算 典式对应原规划的基本解是可行的 典式对应原规划的基本解的检验数 所有 所有 计算 计算 以aek为中心元素进行迭代 以 aek为中心元素进行迭代 停 没有最优解 没有最优解 单纯形法 对偶单纯形法 对偶单纯形法的适用范围 对偶单纯形法适合于解如下形式的线性规划问题 在引入剩余变量化为标准型之后，约束等式两侧同乘-1，能够立即得到检验数全部非正的原规划基本解，可以直接建立初始对偶单纯形表进行求解，非常方便。 对于有些线性规划模型，如果在开始求解时不能很快使所有检验数非正，最好还是采用单纯形法求解。因为，这样可以免去为使检验数全部非正而作的许多工作。从这个意义上看，可以说，对偶单纯形法是单纯形法的一个补充。除此之外，在对线性规划进行灵敏度分析中有时也要用到对偶单纯形方法，可以简化计算。 2.3 灵敏度分析 (Sensitivity Analysis) 2.3.1 价值系数ck的变化分析 2.3.2 右端项b的变化分析 2.3.3 增加一个变量 2.3.4 增加一个约束条件 进一步理解最优单纯形表中各元素的含义 考虑问题 max z = c1 x1 + c2 x2 + … + cn xn s.t. a11x1 + a12x2 + … + a1nxn = b1 a21x1 + a22x2 + … + a2nxn = b2 . . . am1x1 + am2x2 + … + amnxn = bm x1