线性规划的图解法与单纯形解法.pptVIP

【解】:化为标准型后用单纯形法计算如下表所示02【例2.11】求解线性规划01XBx1x2x3x4x5bθ(1)x3x4x5－111[2]2－11000100014→10225—λj24↑000(2)x2x4x5－1/2[2]1/21001/2－11/201000126→4—38λj4↑0－200(3)x2x1x50101001/4－1/2[3/4]1/41/2－1/40017/235/2→14—10/3λj000↑－20(4)x2x1x30101000011/31/3－1/3－1/32/34/38/314/310/3λj000－201表(3)中λj全部非正,则最优解为:2表(3)表明,非基变量x3的检验数λ3=0,x3若增加,目标函数值不变,即当x3进基时Z仍等于20。使x3进基x5出基继续迭代,得到表(4)的另一基本最优解3X(1),X(2)是线性规划的两个最优解，它的凸组合4仍是最优解，从而原线性规划有多重最优解。最优解的判别定理*定理1最优解的判别定理0102定理2有无穷多最优解的判别定理最优解的判别定理*定理3有无界解的判别定理唯一最优解的判断：最优表中所有非基变量的检验数非零,则线规划具有唯一最优解。多重最优解的判断:最优表中存在非基变量的检验数为零,则线则性规划具有多重最优解。无界解的判断:某个λk0且aik≤０（i=1，2,…,m）则线性规划具有无界解单纯形法计算的矩阵描述*单纯形法计算的矩阵描述*单纯形法计算的矩阵描述*单纯形法计算的矩阵描述*单纯形法计算的矩阵描述*单纯形法计算的矩阵描述*单纯形法计算的矩阵描述*线性规划求解的人工变量法*若原线性规划问题的系数矩阵中没有单位向量，则在每个约束方程中加入一个人工变量便可在系数矩阵中形成一个单位向量。由于单位阵可以作为基阵，因此，可选加入的人工变量为基变量。然后，再通过基变换，使得基变量中不含非零的人工变量。如果在最终单纯形表中还存在非零的人工变量，这表示无可行解。人工变量法的基本思路是：人工变量法引用人工变量是用单纯形法求解线性规划问题时解决可行解问题的常用方法。线性规划求解的人工变量法*线性规划求解的人工变量法*线性规划求解的大M法*

为了使加入人工变量后线性规划问题的最优目标函数值不受影响，我们赋予人工变量一个很大的负价值系数-M(M为任意大的正数)。由于人工变量对目标函数有很大的负影响，单纯形法的寻优机制会自动将人工变量赶到基外，从而找到原问题的一个可行基。这种方法我们通常称其为大M法。线性规划求解的大M法*线性规划求解的大M法举例*【例2.12】用大M法解下列线性规划【解】首先将数学模型化为标准形式式中x4，x5为松弛变量，x5可作为一个基变量，第一、三约束中分别加入人工变量x6、x7，目标函数中加入―Mx6―Mx7一项，得到人工变量单纯形法数学模型用前面介绍的单纯形法求解，见下表。Cj32－100－M－MbCBXBx1x2x3x4x5x6x7－M

0－Mx6x5x7－4123－1－212[1]－1000101000014101→λj3-2M2+M-1+2M↑－M000－M0－1x6x5x3－6－32[5]3－2001－1000101003→81λj5-6M5M↑0－M0020－1x2x5x3－6/5[3/5]－2/5100001－1/53/5－2/50103/531/5→11/5λj5↑000023－1x2x1x301010000111025/32/31331/319/3λj000－5-25/3*运筹学

OperationsResearch王慧东南大学经济管理学院电子商务系暨管理工程研究所wh_whq@126.com线性规划的图解法与单纯形解法*01线性规划问题的图解法02线性规划单纯形解法的原理03线性规划单纯形解法的计算步骤04单纯形法计算的矩阵描述05线性