数学建模-PPT课件
1 1
170000
0.03
0.08
1x10 900
xj0, j1,2, ,10
Байду номын сангаас
数学建模
规划模型
13
线性规划问题求解
1. 可行域几何特征
满足约束条件的解称为可行解,所有可行解构成 的集合称为可行域,满足目标式的可行解称为最 优解。
线性规划问题的可行域是一个凸多边形;
数学建模
规划模型
16
0-1规划
例3 (MCM-88B)要把七 种不同规格的包装箱装到两辆铁 路平板车上去,各包装箱宽、高 均相同,但厚度(厘米)与重量 (公斤)不同。下表给出各包装箱的厚度、重量及数量。 每辆平板车有10.2米长的地方可用来装包装箱,载重40吨。由 于当地货运限制,对C5 , C6 , C7 类包装箱总数有一个特别限制:该 类箱子总厚度不超过302.7(厘米)。试把包装箱装到平板车上去 使得浪费空间最小。
[解] x1, x2 分别表示A, B两种产品的计划生产数(单位: 吨),f 表示利润(单位:千元),则
f = 7 x1 + 12 x2
数学建模
规划模型
8
耗煤量为 9 x1 + 5 x2 耗电量为 4 x1 + 5 x2 耗工作日 3x1 + 10 x2 于是得到线性规划模型为:
m axf7x112x2
引入新变量 xn1, xn2(称为松弛变量),则以上两式等
价于以下两式:
数学建模
规划模型
5
a i1 x 1 a i2 x 2 a in x n x n 1 b i x n 1 0
a i1 x 1 a i2 x 2 a in x n x n 2 b i x n 2 0
3. 自由变量标准化
若变量 xj 无约束,可引入两个新变量x j ', x j " ,令 xjxj'xj", xj',xj"0
故以下我们只考虑标准形式。
数学建模
规划模型
6
矩阵形式表示
minzc'x
s.t. Axb
一般要求,
x0 rk(A m n)m , m n
数学建模
规划模型
7
例1 某工厂制造A,B两种产品,制造产品A每吨需用 煤9吨,用电4千瓦,3个工作日;制造产品B每吨需用煤 5吨,用电5千瓦,10个工作日。已知制造产品A和B每吨 分别获利7000元和12000元。现该厂只有煤360吨,电200 千瓦,工作日300个可以利用,问A,B两种产品各应生产 多少吨才能获利最大?
m i n g 0 . 4 0 x 1 0 . 2 8 x 2 0 . 3 2 x 3 0 . 7 2 x 4 0 . 6 4 x 5 0 . 6 0 x 6
0.01 0.01 0.01 0.03 0.03 0.03 1
x1 850
0.02 0.02
0.05 0.05
线性规划问题如果存在最优解,则最优解必在可
行域的顶点处达到。
数学建模
规划模型
14
2. 单纯形法 基本思想:从可行域的一个顶点(基本可行解) 出发,转换到另一个顶点,并且使目标函数值逐 步减小,有限步后可得到最优解。
数学建模
规划模型
15
整数规划 自变量取整数的线性规划称为整数(线性) 规划。
割平面法,分支定界法
线性规划问题的一般形式:
n
min z c j x j j 1
s.t.
n
a ijxj b i i 1 2 , m
j 1
数学建模
x1x2… xn 0
规划模型
3
线性规划问题的标准形式:
n
min z
cjxj
j 1
n
s.t.
aijxjb i(0) i1 2, m
9 x1 5 x2 360
s.t.
4 x1 5 x2 3 x1 10 x2
200 300
x1 , x2 0
数学建模
规划模型
9
例2 设某工厂有甲、乙、丙、丁四个车间,生 产A、B、C、D、E、F六种产品,根据机车性能 和以前的生产情况,得知生产每单位产品所需各 车间的工作时数、每个车间在一个季度工作时数 的上限以及产品的价格,如下表所示。问:每种 产品每季度各应生产多少,才能使这个工厂每季 度生产总值达到最大?
11
[解] 以 x1 ~ x6 分别表示每季度生产产品A、B、C、D、
E、F的单位数,于是它们需满足
x1
0.01 0.02
0.01 0.02
0.01 0.03
0.03 0.05
0.03 0.05
00..0038
x2 x3 x4 x5 x6
数学建模
——从自然走向理性之路
数学建模
规划模型
1
第五讲 规划模型
【主要内容】 介绍线性规划模型、非线性规划模 型及动态规划模型
【主要目的】 了解规划问题的建模与求解,重点 在模型的建立与结果的分析
数学建模
规划模型
2
线性规划模型(Linear Programming)
建立模型
线性规划问题:求多变量线性函数在线性约束条件下的 最优值
850 700
100 900
x1,x2, ,x60
目标函数为
m a x f 0 . 4 0 x 1 0 . 2 8 x 2 0 . 3 2 x 3 0 . 7 2 x 4 0 . 6 4 x 5 0 . 6 0 x 6
数学建模
规划模型
12
引入松弛变量x7 ~ x10 ,化成标准型
数学建模
规划模型
10
产品 车间
甲 乙 丙 丁
A
B
C
D
E
F 每个车间每季度 工作时数上限
0.01 0.01 0.01 0.030. 0.03 0.03
850
0.02
05
700
0.02
0.05
100
0.03
0.08
900
单价(元)
0.40 0.28 0.32 0.72 0.64 0.60
数学建模
规划模型
j 1
x1x2…xn 0
数学建模
规划模型
4
[说明]
任意线性规划问题可化为标准形式。具体方式如下:
1. 目标函数标准化 : maxzmin(z)
2. 约束条件标准化 :
假设约束条件中有不等式约束
a i1 x 1 a i2 x 2 a in x n b i
或
a i1 x 1 a i2x2 a inxn b i