lp案例ab钢铁配矿问题教学用

§3单纯形法

(SimplexMethod)本节重点：检验数的概念和计算最优性判别基变换（换入变量和换出变量的确定）旋转变换2023/10/27管理运筹学课程组3923．1基本思想

对于一个标准型LP问题，从一个初始基可行解出发，判断其是否为最优解，若是则结束；否则求一个与其“相邻”的、改进的基可行解。再判断这个解是否最优，若是则结束，否则再求一个“相邻”的、改进的基可行解……如此迭代下去，直到找到基最优解或判定问题无解为止。x1x204Q2(4,2)Q1Q3Q44x1=164x2=12x1+2x2=82x1+3x2=03Q2如例1，OQ1Q2或OQ4Q3Q22023/10/27管理运筹学课程组393单纯形法要解决的三方面的问题：（1）如何确定初始的基可行解？（2）如何进行解的最优性判别？（3）如何寻找改进的基可行解？2023/10/27管理运筹学课程组3943．2确定初始基可行解

定义：线性规划规范型，当线性规划标准型：

Maxz=CX2023/10/27管理运筹学课程组395其中系数矩阵A=[P1，P2，…，Pn]中含有一单位矩阵I，不妨设单位矩阵I即为一初始可行基。令非基变量取值为零，便得到一组基可行解。

2023/10/27管理运筹学课程组3963.2最优性检验和解的判别

对标准型的一般线性规划问题，经过变换、迭代，总可将线性规划约束条件中非基变量移至方程右边，得如下形式：即：其中i=1，2，…，m2023/10/27管理运筹学课程组397是常数，故可以用将上述表述式代入目标函数式中，整理得：令于是

再令

其中称为检验数，则有

由于检验数表示目标函数中的价值系数。2023/10/27管理运筹学课程组398为对应于基B的一个基可若行解，对于一切有检验数则

为最优解。定理5:（最优解的判别定理）2023/10/27管理运筹学课程组399

定理6（无穷多最优解的判别定理）

若对应于基B的一个基可行解，对于一切，有检验数且存在某个非基变量对应的检验数=0，则该线性规划问题有无穷多个最优解。2023/10/27管理运筹学课程组3910无穷多最优解判别定理：若B的一个基可行解，且对一切的j=m+1,...,n有为对应于基又存在某个非基变量的检验数则线性规划问题又无穷多最优解。证明：非基变量新基可行解新的目标函数值不变换入两个最优解，连线上的所有点均是最优解。2023/10/27管理运筹学课程组3911定理7

（无界解的判别定理）若为对应于基B的一个基可行解，存在某个非基变量对应的检验数>0，并且对应的变量系数，则该线性规划问题有无界解（或无最优解）。2023/10/27管理运筹学课程组3912无界解的判别定理：若一个基可行解，有一个为对应于基B的并且对i=1,...,m有那么线性规划问题具有无界解（无最优解）。证明：构造新的解++===>-=++kmjnmjabxjkmkmiii且,,1,0,0,)1()1(',')1(Llllxxi=1,2,…m2023/10/27管理运筹学课程组3913验证可行性：因为i,m,+00><=lka将代入到目标函数中得无可行解的判别：待以后将完人工变量法以后再讲。x1+a1,m+1’xm+1+…+a1n’xn=b1’x2+a2,m+1’xm+1+…+a2n’xn=b2’……xm+am,m+1’xm+1+…+amn’xn=bm’xj≥0，j=1,2,…,n每一个aij和bi均带“撇”2023/10/27管理运筹学课程组39142023/10/27管理运筹学课程组3915

2.换出变量的确定在中，令xk>0，而xj=0(m+1

j

n，j

k)，要保持xi

0(i=1，2，…,m)，即必须

于是，当为换出变量。若所有则xk

可取无穷大，问题无最优解。2023/10/27管理运筹学课程组39162023/10/27管理运筹学课程组39173迭代

确定换入变量：当，确定换入变量；确定换出变量：当，确定换入变量；将交叉元素（主轴元素）单位化，(旋转)2023/10/27管理运筹学课程组3918即乘以初等矩阵。重复上述步骤直到所有的检验数