文档介绍：线性规划与单纯形法简介
第一章线性规划及单纯形法
线性规划（Linear Programming，简称LP）
运筹学的一个重要分支，是运筹学中研究较早、发展较
快、理论上较成熟和应用上极为广泛的一个分支。
1947年G. )
（i = 1,2,…,m）
xj≥0 （j = 1,2,…,n）
0≤ xj ≤lj
§1 线性规划问题及其数学模型
三个基本要素：
Note：
1、善于抓住关键因素，忽略对系统影响不大的因素；
2、可以把一个大系统合理地分解成 n 个子系统处理。
1、决策变量 xj≥0
2、约束条件 —— 一组决策变量的线性等式或不等式
3、目标函数 —— 决策变量的线性函数
第一章线性规划及单纯形法
max（min）z = c1x1 + c2x2 + … + cnxn
. a11x1 + a12x2 + … + a1nxn ≤（或=，≥）b1
a21x1 + a22x2 + … + a2nxn ≤（或=，≥）b2
… …
am1x1 + am2x2 + … + amnxn ≤（或=，≥）bm
xj ≥ 0 （j = 1,2,…,n）
其中aij、bi、cj（i = 1,2,…,m；j = 1,2,…,n）为已知
常数
线性规划问题的一般形式：
§1 线性规划问题及其数学模型
线性规划问题的标准形式：
max z = c1x1 + c2x2 + … + cnxn
. a11x1 + a12x2 + … + a1nxn = b1
a21x1 + a22x2 + … + a2nxn = b2
… …
am1x1 + am2x2 + … + amnxn = bm
xj ≥ 0 （j = 1,2,…,n）
bi ≥ 0 （i = 1,2,…,m）
特点：
1、目标函数为极
大化；
2、除决策变量的
非负约束外，所有
的约束条件都是等
式，且右端常数均
为非负；
3、所有决策变量
均非负。
第一章线性规划及单纯形法
如何转化为标准形式？
1、目标函数为求极小值，即为：。
因为求 min z 等价于求 max (-z)，令 z’ = - z，
即化为：
2、约束条件为不等式，
xn+1 ≥ 0
松弛变量
如何处理？
§1 线性规划问题及其数学模型
３、右端项bi < 0时，只需将等式两端同乘（-1）
则右端项必大于零
4、决策变量无非负约束
设 xj 没有非负约束，若 xj ≤0，可令 xj = - xj’ ，
则 xj’ ≥0；
又若 xj 为自由变量，即 xj 可为任意实数，
可令 xj = xj’ - xj’’，且 xj’ , xj’’ ≥0
第一章线性规划及单纯形法
. 3
试将 LP 问题
min z = -x1+2x2-3x3
. x1+x2+x3 ≤7
x1-x2+x3 ≥2
-3x1+x2+2x3 = -5
x1,x2 ≥0 化为标准形式。
解：
令 x3= x4 - x5 其中x4、x5 ≥0；
对第一个约束条件加上松弛变量 x6 ；
对第二个约束条件减去松弛变量 x7 ；
对第三个约束条件两边乘以“-1” ；
令 z’=-z 把求 min z 改为求 max z’
max z’= x1-2x2+3x4- 3x5
. x1+x2+x4-x5+x6=7
x1-x2+x4-x5-x7=2
3x1-x2-2x4+2x5=5
x1,x2,x4,x5,x6,x7≥0
§1 线性规划问题及其数学模型
LP的几种表示形式：
§2 线性规划问题的图解法
定义1 在LP 问题中，凡满足约束条件(2)、(3)的
解 x = (x1,x2,…,xn)T 称为LP 问题的可行解，
所有可行解的集合称为可行解集（或可行域）。
记作 D={ x | Ax = b ,x≥0 }。
定义2 设LP问题的可行域为D，若存在x*∈D，使得
对任意的x∈D 都有c x*≥c x，则称x*为LP 问题
的最优解，相应的目标函数值称为最优值，