当前位置：文档之家 › 第一章-3-单纯形法-运筹学

第一章-3-单纯形法-运筹学

  • 格式：ppt
  • 大小：1.88 MB
  • 文档页数：39

下载文档原格式

  / 39

合集下载

运筹学-第一章-单纯形法基本原理

运筹学-第一章-单纯形法基本原理

初始基本可行解：
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,取值无限，
第1章-线性规划及单纯形法-课件(1)

第1章-线性规划及单纯形法-课件(1)


✓ x1、 x2 0
IБайду номын сангаас
设备
1
原材料 A 4
原材料 B 0
利润
2
II 资源限量
2 8 台时
0
16kg
4
12kg
3
第一章 线性规划及单纯形法 运筹学
该计划的数学模型
✓ 目标函数 ✓ 约束条件
Max Z = 2x1 + 3x2
x1 + 2x2 8 4x1 16 4x2 12 x1、 x2 0
x1
✓ 美国航空公司关于哪架飞机用于哪一航班和哪些 机组人员被安排于哪架飞机的决策。
✓ 美国国防部关于如何从现有的一些基地向海湾运 送海湾战争所需要的人员和物资的决策。
✓ ……
第一章 线性规划及单纯形法 运筹学
二、线性规划问题的数学模型
✓ 1、一般形式 ✓ 2、简写形式 ✓ 3、表格形式 ✓ 4、向量形式 ✓ 5、矩阵形式
1、唯一最优解
max Z 2 x 1 3 x 2
2 x 1 2 x 2 12 ⑴
x1 4 x1
2 x2
8 16
⑵ ⑶
4 x 2 12 ⑷
x 1 0 , x 2 0
1 234 56
x2
⑶ ⑷
(4，2)
0 1 234 5678
x1
⑵
⑴
✓最优解：x1 = 4,x2 = 2，有唯一最优解Z=14。
第一章 线性规划及单纯形法 运筹学
三、线性规划模型的标准形式
✓ 1、标准形式 ✓ 2、转换方式
第一章 线性规划及单纯形法 运筹学
1、标准形式
maZx cjxj
xj
aijxj 0
bi
运筹学---单纯形法

运筹学---单纯形法

运筹学---单纯形法单纯形法是一种解线性规划问题的有效算法。

在这个问题中，我们寻找一组决策变量，以便最大化或最小化一个线性目标函数，同时满足一系列线性限制条件。

单纯形法通过暴力搜索可行解并逐步优化目标函数来求解该问题。

单纯形法的主要思想是从一个初始可行解开始，并通过迭代来逐步移动到更优的解。

在每一步迭代中，算法将当前解移动到一个相邻的顶点，直到找到一个优于当前解的顶点。

具体操作包括选择一个非基变量，并将其作为入基变量，同时选择一个基变量并将其作为出基变量。

新的基变量将替换原来的非基变量，并且目标函数的值将被更新。

关键是如何选择入基变量和出基变量。

为此，单纯形法使用一个称为单纯形表的矩阵来跟踪线性规划问题的状态。

单纯形表包含目标函数系数，限制条件系数，决策变量的当前值以及对角线上的单位矩阵。

通过适当地操作这个表，可以确定要移动到哪个相邻顶点，并相应地更新解和目标函数的值。

一般来说，单纯形法需要在指数时间内解决线性规划问题，因为需要遍历所有可能的可行解。

但是，在实际应用中，单纯形法往往比其他算法更快和更有效。

此外，在使用单纯形法时，需要注意陷入无限循环或者找不到一个可行解的可能性。

单纯形法的主要优点是：它是一种简单而直观的求解线性规划问题的方法；它易于实现，并且在许多情况下可以很快地求解问题。

它还可以用于解决大规模问题，包括具有成千上万个变量和限制条件的问题。

在实际应用中，单纯形法经常与其他算法结合使用，例如内点法或分支定界法。

这些方法可以提供更好的性能和结果。

但是，在许多情况下，单纯形法仍然是解决线性规划问题的首选算法。

在总体上，单纯形法是一种强大而灵活的工具，可以帮助研究人员和决策者在面对复杂的决策问题时做出明智的选择，并实现最大的效益。

运筹学1-3(1)

运筹学1-3(1)


是可行域的顶点⇒ ②．证 X 是可行域的顶点⇒X 是基可行解 （等价于证：X 不是基可行解⇒ X 不是可行域的顶点） 设 X 不是基可行解
s
∑P x
j =1 j
j
=b
(s ≤ n) s
存在不全为 0 的一组实数α 1 ,L ,α s ，使
∑α
j =1 s
s
j
Pj = 0
s
用一正数θ乘以上式与前式相加减可得： 用一正数θ乘以上式与前式相加减可得：
i i =1 i =1 k k
因此 C X =C ∑ α i X = ∑ α i CX i
0
i i =1 i =1 k k
在所有的顶点中必然能找到某一个顶点 Xm，使得 CXm 是所有 CXi 中 最大者。并且将 Xm 代替上式中的所有 Xi，就得到
∑α i CX ≤
i i =1
k
α i CX m = C Xm ∑
《运筹学》——刘东南
练习
X1和X2 (X1 ≠X2)为某一线性规划问题的最优 证明该线性规划问题有无穷多个最优解。 解，证明该线性规划问题有无穷多个最优解。
《运筹学》——刘东南
∑( x
j =1
j
+ θα j )Pj = b ,
∑( x
j =1
j
− θα j )Pj = b
即可得 X1பைடு நூலகம்( x1 + θα 1 , x2 + θα 2 ,L , x s + θα s ,0 ,L ,0 ) X2=( x1 − θα 1 , x2 − θα 2 ,L , x s − θα s ,0 ,L ,0 ) X1≠ X2，只要θ充分小，X1、X2 都为可行解， 只要θ充分小， 都为可行解，
运筹学线性规划与单纯形法

运筹学线性规划与单纯形法


整理课件
16
Max Z= x1-2x2+3x3' -3x3" + 0x4 +0x5 s.t. x1+x2+ x3' - x3" +x4 =7
x1-x2+ x3' - x3" -x5=2
-3x1+x2+2x3' -2x3" =5 x1, x2,x3',x3", x4,x5 0
第一节小结：建立模型；三个组成要素；四种形式； 化为标准形（4个条件5点）
.
9x1+4x2 ≤ 360
90 80 60 40 20
4x1+5x2 ≤200
B C
HI G
Z=70x1+120x2 3x1+10x2 ≤300
0
20 D40 E 60
80 1F00 x1
整理课件
30
二、解的几种可能情况
1．唯一最优解。目标函数直线与凸多边形只有 一个切点； 2．无穷多最优解，目标函数图形与某个约束条 件平行。 3．无界解（无最优解）----可行域无界。一般是 漏了一些约束条件。 4．无可行解----可行域为空。
Ⅰ
Ⅱ 计划期可用能力
2
2
12
1
2
8
4
0
16
0
4
12
2
3
问：应如何安排生产计划，才能使总利润最大？
整理课件
3
解：用数学的语言进行描述:
1.决策变量：设产品I、II的产量分别为 x1、x2 2.目标函数：问题要求获取利润最大，该公司获取
利润为2 x1 + 3 x2，令z = 2 x1 + 3 x2，则max z = 2 x1 + 3 x2， max z 是该公司获取利润的目标 值，它是变量x1、 x2的函数，称为目标函数。
运筹学第1章：线性规划问题及单纯型解法

运筹学第1章：线性规划问题及单纯型解法


原料甲 原料乙 最低含量 VA 0.5 0.5 2 VB1 1.0 0.3 3 VB2 0.2 0.6 1.2 VD 0.5 0.2 2 0.3 0.5 单价
分别代表每粒胶丸中甲, 设 x1, x2分别代表每粒胶丸中甲, 乙两种原料的用量
5
例3,合理下料问题 , 分别代表采用切割方案1~8的套数, 的套数, 设 xj 分别代表采用切割方案 的套数
19
( f(x
)= 3
6
1.2.2 单纯型法的基本思路
确定初试基础可行解
检查是否为 最优解? 最优解?
是
求最优解的目标函数值
否 确定改善方向
求新的基础可行解
20
1.2.3 单纯型表及其格式
IV CB III XB II x1 b c1 a11 a21 c1′′= cn+1 xn+1 b1 c2′′= cn+2 xn+2 b2 x2 … xn c2 … cn a12 … a1n a22 … a2n I xn+1 cn+1 1 0 0 zn+1 xn+2 cn+2 0 1 0 zn+2 … … … … … … xn+m cn+m 0 0 1 zn+m
OBJ : max f ( x) = 6x1 + 4x2 2x1 + x2 ≤ 10 铜资源约束 x1 + x2 ≤ 8 铅资源约束 s.t. x2 ≤ 7 产量约束 x1, x2 ≥ 0 产量不允许为负值 最优解: x1 = 2, x2 = 6, max f ( x) = 36.
4
例2,配料问题(min, ≥) ,配料问题(
2 max 1 O 1 2 3 4 D 5 6 7 H 8
运筹学——3.单纯形矩阵描述与改进单纯形法

运筹学——3.单纯形矩阵描述与改进单纯形法


32
计算B的逆矩阵

（6）计算RHS
1 / 2 8 2 1 1 B1 b 1 0 16 16 1 / 4 12 3
23
第2节 改进单纯形法
第1步计算结束后的结果
基 B1 P3 , P4 , P2 ; 基变量 X B1 x3 , x4 , x2 ;
22
（5）计算非基变量的系数矩阵
1 / 2 1 1 1 1 N1 4 B1 N1 1 0 4 1 1 / 4 1 1 1 / 2 4 0 1/ 4
B2 1b i 1 min 1 B2 P5 0 B P 2 5 i 2 8 3 min , , 4 对应x4 1/ 2 2 1/ 4
31
基变换：
新的基
B3 P , P5 , P2 ; 1 换入变量x5 的系数向量是 1 0 1 / 2 0 1 / 2 1 B2 P5 4 1 2 0 2 主元素 0 0 1 / 4 1 1 / 4
确定换出变量
B11b i 1 min 1 B1 P 0 1 B P 1 1 i 2 16 3 min , , 2 对应x3 1 4 0


26
由此得到新的基
B2 P , P4 , P2 1 1 1 B1 P 4 1 0 1 1 0 0 2 4 E2 4 1 0 0 0 0 1 1 0 0 1 0 1/ 2 1 1 B2 E2 B1 4 1 0 0 1 0 0 0 1 0 0 1/ 4 1 0 1/ 2 4 1 2 0 0 1/ 4
运筹学第一章

运筹学第一章

OR1
30
1.1.3解的概念
概念： 1、可行解：满足所有约束条件的解。 2、可行域：即可行解的集合。所有约束条件的交 集，也就是各半平面的公共部分。满足所有约 束条件的解的集合，称为可行域。 3、凸集：集合内任意两点的连线上的点均属于这 个集合。如：实心球、三角形。线性规划的可 行域是凸集。
OR1
OR1
27
线性规划图解法例题
（无界解）
max z x 2 y x y 1 2 x 4 y 3 x 0, y 0
OR1
28
线性规划图解法例题
（无解）
min z x 2 y x y 2 2 x 4 y 3 x 0, y 0
请问该 医院至 少需要 多少名 护士？
5
例题2建模
目标函数：min Z=x1+x2+x3+x4+x5+x6 约束条件： x1+x2 ≥70
x2+x3 ≥60 x3+x4 ≥ 50 x4+x5 ≥20 x5+x6 ≥30 非负性约束：xj ≥0,j=1,2,…6
OR1
6
例题3：运输问题
三个加工棉花的加工厂，并且有三个仓库供应棉花，各 供应点到各工厂的单位运费以及各点的供应量与需求量 分别如下表所示：问如何运输才能使总的运费最小？
OR1
14
总
结
从以上 5 个例子可以看出，它们都属于优化问题，它们 的共同特征： 1 、每个问题都用一组决策变量表示某一方案；这组决 策变量的值就代表一个具体方案，一般这些变量取值是 非负的。 2 、存在一定的约束条件，这些约束条件可以用一组线 性等式或线性不等式来表示。 3 、都有一个要求达到的目标，它可用决策变量的线性 函数（称为目标函数）来表示。按问题的不同，要求目 标函数实现最大化或最小化。 满足以上三个条件的数学模型称为线性规划的数学模型。
运筹学第一章第3节

运筹学第一章第3节


山东建筑大学 管理工程学院
运 筹பைடு நூலகம்学
定理2 线性规划问题的基可行解X对应线性规
划问题可行域（凸集）的顶点。
定理3 若线性规划问题有最优解，一定存在一
个基可行解是最优解。
山东建筑大学 管理工程学院
运 筹 学
启示
线性规划问题若存在最优解，一定可以在
基可行解中找到。
单纯形法的基本思路是先找到一个基可行
代入目标函数得到
z 2x1 3 / 4x5 9
得到另一个基可行解X(1)=(0,3,2,16,0)T ,z=9
山东建筑大学 管理工程学院
运 筹 学
从目标函数的表达式中可以看到，非基变
量x1的系数是正的，说明目标函数值还可以增大
再用上述方法，确定换入、换出变量，继续迭
代。
山东建筑大学 管理工程学院
运 筹 学
x2取何值时，才能满足非负要求
从上式中可以看出，选择 x2=min(8/2,-,12/4)=3，
这就决定用x2去替换x5。
以上数学描述说明：每生产一件产品Ⅱ，需要 用掉各种资源数为(2，0，4)。由这些资源中的薄弱 环节，就确定了产品Ⅱ的产量。
山东建筑大学 管理工程学院
运 筹 学
1 x3 2 x1 2 x5 x4 16 4 x1 1 x2 3 x5 4
山东建筑大学 管理工程学院
运 筹 学
顶点：凸集C中满足下列条件的点X称为顶点：
如果C中不存在任何两个不同的点X1、X2，使得 X成为这两个点连线上的一个点。
山东建筑大学 管理工程学院
运 筹 学
3-1几个基本定理 定理1 若线性规划问题存在可行解，则该问题的
运筹学基础及应用第五版胡运权第一章

运筹学基础及应用第五版胡运权第一章

问题的提出 某企业计划生产Ⅰ、Ⅱ两种产品。这两种产品都要分别在A、B、C、D四种不同设备上加工。生产每件产品Ⅰ需占用各设备分别为2、1、4、0h，生产每件产品Ⅱ，需占用各设备分别为2、2、0、4h。已知各设备计划期内用于生产这两种产品的能力分别为12、8、16、12h，又知每生产一件产品Ⅰ企业能获得2元利润，每生产一件产品Ⅱ企业能获得3元利润，问企业应安排生产两种产品各多少件，使总的利润收入为最大。
xi 0
aij
aLj
xL 0
i
∴ P1 , P2,······,PL-1, PL+1,······ Pm, Pj 线性无关。
∴ X1 也为基本可行解。
四、最优性检验和解的判别
令
，其中 随基的改变而改变
X1 = (x1 0- a1j ,x2 0- a2j ,···,xm 0- amj ,0,···,,···,0)T
必要性：X非基本可行解 X非凸集顶点 不失一般性，设X=(x1,x2,······,xm,0,0,······,0)T，为非基本可行解， ∵ X为可行解，
证：等价于 X非基本可行解X非凸集顶点
又 X是非基本可行解， ∴ P1,P2,······,Pm线性相关，即有 1P1+2P2+······+mPm=0， 其中1，2，······，m不全为0，两端同乘≠0，得 1P1+2P2+······+mPm=0，······（2）
∵ >0, 1->0 ，当xj=0， 必有yj=zj=0
∴
pjyj =
j=1
n
pjyj=b ······(1)
j=1
r
pjzj =
j=1
n
pjzj=b ······(2)
运筹学第1章

运筹学第1章

18
运筹学解决问题的过程
1）提出问题：认清问题。 2）寻求可行方案：建模、求解。 3）确定评估目标及方案的标准或方 法、途径。 4）评估各个方案：解的检验、灵敏 性分析等。
19
运筹学解决问题的过程
5）选择最优方案：决策。 6）方案实施：回到实践中。 7）后评估：考察问题是否得到完 满解决。
1）2）3）形成问题；4）5）分析 问题：定性分析与定量分析相结合，构 成决策。
10
运筹学的产生和发展
战后这些研究成果被应用到生产、 经济领域，并得到迅速发展——有关理 论和方法的研究、实践不断深入。
1947年美国数学家丹捷格(G.B.Dantzig）
提出了求解线性规划的有效方法——单 纯形法。
11
运筹学的产生和发展
数学对运筹学的作用——是有 关理论和方法的研究基础，是建立 运筹学模型的工具。
20
如何学习运筹学课程
学习运筹学要把重点放在分 析、理解有关的概念、思路上。 在自学过程中，应该多向自己提 问，例如一个方法的实质是什么， 为什么这样进行，怎么进行等。
自学时要掌握三个重要环节：
21
如何学习运筹学课程
1.认真阅读教材和参考资料， 以指定教材为主，同时参考其他有 关书籍。一般每一本运筹学教材都 有自己的特点，但是基本原理、概 念都是一致的。注意主从，参考资 料会帮助你开阔思路，使学习深入。 但是，把时间过多放在参考资料上， 会导致思路分散，不利于学好。
2
运筹学
1.绪论 2.线性规划建模及单纯形法 3.线性规划问题的对偶与灵敏度分析 4.运输问题 5.动态规划 6.排队论 7.决策分析
8.图与网络分析
第一章 绪 论
4
运筹学概况简述

运筹学第1章线性规划及单纯形法复习题


max (min)
Z = CX
AX ≤ ( = , ≥ ) b X ≥ 0
3、线性规划的标准形式 、
ma0
4、线性规划问题的解 、 （一）求解方法
一 般 有 两种方法 图 解 法 单纯形法 两个变量、 两个变量、直角坐标 三个变量、 三个变量、立体坐标
适用于任意多个变量、 适用于任意多个变量、但需将 一般形式变成标准形式
（二）线性规划问题的解
1、解的概念 可行解：满足约束条件② 的解为可行解。 ⑴ 可行解：满足约束条件②、③的解为可行解。 所有解的集合为可行解的集或可行域。 所有解的集合为可行解的集或可行域。 最优解： 达到最大值的可行解。 ⑵ 最优解：使目标函数①达到最大值的可行解。 ⑶ 基：B是矩阵A中m×m阶非奇异子矩阵 是矩阵A ≠0）， ），则 是一个基。 （∣B∣≠0），则B是一个基。
§2 图 解 法
例一、 例一、 max
Z = 2 x 2 x 2 x 4 x
2 2 1
+ 3 x
2
2 x1 + x + 1 4 x1 x1 ≥
≤ 12 ≤ 8 ≤ 16 ≤ 12
2
⑴ ⑵ ⑶ ⑷
2
0, x
≥ 0
max
Z = 2 x1 + 3 x 2 x 2 x
2 2
当xj=0时, 必有 j=zj=0, 因此 时 必有y
∑P x = ∑P y = ∑P z
j =1
r
r
r
r
j
j
j =1
j
j
j =1
j
j
=b
∑(y
j =1
j
− z j ) Pj = 0

运筹学第一章

第一章、 线性规划和单纯形法1.1 线性规划的概念一、线性规划问题的导出1．(引例) 配比问题——用浓度为45%和92%的硫酸配置100t 浓度为80%的硫酸。

取45%和92%的硫酸分别为x1和x2t,则有： 求解二元一次方程组得解。

目的相同，但有5种不同浓度的硫酸可选（30%，45%，73%，85%，92%）会出现什么情况？设取这5种硫酸分别为 x1、x2、x3、x4、x5 t, 则有： ⎩⎨⎧⨯=++++=++++1008.092.085.073.045.03.01005432154321x x x x x x x x x x 请问有多少种配比方案？为什么？哪一种方案最好？假设5种硫酸价格分别为：400，700，1400，1900，2500元/t ，则有：2.生产计划问题如何制定生产计划，使三种产品总利润最大？考虑问题：⎩⎨⎧⨯=+=+1008.092.045.01002121x x x x ⎪⎩⎪⎨⎧=≥⨯=++++=++++++++=5,,2,1,01008.092.085.073.045.03.0100..250019001400700400543215432154321 j x x x x x x x x x x x t s x x x x x MinZ j（1）何为生产计划？（2）总利润如何描述？（3）还要考虑什么因素？（4）有什么需要注意的地方（技巧）？（5）最终得到的数学模型是什么？二、线性规划的定义和数学描述（模型）1．定义：对于求取一组变量xj (j =1,2,......,n)，使之既满足线性约束条件，又使具有线性表达式的目标函数取得极大值或极小值的一类最优化问题称为线性规划问题，简称线性规划。

2.配比问题和生产计划问题的线性规划模型的特点：用一组未知变量表示要求的方案，这组未知变量称为决策变量；存在一定的限制条件，且为线性表达式；有一个目标要求（最大化，当然也可以是最小化），目标表示为未知变量的线性表达式，称之为目标函数； 对决策变量有非负要求。

运筹学 线性规划 图解法


x2 4x1=16
x1+2x2=8
Q4
Q3
3
•Q2(4,2) 4x2=12
Q1
0
4
x1
2x1+3x2=0
2.试算法
最优解在顶点达到：
O点：X1=0, X2=0, Z=0 Q1: X1=4, X2=0, Z=8 Q2: X1=4, X2=2, Z=14 Q3: X1=2, X2=3, Z=10 Q4: X1=0, X2=3, Z=6
x2
X1=10/3,x2 =4/3
Z=12.67
0
x1
线性代数基础知识补充与回顾
一、克莱姆规则
含有n个未知数x1,x2,…xn的n个线性方程的方程 组如下式所示：
a11x1 a12x2 ..... a1nxn b1 a21x1 a22x2 ..... a2nxn b2 ...................................... an1x1 an2x2 ..... annxn bn
克莱姆法则 如果上述线性方程组的系数行列式不等于零，即有：
a11 a1n
D
0
an1 ann
那么，上述方程组有唯一解：
x1D D 1,x2D D 2,........xn .. ..D .D .n .
其中Dj（j=1，2，……n）是把系数行列式D中的第j 列的元素用方程组的常数项代替后得到的n阶行列式.
(a)可行域有界 唯一最优解
(b)可行域有界 多个最优解
(c)可行域无界 唯一最优解
(d)可行域无界 多个最优解
(e)可行域无界 目标函数无界
(f)可行域为空集 无可行解
课堂作业：用图解法求解下列问题
某厂利用A、B两种原料，生产甲、乙两种产品，有关数据如下：
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

a1n
M


(
A1 ,
A2
,
..,
An
),
amn
可行域 D x Rn | Ax b, x 0 .
R( A) m ( n),
假设已找到一个非退化的基本可行解 x ，令其所对应的一个基为
B. 不失一般性，设 A (B, N ) ， x (xBT , xNT )T ，则有





xm
0
…
0
…
1 … … am,m1
a mk
a mn
bm
完整的单纯形表
将 目 标 函 数 z 看 成 变 量 ， 由 于 z cBB1b T x 等 价 于

z (cBTB1N cNT )xN cB b ，则将其系数及右端项添加到单纯形
表的最上面作为第 0 行，同时加上 z 对应的列，所得到新的
值
先找到一个初始基本可行 解，判断它是否最优，如果不 是，就找一个更好的基本可行 解，再进行判断.如此迭代下
去，直至找到最优的基本可行
解，或者判定该问题无界.
求新的 基本可行解
单纯形法是一种迭代的算法.
单纯形法的关键步骤
• 初始基本可行解的确定 • 最优性检验与判别 • 基变换
如何得到第一个 基本可行解?
z
x1 ... … 0 ... ... … … ... … …
b1


xr ... … 1 … ... … … ark … …
br


xm ... … 0 … ... … … ... … …
bm
x1 … xr … xm xm+1 … xk … xn
0
…
(3.2) (典式)
若 b 0 ，则(3.2)对应基本可行解 x (b, 0)T .
记 cT

(cBT
,
c
T N
)
，则目标函数
z
cTx
cBT xB

c
T N
x
N
cBT (b B1NxN ) cNT xN
cBT b (cBT B1N cNT ) xN
(3.3)
设 > 0 为任一正数，考察向量 x d .
由于 Ax d Ax Ad b,并且 x d 0 ，因此
x d 是一个可行解.

c x d c x cBT
cNT


B 1 0
Ak


ek

r
…
0

m1
…
0
…
n
z
br ark
k
xˆ1
... … ...
...
...
…
…
0
…
…
bi

br ark
aik


1
xˆk ... … ark … ... … … 1 … …
br a rk


xˆ m
... … ... … ...
…
…
br

br ark
ark

0;
(3)
xˆ k

0

br ark
(
0);
(4) xˆ j 0, 当 i m 1,..,k 1,k 1,..,n ,
可见 xˆ 0 ，它是可行解.
x1 … xr … xm xm+1 … xk … xn
0 … 0 … 0 m+1 … k … n
0
…
…
bm

br ark
amk
下面证明 xˆ 是基本可行解. 由定理 2.2，只需证明 xˆ 的正分量所对应的 A 中的列
向量线性无关.
由上述分析，xˆ 的正分量只可能出现在 xˆ1 , …, xˆr1 , xˆ k , xˆ r1 , …, xˆm 中.因此，若能证明列向量 A1, ..., Ar 1, Ak，
定理 3.1 若检验数向量 0 ，则对应的基本可行
解 x 为原问题的最优解.
（最优性准则）
证明：
由于 T 0 ，因此对任意一个可行解 x 0 ，其目标 函数值
z cT x z0 T x z0 cT x.
定理3.2：判定LP无界
定理 3.2 如果检验数向量 的第 k 个分量 k 0 ，
止；
Step 5 如果 Ak 0 ，则原问题无界，停止；
Step 6 Step 7
令r

argm
in

bi aik
| aik

0, i


1,2,...,m
；
以 Ak 替代 B 中的第 r 列，得到一个新的基 B，
转 Step 2.
2. 单纯形表
下面我们将单纯形法的全部计算过程放在在一个 类似增广矩阵的表格(即单纯形表)上进行.
可行解

x
移动到另一个“更好”的基本可行解

x
.
• 新旧基本可行解的差别在于原来的非基变量xk代
替原来的基变量xr而成为第r个基变量，而xr变为非
基变量.
• 整个过程称为换基，或为进行了一次迭代，称Ar 为退出基列，Ak为进入基列，而迭代前后相同的m-1 个列向量，称它们为相邻基.另外，称xr为离基变量， xk为进基变量.
假设当前的基 B A1, A2,L , Am ，将约束方程组 Ax b变
换为典式后的单纯形表为：
x1 … xr … xm xm1 … xk … xn RHS
x1
1
…
0
…
0
… … a1,m1
a1k
a1n
b1






xr
0
…
1
…
0
… a r ,m 1
a rk
… arn
br

的第 k 个分量 k 0 ，而其所对应的向量 Ak 至少有一个正分量，
则可以找到一个新的基本可行解 xˆ 使得 c xˆ c x .
证明： 只需要将 xˆ 找出来
设 A (B N ) ，且 m 1 k n.

令
d
ቤተ መጻሕፍቲ ባይዱ



Ak 0


ek
，其中
ek
为单位向量，则
由于 ark 0 ，因此，A1, ..., Am 线性相关，与它们是 x 的基
矛盾.
由定理 3.2 的证明，c xˆ c x k .由于 0， k 0 ，
故目标函数值 c xˆ c x .
定理3.3的几点说明：
• 定理3.3的证明过程实质上给出了如何从一个基本
单纯形表为：
z x1 … xr … xm xm1 … xk … xn RHS
z
1
0
…
0
…
0
… m1
k
… n
cBb
x1
0
1
…
0
…
0
… … a1,m1
a1k
a1n
b1





xr
0
0
…
1
…
0
… ar ,m1
a rk
… arn
br





xm
0
0
…
0
…
1 … … am,m1
Ar + 1, ..., Am 线性无关，则 xˆ 为基本可行解.
反证 假设它们线性相关，由于 A1, A2, …, Am 本来 是线性无关的（它们是 x 的基），这表明 Ak 可由 A1, ..., Ar 1, Ar + 1, ..., Am 线性表出.
设存在 m 1 个数 yi , i 1, ..., m, i r ，使得
min s.t.
z z0 T x
xB B1NxN b x0
称为基本可行
解 x 的检验数向
量，它的各个分量称 为检验数
(3.4)
1. 单纯形法的基本原理
定理 3.1（最优性准则） 如果检验数向量 0，
则基本可行解 x 为原问题的最优解.
定理 3.2 如果检验数向量 的第 k 个分量 k 0 ，
a mk
a mn
bm
目标函数值
给定基 B，由于
因此

Tx 0

T N

xBT 0


0
，



z0 cB b T x cB b ，
即单纯形表右上角的
cB

b
就是当前基本可行解

x
的目标
函数值.
实际使用的单纯形表
在对单纯形表进行行初等变换时，变量 z 所对应的 列各元素不会改变，因此可将表格中变量 z 的列去掉， 得到新的单纯形表：

令

m
in

bi aik
_
| aik

0,
1
i

m


br ark
,由于
x


b 0

是
非退化的，可知 b 0 ，因此 0.



故
(1) xi bi aik ( 0), 当 i 1,..,r 1,r 1,..,m ;
(2)