第一节 线性规划的模型与图解法一、线性规划问题及其数学模型在生产管理和经营活动中经常需要解决：如何合理地利用有限的资源，以得到最大的效益。
例 1 某工厂可生产甲、乙两种产品，需消耗煤、
电、油三种资源。现将有关数据列表如下：
试拟订使总收入最大的生产方案。
资源单耗 产品资源甲 乙 资源限量煤电油
9 4
4 5
3 10
360
200
300
单位产品价格 7 12
线性规划模型的三要素
3.约束条件,为实现优化目标需受到的限制，用决策变量的等式或不 等式表示；
1.决策变量,需决策的量，即待求的未知数；
2.目标函数,需优化的量，即欲达的目标，用决策变量的表达式表示；
目标函数：总收入，记为 z,则 z=7x1+12x2，为体现对其追求极大化，在 z 的前面冠以极大号 Max；
决策变量：甲、乙产品的计划产量，记为 ；
在本例中约束条件：分别来自资源煤、电、油限量的约束，和产量非负的约束，表示为
0,
3 0 0103
2 0 054
3 6 049
..
21
21
21
21
xx
xx
xx
xx
ts
,xx
解,设安排甲、乙产量分别 为,总收入为,
则模型为：
21,xx z
21 127 xxM a x z
0,
3 0 0103
2 0 054
3 6 049
..
21
21
21
21
xx
xx
xx
xx
ts
线性规划模型的一个基本特点：
目标和约束均为变量的线性表达式如果模型中出现如的非线性表达式，则属于非线性规划。
3
2
2
1
1ln2
xxx
例 2 某市今年要兴建大量住宅,已知有三种住宅体系可以大量兴建，各体系资源用量及今年供应量见下表：
要求在充分利用各种资源条件下使建造住宅的总面积为最大 (即求安排各住宅多少 m2)，求建造方案。
水泥
(公斤 /m2)
4000
(千工日 )
147000
(千块 )
150000
(吨 )
20000
(吨 )
110000
(千元 )
资源限量
3.5——18025120大模住宅
3.0——19030135壁板住宅
4.521011012105砖混住宅人工
(工日 /m2)
砖
(块 /m2)
钢材
(公斤 /m2)
造价
(元 /m2)
资源住宅体系解,设今年计划修建砖混、壁板、大模住宅各为
x1,x2,x3 m2,z为总面积,则本问题的数学模型为,
0,,
4 0 0 00 0 3 5.00 0 3.00 0 4 5.0
1 4 7 0 0 02 1 0.0
1 5 0 0 0 01 8 0.01 9 0.01 1 0.0
2 0 0 0 00 2 5.00 3 0.00 1 2.0
1 1 0 0 0 01 2 0.01 3 5.01 0 5.0
.
321
321
1
321
321
321
xxx
xxx
x
xxx
xxx
xxx
ts
321 xxxM a x z
前苏联的尼古拉也夫斯克城住宅兴建计划采用了上述模型，共用了 12个变量,10个约束条件。
练习,某畜牧厂每日要为牲畜购买饲料以使其获取 A、
B,C,D四种养分。市场上可选择的饲料有 M,N两种。
有关数据如下：
试决定买 M与 N二种饲料各多少公斤而使支出的总费用为最少？
4
10
售价
0.4 0.6 2.0 1.7牲畜每日每头需要量
0 0.1 0.2 0.1N
0.1 0 0.1 0.2M
每公斤含营养成分
A B C D
饲料解：设购买 M,N饲料各为,则
21 410 xxM i n z
0,
7.11.02.0
0.22.01.0
6.01.00
4.001.0
..
21
21
21
21
21
xx
xx
xx
xx
xx
ts
21,xx
线性规划模型的一般形式,（以 MAX型,约束为例）
决策变量：
目标函数：
约束条件：
nxx,,1?
nn xcxcM ax z11
0,,
..
1
11
11111
n
m
nmnm
nn
xx
bxaxa
bxaxa
ts
则模型可表示为模型一般式的矩阵形式记 T
mnmijn
T
n bbbaAccCxxX ),,(,)(),,,(,),,( 111
0
..
X
bAX
ts
CXM a xz
回顾例 1的模型其中表示决策变量的向量；
表示产品的价格向量；
表示资源限制向量；
表示产品对资源的单耗系数矩阵。
TxxX ),(
21?
)12,7(?C
Tb )300,200,360(?
103
54
49
A
一般地中 称为决策变量向量,称为价格系数向量,
称为技术系数矩阵,称为资源限制向量。
0
..
X
bAX
ts
CXM a xz
X C
A b
问题,为什么 A 称为技术系数矩阵？
二、线性规划模型的图解法
图解法是用画图的方式求解线性规划的一种方法。它虽然只能用于解二维（两个变量）的问题，但其主要作用并不在于求解，
而是在于能够直观地说明线性规划解的一些重要性质。
1,图解法的步骤
（ 1）做约束的图形先做非负约束的图形；
再做资源约束的图形。
以例 1为例，其约束为
0,
3 0 0103
2 0 054
3 6 049
.
21
21
21
21
xx
xx
xx
xx
ts
0
1x
2x
问题,不等式的几何意义是什么？怎样做图？
所表示的区域）。
等式点所在的半平面即该不不等式，满足，说明原
）代入，方法（如把原点（半平面，可用代入点的表示上述直线的哪再确定不等式
））；，）、（，点（
于是该直线过则再令则用两点连线方法（令先做直线的做图方法是：一个半平面。因此，它为边界的，它表示以如
00
36049
040900
,40,0,90,0
,36049
3604936049
21
1221
21
2121
xx
xxxx
xx
xxxx
（ 1）做约束的图形先做非负约束的图形；
再做资源约束的图形。
以例 1为例，其约束为
0,
3 0 0103
2 0 054
3 6 049
.
21
21
21
21
xx
xx
xx
xx
ts
0
1x
2x
90
40 50 100
30
40
各约束的公共部分即模型的约束，称可行域。
1,图解法的步骤
（ 2）做目标的图形
0
1x
2x对于目标函数任给 二不同的值，
便可做出相应的二直线，用虚线表示。
以例 1为例，其目标为
，分别令
，做出相应的二直线，便可看出增大的方向。
nn xcxcz11
z
21 127 xxz
16884 zz 和
z
7
12
14
24
（ 3）求出最优解将目标直线向使目标 优化的方向移，直至可行域的边界为止，
这时其与可行域的,切,
点 即最优解。
如在例 1中，
是可行域的一个角点，
经求解交出 的二约束直线联立的方程可解得
z
*X
*X
*X
TX )24,20(*? 0 1x
2x
90
40 50 100
30
40
*X
由图解法的结果得到例 1的最优解,
还可将其代入目标函数求得相应的最优目标值
。 说明当甲产量安排 20 个单位,乙产量安排 24 个单位时,可获得最大的收入 428。
TX )24,20(*?
428*?z
练习,用图解法求解下面的线性规划。
0,
5.143
12
..
46
21
21
21
21
xx
xx
xx
ts
xxM in z
0
1x
2x
1
5.0
375.0
5.1
1
*X
3,)0,5.0( ** zX T
问题,在上两例中
—— 多边形，而且是,凸,形的多边形。
最优解在什么位置获得？
—— 在边界，而且是在某个顶点获得。
线性规划的可行域是一个什么形状？
2,由图解法得到线性规划解的一些特性
（ 1）线性规划的约束集（即可行域）是一个凸多面体。
凸多面体是凸集的一种。所谓凸集是指：集中任两点的连线仍属此集。试判断下面的图形是否凸集：
凸集中的,极点,,又称顶点或角点，是指它属于凸集，但不能表示成集中某二点连线的内点。如多边形的顶点。
（ 2）线性规划的最优解（若存在的话）必能在可行域的角点获得。
因为，由图解法可知，只有当目标直线平移到边界时，
才能使目标 z 达到最大限度的优化。
问题,本性质有何重要意义？
—— 它使得在可行域中寻优的工作由,无限,上升为,有限,,从而为线性规划的算法设计提供了重要基础。
（ 3）线性规划解的几种情形
① 唯一最优解 ② 多重最优解
③ 无解 ④ 无有限最优解 （无界解）
例 1 某工厂可生产甲、乙两种产品，需消耗煤、
电、油三种资源。现将有关数据列表如下：
试拟订使总收入最大的生产方案。
资源单耗 产品资源甲 乙 资源限量煤电油
9 4
4 5
3 10
360
200
300
单位产品价格 7 12
线性规划模型的三要素
3.约束条件,为实现优化目标需受到的限制，用决策变量的等式或不 等式表示；
1.决策变量,需决策的量，即待求的未知数；
2.目标函数,需优化的量，即欲达的目标，用决策变量的表达式表示；
目标函数：总收入，记为 z,则 z=7x1+12x2，为体现对其追求极大化，在 z 的前面冠以极大号 Max；
决策变量：甲、乙产品的计划产量，记为 ；
在本例中约束条件：分别来自资源煤、电、油限量的约束，和产量非负的约束，表示为
0,
3 0 0103
2 0 054
3 6 049
..
21
21
21
21
xx
xx
xx
xx
ts
,xx
解,设安排甲、乙产量分别 为,总收入为,
则模型为：
21,xx z
21 127 xxM a x z
0,
3 0 0103
2 0 054
3 6 049
..
21
21
21
21
xx
xx
xx
xx
ts
线性规划模型的一个基本特点：
目标和约束均为变量的线性表达式如果模型中出现如的非线性表达式，则属于非线性规划。
3
2
2
1
1ln2
xxx
例 2 某市今年要兴建大量住宅,已知有三种住宅体系可以大量兴建，各体系资源用量及今年供应量见下表：
要求在充分利用各种资源条件下使建造住宅的总面积为最大 (即求安排各住宅多少 m2)，求建造方案。
水泥
(公斤 /m2)
4000
(千工日 )
147000
(千块 )
150000
(吨 )
20000
(吨 )
110000
(千元 )
资源限量
3.5——18025120大模住宅
3.0——19030135壁板住宅
4.521011012105砖混住宅人工
(工日 /m2)
砖
(块 /m2)
钢材
(公斤 /m2)
造价
(元 /m2)
资源住宅体系解,设今年计划修建砖混、壁板、大模住宅各为
x1,x2,x3 m2,z为总面积,则本问题的数学模型为,
0,,
4 0 0 00 0 3 5.00 0 3.00 0 4 5.0
1 4 7 0 0 02 1 0.0
1 5 0 0 0 01 8 0.01 9 0.01 1 0.0
2 0 0 0 00 2 5.00 3 0.00 1 2.0
1 1 0 0 0 01 2 0.01 3 5.01 0 5.0
.
321
321
1
321
321
321
xxx
xxx
x
xxx
xxx
xxx
ts
321 xxxM a x z
前苏联的尼古拉也夫斯克城住宅兴建计划采用了上述模型，共用了 12个变量,10个约束条件。
练习,某畜牧厂每日要为牲畜购买饲料以使其获取 A、
B,C,D四种养分。市场上可选择的饲料有 M,N两种。
有关数据如下：
试决定买 M与 N二种饲料各多少公斤而使支出的总费用为最少？
4
10
售价
0.4 0.6 2.0 1.7牲畜每日每头需要量
0 0.1 0.2 0.1N
0.1 0 0.1 0.2M
每公斤含营养成分
A B C D
饲料解：设购买 M,N饲料各为,则
21 410 xxM i n z
0,
7.11.02.0
0.22.01.0
6.01.00
4.001.0
..
21
21
21
21
21
xx
xx
xx
xx
xx
ts
21,xx
线性规划模型的一般形式,（以 MAX型,约束为例）
决策变量：
目标函数：
约束条件：
nxx,,1?
nn xcxcM ax z11
0,,
..
1
11
11111
n
m
nmnm
nn
xx
bxaxa
bxaxa
ts
则模型可表示为模型一般式的矩阵形式记 T
mnmijn
T
n bbbaAccCxxX ),,(,)(),,,(,),,( 111
0
..
X
bAX
ts
CXM a xz
回顾例 1的模型其中表示决策变量的向量；
表示产品的价格向量；
表示资源限制向量；
表示产品对资源的单耗系数矩阵。
TxxX ),(
21?
)12,7(?C
Tb )300,200,360(?
103
54
49
A
一般地中 称为决策变量向量,称为价格系数向量,
称为技术系数矩阵,称为资源限制向量。
0
..
X
bAX
ts
CXM a xz
X C
A b
问题,为什么 A 称为技术系数矩阵？
二、线性规划模型的图解法
图解法是用画图的方式求解线性规划的一种方法。它虽然只能用于解二维（两个变量）的问题，但其主要作用并不在于求解，
而是在于能够直观地说明线性规划解的一些重要性质。
1,图解法的步骤
（ 1）做约束的图形先做非负约束的图形；
再做资源约束的图形。
以例 1为例，其约束为
0,
3 0 0103
2 0 054
3 6 049
.
21
21
21
21
xx
xx
xx
xx
ts
0
1x
2x
问题,不等式的几何意义是什么？怎样做图？
所表示的区域）。
等式点所在的半平面即该不不等式，满足，说明原
）代入，方法（如把原点（半平面，可用代入点的表示上述直线的哪再确定不等式
））；，）、（，点（
于是该直线过则再令则用两点连线方法（令先做直线的做图方法是：一个半平面。因此，它为边界的，它表示以如
00
36049
040900
,40,0,90,0
,36049
3604936049
21
1221
21
2121
xx
xxxx
xx
xxxx
（ 1）做约束的图形先做非负约束的图形；
再做资源约束的图形。
以例 1为例，其约束为
0,
3 0 0103
2 0 054
3 6 049
.
21
21
21
21
xx
xx
xx
xx
ts
0
1x
2x
90
40 50 100
30
40
各约束的公共部分即模型的约束，称可行域。
1,图解法的步骤
（ 2）做目标的图形
0
1x
2x对于目标函数任给 二不同的值，
便可做出相应的二直线，用虚线表示。
以例 1为例，其目标为
，分别令
，做出相应的二直线，便可看出增大的方向。
nn xcxcz11
z
21 127 xxz
16884 zz 和
z
7
12
14
24
（ 3）求出最优解将目标直线向使目标 优化的方向移，直至可行域的边界为止，
这时其与可行域的,切,
点 即最优解。
如在例 1中，
是可行域的一个角点，
经求解交出 的二约束直线联立的方程可解得
z
*X
*X
*X
TX )24,20(*? 0 1x
2x
90
40 50 100
30
40
*X
由图解法的结果得到例 1的最优解,
还可将其代入目标函数求得相应的最优目标值
。 说明当甲产量安排 20 个单位,乙产量安排 24 个单位时,可获得最大的收入 428。
TX )24,20(*?
428*?z
练习,用图解法求解下面的线性规划。
0,
5.143
12
..
46
21
21
21
21
xx
xx
xx
ts
xxM in z
0
1x
2x
1
5.0
375.0
5.1
1
*X
3,)0,5.0( ** zX T
问题,在上两例中
—— 多边形，而且是,凸,形的多边形。
最优解在什么位置获得？
—— 在边界，而且是在某个顶点获得。
线性规划的可行域是一个什么形状？
2,由图解法得到线性规划解的一些特性
（ 1）线性规划的约束集（即可行域）是一个凸多面体。
凸多面体是凸集的一种。所谓凸集是指：集中任两点的连线仍属此集。试判断下面的图形是否凸集：
凸集中的,极点,,又称顶点或角点，是指它属于凸集，但不能表示成集中某二点连线的内点。如多边形的顶点。
（ 2）线性规划的最优解（若存在的话）必能在可行域的角点获得。
因为，由图解法可知，只有当目标直线平移到边界时，
才能使目标 z 达到最大限度的优化。
问题,本性质有何重要意义？
—— 它使得在可行域中寻优的工作由,无限,上升为,有限,,从而为线性规划的算法设计提供了重要基础。
（ 3）线性规划解的几种情形
① 唯一最优解 ② 多重最优解
③ 无解 ④ 无有限最优解 （无界解）
