第1讲 单纯形法

第一章　线性规划及单纯形法

一、问题的提出

例题1：某公司计划制造Ⅰ、Ⅱ两种家电产品。已知各制造一件时分别占用的设备A、B的台时、调试工序时间及每天可用于这两种家电的能力、各售出一件时的获利情况见下表。问该公司应制造两种家电各多少件，使获取的利润为最大。

项目	Ⅰ	Ⅱ	每天可用能力
设备A	0	5	15
设备B	6	2	24
调试工序	1	1	5
利润	2	1

建立数学模型：

建模练习1（下料问题）：

　　某工厂有要做100套钢架，每套由长2.9米、2.1米和1.5米的圆钢各一根组成，已知原料长7.4米，问应如何下料使需用的原材料最省。

有一批长度为180厘米的钢管，需截成70、52和35厘米3种管料。它们的需求量分别不少于100、150和100根。问应如何下料才能使钢管的消耗量为最少？

建模练习1答案：

建模练习2（运输问题）：

某地有3个有色多发金属矿厂，生产同一种金属矿石，分别运往4四冶炼厂，每个矿厂的产量、每个冶炼厂的需求量、以及每个矿厂到每个冶炼厂的单位运费见下表，问：应如何安排运输，使总的运费最少？

单位　  冶炼厂

运费

矿厂	B1	B2	B3	B4	产量
A1	1.5	2	0.3	3	100
A2	7	0.8	1.4	2	80
A3	1.2	0.3	2	2.5	50
需求量	50	70	80	30

建模练习3（指派问题）：

设有四项工作分派给四个人来做，每项工作只能由一个人来做，每个人只能做一项工作。希望安排人选，发挥各人特长又能使总的效率最大。各人对各项工作的效率见下表：

　工作

人员	A	B	C	D
甲	0.6	0.2	0.3	0.1
乙	0.7	0.4	0.3	0.2
丙	0.8	1.0	0.7	0.3
丁	0.7	0.7	0.5	0.4

二、图解法

例题1的图解法：

3

O

X2

图解法还有几种可能的结果：

1.有无穷多最优解；

2.有无界解；

3.无解。

三、线性规划问题的解

　　

线性规划的标准型的条件：AX＝b；X≥0。

　　即：约束方程均为等式方程；所有变量均为非负变量。

线性规划的规范型的条件：AX＝b；X≥0；b≥0，且A中含有一个单位矩阵I。

规范型的作用是我们可以从规范型中马上确定一个基可行解（顶点）。

任何线性规划问题均可化为标准型，但不一定可以化为规范型。

松驰变量，剩余变量，人工变量。

可行解：满足全部约束条件的解。

最优解：使目标函数达到最优的可行解。

基，基变量，非基变量。

基解：基变量的唯一解，与非基变量为0，所组合成的解。

基可行解：满足非负约束条件的基解。

可行基：对应于基可行解的基。

凸集：如果集合C中任意两个点X1、X2，其连线上的所有点也都是集合C中的点，称C为凸集。

顶点：对点X∈C，若在C中找不到两个不同的点X1、X2，使X＝aX1+(1-a)X2（0＜a＜1）成立，则X为C的一个顶点。

定理1：若线性规划问题存在可行解，则可行解域是凸集。

定理2：线性规划问题的每个基可行解对应于其可行解域的一个顶点。即基可行解是可行解域的顶点，可行解域的顶点是基可行解。

定理3：若线性规划问题有最优解，一定存在一个基可行解是最优解（或最优解必在某个顶点上得到）。

定理4：可行解域的顶点个数是有限的，不超过个。？

四、单纯形法

1、单纯形表：

Cj		c1     c2   …… 　　 cn
CB	XB	x1     x2   …… 　　 xn	b	θ
c1 c2 cm	x1 x2 xm	a11       a12  ……   a1n a21       a22  ……   a2n ……　　……　　…… am1     am2  ……   a1n	b1 b2 … bm	θ1 θ2 … θm
-Z		R1     R2  ……   Rn	-Z0

2、单纯形法的计算步骤：

⑴求初始基可行解，列出初始单纯形表。

⑵最优性检验。若Ri≦0，且基变量中不含人工变量时，即得最优解。当Ri＞0时，如有Pj≤0，则问题为无界解，计算结束；否则转下一步。

⑶确定入基变量。任选Ri行中一个大于0的数所对应的变量为入基变量，一般取大数。

⑷确定出基变量。

⑸作旋转变换，并返回第⑵步。

例题1：

解：将原线性规划模型化为规范型如下：

建立单纯形表，并作旋转计算。

cj		3	4	0	0	0
CB	XB	x1	x2	x3	x4	x5	b	θ
0	x3	1	1	1	0	0	6	6
0	x4	1	2	0	1	0	8	8	O点
0	x5	0	1	0	0	1	3	-
－Z		3	4	0	0	0	0
3	x1	1	1	1	0	0	6	6
0	x4	0	1	-1	1	0	2	2	D点
0	x5	0	1	0	0	1	3	3
－Z		0	1	-3	0	0	-18
3	x1	1	0	2	-1	0	4
4	x2	0	1	-1	1	0	2		C点
0	x5	0	0	1	-1	1	1
－Z		0	0	-2	-1	0	-20

旋转的原因：用非基变量来表示基变量进行解释。

规律：

Max：行大列小（检验数行取大于0中的最大者，θ列中取最小者）；

Min：行小列小（检验数行取小于0中的最小者，θ列中取最小者）。

五、单纯形法的进一步讨论

回顾已学过的单纯形法的特点：

⑴从某一规范形出发，因为规范型可立即确定出一个基可行解。

⑵根据检验数确定入基变量。

⑶根据θ规则确定出基变量。

⑷旋转运算（初等行变换），解出新的基可行解（表现形式为新的规范型）。

例题：

如何找出该线性规划问题的初始基。

1、人工变量法（包括两阶段法、大M法）

最优解中，人工变量取值必须为0。

例题：

化为规范型：

⑴大M法

添加人工变量后，希望人工变量等于0，为此需要人工变量对目标函数产生影响，一般设人工变量在目标函数中的系数为M（min型）或者－M（max型）。

⑵两阶段法

在M法便于手工计算，但不便于计算机计算，为此，提出两阶段法。

第一阶段：希望人工变量等于0，构造仅含人工变量的目标函数并要求实现最小化。

第二阶段：将第一阶段计算得到的最终表，去掉人工变量，将目标函数换回原问题的目标函数，作为第二阶段计算的初始表，继续单纯形法，直至求到最优解。

例题

2、单纯形表中解的性质判断

⑴退化解

在确定换出变量时，如果两个θ值相等，就会出现退化解，此时，下一表的基可行解中至少一个基变量为0。

⑵无可行解

当求解结果中，基变量中仍含有非0人工变量时，表明问题无可行解。

Cj		c1     c2   …… 　　 cn
CB	XB	x1   x2   …xm  xm+1… 　　 xn	b	θ
c1 c2 … cm	x1 x2 … xm	1    0 …  0   a1,m+1 ……a1n 0    1 …  0   a2,m+1 ……a2n …… 0    0 …  1   am,m+1 ……amn	b1 b2 … bm	θ1 θ2 … θm
-Z		R1   R2… Rm   Rm+1 …… Rn	-Z0

⑶惟一最优解

①Rj<0（j=m+1,…,n）；

②bi≥0（i=1,…,m）。

条件①表示任何再入基和出基过程都会使其目标值劣化。

⑷无穷最优解

①Rj≤0（j=m+1,…,n）；

②bi≥0（i=1,…,m）；

③Rj（j=m+1,…,n）中至少有一个等于0，设Rp=0

④aip（i=1,…,m）中至少有一个大于0，设aLp>0

⑤bL>0

  条件①、②当前的基可行解是最优解，条件③、④、⑤可保证xp为入基变量时，可得到另一个最优基可行解。

⑸无界解

①bi≥0（i=1,…,m）；

②Rj（j=m+1,…,n）中存在大于0的检验数（对max型），设为Rp＞0；

③aip≤0，i=1,…,m。

条件①保证为基可行解，条件②、③则说明当xp为入基变量时，对xp的θ值无上限，即xp可无限大，则其目标值就可无限大。

课程练习题：

第1题：（在黑板上做）

第2题：（在电脑上用Excel做）

课后作业题:

分别用图解法和单纯形法求解下列线性规划问题，并对照指出单纯形表中的各基可行解对就图解法中可行域的哪一顶点。

解一：（图解法）

X2

根据上图可看出，B点为最优解，此时的目标函数值为33/4。

解二：（单纯形法）

将原问题化为规范型，并构造单纯形表如下：

CB	XB		2	1	0	0
			X1	X2	X3	X4	b	θ
0	X3		3	5	1	0	15	5
0	X4		6	2	0	1	24	4
-Z			2	1	0	0	0
0		X3	0	4	1	-1/2	3
2		X1	1	1/3	0	1/6	4
-Z			0	1/3	0	-1/3	-8
1		X2	0	1	1/4	-1/8	3/4
2		X1	1	0	-1/12	5/24	15/4
-Z			0	0	-1/12	-7/24	-33/4

此时，检验数行全为非正，已得最优解，最优目标函数值为33/4，与图解法的解一致，单纯形表中的每一个基解分别对应于图解法中的一个顶点，对应关系见上表所示。

2、求解下列线性规划问题

解一（大M法）：

将原问题化为规范型如下：

建立单纯形表：

		4	1	0	0	M	M
		X1	X2	X3	X4	X5	X6	b	θ
M	X5	3	1	0	0	1	0	3
M	X6	4	3	-1	0	0	1	6
0	X4	1	2	0	1	0	0	4
－Z		4-7M	1-4M	M	0	0	0
4	X1	1	1/3	0	0	1/3	0	1
M	X6	0	5/3	-1	0	-4/3	1	2
0	X4	0	5/3	0	1	-1/3	0	3
－Z		0	-1/3-5/3M	M	0	-4/3+7/3M	0
4	X1	1	0	1/5	0	3/5	-1/5	3/5
1	X2	0	1	-3/5	0	-4/5	3/5	6/5
0	X4	0	0	1	1	1	-1	1
－Z		0	0	-1/5	0	M-	M-
4	X1	1	0	0	-1/5	2/5	0	2/5
1	X2	0	1	0	3/5	-1/5	0	9/5
0	X3	0	0	1	1	1	-1	1
－Z		0	0	0	1/5	M-	M-

此时，检验数行全为非负，已得最优解X*=(2/5,9/5,1,0,0,0)，最优目标函数值为17/5。

解二（两阶段法）：

第一阶段：换目标函数，只含人工变量，并求最小值。

			0	0	0	0	1	1
			X1	X2	X3	X4	X5	X6	b	θ
1		X5	3	1	0	0	1	0	3
1		X6	4	3	-1	0	0	1	6
0		X4	1	2	0	1	0	0	4
			-7	-4	1	0	0	0
	X1		1	0.333	0	0	0.333	0	1
	X6		0	1.667	-1	0	-1.33	1	2
	X4		0	1.667	0	1	-0.33	0	3
			0	-1.67	1	0	2.333	0	7
	X1		1	0	0.2	0	0.6	-0.2	0.6
	X2		0	1	-0.6	0	-0.8	0.6	1.2
	X4		0	0	1	1	1	-1	1
			0	0	0	0	1	1	9

此时，检验数行全为非负，已得最优解，且目标函数值为0，可进行下一阶段的计算。

第二阶段：目标函数用原问题的目标函数，计算如下：

		4	1	0	0
		X1	X2	X3	X4	b
4	X1	1	0	0.2	0	0.6
1	X2	0	1	-0.6	0	1.2
0	X4	0	0	1	1	1
		0	0	-0.2	0
4	X1	1	0	0	-0.2	0.4
1	X2	0	1	0	0.6	1.8
0	X3	0	0	1	1	1
		0	0	0	0.2

此时，检验数行全为非负，已得最优解X*=(2/5,9/5,1,0,0,0)，最优目标函数值为17/5。