运筹学课件制作,北京理工大学 吴祈宗等
2
第二章线性规划建模及单纯形法本章内容重点
线性规划模型与解的主要概念
线性规划的单纯形法，线性规划多解分析
线性规划应用 ——建模
3
1.线性规划的概念例 2.1:某工厂拥有 A,B,C三种类型的设备,生产甲,乙两种产品 。 每件产品在生产中需要占用的设备机时数,每件产品可以获得的利润以及三种设备可利用的时数如下表所示：
产品甲 产品乙 设备能力
（ h）
设备 A 3 2 65
设备 B 2 1 40
设备 C 0 3 75
利润（元 /件） 1500 2500
4
问题：工厂应如何安排生产可获得最大的总利润？
解：设变量 xi为第 i种 （ 甲,乙 ） 产品的生产件数 （ i＝ 1,2） 。 根据题意,
我们知道两种产品的生产受到设备能力
（ 机时数 ） 的限制 。 对设备 A,两种产品生产所占用的机时数不能超过 65,于是我们可以得到不等式,3 x1 + 2 x2 ≤ 65；
对设备 B,两种产品生产所占用的机时数不能超过 40,于是我们可以得到不等式,2 x1 + x2 ≤ 40；
1.线性规划的概念
5
对设备 C,两种产品生产所占用的机时数不能超过 75,于是我们可以得到不等式,3x2 ≤ 75 ；另外,产品数不可能为负,即 x1,x2 ≥ 0。 同时,我们有一个追求目标,即获取最大利润 。 于是可写出目标函数 z为相应的生产计划可以获得的总利润,z=1500x1+2500x2 。 综合上述讨论,在加工时间以及利润与产品产量成线性关系的假设下,把目标函数和约束条件放在一起,可以建立如下的线性规划模型：
1.线性规划的概念
6
目标函数 Max z =1500x1+2500x2
约束条件 s.t,3x1+2x2≤ 65
2x1+x2≤ 40
3x2≤ 75
x1,x2 ≥ 0
1.线性规划的概念
7
这是一个典型的利润最大化的生产计划问题 。 其中,,Max”是英文单词,Maximize”的缩写,含义为,最大化,；,s.t.”是,subject to”的缩写,表示,满足于 ……,。 因此,上述模型的含义是：在给定条件限制下,
求使目标函数 z达到最大的 x1,x2 的取值 。
1.线性规划的概念
8
一般形式
目标函数：
Max(Min)z = c1x1 + c2x2 + … + cnxn
约束条件：
a11x1+a12x2+… +a1nxn≤( =,≥ ) b1
a21x1+a22x2+… +a2nxn≤( =,≥ ) b2..
,
am1x1+am2x2 +… +amnxn≤( =,≥ ) bm
x1,x2,…,xn ≥ 0
1.线性规划的概念
9
标准形式
目标函数：
Max z = c1x1 + c2x2 + … + cnxn
约束条件：
a11x1 + a12x2 + … + a1nxn = b1
a21x1 + a22x2 + … + a2nxn = b2..
.
am1x1 + am2x2 + … + amnxn = bm
x1,x2,…,xn ≥ 0
1.线性规划的概念
10
可以看出,线性规划的标准形式有如下四个特点,目标最大化,约束为等式,决策变量均非负,右端项非负 。
对于各种非标准形式的线性规划问题,我们总可以通过以下变换,将其转化为标准形式,
1.线性规划的概念
11
1.极小化目标函数的问题：
设目标函数为
Min f = c1x1 + c2x2 + … + cnxn
则可以令 z ＝ -f,该极小化问题与下面的极大化问题有相同的最优解,即
Max z = -c1x1 - c2x2 - … - cnxn
但必须注意,尽管以上两个问题的最优解相同,但他们最优解的目标函数值却相差一个符号,即
Min f ＝ - Max z
1.线性规划的概念
12
2,约束条件不是等式的问题：
设约束条件为
ai1 x1+ai2 x2+ … +ain xn ≤ bi
可以引进一个新的变量 s,使它等于约束右边与左边之差
s=bi–(ai1 x1 + ai2 x2 + … + ain xn )
显然,s 也具有非负约束,即 s≥ 0，
这时新的约束条件成为
ai1 x1+ai2 x2+ … +ain xn+s = bi
1.线性规划的概念
13
当约束条件为
ai1 x1+ai2 x2+ … +ain xn ≥ bi
时,类似地令
s=(ai1 x1+ai2 x2+ … +ain xn)- bi
显然,s 也具有非负约束,即 s≥ 0，
这时新的约束条件成为
ai1 x1+ai2 x2+ … +ain xn-s = bi
1.线性规划的概念
14
为了使约束由不等式成为等式而引进的变量 s称为,松弛变量,。
如果原问题中有若干个非等式约束,
则将其转化为标准形式时,必须对各个约束引进不同的松弛变量 。
1.线性规划的概念
15
例 2.2：将以下线性规划问题转化为标准形式
Min f = 3.6 x1 - 5.2 x2 + 1.8 x3
s,t,2.3 x1 + 5.2 x2 - 6.1 x3 ≤ 15.7
4.1 x1 + 3.3 x3 ≥ 8.9
x1 + x2 + x3 = 38
x1,x2,x3 ≥ 0
1.线性规划的概念解：首先,将目标函数转换成极大化,
令 z= -f = -3.6x1+5.2x2-1.8x3
16
其次考虑约束,有 2个不等式约束,引进松弛变量 x4,x5 ≥ 0。
于是,我们可以得到以下标准形式的线性规划问题：
Max z = - 3.6 x1 + 5.2 x2 - 1.8 x3
s.t,2.3x1+5.2x2-6.1x3+x4= 15.7
4.1x1+3.3x3-x5= 8.9
x1+x2+x3= 38
x1,x2,x3,x4,x5 ≥ 0
1.线性规划的概念
17
3,变量无符号限制的问题：
在标准形式中,必须每一个变量均有非负约束 。 当某一个变量 xj没有非负约束时,可以令
xj = xj’- xj”
其中
xj’≥ 0,xj”≥ 0
即用两个非负变量之差来表示一个无符号限制的变量,当然 xj的符号取决于 xj’和 xj”的大小 。
1.线性规划的概念
18
4.右端项有负值的问题：
在标准形式中,要求右端项必须每一个分量非负 。 当某一个右端项系数为负时,如 bi<0,则把该等式约束两端同时乘以 -1,得到：
-ai1 x1-ai2 x2- … -ain xn = -bi 。
1.线性规划的概念
19
例 2.3：将以下线性规划问题转化为标准形式
Min f= -3 x1 + 5 x2 + 8 x3 - 7 x4
s.t,2 x1 - 3 x2 + 5 x3 + 6 x4 ≤ 28
4 x1 + 2 x2 + 3 x3 - 9 x4 ≥ 39
6 x2 + 2 x3 + 3 x4 ≤ - 58
x1,x3,x4 ≥ 0
1.线性规划的概念
20
解：首先,将目标函数转换成极大化：
令 z = -f = 3x1–5x2–8x3+7x4 ；
其次考虑约束,有 3个不等式约束,引进松弛变量 x5,x6,x7 ≥ 0 ；
由于 x2无非负限制,可令 x2=x2’-x2”,
其中 x2’≥ 0,x2”≥ 0 ；
由于第 3个约束右端项系数为 -58，
于是把该式两端乘以 -1 。
于是,我们可以得到以下标准形式的线性规划问题：
1.线性规划的概念
21
Max z = 3x1–5x2’+5x2”–8x3 +7x4
s.t,2x1–3x2’+3x2”+5x3+6x4+x5= 28
4x1+2x2’-2x2”+3x3-9x4-x6= 39
-6x2’+6x2”-2x3-3x4-x7 = 58
x1,x2’,x2”,x3,x4,x5,x6,x7 ≥ 0
1.线性规划的概念
22
2.线性规划的图解法线性规划的图解法 (解的几何表示 )对于只有两个变量的线性规划问题,可以二维直角坐标平面上作图表示线性规划问题的有关概念,并求解 。 图解法求解线性规划问题的步骤如下：
(1)分别取决策变量 x1,x2 为坐标向量建立直角坐标系 。
23
2.线性规划的图解法
（ 2） 对每个约束 （ 包括非负约束 ）
条件,先取其等式在坐标系中作出直线,通过判断确定不等式所决定的半平面 。 各约束半平面交出来的区域
(存在或不存在 ）,若存在,其中的点表示的解称为此线性规划的可行解 。
这些符合约束限制的点集合,称为可行集或可行域 。 然后进行 （ 3） 。 否则该线性规划问题无可行解 。
24
2.线性规划的图解法
（ 3） 任意给定目标函数一个值作一条目标函数的等值线,并确定该等值线平移后值增加的方向,平移此目标函数的等值线,
使其达到既与可行域有交点又不可能使值再增加的位置 (有时交于无穷远处,此时称无有限最优解 ） 。 若有交点时,此目标函数等值线与可行域的交点即最优解
（ 一个或多个 ）,此目标函数的值即最优值 。
25
2.线性规划的图解法例 2.4:某工厂拥有 A,B,C三种类型的设备,生产甲,乙两种产品 。 每件产品在生产中需要占用的设备机时数,每件产品可以获得的利润以及三种设备可利用的时数如下表所示：
产品甲 产品乙 设备能力
（ h）
设备 A 3 2 65
设备 B 2 1 40
设备 C 0 3 75
利润（元 /件） 1500 2500
26
2.线性规划的图解法问题：工厂应如何安排生产可获得最大的总利润？ 用图解法求解 。
解：设变量 xi为第 i种 （ 甲,乙 ） 产品的生产件数 （ i＝ 1,2） 。 根据前面分析,可以建立如下的线性规划模型：
Max z = 1500 x1 + 2500 x2
s.t,3x1+2x2 ≤ 65 (A)
2x1+x2 ≤ 40 (B)
3x2 ≤ 75 (C)
x1,x2 ≥ 0 (D,E)
27
2.线性规划的图解法按照图解法的步骤在以决策变量 x1,x2 为坐标向量的平面直角坐标系上对每个约束
（ 包括非负约束 ） 条件作出直线,并通过判断确定不等式所决定的半平面 。 各约束半平面交出来的区域即可行集或可行域如下图阴影所示 。
28
2、线性规划的图解法图解法求解线性规划
29
2.线性规划的图解法任意给定目标函数一个值作一条目标函数的等值线,并确定该等值线平移后值增加的方向,平移此目标函数的等值线,使其达到既与可行域有交点又不可能使值再增加的位置,得到交点 (5,25)T,此目标函数的值为 70000。 于是,我们得到这个线性规划的最优解 x1=5、
x2=25,最优值 z = 70000。 即最优方案为生产甲产品 5件,乙产品 25件,
可获得最大利润为 70000元 。
30
2.线性规划的图解法例 2.5：在例 2.1的线性规划模型中,如果目标函数变为：
Max z = 1500 x1 + 1000 x2
那么,最优情况下目标函数的等值线与直线 （ A） 重合 。 这时,最优解有无穷多个,是从点 (5,25)T 到点
(15,10)T 线段上的所有点,最优值为
32500。 如下图所示：
31
2.线性规划的图解法无穷多解的情况
32
2.线性规划的图解法例 2.6：在例 2.1的线性规划模型中,
如果约束条件 （ A）,（ C） 变为,
3 x1 + 2 x2 ≥ 65 (A’）
3 x2 ≥ 75 (C’）
并且去掉 （ D,E） 的非负限制 。 那么,
可行域成为一个上无界的区域 。 这时,
没有有限最优解,如下图所示：
33
2.线性规划的图解法无有限解的情况
34
2、线性规划的图解法例 2.7：在例 2.1的线性规划模型中,
如果增加约束条件 （ F） 为：
x1 + x2 ≥ 40 （ F）
那么,可行域成为空的区域 。 这时,
没有可行解,显然线性规划问题无解 。 如下图所示：
35
2.线性规划的图解法无可行解的情况
36
根据以上例题，进一步分析讨论可知线性规划的可行域和最优解有以下几种可能的情况
1.可行域为封闭的有界区域
(a)有唯一的最优解；
(b)有无穷多个最优解；
2.可行域为封闭的无界区域
(c)有唯一的最优解；
2.线性规划的图解法
37
(d)有无穷多个最优解；
(e)目标函数无界 (即虽有可行解，
但在可行域中，目标函数可以无限增大或无限减少 )，因而没有有限最优解。
3.可行域为空集
(f)没有可行解，原问题无最优解
2.线性规划的图解法
38
以上几种情况的图示如下：
2.线性规划的图解法可行域有界 —唯一最优解 可行域有界 —多个最优解
39
2.线性规划的图解法可行域无界 —唯一最优解 可行域无界 —无穷多最优解
40
2.线性规划的图解法可行域无界 —目标函数无界 可行域为空集 —无可行解
41
可行解、可行解集（可行域）
最优解、最优值
基、基变量、非基变量
基本解、基本可行解
可行基、最优基熟悉下列一些解的概念
2.线性规划解的概念
42
线性规划的基、基本解与基本可行解在一般情况下，由于图解法无法解决三个变量以上的线性规划问题，对于 n个变量的线性规划问题，我们必须用解方程的办法来求得可行域的极点。再来进一步考察前例。
例 2.8 把例 2.1的线性规划模型标准化，
引入松驰变量 x3,x4,x5 ≥ 0,得到
2.线性规划解的概念
43
Max z = 1500 x1 + 2500 x2
s.t,3x1+2x2+x3= 65 (A)
2x1+x2+x4= 40 (B)
3x2+x5= 75 (C)
x1,x2,x3,x4,x5 ≥ 0
用（ D）（ E）（ F）（ G）（ H）
分别表示 x1 = 0,x2 = 0,x3 = 0、
x4 = 0,x5 = 0 。
这里一共有 8个约束条件，其中 3个等式约束
2.线性规划解的概念
44
（一般情况下，等式约束的个数少于决策变量的个数）,5个变量非负约束（与决策变量个数相同）。每 5个方程若线性无关可解得一个点，我们可以看到前例图解法得到的区域中每两条直线的交点与此例的各个方程有如下关系：见下图。
2.线性规划解的概念
45
2.线性规划解的概念平面上各不等式约束半平面得交点
46
由上图可以看出：
直线 A,B的交点对应于约束条件 (A),（ B）,
（ C）,（ F）,（ G） 的解,即：
x(1) = (15,10,0,0,45)T
直线 A,C的交点对应于约束条件 (A),（ B）,
（ C）,（ F）,（ H） 的解,即：
x(2) = (5,25,0,5,0)T
直线 A,D的交点对应于约束条件 (A),（ B）,
（ C）,（ D）,（ F） 的解,即：
x(3) = (0,32.5,0,7.5,-22.5)T
2.线性规划解的概念
47
直线 A,E的交点对应于约束条件 (A),（ B）,
（ C）,（ E）,（ F） 的解,即：
x(4) = (65/3,0,0,-10/3,75)T
直线 B,C的交点对应于约束条件 (A),（ B）,
（ C）,（ G）,（ H） 的解,即：
x(5) = (7.5,25,-7.5,0,0)T
直线 B,D的交点对应于约束条件 (A),（ B）,
（ C）,（ D）,（ G） 的解,即：
x(6) = (0,40,-15,0,-45)T
2.线性规划解的概念
48
直线 B,E的交点对应于约束条件 (A),（ B）,
（ C）,（ E）,（ G） 的解,即：
x(7) = (20,0,5,0,75)T
直线 C,D的交点对应于约束条件 (A),（ B）,
（ C）,（ D）,（ H） 的解,即：
x(8) = (0,25,15,15,0)T
直线 C,E无交点 （ C,E相互平行 ）
直线 D,E的交点对应于约束条件 (A),（ B）,
（ C）,（ D）,（ E） 的解,即：
x(9) = (0,0,65,40,75)T
2.线性规划解的概念
49
上图各约束直线的交点是由以下方法得到：在标准化的等式约束中,令其中某两个变量为零,得到其他变量的唯一解,
这个解就是相应交点的坐标,如果某一交点的坐标 (x1,x2,x3,x4,x5 )T全为非负,则该交点就对应于线性规划可行域的一个极点 （ 如 A,B,A,C,B,E,C,D
和 D,E的交点 ） ；如果某一交点的坐标中至少有一个分量为负值 （ 如 A,D,A,E，
B,C和 B,D的交点 ）,则该交点不是可行域的极点 。
2.线性规划解的概念
50
由上图可知,A,B交点对应于 x3 = 0，
x4 = 0，在等式约束中令 x3 = 0,x4 = 0，得到 x1 =15,x2 = 10,x5 = 45。即 A,B交点对应于极点 x= (x1,x2,x3,x4,x5)T =(15，
10,0,0,45)T。由于所有分量都为非负，
因此 A,B交点是可行域的极点。又知,B,C
交点对应于 x4= 0,x5= 0，在等式约束中令
x4 = 0,x5 = 0，得到 x1 =7.5,x2 = 25,x3 =
-7.5。即 B,C交点对应于点 x = (x1,x2,
x3,x4,,x5)T=(-7.5,25,-7.5,0,0)T。
由于有负分量，因此 B,C交点不是可行域的极点。我们同样可以讨论其他交点的情况。
2.线性规划解的概念
51
下面讨论线性规划标准形式的基、基本解、基本可行解的概念。
考虑线性规划标准形式的约束条件：
Ax=b,x≥ 0
其中 A为 m× n的矩阵,n>m,秩 (A) = m，
b? Rm 。 在约束等式中,令 n维空间的解向量：
x = (x1,x2,…,xn)T
2.线性规划解的概念
52
中 n-m个变量为零，如果剩下的 m个变量在线性方程组中有唯一解，则这 n个变量的值组成的向量 x就对应于 n维空间 Rn中若干个超平面的一个交点。当这 n个变量的值都是非负时，这个交点就是线性规划可行域的一个极点。
根据以上分析,我们建立以下概念：
（ 1） 线性规划的 基,对于线性规划的约束条件
Ax=b,x≥ 0
2.线性规划解的概念
53
设 B是 A矩阵中的一个非奇异（可逆）的
m× m子矩阵，则称 B为线性规划的一个 基 。
用前文的记号,A=( p1,p2,…,pn ),
其中 pj=( a1j,a2j,…,amj )T? Rm,
任取 A中的 m个线性无关列向量 pj? Rm
构成矩阵 B=( pj1,pj2,…,pjm )。那么 B为线性规划的一个 基 。
我们称对应于基 B的变量 xj1,
xj2,…,xjm为 基变量 ；而其他变量称为非基变量 。
2.线性规划解的概念
54
可以用矩阵来描述这些概念 。
设 B是线性规划的一个基,则 A可以表示为
A=[ B,N ]
x也可相应地分成
xB
x=
xN
其中 xB为 m维列向量,它的各分量称为 基变量,
与基 B的列向量对应； xN为 n-m列向量,它的各分量称为 非基变量,与非基矩阵 N的列向量对应 。
这时约束等式 Ax=b可表示为
2.线性规划解的概念
55
xB
B,N = b
xN
或
BxB + NxN = b
如果对非基变量 xN取确定的值,则 xB有唯一的值与之对应
xB = B-1b - B-1NxN
特别,当取 xN = 0,这时有 xB=B-1b。 关于这类特别的解,有以下概念 。
2.线性规划解的概念
56
（ 2）线性规划问题的 基本解,基本可行解 和 可行基,
对于线性规划问题,设矩阵 B =
( pj1,pj2,…,pjm ) 为一个基,令所有非基变量为零,可以得到 m个关于基变量 xj1,xj2,…,xjm的线性方程,
解这个线性方程组得到基变量的值 。
我们称这个解为一个 基本解 ；若得到的基变量的值均非负,则称为 基本可行解,同时称这个基 B为 可行基 。
2.线性规划解的概念
57
矩阵描述为，对于线性规划的解
xB B-1b
x= =
xN 0
称为线性规划与基 B对应的基本解 。 若其中 B-1b?0,则称以上的基本解为一基本可行解,相应的基 B称为可行基 。
2.线性规划解的概念
58
我们可以证明以下结论,线性规划的基本可行解就是可行域的极点 。
这个结论被称为线性规划的基本定理,它的重要性在于把可行域的极点这一几何概念与基本可行解这一代数概念联系起来,因而可以通过求基本可行解的线性代数的方法来得到可行域的一切极点,从而有可能进一步获得最优极点 。
2.线性规划解的概念
59
例 2.9,考虑例 2.8的线性规划模型
Max z = 1500 x1 + 2500 x2
s.t,3 x1 + 2 x2 + x3 = 65
2 x1 + x2 + x4 = 40
3 x2 + x5 = 75
x1,x2,x3,x4,x5 ≥ 0
注意,线性规划的基本解,基本可行解 （ 极点 ） 和可行基只与线性规划问题标准形式的约束条件有关 。
2.线性规划解的概念
60
3 2 1 0 0
A = [P1,P2,P3,P4,P5] = 2 1 0 1 0
0 3 0 0 1
A矩阵包含以下 10个 3× 3的子矩阵：
B1=[p1,p2,p3] B2=[p1,p2,p4]
B3=[p1,p2,p5] B4=[p1,p3,p4]
B5=[p1,p3,p5] B6=[p1,p4,p5]
B7=[p2,p3,p4] B8=[p2,p3,p5]
B9=[p2,p4,p5] B10=[p3,p4,p5]
2.线性规划解的概念
61
其中?B4?= 0,因而 B4不是该线性规划问题的基 。
其余均为非奇异方阵,因此该问题共有 9个基 。
对于基 B3=[p1,p2,p5],令非基变量 x3 = 0，
x4 = 0,在等式约束中令 x3 = 0,x4 = 0,解线性方程组：
3 x1 + 2 x2 + 0 x5 = 65
2 x1 + x2 + 0 x5 = 40
0 x1 + 3 x2 + x5 = 75
得到 x1 =15,x2 = 10,x5 = 45,对应的基本可行解：
x=(x1,x2,x3,x4,x5)T=(15,10,0,0，
45)T。 于是对应的基 B3是一个可行基 。
2.线性规划解的概念
62
类似可得到
x(2) = (5,25,0,5,0)T （ 对应 B2）
x(7) = (20,0,5,0,75)T （ 对应 B5）
x(8) = (0,25,15,15,0)T （ 对应 B7）
x(9) = (0,0,65,40,75)T （ 对应 B10）
是基本可行解；
而 x(3)= (0,32.5,0,7.5,-22.5)T（ 对应 B9）
x(4)= (65/3,0,0,-10/3,75)T （ 对应 B6）
x(5)= (7.5,25,-7.5,0,0)T （ 对应 B1）
x(6) = (0,40,-15,0,-45)T （ 对应 B8）
是基本解 。
2.线性规划解的概念
63
因此,对应基本可行解 （ 极点 ） 的 B2
B3 B5 B7 B10都是可行基 。
这里指出了一种求解线性规划问题的可能途径,就是先确定线性规划问题的基,
如果是可行基,则计算相应的基本可行解以及相应解的目标函数值 。 由于基的个数是有限的 （ 最多个 ）,因此必定可以从有限个基本可行解中找到最优解 。
2.线性规划解的概念
64
利用求解线性规划问题基本可行解 （ 极点 ） 的方法来求解较大规模的问题是不可行的 。 单纯形法的基本思路是有选择地取基本可行解,即是从可行域的一个极点出发,沿着可行域的边界移到另一个相邻的极点,要求新极点的目标函数值不比原目标函数值差 。
3.单 纯 形 法
65
由上节的讨论可知,对于线性规划的一个基,当非基变量确定以后,基变量和目标函数的值也随之确定 。 因此,一个基本可行解向另一个基本可行解的移动,以及移动时基变量和目标函数值的变化,可以分别由基变量和目标函数用非基变量的表达式来表示 。
同时,当可行解从可行域的一个极点沿着可行域的边界移动到一个相邻的极点的过程中,
所有非基变量中只有一个变量的值从 0开始增加,而其他非基变量的值都保持 0不变 。
3.单 纯 形 法
66
3.单 纯 形 法初始基本可行解是否最优解或无限最优解?
结束沿边界找新的基本可行解
N
Y
单纯形法的基本过程
67
考虑标准形式的线性规划问题：
Max z = c1x1 + c2x2 + … + cnxn
s.t,a11 x1 + a12 x2 + … + a1n xn = b1
a21 x1 + a22 x2 + … + a2n xn = b2..
.
am1 x1 + am2 x2 + … + amn xn = bm
x1,x2,…,xn ≥ 0
x1 c1 b1 a11 a12..a1n
x2 c2 b2 a21 a22..a2n
x=,C=,B=,A=,,,
.,,,,,
xn cn bn am1 am2..amn
3.单 纯 形 法
68
这里,矩阵 A表示为：
A = ( p1,p2,…,pn ),
其中 pj = ( a1j,a2j,…,amj )T? Rm。
若找到一个可行基,无防设
B = ( p1,p2,…,pm ),则 m个基变量为 x1,x2,…,xm,n-m个非基变量为
xm+1,xm+2,…,xn 。 通过运算,所有的基变量都可以用非基变量来表示：
3.单 纯 形 法
69
3.单 纯 形 法
x1=b’1-（ a’1m+1xm+1+a’1m+2xm+2+…+a’1nxn）
x2=b’2-（ a’2m+1xm+1+a’2m+2xm+2+…+a’2nxn） ( 2-11 ).`
..
xm=b’m-（ a’mm+1xm+1+a’mm+2xm+2+…+a’mnxn）
把它们代入目标函数,得
z = z’+?m+1xm+1+?m+2xm+2+…+?nxn ( 2-12 )
其中
j=cj-（ c1a’1j + c2a’2j + … + cm a’mj）
我们把由非基变量表示的目标函数形式称为基
B相应的目标函数 典式 。
70
单纯形法的基本步骤可描述如下：
（ 1） 寻找一个初始的可行基和相应基本可行解 （ 极点 ）,确定基变量,
非基变量以及基变量,非基变量 （ 全部等于 0） 和目标函数的值,并将目标函数和基变量分别用非基变量表示；
3.单 纯 形 法
71
（ 2） 在用非基变量表示的目标函数表达式 （ 2-12） 中,我们称非基变量 xj的系数 （ 或其负值 ） 为检验数记为
j 。 若?j > 0,那么相应的非基变量
xj,它的值从当前值 0开始增加时,目标函数值随之增加 。 这个选定的非基变量 xj称为,进基变量,,转 （ 3） 。
如果任何一个非基变量的值增加都不能使目标函数值增加,即所有?j 非正,
则当前的基本可行解就是最优解,计算结束；
3.单 纯 形 法
72
（ 3） 在用非基变量表示的基变量的表达式 （ 2-11） 中,观察进基变量增加时各基变量变化情况,确定基变量的值在进基变量增加过程中首先减少到 0的变量 xr,满足,
=min?b’i /a’ij?a’ij > 0? = b’r /a’rj
这个基变量 xr称为,出基变量,。 当进基变量的值增加到? 时,出基变量
xr的值降为 0时,可行解就移动到了相邻的基本可行解 （ 极点 ）,转 （ 4） 。
3.单 纯 形 法
73
如果进基变量的值增加时,所有基变量的值都不减少,即所有 a’ij 非正,则表示可行域是不封闭的,且目标函数值随进基变量的增加可以无限增加,此时,
不存在有限最优解,计算结束；
（ 4） 将进基变量作为新的基变量,
出基变量作为新的非基变量,确定新的基,新的基本可行解和新的目标函数值 。
在新的基变量,非基变量的基础上重复
（ 1） 。
3.单 纯 形 法
74
例 2.10：用单纯形法的基本思路解例 2.8的线性规划问题
Max z = 1500 x1 + 2500 x2
s.t,3 x1 + 2 x2 + x3 = 65
2 x1 + x2 + x4 = 40
3 x2 + x5 = 75
x1,x2,x3,x4,x5 ≥ 0
3.单 纯 形 法
75
第一次迭代：
（ 1） 取初始可行基 B10= (p3,p4,p5)，
那么 x3,x4,x5为基变量,x1,x2为非基变量 。 将基变量和目标函数用非基变量表示：
z=1500x1+2500x2
x3 = 65 - 3 x1 - 2 x2
x4 = 40 - 2 x1 - x2
x5 = 75 - 3 x2
当非基变量 x1,x2=0时,相应的基变量和目标函数值为 x3=65,x4=40,x5= 75，
z = 0,得到当前的基本可行解：
x=(0,0,65,40,75)T,z = 0 。 这个解对应于图 2-7的 D,E交点 。
3.单 纯 形 法
76
（ 2） 选择进基变量 。 在目标函数
z = 1500 x1 + 2500 x2中,非基变量 x1，
x2的系数都是正数,因此 x1,x2进基都可以使目标函数 z增大,但 x2的系数为
2500,绝对值比 x1的系数 1500大,因此把 x2作为进基变量可以使目标函数 z增加更快 。 选择 x2为进基变量,使 x2的值从 0
开始增加,另一个非基变量 x1保持零值不变 。
3.单 纯 形 法
77
（ 3） 确定出基变量 。 在约束条件
x3 = 65 - 3 x1 - 2 x2
x4 = 40 - 2 x1 - x2
x5 = 75 - 3 x2
中,由于进基变量 x2在 3个约束条件中的系数都是负数,当 x2的值从 0开始增加时,
基变量 x3,x4,x5的值分别从当前的值
65,40和 75开始减少,当 x2增加到 25时,
x5首先下降为 0成为非基变量 。 这时,新的基变量为 x3,x4,x2,新的非基变量为 x1,x5,当前的基本可行解和目标函数值为：
x = (0,25,15,15,0)T,z = 62500。
这个解对应于图中的 C,D交点 。
3.单 纯 形 法
78
第二次迭代：
（ 1） 当前的可行基为 B7 = (p2,p3,
p4),那么 x2,x3,x4为基变量,x1,x5
为非基变量 。 将基变量和目标函数用非基变量表示：
z = 62500 + 1500 x1 – (2500/3) x5
x2 = 25 – (1/3) x5
x3 = 15 - 3 x1 + (2/3) x5
x4 = 15 - 2 x1 + (1/3) x5
3.单 纯 形 法
79
（ 2） 选择进基变量 。 在目标函数
z = 62500 + 1500 x1 – (2500/3) x5
中,非基变量 x1的系数是正数,因此
x1进基可以使目标函数 z增大,于是选择 x1进基,使 x1的值从 0开始增加,另一个非基变量 x5保持零值不变 。
(3)确定出基变量 。 在约束条件
x2 = 25 – (1/3) x5
x3 = 15 - 3 x1 + (2/3) x5
x4 = 15 - 2 x1 + (1/3) x5
3.单 纯 形 法
80
中,由于进基变量 x1在两个约束条件中的系数都是负数,当 x1的值从 0开始增加时,基变量 x3,x4的值分别从当前的值 15,15开始减少,当 x1增加到 5
时,x3首先下降为 0成为非基变量 。 这时,新的基变量为 x1,x2,x4,新的非基变量为 x3,x5,当前的基本可行解和目标函数值为：
x = (5,25,0,5,0)T,z = 70000。
这个解对应于图中的 A,C交点 。
3.单 纯 形 法
81
第三次迭代：
（ 1） 当前的可行基为 B2 = (p1,
p2,p4 ),那么 x1,x2,x4为基变量,x3,x5为非基变量 。 将基变量和目标函数用非基变量表示：
z = 70000 – 500 x3 – 500 x5
x1 = 5 – (1/3) x3 + (2/9) x5
x2 = 25 – (1/3) x5
x4 = 5 + (2/3) x3 – (1/9) x5
3.单 纯 形 法
82
（ 2） 选择进基变量 。 在目标函数
z = 70000 – 500 x3 – 500 x5 中,非基变量 x3,x5的系数均不是正数,因此进基都不可能使目标函数 z增大,于是得到最优解,x* = (5,25,0,5，
0)T,最优目标值为 z* = 70000。 这个解对应于图 2-7的 A,C交点 。 我们也称相应的基 B2 = (p1,p2,p4)为 最优基 。
计算结束 。
3.单 纯 形 法
83
3,单 纯 形 法
表格单纯形法
考虑,bi > 0 i = 1,…,m
Max z = c1 x1 + c2 x2 + … + c n xn
s.t,a11 x1 + a12 x2 + … + a1n xn ≤ b1
a21 x1 + a22 x2 + … + a2n xn ≤ b2
…… ……
am1 x1 + am2 x2 + … + amn xn ≤ bm
x1,x2,…,xn ≥ 0
84
3,单 纯 形 法
加入松弛变量：
Max z = c1 x1 + c2 x2 + … + c n xn
s.t,a11 x1 + a12 x2 + … + a1n xn + xn+1 = b1
a21 x1 + a22 x2 + … + a2n xn + xn+2 = b2
…… ……
am1 x1 + am2 x2 + … + amn xn+ xn+m = bm
x1,x2,…,xn,xn+1,…,xn+m ≥ 0
85
显然,xj= 0 j = 1,…,n ; xn+i = bi i = 1,…,m 是基本可行解对应的基是单位矩阵。
以下是初始单纯形表：
m m
其中,f = -∑ cn+i bi?j = cj -∑ cn+i aij 为检验数 cn+i = 0 i= 1,…,m
i = 1 i = 1
an+i,i = 1,an+i,j = 0 ( j≠i ) i,j = 1,…,m
3,单 纯 形 法
c 1 … c n c n+ 1 … c n+ m
C B X B
x 1 … x n x n+ 1 … x n+ m θ i
c n+ 1 x n+ 1 b 1 a 11 … a 1n a 1n + 1 … a 1n + m θ
1
c n+ 2 x n+ 2 b 2 a 21 … a 2n a 2n + 1 … a 2n + m θ
2
┇ ┇ ┇ ┇ ┇ ┇ ┇ ┇ ┇ ┇
c n+ m x n+ m b m a m1 … a mn a m n+ 1 … a m n+ m θ
m
- z f σ
1 … σ n 0 … 0
86
3,单 纯 形 法
1500
2500
0 0
0
C
B
X
B
x
1
X
2
x
3
x
4
x
5 θ i
0 x
3
65 3 2 1 0 0 32,5
0 x
4
40 2 1 0 1 0 40
0 x
5
75 0 ( 3) 0 0 1 25
- z 0 1500 2500* 0 0 0
0 x
3
15 ( 3) 0 1 0 - 2/3 5
0 x
4
15 2 0 0 1 - 1/3 7,5
25 00 x
2
25 0 1 0 0 1/3
- z - 62500 1500* 0 0 0 - 2500/3
1 5 0 0 x
1
5 1 0 1/3 0 - 2/ 9
0 x
4
5 0 0 - 2/3 1 1/9
25 00 x
2
25 0 1 0 0 1/3
- z - 70000 0 0 - 500 0 - 500
例 2.10。化标准形式,Max z =1500 x1 + 2500 x2
s.t,3 x1 + 2 x2 + x3 = 65
2 x1 + x2 + x4 = 40
3 x2 + x5 = 75
x1,x2,x3,x4,x5 ≥ 0
最优解 x1 = 5 x2 = 25 x4 = 5（松弛标量，表示 B设备有 5个机时的剩余）
最优值 z* = 70000
87
注意：单纯形法中，
1、每一步运算只能用矩阵初等行变换；
2、表中第 3列的数总应保持非负
（ ≥ 0）；
3、当所有检验数均非正（ ≤ 0）
时，得到最优单纯形表。
3,线 性 规 划
88
一般情况的处理及注意事项的强调：主要是讨论初始基本可行解不明显时，常用的方法。要弄清它的原理，并通过例题掌握这些方法，同时进一步熟悉用单纯形法解题。
考虑一般问题：
bi > 0 i = 1,…,m
3.单 纯 形 法
89
Max z = c1x1 + c2x2 + … + cnxn
s.t.
a11x1+a12x2 +…+a1nxn = b1
a21x1+a22x2 +…+a2nxn = b2.
.,
am1x1+am2x2+…+amnxn = bm
x1,x2,…,xn ≥ 0
3.单 纯 形 法
90
大 M法：
引入人工变量 xn+i ≥ 0 （ i = 1,…,
m）及充分大正数 M 。得到：
Max
z = c1x1 +c2x2 +…+cnxn -Mxn+1 -…-Mxn+m
s.t.
a11 x1 + a12 x2 + … + a1n xn + xn+1 = b1
a21 x1 + a22 x2 + … + a2n xn + xn+2 = b2.
.,
am1 x1 + am2 x2 + … + amn xn + xn+m = bm
x1,x2,…,xn,xn+1,…,xn+m≥ 0
3.单 纯 形 法
91
显然,xj = 0 j=1,…,n ;
xn+i = bi i =1,…,m
是基本可行解。
对应的基是单位矩阵。
结论,若得到的最优解满足
xn+i = 0 i = 1,…,m 则是原问题的最优解；否则，原问题无可行解。
3.单 纯 形 法
92
两阶段法：
引入人工变量 xn+i ≥ 0,i = 1,…,m；
构造,
Max z = - xn+1 - xn+2 - … - xn+m
s.t.
a11x1+a12x2+ … +a1nxn+xn+1 = b1
a21x1+a22x2+ … +a2nxn+xn+2 = b2.
..
am1x1+am2x2+ … +amnxn+xn+m = bm
x1,x2,.,xn,xn+1,…,xn+m ≥ 0
3.单 纯 形 法
93
第一阶段求解上述问题：
显然,xj = 0 j=1,…,n ;
xn+i = bi i =1,…,m
是基本可行解,它对应的基是单位矩阵。
结论,若得到的最优解满足 xn+i=0
i=1,…,m 则是原问题的基本可行解 ;否则，原问题无可行解。
得到原问题的基本可行解后，第二阶段求解原问题。
3.单 纯 形 法
94
例 2.11：（ LP）
Max z = 5x1 + 2x2 + 3x3 - x4
s.t,x1 + 2x2 + 3x3 = 15
2x1 + x2 + 5x3 = 20
x1 + 2x2 + 4x3 + x4 = 26
x1,x2,x3,x4 ≥ 0
3.单 纯 形 法
95
Max z = 5x1+2x2+3x3-x4-Mx5-Mx6
s.t,x1+2x2+3x3+x5 =15
2x1+x2+5x3+x6 =20
x1+2x2+4x3+x4 =26
x1,x2,x3,x4,x5,x6 ≥ 0
3.单 纯 形 法
96
5
2
3 - 1 - M
- M
C
B
X
B
x
1
x
2
x
3
x
4
x
5
x
6 θ i
- M x
5
15 1 2 3 0 1 0 5
- M x
6
20 2 1 ( 5) 0 0 1 4
- 1 x
4
26 1 2 4 1 0 0 6.5
- z 35M + 26 3M + 6 3M + 4 8M + 7 0 0 0
- M x
5
3 - 1/ 5 ( 7/ 5) 0 0 1 - 3/ 5 15/ 7
3 x
3
4 2/ 5 1/ 5 1 0 0 1/ 5 20
- 1 x
4
10 - 3/ 5 6/ 5 0 1 0 - 4/ 5 25/ 3
- z 3M - 2 - M / 5+ 16/ 5 7/ 5M + 13/ 5 0 0 0 - 8/ 5M - 7/ 5
2 x
2
15/ 7 - 1/ 7 1 0 0 5/ 7 - 3/ 7
3 x
3
25/ 7 ( 3/ 7) 0 1 0 - 1/ 7 2/ 7 25/ 3
- 1 x
4
52/ 7 - 3/ 7 0 0 1 - 6/ 7 - 2/ 7
- z - 53/ 7 25/ 7 0 0 0 - M - 13/ 7 - M - 2/ 7
2 x
2
10/ 3 0 1 1/ 3 0 2/ 3 - 1/ 3
5 x
1
25/ 3 1 0 7/ 3 0 - 1/ 3 2/ 3
- 1 x
4
11 0 0 1 1 - 1 0
- z - 1 12/ 3 0 0 - 25/ 3 0 - M - 2/ 3 - M + 8/ 3
大 M法 （ LP - M）
得到 最优解,(25/3,10/3,0,11)T
最优目标值,112/3
3.单 纯 形 法
97
第一阶段问题（ LP - 1）
Max z = - x5 - x6
s.t,x1 + 2x2 + 3x3 + x5 = 15
2x1 + x2 + 5x3 + x6 = 20
x1 + 2x2 + 4x3 + x4 = 26
x1,x2,x3,x4,x5,x6 ≥ 0
3.单 纯 形 法
98
0 0 0 0 -1 -1
C
B
X
B
x
1
x
2
x
3
x
4
x
5
x
6
θ
i
-1 x
5
15 1 2 3 0 1 0 5
-1 x
6
20 2 1 ( 5 ) 0 0 1 4
0 x
4
26 1 2 4 1 0 0 6,5
-z 35 3 3 8 0 0 0
-1 x
5
3 - 1 / 5 ( 7 / 5 ) 0 0 1 - 3 / 5 1 5 / 7
0 x
3
4 2 / 5 1 / 5 1 0 0 1 / 5 20
0 x
4
10 - 3 / 5 6 / 5 0 1 0 - 4 / 5 2 5 / 3
-z 3 - 1 / 5 7 / 5 0 0 0 - 8 / 5
0 x
2
1 5 / 7 - 1 / 7 1 0 0 5 / 7 - 3 / 7
0 x
3
2 5 / 7 3 / 7 0 1 0 - 1 / 7 2 / 7 2 5 / 3
0 x
4
5 2 / 7 - 3 / 7 0 0 1 - 6 / 7 - 2 / 7
-z 0 0 0 0 0 -1 -1
第一阶段 (LP - 1）
得到原问题的基本可行解,
(0,15/7,25/7,52/7)T
3.单 纯 形 法
99
5 2 3 -1
C
B
X
B
x
1
x
2
x
3
x
4
θ
i
2 x
2
15 / 7 - 1/ 7 1 0 0
3 x
3
25 / 7 ( 3/ 7) 0 1 0 25 / 3
-1 x
4
52 / 7 - 3/ 7 0 0 1
-z - 53 / 7 25 / 7 0 0 0
2 x
2
10 / 3 0 1 1/ 3 0
5 x
1
25 / 3 1 0 7/ 3 0
-1 x
4
11 0 0 1 1
-z - 1 12 / 3 0 0 - 25 / 3 0
第二阶段 把基本可行解填入表中
得到原问题的最优解,(25/3,10/3,0,11)T
最优目标值,112/3
3.单 纯 形 法
100
注意,单纯形法中
1、每一步运算只能用矩阵初等行变换；
2、表中第 3列 (b列 )的数总应保持非负
（ ≥ 0）；
3、当所有检验数均非正（ ≤ 0）时，得到最优单纯形表。若直接对目标求最 h，要求 所有检验数均非负；
4,当最优单纯形表存在非基变量对应的检验数为零时,可能存在无穷多解；
3.单 纯 形 法
101
5、关于退化和循环。如果在一个基本可行解的基变量中至少有一个分量
xBi=0 (i=1,2,…,m)，则称此基本可行解是退化的基本可行解。一般情况下，退化的基本可行解（极点）是由若干个不同的基本可行解（极点）在特殊情况下合并成一个基本可行解（极点）而形成的。退化的结构对单纯形迭代会造成不利的影响。
3.单 纯 形 法
102
可能出现以下情况,① 进行进基,出基变换后,虽然改变了基,但没有改变基本可行解 （ 极点 ）,目标函数当然也不会改进 。 进行若干次基变换后,才脱离退化基本可行解 （ 极点 ）,进入其他基本可行解 （ 极点 ） 。 这种情况会增加迭代次数,
使单纯形法收敛的速度减慢 。 ② 在特殊情况下,退化会出现基的循环,一旦出现这样的情况,单纯形迭代将永远停留在同一极点上,因而无法求得最优解 。
3.单 纯 形 法
103
在单纯形法求解线性规划问题时，一旦出现这种因退化而导致的基的循环，单纯形法就无法求得最优解，这是一般单纯形法的一个缺陷。但是实际上，尽管退化的结构是经常遇到的，而循环现象在实际问题中出现得较少。尽管如此，人们还是对如何防止出现循环作了大量研究。 1952
年 Charnes提出了,摄动法,,1954年
Dantzig,Orden和 Wolfe又提出了,字典序法,,
3.单 纯 形 法
104
这些方法都比较复杂，同时也降低了迭代的速度。 1976年,Bland提出了一个避免循环的新方法，其原则十分简单。仅在选择进基变量和出基变量时作了以下规定：① 在选择进基变量时，在所有?j >
0的非基变量中选取下标最小的进基；②
当有多个变量同时可作为出基变量时，选择下标最小的那个变量出基。这样就可以避免出现循环,当然，这样可能使收敛速度降低。
3.单 纯 形 法
105
合理利用线材问题,如何下料使用材最少。
配料问题,在原料供应量的限制下如何获取最大利润。
投资问题,从投资项目中选取方案，使投资回报最大。
4.线性规划应用一、线性规划 ---
106
产品生产计划,合理利用人力、物力、财力等，使获利最大。
劳动力安排,用最少的劳动力来满足工作的需要。
运输问题,如何制定调运方案，使总运费最小。
4.线性规划应用
107
数学规划的建模有许多共同点,
要遵循下列原则：
(1)容易理解 。 建立的模型不但要求建模者理解,还应当让有关人员理解 。 这样便于考察实际问题与模型的关系,使得到的结论能够更好地应用于解决实际问题 。
(2)容易查找模型中的错误 。 这个原则的目的显然与 (1)相关 。 常出现的错误有：书写错误和公式错误 。
4.线性规划应用
108
(3)容易求解 。 对线性规划来说,
容易求解问题主要是控制问题的规模,包括决策变量的个数和约束条件的个数 。 这条原则的实现往往会与 (1)发生矛盾,在实现时需要对两条原则进行统筹考虑 。
4.线性规划应用
109
建立线性规划模型的过程可以分为四个步骤：
(1)设立决策变量；
(2)明确约束条件并用决策变量的线性等式或不等式表示；
(3)用决策变量的线性函数表示目标,并确定是求极大 （ Max） 还是极小 （ Min） ；
(4)根据决策变量的物理性质研究变量是否有非负性 。
4.线性规划应用
110
例 2.12,某昼夜服务的公交线路每天各时间段内所需司机和乘务人员数如下：
班次 时间 所需人数
1 6,00 —— 10,00 60
2 10,00 —— 14,00 70
3 14,00 —— 18,00 60
4 18,00 —— 22,00 50
5 22,—— 2,00 20
6 2,00 —— 6,00 30
人力资源分配的问题设司机和乘务人员分别在各时间段一开始时上班，并连续工作 8h，问该公交线路怎样安排司机和乘务人员，既能满足工作需要，又配备最少司机和乘务人员?
111
解：设 xi 表示第 i班次时开始上班的司机和乘务人员数,这样我们建立如下的数学模型。
目标函数,Min x1 + x2 + x3 + x4 + x5 + x6
约束条件,s.t,x1 + x6 ≥ 60
x1 + x2 ≥ 70
x2 + x3 ≥ 60
x3 + x4 ≥ 50
x4 + x5 ≥ 20
x5 + x6 ≥ 30
x1,x2,x3,x4,x5,x6 ≥ 0
人力资源分配的问题
112
例 2.13:某工厂要做 100套钢架，每套用长为 2.9 m,
2.1m,1.5m的圆钢各一根。已知原料每根长 7.4 m，
问：应如何下料，可使所用原料最省？
方案 1 方案 2 方案 3 方案 4 方案 5 方案 6 方案 7 方案 8
2.9 m 1 2 0 1 0 1 0 0
2.1 m 0 0 2 2 1 1 3 0
1.5 m 3 1 2 0 3 1 0 4
合计 7.4 7.3 7.2 7.1 6.6 6,5 6,3 6.0
剩余料头 0 0.1 0.2 0.3 0.8 0.9 1,1 1,4
套裁下料问题解,考虑下列各种下料方案（按一种逻辑顺序给出）
方案 1 方案 2 方案 3 方案 4 方案 5 方案 6 方案 7 方案 8
2.9 m 2 1 1 1 0 0 0 0
2.1 m 0 2 1 0 3 2 1 0
1.5 m 1 0 1 3 0 2 3 4
合计 7.3 7.1 6,5 7.4 6,3 7.2 6.6 6.0
剩余料头 0.1 0.3 0.9 0 1,1 0.2 0.8 1,4
把各种下料方案按剩余料头从小到大顺序列出
113
假设 x1,x2,x3,x4,x5 分别为上面前 5 种方案下料的原材料根数。我们建立如下的数学模型。
目标函数：
Min x1 + x2 + x3 + x4 + x5
约束条件：
s.t,x1 + 2x2 + x4 ≥ 100
2x3 + 2x4 + x5 ≥ 100
3x1 + x2 + 2x3+ 3x5 ≥ 100
x1,x2,x3,x4,x5 ≥ 0
套裁下料问题方案 1 方案 2 方案 3 方案 4 方案 5
2.9 m 1 2 0 1 0
2.1 m 0 0 2 2 1
1.5 m 3 1 2 0 3
合计 7.4 7.3 7.2 7.1 6.6
剩余料头 0 0.1 0.2 0.3 0.8
114
例 2.14:明兴公司生产甲、乙、
丙三种产品，都需要经过铸造、机加工和装配 三个车间。甲、乙两种产品的铸件可以外包协作，亦可以自行生产，但产品丙必须本厂铸造才能保证质量。数据如下表。问：公司为了获得最大利润，甲、乙、丙三种产品各生产多少件？甲、乙两种产品的铸造中，由本公司铸造和由外包协作各应多少件？
生产计划的问题
115
甲 乙 丙 资源限制铸造工时 ( 小时 / 件 ) 5 10 7 8000
机加工工时 ( 小时 / 件 ) 6 4 8 12000
装配工时 ( 小时 / 件 ) 3 2 2 10000
自产铸件成本 ( 元 / 件 ) 3 5 4
外协铸件成本 ( 元 / 件 ) 5 6 --
机加工成本 ( 元 / 件 ) 2 1 3
装配成本 ( 元 / 件 ) 3 2 2
产品售价 ( 元 / 件 ) 23 18 16
解,设 x1,x2,x3 分别为三道工序都由本公司加工的甲、乙、丙三种产品的件数,x4,x5 分别为由外协铸造再由本公司机加工和装配的甲、乙两种产品的件数。
生产计划的问题
116
求 xi 的利润,利润 = 售价 - 各成本之和 可得到 xi（ i=1,2,3,4,5）的利润分别为 15,10,7,13,9元。
这样我们建立如下数学模型：
目标函数,Max 15x1+10x2+7x3+13x4+9x5
约束条件：
s.t,5x1+10x2+7x3 ≤ 8000
6x1+4x2+8x3+6x4+4x5 ≤12000
3x1+2x2+2x3+3x4+2x5 ≤ 10000
x1,x2,x3,x4,x5 ≥ 0
生产计划的问题
117
例 2.15:永久机械厂生产 Ⅰ,Ⅱ,Ⅲ 三种产品，均要经过 A,B 两道工序加工。假设有两种规格的设备 A1,A2能完成 A 工序；
有三种规格的设备 B1,B2,B3能完成 B 工序。 Ⅰ 可在 A,B的任何规格的设备上加工；
Ⅱ 可在任意规格的 A设备上加工，但对 B工序,只能在 B1设备上加工； Ⅲ 只能在 A2与 B2
设备上加工；数据如下表。问：为使该厂获得最大利润，应如何制定产品加工方案？
生产计划的问题
118
解,设 xijk 表示第 i 种产品，在第 j
种工序上的第 k 种设备上加工的数量,
利润 = [（销售单价 - 原料单价） × 产品件数 ]之和 - （每台时的设备费用 × 设备实际使用的总台时数）之和 。
产品单件工时设备 Ⅰ Ⅱ Ⅲ
设备的有效台时满负荷时的设备费用
A
1
5 10 6000 300
A
2
7 9 12 10000 321
B
1
6 8 4000 50
B
2
4 11 7000 783
B
3
7 4000 200
原料 （元 / 件） 0,25 0,35 0,50
售价 （元 / 件） 1,25 2,00 2,80
生产计划的问题
119
这样我们建立如下的数学模型,
Max
0.75x111+0.7753x112+1.15x211+1.3611x212+1.91
48x312-0.375x121-0.5x221-0.4475x122-
1.2304x322-0.35x123
s.t
5x111+10x211≤6000 （ 设备 A1 ）
7x112+9x212+12x312≤10000 （ 设备 A2 ）
6x121+ 8x221≤ 4000 ( 设备 B1 ）
4x122+11x322≤700 ( 设备 B2 ）
7x123 ≤ 4000 （ 设备 B3 ）
生产计划的问题
120
x111+ x112- x121- x122- x123 = 0
(Ⅰ 产品在 A,B工序加工的数量相等）
x211+ x212- x221 = 0
(Ⅱ 产品在 A,B工序加工的数量相等）
x312 - x322 = 0
(Ⅲ 产品在 A,B工序加工的数量相等）
xijk≥0,i=1,2,3; j=1,2; k=1,2,3
生产计划的问题
121
例 2.14:某工厂要用三种原料 1,2,3混合调配出三种不同规格的产品甲、乙、丙，
数据如下表。问：该厂应如何安排生产，使利润收入为最大？
产品名称 规格要求 单价 （元 /kg ）
甲 原材料 1 不少于 50 %,原材料 2 不超过 25% 50
乙 原材料 1 不少于 25 %,原材料 2 不超过 50% 35
丙 不限 25
原材料名称 每天最多供应量 单价 （元 /kg ）
1 100 65
2 100 25
3 60 35
配料问题
122
配料问题解：设 xij 表示第 i 种（甲、乙、丙）
产品中原料 j 的含量。这样我们建立数学模型时，要考虑：
对于甲,x11,x12,x13；
对于乙,x21,x22,x23；
对于丙,x31,x32,x33；
对于原料 1,x11,x21,x31；
对于原料 2,x12,x22,x32；
对于原料 3,x13,x23,x33；
123
目标函数：
利润最大，利润 = 收入 - 原料支出约束条件,规格要求 4 个；
供应量限制 3 个。
Max
z = -15x11+25x12+15x13-30x21+10x22-40x31-10x33
配料问题
124
s.t,0.5 x11-0.5 x12 -0.5 x13 ≥ 0 （原材料 1不少于 50%）
-0.25x11+0.75x12 -0.25x13 ≤ 0
（原材料 2不超过 25%）
0.75x21-0.25x22 -0.25x23 ≥ 0
（原材料 1不少于 25%）
-0.5 x21+0.5 x22 -0.5 x23 ≤ 0
（原材料 2不超过 50%）
x11+x21+x31≤ 100 ( 供应量限制）
x12+x22+x32≤ 100 ( 供应量限制）
x13+x23+x33≤ 60 ( 供应量限制）
xij≥0,i = 1,2,3; j = 1,2,3
配料问题
125
例 2.17：某部门现有资金 200万元，今后五年内考虑给以下的项目投资。已知：项目 A,从第一年到第五年每年年初都可投资，
当年末能收回本利 110%；项目 B：从第一年到第四年每年年初都可投资，次年末能收回本利 125%，但规定每年最大投资额不能超过 30
万元；项目 C：需在第三年年初投资，第五年末能收回本利 140%，但规定最大投资额不能超过 80万元；项目 D：需在第二年年初投资，
第五年末能收回本利 155%，但规定最大投资额不能超过 100万元。
投资问题
126
据测定每万元每次投资的风险指数如下表：
项目 风险指数（次 / 万元）
A 1
B 3
C 4
D 5,5
投资问题
127
a）应如何确定这些项目的每年投资额，使得第五年年末拥有资金的本利金额为最大？
b）应如何确定这些项目的每年投资额，使得第五年年末拥有资金的本利在 330万元的基础上使得其投资总的风险系数为最小？
问：
投资问题
128
投资问题解,1） 确定决策变量：连续投资问题设 xij ( i = 1—5,j = 1,2,3,4)表示第 i 年初投资于 A(j=1),B(j=2),C(j=3)、
D(j=4)项目的金额。这样我们建立如下 决策变量,
A x11 x21 x31 x41 x51
B x12 x22 x32 x42
C x33
D x24
129
2）约束条件：
第一年,A当年末可收回投资，故第一年年初应把全部资金投出去，于是：
x11+ x12 = 200
第二年,B次年末才可收回投资故第二年年初的资金为 1.1x11，于是：
x21 + x22+ x24 = 1.1x11
第三年,年初的资金为 1.1x21+1.25x12，于是,
x31 + x32+ x33 = 1.1x21+ 1.25x12
第四年,年初的资金为 1.1x31+1.25x22，于是：
x41 + x42 = 1.1x31+ 1.25x22
第五年,年初的资金为 1.1x41+1.25x32，于是：
x51 = 1.1x41+ 1.25x32
B,C,D的投资限制,xi2 ≤ 30 ( i=1,2,3，
4 ),x33 ≤ 80,x24 ≤ 100
投资问题
130
a)
Max z=1.1x51+1.25x42+1.4x33+1.55x24
s.t.x11+ x12 = 200
x21 + x22+ x24 = 1.1x11
x31 + x32+ x33 = 1.1x21+ 1.25x12
x41 + x42 = 1.1x31+ 1.25x22
x51 = 1.1x41+ 1.25x32
xi2 ≤ 30 ( i =1,2,3,4 )，
x33 ≤ 80,x24 ≤ 100
xij≥ 0(i=1,2,3,4,5； j=1,2,3,4）
3）目标函数及模型：
投资问题
131
b)
Min f = （ x11+x21+x31+x41+x51)+
3(x12+x22+x32+x42)+4x33+5.5x24
s.t,x11+ x12 ≤ 200
x21 + x22+ x24 ≤ 1.1 x11
x31 + x32+ x33 ≤ 1.1 x21+ 1.25x12
x41 + x42 ≤ 1.1 x31+ 1.25x22
x51 ≤ 1.1 x41+ 1.25x32
xi2 ≤ 30 ( i =1,2,3,4 )，
x33 ≤ 80,x24 ≤ 100
1.1x51 + 1.25x42+ 1.4x33+ 1.55x24 ≥ 330
xij≥ 0(i=1,2,3,4,5； j = 1,2,3,4）
投资问题
2
第二章线性规划建模及单纯形法本章内容重点
线性规划模型与解的主要概念
线性规划的单纯形法，线性规划多解分析
线性规划应用 ——建模
3
1.线性规划的概念例 2.1:某工厂拥有 A,B,C三种类型的设备,生产甲,乙两种产品 。 每件产品在生产中需要占用的设备机时数,每件产品可以获得的利润以及三种设备可利用的时数如下表所示：
产品甲 产品乙 设备能力
（ h）
设备 A 3 2 65
设备 B 2 1 40
设备 C 0 3 75
利润（元 /件） 1500 2500
4
问题：工厂应如何安排生产可获得最大的总利润？
解：设变量 xi为第 i种 （ 甲,乙 ） 产品的生产件数 （ i＝ 1,2） 。 根据题意,
我们知道两种产品的生产受到设备能力
（ 机时数 ） 的限制 。 对设备 A,两种产品生产所占用的机时数不能超过 65,于是我们可以得到不等式,3 x1 + 2 x2 ≤ 65；
对设备 B,两种产品生产所占用的机时数不能超过 40,于是我们可以得到不等式,2 x1 + x2 ≤ 40；
1.线性规划的概念
5
对设备 C,两种产品生产所占用的机时数不能超过 75,于是我们可以得到不等式,3x2 ≤ 75 ；另外,产品数不可能为负,即 x1,x2 ≥ 0。 同时,我们有一个追求目标,即获取最大利润 。 于是可写出目标函数 z为相应的生产计划可以获得的总利润,z=1500x1+2500x2 。 综合上述讨论,在加工时间以及利润与产品产量成线性关系的假设下,把目标函数和约束条件放在一起,可以建立如下的线性规划模型：
1.线性规划的概念
6
目标函数 Max z =1500x1+2500x2
约束条件 s.t,3x1+2x2≤ 65
2x1+x2≤ 40
3x2≤ 75
x1,x2 ≥ 0
1.线性规划的概念
7
这是一个典型的利润最大化的生产计划问题 。 其中,,Max”是英文单词,Maximize”的缩写,含义为,最大化,；,s.t.”是,subject to”的缩写,表示,满足于 ……,。 因此,上述模型的含义是：在给定条件限制下,
求使目标函数 z达到最大的 x1,x2 的取值 。
1.线性规划的概念
8
一般形式
目标函数：
Max(Min)z = c1x1 + c2x2 + … + cnxn
约束条件：
a11x1+a12x2+… +a1nxn≤( =,≥ ) b1
a21x1+a22x2+… +a2nxn≤( =,≥ ) b2..
,
am1x1+am2x2 +… +amnxn≤( =,≥ ) bm
x1,x2,…,xn ≥ 0
1.线性规划的概念
9
标准形式
目标函数：
Max z = c1x1 + c2x2 + … + cnxn
约束条件：
a11x1 + a12x2 + … + a1nxn = b1
a21x1 + a22x2 + … + a2nxn = b2..
.
am1x1 + am2x2 + … + amnxn = bm
x1,x2,…,xn ≥ 0
1.线性规划的概念
10
可以看出,线性规划的标准形式有如下四个特点,目标最大化,约束为等式,决策变量均非负,右端项非负 。
对于各种非标准形式的线性规划问题,我们总可以通过以下变换,将其转化为标准形式,
1.线性规划的概念
11
1.极小化目标函数的问题：
设目标函数为
Min f = c1x1 + c2x2 + … + cnxn
则可以令 z ＝ -f,该极小化问题与下面的极大化问题有相同的最优解,即
Max z = -c1x1 - c2x2 - … - cnxn
但必须注意,尽管以上两个问题的最优解相同,但他们最优解的目标函数值却相差一个符号,即
Min f ＝ - Max z
1.线性规划的概念
12
2,约束条件不是等式的问题：
设约束条件为
ai1 x1+ai2 x2+ … +ain xn ≤ bi
可以引进一个新的变量 s,使它等于约束右边与左边之差
s=bi–(ai1 x1 + ai2 x2 + … + ain xn )
显然,s 也具有非负约束,即 s≥ 0，
这时新的约束条件成为
ai1 x1+ai2 x2+ … +ain xn+s = bi
1.线性规划的概念
13
当约束条件为
ai1 x1+ai2 x2+ … +ain xn ≥ bi
时,类似地令
s=(ai1 x1+ai2 x2+ … +ain xn)- bi
显然,s 也具有非负约束,即 s≥ 0，
这时新的约束条件成为
ai1 x1+ai2 x2+ … +ain xn-s = bi
1.线性规划的概念
14
为了使约束由不等式成为等式而引进的变量 s称为,松弛变量,。
如果原问题中有若干个非等式约束,
则将其转化为标准形式时,必须对各个约束引进不同的松弛变量 。
1.线性规划的概念
15
例 2.2：将以下线性规划问题转化为标准形式
Min f = 3.6 x1 - 5.2 x2 + 1.8 x3
s,t,2.3 x1 + 5.2 x2 - 6.1 x3 ≤ 15.7
4.1 x1 + 3.3 x3 ≥ 8.9
x1 + x2 + x3 = 38
x1,x2,x3 ≥ 0
1.线性规划的概念解：首先,将目标函数转换成极大化,
令 z= -f = -3.6x1+5.2x2-1.8x3
16
其次考虑约束,有 2个不等式约束,引进松弛变量 x4,x5 ≥ 0。
于是,我们可以得到以下标准形式的线性规划问题：
Max z = - 3.6 x1 + 5.2 x2 - 1.8 x3
s.t,2.3x1+5.2x2-6.1x3+x4= 15.7
4.1x1+3.3x3-x5= 8.9
x1+x2+x3= 38
x1,x2,x3,x4,x5 ≥ 0
1.线性规划的概念
17
3,变量无符号限制的问题：
在标准形式中,必须每一个变量均有非负约束 。 当某一个变量 xj没有非负约束时,可以令
xj = xj’- xj”
其中
xj’≥ 0,xj”≥ 0
即用两个非负变量之差来表示一个无符号限制的变量,当然 xj的符号取决于 xj’和 xj”的大小 。
1.线性规划的概念
18
4.右端项有负值的问题：
在标准形式中,要求右端项必须每一个分量非负 。 当某一个右端项系数为负时,如 bi<0,则把该等式约束两端同时乘以 -1,得到：
-ai1 x1-ai2 x2- … -ain xn = -bi 。
1.线性规划的概念
19
例 2.3：将以下线性规划问题转化为标准形式
Min f= -3 x1 + 5 x2 + 8 x3 - 7 x4
s.t,2 x1 - 3 x2 + 5 x3 + 6 x4 ≤ 28
4 x1 + 2 x2 + 3 x3 - 9 x4 ≥ 39
6 x2 + 2 x3 + 3 x4 ≤ - 58
x1,x3,x4 ≥ 0
1.线性规划的概念
20
解：首先,将目标函数转换成极大化：
令 z = -f = 3x1–5x2–8x3+7x4 ；
其次考虑约束,有 3个不等式约束,引进松弛变量 x5,x6,x7 ≥ 0 ；
由于 x2无非负限制,可令 x2=x2’-x2”,
其中 x2’≥ 0,x2”≥ 0 ；
由于第 3个约束右端项系数为 -58，
于是把该式两端乘以 -1 。
于是,我们可以得到以下标准形式的线性规划问题：
1.线性规划的概念
21
Max z = 3x1–5x2’+5x2”–8x3 +7x4
s.t,2x1–3x2’+3x2”+5x3+6x4+x5= 28
4x1+2x2’-2x2”+3x3-9x4-x6= 39
-6x2’+6x2”-2x3-3x4-x7 = 58
x1,x2’,x2”,x3,x4,x5,x6,x7 ≥ 0
1.线性规划的概念
22
2.线性规划的图解法线性规划的图解法 (解的几何表示 )对于只有两个变量的线性规划问题,可以二维直角坐标平面上作图表示线性规划问题的有关概念,并求解 。 图解法求解线性规划问题的步骤如下：
(1)分别取决策变量 x1,x2 为坐标向量建立直角坐标系 。
23
2.线性规划的图解法
（ 2） 对每个约束 （ 包括非负约束 ）
条件,先取其等式在坐标系中作出直线,通过判断确定不等式所决定的半平面 。 各约束半平面交出来的区域
(存在或不存在 ）,若存在,其中的点表示的解称为此线性规划的可行解 。
这些符合约束限制的点集合,称为可行集或可行域 。 然后进行 （ 3） 。 否则该线性规划问题无可行解 。
24
2.线性规划的图解法
（ 3） 任意给定目标函数一个值作一条目标函数的等值线,并确定该等值线平移后值增加的方向,平移此目标函数的等值线,
使其达到既与可行域有交点又不可能使值再增加的位置 (有时交于无穷远处,此时称无有限最优解 ） 。 若有交点时,此目标函数等值线与可行域的交点即最优解
（ 一个或多个 ）,此目标函数的值即最优值 。
25
2.线性规划的图解法例 2.4:某工厂拥有 A,B,C三种类型的设备,生产甲,乙两种产品 。 每件产品在生产中需要占用的设备机时数,每件产品可以获得的利润以及三种设备可利用的时数如下表所示：
产品甲 产品乙 设备能力
（ h）
设备 A 3 2 65
设备 B 2 1 40
设备 C 0 3 75
利润（元 /件） 1500 2500
26
2.线性规划的图解法问题：工厂应如何安排生产可获得最大的总利润？ 用图解法求解 。
解：设变量 xi为第 i种 （ 甲,乙 ） 产品的生产件数 （ i＝ 1,2） 。 根据前面分析,可以建立如下的线性规划模型：
Max z = 1500 x1 + 2500 x2
s.t,3x1+2x2 ≤ 65 (A)
2x1+x2 ≤ 40 (B)
3x2 ≤ 75 (C)
x1,x2 ≥ 0 (D,E)
27
2.线性规划的图解法按照图解法的步骤在以决策变量 x1,x2 为坐标向量的平面直角坐标系上对每个约束
（ 包括非负约束 ） 条件作出直线,并通过判断确定不等式所决定的半平面 。 各约束半平面交出来的区域即可行集或可行域如下图阴影所示 。
28
2、线性规划的图解法图解法求解线性规划
29
2.线性规划的图解法任意给定目标函数一个值作一条目标函数的等值线,并确定该等值线平移后值增加的方向,平移此目标函数的等值线,使其达到既与可行域有交点又不可能使值再增加的位置,得到交点 (5,25)T,此目标函数的值为 70000。 于是,我们得到这个线性规划的最优解 x1=5、
x2=25,最优值 z = 70000。 即最优方案为生产甲产品 5件,乙产品 25件,
可获得最大利润为 70000元 。
30
2.线性规划的图解法例 2.5：在例 2.1的线性规划模型中,如果目标函数变为：
Max z = 1500 x1 + 1000 x2
那么,最优情况下目标函数的等值线与直线 （ A） 重合 。 这时,最优解有无穷多个,是从点 (5,25)T 到点
(15,10)T 线段上的所有点,最优值为
32500。 如下图所示：
31
2.线性规划的图解法无穷多解的情况
32
2.线性规划的图解法例 2.6：在例 2.1的线性规划模型中,
如果约束条件 （ A）,（ C） 变为,
3 x1 + 2 x2 ≥ 65 (A’）
3 x2 ≥ 75 (C’）
并且去掉 （ D,E） 的非负限制 。 那么,
可行域成为一个上无界的区域 。 这时,
没有有限最优解,如下图所示：
33
2.线性规划的图解法无有限解的情况
34
2、线性规划的图解法例 2.7：在例 2.1的线性规划模型中,
如果增加约束条件 （ F） 为：
x1 + x2 ≥ 40 （ F）
那么,可行域成为空的区域 。 这时,
没有可行解,显然线性规划问题无解 。 如下图所示：
35
2.线性规划的图解法无可行解的情况
36
根据以上例题，进一步分析讨论可知线性规划的可行域和最优解有以下几种可能的情况
1.可行域为封闭的有界区域
(a)有唯一的最优解；
(b)有无穷多个最优解；
2.可行域为封闭的无界区域
(c)有唯一的最优解；
2.线性规划的图解法
37
(d)有无穷多个最优解；
(e)目标函数无界 (即虽有可行解，
但在可行域中，目标函数可以无限增大或无限减少 )，因而没有有限最优解。
3.可行域为空集
(f)没有可行解，原问题无最优解
2.线性规划的图解法
38
以上几种情况的图示如下：
2.线性规划的图解法可行域有界 —唯一最优解 可行域有界 —多个最优解
39
2.线性规划的图解法可行域无界 —唯一最优解 可行域无界 —无穷多最优解
40
2.线性规划的图解法可行域无界 —目标函数无界 可行域为空集 —无可行解
41
可行解、可行解集（可行域）
最优解、最优值
基、基变量、非基变量
基本解、基本可行解
可行基、最优基熟悉下列一些解的概念
2.线性规划解的概念
42
线性规划的基、基本解与基本可行解在一般情况下，由于图解法无法解决三个变量以上的线性规划问题，对于 n个变量的线性规划问题，我们必须用解方程的办法来求得可行域的极点。再来进一步考察前例。
例 2.8 把例 2.1的线性规划模型标准化，
引入松驰变量 x3,x4,x5 ≥ 0,得到
2.线性规划解的概念
43
Max z = 1500 x1 + 2500 x2
s.t,3x1+2x2+x3= 65 (A)
2x1+x2+x4= 40 (B)
3x2+x5= 75 (C)
x1,x2,x3,x4,x5 ≥ 0
用（ D）（ E）（ F）（ G）（ H）
分别表示 x1 = 0,x2 = 0,x3 = 0、
x4 = 0,x5 = 0 。
这里一共有 8个约束条件，其中 3个等式约束
2.线性规划解的概念
44
（一般情况下，等式约束的个数少于决策变量的个数）,5个变量非负约束（与决策变量个数相同）。每 5个方程若线性无关可解得一个点，我们可以看到前例图解法得到的区域中每两条直线的交点与此例的各个方程有如下关系：见下图。
2.线性规划解的概念
45
2.线性规划解的概念平面上各不等式约束半平面得交点
46
由上图可以看出：
直线 A,B的交点对应于约束条件 (A),（ B）,
（ C）,（ F）,（ G） 的解,即：
x(1) = (15,10,0,0,45)T
直线 A,C的交点对应于约束条件 (A),（ B）,
（ C）,（ F）,（ H） 的解,即：
x(2) = (5,25,0,5,0)T
直线 A,D的交点对应于约束条件 (A),（ B）,
（ C）,（ D）,（ F） 的解,即：
x(3) = (0,32.5,0,7.5,-22.5)T
2.线性规划解的概念
47
直线 A,E的交点对应于约束条件 (A),（ B）,
（ C）,（ E）,（ F） 的解,即：
x(4) = (65/3,0,0,-10/3,75)T
直线 B,C的交点对应于约束条件 (A),（ B）,
（ C）,（ G）,（ H） 的解,即：
x(5) = (7.5,25,-7.5,0,0)T
直线 B,D的交点对应于约束条件 (A),（ B）,
（ C）,（ D）,（ G） 的解,即：
x(6) = (0,40,-15,0,-45)T
2.线性规划解的概念
48
直线 B,E的交点对应于约束条件 (A),（ B）,
（ C）,（ E）,（ G） 的解,即：
x(7) = (20,0,5,0,75)T
直线 C,D的交点对应于约束条件 (A),（ B）,
（ C）,（ D）,（ H） 的解,即：
x(8) = (0,25,15,15,0)T
直线 C,E无交点 （ C,E相互平行 ）
直线 D,E的交点对应于约束条件 (A),（ B）,
（ C）,（ D）,（ E） 的解,即：
x(9) = (0,0,65,40,75)T
2.线性规划解的概念
49
上图各约束直线的交点是由以下方法得到：在标准化的等式约束中,令其中某两个变量为零,得到其他变量的唯一解,
这个解就是相应交点的坐标,如果某一交点的坐标 (x1,x2,x3,x4,x5 )T全为非负,则该交点就对应于线性规划可行域的一个极点 （ 如 A,B,A,C,B,E,C,D
和 D,E的交点 ） ；如果某一交点的坐标中至少有一个分量为负值 （ 如 A,D,A,E，
B,C和 B,D的交点 ）,则该交点不是可行域的极点 。
2.线性规划解的概念
50
由上图可知,A,B交点对应于 x3 = 0，
x4 = 0，在等式约束中令 x3 = 0,x4 = 0，得到 x1 =15,x2 = 10,x5 = 45。即 A,B交点对应于极点 x= (x1,x2,x3,x4,x5)T =(15，
10,0,0,45)T。由于所有分量都为非负，
因此 A,B交点是可行域的极点。又知,B,C
交点对应于 x4= 0,x5= 0，在等式约束中令
x4 = 0,x5 = 0，得到 x1 =7.5,x2 = 25,x3 =
-7.5。即 B,C交点对应于点 x = (x1,x2,
x3,x4,,x5)T=(-7.5,25,-7.5,0,0)T。
由于有负分量，因此 B,C交点不是可行域的极点。我们同样可以讨论其他交点的情况。
2.线性规划解的概念
51
下面讨论线性规划标准形式的基、基本解、基本可行解的概念。
考虑线性规划标准形式的约束条件：
Ax=b,x≥ 0
其中 A为 m× n的矩阵,n>m,秩 (A) = m，
b? Rm 。 在约束等式中,令 n维空间的解向量：
x = (x1,x2,…,xn)T
2.线性规划解的概念
52
中 n-m个变量为零，如果剩下的 m个变量在线性方程组中有唯一解，则这 n个变量的值组成的向量 x就对应于 n维空间 Rn中若干个超平面的一个交点。当这 n个变量的值都是非负时，这个交点就是线性规划可行域的一个极点。
根据以上分析,我们建立以下概念：
（ 1） 线性规划的 基,对于线性规划的约束条件
Ax=b,x≥ 0
2.线性规划解的概念
53
设 B是 A矩阵中的一个非奇异（可逆）的
m× m子矩阵，则称 B为线性规划的一个 基 。
用前文的记号,A=( p1,p2,…,pn ),
其中 pj=( a1j,a2j,…,amj )T? Rm,
任取 A中的 m个线性无关列向量 pj? Rm
构成矩阵 B=( pj1,pj2,…,pjm )。那么 B为线性规划的一个 基 。
我们称对应于基 B的变量 xj1,
xj2,…,xjm为 基变量 ；而其他变量称为非基变量 。
2.线性规划解的概念
54
可以用矩阵来描述这些概念 。
设 B是线性规划的一个基,则 A可以表示为
A=[ B,N ]
x也可相应地分成
xB
x=
xN
其中 xB为 m维列向量,它的各分量称为 基变量,
与基 B的列向量对应； xN为 n-m列向量,它的各分量称为 非基变量,与非基矩阵 N的列向量对应 。
这时约束等式 Ax=b可表示为
2.线性规划解的概念
55
xB
B,N = b
xN
或
BxB + NxN = b
如果对非基变量 xN取确定的值,则 xB有唯一的值与之对应
xB = B-1b - B-1NxN
特别,当取 xN = 0,这时有 xB=B-1b。 关于这类特别的解,有以下概念 。
2.线性规划解的概念
56
（ 2）线性规划问题的 基本解,基本可行解 和 可行基,
对于线性规划问题,设矩阵 B =
( pj1,pj2,…,pjm ) 为一个基,令所有非基变量为零,可以得到 m个关于基变量 xj1,xj2,…,xjm的线性方程,
解这个线性方程组得到基变量的值 。
我们称这个解为一个 基本解 ；若得到的基变量的值均非负,则称为 基本可行解,同时称这个基 B为 可行基 。
2.线性规划解的概念
57
矩阵描述为，对于线性规划的解
xB B-1b
x= =
xN 0
称为线性规划与基 B对应的基本解 。 若其中 B-1b?0,则称以上的基本解为一基本可行解,相应的基 B称为可行基 。
2.线性规划解的概念
58
我们可以证明以下结论,线性规划的基本可行解就是可行域的极点 。
这个结论被称为线性规划的基本定理,它的重要性在于把可行域的极点这一几何概念与基本可行解这一代数概念联系起来,因而可以通过求基本可行解的线性代数的方法来得到可行域的一切极点,从而有可能进一步获得最优极点 。
2.线性规划解的概念
59
例 2.9,考虑例 2.8的线性规划模型
Max z = 1500 x1 + 2500 x2
s.t,3 x1 + 2 x2 + x3 = 65
2 x1 + x2 + x4 = 40
3 x2 + x5 = 75
x1,x2,x3,x4,x5 ≥ 0
注意,线性规划的基本解,基本可行解 （ 极点 ） 和可行基只与线性规划问题标准形式的约束条件有关 。
2.线性规划解的概念
60
3 2 1 0 0
A = [P1,P2,P3,P4,P5] = 2 1 0 1 0
0 3 0 0 1
A矩阵包含以下 10个 3× 3的子矩阵：
B1=[p1,p2,p3] B2=[p1,p2,p4]
B3=[p1,p2,p5] B4=[p1,p3,p4]
B5=[p1,p3,p5] B6=[p1,p4,p5]
B7=[p2,p3,p4] B8=[p2,p3,p5]
B9=[p2,p4,p5] B10=[p3,p4,p5]
2.线性规划解的概念
61
其中?B4?= 0,因而 B4不是该线性规划问题的基 。
其余均为非奇异方阵,因此该问题共有 9个基 。
对于基 B3=[p1,p2,p5],令非基变量 x3 = 0，
x4 = 0,在等式约束中令 x3 = 0,x4 = 0,解线性方程组：
3 x1 + 2 x2 + 0 x5 = 65
2 x1 + x2 + 0 x5 = 40
0 x1 + 3 x2 + x5 = 75
得到 x1 =15,x2 = 10,x5 = 45,对应的基本可行解：
x=(x1,x2,x3,x4,x5)T=(15,10,0,0，
45)T。 于是对应的基 B3是一个可行基 。
2.线性规划解的概念
62
类似可得到
x(2) = (5,25,0,5,0)T （ 对应 B2）
x(7) = (20,0,5,0,75)T （ 对应 B5）
x(8) = (0,25,15,15,0)T （ 对应 B7）
x(9) = (0,0,65,40,75)T （ 对应 B10）
是基本可行解；
而 x(3)= (0,32.5,0,7.5,-22.5)T（ 对应 B9）
x(4)= (65/3,0,0,-10/3,75)T （ 对应 B6）
x(5)= (7.5,25,-7.5,0,0)T （ 对应 B1）
x(6) = (0,40,-15,0,-45)T （ 对应 B8）
是基本解 。
2.线性规划解的概念
63
因此,对应基本可行解 （ 极点 ） 的 B2
B3 B5 B7 B10都是可行基 。
这里指出了一种求解线性规划问题的可能途径,就是先确定线性规划问题的基,
如果是可行基,则计算相应的基本可行解以及相应解的目标函数值 。 由于基的个数是有限的 （ 最多个 ）,因此必定可以从有限个基本可行解中找到最优解 。
2.线性规划解的概念
64
利用求解线性规划问题基本可行解 （ 极点 ） 的方法来求解较大规模的问题是不可行的 。 单纯形法的基本思路是有选择地取基本可行解,即是从可行域的一个极点出发,沿着可行域的边界移到另一个相邻的极点,要求新极点的目标函数值不比原目标函数值差 。
3.单 纯 形 法
65
由上节的讨论可知,对于线性规划的一个基,当非基变量确定以后,基变量和目标函数的值也随之确定 。 因此,一个基本可行解向另一个基本可行解的移动,以及移动时基变量和目标函数值的变化,可以分别由基变量和目标函数用非基变量的表达式来表示 。
同时,当可行解从可行域的一个极点沿着可行域的边界移动到一个相邻的极点的过程中,
所有非基变量中只有一个变量的值从 0开始增加,而其他非基变量的值都保持 0不变 。
3.单 纯 形 法
66
3.单 纯 形 法初始基本可行解是否最优解或无限最优解?
结束沿边界找新的基本可行解
N
Y
单纯形法的基本过程
67
考虑标准形式的线性规划问题：
Max z = c1x1 + c2x2 + … + cnxn
s.t,a11 x1 + a12 x2 + … + a1n xn = b1
a21 x1 + a22 x2 + … + a2n xn = b2..
.
am1 x1 + am2 x2 + … + amn xn = bm
x1,x2,…,xn ≥ 0
x1 c1 b1 a11 a12..a1n
x2 c2 b2 a21 a22..a2n
x=,C=,B=,A=,,,
.,,,,,
xn cn bn am1 am2..amn
3.单 纯 形 法
68
这里,矩阵 A表示为：
A = ( p1,p2,…,pn ),
其中 pj = ( a1j,a2j,…,amj )T? Rm。
若找到一个可行基,无防设
B = ( p1,p2,…,pm ),则 m个基变量为 x1,x2,…,xm,n-m个非基变量为
xm+1,xm+2,…,xn 。 通过运算,所有的基变量都可以用非基变量来表示：
3.单 纯 形 法
69
3.单 纯 形 法
x1=b’1-（ a’1m+1xm+1+a’1m+2xm+2+…+a’1nxn）
x2=b’2-（ a’2m+1xm+1+a’2m+2xm+2+…+a’2nxn） ( 2-11 ).`
..
xm=b’m-（ a’mm+1xm+1+a’mm+2xm+2+…+a’mnxn）
把它们代入目标函数,得
z = z’+?m+1xm+1+?m+2xm+2+…+?nxn ( 2-12 )
其中
j=cj-（ c1a’1j + c2a’2j + … + cm a’mj）
我们把由非基变量表示的目标函数形式称为基
B相应的目标函数 典式 。
70
单纯形法的基本步骤可描述如下：
（ 1） 寻找一个初始的可行基和相应基本可行解 （ 极点 ）,确定基变量,
非基变量以及基变量,非基变量 （ 全部等于 0） 和目标函数的值,并将目标函数和基变量分别用非基变量表示；
3.单 纯 形 法
71
（ 2） 在用非基变量表示的目标函数表达式 （ 2-12） 中,我们称非基变量 xj的系数 （ 或其负值 ） 为检验数记为
j 。 若?j > 0,那么相应的非基变量
xj,它的值从当前值 0开始增加时,目标函数值随之增加 。 这个选定的非基变量 xj称为,进基变量,,转 （ 3） 。
如果任何一个非基变量的值增加都不能使目标函数值增加,即所有?j 非正,
则当前的基本可行解就是最优解,计算结束；
3.单 纯 形 法
72
（ 3） 在用非基变量表示的基变量的表达式 （ 2-11） 中,观察进基变量增加时各基变量变化情况,确定基变量的值在进基变量增加过程中首先减少到 0的变量 xr,满足,
=min?b’i /a’ij?a’ij > 0? = b’r /a’rj
这个基变量 xr称为,出基变量,。 当进基变量的值增加到? 时,出基变量
xr的值降为 0时,可行解就移动到了相邻的基本可行解 （ 极点 ）,转 （ 4） 。
3.单 纯 形 法
73
如果进基变量的值增加时,所有基变量的值都不减少,即所有 a’ij 非正,则表示可行域是不封闭的,且目标函数值随进基变量的增加可以无限增加,此时,
不存在有限最优解,计算结束；
（ 4） 将进基变量作为新的基变量,
出基变量作为新的非基变量,确定新的基,新的基本可行解和新的目标函数值 。
在新的基变量,非基变量的基础上重复
（ 1） 。
3.单 纯 形 法
74
例 2.10：用单纯形法的基本思路解例 2.8的线性规划问题
Max z = 1500 x1 + 2500 x2
s.t,3 x1 + 2 x2 + x3 = 65
2 x1 + x2 + x4 = 40
3 x2 + x5 = 75
x1,x2,x3,x4,x5 ≥ 0
3.单 纯 形 法
75
第一次迭代：
（ 1） 取初始可行基 B10= (p3,p4,p5)，
那么 x3,x4,x5为基变量,x1,x2为非基变量 。 将基变量和目标函数用非基变量表示：
z=1500x1+2500x2
x3 = 65 - 3 x1 - 2 x2
x4 = 40 - 2 x1 - x2
x5 = 75 - 3 x2
当非基变量 x1,x2=0时,相应的基变量和目标函数值为 x3=65,x4=40,x5= 75，
z = 0,得到当前的基本可行解：
x=(0,0,65,40,75)T,z = 0 。 这个解对应于图 2-7的 D,E交点 。
3.单 纯 形 法
76
（ 2） 选择进基变量 。 在目标函数
z = 1500 x1 + 2500 x2中,非基变量 x1，
x2的系数都是正数,因此 x1,x2进基都可以使目标函数 z增大,但 x2的系数为
2500,绝对值比 x1的系数 1500大,因此把 x2作为进基变量可以使目标函数 z增加更快 。 选择 x2为进基变量,使 x2的值从 0
开始增加,另一个非基变量 x1保持零值不变 。
3.单 纯 形 法
77
（ 3） 确定出基变量 。 在约束条件
x3 = 65 - 3 x1 - 2 x2
x4 = 40 - 2 x1 - x2
x5 = 75 - 3 x2
中,由于进基变量 x2在 3个约束条件中的系数都是负数,当 x2的值从 0开始增加时,
基变量 x3,x4,x5的值分别从当前的值
65,40和 75开始减少,当 x2增加到 25时,
x5首先下降为 0成为非基变量 。 这时,新的基变量为 x3,x4,x2,新的非基变量为 x1,x5,当前的基本可行解和目标函数值为：
x = (0,25,15,15,0)T,z = 62500。
这个解对应于图中的 C,D交点 。
3.单 纯 形 法
78
第二次迭代：
（ 1） 当前的可行基为 B7 = (p2,p3,
p4),那么 x2,x3,x4为基变量,x1,x5
为非基变量 。 将基变量和目标函数用非基变量表示：
z = 62500 + 1500 x1 – (2500/3) x5
x2 = 25 – (1/3) x5
x3 = 15 - 3 x1 + (2/3) x5
x4 = 15 - 2 x1 + (1/3) x5
3.单 纯 形 法
79
（ 2） 选择进基变量 。 在目标函数
z = 62500 + 1500 x1 – (2500/3) x5
中,非基变量 x1的系数是正数,因此
x1进基可以使目标函数 z增大,于是选择 x1进基,使 x1的值从 0开始增加,另一个非基变量 x5保持零值不变 。
(3)确定出基变量 。 在约束条件
x2 = 25 – (1/3) x5
x3 = 15 - 3 x1 + (2/3) x5
x4 = 15 - 2 x1 + (1/3) x5
3.单 纯 形 法
80
中,由于进基变量 x1在两个约束条件中的系数都是负数,当 x1的值从 0开始增加时,基变量 x3,x4的值分别从当前的值 15,15开始减少,当 x1增加到 5
时,x3首先下降为 0成为非基变量 。 这时,新的基变量为 x1,x2,x4,新的非基变量为 x3,x5,当前的基本可行解和目标函数值为：
x = (5,25,0,5,0)T,z = 70000。
这个解对应于图中的 A,C交点 。
3.单 纯 形 法
81
第三次迭代：
（ 1） 当前的可行基为 B2 = (p1,
p2,p4 ),那么 x1,x2,x4为基变量,x3,x5为非基变量 。 将基变量和目标函数用非基变量表示：
z = 70000 – 500 x3 – 500 x5
x1 = 5 – (1/3) x3 + (2/9) x5
x2 = 25 – (1/3) x5
x4 = 5 + (2/3) x3 – (1/9) x5
3.单 纯 形 法
82
（ 2） 选择进基变量 。 在目标函数
z = 70000 – 500 x3 – 500 x5 中,非基变量 x3,x5的系数均不是正数,因此进基都不可能使目标函数 z增大,于是得到最优解,x* = (5,25,0,5，
0)T,最优目标值为 z* = 70000。 这个解对应于图 2-7的 A,C交点 。 我们也称相应的基 B2 = (p1,p2,p4)为 最优基 。
计算结束 。
3.单 纯 形 法
83
3,单 纯 形 法
表格单纯形法
考虑,bi > 0 i = 1,…,m
Max z = c1 x1 + c2 x2 + … + c n xn
s.t,a11 x1 + a12 x2 + … + a1n xn ≤ b1
a21 x1 + a22 x2 + … + a2n xn ≤ b2
…… ……
am1 x1 + am2 x2 + … + amn xn ≤ bm
x1,x2,…,xn ≥ 0
84
3,单 纯 形 法
加入松弛变量：
Max z = c1 x1 + c2 x2 + … + c n xn
s.t,a11 x1 + a12 x2 + … + a1n xn + xn+1 = b1
a21 x1 + a22 x2 + … + a2n xn + xn+2 = b2
…… ……
am1 x1 + am2 x2 + … + amn xn+ xn+m = bm
x1,x2,…,xn,xn+1,…,xn+m ≥ 0
85
显然,xj= 0 j = 1,…,n ; xn+i = bi i = 1,…,m 是基本可行解对应的基是单位矩阵。
以下是初始单纯形表：
m m
其中,f = -∑ cn+i bi?j = cj -∑ cn+i aij 为检验数 cn+i = 0 i= 1,…,m
i = 1 i = 1
an+i,i = 1,an+i,j = 0 ( j≠i ) i,j = 1,…,m
3,单 纯 形 法
c 1 … c n c n+ 1 … c n+ m
C B X B
x 1 … x n x n+ 1 … x n+ m θ i
c n+ 1 x n+ 1 b 1 a 11 … a 1n a 1n + 1 … a 1n + m θ
1
c n+ 2 x n+ 2 b 2 a 21 … a 2n a 2n + 1 … a 2n + m θ
2
┇ ┇ ┇ ┇ ┇ ┇ ┇ ┇ ┇ ┇
c n+ m x n+ m b m a m1 … a mn a m n+ 1 … a m n+ m θ
m
- z f σ
1 … σ n 0 … 0
86
3,单 纯 形 法
1500
2500
0 0
0
C
B
X
B
x
1
X
2
x
3
x
4
x
5 θ i
0 x
3
65 3 2 1 0 0 32,5
0 x
4
40 2 1 0 1 0 40
0 x
5
75 0 ( 3) 0 0 1 25
- z 0 1500 2500* 0 0 0
0 x
3
15 ( 3) 0 1 0 - 2/3 5
0 x
4
15 2 0 0 1 - 1/3 7,5
25 00 x
2
25 0 1 0 0 1/3
- z - 62500 1500* 0 0 0 - 2500/3
1 5 0 0 x
1
5 1 0 1/3 0 - 2/ 9
0 x
4
5 0 0 - 2/3 1 1/9
25 00 x
2
25 0 1 0 0 1/3
- z - 70000 0 0 - 500 0 - 500
例 2.10。化标准形式,Max z =1500 x1 + 2500 x2
s.t,3 x1 + 2 x2 + x3 = 65
2 x1 + x2 + x4 = 40
3 x2 + x5 = 75
x1,x2,x3,x4,x5 ≥ 0
最优解 x1 = 5 x2 = 25 x4 = 5（松弛标量，表示 B设备有 5个机时的剩余）
最优值 z* = 70000
87
注意：单纯形法中，
1、每一步运算只能用矩阵初等行变换；
2、表中第 3列的数总应保持非负
（ ≥ 0）；
3、当所有检验数均非正（ ≤ 0）
时，得到最优单纯形表。
3,线 性 规 划
88
一般情况的处理及注意事项的强调：主要是讨论初始基本可行解不明显时，常用的方法。要弄清它的原理，并通过例题掌握这些方法，同时进一步熟悉用单纯形法解题。
考虑一般问题：
bi > 0 i = 1,…,m
3.单 纯 形 法
89
Max z = c1x1 + c2x2 + … + cnxn
s.t.
a11x1+a12x2 +…+a1nxn = b1
a21x1+a22x2 +…+a2nxn = b2.
.,
am1x1+am2x2+…+amnxn = bm
x1,x2,…,xn ≥ 0
3.单 纯 形 法
90
大 M法：
引入人工变量 xn+i ≥ 0 （ i = 1,…,
m）及充分大正数 M 。得到：
Max
z = c1x1 +c2x2 +…+cnxn -Mxn+1 -…-Mxn+m
s.t.
a11 x1 + a12 x2 + … + a1n xn + xn+1 = b1
a21 x1 + a22 x2 + … + a2n xn + xn+2 = b2.
.,
am1 x1 + am2 x2 + … + amn xn + xn+m = bm
x1,x2,…,xn,xn+1,…,xn+m≥ 0
3.单 纯 形 法
91
显然,xj = 0 j=1,…,n ;
xn+i = bi i =1,…,m
是基本可行解。
对应的基是单位矩阵。
结论,若得到的最优解满足
xn+i = 0 i = 1,…,m 则是原问题的最优解；否则，原问题无可行解。
3.单 纯 形 法
92
两阶段法：
引入人工变量 xn+i ≥ 0,i = 1,…,m；
构造,
Max z = - xn+1 - xn+2 - … - xn+m
s.t.
a11x1+a12x2+ … +a1nxn+xn+1 = b1
a21x1+a22x2+ … +a2nxn+xn+2 = b2.
..
am1x1+am2x2+ … +amnxn+xn+m = bm
x1,x2,.,xn,xn+1,…,xn+m ≥ 0
3.单 纯 形 法
93
第一阶段求解上述问题：
显然,xj = 0 j=1,…,n ;
xn+i = bi i =1,…,m
是基本可行解,它对应的基是单位矩阵。
结论,若得到的最优解满足 xn+i=0
i=1,…,m 则是原问题的基本可行解 ;否则，原问题无可行解。
得到原问题的基本可行解后，第二阶段求解原问题。
3.单 纯 形 法
94
例 2.11：（ LP）
Max z = 5x1 + 2x2 + 3x3 - x4
s.t,x1 + 2x2 + 3x3 = 15
2x1 + x2 + 5x3 = 20
x1 + 2x2 + 4x3 + x4 = 26
x1,x2,x3,x4 ≥ 0
3.单 纯 形 法
95
Max z = 5x1+2x2+3x3-x4-Mx5-Mx6
s.t,x1+2x2+3x3+x5 =15
2x1+x2+5x3+x6 =20
x1+2x2+4x3+x4 =26
x1,x2,x3,x4,x5,x6 ≥ 0
3.单 纯 形 法
96
5
2
3 - 1 - M
- M
C
B
X
B
x
1
x
2
x
3
x
4
x
5
x
6 θ i
- M x
5
15 1 2 3 0 1 0 5
- M x
6
20 2 1 ( 5) 0 0 1 4
- 1 x
4
26 1 2 4 1 0 0 6.5
- z 35M + 26 3M + 6 3M + 4 8M + 7 0 0 0
- M x
5
3 - 1/ 5 ( 7/ 5) 0 0 1 - 3/ 5 15/ 7
3 x
3
4 2/ 5 1/ 5 1 0 0 1/ 5 20
- 1 x
4
10 - 3/ 5 6/ 5 0 1 0 - 4/ 5 25/ 3
- z 3M - 2 - M / 5+ 16/ 5 7/ 5M + 13/ 5 0 0 0 - 8/ 5M - 7/ 5
2 x
2
15/ 7 - 1/ 7 1 0 0 5/ 7 - 3/ 7
3 x
3
25/ 7 ( 3/ 7) 0 1 0 - 1/ 7 2/ 7 25/ 3
- 1 x
4
52/ 7 - 3/ 7 0 0 1 - 6/ 7 - 2/ 7
- z - 53/ 7 25/ 7 0 0 0 - M - 13/ 7 - M - 2/ 7
2 x
2
10/ 3 0 1 1/ 3 0 2/ 3 - 1/ 3
5 x
1
25/ 3 1 0 7/ 3 0 - 1/ 3 2/ 3
- 1 x
4
11 0 0 1 1 - 1 0
- z - 1 12/ 3 0 0 - 25/ 3 0 - M - 2/ 3 - M + 8/ 3
大 M法 （ LP - M）
得到 最优解,(25/3,10/3,0,11)T
最优目标值,112/3
3.单 纯 形 法
97
第一阶段问题（ LP - 1）
Max z = - x5 - x6
s.t,x1 + 2x2 + 3x3 + x5 = 15
2x1 + x2 + 5x3 + x6 = 20
x1 + 2x2 + 4x3 + x4 = 26
x1,x2,x3,x4,x5,x6 ≥ 0
3.单 纯 形 法
98
0 0 0 0 -1 -1
C
B
X
B
x
1
x
2
x
3
x
4
x
5
x
6
θ
i
-1 x
5
15 1 2 3 0 1 0 5
-1 x
6
20 2 1 ( 5 ) 0 0 1 4
0 x
4
26 1 2 4 1 0 0 6,5
-z 35 3 3 8 0 0 0
-1 x
5
3 - 1 / 5 ( 7 / 5 ) 0 0 1 - 3 / 5 1 5 / 7
0 x
3
4 2 / 5 1 / 5 1 0 0 1 / 5 20
0 x
4
10 - 3 / 5 6 / 5 0 1 0 - 4 / 5 2 5 / 3
-z 3 - 1 / 5 7 / 5 0 0 0 - 8 / 5
0 x
2
1 5 / 7 - 1 / 7 1 0 0 5 / 7 - 3 / 7
0 x
3
2 5 / 7 3 / 7 0 1 0 - 1 / 7 2 / 7 2 5 / 3
0 x
4
5 2 / 7 - 3 / 7 0 0 1 - 6 / 7 - 2 / 7
-z 0 0 0 0 0 -1 -1
第一阶段 (LP - 1）
得到原问题的基本可行解,
(0,15/7,25/7,52/7)T
3.单 纯 形 法
99
5 2 3 -1
C
B
X
B
x
1
x
2
x
3
x
4
θ
i
2 x
2
15 / 7 - 1/ 7 1 0 0
3 x
3
25 / 7 ( 3/ 7) 0 1 0 25 / 3
-1 x
4
52 / 7 - 3/ 7 0 0 1
-z - 53 / 7 25 / 7 0 0 0
2 x
2
10 / 3 0 1 1/ 3 0
5 x
1
25 / 3 1 0 7/ 3 0
-1 x
4
11 0 0 1 1
-z - 1 12 / 3 0 0 - 25 / 3 0
第二阶段 把基本可行解填入表中
得到原问题的最优解,(25/3,10/3,0,11)T
最优目标值,112/3
3.单 纯 形 法
100
注意,单纯形法中
1、每一步运算只能用矩阵初等行变换；
2、表中第 3列 (b列 )的数总应保持非负
（ ≥ 0）；
3、当所有检验数均非正（ ≤ 0）时，得到最优单纯形表。若直接对目标求最 h，要求 所有检验数均非负；
4,当最优单纯形表存在非基变量对应的检验数为零时,可能存在无穷多解；
3.单 纯 形 法
101
5、关于退化和循环。如果在一个基本可行解的基变量中至少有一个分量
xBi=0 (i=1,2,…,m)，则称此基本可行解是退化的基本可行解。一般情况下，退化的基本可行解（极点）是由若干个不同的基本可行解（极点）在特殊情况下合并成一个基本可行解（极点）而形成的。退化的结构对单纯形迭代会造成不利的影响。
3.单 纯 形 法
102
可能出现以下情况,① 进行进基,出基变换后,虽然改变了基,但没有改变基本可行解 （ 极点 ）,目标函数当然也不会改进 。 进行若干次基变换后,才脱离退化基本可行解 （ 极点 ）,进入其他基本可行解 （ 极点 ） 。 这种情况会增加迭代次数,
使单纯形法收敛的速度减慢 。 ② 在特殊情况下,退化会出现基的循环,一旦出现这样的情况,单纯形迭代将永远停留在同一极点上,因而无法求得最优解 。
3.单 纯 形 法
103
在单纯形法求解线性规划问题时，一旦出现这种因退化而导致的基的循环，单纯形法就无法求得最优解，这是一般单纯形法的一个缺陷。但是实际上，尽管退化的结构是经常遇到的，而循环现象在实际问题中出现得较少。尽管如此，人们还是对如何防止出现循环作了大量研究。 1952
年 Charnes提出了,摄动法,,1954年
Dantzig,Orden和 Wolfe又提出了,字典序法,,
3.单 纯 形 法
104
这些方法都比较复杂，同时也降低了迭代的速度。 1976年,Bland提出了一个避免循环的新方法，其原则十分简单。仅在选择进基变量和出基变量时作了以下规定：① 在选择进基变量时，在所有?j >
0的非基变量中选取下标最小的进基；②
当有多个变量同时可作为出基变量时，选择下标最小的那个变量出基。这样就可以避免出现循环,当然，这样可能使收敛速度降低。
3.单 纯 形 法
105
合理利用线材问题,如何下料使用材最少。
配料问题,在原料供应量的限制下如何获取最大利润。
投资问题,从投资项目中选取方案，使投资回报最大。
4.线性规划应用一、线性规划 ---
106
产品生产计划,合理利用人力、物力、财力等，使获利最大。
劳动力安排,用最少的劳动力来满足工作的需要。
运输问题,如何制定调运方案，使总运费最小。
4.线性规划应用
107
数学规划的建模有许多共同点,
要遵循下列原则：
(1)容易理解 。 建立的模型不但要求建模者理解,还应当让有关人员理解 。 这样便于考察实际问题与模型的关系,使得到的结论能够更好地应用于解决实际问题 。
(2)容易查找模型中的错误 。 这个原则的目的显然与 (1)相关 。 常出现的错误有：书写错误和公式错误 。
4.线性规划应用
108
(3)容易求解 。 对线性规划来说,
容易求解问题主要是控制问题的规模,包括决策变量的个数和约束条件的个数 。 这条原则的实现往往会与 (1)发生矛盾,在实现时需要对两条原则进行统筹考虑 。
4.线性规划应用
109
建立线性规划模型的过程可以分为四个步骤：
(1)设立决策变量；
(2)明确约束条件并用决策变量的线性等式或不等式表示；
(3)用决策变量的线性函数表示目标,并确定是求极大 （ Max） 还是极小 （ Min） ；
(4)根据决策变量的物理性质研究变量是否有非负性 。
4.线性规划应用
110
例 2.12,某昼夜服务的公交线路每天各时间段内所需司机和乘务人员数如下：
班次 时间 所需人数
1 6,00 —— 10,00 60
2 10,00 —— 14,00 70
3 14,00 —— 18,00 60
4 18,00 —— 22,00 50
5 22,—— 2,00 20
6 2,00 —— 6,00 30
人力资源分配的问题设司机和乘务人员分别在各时间段一开始时上班，并连续工作 8h，问该公交线路怎样安排司机和乘务人员，既能满足工作需要，又配备最少司机和乘务人员?
111
解：设 xi 表示第 i班次时开始上班的司机和乘务人员数,这样我们建立如下的数学模型。
目标函数,Min x1 + x2 + x3 + x4 + x5 + x6
约束条件,s.t,x1 + x6 ≥ 60
x1 + x2 ≥ 70
x2 + x3 ≥ 60
x3 + x4 ≥ 50
x4 + x5 ≥ 20
x5 + x6 ≥ 30
x1,x2,x3,x4,x5,x6 ≥ 0
人力资源分配的问题
112
例 2.13:某工厂要做 100套钢架，每套用长为 2.9 m,
2.1m,1.5m的圆钢各一根。已知原料每根长 7.4 m，
问：应如何下料，可使所用原料最省？
方案 1 方案 2 方案 3 方案 4 方案 5 方案 6 方案 7 方案 8
2.9 m 1 2 0 1 0 1 0 0
2.1 m 0 0 2 2 1 1 3 0
1.5 m 3 1 2 0 3 1 0 4
合计 7.4 7.3 7.2 7.1 6.6 6,5 6,3 6.0
剩余料头 0 0.1 0.2 0.3 0.8 0.9 1,1 1,4
套裁下料问题解,考虑下列各种下料方案（按一种逻辑顺序给出）
方案 1 方案 2 方案 3 方案 4 方案 5 方案 6 方案 7 方案 8
2.9 m 2 1 1 1 0 0 0 0
2.1 m 0 2 1 0 3 2 1 0
1.5 m 1 0 1 3 0 2 3 4
合计 7.3 7.1 6,5 7.4 6,3 7.2 6.6 6.0
剩余料头 0.1 0.3 0.9 0 1,1 0.2 0.8 1,4
把各种下料方案按剩余料头从小到大顺序列出
113
假设 x1,x2,x3,x4,x5 分别为上面前 5 种方案下料的原材料根数。我们建立如下的数学模型。
目标函数：
Min x1 + x2 + x3 + x4 + x5
约束条件：
s.t,x1 + 2x2 + x4 ≥ 100
2x3 + 2x4 + x5 ≥ 100
3x1 + x2 + 2x3+ 3x5 ≥ 100
x1,x2,x3,x4,x5 ≥ 0
套裁下料问题方案 1 方案 2 方案 3 方案 4 方案 5
2.9 m 1 2 0 1 0
2.1 m 0 0 2 2 1
1.5 m 3 1 2 0 3
合计 7.4 7.3 7.2 7.1 6.6
剩余料头 0 0.1 0.2 0.3 0.8
114
例 2.14:明兴公司生产甲、乙、
丙三种产品，都需要经过铸造、机加工和装配 三个车间。甲、乙两种产品的铸件可以外包协作，亦可以自行生产，但产品丙必须本厂铸造才能保证质量。数据如下表。问：公司为了获得最大利润，甲、乙、丙三种产品各生产多少件？甲、乙两种产品的铸造中，由本公司铸造和由外包协作各应多少件？
生产计划的问题
115
甲 乙 丙 资源限制铸造工时 ( 小时 / 件 ) 5 10 7 8000
机加工工时 ( 小时 / 件 ) 6 4 8 12000
装配工时 ( 小时 / 件 ) 3 2 2 10000
自产铸件成本 ( 元 / 件 ) 3 5 4
外协铸件成本 ( 元 / 件 ) 5 6 --
机加工成本 ( 元 / 件 ) 2 1 3
装配成本 ( 元 / 件 ) 3 2 2
产品售价 ( 元 / 件 ) 23 18 16
解,设 x1,x2,x3 分别为三道工序都由本公司加工的甲、乙、丙三种产品的件数,x4,x5 分别为由外协铸造再由本公司机加工和装配的甲、乙两种产品的件数。
生产计划的问题
116
求 xi 的利润,利润 = 售价 - 各成本之和 可得到 xi（ i=1,2,3,4,5）的利润分别为 15,10,7,13,9元。
这样我们建立如下数学模型：
目标函数,Max 15x1+10x2+7x3+13x4+9x5
约束条件：
s.t,5x1+10x2+7x3 ≤ 8000
6x1+4x2+8x3+6x4+4x5 ≤12000
3x1+2x2+2x3+3x4+2x5 ≤ 10000
x1,x2,x3,x4,x5 ≥ 0
生产计划的问题
117
例 2.15:永久机械厂生产 Ⅰ,Ⅱ,Ⅲ 三种产品，均要经过 A,B 两道工序加工。假设有两种规格的设备 A1,A2能完成 A 工序；
有三种规格的设备 B1,B2,B3能完成 B 工序。 Ⅰ 可在 A,B的任何规格的设备上加工；
Ⅱ 可在任意规格的 A设备上加工，但对 B工序,只能在 B1设备上加工； Ⅲ 只能在 A2与 B2
设备上加工；数据如下表。问：为使该厂获得最大利润，应如何制定产品加工方案？
生产计划的问题
118
解,设 xijk 表示第 i 种产品，在第 j
种工序上的第 k 种设备上加工的数量,
利润 = [（销售单价 - 原料单价） × 产品件数 ]之和 - （每台时的设备费用 × 设备实际使用的总台时数）之和 。
产品单件工时设备 Ⅰ Ⅱ Ⅲ
设备的有效台时满负荷时的设备费用
A
1
5 10 6000 300
A
2
7 9 12 10000 321
B
1
6 8 4000 50
B
2
4 11 7000 783
B
3
7 4000 200
原料 （元 / 件） 0,25 0,35 0,50
售价 （元 / 件） 1,25 2,00 2,80
生产计划的问题
119
这样我们建立如下的数学模型,
Max
0.75x111+0.7753x112+1.15x211+1.3611x212+1.91
48x312-0.375x121-0.5x221-0.4475x122-
1.2304x322-0.35x123
s.t
5x111+10x211≤6000 （ 设备 A1 ）
7x112+9x212+12x312≤10000 （ 设备 A2 ）
6x121+ 8x221≤ 4000 ( 设备 B1 ）
4x122+11x322≤700 ( 设备 B2 ）
7x123 ≤ 4000 （ 设备 B3 ）
生产计划的问题
120
x111+ x112- x121- x122- x123 = 0
(Ⅰ 产品在 A,B工序加工的数量相等）
x211+ x212- x221 = 0
(Ⅱ 产品在 A,B工序加工的数量相等）
x312 - x322 = 0
(Ⅲ 产品在 A,B工序加工的数量相等）
xijk≥0,i=1,2,3; j=1,2; k=1,2,3
生产计划的问题
121
例 2.14:某工厂要用三种原料 1,2,3混合调配出三种不同规格的产品甲、乙、丙，
数据如下表。问：该厂应如何安排生产，使利润收入为最大？
产品名称 规格要求 单价 （元 /kg ）
甲 原材料 1 不少于 50 %,原材料 2 不超过 25% 50
乙 原材料 1 不少于 25 %,原材料 2 不超过 50% 35
丙 不限 25
原材料名称 每天最多供应量 单价 （元 /kg ）
1 100 65
2 100 25
3 60 35
配料问题
122
配料问题解：设 xij 表示第 i 种（甲、乙、丙）
产品中原料 j 的含量。这样我们建立数学模型时，要考虑：
对于甲,x11,x12,x13；
对于乙,x21,x22,x23；
对于丙,x31,x32,x33；
对于原料 1,x11,x21,x31；
对于原料 2,x12,x22,x32；
对于原料 3,x13,x23,x33；
123
目标函数：
利润最大，利润 = 收入 - 原料支出约束条件,规格要求 4 个；
供应量限制 3 个。
Max
z = -15x11+25x12+15x13-30x21+10x22-40x31-10x33
配料问题
124
s.t,0.5 x11-0.5 x12 -0.5 x13 ≥ 0 （原材料 1不少于 50%）
-0.25x11+0.75x12 -0.25x13 ≤ 0
（原材料 2不超过 25%）
0.75x21-0.25x22 -0.25x23 ≥ 0
（原材料 1不少于 25%）
-0.5 x21+0.5 x22 -0.5 x23 ≤ 0
（原材料 2不超过 50%）
x11+x21+x31≤ 100 ( 供应量限制）
x12+x22+x32≤ 100 ( 供应量限制）
x13+x23+x33≤ 60 ( 供应量限制）
xij≥0,i = 1,2,3; j = 1,2,3
配料问题
125
例 2.17：某部门现有资金 200万元，今后五年内考虑给以下的项目投资。已知：项目 A,从第一年到第五年每年年初都可投资，
当年末能收回本利 110%；项目 B：从第一年到第四年每年年初都可投资，次年末能收回本利 125%，但规定每年最大投资额不能超过 30
万元；项目 C：需在第三年年初投资，第五年末能收回本利 140%，但规定最大投资额不能超过 80万元；项目 D：需在第二年年初投资，
第五年末能收回本利 155%，但规定最大投资额不能超过 100万元。
投资问题
126
据测定每万元每次投资的风险指数如下表：
项目 风险指数（次 / 万元）
A 1
B 3
C 4
D 5,5
投资问题
127
a）应如何确定这些项目的每年投资额，使得第五年年末拥有资金的本利金额为最大？
b）应如何确定这些项目的每年投资额，使得第五年年末拥有资金的本利在 330万元的基础上使得其投资总的风险系数为最小？
问：
投资问题
128
投资问题解,1） 确定决策变量：连续投资问题设 xij ( i = 1—5,j = 1,2,3,4)表示第 i 年初投资于 A(j=1),B(j=2),C(j=3)、
D(j=4)项目的金额。这样我们建立如下 决策变量,
A x11 x21 x31 x41 x51
B x12 x22 x32 x42
C x33
D x24
129
2）约束条件：
第一年,A当年末可收回投资，故第一年年初应把全部资金投出去，于是：
x11+ x12 = 200
第二年,B次年末才可收回投资故第二年年初的资金为 1.1x11，于是：
x21 + x22+ x24 = 1.1x11
第三年,年初的资金为 1.1x21+1.25x12，于是,
x31 + x32+ x33 = 1.1x21+ 1.25x12
第四年,年初的资金为 1.1x31+1.25x22，于是：
x41 + x42 = 1.1x31+ 1.25x22
第五年,年初的资金为 1.1x41+1.25x32，于是：
x51 = 1.1x41+ 1.25x32
B,C,D的投资限制,xi2 ≤ 30 ( i=1,2,3，
4 ),x33 ≤ 80,x24 ≤ 100
投资问题
130
a)
Max z=1.1x51+1.25x42+1.4x33+1.55x24
s.t.x11+ x12 = 200
x21 + x22+ x24 = 1.1x11
x31 + x32+ x33 = 1.1x21+ 1.25x12
x41 + x42 = 1.1x31+ 1.25x22
x51 = 1.1x41+ 1.25x32
xi2 ≤ 30 ( i =1,2,3,4 )，
x33 ≤ 80,x24 ≤ 100
xij≥ 0(i=1,2,3,4,5； j=1,2,3,4）
3）目标函数及模型：
投资问题
131
b)
Min f = （ x11+x21+x31+x41+x51)+
3(x12+x22+x32+x42)+4x33+5.5x24
s.t,x11+ x12 ≤ 200
x21 + x22+ x24 ≤ 1.1 x11
x31 + x32+ x33 ≤ 1.1 x21+ 1.25x12
x41 + x42 ≤ 1.1 x31+ 1.25x22
x51 ≤ 1.1 x41+ 1.25x32
xi2 ≤ 30 ( i =1,2,3,4 )，
x33 ≤ 80,x24 ≤ 100
1.1x51 + 1.25x42+ 1.4x33+ 1.55x24 ≥ 330
xij≥ 0(i=1,2,3,4,5； j = 1,2,3,4）
投资问题
