1-3-单纯形法完成.ppt

1、3.5人工变量及其处理方法,引用人工变量是用单纯形法求解线性规划问题时解决可行解问题的常用方法。人工变量法的基本思路是若原线性规划问题的系数矩阵中没有单位向量，则在每个约束方程中加入一个人工变量便可在系数矩阵中形成一个单位向量。 由于单位矩阵可以作为基阵，因此可选加入的人工变量为基变量。然后，再通过基变换，使得基变量中不含非零的人工变量。如果在最终的单纯形表中还存在非零的人工变量，这表示无可行解。,对于如下线性规划问题,首先分别对每个约束方程中加入一个人工变量 这样我们就可选 为基变量，令非基变 =0便可以得到一个初始基可行解,X(0)=(0，0，0b1，b2bm)T,3.5.1约束方程为“=

2、”或“=”的情形（加人工变量）,人工变量法（确定初始可行基）：,原约束方程：AX=b,加入人工变量：xn+1，xn+m,人工变量是虚拟变量，加入原方程中是作为临时基变量，经过基的旋转变换，将人工变量均能换成非基变量，所得解是最优解；若在最终表中检验数小于零，而且基变量中还有某个非零的人工变量，原问题无可行解。,其中第2、3个约束方程中无明显基变量，分别加上人工变x6, x7,这时，初始基和初始基可行解很明显。X(0)=(0，0，0，11，0，3，1)T不满足原来的约束条件。如何使得可从X(0)开始，经迭代逐步得到x6=0，x7=0 的基可行解，从而求得问题的最优解，有两种方法：,3.5.2 大

3、M法（又称惩罚法）,由于人工变量对目标函数有很大的负影响，只要人工变量取值大于0，目标函数值就不可能是最优。单纯形法的寻优机制会自动将人工变量赶到基外，从而可以找到原问题的一个可行基。这种方法我们通常称其为大M法，又称惩罚法。 原理：当目标函数为max z ，对应的人工变量目标系数为M;当目标函数为min z ，对应的人工变量目标系数为+M,其中 M 为充分大的正数。根据最优检验数判别定理进行基的转换，使得人工变量逐渐换出基底，再寻求原问题的最优解。,解 先化标准型,例3.12 用单纯形法求解线性规划问题,然后，再添加人工变量 ，将原线性规划问题变为 例2.12用单纯形法求解的过程见下表,3.

4、5.3 两阶段法,原理：当目标函数为max Z ，对应的人工变量目标系数为-1; 当目标函数为min Z ，对应的人工变量目标系数为+1。 第一阶段 将原目标系数暂时取零值。根据最优检验数判别定理进行基的转换，使得人工变量逐渐换出基底。 第二阶段 再去掉人工变量对应的列，恢复原线性规划问题的目标系数，寻原问题的最优解。,3. 5.4 线性规划问题解的讨论,一、无可行解 max z=2x1+4x2 x1 +x2 10 2x1 +x2 40 x1 ,x2 0,人工变量不能从基底换出，此时原线性规划问题无可行解。,两阶段法,例: max z=3x1+4x2 x1 +x2 40 2x1+x260 x1

5、-x2 =0 x1 ,x2 0,此题初始解是退化的。最优解也是退化解。 退化解迭代中，当换入变量取零值时目标函数值没有改进，,例 max z=3x1+5x2 3x1 +5x2 15 2x1 + x2 5 2x1+2x2 11 x1 ,x2 0,如果将x1换入基底，得另一解，由可行域凸性易知，有两个最优解必有无穷多组最优解 当非基底变量的检验数中有取零值，或检验数中零的个数大于基变量个数时，有无穷多解。,四、无（有）界解 max z=x1+x2 -2x1+x2 4 x1- x2 2 -3x1+x23 x1 ,x2 0,若检验数有大于0，而对应系数列中元素全部小于或等于零（无换出变量）则原问题有无界解。,练习：写出单纯形表,分析检验数 与系数关系并画图验证。,线性规划解除有唯一最优解的情况外，还有如下几种情况,无可行解 退化 无穷多解 无界解,人工变量不能从基底中换出,基可行解中非零元素个数小于基变量数,检验数中零的个数多于基变量的个数,检验数大于零，但对应列元素小于等于零，无换出变量,对目标函数求极大值标准型线性规划问题，单纯形法计算步骤的框图：,练习,下表中给出某线性规划问题计算过程中的一个单纯形表，目标函数为Max Z=28x4+x5+2x6,约束条件为，表中x1,x2,x3为松弛变量，表中解的目标函数值为Z=14 （1）求ag的值； （2）判断给出的解是否为最优解；,练习,