运筹学5-单纯形法

1、第五章是单纯形法，1。线性规划问题2的解法。单纯形法3。寻找初始基的人工变量法。线性规划问题的解，(1)解的基本概念，定义在线性规划问题中，约束方程(2)的系数矩阵A(假设)的任意阶的非奇异(可逆)子矩阵B，称为线性规划问题的矩阵。矩阵，非矩阵，基向量，非基向量，基变量，非基变量，然后，在约束方程(2)中定义，对于选定的基B，通过使所有非基变量为零而获得的解被称为对应于基B的基本解.在基本解中定义，如果基本解满足非负约束，即基本解称为基本可行解，简称为基本可行解；相应的基b称为可行基。定义在线性规划问题的一个基本可行解中，如果所有的基本变量都是正的，则称之为非回归解，如果所有的基本可行解都是非

2、回归解。这个问题被称为非退化线性规划问题。如果基本可行解的基本变量为零，则称为回归解，这个问题称为退化线性规划问题。基本解决方案中最多有m个非零组件。基本解决方案的数量不超过。不可行解，解集：可行解，基本解，最优解，基本可行解，解空间，(2)解的基本性质，判断可行解为基本可行解的标准，定理1线性规划问题的可行解是基本可行解，当且仅当对应非零向量的列向量是线性独立的。那么它必须有一个基本可行的解决方案。定理3如果线性规划问题有一个最优解，就必须有一个基本可行解，也就是它的最优解。得出几个结论：如果线性规划问题有一个可行解，那么可行域是一个凸多边形或凸多面体(凸集)，只有有限数量的顶点(极点)；线

3、性规划问题的每个基本可行解对应于可行域上的一个顶点(极点)；如果线性规划问题有最优解，则最优解必须在基本可行解(极点)上达到；线性规划问题的基本可行解(极点)的数量是有限的，不会超过。上述结论表明，线性规划的最优解可以通过有限运算从基本可行解中得到。2单纯形法，例1，(1)单纯形法介绍，解：(1)确定初始可行解，B=(P3 P4 P5)=1，设X1为30，60，24)T Z(1)=0，(2)确定解是否最优，z=0.40X150X2当X1为0或X2为0 Z至0时，X(1)不是最优解，(3)一个基可行，另一个基可行。50 40从0中选择X2，x1=0，x2=min (30/2，60/2，24/2)

4、=12x2:基变量，X5:基变量。B2=(P3P4P2)，1/2，代入公式，使x1=X5=0x (2)=(0，12，6，36，0) TZ (2)=600。(2)判断4002不是最优解。(3)从0中选择X1，X5=0，x1=min (6/1，36/3，aik(1=1，2，m)不全小于或等于0，即至少一个aik 0(1k m)；Bi 0(I=1，2，m)，即X(0)是一个非退化的基本可行解。然后从X(0)开始，我们可以找到一个新的可行解X(1)，这使得CX(1) CX(0)。(5)单纯形表，其中线性规划问题的标准形式的变量和系数被填入一个表中，称为单纯形表。单纯形法的矩阵表示，单纯形表一对应于类型

5、一(初始单纯形表)，单纯形表二对应于类型二，迭代，当CN -CBB-1N0时，它是最优单纯形表，(1)确定初始基域的初始基本可行解，并列出初始单纯形表，(3)如果有J，则转至(4)、(2)，非基本变量对应的测试数j均小于0。如果是，停止并获得最佳解决方案；如果没有，转到(3)。(6)单纯形法的迭代步骤，其中Xr是基本变量，arm k是主成分。，通过最小比值法，将最大j=m的kXm k转化为基变量，j 0，(4)，(2)，(5)，以臂k为中心，改变基迭代，从每个循环的步骤(2)-(5)开始，它被称为单纯形迭代。单纯形表的计算步骤给出了线性规划问题的一个例子。唯一的最优解，例2、达到最优状态，如果

6、有零的非基变量，则有无限的最优解，例3可以是零，例4、例5，并且不能获得初始基和可行解。3初始基的人工变量法和求解线性规划问题的单纯形法第一步是寻找初始可行基和初始基的可行解。获得初始可行基和初始可行解的主要方法有：(1)试算法；(2)人工变量法。在约束方程中没有单位向量的情况下，在每个约束方程中人为地添加一个变量，从而在系数矩阵中形成单位平方矩阵，以形成初始可行矩阵。约束条件：a11x 1a 12x 2 a1nx n1=b1a 21x 1a 22x 2 a2nx N2=B2.am1x1am2amxnxnxn m=bmx1，x2，xn，xn1，xn 0，s.t .人工变量，人工基数，等效项？对大M法、两阶段法、大M法和两阶段法的一些解释由于人工变量不能存在于原问题的解中，所以应尽快迭代，所以目标函数中相应的人工变量的值系数应该是惩罚性的，即罚系数。大m法与原始单纯形法基本相同，m可视为一个大常数。迭代之后，人工变量将不再成为基本变量。当所有的测试数都满足最优条件时，基本变量中仍然存在人工变量，这表明原线性规划问题没有可行解。用大m法手工计算很不方便。因此，建议在两阶段计算机中常用的两阶段方法可以容易地用手计算。迭代后，人工变量将不再成为基变量。例4没有达到最优状态，但不能继续改进，即没有有限的最优解。示例5已经达到了最佳状态，但是基变量中的人工变量还没有退出，因