第三讲　单纯形法

第 1章 线性规划与单纯形法第 1节 线性规划问题及其数学模型第 2节 线性规划问题的几何意义第 3节 单纯形法第 4节 单纯形法的计算步骤第 5节 单纯形法的进一步讨论第 6节 应用举例线性规划问题解的关系图AX=b的解基解若非基变量为 0基可行解基最优解B是 A的 M阶子矩阵基 B若 |B|0可行基 B当 B-1b0最优基 B若基变量取非负若对应目标函数 值最优非可行解线性规划问题解的关系图（ 2）可行解基可行解基解基可行基最优基二 .几个基本定理定理 1 若线性规划问题存在可行解 ,则问题的可行域是凸集 . 定理 2 线性规划问题的基可行解 X对应线性规划问题可行域 (凸集 )的顶点 .定理 3 若可行域有界 ,线性规划问题的目标函数一定可以在其可行域顶点上达到最优 .引理 2 若 K是有界凸集，则任何一点 X K可表示为 K的顶点的凸组合。引理 1 线性规划的可行解 X (x1,x2, xn)T为基可行解的充要条件是 X的正分量所对应的系数列向量是线性独立的。单纯形法单纯形法引例考虑线性规划问题 ： 约束方程的系数矩阵 A很显然 A中的后 3列是线性无关的，它们构成一个基基 B对应的 变量 x3,x4,x5是 基变量，则单纯形法引例（ 2）即 ： 将它们代入目标函数中得令 非基变量 x1=x2=0,得目标值 Z 0一个基可行解 X(0) (0,0,8,16,12)为了使目标函数能更大，让 x2变成基变量 ， 原基变量 的 x3， x4， x5要有一个变为非基变量当 x1=0,由最上式得从上式可看出，当 x2=3仍可保证 所有变量非负 ，并使 目标函数增大单纯形法引例（ 3）为了得到以 x3,x4,x2为基变量的一个基可行解，则对左边方程中的 x2与 x5互换 得再令 非基变量 x1=x5=0,得目标值 Z 9一个基可行解 X(0) (0,3,2,16,0)为了使目标函数能更大，让 x1变成基变量 ， 原基变量 的 x3， x4， x2要有一个变为非基变量目标函数变为单纯形法引例（ 4）这样如此下去，可得 X(2) (2,3,0,8,0)为了使目标函数能更大，让 x1变成基变量 ， 原基变量 的 x3， x4， x2要有一个变为非基变量此时目标函数变为X(3) (4,2,0,0,4)由于目标函数中的变量系数都小于等于 0，所以 X(3)（ 4,2,0,0,4)为最优解，最优值 Z 14CBXBCj b xj 2 3 0 0 0x1 x2 x3 x4 x5j000X3X4X5816121 2 1 0 04 0 0 1 00 4 0 0 18/2-12/4-Z 0 2 3 0 0 0003X3X4 X221631 0 1 0 -1/24 0 0 1 00 1 0 0 1/42/116/4-Z -9 2 0 0 0 -3/4 203X1X4 X22831 0 1 0 -1/20 0 -4 1 2 0 1 0 0 1/4 -8/23/(1/4)-Z -13 0 0 -2 0 1/4CBXBCj b xj 2 3 0 0 0x1 x2 x3 x4 x5j203X1X4 X22831 0 1 0 -1/20 0 -4 1 2 0 1 0 0 1/4 -8/23/(1/4)-Z -13 0 0 -2 0 1/4203X1X5 X24421 0 0 1/4 00 0 -2 1/2 1 0 1 1/2 -1/8 0-Z -14 0 0 -3/2 -1/8 0单纯形法迭代原理：确定初始可行解最优性检验和解的判别检验数单纯形解题步骤：单纯形解题步骤： （已知初始可行基）（已知初始可行基）求最大化时求最大化时一、作对应一、作对应 B的单纯形表的单纯形表 ：Cj C1 C2 Cn i CB XB b x1 x2 . xn C1 C2 Cmx1x2xmb 1b2bma11 a12 a 1na21 a22 a 2n am1 am2 amn12mj 1 2 n 二、判别二、判别若检验数全小于等于零，则基若检验数全小于等于零，则基 B所对应所对应的基础可行解的基础可行解 X就是最优解，终止。就是最优解，终止。若存在检验数大于零，但所对应的换若存在检验数大于零，但所对应的换入变量入变量 Xk的系数向量的系数向量 Pk0,则原问题无则原问题无最优解，终止。最优解，终止。若存在检验数大于零，且对应的系数若存在检验数大于零，且对应的系数列有大于零的分量，则需要换基迭代。列有大于零的分量，则需要换基迭代。三、换基迭代三、换基迭代确定换入变量确定换入变量 Xk， 其中其中max(j 0)= k, xk为换入变量为换入变量确定换出基变量确定换出基变量 Xr,根据最小比值原则根据最小比值原则min (bi/aik , aik 0 , 1im) = bl/blkalk为主元素为主元素 , Xl为为 换出基变量。换出基变量。对单纯形表进行初等行变换（主元运算对单纯形表进行初等行变换（主元运算）得到新的单纯形表。）得到新的单纯形表。经过上述有限次的换基迭代，就可得到经过上述有限次的换基迭代，就可得到原问题的最优解，或判定无最优解。原问题的最优解，或判定无最优解。六单纯形法举例 1(1)例 用单纯形法解下列线性规划 解:将原问题化为标准形式则 基变量 为 x3,x4,x5 取 B1=(P3,P4,P5)=I CBXBCj b xj 2 1 0 0 0x1 x2 x3 x4 x5j000X3X4X54381 0 1 0 0 0 1 0 1 0 1 2 0 0 1 4/1-8/1-Z 0 2 1 0 0 0200X1X4 X54341 0 1 0 00 1 0 1 00 2 -1 0 1-3/14/2-Z -8 0 1 -2 0 0201X1X4 X24121 0 1 0 00 0 1/2 1 -1/20 1 -1/2 0 1/2-Z -10 0 0 -3/2 0 -1/2最优解 X*=(4,2,0,1,0)T最优值 Z*=10六单纯形法举例 2(1)例 2: 用单纯形法解下列线性规划 解:将原问题化为标准形式取 初始可行基为 B1=(P3,P4,P5)=I XB b X1 X2 X3 X4 X5X3X4X54381 0 1 0 00 1 0 1 01 2 0 0 1-Z 0 1 2 0 0 0T(B1)X3X2X5-Z4 1 0 1 0 03 0 1 0 1 02 1 0 0 -2 1-6 1 0 0 -2 0T(B2)六单纯形法举例 2(2)XB b X1 X2 X3 X4 X5X3X2X54321 0 1 0 00 1 0 1 01 0 0 -2 1-Z -6 1 0 0 -2 0T(B2)X3X2X1-Z2 0 0 1 2 -13 0 1 0 1 02 1 0 0 -2 1-8 0 0 0 0 -1T(B3)六单纯形法举例 2(3)最优解 X*=(2,3,2,0,0)T最优值 Z*=8XB b X1 X2 X3 X4 X5X3X2X12320 0 1 2 -10 1 0 1 01 0 0 -2 1-Z