2-运筹学LP.ppt

单纯形法的计算步骤 cj 3 4 0 0 θi cB 基变量 b x1 x2 x3 x4 0 x3 40 2 1 1 0 0 x4 30 1 3 0 1 3 4 0 0 0 x3 4 x2 3 x1 4 x2 换入列 bi /ai2，ai20 40 10 换出行 将3化为1 5/3 1 18 0 1/3 0 1/3 10 1 －1/3 30 30 0 5/3 0 －4/3 乘以1/3后得到 1 0 3/5 －1/5 18 0 1 －1/5 －2/5 4 0 0 －1 －1 单纯形法的计算步骤 例1.9 用单纯形法求解 解：将数学模型化为标准形式： 不难看出x4、x5可作为初始基变量，列单纯形表计算。 单纯形法的计算步骤 cj 1 2 1 0 0 θi cB 基变量 b x1 x2 x3 x4 x5 0 x4 15 2 -3 2 1 0 0 x5 20 1/3 1 5 0 1 1 2 1 0 0 0 x4 2 x2 20 － x2 2 1/3 1 5 0 1 20 75 3 0 17 1 3 1/3 0 －9 0 －2 25 60 x1 1 1 0 17/3 1/3 1 25 0 1 28/9 -1/9 2/3 35/3 0 0 -98/9 -1/9 -7/3 单纯形法的计算步骤 学习要点： 1. 线性规划解的概念以及3个基本定理 2. 熟练掌握单纯形法的解题思路及求解步骤 单纯形法的进一步讨论－人工变量法 人工变量法： 前面讨论了在标准型中系数矩阵有单位矩阵，很容易确定一组基可行解。在实际问题中有些模型并不含有单位矩阵，为了得到一组基向量和初基可行解，在约束条件的等式左端加一组虚拟变量，得到一组基变量。这种人为加的变量称为人工变量，构成的可行基称为人工基，用大M法或两阶段法求解，这种用人工变量作桥梁的求解方法称为人工变量法。 单纯形法的进一步讨论－人工变量法 例1.10 用大M法解下列线性规划 解：首先将数学模型化为标准形式 系数矩阵中不存在单位矩阵，无法建立初始单纯形表。 单纯形法的进一步讨论－人工变量法 故人为添加两个单位向量，得到人工变量单纯形法数学模型： 其中：M是一个很大的抽象的数，不需要给出具体的数值，可以理解为它能大于给定的任何一个确定数值；再用前面介绍的单纯形法求解该模型，计算结果见下表。 单纯形法的进一步讨论－人工变量法 cj 3 2 -1 0 0 -M -M CB XB b x1 x2 x3 x4 x5 x6 x7 θi 0 x6 4 -4 3 1 -1 0 1 0 4 -M x5 10 1 -1 2 0 1 0 0 5 -M x7 1 2 -2 1 0 0 0 1 1 3-2M 2+M -1+2M↑ -M 0 x6 3 -6 5 0 -1 0 1 3/5 -M x5 8 -3 3 0 0 1 0 8/3 -1 x3 1 2 -2 1 0 0 0 —— 5-6M 5M↑ 0 -M 0 0 2 x2 3/5 －6/5 1 0 －1/5 0 —— -M x5 31/5 3/5 0 0 3/5 1 31/3 -1 x3 11/5 －2/5 0 1 －2/5 0 —— 5 ↑ 0 0 0 0 2 x2 13 0 1 0 1 2 3 x1 31/3 1 0 0 1 5/3 -1 x3 19/3 0 0 1 0 2/3 0 0 0 -5 -25/3 → → → 两阶段法 在用计算机求解时，M是用一个很大的数字来表示无限大的，但是如果LP模型中的系数也很大，容易导致误差。两阶段法可解决这问题。 例：第一阶段：以人工变量加和为目标函数的最小化问题。 Min x6+x7 Max ω＝ -x6 -x7 x1+x2+x3 +x4 =4 -2x1+x2 - x3 - x5 + x6 =1 3x2 +x3 +x7 =9 xi≥0，i＝1……7 在此阶段若存在最优解，必为人工变量X6 ＝X7＝0，此时目标函数＝0。这个最优解满足原问题的约束条件，又是原问题的基解，因此就是原问题的基可行解。 CB