安安全全上楼梯幻灯片.pptx

第二章线性规划
Linear Programming
线性规划
线性规划是运筹学中研究较早、应用较广泛、发展较成
熟的一个分支。它有效地解决了生产规划、任务分配以
及配料等的最优化问题。这种最优化方法在油气储运工
程中的应用也较为广泛,如炼厂或商品油库的油品调和
的最优化问题,最优月输油计划、商品油库的最优进货
计划问题等,都可以用线性规划方法解决。单纯形法是
线性规划的主要算法,虽然有人还提出过其他一些算
法,但到目前为止,单纯形法仍然是最有效的算法。本
章重点介绍单纯形法的原理和算法
§ 线性规划问题的一般形式及其标准型
线性规划问题是一类特殊的数学规划问题,其目标函数
是决策变量的线性函数,约束条件是关于决策变量的线
性等式或不等式。线性规划问题的一般形式为:
max(min) S c1 x1 c2 x2 cn xn
a11 x1 a12 x2 a1n xn b1

a x a x a x b
21 1 22 2 2n n 2

.
a x a x a x b
m1 1 m2 2 mn n m
x1 , x2 ,, xn 0
线性规划问题的一般形式及其标准型
n
简写为:
max(min) S c j x j
j1
n
aij x j bi i 1 ~ m
.j1

x j 0 j 1 ~ n
在上述数学模型中, ≥的含义包括≥、=、
≤。为了便于讨论和求解,通常把给定的线
性规划问题都划成如下的标准形式:
线性规划问题的一般形式及其标准型
n
max S c j x j
j1
n
aij x j bi i 1 ~ m
.j1

x j 0 j 1 ~ n
这种形式称为线性规划问题的标准型, 其中
bi≥0(i=1~m)。有些书上规定标准型的目标函数是求 min ,
但这对问题的求解没有本质的影响,因为求min 也可以
转化为求max。
线性规划问题的一般形式及其标准型
标准型的向量形式:
max S CX
n 
Pj x j b

.j1

X 0
其中:C=(c1 , c 2, …, c n ) 称为目标系数行向
量。
线性规划问题的一般形式及其标准型
a
x1 1 j b1 

x a  b
X  2  P  2 j  b  2 
 j 

x b
 n a mj m 
(决策变量列向量) (xj的系数列向量) (右端系数列向量)
标准型的矩阵形式:
max S CX a11 a12  a1n 

 a a  a 
AX b 其中 A 21 22 2n a 
. ij mn
X 0 
am1 am 2  amn 
A称为约束系数矩阵。
线性规划问题的一般形式及其标准型
对于给定的线性规划问题,如果它不符合标准型
的要求,则可通过下述途径将其化为标准型:
1、目标函数为min S
令SS,则min S maxSmax S
n
、约束条件为
2 aij x j bi
j1
在不等式左边加上一个非负变量xni 0,使得
n
aij x j xni bi
j1
xn+i称为松弛变量(slack variable)。
线性规划问题的一般形式及其标准型
n
、约束条件为
3 aij x j bi
j1
在不等式左边减去一个非负变量xni 0,使得
n
aij x j xni bi
j1
xn+i称为剩余变量(surplus variable)。
n
、约束条件为
4 aij x j bi (bi 0)
j 1
在等式两端同乘以-1,则
n

(aij x j ) bi bi (bi 0)
j1
线性规划问题的一般形式及其标准型
5、x j为自由变量,即对 x j的数值无正负要求, x j可正
可负。
为了满足标准型的要求,令
x j xj xj,xj、xj0。
关于松弛变量和剩余