最优化理论与方法单纯形法

最优化理论与方法单纯形法
wk.baidu.com
一般线性规划问题总可以写成下列标准形式：
n
min c j x j
j 1
n
s.t. aij x j bi
(2.1.1)
i 1,..., m
j 1
xj 0
j 1,..., n
用矩阵表示： min cx
s.t. Ax b
(2.1.2)
x0
其中，A是mXn矩阵，c是n维行向量，b是m维列向量。 为了计算方便，一般假设b 0，即b的每个分量都是非负数。
是目标函数的最优解。（最优基本可行解）
就是，从一个基本可行解出发，求一个使目 标函数值有所改变的基本可行解；通过不断 改进基本可行解，力图达到最优基本可行解。
怎样实现基本可行解的转换？
min f cx s.t. Ax b
x0
min f s.t. f cB xB cN xN 0
BxB NxN b xB 0, xN 0
若线性规划(2.1.2)存在有限最优解，则目标函数的最优值可在某 个极点上达到。（最优极点）
极点是个几何概念，直观性强，但不便于演算， 因此需要研究极点的代数含义。
x
xB xN
B1b 0
称为方程组的一个基本解；
又若 B1b 0，则称
x
xB xN
B1b 0
为约束条件
s.t. Ax xa b x 0, xa 0
（1） xa 0 （无可行解） （2） xa 0 且 xa 的分量都是非基变量
（得基本可行解 x x ）
用单纯形法求解原问题。 （3） xa 0 且 xa 的某些分量是基变量
（用主元消去法）
其基本思想是：在约束中增加人工变量 xa，同时修改目 标函数，增加惩罚值MeTxa ，M是很大的正数，这样， 在极小化目标函数的过程中，由于M的存在，将迫使人
B称为基矩阵，简称基；
xB的各分量称为基变量；
基变量的全体 xB1 , xB2 ,..., xBm 称为一组基；
xN的各分量称为非基变量；
Ax b, x 0 的基本可行解， 称B为可行基矩阵， xB1 , xB2 ,..., xBm为一组可行基；
若B1b 0，则称基本可行解是非退化的 基本可行解；
0
0
xj
xk
y1 j
y1k
进基 变量
b1
xBr 0
1
0
yrj
yrk
br
xBm 0
0
1
ymj
ymk
bm
f0
0
0
zj cj
zk ck
cBb
主元
zk ck max{z j c j}
xk
br yrk
min
bi yik
|
yik
0
显然，在单纯形表中包含了单纯形方法所需的全部数据。
解的几种情况在单纯形表上的体现(min型)：
唯一最优解：终表非基变量判别数均小于零； 多重最优解：终表非基变量判别数中有等于零的； 无界解：任意表有正判别数相应的系数列均非正。
max型单纯形表与min型的区别仅在于： 判别数反号，即，
令负判别数中最小的对应的变量进基； 当判别数均大于等于零时为最优。
用单纯形法消去人工变量（如果可能），即把人工变量
设S {x | Ax b, x 0} 为非空多面集，则有：
极点集非空，且存在有限个极点 x(1),..., x(k) .
极方向集为空集的充要条件是S有界。若S无界，则存在有限
个极方向 d (1) ,..., d (l) .
x∈S的充要条件是：
k
l
x j x( j) jd ( j)
min f
s.t.
xB
B1NxN B1b
f 0 xB (cB B1N cN )xN cB B1b
xB 0, xN 0
f
xB
0
f
1
xB
xN
右端
Im
B-1N
B-1b
0
cBB-1N-cN
cBB-1b
显然，在单纯形表中包含了单纯形方法所需的全部数据。
离基
xB1
xBr
xBm
变量
xB1 1
线性规划(2.1.2)存在有限最优解的充要条件是所有cd ( j)为非负数， 其中 d ( j)是可行域的极方向。
若线性规划(2.1.2)存在有限最优解，则目标函数的最优值可在某 个极点上达到。（最优极点）
线性规划的可行域的极点集与基本可行解集等价；
当线性规划(2.1.2)有可行解，则一定存在基本可行解。 当线性规划(2.1.2)存在最优解时，则一定存在一个基本可行解
2. 对于每个非基变量，计算判别数，令 zk ck max{z j c j} 。
工变量离基。
min f =cx s.t. Ax b
x0
min f =cx+MeT xa s.t. Ax xa b
x 0, xa 0
在运用单纯形法解决线性规划问题时，如果知道了可行 基的逆，就能利用它和原始数据来计算基变量的取值及 判别数，从而能够确定一个基本可行解，并判断它是否 为最优解。因此，只要保存原始数据和现行基的逆即可。
变为非基变量，求出原问题的一个基本可行解；
首先引入人工变量。令 Ax xa b ， x 0 , xa 0
即
x
(
A,
I
m
)
xa
b
x0 , 消去人工变量的一种方法是解如下第一阶段问题：
xa 0
min eT xa
设得到的最优基本可行解是 (xT , 时必有下列三种情况之一：
xaT )T ，此
修正单纯形法的基本思想是：给定初始基本可行解以后， 通过修改旧基的逆来获得新基的逆，进而完成单纯形法 的其它运算。在整个过程中保存现行基的逆。
1. 给定初始可行基的逆 B1 ，计算单纯形乘子w 和右端向量 b 。构成下表：
单纯形乘子
w (=cB B1)
cBb
目标函数值
xB
B 1
可行基的逆 b (=B1b)
若B1b 0且至少有一个分量是零，则称
此时的基本可行解是退化的基本可行解； 同时，此基本可行解对应的基被称为退化 的可行基。
若A是mXn矩阵， A的秩为m时， 基本可行解的个数不会超过：
n
m
n! m!(n
m)!
线性规划的可行域是凸集。
设线性规划 (2.1.2)的可行域非空，则有下列结论：
j 1
j 1
k
j 1,
j 1
j 0, j 1,..., k,
j 0, j 1,...,l.
线性规划的可行域是凸集。 设线性规划 (2.1.2)的可行域非空，则有下列结论：
线性规划(2.1.2)存在有限最优解的充要条件是所有cd ( j)为非负数， 其中 d ( j)是可行域的极方向。