§1 单纯形法的基本思路和原理 由于线性规划的标准型中要求b≥0，若能找到一 个基是单位矩阵（各列向量顺序无关重要)，例如： 0 10 01 所得基本解一定是基本可行解，解中的各个变量或 等于某个b或等于零
§ 1 单纯形法的基本思路和原理 由于线性规划的标准型中要求 bj ≥0，若能找到一 个基是单位矩阵（各列向量顺序无关重要），例如： 所得基本解一定是基本可行解，解中的各个变量或 等于某个 bj 或等于零。 0 0 1 1 0 0 0 1 0
§1 单纯形法的基本思路和原理 第一次找到的可行基为单位矩阵（各列可以乱 序)，称之为初始可行基，相应的基本可行解叫初始 基本可行解。 本例中找到了一个基是单位矩阵： 100 B2=01 001 令其非基变量x1=x20,得初始基本可行解： x=0=0,S1=300,52=400,S3=250 注：苔找不到单位矩阵（各列可以乱序）的基作为初始可行基， 需要构造初给可行基
本例中找到了一个基是单位矩阵： 令其非基变量 x1=x2=0，得初始基本可行解： x1=0，x2=0，s1=300，s2=400，s3=250 § 1 单纯形法的基本思路和原理 第一次找到的可行基为单位矩阵（各列可以乱 序），称之为初始可行基，相应的基本可行解叫初始 基本可行解。 2 1 0 0 0 1 0 0 0 1 B 注：若找不到单位矩阵（各列可以乱序）的基作为初始可行基， 需要构造初始可行基
§1 单纯形法的基本思路和原理 二、最优性检验 判断已求得的基本可行解是否是最优解。 1.最优性检验的依据—检验数σ 目标函数 目标函数 约束等式中，非基变 基变量&非基变量 量移到右边，用非基 变量表示基变量 非基变量 则目标函数中变量系数即为其检验数，把x,的检验数 量检验数为0
1．最优性检验的依据——检验数 σj 二、最优性检验 判断已求得的基本可行解是否是最优解。 § 1 单纯形法的基本思路和原理 基变量&非基变量 目标函数 非基变量 目标函数 约束等式中，非基变 量移到右边，用非基 变量表示基变量 则目标函数中变量系数即为其检验数，把 xi的检验数 记为 σi。所有基变量检验数为0
§1 单纯形法的基本思路和原理 例题中找到一个初始可行基： 100 B2= 010 00 1 目标函数为50x1+100x2,由于初始可行解中x1,x2为 非基变量，所以此目标函数已经用非基变量表示了，无 需代换出基变量。各检验数为： 03=0,04=0,05=0
§ 1 单纯形法的基本思路和原理 例题中找到一个初始可行基： 目标函数为50x1+100x2，由于初始可行解中x1，x2 为 非基变量，所以此目标函数已经用非基变量表示了，无 需代换出基变量。各检验数为： σ1=50，σ2=100，σ3=0，σ4=0，σ5=0 2 1 0 0 0 1 0 0 0 1 B
§1 单纯形法的基本思路和原理 2.最优解判别定理 求最大目标函数的问题中，若某个基本可行解所有 检验数0，≤0，则该解是最优解。 通俗地解释最优解判别定理，设用非基变量表示的 目标函数如下所示： z=+∑0 于求目标函数最值的情况，只需把0≤0改为o之0
§ 1 单纯形法的基本思路和原理 2．最优解判别定理 求最大目标函数的问题中，若某个基本可行解所有 检验数 σj ≤0，则该解是最优解。 通俗地解释最优解判别定理，设用非基变量表示的 目标函数如下所示： 注：对于求目标函数最小值的情况，只需把σj ≤0改为σj ≥0。 0 j j j J z z x