运筹学
OPERATIONAL RESEARCH
--
第一章 线性规划及单纯形法
--
2
第一节 线性规划问题及其数学模型
第二节 图解法
第三节 单纯形法原理
第四节 单纯形法计算步骤
第五节 第六节 第七节
单纯形法的进一步讨论 数据包络分析 其他应用例子
--
第一节 线性规划问题及其数学模型
一、问题的提出 二、线性规划问题的与模型 三、线性规划的数学模型 四、线性规划模型的应用 五、线性规划问题的标准形式
a 确定性：线性规划中的参数 ij , bi , ci为确定值
--
三、线性规划问题的标准形式
线性规划的标准化
一般形式
目标函数： 约束条件：
标准形式
目标函数： 约束条件：
Max （Min） z = c1 x1 + c2 x2 + … + cn xn s.t. a11 x1 + a12 x2 + … + a1n xn ≤ （ =, ≥ ）b1
--
x11
x 21
x 31
x 41
Ⅰ
Ⅱ
Ⅲ
Ⅳ
Ⅴ
x12
x32
x13
x22
x14
x 23
∑≥15
∑≥10
∑≥20
∑≥12
x11 x12 x13 x14 15 x 1 3x 1 4x 2 2x 2 3x 3 1x 3 220
x 1 2x 1 3x 1 4x 2 1x 2 2x 2 310
x14 x23 x32 x41 12
--
n
max(mZin ) CjXj j1
n
j1
aij X
j bi (i
1,2,
, m)
X j 0( j 1,2, , n)
目标函数 价值系数
技术系数 右端项常数
--
决策变量
（二）隐含的假设
比例性：决策变量变化引起目标的改变量与决策变量改 变量成正比 可加性：每个决策变量对目标和约束的影响独立于其它 变量 连续性：每个决策变量取连续值
决策变量：向量(x1… xn)T 决策人要考虑和控制的
因素非负 约束条件：线性等式或不等式
目标函数：Z=ƒ(x1 … xn) 线性式，求Z极大或极小
--
（一）一般式
Max(min)Z=C1X1+ C2X2+…+CnXn a11X1+ a12X2+…+ a1nXn (=, )b1 a21X1+ a22X2+…+ a2nXn (=, )b2 ……… am1X1+ am2X2+…+ amnXn (=, )bm Xj 0(j=1,…,n)
最优解的目标函数值却相差一个符号，即 Min f ＝ - Max z
--
三、线性规划问题的标准形式
2、约束条件不是等式的问题： 设约束条件为 ai1 x1+ai2 x2+ … +ain xn ≤ bi 可以引进一个新的变量s ，使它等于约束右边与左
边之差 s=bi–(ai1 x1 + ai2 x2 + … + ain xn )
显然，s 也具有非负约束，即s≥0， 这时新的约束条件成为 ai1 x1+ai2 x2+ … +ain xn+s = bi
--
三、线性规划问题的标准形式
当约束条件为
ai1 x1+ai2 x2+ … +ain xn ≥ bi 时，
类似地令
s=(ai1 x1+ai2 x2+ … +ain xn)- bi 显然，s 也具有非负约束，即s≥0，这时新的约
--
一、问题提出 例1生产计划问题
Ⅰ
设备A
0
设备B
6
调试工序 1
利润
2
Ⅱ 每天可用能力
5
各生产多少, 可获最大利润?
--
解:设两种家电产量分别为变量x1 ， x2
max Z= 2x1 +x2 5x2 15
6x1 + 2x2 24 x1 + x2 5 x1，x2 0
Z2800(x1 1x2 1x3 1x4)14500(x12x22x32)6000(x13x23)730x014
--
经过上面的讨论，得到下面的LP模型：
目标函数 m Z 2 i( x n 1 8 x 1 2 0 x 1 3 x 1 0 4 ) 1 4( x 1 5 x 2 2 0 x 2 3 )
束条件成为
ai1 x1+ai2 x2+ … +ain xn-s = bi
--
三、线性规划问题的标准形式
对于各种非标准形式的线性规划问题，我们总可 以通过以下变换，将其转化为标准形式:
--
三、线性规划问题的标准形式
1.极小化目标函数的问题： 设目标函数为 Min f = c1x1 + c2x2 + … + cnxn (可以)令 z ＝ -f ， 则该极小化问题与下面的极大化问题有相同的最优解，
即 Max z = - c1x1 - c2x2 - … - cnxn 但必须注意，尽管以上两个问题的最优解相同，但它们
--
LP问题的三要素 1、决策变量x1 ， x2
2、目标函数max Z= 2x1 +x2 5x2 15
3、约束条件 6x1 + 2x2 24 x1 + x2 5 x1，x2 0
--
例2
--
例2
解：设x ij 表示捷运公司在第i (i=1,2,3,4)月初签订的租期为j
(j=1,2,3,4)个月的仓库面积的合同（单位为100m2)。
约束条件
60(x 013 0x2)373x1 040
x11 x12 x13 x14
st.xx1132xx1143xx1242
x21 x23
x14 x23 x32 x41
xij 0(i 1, ,4;
15 x22 x31 12 j 1,
x23 x32
,4)
10 20
--
二、线性规划模型特点
a21 x1 + a22 x2 + … + a2n xn ≤ （ =, ≥ ）b2 …… …… am1 x1 + am2 x2 + … + amn xn ≤ （ =, ≥ ）bm x1 ，x2 ，… ，xn ≥ 0
Max z = c1 x1 + c2 x2 + … + cn xn s.t. a11 x1 + a12 x2 + … + a1n xn = b1
a21 x1 + a22 x2 + … + a2n xn = b2 …… …… am1 x1 + am2 x2 + … + amn xn = bm
x1 ，x2 ，… ，xn ≥ 0，bi ≥0
--
三、线性规划问题的标准形式
可以看出，线性规划的标准形式有如下四个特 点：
目标最大化； 约束为等式； 决策变量均非负； 右端项非负。