当前位置:首页 >> 数学 >>

数学实验之5.线性规划1_图文

线性规划

主要内容
动物饲料配置 线性规划模型
Matlab软件求解

实 验 目 的

最 优 化 问 题 简 介

求解方法简介
灵敏度分析

整数规划简介
实验
回主页

实验目的
1.掌握用MATLAB优化工具箱求解线性规划的方法;
2、了解线性规划模型中的灵敏度分析方法;掌握如 何使用软件来实现分析; 3 .练习怎样由实际问题建立线性规划模型的全过程。

2002.5.

上一页

下一页

返 回

3

最优化问题简介
1、生产计划问题;
2、运输问题; 特点:从若干可能的计划(方案)中寻求某 种意义下的最优方案,数学上将这种问题称 为最优化问题(optimization).

2002.5.

上一页

下一页

4

生产计划问题 单耗
材料 工时 … 利润(元/件)

数据表 甲 乙 x1 x2

设xi为生产第i种产品的数量
丙 x3 限额

2 3 4

3 2 3

1 1.5 2

34 36

在一定的条件下,问生产数量xi=?使利润达到最大?

规划模型

max Z ? 4 x1 ? 3 x 2 ? 2 x3 ?2 x1 ? 3 x 2 ? x3 ? 34 ? s.t.?3 x1 ? 2 x 2 ? 1.5 x3 ? 36 ?x , x , x ? 0 ? 1 2 3

利润 材料 工时

2002.5.

上一页

下一页

5

运输问题
S3 S2
1200

290 160 320 160 70 70 30

30

S7
20

S4
690

20

690 170
720
520

S6
110 62 420 500

A15

88 462

202 1100 20 195 306 1150 600 450 80 2 3 104 750 606 10 10 31 680 201

S5
220

10

A14

S1
12

70 42 10 210

A13 A12

480

A9

A10

300

A11

S1~S7 钢管厂
铁路 火车站 公路 管道 450 里程(km)
6) (沿管道建有公路

A8

5

194

A6

205

A7

A5

A4

A2

301

A3

目标:运费达到最小
上一页 下一页

A1

2002.5.

运输问题
某种原材料有M个产地,现在需要将原材料从 产地运往N个工地,假定M个产地的产量为ai和N个 工地的需求量为bj,单位产品的运费cij已知,那么如 何安排运输方案可以使总运费最低?
状 数学模型: 态 变 量 cij —单位运费;

min s.t.

? ?c
i ?1 j ?1

M

N

ij x ij

xij —运输量;
ai —第i 地产量;

?x
j ?1 M
下一页

N

ij

? ai , ? bj

i ? 1,2,..., M j ? 1,2,..., N
7

bj —第j 地需要量;
2002.5. 上一页

?x
i ?1

ij

建立最优化的数学模型应具备三个基本要素

1、决策变量(decision variables);

2、约束条件(constraints);
3、目标函数(objective function) 最优化问题分类: ① 线性、非线性 ② 静态、动态 ③ 整数、非整数 ④ 随机、非随机等

2002.5.

上一页

下一页

8

动物饲料配置问题
美国一家公司以专门饲养并出售一种实验用的 动物而闻名。这种动物的生长对饲料中的三种营养 成分特别敏感,即蛋白质、矿物质和维生素。 需 要 的 营 养 量

蛋白质:70克
矿物质:3克 维生素:9.1毫克

现有五种饲料,公司希望找出满足动物营养 需要使成本达到最低的混合饲料配置。
2002.5. 上一页 下一页 9

每一种饲料每磅所含的营养成分
饲料 1(x1) 2(x2) 3(x3) 4(x4) 5(x5) 需要量 蛋白质(克) 0.30 2.00 1.00 0.60 1.80 70 矿物质(克) 0.10 0.05 0.02 0.20 0.05 3 维生素(毫克) 0.05 0.10 0.02 0.20 0.08 9.1

每种饲料每磅的成本
饲料 成本(美元) 1 0.02 2 0.07 3 0.04 4 0.03 5 0.05

2002.5.

上一页

下一页

10

建立数学模型
① 决策变量:在混合饲料中,每天所需第j种饲料的 磅数xj,j = 1,2,3,4,5; ② 约束条件: 蛋白质:0.30x1+2x2+x3+0.6x4+1.8x5≥70

矿物质:0.10x1+0.05x2+0.02x3+0.2x4+0.05x5≥3
维生素:0.05x1+0.1x2+0.02x3+0.2x4+0.08x5≥10

自然约束条件:xi≥0 ③ 确定目标:混合饲料的成本最低
0.02x1+0.07x2+0.04x3+0.03x4+0.05x5→min
2002.5. 上一页 下一页 11

完整的线性规划模型:
min 0.02x1+0.07x2+0.04x3+0.03x4+0.05x5 s.t. 0.30x1+2x2+x3+0.6x4+1.8x5≥70 0.10x1+0.05x2+0.02x3+0.2x4+0.05x5≥3 0.05x1+0.1x2+0.02x3+0.2x4+0.08x5≥10
归纳:

xj≥0 j = 1,2,3,4,5;
cT ? [0.02, 0.07, 0.04, 0.03, 0.05] 2 1 0.6 1.8 ? ? 0.3 ?70? ?, b ? ? 3 ? A?? 0 . 1 0 . 05 0 . 02 0 . 2 0 . 05 ? ? ? ? ? ? ?0.05 0.1 0.02 0.2 0.08? ? ?10? ?
上一页 下一页 返 回 12

min cTx
s.t. Ax≥b x≥0
2002.5.

线性规划模型
min (max) cTx

s.t. Ax≥b
x≥0 标准形式:

(Ax≤b, Ax = b)

max cTx

s.t. Ax = b ( b≥0)
x≥0 (a ≤ x ≤ b) 其中:x∈Rn,A ∈Rm×n, b∈Rm, c∈Rn

Z
2002.5.

标准形式的线性规划模型起什么作用?
上一页 下一页 13

实用形式之一:

实用形式之二:
min cTx

min cTx
s.t. A1x = b1

s.t. A1x = b1
b2 ≤A2x≤b3 L≤x≤U

A2x≤b2
L≤x≤U

MATLAB软件可以直接支持实用形式之一。

Z
2002.5.

其他形式的线性规划模型怎样 转化为以上形式?如b2 ≤A2x≤b3 怎 样转化为Ax≤b?
上一页 下一页 返 回 14

有关线性规划解的若干概念 1、可行解(可行点) 2、可行域 3、最优解 4、无界解 例:Max z = 3x1+x2 s.t. -x1+x2≤2 x1-2x2≤2 3x1+2x2≤14

x1,x2≥0

2002.5.

上一页

下一页

15

线性规划的基本性质
? 若存在可行域,它必是凸多面体; ? 线性规划目标函数等值线是平行的等值线;

? 若存在最优解,必在可行域的顶点处取得;
单纯形法的基本思路: 用迭代法从一个顶点转到另一个顶点,验证是 否使目标函数值增大(减小)。

2002.5.

上一页

下一页

16

线性规划的灵敏度分析 灵敏度分析也称变动分析(ranging analysis),主要 指参数如何变化而不影响解的结果。 max cTx 参数:c, A, b 标准形式: 决策变量:x s.t. Ax = b ( b≥0)

x≥0
参数变动有以下三种情况: 1、c→c+△c; △c影响目标平面的方向; 2、A →A+△A; △A影响约束平面的方向; 3、b→b+△b; △b使约束平面平移;
2002.5. 上一页 下一页 17

线性规划的灵敏度分析

解 释
新最优解 maxz = 3x1+x2 c=[3,1]; c+△c=[3,3]

maxz = 3x1+3x2

情况1 c → c+△c
2002.5. 上一页 下一页

z = 3x1+0.5x2
18

3x1+x2=14

A → A+△A 情况2
2002.5. 上一页 下一页

b → b+△b 情况3
19

Z
实际问题中,为什么要进行灵敏度分析? 线性规划的结构灵敏度分析 1、变量的增加或减少; 2、约束的增加或减少;

2002.5.

上一页

下一页

20

MATLAB软件(5.3)求解

实用形式之一:
Ax ? b ? A1 ? ? b1 ? A ? ? ?, b ? ? ?; ?A 2 ? ?b 2 ?

min cTx s.t. A1x = b1

A2x≤b2
L≤x≤U

x = lp(c, A, b, L, U, x0, nEq)
初始值 等式约束的个数

[x, lag, how] = lp(c, A, b, L, U, x0, nEq)
拉格朗日乘子 给出错误信息:infeasible, unbounded
2002.5. 上一页 下一页 21

例1

max Z ? 5 x1 ? 2 x 2 ? 3 x3 ? x1 ? 5 x 2 ? 2 x3 ? 30 ? s.t.? x1 ? 5 x 2 ? 6 x3 ? 40 ?x , x , x ? 0 ? 1 2 3

[a=?, b=?]

编程计算:(li1.m)
A1

计算结果:

c=[-5,-2,-3]'; x = 30.0000 0.0000 0 A=[1,5,2;1,-5,-6]; lag = 5.0000 0 0 b=[30,40]'; 23.0000 7.0000 0 0 0 L=[0,0,0]';L=zeros(3,1); U=[inf,inf,inf]'; how = ok x0=[1,1,1]'; 思考:灵敏度分析(li4.m) neq=1; [x,lag,how]=lp(c,A,b,L,U,x0,neq) z=-c'*x
2002.5. 上一页 下一页 22

for c3=0:0.05:15 (li4.m) c=[-5,-2,-c3]'; A=[1,-5,-6]; b=40; Aeq=[1,5,2]; beq=30; L=[0,0,0]'; x=lp(c,A,b,Aeq,beq,L); z=-c'*x; plot(c3,z,'.') hold on end hold on for c2=0:0.05:15 c=[-5,-c2,-3]'; x=lp(c,A,b,Aeq,beq,L); z=-c'*x; plot(c2,z,'r') hold on end
2002.5. 上一页 下一页

灵敏度分析

23

动物饲料配置问题
计算程序及结果结果:
c=[0.02,0.07,0.04,0.03,0.05]'; A= -[0.3,2,1,0.6,1.8;… 0.1,0.05,0.02,0.2,0.05;… 0.05,0.1,0.02,0.2,0.08]; b= -[70,3,10]'; L=zeros(5,1); 计算结果: x=lp(c,A,b,L) x = 0.0000 0.0000 0.0000 39.7436 25.6410 z=c ' *x z = 2.4744

2002.5.

上一页

下一页

24

MATLAB6.0升级版的特点 1、函数变化,lp → linprog; 2、输入、输出格式简化,易懂; 3、规模增大,上千个变量以及几百个等式或 不等式约束; Matlab6.0 解决的线性规划的标准格式为: min cTx x∈Rn s.t. A· x<b Aeq· x = beq L≤x≤U

其中,A, b, c, x, Aeq, beq, L, U等均表示矩阵向量。
2002.5. 上一页 下一页 25

MATLAB6.0升级版的语句 格式;min cTx x∈Rn s.t. A· x < b2 Aeq· x = beq L≤x≤U

[x,fval,lambda,exitflag,output] =
lower 下界 Upper 上界 ineqlin 不等式约束 eqlin 等式约束

iterations,迭代次数 algorithm,使用的运算规则 cgiterations, PCG迭代次数

linprog(c, A, b, Aeq, beq, L, U, x0)
若没有等式约束,则 Aeq=[];beq=[]; 或 A=[]; b=[]; 若没有这些项, 则可以省略。

>0, 函数收敛于解x; =0,超过函数估值; <0,函数不收敛于x
2002.5. 上一页

下一页

26

归纳:

MATLAB6.0升级版的语句

思考:linprog与lp的最大区别在哪里?
2002.5. 上一页 下一页 27

例3

min Z ? ?5 x1 ? 4 x2 ? 6 x3 ? x1 ? x2 ? x3 ? 20 ?3 x ? 2 x ? 4 x ? 42 ? 1 2 3 s.t.? ?3 x1 ? 2 x2 ? 30 ? ? x1 , x2 , x3 ? 0

程序:(li3.m)
c=[-5,-4,-6]'; A=[1,-1,1;3,2,4;3,2,0]; b=[20,42,30]'; L=zeros(3,1); [x,fval,exitflag,output,lambda] =linprog(c,A,b,[],[],L)

2002.5.

上一页

下一页

28

输出结果:
x = 0.0000 15.0000 3.0000 fval = -78.0000 exitflag = 1 output = iterations: 6 cgiterations: 0 algorithm: 'lipsol' lambda = ineqlin: [3x1 double] eqlin: [0x1 double] upper: [3x1 double] lower: [3x1 double] >>lambda.ineqlin ans = 0.0000 1.5000 >> lambda.lower ans = 1.0000 0.0000

0.5000
0.0000

表示不等式约束条件2、3和第1个下界是有效的。
2002.5. 上一页 下一页 29

整数线性规划算法简介
在线性规划中,当变量要求取整(即xi为整型变量), 就定义为整数规划。 整数规划是一个组合问题。无论在理论上还是在 实践中都要困难得多!未找到多项式时间算法。常用 求解方法:
√ 1、枚举法;(变量个数很少的情况才有效) √ 2、分枝定界法;(规模较小的问题可行) √ 3、割平面法;(同上)

4、近似或启发式算法;(大规模)
2002.5. 上一页 下一页 30

分枝定界法

max z ? 5 x1 ? 8 x 2
LP0 X=(2.25, 3.75) Z0=41.25

s.t. x1 ? x 2 ? 6 5 x1 ? 9 x 2 ? 45
x2≥4 LP2 X=(1.8, 4) Z2=41

x2≤3 LP1 X=(3, 3) Z1=39

x1 , x 2 ? 0且为整数

x1≤1 LP3 X=(1, 4.44) Z3=41.25 x2≤4 LP5 X=(1, 4) Z5=37
2002.5. 上一页 下一页

x1≥2 LP4 无可行解 x2≥5

LP6 X=(0, 5) Z6=40
31

割平面算法 算法步骤:

max z ? 5 x1 ? 8 x 2 s.t. x1 ? x 2 ? 6 5 x1 ? 9 x 2 ? 45 x1 , x 2 ? 0且为整数

第一步:不受整数约束,求解线性规划问题; 第二步:判断,若第一步的解是全整数解,则停止, 否则转下一步;

第三步:把一个新的约束(割)加到问题中,并返
回第一步。
(0, 5)是整数最优解 x1+x2=6
增加一个约束约束 x2≥4 5x1+9x2=45

2002.5.

上一页

下一页

32

范例:装箱问题
要将七种不同规格的包装箱装到两辆铁路平板 车上去,各包装箱宽、高均相同,但厚度t(厘米)与 重量w(公斤)不同。如下表: c1 c2 c3 c4 c5 c6 c7 t 48.7 52.0 61.3 72.0 48.7 52.0 64.0 w 2000 3000 1000 500 4000 2000 1000 8 7 9 6 6 4 8 件数

2002.5.

上一页

下一页

33

每辆平板车有10.2米长的地方可用来装包装箱 (像面包片那样),载重40吨。由于当地货运限制, 对c5,c6,c7类包装箱总数有一个特别的限制:该类箱 子总厚度不得超过302.7(厘米)。试将包装箱装到平 板车上去使得浪费空间最小。 设对应于表中cj(1≤j≤7)的厚度为tj,重量为wj, 件数为nj。设决策变量为xij,它表示第i辆平板车装 cj箱的个数,i=1,2, j=1,…,7。 约束条件

重量限制:
2xi1 ? 3xi 2 ? xi 3 ? 0.5xi 4 ? 4xi 5 ? 2xi 6 ? xi 7 ? 40

件数限制:
x1 j ? x2 j ? n j
2002.5.

i ? 1,2

j ? 1,2,...,7
上一页 下一页 34

厚度限制
0.487xi1 ? 0.52xi 2 ? 0.613xi3 ? 0.72xi 4 ? 0.487xi5 ? 0.52xi 6 ? 0.64xi 7 ? 10.2

特别厚度限制条件
0.487xi 5 ? 0.52xi 6 ? 0.64xi 7 ? 3.027

i ? 1,2 i ? 1,2

共有13个约束条件 目标函数
2

max ? [0.487xi1 ? 0.52xi 2 ? 0.613xi 3 ? 0.72xi 4
i ?1

? 0.487xi 5 ? 0.52xi 6 ? 0.64xi 7 ]

2002.5.

上一页

下一页

35

归纳
max ? [0.487xi1 ? 0.52xi 2 ? 0.613xi 3 ? 0.72xi 4
i ?1 2

? 0.487xi 5 ? 0.52xi 6 ? 0.64xi 7 ]

s.t.

x1 j ? x2 j ? n j

j ? 1,2,...,7

2xi1 ? 3xi 2 ? xi 3 ? 0.5xi 4 ? 4xi 5 ? 2xi 6 ? xi 7 ? 40
0.487xi1 ? 0.52xi 2 ? 0.613xi3 ? 0.72xi 4 ? 0.487xi5 ? 0.52xi 6 ? 0.64xi 7 ? 10.2

0.487xi 5 ? 0.52xi 6 ? 0.64xi 7 ? 3.027

思考:1、状态变量有多少? 2、如何求解?
2002.5. 上一页 下一页

i ? 1,2

36

实验内容
1、两种面包产品的产量配比问题 P162页实验一。 2、运动员的营养配餐

P163页实验二。

2002.5.

上一页

下一页

37

3、投资策略
某部门现有资金10万元,五年内有以下投资 项目供选择: 项目A:从第一年到第四年每年初投资,次年末收回本金且获 利15%; 项目B:第三年初投资,第五年末收回本金且获利25%,最大 投资额为4万元; 项目C:第二年初投资,第五年末收回本金且获利40%,最大 投资额为3万元; 项目D:每年初投资,年末收回本金且获利6%; 问如何确定投资策略使第五年末本息总额最大?
2002.5. 上一页 下一页 38


相关文章:
高一数学必修5简单的线性规划1ppt1_图文.ppt
高一数学必修5简单的线性规划1ppt1 - y 线性规划的简单应用 o x
重大数学实验五线性拟合_图文.doc
开课学院、实验室: 实验时间课程 数学实验 名称 指导 教师 : 线性规划验证
数学实验4-线性规划_图文.pdf
数学实验 Experiments in Mathematics Laboratory Mathematics 阮小娥博士 线性规划 ...0-1线性规划 ? 线性多目标规划 ? 最优化问题简介参看:实验8,实验9 5 、...
数学建模与数学实验之非线性规划._图文.ppt
数学建模与数学实验之线性规划. - 数学建模与数学实验 之线性规 划 后勤工程学院数学教研室 1 实验目的 1、直观了解非线性规划的基本内容。 2、掌握用数学...
数学建模线性规划_图文.ppt
数学建模线性规划 - 数学建模与数学实验 线性规划 实验目的 1、了解线性规划的基本内容。 2、掌握用数学软件包求解线性规划问题。 实验内容 1、两个引例。 *2、...
数学建模与数学实验 第4讲 线性规划_图文.ppt
实验内容 1、两个引例。 2、用数学软件包matlab求解线性规划问题。 3、用数学软件包lindo、lingo求解线性规划问题。 4、建模案例:投资的收益与风险 5实验作业...
[理学]大学数学实验11-线性规划_图文.ppt
[理学]大学数学实验11-线性规划_幼儿读物_幼儿教育_教育专区。[ ...车床 类型甲乙 单位工件所需加工台时数 工件 1 0.4 0.5 工件 2 1.1 1...
【大学课件】数学建模与数学实验 线性规划-文档资料_图文.ppt
实验内容 1. 两个引例. 2. 用数学软件包MATLAB求解线性规划问题. 3. 用数学软件包LINDO、LINGO求解线性规划问题. 4. 建模案例:投资的收益与风险. 5. 实验...
高一数学必修5 二元一次不等式组与简单的线性规划问题 ....ppt
高一数学必修5 二元一次不等式组与简单的线性规划问题 ppt1 - 二元一次不等
数学建模--线性规划_图文.ppt
数学建模--线性规划 - 数学建模与数学实验 线性规划 2019/5/10 后勤工程学院数学教研室 课件 1 实验目的 1、了解线性规划的基本内容。 2、掌握用数学软件包求解...
数学实验五MATLAB优化工具箱_图文.ppt
数学实验五MATLAB优化工具箱 - 线性规划线性规划 数学实验五 MATLAB优化工具箱 ? ? 线性规划线性规划 最小二乘 ? 最小二乘意义下的最优 ? 方...
第5讲 线性规划_图文.ppt
5线性规划 - 数学建模与数学实验 线性规划 实验目的 1、了解线性规划的基本内容。 、了解线性规划的基本内容。 2、掌握用数学软件包求解线性规划问题。 、...
【大学课件】数学建模与数学实验 线性规划46页PPT_图文.ppt
实验内容 1. 两个引例. 2. 用数学软件包MATLAB求解线性规划问题. 3. 用数学软件包LINDO、LINGO求解线性规划问题. 4. 建模案例:投资的收益与风险. 5. 实验...
数学实验线性规划.doc
数学实验线性规划 - 实验 5 线性规划 分 1 黄浩 43 一、 实验目的 1. 掌握用 MATLAB 工具箱求解线性规划的方法 2. 练习建立实际问题的线性规划模型 二...
数学建模之线性规划问题_图文.pdf
1984 年美国贝尔电话实验室的印度数学家 N.卡马卡提出解线性规划问题的 新的...1 2 3 4 5 6 Value 2.500000 7.000000 31000.00 0.000000 1 Reduced ...
高教版《数学建模与数学实验(第3版)》第4讲 线性规划_图文.ppt
实验内容 1. 两个引例. 2. 用数学软件包MATLAB求解线性规划问题. 3. 用数学软件包LINDO、LINGO求解线性规划问题. 4. 建模案例:投资的收益与风险. 5. 实验...
数学实验第五次讲稿_图文.ppt
数学实验次讲稿 - 数学实验线性规划 2017/4/18 1
数学实验线性规划.doc
数学实验线性规划 - 数学实验报告 实验 5 线性规划 实验 5 线性规划 分 1 黄浩 2011011743 一、 实验目的 1. 掌握用 MATLAB 工具箱求解线性规划的方法 2...
0-1线性规划模型_图文.ppt
{0,1},i=1,…,5,j=1,…,4 ? 这类线性规划问题的特点是决策变量只 ...数学实验 学 所属类别 分 5 数学 4 数学 4 3 4 3 2 2 3 先修课 ...
整数线性规划及0-1规划_图文.ppt
整数线性规划及0-1规划 典型的整数线性规划问题一、背包问题 有一徒步旅行者要...数学实验 学分 5 4 4 3 4 3 2 2 3 所属类别数学 数学 数学;运筹学 ...