文档介绍：§ 单纯形算法
1、单纯形算法
单纯形算法的主要思想:
先找一个基本可行解,判定它是否为最优解,若不是,就找一个更好的基本可行解,在进行判定,如此迭代进行,直到找到最优解,或判定问题无界。
需解决两个问题:
<1> 如何得到第一个基本可行解(§)
<2> 如何判定和迭代(本节)
转化:
(1)线性方程组的转化
基的典式:
由可得
()
不妨设,
记,

则由()有
所以有
即()
典式的特点:基变量的系数向量为单位向量。
符号的含义
(2)目标函数的转化
相应于基,记价值向量为, 则

由典式有, 所以
设基本可行解的目标函数值为,则

所以
令

称为的检验数, 为基本可行解的检验数向量。
结论 1: 基变量的检验数一定为0
证:因为
所以是第个分量为1,其余分量为0的维单位向量。所以

结论 2:
所以有
从而,对应于基本可行解,线性规划
化为
例

已知是它的基本可行解,对应的基为, 写出对应基的典式
解: , ,
所以,对应于基的典式为
,
验证是否有, ?
(最优性准则)如果()式中,则基本可行解为原问题的最优解。
证明:设为原问题的任一可行解,由于, ,所以, 从而
如果()式中向量的第个分量(显然, ),而向量,则原问题无界。
证明思路:构造一列可行解,使得他们的目标函数值趋于负无穷。
(1)构造向量使得且
(2)证是可行解(其中)
(3)证目标函数值
证:令,其中是第个分量为1,其余分量为0的维单位向量。所以, 且
设是正数,考查向量,有
所以是可行解,其目标函数值为
当以上两个判定定理的条件都不满足时,需要从基本可行解迭代到一个新的基本可行解。修改的思想为:
从的非基变量中选一个变量(选检验数大于0的)让它变成基变量,并且从原来的基变量中选一个变量(怎么确定?)让它变成非基变量。
设的非基变量的检验数,, 则

当的非基变量变成基变量时,它的值由0变为正数,设为,则新的基本可行解的目标函数值
对于非退化的基本可行解,若()式中向量的第个分量,而向量至少有一个正分量,则可以找到一个新的基本可行解使得。
证明思路:利用上面的修改思想构造新的基本可行解使得。
(1),构造向量,则,但。
(2)选适当的使是可行解。
显然, 所以只需取适当的使

所以取适当的使只需。所以取
()
(3) 证是基本解
的各分量为
。
()
(4)证
因是非退化的,所以,因而
所以
注意:(1)(2)
定义:进基变量和离基变量
迭代步骤:
单纯形方法步骤:
step1 找一个初始可行基
step2 求出典式和检验数
step3 求
step4 如果则该基可行解就是最优解停止;否则转step5;
step5 如果,则问题无最优解,停止;否则转step6
step6 求
step7 以替代得到一个新的基,转step2;
2、单纯形表
可得

1 0 0 3 2
1 1 0 5 1
1 0 1 2 5
1
3
4
(1)在表上化典式(设基)

1 0 0 3 2
0 1 0 2 -1
0 0 1 -1 3
1
2
3
(2)在表上进行基的变换
假设为进基变量,下面确定离基变量

1 0 0 3* 2
0 1 0 2 -1
0 0 1 -1 3
1
2
3
1/3
2/2
由于,所以为离基变量,新的基为。进行基的变换

1/3 0 0 1 2/3
-2/3 1 0 0 -7/3
1/3 0 1 0 11/3
1/3
4/3
10/3
所以,新的基本可行解为
一般假设当前的基对应的单纯形表为
…………
1 0 0 ……

0 1 0 ……

0 0 1 ……
假设为进基变量, 为离基变量,则只需经过初等行变换,把变为1,这一列的其它分量变为0,就可以新基对应的单纯形表
………
1 0 … 0 …

0 0 … 1* …

0 1 0 …
但这种单纯形表并不完整,因为从它里面无法确定进基变量。下面将完善此表,使得检验数也能在单纯形表上体现。
目标函数

等价于
把看成变量在单纯形表中加上一列,则可以得到新的单纯形表
…
…
…
…
RHS
1
0