第1章 线性规划与单纯形法-第4、5节 运筹学ppt.pptVIP

第1章 线性规划与单纯形法 第4节 单纯形法原理及计算步骤 一、 举例 二、 单纯形法迭代原理 三、 单纯形表及其计算步骤 单纯形法求解线性规划的思路： 单纯形计算方法(Simplex method)是先求出一个初始基可行解，判断它是否最优，若不是最优，则转换到相邻的基可行解，使目标函数值不断增大，直到得出最优解为止。它是一种逐步逼近最优解的迭代方法。 普通单纯形法是最基本最简单的一种方法，它假定标准型系数矩阵A中可以观察到一个可行基（通常是一个单位矩阵或m个线性无关的单位向量组成的矩阵），可以通过解线性方程组求得基本可行解。 掌握好普通单纯形法，后面还将介绍大M单纯形法、两阶段单纯形法及对偶单纯形法，这些方法统称为单纯形法。 一、 举例 例1：求解线性规划： 解：所给问题是标准型，约束方程组(2)的增广矩阵为 系数矩阵A中含有一个3阶单位子阵，于是 是线性规划的一个基，相应的基变量是x3,x4,x5，非基变量是x1,x2 相应的目标函数值z=120+0。从式(5)看到，如果使x1或x2由非基变量转换为基变量，即由0转换为正数，那么将使目标函数值z增加；还可以看到，转换x2将比转换x1使z增加的更快。x2由0变为1，z增加10，x1由0变为1，z增加6。因此，考虑x2转换为进基变量。 基变量个数为R(A)=m=3，所以原来的基变量必须有1个转换为非基变量，成为出基变量。如何找出基变量？ x1仍为非基变量，故x1 =0,约束方程组为： 在式(4)中，x2和x3的位置进行转换，为此，需要把式(2)中的x2的系数变为单位向量e1=(1,0,0)T。过程为：1)把式（2）的第一行除以元素a12(即除以2)2)把式（2）的第二行减去（1-1） 从而得到： 从而确定了x4为出基变量。将式(7)中x1的系数向量变为单位向量e2=(0，1，0)T，具体方法: 基变量转换为x1,x2,x5，其对应的基为B2=(P1,P2,P5) 令非基变量x3=x4=0,得到对应于基B2的基可行解 小结：求解线性规划问题的基本思路 1、构造初始可行基; 2、求出基可行解（顶点）; 3、最优性检验：判断是否最优解； 4、基变化，转2。要保证目标函数值比 原来更优。 第1步 确定初始可行基 第2步 确定初始基可行解 第3步 最优性检验 分析目标函数 第4步 基变换 换入基变量： 继续迭代, 可得到: 结合图解法分析 为了确定初始基可行解，要首先找出初始可行基，其方法如下。 (1)直接观察 (2)加松弛变量 (3)加非负的人工变量 约束方程组的系数矩阵A中含有m阶单位子阵 (2)加松弛变量 对所有约束条件是“≤”形式的不等式，可以利用化为标准型的方法，在每个约束条件的左端加上一个松弛变量。 经过整理，重新对 及 进行编号，则可得下列方程组： x1,x2,…,xm 为松弛变量 (3)加非负的人工变量 对所有约束条件是“≥”形式的不等式及等式约束情况，若不存在单位矩阵时，就采用人造基方法。 即对不等式约束减去一个非负的剩余变量后，再加上一个非负的人工变量； 对于等式约束再加上一个非负的人工变量，总能得到一个单位矩阵。 2.最优性检验及解的判别 为了检验X(0)是否是最优解，将式(12)所表示的基变量 称 为解的检验数。 最优解的判别定理： (1) 若 为基可行解且全 部 ，则 为最优解。 (2) 唯一最优解判别定理： 若所有 ,则存在唯一最优解。 (4)无穷多最优解判定定理： 假设 是目标函数达到最大值的顶点，那么这些顶点的凸组合，即 3.从一个基可行解转换到相邻的基可行解。 (1)确定换入基的变量。 假设只有一个检验数 (2)确定换出基的变量 仍令非基变量 现考虑以下形式的约束方程组： 设x1,x2,…,xm为基变量，对应的系数矩阵是m×m单位阵I，它是可