第七章 线性规划.ppt

第七章 线性规划 单纯形法的一般原理 表格单纯形法 借助人工变量求初始的基本可行解 单纯形表与线性规划问题的讨论 改进单纯形法 确定初始的基本可行解 例3、用单纯形方法求解线性规划问题 解：本题的目标函数是求极小化的线性函数， 可以令 则 这两个线性规划问题具有相同的可行域和最优解， 只是目标函数相差一个符号而已。 0 1 0 1 0 3 x2 2 0 0 1 2 -1 2 x3 0 - 0 1 0 1 0 3 x2 2 4/1 1 0 1 0 0 4 x3 0 3/1 0 1 0 1 0 3 x4 0 _ 1 0 1 0 0 4 x3 0 0 0 0 0 -1 8 Z’ 1 0 0 -2 1 2 x1 1 1 0 0 -2 0 6 Z’ 2/1 1 0 0 -2 1 2 x5 0 1 2 0 0 0 0 Z’ 8/2 1 2 0 0 1 8 x5 0 x1 x2 x3 x4 x5 b XB CB Θ 1 2 0 0 0 C 最优解　　　　　　　　　最优值 2/2 3/1 - ? 因为非基变量x4的检验数σ4=0，由无穷多最优解判别定理，本例的线性规划问题存在无穷多最优解。事实上若以x4为换入变量，以x3为换出变量，再进行一次迭代，可得一下单纯形表： 最优解　　　　　 　　　　最优值 最优解的一般表示式 0 0 0 0 -1 8 Z’ 0 0 1/2 1 -1/2 0 1 -1/2 0 1/2 1 0 1 0 0 1 2 4 x4 x2 x1 0 2 1 x1 x2 x3 x4 x5 b XB CB Θ 1 2 0 0 0 C 对于极小化的线性规划问题的处理： 先化为标准型，即将极小化问题变换为极大化问题，然后利用单 纯形方法求解． 直接利用单纯形方法求解，但是检验是否最优的准则有所不同， 即： 若某个基本可行解的所有非基变量对应的检验数 　　　　　　　 （而不是≤０）， 则基本可行解为最优解． 否则采用最大减少原则（而非最大增加原则）来确定换入变量， 即： 若 则选取对应的非基变量xm+k为换入变量． 确定了换入变量以后，换出变量仍采用最小比值原则来确定。 借助人工变量求初始的基本可行解 　　若约束方程组含有“≥”不等式，那么在化标准形时除了在方程式左端减去剩余变量，还必须在左端加上一个非负的人工变量。 　　因为人工变量是在约束方程已为等式的基础上，人为的加上去的一个新变量，因此加入人工变量后的约束方程组与原约束方程组是不等价的。 　　加上人工变量以后，线性规划的基本可行解不一定是原线性规划的问题的基本可行解。只有当基本可行解中所有人工变量都为取零值的非基变量时，该基本可行解对原线性规划才有意义。因为此时只需去掉基本可行解中的人工变量部分，剩余部分即为原线性规划的一个基本可行解．而这正是我们引入人工变量的主要目的。 考虑线性规划问题： 为了在约束方程组的系数矩阵中得到一个m阶单位矩阵作为 初始可行基，在每个约束方程组的左端加上一个人工变量 　　　　　　 可得到： 　———————————————————————— 添加了m个人工变量以后，在系数矩阵中得到一个m阶单位矩阵，以该单位矩阵对应的人工变量