本科-线性规划单纯形法.pptVIP

单纯形法 单纯形方法的矩阵描述： 设线性规划问题 max Z = CX max Z = CX + 0XS s.t. AX ≤ b s.t. AX + I XS = b （I 式） 　 X ≥ 0 X ，XS ≥ 0 其中 b ≥ 0 ，I 是 m?m 单位矩阵。 对上面（I 式）经过迭代，并设最终的最优基矩阵为B（不妨设B 为A 的首m 列，则将（I 式）改写后有 线性规划 Linear Programming（LP） 单纯形法 max Z = CBXB + CNXN + 0XS s.t. BXB + NXN + I XS = b XB ，XN，XS ≥ 0 max Z = CB B -1 b+(CN- CB B -1N)XN - CB B -1XS s.t. XB + B -1NXN + B -1XS = B -1b XB ，XN，XS ≥ 0 B 式中最优目标函数值Z*= CB B -1 b，检验数 CN - CB B -1 N ≤ 0 ， - CB B -1 ≤ 0 单纯形方法迭代 （I 式） （B 式） 线性规划 Linear Programming（LP） 单纯形法 单纯形方法的矩阵描述： 基 解 XB XN XS ? XS b B N I ?j ? CB CN 0 基 解 XB XN XS ? XB B -1b I B -1N B -1 ?j ? 0 CN - CB B –1N - CB B -1 对应I 式的单纯形表—— I 表 对应B 式的单纯形表—— B 表 迭代 线性规划 Linear Programming（LP） 线性规划 Linear Programming（LP） 问题：线性规划 问题化为标准形时， 若约束条件的系数 矩阵中不存在单位 矩阵，如何构造 初始可行基？  A2，A4线性相关，不能构成基； A1，A2线性无关，可构成基，得到 基解x=(-1/3,11/3,0,0)T，不可行解 找一个可行基很困难 人工变量法 加入人工变量 设线性规划问题的标准型为： 加入人工变量,构造初始可行基. 人工变量法 系数矩阵为 单位矩阵， 可构成初始 可行基。 约束条件已改变， 目标函数如何调整？ 人工变量法 “惩罚” 人工变量！ （1）大M法 （2）两阶段法 一、大 M 法 人工变量在目标函数中的系数为 -M, 其中，M 为任意大的正数。 目标函数中添加“罚因子” -M（M是任意大的正数） 为人工变量系数，只要人 工变量0，则目标函数 不可能实现最优。 例: 求解线性规划问题 一、大 M 法 解: 一、大 M 法 加入松弛变量和剩余变量进行标准 化, 加入人工变量构造初始可行基. 求解结果出现检验数非正 若基变量中含非零的人工变量， 则无可行解； 否则，有最优解。 一、大 M 法 用单纯形法求解（见下页）。 目标函数中添加“罚因子” -M为人工变量系数，只要人 工变量0，则目标函数 不可能实现最优。 1 -2 1 -4 1 2 -2 0 1 3-6M M -1 3M-1 3 -1 -1 x1 x2 x3 0 x4 11 -M x6 3 -M x7 1 C j - Z j C j CB XB b 1 0 0 -1 0 0 0 -M 0