单纯形法的计算步骤及应用.ppt

单纯形法的计算步骤及应用 单纯形法的计算步骤及应用 单纯形法介绍及相关问题研究 单纯形法的计算步骤 单纯形法应用实例分析 总结 单纯形法介绍及相关问题 单纯形法的策略是从一个已知的初始基本可行解x0 或者说从可行域的某一个顶点 出发 转换到另一个基本可行解 或者另一个顶点 x1 使s x0 s x1 再从x1转到x2 依次类推使得s x0 s x1 s x2 s x3 直到目标函数达到最大值时就得到最优解 每一次转换称之为一次迭代 由于基本可行解的个数是有限的 所以经过有限次迭代 一定可以达到最优解 1 初始基本可行解的确定 2 怎样由一个基本可行解迭代出另一个基本可行解 3 怎样确定可以使目标函数有较大上升的基本可行解 单纯形法介绍及相关问题 1 初始基本可行解的确定为了确定初始基本可行解 要首先找出初始可行基 一个实际的线性规划问题 经过化成标准型之后 若约束方程的系数矩阵中出现了m个线性独立的单位向量 那么这m个单位向量就可以作为一个初始可行基 比如一个小于等于约束在化为标准型时 每增加一个非负的松弛变量 就会产生一个单位向量 如果所有的约束都是小于等于型 那么产生的单位向量正好为m个 单纯形法介绍及相关问题 标准型线性规划问题maxs c1x1 c2x2 cnxns t a11x1 a12x2 a1nxn b1a21x1 a22x2 a2nxn b2an1x1 an2x2 annxn bnxj 0 j 1 2 n 单纯形法介绍及相关问题 例1已知约束如下3x1 x2 22x1 2x2 1 2x1 x2 3x1 x2 0求基本可行解 解 化为标准型3x1 x2 x3 22x1 2x2 x4 1 2x1 x2 x5 3xj 0 j 1 2 5 其中即为一个可行基 单纯形法介绍及相关问题 如果除了小于等于形式的约束之外还有等于或者大于等于形式的约束 那么 小于等于约束加松弛变量所产生的单位向量就不足m个 对于等式形式的约束 可以采用一个非负的人工变量 也即人为的制造一个单位向量的办法 对于大于等于的约束 在化标准型时减去非负的剩余变量 由于剩余变量所对应的向量不是单位向量 因此 再采用等于约束的处理办法 加上一个人工变量 单纯形法介绍及相关问题 例2 已知约束如下x1 x2 x3 5 6x1 10 x2 5x3 205x1 3x2 x3 15xj 0 j 1 2 3 求一初始可行基 解 先化为标准型x1 x2 x3 5 6x1 10 x2 5x3 x4 205x1 3x2 x3 x5 15xj 0 j 1 2 5 引入人工变量x1 x2 x3 x6 5 6x1 10 x2 5x3 x4 205x1 3x2 x3 x5 x7 15xj 0 j 1 2 7 其中x6与x7为两个人工变量 则下面两向量即为一个初始可行基 单纯形法介绍及相关问题 根据上述办法 我们总有可以找到m个线性无关的单位向量 构成初始可行基 假如对约束方程经过整理 重新对xj及aij i 1 2 m j 1 2 n 进行编号 总可以得到以下方程组 x1 a1 m 1xm 1 a1nxn b1x2 a2 m 1xm 1 a2nxn b2 4 10 xm am m 1xm 1 amnxn bmxj 0 j 1 2 n 这样就得到一个单位 m m 矩阵作为初始可行基 将式 4 10 移项得x1 b1 a1 m 1xm 1 a1nxnx2 b2 a2 m 1xm 1 a2nxn 4 11 xm bm am m 1xm 1 amnxn令xm 1 xm 2 xn 0 由式 4 11 可得xi bi i 1 2 m 根据线性规划标准型的要求bi 0 所以就得到一个初始基本可行解x x1 x2 xm 0 0 T b1 b2 bm 0 0 T 单纯形法介绍及相关问题 2 基本可行解之间的迭代在讨论中我们假设对方程组 4 10 的系数增广矩阵p1 plpmpm 1pkpnb 4 12 施以初等变换 就可以把任何一个列向量化为单位向量 例如把pk m 1 k n 化为单位向量 这时在原来的基向量p1 pl pm中必然有一个向量要化为非单位向量 而其余m 1个向量仍保持为单位向量 加上pk就得到一组新的可行基 单纯形法介绍及相关问题 假定向量pk中的第l个分量al k 0 那么 基变换的步骤为将增广矩阵 4 12 中的第l行除以al k得到 4 13 将式 4 12 中pk列的各元素 除al k已变为1以外 都变为0 这可将式 4 13 乘以 al k i 1 2 m i l 后与第i行相加 从而得到新的第i行 各元素的变换公式为 4 14 4 15 单纯形法介绍及相关问题 4 16 4 17 这样经过变换以后就得到了新的增广矩阵p1 plpmpm 1pkpnb其中p1 p2 pl 1 pl 1 pm和pk为一个m阶的单位矩阵 构成一组新基 当非基变量xm 1 xl xn为零时 就得到一个新的基本解 单纯形法介绍及相关问题 为了保证新得到的基本解的可行性 要求 i 1 2 m 由式 4 15 可以看出 必须al k 0 也就是说 主元只能从向量的正分量中选取 其次 从式 4 17 中看出 必须当时上式自然满足 所以当限定ai k 0时 上式可写为此式说明 主元所在的行l应使比值去最小值的序号i 即 4 18 这一按最小比值来确定主元所在行的规则称为 规则 单纯形法介绍及相关问题 例3 已知约束x1 3x4 x5 2x2 2x4 2x5 1x3 2x4 x5 3xj 0 j 1 2 5 试把p4变为基向量 并求相应的基本可行解 解 把约束方程系数矩阵及右项列成表由表可以看出p1 p2 p3构成可行基 与其相对应的基本可行解是x 2 1 3 0 0 T把p4变为单位向量引入基底 首先选择主元所在的行 p2为换出向量 p4为换入向量 单纯形法介绍及相关问题 由表可以看出p1 p3 p4都是单位向量 构成可行基 与其相对应的基本可行解是x 1 2 0 4 1 2 0 T 单纯形法介绍及相关问题 3 最优解的判别准则及换入向量的确定在讨论基本可行解之间的迭代是 所导出的规则 解决了如何确定换出向量的问题 所有的讨论没有涉及到目标函数 也就是说 没有顾及如何选择换入向量使得到的基本可行解所对应的目标函数值有所改善 另外 也没有顾及基本可行解的最优性 即满足什么条件的基本可行解是最优解 考虑下述形式的线性规划问题maxs c1x1 c2x2 cmxm cm 1xm 1 cnxn 4 19a s t x1 a1 m 1xm 1 a1nxn b1x2 a2 m 1xm 1 a2nxn b2 4 19b xm am m 1xm 1 amnxn bmxj 0 j 1 2 n 4 19c 如前所述 引进松弛变量 人工变量等 再加以整理可以把任何一个实际的线性规划问题化为这种形式 因此它具有一般性 以p1 p2 pm为一组可行基 则求解 4 20 所得的唯一解就是一个基本可行解 其对应的目标函数值是 4 21 单纯形法介绍及相关问题 由于p1 p2 pm为线性无关的单位向量 应有 j m 1 m 2 n 4 22 假定x为式 4 19 的一个基本可行解 因此有 4 23 把式 4 22 代入式 4 23 得整理得 4 24 比较式 4 20 与式 4 24 有 单纯形法介绍及相关问题 4 25 记可行解x所对应的目标函数值为s 并注意到式 4 25 有 4 26 其中 4 27 由于x为一任意可行解 故有xj 0 j m 1 n 所以当时 就一定有 单纯形法介绍及相关问题 故s0是目标函数所能取得的最大值 x0即为其最优解 其中 j j m 1 n 称为非基变量的检验数 其实从式 4 25 看 基变量的检验数为 j 0 j 1 2 m 定理4 4若线性规划问题的所有变量的检验数 j 0 j 1 2 n 则基本可行解 不管退化与否 就是最有解 例4判定 4 5 0 0 T是否为如下线性规划问题的最优解 maxs x1 3x2 2x3 2x4s tx1 2x3 4x4 4x2 x3 2x4 5xj 0 j 1 2 4 解 由于所构成的基本可行基恰好对应基本可行解x 4 5 0 0 T用式 4 27 计算 因为所有的 j 0 所以 4 5 0 0 T是最优解 单纯形法介绍及相关问题 定理4 5假设 1 线性规划问题的基本可行解是非退化的 即b 0 2 至少存在一个非基变量 其检验数是正的 假定xk的检验数 j 0 3 xk所对应的非基向量pk的分量至少有一个是正的 那么 用去替换原基底中的某个向量将得到使目标函数值增大的基本可行解 推论若定理4 5的条件 1 和 2 成立 此外 3 pk 0 即pk的分量全部都是非正的 则线性规划 4 19 具有可以使目标函数值任意增大的可行解 单纯形法介绍及相关问题 例5判定线性规划maxs 2x1 x2 5x3 x4s tx1 x3 3x4 3x2 2x3 3x4 1xj 0 j 1 2 4 具有无界解 解 由于可以构成可行基 现考虑由公式计算x3的判别数 3 根据推论 该线性规划具有无界解 单纯形法的计算步骤 4 单纯形表格为了便于计算和检验 可以设计一种表格来进行迭代运算 将式 4 19b 与目标函数式 4 19a 一起组成n 1个变量 包括s 和m 1方程的方程组 x1 a1 m 1xm 1 a1nxn b1x2 a2 m 1xm 1 a2nxn b2xm am m 1xm 1 amnxn bm s c1x1 c2x2 cmxm cm 1xm 1 cnxn 0该方程组的系数矩阵的增广矩阵 sx1x2 xmxm 1 xnb 单纯形法的计算步骤 若将 s看成不参与基变换的基变量 它与x1 x2 xm的系数列向量构成一个基 将它们的系数列向量变换为 m 1 m 1 阶的单位矩阵 即将c1 c2 cm的位置变换为零 这时可采用初等变换得到 sx1xl xmxm 1 xk xnb将上述增广矩阵设计成一种计算表格的形式 见表4 4 在表4 4中 cB列中填入基变量的价值系数 即c1 cl cm 它们随着迭代过程基变量的改变而改变 但与基变量相对应 单纯形法的计算步骤 xb列中基变量 这里是x1 xl xm也随迭代过程而变化 b列中填入约束方程组右端的常数项 cj是各变量的价值系数 最后一行为检验数 对应基变量 j 0 j 1 2 m 对应非基变量 则为初始可行基下基本可行解所对应的目标函数的反号值 i列的数字是需要事先确定换入变量之后 按 规则计算出来后再填入的 表4 4称为初始单纯形表 以后的迭代都从初始单纯形表开始 每迭代一次得到一张新的单纯形表 表4 4初始单纯形表 单纯形法的计算步骤 5 单纯形法的计算步骤有了初始单纯形表之后 就可以按照前面的结论 即根据式 4 35 确定换入向量pk 根据式 4 18 确定换出变量pl 在单纯形表中第k列称为主列 第l行称为主行 它们的元素分别称为主列元素和主行元素 主列和主行相交的元素al k 即为主元素 单纯形表中的所有元素再分别按式 4 14 和式 4 17 进行计算 就产生了一张新的单纯形表 4 5 从而得到了一个新的基本可行解 实现单纯形法的迭代 表4 5中最后一行的数据 类似的 按以下公式计算 4 36 4 37 那么 表4 5上的是否仍然对应列的变量的检验数和目标函数的反号值呢 单纯形法的计算步骤 表4 5变换后的新单纯形表 因为基变量已变为x1 xl 1 xk xl 1 xm 所以根据检验数和目标函数值的定义需要证明的公式是 4 38 4 39 单纯形法的计算步骤 实际上 把式 4 27 代入式 4 36 再利用 4 16 和式 4 14 便可以得到这正是式 4 38 同理 单纯形法的计算步骤 这恰好是式 4 39 这就证明了各个检验数和目标函数 在每一次迭代过程中勿需按各自的定义式进行计算 只要把它们当作单纯形表中的一般元素加以计算即可 这对简化计算程序是有利的 单纯形法的计算步骤可归纳如下 1 化线性规划问题为标准型 并确定初始可行基 2 初始单纯形表 首先需要将目标函数与约束方程一起组成n 1个变量和m 1个方程的方程组 并写入方程组系数矩阵的增广矩阵 然后 对增广矩阵施行初等行变换 使最后一行基变量所对应的元素为零 再把增广矩阵中的数据填入初始单纯形表中 3 检查个 j j 1 2 n 如果所有的 j 0 则有最优解 此时 xB列即为最优解中各基变量 与之对应的b列即为个基变量的值和最优目标函数的反号值 非基变量值则为零 输出最优解 停机 如果有一个 j 0 而对应的xk列的列向量为pk 则此问题的解是无界的 没有最优解 否则 转入步骤 4 4 确定换入向量 确定主列 即max j 0 k则 k所对应的pk即为换入向量 此列为主列 5 确定换出向量 确定主行 即则 l所对应的pl即为换出向量 此行为主行 单纯形法的计算步骤 6 修正单纯形表 用非基变量xk 替换xB列中的基变量xl 非主行和非主列元素按下式变换 主行元素 主列元素其他元素 7 转入步骤 3 单纯形法的计算步骤 例 4 21求解线性规划问题maxs 2x1 3x2s t2x1 2x2 12x1 2x2 184x1 164x2 12xj 0 j 1 2 解 引入松弛变量 化为标准型maxs 2x1 3x2 0 x3 0 x4 0 x5 0 x6s t2x1 2x2 x3 12x1 2x2 x4 184x1 x5 164x2 x6 12xj 0 j 1 2 6 由于p3 p4 p5 p6构成一组基底 其对应的价值系数为0 因此勿需对增广矩阵施加初等变换 可直接写出初始单纯形表 如表4 11中的计算表1 单纯形法的计算步骤 表4 11例4 21初始单纯形表由于在表4 11中计算表4中的最后一行的所有检验数都已为零或负数 所以得到最优解为x 4 2