Ch线性规划单纯性解法说课.ppt

约束方程的系数矩阵 为基变量 为非基变量 I 为单位矩阵且线性独立 令： 则： ∴ 基本可行解为（0 0 12 8 16 12） 此时，Z = 0 然后，找另一个基本可行解。即将非基变量换入基变量中，但保证其余的非负。如此循环下去，直到找到最优解为止。 注意：为尽快找到最优解，在换入变量时有一定的要求。如将目标系数大的先换入等。 当 时， 为换入变量 确定换出变量 为换出变量 接下来有下式： 用高斯法，将 的系数列向量换为单位列向量，其步骤是： 结果是： 代入目标函数： 有正系数表明：还有潜力可挖，没有达到最大值； 此时：令 得到另一个基本可行解 （0，3，6，2，16，0） 有负系数表明：若要剩余资源发挥作用，就必须支付附加费用。当 时，即不再利用这些资源。 如此循环进行，直到找到最优为止。 本例最优解为： （4，2，0，0，0，4） 三、关于解的最优性检验及检验数的计算 设线性规划模型为 第四节单纯形法 令基为B，并作相应的矩阵分割，从约束条件得 代入目标函数 得 第四节单纯形法 令 则目标函数可写成 所以可用 判断是否最优解，称为检验数。 第四节单纯形法 4 3 0 0 0 0 0 0 x3 x4 x5 1600 2500 400 2 5 1 2 2.5 0 1 0 0 0 1 0 0 0 1 800 500 400 0 -4 -3 0 0 0 五、表解形式的单纯形法 第四节单纯形法 4 3 0 0 0 0 0 4 x3 x4 x1 800 500 400 0 0 1 2 2.5 0 1 0 0 0 1 0 -2 -5 1 400 200 1600 0 -3 0 0 4 0 3 4 x3 x2 x1 400 200 400 0 0 1 0 1 0 1 0 0 -0.8 0.4 0 2 -2 1 200 400 2200 0 0 0 1.2 -2 0 3 4 x5 x2 x1 200 600 200 0 0 1 0 1 0 0.5 1 -0.5 -0.4 -0.4 0.4 1 0 0 2600 0 0 1 0.4 0 第四节单纯形法算法总结 Step1 确定初始基本可行解，建立初始单纯形表；Step2 最优性检验。若所有的检验数 ，则已得到最优解，停止运算。否则转下一步；Step3 确定进基变量xk..在所有正检验数中选择最大的正检验数所对应的非基变量为进基变量，即若 则相应的xk为进基变量。若有两个或两个以上的非基变量的检验数均为最大，可选其下标最小者，如果进基变量xk所在列的所有系数 则该线性规划问题为无界解，停止运算；否则进行下一步；Step4 确定出基变量xs.按最小比值法求出故xs为出基变量。若出现相同最小比值时，则从相同的最小比值所对应的基变量中，选下标小者作为出基变量，转下一步；Step5 以ask为主元（为明显可标记*号），进行变换，（即进行矩阵的初等行变换）将xk所对应的列向量变为单位列向量 习题 P.276，习题4（2） P.277，习题10（1） （四）单纯形表 判定标准： 若求 或 例 题： cj 2 3 0 0 0 0 cB xB b x1 x2 x3 x4 x5 x6 0 0 0 0 x3 x4 x5 x6 12 8 16 12 2 2 1 0 0 0 1 2 0 1 0 0 4 0 0 0 1 0 0 4 0 0 0 1 Z 0 2 3 0 0 0 0 12/2 8/2 － 12/4 cj 2 3 0 0 0 0 cB xB b x1 x2 x3 x4 x5 x6 0 0 0 x3 x4 x5 16 4 0 0 0 1