八. 线性规划 (Linear Programming)
引 言
线性规划讨论的是最优化问题。 最优化理论所研究的对象是静态系统，即与时间无关的系 统，与前面各章所讨论的最优控制问题不同。 最优化理论和算法要解决的问题是： 在可选的方案中哪个方案最优(目标函数极值)； 怎样找出最优方案。 与最优控制理论相同，最优化理论也是泛函极值理论发展 的一个重要分支，20世纪40年代起逐渐形成单独的学科。 最优化理论和算法内容非常丰富，主要包括：线性规划、 整数规划、非线性规划、几何规划、 动态规划、随机规划、 网络决策等，而最基本的内容是线性规划和非线性规划。
8.1 凸集和凸函数
凸集和凸函数是线性规划和非线性规划(以及整个最优 化问题中)的非常重要的概念。 一般的最优化理论都建立在凸集和凸函数基础之上。 本节内容作为基础知识不作深入介绍，供需要时参考。
8.2 线性规划的定义和标准形式
(1) 线性规划的定义
考虑最优化问题的数学模型一般表示为 min (or max) f(x) s.t. g(x) = B 其中， f(x) 为目标函数， g(x) 为约束函数； x∈En, B 为 m 维列向 量，g(x)为m维向量函数， 线性规划定义：最优化问题数学模型中目标函数和约束函数都是变 量x的线性函数的，称之为线性规划问题。 线性规划是非线性规划的一种特殊形式，但在最优化理论与算法中 已成为非常重要的一个分支，在理论和算法上都很成熟，应用非常 广泛。
(2) 线性规划标准形式
一般线性规划问题总可以表示为：
( or max) i 1
min c i x i
n
(8-2-1)
ji
s .t .
a
i 1
n
xi b j ,
j 1,2,3, , m
(8-2-2)
j 1,2,3, , m
x i 0,
i 1,2,3, , n;
b j 0,
(8-2-3) (8-2-1’) (8-2-2’) (8-2-3’)
或用矩阵形式表示为：
( or max)
min Cx
s.t .
Ax B
x 0;
B0
其中A为 m ╳ n 维矩阵，C为n维行向量，B为m维列向量。
任何其他形式的线性规划问题均可转换成以上标准形式。 例如，若有 b j 0 可在相应等式两边乘（-1）（非负化）；
，用 若无 x i 0 限制，可令 x i x i x i ，其中x i , x i 0 x i , x i 代替 xi ； 若非 Ax B ，而是Ax B 或 Ax B，可引入 x n 1 , x n 2 , x n m ， 在每个不等式中加入或减去一个松驰变量，使其转化为等式 标准形式，而在目标函数中则令松驰变量的系数为零。
8.3 线性规划问题的图解法
对于n=2的线性规划问题，可以用图解法求解，以便较为直观地了解 多变量线性规划的一般性质。 例：生产安排问题 某工厂生产甲乙两种产品，其产量分别为 x1 , x2 个单位，每天可用资 源限制、单位产品资源消耗及单
位产品产值如表所示。
资源 名称 总量 消耗系数 甲产品 乙产品 原料A 1575kg 5kg/单位产量 3kg/单位产量 原料B 1500kg 4kg/单位产量 5kg/单位产量 工时 420分钟 1分钟 /单位产量 2分钟 /单位产量 产值系数 （元/单位产量） 13元/单位产量 11元/单位产量
问题：每天应生产甲乙两种产品（即 x1 , x2）各多少，使总产值 f ( x ) 13 x1 11 x2 最大？
此问题数学模型为：
max f ( x ) max(13 x1 11 x2 )
s.t .
x2
(1)
500 400 300
(2) (3)
(1) (2) x1 2 x2 420 4 x1 5 x2 1500 (3) x2 0 x1 0 ，
5 x1 3 x 2 1575
b
200 100
由约束条件，可在 x1 x2平面上作 出5条直线 x2 0 围 其中由(1)、(2)和 x1 0 ， 成的多边形满足所有的约束条件 多边形顶点为
a
0 100 200
d
300
c
400
500
x1
325 0 0 270 c ， ， a ，b d 0 75 210 0
设目标函数等值线方程为
13 x1 11 x2 变化时等值线 x 2 1 13 x1 在
11
x2
500 400 300
(1)
(3)
(2)
11 平面上平移，等值线法向量 n (13,11)T
也是目标函数的梯度，指向目标函 数增大的方向，因此沿此方向移动 等值线，目标函数值将增大。
200 100
b
a
0 100 200
d
300
x1 c
400 500
将等值线一直移动到约束条件构成 的多边形边缘，即多边形顶点d处， 270 x d 得目标函数极大值，即极值点为 75 最优解为 max f ( x ) f ( xd ) 13 270 11 75 4335
即x1=270，x2=75时可获得最大产值4335元。显然，这时约束条件 全部满足。
8.4 线性规划的基本性质
结合前面图解的例子，可对线性规划的基本性质作出直观解释。 (1) 可行解――满足约束条件（等式或不等式）的一组解称为可行解。 可行解有无穷多个，即多边形中任意一点。 (2) 最优解――使目标函数为极值的可行解，如上例中的xd。 (3) 可行（解）域 —— 约束条件所包含的范围，由无穷多个可行解组 成，包含最优解，如上例中的多边形 abdc。
定理：线性规划的可行域是凸集。
(4) 定理：线性规划的目标函数极值如果存在，一定在可行域多边形 （多面体）的顶点上达到（最优顶点）。 基本可行解 —— 可行域多边形（多面体）顶点的解称为基本可行解。 （更严格的定义后面将作介绍） x 0 有可行解，则一定存在 (5) 基本可行解的存在定理：如果 Ax B， 基本可行解。其中A是 m n 矩阵，rank(A)=m。
(6) 若有两个以上的顶点是最优解，则这些顶点的凸组合也都是最优解。 (7) 基本可行解数是有限的。因此解线性规划的问题可从可行解域 减少为基本可行解数，进行有限步迭代总可以找到最优解。 (8) 线性规
划的几种特殊情况 。 ① 约束条件与变量数不等 如上例中约束条件多于变量数，则有2个有效约束，1个松驰 约束。 ② 目标函数与可行域一边平行，最优解不唯一。 x max f ( x ) max(18 x1 10 x2 ) 例：
2
s .t .
9 x1 5 x 2 45
7 x1 9 x 2 63 x1 0 , x2 0
10 8
6 4 2 0 2 4 6 8 10
x1
③ 可行域无界 例(a) ： max f ( x ) x2 2 x1 s .t . x1 x 2 1
x1 3 x 2 3
x2
1
此时有解， 0 * x 1
0 1
x1 0 , x2 0
x2
x1
f ( x* ) 1
例(b) ： max f ( x ) x1 x2 1 s.t . x2 x1 2 2 x 2 x1 4
x1 0 , x2 0
4
此时无解。
x1
0
4
x2
例(c) ： max f ( x ) x1 4 x2
s .t .
x2 2
2
x1 0 , x2 0
0 2
x
1
此时有解， 0 * x 2 f ( x* ) 8
④ 无可行解 例： max f ( x ) x1 x2
x2
s .t .
x1 x 2 10 2 x1 x 2 30
10
两个约束矛盾， 无解。
0 10
x1 0 , x2 0
x1
8.5 单纯形方法(Simplex Method)
单纯形方法是求解线性规划的普遍方法，1947年由匈牙利数学 家G. B. Dantzig提出，使线性规划成为运筹学的一个分支。 单纯形方法基本思想：从一个基本可行解出发，求一个使目标函数 值有所改善的基本可行解；通过不断改进基本可行解，达到最优基 本可行解。 考虑线性规划问题标准形式： min Cx s.t. Ax=b x≥ 0 其中A是m ╳ n维矩阵，C为n维行向量，b为m维列向量。
(1)基本可行解的严格定义
上面标准形式中，设A的秩为m，则可设 A=[B, N]，其中B为m阶可 逆方阵。这种做法不失一般性。 xB x 又记 x ，x B 的分量与B中列对应，x N的分量与N中列对应. N 则有 Ax b [ B, N ]
xB b xN
或表示为 Bx B Nx N b 因而有
x B B 1 b B 1 Nx N
xN的分量是自由未知变量，它们取值不同，方程组的解就不同。 x B B 1 b 当 x N 0 时，解为 x 。 xN 0
x B B 1 b 定义： x 为Ax=b的一个基本解。 x 0 N
B称为基矩阵，或简称为基。 xB的各分量称为基变量，基变量的全体xB1,xB2,……,xBm称为一组基。 xN的各分量称为非基变量。 x B B 1 b 1 若 B b 0 ，则称 x 为约束条件Ax=b，x≥0的基本可 xN 0 行解，并称B为可行基矩阵。 若 B 1b 0 ，则基变量取值均为正数 ——非退化基本可行解 若 B 1b 0 ，且至少一个分量为0 ——退化的基本可行解
(2) 基本可行解的转换
令 f = Cx ，为目标函数。 记 A = ( p1, p2,……,pn)， pi为m维列向量。 将A分解成 (B, N) (可能经列调换)，使B为基矩阵，N为非基矩阵。 1 B b
(0) 设x 为基本可行解,此处目标函数值为 0 1 B b 1 (0) f 0 Cx ( C B , C N ) CB B b 0 其中，CB是C中与基变量对应的分量组成的m维行向量，CN为C中 与非基变量对应的n-m维行向量。 下面要从x(0)出发，求一个改进的基本可行解。 xB 设 x 为任一可行解，则由Ax=b得 x B B 1b B 1 Nx N xN
在x点处目标函数值为
xB f Cx ( C B , C N ) C B x B C N x N xN C B ( B 1b B 1 Nx N ) C N x N C B B 1b (C B B 1 N C N ) x N f 0 (C B B 1 p j c j ) x j f 0 ( z j c j ) x j
j R
其中R是非基变量下标集， z j C B B p j
1
j R
从上式可见，当 x j ( j R ) 取值相同时， z j c j 越大(正数)，目标函数 值下降越多。 因此选 zk ck max( z j c j ) 对应的非基变量(这里假定 z k ck 0)由 零变为正数，而其它非基变量仍为零，有Ax=b的解为 x B B 1 b B 1 pk x k b y k x k
1 其中 b 和 yk 均为m维列向量， b B 1b ，y k B pk 。
jR
将xB写成分量形式，并考虑xN中某一元素由0转为非0，有 x B1 b1 y1k x y b B2 2k 2 x k ， x N 0 0 x k 0 0 0T xB x y b Bm m mk 则在新的点目标函数值为 f f 0 ( z k ck ) x k 。
x k f ，同时由x≥0的限制，若xk过 考虑xk的取值：由上式， 大，则有可能 x Bi 0 。 为保证 x Bi 0 ，即 x Bi bi y ik x k 0 ，必须取 bi xk (i = 1,2,…,m) (当 y ik 0 时)。 yik
(当 y ik 0 时，无论xk取何正值，均有 x Bi 0 ，无法对xk进行限制(xi 应受到可行性限制))
所以，为使 x B 0 ，应令 x k min{
x x B1 x Br 1
这时，原来的基变量 x Br 0，得新的可行解：
0 x Br 1 x Bm
bi b yik 0} r 。 yik yrk
0 0 xk 0 0
T
必为基本可行解。 这样，就实现了基本可行解的转移。转换后的目标函数值比原来减少 了( z k ck ) x k 。 重复上述过程，不断改进基本可行解，直到所有的 z j c j 均为负 值，任何一个非基变量为正都不能使 f 值下降为止。 定理：若在极小化问题中，对于某个基本可行解，所有 z j c j 0 ，则 此基本可行解是最优解；而在极大化问题中，对某个基本可行解，所 有 z j c j ，则此基本可行解为最优解，其中 0 z j c j C B B 1 p j c j ，( j= 1,2,…, n)，称为判别数或检验数。
(3) 单纯形方法计算步骤
以极小化为例。
(1) 给定初始基本可行解，设初始基矩阵B； (2)
解 Bx B b ，求得 xB B1b b，令 x N 0，计算目标函数值 f C B xB ； (3) 求单纯形乘子w：解wB=CB，得 w C B 1 。对于所有非基变 B 量，计算判别数 z c wp c ，令 zk ck max( z j c j ) j j j j 若 z k c k 0 ，则对所有非基变量均有 z j c j 0，应停止计算， 现行基本可行解即是最优解。否则，进行下一步。 (4) 解 Byk pk ，得 yk B 1 pk ，若 yk 0，即yk的每个分量均非正 数，应停止计算，问题不存在有限最优解；否则，进行下一 步； bi br min y ik 0 ，则xBr为离基变量，xk为 (5)确定下标r，使
y rk y ik
jR
进基变量，用pk代替pBr，得新的基矩阵B，返回(2)。
( z j c j ) 外，其它步骤完全相同。 对极大化问题，除令(3)中 zk ck min jR
例 用单纯形方法解下列线性规划问题：
min f ( x ) 4 x1 x2
s.t . x1 2 x2 4 2 x1 3 x2 12 x1 x2 3 x1 0 , x2 0
为用单纯形方法求解上述问题，先引入松弛变量x3、x4、x5，把问题化为 标准形式
min f ( x ) 4 x1 x 2 s . t . x1 2 x 2 x 3 4 2 x1 3 x 2 x4 12 x1 x 2 x5 3 x j 0, j 1, , 5
系数矩阵
1 2 1 0 0 A ( p1 p2 p3 p4 p5 ) 2 3 0 1 0 1 1 0 0 1
第1次迭代：
1 0 0 B ( p3 p4 p5 ) 0 1 0 0 0 1 x3 4 x B x4 B 1b 12 3 x5
1 0 0 B 1 0 1 0 0 0 1
x 0 xN 1 x2 0
f1 c B x B (0 0 0)(4 12 3)T 0 1 0 0 (0 0 0) w cB B 1 (0 0 0) 0 1 0 0 0 1
z1 c1 wp1 c1 (0 0 0)( 1 2 1)T 4 4
z2 c2 wp2 c2 (0 0 0)(2 3 1)T 1 1
因此最大判别数是 z1 c1 4 ，下标k=1。
计算y1：
1 0 y1 B 1 p1 0 1 0 0 br b2 min{ 可由 yr 1 y21 0 1 1 2 2 0 1 1 1 b3 12 } min{ y31 2
b x B (4 12 3)T
3 }3 1
确定下标r为r =3。即xB中第3个分量x5为离基变量，x1为进基变量。用 p1代替p5，得到新基，进行下一次迭代。 第2次迭代：
1 0 1 B ( p3 p4 p1 ) 0 1 2 0 0 1 x3 7 b1 b 6 x B x4 B 1b 2 3 b3 x1
1 0 1 B 1 0 1 2 0 0 1
x2 0 xN x5 0
f 2 c B x B (0 0 4)(7 6 3)T
12
1 0 1 0 1 2 (0 0 4) w cB B 1 (0 0 4) 0 0 1 z2 c2 wp2 c2 (0 0 4)(2 3 1)T 1 5 z5 c5 wp5 c5 (0 0 4)(0 0 1)T 0 4
最大判别数是 计算y2：
z2 c2 5 ，下标 k =2 。
1 0 1 2 1 3 5 y2 B 1 p2 0 1 2 0 0 1 1 1
br b1 min{ yr 2 y12
b2 7 } min{ y22 1
6 6 } 5 5
则xBr=x4为离基变量，x2为进基变量。用p2代替p4，得到新基，进行 下一次迭代。 第3次迭代：
1 2 1 B ( p3 p2 p1 ) 0 3 2 0 1 1
7 1 1 5 5 B 1 0 1 2 5 5 3 1 0 5 5
29 x3 5 b1 1 6 b x B x2 B b 5 2 21 b x1 3 5
x4 0 xN x5 0
f 3 cB x B (0 1 4)( 29
7 1 1 5 5 w cB B 1 (0 1 4) 0 1 2 (0 1 2) 5 5 3 1 0 5 5
z4 c4 wp4 c4 (0 1 2)(0 1 0)T 0 1 z5 c5 wp5 c5 (0 1 2)(0 0 1)T 0 2
由于所有
* 1
5
6
5
21 )T 18 5
z j c j 0 ，因此得到最优解
和目标函数最优值
fmin 18
6 21 * x , x2 5 5
按照上述计算步骤，单纯形方法很容易用计算机程序实现。 上面介绍的只是单纯形方法的基本方法，在基本方法的基础 上，已经发展出很多改进算法。
表格形式 — 求解过程表格化； 两阶段法 — 引入人工变量，先求基本可行解，再求最优解； 大M法 — 在约束中增加人工变量xa ，修改目标函数，加上罚 项MeTxa, 在极小化目标函数过程中，用很大的正数M迫使 xa离 基； 退化情况 — 摄动法。退化情况下，有限次迭代可能求不出最 优解，出现循环； 修正单纯形法 — 修改旧基的逆阵来得到新基的； 变量有界情况； ……
随着优化问题规模的不断增大，计算效率成为在进行大规模优 化计算时必须考虑的问题。 虽然单纯形方法是求解线性规划最普遍的方法，但从计算效率 考虑，并不是求解线性规划问题的多项式时间算法。
多项式时间算法
根据计算复杂性理论，在数值计算中，一个问题的规模大小是用 输入长度来表示的。 输入长度：把一个问题的数据输入计算机时所需二进制代码的长 度l。 多项式时间算法：如果用某种算法解一数值计算问题时，所需计算 时间在最坏的情况下，不超过输入长度的某个多
项式的确定的数值 P(l)，则称该算法是解此问题的多项式时间算法。 多项式时间算法明显比指数时间算法等(如3l、l !)好，收敛速度快。 用上述方法检验, 单纯形方法在理论上还不是多项式时间算法。 问题是，对于线性规划问题, 能否找到多项式时间算法?
Karmarkar算法
Karmarkar算法是1984年提出的解线性规划问题的一种新方 法，是关于线性规划的多项式时间算法，计算复杂性比单纯形方法 低。
单纯形法及其衍生算法，都是沿可行解凸集的顶点寻优的。 Karmarkar算法改变了这种做法，对线性规划问题也从内点寻优。 并通过线性问题非线性化，在计算上达到简单化，是一种内点算法。
Karmarkar算法基本思想: 给定一个可行内点，对解空间进行 变换，使线性解位于变换空间多胞形的中心附近，然后使它沿最速 下降方向移动，求得一个改进的可行内点；再作逆变换，将在变换 空间中求得的点映射回原来的解空间，得到新的内点。重复以上过 程, 直至求出满足精度要求的最优解。
内点算法是优化算法研究的发展趋势之一。
八. 线性规划 (Linear Programming)
引 言
线性规划讨论的是最优化问题。 最优化理论所研究的对象是静态系统，即与时间无关的系 统，与前面各章所讨论的最优控制问题不同。 最优化理论和算法要解决的问题是： 在可选的方案中哪个方案最优(目标函数极值)； 怎样找出最优方案。 与最优控制理论相同，最优化理论也是泛函极值理论发展 的一个重要分支，20世纪40年代起逐渐形成单独的学科。 最优化理论和算法内容非常丰富，主要包括：线性规划、 整数规划、非线性规划、几何规划、 动态规划、随机规划、 网络决策等，而最基本的内容是线性规划和非线性规划。
8.1 凸集和凸函数
凸集和凸函数是线性规划和非线性规划(以及整个最优 化问题中)的非常重要的概念。 一般的最优化理论都建立在凸集和凸函数基础之上。 本节内容作为基础知识不作深入介绍，供需要时参考。
8.2 线性规划的定义和标准形式
(1) 线性规划的定义
考虑最优化问题的数学模型一般表示为 min (or max) f(x) s.t. g(x) = B 其中， f(x) 为目标函数， g(x) 为约束函数； x∈En, B 为 m 维列向 量，g(x)为m维向量函数， 线性规划定义：最优化问题数学模型中目标函数和约束函数都是变 量x的线性函数的，称之为线性规划问题。 线性规划是非线性规划的一种特殊形式，但在最优化理论与算法中 已成为非常重要的一个分支，在理论和算法上都很成熟，应用非常 广泛。
(2) 线性规划标准形式
一般线性规划问题总可以表示为：
( or max) i 1
min c i x i
n
(8-2-1)
ji
s .t .
a
i 1
n
xi b j ,
j 1,2,3, , m
(8-2-2)
j 1,2,3, , m
x i 0,
i 1,2,3, , n;
b j 0,
(8-2-3) (8-2-1’) (8-2-2’) (8-2-3’)
或用矩阵形式表示为：
( or max)
min Cx
s.t .
Ax B
x 0;
B0
其中A为 m ╳ n 维矩阵，C为n维行向量，B为m维列向量。
任何其他形式的线性规划问题均可转换成以上标准形式。 例如，若有 b j 0 可在相应等式两边乘（-1）（非负化）；
，用 若无 x i 0 限制，可令 x i x i x i ，其中x i , x i 0 x i , x i 代替 xi ； 若非 Ax B ，而是Ax B 或 Ax B，可引入 x n 1 , x n 2 , x n m ， 在每个不等式中加入或减去一个松驰变量，使其转化为等式 标准形式，而在目标函数中则令松驰变量的系数为零。
8.3 线性规划问题的图解法
对于n=2的线性规划问题，可以用图解法求解，以便较为直观地了解 多变量线性规划的一般性质。 例：生产安排问题 某工厂生产甲乙两种产品，其产量分别为 x1 , x2 个单位，每天可用资 源限制、单位产品资源消耗及单
位产品产值如表所示。
资源 名称 总量 消耗系数 甲产品 乙产品 原料A 1575kg 5kg/单位产量 3kg/单位产量 原料B 1500kg 4kg/单位产量 5kg/单位产量 工时 420分钟 1分钟 /单位产量 2分钟 /单位产量 产值系数 （元/单位产量） 13元/单位产量 11元/单位产量
问题：每天应生产甲乙两种产品（即 x1 , x2）各多少，使总产值 f ( x ) 13 x1 11 x2 最大？
此问题数学模型为：
max f ( x ) max(13 x1 11 x2 )
s.t .
x2
(1)
500 400 300
(2) (3)
(1) (2) x1 2 x2 420 4 x1 5 x2 1500 (3) x2 0 x1 0 ，
5 x1 3 x 2 1575
b
200 100
由约束条件，可在 x1 x2平面上作 出5条直线 x2 0 围 其中由(1)、(2)和 x1 0 ， 成的多边形满足所有的约束条件 多边形顶点为
a
0 100 200
d
300
c
400
500
x1
325 0 0 270 c ， ， a ，b d 0 75 210 0
设目标函数等值线方程为
13 x1 11 x2 变化时等值线 x 2 1 13 x1 在
11
x2
500 400 300
(1)
(3)
(2)
11 平面上平移，等值线法向量 n (13,11)T
也是目标函数的梯度，指向目标函 数增大的方向，因此沿此方向移动 等值线，目标函数值将增大。
200 100
b
a
0 100 200
d
300
x1 c
400 500
将等值线一直移动到约束条件构成 的多边形边缘，即多边形顶点d处， 270 x d 得目标函数极大值，即极值点为 75 最优解为 max f ( x ) f ( xd ) 13 270 11 75 4335
即x1=270，x2=75时可获得最大产值4335元。显然，这时约束条件 全部满足。
8.4 线性规划的基本性质
结合前面图解的例子，可对线性规划的基本性质作出直观解释。 (1) 可行解――满足约束条件（等式或不等式）的一组解称为可行解。 可行解有无穷多个，即多边形中任意一点。 (2) 最优解――使目标函数为极值的可行解，如上例中的xd。 (3) 可行（解）域 —— 约束条件所包含的范围，由无穷多个可行解组 成，包含最优解，如上例中的多边形 abdc。
定理：线性规划的可行域是凸集。
(4) 定理：线性规划的目标函数极值如果存在，一定在可行域多边形 （多面体）的顶点上达到（最优顶点）。 基本可行解 —— 可行域多边形（多面体）顶点的解称为基本可行解。 （更严格的定义后面将作介绍） x 0 有可行解，则一定存在 (5) 基本可行解的存在定理：如果 Ax B， 基本可行解。其中A是 m n 矩阵，rank(A)=m。
(6) 若有两个以上的顶点是最优解，则这些顶点的凸组合也都是最优解。 (7) 基本可行解数是有限的。因此解线性规划的问题可从可行解域 减少为基本可行解数，进行有限步迭代总可以找到最优解。 (8) 线性规
划的几种特殊情况 。 ① 约束条件与变量数不等 如上例中约束条件多于变量数，则有2个有效约束，1个松驰 约束。 ② 目标函数与可行域一边平行，最优解不唯一。 x max f ( x ) max(18 x1 10 x2 ) 例：
2
s .t .
9 x1 5 x 2 45
7 x1 9 x 2 63 x1 0 , x2 0
10 8
6 4 2 0 2 4 6 8 10
x1
③ 可行域无界 例(a) ： max f ( x ) x2 2 x1 s .t . x1 x 2 1
x1 3 x 2 3
x2
1
此时有解， 0 * x 1
0 1
x1 0 , x2 0
x2
x1
f ( x* ) 1
例(b) ： max f ( x ) x1 x2 1 s.t . x2 x1 2 2 x 2 x1 4
x1 0 , x2 0
4
此时无解。
x1
0
4
x2
例(c) ： max f ( x ) x1 4 x2
s .t .
x2 2
2
x1 0 , x2 0
0 2
x
1
此时有解， 0 * x 2 f ( x* ) 8
④ 无可行解 例： max f ( x ) x1 x2
x2
s .t .
x1 x 2 10 2 x1 x 2 30
10
两个约束矛盾， 无解。
0 10
x1 0 , x2 0
x1
8.5 单纯形方法(Simplex Method)
单纯形方法是求解线性规划的普遍方法，1947年由匈牙利数学 家G. B. Dantzig提出，使线性规划成为运筹学的一个分支。 单纯形方法基本思想：从一个基本可行解出发，求一个使目标函数 值有所改善的基本可行解；通过不断改进基本可行解，达到最优基 本可行解。 考虑线性规划问题标准形式： min Cx s.t. Ax=b x≥ 0 其中A是m ╳ n维矩阵，C为n维行向量，b为m维列向量。
(1)基本可行解的严格定义
上面标准形式中，设A的秩为m，则可设 A=[B, N]，其中B为m阶可 逆方阵。这种做法不失一般性。 xB x 又记 x ，x B 的分量与B中列对应，x N的分量与N中列对应. N 则有 Ax b [ B, N ]
xB b xN
或表示为 Bx B Nx N b 因而有
x B B 1 b B 1 Nx N
xN的分量是自由未知变量，它们取值不同，方程组的解就不同。 x B B 1 b 当 x N 0 时，解为 x 。 xN 0
x B B 1 b 定义： x 为Ax=b的一个基本解。 x 0 N
B称为基矩阵，或简称为基。 xB的各分量称为基变量，基变量的全体xB1,xB2,……,xBm称为一组基。 xN的各分量称为非基变量。 x B B 1 b 1 若 B b 0 ，则称 x 为约束条件Ax=b，x≥0的基本可 xN 0 行解，并称B为可行基矩阵。 若 B 1b 0 ，则基变量取值均为正数 ——非退化基本可行解 若 B 1b 0 ，且至少一个分量为0 ——退化的基本可行解
(2) 基本可行解的转换
令 f = Cx ，为目标函数。 记 A = ( p1, p2,……,pn)， pi为m维列向量。 将A分解成 (B, N) (可能经列调换)，使B为基矩阵，N为非基矩阵。 1 B b
(0) 设x 为基本可行解,此处目标函数值为 0 1 B b 1 (0) f 0 Cx ( C B , C N ) CB B b 0 其中，CB是C中与基变量对应的分量组成的m维行向量，CN为C中 与非基变量对应的n-m维行向量。 下面要从x(0)出发，求一个改进的基本可行解。 xB 设 x 为任一可行解，则由Ax=b得 x B B 1b B 1 Nx N xN
在x点处目标函数值为
xB f Cx ( C B , C N ) C B x B C N x N xN C B ( B 1b B 1 Nx N ) C N x N C B B 1b (C B B 1 N C N ) x N f 0 (C B B 1 p j c j ) x j f 0 ( z j c j ) x j
j R
其中R是非基变量下标集， z j C B B p j
1
j R
从上式可见，当 x j ( j R ) 取值相同时， z j c j 越大(正数)，目标函数 值下降越多。 因此选 zk ck max( z j c j ) 对应的非基变量(这里假定 z k ck 0)由 零变为正数，而其它非基变量仍为零，有Ax=b的解为 x B B 1 b B 1 pk x k b y k x k
1 其中 b 和 yk 均为m维列向量， b B 1b ，y k B pk 。
jR
将xB写成分量形式，并考虑xN中某一元素由0转为非0，有 x B1 b1 y1k x y b B2 2k 2 x k ， x N 0 0 x k 0 0 0T xB x y b Bm m mk 则在新的点目标函数值为 f f 0 ( z k ck ) x k 。
x k f ，同时由x≥0的限制，若xk过 考虑xk的取值：由上式， 大，则有可能 x Bi 0 。 为保证 x Bi 0 ，即 x Bi bi y ik x k 0 ，必须取 bi xk (i = 1,2,…,m) (当 y ik 0 时)。 yik
(当 y ik 0 时，无论xk取何正值，均有 x Bi 0 ，无法对xk进行限制(xi 应受到可行性限制))
所以，为使 x B 0 ，应令 x k min{
x x B1 x Br 1
这时，原来的基变量 x Br 0，得新的可行解：
0 x Br 1 x Bm
bi b yik 0} r 。 yik yrk
0 0 xk 0 0
T
必为基本可行解。 这样，就实现了基本可行解的转移。转换后的目标函数值比原来减少 了( z k ck ) x k 。 重复上述过程，不断改进基本可行解，直到所有的 z j c j 均为负 值，任何一个非基变量为正都不能使 f 值下降为止。 定理：若在极小化问题中，对于某个基本可行解，所有 z j c j 0 ，则 此基本可行解是最优解；而在极大化问题中，对某个基本可行解，所 有 z j c j ，则此基本可行解为最优解，其中 0 z j c j C B B 1 p j c j ，( j= 1,2,…, n)，称为判别数或检验数。
(3) 单纯形方法计算步骤
以极小化为例。
(1) 给定初始基本可行解，设初始基矩阵B； (2)
解 Bx B b ，求得 xB B1b b，令 x N 0，计算目标函数值 f C B xB ； (3) 求单纯形乘子w：解wB=CB，得 w C B 1 。对于所有非基变 B 量，计算判别数 z c wp c ，令 zk ck max( z j c j ) j j j j 若 z k c k 0 ，则对所有非基变量均有 z j c j 0，应停止计算， 现行基本可行解即是最优解。否则，进行下一步。 (4) 解 Byk pk ，得 yk B 1 pk ，若 yk 0，即yk的每个分量均非正 数，应停止计算，问题不存在有限最优解；否则，进行下一 步； bi br min y ik 0 ，则xBr为离基变量，xk为 (5)确定下标r，使
y rk y ik
jR
进基变量，用pk代替pBr，得新的基矩阵B，返回(2)。
( z j c j ) 外，其它步骤完全相同。 对极大化问题，除令(3)中 zk ck min jR
例 用单纯形方法解下列线性规划问题：
min f ( x ) 4 x1 x2
s.t . x1 2 x2 4 2 x1 3 x2 12 x1 x2 3 x1 0 , x2 0
为用单纯形方法求解上述问题，先引入松弛变量x3、x4、x5，把问题化为 标准形式
min f ( x ) 4 x1 x 2 s . t . x1 2 x 2 x 3 4 2 x1 3 x 2 x4 12 x1 x 2 x5 3 x j 0, j 1, , 5
系数矩阵
1 2 1 0 0 A ( p1 p2 p3 p4 p5 ) 2 3 0 1 0 1 1 0 0 1
第1次迭代：
1 0 0 B ( p3 p4 p5 ) 0 1 0 0 0 1 x3 4 x B x4 B 1b 12 3 x5
1 0 0 B 1 0 1 0 0 0 1
x 0 xN 1 x2 0
f1 c B x B (0 0 0)(4 12 3)T 0 1 0 0 (0 0 0) w cB B 1 (0 0 0) 0 1 0 0 0 1
z1 c1 wp1 c1 (0 0 0)( 1 2 1)T 4 4
z2 c2 wp2 c2 (0 0 0)(2 3 1)T 1 1
因此最大判别数是 z1 c1 4 ，下标k=1。
计算y1：
1 0 y1 B 1 p1 0 1 0 0 br b2 min{ 可由 yr 1 y21 0 1 1 2 2 0 1 1 1 b3 12 } min{ y31 2
b x B (4 12 3)T
3 }3 1
确定下标r为r =3。即xB中第3个分量x5为离基变量，x1为进基变量。用 p1代替p5，得到新基，进行下一次迭代。 第2次迭代：
1 0 1 B ( p3 p4 p1 ) 0 1 2 0 0 1 x3 7 b1 b 6 x B x4 B 1b 2 3 b3 x1
1 0 1 B 1 0 1 2 0 0 1
x2 0 xN x5 0
f 2 c B x B (0 0 4)(7 6 3)T
12
1 0 1 0 1 2 (0 0 4) w cB B 1 (0 0 4) 0 0 1 z2 c2 wp2 c2 (0 0 4)(2 3 1)T 1 5 z5 c5 wp5 c5 (0 0 4)(0 0 1)T 0 4
最大判别数是 计算y2：
z2 c2 5 ，下标 k =2 。
1 0 1 2 1 3 5 y2 B 1 p2 0 1 2 0 0 1 1 1
br b1 min{ yr 2 y12
b2 7 } min{ y22 1
6 6 } 5 5
则xBr=x4为离基变量，x2为进基变量。用p2代替p4，得到新基，进行 下一次迭代。 第3次迭代：
1 2 1 B ( p3 p2 p1 ) 0 3 2 0 1 1
7 1 1 5 5 B 1 0 1 2 5 5 3 1 0 5 5
29 x3 5 b1 1 6 b x B x2 B b 5 2 21 b x1 3 5
x4 0 xN x5 0
f 3 cB x B (0 1 4)( 29
7 1 1 5 5 w cB B 1 (0 1 4) 0 1 2 (0 1 2) 5 5 3 1 0 5 5
z4 c4 wp4 c4 (0 1 2)(0 1 0)T 0 1 z5 c5 wp5 c5 (0 1 2)(0 0 1)T 0 2
由于所有
* 1
5
6
5
21 )T 18 5
z j c j 0 ，因此得到最优解
和目标函数最优值
fmin 18
6 21 * x , x2 5 5
按照上述计算步骤，单纯形方法很容易用计算机程序实现。 上面介绍的只是单纯形方法的基本方法，在基本方法的基础 上，已经发展出很多改进算法。
表格形式 — 求解过程表格化； 两阶段法 — 引入人工变量，先求基本可行解，再求最优解； 大M法 — 在约束中增加人工变量xa ，修改目标函数，加上罚 项MeTxa, 在极小化目标函数过程中，用很大的正数M迫使 xa离 基； 退化情况 — 摄动法。退化情况下，有限次迭代可能求不出最 优解，出现循环； 修正单纯形法 — 修改旧基的逆阵来得到新基的； 变量有界情况； ……
随着优化问题规模的不断增大，计算效率成为在进行大规模优 化计算时必须考虑的问题。 虽然单纯形方法是求解线性规划最普遍的方法，但从计算效率 考虑，并不是求解线性规划问题的多项式时间算法。
多项式时间算法
根据计算复杂性理论，在数值计算中，一个问题的规模大小是用 输入长度来表示的。 输入长度：把一个问题的数据输入计算机时所需二进制代码的长 度l。 多项式时间算法：如果用某种算法解一数值计算问题时，所需计算 时间在最坏的情况下，不超过输入长度的某个多
项式的确定的数值 P(l)，则称该算法是解此问题的多项式时间算法。 多项式时间算法明显比指数时间算法等(如3l、l !)好，收敛速度快。 用上述方法检验, 单纯形方法在理论上还不是多项式时间算法。 问题是，对于线性规划问题, 能否找到多项式时间算法?
Karmarkar算法
Karmarkar算法是1984年提出的解线性规划问题的一种新方 法，是关于线性规划的多项式时间算法，计算复杂性比单纯形方法 低。
单纯形法及其衍生算法，都是沿可行解凸集的顶点寻优的。 Karmarkar算法改变了这种做法，对线性规划问题也从内点寻优。 并通过线性问题非线性化，在计算上达到简单化，是一种内点算法。
Karmarkar算法基本思想: 给定一个可行内点，对解空间进行 变换，使线性解位于变换空间多胞形的中心附近，然后使它沿最速 下降方向移动，求得一个改进的可行内点；再作逆变换，将在变换 空间中求得的点映射回原来的解空间，得到新的内点。重复以上过 程, 直至求出满足精度要求的最优解。
内点算法是优化算法研究的发展趋势之一。