文档介绍：第五讲修正单纯形法(1)
大约在1954年,Dantzig和他的同事就发现了更有效的单
纯形法。
我们知道,在单纯(扩展)表格中,共有3组元素,分别
与矢量组“a1,…,an”,“b”及“e1……em”相对应,如果说
前面讲的****惯用的一般单纯形表格法可只采用左边两组
的话,那么,修正单纯形法在运算迭代中只应用右边两
组,下面就具体阐述该种方法。
仍假设: AX=b, X≥0, CTX=min (1)
且A、b、C已知,属非退化情形,计算过程,将始终
用到A,B,C这些原始数据,故需保存。每一个阶段仍
用单纯形表格迭代,只用右边两组,即m+1列,每个表
格与当前基础解集相对应(j1,…,jm):
修正单纯形法(2)
t10
·
·
·
tm0
u11 … u1m
 
 
 
um1 … umm
z0
y1 … ym
(2)
其中:ti0——给出当前基础解
uij——给出当前基础阵之逆
z0——给出当前基础解费用
yi——给出当前基础阵之联立方程解
YTM= (3)
修正单纯形法(3)
(5)
其中——当前基础解的目标系数。
表格的起步可根据两阶段法的第1阶段之初始基础解表格开始,即:
ti0=bi ,uij = ij ,z0=Σbi,yi=1 (4)
第1阶段结束后,第2阶段开始的表格需加以修改,唯一修改处是最末一行,这是由于目标函数发生了变化z0和yi计算公式为:
修正单纯形法(4)
(6)
如果zj > cj,则令j = s,并作为支点列。
如果zj ≤cj,则去试探其它非基础列j,假若所有非基础
列j的zj ≤cj,则已达到最优解,其最优解值为:
下面来阐述表格的迭代过程。在一般单纯形表格法中,每次检验元素zj-cj全部算出,然后寻找支点列,而在修正单纯形表格中,不需一次计算全部检验元素,而是逐个计算。设j属非基础集,则:
修正单纯形法(5)
(7)
其最小费用为z0和最优对偶解为yT。
否则,计算zj(按6式),找出zj > cj,并令j = s,然后处理如下:
首先,计算单纯形表的支点列s:
(8)
修正单纯形法(6)
如果所有tis≤0,则最优解不存在,最优目标无限,即,
(9)
费用
若存在tis>0,可求出支点行:
(10)
修正单纯形法(7)
求出支点行后,就可进行修正单纯形表格的转换,其表格转换元素的计算只需计算后面m+1列,即:
新行r = (原行r)/trs (11)
新行i (i r) = (原行i) - i(原行r) (12)
其中:
最后,用as取代旧表格Vr中表示的基矢量。
修正单纯形法(8)
[例1-23] 已知线性规划为:
[解] 1)应用阶段1,求出初始基础可行解
构成新规划:A' X ' = b ' ,X '≥0, C'TX'=min
修正单纯形法(9)
令人工变量作为第1个基础可行解之基础变量,其对应的表格为:
e1
e2
b e1 e2
5 1 0
13 0 1
18 1 1
修正单纯形法(10)
检验非基础变量a1,a2,a3能否进基,可按任何次序检验。先检验a1: