管理运筹学谢家平 博士 副教授研究领域,系统建模与优化、生产与运作管理、物流与供应链管理讲授课程,管理运筹学、管理系统工程、生产运作管理、
供应链管理、国际物流管理、企业资源计划单 位,上海财经大学 国际工商管理学院 供应链管理研究中心
E-mail,jiaping_xie@sina.com.cn
电 话,55036936(H) 65903541(O)
上海财经大学国际工商管理学院
SHUFE
2
第一讲 线性规划第一章 线性规划的数学模型第一节 线性规划一般模型第二节 线性规划的图解法第三节 线性规划的标准型第四节 线性规划解的概念第二章 线性规划的单纯形法第一节 单纯形法原理第二节 表格单纯形法第三节 人工变量问题第四节 单纯形法补遗第三章 线性规划的对偶理论第四章 线性规划灵敏性分析上海财经大学国际工商管理学院
SHUFE
3
第一章 线性规划的数学模型
线性规划 Linear Programming LP
规划论中的静态规划
解决有限资源的最佳分配问题
求解方法：
图解法
单纯形解法上海财经大学国际工商管理学院
SHUFE
4
第一章 线性规划的数学模型第一节 线性规划一般模型第二节 线性规划的图解法第三节 线性规划的标准型第四节 线性规划解的概念上海财经大学国际工商管理学院
SHUFE
5
第一节 线性规划一般模型一、线性规划问题的三个要素
决策问题待定的量值称为决策变量 。
决策变量的取值要求非负 。
约束条件
任何问题都是限定在一定的条件下求解,把各种限制条件表示为一组等式或不等式,称之为约束条件 。
约束条件是决策方案可行的保障 。
LP的约束条件,都是决策变量的线性函数 。
目标函数
衡量决策方案优劣的准则,如时间最省,利润最大,成本最低 。
目标函数是决策变量的线性函数 。
有的目标要实现极大,有的则要求极小 。
上海财经大学国际工商管理学院
SHUFE
6
第一节 线性规划一般模型
例 1,生产计划问题某厂生产甲乙两种产品,各自的零部件分别在 A,B车间生产,最后都需在 C车间装配,相关数据如表所示：
问如何安排甲、乙两产品的产量，使利润为最大。
二、线性规划模型的构建产品车间工时单耗甲 乙生产能力
A
B
C
1 0
0 2
3 4
8
12
36
单位产品获利 3 5
上海财经大学国际工商管理学院
SHUFE
7
第一节 线性规划一般模型
(1)决策变量 。 要决策的问题是甲,乙两种产品的产量,因此有两个决策变量：设 x1为甲产品产量,x2为乙产品产量 。
(2)约束条件 。 生产这两种产品受到现有生产能力的制约,
用量不能突破 。
生产单位甲产品的零部件需耗用 A车间的生产能力 1工时,
生产单位乙产品不需耗用 A车间的生产能力,
A车间的能力总量为 8工时,则 A车间能力约束条件表述为
x1 ≤8
同理,B和 C车间能力约束条件为
2x2 ≤12
3x1 +4 x2 ≤36
建立模型上海财经大学国际工商管理学院
SHUFE
8
第一节 线性规划一般模型
(3)目标函数 。 目标是利润最大化，用 Z表示利润，则
maxZ= 3x1 +5 x2
(4)非负约束 。 甲乙产品的产量不应是负数,否则没有实际意义,这个要求表述为
x1 ≥0,x2 ≥0
综上所述，该问题的数学模型表示为
maxZ= 3x1 +5 x2
x1 ≤8
2x2 ≤12
3x1 +4 x2 ≤36
x1≥0,x2≥0
S.t.
上海财经大学国际工商管理学院
SHUFE
9
第一节 线性规划一般模型某名牌饮料在国内有三个生产厂,分布在城市 A1、
A2,A3,其一级承销商有 4个,分布在城市 B1,B2,B3、
B4,已知各厂的产量,各承销商的销售量及从 Ai到 Bj
的每吨饮料运费为 Cij,为发挥集团优势,公司要统一筹划运销问题,求运费最小的调运方案 。
例 2,运输问题销地产地 B1 B2 B3 B4 产量
A1
A2
A3
6 3 2 5
7 5 8 4
3 2 9 7
5
2
3
销量 2 3 1 4
上海财经大学国际工商管理学院
SHUFE
10
第一节 线性规划一般模型
(1)决策变量 。 设从 Ai到 Bj的运输量为 xij，
(2)目标函数 。 运费最小的目标函数为
minZ=6x11+3x12+2x13+5x14+7x21+5x22+8x23+4x24+3x31+2x32+9x33+7x34
(3)约束条件 。 产量之和等于销量之和,故要满足：
供应平衡条件 x11+x12+x13+x14=5x
21+x22+x23+x24=2
x31+x32+x33+x34 =3
销售平衡条件 x11+x21+x31=2
x12+x22+x32=3
x13+x23+x33=1
x14+x24+x34=4
非负性约束 xij≥0 (i=1,2,3； j=1,2,3,4)
上海财经大学国际工商管理学院
SHUFE
11
第一节 线性规划一般模型
用一组非负决策变量表示一个决策问题，
存在一定的等式或不等式的线性约束条件，
有一个希望达到的目标，可表示成决策变量的线性函数。可能是最大化，也可能是最小化。
线性规划一般模型的代数式 为：
三、线性规划的一般模型
max(min)Z=c1x1+c2x2+…+c nxn
a11x1+a12x2+…+a 1nxn ≤(≥,＝ )b1
a21x1+a22x2+…+a 2nxn ≤(≥,＝ )b2
… … … … …
am1x1+am2x2+…+a mnxn≤(≥,＝ )bm
x1,x2,…,x n ≥(≤)0
上海财经大学国际工商管理学院
SHUFE
12
第二节 线性规划的图解法
图解法即是用图示的方法来求解线性规划问题。
一个二维的线性规划问题，可以在平面图上求解，
三维的线性规划则要在立体图上求解，这就比较麻烦，而维数再高以后就不能图示了。
一、图解法的基本步骤上海财经大学国际工商管理学院
SHUFE
13
第二节 线性规划的图解法
1,可行域的确定
例 1的数学模型为
maxZ= 3x1 +5 x2
x1 ≤8
2x2 ≤12
3x1 +4 x2 ≤36
x1≥0,x2≥0
S.t.
x1 =8
2x2 =12
3x1 +4 x2 =36
x1
x2
4 8 12
3
6
9
0 A
B
C(4,6)D
五边形 OABCD内 (含边界 )的任意一点 (x1,x2) 都是满足所有约束条件的一个解，称之可行解 。
满足所有约束条件的解的集合，称之为可行域。即所有约束条件共同围城的区域。
上海财经大学国际工商管理学院
SHUFE
14
第二节 线性规划的图解法
2,最优解的确定
Z=30 Z=42
Z=15
目标函数 Z= 3x1 +5 x2 代表以 Z为参数的一族平行线。
x1 =8
2x2 =12
3x1 +4 x2 =36
x1
x2
4 8 12
3
6
9
0 A
B
C(4,6)D
等值线：位于同一直线上的点的目标函数值相同。
最优解：可行解中使目标函数最优 (极大或极小 )的解上海财经大学国际工商管理学院
SHUFE
15
第二节 线性规划的图解法
由线性不等式组成的可行域是凸集 (凸集的定义是：
集合内部任意两点连线上的点都属于这个集合 )。
可行域有有限个顶点 。 设规划问题有 n个变量,m个约束,则顶点的个数不多于 Cnm个 。
目标函数最优值一定在可行域的边界达到,而不可能在其内部 。
二、几点说明上海财经大学国际工商管理学院
SHUFE
16
第二节 线性规划的图解法三,解的可能性
x1 =8
2x2 =12
3x1 +4 x2 =36
x1
x2
4 8 12
3
6
9
0 A
B
C(4,6)D
例 1的数学模型变为
maxZ= 3x1 +4 x2
x1 ≤8
2x2 ≤12
3x1 +4 x2 ≤36
x1≥0,x2≥0
S.t.
Z=24 Z=36
Z=12
唯一最优解：只有一个最优点 。
多重最优解：无穷多个最优解 。 若在两个顶点同时得到最优解,则它们连线上的每一点都是最优解 。
上海财经大学国际工商管理学院
SHUFE
17
第二节 线性规划的图解法
无界解：线性规划问题的可行域无界,使目标函数无限增大而无界 。 （ 缺乏必要的约束条件 ）
三,解的可能性（续）
例如
maxZ= 3x1 +2 x2
-2x1 + x2 ≤2
x1 -3 x2 ≤3
x1≥0,x2≥0
-2x1 + x2 =2
x1 -3 x2
=3
x2
1
2
3
-1
x11 2 3-1
Z=6
Z=12
S.t.
上海财经大学国际工商管理学院
SHUFE
18
第二节 线性规划的图解法
无可行解：若约束条件相互矛盾,则可行域为空集三,解的可能性（续）
例如
maxZ= 3x1 +2 x2
-2x1 + x2 ≥2
x1 -3 x2 ≥3
x1≥0,x2≥0
-2x1 + x2 =2
x1 -3 x2
=3
x2
1
2
3
-1
x11 2 3-1
S.t.
上海财经大学国际工商管理学院
SHUFE
19
第三节 线性规划的标准型
线性规划问题的数学模型有各种不同的形式,如
目标函数有极大化和极小化；
约束条件有,≤”,,≥” 和,＝,三种情况；
决策变量一般有非负性要求,有的则没有 。
为了求解方便,特规定一种线性规划的标准形式,
非标准型可以转化为标准型 。 标准形式为：
目标函数极大化,
约束条件为等式,
右端常数项 bi≥0，
决策变量非负 。
一,标准型上海财经大学国际工商管理学院
SHUFE
20
第三节 线性规划的标准型
1,代数式二、标准型的表达方式有代数式、矩阵式：
maxZ=c1x1+c2x2+…+c nxn
a11x1+a12x2+…+a 1nxn ＝ b1
a21x1+a22x2+…+a 2nxn ＝ b2
… … … … …
am1x1+am2x2+…+a mnxn＝ bm
x1,x2,…,x n ≥0
maxZ= cjxj
aijxj＝ bi ( i=1,2,…,m )
xj≥0 ( j=1,2,…,n )
n
j 1
n
j 1
简记上海财经大学国际工商管理学院
SHUFE
21
第三节 线性规划的标准型
2,矩阵式
0
..
m ax
X
bAX
ts
XCZ ),,,( 21 ncccC价值向量
mnmm
n
n
aaa
aaa
aaa
A
21
22221
11211
技术矩阵
m
b
b
b
b
2
1
资源向量
n
x
x
x
X
2
1
决策向量上海财经大学国际工商管理学院
SHUFE
22
第三节 线性规划的标准型
目标函数极小化问题
minZ=CTX,只需将等式两端乘以 -1 即变为极大化问题 。
因为 minZ=-max (-Z)=CTX，令 Z′= -Z，则 maxZ′=-CX
右端常数项非正两端同乘以 -1
约束条件为不等式
当约束方程为,≤”时，左端加入一个非负的松弛变量，就把不等式变成了等式；
当约束条件为,≥”时，不等式左端减去一个非负的剩余变量 (也可称松弛变量 )即可。
决策变量 xk没有非负性要求令 xk=xk′-x k〃,xk=xk′,x k〃 ≥0,用 xk′,x k〃 取代模型中 xk
三、非标准型向标准型转化上海财经大学国际工商管理学院
SHUFE
23
第三节 线性规划的标准型
例 1 的标准型
例 1 maxZ= 3x1 +5 x2
x1 ≤8
2x2 ≤12
3x1 +4 x2 ≤36
x1≥0,x2≥0
S.t.
x1 +x3 =8
2x2 +x4 = 12
3x1 +4 x2 +x5= 36
x1,x2,x3,x4,x5≥0
maxZ= 3x1 +5 x2 +0x3 +0x4+0x5
上海财经大学国际工商管理学院
SHUFE
24
minZ= x1 +2 x2 +3 x3′
x1 +2 x2 + x3′≤5
2x1 +3 x2 + x3′≥6
-x1 - x2 - x3′≥ -2
x1≥0,x3′≥0
第三节 线性规划的标准型
例 minZ= x1 +2 x2 -3 x3
x1 +2 x2 - x3 ≤5
2x1 +3 x2 - x3 ≥6
-x1 - x2 + x3 ≥ -2
x1≥0,x3≤0
标准化 1
S.t.
上海财经大学国际工商管理学院
SHUFE
25
第三节 线性规划的标准型
标准化 2
minZ= x1 +2 (x2′-x 2〃 ) +3 x3′
x1 +2 (x2′-x 2〃 ) + x3′≤5
2x1 +3 (x2′-x 2〃 ) + x3′≥6
- x1 - (x2′-x 2〃 ) - x3′≥ -2
x1,x2′,x 2〃,x3′≥0
标准化 3
minZ= x1 +2 (x2′-x 2〃 ) +3 x3′
x1 +2 (x2′-x 2〃 ) + x3′≤5
2x1 +3 (x2′-x 2〃 ) + x3′≥6
x1 + (x2′-x 2〃 ) + x3 ′≤ 2
x1,x2′,x 2〃,x3′ ≥0
上海财经大学国际工商管理学院
SHUFE
26
第三节 线性规划的标准型
标准化 4
minZ= x1 +2 (x2′-x 2〃 ) +3 x3′
x1 +2 (x2′-x 2〃 ) + x3′+ x4 =5
2x1 +3 (x2′-x 2〃 ) + x3′≥6
x1 + (x2′-x 2〃 ) + x3′ ≤ 2
x1,x2′,x 2〃,x3′,x4≥0
标准化 5
minZ= x1 +2 (x2′-x 2〃 ) +3 x3′
x1 +2 (x2′-x 2〃 ) + x3′+ x4 =5
2x1 +3 (x2′-x 2〃 ) + x3′ - x5 = 6
x1 + (x2′-x 2〃 ) + x3′ ≤ 2
x1,x2′,x 2〃,x3′,x4,x5≥0
上海财经大学国际工商管理学院
SHUFE
27
第三节 线性规划的标准型
标准化 6
minZ= x1 +2 (x2′-x 2〃 ) +3 x3′
x1 +2 (x2′-x 2〃 ) + x3′+ x4 =5
2x1 +3 (x2′-x 2〃 ) + x3′ - x5 = 6
x1 + (x2′-x 2〃 ) - x3′ + x6= 2
x1,x2′,x 2〃,x3′,x4,x5,x6≥0
标准化 7
maxZ= -x1 -2 (x2′-x 2〃 ) - 3x3′+0x4+0x5+0x6
x1 +2 (x2′-x 2〃 ) + x3′+ x4 =5
2x1 +3 (x2′-x 2〃 ) + x3′ - x5 = 6
x1 + (x2′-x 2〃 ) - x3′ + x6 = 2
x1,x2′,x 2〃,x3′,x4,x5,x6≥0
上海财经大学国际工商管理学院
SHUFE
28
第四节 线性规划解的概念
可行解：
满足约束条件 AX=b,X≥0的解。
最优解：
使目标函数最优的可行解，称为最优解。
基
m＜ n，且 m个方程线性无关，即矩阵 A的秩为 m；根据线性代数定理可知,n＞ m，则方程组有多个解，这也正是线性规划寻求最优解的余地所在。
一、线性规划解的概念上海财经大学国际工商管理学院
SHUFE
29
第四节 线性规划解的概念
线性方程组的增广矩阵
例 1 的标准型
maxZ= 3x1 +5 x2 +0x3 +0x4+0x5
x1 +x3 =8
2x2 +x4 = 12
3x1 +4 x2 +x5= 36
x1,x2,x3,x4,x5≥0
3610
1201
800
043
020
101
~
A
x1 x2 x3 x4 x5 单位矩阵上海财经大学国际工商管理学院
SHUFE
30
第四节 线性规划解的概念
基矩阵：
系数矩阵 A中任意 m列所组成的 m阶非奇异子矩阵，称为该线性规划问题的一个基矩阵。
或称为一个基，用 B表示。
称基矩阵的列为基向量，用 Pj表示 (j=1,2,…,m ) 。
10
01
00
043
020
101
~
A 的基矩阵 B最多 C5
3=10，如下：
100
010
001
x3 x4 x5
103
010
001
x1 x4 x5
104
012
000
x2 x4 x5
130
000
011
x3 x1 x5
140
020
001
x3 x2 x5
300
010
101
x3 x4 x1
400
210
001
x3 x4 x2
043
020
101
x1 x2 x5 x1 x2 x4
043
120
001
x1 x2 x5
143
020
001
上海财经大学国际工商管理学院
SHUFE
31
第四节 线性规划解的概念
基变量：
与基向量 Pj相对应的 m个变量 xj称为基变量，
其余的 m-n个变量为非基变量。
基解：
令所有非基变量等于零，对 m个基变量所求的解，
对应一个特定的基矩阵能求得一组唯一解，这个对应于基的解称为基解。
结合图解来看，基解是各约束方程及坐标轴之间交点的坐标。
100
010
001
B
x3 x4 x5
基变量是 x3,x4,x5
非基变量是 x1,x2
令非基变量 x1=x2=0，得到一个基解
x3=8,x4=12,x5=36
上海财经大学国际工商管理学院
SHUFE
32
第四节 线性规划解的概念
基可行解：满足非负性约束的基解称为基可行解 。
可行基：对应于基可行解的基,称为可行基 。
最优基：最优解对应的基矩阵，称为最优基。
非可行解可行解基解基可行解上海财经大学国际工商管理学院
SHUFE
33
第四节 线性规划解的概念
定理 1.若线性规划问题存在可行域,则其可行域一定是凸集 。
定理 2.线性规划问题的基可行解对应可行域的顶点 。
定理 3.若可行域有界,线性规划的目标函数一定可以在可行域的顶点上达到最优 。
二、线性规划的基本定理
线性规划问题可以有无数个可行解,最优解只可能在顶点上达到,而有限个顶点对应的是基可行解,故只要在有限个基可行解中寻求最优解即可 。
从一个顶点出发找到一个可行基,得到一组基可行解,拿目标函数做尺度衡量一下看是否最优 。
如若不是,则向邻近的顶点转移,换一个基再行求解,检验,
如此迭代循环目标值逐步改善,直至求得最优解 。
三、线性规划的解题思路上海财经大学国际工商管理学院
SHUFE
34
第二章 线性规划单纯形法
单纯形法 (Simplex Method)是美国人丹捷格
(G.Dantzig)1947年创建的
这种方法简捷、规范，是举世公认的解决线性规划问题行之有效的方法。
单纯形法的表现形式：
代数法
表格法
矩阵法上海财经大学国际工商管理学院
SHUFE
35
第二章 线性规划单纯形法第一节 单纯形法原理第二节 表格单纯形法第三节 人工变量问题第四节 单纯形法补遗上海财经大学国际工商管理学院
SHUFE
36
第一节 单纯形法原理一、代数解法
x1 + x3 =8
2x2 + x4 =12
3x1 +4 x2 + x5=36
-Z+3x1 +5 x2 +0x3 +0x4+0x5 =0
x1,x2,x3,x4,x5≥0
10
01
00
043
020
101
A
x1 x2 x3 x4 x5
100
010
001
B
x3 x4 x5
非奇异子阵，
做为一个基基变量
x3,x4,x5
非基变量
x1,x2
上海财经大学国际工商管理学院
SHUFE
37
第一节 单纯形法原理
将基变量用非基变量线性表示，即
x3= 8 - x1
x4=12 - 2x2
x5=36 -3x1-4 x2
令非基变量 x1=0,x2=0，找到一个初始基可行解,
x1=0,x2 =0,x3 =8,x4 =12,x5 =36
即 X0=(0,0,8,12,36) T
一个可行解就是一个生产方案，在上述方案中两种产品都不生产，利润 Z=0。
1,求初始基可行解上海财经大学国际工商管理学院
SHUFE
38
第一节 单纯形法原理
确定进基变量
x1 + x3 =8
2x2 + x4 =12
3x1 +4 x2 + x5=36
-Z+3x1 +5 x2 +0x3 +0x4+0x5=0
从目标函数 -Z+3x1+5 x2 +0x3 +0x4+0x5=0可知：
非基变量 x1和 x2的系数均为正数,生产哪种产品都会增加利润 。
因为 x2的系数大于 x1的系数,即生产单位乙产品比甲产品利润更高一些,故应优先多生产乙产品 。
2,第一次迭代上海财经大学国际工商管理学院
SHUFE
39
第一节 单纯形法原理
确定离基变量
基变量用非基变量线性表示
x3 =8 –x1
x4 =12- 2x2
x5=36 -3x1-4 x2
保持原非基变量 x1 =0，
x2变成基变量时应保证 x3,x4,,x5非负,即有
2,第一次迭代（续）
x3 =8 ≥0
x4 =12- 2x2 ≥0
x5=36 -4 x2 ≥0
x2 ≤12/2
x2 ≤36/4
6212}436,212,m i n {2x即上海财经大学国际工商管理学院
SHUFE
40
第一节 单纯形法原理
2,第一次迭代（续）
主行主列主元
x1 +0x2 + x3 =8
2x2 + x4 =12
3x1 +4 x2 + x5=36
-Z+3x1 +5 x2 +0x3 +0x4+0x5 =0
进基变量所在列为主列，离基变量所在行为主行上海财经大学国际工商管理学院
SHUFE
41
第一节 单纯形法原理
基变换
进行初等变换，变主元为 1，主列为单位列向量。
2,第一次迭代（续）
x1 + x3 =8
x2 +1/2 x4 =6
3x1 + -2 x4 + x5=12
-Z+3x1 +0 x2 +0x3–5/2x4 +0x5=-30
x1 + x3 =8
x2 +1/2 x4 =6
3x1 + -2 x4 + x5=12
-Z+3x1 +5 x2 +0x3+0x4 +0x5=0
x1 +0x2 + x3 =8
2x2 + x4 =12
3x1 +4 x2 + x5=36
-Z+3x1 +5 x2 +0x3 +0x4+0x5 =0
x1 + x3 =8
x2 +1/2 x4 =6
3x1 +4 x2 + x5=36
-Z+3x1 +5 x2 +0x3+0x4 +0x5 =0
上海财经大学国际工商管理学院
SHUFE
42
第一节 单纯形法原理
2,第一次迭代（续）
将基变量用非基变量线性表示，即
x3=8 –x1
x2=6- 1/2x4
x5=12 -3x1+4 x4
令非基变量 x1=0,x4=0，找到另一个基可行解
x1=0,x2 =6,x3 =8,x4 =0,x5 =12
即 X1=(0,6,8,0,12) T
目标函数 Z=30
上海财经大学国际工商管理学院
SHUFE
43
第一节 单纯形法原理
确定进基变量
3,第二次迭代第一次迭代结果
x1 + x3 =8
x2 +1/2 x4 =6
3x1 + -2 x4 + x5=12
-Z+3x1 +0 x2 +0x3–5/2x4 +0x5=-30
目标函数 -Z+3x1 +0 x2 +0x3 –5/2x4 +0x5 =-30，
非基变量 x1的系数?1=3（ 检验数 ） 为正数,
确定 x1为进基变量 。
上海财经大学国际工商管理学院
SHUFE
44
第一节 单纯形法原理
确定离基变量
3,第二次迭代 （续）
x3 =8- x1 ≥0
x2 =6 ≥0
x5=12 -3x1≥0
x1 ≤8/1
x1 ≤12/3
4312}312,,18m i n {1x即基变量用非基变量线性表示
x3=8 –x1
x2=6- 1/2x4
x5=12 -3x1+4 x4
保持原非基变量 x4 =0，
x1变成基变量时应保证 x2,x3,,x5非负,即上海财经大学国际工商管理学院
SHUFE
45
第一节 单纯形法原理
基变换
变主元为 1，主列为单位列向量。
3,第二次迭代（续）
x1 + x3 =8
x2 +1/2 x4 =6
x1 + -2/3 x4 + 1/3x5=4
-Z+3x1 +0 x2 +0x3–5/2x4+0x5 =-30
x3 +2/3 x4 -1/3x5 =4
x2 +1/2 x4 =6
x1 + -2/3 x4 + 1/3x5=4
-Z+3x1 +0 x2 +0x3–5/2x4+0x5 =-30
x3 +2/3 x4 -1/3x5 =4
x2 +1/2 x4 =6
x1 + -2/3 x4 +1/3x5=4
-Z+0x1 +0x2 +0x3-1/2x4 - x5 =-42
1 x1 + x3 =8
x2 +1/2 x4 =6
3x1 + -2 x4 + x5=12
-Z+3x1 +0 x2 +0x3–5/2x4+0x5 =-30
上海财经大学国际工商管理学院
SHUFE
46
第一节 单纯形法原理
3,第二次迭代（续）
将基变量用非基变量线性表示，即
x3 =4 –2/3x4 +1/3x5
x2=6- 1/4x4
x1=4 +2/3x4-1/3 x5
令非基变量 x4=0,x5=0，又找到一个基可行解
目标函数 -Z+0x1 +0x2+0x3 -1/2x4 - x5 =-42
x1=4,x2 =6,x3 =4,x4 =0,x5 =0
即 X2=(4,6,4,0,0)T Z=42
检验数 σj非正,得最优解 X*=(4,6,4,0,0)T,Z*=42
上海财经大学国际工商管理学院
SHUFE
47
第一节 单纯形法原理二、单纯形法的几何意义
x1 =8
2x2 =12
3x1 +4 x2 =36
x1
x2
4 8 12
3
6
9
0 A
B
C(4,6)D
X0=(0,0,8,12,36)T
X1=(0,6,8,0,12)T X1=(4,6,4,0,0)T
上海财经大学国际工商管理学院
SHUFE
48
第二节 表格单纯形法
表格单纯形法，是对上节讨论的方法步骤进行具体化、规范化、表格化的结果。
一、单纯形法表
Cj C1 C2 … Cj … Cn 比值CB XB b x1 x2 … xj … xn
CB1 xB1 b1 a11 a12 … a1j … a1n?1
CB2 xB2 b2 a21 a22 … a2j … a2n?2
… … … … … … … … …
CBn xBn bm am1 am2 … amj … amn?m
检验数?j -Z?1?2 …?j …?n
上海财经大学国际工商管理学院
SHUFE
49
第二节 表格单纯形法
① 将线性规划问题化成标准型 。
② 找出或构造一个 m阶单位矩阵作为初始可行基,建立初始单纯形表 。
③ 计算各非基变量 xj的检验数?j=Cj-CBPj ′,若所有?j≤0,则问题已得到最优解,停止计算,否则转入下步 。
④ 在大于 0的检验数中,若某个?k所对应的系数列向量 Pk′≤0,则此问题是无界解,停止计算,否则转入下步 。
⑤ 根据 max{?j｜?j＞ 0}=?k原则,确定 xk为换入变量 (进基变量 ),再按?
规则计算,?=min{bi′/aik′| aik′＞ 0}=bl′/ aik′ 确定 xBl为换出变量 。 建立新的单纯形表,此时基变量中 xk取代了 xBl的位置 。
⑥ 以 aik′为主元素进行迭代,把 xk所对应的列向量变为单位列向量,即
aik′变为 1,同列中其它元素为 0,转第 ③ 步 。
二、单纯形法的计算步骤上海财经大学国际工商管理学院
SHUFE
50
第二节 表格单纯形法
maxZ=3x1 +5 x2 +0x3 +0x4+0x5 =0
x1 + x3 =8
2x2 + x4 =12
3x1 +4 x2 + x5=36
三、单纯形法计算举例
Cj 比值CB XB b
检验数?j
x1 x2 x3 x4 x5
3 5 0 0 0
8 1 0 1 0 0
12 0 2 0 1 0
36 3 4 0 0 1
x3
x4
x5
0
0
0
0 3 5 0 0 0
-
12/2=6
36/4=9
m
i
ijBjj aCC i
1
'?
上海财经大学国际工商管理学院
SHUFE
51
第二节 表格单纯形法检验数?j
8 1 0 1 0 0
6 0 1 0 1/2 0
12 3 0 0 -2 1
x3
x2
x5
0
5
0
-30 3 0 0 -5/2 0
8
-
4
Cj 比值CB XB b
检验数?j
x1 x2 x3 x4 x5
3 5 0 0 0
8 1 0 1 0 0
12 0 2 0 1 0
36 3 4 0 0 1
x3
x4
x5
0
0
0
0 3 5 0 0 0
-
12/2=6
36/4=9
上海财经大学国际工商管理学院
SHUFE
52
第二节 表格单纯形法
Cj 比值CB XB b
检验数?j
x1 x2 x3 x4 x5
3 5 0 0 0
8 1 0 1 0 0
6 0 1 0 1/2 0
12 3 0 0 -2 1
x3
x2
x5
0
5
0
-30 3 0 0 -5/2 0
8
-
4
检验数?j
4 0 0 1 2/3 -1/3
6 0 1 0 1/2 0
4 1 0 0 -2/3 1/3
x3
x2
x1
0
5
3
-42 0 0 0 -1/2 -1
最优解,X*=(4,6,4,0,0)T,Z*=42
上海财经大学国际工商管理学院
SHUFE
53
第二节 表格单纯形法
最优基
Cj 3 5 0 0 0 比值CB XB b x1 x2 x3 x4 x5
0 x3 4 0 0 1 2/3 -1/3
5 x2 6 0 1 0 1/2 0
3 x1 4 1 0 0 -2/3 1/3
检验数?j -42 0 0 0 -1/2 -1
340
020
101
*B
x3 x2 x1
3
1
3
2
0
0
2
1
0
3
1
3
2
1
1*
B
最优基的逆
最优基和最优基的逆上海财经大学国际工商管理学院
SHUFE
54
第二节 表格单纯形法
例如
maxZ= 3x1 +2 x2
-2x1 + x2 ≤2
x1 -3 x2 ≤3
x1,x2≥0
S.t.
标准化
maxZ= 3x1 +2 x2
-2x1 + x2 + x3 =2
x1 -3 x2 + x4 =3
x1,x2,x3,x4≥0
Cj 比值CB XB b
检验数?j
x1 x2 x3 x4
3 2 0 0
2 -2 1 1 0
3 1 -3 0 1
x3
x4
0
0
0 3 2 0 0
-
3
检验数?j
8 0 -5 1 2x3
x1
0
3
-
-3 1 -3 0 1
-9 0 11 0 -3
此时,检验数?2=11＞ 0，还没有得到最优解。
确定 x2进基，但 x2所在列的系数向量元素非正，无界
值不存在，有进基变量但无离基变量。
上海财经大学国际工商管理学院
SHUFE
55
第三节 人工变量问题
用单纯形法解题时，需要有一个单位阵作为初始基。
当约束条件都是,≤”时，加入松弛变量就形成了初始基。
但实际存在,≥”或“＝”型的约束，没有现成的单位矩阵。
一、人工变量
采用人造基的办法,人工构造单位矩阵
在没有单位列向量的等式约束中加入人工变量，构成原线性规划问题的伴随问题，从而得到一个初始基。
人工变量是在等式中人为加进的，只有它等于 0时，约束条件才是它本来的意义。
处理方法有两种：
大 M 法
两阶段法上海财经大学国际工商管理学院
SHUFE
56
第三节 人工变量问题
没有单位矩阵，不符合构造初始基的条件，需加入人工变量 。
人工变量最终必须等于 0才能保持原问题性质不变。
为保证人工变量为 0，在目标函数中令其系数为 -M。
M为无限大的正数，这是一个惩罚项，倘若人工变量不为零，
则目标函数就永远达不到最优，所以必须将人工变量逐步从基变量中替换出去。
如若到最终表中人工变量仍没有置换出去，那么这个问题就没有可行解，当然亦无最优解。
大 M法例如 maxZ= 3x1 - x2 -2 x3
3x1 + 2 x2 -3 x3 =6
x1 - 2 x2 + x3 =4
x1,x2,x3≥0
S.t.
上海财经大学国际工商管理学院
SHUFE
57
第三节 人工变量问题
按大 M法构造人造基，引入人工变量 x4,x5 的辅助问题如下：
maxZ= 3x1 - x2 -2 x3 -M x4 -M x5
3x1 + 2 x2 -3 x3 + x4 =6
x1 - 2 x2 + x3 + x5 =4
x1,x2,x3,x4,x5≥0
Cj 比值CB XB b
检验数?j
x1 x2 x3 x4 x5
3 -1 -2 -M -M
6 3 2 -3 1 0
4 1 -2 1 0 1
-10M 3+4M -1 -2-2M 0 0
x4
x5
-M
-M
2
4
m
i
ijBjj aCC i
1
'?
上海财经大学国际工商管理学院
SHUFE
58
第三节 人工变量问题
Cj 比值CB XB b
检验数?j
x1 x2 x3 x4 x5
3 -1 -2 -M -M
6 3 2 -3 1 0
4 1 -2 1 0 1
3+4M -1 -2-2M 0 0
x4
x5
-M
-M
2
4
检验数?j
2 1 2/3 -1 1/3 0
2 0 -8/3 2 -1/3 1
0 -3-8M/3 1+2M -1-4M/3 0
x1
x5
3
-M
-
1
检验数?j
3 1 -2/3 0 1/6 1/2
1 0 -4/3 1 -1/6 1/2
0 -5/3 0 -M-5/6 -M-1/2
x1
x3
3
-2
上海财经大学国际工商管理学院
SHUFE
59
第四节 单纯形法补遗
进基变量相持：
单纯形法运算过程中,同时出现多个相同的?j最大 。
在符合要求的?j(目标为 max,?j＞ 0,min,?j＜ 0)中,选取下标最小的非基变量为换入变量；
离基变量相持：
单纯形法运算过程中,同时出现多个相同的最小 θ值 。
继续迭代,便有基变量为 0,称这种情况为 退化解 。
选取其中下标最大的基变量做为换出变量 。
多重最优解：
最优单纯形表中,存在非基变量的检验数?j=0。
让这个 非基变量进基,继续迭代,得另一个最优解 。
无界解：
大于 0的检验数中,若某个?k所对应的系数列向量 Pk′≤0,则解无界 。
无可行解：
最终表中存在人工变量是基变量 。
上海财经大学国际工商管理学院
SHUFE
60
第三章 对偶理论
若例 1中该厂的产品平销,现有另一企业想租赁其设备 。 厂方为了在谈判时心中有数,需掌握设备台时费用的最低价码,以便衡量对方出价,对出租与否做出抉择 。
在这个问题上厂长面临着两种选择：自行生产或出租设备 。 首先要弄清两个问题：
① 合理安排生产能取得多大利润?
② 为保持利润水平不降低,资源转让的最低价格是多少？
问题 ① 的最优解,x1=4,x2=6,Z*=42。
一、对偶问题上海财经大学国际工商管理学院
SHUFE
61
第三章 对偶理论第二个问题：出让定价
假设出让 A,B,C设备所得利润分别为 y1,y2,y3
原本用于生产甲产品的设备台时，如若出让，不应低于自行生产带来的利润，否则宁愿自己生产。于是有
y1+0y2+3y3≥ 3
同理，对乙产品而言，则有
0y1+2y2+4y3≥ 5
设备台时出让的收益（希望出让的收益最少值）
min?=8y1+12y2+36y3
显然还有
y1,y2,y3≥0
上海财经大学国际工商管理学院
SHUFE
62
第三章 对偶理论
对偶问题的最优解,y1=0,y2=1/2,y3=1,W* =42
两个问题的目标函数值相等，这不是偶然的，上述两个问题实际上是一个问题的两个方面，如果把前者称为线性规划原问题，则后者便是它的对偶问题，反之亦然。
对偶问题的最优解对应于原问题最优单纯型法表中，初始基变量的检验数的负值。
例 1的对偶问题的数学模型
min?=8y1+12y2+36y3
y1+ 0y2+ 3y3≥ 3
0y1+ 2y2+ 4y3≥ 5
y1,y2,y3≥0
S.t.
maxZ= 3x1 +5 x2
x1 ≤8
2x2 ≤12
3x1 +4 x2 ≤36
x1,x2≥0
S.t.
上海财经大学国际工商管理学院
SHUFE
63
第三章 对偶理论
这说明 yi是右端项 bi每增加一个单位对目标函数 Z的贡献 。
对偶变量 yi在经济上表示原问题第 i种资源的 边际价值 。
对偶变量的值 yi*所表示的第 i种资源的边际价值,称为 影子价值 。
若原问题的价值系数 Cj表示单位产值,则 yi称为 影子价格 。
若原问题的价值系数 Cj表示单位利润,则 yi称为 影子利润 。
二、对偶问题的经济解释
n
j
m
i
iijj ybxcZ
1 1
i
i
y
b
Z?
上海财经大学国际工商管理学院
SHUFE
64
第三章 对偶理论
影子价格不是资源的实际价格,而是资源配置结构的反映,
是在其它数据相对稳定的条件下某种资源增加一个单位导致的目标函数值的增量变化 。
对资源 i总存量的评估,购进 or 出让
对资源 i当前分配量的评估,增加 or 减少
① 它表明了当前的资源配置状况,告诉经营者应当优先增加何种资源,才能获利更多 。
② 告诉经营者以怎样的代价去取得紧缺资源 。
③ 提示设备出租或原材料转让的基价 。
④ 告诉经营者补给紧缺资源的数量,不要盲目大量补给 。
⑤ 借助影子价格进行内部核算 。
特别注意上海财经大学国际工商管理学院
SHUFE
65
第四章 灵敏度分析
线性规划研究的是一定条件下的最优化问题,采用优化方案可以达到节约资源,提高效益的目的,但是对,优化方案,
必须要有全面的认识,不可机械地对待 。
优化方案是建立在特定的资源环境和技术条件之上的,而环境和条件总是处在不断地变化之中,如产品价格,原材料成本,
加工技术水平,资源消耗系数等时有波动,所以优化方案是个相对稳定的概念 。 当基础数据发生变化时,最优方案也就变了 。
基础数据往往是测算估计的数值,虽然在运算过程中要求十分严格,但基础数据的误差是不可避免的 。 为了对优化结果有更全面的了解和恰当的运用,就需要进行灵敏度分析 。
灵敏度分析的意义上海财经大学国际工商管理学院
SHUFE
66
第四章 灵敏度分析
灵敏度分析又称敏感性分析或优化后分析，它研究基础数据发生波动后对最优解的影响，以及在多大的范围内波动才不影响最优基。
灵敏度分析就是研究最优解对数据变化的敏感程度。
感性太强，则说明最优解的稳定性程度较低。
灵敏度分析解决的问题：
参数在什么范围变化而最优基不变。
已知参数的变化范围，考察最优解 (最优基 )是否改变 。
灵敏度分析的概念上海财经大学国际工商管理学院
SHUFE
67
第四章 灵敏度分析
价值系数 Cj变化影响检验数
参数 Cj
m
i
ijBjj aCC i
1
'?
上海财经大学国际工商管理学院
SHUFE
68
第四章 灵敏度分析
非基变量 Cj的变化范围
非基变量 Cj变化，只影响它自己的检验数
Cj 3 5 0 0 0 比值CB XB b x1 x2 x3 x4 x5
0 x3 4 0 0 1 2/3 -1/3
5 x2 6 0 1 0 1/2 0
3 x1 4 1 0 0 -2/3 1/3
检验数?j 0 0 0 -1/2 -1
0
)(
*
1
'
1
'
jj
m
i
ijBjj
m
i
ijBjj
C
aCCC
aCC
i
i
*jjC即上海财经大学国际工商管理学院
SHUFE
69
第四章 灵敏度分析
基变量 CBl的变化范围
Cj C1 5 0 0 0 比值CB XB b x1 x2 x3 x4 x5
0 x3 4 0 0 1 2/3 -1/3
5 x2 6 0 1 0 1/2 0
C1 x1 4 1 0 0 -2/3 1/3
检验数?j 0 0 0 -2C1/3+5/2 -C1/3
4
1500
1 cj?
上海财经大学国际工商管理学院
SHUFE
70
第四章 灵敏度分析
4
6
4
3
1
3
2
0
0
2
1
0
3
1
3
2
1
*1* bB
例如
参数 bi
0
)(
1*
11
1
1
bBb
bBbB
bbB
bBX B
上海财经大学国际工商管理学院
SHUFE
71
第四章 灵敏度分析
3
3
3
1*
3
3
1
0
3
1
0
0
3
1
3
2
0
0
2
1
0
3
1
3
2
1
0
0
b
b
b
bB
b
b
120
3
1
4
120
3
1
4
33
33
bb
bb
供应链管理、国际物流管理、企业资源计划单 位,上海财经大学 国际工商管理学院 供应链管理研究中心
E-mail,jiaping_xie@sina.com.cn
电 话,55036936(H) 65903541(O)
上海财经大学国际工商管理学院
SHUFE
2
第一讲 线性规划第一章 线性规划的数学模型第一节 线性规划一般模型第二节 线性规划的图解法第三节 线性规划的标准型第四节 线性规划解的概念第二章 线性规划的单纯形法第一节 单纯形法原理第二节 表格单纯形法第三节 人工变量问题第四节 单纯形法补遗第三章 线性规划的对偶理论第四章 线性规划灵敏性分析上海财经大学国际工商管理学院
SHUFE
3
第一章 线性规划的数学模型
线性规划 Linear Programming LP
规划论中的静态规划
解决有限资源的最佳分配问题
求解方法：
图解法
单纯形解法上海财经大学国际工商管理学院
SHUFE
4
第一章 线性规划的数学模型第一节 线性规划一般模型第二节 线性规划的图解法第三节 线性规划的标准型第四节 线性规划解的概念上海财经大学国际工商管理学院
SHUFE
5
第一节 线性规划一般模型一、线性规划问题的三个要素
决策问题待定的量值称为决策变量 。
决策变量的取值要求非负 。
约束条件
任何问题都是限定在一定的条件下求解,把各种限制条件表示为一组等式或不等式,称之为约束条件 。
约束条件是决策方案可行的保障 。
LP的约束条件,都是决策变量的线性函数 。
目标函数
衡量决策方案优劣的准则,如时间最省,利润最大,成本最低 。
目标函数是决策变量的线性函数 。
有的目标要实现极大,有的则要求极小 。
上海财经大学国际工商管理学院
SHUFE
6
第一节 线性规划一般模型
例 1,生产计划问题某厂生产甲乙两种产品,各自的零部件分别在 A,B车间生产,最后都需在 C车间装配,相关数据如表所示：
问如何安排甲、乙两产品的产量，使利润为最大。
二、线性规划模型的构建产品车间工时单耗甲 乙生产能力
A
B
C
1 0
0 2
3 4
8
12
36
单位产品获利 3 5
上海财经大学国际工商管理学院
SHUFE
7
第一节 线性规划一般模型
(1)决策变量 。 要决策的问题是甲,乙两种产品的产量,因此有两个决策变量：设 x1为甲产品产量,x2为乙产品产量 。
(2)约束条件 。 生产这两种产品受到现有生产能力的制约,
用量不能突破 。
生产单位甲产品的零部件需耗用 A车间的生产能力 1工时,
生产单位乙产品不需耗用 A车间的生产能力,
A车间的能力总量为 8工时,则 A车间能力约束条件表述为
x1 ≤8
同理,B和 C车间能力约束条件为
2x2 ≤12
3x1 +4 x2 ≤36
建立模型上海财经大学国际工商管理学院
SHUFE
8
第一节 线性规划一般模型
(3)目标函数 。 目标是利润最大化，用 Z表示利润，则
maxZ= 3x1 +5 x2
(4)非负约束 。 甲乙产品的产量不应是负数,否则没有实际意义,这个要求表述为
x1 ≥0,x2 ≥0
综上所述，该问题的数学模型表示为
maxZ= 3x1 +5 x2
x1 ≤8
2x2 ≤12
3x1 +4 x2 ≤36
x1≥0,x2≥0
S.t.
上海财经大学国际工商管理学院
SHUFE
9
第一节 线性规划一般模型某名牌饮料在国内有三个生产厂,分布在城市 A1、
A2,A3,其一级承销商有 4个,分布在城市 B1,B2,B3、
B4,已知各厂的产量,各承销商的销售量及从 Ai到 Bj
的每吨饮料运费为 Cij,为发挥集团优势,公司要统一筹划运销问题,求运费最小的调运方案 。
例 2,运输问题销地产地 B1 B2 B3 B4 产量
A1
A2
A3
6 3 2 5
7 5 8 4
3 2 9 7
5
2
3
销量 2 3 1 4
上海财经大学国际工商管理学院
SHUFE
10
第一节 线性规划一般模型
(1)决策变量 。 设从 Ai到 Bj的运输量为 xij，
(2)目标函数 。 运费最小的目标函数为
minZ=6x11+3x12+2x13+5x14+7x21+5x22+8x23+4x24+3x31+2x32+9x33+7x34
(3)约束条件 。 产量之和等于销量之和,故要满足：
供应平衡条件 x11+x12+x13+x14=5x
21+x22+x23+x24=2
x31+x32+x33+x34 =3
销售平衡条件 x11+x21+x31=2
x12+x22+x32=3
x13+x23+x33=1
x14+x24+x34=4
非负性约束 xij≥0 (i=1,2,3； j=1,2,3,4)
上海财经大学国际工商管理学院
SHUFE
11
第一节 线性规划一般模型
用一组非负决策变量表示一个决策问题，
存在一定的等式或不等式的线性约束条件，
有一个希望达到的目标，可表示成决策变量的线性函数。可能是最大化，也可能是最小化。
线性规划一般模型的代数式 为：
三、线性规划的一般模型
max(min)Z=c1x1+c2x2+…+c nxn
a11x1+a12x2+…+a 1nxn ≤(≥,＝ )b1
a21x1+a22x2+…+a 2nxn ≤(≥,＝ )b2
… … … … …
am1x1+am2x2+…+a mnxn≤(≥,＝ )bm
x1,x2,…,x n ≥(≤)0
上海财经大学国际工商管理学院
SHUFE
12
第二节 线性规划的图解法
图解法即是用图示的方法来求解线性规划问题。
一个二维的线性规划问题，可以在平面图上求解，
三维的线性规划则要在立体图上求解，这就比较麻烦，而维数再高以后就不能图示了。
一、图解法的基本步骤上海财经大学国际工商管理学院
SHUFE
13
第二节 线性规划的图解法
1,可行域的确定
例 1的数学模型为
maxZ= 3x1 +5 x2
x1 ≤8
2x2 ≤12
3x1 +4 x2 ≤36
x1≥0,x2≥0
S.t.
x1 =8
2x2 =12
3x1 +4 x2 =36
x1
x2
4 8 12
3
6
9
0 A
B
C(4,6)D
五边形 OABCD内 (含边界 )的任意一点 (x1,x2) 都是满足所有约束条件的一个解，称之可行解 。
满足所有约束条件的解的集合，称之为可行域。即所有约束条件共同围城的区域。
上海财经大学国际工商管理学院
SHUFE
14
第二节 线性规划的图解法
2,最优解的确定
Z=30 Z=42
Z=15
目标函数 Z= 3x1 +5 x2 代表以 Z为参数的一族平行线。
x1 =8
2x2 =12
3x1 +4 x2 =36
x1
x2
4 8 12
3
6
9
0 A
B
C(4,6)D
等值线：位于同一直线上的点的目标函数值相同。
最优解：可行解中使目标函数最优 (极大或极小 )的解上海财经大学国际工商管理学院
SHUFE
15
第二节 线性规划的图解法
由线性不等式组成的可行域是凸集 (凸集的定义是：
集合内部任意两点连线上的点都属于这个集合 )。
可行域有有限个顶点 。 设规划问题有 n个变量,m个约束,则顶点的个数不多于 Cnm个 。
目标函数最优值一定在可行域的边界达到,而不可能在其内部 。
二、几点说明上海财经大学国际工商管理学院
SHUFE
16
第二节 线性规划的图解法三,解的可能性
x1 =8
2x2 =12
3x1 +4 x2 =36
x1
x2
4 8 12
3
6
9
0 A
B
C(4,6)D
例 1的数学模型变为
maxZ= 3x1 +4 x2
x1 ≤8
2x2 ≤12
3x1 +4 x2 ≤36
x1≥0,x2≥0
S.t.
Z=24 Z=36
Z=12
唯一最优解：只有一个最优点 。
多重最优解：无穷多个最优解 。 若在两个顶点同时得到最优解,则它们连线上的每一点都是最优解 。
上海财经大学国际工商管理学院
SHUFE
17
第二节 线性规划的图解法
无界解：线性规划问题的可行域无界,使目标函数无限增大而无界 。 （ 缺乏必要的约束条件 ）
三,解的可能性（续）
例如
maxZ= 3x1 +2 x2
-2x1 + x2 ≤2
x1 -3 x2 ≤3
x1≥0,x2≥0
-2x1 + x2 =2
x1 -3 x2
=3
x2
1
2
3
-1
x11 2 3-1
Z=6
Z=12
S.t.
上海财经大学国际工商管理学院
SHUFE
18
第二节 线性规划的图解法
无可行解：若约束条件相互矛盾,则可行域为空集三,解的可能性（续）
例如
maxZ= 3x1 +2 x2
-2x1 + x2 ≥2
x1 -3 x2 ≥3
x1≥0,x2≥0
-2x1 + x2 =2
x1 -3 x2
=3
x2
1
2
3
-1
x11 2 3-1
S.t.
上海财经大学国际工商管理学院
SHUFE
19
第三节 线性规划的标准型
线性规划问题的数学模型有各种不同的形式,如
目标函数有极大化和极小化；
约束条件有,≤”,,≥” 和,＝,三种情况；
决策变量一般有非负性要求,有的则没有 。
为了求解方便,特规定一种线性规划的标准形式,
非标准型可以转化为标准型 。 标准形式为：
目标函数极大化,
约束条件为等式,
右端常数项 bi≥0，
决策变量非负 。
一,标准型上海财经大学国际工商管理学院
SHUFE
20
第三节 线性规划的标准型
1,代数式二、标准型的表达方式有代数式、矩阵式：
maxZ=c1x1+c2x2+…+c nxn
a11x1+a12x2+…+a 1nxn ＝ b1
a21x1+a22x2+…+a 2nxn ＝ b2
… … … … …
am1x1+am2x2+…+a mnxn＝ bm
x1,x2,…,x n ≥0
maxZ= cjxj
aijxj＝ bi ( i=1,2,…,m )
xj≥0 ( j=1,2,…,n )
n
j 1
n
j 1
简记上海财经大学国际工商管理学院
SHUFE
21
第三节 线性规划的标准型
2,矩阵式
0
..
m ax
X
bAX
ts
XCZ ),,,( 21 ncccC价值向量
mnmm
n
n
aaa
aaa
aaa
A
21
22221
11211
技术矩阵
m
b
b
b
b
2
1
资源向量
n
x
x
x
X
2
1
决策向量上海财经大学国际工商管理学院
SHUFE
22
第三节 线性规划的标准型
目标函数极小化问题
minZ=CTX,只需将等式两端乘以 -1 即变为极大化问题 。
因为 minZ=-max (-Z)=CTX，令 Z′= -Z，则 maxZ′=-CX
右端常数项非正两端同乘以 -1
约束条件为不等式
当约束方程为,≤”时，左端加入一个非负的松弛变量，就把不等式变成了等式；
当约束条件为,≥”时，不等式左端减去一个非负的剩余变量 (也可称松弛变量 )即可。
决策变量 xk没有非负性要求令 xk=xk′-x k〃,xk=xk′,x k〃 ≥0,用 xk′,x k〃 取代模型中 xk
三、非标准型向标准型转化上海财经大学国际工商管理学院
SHUFE
23
第三节 线性规划的标准型
例 1 的标准型
例 1 maxZ= 3x1 +5 x2
x1 ≤8
2x2 ≤12
3x1 +4 x2 ≤36
x1≥0,x2≥0
S.t.
x1 +x3 =8
2x2 +x4 = 12
3x1 +4 x2 +x5= 36
x1,x2,x3,x4,x5≥0
maxZ= 3x1 +5 x2 +0x3 +0x4+0x5
上海财经大学国际工商管理学院
SHUFE
24
minZ= x1 +2 x2 +3 x3′
x1 +2 x2 + x3′≤5
2x1 +3 x2 + x3′≥6
-x1 - x2 - x3′≥ -2
x1≥0,x3′≥0
第三节 线性规划的标准型
例 minZ= x1 +2 x2 -3 x3
x1 +2 x2 - x3 ≤5
2x1 +3 x2 - x3 ≥6
-x1 - x2 + x3 ≥ -2
x1≥0,x3≤0
标准化 1
S.t.
上海财经大学国际工商管理学院
SHUFE
25
第三节 线性规划的标准型
标准化 2
minZ= x1 +2 (x2′-x 2〃 ) +3 x3′
x1 +2 (x2′-x 2〃 ) + x3′≤5
2x1 +3 (x2′-x 2〃 ) + x3′≥6
- x1 - (x2′-x 2〃 ) - x3′≥ -2
x1,x2′,x 2〃,x3′≥0
标准化 3
minZ= x1 +2 (x2′-x 2〃 ) +3 x3′
x1 +2 (x2′-x 2〃 ) + x3′≤5
2x1 +3 (x2′-x 2〃 ) + x3′≥6
x1 + (x2′-x 2〃 ) + x3 ′≤ 2
x1,x2′,x 2〃,x3′ ≥0
上海财经大学国际工商管理学院
SHUFE
26
第三节 线性规划的标准型
标准化 4
minZ= x1 +2 (x2′-x 2〃 ) +3 x3′
x1 +2 (x2′-x 2〃 ) + x3′+ x4 =5
2x1 +3 (x2′-x 2〃 ) + x3′≥6
x1 + (x2′-x 2〃 ) + x3′ ≤ 2
x1,x2′,x 2〃,x3′,x4≥0
标准化 5
minZ= x1 +2 (x2′-x 2〃 ) +3 x3′
x1 +2 (x2′-x 2〃 ) + x3′+ x4 =5
2x1 +3 (x2′-x 2〃 ) + x3′ - x5 = 6
x1 + (x2′-x 2〃 ) + x3′ ≤ 2
x1,x2′,x 2〃,x3′,x4,x5≥0
上海财经大学国际工商管理学院
SHUFE
27
第三节 线性规划的标准型
标准化 6
minZ= x1 +2 (x2′-x 2〃 ) +3 x3′
x1 +2 (x2′-x 2〃 ) + x3′+ x4 =5
2x1 +3 (x2′-x 2〃 ) + x3′ - x5 = 6
x1 + (x2′-x 2〃 ) - x3′ + x6= 2
x1,x2′,x 2〃,x3′,x4,x5,x6≥0
标准化 7
maxZ= -x1 -2 (x2′-x 2〃 ) - 3x3′+0x4+0x5+0x6
x1 +2 (x2′-x 2〃 ) + x3′+ x4 =5
2x1 +3 (x2′-x 2〃 ) + x3′ - x5 = 6
x1 + (x2′-x 2〃 ) - x3′ + x6 = 2
x1,x2′,x 2〃,x3′,x4,x5,x6≥0
上海财经大学国际工商管理学院
SHUFE
28
第四节 线性规划解的概念
可行解：
满足约束条件 AX=b,X≥0的解。
最优解：
使目标函数最优的可行解，称为最优解。
基
m＜ n，且 m个方程线性无关，即矩阵 A的秩为 m；根据线性代数定理可知,n＞ m，则方程组有多个解，这也正是线性规划寻求最优解的余地所在。
一、线性规划解的概念上海财经大学国际工商管理学院
SHUFE
29
第四节 线性规划解的概念
线性方程组的增广矩阵
例 1 的标准型
maxZ= 3x1 +5 x2 +0x3 +0x4+0x5
x1 +x3 =8
2x2 +x4 = 12
3x1 +4 x2 +x5= 36
x1,x2,x3,x4,x5≥0
3610
1201
800
043
020
101
~
A
x1 x2 x3 x4 x5 单位矩阵上海财经大学国际工商管理学院
SHUFE
30
第四节 线性规划解的概念
基矩阵：
系数矩阵 A中任意 m列所组成的 m阶非奇异子矩阵，称为该线性规划问题的一个基矩阵。
或称为一个基，用 B表示。
称基矩阵的列为基向量，用 Pj表示 (j=1,2,…,m ) 。
10
01
00
043
020
101
~
A 的基矩阵 B最多 C5
3=10，如下：
100
010
001
x3 x4 x5
103
010
001
x1 x4 x5
104
012
000
x2 x4 x5
130
000
011
x3 x1 x5
140
020
001
x3 x2 x5
300
010
101
x3 x4 x1
400
210
001
x3 x4 x2
043
020
101
x1 x2 x5 x1 x2 x4
043
120
001
x1 x2 x5
143
020
001
上海财经大学国际工商管理学院
SHUFE
31
第四节 线性规划解的概念
基变量：
与基向量 Pj相对应的 m个变量 xj称为基变量，
其余的 m-n个变量为非基变量。
基解：
令所有非基变量等于零，对 m个基变量所求的解，
对应一个特定的基矩阵能求得一组唯一解，这个对应于基的解称为基解。
结合图解来看，基解是各约束方程及坐标轴之间交点的坐标。
100
010
001
B
x3 x4 x5
基变量是 x3,x4,x5
非基变量是 x1,x2
令非基变量 x1=x2=0，得到一个基解
x3=8,x4=12,x5=36
上海财经大学国际工商管理学院
SHUFE
32
第四节 线性规划解的概念
基可行解：满足非负性约束的基解称为基可行解 。
可行基：对应于基可行解的基,称为可行基 。
最优基：最优解对应的基矩阵，称为最优基。
非可行解可行解基解基可行解上海财经大学国际工商管理学院
SHUFE
33
第四节 线性规划解的概念
定理 1.若线性规划问题存在可行域,则其可行域一定是凸集 。
定理 2.线性规划问题的基可行解对应可行域的顶点 。
定理 3.若可行域有界,线性规划的目标函数一定可以在可行域的顶点上达到最优 。
二、线性规划的基本定理
线性规划问题可以有无数个可行解,最优解只可能在顶点上达到,而有限个顶点对应的是基可行解,故只要在有限个基可行解中寻求最优解即可 。
从一个顶点出发找到一个可行基,得到一组基可行解,拿目标函数做尺度衡量一下看是否最优 。
如若不是,则向邻近的顶点转移,换一个基再行求解,检验,
如此迭代循环目标值逐步改善,直至求得最优解 。
三、线性规划的解题思路上海财经大学国际工商管理学院
SHUFE
34
第二章 线性规划单纯形法
单纯形法 (Simplex Method)是美国人丹捷格
(G.Dantzig)1947年创建的
这种方法简捷、规范，是举世公认的解决线性规划问题行之有效的方法。
单纯形法的表现形式：
代数法
表格法
矩阵法上海财经大学国际工商管理学院
SHUFE
35
第二章 线性规划单纯形法第一节 单纯形法原理第二节 表格单纯形法第三节 人工变量问题第四节 单纯形法补遗上海财经大学国际工商管理学院
SHUFE
36
第一节 单纯形法原理一、代数解法
x1 + x3 =8
2x2 + x4 =12
3x1 +4 x2 + x5=36
-Z+3x1 +5 x2 +0x3 +0x4+0x5 =0
x1,x2,x3,x4,x5≥0
10
01
00
043
020
101
A
x1 x2 x3 x4 x5
100
010
001
B
x3 x4 x5
非奇异子阵，
做为一个基基变量
x3,x4,x5
非基变量
x1,x2
上海财经大学国际工商管理学院
SHUFE
37
第一节 单纯形法原理
将基变量用非基变量线性表示，即
x3= 8 - x1
x4=12 - 2x2
x5=36 -3x1-4 x2
令非基变量 x1=0,x2=0，找到一个初始基可行解,
x1=0,x2 =0,x3 =8,x4 =12,x5 =36
即 X0=(0,0,8,12,36) T
一个可行解就是一个生产方案，在上述方案中两种产品都不生产，利润 Z=0。
1,求初始基可行解上海财经大学国际工商管理学院
SHUFE
38
第一节 单纯形法原理
确定进基变量
x1 + x3 =8
2x2 + x4 =12
3x1 +4 x2 + x5=36
-Z+3x1 +5 x2 +0x3 +0x4+0x5=0
从目标函数 -Z+3x1+5 x2 +0x3 +0x4+0x5=0可知：
非基变量 x1和 x2的系数均为正数,生产哪种产品都会增加利润 。
因为 x2的系数大于 x1的系数,即生产单位乙产品比甲产品利润更高一些,故应优先多生产乙产品 。
2,第一次迭代上海财经大学国际工商管理学院
SHUFE
39
第一节 单纯形法原理
确定离基变量
基变量用非基变量线性表示
x3 =8 –x1
x4 =12- 2x2
x5=36 -3x1-4 x2
保持原非基变量 x1 =0，
x2变成基变量时应保证 x3,x4,,x5非负,即有
2,第一次迭代（续）
x3 =8 ≥0
x4 =12- 2x2 ≥0
x5=36 -4 x2 ≥0
x2 ≤12/2
x2 ≤36/4
6212}436,212,m i n {2x即上海财经大学国际工商管理学院
SHUFE
40
第一节 单纯形法原理
2,第一次迭代（续）
主行主列主元
x1 +0x2 + x3 =8
2x2 + x4 =12
3x1 +4 x2 + x5=36
-Z+3x1 +5 x2 +0x3 +0x4+0x5 =0
进基变量所在列为主列，离基变量所在行为主行上海财经大学国际工商管理学院
SHUFE
41
第一节 单纯形法原理
基变换
进行初等变换，变主元为 1，主列为单位列向量。
2,第一次迭代（续）
x1 + x3 =8
x2 +1/2 x4 =6
3x1 + -2 x4 + x5=12
-Z+3x1 +0 x2 +0x3–5/2x4 +0x5=-30
x1 + x3 =8
x2 +1/2 x4 =6
3x1 + -2 x4 + x5=12
-Z+3x1 +5 x2 +0x3+0x4 +0x5=0
x1 +0x2 + x3 =8
2x2 + x4 =12
3x1 +4 x2 + x5=36
-Z+3x1 +5 x2 +0x3 +0x4+0x5 =0
x1 + x3 =8
x2 +1/2 x4 =6
3x1 +4 x2 + x5=36
-Z+3x1 +5 x2 +0x3+0x4 +0x5 =0
上海财经大学国际工商管理学院
SHUFE
42
第一节 单纯形法原理
2,第一次迭代（续）
将基变量用非基变量线性表示，即
x3=8 –x1
x2=6- 1/2x4
x5=12 -3x1+4 x4
令非基变量 x1=0,x4=0，找到另一个基可行解
x1=0,x2 =6,x3 =8,x4 =0,x5 =12
即 X1=(0,6,8,0,12) T
目标函数 Z=30
上海财经大学国际工商管理学院
SHUFE
43
第一节 单纯形法原理
确定进基变量
3,第二次迭代第一次迭代结果
x1 + x3 =8
x2 +1/2 x4 =6
3x1 + -2 x4 + x5=12
-Z+3x1 +0 x2 +0x3–5/2x4 +0x5=-30
目标函数 -Z+3x1 +0 x2 +0x3 –5/2x4 +0x5 =-30，
非基变量 x1的系数?1=3（ 检验数 ） 为正数,
确定 x1为进基变量 。
上海财经大学国际工商管理学院
SHUFE
44
第一节 单纯形法原理
确定离基变量
3,第二次迭代 （续）
x3 =8- x1 ≥0
x2 =6 ≥0
x5=12 -3x1≥0
x1 ≤8/1
x1 ≤12/3
4312}312,,18m i n {1x即基变量用非基变量线性表示
x3=8 –x1
x2=6- 1/2x4
x5=12 -3x1+4 x4
保持原非基变量 x4 =0，
x1变成基变量时应保证 x2,x3,,x5非负,即上海财经大学国际工商管理学院
SHUFE
45
第一节 单纯形法原理
基变换
变主元为 1，主列为单位列向量。
3,第二次迭代（续）
x1 + x3 =8
x2 +1/2 x4 =6
x1 + -2/3 x4 + 1/3x5=4
-Z+3x1 +0 x2 +0x3–5/2x4+0x5 =-30
x3 +2/3 x4 -1/3x5 =4
x2 +1/2 x4 =6
x1 + -2/3 x4 + 1/3x5=4
-Z+3x1 +0 x2 +0x3–5/2x4+0x5 =-30
x3 +2/3 x4 -1/3x5 =4
x2 +1/2 x4 =6
x1 + -2/3 x4 +1/3x5=4
-Z+0x1 +0x2 +0x3-1/2x4 - x5 =-42
1 x1 + x3 =8
x2 +1/2 x4 =6
3x1 + -2 x4 + x5=12
-Z+3x1 +0 x2 +0x3–5/2x4+0x5 =-30
上海财经大学国际工商管理学院
SHUFE
46
第一节 单纯形法原理
3,第二次迭代（续）
将基变量用非基变量线性表示，即
x3 =4 –2/3x4 +1/3x5
x2=6- 1/4x4
x1=4 +2/3x4-1/3 x5
令非基变量 x4=0,x5=0，又找到一个基可行解
目标函数 -Z+0x1 +0x2+0x3 -1/2x4 - x5 =-42
x1=4,x2 =6,x3 =4,x4 =0,x5 =0
即 X2=(4,6,4,0,0)T Z=42
检验数 σj非正,得最优解 X*=(4,6,4,0,0)T,Z*=42
上海财经大学国际工商管理学院
SHUFE
47
第一节 单纯形法原理二、单纯形法的几何意义
x1 =8
2x2 =12
3x1 +4 x2 =36
x1
x2
4 8 12
3
6
9
0 A
B
C(4,6)D
X0=(0,0,8,12,36)T
X1=(0,6,8,0,12)T X1=(4,6,4,0,0)T
上海财经大学国际工商管理学院
SHUFE
48
第二节 表格单纯形法
表格单纯形法，是对上节讨论的方法步骤进行具体化、规范化、表格化的结果。
一、单纯形法表
Cj C1 C2 … Cj … Cn 比值CB XB b x1 x2 … xj … xn
CB1 xB1 b1 a11 a12 … a1j … a1n?1
CB2 xB2 b2 a21 a22 … a2j … a2n?2
… … … … … … … … …
CBn xBn bm am1 am2 … amj … amn?m
检验数?j -Z?1?2 …?j …?n
上海财经大学国际工商管理学院
SHUFE
49
第二节 表格单纯形法
① 将线性规划问题化成标准型 。
② 找出或构造一个 m阶单位矩阵作为初始可行基,建立初始单纯形表 。
③ 计算各非基变量 xj的检验数?j=Cj-CBPj ′,若所有?j≤0,则问题已得到最优解,停止计算,否则转入下步 。
④ 在大于 0的检验数中,若某个?k所对应的系数列向量 Pk′≤0,则此问题是无界解,停止计算,否则转入下步 。
⑤ 根据 max{?j｜?j＞ 0}=?k原则,确定 xk为换入变量 (进基变量 ),再按?
规则计算,?=min{bi′/aik′| aik′＞ 0}=bl′/ aik′ 确定 xBl为换出变量 。 建立新的单纯形表,此时基变量中 xk取代了 xBl的位置 。
⑥ 以 aik′为主元素进行迭代,把 xk所对应的列向量变为单位列向量,即
aik′变为 1,同列中其它元素为 0,转第 ③ 步 。
二、单纯形法的计算步骤上海财经大学国际工商管理学院
SHUFE
50
第二节 表格单纯形法
maxZ=3x1 +5 x2 +0x3 +0x4+0x5 =0
x1 + x3 =8
2x2 + x4 =12
3x1 +4 x2 + x5=36
三、单纯形法计算举例
Cj 比值CB XB b
检验数?j
x1 x2 x3 x4 x5
3 5 0 0 0
8 1 0 1 0 0
12 0 2 0 1 0
36 3 4 0 0 1
x3
x4
x5
0
0
0
0 3 5 0 0 0
-
12/2=6
36/4=9
m
i
ijBjj aCC i
1
'?
上海财经大学国际工商管理学院
SHUFE
51
第二节 表格单纯形法检验数?j
8 1 0 1 0 0
6 0 1 0 1/2 0
12 3 0 0 -2 1
x3
x2
x5
0
5
0
-30 3 0 0 -5/2 0
8
-
4
Cj 比值CB XB b
检验数?j
x1 x2 x3 x4 x5
3 5 0 0 0
8 1 0 1 0 0
12 0 2 0 1 0
36 3 4 0 0 1
x3
x4
x5
0
0
0
0 3 5 0 0 0
-
12/2=6
36/4=9
上海财经大学国际工商管理学院
SHUFE
52
第二节 表格单纯形法
Cj 比值CB XB b
检验数?j
x1 x2 x3 x4 x5
3 5 0 0 0
8 1 0 1 0 0
6 0 1 0 1/2 0
12 3 0 0 -2 1
x3
x2
x5
0
5
0
-30 3 0 0 -5/2 0
8
-
4
检验数?j
4 0 0 1 2/3 -1/3
6 0 1 0 1/2 0
4 1 0 0 -2/3 1/3
x3
x2
x1
0
5
3
-42 0 0 0 -1/2 -1
最优解,X*=(4,6,4,0,0)T,Z*=42
上海财经大学国际工商管理学院
SHUFE
53
第二节 表格单纯形法
最优基
Cj 3 5 0 0 0 比值CB XB b x1 x2 x3 x4 x5
0 x3 4 0 0 1 2/3 -1/3
5 x2 6 0 1 0 1/2 0
3 x1 4 1 0 0 -2/3 1/3
检验数?j -42 0 0 0 -1/2 -1
340
020
101
*B
x3 x2 x1
3
1
3
2
0
0
2
1
0
3
1
3
2
1
1*
B
最优基的逆
最优基和最优基的逆上海财经大学国际工商管理学院
SHUFE
54
第二节 表格单纯形法
例如
maxZ= 3x1 +2 x2
-2x1 + x2 ≤2
x1 -3 x2 ≤3
x1,x2≥0
S.t.
标准化
maxZ= 3x1 +2 x2
-2x1 + x2 + x3 =2
x1 -3 x2 + x4 =3
x1,x2,x3,x4≥0
Cj 比值CB XB b
检验数?j
x1 x2 x3 x4
3 2 0 0
2 -2 1 1 0
3 1 -3 0 1
x3
x4
0
0
0 3 2 0 0
-
3
检验数?j
8 0 -5 1 2x3
x1
0
3
-
-3 1 -3 0 1
-9 0 11 0 -3
此时,检验数?2=11＞ 0，还没有得到最优解。
确定 x2进基，但 x2所在列的系数向量元素非正，无界
值不存在，有进基变量但无离基变量。
上海财经大学国际工商管理学院
SHUFE
55
第三节 人工变量问题
用单纯形法解题时，需要有一个单位阵作为初始基。
当约束条件都是,≤”时，加入松弛变量就形成了初始基。
但实际存在,≥”或“＝”型的约束，没有现成的单位矩阵。
一、人工变量
采用人造基的办法,人工构造单位矩阵
在没有单位列向量的等式约束中加入人工变量，构成原线性规划问题的伴随问题，从而得到一个初始基。
人工变量是在等式中人为加进的，只有它等于 0时，约束条件才是它本来的意义。
处理方法有两种：
大 M 法
两阶段法上海财经大学国际工商管理学院
SHUFE
56
第三节 人工变量问题
没有单位矩阵，不符合构造初始基的条件，需加入人工变量 。
人工变量最终必须等于 0才能保持原问题性质不变。
为保证人工变量为 0，在目标函数中令其系数为 -M。
M为无限大的正数，这是一个惩罚项，倘若人工变量不为零，
则目标函数就永远达不到最优，所以必须将人工变量逐步从基变量中替换出去。
如若到最终表中人工变量仍没有置换出去，那么这个问题就没有可行解，当然亦无最优解。
大 M法例如 maxZ= 3x1 - x2 -2 x3
3x1 + 2 x2 -3 x3 =6
x1 - 2 x2 + x3 =4
x1,x2,x3≥0
S.t.
上海财经大学国际工商管理学院
SHUFE
57
第三节 人工变量问题
按大 M法构造人造基，引入人工变量 x4,x5 的辅助问题如下：
maxZ= 3x1 - x2 -2 x3 -M x4 -M x5
3x1 + 2 x2 -3 x3 + x4 =6
x1 - 2 x2 + x3 + x5 =4
x1,x2,x3,x4,x5≥0
Cj 比值CB XB b
检验数?j
x1 x2 x3 x4 x5
3 -1 -2 -M -M
6 3 2 -3 1 0
4 1 -2 1 0 1
-10M 3+4M -1 -2-2M 0 0
x4
x5
-M
-M
2
4
m
i
ijBjj aCC i
1
'?
上海财经大学国际工商管理学院
SHUFE
58
第三节 人工变量问题
Cj 比值CB XB b
检验数?j
x1 x2 x3 x4 x5
3 -1 -2 -M -M
6 3 2 -3 1 0
4 1 -2 1 0 1
3+4M -1 -2-2M 0 0
x4
x5
-M
-M
2
4
检验数?j
2 1 2/3 -1 1/3 0
2 0 -8/3 2 -1/3 1
0 -3-8M/3 1+2M -1-4M/3 0
x1
x5
3
-M
-
1
检验数?j
3 1 -2/3 0 1/6 1/2
1 0 -4/3 1 -1/6 1/2
0 -5/3 0 -M-5/6 -M-1/2
x1
x3
3
-2
上海财经大学国际工商管理学院
SHUFE
59
第四节 单纯形法补遗
进基变量相持：
单纯形法运算过程中,同时出现多个相同的?j最大 。
在符合要求的?j(目标为 max,?j＞ 0,min,?j＜ 0)中,选取下标最小的非基变量为换入变量；
离基变量相持：
单纯形法运算过程中,同时出现多个相同的最小 θ值 。
继续迭代,便有基变量为 0,称这种情况为 退化解 。
选取其中下标最大的基变量做为换出变量 。
多重最优解：
最优单纯形表中,存在非基变量的检验数?j=0。
让这个 非基变量进基,继续迭代,得另一个最优解 。
无界解：
大于 0的检验数中,若某个?k所对应的系数列向量 Pk′≤0,则解无界 。
无可行解：
最终表中存在人工变量是基变量 。
上海财经大学国际工商管理学院
SHUFE
60
第三章 对偶理论
若例 1中该厂的产品平销,现有另一企业想租赁其设备 。 厂方为了在谈判时心中有数,需掌握设备台时费用的最低价码,以便衡量对方出价,对出租与否做出抉择 。
在这个问题上厂长面临着两种选择：自行生产或出租设备 。 首先要弄清两个问题：
① 合理安排生产能取得多大利润?
② 为保持利润水平不降低,资源转让的最低价格是多少？
问题 ① 的最优解,x1=4,x2=6,Z*=42。
一、对偶问题上海财经大学国际工商管理学院
SHUFE
61
第三章 对偶理论第二个问题：出让定价
假设出让 A,B,C设备所得利润分别为 y1,y2,y3
原本用于生产甲产品的设备台时，如若出让，不应低于自行生产带来的利润，否则宁愿自己生产。于是有
y1+0y2+3y3≥ 3
同理，对乙产品而言，则有
0y1+2y2+4y3≥ 5
设备台时出让的收益（希望出让的收益最少值）
min?=8y1+12y2+36y3
显然还有
y1,y2,y3≥0
上海财经大学国际工商管理学院
SHUFE
62
第三章 对偶理论
对偶问题的最优解,y1=0,y2=1/2,y3=1,W* =42
两个问题的目标函数值相等，这不是偶然的，上述两个问题实际上是一个问题的两个方面，如果把前者称为线性规划原问题，则后者便是它的对偶问题，反之亦然。
对偶问题的最优解对应于原问题最优单纯型法表中，初始基变量的检验数的负值。
例 1的对偶问题的数学模型
min?=8y1+12y2+36y3
y1+ 0y2+ 3y3≥ 3
0y1+ 2y2+ 4y3≥ 5
y1,y2,y3≥0
S.t.
maxZ= 3x1 +5 x2
x1 ≤8
2x2 ≤12
3x1 +4 x2 ≤36
x1,x2≥0
S.t.
上海财经大学国际工商管理学院
SHUFE
63
第三章 对偶理论
这说明 yi是右端项 bi每增加一个单位对目标函数 Z的贡献 。
对偶变量 yi在经济上表示原问题第 i种资源的 边际价值 。
对偶变量的值 yi*所表示的第 i种资源的边际价值,称为 影子价值 。
若原问题的价值系数 Cj表示单位产值,则 yi称为 影子价格 。
若原问题的价值系数 Cj表示单位利润,则 yi称为 影子利润 。
二、对偶问题的经济解释
n
j
m
i
iijj ybxcZ
1 1
i
i
y
b
Z?
上海财经大学国际工商管理学院
SHUFE
64
第三章 对偶理论
影子价格不是资源的实际价格,而是资源配置结构的反映,
是在其它数据相对稳定的条件下某种资源增加一个单位导致的目标函数值的增量变化 。
对资源 i总存量的评估,购进 or 出让
对资源 i当前分配量的评估,增加 or 减少
① 它表明了当前的资源配置状况,告诉经营者应当优先增加何种资源,才能获利更多 。
② 告诉经营者以怎样的代价去取得紧缺资源 。
③ 提示设备出租或原材料转让的基价 。
④ 告诉经营者补给紧缺资源的数量,不要盲目大量补给 。
⑤ 借助影子价格进行内部核算 。
特别注意上海财经大学国际工商管理学院
SHUFE
65
第四章 灵敏度分析
线性规划研究的是一定条件下的最优化问题,采用优化方案可以达到节约资源,提高效益的目的,但是对,优化方案,
必须要有全面的认识,不可机械地对待 。
优化方案是建立在特定的资源环境和技术条件之上的,而环境和条件总是处在不断地变化之中,如产品价格,原材料成本,
加工技术水平,资源消耗系数等时有波动,所以优化方案是个相对稳定的概念 。 当基础数据发生变化时,最优方案也就变了 。
基础数据往往是测算估计的数值,虽然在运算过程中要求十分严格,但基础数据的误差是不可避免的 。 为了对优化结果有更全面的了解和恰当的运用,就需要进行灵敏度分析 。
灵敏度分析的意义上海财经大学国际工商管理学院
SHUFE
66
第四章 灵敏度分析
灵敏度分析又称敏感性分析或优化后分析，它研究基础数据发生波动后对最优解的影响，以及在多大的范围内波动才不影响最优基。
灵敏度分析就是研究最优解对数据变化的敏感程度。
感性太强，则说明最优解的稳定性程度较低。
灵敏度分析解决的问题：
参数在什么范围变化而最优基不变。
已知参数的变化范围，考察最优解 (最优基 )是否改变 。
灵敏度分析的概念上海财经大学国际工商管理学院
SHUFE
67
第四章 灵敏度分析
价值系数 Cj变化影响检验数
参数 Cj
m
i
ijBjj aCC i
1
'?
上海财经大学国际工商管理学院
SHUFE
68
第四章 灵敏度分析
非基变量 Cj的变化范围
非基变量 Cj变化，只影响它自己的检验数
Cj 3 5 0 0 0 比值CB XB b x1 x2 x3 x4 x5
0 x3 4 0 0 1 2/3 -1/3
5 x2 6 0 1 0 1/2 0
3 x1 4 1 0 0 -2/3 1/3
检验数?j 0 0 0 -1/2 -1
0
)(
*
1
'
1
'
jj
m
i
ijBjj
m
i
ijBjj
C
aCCC
aCC
i
i
*jjC即上海财经大学国际工商管理学院
SHUFE
69
第四章 灵敏度分析
基变量 CBl的变化范围
Cj C1 5 0 0 0 比值CB XB b x1 x2 x3 x4 x5
0 x3 4 0 0 1 2/3 -1/3
5 x2 6 0 1 0 1/2 0
C1 x1 4 1 0 0 -2/3 1/3
检验数?j 0 0 0 -2C1/3+5/2 -C1/3
4
1500
1 cj?
上海财经大学国际工商管理学院
SHUFE
70
第四章 灵敏度分析
4
6
4
3
1
3
2
0
0
2
1
0
3
1
3
2
1
*1* bB
例如
参数 bi
0
)(
1*
11
1
1
bBb
bBbB
bbB
bBX B
上海财经大学国际工商管理学院
SHUFE
71
第四章 灵敏度分析
3
3
3
1*
3
3
1
0
3
1
0
0
3
1
3
2
0
0
2
1
0
3
1
3
2
1
0
0
b
b
b
bB
b
b
120
3
1
4
120
3
1
4
33
33
bb
bb
