第二章 线性规划
➢ 二维问题的图解法 ➢ 线性规划的基本定理
➢ 大M法 要点：基本定理、顶点、标准形式、典范形式、可行基本解、
价值系数、最优性准则、单纯形表格法
☆ 在模型
min f(x)
中
s.t. gi (x) 0, i 1,, l
h j (x) 0, j 1,, m
当f(x), g i(x), (i=1,…l ), hj(x), (j=1,…m)为线性函数时，称为线性规划问题
§2.4.2 线性规划的两个重要性质 ☆基本定理
（1）线性规划的可行域是一个凸集； （2）线性规划若存在可行点，则必存在可行域的顶点；
若存在最优点，则至少有一个顶点是最优点。
☆定理的重要意义 （1）保证了顶点的存在性； （2）把一般要从无限个可行点中寻优最优点的问题 简化为仅在有限个顶点中确定最优点的问题
问题：为什么顶点只有有限个？怎样找出顶点？
§2.5 线性规划的标准形式
➢ 思路：
一般LP
标准LP
单纯形法求解标准LP
➢ LP的标准形式：
min z=c1x1+ c2x2+．．．+ cnxn
s.t. a11x1+ a12x2+．．．+ a1nxn=b1 a21x1+ a22x2+．．．+ a2nxn=b2 ．．．．．．．．．．．．． am1x1+ am2x2+．．．+ amnxn=bm
☆ 凸集的基本性质
若M1和M2为凸集，λ为正实数，则集合 （1）{y|y =λx, x∈M1} （2）{y|y =x+z, x∈M1, z∈M2} （3）M1和M2的交集M1∩M2
都为凸集。
☆ 顶点
如果凸集M中的一个点x不是M中任一线段的内点，则x是M 的一个顶点
E
A
B
K
F
H
C
D
G
（球面上的所有 点都是顶点）
0
3x1+4x2=12 3x1+3x2=10
x1
§2.4 线性规划的基本定理
§2.4.1 凸集与顶点 ☆凸集：设M为Rn中的一个集合，如果对M中任意两点为端点
的线段全部含于M中，则称M为凸集。
x(1)
x(1)
x(1)
x(2)
x(2)
x(2)
☆直观理解：内部没有“洞”，边界不向内凹的形体
非凸集 实例
f(x) = 8(5x1+4.5x2) = 40 x1+36x2
数学模型
min f(x)=40x1+36x2 s.t. 5x1+3x2 45 x1≤8 x2≤10 x1, x2 ≥0
隐含的 约束条件
§2.2 二维问题的图解法
图解步骤 （1）在x10x2坐标平面上画出可行域； （2）作目标函数的等高线 (为一组平行的直线)， 根据等高线函数值的变化规律及目标函数的要 求，确定等高线的移动方向，按此方向移动 等高线，使其达到可行域的极限点（最优点）；
Linear Programming ( LP )
☆ 1832和1911年，法国数学家J. B. J.傅里叶和C.瓦莱普森分别 提出线性规划的想法
☆ 1939年，苏联数学家康托洛维奇提出并解决了一个线性规划 问题（《生产组织与计划中的数学方法》）
☆ 1947年，美国数学家G.B.Dantzing提出单纯形法，奠定了LP 的理论基础
☆ 研究重要性
（1）一些 NLP 问题可简化为 LP 问题求解 （2）是开发一些较复杂 NLP 算法的基础 （3）是所有最优化方法中最常用的技术
( 占47％；科学计算中，LP的计算时间占1/4）
§2.1 建立LP问题数学模型的实例
（1）确定自变量 建模的三个步骤 （2）把问题的约束条件表示成等式或不
（3）根据最优点的位置，联立求解对应的约束方程， 求出最优点坐标；
（4）将最优点坐标代入目标函数，求出最优值。
P19 例： max f(x)=4x1+3x2 s.t. 3x1+4x2≤12
3x1+3x2≤10 4x1+2x2≤8
x1, x2 ≥0
x2
4x1+2x2=8
3
A
最优点(x1* =4/5, x2*=12/5)
x1, x2 ≥0 最优点：
CD上的所有点
B
f *=8
0
f =4
3x1+4x2≤12
3x1+3x2≤10 C
f =8
x1
§2.3.2 无界可行域
例：
x2
max f(x)=4x1+3x2 s.t. 3x1+4x2 ≤≥ 12
3x1+3x2 ≤≥ 10 4x1+2x2 ≥≤ 8
x1, x2 ≥ 0 数学上存在
D
f =52/5
f *=52/5
B
0
3x1+4x2=12
3x1+3x2=10
C
4
f =7
x1
§2.3 线性规划问题的几种特殊情况
§2.3.1 有无限个最优解 x2
例： max f(x)=4x1+ 23 x2 s.t. 3x1+4x2≤12
4x1+2x2≤8 A
3x1+3x2≤10
D
4x1+2x2≤8
等式 （3）写出目标函数
例2.1.1 确定职工编制问题
某厂每日8小时的产量不低于1800件。为了进行质量控制，计划聘请两 种不同水平的检验员。一级检验员的标准是：速度 25件/小时，正确率 98％， 计时工资 4元/小时；二级检验员的标准是：速度 15件/小时，正确率 95％， 计时工资 3元/小时。检验员每错验一次，工厂要损失2元。现可供厂方聘请 的检验员人数为一级8人和二级10人。为使总检验费用最省，该工厂应聘一 级和二级检验员各多少名？
分析：设应聘一级检验员x1 ，二级检验员x2
约束一：可聘两级检验员人数
x18
约束二：每日产量要求 目标函数
x210 8(25)x1+8(15)x21800
5x1+3x2 45
一级检验员每小时费用 4＋25 (0.02) (2)=5元/小时
二级检验员每小时费用 3＋15 (0.05) (2)=4.5元/小时
x1≥0, x2≥0, ．．．, xn≥0 b1≥0, b2≥0, ．．．, bm≥0
目标函数 约束方程组 非负条件
➢ 用矩阵和向量表示的LP的标准形式：
min z = cTx s.t. Ax = b
目标函数 约束方程组
4x1+2x2=8
但对于实际问题，可 能是遗漏或写错了约 束条件！
0
f 增大方向
3x1+4x2=12 3x1+3x2=10
x1
§2.3.3 可行域为空集
例：
x2
max f(x)=4x1+3x2 s.t. 3x1+4x2 ≤ 12
3x1+3x2 ≤≥ 10 4x1+2x2 ≤ 8
x1, x2 ≥0
4x1+2x2=8