管理运筹学讲义：线性规划（复习）.ppt

管理运筹学
谢家平博士副教授
研究领域:系统建模与优化、生产与运作管理、物流与供应链管理
讲授课程:管理运筹学、管理系统工程、生产运作管理、
供应链管理、国际物流管理、企业资源计划
单位:上海财经大学国际工商管理学院供应链管理研究中心
E-mail:jiaping_xie@
电话:55036936(H) 65903541(O)
1
线性规划问题
线性规划主要解决有限资源的最佳分配问题
决策变量
决策变量的取值要求非负。
约束条件
存在一组决策变量构成的线性等式或不等式的约束条件。
目标函数
存在唯一的线性目标函数(极大或极小)。
求解方法:
图解法
单纯形解法
2
线性规划的一般模型

某厂生产甲乙两种产品,各自的零部件分别在A、B车间生产,最后都需在C车间装配,相关数据如表所示:
问如何安排甲、乙两产品的产量,使利润为最大。
线性规划模型的构建
产品
资源
工时单耗
甲乙
生产能力
A
B
C
1 0
0 2
3 4
8
12
36
单位产品获利
3 5
3
线性规划的一般模型
(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
建立模型
4
线性规划问题的图解法
线性规划的图解法
例1的数学模型为
maxZ= 3x1 +5 x2
x1 ≤8
2x2 ≤12
3x1 +4 x2 ≤36
x1 ≥0, x2 ≥0
.
最优解:可行解中使目标函数最优(极大或极小)的解。
最优值一定在可行域的边界达到,而不可能在其内部。
满足所有约束条件的解的集合,称之为可行域。
所有约束条件共同围城的区域。
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
5
线性规划问题的图解法
唯一最优解:只有一个最优点。
多重最优解
两个顶点同是最优解,其连线上的每一点都是最优解,即无穷多个最优解。
判据:最优单纯形表中存在非基变量的检验数等于k = 0。
无界解
LP问题的可行域无界,目标函数无限增大,缺乏必要的约束。
判据:若某个k ≥0所对应的系数列向量Pk′≤0(有进基变量但无离基变量),则是无界解。
无可行解
若约束条件相互矛盾,则可行域为空集。
判据:最终单纯形表中人工变量仍没有置换出去,则没有可行解。
解的可能性
6
线性规划标准型
标准型
目标函数极大化,
约束条件为等式,
右端常数项bi≥0,
决策变量非负。
maxZ=c1x1+c2x2+…+cnxn
a11x1+a12x2+…+a1nxn =b1
a21x1+a22x2+…+a2nxn =b2
……………
am1x1+am2x2+…+amnxn=bm
x1,x2,…,xn ≥0
maxZ= cjxj
aijxj=bi ( i=1,2,…,m)
xj≥0 ( j=1,2,…,n)
简记
7
线性规划标准型
目标函数极小化问题
只需将目标等式两端乘以-1 即变为极大化问题。
右端常数项非正
将约束等式两端同乘以-1
约束条件为不等式
当约束方程为“≤”时,左端加入一个非负的松弛变量;
当约束条件为“≥”时,不等式左端减去一个非负的剩余变量(也可称松弛变量)即可。
决策变量xk没有非负性要求
令xk=xk′-x k〃, xk=xk′,x k〃≥0, 用xk′、x k〃取代模型中xk
非标准型向标准型转化
8
线性规划解的概念
基
m个线性无关的约束方程,称为一个基,用B表示。
称基矩阵的列为基向量,用Pj表示(j=1,2,…,m) 。
基变量
与基向量Pj相对应的m个变量xj称为基变量
其余的m-n个变量为非基变量。
线性规划解的概念
x1
x2
x3
x4
x5
单位矩阵
基解
令所有非基变量等于零,求出基变量的值,
基解是各约束方程及坐标轴之间交点的坐标。
基可行解:满足非负性约束的基解。
最优基:最优解对应的基矩阵,称为最优基。
9
表格单纯形法
maxZ=3x1 +5 x2 +0x3 +0x4+0x5 =0
x1 + x3 =8
2x2 + x4 =1