a1n xn b1 a2n xn b2
am1x1 am2 x2 amn xn bm
x1, x2 , , xn 0
．目标函数 max ．变量 非负 ．约束条件 等式 ．约束常数 非负
Байду номын сангаас
(1.4)
9
例1－3将例1－1的数学模型化为标准型。 Max Z=2x1+3x2 3x2 15 4x1 12 2x1+2x2 14 x1，x2≥0
3
例1－1：（计划安排问题）
I II 设备A(h) 0 3 设备B(h) 4 0 原材料(公斤) 2 2 利润(万元） 2 3
资源总量 15 12 14
max S= 2x1 +3x2 3x2 15
4x1
12
2x1+2x2 14
I,II生产多少, 可获最大利润? x1，x2 0
解:设 计划期内生产产品I、II的数量x1、x2
2. 最优解: 满足约束条件及目标函数的可行解称为线性规划 问题的最优解。
最优值
3. 基: 假设 A 是约束方程组的系数矩阵，其秩数为 m ，B是 矩阵 A 中由 m 列构成的非奇异子矩阵(B的行列式的值不为0)， 则称 B 是线性规划问题的一个基。这就是说，矩阵 B 是由 m 个 线性无关的列向量组成，不失一般性，可假设:
S=CB B-1 b+(CN -CB B-1 N)XN14
若令非基变量 xm+1 = ···= xn = 0 ,用高斯消元法 可求出LP标准型的一个解 X = ( x1 x2 ···xm 0 ···0 )T 称 X 为基本解.
这个解的非0分量的数目不大于方程个数 m.
15
1. 可行解: 满足约束条件的解 X = ( x1, x2, ···, xn) 称为线性规T 划问题的可行解；所有可行解的集合称为可行解集或可行域。
如何从A，B两处采购原油，在满足供应合同的条件下，
使购买成本最小。
油品来源 A
B
成分
min S 200x1 290x2
汽油
15% 50%
0.15x1 0.50x2 15
煤油 重油
20% 30% 50% 15%
0.20x1 0.50x1
0.30x2 0.15x2
12 12
其它
15% 5%
则该问题的数学模型为：
4
例1－2 成本问题
某炼油厂根据每季度需供应给合同单位汽油15万吨、煤油
12万吨、重油12万吨。该厂计划从A，B两处运回原油
提炼，已知两处的原油成分含量见表1－2；又已知从A
处采购的原油价格为每吨（包括运费）200元，B处采购
的原油价格为每吨（包括运费）290元, 问：该炼油厂该
解：引进3个新非负变量x3，x4，x5使不等式变为等式 ，标准型为：
Max Z=2x1+3x2+0·x3+0·x4+0·x5 3x2+x3=15 4x1+x4 =12 2x1+2x2+x5=14 x1，x2，x3，x4，x5≥0
10
例1－4
将 min S = -x1+2x2 –3x3
x1+x2 +x3 7
am1 … amm amm+1 … amn P1 … Pm Pm+1 … Pn
A=[BB N ] N
(m< n) r(A)=m , 至少有一个m 阶子式不为0
不失一般性,不妨假设P1 … Pm线性无关
基阵—A中一个子矩阵B是可逆矩 阵， 则方阵B称为LP问题的一个基。13
有：AX=P1 x1+ P2 x2 + … +Pn xn=b
a11x1+ a12x2+…+ a1nxn (=, )b1 a21x1+ a22x2+…+ a2nxn (=, )b2
………
am1x1+ am2x2+…+ amnxn (=, )bm
xaj110a(12j=…1…,……,na)1n
x1
b1
令 A=
a21 a22 ……… a2n
X= x2 b= b2
… …
…
A= (P1 … Pm Pm+1 … Pn )
=(B N ) 定义：基向量 X= x1 … xm T xm+1 … xn T
非基向量
=(XB XN)T 定义：基变量 非基变量
AX=b 求解 A=(BN) X=(XB XN )T
(BN)
XB XN
=b
BXB +NXN=b
BXB =b-NXN
XB = B-1 b - B-1N XN
11
第二节 线性规划问题的图解法及几何意义
一、线性规划问题的解的概念
n
max Z c j x j j 1
n
aij x j bi
j1
x
j
0
(i 1,2, ,m) ( j 1, 2, , n)
(1.6) (1.7) (1.8)
12
max S=CX
AX =b
X0 Am×n 满秩
a11 … a1m a1m+1 … a1n a21 … a2m a2m+1 … a2n ………… ……………
经济与管理学院 -张凤林
1
授课内容 第一章 线性规划 第二章 对偶单纯形法与灵敏度分析 第三章 运输问题 第四章 整数规划 第五章 动态规划 第六章 图论与网络计划 第七章 存储论 第八章 决策分析
2
第一章 线性规划
第 一 节 线性规划问题及其数学模型
一、线性规划问题的数学模型
主要解决以下两类问题： 1、任务确定后，如何统筹安排，做到应用尽量少的人 力和物力资源来完成任务； 2、在一定量的人力、物力资源的条件下，如何安排、 使用他们，使完成的任务最多。
解：① 令x3 =x4 - x5
x1 -x2 +x3 2 x1，x2 0，x3无限制
② 添加松弛变量x6 ③ 添加剩余变量x7 ④ 令S'= -S
化为标准型
maxS'= x1 –2x2 +3x4 –3x5
x1 +x2 +x4 -x5 +x6=7
x1 -x2 +x4 -x5 -x7 =2
x1 , x2 , x4 , … , x7 0
x1 0, x2 0
5
线性规划模型特点
• 决策变量：向量(x1… xn)T , xi非负 • 约束条件：线性等式或不等式 • 目标函数：Z=ƒ(x1 … xn) 线性式，
求Z极大或极小
满足以上三个条件的数学模型称为 -------线性规划数学模6型
一般形式：
max(min) S=c1x1+ c2x2+…+cnxn
…………………
am1 am2 ………amn m×n
xn
bm
C=(C1 C2 …Cn )
7
矩阵形式：
(目标函数)
(约束条件)
max(min)S CX
AX (或 , )b
s.t
X O
8
二、线性规划问题的标准型
max Z c1x1 c2 x2 cn xn
a11x1 a12 x2 a21x1 a22 x2