文档介绍：研究生课程《工程数学》之“最优化方法”
第二章线性规划
能源与动力工程学院
College of Energy and Power Engineering
第二节单纯形方法
第二节单纯形法
单纯形法的一般原理
表格单纯形法
借助人工变量求初始的基本可行解
单纯形表与线性规划问题的讨论
改进单纯形法
考虑到如下线性规划问题
其中A一个m×n矩阵,且秩为m,b总可以被调整为一个m维非负列向量,C为n维行向量,X为n维列向量。
根据线性规划基本定理:
如果可行域D={ X∈Rn / AX=b,X≥0}非空有界,
则D上的最优目标函数值Z=CX一定可以在D的一个顶点上达到。
这个重要的定理启发了Dantzig的单纯形法, 即将寻优的目标集中在D的各个顶点上。
单纯形法的一般原理
Dantzig的单纯形法把寻优的目标集中在所有基本可行解(即可行域顶点)中。
其基本思路是从一个初始的基本可行解出发,寻找一条达到最优基本可行解的最佳途径。单纯形法的一般步骤如下:
(1)寻找一个初始的基本可行解。
(2)检查现行的基本可行解是否最优,如果为最优,则停止迭代,已找到最优解,否则转(1)步。
(3)移至目标函数值有所改善的另一个基本可行解,然后转回到步骤(2)。
确定初始的基本可行解
确定初始的基本可行解等价于确定初始的可行基,一旦初始的可行基确定了,那么对应的初始基本可行解也就唯一确定
为了讨论方便,不妨假设在标准型线性规划中,系数矩阵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 。
体现了极值的思想