运筹学课件 单纯形法

第三节线性规划问题的单纯形解法线性规划问题解的基本概念单纯形解法解的最优性检验表解形式的单纯形法单纯形解法的一些问题及其处理方法一、线性规划问题解的基本概念可行解最优解基及基本解可行基及基本可行解代数解与几何解的关系单纯形法的要点二、单纯形解法建立基本可行解计算变量的检验数判断是否最优若不是最优解，换基计算新的基本可行解迭代计算直到求得最优解或可判断无最优解为止建立初始基本可行基对于小于等于情况，通过标准化，每个约束条件的左边加上了一的松弛变量，该松弛变量的系数矢量时单位矢量。当约束条件的右手项都大于等于零时，可令松弛变量为初始基本可行基。例1.1的标准型线性方程组的增广矩阵表示它的初始可行基初始基本可行解初始基变量是松弛变量。初始可行解（只要满足非负条件）初始基本可行解目标函数与最优性检验第一次迭代确定入基变量，应当是，它的系数是4。确定出基变量，方法如下，得确定新基和求解新的基本可行解新基新的基变量：新的基本可行解新的基本可行解和目标函数基本可行解目标函数第二次迭代确定入基变量：确定出基变量：确定新基和求解新的基本可行解

新基新的基变量：新的基本可行解新的基本可行解和目标函数基本可行解目标函数第三次迭代确定入基变量：确定出基变量：确定新基和求解新的基本可行解新基新的基变量：新的基本可行解基本可行解目标函数这是最优解。最大目标函数值为2600。新的基本可行解和目标函数三、关于解的最优性检验设线性规划模型为令基为B，并作相应的矩阵分割，从约束条件得代入目标函数得令则目标函数可写成所以可用判断是否最优解，它叫做检验数。四、表解形式的单纯形法表的格式在表上的计算方法表上计算的原理表解单纯形法的实例：例1-1初始单纯形表43000b0001600250040025122.50100010001800500400043000第一次迭代43000b00480050040000122.50100010-2-5140020016000300-4第二次迭代43000b034400200400001010100-0.80.402-212004002200000-1.22第三次迭代43000b0342006002000010100.51-0.5-0.4-0.40.4100000-1-0.40五、单纯形解法中的一些问题及其处理方法换入变量的选择问题下标最先原则检验数最大原则换出变量的选择问题比值最小原则下标最先原则无换出变量的情况—无界解非基变量检验数有等于零—多个最优解的情况多个最优解情况假设载重车每辆获利2千元，则目标函数变为它与约束条件平行，因此可行域顶点B和C都市最优解，其凸组合边BC都是最优解。第一次迭代42000b00480050040000122.50100010-2-5140020016000200-4一个检验数=0，第一个最优解42000b024400200400001010100-0.80.402-212004002000000-0.80迭代一次后得到另一个最优解42000b0242006002000010100.51-0.5-0.4-0.40.41002000000-0.80最优解一个最优解点B：X1=(2