第二章单纯形法

s.t.
32x1x133x2x22xx33
100 120
x1, x2, x3 0
CB XB b 0 x4 100 0 x5 120
OBJ = 0 zj cj-zj
40 45 24 0 0
x1 x2 x3 x4 x5
23110 33201 00000 40 45 24 0 0
求解过程：
序
40 45 24 0 0
基本步骤：
始
确定初试基础可行解
检查是否为
是
最优解？
否 确定改善方向
求新的基础可行解
求最优解的目标函数值
1、初始基本可行解的确定
对目标函数为(MAX≤)形式的线性规划背景模型，通过标准化， 每一个约束方程引入一个松弛变量，松弛变量为基变量，其 他变量为非基变量，得到一个初始基本可行解。
n
max f (x) cj xj j 1
cB
p
' j
c ia
' ij
,
j
m
1,
n;
机会成本
i1
j c j z j, j m 1, n ;
检验数
线性规划问题的典式展开式：
max z cBB1b (cm1 cB pm' 1)xm1 (cj cB p'j )xj
(cn cB pn' )xn
x1 x2
a x ' 1,m1 m1
a1', j xj
a' 1,n
xn
b1'
a x ' 2,m1 m1a2' , xja' 2,n
xn
b2'
xm
a x ' m,m1 m1
am' , j xj
a' m,n
xn
bm'
x1, x2, xm 0; xj 0( j m 1,m 2 n)
表格形式典式
I II III
c1 CB XB b x1
5
B
G
2 x1 3
C x1
x2 x2 x2
x3 x4 x5
10 8 7
f(x) = 3 6
4
x1 , x 2 , x 3 , x2 4 , x 5 0
3 最优解
2
:
x
K
1
2, 1
x2
6,
1 max f ( x ) 36 .
D
H
O 12345678
非基 变量
基变量
图中的点 解
x1, x2 x3 =10 x4 =8 x5 =7 O 基本可行解
x1, x3 x2 =10 x4 =-2 x1, x4 x2 =8 x3 =2 x1, x5 x2 =7 x3 =3
x5 =-3 x5 =-1 x4 =1
F
基解
E
基解
A 基本可行解
x2, x3 x2, x4 x3, x4
x1 =5 x1 =8 x1 =2
且至少有一个为零，才能保证基变量个数不变。
(3)基可行解的改进（通过初等变换求更优基可行解)
主行 i* 行与主列 j* 相交的元素ai*j* 称为主元，迭代以主 元为中心进行，迭代的实质是线性变换，即要将主元ai*j*变为1，
主列上其它元素变为0，基本步骤为：
变换主行 a i*ja i*j a i*j* j 1 ,2 , ,m n
s .t
x
B
B
1 Nx
N
B 1b
x 0
m
令 z 0 c B B 1 b
c
ib
' i
;
i1
m
z j
c B 机B 会 1成p 本j
cB
p
' j
c ia
' ij
,
j
m
1,
i1
n;
j c j z j, j m 1, n ;
检验数
解的判断：
当所有σj≤０时，表示目标函数已经达到最优，若 存在一个非基变量的检验数等于0，则该线性规划问题 有多重最优解； σj＞0，则表示没有达到最优，若对应该列所有aij ≤０时，则线性规划问题为无界解
2
a2,m+
2
…
am,m+
2
zm+2
cm+2z
… … …
… … … … …
cn xn
a1n
a2n
… amn
zn cn-zn
§2-3 单纯形法
一、单纯形法的基本思路和步骤
思路：如果线性规划问题存在最优解，一定有一 个基本可行解是最优解。因此单纯形法迭代的基 本思路是：先找出一个基本可行解，判断其是否 为最优解，如为否，则转换到相邻的基本可行解， 并使目标函数值不断增大，一直找到最优解为止。
25
二、单纯型表及其格式
IV III II
I
c1 c2 … cn cn+1 CB XB b x1 x2 … xn xn+1
cn+2 … cn+m xn+2 … xn+m
cn+1 xn+1 b1 a11 a12 … a1n
1
0… 0
cn+2 xn+2 b2 a21 a22 … a2n
0
1… 0
c1 x1 b1' 1
c2 x2 b2' 0
… …… …
cm xm bm' 0
OBJ= CBb’ c1 0
IV
c2 … cm x2 … xm
0 …0
1 …0
… …… 0 …1
c2 … cm 0 …0
cm+1 xm+1
a1,m+1
a2,m+1
… am,m+1
zm+1 cm+1z
cm+2 xm+2
a1,m+
解空间 退化解
二、凸集及凸集的顶点
1、凸集
设X1,X2∈Ｋ，若两点连线上任意一点αX1＋（１-α）X２ ∈ Ｋ,且０≤α≤１，则称Ｋ为凸集．
2、极点
设Ｋ为凸集，X∈Ｋ，若Ｘ不能用两点X1,X2∈Ｋ的线性组合 表示为αX1＋（１-α）X２ ∈Ｋ,且０＜α＜１，则称Ｘ为 Ｋ的极点或顶点．（X不是K中任何线段的内点）
x4 =3 x3 =-6 x2 =6
x5 =7 x5 =7 x5 =1
D 基本可行解 H 基解 C 基本可行解
最优解
x3, x5 x1 =1.5 x2 =7 x4 =-0.5 G
基解
x4, x5 x1 =1 x2 =7 x3 =1 B 基本可行解
x 1 x1 =2, x2 =2, x3 =4, x4 =4, x5 =3 K
三、线性规划问题的基本定理
定理1:若线性规划问题存在可行域（满足约束条件），则可行域 是凸集。
证明:假设X1和X2分别是线性规划问题的可行解,则存在:AX1=b;AX2=b 现有X=αX1+(1-α)X2; AX=A[αX1+(1-α)X2]=AαX1+AX2-AαX2=α×b+b-α×b=b,故X也是一可行解.
s.t.
n j1
aij x j
bi ,
xj 0,
n
m
化 maxf (x) cjxj 0 xsi
为
j1
i1
i 1,2, ,m
j 1,2, ,n
标
准型：s.t.
n
j1
aijxj
xsi
bi
,
xj, xsi 0,
i 1,2, ,m j 1,2, ,n
松弛变量
标准型约束方程的系数矩阵为:
可行解
标准型LP问题解的概念
解 可行解X
最优解X*
基解X=
X X
B N
基本可行解
X=
X X
B N
满足条件
适用对象
备注
AXb X0
AX* b AXb
AXb
X0 CTX*optTCX
B 0 XN 0
B 0
XB 0 X N 0
XXN含 B含有有 nm-m个个分分量量
线性规划标准型问题解的关系
非可行解 可行解 约基束可方行程解的 基解
量个数<m 时，称为退化解；基本可行解所对应的基
称为可行基（feasible basis）。
5、最优解：若基本可行解又是最优解（也称基本最 优解），这个基就称为最优基（optimal basis）。
可行解、基解和基可行解举例
x2
10 F
9 max f ( x ) 6 x1 4 x2
8E 7A
6 s.t.
变换主列除主元保留为1，其余都置0
变换非主行、主列元素 aij (包括 bi)
bi
bi
bi*aij* ai*j*
(1.2.5a)
aij
aij
ai*jaij* ai*j*
(1.2.5b)
(4)标准型的单纯型算法
主行 ai*j
主元
ai*j*
aij
aij*
主
四角算法图示
列
迭代过程:
1.变换CB，XB; 2.计算目标函数、机会成本 zj 和检验数 cj zj
a 11
a12
a1n 1 0
0
A
a 21
a
m1
a 22
am2
a2n 0 1
a mn 0 0
0 1
n
m阶方阵
令xj=0,则xsi=bi，推出X=(0,0,0…０,b1,b2…bm)为线 性规划问题的初始基可行解