初始可行基 ：
1 0 0
B(0)
(Pn1,Pn2,,Pnm)
0010
0 1
初始基本可行解：
X (0 )(0 ,0 , ,0 ,b 1,b 2, ,b m )T
一般（经过若干次迭代），对于基B，
用非基变量表出基变量的表达式 为：
n
xni bi' ai'jxj, j1
0 0 1
对应的基变量是 x3，x4，x5； 第三步：写出初始基本可行解和相应的
目标函数值
两个关键的基本表达式：
①用非基变量表示基变量的表达式
x3 8x12x2 x4 164x1 x5 12 4x2
初始基本可行解
X(0) (0,0,8,16,12)T
②用非基变量表示目标函数的表达式
Z02x13x2
二、单纯形法原理（用代数方法求解 LP） 例
maxZ 2x1 3x2
x1 2x2 8
s.t.4x1 4x2
16 12
x1, x2 0
(台时约束) （原材料约束）
第 一 步 ： 引 入 非 负 的 松 弛 变 量 X3,x4,x5, 将 该 LP化为标准型
maxZ2x13x2 0x30x4 0x5
选哪一个非基变量进基？
选x2为进基变量（换入变量） 问题讨论：能否选其他的非基变量进基？
任意一个 × 任意一个正检验数对应的非基变量 ✓ 最大正检验数对应的非基变量 ✓ 排在最前面的正检验数对应的非基变量 ✓
② 确定出基变量：分析非基变量表示基变 量的表达式
问题讨论
x2进基意味着其取值从0变成一个正数（经济 意义——生产乙产品），能否无限增大？ 当x2增加时，x3、x4、x5 会如何变化？ 具体如何确定换出变量？
LP限制条件中全部是“≤”类型的约束 ——将新增的松弛变量作为初始基变量，
对应的系数列向量构成单位阵；
（2）写出初始基本可行解——
根据“用非基变量表示基变量的表达式”， 非基变量取0，算出基变量，搭配在一起构成 初始基本可行解。
2、建立判别准则
写出用非基变量表示目标函数的表达式
就LP限制条件中全部是“≤”类型约束，新 增的松弛变量作为初始基变量的情况来描述：
于是，若LP只有唯一最优解，这个最优解 所对应的点一定是可行域的一个顶点；若LP有 多个最优解，那么肯定在可行域的顶点中可以找 到至少一个最优解。
2．需要解决的问题：
(1) 第一个（顶点） 基本可行解怎么找？ (2) 如 何 决 定 一 个 基 本 可 行 解 是 不 是 最 优 解——最优判断标准是什么？ (3)如果不是最优，怎么从一个基本可行解 向下一个基本可行解转移 ——转移方法？
x2
3
1 4 x5
得新的基本可行解 X(1)=(0，3，2，16，0)T
写出用非基变量表示目标函数的表达式:
Z 2x1 3x2
2x1
33
1 4
x5
92x1
3 4
x5
可得相应的目标函数值为Z(1)=9
检验数仍有正的, 继续换基、判断。
第五步：上述过程何时停止？ 当用非基变量表示目标函数的表达式中，非
此时LP的标准型为
nm
M a xZ c j x j j 1
a11 x1 a12 x2 L a1n x n x n 1 b1
s.t. Ma 21 x1
a22
x2
L M
a2n xn xn2 b2 M
a
m
1
x1
am2 x2
L
amn xn xnm bm
x1 , x2 ,L , xn m 0
x12x2 x3
8
s.t.4x1
x4 16
4x2
x5 12
x1,x2,x3,x4,x5 0
(台时约束) （原材料约束）
➢x3, x4, x5 三个松弛变量的经济含义表示什么？
第二步：寻求初始可行基，确定基变量
1 2 1 0 0
1 0 0
A
4
0
0 4
0 0
1 0
0
1
BP3,
P4,
P50 1 0
➢根据非基变量表示基变量的表达式
x3 8 x1 2 x2
x
4
16
4 x1
x
5
12
4 x2
当x2增加时， x3， x5会减小，但有限度——必
须≥0，以保持解的可行性！于是
x38x12x20 x4164x10 x512 4x20
x282
x2142
x2min82,,1423
当x2的值从0增加到3时, x5首先变为0, 此时x3=2>0，
基变量的系数（检验数）全部非正时，当前的 基本可行解就是最优解!
为什么？ ——分析用非基变量表示目标函数的表达式， 如果让负检验数所对应的变量进基，目标函数 值将下降！Z=14-1.5x3-0.125x4
三、单纯形法的一般描述：
1、初始可行解的确定
(1)初始可行基的确定 观察法——观察系数矩阵中是否含有现成 的单位阵？
图解法的局限性？
1947 年 美 国 数 学 家 丹 捷 格 (G.B.Dantzig)提出的单纯形法 提供了方便、有效的通用算法求 解线性规划。
一、单纯形法的基本思想
1、顶点的逐步转移
ቤተ መጻሕፍቲ ባይዱ
LP可行域
基本可 行解
顶点转移的依据？
根据线性规划问题的可行域是凸集（凸多边 形或凸多面体），若LP有最优解，就一定可以 在可行域的顶点上找到。
因此选x5为出基变量（换出变量）。
这种用来确定出基变量的规则称为 “最 小比值原则”（或θ原则）。
基变量 x5 出基:
非基变量 x2 进基:
1 2 1 0 0
A
4
0
0
1
0
0 4 0 0 1
B = (P3，P4, P5 )
向量: P1 P2 P3 P4 P5 变量: x1 x2 x3 x4 x5
当前的目标函数值
Z (0) 0
请解释结果的经济含义 ——
不生产任何产品，资源都没有被利用 （ x3=8,x4=16,x5=12），两种产品的总利润 为0！
第四步：分析两个基本表达式 ① 分析用非基变量表示目标函数的表达式，看
看目标函数是否可以改善,如何改善？
Z2x13x2
非基变量前面的系数均为正数，所以任何 一个非基变量变成基变量（进基）都可能 使Z值增加 通常, 把非基变量前面的系数叫“检验数”
B = ( P2, P3，P4 )
基变换（写出第二个基本可行解及其对
应的目标函数值）
新的基变量——x2 , x3, x4；新的非基变量x1, x5；
写出用非基变量表示基变量的表达式：
由
x3 8 x1 2 x2
x4
16
4
x1
→
x5
12
4x2
x3
2
x1
1 2
x5
x4 16 4 x1