1线性规划及单纯形法

90 B3 60
30
O
3
6
9
12
职员数
【解】为进行分析，以职员数为横坐标、营 业面积为纵坐标，将四个储蓄所的投入绘图
营业面积m2 120 B2 B1 由虚线和折线形成 的数据包络线称为 生产前沿面。 即：不可能由这条 包络线以外的点对 应的职员数和营业 面积完成10，000笔 存取款业务， B4
90 B3 60
单位绩效衡量
• 衡量一个单位的绩效，通常用投入产出比 这个指标，当所有投入和产出指标均分别 可折算成同一单位时（如货币值），容易 根据投入产出比大小对要评定的决策单元 进行绩效排序，但大多数情况下做不到这 一点。 • 由A. Charnes等人提出的DEA方法为具有 多个投入和多个产出的同类型决策单元的 绩效评价提供了依据。
给每一产出项赋权值u1 y11 u2 y21 ... ... u s ys1
若用vi 表示第i项投入的权值， ur 表示第r项产出的权值， 则：第j决策单元的投入产出比 h j的表达式为： hj
u y
r 1 m r
s
rj
v x
i 1
( j 1,2,...,n)
6-2
评价决策单元DEA有效性C2R模型
设：有n个决策单元（ j 1,2,...,n） , 每个决策单元有相同的 m项投入（i 1,2,...,m）和相同的s项产出（r 1,2,...,s）， 用xij 表示第j个单元的第i项投入量，yij 表示第j个单元的第 r项产出量。其投入产出 情况表示如下： 决策单元 1 2 ... n 1 x11 2 x21 投入 ...... ... m xm1
[例12] 有4所医院，其投入产出情况如表所 示。试分析评价上述4所医院是否DEA有效。
医院 H1 H2 H3 H4 投入 职员数 285 162 275 230 床位数 100 64 90 85 面积m2 8000 6500 8500 7500 产出 年门诊病人次 35500 28000 33000 30000 住院病人日 25000 18000 24000 21000
s ur yrj r 1 1 ( j 1,...,n) m s.t. vi xij i 1 vi 0(i 1,...,m), ur 0(r 1,...,s ) 1 令：t m , i t vi , vi xij0
i 1
i ij
通过适当的选取权值 vi (i 1,...,m)和ur (r 1,...,s ), 使得j 1,...,n, 有h j 1，则对第j0个决策单元的绩效评价 可归结为如下优化模型 ：
max h j0
u y
r 1 m r
s
rj 0
v x
i 1
i ij0
s ur yrj r 1 1 ( j 1,...,n) m s.t , vi xij i 1 vi 0(i 1,...,m), ur 0(r 1,...,s) 这是一个非线性规划问 题，为便于应用和求解 我们将其 转化为一个等价的线性 规划问题。
6-1
几个基本概念
[例11]有4个银行储蓄所，每月均 完成10,000笔人民币的存款 取款业务，但其投入情 况不同，见表 1 17所示，试分析 4个 储蓄所的绩效。
1-17 各储蓄所完成10，000笔存取款的投入
储蓄所 职员数 营业面积（m2）
B1
B2
B3
B4
6 100
3 120
10 50
7 70
y11 y 21 ... ys1
x12 x22 ... xm 2
y12 y22 ... ys 2
... x1n ... x2 n ... ... xmn
... y1n 1 ... y2 n 2 ... ... ... ysn s 产出
其对偶问题可写成： min n (i 1,...,m) j xij xij0 j 1 n s.t. j yrj yrj 0 (r 1,...,s ) j 1 0 ( j 1,...,n) 该模型显示出对偶问题 的经济意义十分明显： 为了评价j0决策单元的绩效，可用 一个假想的组合决策单 元 与其比较。约束条件的 左端项分别是这个组合 决策单元的 投入和产出。 因此，上述模型的含义 为，如果的最优值小于 1，则表明可 以找到这样一个假想的 决策单元，它可以用比 评价决策单元 更少的投入，获得不少 于被评价决策单元的产 出，从而表明 被评价的决策单元为非 DEA有效。只有 1时，才表明被评 价的决策单元DEA有效。
[解]先以医院H1为例，确定其是否 DEA有效， 写出H1绩效评价的线性规划模 型：
[例12] 有4所医院，其投入产出情况如表所 示。试分析评价上述4所医院是否DEA有效。
医院 H1 H2 H3 H4 引入对 偶变量 投入 职员数 285 162 275 230 床位数 100 64 90 85 面积m2 8000 6500 8500 7500 产出 年门诊病人次 35500 28000 33000 30000 住院病人日 25000 18000 24000 21000
令：t
1
v x
i 1
m
,
i t vi ,
r t ur
i ij0
则： max h j0
u y
r 1 m r i 1 s
s
rj 0
vi xij0
可转化为max h j0 t ur yrj 0 r yrj 0
r 1 r 1
s
s
即： max h j0 r yrj 0
y12 y22 ... ys 2
... x1n 给每一投入项赋权值v1 ... x2 n v2 ... ... ... xmn vm
... y1n 1 ... y2 n 2 ... ... ... ysn s 产出
30
O
3
6
9
12
职员数
【解】为进行分析，以职员数为横坐标、营 业面积为纵坐标，将四个储蓄所的投入绘图
营业面积m2 120 B2 B1 处于包络线以内的 决策单元称为DEA有 效（或Pareto有效） 即：减少人员数就 增加营业面积，并 不超出数据包络线 B3 60
90
B4
30
O
3
6
9
12
职员数
【解】为进行分析，以职员数为横坐标、营 业面积为纵坐标，将四个储蓄所的投入绘图
min 8000 1 6500 2 8500 3 7500 4 8000
[例12] 有4所医院，其投入产出情况如表所 示。试分析评价上述4所医院是否DEA有效。
医院 H1 H2 H3 H4 引入对 偶变量 投入 职员数 285 162 275 230 床位数 100 64 90 85 面积m2 8000 6500 8500 7500 产出 年门诊病人次 35500 28000 33000 30000 住院病人日 25000 18000 24000 21000
min 2851 1622 2753 2304 285
[例12] 有4所医院，其投入产出情况如表所 示。试分析评价上述4所医院是否DEA有效。
医院 H1 H2 H3 H4 引入对 偶变量 投入 职员数 285 162 275 230 床位数 100 64 90 85 面积m2 8000 6500 8500 7500 产出 年门诊病人次 35500 28000 33000 30000 住院病人日 25000 18000 24000 21000
营业面积m2 120 B2 B1 决策单元B1位于数 据包络线右上方， 连接O-B1，交于包 络线D点，坐标为 （5.6，93.3） B3 60
90
D
B4
30
O
3
6
9
12
职员数
【解】为进行分析，以职员数为横坐标、营 业面积为纵坐标，将四个储蓄所的投入绘图
营业面积m2 120 B2 B1
5.6 93.3 因有： 93.3% 6 100 即：将B1的职员和面积数 减少至原来的 93.3%，达
1.
线性规划及单纯形法
主讲教师：王旭 本章学时：12 h 剩余学时： 4 h
§6
数据包络分析
数据包络分析 （data envelopment analysis，DEA） 是一种对具有相同类型决策单元 （decision making unit，DMU）进行绩效评价的 方法。 相同类型决策单元——是指这类决策单元具有相同 性质的投入产出。 ——例如：医院投入的是医护人员、面积、床位数、 医疗设备和药品等，产出的是门诊病人人数、住 院病人人日、代培实习的医护人员数等。
i 1
r t ur
可以转ຫໍສະໝຸດ Baidu为：
s m i xij r yrj 0 ( j 1,...,n) r i i 1 m s.t. i xij0 1 i 1 vi 0(i 1,...,m), ur 0(r 1,...,s )
r 1
s ur yrj r 1 1 ( j 1,...,n) m s.t. vi xij i 1 vi 0(i 1,...,m), ur 0(r 1,...,s ) 1 令：t m , i t vi , vi xij0
r t ur
可以转化为：
s m i xij r yrj 0 ( j 1,...,n) 令对偶变量为（ ） r i i 1 m s.t. i xij0 1 令对偶变量为 i 1 vi 0(i 1,...,m), ur 0(r 1,...,s ) 写出其对偶问题。
6-2
评价决策单元DEA有效性C2R模型
设：有n个决策单元（ j 1,2,...,n） , 每个决策单元有相同的 m项投入（i 1,2,...,m）和相同的s项产出（r 1,2,...,s）， 用xij 表示第j个单元的第i项投入量，yij 表示第j个单元的第 r项产出量。其投入产出 情况表示如下： 决策单元 1 2 ... n 1 x11 2 x21 投入 ...... ... m xm1 x12 x22 ... xm 2
min 1001 642 903 854 100
[例12] 有4所医院，其投入产出情况如表所 示。试分析评价上述4所医院是否DEA有效。
医院 H1 H2 H3 H4 引入对 偶变量 投入 职员数 285 162 275 230 床位数 100 64 90 85 面积m2 8000 6500 8500 7500 产出 年门诊病人次 35500 28000 33000 30000 住院病人日 25000 18000 24000 21000
【解】为进行分析，以职员数为横坐标、营 业面积为纵坐标，将四个储蓄所的投入绘图
营业面积m2 120 B2 B1
90 B3 60
B4
30
O
3
6
9
12
职员数
【解】为进行分析，以职员数为横坐标、营 业面积为纵坐标，将四个储蓄所的投入绘图
营业面积m2 120 B2 B1 连接B2-B3-B4形成 一条凸折线。 构成生产可行集合。 说明集合内的点对 应的职员数和营业 面积数的储蓄所均 有能力完成10，000 笔存取款业务。 B4
90
D
（5.6，93.3） 到D点水平，才算DEA有 效。而D点则可由 35%的 B3 B2和65% 的B4线性组合而 成。 B4
60
30
O
3
6
9
12
职员数
6-2
评价决策单元DEA有效性C2R模型
该模型由Charenes、Coopper和Rhodes提出， 故名，DEA有效性的评价是对已有决策单元绩 效的比较评价，属相对评价。