3单纯形法剖析.ppt

1.5 单纯形法的进一步讨论 一、 目标函数为Min的情形 三种处理方法： 1.5.1 几种情况 其中第2、3个约束方程中无明显基变量，分别加上人工变x6， x7。 二、 约束方程为“=”或“=”的情形（加人工变量） 这时，初始基和初始基可行解很明显。X(0)=(0，0，0，11，0，3，1)T不满足原来的约束条件。如何使得可从X(0)开始，经迭代逐步得到x6=0，x7=0 的基可行解，从而求得问题的最优解，有两种方法： 反之，若加了人工变量的问题解后最优解中仍含人工变量为基变量，便说明原问题无可行解。例8的单纯形表格为： 只要原问题有可行解，随着目标函数向最大化方向的改善，人工变量一定会逐步换出基，从而得到原问题的基可行解，进而得到基最优解。 1.5.2 大M法 在目标函数中加上惩罚项。 max =3x1-x2-x3-Mx6-Mx7 其中M为充分大的正数。 3-6M M-1 3M-1 0 -M 0 0 0 x4 10 3 -2 0 1 0 0 -1 -M x6 1 0 1 0 0 -1 1 -2 -1 x3 1 -2 0 1 0 0 0 1 1 -1+M 0 0 -M 0 -3M+1 1 0 0 0 -1 11 3/2 1 〔 〕 [ ] 1 4 [ ] X* = (4，1，9，0，0)T, z* = 2 3 x1 4 1 0 0 1/3 -2/3 -1 x2 1 0 1 0 0 -1 -1 x3 9 0 0 1 2/3 -4/3 -2 0 0 0 -1/3 -1/3 0 x4 12 3 0 0 1 -2 -1 x2 1 0 1 0 0 -1 -1 x3 1 -2 0 1 0 0 1.5.3 两阶段法 第一阶段：以人工变量之和最小化为目标函数。 min ? = x6+x7 第二阶段：以第一阶段的最优解(不含人工变量)为初始解，以原目标函数为目标函数。 s.t. X* = (4，1，9，0，0)T, z* = 2 约束方程为“=”或“=”的情形（加人工变量） 人工变量法（确定初始可行基）： 原约束方程：AX=b 加入人工变量：xn+1，?，xn+m 人工变量是虚拟变量，加入原方程中是作为临时基变量，经过基的旋转变换，将人工变量均能换成非基变量，所得解是最优解；若在最终表中检验数小于零，而且基变量中还有某个非零的人工变量，原问题无可行解。 Max Z=2x1+ x 2+ x 3 4x1+2x2+ 2x 3≥4 2x1+4x2 ≤20 4x1+8x2+ 2x