文档介绍：第二章 线性规划与单纯形法 （Linear Programming，简称LP）
§1 线性规化问题及其数学模型
§2 线性规化问题的几何意义
§3 单纯形法
§4 单纯形法的计算步骤
§5 单纯形法的进一步讨论
§6 应用案例
§1线性规化问题及其数学模型
问题的提出
例1：某工厂在计划期内要安排生产Ⅰ、Ⅱ两种产品，已知生产单位产品所需的设备台时及A、B两种原材料的消耗如下表，该工厂每生产一件产品Ⅰ可获利2元，每生产一件产品Ⅱ可获利3元，问应如何安排生产计划使该工厂获利最多？
Ⅰ
Ⅱ
资源
设备
原材料A
原材料B
1
4
0
2
0
4
8 台时
16 kg
12 kg
利润
2
3
x1
x2
§1线性规化问题及其数学模型
Ⅰ
Ⅱ
设备
原材料A
原材料B
1
4
0
2
0
4
8 台时
16 kg
12 kg
利润
2
3
max
目标函数
约束条件
问题的提出
x1
x2
z
例2：靠近某河流有两个化工厂，流经第一化工厂的河流流量为每天500万m3,在两个化工之间有一条河流量为每天200万m3的支流,第一化工厂每天排放含某种有害物质的工业污水2万m3,,从第一化工厂排出的工业污水流到第二化工厂之前，有20%可以自然净化。%。这两个化工厂都需处理一部分工业污水。第一化工厂处理工业污水的成本为1000元/万m3,第二化工厂处理工业污水的成本为800元/万m3。问在满足环保要求的条件下，每厂各应处理多少工业污水，使两个化工厂处理工业污水的总成本最小。
500万m3
200万m3
工厂1
工厂2
2万m3
1000元/万m3
800元/万m3
%
自然净化20%
min
目标函数
约束条件
特征：
每一个问题都用一组决策变量（ x1， x2， …，xn ）表示某一个方案；
存在一定的约束条件，这些约束条件可以用一组线性等式或线性不等式来表示；
都有一个要求达到的目标，它可以用决策变量的线性函数来表示，按问题的不同，要求目标函数实现最大化或最小化。
min
线性规划：目标函数是线性的，约束条件是
线性等式或不等式。
线性规划
线性规划的历史
渊源要追溯到Euler、Liebnitz、Lagrange等
George Dantzig, Non Neumann(Princeton)和Leonid Kantorovich在1940’s创建了线性规划
1947年, George Dantzig于发明了单纯形法
1979年，L. Khachain找到了求解线性规划的一种有效方法(第一个多项式时间算法－椭球内点法)
1984年，Narendra Karmarkan发现了另一种求解线性规划的有效方法，已证明是单纯形法的强有力的竞争者(投影内点法)
现在求解大规模、退化问题最有效的是原－对偶内点法
线性规划问题的数学模型的一般形式为：
目标函数
约束条件
线性规划问题解的概念
可行解：
若（x1，x2，……，xn）满足上述约束条件，则称（x1，x2，……，xn）为线性规划问题的可行解。
可行域：
所有可行解组成的集合称为可行域。
最优解：
使目标函数达到最大或最小的可行解称为最优解。
图解法
Z= 2
Z= 6
Z=10
Q(4, 2)
x2
x1
0 1 2 3 4 5
4
3
2
1
Z=14
X*= (4，2) Z*=14