m1x1 m2 x2 L mn xn (, )bm x1, x2 L xn 0
第12页/共72页
约束条件
注解：
o x1, x2 L xn称为决策变量。
o 上述规划中的决策变量也可以是无约束的。 o 满足所有约束条件的一组决策变量称为可行解
o 使目标函数达到最大的一组决策变量称为最优解
o 最优解所对应的目标函数值称为最优值 o 所有可行解组成的集合称为可行域
在人们的生产实践中，经常会遇到 如何利用现有资源来安排生产，以取得 最大经济效益的问题。此类问题构成了 运筹学的一个重要分支—数学规划，而 线性规划(Linear Programming 简记 LP)则是数学规划的一个重要分支。
第1页/共72页
自从1947年G. B. Dantzig 提出求解线性 规划的单纯形方法以来，线性规划在理论上 趋向成熟，在实用中日益广泛与深入。特别 是在计算机能处理成千上万个约束条件和决 策变量的线性规划问题之后，线性规划的适 用领域更为广泛了，已成为现代管理中经常 采用的基本方法之一。
第13页/共72页
第二节
线性规划的图解法
第14页/共72页
图解法
缺点： 只能求解两个决策变 量的线性规划
优点：简单、直观、帮助我 们了解求解线性规划的原理
第15页/共72页
2.2、图解法
变要量点用直：角坐标系中的点表示
约束条件用坐标系中的半空间或直线的 交表示
第16页/共72页
目标函数用一组等值线表示，沿着增加 或减少的方向移动
结论： 可行域一定是凸集 若最优解存在，则最优解一定
在凸集的顶点达到
第20页/共72页
上例中求得 问题的解是唯一的， 但对一般线性规划问题，求解结果还 可能出现以下几种情况：
1、无穷多最优解（多重解）
若将上例中的目标函数 max z 2x1 4x2
改为则表示目标函数中以参数的等值线 与约束条件的边界平行，当值由小变大 时，将与此边界重合，线段AB上的所有 点都是最优解。
产品 Q3
原料可用量 （公斤/日）
原料P1
2
3
0
1500
原料P2
0
2
4
800
原料P3
3
2
5
2000
单位产品的利润
3
5
4
（千元）
第5页/共72页
可控因素：每天生产三种产品的数量，
分别设为：x1 , x2 , x3
目标：每天的利润最大
利润函数：3x1 5x2 4x3
受制条件：每天原料的需求量不超过可用量
第8页/共72页
从以上例可以看出，其特征是：
1) 问题用一组决策变量 (x1, x2 L xn )
表示某一方案；决策变量的值就代表 一个具体的方案，一般这些变量是非 负的。
第9页/共72页
2. 存在一定的约束条件，这些约束都可 以用一组线性等式或线性不等式表示。
3. 都有一个要达到的目标，它可以用决 策变量的线性函数来表示。按问题的 不同要求，目标函数实现最大化或最 小化。
第10页/共72页
满足以上三个条件的数 学模型称为线性规划的数 学模型，其一般形式为:
第11页/共72页
目标函数
max(min)z c1x1 c2x2 L cnxn
s.tx1 x2 L 1n xn (, )b1 x1 x2 L 2n xn (, )b2 L L L L L L L L L L L L L L
x1 , x2 , x3 0
第7页/共72页
原料可用量 （公斤/日）
1500 800 2000
综上，本问题可用如下模型描述：
目标函数： max z 3x1 5x2 4x3
约束条件：
2x1 3x2 1500
2x1 4x3 800 3x1 2x2 5x3 2000
x1 , x2 , x3 0
2x1 x2 5
x1, x2 0
第25页/共72页
总之，可能出现的情况：
➢ 可行域是空集
➢可行域无界无最优解 ➢最优解存在且唯一，则一定在顶点上达到 ➢最优解存在且不唯一，一定存在顶点是
最优解
第26页/共2页
注：图解法简便、直观，有助于了解
线性规划问题求解的基本原理，但是当 变量的个数多于三个时，它就无能为力 了，因此我们将介绍单纯形法。为了便 于讨论，我们先规定线性规划问题的数 学模型的标准形式。
等值线
第17页/共72页
例1:
msa.txxz122xx1238x2
x1 16
4x2 12
x1, x22 0
第18页/共72页
x2 4x2 12
A
可行域
B
msa.txxz122xx1238x2
x1 16
4x2 12 x1, x2 0
x1 16
第19页/共72页
最优解（4，2）
x1
x1 2x2 8
第2页/共72页
§2.1 问题的提出 §2.2 线性规划的图解法 §2.3 图解法的灵敏度分析
第3页/共72页
第一节 问题的提出
第4页/共72页
1.1、问题的提出
例1: 某工厂用三种原料生产三种产品，已知
的条件如下表所示，试制订总利润最大的生 产计划
单位产品所需原 料数量（公斤）
产品 Q1
产品 Q2
第23页/共72页
由图可知，该问题的可行域无界，目 标函数可以增大到无穷大，称这种情况 为无界解或无最优解。
第24页/共72页
3、无可行解
在上述问题中增加一个约束条件， 2x1 x2 5
该问题可行域为空集，即无可行解，从而不存在最优解。
max z s.t
x1 x2 x1 x2
4
x1 x2 2
第27页/共72页
线性规划问题的标准形式
第28页/共72页
线性规划的一般形式
max(min)z c1x1 c2x2 L cnxn
第21页/共72页
2、无界解
对下述问题用图解法求解结果见下图：
max z s.t
x1 x2 x1 x2
4
x1 x2 2
x1, x2 0
第22页/共72页
max z s.t
x1 x2 x1 x2
4
x1 x2 2
x2
x1, x2 0
2x1 x2 4
x1 x2 2
x1
第6页/共72页
单位产品所需原料 数量（公斤）
产品 Q1
产品 Q2
产品 Q3
原料P1
2
3
0
原料P2
0
2
4
原料P3
3
2
5
单位产品的利润
3
5
4
（千元）
原料 p1: 2x1 3x2 1500
原料 p2: 2x1 4x3 800
原料 p:3 3x1 2x2 5x3 2000
蕴含约束：产量非负