文档介绍：线性规划单纯形方法第二节单纯形法单纯形法的一般原理表格单纯形法借助人工变量求初始的基本可行解单纯形表与线性规划问题的讨论改进单纯形法考虑到如下线性规划问题其中A一个m×n矩阵,且秩为m,b总可以被调整为一个m维非负列向量,C为n维行向量,X为n维列向量。根据线性规划基本定理:如果可行域D={X∈Rn/AX=b,X≥0}非空有界,则D上的最优目标函数值Z=CX一定可以在D的一个顶点上达到。这个重要的定理启发了丹齐格()的单纯形法,即将寻优的目标集中在D的各个顶点上。单纯形法的一般原理Dantzig的单纯形法把寻优的目标集中在所有基本可行解(即可行域顶点)中。其基本思路是从一个初始的基本可行解出发,寻找一条达到最优基本可行解的最佳途径。单纯形法的一般步骤如下:(1)寻找一个初始的基本可行解;(2)检查现行的基本可行解是否最优可行解;(3)如果不是最优可行解,如何改善现行的基本可行解——进行基变换,得到下一个基本可行解。确定初始的基本可行解确定初始的基本可行解等价于确定初始的可行基,一旦初始的可行基确定了,那么对应的初始基本可行解也就唯一确定为了讨论方便,不妨假设在标准型线性规划中,系数矩阵A中前m个系数列向量恰好构成一个可行基,即A=(BN),其中B=(P1,P2,…Pm)为基变量x1,x2,…xm的系数列向量构成的可行基,N=(Pm+1,Pm+2,…Pn)为非基变量xm+1,xm+2,…xn的系数列向量构成的矩阵。所以约束方程就可以表示为用可行基B的逆阵B-1左乘等式两端,再通过移项可推得: 若令所有非基变量,则基变量由此可得初始的基本可行解问题:要判断m个系数列向量是否恰好构成一个基并不是一件容易的事。基由系数矩阵A中m个线性无关的系数列向量构成。但是要判断m个系数列向量是否线性无关并非易事。即使系数矩阵A中找到了一个可行基B,也不能保证该基恰好是可行基。因为不能保证基变量XB=B-1b≥0。为了求得基本可行解,必须求可行基B的逆阵B-1。但是求逆阵B-1也是一件麻烦的事。结论:在线性规划标准化过程中设法得到一个m阶单位矩阵I作为初始可行基B,若在化标准形式前,约束方程中有“≥”不等式,那么在化标准形时除了在方程式左端减去剩余变量使不等式变成等式以外,还必须在左端再加上一个非负新变量,,约束方程中有等式方程,那么可以直接在等式左端添加人工变量。为了设法得到一个m阶单位矩阵I作为初始可行基B,可在性规划标准化过程中作如下处理:若在化标准形式前,m个约束方程都是“≤”的形式, 那么在化标准形时只需在一个约束不等式左端都加上一个松弛变量xn+i(i=12…m)。判断现行的基本可行解是否最优假如已求得一个基本可行解将这一基本可行解代入目标函数,可求得相应的目标函数值其中分别表示基变量和非基变量所对应的系数子向量。其中称为非基变量XN的检验向量,它的各个分量称为检验数。若σN的每一个检验数均小于等于0,即σN≤0,那么现在的基本可行解就是最优解,此结论针对目标函数最大化问题。若针对目标函数最小化问题,则σN≥0。要判定是否已经达到最大值,只需将代入目标函数,使目标函数用非基变量表示,即:体现了极值的思想——线性问题的典式(或规范式)