?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
??? ??
?
F u z z y L P
LP
LP
LP
k a r m a r k a r
M
LP
LP
LP
多目标
运输问题
整数
特殊
题经济管理方面的典型问
算法哈奇扬算法、算法复杂性问题
参数规划灵敏度分析
对偶理论
修正单纯形法
进一步讨论
前提？步骤？
（求解）
对偶单纯形法
）
两阶段法
法大
法、人工变量法单纯形法（原始单纯形
图解法
基本方法
要定理解的基本性质：四个主
基本最优解
最优解
基本可行解（重点）
基本解（难点）
可行解（重点）
各种解的概念：）（
数学模型）（
基本概念
模型实际问题
？条件
2
1
线
性
规
划
内
容
框
架
第一章,线性规划
1.1 线性规划的概念
一、线性规划问题的导出
1,(引例 ) 配比问题 ——
用浓度为 45%和 92%的硫酸配置
100t浓度为 80%的硫酸 。
取 45%和 92%的硫酸分别为 x1和 x2t,
则有：
求解一元二次方程组得解。
?
?
?
???
??
1008.092.045.0
100
21
21
xx
xx
目的相同，但有 5种不同浓度的硫
酸可选（ 30%,45%,73%,85%，
92%）会出现什麽情况？
取这 5种硫酸分别为 x1,x2,x3、
x4,x5 t,则有：
?
?
?
??????
?????
1 0 08.092.085.073.045.03.0
1 0 0
54321
54321
xxxxx
xxxxx
· 有多少种配比方案？为什麽？
?
?
?
?
?
??
??????
?????
?????
5,,2,1,0
1008.092.085.073.045.03.0
100
..
250019001400700400
54321
54321
54321
?jx
xxxxx
xxxxx
ts
xxxxxM in Z
j
·何为最好？
5种硫酸价格分别为,400,700,1400，
1900,2500元 /t，则有：
2,生产计划问题：
生产单位 产品
产品所需资源
资 源
A B C 每天可利用
资源量
工时（单位） 1 1 1 3
材料（ t） 1 4 7 9
产品利润
（元 /t） 2000 3000 1000
如何制定生产计划，使三种产品总
利润最大？
问题讨论
?何为生产计划？
?总利润如何描述？
?还要考虑什麽因素？
?有什麽需要注意的地方（技巧）？
?最终得到的数学模型是什麽？
?
?
?
?
?
??
???
???
???
3,2,1,0
974
3
..
32
321
321
321
jx
xxx
xxx
ts
xxxM in Z
j
二、线性规划的定义和数学描述（模型）
1,定义,对于求取一组变量 xj (j =1,2,......,n)，
使之既满足线性约束条件, 又使具有线性表达
式的目标函数取得极大值或极小值的一类最优
化问题称为 线性规划问题, 简称 线性规划 。
2.配比问题和生产计划问题的线性规
划模型的特点：
? 用一组未知变量表示要求的方案, 这组
未知变量称为 决策变量 ；
? 存在一定的 限制条件, 且为线性表达式；
? 有一个 目标要求 （ 最大化, 当然也可以
是最小化 ）, 目标表示为未知变量的线
性表达式, 称之为 目标函数 ；
? 对决策变量有 非负要求 。
3,LP的数学描述 (数学模型 )：
（ 1）一般形式
?
?
?
?
?
?
?
?
?
?
??????
?????
??????
????
0,,,
),(
),(
),(
..
)(
21
2211
22222121
11212111
2211
n
mnmnmm
nn
nn
nn
xxx
bxaxaxa
bxaxaxa
bxaxaxa
ts
xcxcxcZM inM a x
?
?
???
?
?
?或
?
?
?
?
?
??
????
?
?
?
?
?
njx
mibxa
ts
xcZM i nM a x
j
n
j
ijij
n
j
jj
?
?
,2,10
,2,1),(
..
)(
1
1
或
（ 2）紧缩形式
（ 3） 矩阵形式
?
?
?
?
???
?
0
)(
..
)(
X
bAX
ts
CXZM i nM a x 或
其中,
),,( 21 ncccC ??
?? ),,( 21 nxxxX ?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
mnmm
n
n
aaa
aaa
aaa
A
?
????
?
?
21
22221
11211
T
mbbbb ),,,( 21 ??
（ 4） 向量 — 矩阵形式：
?
?
?
?
?
?
???
?
?
?
0
)(
..
)(
1
X
bxP
ts
CXZM inM a x
n
j
jj
或
其中：
njaaaP Tmjjjj,,2,1,),,,( 21 ?? ??
),,,( 21 nPPPA ??
（ 1） P68 习题 1 （ 1-1）
加深理解线性规划的定义
（ 2）复习线性规划定义及数学描述
以, 生产计划问题, 为例，
写出线性规划的 4种模型
课堂讨论：
三, LP的标准型,
1,LP标准型的概念
（ 1） 什麽是 LP的标准型？
（ 2） LP标准型的特点
? 目标函数约定是极大化 Max（ 或极小化
Min） ;
? 约束条件均用等式表示 ;
? 决策变量限于取非负值 ;
? 右端常数均为非负值 ;
（ 3）数学表达式,
有几种形式?
为什麽?
如何书写?
2,LP问题的标准化
（ 1）目标函数的标准化
MinZ=CX MaxZ’=-CXZ’=-Z
y
3
y = f ( x )
1
0 2 5 x
- 1
y ’ = - f ( x)
- 3
目
标
函
数
标
准
化
示
意
图
***********************
（ 2） 约束条件的标准化
& 约束条件是 ≤类型
—— 左边 加 非负松弛变量
& 约束条件是 ≥类型
—— 左边 减 非负剩余变量
& 变量符号不限
—— 引入 新变量 21
kkk xxx ??
课堂练习 1-1：将下面的线性规划问题化
为标准型：
?
?
?
?
?
?
?
?
????
???
???
????
符号不受限制
321
321
321
321
321
,0,
13
823
10
..
32
xxx
xxx
xxx
xxx
ts
xxxM i n Z
讨论：
·如何下手？标准化过程排序 -------
① x3；
② 约束 1引松弛变量；约束 2引剩余变量；
约束 3变号；
③ 目标函数标准化, 引入变换 Z’=-Z；
④ 整理；
? 提问, 答疑, 讨论
?总结, 看最终结果 P15