bm 0 1 am ,m 1 amn m
j
0 0 j c j c i a ij
bi 其中： i a kj 0 a kj
单纯形法的计算步骤
例1.8 用单纯形法求下列线性规划的最优解
max Z 3 x1 4 x 2 2 x1 x 2 40 x1 3 x 2 30 x , x 0 1 2
A
0
E
| 5
| 6
| 7
| 8
| 9
x1
图解法
9— 8—
目标函数 Max Z = 2x1 + 3x2
约束条件 x1 + 2x2 8
4x1 16 4x2 12 x1、 x2 0
x2
7—
6— 5—
4x1 16
C 4 x2 16
4 —B
3— 2— 1—
D
| 1 | 2 | 3 | 4
4—
3— 2— 1— 0
x1
图解法
9— 8—
目标函数 Max Z = 2x1 + 3x2
约束条件 x1 + 2x2 8
4x1 16 4x2 12 x1、 x2 0
x2
7—
6— 5—
4x1 16 4 x2 12 x1 + 2x2 8
4—
3— 2— 1— 0
可行域
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
x2
X1 + 1.9X2 = 11.4 (≤)
8=5X1+4X2 此点是唯一最优解 （ 0， 2）
D
43=5X1+4X2
可行域
max Z
min Z
X1 + 1.9X2 = 3.8(≥)
X1 - 1.9X2 = 3.8 (≤)
o
L0： 0=5X1+4X2
x1
图解法---无穷多最优解
max Z=3X1+5.7X2
图解法
线性规划问题的求解方法 一般有 两种方法 两个变量、直角坐标 三个变量、立体坐标 适用于任意变量、但必需将 一般形式变成标准形式
图解法
单纯形法
下面我们分析一下简单的情况—— 只有两个决策 变量的线性规划问题，这时可以通过图解的方法来 求解。图解法具有简单、直观、便于初学者窥探线 性规划基本原理和几何意义等优点。
② 确定换出变量。根据下式计算并选择θ ，选最小的θ对应基
单纯形法的计算步骤
③
用换入变量xk替换基变量中的换出变量，得到一个新的基。 对应新的基可以找出一个新的基可行解，并相应地可以画出 一个新的单纯形表。
5）重复3）、4）步直到计算结束为止。
单纯形法的计算步骤
换入列
将3化为1
cj cB 0 0 0 基变量 x3 b 40 30 3 x1 2 1 3 x3 4 x2 1 3 4 0 x3 1 0 0
4
2
max Z
min Z
x1+x2=4(≥)
无界解(无最优解)
x1+3x2=6(≥)
2
4
6
x1
x ---无可行解 图解法
2
50
例1.7
40
max Z=3x1+4x2
2 x 1 x 2 40 x 1 1.5 x 2 30 x 1 x 2 50 x 1 0, x 2 0
bi /ai2，ai2>0
0 x4 0 1 0 θi
j j
x4
40 10
换 出 行
乘 以 1/3 后 得 到
4
x2
x1
30 10
18 4
3 4
j
x2
5/3 1/3 5/3 1 0 0
0 1 0 0 1 0
1 0 0 3/5 －1/5 －1
－1/3 1/3 －4/3 －1/5 2/5 －1
18 30
4 —B
3— 2— 1—
最优解 (4, 2)
D
x1 + 2x2 8
| 6 | 7 | 8 | 9 | 4
A
0
| 1
| 2
| 3
E
| 5
x1
图解法求解步骤
1.由全部约束条件作图求出可行域； 2.作目标函数等值线，确定使目标函数 最优的移动方向； 3.平移目标函数的等值线，找出最优点 ，算出最优值。
单纯形法的计算步骤
例1.9 用单纯形法求解
max Z x 1 2 x 2 x 3 2 x 1 3 x 2 2 x 3 15 1 s .t x 1 x 2 5 x 3 20 3 x 1、 x 2、 x 3 0
解：将数学模型化为标准形式：
① 确定换入基的变量。选择 j 0 ，对应的变量xj作为换入变
量，当有一个以上检验数大于0时，一般选择最大的一个检 验数，即： k max{ j | j 0} ，其对应的xk作为换入变 量。 变量作为换出变量。 bi L min a ik 0 a ik
s.t.
X1 + 1.9X2 ≥ 3.8 X1 - 1.9X2 ≤ 3.8 X1 + 1.9X2 ≤11.4 X1 - 1.9X2 ≥ -3.8 X 1 ，X 2 ≥ 0
X1 - 1.9X2 = -3.8 (≥)
x2
4 = 2X1 + X2
X1 + 1.9X2 = 11.4(≤) 11 = 2X1 + X2
X1 - 1.9X2 = -3.8(≥)
x2
X1 + 1.9X2 = 11.4 (≤)
（3.8，4）
D
max Z
蓝色线段上的所有点都是最 优解这种情形为有无穷多最 优解，但是最优目标函数值 max Z=34.2是唯一的。
可行域
（7.6，2）
34.2 = 3X1+5.7X2
X1 + 1.9X2 = 3.8(≥)
（由图解法得到的启示）




可行域是有界或无界的凸多边形。 若线性规划问题存在最优解，它一定可以在可 行域的顶点得到。 若两个顶点同时得到最优解，则其连线上的所 有点都是最优解。 解题思路：找出凸集的顶点，计算其目标函数 值，比较即得。
练习：
设
z 2x y
式中变量 x, y 满足下列条件 y
cj cB 0 基 x3 b 40 3 x1 2 4 x2 1 0 x3 1 0 x4 0
θi
0
j
x4
30
1
3
3
4
0
0
1
0
检验数
1 c1 (c3a11 c4a21 ) 3 (0 2 0 1) 3
单纯形法的计算步骤
3）进行最优性检验 如果表中所有检验数 0 ，则表中的基可行解就是问题 j 的最优解，计算停止。否则继续下一步。 4）从一个基可行解转换到另一个目标值更大的基可行解， 列出新的单纯形表
解：1）将问题化为标准型，加入松驰变量x3、x4则标准型为:
max Z 3 x 1 4 x 2 2 x 1 x 2 x 3 40 x 1 3 x 2 x 4 30 x , x , x , x 0 1 2 3 4
单纯形法的计算步骤
2）求出线性规划的初始基可行解，列出初始单纯形表。
求 z 的最大值和最小值
zmax 12 zmin 3
3x+5y-25=0
O
l0
l1
l
x
l2
单纯形法基本原理
定理1：若线性规划问题存在可行解，则该问题的可行域是 凸集。 定理2：线性规划问题的基可行解X对应可行域(凸集)的顶 点。 定理3：若问题存在最优解，一定存在一个基可行解是最优 解。（或在某个顶点取得）
x1
图解法
9— 8—
目标函数 Max Z = 2x1 + 3x2
约束条件 x1 + 2x2 8
4x1 16 4x2 12 x1、 x2 0
x2
7—
6— 5—
4x1 16
C 4 x2 16 x1 + 2x2 8
4 —B
3— 2— 1—
D
可行域
| 1 | 2 | 3 | 4
17.2 = 2X1 + X2
20 = 2X1 + X2
此点是唯一最优解， 且最优目标函数值 max Z=17.2
D
max Z
可行域
（7.6，2）
X1 + 1.9X2 = 3.8(≥)
min Z
o
Lo： 0 = 2X1 + X2
X1 - 1.9X2 = 3.8(≤)
x1
图解法---唯一最优解
min Z=5X1+4X2
线 性 规 划 问 题 的 几 何 意 义
设 k是 n维欧氏空间的一点集， 对 X
（ 1）
K， X
（ 2）
K
连线上的一切点 αX （ 1 α ） X K， （ 0 α 1 ），则 K为凸集。
（ 1） （ 2）
凸集
凹集
顶点: 若K是凸集，X∈K；若X不能用不同
的两点的线性组合表示为：
单纯形法的计算步骤
单纯形法的思路 找出一个初始可行解
是否最优 循 环 否
是
最优解 结束
转移到另一个基本可行解 （找出更大的目标函数值） 核心是：变量迭代
单纯形法的计算步骤
单纯形表
cj
cB
XB
c1 cm
x1 xm
c1 c m c m 1 c n i b x1 x m x m 1 x n 1 0 a1,m 1 a1n 1 b 1