管理运筹学谢家平 博士 副教授研究领域,系统建模与优化、生产与运作管理、物流与供应链管理讲授课程,管理运筹学、管理系统工程、生产运作管理、
供应链管理、国际物流管理、企业资源计划单 位,上海财经大学 国际工商管理学院 供应链管理研究中心
E-mail,jiaping_xie@sina.com.cn
电 话,55036936(H) 65903541(O)
上海财经大学国际工商管理学院
SHUFE
2
线性规划问题
线性规划主要解决有限资源的最佳分配问题
决策变量的取值要求非负 。
存在一组决策变量构成的线性等式或不等式的约束条件 。
存在唯一的线性目标函数 （ 极大或极小 ） 。
求解方法：
图解法
单纯形解法上海财经大学国际工商管理学院
SHUFE
3
线性规划的一般模型
例 1.生产计划问题某厂生产甲乙两种产品,各自的零部件分别在 A,B车间生产,最后都需在 C车间装配,相关数据如表所示：
问如何安排甲、乙两产品的产量，使利润为最大。
线性规划模型的构建产品资源工时单耗甲 乙生产能力
A
B
C
1 0
0 2
3 4
8
12
36
单位产品获利 3 5
上海财经大学国际工商管理学院
SHUFE
4
线性规划的一般模型
(1)决策变量,设 x1为甲产品产量,x2为乙产品产量 。
(2)约束条件,A车间能力约束 x1 ≤8
B车间能力约束 2x2 ≤12
C车间能力约束 3x1 +4 x2 ≤36
(3)目标函数,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
建立模型上海财经大学国际工商管理学院
SHUFE
5
线性规划问题的图解法
线性规划的图解法
例 1的数学模型为
maxZ= 3x1 +5 x2
x1 ≤8
2x2 ≤12
3x1 +4 x2 ≤36
x1 ≥0,x2 ≥0
S.t.
最优解：可行解中使目标函数最优 (极大或极小 )的解。
最优值一定在可行域的边界达到，而不可能在其内部。
满足所有约束条件的解的集合，称之为可行域。
所有约束条件共同围城的区域。
Z=30 Z=42
Z=15
x1 =8
2x2 =12
3x1 +4 x2 =36
x1
x2
4 8 12
3
6
9
0 A
B
C(4,6)D
上海财经大学国际工商管理学院
SHUFE
6
线性规划问题的图解法
唯一最优解：只有一个最优点 。
多重最优解
两个顶点同是最优解,其连线上的每一点都是最优解,即无穷多个最优解 。
判据,最优单纯形表中存在非基变量的检验数等于?k= 0。
无界解
LP问题的可行域无界,目标函数无限增大,缺乏必要的约束 。
判据,若某个?k ≥0所对应的系数列向量 Pk′≤0（ 有进基变量但无离基变量 ）,则是无界解 。
无可行解
若约束条件相互矛盾,则可行域为空集 。
判据,最终单纯形表中人工变量仍没有置换出去,则 没有可行解 。
解的可能性上海财经大学国际工商管理学院
SHUFE
7
线性规划标准型
标准型
目标函数极大化,
约束条件为等式,
右端常数项 bi≥0，
决策变量非负 。
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
8
线性规划标准型
目标函数极小化问题只需将目标等式两端乘以 -1即变为极大化问题 。
右端常数项非正将约束等式两端同乘以 -1
约束条件为不等式
当约束方程为,≤”时，左端加入一个非负的松弛变量；
当约束条件为,≥”时，不等式左端减去一个非负的剩余变量
(也可称松弛变量 )即可。
决策变量 xk没有非负性要求令 xk=xk′-x k〃,xk=xk′,x k〃 ≥0，
用 xk′,x k〃 取代模型中 xk
非标准型向标准型转化上海财经大学国际工商管理学院
SHUFE
9
线性规划解的概念
基
m个线性无关的约束方程，称为一个基，用 B表示。
称基矩阵的列为基向量，用 Pj表示 (j=1,2,…,m ) 。
基变量
与基向量 Pj相对应的 m个变量 xj称为基变量
其余的 m-n个变量为非基变量。
线性规划解的概念
1
0
0
0
1
0
043
020
101
A
x1 x2 x3 x4 x5
单位矩阵? 基解
令所有非基变量等于零，求出基变量的值，
基解是各约束方程及坐标轴之间交点的坐标。
基可行解：满足非负性约束的基解。
最优基：最优解对应的基矩阵，称为最优基。
上海财经大学国际工商管理学院
SHUFE
10
表格单纯形法
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
上海财经大学国际工商管理学院
SHUFE
11
表格单纯形法
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
检验数?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
12
表格单纯形法
最优基
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
13
表格单纯形法
单纯形法的几何意义
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
线性规划的解题思路
线性规划问题可以有无数个可行解,最优解只可能在顶点上达到 。
顶点对应的是基可行解,故只要在有限个基可行解中寻求最优解 。
从一个顶点出发找到一个可行基,得到一组基可行解,
以目标函数做尺度衡量是否最优：若不是,则向邻近的顶点转移,换一个基再求解,检验,如此迭代使目标值逐步改善,直至求得最优解 。
340
020
101
*B
x3 x2 x1
100
010
001
0B
x3 x4 x5
140
020
001
1B
x3 x2 x5
上海财经大学国际工商管理学院
SHUFE
14
人工变量问题
没有单位列向量的约束方程，需加入人工变量 。
人工变量最终必须等于 0才能保持原问题性质不变，在目标函数中令其系数为 -M。
M为无限大的正数，若人工变量不为 0，则目标函数永远达不到最优，所以必须将人工变量逐步从基变量中替换出去。
如若到最终表中人工变量仍没有置换出去，那么这个问题就没有可行解，当然亦无最优解。
大 M
例如 maxZ= 3x1 - x2 -2 x3
3x1 + 2 x2 -3 x3 =6
x1 - 2 x2 + x3 =4
x1,x2,x3 ≥0
S.t.
上海财经大学国际工商管理学院
SHUFE
15
人工变量问题
按大 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
上海财经大学国际工商管理学院
SHUFE
16
人工变量问题
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
17
对偶理论
对偶问题的最优解对应于原问题最优单纯型法表中，初始基变量的检验数的负值。
对偶问题的最优解,y1=0,y2=1/2,y3=1,W* =42
例 1的对偶问题的数学模型
min?=8y1+12y2+36y3
y1+ 0y2+ 3y3≥ 3
0y1+ 2y2+ 3y3≥ 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
18
对偶理论
这说明 yi是右端项 bi每增加一个单位对目标函数 Z的贡献。
对偶变量的值 yi*所表示的第 i种资源的边际价值，称为影子价值。
若原问题的价值系数 Cj表示单位产值,则 yi称为影子价格 。
若原问题的价值系数 Cj表示单位利润,则 yi称为影子利润 。
影子价格不是资源的实际价格,而是资源配置结构的反映,是在其它数据相对稳定的条件下某种资源增加一个单位导致的目标函数值的增量变化 。
对资源 i总存量的评估,购进 or 出让
对资源 i当前分配量的评估,增加 or 减少
对偶问题的经济解释
n
j
m
i
iijj ybxcZ
1 1
i
i
ybZ
供应链管理、国际物流管理、企业资源计划单 位,上海财经大学 国际工商管理学院 供应链管理研究中心
E-mail,jiaping_xie@sina.com.cn
电 话,55036936(H) 65903541(O)
上海财经大学国际工商管理学院
SHUFE
2
线性规划问题
线性规划主要解决有限资源的最佳分配问题
决策变量的取值要求非负 。
存在一组决策变量构成的线性等式或不等式的约束条件 。
存在唯一的线性目标函数 （ 极大或极小 ） 。
求解方法：
图解法
单纯形解法上海财经大学国际工商管理学院
SHUFE
3
线性规划的一般模型
例 1.生产计划问题某厂生产甲乙两种产品,各自的零部件分别在 A,B车间生产,最后都需在 C车间装配,相关数据如表所示：
问如何安排甲、乙两产品的产量，使利润为最大。
线性规划模型的构建产品资源工时单耗甲 乙生产能力
A
B
C
1 0
0 2
3 4
8
12
36
单位产品获利 3 5
上海财经大学国际工商管理学院
SHUFE
4
线性规划的一般模型
(1)决策变量,设 x1为甲产品产量,x2为乙产品产量 。
(2)约束条件,A车间能力约束 x1 ≤8
B车间能力约束 2x2 ≤12
C车间能力约束 3x1 +4 x2 ≤36
(3)目标函数,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
建立模型上海财经大学国际工商管理学院
SHUFE
5
线性规划问题的图解法
线性规划的图解法
例 1的数学模型为
maxZ= 3x1 +5 x2
x1 ≤8
2x2 ≤12
3x1 +4 x2 ≤36
x1 ≥0,x2 ≥0
S.t.
最优解：可行解中使目标函数最优 (极大或极小 )的解。
最优值一定在可行域的边界达到，而不可能在其内部。
满足所有约束条件的解的集合，称之为可行域。
所有约束条件共同围城的区域。
Z=30 Z=42
Z=15
x1 =8
2x2 =12
3x1 +4 x2 =36
x1
x2
4 8 12
3
6
9
0 A
B
C(4,6)D
上海财经大学国际工商管理学院
SHUFE
6
线性规划问题的图解法
唯一最优解：只有一个最优点 。
多重最优解
两个顶点同是最优解,其连线上的每一点都是最优解,即无穷多个最优解 。
判据,最优单纯形表中存在非基变量的检验数等于?k= 0。
无界解
LP问题的可行域无界,目标函数无限增大,缺乏必要的约束 。
判据,若某个?k ≥0所对应的系数列向量 Pk′≤0（ 有进基变量但无离基变量 ）,则是无界解 。
无可行解
若约束条件相互矛盾,则可行域为空集 。
判据,最终单纯形表中人工变量仍没有置换出去,则 没有可行解 。
解的可能性上海财经大学国际工商管理学院
SHUFE
7
线性规划标准型
标准型
目标函数极大化,
约束条件为等式,
右端常数项 bi≥0，
决策变量非负 。
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
8
线性规划标准型
目标函数极小化问题只需将目标等式两端乘以 -1即变为极大化问题 。
右端常数项非正将约束等式两端同乘以 -1
约束条件为不等式
当约束方程为,≤”时，左端加入一个非负的松弛变量；
当约束条件为,≥”时，不等式左端减去一个非负的剩余变量
(也可称松弛变量 )即可。
决策变量 xk没有非负性要求令 xk=xk′-x k〃,xk=xk′,x k〃 ≥0，
用 xk′,x k〃 取代模型中 xk
非标准型向标准型转化上海财经大学国际工商管理学院
SHUFE
9
线性规划解的概念
基
m个线性无关的约束方程，称为一个基，用 B表示。
称基矩阵的列为基向量，用 Pj表示 (j=1,2,…,m ) 。
基变量
与基向量 Pj相对应的 m个变量 xj称为基变量
其余的 m-n个变量为非基变量。
线性规划解的概念
1
0
0
0
1
0
043
020
101
A
x1 x2 x3 x4 x5
单位矩阵? 基解
令所有非基变量等于零，求出基变量的值，
基解是各约束方程及坐标轴之间交点的坐标。
基可行解：满足非负性约束的基解。
最优基：最优解对应的基矩阵，称为最优基。
上海财经大学国际工商管理学院
SHUFE
10
表格单纯形法
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
上海财经大学国际工商管理学院
SHUFE
11
表格单纯形法
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
检验数?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
12
表格单纯形法
最优基
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
13
表格单纯形法
单纯形法的几何意义
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
线性规划的解题思路
线性规划问题可以有无数个可行解,最优解只可能在顶点上达到 。
顶点对应的是基可行解,故只要在有限个基可行解中寻求最优解 。
从一个顶点出发找到一个可行基,得到一组基可行解,
以目标函数做尺度衡量是否最优：若不是,则向邻近的顶点转移,换一个基再求解,检验,如此迭代使目标值逐步改善,直至求得最优解 。
340
020
101
*B
x3 x2 x1
100
010
001
0B
x3 x4 x5
140
020
001
1B
x3 x2 x5
上海财经大学国际工商管理学院
SHUFE
14
人工变量问题
没有单位列向量的约束方程，需加入人工变量 。
人工变量最终必须等于 0才能保持原问题性质不变，在目标函数中令其系数为 -M。
M为无限大的正数，若人工变量不为 0，则目标函数永远达不到最优，所以必须将人工变量逐步从基变量中替换出去。
如若到最终表中人工变量仍没有置换出去，那么这个问题就没有可行解，当然亦无最优解。
大 M
例如 maxZ= 3x1 - x2 -2 x3
3x1 + 2 x2 -3 x3 =6
x1 - 2 x2 + x3 =4
x1,x2,x3 ≥0
S.t.
上海财经大学国际工商管理学院
SHUFE
15
人工变量问题
按大 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
上海财经大学国际工商管理学院
SHUFE
16
人工变量问题
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
17
对偶理论
对偶问题的最优解对应于原问题最优单纯型法表中，初始基变量的检验数的负值。
对偶问题的最优解,y1=0,y2=1/2,y3=1,W* =42
例 1的对偶问题的数学模型
min?=8y1+12y2+36y3
y1+ 0y2+ 3y3≥ 3
0y1+ 2y2+ 3y3≥ 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
18
对偶理论
这说明 yi是右端项 bi每增加一个单位对目标函数 Z的贡献。
对偶变量的值 yi*所表示的第 i种资源的边际价值，称为影子价值。
若原问题的价值系数 Cj表示单位产值,则 yi称为影子价格 。
若原问题的价值系数 Cj表示单位利润,则 yi称为影子利润 。
影子价格不是资源的实际价格,而是资源配置结构的反映,是在其它数据相对稳定的条件下某种资源增加一个单位导致的目标函数值的增量变化 。
对资源 i总存量的评估,购进 or 出让
对资源 i当前分配量的评估,增加 or 减少
对偶问题的经济解释
n
j
m
i
iijj ybxcZ
1 1
i
i
ybZ
