1
,运筹学,课程 教学大纲运筹学 Operations research
课程各章节内容及学时分配
64 学时任课教师：余 勇 Tel,88061330
2
,运筹学,课程 教学大纲课时安排：
序号 课程内容 学时
1 第一讲 管理运筹学序论 2
2 第二讲 线性规划,运输问题,目标规划,整数规划 30
3 *第三讲 非线性规划 2
4 第四讲 动态规划 8
5 第五讲 图与网络分析 8
6 *第七讲 排队论,对策论 2
7 案例讨论，实验 12
3
绪论 历史，性质，应用
20世纪整个世界参与规模最大的事件是什么？
第二次世界大战 ！
整个世界的资源都投入到了第二次世界大战中。
如何才能更好地利用资源，分配有限的资源，这是一个值得研究的问题。
当时在英国军队中率先成立了研究小组 —— 运筹小组来研究这些问题，这就是著名的 OR小组,很快美军中也相继成立了 OR小组。
战争 —— 运筹学诞生的温床。
4
绪论 历史，性质，应用二战中成功的运筹学案例：
英国防空部门如何布置防空雷达，建立最有效的防空警报系统。
英，美空军如何提高对地面目标轰炸的命中率。
如何安排反潜飞机的巡逻飞行线路。
深水炸弹的合理爆炸深度，摧毁德军潜艇数增加 400%。
商船如何编队，遭潜艇攻击时如何减少损失。
使船只受敌机攻击时，中弹数由 47%降到 29%。
这些研究大大提高了盟军的作战能力，为反法西斯战争的最后胜利作出了巨大的贡献！
5
绪论 历史，性质，应用战争结束了！ 整个世界投入到了战后的重建国家的经济之中。
运筹学的方法相继在工业，农业，经济，社会问题等各个领域中展开了应用。与此同时，运筹数学有了飞快的发展，并形成了许多运筹学的分支。
线性规划，非线性规划，整数规划，目标规划，动态规划，
图与网络分析，统筹方法，排队论，存储论，对策论，决策论，多目标决策。
6
绪论 历史，性质，应用
运筹学的性质和特点
a,一种哲学方法论 ;
b,研究“事”而非“物” ;
c,科学性，实践性，系统性，综合性 ;
d,模型的特点 —— 系统优化模型。
运筹学 —— 为决策机构在对其控制下业务活动进行决策时，
提供以数量化为基础的科学方法。
运筹学 —— 一门应用科学，它广泛应用现有的科学技术知识和数学方法，解决实际中提出的专门问题。
运筹学 —— 是一种给出问题坏的答案的艺术，否则问题的结果会更坏。
7
绪论 历史，性质，应用
运筹学的工作步骤运筹学在解决大量实际问题的过程中形成了自己的工作步骤。
（ 1） 提出和形成问题。 即弄清问题的目标，可能的约束，
问题的可控变量以及有关参数，搜集有关资料 ;
（ 2） 建立模型。 即把问题中可控变量，参数和目标与约束之间的关系用一定的模型表示出来 ;
（ 3） 求解。用各种手段（主要是数学方法，也可用其他方法）将模型求解。解可以是最优解、次优解、满意解。复杂模型的求解需用计算机，解的精度要可由求决策者提出；
8
绪论 历史，性质，应用
运筹学的工作步骤
（ 4） 解的检验。首先检查求解步骤和程序有无错误，然后检查解是否反映现实问题；
（ 5） 解的控制。通过控制解的变化过程决定是否要作一定的改变；
（ 6） 解的实施。是指将解用到实际中必须考虑到实施的问题，如向实际部门讲清解的用法，在实施中可能产生的问题和修改。
9
绪论 历史，性质，应用
运筹学的模型
运筹学在解决问题时，按研究对象不同可构造各种不同的模型。模型是研究者对客观现实经过思维抽象后用文字、图表、
符号、关系以及实体模样描述所认识到的客观对象。模型的有关参数和关系式是较容易改变的，这样是有助于问题的分析和研究。利用模型可以进行一定预测、灵敏度分析等。
模型的三种基本形式：
（ 1）形象模型，（ 2）模拟模型，（ 3）符号或数学模型。
构造模型是一种创造性劳动，成功的模型往往是科学和艺术的结晶，构造模型的方法和思路通常有以下几种：
10
绪论 历史，性质，应用
直接分析法 按研究者对问题内在机理的认识直接构造出模型。运筹学中已有不少现存的模型，如线性规划模型、投入产出模型、排队模型、存储模型、决策和对策模型等等。这些模型都有很好的求解方法及求解软件，但用这些现成的模型研究问题时，应注意不能生搬硬套。
类比法 有些问题可以用不同方法构造出模型；而这些模型的结构性质是类同的，这就可以互相类比。如物理学中的机械系统、气体动力学系统、水力学系统、热力学系统及电路系统之间就有不少彼此类同的现象。甚至有些经济、社会系统也可以用物理系统来类比。在分析有些经济、社会问题时，
不同国家之间也可以找出某些类比的现象。
11
绪论 历史，性质，应用
数据分析法 对有些问题的机理尚未了解清楚，若能搜集到与此问题密切有关的大量数据，或通过某些试验获得大量数据，这就可以用统计分析法建摸。
试验分析法 有些问题的机理不清，又不能作大量试验来获得数据，这时只能通过做局部试验的数据加上分析来构造模型。
想定（构想）法 当有些问题的机理不清，又缺少数据，又不能作试验来获得数据时，例如有些社会、经济、军事问题，
人们只能在已有的知识、经验和某些研究的基础上，对于将来可能发生的情况给出逻辑上合理的设想和描述。然后用已有的方法构造模型，并不断修正完善，直至比较满意为止。
12
绪论 历史，性质，应用
运筹学的主要应用 二次大战后运筹学的应用迅速转向了民用，下面对某些重要领域给于简述。
1、市场销售 ------广告预算和媒介选择、竞争性定价、新品开发、销售计划的制订。 （美）杜邦公司在五十年代起就非常重视将运筹学用于如何做好广告工作、产品定价、新品引入。
2、生产计划 ------从总体确定生产、存储和劳动力的配合等计划适应波动的需求计划。 巴基斯坦一重型制造厂用线性规划安排生产计划，节省 10%的生产费用。
3、运输问题 ------涉及空运、水运、公路、铁路运输、管道运输等。公路网的设计和分析，市内公共汽车路线的选择和行车时刻表的安排，出租车的调度等。
13
绪论 历史，性质，应用
4、人事管理 ------需求估计，教育和培训，人员分配（各种指派问题），合理利用，人才评价等。
5、设备维修，更新和可靠性等。
6、计算机和信息系统 ------内存分配研究，网络设计分析等。
7、城市管理 ------紧急服务系统的设计和运用，区域布局规划，管道网络设计等。 （美）曾用排队论确定纽约市紧急电话站的值班人数，（加）设计城市警车配置和负责范围、指挥接警后的行走路线等。
8、对策研究 ------价格竞争，中央与地方政府投资分配博弈，
工会与雇主间的博弈。
14
第一讲线性规划 Linear Programming( LP )
目标规划 Goal Programming( GP )
整数规划 Integer Programming( IP )
15
第一章线性规划及单纯形法线性规划 Linear Programming（ LP）
16
引 言
解决有限资源在有竞争的使用方向中如何进行最佳分配。
线性规划是运筹学的一个重要分支，也是运筹学中应用最广泛的方法之一。自 1947年旦茨基（ G,B,Dantzig）提出了一般线性规划问题求解的方法 —— 单纯形法（ simplex
method）之后，线性规划已被广泛应用于解决经济管理和工业生产中遇到的实际问题。调查表明，在世界 500家最大的企业中，有 85%的企业都曾使用过线性规划解决经营管理中遇到的复杂问题。线性规划的使用为应用者节约了数以亿万计的资金。
线性规划 Linear Programming（ LP）
17
本讲中我们将讨论什么是线性规划问题，线性规划问题的数学表示，基本理论、概念和求解方法。
线性规划问题是什么样的一类问题呢？
请看案例 ------
线性规划 Linear Programming（ LP）
18
线性规划 Linear Programming（ LP）
曾几何时长江水，
哺育华夏代代人，
谁知后代疏珍惜，
清清江水黑如泥。
案 例 河流污染治理规划问题
19
线性规划 Linear Programming（ LP）
曾几何时长江水，
哺育华夏代代人，
谁知后代疏珍惜，
清清江水黑如泥。
工厂 2
工厂 3
工厂 1 工厂 4
工厂 5
工厂 6
工厂 9
工厂 8
工厂 7
案 例 河流污染治理规划问题
20
线性规划 Linear Programming（ LP）
曾几何时长江水，
哺育华夏代代人，
谁知后代疏珍惜，
清清江水黑如泥。
今日认识未为晚，
吾辈齐心治环境，
线性规划大有用，
定让江水绿如蓝。
工厂 2
工厂 3
工厂 1 工厂 4
工厂 5
工厂 6
工厂 9
工厂 8
工厂 7
案 例 河流污染治理规划问题
21
线性规划 Linear Programming（ LP）
今日认识未为晚，
吾辈齐心治环境，
线性规划大有用，
定让江水绿如蓝。
曾几何时长江水，
哺育华夏代代人，
谁知后代疏珍惜，
清清江水黑如泥。
工厂 2
工厂 3
工厂 1 工厂 4
工厂 5
工厂 6
工厂 9
工厂 8
工厂 7
案 例 河流污染治理规划问题
22
线性规划 Linear Programming（ LP）
案 例 河流污染治理规划问题
背景资料,
长江流域某区域内有 9化工厂，各厂每月产生的工业污水量如表 -1，流经各化工厂的河流流量如表 -2，各化工厂治理工业污水的成本如表 -3。上游厂排放的污水流到相邻下游厂以前，有 20%可自然净化。 根据环保标准河流中此种工业污水的含量不应超过 0.2%。从该区域整体考虑，各化工厂应该分别处理多少工业污水才能既满足环保要求，又使 9化工厂治理工业污水的总费用最少。
23
背景资料,
线性规划 Linear Programming（ LP）
化工厂 1 1.2 化工厂 4 2 化工厂 7 2
化工厂 2 1 化工厂 5 1 化工厂 8 0.8
化工厂 3 3 化工厂 6 1 化工厂 9 1.5
表 -1 污水排放量 单位：万 m3
表 -2 流经各化工厂的河流流量 单位：万 m3
表 -3 治理工业污水的成本 单位：百万元 /万 m3
化工厂 1 500 化工厂 4 1200 化工厂 7 1200
化工厂 2 300 化工厂 5 600 化工厂 8 200
化工厂 3 1800 化工厂 6 400 化工厂 9 700
化工厂 1 3 化工厂 4 4 化工厂 7 1
化工厂 2 5 化工厂 5 5 化工厂 8 2
化工厂 3 2 化工厂 6 6 化工厂 9 3
24
线性规划 Linear Programming（ LP）
1
9
4
5
8
2
6
3
7
案 例 河流污染治理规划问题
问题分析：
区域污染治理的决策 ——各个化工厂应处理的工业污水量
（或应排放的工业污水量）。
区域污染治理的约束 ——即满足环保要求排放工业污水（区域内河流中任何点检测都应符合环保标准）。
区域污染治理的目标 ——总治理成本最少。
25
线性规划 Linear Programming（ LP）
1
9
4
5
8
2
6
3
7
案 例 河流污染治理规划问题
模型描述：
设第 i个化工厂应处理的工业污水量为 Xi万 m3，则根据问题描述的情况以化工厂 1,2,…,9 加以分析则可得如下近似关系式
对化工厂 2应有 ---
（ 1-X2） / 300 ≦ 0.2%
对化工厂 8应有 ---
（ 2-X8） /200 ≦ 0.2%
对化工厂 1应有 ---
｛（ 3-X1） + 0.8?（ 1-X2） +（ 2-X8）? ｝ /500 ≦ 0.2%
26
线性规划 Linear Programming（ LP）
1
9
4
5
8
2
6
3
7
案 例 河流污染治理规划问题
对 化工厂 9应有 ——
（ 1.5-X9） / 700 ≦ 0.2%
对 化工厂 7应有 ——
（ 2-X7） + 0.8（ 1.5-X9）? / 1200 ≦ 0.2%
……
此外显然还应有
Xi ≧0 （ i=1,2,3 … 8,9）
综上所述决策者所需考虑的区域内各个化工厂应处理的工业污水量 Xi应满足上述所有不等式方程。我们将这些不等式方程构成的方程组称为 污水治理的约束条件。
27
线性规划 Linear Programming（ LP）
1
9
4
5
8
2
6
3
7
案 例 河流污染治理规划问题另一方面污水治理的总成本可表示为 Z
Z=3X1+5X2+2X3+4X4+5X5+6X6+1X7+2X8+3X9
而决策者的目标是确定 满足 约束条件的 Xi使得 Z取得最小值。
将上述分析归纳后即可得如下数学符合模型：
28
线性规划 Linear Programming（ LP）
1
9
4
5
8
2
6
3
7
案 例 河流污染治理规划问题数学模型（整理之后）
Min Z= 3X1 +5X2 +2X3 +4X4 +5X5 +6X6 +1X7 +2X8 +3X9
X2 ≧ 0.4
X8 ≧ 1.6
X1 +0.8X2 +0.8X8 ≧ 4.4
X9 ≧ 0.1
X7 +0.8 X9 ≧ 0.8
X4 +0.8X7 +0.64X9 ≧ 2.16
X6 ≧ 0.2
X5 +0.8X6 ≧ 0.6
X3 +0.8X4 +0.8X5 +0.64X6 +0.64X7 +5.12X9 ≧ 9.4
Xi ≧ 0 （ i=1,2,3,4,5,6,7,8,9）
s.t.
29
线性规划 Linear Programming（ LP）
基本概念线性规划模型
—— Linear Programming Model
或 Linear Optimization Model
用线性规划方法解决实际问题的第一步是建立能够完整描述和反映实际问题的线性规划模型。
30
线性规划 Linear Programming（ LP）
基本概念通常建立 LP模型有以下几个步骤：
1,确定决策变量,决策变量是模型要确定的未知变量，也是模型最重要的参数，是决策者解决实际问题的控制变量。
2,确定目标函数,目标函数决定线性规划问题的优化方向，是模型的重要组成部分。实际问题的目标可表示为决策变量的一个线性函数，并根据实际问题的优化方向求其最大化（ max）或最小化（ min）。
3,确定约束方程,一个正确的线性规划模型应能通过约束方程来描述和反映一系列客观条件或环境的限制，这些限制通过一系列线性等式或不等式方程组来描述。
4,变量取值限制,一般情况下，决策变量取正值（非负值）。因此，模型中应有变量的非负约束即 Xj≥0，但也存在例外。
31
线性规划 Linear Programming（ LP）
基本概念线性规划的一般形式,
max（或 min） z = c1x1 + c2x2 + … + cnxn
a11x1 + a12x2 +… + a1nxn （ ≤ = ≥ ） b1
a21x1 + a22x2 +… + a2nxn （ ≤ = ≥ ） b2
s.t,… … … … … …
am1x1 + am2x2 +… + amnxn （ ≤ = ≥ ） bm
xj ≥ 0 （ j=1,2 … n）
32
线性规划 Linear Programming（ LP）
基本概念线性规划问题的标准形式
1、目标函数极大化 ——,max,
2、等式约束条件 ——,=,
3、变量非负 ——,xj ≥ 0,
max z = c1x1 + c2x2 + … + cnxn
a11x1 + a12x2 +… + a1nxn = b1
a21x1 + a22x2 +… + a2nxn = b2
s.t,… … … … …
am1x1 + am2x2 +… + amnxn = bm
xj ≥ 0 （ j=1,2 … n）
33
线性规划 Linear Programming（ LP）
基本概念化标准形式的一般步骤
1、目标函数极小化?,极大化,
2、约束条件的右端项 bi≤0?,bi≥0,
3、约束条件为不等式 ≤ 或 ≥?,=”
4、取值无约束（自由）变量?,非负变量,
5、取值非正变量?,非负变量,
34
线性规划 Linear Programming（ LP）
基本概念线性规划问题的求解解：（图解）
如何求解一般的线性规划呢？
下面我们分析一下简单的情况 —— 只有两个决策变量的线性规划问题，这时可以通过图解的方法来求解。图解法具有简单、直观、便于初学者窥探线性规划基本原理和几何意义等优点。
35
线性规划 Linear Programming（ LP）
基本概念例 1（ page 11）
max z = 2x1 + x2
5x2 ≤ 15
s.t,6x1 + 2x2 ≤ 24
x1 + x2 ≤ 5
x1,x2 ≥ 0
36
线性规划 Linear Programming（ LP）
基本概念 max z = 2x1 + x2
5x2 ≤ 15
s.t,6x1 + 2x2 ≤ 24
x1 + x2 ≤ 5
x1,x2 ≥ 0
37
线性规划 Linear Programming（ LP）
基本概念例
max Z = 2X1 + X2
X1 + 1.9X2 ≥ 3.8
X1 - 1.9X2 ≤ 3.8
s.t,X1 + 1.9X2 ≤10.2
X1 - 1.9X2 ≥ -3.8
X1,X2 ≥ 0
38
线性规划 Linear Programming（ LP）
基本概念
max Z = 2X1 + X2
x1
x2
o
X1 - 1.9X2 = 3.8(≤)
X1 + 1.9X2 = 3.8(≥)
X1 - 1.9X2 = -3.8 (≥)
X1 + 1.9X2 = 10.2(≤)
4 = 2X1 + X2 20 = 2X1 + X2
17.2 = 2X1 + X211 = 2X
1 + X2
Lo,0 = 2X1 + X2
（ 7.6,2）D
max Z
min Z
此点是唯一最优解，
且最优目标函数值
max Z=17.2
可行域
39
线性规划 Linear Programming（ LP）
基本概念
max Z = 3X1+5.7X2
x1
x2
o
X1 - 1.9X2 = 3.8 (≤)
X1 + 1.9X2 = 3.8(≥)
X1 - 1.9X2 = -3.8(≥)
X1 + 1.9X2 = 10.2 (≤)
（ 7.6,2）D
L0,0=3X1+5.7X2
max Z
min Z
（ 3.8,4）
34.2 = 3X1+5.7X2
绿色线段上的所有点都是最优解这种情形为有无穷多最优解，但是最优目标函数值
max Z=34.2是唯一的。
可行域
40
线性规划 Linear Programming（ LP）
基本概念
min Z = 5X1+4X2
x1
x2
o
X1 - 1.9X2 = 3.8 (≤)
X1 + 1.9X2 = 3.8(≥)
X1 - 1.9X2 = -3.8(≥)
X1 + 1.9X2 = 10.2 (≤)
D
L0,0=5X1+4X2
max Z
min Z
8=5X1+4X2 43=5X1+4X2
（ 0,2） 可行域此点是唯一最优解
41
线性规划 Linear Programming（ LP）
基本概念图解法的启示
1,线性规划问题解的可能情况
a.唯一最优解
b.无穷多最优解
c.无解（没有有界最优解，无可行解）
2,若线性规划问题的可行域非空，则可行域是一个凸集；
3,若线性规划问题的最优解存在，则一定可以在可行域的凸集的某个顶点上达到。
42
线性规划 Linear Programming（ LP）
单纯形法单纯形方法是 G.B.Danzig于 1947年首先发明的。近 50
年来，一直是求解线性规划的最有效的方法之一，被广泛应用于各种线性规划问题的求解。本节讨论单纯形法的基本概念、
原理及算法。
43
线性规划 Linear Programming（ LP）
单纯形法给定线性规划问题（标准形式）
max z = c1x1 + c2x2 + … + cnxn
a11x1 + a12x2 +… + a1nxn = b1
a21x1 + a22x2 +… + a2nxn = b2
s.t,… … … … …
am1x1 + am2x2 +… + amnxn = bm
xj ≥ 0 （ j=1,2 … n）
44
线性规划 Linear Programming（ LP）
单纯形法一、线性规划问题的解的概念可行解最优解基基解（基本解）
基可行解可行基
45
线性规划 Linear Programming（ LP）
单纯形法二、凸集及其顶点凸集顶点（极点）
凸集 凹集
46
线性规划 Linear Programming（ LP）
1
2
3
4
5
6
78
47
线性规划 Linear Programming（ LP）
单纯形法三、线性规划基本定理基本定理 1 线性规划所有可行解组成的集合 S= { X | AX = b,X ≥0 }是 凸集。
基本定理 2 X是线性规划问题的 基本可行解的充要条件 为 是 X 是凸集
S={ X | AX = b,X ≥0 }的极点。
基本定理 3 给定线性规划问题,A是秩为 m 的 m? n 矩阵，
（ i） 若线性规划问题存在 可行解，则必 存在 基本可行解
（ ii） 若线性规划问题存在有界最优解,则必 存在有界最优 基本可行解。
48
线性规划 Linear Programming（ LP）
单纯形法单纯形法迭代原理及其思路单纯形法的初步讨论例 1.8 求解 LP问题
Max Z = 50X1+30X2
s.t,4X1+3X2 ≤120
2X1+ X2 ≤ 50
X1,X2 ≥0
Max Z = 50X1+30X2
s.t,4X1+3X2 +X3 = 120
2X1+ X2 + X4 = 50
X1,X2,X3,X4 ≥0
化为 标准型
（ 1.18）
49
线性规划 Linear Programming（ LP）
单纯形法此线性规划问题 转化为了一个含有四个变量的 标准形 线性规划问题,X3,X4为松弛变量。为求解上面的 LP问题，我们要考虑满足约束条件 s.t.并使 Z 取得 Max的 X1,X2,X3，
X4的值，由此分析如下 ---
50
线性规划 Linear Programming（ LP）
单纯形法确定初始基可行解：
通过观察可以发现，松弛变量 X3和 X4对应的等式 约束条件中的系数矩阵为单位矩阵可以作为初始 可行基 矩阵。因此取,X3,X4为基变量； X1,X2为非基变量。则（ 1.18）可变为
Max Z =50X1+30X2
s.t,X3 = 120 - 4X1 - 3X2
X4= 50 - 2X1 - X2 （ 1.19）
X1,X2,X3,X4≥0
51
线性规划 Linear Programming（ LP）
单纯形法典式
（ 1.19）或 （ 1.18） 称为关于基的 典式 ——
1,等式 约束条件中显含 基可行解
2、目标函数中不 含 基 变量
Max Z = 50X1+30X2
s.t,4X1+3X2 +X3 = 120
2X1+ X2 + X4 = 50 (1.18)
X1,X2,X3,X4 ≥0
Max Z =50X1+30X2
s.t,X3 = 120 - 4X1 - 3X2
X4= 50 - 2X1 - X2 （ 1.19）
X1,X2,X3,X4≥0
52
线性规划 Linear Programming（ LP）
单纯形法在典式 （ 1.19） 中令,X1=X2 =0，
我们得到一个 基本可行解
X1=（ X1,X2,X3,X4 ） T=（ 0,0,120,50） T,
其对应的目标函数值 Z1 = 50X1 + 30X2 = 0
53
线性规划 Linear Programming（ LP）
单纯形法最优性检验：
基本可行解 X1是最优解吗？显然不是。应寻找更好的解。
从问题的数学角度分析，在典式 （ 1.19） 的目标函数中,非基变量 X1,X2前的系数都为正，表明 目标函数值有增加的可能。
只要将目标函数中 系数为正的某 非基变量 与某一基变量地位对换。
54
线性规划 Linear Programming（ LP）
单纯形法换基迭代：
进行 换基就是要从非基变量中选一个变量 入基,再从基变量中选一个变量 出基 。并且换基后仍需满足：
1,新的解仍是基本 可行解；
2,目标函数值将得到改善。
55
线性规划 Linear Programming（ LP）
单纯形法选择入基变量,由于在目标函数 Z1=50X1+30X2 中 X1,X2的系数都为正，哪一个入基都可使目标函数值得到改善。对于求目标函数极大化的问题，我们希望目标值增加得越快越好，因此系数最大的 X1入基。
选择出基变量,X1入基后，其值从零增加并由于 约束条件的原因会引起其他变量的变化。由 典式 （ 1.19） 以及变量必须取正值的条件，我们可以得到下列不等式关系：
X3 = 120 - 4X1- 3X2 ≥0
X4= 50 - 2X1- X2 ≥0
56
线性规划 Linear Programming（ LP）
单纯形法因为迭代后 X2仍为 非基变量 （ 仍会令其取值为零 ）,则上式可简化为：
120 - 4X1 ≥0 由此可以看出，虽然我们希望 X1入基后取正值，且
50 - 2X1 ≥0 取值越大目标值增加越大，但是,X1又得受到 约束。
显然，只有 取 X1 =min（ 120/4,50/2） =25时，才能使上述不等式成立并且恰使 基变量 X4变为零，这正好满足非基变量必须取 值 零的条件，
所以可 令 X4 出基,方程变为：
4X1+ X3 =120 - 3X2
2X1 = 50 - X2 - X4
化简后得,新的 典式 方程 X3 = 20 - X2 + 2X4
X1 = 25 -0.5X2 -0.5X4
57
线性规划 Linear Programming（ LP）
单纯形法代入目标函数可得,Z2 =1250+5X2-25X4
令 非基变量 X2 =X4 = 0，即可得一个新的 基本可行解
X2 =（ 25,0,20,0） T,其对应的目标函数值 Z2 =1250，并完成了第一次 迭代。
由于 目标函数 Z2 =1250+5X2-25X4中 X2的系数仍为正，该解 X2仍不是最优解。重复上述 迭代过程得到,X2入基,X3出基，则新的 典式 方程变为：
X1 = 15 +0.5X3 - 1.5X4
X2 =20 - X3 + 2X4
Z3 =1350 -5X3 - 15X4
58
线性规划 Linear Programming（ LP）
单纯形法第三个 基本可行解 X3 =（ 15,20,0,0） T，其对应的目标函数值 Z3=
1350 。 此时松弛变量 都是 非基变量 （ 取值为零 ）,这表明资源已用尽；并且目标函数值 Z3=1350 -5X3 - 15X4中 非基变量 X3,X4的系数全为负值，说明目标函数已无法进一步改善，因此该解已是最优解。
59
线性规划 Linear Programming（ LP）
单纯形法单纯形法小结：
单纯形法是这样一种 迭代算法 —— 如下图 …
当 Zk中 非基变量 的系数的系数全为负值时，这时的 基本可行解 Xk即是线性规划问题的最优解,迭代结束。
X1
Z1
保持 单调增保持 可行 性 保持 可行 性 保持 可行 性 保持 可行 性保持 单调增 保持 单调增 保持 单调增
X2 X3,.,Xk
Z2 Z3,.,Zk
当 Zk 中 非基变量 的系数的系数全为负值时，这时的 基本可行解 Xk 即是线性规划问题的最优解,迭代结束。
60
线性规划 Linear Programming（ LP）
单纯形法单纯形表对于给定的线性规划问题：
max Z = c1x1 + c2x2 + … + cnxn
a11x1 + a12x2 + … + a1nxn≤ b1
a21x1 + a22x2 + … + a2nxn≤ b2
s.t,… … …
am1x1 + am2x2 + … + amnxn≤ bm
xj ≥ 0 （ j=1,2 … n）
对此问题添加 m个松弛变量后，可得下面线性规划问题并且是 典式的形式。
61
线性规划 Linear Programming（ LP）
单纯形法线性规划的典式
max Z = c1x1 + c2x2 + … + cnxn
a11x1 + a12x2 +… + a1nxn + xn+1 = b1
a21x1 + a22x2 +… + a2nxn + xn+2 = b2
s.t,…
am1x1 + am2x2 +… + amnxn + xn+m = bm
xj ≥ 0 （ j=1,2 … n,n+1,n+2,… n+m）
62
线性规划 Linear Programming（ LP）
单纯形法单纯形表：
将上面 典式中各变量及系数填写在一张表格中就形成下面的 单纯形表
cj? c1 c2 … c n cn+1 cn+2 … c n+m
C
B 基 解 x1 x2 … x n xn+1 xn+2 … x n+1
0
0
0
0
xn+1
xn+1
…
xn+1
b1
b2
…
bm
a11 a12 … a 1n 1
a21 a22 … a 2n 1
… … … … …
am1 am2 … a mn 1
1
2
…
m
j = cj – zj? c1 c2 … c n 0 0 … 0
j = cj – zj1? 2 …? n?n+1?n+2 …?n+m
63
线性规划 Linear Programming（ LP）
单纯形法单纯形表：
上面 的 单纯形表还可以表示成矩阵的形式基 解 X XS?
XS b A I
j? C 0
基 解 XB XN XS?
XS b B N I
j? CB CN 0
64
线性规划 Linear Programming（ LP）
单纯形法由单纯形表进行 迭代步骤：
1,选择 Xj 入基：当?j 行中 cj= max ci∣ ci? 0
2,选择 Xi 出基：当?i= min bi/aij∣ aij? 0
3,换基 迭代：当确定了 入基变量 Xj,出基变量 Xi 后，以 aij 作为主元对单纯形表进行初等行变换（取 主 运算），即将 aij 所在列除采用初等行变换 将 aii 变换为 1外的其余元素都 变换为 0。注意这种 变换只能采用初等行变换 !
65
线性规划 Linear Programming（ LP）
单纯形法最优解检验：
1,当迭代进行至某一步时,? j 行中所有 检验数均小于等于零，
则 迭代结束。 表中当前 所指 基本可行解即为 最优解。
2,当迭代进行至某一步时,? j 行中所有 检验数均小于等于零，
且此时至少有一个 非基变量所对应的 检验数 rk等于零，则原线性规划问题有无穷多个 最优解。
3,当迭代进行至某一步时,? j 行中至少有一个 检验数 rk 大于零，
且该检验数对应的 列中 a1k,a2k,… amk,均 小 于等于 零，则原线性规划问题 最优解无界（ max Z→ +∞）。
66
线性规划 Linear Programming（ LP）
单纯形法单纯形方法的矩阵描述：
设线性规划问题 max Z = CX max Z = CX + 0XS
s.t,AX ≤ b s.t,AX + I XS = b （ I 式 ）
X ≥ 0 X,XS ≥ 0
其中 b ≥ 0,I 是 m?m 单位 矩阵。
对上面 （ I 式 ） 经过迭代,并设最终的最优基矩阵为 B（不妨设 B为 A 的首 m 列，则将（ I 式 ）改写后有
67
线性规划 Linear Programming（ LP）
单纯形法
max Z = CBXB + CNXN + 0XS
s.t,BXB + NXN + I XS = b
XB,XN,XS ≥ 0
max Z = CB B -1+（ CN- CB B -1） XN - CB B -1XS
s.t,XB + B -1NXN + B -1XS = B -1b
XB,XN,XS ≥ 0
B 式中 最优 目标函数值 Z*= CB B -1,检验数 CN - CB B -1 ≤ 0,- CB B -1 ≤ 0
单纯形方法 迭代（ I 式） （ B 式 ）
68
线性规划 Linear Programming（ LP）
单纯形法单纯形方法的矩阵描述：
基 解 XB XN XS?
XS b B N I
j? CB CN 0
基 解 XB XN XS?
XB B -1b I B -1N B -1
j? 0 CN - CB B –1N - CB B -1
对应 I 式 的 单纯形表 ——I 表对应 B式 的 单纯形表 —— B 表迭代
69
线性规划 Linear Programming（ LP）
单纯形表计算步骤举例给定线性规划问题 max z = 50X
1 + 30X2
s.t,4X1+3X2 ≤ 120
2X1+ X2 ≤ 50
X1,X2 ≥ 0
max z = 50X1 + 30X2
s.t,4X1+ 3X2 + X3 = 120
2X1+ X2 + X4 = 50
X1,X2,X3,X4 ≥ 0
70
线性规划 Linear Programming（ LP）
单纯形表计算步骤举例给定线性规划问题
max z = 50X1 + 30X2
s.t,4X1+ 3X2 + X3 = 120
2X1+ X2 + X4 = 50
X1,X2,X3,X4 ≥ 0
基 XB 解 B-1b X1 X2 X3 X4?
X3 120 4 3 1 0
X4 50 2 1 0 1
检验数?j 50 30 0 0
120/4
50/21 1 1/2 1/225
020 1 - 2
0 5 - 25
20/1
25× 2
2
15 0 - 1/2 3
0 - 5 15
71
线性规划 Linear Programming（ LP）
单纯形法的进一步讨论人工变量法：
当一般线性规划问题标准化之后，我们或可得到一个显然的 基本可行解（如 松弛变量作为 基变量的一个 初始 基本可行解），这样我们就可以马上进入 单纯形表的运算步骤。然而，并非所有 问题标准化之后我们都可得到一个显然的 初始 基本可行解,这时就需要我们首先确定出一个 基本可行解作为 初始 基本可行解。通常采用的是人工变量法来确定这样的 初始 基本可行解。这种情况下一般有两种方法：
1、大 M法（罚因子法）
2、两阶段法
72
线性规划 Linear Programming（ LP）
单纯形法的进一步讨论
1、大 M 法（罚因子法）
max z = - 3X1 + X3
x1 + x2 + x3 ≤ 4
- 2x1 + x2 – x3 ≥ 1
3x2 + x3 = 9
x1,x2,x3 ≥ 0
LPM max z = - 3x1 + x3 + 0x4 + 0x5 – Mx6 – Mx7
x1 + x2 + x3 + x4 = 4
- 2x1 + x2 – x3 - x5 + x6 = 1
3x2 + x3 +x7 = 9
x1,x2,x3,x4,x5,x6,x7 ≥ 0
73
线性规划 Linear Programming（ LP）
1、大 M 法 LPM max z = - 3x1 + x3 + 0x4 + 0x5 – Mx6 – Mx7
x1 + x2 + x3 + x4 = 4
- 2x1 + x2 – x3 - x5 + x6 = 1
3x2 + x3 +x7 = 9
x1,x2,x3,x4,x5,x6,x7 ≥ 0
基 XB 解 B-1b X1 X2 X3 X4 X5 X6 X7?
X4 4 1 1 1 1 0 0 0
X6 1 -2 1 -1 0 -1 1 0
X7 9 0 3 1 0 0 0 1
检验数?j -3 0 1 0 0 -M -M
74
线性规划 Linear Programming（ LP）
1、大 M 法基 XB 解 B-1b X1 X2 X3 X4 X5 X6 X7?
X4 4 1 1 1 1 0 0 0
X6 1 -2 1 -1 0 -1 1 0
X7 9 0 3 1 0 0 0 1
检验数?j -3-2M M 1-M 0 -M 0 -M
基 XB 解 B-1b X1 X2 X3 X4 X5 X6 X7?
X4 4 1 1 1 1 0 0 0
X6 1 -2 1 -1 0 -1 1 0
X7 9 0 3 1 0 0 0 1
检验数?j -3-2M 4M 1 0 -M 0 0
75
线性规划 Linear Programming（ LP）
1、大 M 法基 XB 解 B-1b X1 X2 X3 X4 X5 X6 X7?
X4 4 1 1 1 1 0 0 0 4
X6 1 -2 1 -1 0 -1 1 0 1
X7 9 0 3 1 0 0 0 1 3
检验数?j -3-2M 4M 1 0 -M 0 0
基 XB 解 B-1b X1 X2 X3 X4 X5 X6 X7?
X4 3 3 0 2 1 1 -1 0
X2 1 -2 1 -1 0 -1 1 0
X7 6 6 0 4 0 3 -3 1
检验数?j -3+6M 0 1+4M 0 3M -4M 0
76
线性规划 Linear Programming（ LP）
1、大 M 法基 XB 解 B-1b X1 X2 X3 X4 X5 X6 X7?
X4 3 3 0 2 1 1 -1 0 1
X2 1 -2 1 -1 0 -1 1 0 ---
X7 6 6 0 4 0 3 -3 1 1
检验数?j -3+6M 0 1+4M 0 3M -4M 0
基 XB 解 B-1b X1 X2 X3 X4 X5 X6 X7?
X4 0 0 0 0 1 -1/2 1/2 -1/2
X2 3 0 1 1/3 0 0 0 1/3
X1 1 1 0 2/3 0 1/2 -1/2 1/6
检验数?j 0 0 3 0 1.5 -1.5-M 0.5-M
77
线性规划 Linear Programming（ LP）
1、大 M 法基 XB 解 B-1b X1 X2 X3 X4 X5 X6 X7?
X4 0 0 0 0 1 -1/2 1/2 -1/2 ---
X2 3 0 1 1/3 0 0 0 1/3 9
X1 1 1 0 2/3 0 1/2 -1/2 1/6 3/2
检验数?j 0 0 3 0 1.5 -1.5-M 0.5-M
基 XB 解 B-1b X1 X2 X3 X4 X5 X6 X7?
X4 0 0 0 0 1 -1/2 1/2 -1/2
X2 5/2 -1/2 1 0 0 -1/4 1/4 1/4
X3 3/2 3/2 0 1 0 3/4 -3/4 1/4
检验数?j -9/2 0 0 0 -3/4 3/4-M -1/4-M
78
线性规划 Linear Programming（ LP）
单纯形法的进一步讨论采用大 M 法求解线性规划问题时可能出现的几种情况：
1、当采用单纯形法求解 LPM 得到最优解时，基变量 不含 任何人工变量，则所得到的最优解就是原问题的最优解；
2、当采用单纯形法求解 LPM 得到最优解时，基变量至少 含有 一个人工变量且 非零,则原问题无可行解；
3、当采用单纯形法求解 LPM 得到最优解时，基变量至少 含有 一个人工变量且人工变量都 为零,则通过变换得到原问题最优解；
79
线性规划 Linear Programming（ LP）
单纯形法的进一步讨论
2、两阶段法
max z = - 3X1 + X3
x1 + x2 + x3 ≤ 4
- 2x1 + x2 – x3 ≥ 1
3x2 + x3 = 9
x1,x2,x3 ≥ 0
I阶段问题 max z = – x6 – x7
x1 + x2 + x3 + x4 = 4
- 2x1 + x2 – x3 - x5 + x6 = 1
3x2 + x3 +x7 = 9
x1,x2,x3,x4,x5,x6,x7 ≥ 0
80
线性规划 Linear Programming（ LP）
2、两阶段法 I 阶段问题 max z = – x6 – x7
x1 + x2 + x3 + x4 = 4
- 2x1 + x2 – x3 - x5 + x6 = 1
3x2 + x3 +x7 = 9
x1,x2,x3,x4,x5,x6,x7 ≥ 0
基 XB 解 B-1b X1 X2 X3 X4 X5 X6 X7?
X4 4 1 1 1 1 0 0 0
X6 1 -2 1 -1 0 -1 1 0
X7 9 0 3 1 0 0 0 1
检验数?j 0 0 0 0 0 -1 -1
81
线性规划 Linear Programming（ LP）
2、两阶段法 ——第 I 阶段基 XB 解 B-1b X1 X2 X3 X4 X5 X6 X7?
X4 4 1 1 1 1 0 0 0
X6 1 -2 1 -1 0 -1 1 0
X7 9 0 3 1 0 0 0 1
检验数?j 0 0 0 0 0 -1 -1
基 XB 解 B-1b X1 X2 X3 X4 X5 X6 X7?
X4 4 1 1 1 1 0 0 0
X6 1 -2 1 -1 0 -1 1 0
X7 9 0 3 1 0 0 0 1
检验数?j -2 4 0 0 -1 0 0
82
线性规划 Linear Programming（ LP）
2、两阶段法 ——第 I 阶段基 XB 解 B-1b X1 X2 X3 X4 X5 X6 X7?
X4 4 1 1 1 1 0 0 0 4
X6 1 -2 1 -1 0 -1 1 0 1
X7 9 0 3 1 0 0 0 1 3
检验数?j -2 4 0 0 -1 0 0
基 XB 解 B-1b X1 X2 X3 X4 X5 X6 X7?
X4 3 3 0 2 1 1 -1 0
X2 1 -2 1 -1 0 -1 1 0
X7 6 6 0 4 0 3 -3 1
检验数?j 6 0 4 0 3 -4 0
83
线性规划 Linear Programming（ LP）
2、两阶段法 ——第 I 阶段基 XB 解 B-1b X1 X2 X3 X4 X5 X6 X7?
X4 3 3 0 2 1 1 -1 0 1
X2 1 -2 1 -1 0 -1 1 0 ---
X7 6 6 0 4 0 3 -3 1 1
检验数?j 6 0 4 0 3 -4 0
基 XB 解 B-1b X1 X2 X3 X4 X5 X6 X7?
X4 0 0 0 0 1 -1/2 1/2 -1/2
X2 3 0 1 1/3 0 0 0 1/3
X1 1 1 0 2/3 0 1/2 -1/2 1/6
检验数?j 0 0 0 0 0 -1 -1
84
线性规划 Linear Programming（ LP）
2、两阶段法 ——第 II 阶段基 XB 解 B-1b X1 X2 X3 X4 X5 X6 X7?
X4 0 0 0 0 1 -1/2 1/2 -1/2
X2 3 0 1 1/3 0 0 0 1/3
X1 1 1 0 2/3 0 1/2 -1/2 1/6
检验数?j 0 0 0 0 0 -1 -1
基 XB 解 B-1b X1 X2 X3 X4 X5?
X4 0 0 0 0 1 -1/2
X2 3 0 1 1/3 0 0
X1 1 1 0 2/3 0 1/2
检验数?j 0 0 3 0 3/2
-3 1
85
线性规划 Linear Programming（ LP）
2、两阶段法 ——第 II 阶段基 XB 解 B-1b X1 X2 X3 X4 X5?
X4 0 0 0 0 1 -1/2 ---
X2 3 0 1 1/3 0 0 9
X1 1 1 0 2/3 0 1/2 3/2
检验数?j 0 0 3 0 3/2
基 XB 解 B-1b X1 X2 X3 X4 X5?
X4 0 0 0 0 1 -1/2
X2 5/2 -1/2 1 0 0 -1/4
X3 3/2 3/2 0 1 0 3/4
检验数?j -9/2 0 0 0 -3/4
86
线性规划 Linear Programming（ LP）
单纯形法中的几个问题
1,目标函数极小化时，解的最优判别：
j ≥ 0
2,退化：
一个或几个 基变量 等于零，一个简单易行的避免退化的方法是 1974
年由勃兰德（ Bland）提出的 Bkand 法则。
3,无可行解的判别：
在采用人工变量求解线性规划问题得到最优解时，如果基变量中仍含有 非零人工变量,则原问题无可行解。
87
线性规划 Linear Programming（ LP）
数据包络分析 DEA （ date envelopment analysis）
概念一种基于线性规划的用于评价同类型组织（或项目）工作绩效相对有效性 的特殊工具手段。这类组织例如学校、医院、银行的分支机构、超市的各个营业部等，各自具有相同的投入相同的产出。
衡量这类组织之间的绩效高低，通常采用投入产出比这个指标，当各自的投入产出均可折算成同一单位计量时，容易计算出各自的投入产出比并按其大小进行绩效排序。但当被衡量的同类型组织有多项投入和多项产出，且不能折算成统一单位时，就无法算出投入产出比的数值，因而，需采用一种全新的方法进行绩效比较。这种方法就是二十世纪七十年代末产生的数据包络分析 DEA。
88
线性规划 Linear Programming（ LP）
数据包络分析 DEA （ date envelopment analysis）
概念
1978年，著名运筹学家、美国德克萨斯大学教授 A.Charnes及
W.W.Cooperh和 E.Rhodes发表了一篇重要论文：,Measuring
the efficiency of decision making units‖（决策单元的有效性度量），刊登在权威的“欧洲运筹学杂志”上。正式提出了运筹学的一个新领域：数据包络分析。其模型简称 C2R 模型。
89
线性规划 Linear Programming（ LP）
数据包络分析 DEA （ date envelopment analysis）
相对有效性评价问题举例例 1：硕士点教育质量评价某系统工程研究所对我国金属热处理专业的 26个硕士点的教育质量，进行了有效性评价。
评价采用的指标体系为：
输入：导师人数；实验设备；图书资料；学生入学情况。
输出：科研成果；论文篇数；学生毕业时的情况。
使用 DEA进行评价，结果基本合理。
90
线性规划 Linear Programming（ LP）
数据包络分析 DEA （ date envelopment analysis）
相对有效性评价问题举例例 2：行风（行业作风）建设有效性评价本项目研究人员选定江苏省 S市交通客运系统作为对象，包括 7家交通客运汽车公司。
评价采用的指标基础依据为：
1、国际公交组织颁布的“十项基本考核指标”
2、国内颁布的公交运营服务的“八项考核指标”。
在此基础上，根据该系统实际情况，最终选定了输入指标 4项，输出指标 4项。分别是：
91
线性规划 Linear Programming（ LP）
数据包络分析 DEA （ date envelopment analysis）
相对有效性评价问题举例输入指标,1、年末职工总熟（单位：人）；
2、单位成本（单位：元 /千人公里）；
3、燃料单位消耗（单位：升 /千人公里）；
4、行车责任事故率（单位：次 /千人公里）。
输出指标,1、劳动生产率（单位：元 /人）；
2、行车准点率（ %）；
3、群众满意率（按问卷调查）（ %）
4、车辆服务合格率（包括：服务态度、服务措施、车辆设施等）（ %）
92
线性规划 Linear Programming（ LP）
数据包络分析 DEA （ date envelopment analysis）
相对有效性评价问题举例收集到所需数据后，使用 DEA方法综合评价，结果为：
1,3家公司为行风建设有效；
2,4家公司在行风建设上存在不同程度（以量化形式给出）的缺点与不足。
93
线性规划 Linear Programming（ LP）
数据包络分析 DEA （ date envelopment analysis）
相对有效性评价问题举例
4所小学 S1,S2,S3,S4，在校学生分别为 1200,100,1600，
1400人，按 800名标准学生的规模折算各个学校的教职工人数和建筑面积的投入，如下表：
学 校投 入 S1 S2 S3 S4
教职工人数建筑面积 /m2
25
1800
40
1500
35
1700
20
2500
94
线性规划 Linear Programming（ LP）
数据包络分析 DEA （ date envelopment analysis ）
相对有效性评价问题举例教职工人数建筑面积生产前沿线（面）
S4
S1 S3
S2
M
数据包络线
95
线性规划 Linear Programming（ LP）
数据包络分析 DEA （ date envelopment analysis）
相对有效性评价问题线性规划数学模型在 DEA中一般称被衡量绩效的组织为决策单元（ decision
making unit——DMU）。
设,n 个决策单元（ j = 1,2,…,n ）
每个决策单元有相同的 m 项投入（输入）（ i = 1,2,…,m ）
每个决策单元有相同的 s 项产出（输出） （ r = 1,2,…,s ）
Xij ——第 j 决策单元的第 i 项投入
yrj ——第 j 决策单元的第 r 项产出衡量第 j0 决策单元是否 DEA有效
96
线性规划 Linear Programming（ LP）
数据包络分析 DEA （ date envelopment analysis）
相对有效性评价问题线性规划数学模型决策单元 1 2 … n
投入项目
1
2
…
m
X11 X12 … X1n
X21 X22 … X2n
… … … …
Xm1 Xm2 … Xmn
1 2 … n 决策单元
y11 y12 … y1n
y21 y22 … y2n
… … … …
ys1 ys2 … ysn
1
2
…
s
产出项目
97
线性规划 Linear Programming（ LP）
数据包络分析 DEA （ date envelopment analysis）
相对有效性评价问题线性规划数学模型构建模型的思路：
衡量某一决策单元 j0 是否 DEA有效 ——是否处于由包络线组成的生产前沿面上，先构造一个由 n 个决策单元组成 （线性组合成）
的 假想决策单元 。如果该假想单元的各项产出均 不低于 j0 决策单元的各项产出，它的各项投入均 低于 j0 决策单元的各项的各项投入。
即有：
98
线性规划 Linear Programming（ LP）
数据包络分析 DEA （ date envelopment analysis）
相对有效性评价问题线性规划数学模型
∑?j yrj ≥ yrj0 （ r = 1,2,…,s）
∑?j xij ≤ E xij0 （ i = 1,2,…,m,E＜ 1）
∑?j = 1,?j ≥0 （ j = 1,2,…,n）
j=1
j=1
j=1
n
n
n
这说明 j0 决策单元不处于生产前沿面上。
99
线性规划 Linear Programming（ LP）
数据包络分析 DEA （ date envelopment analysis）
相对有效性评价问题线性规划数学模型基于上述事实，可以写出如下线性规划的数学模型：
min E
S.t.
∑?j yrj ≥ yrj0 （ r = 1,2,…,s）
∑?j xij ≤ E xij0 （ i = 1,2,…,m）
∑?j = 1,?j ≥0 （ j = 1,2,…,n）
j=1
j=1
j=1
n
n
n
100
线性规划 Linear Programming（ LP）
数据包络分析 DEA （ date envelopment analysis）
相对有效性评价问题线性规划数学模型结果分析：
1、当求解结果有 E ＜ 1 时，则 j0 决策单元 非 DEA有效；
2,否则，则 j0 决策单元 DEA有效。
101
线性规划 Linear Programming（ LP）
数据包络分析 DEA （ date envelopment analysis）
相对有效性评价问题线性规划数学模型例 8（ Page 39） 振华银行的 4 个分理处的投入产出如下表。求各个分理处的运行是否 DEA有效。 产出单位：处理笔数 /月分理处 投入 产出职员数 营业面积（ m2） 储蓄存取 贷款 中间业务分理处 1
分理处 2
分理处 3
分理处 4
15
20
21
20
140
130
120
135
1800
1000
800
900
200
350
450
420
1600
1000
1300
1500
102
线性规划 Linear Programming（ LP）
数据包络分析 DEA （ date envelopment analysis）
相对有效性评价问题线性规划数学模型解,若先确定 分理处 1的运行是否 DEA有效。建立线性规划模型 min E
1800?1 +1000?2 + 800?3 + 900?4 ≥1800
200?1 + 350?2 + 450?3 + 420?4 ≥ 200
1600?1 +1000?2 +1300?3 +1500?4 ≥1600
S.t,15?1 + 20?2 + 21?3 + 20?4 ≤ 15E
140?1 + 130?2 + 120?3 + 135?4 ≤140E
1 +?2 +?3 +?4 = 1
j ≥0 （ j = 1,2,3,4 ）
103
线性规划 Linear Programming（ LP）
数据包络分析 DEA （ date envelopment analysis）
相对有效性评价问题线性规划数学模型求解结果分析：
对 分理处 1,E =1，说明分理处 1的运行 DEA有效。
对 分理处 2,E =0.996，说明分理处 2的运行非 DEA有效。
对 分理处 3,E =1，说明分理处 3的运行 DEA有效。
对 分理处 4,E =1，说明分理处 4的运行 DEA有效。
104
线性规划 Linear Programming（ LP）
数据包络分析 DEA （ date envelopment analysis）
DEA应用中的“窗口”技术 ——空军基地的效率评价（美国）
美国空军军方曾对 7 个空军基地的效率进行了评价，使用的方法为 DEA。输入指标选定 3 项，输出指标选定 4 项（内容未报道）。
评价的时间范围为 1992 年 10 月 1 日至 1993 年 12 月 31 日。尽管具体内容及结果未予公布，但有一项技术 ——―窗口技术”却很有参考价值，介绍如下：
在对决策单元集进行 DEA 评价时，对单元的个数 n,输入指标个数 m,以及输出指标个数 s 应有一定的要求。经验表明它们大体上应满足或接近
n ≥ 2ms
105
线性规划 Linear Programming（ LP）
数据包络分析 DEA （ date envelopment analysis）
DEA应用中的“窗口”技术 ——空军基地的效率评价（美国）
在本例中，空军基地有 7 个，分别记为 A,B,C,D,E,
F,G 。即 n = 7；而输入指标有 3 项，即 m = 3；输出指标有 4
项，即 s = 4 。显然，决策单元数过少了。
实施此项评价的美国学者采取了“分割 ——连接 ——滑动”的处理办法。将评价的时间段变小，将 1992.10.1 ～ 1993.12.31，按季度分割为 5 个季度，将“每个基地 ——每个季度”作为决策单元，
这样就得到了 35 个决策单元。
但在每项评价时，只使用相邻的 3 个季度，即 n = 21,接近
2ms = 2× 3× 4 = 24,将它们构成一个“窗口”。评价结束后，将
“窗口”向下一季度递推，进行第二轮 DEA 评价。如此进行，共作三轮，获得了良好的结果。
106
线性规划 Linear Programming（ LP）
数据包络分析 DEA （ date envelopment analysis）
DEA应用中的“窗口”技术 ——空军基地的效率评价（美国）
季度 1 季度 2 季度 3 季度 4 季度 5
A
B
C
D
E
F
G
A1 A2 A3 A4 A5
B1 B2 B3 B4 B5
… … … … …
… … … … …
… … … … …
F1 F2 F3 F4 F5
G1 G2 G3 G4 G5
107
线性规划 Linear Programming（ LP）
数据包络分析 DEA （ date envelopment analysis）
DEA应用中的“窗口”技术 ——空军基地的效率评价（美国）
窗口技术有许多优点，主要为：
1) 适用于决策单元个数 n 较小的情况。
2) 可以获得各个决策单元关于效率的稳定性。以及变化趋势、季节行为等方面的有价值的辅助信息。
3) 提供了纵向评价（沿时间轴评价）的一种思路。
108
线性规划 Linear Programming（ LP）
线性规划其他应用例子我们应该牢记：,应用线性规划解决经济，管理领域的实际问题时，最重要的一步是建立全面、准确地反映实际问题的线性规划模型,,这是一项技巧性很强的创造性工作，既要求对所研究的问题有深入了解，又要求很好掌握线性规划模型的结构特点，并具有对实际问题进行数学描述的较强能力。因此，在研究建立一些较复杂问题的数学模型时，需要各个方面的专业人员的通力协作配合。
109
线性规划 Linear Programming（ LP）
线性规划其他应用例子一般情况下，一个经济、管理问题要满足下列条件，才能归结为线性规划的模型：
1,要求解的问题的目标能用某种效益指标度量大小，并能用线性函数描述目标的要求；
2,为了达到这个目标存在多种方案；
3,要达到的目标是在一定约束条件下实现的，这些条件可以用一组线性等式或不等式描述。
110
线性规划 Linear Programming（ LP）
线性规划其他应用例子例 一家连琐店公司正在计划明年的广告预算，该公司计划用 1000
万元在报纸、广播和电视上做广告。下表是他们做规划用的统计数据：
统计数据 广告媒体效果 报纸 电台 电视每个广告影响的总人数影响的已婚人数影响平均收入以上的人数最高广告数量限制（个）
最低广告数量限制（个）
每个广告的成本（万元）
50000
15000
20000
100
25
3
100000
20000
30000
150
30
1.5
150000
40000
50000
50
30
15
111
线性规划 Linear Programming（ LP）
线性规划其他应用例子该公司的目标是使广告影响的人数最多，并且满足下面的条件：
1) 至少要影响 500 万人口；
2) 至少要影响 100 万已结婚的人口；
3) 至少要影响 150 万收入在平均收入以上的人口；
4) 在每种媒介上所做的广告要在最高和最低限制数之间。
统计数据 广告媒体效果 报纸 电台 电视每个广告影响的总人数影响的已婚人数影响平均收入以上的人数最低广告数量限制（个）
最高广告数量限制（个）
每个广告的成本（万元）
50000
15000
20000
25
100
3
100000
20000
30000
30
150
1.5
150000
40000
50000
20
50
15
112
线性规划 Linear Programming（ LP）
线性规划其他应用例子例 发电厂有两台锅炉，每台锅炉投入运行时生产的蒸汽量一定要维持在最高产汽量和最低产汽量之间。每个锅炉的产汽量范围和生产成本（如表 1），锅炉生产的蒸汽可送到两台汽轮机组发电，每台汽轮机组的蒸汽消耗量也有最低和最高限制，且运行成本和每吨蒸汽的发电量亦不同（如表 2）。
请建立一个线性规划模型使发电厂在满足 8000度发电计划的前提下运行成本最低。
锅炉号最低产汽量
（吨）
最高产汽量
（吨）
运行成本（元 /
吨）
1
2
400
500
900
1000
8
6
汽轮机号最低用汽量
（吨）
最高用汽量
（吨）
每吨蒸汽生产电量
（度）
运行成本
（元 /
吨）
1
2
500
600
800
900
5
6
3
4
113
线性规划 Linear Programming（ LP）
线性规划其他应用例子例 制造某种机床，需要 A,B,C 三种轴件，其规格与数量如下表，各类轴件都用 5.5 米长的同一种圆钢下料。若计划生产 100 台机床，最少要用多少根圆钢？
轴类 规格：长度（米） 每台机床所需轴件数
A
B
C
3.1
2.1
1.2
1
2
4
114
线性规划 Linear Programming（ LP）
第一章结束谢谢！
,运筹学,课程 教学大纲运筹学 Operations research
课程各章节内容及学时分配
64 学时任课教师：余 勇 Tel,88061330
2
,运筹学,课程 教学大纲课时安排：
序号 课程内容 学时
1 第一讲 管理运筹学序论 2
2 第二讲 线性规划,运输问题,目标规划,整数规划 30
3 *第三讲 非线性规划 2
4 第四讲 动态规划 8
5 第五讲 图与网络分析 8
6 *第七讲 排队论,对策论 2
7 案例讨论，实验 12
3
绪论 历史，性质，应用
20世纪整个世界参与规模最大的事件是什么？
第二次世界大战 ！
整个世界的资源都投入到了第二次世界大战中。
如何才能更好地利用资源，分配有限的资源，这是一个值得研究的问题。
当时在英国军队中率先成立了研究小组 —— 运筹小组来研究这些问题，这就是著名的 OR小组,很快美军中也相继成立了 OR小组。
战争 —— 运筹学诞生的温床。
4
绪论 历史，性质，应用二战中成功的运筹学案例：
英国防空部门如何布置防空雷达，建立最有效的防空警报系统。
英，美空军如何提高对地面目标轰炸的命中率。
如何安排反潜飞机的巡逻飞行线路。
深水炸弹的合理爆炸深度，摧毁德军潜艇数增加 400%。
商船如何编队，遭潜艇攻击时如何减少损失。
使船只受敌机攻击时，中弹数由 47%降到 29%。
这些研究大大提高了盟军的作战能力，为反法西斯战争的最后胜利作出了巨大的贡献！
5
绪论 历史，性质，应用战争结束了！ 整个世界投入到了战后的重建国家的经济之中。
运筹学的方法相继在工业，农业，经济，社会问题等各个领域中展开了应用。与此同时，运筹数学有了飞快的发展，并形成了许多运筹学的分支。
线性规划，非线性规划，整数规划，目标规划，动态规划，
图与网络分析，统筹方法，排队论，存储论，对策论，决策论，多目标决策。
6
绪论 历史，性质，应用
运筹学的性质和特点
a,一种哲学方法论 ;
b,研究“事”而非“物” ;
c,科学性，实践性，系统性，综合性 ;
d,模型的特点 —— 系统优化模型。
运筹学 —— 为决策机构在对其控制下业务活动进行决策时，
提供以数量化为基础的科学方法。
运筹学 —— 一门应用科学，它广泛应用现有的科学技术知识和数学方法，解决实际中提出的专门问题。
运筹学 —— 是一种给出问题坏的答案的艺术，否则问题的结果会更坏。
7
绪论 历史，性质，应用
运筹学的工作步骤运筹学在解决大量实际问题的过程中形成了自己的工作步骤。
（ 1） 提出和形成问题。 即弄清问题的目标，可能的约束，
问题的可控变量以及有关参数，搜集有关资料 ;
（ 2） 建立模型。 即把问题中可控变量，参数和目标与约束之间的关系用一定的模型表示出来 ;
（ 3） 求解。用各种手段（主要是数学方法，也可用其他方法）将模型求解。解可以是最优解、次优解、满意解。复杂模型的求解需用计算机，解的精度要可由求决策者提出；
8
绪论 历史，性质，应用
运筹学的工作步骤
（ 4） 解的检验。首先检查求解步骤和程序有无错误，然后检查解是否反映现实问题；
（ 5） 解的控制。通过控制解的变化过程决定是否要作一定的改变；
（ 6） 解的实施。是指将解用到实际中必须考虑到实施的问题，如向实际部门讲清解的用法，在实施中可能产生的问题和修改。
9
绪论 历史，性质，应用
运筹学的模型
运筹学在解决问题时，按研究对象不同可构造各种不同的模型。模型是研究者对客观现实经过思维抽象后用文字、图表、
符号、关系以及实体模样描述所认识到的客观对象。模型的有关参数和关系式是较容易改变的，这样是有助于问题的分析和研究。利用模型可以进行一定预测、灵敏度分析等。
模型的三种基本形式：
（ 1）形象模型，（ 2）模拟模型，（ 3）符号或数学模型。
构造模型是一种创造性劳动，成功的模型往往是科学和艺术的结晶，构造模型的方法和思路通常有以下几种：
10
绪论 历史，性质，应用
直接分析法 按研究者对问题内在机理的认识直接构造出模型。运筹学中已有不少现存的模型，如线性规划模型、投入产出模型、排队模型、存储模型、决策和对策模型等等。这些模型都有很好的求解方法及求解软件，但用这些现成的模型研究问题时，应注意不能生搬硬套。
类比法 有些问题可以用不同方法构造出模型；而这些模型的结构性质是类同的，这就可以互相类比。如物理学中的机械系统、气体动力学系统、水力学系统、热力学系统及电路系统之间就有不少彼此类同的现象。甚至有些经济、社会系统也可以用物理系统来类比。在分析有些经济、社会问题时，
不同国家之间也可以找出某些类比的现象。
11
绪论 历史，性质，应用
数据分析法 对有些问题的机理尚未了解清楚，若能搜集到与此问题密切有关的大量数据，或通过某些试验获得大量数据，这就可以用统计分析法建摸。
试验分析法 有些问题的机理不清，又不能作大量试验来获得数据，这时只能通过做局部试验的数据加上分析来构造模型。
想定（构想）法 当有些问题的机理不清，又缺少数据，又不能作试验来获得数据时，例如有些社会、经济、军事问题，
人们只能在已有的知识、经验和某些研究的基础上，对于将来可能发生的情况给出逻辑上合理的设想和描述。然后用已有的方法构造模型，并不断修正完善，直至比较满意为止。
12
绪论 历史，性质，应用
运筹学的主要应用 二次大战后运筹学的应用迅速转向了民用，下面对某些重要领域给于简述。
1、市场销售 ------广告预算和媒介选择、竞争性定价、新品开发、销售计划的制订。 （美）杜邦公司在五十年代起就非常重视将运筹学用于如何做好广告工作、产品定价、新品引入。
2、生产计划 ------从总体确定生产、存储和劳动力的配合等计划适应波动的需求计划。 巴基斯坦一重型制造厂用线性规划安排生产计划，节省 10%的生产费用。
3、运输问题 ------涉及空运、水运、公路、铁路运输、管道运输等。公路网的设计和分析，市内公共汽车路线的选择和行车时刻表的安排，出租车的调度等。
13
绪论 历史，性质，应用
4、人事管理 ------需求估计，教育和培训，人员分配（各种指派问题），合理利用，人才评价等。
5、设备维修，更新和可靠性等。
6、计算机和信息系统 ------内存分配研究，网络设计分析等。
7、城市管理 ------紧急服务系统的设计和运用，区域布局规划，管道网络设计等。 （美）曾用排队论确定纽约市紧急电话站的值班人数，（加）设计城市警车配置和负责范围、指挥接警后的行走路线等。
8、对策研究 ------价格竞争，中央与地方政府投资分配博弈，
工会与雇主间的博弈。
14
第一讲线性规划 Linear Programming( LP )
目标规划 Goal Programming( GP )
整数规划 Integer Programming( IP )
15
第一章线性规划及单纯形法线性规划 Linear Programming（ LP）
16
引 言
解决有限资源在有竞争的使用方向中如何进行最佳分配。
线性规划是运筹学的一个重要分支，也是运筹学中应用最广泛的方法之一。自 1947年旦茨基（ G,B,Dantzig）提出了一般线性规划问题求解的方法 —— 单纯形法（ simplex
method）之后，线性规划已被广泛应用于解决经济管理和工业生产中遇到的实际问题。调查表明，在世界 500家最大的企业中，有 85%的企业都曾使用过线性规划解决经营管理中遇到的复杂问题。线性规划的使用为应用者节约了数以亿万计的资金。
线性规划 Linear Programming（ LP）
17
本讲中我们将讨论什么是线性规划问题，线性规划问题的数学表示，基本理论、概念和求解方法。
线性规划问题是什么样的一类问题呢？
请看案例 ------
线性规划 Linear Programming（ LP）
18
线性规划 Linear Programming（ LP）
曾几何时长江水，
哺育华夏代代人，
谁知后代疏珍惜，
清清江水黑如泥。
案 例 河流污染治理规划问题
19
线性规划 Linear Programming（ LP）
曾几何时长江水，
哺育华夏代代人，
谁知后代疏珍惜，
清清江水黑如泥。
工厂 2
工厂 3
工厂 1 工厂 4
工厂 5
工厂 6
工厂 9
工厂 8
工厂 7
案 例 河流污染治理规划问题
20
线性规划 Linear Programming（ LP）
曾几何时长江水，
哺育华夏代代人，
谁知后代疏珍惜，
清清江水黑如泥。
今日认识未为晚，
吾辈齐心治环境，
线性规划大有用，
定让江水绿如蓝。
工厂 2
工厂 3
工厂 1 工厂 4
工厂 5
工厂 6
工厂 9
工厂 8
工厂 7
案 例 河流污染治理规划问题
21
线性规划 Linear Programming（ LP）
今日认识未为晚，
吾辈齐心治环境，
线性规划大有用，
定让江水绿如蓝。
曾几何时长江水，
哺育华夏代代人，
谁知后代疏珍惜，
清清江水黑如泥。
工厂 2
工厂 3
工厂 1 工厂 4
工厂 5
工厂 6
工厂 9
工厂 8
工厂 7
案 例 河流污染治理规划问题
22
线性规划 Linear Programming（ LP）
案 例 河流污染治理规划问题
背景资料,
长江流域某区域内有 9化工厂，各厂每月产生的工业污水量如表 -1，流经各化工厂的河流流量如表 -2，各化工厂治理工业污水的成本如表 -3。上游厂排放的污水流到相邻下游厂以前，有 20%可自然净化。 根据环保标准河流中此种工业污水的含量不应超过 0.2%。从该区域整体考虑，各化工厂应该分别处理多少工业污水才能既满足环保要求，又使 9化工厂治理工业污水的总费用最少。
23
背景资料,
线性规划 Linear Programming（ LP）
化工厂 1 1.2 化工厂 4 2 化工厂 7 2
化工厂 2 1 化工厂 5 1 化工厂 8 0.8
化工厂 3 3 化工厂 6 1 化工厂 9 1.5
表 -1 污水排放量 单位：万 m3
表 -2 流经各化工厂的河流流量 单位：万 m3
表 -3 治理工业污水的成本 单位：百万元 /万 m3
化工厂 1 500 化工厂 4 1200 化工厂 7 1200
化工厂 2 300 化工厂 5 600 化工厂 8 200
化工厂 3 1800 化工厂 6 400 化工厂 9 700
化工厂 1 3 化工厂 4 4 化工厂 7 1
化工厂 2 5 化工厂 5 5 化工厂 8 2
化工厂 3 2 化工厂 6 6 化工厂 9 3
24
线性规划 Linear Programming（ LP）
1
9
4
5
8
2
6
3
7
案 例 河流污染治理规划问题
问题分析：
区域污染治理的决策 ——各个化工厂应处理的工业污水量
（或应排放的工业污水量）。
区域污染治理的约束 ——即满足环保要求排放工业污水（区域内河流中任何点检测都应符合环保标准）。
区域污染治理的目标 ——总治理成本最少。
25
线性规划 Linear Programming（ LP）
1
9
4
5
8
2
6
3
7
案 例 河流污染治理规划问题
模型描述：
设第 i个化工厂应处理的工业污水量为 Xi万 m3，则根据问题描述的情况以化工厂 1,2,…,9 加以分析则可得如下近似关系式
对化工厂 2应有 ---
（ 1-X2） / 300 ≦ 0.2%
对化工厂 8应有 ---
（ 2-X8） /200 ≦ 0.2%
对化工厂 1应有 ---
｛（ 3-X1） + 0.8?（ 1-X2） +（ 2-X8）? ｝ /500 ≦ 0.2%
26
线性规划 Linear Programming（ LP）
1
9
4
5
8
2
6
3
7
案 例 河流污染治理规划问题
对 化工厂 9应有 ——
（ 1.5-X9） / 700 ≦ 0.2%
对 化工厂 7应有 ——
（ 2-X7） + 0.8（ 1.5-X9）? / 1200 ≦ 0.2%
……
此外显然还应有
Xi ≧0 （ i=1,2,3 … 8,9）
综上所述决策者所需考虑的区域内各个化工厂应处理的工业污水量 Xi应满足上述所有不等式方程。我们将这些不等式方程构成的方程组称为 污水治理的约束条件。
27
线性规划 Linear Programming（ LP）
1
9
4
5
8
2
6
3
7
案 例 河流污染治理规划问题另一方面污水治理的总成本可表示为 Z
Z=3X1+5X2+2X3+4X4+5X5+6X6+1X7+2X8+3X9
而决策者的目标是确定 满足 约束条件的 Xi使得 Z取得最小值。
将上述分析归纳后即可得如下数学符合模型：
28
线性规划 Linear Programming（ LP）
1
9
4
5
8
2
6
3
7
案 例 河流污染治理规划问题数学模型（整理之后）
Min Z= 3X1 +5X2 +2X3 +4X4 +5X5 +6X6 +1X7 +2X8 +3X9
X2 ≧ 0.4
X8 ≧ 1.6
X1 +0.8X2 +0.8X8 ≧ 4.4
X9 ≧ 0.1
X7 +0.8 X9 ≧ 0.8
X4 +0.8X7 +0.64X9 ≧ 2.16
X6 ≧ 0.2
X5 +0.8X6 ≧ 0.6
X3 +0.8X4 +0.8X5 +0.64X6 +0.64X7 +5.12X9 ≧ 9.4
Xi ≧ 0 （ i=1,2,3,4,5,6,7,8,9）
s.t.
29
线性规划 Linear Programming（ LP）
基本概念线性规划模型
—— Linear Programming Model
或 Linear Optimization Model
用线性规划方法解决实际问题的第一步是建立能够完整描述和反映实际问题的线性规划模型。
30
线性规划 Linear Programming（ LP）
基本概念通常建立 LP模型有以下几个步骤：
1,确定决策变量,决策变量是模型要确定的未知变量，也是模型最重要的参数，是决策者解决实际问题的控制变量。
2,确定目标函数,目标函数决定线性规划问题的优化方向，是模型的重要组成部分。实际问题的目标可表示为决策变量的一个线性函数，并根据实际问题的优化方向求其最大化（ max）或最小化（ min）。
3,确定约束方程,一个正确的线性规划模型应能通过约束方程来描述和反映一系列客观条件或环境的限制，这些限制通过一系列线性等式或不等式方程组来描述。
4,变量取值限制,一般情况下，决策变量取正值（非负值）。因此，模型中应有变量的非负约束即 Xj≥0，但也存在例外。
31
线性规划 Linear Programming（ LP）
基本概念线性规划的一般形式,
max（或 min） z = c1x1 + c2x2 + … + cnxn
a11x1 + a12x2 +… + a1nxn （ ≤ = ≥ ） b1
a21x1 + a22x2 +… + a2nxn （ ≤ = ≥ ） b2
s.t,… … … … … …
am1x1 + am2x2 +… + amnxn （ ≤ = ≥ ） bm
xj ≥ 0 （ j=1,2 … n）
32
线性规划 Linear Programming（ LP）
基本概念线性规划问题的标准形式
1、目标函数极大化 ——,max,
2、等式约束条件 ——,=,
3、变量非负 ——,xj ≥ 0,
max z = c1x1 + c2x2 + … + cnxn
a11x1 + a12x2 +… + a1nxn = b1
a21x1 + a22x2 +… + a2nxn = b2
s.t,… … … … …
am1x1 + am2x2 +… + amnxn = bm
xj ≥ 0 （ j=1,2 … n）
33
线性规划 Linear Programming（ LP）
基本概念化标准形式的一般步骤
1、目标函数极小化?,极大化,
2、约束条件的右端项 bi≤0?,bi≥0,
3、约束条件为不等式 ≤ 或 ≥?,=”
4、取值无约束（自由）变量?,非负变量,
5、取值非正变量?,非负变量,
34
线性规划 Linear Programming（ LP）
基本概念线性规划问题的求解解：（图解）
如何求解一般的线性规划呢？
下面我们分析一下简单的情况 —— 只有两个决策变量的线性规划问题，这时可以通过图解的方法来求解。图解法具有简单、直观、便于初学者窥探线性规划基本原理和几何意义等优点。
35
线性规划 Linear Programming（ LP）
基本概念例 1（ page 11）
max z = 2x1 + x2
5x2 ≤ 15
s.t,6x1 + 2x2 ≤ 24
x1 + x2 ≤ 5
x1,x2 ≥ 0
36
线性规划 Linear Programming（ LP）
基本概念 max z = 2x1 + x2
5x2 ≤ 15
s.t,6x1 + 2x2 ≤ 24
x1 + x2 ≤ 5
x1,x2 ≥ 0
37
线性规划 Linear Programming（ LP）
基本概念例
max Z = 2X1 + X2
X1 + 1.9X2 ≥ 3.8
X1 - 1.9X2 ≤ 3.8
s.t,X1 + 1.9X2 ≤10.2
X1 - 1.9X2 ≥ -3.8
X1,X2 ≥ 0
38
线性规划 Linear Programming（ LP）
基本概念
max Z = 2X1 + X2
x1
x2
o
X1 - 1.9X2 = 3.8(≤)
X1 + 1.9X2 = 3.8(≥)
X1 - 1.9X2 = -3.8 (≥)
X1 + 1.9X2 = 10.2(≤)
4 = 2X1 + X2 20 = 2X1 + X2
17.2 = 2X1 + X211 = 2X
1 + X2
Lo,0 = 2X1 + X2
（ 7.6,2）D
max Z
min Z
此点是唯一最优解，
且最优目标函数值
max Z=17.2
可行域
39
线性规划 Linear Programming（ LP）
基本概念
max Z = 3X1+5.7X2
x1
x2
o
X1 - 1.9X2 = 3.8 (≤)
X1 + 1.9X2 = 3.8(≥)
X1 - 1.9X2 = -3.8(≥)
X1 + 1.9X2 = 10.2 (≤)
（ 7.6,2）D
L0,0=3X1+5.7X2
max Z
min Z
（ 3.8,4）
34.2 = 3X1+5.7X2
绿色线段上的所有点都是最优解这种情形为有无穷多最优解，但是最优目标函数值
max Z=34.2是唯一的。
可行域
40
线性规划 Linear Programming（ LP）
基本概念
min Z = 5X1+4X2
x1
x2
o
X1 - 1.9X2 = 3.8 (≤)
X1 + 1.9X2 = 3.8(≥)
X1 - 1.9X2 = -3.8(≥)
X1 + 1.9X2 = 10.2 (≤)
D
L0,0=5X1+4X2
max Z
min Z
8=5X1+4X2 43=5X1+4X2
（ 0,2） 可行域此点是唯一最优解
41
线性规划 Linear Programming（ LP）
基本概念图解法的启示
1,线性规划问题解的可能情况
a.唯一最优解
b.无穷多最优解
c.无解（没有有界最优解，无可行解）
2,若线性规划问题的可行域非空，则可行域是一个凸集；
3,若线性规划问题的最优解存在，则一定可以在可行域的凸集的某个顶点上达到。
42
线性规划 Linear Programming（ LP）
单纯形法单纯形方法是 G.B.Danzig于 1947年首先发明的。近 50
年来，一直是求解线性规划的最有效的方法之一，被广泛应用于各种线性规划问题的求解。本节讨论单纯形法的基本概念、
原理及算法。
43
线性规划 Linear Programming（ LP）
单纯形法给定线性规划问题（标准形式）
max z = c1x1 + c2x2 + … + cnxn
a11x1 + a12x2 +… + a1nxn = b1
a21x1 + a22x2 +… + a2nxn = b2
s.t,… … … … …
am1x1 + am2x2 +… + amnxn = bm
xj ≥ 0 （ j=1,2 … n）
44
线性规划 Linear Programming（ LP）
单纯形法一、线性规划问题的解的概念可行解最优解基基解（基本解）
基可行解可行基
45
线性规划 Linear Programming（ LP）
单纯形法二、凸集及其顶点凸集顶点（极点）
凸集 凹集
46
线性规划 Linear Programming（ LP）
1
2
3
4
5
6
78
47
线性规划 Linear Programming（ LP）
单纯形法三、线性规划基本定理基本定理 1 线性规划所有可行解组成的集合 S= { X | AX = b,X ≥0 }是 凸集。
基本定理 2 X是线性规划问题的 基本可行解的充要条件 为 是 X 是凸集
S={ X | AX = b,X ≥0 }的极点。
基本定理 3 给定线性规划问题,A是秩为 m 的 m? n 矩阵，
（ i） 若线性规划问题存在 可行解，则必 存在 基本可行解
（ ii） 若线性规划问题存在有界最优解,则必 存在有界最优 基本可行解。
48
线性规划 Linear Programming（ LP）
单纯形法单纯形法迭代原理及其思路单纯形法的初步讨论例 1.8 求解 LP问题
Max Z = 50X1+30X2
s.t,4X1+3X2 ≤120
2X1+ X2 ≤ 50
X1,X2 ≥0
Max Z = 50X1+30X2
s.t,4X1+3X2 +X3 = 120
2X1+ X2 + X4 = 50
X1,X2,X3,X4 ≥0
化为 标准型
（ 1.18）
49
线性规划 Linear Programming（ LP）
单纯形法此线性规划问题 转化为了一个含有四个变量的 标准形 线性规划问题,X3,X4为松弛变量。为求解上面的 LP问题，我们要考虑满足约束条件 s.t.并使 Z 取得 Max的 X1,X2,X3，
X4的值，由此分析如下 ---
50
线性规划 Linear Programming（ LP）
单纯形法确定初始基可行解：
通过观察可以发现，松弛变量 X3和 X4对应的等式 约束条件中的系数矩阵为单位矩阵可以作为初始 可行基 矩阵。因此取,X3,X4为基变量； X1,X2为非基变量。则（ 1.18）可变为
Max Z =50X1+30X2
s.t,X3 = 120 - 4X1 - 3X2
X4= 50 - 2X1 - X2 （ 1.19）
X1,X2,X3,X4≥0
51
线性规划 Linear Programming（ LP）
单纯形法典式
（ 1.19）或 （ 1.18） 称为关于基的 典式 ——
1,等式 约束条件中显含 基可行解
2、目标函数中不 含 基 变量
Max Z = 50X1+30X2
s.t,4X1+3X2 +X3 = 120
2X1+ X2 + X4 = 50 (1.18)
X1,X2,X3,X4 ≥0
Max Z =50X1+30X2
s.t,X3 = 120 - 4X1 - 3X2
X4= 50 - 2X1 - X2 （ 1.19）
X1,X2,X3,X4≥0
52
线性规划 Linear Programming（ LP）
单纯形法在典式 （ 1.19） 中令,X1=X2 =0，
我们得到一个 基本可行解
X1=（ X1,X2,X3,X4 ） T=（ 0,0,120,50） T,
其对应的目标函数值 Z1 = 50X1 + 30X2 = 0
53
线性规划 Linear Programming（ LP）
单纯形法最优性检验：
基本可行解 X1是最优解吗？显然不是。应寻找更好的解。
从问题的数学角度分析，在典式 （ 1.19） 的目标函数中,非基变量 X1,X2前的系数都为正，表明 目标函数值有增加的可能。
只要将目标函数中 系数为正的某 非基变量 与某一基变量地位对换。
54
线性规划 Linear Programming（ LP）
单纯形法换基迭代：
进行 换基就是要从非基变量中选一个变量 入基,再从基变量中选一个变量 出基 。并且换基后仍需满足：
1,新的解仍是基本 可行解；
2,目标函数值将得到改善。
55
线性规划 Linear Programming（ LP）
单纯形法选择入基变量,由于在目标函数 Z1=50X1+30X2 中 X1,X2的系数都为正，哪一个入基都可使目标函数值得到改善。对于求目标函数极大化的问题，我们希望目标值增加得越快越好，因此系数最大的 X1入基。
选择出基变量,X1入基后，其值从零增加并由于 约束条件的原因会引起其他变量的变化。由 典式 （ 1.19） 以及变量必须取正值的条件，我们可以得到下列不等式关系：
X3 = 120 - 4X1- 3X2 ≥0
X4= 50 - 2X1- X2 ≥0
56
线性规划 Linear Programming（ LP）
单纯形法因为迭代后 X2仍为 非基变量 （ 仍会令其取值为零 ）,则上式可简化为：
120 - 4X1 ≥0 由此可以看出，虽然我们希望 X1入基后取正值，且
50 - 2X1 ≥0 取值越大目标值增加越大，但是,X1又得受到 约束。
显然，只有 取 X1 =min（ 120/4,50/2） =25时，才能使上述不等式成立并且恰使 基变量 X4变为零，这正好满足非基变量必须取 值 零的条件，
所以可 令 X4 出基,方程变为：
4X1+ X3 =120 - 3X2
2X1 = 50 - X2 - X4
化简后得,新的 典式 方程 X3 = 20 - X2 + 2X4
X1 = 25 -0.5X2 -0.5X4
57
线性规划 Linear Programming（ LP）
单纯形法代入目标函数可得,Z2 =1250+5X2-25X4
令 非基变量 X2 =X4 = 0，即可得一个新的 基本可行解
X2 =（ 25,0,20,0） T,其对应的目标函数值 Z2 =1250，并完成了第一次 迭代。
由于 目标函数 Z2 =1250+5X2-25X4中 X2的系数仍为正，该解 X2仍不是最优解。重复上述 迭代过程得到,X2入基,X3出基，则新的 典式 方程变为：
X1 = 15 +0.5X3 - 1.5X4
X2 =20 - X3 + 2X4
Z3 =1350 -5X3 - 15X4
58
线性规划 Linear Programming（ LP）
单纯形法第三个 基本可行解 X3 =（ 15,20,0,0） T，其对应的目标函数值 Z3=
1350 。 此时松弛变量 都是 非基变量 （ 取值为零 ）,这表明资源已用尽；并且目标函数值 Z3=1350 -5X3 - 15X4中 非基变量 X3,X4的系数全为负值，说明目标函数已无法进一步改善，因此该解已是最优解。
59
线性规划 Linear Programming（ LP）
单纯形法单纯形法小结：
单纯形法是这样一种 迭代算法 —— 如下图 …
当 Zk中 非基变量 的系数的系数全为负值时，这时的 基本可行解 Xk即是线性规划问题的最优解,迭代结束。
X1
Z1
保持 单调增保持 可行 性 保持 可行 性 保持 可行 性 保持 可行 性保持 单调增 保持 单调增 保持 单调增
X2 X3,.,Xk
Z2 Z3,.,Zk
当 Zk 中 非基变量 的系数的系数全为负值时，这时的 基本可行解 Xk 即是线性规划问题的最优解,迭代结束。
60
线性规划 Linear Programming（ LP）
单纯形法单纯形表对于给定的线性规划问题：
max Z = c1x1 + c2x2 + … + cnxn
a11x1 + a12x2 + … + a1nxn≤ b1
a21x1 + a22x2 + … + a2nxn≤ b2
s.t,… … …
am1x1 + am2x2 + … + amnxn≤ bm
xj ≥ 0 （ j=1,2 … n）
对此问题添加 m个松弛变量后，可得下面线性规划问题并且是 典式的形式。
61
线性规划 Linear Programming（ LP）
单纯形法线性规划的典式
max Z = c1x1 + c2x2 + … + cnxn
a11x1 + a12x2 +… + a1nxn + xn+1 = b1
a21x1 + a22x2 +… + a2nxn + xn+2 = b2
s.t,…
am1x1 + am2x2 +… + amnxn + xn+m = bm
xj ≥ 0 （ j=1,2 … n,n+1,n+2,… n+m）
62
线性规划 Linear Programming（ LP）
单纯形法单纯形表：
将上面 典式中各变量及系数填写在一张表格中就形成下面的 单纯形表
cj? c1 c2 … c n cn+1 cn+2 … c n+m
C
B 基 解 x1 x2 … x n xn+1 xn+2 … x n+1
0
0
0
0
xn+1
xn+1
…
xn+1
b1
b2
…
bm
a11 a12 … a 1n 1
a21 a22 … a 2n 1
… … … … …
am1 am2 … a mn 1
1
2
…
m
j = cj – zj? c1 c2 … c n 0 0 … 0
j = cj – zj1? 2 …? n?n+1?n+2 …?n+m
63
线性规划 Linear Programming（ LP）
单纯形法单纯形表：
上面 的 单纯形表还可以表示成矩阵的形式基 解 X XS?
XS b A I
j? C 0
基 解 XB XN XS?
XS b B N I
j? CB CN 0
64
线性规划 Linear Programming（ LP）
单纯形法由单纯形表进行 迭代步骤：
1,选择 Xj 入基：当?j 行中 cj= max ci∣ ci? 0
2,选择 Xi 出基：当?i= min bi/aij∣ aij? 0
3,换基 迭代：当确定了 入基变量 Xj,出基变量 Xi 后，以 aij 作为主元对单纯形表进行初等行变换（取 主 运算），即将 aij 所在列除采用初等行变换 将 aii 变换为 1外的其余元素都 变换为 0。注意这种 变换只能采用初等行变换 !
65
线性规划 Linear Programming（ LP）
单纯形法最优解检验：
1,当迭代进行至某一步时,? j 行中所有 检验数均小于等于零，
则 迭代结束。 表中当前 所指 基本可行解即为 最优解。
2,当迭代进行至某一步时,? j 行中所有 检验数均小于等于零，
且此时至少有一个 非基变量所对应的 检验数 rk等于零，则原线性规划问题有无穷多个 最优解。
3,当迭代进行至某一步时,? j 行中至少有一个 检验数 rk 大于零，
且该检验数对应的 列中 a1k,a2k,… amk,均 小 于等于 零，则原线性规划问题 最优解无界（ max Z→ +∞）。
66
线性规划 Linear Programming（ LP）
单纯形法单纯形方法的矩阵描述：
设线性规划问题 max Z = CX max Z = CX + 0XS
s.t,AX ≤ b s.t,AX + I XS = b （ I 式 ）
X ≥ 0 X,XS ≥ 0
其中 b ≥ 0,I 是 m?m 单位 矩阵。
对上面 （ I 式 ） 经过迭代,并设最终的最优基矩阵为 B（不妨设 B为 A 的首 m 列，则将（ I 式 ）改写后有
67
线性规划 Linear Programming（ LP）
单纯形法
max Z = CBXB + CNXN + 0XS
s.t,BXB + NXN + I XS = b
XB,XN,XS ≥ 0
max Z = CB B -1+（ CN- CB B -1） XN - CB B -1XS
s.t,XB + B -1NXN + B -1XS = B -1b
XB,XN,XS ≥ 0
B 式中 最优 目标函数值 Z*= CB B -1,检验数 CN - CB B -1 ≤ 0,- CB B -1 ≤ 0
单纯形方法 迭代（ I 式） （ B 式 ）
68
线性规划 Linear Programming（ LP）
单纯形法单纯形方法的矩阵描述：
基 解 XB XN XS?
XS b B N I
j? CB CN 0
基 解 XB XN XS?
XB B -1b I B -1N B -1
j? 0 CN - CB B –1N - CB B -1
对应 I 式 的 单纯形表 ——I 表对应 B式 的 单纯形表 —— B 表迭代
69
线性规划 Linear Programming（ LP）
单纯形表计算步骤举例给定线性规划问题 max z = 50X
1 + 30X2
s.t,4X1+3X2 ≤ 120
2X1+ X2 ≤ 50
X1,X2 ≥ 0
max z = 50X1 + 30X2
s.t,4X1+ 3X2 + X3 = 120
2X1+ X2 + X4 = 50
X1,X2,X3,X4 ≥ 0
70
线性规划 Linear Programming（ LP）
单纯形表计算步骤举例给定线性规划问题
max z = 50X1 + 30X2
s.t,4X1+ 3X2 + X3 = 120
2X1+ X2 + X4 = 50
X1,X2,X3,X4 ≥ 0
基 XB 解 B-1b X1 X2 X3 X4?
X3 120 4 3 1 0
X4 50 2 1 0 1
检验数?j 50 30 0 0
120/4
50/21 1 1/2 1/225
020 1 - 2
0 5 - 25
20/1
25× 2
2
15 0 - 1/2 3
0 - 5 15
71
线性规划 Linear Programming（ LP）
单纯形法的进一步讨论人工变量法：
当一般线性规划问题标准化之后，我们或可得到一个显然的 基本可行解（如 松弛变量作为 基变量的一个 初始 基本可行解），这样我们就可以马上进入 单纯形表的运算步骤。然而，并非所有 问题标准化之后我们都可得到一个显然的 初始 基本可行解,这时就需要我们首先确定出一个 基本可行解作为 初始 基本可行解。通常采用的是人工变量法来确定这样的 初始 基本可行解。这种情况下一般有两种方法：
1、大 M法（罚因子法）
2、两阶段法
72
线性规划 Linear Programming（ LP）
单纯形法的进一步讨论
1、大 M 法（罚因子法）
max z = - 3X1 + X3
x1 + x2 + x3 ≤ 4
- 2x1 + x2 – x3 ≥ 1
3x2 + x3 = 9
x1,x2,x3 ≥ 0
LPM max z = - 3x1 + x3 + 0x4 + 0x5 – Mx6 – Mx7
x1 + x2 + x3 + x4 = 4
- 2x1 + x2 – x3 - x5 + x6 = 1
3x2 + x3 +x7 = 9
x1,x2,x3,x4,x5,x6,x7 ≥ 0
73
线性规划 Linear Programming（ LP）
1、大 M 法 LPM max z = - 3x1 + x3 + 0x4 + 0x5 – Mx6 – Mx7
x1 + x2 + x3 + x4 = 4
- 2x1 + x2 – x3 - x5 + x6 = 1
3x2 + x3 +x7 = 9
x1,x2,x3,x4,x5,x6,x7 ≥ 0
基 XB 解 B-1b X1 X2 X3 X4 X5 X6 X7?
X4 4 1 1 1 1 0 0 0
X6 1 -2 1 -1 0 -1 1 0
X7 9 0 3 1 0 0 0 1
检验数?j -3 0 1 0 0 -M -M
74
线性规划 Linear Programming（ LP）
1、大 M 法基 XB 解 B-1b X1 X2 X3 X4 X5 X6 X7?
X4 4 1 1 1 1 0 0 0
X6 1 -2 1 -1 0 -1 1 0
X7 9 0 3 1 0 0 0 1
检验数?j -3-2M M 1-M 0 -M 0 -M
基 XB 解 B-1b X1 X2 X3 X4 X5 X6 X7?
X4 4 1 1 1 1 0 0 0
X6 1 -2 1 -1 0 -1 1 0
X7 9 0 3 1 0 0 0 1
检验数?j -3-2M 4M 1 0 -M 0 0
75
线性规划 Linear Programming（ LP）
1、大 M 法基 XB 解 B-1b X1 X2 X3 X4 X5 X6 X7?
X4 4 1 1 1 1 0 0 0 4
X6 1 -2 1 -1 0 -1 1 0 1
X7 9 0 3 1 0 0 0 1 3
检验数?j -3-2M 4M 1 0 -M 0 0
基 XB 解 B-1b X1 X2 X3 X4 X5 X6 X7?
X4 3 3 0 2 1 1 -1 0
X2 1 -2 1 -1 0 -1 1 0
X7 6 6 0 4 0 3 -3 1
检验数?j -3+6M 0 1+4M 0 3M -4M 0
76
线性规划 Linear Programming（ LP）
1、大 M 法基 XB 解 B-1b X1 X2 X3 X4 X5 X6 X7?
X4 3 3 0 2 1 1 -1 0 1
X2 1 -2 1 -1 0 -1 1 0 ---
X7 6 6 0 4 0 3 -3 1 1
检验数?j -3+6M 0 1+4M 0 3M -4M 0
基 XB 解 B-1b X1 X2 X3 X4 X5 X6 X7?
X4 0 0 0 0 1 -1/2 1/2 -1/2
X2 3 0 1 1/3 0 0 0 1/3
X1 1 1 0 2/3 0 1/2 -1/2 1/6
检验数?j 0 0 3 0 1.5 -1.5-M 0.5-M
77
线性规划 Linear Programming（ LP）
1、大 M 法基 XB 解 B-1b X1 X2 X3 X4 X5 X6 X7?
X4 0 0 0 0 1 -1/2 1/2 -1/2 ---
X2 3 0 1 1/3 0 0 0 1/3 9
X1 1 1 0 2/3 0 1/2 -1/2 1/6 3/2
检验数?j 0 0 3 0 1.5 -1.5-M 0.5-M
基 XB 解 B-1b X1 X2 X3 X4 X5 X6 X7?
X4 0 0 0 0 1 -1/2 1/2 -1/2
X2 5/2 -1/2 1 0 0 -1/4 1/4 1/4
X3 3/2 3/2 0 1 0 3/4 -3/4 1/4
检验数?j -9/2 0 0 0 -3/4 3/4-M -1/4-M
78
线性规划 Linear Programming（ LP）
单纯形法的进一步讨论采用大 M 法求解线性规划问题时可能出现的几种情况：
1、当采用单纯形法求解 LPM 得到最优解时，基变量 不含 任何人工变量，则所得到的最优解就是原问题的最优解；
2、当采用单纯形法求解 LPM 得到最优解时，基变量至少 含有 一个人工变量且 非零,则原问题无可行解；
3、当采用单纯形法求解 LPM 得到最优解时，基变量至少 含有 一个人工变量且人工变量都 为零,则通过变换得到原问题最优解；
79
线性规划 Linear Programming（ LP）
单纯形法的进一步讨论
2、两阶段法
max z = - 3X1 + X3
x1 + x2 + x3 ≤ 4
- 2x1 + x2 – x3 ≥ 1
3x2 + x3 = 9
x1,x2,x3 ≥ 0
I阶段问题 max z = – x6 – x7
x1 + x2 + x3 + x4 = 4
- 2x1 + x2 – x3 - x5 + x6 = 1
3x2 + x3 +x7 = 9
x1,x2,x3,x4,x5,x6,x7 ≥ 0
80
线性规划 Linear Programming（ LP）
2、两阶段法 I 阶段问题 max z = – x6 – x7
x1 + x2 + x3 + x4 = 4
- 2x1 + x2 – x3 - x5 + x6 = 1
3x2 + x3 +x7 = 9
x1,x2,x3,x4,x5,x6,x7 ≥ 0
基 XB 解 B-1b X1 X2 X3 X4 X5 X6 X7?
X4 4 1 1 1 1 0 0 0
X6 1 -2 1 -1 0 -1 1 0
X7 9 0 3 1 0 0 0 1
检验数?j 0 0 0 0 0 -1 -1
81
线性规划 Linear Programming（ LP）
2、两阶段法 ——第 I 阶段基 XB 解 B-1b X1 X2 X3 X4 X5 X6 X7?
X4 4 1 1 1 1 0 0 0
X6 1 -2 1 -1 0 -1 1 0
X7 9 0 3 1 0 0 0 1
检验数?j 0 0 0 0 0 -1 -1
基 XB 解 B-1b X1 X2 X3 X4 X5 X6 X7?
X4 4 1 1 1 1 0 0 0
X6 1 -2 1 -1 0 -1 1 0
X7 9 0 3 1 0 0 0 1
检验数?j -2 4 0 0 -1 0 0
82
线性规划 Linear Programming（ LP）
2、两阶段法 ——第 I 阶段基 XB 解 B-1b X1 X2 X3 X4 X5 X6 X7?
X4 4 1 1 1 1 0 0 0 4
X6 1 -2 1 -1 0 -1 1 0 1
X7 9 0 3 1 0 0 0 1 3
检验数?j -2 4 0 0 -1 0 0
基 XB 解 B-1b X1 X2 X3 X4 X5 X6 X7?
X4 3 3 0 2 1 1 -1 0
X2 1 -2 1 -1 0 -1 1 0
X7 6 6 0 4 0 3 -3 1
检验数?j 6 0 4 0 3 -4 0
83
线性规划 Linear Programming（ LP）
2、两阶段法 ——第 I 阶段基 XB 解 B-1b X1 X2 X3 X4 X5 X6 X7?
X4 3 3 0 2 1 1 -1 0 1
X2 1 -2 1 -1 0 -1 1 0 ---
X7 6 6 0 4 0 3 -3 1 1
检验数?j 6 0 4 0 3 -4 0
基 XB 解 B-1b X1 X2 X3 X4 X5 X6 X7?
X4 0 0 0 0 1 -1/2 1/2 -1/2
X2 3 0 1 1/3 0 0 0 1/3
X1 1 1 0 2/3 0 1/2 -1/2 1/6
检验数?j 0 0 0 0 0 -1 -1
84
线性规划 Linear Programming（ LP）
2、两阶段法 ——第 II 阶段基 XB 解 B-1b X1 X2 X3 X4 X5 X6 X7?
X4 0 0 0 0 1 -1/2 1/2 -1/2
X2 3 0 1 1/3 0 0 0 1/3
X1 1 1 0 2/3 0 1/2 -1/2 1/6
检验数?j 0 0 0 0 0 -1 -1
基 XB 解 B-1b X1 X2 X3 X4 X5?
X4 0 0 0 0 1 -1/2
X2 3 0 1 1/3 0 0
X1 1 1 0 2/3 0 1/2
检验数?j 0 0 3 0 3/2
-3 1
85
线性规划 Linear Programming（ LP）
2、两阶段法 ——第 II 阶段基 XB 解 B-1b X1 X2 X3 X4 X5?
X4 0 0 0 0 1 -1/2 ---
X2 3 0 1 1/3 0 0 9
X1 1 1 0 2/3 0 1/2 3/2
检验数?j 0 0 3 0 3/2
基 XB 解 B-1b X1 X2 X3 X4 X5?
X4 0 0 0 0 1 -1/2
X2 5/2 -1/2 1 0 0 -1/4
X3 3/2 3/2 0 1 0 3/4
检验数?j -9/2 0 0 0 -3/4
86
线性规划 Linear Programming（ LP）
单纯形法中的几个问题
1,目标函数极小化时，解的最优判别：
j ≥ 0
2,退化：
一个或几个 基变量 等于零，一个简单易行的避免退化的方法是 1974
年由勃兰德（ Bland）提出的 Bkand 法则。
3,无可行解的判别：
在采用人工变量求解线性规划问题得到最优解时，如果基变量中仍含有 非零人工变量,则原问题无可行解。
87
线性规划 Linear Programming（ LP）
数据包络分析 DEA （ date envelopment analysis）
概念一种基于线性规划的用于评价同类型组织（或项目）工作绩效相对有效性 的特殊工具手段。这类组织例如学校、医院、银行的分支机构、超市的各个营业部等，各自具有相同的投入相同的产出。
衡量这类组织之间的绩效高低，通常采用投入产出比这个指标，当各自的投入产出均可折算成同一单位计量时，容易计算出各自的投入产出比并按其大小进行绩效排序。但当被衡量的同类型组织有多项投入和多项产出，且不能折算成统一单位时，就无法算出投入产出比的数值，因而，需采用一种全新的方法进行绩效比较。这种方法就是二十世纪七十年代末产生的数据包络分析 DEA。
88
线性规划 Linear Programming（ LP）
数据包络分析 DEA （ date envelopment analysis）
概念
1978年，著名运筹学家、美国德克萨斯大学教授 A.Charnes及
W.W.Cooperh和 E.Rhodes发表了一篇重要论文：,Measuring
the efficiency of decision making units‖（决策单元的有效性度量），刊登在权威的“欧洲运筹学杂志”上。正式提出了运筹学的一个新领域：数据包络分析。其模型简称 C2R 模型。
89
线性规划 Linear Programming（ LP）
数据包络分析 DEA （ date envelopment analysis）
相对有效性评价问题举例例 1：硕士点教育质量评价某系统工程研究所对我国金属热处理专业的 26个硕士点的教育质量，进行了有效性评价。
评价采用的指标体系为：
输入：导师人数；实验设备；图书资料；学生入学情况。
输出：科研成果；论文篇数；学生毕业时的情况。
使用 DEA进行评价，结果基本合理。
90
线性规划 Linear Programming（ LP）
数据包络分析 DEA （ date envelopment analysis）
相对有效性评价问题举例例 2：行风（行业作风）建设有效性评价本项目研究人员选定江苏省 S市交通客运系统作为对象，包括 7家交通客运汽车公司。
评价采用的指标基础依据为：
1、国际公交组织颁布的“十项基本考核指标”
2、国内颁布的公交运营服务的“八项考核指标”。
在此基础上，根据该系统实际情况，最终选定了输入指标 4项，输出指标 4项。分别是：
91
线性规划 Linear Programming（ LP）
数据包络分析 DEA （ date envelopment analysis）
相对有效性评价问题举例输入指标,1、年末职工总熟（单位：人）；
2、单位成本（单位：元 /千人公里）；
3、燃料单位消耗（单位：升 /千人公里）；
4、行车责任事故率（单位：次 /千人公里）。
输出指标,1、劳动生产率（单位：元 /人）；
2、行车准点率（ %）；
3、群众满意率（按问卷调查）（ %）
4、车辆服务合格率（包括：服务态度、服务措施、车辆设施等）（ %）
92
线性规划 Linear Programming（ LP）
数据包络分析 DEA （ date envelopment analysis）
相对有效性评价问题举例收集到所需数据后，使用 DEA方法综合评价，结果为：
1,3家公司为行风建设有效；
2,4家公司在行风建设上存在不同程度（以量化形式给出）的缺点与不足。
93
线性规划 Linear Programming（ LP）
数据包络分析 DEA （ date envelopment analysis）
相对有效性评价问题举例
4所小学 S1,S2,S3,S4，在校学生分别为 1200,100,1600，
1400人，按 800名标准学生的规模折算各个学校的教职工人数和建筑面积的投入，如下表：
学 校投 入 S1 S2 S3 S4
教职工人数建筑面积 /m2
25
1800
40
1500
35
1700
20
2500
94
线性规划 Linear Programming（ LP）
数据包络分析 DEA （ date envelopment analysis ）
相对有效性评价问题举例教职工人数建筑面积生产前沿线（面）
S4
S1 S3
S2
M
数据包络线
95
线性规划 Linear Programming（ LP）
数据包络分析 DEA （ date envelopment analysis）
相对有效性评价问题线性规划数学模型在 DEA中一般称被衡量绩效的组织为决策单元（ decision
making unit——DMU）。
设,n 个决策单元（ j = 1,2,…,n ）
每个决策单元有相同的 m 项投入（输入）（ i = 1,2,…,m ）
每个决策单元有相同的 s 项产出（输出） （ r = 1,2,…,s ）
Xij ——第 j 决策单元的第 i 项投入
yrj ——第 j 决策单元的第 r 项产出衡量第 j0 决策单元是否 DEA有效
96
线性规划 Linear Programming（ LP）
数据包络分析 DEA （ date envelopment analysis）
相对有效性评价问题线性规划数学模型决策单元 1 2 … n
投入项目
1
2
…
m
X11 X12 … X1n
X21 X22 … X2n
… … … …
Xm1 Xm2 … Xmn
1 2 … n 决策单元
y11 y12 … y1n
y21 y22 … y2n
… … … …
ys1 ys2 … ysn
1
2
…
s
产出项目
97
线性规划 Linear Programming（ LP）
数据包络分析 DEA （ date envelopment analysis）
相对有效性评价问题线性规划数学模型构建模型的思路：
衡量某一决策单元 j0 是否 DEA有效 ——是否处于由包络线组成的生产前沿面上，先构造一个由 n 个决策单元组成 （线性组合成）
的 假想决策单元 。如果该假想单元的各项产出均 不低于 j0 决策单元的各项产出，它的各项投入均 低于 j0 决策单元的各项的各项投入。
即有：
98
线性规划 Linear Programming（ LP）
数据包络分析 DEA （ date envelopment analysis）
相对有效性评价问题线性规划数学模型
∑?j yrj ≥ yrj0 （ r = 1,2,…,s）
∑?j xij ≤ E xij0 （ i = 1,2,…,m,E＜ 1）
∑?j = 1,?j ≥0 （ j = 1,2,…,n）
j=1
j=1
j=1
n
n
n
这说明 j0 决策单元不处于生产前沿面上。
99
线性规划 Linear Programming（ LP）
数据包络分析 DEA （ date envelopment analysis）
相对有效性评价问题线性规划数学模型基于上述事实，可以写出如下线性规划的数学模型：
min E
S.t.
∑?j yrj ≥ yrj0 （ r = 1,2,…,s）
∑?j xij ≤ E xij0 （ i = 1,2,…,m）
∑?j = 1,?j ≥0 （ j = 1,2,…,n）
j=1
j=1
j=1
n
n
n
100
线性规划 Linear Programming（ LP）
数据包络分析 DEA （ date envelopment analysis）
相对有效性评价问题线性规划数学模型结果分析：
1、当求解结果有 E ＜ 1 时，则 j0 决策单元 非 DEA有效；
2,否则，则 j0 决策单元 DEA有效。
101
线性规划 Linear Programming（ LP）
数据包络分析 DEA （ date envelopment analysis）
相对有效性评价问题线性规划数学模型例 8（ Page 39） 振华银行的 4 个分理处的投入产出如下表。求各个分理处的运行是否 DEA有效。 产出单位：处理笔数 /月分理处 投入 产出职员数 营业面积（ m2） 储蓄存取 贷款 中间业务分理处 1
分理处 2
分理处 3
分理处 4
15
20
21
20
140
130
120
135
1800
1000
800
900
200
350
450
420
1600
1000
1300
1500
102
线性规划 Linear Programming（ LP）
数据包络分析 DEA （ date envelopment analysis）
相对有效性评价问题线性规划数学模型解,若先确定 分理处 1的运行是否 DEA有效。建立线性规划模型 min E
1800?1 +1000?2 + 800?3 + 900?4 ≥1800
200?1 + 350?2 + 450?3 + 420?4 ≥ 200
1600?1 +1000?2 +1300?3 +1500?4 ≥1600
S.t,15?1 + 20?2 + 21?3 + 20?4 ≤ 15E
140?1 + 130?2 + 120?3 + 135?4 ≤140E
1 +?2 +?3 +?4 = 1
j ≥0 （ j = 1,2,3,4 ）
103
线性规划 Linear Programming（ LP）
数据包络分析 DEA （ date envelopment analysis）
相对有效性评价问题线性规划数学模型求解结果分析：
对 分理处 1,E =1，说明分理处 1的运行 DEA有效。
对 分理处 2,E =0.996，说明分理处 2的运行非 DEA有效。
对 分理处 3,E =1，说明分理处 3的运行 DEA有效。
对 分理处 4,E =1，说明分理处 4的运行 DEA有效。
104
线性规划 Linear Programming（ LP）
数据包络分析 DEA （ date envelopment analysis）
DEA应用中的“窗口”技术 ——空军基地的效率评价（美国）
美国空军军方曾对 7 个空军基地的效率进行了评价，使用的方法为 DEA。输入指标选定 3 项，输出指标选定 4 项（内容未报道）。
评价的时间范围为 1992 年 10 月 1 日至 1993 年 12 月 31 日。尽管具体内容及结果未予公布，但有一项技术 ——―窗口技术”却很有参考价值，介绍如下：
在对决策单元集进行 DEA 评价时，对单元的个数 n,输入指标个数 m,以及输出指标个数 s 应有一定的要求。经验表明它们大体上应满足或接近
n ≥ 2ms
105
线性规划 Linear Programming（ LP）
数据包络分析 DEA （ date envelopment analysis）
DEA应用中的“窗口”技术 ——空军基地的效率评价（美国）
在本例中，空军基地有 7 个，分别记为 A,B,C,D,E,
F,G 。即 n = 7；而输入指标有 3 项，即 m = 3；输出指标有 4
项，即 s = 4 。显然，决策单元数过少了。
实施此项评价的美国学者采取了“分割 ——连接 ——滑动”的处理办法。将评价的时间段变小，将 1992.10.1 ～ 1993.12.31，按季度分割为 5 个季度，将“每个基地 ——每个季度”作为决策单元，
这样就得到了 35 个决策单元。
但在每项评价时，只使用相邻的 3 个季度，即 n = 21,接近
2ms = 2× 3× 4 = 24,将它们构成一个“窗口”。评价结束后，将
“窗口”向下一季度递推，进行第二轮 DEA 评价。如此进行，共作三轮，获得了良好的结果。
106
线性规划 Linear Programming（ LP）
数据包络分析 DEA （ date envelopment analysis）
DEA应用中的“窗口”技术 ——空军基地的效率评价（美国）
季度 1 季度 2 季度 3 季度 4 季度 5
A
B
C
D
E
F
G
A1 A2 A3 A4 A5
B1 B2 B3 B4 B5
… … … … …
… … … … …
… … … … …
F1 F2 F3 F4 F5
G1 G2 G3 G4 G5
107
线性规划 Linear Programming（ LP）
数据包络分析 DEA （ date envelopment analysis）
DEA应用中的“窗口”技术 ——空军基地的效率评价（美国）
窗口技术有许多优点，主要为：
1) 适用于决策单元个数 n 较小的情况。
2) 可以获得各个决策单元关于效率的稳定性。以及变化趋势、季节行为等方面的有价值的辅助信息。
3) 提供了纵向评价（沿时间轴评价）的一种思路。
108
线性规划 Linear Programming（ LP）
线性规划其他应用例子我们应该牢记：,应用线性规划解决经济，管理领域的实际问题时，最重要的一步是建立全面、准确地反映实际问题的线性规划模型,,这是一项技巧性很强的创造性工作，既要求对所研究的问题有深入了解，又要求很好掌握线性规划模型的结构特点，并具有对实际问题进行数学描述的较强能力。因此，在研究建立一些较复杂问题的数学模型时，需要各个方面的专业人员的通力协作配合。
109
线性规划 Linear Programming（ LP）
线性规划其他应用例子一般情况下，一个经济、管理问题要满足下列条件，才能归结为线性规划的模型：
1,要求解的问题的目标能用某种效益指标度量大小，并能用线性函数描述目标的要求；
2,为了达到这个目标存在多种方案；
3,要达到的目标是在一定约束条件下实现的，这些条件可以用一组线性等式或不等式描述。
110
线性规划 Linear Programming（ LP）
线性规划其他应用例子例 一家连琐店公司正在计划明年的广告预算，该公司计划用 1000
万元在报纸、广播和电视上做广告。下表是他们做规划用的统计数据：
统计数据 广告媒体效果 报纸 电台 电视每个广告影响的总人数影响的已婚人数影响平均收入以上的人数最高广告数量限制（个）
最低广告数量限制（个）
每个广告的成本（万元）
50000
15000
20000
100
25
3
100000
20000
30000
150
30
1.5
150000
40000
50000
50
30
15
111
线性规划 Linear Programming（ LP）
线性规划其他应用例子该公司的目标是使广告影响的人数最多，并且满足下面的条件：
1) 至少要影响 500 万人口；
2) 至少要影响 100 万已结婚的人口；
3) 至少要影响 150 万收入在平均收入以上的人口；
4) 在每种媒介上所做的广告要在最高和最低限制数之间。
统计数据 广告媒体效果 报纸 电台 电视每个广告影响的总人数影响的已婚人数影响平均收入以上的人数最低广告数量限制（个）
最高广告数量限制（个）
每个广告的成本（万元）
50000
15000
20000
25
100
3
100000
20000
30000
30
150
1.5
150000
40000
50000
20
50
15
112
线性规划 Linear Programming（ LP）
线性规划其他应用例子例 发电厂有两台锅炉，每台锅炉投入运行时生产的蒸汽量一定要维持在最高产汽量和最低产汽量之间。每个锅炉的产汽量范围和生产成本（如表 1），锅炉生产的蒸汽可送到两台汽轮机组发电，每台汽轮机组的蒸汽消耗量也有最低和最高限制，且运行成本和每吨蒸汽的发电量亦不同（如表 2）。
请建立一个线性规划模型使发电厂在满足 8000度发电计划的前提下运行成本最低。
锅炉号最低产汽量
（吨）
最高产汽量
（吨）
运行成本（元 /
吨）
1
2
400
500
900
1000
8
6
汽轮机号最低用汽量
（吨）
最高用汽量
（吨）
每吨蒸汽生产电量
（度）
运行成本
（元 /
吨）
1
2
500
600
800
900
5
6
3
4
113
线性规划 Linear Programming（ LP）
线性规划其他应用例子例 制造某种机床，需要 A,B,C 三种轴件，其规格与数量如下表，各类轴件都用 5.5 米长的同一种圆钢下料。若计划生产 100 台机床，最少要用多少根圆钢？
轴类 规格：长度（米） 每台机床所需轴件数
A
B
C
3.1
2.1
1.2
1
2
4
114
线性规划 Linear Programming（ LP）
第一章结束谢谢！
