1、一、单纯形法原理及步骤一、单纯形法原理及步骤二、用向量矩阵描述单纯形法原理二、用向量矩阵描述单纯形法原理三、单纯形表三、单纯形表四、四、两阶段法和大两阶段法和大M法法五、退化和循环五、退化和循环用向量矩阵描述单纯形法原理用向量矩阵描述单纯形法原理并设并设 是是A A的一个基。的一个基。12,BBBmBPPP设标准的线性规划问题为设标准的线性规划问题为,AB N则则 ，相应地，向量，相应地，向量X X 和和C C 可以记为可以记为 max z=X AX=X0 s.t.,BBNNCCX XX XC CX XBXB+NXN=bXB=B-1b-B-1NXNCBXB+CNXNz=CBB-1b-(CBB-
2、1N-CN)XN用向量矩阵描述单纯形法原理用向量矩阵描述单纯形法原理z=CBB-1b-(CBB-1N-CN)XNXN=0基础解基础解10BNB bX XX XX XCBB-1N-CN=0：任意非基变量进基，目标函数：任意非基变量进基，目标函数值减少，当前解已经是最优解。值减少，当前解已经是最优解。检验数！变量xj的检验数：j用向量矩阵描述单纯形法原理用向量矩阵描述单纯形法原理基于向量矩阵的单纯形法基本思路：基于向量矩阵的单纯形法基本思路：(1)取得初始可行基B、相应的基本可行解 及对应的目标函数值10BNXB bXX1BBBzC XC B b (2)从当前的非基变量非基变量中选取一个xk,使x
3、k的值由当前的值0开始增加，其余非基变量的值均保持零值不变。如果任何一个非基变量的值由0增加时，目标函数都不能增加，则当前的基已经是最优基。用向量矩阵描述单纯形法原理用向量矩阵描述单纯形法原理基于向量矩阵的单纯形法基本思路：基于向量矩阵的单纯形法基本思路：(3)当xk的值由0开始增加时，当前各基变量的值也会随之变化：1)当当xk的值增加时，的值增加时，某些基变量的值随之减某些基变量的值随之减小，则必定有一个基变量小，则必定有一个基变量xr的值在的值在xk的增加过程中的增加过程中首先降为首先降为0。这时，这个基变量xr成为非基变量，而非基变量xk进基成为基变量，相应地，xk在矩阵A中相应（不在基
4、B中）的列向量pk将取代基变量xr在基B中的列向量pr。此时基变换后的目标函数值必定大于原目标函数值。用向量矩阵描述单纯形法原理用向量矩阵描述单纯形法原理基于向量矩阵的单纯形法基本思路：基于向量矩阵的单纯形法基本思路：2)当当xk的值增加时，所有的值增加时，所有基变量的值基变量的值都都随之随之增加，则不会有任何基变量出基，这时增加，则不会有任何基变量出基，这时xk值的增值的增加没有任何限制。加没有任何限制。此时可行域无界，即目标函数无界。(4)重复步骤(2)和(3)，就一定可以获得最优基或确定目标函数无界。用向量矩阵描述单纯形法原理用向量矩阵描述单纯形法原理单纯形法的几何意义：单纯形法的几何意
5、义：从几何意义方面解释，单纯形法就是在可行在可行域的边界上，沿着相邻的极点进行搜索的一种算域的边界上，沿着相邻的极点进行搜索的一种算法法。所谓相邻的极点，就是每次只有一个变量进基，一个变量出基转换前后所对应的基本可行解。我们把这两个基本可行解所对应的两个基称为“相邻的”基。单纯形表单纯形表根据单纯形法的向量矩阵描述，可得：0XXbNXBXXCXCNBNBNNBBz,0系数矩阵B-1B-1B-1=ECBCBCB需要变成0！单纯形表单纯形表与基B对应的单纯形表目标函数值基变量的目标函数系数jjBzp 1BC令则检验数j可以记为1BNjjzcC C B B N NC C 单纯形表单纯形表单纯形表单纯
6、形表列出以x3、x4为基变量的单纯形表如下。z2-c2=-30，最优！X*=(2,1,0,0),Z*=7旋转运算 Cj 2 3 0 0单纯形表单纯形表例2列出以x3、x4为基变量的单纯形表如下。x2进基11 2111ba22 2221ba X3离基(1)Cj 1 2 0 0单纯形表单纯形表(2)x1进基22 1111ba X4离基(3)x3进基目标函数无界！能确定进基变量，无法确定离基变量 Cj 1 2 0 0单纯形表单纯形表例3标准化（加入松弛变量x3、x4，z=-z）后，列出以x3、x4为基变量的单纯形表如下。(1)x2进基11 2111ba22 2221ba X3离基 Cj -2 2 0
7、 0单纯形表单纯形表(2)x1进基22 1111ba X4离基最优解X1=(0,1,0,1)T，z=2(3)最优解X2=(1,2,0,1)T，z=2最优解X=t X1+(1-t)X2=(1-t,2-t,0,t)T，(0t1)Cj -2 2 0 0单纯形表单纯形表单纯形算法流程图单纯形表单纯形表例4列出以x3、x4为基变量的单纯形表如下。x1进基11 2933ba22 18165.ba X4离基(1)Cj 10 5 0 0单纯形表单纯形表(2)x2进基11 22 1531 452/ba22 285425/ba X3离基(3)0，最优！X*=(1,3/2,0,0),Z*=35/2旋转运算 Cj 10 5 0 0单纯形表单纯形表例5引进松弛变量，标准化并初始单纯形表：x2进基121/183/X5离基(1)241/Cj 1 2 1 0 0 0单纯形表单纯形表x3进基623/613/X4离基(2)1 823/(3)最优解为x1=0，x2=3，x3=9，x4=0，x5=0，x6=12，max z=15 Cj 1 2 1 0 0 0docin/sanshengshiyuandoc88/sanshenglu 更多精品资源请访问更多精品资源请访问
