初始基本可行解：
X ( 0) ( x1 , x2 ,, xm ,0,0,...,0)T (b1 , b2 ,......,bm ,0,0,...,0)T
0
0
0
单纯形法基本原理
2、基变换 定义：两个基可行解称为相邻的，如果它们之间变换 且仅变换一个基变量。 初始基可行解的前m个为基变量，
X
凸集
顶点
凸集
不是凸集
顶点：如果凸集C中不存在任何两个不同的点X1，X2，使X 成为这两个点连线上的一个点
单纯形法基本原理
定理1：若线性规划问题存在可行解，则该问题的可行域是 凸集。 定理2：线性规划问题的基可行解X对应可行域(凸集)的顶 点。 定理3：若问题存在最优解，一定存在一个基可行解是最优 解。（或在某个顶点取得）
的左边变成一个单位矩阵，
b (b1 a1 j ,.,bl 1 al 1 j , , bl 1 al 1 j ,.,bm am1 j , ) ( x1 , x2 ,..., xl 1 , x j , xl 1 ,..., xm )
X
(1)
T
与X
( 0)
是相邻的基可行解。
M M bm 0 L
M M
M M
L 1 am,m1 L L 00
M , M amn m
bi 其中： i a kj 0 a kj
j c j ci aij c j z j
单纯形法的计算步骤
例1.12 用单纯形法求下列线性规划的最优解
max Z 3 x1 4 x 2 2 x1 x 2 40 x1 3 x 2 30 x , x 0 1 2
xi0 aij 0, aij 0,取值无限，
表明目标函数达到无限，说明LP有无界解。
单纯形法的计算步骤
单纯形表
cB
cj
XB
c1 cm
x1 xm
j
c1 L L cm cm1 L L cn i b x1 L L xm xm1 L L xn b1 1 L L 0 a1,m1 L L a1n 1
运 筹 帷 幄 之 中 云南财经大学 物流学院 窦志武
决 胜
单纯形法基本原理
千 里 之 外
单纯形法基本原理
连接几何形体中任意两点的线段仍完全在该几何形 体之中。 有限个凸集的交集仍然是凸集。
单纯形法基本原理
凸集：如果集合C中任意两个点X1、X2，其连线上的所有点 也都是集合C中的点，称C为凸集。
m 0 m 0
( p j aij pi ) pi xi b, ( xi aij ) pi p j b
i 1 i 1 i 1
m
找到满足约束方程组
p x
j 1 j
n
j
b 的另一点：
第j个大于0 只变换1个变量； 前m个变量必须换 出1 个
0 0 X (1) ( x1 a1 j ,...,xm amj ,0,..., ,...0)T
18 30
单纯形法的计算步骤
例1.13 用单纯形法求解
max Z x1 2 x 2 x 3 2 x1 3 x 2 2 x 3 15 1 s .t x1 x 2 5 x 3 20 3 x1、x 2、x 3 0
解：将数学模型化为标准形式：
( 0)
( x , x2 ,...xm , o,...o)
n j 1
0 1
0
0
T
MaxZ c j x j
n Pj x j b s.t. j 1 x j 0( j 1,2,3...n)
代入约束条件有
px
i 1
m
0
i i
b
单纯形法基本原理
系数矩阵的增广矩阵
0 i
单纯形法基本原理
0 0 X (1) ( x1 a1 j ,...,xm amj ,0,..., ,...0)T
是一个可行解。因为变量 x11, x21,
xl-11, xl+11,…………xm1, xj1所对应的向量，
经过重新排列后加行b列形成的增广矩阵为：
p1 1 0 . 0 0 0 . 0 p2 1 0 0 0 . 0 0 amj 0 ... pl 1 . 0 pj a1 j a2 j pl 1 0 0 0 1 ... pm 0 . 1 al 1 j 0 alj 0 al 1 j 0 0 0 . 1 bl 1 bl bl 1 . bm b b1 b2
cj cB 0 Xb x3 b 40 3 x1 2 4 x2 1 0 x3 1 0
θi
x4 0
0
x4
30
1
3
3
4
0
0
1
0
j
检验数
1 c1 (c3a11 c4a21 ) 3 (0 2 0 1) 3
2 c2 (c3a21 c4a22 ) 4 (0 1 0 3) 4
单纯形法基本原理
最优性判别 １、如果所有的检验数 j 0 ，表明现有的顶点对应 的基可行解为最优解。 ２、当所有的检验数 j 0 ，又对某个非基变量xj 的检验数等于 0，并且可以找到 >0,这表明可以找到 一个顶点目标函数达到最大，说明LP有无穷多个最 优解。 ３、如果存在某个检验数 j >0,又 P j ≤0,
单纯形法基本原理
问题
①如果限制条件中既有“≤”类型的约束， 又有“≥”或“=”类型的约束，怎么办？ 构造单位阵 ②初始可行基一定要选单位阵？ b列正好就是基变量的取值，因此称b列 为解答列
单纯形法基本原理
（2）写出初始基可 b(i) ，一起构 成初始基可行解
② 确定换出变量。根据下式计算并选择θ ，选最小的θ对应基
单纯形法的计算步骤
③
用换入变量xk替换基变量中的换出变量，得到一个新的基。 对应新的基可以找出一个新的基可行解，并相应地可以画出 一个新的单纯形表。
5）重复3）、4）步直到计算结束为止。
单纯形法的计算步骤
换入列
将3化为1
bi /ai2，ai2>0 4 0 0 θi 换 出 行
因为p1,…,pm,是一个基，其他向量pj可以这个基 的线性组合表示：
p j aij pi
i 1
m
单纯形法基本原理
m
( p j aij pi ) 0
i 1
m
p j aij pi 相减，然后乘上一个正数θ ,加上
i 1
p x
i 1
m
( 0)
i i
b 经过整理得到：
max Z x1 2 x 2 x 3 2 x1 3 x 2 2 x 3 x 4 15 1 s .t x1 x 2 5 x 3 x 5 20 3 x j 0, j 1,2, ,5
不难看出x4、x5可作为初始基变量，列单纯形表计算。
当线性规划的约束条件均为≤，其松弛变量的系数矩阵为单位 矩阵；当线性规划的约束条件均为≥或=，为便于找到初始基 可行解，构造人工变量，人为产生一个单位矩阵。
单纯形法基本原理
式中p1,„,pm 为基变量,同其所对应的 x1,x2,„..,xm为基变量；其它变量 xm+1,xm+2，„„,xn为非基变量。令所有的非基变量 等于零。
单纯形法的计算步骤
单纯形法的思路 找出一个初始可行解
是否最优
循 环 否
是
最优解 结束
转移到另一个基本可行解 （找出更大的目标函数值） 核心是：变量迭代
单纯形法基本原理
四、单纯形法的迭代原理
1、确定初始基可行解
(1)初始可行基的确定
观察法 —— 观察系数矩阵中是否含有现成 的单位阵？ LP限制条件中全部是“≤”类型的约束—— 将新增的松弛变量作为初始基变量，对应的 系数列向量构成单位阵；
单纯形法基本原理
其中θ 是X（1）的第j个坐标的值，要使X（1）是一个 基可行解，对所有的i=1,…,m,存在
x aij 0,
0 i
令这m个不等式至少有一个等号成立，当
xi0 xl0 ai j 0, 上式成立，令 min{ | aij 0} aij alj
0, (i l ) x aij 0, (i l )
单纯形法的计算步骤
cj 1 2 1 0 0
cB
基变 量 0 x4 0 j x5
b
x1
x2
x3
x4
x5
θi
15 2 20 1/3
1 75 3 20 1/3 1/3
-3 1
单纯形法基本原理
线性规划限制条件都是“≥”或“=”类 型的约束——
先将约束条件标准化，再引入非负的人工变量， 以人工变量作为初始基变量，其对应的系数列向量 构成单位阵，称为“人造基”； 然后用大M法或两阶段法求解；
单纯形法基本原理
使约束方程的系数矩阵中出现一个单位阵， 用单位阵的每一个列向量对应的决策变量作 为“基变量”，这样，出现在单纯形表格中 的B(i)列（即约束方程的右边常数）值正好就 是基变量的取值。
单纯形法的计算步骤
3）进行最优性检验 如果表中所有检验数 0 ，则表中的基可行解就是问题 j 的最优解，计算停止。否则继续下一步。 4）从一个基可行解转换到另一个目标值更大的基可行解， 列出新的单纯形表
① 确定换入基的变量。选择 j 0 ，对应的变量xj作为换入变
量，当有一个以上检验数大于0时，一般选择最大的一个检 验数，即： k max{ j | j 0} ，其对应的xk作为换入变 量。 变量作为换出变量。 bi L min a ik 0 a ik