经济管理学院2010年 5月 14日
---第 1 章 线性规划 ---
-1-
经济管理学院2010年 5月 14日
---第 1 章 线性规划 ---
-2-
第 一 章 线性规划
Linear Programming
经济管理学院2010年 5月 14日
---第 1 章 线性规划 ---
-3-
1.1 线性规划概述（ 1）
? 线性规划的广泛应用是计算机时代的产物。
? 1902年,Julius Farkas 发表论文，阐述有关线性规划问题。
? 1938年，英国人康德进行较详细研究。
? 1947年，美国学者 George Dantzig（丹茨格）发明了求解线性规划
的单纯形法（ 1951年发表），从而为线性规划的推广奠定了基础。
有人认为，求解线性规划的单纯形算法可与求解线性方程组的高
斯消元法相媲美。
经济管理学院2010年 5月 14日
---第 1 章 线性规划 ---
-4-
§ 1.1 线性规划概述（ 2）
? 线性规划的数学模型有三要素，从实际问题提炼成数学模
型时，首先寻找需求解的未知量 xj (j=1,…,n)，然后列举三
要素：
1,列写与自变量（未知量）有关的若干个线性约束条件（等
式或不等式）。
2,列写自变量 xj取值限制（ xj≥ 0,xj≤ 0或不限）。
3,列写关于自变量的线性目标函数值（极大值或极小值）。
? 其中，前两条称为可行条件，最后一条称为优化条件。符
合这三个条件的数学模型通常称为线性规划的一般型
（ general）。
经济管理学院2010年 5月 14日
---第 1 章 线性规划 ---
-5-
设备
产品
A B C D 单位利润
甲产品
乙产品
2
2
1
2
4
0
0
4
2
3
加工能力 12 8 16 12
1.1.1 问题的提出
例：某企业计划生产甲、乙两种产品，该两种产品均需经 A,B,C,D四
种不同设备上加工，按工艺资料规定，在各种不同设备上的加工时间及设
备加工能力、单位产品利润如表中所示。问,如何安排产品的生产计划,才能
使企业获利最大?
1.1 一般线性规划问题及数学模型 （ 3）
经济管理学院2010年 5月 14日
---第 1 章 线性规划 ---
-6-
建立模型：
设 产品的产量 甲 ?? x1件,乙 ?? x2件，则
Max z=2 x1+3 x2
2 x1+2 x2 ? 12
x1+2 x2 ? 8
4 x1 ? 16
4 x2 ?12
x1?0,x2 ?0
目标 (object),
限制条件
(subject to )：
经济管理学院2010年 5月 14日
---第 1 章 线性规划 ---
-7-
1.1.2 线性规划问题的一般数学模型
1.相关概念
（ 1）决策变量：指模型中要求解的未知量，简称变
量。
（ 2）目标函数：指模型中要达到的目标的数学表达
式。
（ 3）约束条件：指模型中的变量取值所需要满足的
一切限制条件。
此三项内容称为模型结构的三要素。
经济管理学院2010年 5月 14日
---第 1 章 线性规划 ---
-8-
2.线性规划模型的一般要求
（ 1）变量：取值为连续的、可控的量；
（ 2）目标函数：线性表达式；
（ 3）约束条件：线性的等式或者不等式。
经济管理学院2010年 5月 14日
---第 1 章 线性规划 ---
-9-
3, 线性规划问题的一般表示方法
（ 1）一般式：
max z=c1x1+c2x2+……… +cnxn
s.t,a11x1+a12x2+……… +a1nxn≤ b1
a21x1+a22x2+……… +a2nxn≤ b2
…… …… …… ……………
am1x1+am2x2+……… +amnxn≤ bm
x1,x2,………,xn≥ 0
s.t.---subject to
经济管理学院2010年 5月 14日
---第 1 章 线性规划 ---
-10-
n
(2) 和式,max z=? cjxjj=1
n
s.t,? aijxj≤bi （ i=1,2,……,m)
j=1
xj≥ 0 （ j=1,2,……,n)
其中,cj---------表示目标函数系数
aij---------表示约束条件系数
bi ---------表示约束右端项
经济管理学院2010年 5月 14日
---第 1 章 线性规划 ---
-11-
n
（ 4） 向量, max z=?cjxj
n j=1
s.t ? pjxj≤ b （ i=1,2,……,m）
j=1
xj≥ 0 （ j=1,2,……,n)
（ 3） 矩阵, max z=CX
s.t,AX≤ b
X≥ 0
经济管理学院2010年 5月 14日
---第 1 章 线性规划 ---
-12-
4,线性规划模型的标准形式
（ 1）变量：所有变量均 xj≥ 0
（ 2）目标函数：为取,max”形式
（ 3）约束条件：全部约束方程均为,=”连接
（ 4）约束右端项,bi≥ 0
非标准形式情况有
?变量,xj≤ 0,或 xj无约束
?目标函数,min
?约束条件：,≤,或,≥,
?约束右端项,bi<0
经济管理学院2010年 5月 14日
---第 1 章 线性规划 ---
-13-
LP的标准化：
（ 1）变量：若 xj?0，令 xj=-xj?,xj??0
若 xj无约束，则令 xj= xj?－ xj??,xj??0,xj???0
x
z
z
zmin
z ?= - z
z ? max
（ 3）约束方程：当, ?”时，引进松
弛（ slack）变量 +xs；
如 x1+x2?3 ? x1+x2+ x3=3
当, ?”时，引进剩余（ surplus）变
量 - xs；
如 x1+2x2? 4 ? x1+2x2－ x4=4
（ 2）目标函数：若求 min z，则 令 z ? = -z，等价于求 max （ z ?）
即有 min z= - max （ - z）
（ 4）约束右端项：当 bi < 0，则不等式
两端同乘（ - 1）
经济管理学院2010年 5月 14日
---第 1 章 线性规划 ---
-14-
例,将下述 LP模型标准化：
obj,Min z=2x1- x2+3x3
st,x1+2 x2+4x3 ? 6
3x1- 2x2+ x3 = 4
2x1- x2 - 3x3 ?5
x1 ?0,x2无符号限制,x3 ?0
解：设 z?= - z,x2= x2? - x2? ?,x2? ?0,x2? ? ?0,x3= - x3 ?,
x3??0, x4?0,x5?0,则有
obj,Max z?= -2x1 + (x2? - x2? ? ) + 3x3 ?
st,x1+2(x2? - x2? ? ) - 4x3 ?+x4=6
3x1 - 2(x2? - x2? ? ) - x3 ?=4
2x1 - (x2? - x2? ?) + 3x3 ?-x5=5
x1 ?0,x2? ?0,x2? ? ?0,x3 ??0,x4 ?0,x5 ?0
经济管理学院2010年 5月 14日
---第 1 章 线性规划 ---
-15-
复习思考题：
1,什么是模型结构的三要素？
2,什么是线性规划模型？能举出线性规划模型的例子
吗？
3,LP模型中目标函数系数、约束条件系数、约束右端
项的含义指的是什么？通常以什么符号表示？
4,LP模型的一般表示方法有几种形式？能否写出这些
形式？
5,什么是线性规划模型的标准形式？为何提出标准形
式？你能否把一个线性规划模型的非标准形式转化为标
准形式？
经济管理学院2010年 5月 14日
---第 1 章 线性规划 ---
-16-
1.1.3 简单线性规划模型的建立
步骤：
（ 2）具体构造模型：选择合适的决策变量、确定目标函
数的表达式、约束条件的表达式，分析各变量取值的符号
限制。
（ 1）分析问题：确定决策内容、要实现的目标以及所受
到的限制条件。
经济管理学院2010年 5月 14日
---第 1 章 线性规划 ---
-17-
例 1,某工厂在生产过程中需要使用浓度为 80%的硫酸
100 吨，而市面上只有浓度为 30%,45%,73%,85%，
92%的硫酸出售,每吨的价格分别为 400,700,1400、
1900和 2500元。 问：采用怎样的购买方案，才能使所需
总费用最小？
经济管理学院2010年 5月 14日
---第 1 章 线性规划 ---
-18-
模型：
设 第 j 种硫酸需购买 xj 吨，则
Min z=400x1+700x2+1400x3+1900x4+2500x5
st,x1+x2+x3+x4+x5=100
30?x1+45?x2+73?x3+85 ? x4+92?x5=100?80?
x1?0,x2?0,x3?0,x4?0,x5?0
经济管理学院2010年 5月 14日
---第 1 章 线性规划 ---
-19-
例 2：设有下面四个投资机会：
甲：在三年内，投资人应在每年年初投资，每年每元投资可获利 0.2
元，每年取息后可重新将本息用于投资。
乙：在三年内，投资人应在第一年年初投资，每两年每元投资可获
利 0.5元，两年后取息，取息后可重新将本息用于投资。这种投资最多
不得超过 20,000元。
丙：在三年内，投资人应在第二年年初投资，两年后每元投资可获
利 0.6元。这种投资最多不得超过 15,000元。
丁：在三年内，投资人应在第三年年初投资，一年后每元投资可获
利 0.4元。这种投资最多不得超过 10,000元。
假定在这三年为一期的投资中，每期的开始有 30,000元资金可供使
用，问：采取怎样的投资计划，才能在第三年年底获得最大收益？
经济管理学院2010年 5月 14日
---第 1 章 线性规划 ---
-20-
模型：
设 xij第 i 年投资于第 j 项目上的资金量，则
Max z=0.2 (x11+x21+ x31) + 0.5 x12 + 0.6 x2 3+ 0.4 x34
st,x11+ x12?30,000
x21+ x23?30,000? x12+ 0.2 x11
x31+ x34?30,000? x23 +0.2(x11+ x21)+0.5x12
x12 ?20,000
x23 ?15,000
x34?10,000
xij?0,(i=1,2,3; j=1,2,3,4)
x11
x12
x21
x23
x31
x341 2 3 4
30,000
经济管理学院2010年 5月 14日
---第 1 章 线性规划 ---
-21-
例 3,合理下料问题：
要制作 100套钢筋架子，每套含 2.9米,2.1米,1.5米
的钢筋各一根。已知原料长 7.4米，问：如何下料，使用
料最省？
长度 Ⅰ Ⅱ Ⅲ Ⅳ Ⅴ
2.9米
2.1米
1.5米
1 2 1
2 2 1
3 1 2 3
合计 (米 ) 7.4 7.3 7.2 7.1 6.6
料头 (米 ) 0 0.1 0.2 0.3 0.8
经济管理学院2010年 5月 14日
---第 1 章 线性规划 ---
-22-
模型,
设 xj ?? 为第 j种方案用料的数量,则
Min z=0x1+0.1x2+0.2x3+0.3x4+0.8x5
st,x1+2x2 + x4 =100
2x3+2x4+ x5=100
3x1+ x2+2x3 +3x5=100
xj?0,(j=1,2,---,5)
思考题：目标函数是否可以选取为 min z'=x1+x2+x3+x4+x5,为什
么？
经济管理学院2010年 5月 14日
---第 1 章 线性规划 ---
-23-
例 4,有 A,B两种产品，都需要经过前、后两到化学反应过程。每种产
品需要的反应时间及其可供使用的总时间如表示。
每生产一个单位产品 B的同时，会产生 2个单位的副产品 C，且不需外
加任何费用。副产品 C的一部分可以出售盈利，其余的只能加以销毁。
副产品 C每卖出一个单位可获利 3元，但是如果卖不出去，则每单位
需销毁费用 2元。预测表明，最多可售出 5个单位的副产品 C。
要求确定使利润最大的
生产计划。
产品
过程
A B
可利用
时间
前道过程 2 3 16
后道过程 3 4 24
单位利润 4 10
经济管理学院2010年 5月 14日
---第 1 章 线性规划 ---
-24-
模型：
设 产品的产量为 A? x1单位,B ? x2单位，已售出的产品 C ? x3 单
位，销毁的产品 C ? x4单位，则
Max z=4x1+10x2+3x3－ 2x4
st,2x1+3x2?16
3x1+4x2?24
2x2=x3+x4
x3? 5
xj?0,(j=1,2,3,4)
经济管理学院2010年 5月 14日
---第 1 章 线性规划 ---
-25-
例 5,一家昼夜服务的饭店,24小时中需要的服务员数如下表所
示。每个服务员每天连续工作 8小时，且在时段开始时上班。问：
最少需要多少名服务员？试建立该问题的线性规划模型。
起迄时间 服务员人数
2 - - - - 6 时 4
6 - - - 1 0 时 8
1 0 - - 1 4 时 10
1 4 - - 1 8 时 7
1 8 - - 2 2 时 12
2 2 - - - 2 时 4
经济管理学院2010年 5月 14日
---第 1 章 线性规划 ---
-26-
模型：
设 xj? 第 j时段开始上班工作的服务员数，则
Min z=x1+x2+x3+x4+x5+x6
st,x6+x1?4
x1+x2?8
x2+x3?10
x3+x4?7
x4+x5?12
x5+x6?4
xj?0,(j=1,2,---,6)
经济管理学院2010年 5月 14日
---第 1 章 线性规划 ---
-27-
建立线性规划模型要求：
（ 1）要求决策的量是连续的、可控的量，或者是可以简化为连
续取值的变量；
（ 2）要求所解决的问题的目标可用数值指标描述，并且能表示
成线性函数；
（ 3）存在着多种决策方案可供选择；
（ 4）决策所受到的限制条件可用线性的等式或者不等式表示。
经济管理学院2010年 5月 14日
---第 1 章 线性规划 ---
-28-
1.1.4 线性规划问题解的有关概念
设模型 n
max z=?cjxj
j=1
n
s.t,?aijxj=bi （ i=1,2,……,m)
j=1
xj≥ 0 （ j=1,2,……,n)
（ 1）可行解：满足所有约束方程和变量符号限制条件的一组变量的
取值。
（ 2）可行域：全部可行解的集合称为可行域。
（ 3）最优解：使目标函数达到最优值的可行解。
经济管理学院2010年 5月 14日
---第 1 章 线性规划 ---
-29-
（ 4） 基,设 A为线性规划模型约束条件系数矩阵（ m ? n,m<n），
而 B为其 m?m子矩阵，若 |B|≠ 0，则称 B为该线性规划模型的一个基。
（ 5） 基变量,基中每个向量所对应的变量称为基变量。
（ 6） 非基变量,模型中基变量之外的变量称为非基变量。
（ 7） 基本解（基解）,令模型中所有非基变量 X非基 =0后，由模型约束方
程组 n
?aijxj =bi (i=1,2,……,m)得到的一组解。
j=1
（ 8） 基本可行解（基可行解）,在基本解中，同时又是可行解的解称为
基本可行解。
（ 9） 可行基,对应于 基本可行解 的基称为可行基。
经济管理学院2010年 5月 14日
---第 1 章 线性规划 ---
-30-
Max z=2x1+3x2
st,x1+x2≤3
x1+2x2≤4
x1,x2≥0
Max z=2x1+3x2 +0x3 +0x4
st,x1+x2+x3=3
x1+2x2+x4=4
x1,x2,x3,x4≥0
A=
x1 x2 x3 x4
1 1 1 0
1 2 0 1
可行解,X=(0,0)T,X=(0,1)T,X=(1/2,1/3)T 等。
设 B= 1 0
0 1，令
，则 | B |=1≠0,
令 x1=x2 =0，则 x3 =3,x4=4,X=(0,0,3,4)T
例：
x3 x4 —— 基变量
令 B= 1 1
1 0
x1 x3
，则
令 x2=x4 =0，则 x3 =-1,x1=4,X=(4,0,-1,0)T
| B |=-1≠0,
—— 非基本可行解
—— 基本可行解
标准化
经济管理学院2010年 5月 14日
---第 1 章 线性规划 ---
-31-
复习思考题：
1,可行解和可行域有怎样的关系？
2,一个标准化 LP模型，最多可有多少个基？
3,基本解是如何定义的？怎样才能得到基本解？
4,可行解、基本解、基本可行解三者之间有什么关系？在 LP
模型中是否一定存在？
5,什么是可行基？
经济管理学院2010年 5月 14日
---第 1 章 线性规划 ---
-32-
1.2 线性规划问题的图解方法
* 利用作图方法求解。
例,max z=2x1+3x2
s.t 2x1+2x2?12 ----------①
x1+2x2? 8 ----------②
4x1?16 ----------③
4x2 ?12 ----------④
x1?0,x2?0
经济管理学院2010年 5月 14日
---第 1 章 线性规划 ---
-33-
x1
x2
2
2 4 6 8
4
6
0
①
②
④
③
Z=6Z=0
(4,2) Z
max
经济管理学院2010年 5月 14日
---第 1 章 线性规划 ---
-34-
A A
B
唯一解 无穷多解
无界解 无可行解
??
?
经济管理学院2010年 5月 14日
---第 1 章 线性规划 ---
-35-
步骤,（ 1）作平面直角坐标系，标上刻度；
（ 2）做出约束方程所在直线，确定可行域；
（ 3）做出一条目标函数等值线，判定优化方向；
（ 4）沿优化方向移动，确定与可行域相切的点，确定最优
解，并计算最优值。
讨论一：模型求解时，可得到如下几种解的状况：
（ 1）唯一最优解：只有一点为最优解点，简称唯一解；
（ 2）无穷多最优解：有许多点为最优解点，简称无穷多解；
（ 3）无界最优解：最优解取值无界，简称无界解 ；
（ 4）无可行解：无可行域，模型约束条件矛盾。
讨论二,LP模型求解思路：
（ 1）若 LP模型可行域存在，则为一凸形集合；
（ 2）若 LP模型最优解存在，则其应在其可行域顶点上找到；
（ 3）顶点与基本解、基本可行解的关系：
经济管理学院2010年 5月 14日
---第 1 章 线性规划 ---
-36-
复习思考题：
1,LP模型的可行域是否一定存在?
2,图解中如何去判断模型有唯一解、无穷多解、无界解
和无可行解？
3,LP模型的可行域的顶点与什么解具有对应关系？
4.你认为把所有的顶点都找出来，再通过比较目标函数
值大小的方式找出最优解，是否是最好的算法？为什么？
经济管理学院2010年 5月 14日
---第 1 章 线性规划 ---
-37-
1.3 单纯形法 的基本原理 （ Simplex Method）
1.3.1 两个概念：
（ 1）凸集：对于集合 C中任意两点连线上的点，若也在 C内，则称
C为凸集。
或者, 任给 X1?C,X2 ?C,X=?X1+ (1-?)X2 ? C (0<?<1)，则 C
为凸集。
凸集 非凸集
经济管理学院2010年 5月 14日
---第 1 章 线性规划 ---
-38-
（ 2）顶点：凸集中不成为任意两点连线上的点，称为凸集顶点。
或者,
设 C为凸集,对于 X?C，不存在任何 X1?C,X2 ?C,且 X1≠X 2，
使得 X=?X1+(1-?)X2?C,(0<?<1)，则 X为凸集顶点。
X
X
X
X
X
经济管理学院2010年 5月 14日
---第 1 章 线性规划 ---
-39-
定理 1,若线性 LP模型存在可行解，则可行域为凸集。
证明,设 max z=CX
st,AX=b
X?0
并设其可行域为 C，若 X1,X2为其可行解,且 X1≠X2,
则 X1?C,X2 ?C,即 AX1=b,AX2=b,X1?0,X2?0，
又 X为 X1,X2连线上一点，即 X=?X1+(1-?)X2?C,(0<?<1)，
∴ AX=?AX1+ (1-?)AX2 = ?b+ (1-?)b =b,(0<?<1)，且 X ?0，
∴ X ?C，
∴ C为凸集。
1.3.2 三个基本定理：
经济管理学院2010年 5月 14日
---第 1 章 线性规划 ---
-40-
引理,线性规划问题的可行解 X=(x1,x2,·····,xn)T 为基本可行解
的充要条件是 X的正分量所对应的系数列向量线性独立。
证：
（ 1）必要性,X基本可行解 ?X的正分量所对应的系数列向量线性独立
可设 X=(x1,x2,···,xk,0,0,···,0)T，若 X为基本可行解,显然，由 基
本可行解 定义可知 x1,x2,······,xk所对应 的系数列向量 P1,P2,······,Pk应该线
性独立。
（ 2）充分性,X的正分量所对应的系数列向量线性独立 ?X为基本可行解
若 A的秩为 m，则 X的正分量的个数 k?m；
当 k=m时，则 x1,x2,······,xk的系数列向量 P1,P2,······,Pk恰好构成基，
∴ X为基本可行解。
当 k<m时，则必定可再找出 m-k个列向量与 P1,P2,······,Pk一起构成基，
∴ X为基本可行解。
经济管理学院2010年 5月 14日
---第 1 章 线性规划 ---
-41-
证：用反证法 X非基本可行解 ?X非凸集顶点
（ 1）必要性, X非基本可行解 ?X非凸集顶点
不失一般性，设 X=(x1,x2,·····,xm,0,0,····,0)T，为非基本可行解，
∵ X为可行解，
∴ ?pjxj=b，
j=1
n
即 ?pjxj=b ······(1)
j=1
m
又 X是非基本可行解,∴ P1,P2,······,Pm线性相关，即有
?1P1+?2P2+······+?mPm=0,其中 ?1,?2,······,?m不全为 0，两端同乘 ?≠ 0，得
??1P1+??2P2+······+??mPm=0,······（ 2）
定理 2,线性规划模型的基本可行解对应其可行域的顶点。
经济管理学院2010年 5月 14日
---第 1 章 线性规划 ---
-42-
由 (1)+(2)得 (x1+ ??1)P1+ (x2+ ??2)P2+······+ (xm+ ??m)Pm=b
由 (1)-(2)得 (x1 -??1)P1+ (x2 -??2)P2+······+ (xm -??m)Pm=b
令 X1=(x1+ ??1,x2+ ??2,······,xm+ ??m,0,·····,0)T
X2=(x1-??1,x2-??2,······,xm-??m, 0,·····,0)T
取 ?充分小,使得 xj???j?0,则 X1,X2均为可行解，
但 X=0.5X1+(1-0.5)X2,∴ X是 X1,X2连线上的点，
∴ X非凸集顶点。
经济管理学院2010年 5月 14日
---第 1 章 线性规划 ---
-43-
（ 2）充分性,X非凸集顶点 ?X非基本可行解
设 X=(x1,x2,···,xr,0,0,···,0)T为 非凸集顶点，则必存在 Y,Z两点，使得
X=?Y+(1-?)Z,(0<?<1)，且 Y,Z为可行解
或者 xj=?yj+(1-?)zj (0<?<1)，（ j=1,2,···,n),yj?0,zj?0
∵ ?>0,1-?>0,当 xj=0,必有 yj=zj=0
∴ ?pjyj =
j=1
n
?pjyj=b ······(1)
j=1
r
?pjzj =
j=1
n
?pjzj=b ······(2)
j=1
r ? (yj-zj)pj=0j=1
r
,(1)-(2),得
即 (y1 - z1)P1+ (y2 - z2)P2+······+ (yr -zr)Pr=0
经济管理学院2010年 5月 14日
---第 1 章 线性规划 ---
-44-
∵ Y,Z为不同两点,∴ yj-zj不全为 0，
∴ P1,P2,······,Pr线性相关，
∴ X非基本可行解。
经济管理学院2010年 5月 14日
---第 1 章 线性规划 ---
-45-
3
4O
(3,3)
C (4,2)
6
6
2X1+2X2+X3=12
4X2+X5=12
4X1+X4=16
XA=(0,3,6,16,0)T
XO=(0,0,12,16,12)T
XB=(3,3,0,4,0)T
XC=(4,2,0,0,4)T
XD=(4,0,4,0,12)T
A
D
B
X1
X2
经济管理学院2010年 5月 14日
---第 1 章 线性规划 ---
-46-
z1=CX1=CX0-C?=zmax-C?, z2=CX2=CX0+C? =zmax+C?
∵ z0 = zmax ? z1, z0 = zmax ? z2,
∴ z1 = z2 = z0,即 X1, X2也为最优解，
若 X1,X2仍不是顶点，可如此递推，直至找出一个顶点为最优
解。
从而，必然会找到一个 基本可行解 为最优解。
定理 3,若线性规划模型有最优解，则一定存在一个基本可
行解为最优解 。
证,设 X0=(x10,x20,······,xn0)T 是线性规划模型的一个最优解，
z0=zmax=CX0
若 X0非基本可行解，即非顶点，只要取 ?充分小，
则必能找出 X1= X0-??0,X2 = X0+??0，即 X1, X2为可行解，
经济管理学院2010年 5月 14日
---第 1 章 线性规划 ---
-47-
单纯形法的计算步骤：
初始基本可行解
新的基本可行解
最优否？ STOPY
N
经济管理学院2010年 5月 14日
---第 1 章 线性规划 ---
-48-
1．初始基本可行解的确定：
设模型 n
max z=?cjxj
j=1
n
s.t,?aijxj?bi （ i=1,2,……,m) ????
j=1
xj?0 （ j=1,2,……,n)
n mmax z=?c
jxj + ? 0·xsij=1 I=1
n
s.t,?aijxj+xsi=bi （ i=1,2,……,m)
j=1
xj?0,xsi?0 （ j=1,2,……,n; i=1,2,……,m)
化标准形
∴ 初始基本可行解 X=(0,0,···,0,b1,b2,···,bm)T，
n-m个 0
经济管理学院2010年 5月 14日
---第 1 章 线性规划 ---
-49-
2．从一个基本可行解向另一个基本可行解转换
不失一般性，设基本可行解 X0=(x10,x20,······,xm0,0,···,0)T,
前 m个分量为正值，秩为 m，其系数矩阵为
P1 P2 …… P m Pm+1 …… P j…… P n b
1 0 …… 0 a 1,m+1 ····· a1j ····· a 1n b1
0 1 …… 0 a 2,m+1 ····· a2j ····· a 2n b2
0 0 …… 1 a m,m+1 ····· amj ····· a mn bm
…… ………… …… ………………
∴ ?pjxj0 =
j=1
n
?pixi0=b ······(1)
i=1
m
经济管理学院2010年 5月 14日
---第 1 章 线性规划 ---
-50-
又 P1 P2 …… P m为一个基，任意一个非基向量 Pj可以以该组向
量线性组合表示，即
Pj = a1j P1 + a2j P2 +···+ amj Pm,即 Pj =? aij pi,
移项，两端同乘 ?>0,有 ?(Pj-?aij pi )=0 ·········(2)
i=1
m
i=1
m
(1)+(2),?(xi 0-?aij)Pi + ? Pj =b，
取 ?充分小，使所有 xi 0 -?aij ?0，从而
i=1
m
X1 = (x1 0-?a1j,x2 0-?a2j,······,xm 0-?amj,0,······,?,···,0)T
也是可行解。
当取 ? = min — aij >0 = —,则 X1的前 m个分量至少有一个 xL1为 0。xi 0a
ij alj
xL 0
i
∴ P1,P2,······,PL-1,PL+1,······ Pm,Pj 线性无关。
经济管理学院2010年 5月 14日
---第 1 章 线性规划 ---
-51-
∴ X1 也为基本可行解。
3.最优解的判别
依题义 z0 =? c
jxj0 =?ci xi0i=1
m
j=1
n
z1 =? cjxj1 =?ci(xi 0-?aij)+ cj ?
i=1
m
j=1
n
=?cixi 0+?(cj - ?ciaij)= z0 +??j
i=1
m
i=1
m
经济管理学院2010年 5月 14日
---第 1 章 线性规划 ---
-52-
因 ?>0，所以有如下结论：
(1) 对所有 j，当 ?j?0,有 z1 ? z0,即 z0为最优值,X0为最优解；
(2) 对所有 j，当 ?j?0,但存在某个非基变量 ?k=0，则对此 Pk作
为新基向量得出的解 X1，应有 z1 = z0,故 z1 也 为最优值，
从而 X1为最优解，且为基本可行解，
∴ X0,X1 连线上所有的点均为最优解，因此该线性规划模型
具有无穷多解；
(3) 若存在某个 ?j ?0，但对应 aij?0，则因当 ???时，有 z1 ??，
∴ 该线性规划模型具有无界解。
经济管理学院2010年 5月 14日
---第 1 章 线性规划 ---
-53-
1.4 单纯形法的计算及示例
1.4.1 单纯形法几何解释 ---顶点寻优
例,max z=2x1+3x2 max z=2x1+3x2+0x3 +0x4
s.t x1+x2?3 标准化 s.t x1+x2+x3=3
x1+2x2 ? 4 ? x1+2x2+x4=4
x1?0,x2?0 xj?0,(j=1,2,3,4)
（ 1）初始基本可行解的选择,-----坐标原点处
令 x1 =x2 =0,由 x1+x2+x3=3
x1+2x2+x4=4
（ 2） 是否为最优解的判定,-----计算检验数
若 x1↑1,则 x3↓1,x4↓1,σ1= 2-（ 0?1+0 ?1） =2 σj
=△ z=cj-zj = cj-?ciaij, 称 σj为检验数。
x3=3 -(x1+x2)
x4=4 -(x1+2x2)
解得 X=( 0,0,3,4 )T
经济管理学院2010年 5月 14日
---第 1 章 线性规划 ---
-54-
若 x2↑1,则 x3↓1,x4↓2,σ2=3-(0?1+0?2)=3
**** 当所有检验数均有 σ j ? 0时，则为最优解。 ****
（ 3）找新的顶点（基本可行解）：
直观看,x2↑1,则 z ↑ 3,∴ 应找 A点，即增加 x2。
x2 可增加多少？需要保证 x3=3 -(x1+x2)?0
x4=4 -(x1+2x2)?0,
∴ x2 = min（ 3/1,4/2），从而
x3=1 -(x1 / 2 - x4/2）
x2=2 -(x1 / 2 + x4 / 2)
令 x1 = x4 =0，则新的基本可行解为 X=( 0,2,1,0)T
重复上述过程，直至所有检验数 σ j ? 0。
经济管理学院2010年 5月 14日
---第 1 章 线性规划 ---
-55-
继续迭代：
找新的顶点（基本可行解）：
若 x1↑1,则 z ↑ 1/2,∴ 应找 B点，即增加 x1。
x1 可增加多少？需要保证 x3=1 -(x1/2 - x4 /2)?0
x2=2 -(x1/2+x4/2)?0，
∴ x1 = min（ 2,4），从而
x1=2 -(2x3-x4)
x2=1 -(-x3+x4),
则新的基本可行解为 X=( 2,1,0,0)T
若 x1↑1,则 x3↓1/2,x2↓1/2,σ1= 2-（ 0?1/2+3?1/2） =1/2
若 x4↑1,则 x3↓-1/2,x2↓1/2,σ4= 0-（ 0?(-1/2)+3?1/2） =-3/2
σ3 = -1,σ4 = -1,zmax=7
经济管理学院2010年 5月 14日
---第 1 章 线性规划 ---
-56-
①
②
O C
A
B
X1
X2
(0,2)
(3,0)
(2,1)
3
4
经济管理学院2010年 5月 14日
---第 1 章 线性规划 ---
-57-
Cj →
x1 x2 x3 x4XB bCB
1 1 1 0
1 2 0 1
2 3 0 0
3
4
x3
x4
0
0
cj - zj 2 3 0 0
3/1=3
4/2= 2
1/2 0 1 -1/2
1/2 1 0 1/2
x3
x2 12
cj - zj 1/2 0 0 -3/2
0
3
2
4
1 0 2 -1
0 1 -1 1
x1
x2
2
1
cj - zj 0 0 -1 -1
2
3
1.4.2 单纯形法计算：
θi
经济管理学院2010年 5月 14日
---第 1 章 线性规划 ---
-58-
单纯形法计算过程总结：
（ 1）化标准形，列初始单纯形表；
（ 2）计算检验数,σj =△ z=cj-zj = cj- ?ciaij
（ 3）最优性判断,当 所有检验数均有 σ j ? 0时，则为最优解。否则
迭代求新的基本可行解。
（ 4）迭代：
入基变量：取 max{σ j ?0 }=σk→xk
出基变量：取 min {θi=bi/aik ? aik>0}=θl → x(l)
主元素,[alk]
新单纯表,pk=单位向量
注,当所有检验数 σ j ? 0时，若存在非基
变量检验数为 0时，则有无穷多解，否则只
有唯一最优解。
i=1
m
经济管理学院2010年 5月 14日
---第 1 章 线性规划 ---
-59-
例,min z=2x1+3x2 max z=-2x1-3x2+0x3
s.t x1+x2? 3 标准化 s.t x1+x2 -x3=3
x1+2x2 = 4 ? x1+2x2=4
x1?0,x2?0 xj?0,(j=1,2,3,4)
max z=-2x1-3x2+0x3 -Mx4-M x5
s.t x1+x2 -x3+ x4 =3
x1+2x2 +x5 =4
xj?0,(j=1,2,3,4,5)
引进人工变量，及 M—— 非常大正系数，模型转变为
这种处理方法称为大 M法，以下则可完全按单纯形法求解。
1．大 M法
1.5 单纯形法进一步讨论
经济管理学院2010年 5月 14日
---第 1 章 线性规划 ---
-60-
Cj →
x1 x2 x3 x4XB bCB
1 1 -1 1 0
1 2 0 0 1
-2 -3 0 -M -M
3
4
x4
x5
-M
-M
cj - zj -2+2M -3+3M -M 0
3/1=3
4/2= 2
1/2 0 -1 1 -1/2
1/2 1 0 0 1/2
x4
x2 12
cj - zj -1/2+M/2 0 -M 0 3/2-M/2
-M
-3 24
1 0 -2 2 -1
0 1 1 -1 1
x1
x2
2
1
cj - zj 0 0 -1 -1-M -1-M
-2
-3
θix
5
0
经济管理学院2010年 5月 14日
---第 1 章 线性规划 ---
-61-
说明：
当所有 ?j?0, 但存在人工变量 x人 ?0,则可以判定
该模型无可行解。
采用大 M法求解线性规划模型时，如果模型中各个
系数与 M的值非常接近时，若手工计算时，不会出现任
何问题。如果利用计算机程序求解，则大 M表现为一个
较大的数字，由于综合计算的影响，导致检验数出现
符号误差，引起判断错误，从而使大 M方法失效。在这
种情况下，可采用下面的两阶段法进行计算。
经济管理学院2010年 5月 14日
---第 1 章 线性规划 ---
-62-
2．两阶段法,
例, min z=2x1+3x2 max z=-2x1-3x2+0x3
s.t x1+x2? 3 标准化 s.t x1+x2 -x3=3
x1+2x2 = 4 ? x1+2x2=4
x1?0,x2?0 xj?0,(j=1,2,3,4)
obj,max z=-x4-x5
s.t x1+x2 -x3+ x4 =3
x1+2x2 +x5 =4
xj?0,(j=1,2,3,4,5)
(1)第一阶段，构造判断是否存在可行解的模型：
用单纯形法求解，若 zmax=0,表明该模型有可行解，则可进
入第二阶段，求原模型最优解。
经济管理学院2010年 5月 14日
---第 1 章 线性规划 ---
-63-
Cj →
x1 x2 x3 x4XB bCB
1 1 -1 1 0
1 2 0 0 1
0 0 0 -1 -1
3
4
x4
x5-1 -1
cj - zj 2 3 -1 0
3/1=3
4/2= 2
1/2 0 -1 1 -1/2
1/2 1 0 0 1/2
x4
x2 12
cj - zj 1/2 0 -1 0 -3/2
-1
0
2
4
1 0 -2 2 -1
0 1 1 -1 1
x1
x2
2
1
cj - zj 0 0 0 -1 -1
0
0
θix
5
0
经济管理学院2010年 5月 14日
---第 1 章 线性规划 ---
-64-
(2) 第二阶段，将原目标函数引入最终单纯形表，继续迭代：
max z=-2x1-3x2+0x3
Cj →
x1 x2 x3XB bCB
1 0 -2
0 1 1
-2 -3 0
2
1
x1
x2-2-3
cj - zj 0 0 -1
经济管理学院2010年 5月 14日
---第 1 章 线性规划 ---
-65-
1.4.3 程序求解
（ 1）用 LINDO软件求解
（ 2）用 EXCEL工具求解
这是一个 DOS程序，使用 BASIC语言编写。运行时采
用命令格式，以文本形式输入。
使用 EXCEL中数据处理工具 ——— 规划求解。
经济管理学院2010年 5月 14日
---第 1 章 线性规划 ---
-66-
1.6 改进单纯形法
单纯形法迭代过程可用矩阵变换描述如下,设
max z=CX
st AX?b
X?0
分解 max z=CBXB+ CNXN+0XS
st BXB+ NXN+IXS=b
XB,XN,,XS?0
约束方程两端同乘 B-1,则可得如下表达式：
式中,B—— 最终表中基对应的矩阵，
N—— 初始表与最终表中均为非基对应的矩阵，
I—— 单位矩阵
A=[ B N ]
max z=CBXB+ CNXN+0XS
st B-1 BXB+ B-1 NXN+ B-1 XS= B-1 b
XB,XN,,XS?0 —— 对应最终单纯形表的模型
经济管理学院2010年 5月 14日
---第 1 章 线性规划 ---
-67-
用单纯形表表示如下：
XS = b B N I
XB = b′ I N′ B-1
初始表 XB XN XS
cj - zj 0,······,0 ?N ?S
最终表 XB XN XS
cj - zj ?B ?N 0,······,0
表中，
b′=B-1b
N′ =B-1N
或者 Pj′ =B-1Pj
?N′= CN-CB B-1 N
或者 ?j′=Cj-CBB-1 Pj
?S′= -CB B-1
········
经济管理学院2010年 5月 14日
---第 1 章 线性规划 ---
-68-
⑴ 化标准形,B-1 new =I,XB =b，
⑵ 求检验数,?N = CN-CB B-1 new N,?S = -CB B-1 new
⑶ 最优性判别：
① 所有 ?? 0,X人 ≠0,无可行解；
② 所有 ?? 0,X人 =0，存在 ?N =0，无穷多解；
③ 所有 ?? 0,X人 =0，不存在 ?N =0，唯一解；
④ 否则 (存在 ?>0)，转⑷,
⑷ 取 ?max ? xk, 为换入变量，
计算 Pk′= B-1 new Pk，若 ? Pk′??0 ?无界解,
否则，计算 ?i =? bi /aik |aik >0?,取 ?min ?xl为换出变量，
⑸ 令
改进单纯形法计算步骤：
经济管理学院2010年 5月 14日
---第 1 章 线性规划 ---
-69-
D=
1 ······ - a1k / aLk ····· 0
0 ······ 1/ aLk ····· 0
0 ······ - amk / aLk ····· 1
···
·
··
···
·
··
···
·
··
xL
计算 B-1 new =D B-1old,
b′ = B-1 newb
转⑵。
注,D矩阵为单位矩阵中出基变量所在单位向量以上述列
向量代换。
实例演算如下：
经济管理学院2010年 5月 14日
---第 1 章 线性规划 ---
-70-
例,max z=2x1+3x2 max z=2x1+3x2+0x3 +0x4
s.t x1+x2?3 标准化 s.t x1+x2+x3=3
x1+2x2 ? 4 ? x1+2x2+x4=4
x1?0,x2?0 xj?0,(j=1,2,3,4)
x1 x2 x3 x4 b
1 1 1 0 3
1 2 0 1 4
⑴ 初始解：
B-1 new=I,XB=(x3,,x4)T=(3,4)T,?N=(?1,?2)=(2,3)，
计算 P2′ = B-1 new P2=(1,2)T，
∴ 换入变量,?max ? x2,
换出变量,?i =? bi /ai2 |ai2 >0? = (3,2),?min ? x4,
经济管理学院2010年 5月 14日
---第 1 章 线性规划 ---
-71-
⑵ 第二次计算：
1 -1/2
0 1/2
D=, B-1 new =D B-1old = 1 -1/2
0 1/2
1 0
0 1
1 -1/2
0 1/2=
XB=(x3,,x2)T= B-1 new b =(1,2)T,
?N=(?1,?4)= CN -CB B-1 N =(2,0)-(0,3) 1 -1/2
0 1/2
1 0
1 1
=(1/2,-3/2),
∴ 换入变量,?max ?x1,
计算 P1′ = B-1 new P1=(1/2,1/2)T，
∴ 换出变量,?i =? bi /ai1 |ai1 >0? = (2,4),?min ? x3,
经济管理学院2010年 5月 14日
---第 1 章 线性规划 ---
-72-
2 0
-1 1
D=, B-1 new =D B-1old = 2 0
-1 1
2 -1
-1 1
1 -1/2
0 1/2 =
XB=(x1,x2)T= B-1 new b =(2,1)T,
?N=(?3,?4)= CN -CB B-1 N =(0,0)-(2,3) 2 -1
-1 1
1 0
0 1
=(-1,-1),
⑶ 第三次计算：
所有 ?? 0，
故为最优解，
XB=(x1,x2)T=(2,1)T,
z max =7
经济管理学院2010年 5月 14日
---第 1 章 线性规划 ---
-73-
例 用单纯形法解目标规划问题时，有如下二个单纯
形表，试把表中数字补全。
Cj →
x1 x2 x3 x4XB bCB
1 0
0 1
0 0
3 x3 x
4
0
0
cj - zj
CB XB b x1 x2 x3 x4
2 -1
-1
1
x1
x2 1
cj - zj -1 -1
2
3
···
经济管理学院2010年 5月 14日
---第 1 章 线性规划 ---
-74-
?S=(-1,-1)=(?3,?4)= CS-CB B-1 = -(c1,c2) 2 -1-1 1 1 00 1
=-(2c1-c2,-c1+c2)
c1=2
c2=3∴ 又 b
′ = B-1 b，
b1′
1
2 -1
-1 1
3
b2
6-b2
-3+b2= =
b1′=2
b2 =4∴
2 -1
-1 1
1 0
0 1 =
a11 a12
a21 a22
1 0
0 1 =
2a11 -a21 -2a12 -a22
-a11 +a21 -a12 +a22?
∴ a11 =1,a12 =1,a21 =1,a22 =2
解：
经济管理学院2010年 5月 14日
---第 1 章 线性规划 ---
-75-
1.7 线性规划问题的应用案例
例一, 泰和玩具公司,预计 2001年里公司的月现金流量如表中所示。
负的现金流量表示流出的现金超过流入的现金。为应付它的债务，公司
需要在年内提早借款。该公司可有两种借款方式：（ 1）可在 1月份贷到
所需要的一年期的长期贷款，从 2001年 2月份开始,每月需为这笔贷款支
付 1%的利息,贷款本金必须在 2002年 1月初归还。（ 2）公司还可获得短
期的银行贷款，月利率为 1.5%，公司需在下一个月里归还上一个月初的
短期贷款本金与利息。所有的短期贷款必须在 2002年 1月初归还。在每
月末，现金余额可获得 0.4%的利息。问：如何制定借款计划，可使公司
在 2002年 1月初获得最大的现金余额？
月份 1 月 2 月 3 月 4 月 5 月 6 月 7 月 8 月 9 月 10 月 11 月 12 月
现金流量
( 千元 )
-1 2 -1 0 -8 -1 0 -4 5 -7 -2 15 12 -7 45
经济管理学院2010年 5月 14日
---第 1 章 线性规划 ---
-76-
应解决的问题,
?长期贷款的数量 (L)
?每月短期贷款的数量 (St)
?每月月末的现金平衡（余额） (Cbt)
?期间最后的现金平衡 (2002年初现金余额 ) (Cb13)
?每月所付的长期与短期的贷款利息 (I,It)
?每月获得的上个月末现金余额的利息 (ICt)
月末的现金平衡（余额）公式：
t月现金余额 =（ t-1）月现金余额 +（ t-1）月现金余额利息 + t月份的现
金流 + t月份收到的贷款 -t月付长期贷款利息 - 付（ t-1） 月短期贷款
利息 - 归还（ t-1）月的短期贷款 -归还的长期贷款（仅对 2002年 1月）
经济管理学院2010年 5月 14日
---第 1 章 线性规划 ---
-78-
动态投资问题：
菲克投资公司要确定未来三年的投资策略。目前（时
刻 1）有 10万元资金可供投资使用，且有 A,B,C,D,E五个
项目可供投资选择，各个项目有关的投资现金流量在表中给
出。比如，在项目 B上的投资，在时刻 2需要 1元的现金流出
量，在时刻 3时有 0.5元的回报（现金流入），为了保证公司
投资的多元化，要求在任何一个项目上的投资最多不得超过
75,000元。没有投到项目上的资金可在资金市场上获得 8?的
存款利息。来自投资项目上的收益可直接用于再投资，例
如，在时刻 2来自 C项目上的现金流量 1.2元可直接投资于项
目 B。菲克公司不能借款，因此，在任何时刻可用于投资的
现金仅限于手中拥有的数额。试确定投资计划，能在时刻 4
时使手中的现金量最大。
经济管理学院2010年 5月 14日
---第 1 章 线性规划 ---
-79-
资金流量表
A B C D E时刻
1
2
3
4
-1.0 0 -1.0 -1.0 0
0.5 -1.0 1.2 0 0
1.0 0.5 0 0 -1.0
0 1.0 0 1.9 1.5
1 2 3 4
A C D
A C A B B D E
B E
经济管理学院2010年 5月 14日
---第 1 章 线性规划 ---
-80-
模型：
设 xij? 在时刻 i对 j项目的投资额，
Fi ? 时刻 i手中拥有的现金数额，
IFi ? 第 i时刻获得的利息
时刻 Fi IFi A B C D E
1
2
3
4
F1 0 -x11 0 -x13 -x14 0
F2 IF2 0.5x11 -x22 1.2x13 0 0
F3 IF3 1.0x11 0.5x22 0 0 -x35
F4 IF4 0 1.0x22 0 1.9x14 1.5x35
投资及收益情况分析表
经济管理学院2010年 5月 14日
---第 1 章 线性规划 ---
-82-
例：外汇交易
外汇交易市场日交易额常常超过 100亿美元。分别在现汇市场、期货市场上进
行。交易的形式有现汇、现汇期权等。我们现在着眼于现汇市场的讨论。
简单地说，现汇交易就是用一种货币购买一定数量另一种货币的协议。例如，
一个英国公司需要预付给一个日本供应商 1.5亿日元购货款，设英镑对日元的现钞
比价为 154.7733 (一英镑兑换 154.7733日元 )，那么这个英国公司可以利用现汇交易
市场以 969,159.41 (1.5亿 ?154.7743) 英镑购买 1.5亿日元。当日外汇交叉汇率样本如
表中所示。
假如英国公司终止了同日本供应商的合同订单，并想把 1.5亿日元兑换成英镑，
日元对英镑的现钞比价为 0.00645，则英国公司可用这 1.5亿日元买回 967,500 (=1.5
亿 ? 0.00645)英镑。注意到 967,500英镑低于原来的 969,159.41英镑，其差额是由买
卖差价引起的，代表公司的交易费用。偶然的情况也会发生市场价格脱离了一致
性的现象，这时候存在着套汇的机会。所谓的“套汇”是指存在着一组这样的交
易：经过一系列的交易后，手中的现钞额会大于初始的现钞额，如 1英镑 ?马克 ?
法郎 ?日元 ?英镑，若最后多于 1英镑，就说明有套汇的机会。
现问，表中给出的汇率是否存在这种套汇机会？试建立线性规划模型讨论该
问题。
经济管理学院2010年 5月 14日
---第 1 章 线性规划 ---
-83-
T O
F R O M
US,$ B,￡ F, F ra, D, M a r k Y, e n
US,$ ----- 0.6 390 0 5.3 712 0 1.5 712 0 98,890 1
B,￡ 1.5 648 0 ----- 8.4 304 0 2.4 590 0 154,77 33
F, F ra, 0.1 856 0 0.1 186 0 ----- 0.2 921 0 18,412 2
D, M a r k 0.6 361 0 0.4 063 0 3.4 233 0 ----- 62,940 0
Y, e n 0.0 101 1 0.0 064 5 0.0 543 1 0.0 158 8 -----
经济管理学院2010年 5月 14日
---第 1 章 线性规划 ---
-84-
建模思路
1.确定能够“产生”套汇的货币链
2.变量的设计
xj-----1美元中用来兑换第 j种货币的数量 ;
yj------换到的英镑中用于兑换第 j种货币的数量 ;
zj------换到的法郎中用于兑换第 j种货币的数量 ;
uj------换到的马克中用于兑换第 j种货币的数量 ;
vj------换到的日元中用于兑换第 j种货币的数量 ;
经济管理学院2010年 5月 14日
---第 1 章 线性规划 ---
-86-
问题：
1．如何看待模型的解？
2．若最优目标函数值为 1，是否说明无套汇机会？
为什么？
3．完整的模型该怎么建？你有什么好方法？
4．现实中这样的套汇链会存在吗？你如何分析？
经济管理学院2010年 5月 14日
---第 1 章 线性规划 ---
-87-
一, 问题的提出
实际问题中常常会碰到测定一组同类可比机构综合运作效率的问
题, 例如, 对学校, 医院, 银行, 法院, 连锁店等系统内各分支机构
部门运作效率的评价 。 由于测定指标的多样化, 所以需要有一种科学
的方法能够将各项指标进行综合归纳, 避免诸如评分类方法在操作过
程中过多的人为因素作用 。
DEA（ Data Envelopment Analysis） 方法采用的是一种相对评价技
术, 它能够对被测定部门的工作效果度量, 从而对系统中参评机构的
运作效率评定优劣 。
LP方法的一个应用 ── 数据包络分析（ DEA）
经济管理学院2010年 5月 14日
---第 1 章 线性规划 ---
-88-
一个评价问题示例
[例 ]：某城市有四家综合性医院：中心医院, 市立
医院, 省医院和医大附属医院, 现有他们的管理部门
要对该四家医院的工作效率进行考评, 测定哪家医院
效率更高？
经济管理学院2010年 5月 14日
---第 1 章 线性规划 ---
-89-
评价一个任何一个组织机构的工作效果, 通常都是经过对其, 输入
量, 和, 输出量, 的比较而衡量其运作效率的, 并且对, 好,,
,坏, 的认定必须能够确定出一个参照标准, 或者是借助于与同类机
构的比较分析才能实现, 否则, 评价无意义 。
DEA方法的建模思想就是通过对各机构的输入, 输出量的比较分析
后, 建立一个, 较理想, 的, 复合机构, （ 高效率 ） 作为评价的标
准, 将被评机构与该, 复合机构, 进行对比分析：设定, 复合机构,
的输出量不小于某一参评机构的输出量, 那么它的输入量与该参评机
构输入量的比较则可反映被评机构的效率情况 。 如果, 复合机构, 用
较小的输入量即可获得同样或者较多的输出, 则可认定该被评机构是
低效的, 而按此比值量的大小就可以对各个参评机构的运作效率进行
排序 。
二,建模思想
经济管理学院2010年 5月 14日
---第 1 章 线性规划 ---
-90-
Min Z=Ei （ i=1,·····,n） —— 对第 i机构评价
ST,∑ wi=1 —— 权重限制
∑ wi·Oit?Oit (t=1,······,T) —— 输出约束
∑ wi·Iis?Ei·Iis(s=1,····,S) —— 输入约束
wi? 0,Ei? 0 —— 变量符号限制
三,模型结构
i=1
n
n
i=1n
i=1
经济管理学院2010年 5月 14日
---第 1 章 线性规划 ---
-91-
机构 1
输入指标
机构 2
输入指标
机构 n
输入指标
w1
w2
wn
复合机构
机构 1
输出指标
机构 2
输出指标
机构 n
输出指标
w1
w2
wn
输入 输出
…… ……
DEA方法原理示意图
经济管理学院2010年 5月 14日
---第 1 章 线性规划 ---
-92-
式中,
Ei—— 效率指数,, 复合机构, 需要的输入为第 i机构输入的百分比；
wi—— 权系数, 第 i机构在, 复合机构, 中所占的权重；
Oit—— 第 i机构第 t项输出指标的数值；
Iis—— 第 i机构第 s项输入指标的数值；
T—— 输出指标总数量；
S—— 输入指标总数量；
n—— 参评机构总数 。
上述模型为 LP模型 。 若参评机构为 n个, 要计算每个机构的效率
指数, 则必须建立起 n个 LP模型 。 对第 i个机构而言, 若 Ei<1,则第 i个
机构为低效 。
经济管理学院2010年 5月 14日
---第 1 章 线性规划 ---
-93-
四、应用示例
1．输入、输出指标的设计
在评价时首先要选择输入、输出指标，通常应该选择数量化的指标，
且指标不宜过多，能够切实反映问题即可。本例中选择：
输入：
（ 1）医护人员数量（人）
（ 2）年经费数额（千元）
（ 3）床位总数（千床 ?日）
输出：
（ 1）就诊患者人数（万人 ?次 ）
（ 2）住院医疗人数（千人 ?日）
（ 3）培训护士人数（人）
（ 4）培训实习医生人数（人）
经济管理学院2010年 5月 14日
---第 1 章 线性规划 ---
-94-
输入、输出指标统计数值
输入指标统计值：
医护人员数量 285.20 162.30 275.70 210.40
年经费数额 123.80 128.70 348.50 154.10
床位总数 106.72 64.21 104.10 104.04
指标 中心医院 市立医院 省医院 医大附属医院
输出指标统计值：
指标 中心医院 市立医院 省医院 医大附属医院
就诊患者人数 48.14 34.62 36.72 33.16
住院医疗人数 43.10 27.11 45.98 56.46
培训护士人数 253 148 175 160
培训实习医生人数 41 27 23 84
经济管理学院2010年 5月 14日
---第 1 章 线性规划 ---
-95-
2．建立模型
按 DEA思想，首先应该构造一个“复合医院”，该“复合医院”
可以看作是从被评价医院种选择出“优质资产”（输入）“重组”而
成，所以具有最优的效率。因此，首先应确定各医院“资产”在“复
合医院”中的比重。比如，我们先来看省医院的运作效率模型：
设
w1—— 中心医院在复合医院中所占比重
w2—— 市立医院在复合医院中所占比重
w3—— 省医院在复合医院中所占比重
w4—— 医大附属医院在复合医院中所占比重
则其 DEA模型如下：
经济管理学院2010年 5月 14日
---第 1 章 线性规划 ---
-96-
省医院运作效率评价的 DEA模型
min E
st,w1+ w2+ w3+ w4=1
48.14w1+34.62w2+ 36.72w3 + 33.16w4?36.72
43.10w1+27.11w2 + 45.98w3+ 56.46w4?45.98
253w1+ 148w2+ 175w3+ 160w4?175
41w1+ 27w2+ 23w3+ 84w4?23
285.20w1+ 162.30w2+ 275.70w3+ 210.40w4?275.70E
123.80w1+ 128.70w2+ 348.50w3+ 154.10w4?348.50E
106.72w1+ 64.21 w2+ 104.10w3+ 104.04w4?104.10E
wi?0,(i=1,2,3,4),E?0
输出
输入
权数
变量符号
经济管理学院2010年 5月 14日
---第 1 章 线性规划 ---
-97-
最优解为：
w1=0.212,w2=0.261,w3=0.000,w4=0.527
E=0.905
结论分析,若 E=1，则“复合医院”需要与省医院同样多 的资源，
方能得到不低于省医院产出量的数值；
若 E<1，则“复合医院”可用较少的资源，获得不低于
省医院产出的数值，所以可判定省医院是低效的。
问题：若 E=1，是否可判定省医院一定是最优的？
经济管理学院2010年 5月 14日
---第 1 章 线性规划 ---
-98-
医护人员数量 213.7
年经费数额 141.05
床位总数 94.21
就诊患者人数 36.72
住院医疗人数 45.98
培训护士人数 176.6
培训实习医生 60
复合医院输入 输出
复合医院实际的输入, 输出指标构成示意图
---第 1 章 线性规划 ---
-1-
经济管理学院2010年 5月 14日
---第 1 章 线性规划 ---
-2-
第 一 章 线性规划
Linear Programming
经济管理学院2010年 5月 14日
---第 1 章 线性规划 ---
-3-
1.1 线性规划概述（ 1）
? 线性规划的广泛应用是计算机时代的产物。
? 1902年,Julius Farkas 发表论文，阐述有关线性规划问题。
? 1938年，英国人康德进行较详细研究。
? 1947年，美国学者 George Dantzig（丹茨格）发明了求解线性规划
的单纯形法（ 1951年发表），从而为线性规划的推广奠定了基础。
有人认为，求解线性规划的单纯形算法可与求解线性方程组的高
斯消元法相媲美。
经济管理学院2010年 5月 14日
---第 1 章 线性规划 ---
-4-
§ 1.1 线性规划概述（ 2）
? 线性规划的数学模型有三要素，从实际问题提炼成数学模
型时，首先寻找需求解的未知量 xj (j=1,…,n)，然后列举三
要素：
1,列写与自变量（未知量）有关的若干个线性约束条件（等
式或不等式）。
2,列写自变量 xj取值限制（ xj≥ 0,xj≤ 0或不限）。
3,列写关于自变量的线性目标函数值（极大值或极小值）。
? 其中，前两条称为可行条件，最后一条称为优化条件。符
合这三个条件的数学模型通常称为线性规划的一般型
（ general）。
经济管理学院2010年 5月 14日
---第 1 章 线性规划 ---
-5-
设备
产品
A B C D 单位利润
甲产品
乙产品
2
2
1
2
4
0
0
4
2
3
加工能力 12 8 16 12
1.1.1 问题的提出
例：某企业计划生产甲、乙两种产品，该两种产品均需经 A,B,C,D四
种不同设备上加工，按工艺资料规定，在各种不同设备上的加工时间及设
备加工能力、单位产品利润如表中所示。问,如何安排产品的生产计划,才能
使企业获利最大?
1.1 一般线性规划问题及数学模型 （ 3）
经济管理学院2010年 5月 14日
---第 1 章 线性规划 ---
-6-
建立模型：
设 产品的产量 甲 ?? x1件,乙 ?? x2件，则
Max z=2 x1+3 x2
2 x1+2 x2 ? 12
x1+2 x2 ? 8
4 x1 ? 16
4 x2 ?12
x1?0,x2 ?0
目标 (object),
限制条件
(subject to )：
经济管理学院2010年 5月 14日
---第 1 章 线性规划 ---
-7-
1.1.2 线性规划问题的一般数学模型
1.相关概念
（ 1）决策变量：指模型中要求解的未知量，简称变
量。
（ 2）目标函数：指模型中要达到的目标的数学表达
式。
（ 3）约束条件：指模型中的变量取值所需要满足的
一切限制条件。
此三项内容称为模型结构的三要素。
经济管理学院2010年 5月 14日
---第 1 章 线性规划 ---
-8-
2.线性规划模型的一般要求
（ 1）变量：取值为连续的、可控的量；
（ 2）目标函数：线性表达式；
（ 3）约束条件：线性的等式或者不等式。
经济管理学院2010年 5月 14日
---第 1 章 线性规划 ---
-9-
3, 线性规划问题的一般表示方法
（ 1）一般式：
max z=c1x1+c2x2+……… +cnxn
s.t,a11x1+a12x2+……… +a1nxn≤ b1
a21x1+a22x2+……… +a2nxn≤ b2
…… …… …… ……………
am1x1+am2x2+……… +amnxn≤ bm
x1,x2,………,xn≥ 0
s.t.---subject to
经济管理学院2010年 5月 14日
---第 1 章 线性规划 ---
-10-
n
(2) 和式,max z=? cjxjj=1
n
s.t,? aijxj≤bi （ i=1,2,……,m)
j=1
xj≥ 0 （ j=1,2,……,n)
其中,cj---------表示目标函数系数
aij---------表示约束条件系数
bi ---------表示约束右端项
经济管理学院2010年 5月 14日
---第 1 章 线性规划 ---
-11-
n
（ 4） 向量, max z=?cjxj
n j=1
s.t ? pjxj≤ b （ i=1,2,……,m）
j=1
xj≥ 0 （ j=1,2,……,n)
（ 3） 矩阵, max z=CX
s.t,AX≤ b
X≥ 0
经济管理学院2010年 5月 14日
---第 1 章 线性规划 ---
-12-
4,线性规划模型的标准形式
（ 1）变量：所有变量均 xj≥ 0
（ 2）目标函数：为取,max”形式
（ 3）约束条件：全部约束方程均为,=”连接
（ 4）约束右端项,bi≥ 0
非标准形式情况有
?变量,xj≤ 0,或 xj无约束
?目标函数,min
?约束条件：,≤,或,≥,
?约束右端项,bi<0
经济管理学院2010年 5月 14日
---第 1 章 线性规划 ---
-13-
LP的标准化：
（ 1）变量：若 xj?0，令 xj=-xj?,xj??0
若 xj无约束，则令 xj= xj?－ xj??,xj??0,xj???0
x
z
z
zmin
z ?= - z
z ? max
（ 3）约束方程：当, ?”时，引进松
弛（ slack）变量 +xs；
如 x1+x2?3 ? x1+x2+ x3=3
当, ?”时，引进剩余（ surplus）变
量 - xs；
如 x1+2x2? 4 ? x1+2x2－ x4=4
（ 2）目标函数：若求 min z，则 令 z ? = -z，等价于求 max （ z ?）
即有 min z= - max （ - z）
（ 4）约束右端项：当 bi < 0，则不等式
两端同乘（ - 1）
经济管理学院2010年 5月 14日
---第 1 章 线性规划 ---
-14-
例,将下述 LP模型标准化：
obj,Min z=2x1- x2+3x3
st,x1+2 x2+4x3 ? 6
3x1- 2x2+ x3 = 4
2x1- x2 - 3x3 ?5
x1 ?0,x2无符号限制,x3 ?0
解：设 z?= - z,x2= x2? - x2? ?,x2? ?0,x2? ? ?0,x3= - x3 ?,
x3??0, x4?0,x5?0,则有
obj,Max z?= -2x1 + (x2? - x2? ? ) + 3x3 ?
st,x1+2(x2? - x2? ? ) - 4x3 ?+x4=6
3x1 - 2(x2? - x2? ? ) - x3 ?=4
2x1 - (x2? - x2? ?) + 3x3 ?-x5=5
x1 ?0,x2? ?0,x2? ? ?0,x3 ??0,x4 ?0,x5 ?0
经济管理学院2010年 5月 14日
---第 1 章 线性规划 ---
-15-
复习思考题：
1,什么是模型结构的三要素？
2,什么是线性规划模型？能举出线性规划模型的例子
吗？
3,LP模型中目标函数系数、约束条件系数、约束右端
项的含义指的是什么？通常以什么符号表示？
4,LP模型的一般表示方法有几种形式？能否写出这些
形式？
5,什么是线性规划模型的标准形式？为何提出标准形
式？你能否把一个线性规划模型的非标准形式转化为标
准形式？
经济管理学院2010年 5月 14日
---第 1 章 线性规划 ---
-16-
1.1.3 简单线性规划模型的建立
步骤：
（ 2）具体构造模型：选择合适的决策变量、确定目标函
数的表达式、约束条件的表达式，分析各变量取值的符号
限制。
（ 1）分析问题：确定决策内容、要实现的目标以及所受
到的限制条件。
经济管理学院2010年 5月 14日
---第 1 章 线性规划 ---
-17-
例 1,某工厂在生产过程中需要使用浓度为 80%的硫酸
100 吨，而市面上只有浓度为 30%,45%,73%,85%，
92%的硫酸出售,每吨的价格分别为 400,700,1400、
1900和 2500元。 问：采用怎样的购买方案，才能使所需
总费用最小？
经济管理学院2010年 5月 14日
---第 1 章 线性规划 ---
-18-
模型：
设 第 j 种硫酸需购买 xj 吨，则
Min z=400x1+700x2+1400x3+1900x4+2500x5
st,x1+x2+x3+x4+x5=100
30?x1+45?x2+73?x3+85 ? x4+92?x5=100?80?
x1?0,x2?0,x3?0,x4?0,x5?0
经济管理学院2010年 5月 14日
---第 1 章 线性规划 ---
-19-
例 2：设有下面四个投资机会：
甲：在三年内，投资人应在每年年初投资，每年每元投资可获利 0.2
元，每年取息后可重新将本息用于投资。
乙：在三年内，投资人应在第一年年初投资，每两年每元投资可获
利 0.5元，两年后取息，取息后可重新将本息用于投资。这种投资最多
不得超过 20,000元。
丙：在三年内，投资人应在第二年年初投资，两年后每元投资可获
利 0.6元。这种投资最多不得超过 15,000元。
丁：在三年内，投资人应在第三年年初投资，一年后每元投资可获
利 0.4元。这种投资最多不得超过 10,000元。
假定在这三年为一期的投资中，每期的开始有 30,000元资金可供使
用，问：采取怎样的投资计划，才能在第三年年底获得最大收益？
经济管理学院2010年 5月 14日
---第 1 章 线性规划 ---
-20-
模型：
设 xij第 i 年投资于第 j 项目上的资金量，则
Max z=0.2 (x11+x21+ x31) + 0.5 x12 + 0.6 x2 3+ 0.4 x34
st,x11+ x12?30,000
x21+ x23?30,000? x12+ 0.2 x11
x31+ x34?30,000? x23 +0.2(x11+ x21)+0.5x12
x12 ?20,000
x23 ?15,000
x34?10,000
xij?0,(i=1,2,3; j=1,2,3,4)
x11
x12
x21
x23
x31
x341 2 3 4
30,000
经济管理学院2010年 5月 14日
---第 1 章 线性规划 ---
-21-
例 3,合理下料问题：
要制作 100套钢筋架子，每套含 2.9米,2.1米,1.5米
的钢筋各一根。已知原料长 7.4米，问：如何下料，使用
料最省？
长度 Ⅰ Ⅱ Ⅲ Ⅳ Ⅴ
2.9米
2.1米
1.5米
1 2 1
2 2 1
3 1 2 3
合计 (米 ) 7.4 7.3 7.2 7.1 6.6
料头 (米 ) 0 0.1 0.2 0.3 0.8
经济管理学院2010年 5月 14日
---第 1 章 线性规划 ---
-22-
模型,
设 xj ?? 为第 j种方案用料的数量,则
Min z=0x1+0.1x2+0.2x3+0.3x4+0.8x5
st,x1+2x2 + x4 =100
2x3+2x4+ x5=100
3x1+ x2+2x3 +3x5=100
xj?0,(j=1,2,---,5)
思考题：目标函数是否可以选取为 min z'=x1+x2+x3+x4+x5,为什
么？
经济管理学院2010年 5月 14日
---第 1 章 线性规划 ---
-23-
例 4,有 A,B两种产品，都需要经过前、后两到化学反应过程。每种产
品需要的反应时间及其可供使用的总时间如表示。
每生产一个单位产品 B的同时，会产生 2个单位的副产品 C，且不需外
加任何费用。副产品 C的一部分可以出售盈利，其余的只能加以销毁。
副产品 C每卖出一个单位可获利 3元，但是如果卖不出去，则每单位
需销毁费用 2元。预测表明，最多可售出 5个单位的副产品 C。
要求确定使利润最大的
生产计划。
产品
过程
A B
可利用
时间
前道过程 2 3 16
后道过程 3 4 24
单位利润 4 10
经济管理学院2010年 5月 14日
---第 1 章 线性规划 ---
-24-
模型：
设 产品的产量为 A? x1单位,B ? x2单位，已售出的产品 C ? x3 单
位，销毁的产品 C ? x4单位，则
Max z=4x1+10x2+3x3－ 2x4
st,2x1+3x2?16
3x1+4x2?24
2x2=x3+x4
x3? 5
xj?0,(j=1,2,3,4)
经济管理学院2010年 5月 14日
---第 1 章 线性规划 ---
-25-
例 5,一家昼夜服务的饭店,24小时中需要的服务员数如下表所
示。每个服务员每天连续工作 8小时，且在时段开始时上班。问：
最少需要多少名服务员？试建立该问题的线性规划模型。
起迄时间 服务员人数
2 - - - - 6 时 4
6 - - - 1 0 时 8
1 0 - - 1 4 时 10
1 4 - - 1 8 时 7
1 8 - - 2 2 时 12
2 2 - - - 2 时 4
经济管理学院2010年 5月 14日
---第 1 章 线性规划 ---
-26-
模型：
设 xj? 第 j时段开始上班工作的服务员数，则
Min z=x1+x2+x3+x4+x5+x6
st,x6+x1?4
x1+x2?8
x2+x3?10
x3+x4?7
x4+x5?12
x5+x6?4
xj?0,(j=1,2,---,6)
经济管理学院2010年 5月 14日
---第 1 章 线性规划 ---
-27-
建立线性规划模型要求：
（ 1）要求决策的量是连续的、可控的量，或者是可以简化为连
续取值的变量；
（ 2）要求所解决的问题的目标可用数值指标描述，并且能表示
成线性函数；
（ 3）存在着多种决策方案可供选择；
（ 4）决策所受到的限制条件可用线性的等式或者不等式表示。
经济管理学院2010年 5月 14日
---第 1 章 线性规划 ---
-28-
1.1.4 线性规划问题解的有关概念
设模型 n
max z=?cjxj
j=1
n
s.t,?aijxj=bi （ i=1,2,……,m)
j=1
xj≥ 0 （ j=1,2,……,n)
（ 1）可行解：满足所有约束方程和变量符号限制条件的一组变量的
取值。
（ 2）可行域：全部可行解的集合称为可行域。
（ 3）最优解：使目标函数达到最优值的可行解。
经济管理学院2010年 5月 14日
---第 1 章 线性规划 ---
-29-
（ 4） 基,设 A为线性规划模型约束条件系数矩阵（ m ? n,m<n），
而 B为其 m?m子矩阵，若 |B|≠ 0，则称 B为该线性规划模型的一个基。
（ 5） 基变量,基中每个向量所对应的变量称为基变量。
（ 6） 非基变量,模型中基变量之外的变量称为非基变量。
（ 7） 基本解（基解）,令模型中所有非基变量 X非基 =0后，由模型约束方
程组 n
?aijxj =bi (i=1,2,……,m)得到的一组解。
j=1
（ 8） 基本可行解（基可行解）,在基本解中，同时又是可行解的解称为
基本可行解。
（ 9） 可行基,对应于 基本可行解 的基称为可行基。
经济管理学院2010年 5月 14日
---第 1 章 线性规划 ---
-30-
Max z=2x1+3x2
st,x1+x2≤3
x1+2x2≤4
x1,x2≥0
Max z=2x1+3x2 +0x3 +0x4
st,x1+x2+x3=3
x1+2x2+x4=4
x1,x2,x3,x4≥0
A=
x1 x2 x3 x4
1 1 1 0
1 2 0 1
可行解,X=(0,0)T,X=(0,1)T,X=(1/2,1/3)T 等。
设 B= 1 0
0 1，令
，则 | B |=1≠0,
令 x1=x2 =0，则 x3 =3,x4=4,X=(0,0,3,4)T
例：
x3 x4 —— 基变量
令 B= 1 1
1 0
x1 x3
，则
令 x2=x4 =0，则 x3 =-1,x1=4,X=(4,0,-1,0)T
| B |=-1≠0,
—— 非基本可行解
—— 基本可行解
标准化
经济管理学院2010年 5月 14日
---第 1 章 线性规划 ---
-31-
复习思考题：
1,可行解和可行域有怎样的关系？
2,一个标准化 LP模型，最多可有多少个基？
3,基本解是如何定义的？怎样才能得到基本解？
4,可行解、基本解、基本可行解三者之间有什么关系？在 LP
模型中是否一定存在？
5,什么是可行基？
经济管理学院2010年 5月 14日
---第 1 章 线性规划 ---
-32-
1.2 线性规划问题的图解方法
* 利用作图方法求解。
例,max z=2x1+3x2
s.t 2x1+2x2?12 ----------①
x1+2x2? 8 ----------②
4x1?16 ----------③
4x2 ?12 ----------④
x1?0,x2?0
经济管理学院2010年 5月 14日
---第 1 章 线性规划 ---
-33-
x1
x2
2
2 4 6 8
4
6
0
①
②
④
③
Z=6Z=0
(4,2) Z
max
经济管理学院2010年 5月 14日
---第 1 章 线性规划 ---
-34-
A A
B
唯一解 无穷多解
无界解 无可行解
??
?
经济管理学院2010年 5月 14日
---第 1 章 线性规划 ---
-35-
步骤,（ 1）作平面直角坐标系，标上刻度；
（ 2）做出约束方程所在直线，确定可行域；
（ 3）做出一条目标函数等值线，判定优化方向；
（ 4）沿优化方向移动，确定与可行域相切的点，确定最优
解，并计算最优值。
讨论一：模型求解时，可得到如下几种解的状况：
（ 1）唯一最优解：只有一点为最优解点，简称唯一解；
（ 2）无穷多最优解：有许多点为最优解点，简称无穷多解；
（ 3）无界最优解：最优解取值无界，简称无界解 ；
（ 4）无可行解：无可行域，模型约束条件矛盾。
讨论二,LP模型求解思路：
（ 1）若 LP模型可行域存在，则为一凸形集合；
（ 2）若 LP模型最优解存在，则其应在其可行域顶点上找到；
（ 3）顶点与基本解、基本可行解的关系：
经济管理学院2010年 5月 14日
---第 1 章 线性规划 ---
-36-
复习思考题：
1,LP模型的可行域是否一定存在?
2,图解中如何去判断模型有唯一解、无穷多解、无界解
和无可行解？
3,LP模型的可行域的顶点与什么解具有对应关系？
4.你认为把所有的顶点都找出来，再通过比较目标函数
值大小的方式找出最优解，是否是最好的算法？为什么？
经济管理学院2010年 5月 14日
---第 1 章 线性规划 ---
-37-
1.3 单纯形法 的基本原理 （ Simplex Method）
1.3.1 两个概念：
（ 1）凸集：对于集合 C中任意两点连线上的点，若也在 C内，则称
C为凸集。
或者, 任给 X1?C,X2 ?C,X=?X1+ (1-?)X2 ? C (0<?<1)，则 C
为凸集。
凸集 非凸集
经济管理学院2010年 5月 14日
---第 1 章 线性规划 ---
-38-
（ 2）顶点：凸集中不成为任意两点连线上的点，称为凸集顶点。
或者,
设 C为凸集,对于 X?C，不存在任何 X1?C,X2 ?C,且 X1≠X 2，
使得 X=?X1+(1-?)X2?C,(0<?<1)，则 X为凸集顶点。
X
X
X
X
X
经济管理学院2010年 5月 14日
---第 1 章 线性规划 ---
-39-
定理 1,若线性 LP模型存在可行解，则可行域为凸集。
证明,设 max z=CX
st,AX=b
X?0
并设其可行域为 C，若 X1,X2为其可行解,且 X1≠X2,
则 X1?C,X2 ?C,即 AX1=b,AX2=b,X1?0,X2?0，
又 X为 X1,X2连线上一点，即 X=?X1+(1-?)X2?C,(0<?<1)，
∴ AX=?AX1+ (1-?)AX2 = ?b+ (1-?)b =b,(0<?<1)，且 X ?0，
∴ X ?C，
∴ C为凸集。
1.3.2 三个基本定理：
经济管理学院2010年 5月 14日
---第 1 章 线性规划 ---
-40-
引理,线性规划问题的可行解 X=(x1,x2,·····,xn)T 为基本可行解
的充要条件是 X的正分量所对应的系数列向量线性独立。
证：
（ 1）必要性,X基本可行解 ?X的正分量所对应的系数列向量线性独立
可设 X=(x1,x2,···,xk,0,0,···,0)T，若 X为基本可行解,显然，由 基
本可行解 定义可知 x1,x2,······,xk所对应 的系数列向量 P1,P2,······,Pk应该线
性独立。
（ 2）充分性,X的正分量所对应的系数列向量线性独立 ?X为基本可行解
若 A的秩为 m，则 X的正分量的个数 k?m；
当 k=m时，则 x1,x2,······,xk的系数列向量 P1,P2,······,Pk恰好构成基，
∴ X为基本可行解。
当 k<m时，则必定可再找出 m-k个列向量与 P1,P2,······,Pk一起构成基，
∴ X为基本可行解。
经济管理学院2010年 5月 14日
---第 1 章 线性规划 ---
-41-
证：用反证法 X非基本可行解 ?X非凸集顶点
（ 1）必要性, X非基本可行解 ?X非凸集顶点
不失一般性，设 X=(x1,x2,·····,xm,0,0,····,0)T，为非基本可行解，
∵ X为可行解，
∴ ?pjxj=b，
j=1
n
即 ?pjxj=b ······(1)
j=1
m
又 X是非基本可行解,∴ P1,P2,······,Pm线性相关，即有
?1P1+?2P2+······+?mPm=0,其中 ?1,?2,······,?m不全为 0，两端同乘 ?≠ 0，得
??1P1+??2P2+······+??mPm=0,······（ 2）
定理 2,线性规划模型的基本可行解对应其可行域的顶点。
经济管理学院2010年 5月 14日
---第 1 章 线性规划 ---
-42-
由 (1)+(2)得 (x1+ ??1)P1+ (x2+ ??2)P2+······+ (xm+ ??m)Pm=b
由 (1)-(2)得 (x1 -??1)P1+ (x2 -??2)P2+······+ (xm -??m)Pm=b
令 X1=(x1+ ??1,x2+ ??2,······,xm+ ??m,0,·····,0)T
X2=(x1-??1,x2-??2,······,xm-??m, 0,·····,0)T
取 ?充分小,使得 xj???j?0,则 X1,X2均为可行解，
但 X=0.5X1+(1-0.5)X2,∴ X是 X1,X2连线上的点，
∴ X非凸集顶点。
经济管理学院2010年 5月 14日
---第 1 章 线性规划 ---
-43-
（ 2）充分性,X非凸集顶点 ?X非基本可行解
设 X=(x1,x2,···,xr,0,0,···,0)T为 非凸集顶点，则必存在 Y,Z两点，使得
X=?Y+(1-?)Z,(0<?<1)，且 Y,Z为可行解
或者 xj=?yj+(1-?)zj (0<?<1)，（ j=1,2,···,n),yj?0,zj?0
∵ ?>0,1-?>0,当 xj=0,必有 yj=zj=0
∴ ?pjyj =
j=1
n
?pjyj=b ······(1)
j=1
r
?pjzj =
j=1
n
?pjzj=b ······(2)
j=1
r ? (yj-zj)pj=0j=1
r
,(1)-(2),得
即 (y1 - z1)P1+ (y2 - z2)P2+······+ (yr -zr)Pr=0
经济管理学院2010年 5月 14日
---第 1 章 线性规划 ---
-44-
∵ Y,Z为不同两点,∴ yj-zj不全为 0，
∴ P1,P2,······,Pr线性相关，
∴ X非基本可行解。
经济管理学院2010年 5月 14日
---第 1 章 线性规划 ---
-45-
3
4O
(3,3)
C (4,2)
6
6
2X1+2X2+X3=12
4X2+X5=12
4X1+X4=16
XA=(0,3,6,16,0)T
XO=(0,0,12,16,12)T
XB=(3,3,0,4,0)T
XC=(4,2,0,0,4)T
XD=(4,0,4,0,12)T
A
D
B
X1
X2
经济管理学院2010年 5月 14日
---第 1 章 线性规划 ---
-46-
z1=CX1=CX0-C?=zmax-C?, z2=CX2=CX0+C? =zmax+C?
∵ z0 = zmax ? z1, z0 = zmax ? z2,
∴ z1 = z2 = z0,即 X1, X2也为最优解，
若 X1,X2仍不是顶点，可如此递推，直至找出一个顶点为最优
解。
从而，必然会找到一个 基本可行解 为最优解。
定理 3,若线性规划模型有最优解，则一定存在一个基本可
行解为最优解 。
证,设 X0=(x10,x20,······,xn0)T 是线性规划模型的一个最优解，
z0=zmax=CX0
若 X0非基本可行解，即非顶点，只要取 ?充分小，
则必能找出 X1= X0-??0,X2 = X0+??0，即 X1, X2为可行解，
经济管理学院2010年 5月 14日
---第 1 章 线性规划 ---
-47-
单纯形法的计算步骤：
初始基本可行解
新的基本可行解
最优否？ STOPY
N
经济管理学院2010年 5月 14日
---第 1 章 线性规划 ---
-48-
1．初始基本可行解的确定：
设模型 n
max z=?cjxj
j=1
n
s.t,?aijxj?bi （ i=1,2,……,m) ????
j=1
xj?0 （ j=1,2,……,n)
n mmax z=?c
jxj + ? 0·xsij=1 I=1
n
s.t,?aijxj+xsi=bi （ i=1,2,……,m)
j=1
xj?0,xsi?0 （ j=1,2,……,n; i=1,2,……,m)
化标准形
∴ 初始基本可行解 X=(0,0,···,0,b1,b2,···,bm)T，
n-m个 0
经济管理学院2010年 5月 14日
---第 1 章 线性规划 ---
-49-
2．从一个基本可行解向另一个基本可行解转换
不失一般性，设基本可行解 X0=(x10,x20,······,xm0,0,···,0)T,
前 m个分量为正值，秩为 m，其系数矩阵为
P1 P2 …… P m Pm+1 …… P j…… P n b
1 0 …… 0 a 1,m+1 ····· a1j ····· a 1n b1
0 1 …… 0 a 2,m+1 ····· a2j ····· a 2n b2
0 0 …… 1 a m,m+1 ····· amj ····· a mn bm
…… ………… …… ………………
∴ ?pjxj0 =
j=1
n
?pixi0=b ······(1)
i=1
m
经济管理学院2010年 5月 14日
---第 1 章 线性规划 ---
-50-
又 P1 P2 …… P m为一个基，任意一个非基向量 Pj可以以该组向
量线性组合表示，即
Pj = a1j P1 + a2j P2 +···+ amj Pm,即 Pj =? aij pi,
移项，两端同乘 ?>0,有 ?(Pj-?aij pi )=0 ·········(2)
i=1
m
i=1
m
(1)+(2),?(xi 0-?aij)Pi + ? Pj =b，
取 ?充分小，使所有 xi 0 -?aij ?0，从而
i=1
m
X1 = (x1 0-?a1j,x2 0-?a2j,······,xm 0-?amj,0,······,?,···,0)T
也是可行解。
当取 ? = min — aij >0 = —,则 X1的前 m个分量至少有一个 xL1为 0。xi 0a
ij alj
xL 0
i
∴ P1,P2,······,PL-1,PL+1,······ Pm,Pj 线性无关。
经济管理学院2010年 5月 14日
---第 1 章 线性规划 ---
-51-
∴ X1 也为基本可行解。
3.最优解的判别
依题义 z0 =? c
jxj0 =?ci xi0i=1
m
j=1
n
z1 =? cjxj1 =?ci(xi 0-?aij)+ cj ?
i=1
m
j=1
n
=?cixi 0+?(cj - ?ciaij)= z0 +??j
i=1
m
i=1
m
经济管理学院2010年 5月 14日
---第 1 章 线性规划 ---
-52-
因 ?>0，所以有如下结论：
(1) 对所有 j，当 ?j?0,有 z1 ? z0,即 z0为最优值,X0为最优解；
(2) 对所有 j，当 ?j?0,但存在某个非基变量 ?k=0，则对此 Pk作
为新基向量得出的解 X1，应有 z1 = z0,故 z1 也 为最优值，
从而 X1为最优解，且为基本可行解，
∴ X0,X1 连线上所有的点均为最优解，因此该线性规划模型
具有无穷多解；
(3) 若存在某个 ?j ?0，但对应 aij?0，则因当 ???时，有 z1 ??，
∴ 该线性规划模型具有无界解。
经济管理学院2010年 5月 14日
---第 1 章 线性规划 ---
-53-
1.4 单纯形法的计算及示例
1.4.1 单纯形法几何解释 ---顶点寻优
例,max z=2x1+3x2 max z=2x1+3x2+0x3 +0x4
s.t x1+x2?3 标准化 s.t x1+x2+x3=3
x1+2x2 ? 4 ? x1+2x2+x4=4
x1?0,x2?0 xj?0,(j=1,2,3,4)
（ 1）初始基本可行解的选择,-----坐标原点处
令 x1 =x2 =0,由 x1+x2+x3=3
x1+2x2+x4=4
（ 2） 是否为最优解的判定,-----计算检验数
若 x1↑1,则 x3↓1,x4↓1,σ1= 2-（ 0?1+0 ?1） =2 σj
=△ z=cj-zj = cj-?ciaij, 称 σj为检验数。
x3=3 -(x1+x2)
x4=4 -(x1+2x2)
解得 X=( 0,0,3,4 )T
经济管理学院2010年 5月 14日
---第 1 章 线性规划 ---
-54-
若 x2↑1,则 x3↓1,x4↓2,σ2=3-(0?1+0?2)=3
**** 当所有检验数均有 σ j ? 0时，则为最优解。 ****
（ 3）找新的顶点（基本可行解）：
直观看,x2↑1,则 z ↑ 3,∴ 应找 A点，即增加 x2。
x2 可增加多少？需要保证 x3=3 -(x1+x2)?0
x4=4 -(x1+2x2)?0,
∴ x2 = min（ 3/1,4/2），从而
x3=1 -(x1 / 2 - x4/2）
x2=2 -(x1 / 2 + x4 / 2)
令 x1 = x4 =0，则新的基本可行解为 X=( 0,2,1,0)T
重复上述过程，直至所有检验数 σ j ? 0。
经济管理学院2010年 5月 14日
---第 1 章 线性规划 ---
-55-
继续迭代：
找新的顶点（基本可行解）：
若 x1↑1,则 z ↑ 1/2,∴ 应找 B点，即增加 x1。
x1 可增加多少？需要保证 x3=1 -(x1/2 - x4 /2)?0
x2=2 -(x1/2+x4/2)?0，
∴ x1 = min（ 2,4），从而
x1=2 -(2x3-x4)
x2=1 -(-x3+x4),
则新的基本可行解为 X=( 2,1,0,0)T
若 x1↑1,则 x3↓1/2,x2↓1/2,σ1= 2-（ 0?1/2+3?1/2） =1/2
若 x4↑1,则 x3↓-1/2,x2↓1/2,σ4= 0-（ 0?(-1/2)+3?1/2） =-3/2
σ3 = -1,σ4 = -1,zmax=7
经济管理学院2010年 5月 14日
---第 1 章 线性规划 ---
-56-
①
②
O C
A
B
X1
X2
(0,2)
(3,0)
(2,1)
3
4
经济管理学院2010年 5月 14日
---第 1 章 线性规划 ---
-57-
Cj →
x1 x2 x3 x4XB bCB
1 1 1 0
1 2 0 1
2 3 0 0
3
4
x3
x4
0
0
cj - zj 2 3 0 0
3/1=3
4/2= 2
1/2 0 1 -1/2
1/2 1 0 1/2
x3
x2 12
cj - zj 1/2 0 0 -3/2
0
3
2
4
1 0 2 -1
0 1 -1 1
x1
x2
2
1
cj - zj 0 0 -1 -1
2
3
1.4.2 单纯形法计算：
θi
经济管理学院2010年 5月 14日
---第 1 章 线性规划 ---
-58-
单纯形法计算过程总结：
（ 1）化标准形，列初始单纯形表；
（ 2）计算检验数,σj =△ z=cj-zj = cj- ?ciaij
（ 3）最优性判断,当 所有检验数均有 σ j ? 0时，则为最优解。否则
迭代求新的基本可行解。
（ 4）迭代：
入基变量：取 max{σ j ?0 }=σk→xk
出基变量：取 min {θi=bi/aik ? aik>0}=θl → x(l)
主元素,[alk]
新单纯表,pk=单位向量
注,当所有检验数 σ j ? 0时，若存在非基
变量检验数为 0时，则有无穷多解，否则只
有唯一最优解。
i=1
m
经济管理学院2010年 5月 14日
---第 1 章 线性规划 ---
-59-
例,min z=2x1+3x2 max z=-2x1-3x2+0x3
s.t x1+x2? 3 标准化 s.t x1+x2 -x3=3
x1+2x2 = 4 ? x1+2x2=4
x1?0,x2?0 xj?0,(j=1,2,3,4)
max z=-2x1-3x2+0x3 -Mx4-M x5
s.t x1+x2 -x3+ x4 =3
x1+2x2 +x5 =4
xj?0,(j=1,2,3,4,5)
引进人工变量，及 M—— 非常大正系数，模型转变为
这种处理方法称为大 M法，以下则可完全按单纯形法求解。
1．大 M法
1.5 单纯形法进一步讨论
经济管理学院2010年 5月 14日
---第 1 章 线性规划 ---
-60-
Cj →
x1 x2 x3 x4XB bCB
1 1 -1 1 0
1 2 0 0 1
-2 -3 0 -M -M
3
4
x4
x5
-M
-M
cj - zj -2+2M -3+3M -M 0
3/1=3
4/2= 2
1/2 0 -1 1 -1/2
1/2 1 0 0 1/2
x4
x2 12
cj - zj -1/2+M/2 0 -M 0 3/2-M/2
-M
-3 24
1 0 -2 2 -1
0 1 1 -1 1
x1
x2
2
1
cj - zj 0 0 -1 -1-M -1-M
-2
-3
θix
5
0
经济管理学院2010年 5月 14日
---第 1 章 线性规划 ---
-61-
说明：
当所有 ?j?0, 但存在人工变量 x人 ?0,则可以判定
该模型无可行解。
采用大 M法求解线性规划模型时，如果模型中各个
系数与 M的值非常接近时，若手工计算时，不会出现任
何问题。如果利用计算机程序求解，则大 M表现为一个
较大的数字，由于综合计算的影响，导致检验数出现
符号误差，引起判断错误，从而使大 M方法失效。在这
种情况下，可采用下面的两阶段法进行计算。
经济管理学院2010年 5月 14日
---第 1 章 线性规划 ---
-62-
2．两阶段法,
例, min z=2x1+3x2 max z=-2x1-3x2+0x3
s.t x1+x2? 3 标准化 s.t x1+x2 -x3=3
x1+2x2 = 4 ? x1+2x2=4
x1?0,x2?0 xj?0,(j=1,2,3,4)
obj,max z=-x4-x5
s.t x1+x2 -x3+ x4 =3
x1+2x2 +x5 =4
xj?0,(j=1,2,3,4,5)
(1)第一阶段，构造判断是否存在可行解的模型：
用单纯形法求解，若 zmax=0,表明该模型有可行解，则可进
入第二阶段，求原模型最优解。
经济管理学院2010年 5月 14日
---第 1 章 线性规划 ---
-63-
Cj →
x1 x2 x3 x4XB bCB
1 1 -1 1 0
1 2 0 0 1
0 0 0 -1 -1
3
4
x4
x5-1 -1
cj - zj 2 3 -1 0
3/1=3
4/2= 2
1/2 0 -1 1 -1/2
1/2 1 0 0 1/2
x4
x2 12
cj - zj 1/2 0 -1 0 -3/2
-1
0
2
4
1 0 -2 2 -1
0 1 1 -1 1
x1
x2
2
1
cj - zj 0 0 0 -1 -1
0
0
θix
5
0
经济管理学院2010年 5月 14日
---第 1 章 线性规划 ---
-64-
(2) 第二阶段，将原目标函数引入最终单纯形表，继续迭代：
max z=-2x1-3x2+0x3
Cj →
x1 x2 x3XB bCB
1 0 -2
0 1 1
-2 -3 0
2
1
x1
x2-2-3
cj - zj 0 0 -1
经济管理学院2010年 5月 14日
---第 1 章 线性规划 ---
-65-
1.4.3 程序求解
（ 1）用 LINDO软件求解
（ 2）用 EXCEL工具求解
这是一个 DOS程序，使用 BASIC语言编写。运行时采
用命令格式，以文本形式输入。
使用 EXCEL中数据处理工具 ——— 规划求解。
经济管理学院2010年 5月 14日
---第 1 章 线性规划 ---
-66-
1.6 改进单纯形法
单纯形法迭代过程可用矩阵变换描述如下,设
max z=CX
st AX?b
X?0
分解 max z=CBXB+ CNXN+0XS
st BXB+ NXN+IXS=b
XB,XN,,XS?0
约束方程两端同乘 B-1,则可得如下表达式：
式中,B—— 最终表中基对应的矩阵，
N—— 初始表与最终表中均为非基对应的矩阵，
I—— 单位矩阵
A=[ B N ]
max z=CBXB+ CNXN+0XS
st B-1 BXB+ B-1 NXN+ B-1 XS= B-1 b
XB,XN,,XS?0 —— 对应最终单纯形表的模型
经济管理学院2010年 5月 14日
---第 1 章 线性规划 ---
-67-
用单纯形表表示如下：
XS = b B N I
XB = b′ I N′ B-1
初始表 XB XN XS
cj - zj 0,······,0 ?N ?S
最终表 XB XN XS
cj - zj ?B ?N 0,······,0
表中，
b′=B-1b
N′ =B-1N
或者 Pj′ =B-1Pj
?N′= CN-CB B-1 N
或者 ?j′=Cj-CBB-1 Pj
?S′= -CB B-1
········
经济管理学院2010年 5月 14日
---第 1 章 线性规划 ---
-68-
⑴ 化标准形,B-1 new =I,XB =b，
⑵ 求检验数,?N = CN-CB B-1 new N,?S = -CB B-1 new
⑶ 最优性判别：
① 所有 ?? 0,X人 ≠0,无可行解；
② 所有 ?? 0,X人 =0，存在 ?N =0，无穷多解；
③ 所有 ?? 0,X人 =0，不存在 ?N =0，唯一解；
④ 否则 (存在 ?>0)，转⑷,
⑷ 取 ?max ? xk, 为换入变量，
计算 Pk′= B-1 new Pk，若 ? Pk′??0 ?无界解,
否则，计算 ?i =? bi /aik |aik >0?,取 ?min ?xl为换出变量，
⑸ 令
改进单纯形法计算步骤：
经济管理学院2010年 5月 14日
---第 1 章 线性规划 ---
-69-
D=
1 ······ - a1k / aLk ····· 0
0 ······ 1/ aLk ····· 0
0 ······ - amk / aLk ····· 1
···
·
··
···
·
··
···
·
··
xL
计算 B-1 new =D B-1old,
b′ = B-1 newb
转⑵。
注,D矩阵为单位矩阵中出基变量所在单位向量以上述列
向量代换。
实例演算如下：
经济管理学院2010年 5月 14日
---第 1 章 线性规划 ---
-70-
例,max z=2x1+3x2 max z=2x1+3x2+0x3 +0x4
s.t x1+x2?3 标准化 s.t x1+x2+x3=3
x1+2x2 ? 4 ? x1+2x2+x4=4
x1?0,x2?0 xj?0,(j=1,2,3,4)
x1 x2 x3 x4 b
1 1 1 0 3
1 2 0 1 4
⑴ 初始解：
B-1 new=I,XB=(x3,,x4)T=(3,4)T,?N=(?1,?2)=(2,3)，
计算 P2′ = B-1 new P2=(1,2)T，
∴ 换入变量,?max ? x2,
换出变量,?i =? bi /ai2 |ai2 >0? = (3,2),?min ? x4,
经济管理学院2010年 5月 14日
---第 1 章 线性规划 ---
-71-
⑵ 第二次计算：
1 -1/2
0 1/2
D=, B-1 new =D B-1old = 1 -1/2
0 1/2
1 0
0 1
1 -1/2
0 1/2=
XB=(x3,,x2)T= B-1 new b =(1,2)T,
?N=(?1,?4)= CN -CB B-1 N =(2,0)-(0,3) 1 -1/2
0 1/2
1 0
1 1
=(1/2,-3/2),
∴ 换入变量,?max ?x1,
计算 P1′ = B-1 new P1=(1/2,1/2)T，
∴ 换出变量,?i =? bi /ai1 |ai1 >0? = (2,4),?min ? x3,
经济管理学院2010年 5月 14日
---第 1 章 线性规划 ---
-72-
2 0
-1 1
D=, B-1 new =D B-1old = 2 0
-1 1
2 -1
-1 1
1 -1/2
0 1/2 =
XB=(x1,x2)T= B-1 new b =(2,1)T,
?N=(?3,?4)= CN -CB B-1 N =(0,0)-(2,3) 2 -1
-1 1
1 0
0 1
=(-1,-1),
⑶ 第三次计算：
所有 ?? 0，
故为最优解，
XB=(x1,x2)T=(2,1)T,
z max =7
经济管理学院2010年 5月 14日
---第 1 章 线性规划 ---
-73-
例 用单纯形法解目标规划问题时，有如下二个单纯
形表，试把表中数字补全。
Cj →
x1 x2 x3 x4XB bCB
1 0
0 1
0 0
3 x3 x
4
0
0
cj - zj
CB XB b x1 x2 x3 x4
2 -1
-1
1
x1
x2 1
cj - zj -1 -1
2
3
···
经济管理学院2010年 5月 14日
---第 1 章 线性规划 ---
-74-
?S=(-1,-1)=(?3,?4)= CS-CB B-1 = -(c1,c2) 2 -1-1 1 1 00 1
=-(2c1-c2,-c1+c2)
c1=2
c2=3∴ 又 b
′ = B-1 b，
b1′
1
2 -1
-1 1
3
b2
6-b2
-3+b2= =
b1′=2
b2 =4∴
2 -1
-1 1
1 0
0 1 =
a11 a12
a21 a22
1 0
0 1 =
2a11 -a21 -2a12 -a22
-a11 +a21 -a12 +a22?
∴ a11 =1,a12 =1,a21 =1,a22 =2
解：
经济管理学院2010年 5月 14日
---第 1 章 线性规划 ---
-75-
1.7 线性规划问题的应用案例
例一, 泰和玩具公司,预计 2001年里公司的月现金流量如表中所示。
负的现金流量表示流出的现金超过流入的现金。为应付它的债务，公司
需要在年内提早借款。该公司可有两种借款方式：（ 1）可在 1月份贷到
所需要的一年期的长期贷款，从 2001年 2月份开始,每月需为这笔贷款支
付 1%的利息,贷款本金必须在 2002年 1月初归还。（ 2）公司还可获得短
期的银行贷款，月利率为 1.5%，公司需在下一个月里归还上一个月初的
短期贷款本金与利息。所有的短期贷款必须在 2002年 1月初归还。在每
月末，现金余额可获得 0.4%的利息。问：如何制定借款计划，可使公司
在 2002年 1月初获得最大的现金余额？
月份 1 月 2 月 3 月 4 月 5 月 6 月 7 月 8 月 9 月 10 月 11 月 12 月
现金流量
( 千元 )
-1 2 -1 0 -8 -1 0 -4 5 -7 -2 15 12 -7 45
经济管理学院2010年 5月 14日
---第 1 章 线性规划 ---
-76-
应解决的问题,
?长期贷款的数量 (L)
?每月短期贷款的数量 (St)
?每月月末的现金平衡（余额） (Cbt)
?期间最后的现金平衡 (2002年初现金余额 ) (Cb13)
?每月所付的长期与短期的贷款利息 (I,It)
?每月获得的上个月末现金余额的利息 (ICt)
月末的现金平衡（余额）公式：
t月现金余额 =（ t-1）月现金余额 +（ t-1）月现金余额利息 + t月份的现
金流 + t月份收到的贷款 -t月付长期贷款利息 - 付（ t-1） 月短期贷款
利息 - 归还（ t-1）月的短期贷款 -归还的长期贷款（仅对 2002年 1月）
经济管理学院2010年 5月 14日
---第 1 章 线性规划 ---
-78-
动态投资问题：
菲克投资公司要确定未来三年的投资策略。目前（时
刻 1）有 10万元资金可供投资使用，且有 A,B,C,D,E五个
项目可供投资选择，各个项目有关的投资现金流量在表中给
出。比如，在项目 B上的投资，在时刻 2需要 1元的现金流出
量，在时刻 3时有 0.5元的回报（现金流入），为了保证公司
投资的多元化，要求在任何一个项目上的投资最多不得超过
75,000元。没有投到项目上的资金可在资金市场上获得 8?的
存款利息。来自投资项目上的收益可直接用于再投资，例
如，在时刻 2来自 C项目上的现金流量 1.2元可直接投资于项
目 B。菲克公司不能借款，因此，在任何时刻可用于投资的
现金仅限于手中拥有的数额。试确定投资计划，能在时刻 4
时使手中的现金量最大。
经济管理学院2010年 5月 14日
---第 1 章 线性规划 ---
-79-
资金流量表
A B C D E时刻
1
2
3
4
-1.0 0 -1.0 -1.0 0
0.5 -1.0 1.2 0 0
1.0 0.5 0 0 -1.0
0 1.0 0 1.9 1.5
1 2 3 4
A C D
A C A B B D E
B E
经济管理学院2010年 5月 14日
---第 1 章 线性规划 ---
-80-
模型：
设 xij? 在时刻 i对 j项目的投资额，
Fi ? 时刻 i手中拥有的现金数额，
IFi ? 第 i时刻获得的利息
时刻 Fi IFi A B C D E
1
2
3
4
F1 0 -x11 0 -x13 -x14 0
F2 IF2 0.5x11 -x22 1.2x13 0 0
F3 IF3 1.0x11 0.5x22 0 0 -x35
F4 IF4 0 1.0x22 0 1.9x14 1.5x35
投资及收益情况分析表
经济管理学院2010年 5月 14日
---第 1 章 线性规划 ---
-82-
例：外汇交易
外汇交易市场日交易额常常超过 100亿美元。分别在现汇市场、期货市场上进
行。交易的形式有现汇、现汇期权等。我们现在着眼于现汇市场的讨论。
简单地说，现汇交易就是用一种货币购买一定数量另一种货币的协议。例如，
一个英国公司需要预付给一个日本供应商 1.5亿日元购货款，设英镑对日元的现钞
比价为 154.7733 (一英镑兑换 154.7733日元 )，那么这个英国公司可以利用现汇交易
市场以 969,159.41 (1.5亿 ?154.7743) 英镑购买 1.5亿日元。当日外汇交叉汇率样本如
表中所示。
假如英国公司终止了同日本供应商的合同订单，并想把 1.5亿日元兑换成英镑，
日元对英镑的现钞比价为 0.00645，则英国公司可用这 1.5亿日元买回 967,500 (=1.5
亿 ? 0.00645)英镑。注意到 967,500英镑低于原来的 969,159.41英镑，其差额是由买
卖差价引起的，代表公司的交易费用。偶然的情况也会发生市场价格脱离了一致
性的现象，这时候存在着套汇的机会。所谓的“套汇”是指存在着一组这样的交
易：经过一系列的交易后，手中的现钞额会大于初始的现钞额，如 1英镑 ?马克 ?
法郎 ?日元 ?英镑，若最后多于 1英镑，就说明有套汇的机会。
现问，表中给出的汇率是否存在这种套汇机会？试建立线性规划模型讨论该
问题。
经济管理学院2010年 5月 14日
---第 1 章 线性规划 ---
-83-
T O
F R O M
US,$ B,￡ F, F ra, D, M a r k Y, e n
US,$ ----- 0.6 390 0 5.3 712 0 1.5 712 0 98,890 1
B,￡ 1.5 648 0 ----- 8.4 304 0 2.4 590 0 154,77 33
F, F ra, 0.1 856 0 0.1 186 0 ----- 0.2 921 0 18,412 2
D, M a r k 0.6 361 0 0.4 063 0 3.4 233 0 ----- 62,940 0
Y, e n 0.0 101 1 0.0 064 5 0.0 543 1 0.0 158 8 -----
经济管理学院2010年 5月 14日
---第 1 章 线性规划 ---
-84-
建模思路
1.确定能够“产生”套汇的货币链
2.变量的设计
xj-----1美元中用来兑换第 j种货币的数量 ;
yj------换到的英镑中用于兑换第 j种货币的数量 ;
zj------换到的法郎中用于兑换第 j种货币的数量 ;
uj------换到的马克中用于兑换第 j种货币的数量 ;
vj------换到的日元中用于兑换第 j种货币的数量 ;
经济管理学院2010年 5月 14日
---第 1 章 线性规划 ---
-86-
问题：
1．如何看待模型的解？
2．若最优目标函数值为 1，是否说明无套汇机会？
为什么？
3．完整的模型该怎么建？你有什么好方法？
4．现实中这样的套汇链会存在吗？你如何分析？
经济管理学院2010年 5月 14日
---第 1 章 线性规划 ---
-87-
一, 问题的提出
实际问题中常常会碰到测定一组同类可比机构综合运作效率的问
题, 例如, 对学校, 医院, 银行, 法院, 连锁店等系统内各分支机构
部门运作效率的评价 。 由于测定指标的多样化, 所以需要有一种科学
的方法能够将各项指标进行综合归纳, 避免诸如评分类方法在操作过
程中过多的人为因素作用 。
DEA（ Data Envelopment Analysis） 方法采用的是一种相对评价技
术, 它能够对被测定部门的工作效果度量, 从而对系统中参评机构的
运作效率评定优劣 。
LP方法的一个应用 ── 数据包络分析（ DEA）
经济管理学院2010年 5月 14日
---第 1 章 线性规划 ---
-88-
一个评价问题示例
[例 ]：某城市有四家综合性医院：中心医院, 市立
医院, 省医院和医大附属医院, 现有他们的管理部门
要对该四家医院的工作效率进行考评, 测定哪家医院
效率更高？
经济管理学院2010年 5月 14日
---第 1 章 线性规划 ---
-89-
评价一个任何一个组织机构的工作效果, 通常都是经过对其, 输入
量, 和, 输出量, 的比较而衡量其运作效率的, 并且对, 好,,
,坏, 的认定必须能够确定出一个参照标准, 或者是借助于与同类机
构的比较分析才能实现, 否则, 评价无意义 。
DEA方法的建模思想就是通过对各机构的输入, 输出量的比较分析
后, 建立一个, 较理想, 的, 复合机构, （ 高效率 ） 作为评价的标
准, 将被评机构与该, 复合机构, 进行对比分析：设定, 复合机构,
的输出量不小于某一参评机构的输出量, 那么它的输入量与该参评机
构输入量的比较则可反映被评机构的效率情况 。 如果, 复合机构, 用
较小的输入量即可获得同样或者较多的输出, 则可认定该被评机构是
低效的, 而按此比值量的大小就可以对各个参评机构的运作效率进行
排序 。
二,建模思想
经济管理学院2010年 5月 14日
---第 1 章 线性规划 ---
-90-
Min Z=Ei （ i=1,·····,n） —— 对第 i机构评价
ST,∑ wi=1 —— 权重限制
∑ wi·Oit?Oit (t=1,······,T) —— 输出约束
∑ wi·Iis?Ei·Iis(s=1,····,S) —— 输入约束
wi? 0,Ei? 0 —— 变量符号限制
三,模型结构
i=1
n
n
i=1n
i=1
经济管理学院2010年 5月 14日
---第 1 章 线性规划 ---
-91-
机构 1
输入指标
机构 2
输入指标
机构 n
输入指标
w1
w2
wn
复合机构
机构 1
输出指标
机构 2
输出指标
机构 n
输出指标
w1
w2
wn
输入 输出
…… ……
DEA方法原理示意图
经济管理学院2010年 5月 14日
---第 1 章 线性规划 ---
-92-
式中,
Ei—— 效率指数,, 复合机构, 需要的输入为第 i机构输入的百分比；
wi—— 权系数, 第 i机构在, 复合机构, 中所占的权重；
Oit—— 第 i机构第 t项输出指标的数值；
Iis—— 第 i机构第 s项输入指标的数值；
T—— 输出指标总数量；
S—— 输入指标总数量；
n—— 参评机构总数 。
上述模型为 LP模型 。 若参评机构为 n个, 要计算每个机构的效率
指数, 则必须建立起 n个 LP模型 。 对第 i个机构而言, 若 Ei<1,则第 i个
机构为低效 。
经济管理学院2010年 5月 14日
---第 1 章 线性规划 ---
-93-
四、应用示例
1．输入、输出指标的设计
在评价时首先要选择输入、输出指标，通常应该选择数量化的指标，
且指标不宜过多，能够切实反映问题即可。本例中选择：
输入：
（ 1）医护人员数量（人）
（ 2）年经费数额（千元）
（ 3）床位总数（千床 ?日）
输出：
（ 1）就诊患者人数（万人 ?次 ）
（ 2）住院医疗人数（千人 ?日）
（ 3）培训护士人数（人）
（ 4）培训实习医生人数（人）
经济管理学院2010年 5月 14日
---第 1 章 线性规划 ---
-94-
输入、输出指标统计数值
输入指标统计值：
医护人员数量 285.20 162.30 275.70 210.40
年经费数额 123.80 128.70 348.50 154.10
床位总数 106.72 64.21 104.10 104.04
指标 中心医院 市立医院 省医院 医大附属医院
输出指标统计值：
指标 中心医院 市立医院 省医院 医大附属医院
就诊患者人数 48.14 34.62 36.72 33.16
住院医疗人数 43.10 27.11 45.98 56.46
培训护士人数 253 148 175 160
培训实习医生人数 41 27 23 84
经济管理学院2010年 5月 14日
---第 1 章 线性规划 ---
-95-
2．建立模型
按 DEA思想，首先应该构造一个“复合医院”，该“复合医院”
可以看作是从被评价医院种选择出“优质资产”（输入）“重组”而
成，所以具有最优的效率。因此，首先应确定各医院“资产”在“复
合医院”中的比重。比如，我们先来看省医院的运作效率模型：
设
w1—— 中心医院在复合医院中所占比重
w2—— 市立医院在复合医院中所占比重
w3—— 省医院在复合医院中所占比重
w4—— 医大附属医院在复合医院中所占比重
则其 DEA模型如下：
经济管理学院2010年 5月 14日
---第 1 章 线性规划 ---
-96-
省医院运作效率评价的 DEA模型
min E
st,w1+ w2+ w3+ w4=1
48.14w1+34.62w2+ 36.72w3 + 33.16w4?36.72
43.10w1+27.11w2 + 45.98w3+ 56.46w4?45.98
253w1+ 148w2+ 175w3+ 160w4?175
41w1+ 27w2+ 23w3+ 84w4?23
285.20w1+ 162.30w2+ 275.70w3+ 210.40w4?275.70E
123.80w1+ 128.70w2+ 348.50w3+ 154.10w4?348.50E
106.72w1+ 64.21 w2+ 104.10w3+ 104.04w4?104.10E
wi?0,(i=1,2,3,4),E?0
输出
输入
权数
变量符号
经济管理学院2010年 5月 14日
---第 1 章 线性规划 ---
-97-
最优解为：
w1=0.212,w2=0.261,w3=0.000,w4=0.527
E=0.905
结论分析,若 E=1，则“复合医院”需要与省医院同样多 的资源，
方能得到不低于省医院产出量的数值；
若 E<1，则“复合医院”可用较少的资源，获得不低于
省医院产出的数值，所以可判定省医院是低效的。
问题：若 E=1，是否可判定省医院一定是最优的？
经济管理学院2010年 5月 14日
---第 1 章 线性规划 ---
-98-
医护人员数量 213.7
年经费数额 141.05
床位总数 94.21
就诊患者人数 36.72
住院医疗人数 45.98
培训护士人数 176.6
培训实习医生 60
复合医院输入 输出
复合医院实际的输入, 输出指标构成示意图
