第一章 线性规划.ppt

第一讲线性规划
第一章线性规划的数学模型(1)
第一节线性规划一般模型(4)
第二节线性规划的图解法(16)
第三节线性规划的标准型(23)
第四节线性规划解的概念(32)
第二章线性规划的单纯形法(40)
第一节单纯形法原理(41)
第二节表格单纯形法(53)
第三节人工变量问题(67)
第四节单纯形法补遗(76)
第三章线性规划的对偶理论(93)
第四章线性规划灵敏性分析(123)
1
第一章线性规划的数学模型
线性规划 Linear Programming LP
规划论中的静态规划
解决有限资源的最佳分配问题
求解方法:
图解法
单纯形解法
2
第一章线性规划的数学模型
第一节线性规划一般模型
第二节线性规划的图解法
第三节线性规划的标准型
第四节线性规划解的概念
3
第一节线性规划一般模型
一、线性规划问题的三个要素
决策变量
决策问题待定的量值称为决策变量。
决策变量的取值要求非负。
约束条件
任何问题都是限定在一定的条件下求解,把各种限制条件表示为一组等式或不等式,称之为约束条件。
LP的约束条件,都是决策变量的线性函数。
目标函数
衡量决策方案优劣的准则,如时间最省、利润最大、成本最低。
目标函数是决策变量的线性函数。
有的目标要实现极大,有的则要求极小。
4
第一节线性规划一般模型
例1. 生产计划问题
某厂生产甲乙两种产品,各自的零部件分别在A、B车间生产,最后都需在C车间装配,相关数据如表所示:
问如何安排甲、乙两产品的产量,使利润为最大。
二、线性规划模型的构建
产品
车间
工时单耗
甲乙
生产能力
A
B
C
1 0
0 2
3 4
8
12
36
单位产品获利
3 5
5
第一节线性规划一般模型
(1)决策变量。要决策的问题是甲、乙两种产品的产量,因此有两个决策变量:设x1为甲产品产量,x2为乙产品产量。
(2)约束条件。生产这两种产品受到现有生产能力的制约,用量不能突破。
生产单位甲产品的零部件需耗用A车间的生产能力1工时,
生产单位乙产品不需耗用A车间的生产能力,
A车间的能力总量为8工时,则A车间能力约束条件表述为
x1 ≤8
同理,B和C车间能力约束条件为
2x2 ≤12
3x1 +4 x2 ≤36
建立模型
6
第一节线性规划一般模型
(3)目标函数。目标是利润最大化,用Z表示利润,则
maxZ= 3x1 +5 x2 
(4)非负约束。甲乙产品的产量不应是负数,否则没有实际意义,这个要求表述为
x1 ≥0, x2 ≥0
综上所述,该问题的数学模型表示为
maxZ= 3x1 +5 x2
x1 ≤8
2x2 ≤12
3x1 +4 x2 ≤36
x1 ≥0, x2 ≥0
.
7
第一节线性规划一般模型
某名牌饮料在国内有三个生产厂,分布在城市A1、A2、A3,其一级承销商有4个,分布在城市B1、B2、B3、B4,已知各厂的产量、各承销商的销售量及从Ai到Bj的每吨饮料运费为Cij,为发挥集团优势,公司要统一筹划运销问题,求运费最小的调运方案。
例2. 运输问题
销地
产地
B1 B2 B3 B4
产量
A1
A2
A3
6 3 2 5
7 5 8 4
3 2 9 7
5
2
3
销量
2 3 1 4
8
第一节线性规划一般模型
(1)决策变量。设从Ai到Bj的运输量为xij,
(2)目标函数。运费最小的目标函数为
minZ=6x11+3x12+2x13+5x14+7x21+5x22+8x23+4x24+3x31+2x32+9x33+7x34
(3)约束条件。产量之和等于销量之和,故要满足:
供应平衡条件
x11+x12+x13+x14=5
x21+x22+x23+x24=2
x31+x32+x33+x34 =3
销售平衡条件
x11+x21+x31=2
x12+x22+x32=3
x13+x23+x33=1
x14+x24+x34=4
非负性约束 xij≥0 (i=1,2,3;j=1,2,3,4)
9
例3:合理下料问题 在180cm材料上,需切割三种毛坯(70cm 、52cm 、35cm),其需要量分别为100、150、100根,问如何切割,余料最省?
下料方式
一
二
三
四
五
六
七
八
零件需要量
A 70cm
2
1
1
1
0
0
0
0
100
B52cm
0
2
1
0
3
2
1
0
150
C35cm
1
0
1
3
0
2
3
5
100
余料
5
6
23
5
24
6
23
5
10