单纯形法完成.PPTVIP

唯一最优解 否 否 否 是 是 是 添加松弛变量、人工变量 列出初始单纯形表 计算非基变量 各列的检验数бj 所有бj?0 基变量中 有非零的 人工变量 某非基变量检验数为零 无可行解 无穷多最优解 对任一бj0 有aik≤0 无界解 令бk=max{бj} xk为换入变量 对所有aik0计算θi=bi/aik 令θl=min{θi} 第l个基变量为换出变量，alk为主元素 迭代运算 .用非基变量xk替换换出变量 .对主元素行(第l行) 令 bl/alk→bl;alj/alk→ajl 对主元素列(第k列)令1→alk;0→其它元素表中其它行列元素 令 aij-ali/alk·aik→aij bi-bl/alk·aik→bi бj- alj/alk· бk → бj 否 对目标函数求极大值标准型线性规划问题，单纯形法计算步骤的框图： 练习 下表中给出某线性规划问题计算过程中的一个单纯形表，目标函数为Max Z=28x4+x5+2x6,约束条件为≤，表中x1,x2,x3为松弛变量，表中解的目标函数值为Z=14 （1）求a~g的值； （2）判断给出的解是否为最优解； x1 x2 x3 x4 x5 x6 x6 a x2 5 x4 0 3 6 0 0 d e -14/3 2 f 0 0 1 1 5/2 0 1 0 0 cj-zj b c 0 0 -1 g 练习 下表是某求极大值线性规划问题的初始表及迭代后的表，x4,x5为松弛变量，求表中的a~l的值及各下表m~t的值 x1 x2 x3 x4 x5 xm 6 xn 1 b -1 c 3 d e 1 0 0 1 cj-zj a 1 -2 0 0 xs f xt 4 g h 2 i -1 1 ? ? 0 1 cj-zj 0 7 j k l 课后作业 P45 1.5 （1）（2）大M法 （3）（4）两阶段法 作业要求上交 * * 3.5人工变量及其处理方法 引用人工变量是用单纯形法求解线性规划问题时解决可行解问题的常用方法。人工变量法的基本思路是若原线性规划问题的系数矩阵中没有单位向量，则在每个约束方程中加入一个人工变量便可在系数矩阵中形成一个单位向量。 由于单位矩阵可以作为基阵，因此可选加入的人工变量为基变量。然后，再通过基变换，使得基变量中不含非零的人工变量。如果在最终的单纯形表中还存在非零的人工变量，这表示无可行解。 对于如下线性规划问题 首先分别对每个约束方程中加入一个人工变量 这样我们就可选 …… 为基变量，令非基变 …… =0便可以得到一个初始基可行解 X(0)=(0，0，0…b1，b2…bm)T 3.5.1约束方程为“=”或“=”的情形（加人工变量） 人工变量法（确定初始可行基）： 原约束方程：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 大M法（又称惩罚法） 由于人工变量对目标函数有很大的负影响，只要人工变量取值大于0，目标函数值就不可能是最优。单纯形法的寻优机制会自动将人工变量赶到基外，从而可以找到原问题的一个可行基。这种方法我们通常称其为大M法，又称惩罚法。 原理：当目标函数为max z ，对应的人工变量目标系数为—M;当目标函数为min z ，对应的人工变量目标系数为+M,其中 M 为充分大的正数。根据最优检验数判别定理进行基的转换，使得人工变量逐渐换出基底，再寻求原问题的最优解。 解 先化标准型 例3.12 用单纯形法求解线性规划问题 然后，再添加人工变量 ，将原线性规划问题变为 例2.12用单纯形法求解的过程见下表 3.5.3 两阶段法 原理：当目标函数为max Z ，对应的人工变量目标系数为-