tceic.com
学霸学习网 这下你爽了
当前位置:首页 >> 数学 >>

2015数学建模提高班专题1——规划专题_图文

2015数学建模提高班 ——规划模型专题
王义康 2015/3/21

提高班概况及相关要求
本次数学建模提高班(2015年全国大学生数学建模 竞赛预备班)共有来自全校12个分院逾500名同学报名, 本着以人为本,共同学习、共同提高的原则,经过数学 建模教练组的认真审查遴选,共有429名同学进入提高 班学习。 提高班将分两个班进行,每周采用半天集中授课,其 它时间自行复习、交流、练习的方法进行。每周末提高课 结束后将会有适当的练习留给大家,请大家务必在次周周 五晚21点前上交作业电子版,作业提交邮箱,提高班1: jlmcm1@163.com; 提高班2:jlmcm2@163.com,邮件 主题和附件名均用:XX班XXX第X次作业

计量数模QQ群:46398770,请大家务必加 入;群共享里可以下载到每次课的课件;另外 QQ群是课后讨论答疑的主战场,也是大家展现 激情与智慧的重要平台。
个人电脑需要安装的软件:matlab, lingo, spss,acrobat read等,其中word里要把公式编辑 器装上(一些高版本文字处理软件自带公式编辑 器) ,或装上mathtype;需要相关软件自行下载!

提高班将在5月上旬结束,根据个人意愿、提高班表 现、校赛成绩、个人学业业绩等择优选拔150人左右进

入暑假全国大学生数学建模竞赛集训队,根据集训效果
再选拔约120人左右参加全国比赛。 提高班活动开展过程中,对于参与认真,进步快, 效率高,善于质疑和答疑的优秀学员,将直接选拔进入

集训队,计划直选60人左右。
计划通过校赛和后继表现再选入60人左右。暑期集 训的选拔工作将在6月上旬完成。

提高班学习方法

课件 预习

听提高讲座

看课件复习

做专题练习

QQ群质询答 疑,互助讨论

2015,我们的数模之旅
全国五一联赛
2015年 3月启 程 2015年5月中旬 jlmcm小试牛刀 2015年7月上旬 cumcm集训第一阶 段(3 weeks) 2015年8月下旬 cumcm集训第二 阶段(15 d)

2015年 9月上旬某周末 cumcm华山论剑

2015年11月 全国机电工程学 会杯

2015年1月~2 月mcm&icm集 训

2016年2月 mcm&icm 武林大会

全国电工杯

本次提高班的具体安排
?

1.第3周周六(3.21):规划模型、案例及软件求解(王义康) ? 2.第4周周日(3.29):统计回归模型及软件求解(刘学艺) ? 3.第6周周日(4.12):多元统计模型及软件求解(李有梅) ? 4.第8周周日(4.26):微分方程模型及软件求解(杨静华) ? 5.第10周周六(5.9):差分方程及时间序列建模(柴中林) ? 6.第11周周六(5.16):网络优化模型及案例分析(赵承业) ? 7.第12周:论文写作与优秀作品赏析(自学) ? 第七届中国计量学院数学建模竞赛(5.17~5.24)

历届竞赛赛题基本解法
赛题 93A非线性交调的频率设计 93B足球队排名 94A逢山开路 94B锁具装箱问题 95A飞行管理问题 95B天车与冶炼炉作业调度 拟合、规划 图论、层次分析、整数规划 图论、插值、动态规划 图论、组合数学 非线性规划、线性规划 动态规划、排队论、图论 解法

96A最优捕鱼策略
96B节水洗衣机

微分方程、优化
非线性规划

历届竞赛赛题基本解法
97A零件的参数设计
97B截断切割的最优排列 98A一类投资组合问题 98B灾情巡视的最佳路线 99A自动化车床管理

非线性规划
随机模拟、图论 多目标优化、非线性规划 图论、组合优化 随机优化、计算机模拟

99B钻井布局
00A DNA序列分类 00B钢管订购和运输

0-1规划、图论
模式识别、Fisher判别、人工神经网络 组合优化、运输问题

历届竞赛赛题基本解法
01A血管三维重建 曲线拟合、曲面重建

01B 工交车调度问题
02A车灯线光源的优化 02B彩票问题 03A SARS的传播 03B 露天矿生产的车辆安排

多目标规划
非线性规划 单目标决策 微分方程、差分方程 整数规划、运输问题

04A奥运会临时超市网点设计
04B电力市场的输电阻塞管理

统计分析、数据处理、优化
数据拟合、优化

历届竞赛赛题基本解法
05A 长江水质的评价和预测 05B DVD在线租赁 06A 出版社的资源配置 06B 艾滋病疗法评价及疗效预测 聚类、模糊评判 主成分分析、多目标决策

多目标规划
线性规划、多目标规划 回归 线性规划

07A 中国人口增长预测问题
07B 乘公交,看奥运问题

微分方程、差分方程
图论、0-1 规划、动态规划

08A 数码相机定位问题 08B 高等教育学费标准探讨

几何、优化 多元回归、多目标优化

历届竞赛赛题基本解法
09A 制动实验台控制方法分析 09B 眼科医院病床管理 10A 地下储油罐变位参数识别 10B 定量评价上海世博会影响力 11A 城市表层土壤的重金属污染分析 11B 交巡警平台的设置与调度 12A 葡萄酒的评价 12B 太阳能小屋的设计

物理,拟合,误差分析

统计分析、排队论模型
几何,微元,非线性拟合,非线性优化 层次分析,综合评价 综合评价,微分方程 规划,图论,智能算法 分布检验,多元统计分析,综合评价 多目标规划,启发式算法

历届竞赛赛题基本解法
?

2013A 交通事故对道路通行能力的影响 机理分析、差分方程、排队论、模拟仿真 交通波、曲线回归
2013B 碎纸拼接复原 0-1规划、图论、启发式算法

?

历届竞赛赛题基本解法
?

2014A 嫦娥三号软着陆轨道设计与控制策略 机理分析、微分方程、数值模拟、优化建模
2014B 创意平板折叠桌 几何、优化

?

?44个问题从实际意义分析大体上可分:
工业、农业、工程设计、交通运输、经济管理、生 物医学和社会事业等七个大类。 工业类:电子通信、机械加工与制造、机械设计与控 制等行业,共有13个题,占29.5%。 农业类: 3个题,占6.8%。 工程设计类: 6个题,占13.6%。 交通运输类: 7个题,占15.9% 经济管理类: 6个题,占13.6% 生物医学类:5个题,占11.4% 社会事业类:4个题,占9.1%

第一讲

规划模型、案例及软件求解

一、引言
二、线性规划模型及软件求解 三、整数与01规划模型 四、经典的线性规划模型

五、多目标规划模型(后续) 六、非线性规划模型(后续)
七、国赛案例分析(后续)

一、引言
如何来分配有限资源,从而达到人们期望目标的
优化分配数学模型. 它在数学建模中处于中心的地位.

这类问题一般可以归结为数学规划模型.规划模型的应
用极其广泛,其作用已为越来越多的人所重视. 在数模竞赛过程中,规划模型是最常见的一类数 学模型. 从92-14年全国大学生数模竞赛试题的解题

方法统计结果来看,规划模型出现了近22次,占到了
近50%,也就是说每两道竞赛题中就有一道涉及到利

用规划理论来分析、求解.

规划模型的一般意义
(一)规划模型的数学描述
将一个优化问题用数学式子来描述,即求函数

u ? f ( x)
在约束条件 和

x ? ( x1 , x2 ,..., xn )

hi ( x) ? 0, i ? 1,2,...,m.

gi ( x) ? 0( gi ( x) ? 0),i ? 1,2,..., p.

下的最大值或最小值,其中

x f ( x)
x??

决策变量 目标函数 可行域

min(or max)u ? f ( x) x ? ?

s. t. hi ( x) ? 0, i ? 1,2,...,m.
gi ( x) ? 0( gi ( x) ? 0),i ? 1,2,..., p.

s. t.

subject to

“受约束于”之意

(二)规划模型的分类
1.根据是否存在约束条件 有约束问题和无约束问题。 2.根据决策变量的性质 静态问题和动态问题。 3.根据目标函数和约束条件表达式的性质 线性规划,非线性规划,二次规划,多目标规划等。

(1)非线性规划
目标函数和约束条件中,至少有一个非线性函数。

min u ? f ( x) x ? ?

s. t. hi ( x) ? 0, i ? 1,2,...,m.
gi ( x) ? 0( gi ( x) ? 0),i ? 1,2,..., p.

(2)线性规划 目标函数和所有的约束条件都是决策变量 的线性函数。

min u ? ? ci xi
i ?1

n

? n ?? a ji xi ? b j , j ? 1, 2,..., m. s.t. ? i ?1 ? x ? 0, i ? 1, 2,..., n. ? i

(3)二次规划问题
目标函数为二次函数,约束条件为线性约束

1 n min u ? f ( x ) ? ? ci xi ? ? bij xi x j 2 i , j ?1 i ?1 ? n ?? a ji xi ? b j , j ? 1, 2,..., m. s.t. ? i ?1 ? x ? 0.i ? 1, 2,..., n. ? i

n

4. 根据决策变量的允许值
整数规划(0-1规划)和实数规划。

(三)建立规划模型的一般步骤

1.确定决策变量; 2.确定目标函数的表达式; 3.寻找约束条件。

二、线性规划模型及软件求解

规划求解:Lingo(主流)

Matlab(用得少)

例1 : 任务分配问题:某车间有甲、乙两台机床,可用于加工三
种工件。假定这两台车床的可用台时数分别为800和900,三种工件 的数量分别为400、600和500,且已知用两种不同车床加工单位数 量不同工件所需的台时数和加工费用如下表。问怎样分配车床的加 工任务,才能既满足加工工件的要求,又使加工费用最低?
车床 类 型 甲 乙 单位工件所需加工台时数 工件 1 0.4 0.5 工件 2 1.1 1.2 工件 3 1.0 1.3 单位工件的加工费用 工件 1 13 11 工件 2 9 12 工件 3 10 8 可用台 时数 800 900



设在甲车床上加工工件1、2、3的数量分别为x1、x2、x3,在乙

车床上加工工件1、2、3的数量分别为x4、x5、x6。可建立以下线性

规划模型:

min z ? 13x1 ? 9x2 ? 10x3 ? 11x4 ? 12x5 ? 8x6
? x1 ? x4 ? 400 ? x ? x ? 600 ? 2 5 ? ? x3 ? x6 ? 500 s.t. ? ?0.4 x1 ? 1.1x2 ? x3 ? 800 ?0.5 x4 ? 1.2 x5 ? 1.3x6 ? 900 ? ? ? xi ? 0, i ? 1, 2, , 6

例1的Lingo求解

model: min=13*x1+9*x2+10*x3+11* x4+12*x5+8*x6; x1+x4=400; x2+x5=600; x3+x6=500; 0.4*x1+1.1*x2+x3<800; 0.5*x1+1.2*x2+1.3*x3<900; end

Matlab解答

例2: 某厂每日8小时的产量不低于1800件。为了进行质量控制,
计划聘请两种不同水平的检验员。一级检验员的标准为:速度25件/ 小时,正确率98%,计时工资4元/小时;二级检验员的标准为:速 度15小时/件,正确率95%,计时工资3元/小时。检验员每错检一次, 工厂要损失2元。为使总检验费用最省,该工厂应聘一级、二级检验 员各几名?
解 设需要一级和二级检验员的人数分别为x1、x2人,

则应付检验员的工资为:

8 ? 4 ? x1 ? 8 ? 3 ? x2 ? 32 x1 ? 24 x2
因检验员错检而造成的损失为:

(8 ? 25 ? 2% ? x1 ? 8 ?15 ? 5% ? x2 ) ? 2 ? 8x1 ? 12 x2

故目标函数为:

min z ? (32 x1 ? 24 x2 ) ? (8x1 ? 12 x2 ) ? 40 x1 ? 36 x2
约束条件为:

?8 ? 25 ? x1 ? 8 ? 15 ? x2 ? 1800 ?8 ? 25 ? x ? 1800 ? 1 ? 8 ? 15 ? x ? 1800 2 ? ? ? x1 ? 0, x2 ? 0

线性规划模型:

min z ? 40 x1 ? 36 x2
?5 x1 ? 3 x2 ? 45 ?x ? 9 ? 1 s.t. ? ? x2 ? 15 ? ? x1 ? 0, x2 ? 0

例2的Lingo求解

! 例2的Lingo求解; model: min=40*x1+36*x2; 5*x1+3*x2>45; x1<9; x2<15; end

Matlab解答

Lingo是Linear Interactive and General Optimizer的缩写, 即“交互式的线性和通用优化求解器”,是美国 Lindo系统公 司(Lindo System Inc)开发的求解数学规划系列软件中的一 个(其他软件为Lindo ,GINO, What’ Best等),它的主要功 能是求解大型线性、非线性和整数规划问题,目前常用的版本 是V11.0。 Lingo的主要功能特色为: ( 1)既能求解线性规划问题,也有较强的求解非线性规划 问题的能力; (2)输入模型简练直观; (3)运行速度快、计算能力强; ( 4)内置建模语言,提供几十个内部函数,从而能以较少 语句,较直观的方式描述较大规模的优化模型; ( 5)将集合的概念引入编程语言,很容易将实际问题转换 为Lingo模型; (6)能方便地与Excel、数据库等其他软件交换数据。

Lingo概况

使用Lingo建模需要注意的几个基本问题
1、尽量使用实数优化,减少整数约束和整数变量;

2、尽量使用光滑优化,减少非光滑约束的个数,
如:尽量少使用绝对值、符号函数、多个变量求最大/ 最小值、四舍五入、取整函数等; 3、尽量使用线性模型,减少非线性约束和非线性变量的 个数,(如x/y <5 改为x<5y);

4、合理设定变量上下界,尽可能给出变量初始值;
5、模型中使用的参数数量级要适当(如小于103)。

使用LINGO需要掌握的几个重要方面
正确阅读求解报告(Solution Report) 掌握敏感性分析(Range Report)

三个界面

集合(SETS)的应用;
正确理解求解状态窗口(Solver Status)

学会设置基本的求解选项(OPTIONS) ;
掌握与外部文件的基本接口方法。

例3

加工奶制品的生产计划(教材P85)
12小时 8小时 3公斤A1 获利24元/公斤

1桶 牛奶 或

4公斤A2
时间480小时

获利16元/公斤
至多加工100公斤A1

每天: 50桶牛奶

制订生产计划,使每天获利最大 ? 35元可买到1桶牛奶,买吗?若买,每天最多买多少? ? 可聘用临时工人,付出的工资最多是每小时几元? ? A1的获利增加到 30元/公斤,应否改变生产计划?

1桶 牛奶 或

12小时

3公斤A1 4公斤A2

获利24元/公斤 获利16元/公斤

每天

8小时 50桶牛奶 时间480小时 x1桶牛奶生产A1

至多加工100公斤A1
x2桶牛奶生产A2

决策变量

目标函数

获利 24×3x1 获利 16×4 x2 每天获利 Max z ? 72x1 ? 64x2 原料供应

x1 ? x2 ? 50
12x1 ? 8x2 ? 480

约束条件

劳动时间 加工能力 非负约束

3x1 ? 100 x1 , x2 ? 0

模型求解
OBJECTIVE FUNCTION VALUE

Model:

max=72*x1+64*x2;
x1+x2<50; 12*x1+8*x2<480;

1)
VARIABLE X1

3360.000
VALUE 20.000000 REDUCED COST 0.000000

3*x1<100;
end DO RANGE (SENSITIVITY) No ANALYSIS?

X2

30.000000

0.000000

ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 48.000000

3)
4)

0.000000
40.000000 2

2.000000
0.000000

NO. ITERATIONS=

20桶牛奶生产A1, 30桶生产A2,利润3360元。

模型求解
OBJECTIVE FUNCTION VALUE 1) VARIABLE X1 X2 3360.000 VALUE 20.000000 30.000000

可不掌握

REDUCED COST 0.000000 0.000000

reduced cost值表示 当该非基变量增加 一个单位时(其他 非基变量保持不变) 目标函数减少的量 (对max型问题) 也可理解为: 为了使该非基变量 变成基变量,目标 函数中对应系数应 增加的量

ROW SLACK OR SURPLUS DUAL PRICES 2) 3) 4) 0.000000 0.000000 40.000000 2 48.000000 2.000000 0.000000

NO. ITERATIONS=

结果解释
Model: max=72*x1+64*x2; x1+x2<50; 12*x1+8*x2<480; 3*x1<100; end
OBJECTIVE FUNCTION VALUE 1) VARIABLE X1 X2 3360.000 VALUE 20.000000 30.000000 REDUCED COST 0.000000 0.000000 DUAL PRICES

ROW SLACK OR SURPLUS

原料无剩余 三 2) 0.000000 48.000000 种 时间无剩余 3) 0.000000 2.000000 资 加工能力剩余40 4) 40.000000 0.000000 源 “资源” 剩余为零的约束为紧约束(有效约束)

结果解释

OBJECTIVE FUNCTION VALUE
1) 3360.000 VALUE REDUCED COST

最优解下“资源”增加1 VARIABLE 单位时“效益”的增量
X1
X2

20.000000
30.000000

0.000000
0.000000 DUAL PRICES

影子价格 原料增1单位, 利润增48 时间加1单位, 利润增2 能力增减不影响利润

ROW SLACK OR SURPLUS

2)
3) 4)

0.000000
0.000000 40.000000

48.000000
2.000000 0.000000

? 35元可买到1桶牛奶,要买吗?

35 <48, 应该买! 2元!

? 聘用临时工人付出的工资最多每小时几元?

结果解释
Yes DO RANGE(SENSITIVITY) ANALYSIS? RANGES IN WHICH THE BASIS IS UNCHANGED: OBJ COEFFICIENT RANGES VARIABLE CURRENT ALLOWABLE ALLOWABLE COEF INCREASE DECREASE
X1 X2 72.000000 24.000000 8.000000 64.000000 8.000000 16.000000 RIGHTHAND SIDE RANGES CURRENT ALLOWABLE ALLOWABLE RHS INCREASE DECREASE 50.000000 10.000000 6.666667

最优解不变时目标 系数允许变化范围 (约束条件不变) x1系数范围(64,96) x2系数范围(48,72)
x1系数由24?3= 72 增加为30?3= 90, 在允许范围内 不变!

ROW
2

3
4

480.000000
100.000000

53.333332
INFINITY

80.000000
40.000000

? A1获利增加到 30元/千克,应否改变生产计划

结果解释
RANGES IN WHICH THE BASIS IS UNCHANGED: OBJ COEFFICIENT RANGES VARIABLE CURRENT ALLOWABLE ALLOWABLE COEF INCREASE DECREASE X1 X2 ROW 72.000000 24.000000 8.000000

影子价格有意义 时约束右端的允 许变化范围
(目标函数不变)

64.000000 8.000000 16.000000 RIGHTHAND SIDE RANGES CURRENT ALLOWABLE ALLOWABLE RHS INCREASE DECREASE

2
3 4

50.000000
480.000000 100.000000

10.000000
53.333332 INFINITY

6.666667
80.000000 40.000000

原料最多增加10
时间最多增加53

? 35元可买到1桶牛奶,每天最多买多少?

最多买10桶?

灵敏度分析
?

敏感性分析的作用是给出“Ranges in which the basis is

unchanged”,即研究当目标函数的系数和约束右端项在什么范围 变化(此时假定其他系数保持不变)时,最优基(矩阵)保持不变。 注意:这里LINGO不询问是否进行敏感性分析。如果需要进行敏感 性分析,必须用“LINGO |Options”命令打开系统选项对话框,在 “General Solver”标签下的“Dual Computations”下拉列表中选 中“Prices & Range”,再按下“OK”按钮激活敏感性分析功能。 修改了系统选项后,以后只需调用“LINGO |Range”命令即可进行 敏感性分析了。

?

修改运行时的 内存限制

激活灵敏度 分析

结 论
? 应该批准用35元买1桶牛奶的投资,但每天最

多购买10桶牛奶。
? 可以用低于2元/h的工资聘用临时工人以增加劳

动时间,但最多增加53.3333h。
? 若每千克A1的获利增加到30元,则x1系数变为

30×3=90,在允许的范围内,所以不应改变生 产计划,但最优值变为90×20+64×30=3720。

例 4 SAILCO公司需要决定下四个季度的帆船生 产量。下四个季度的帆船需求量分别是40条,60 条,75条,25条,这些需求必须按时满足。每个 季度正常的生产能力是40条帆船,每条船的生产 费用为400美元。如果加班生产,每条船的生产 费用为450美元。每个季度末,每条船的库存费 用为20美元,假定生产提前期为0,初始库存为 10条船。如何安排生产可使总费用最小?

DEM——需求量,RP——正常生产的产量,OP——加班生产 的产量,INV——库存量

目标函数: Min

??400RP( I ) ? 450OP( I ) ? 20INV ( I )?
I ?1

4

约束条件: (1)能力限制 RP(I)≤40,I=1,2,3,4 (2)产品数量的平衡方程 INV(I)=INV(I-1)+RP(I)+OP(I)-DEM(I) I=1, 2, 3, 4 INV(0)=10; (3)变量的非负约束

Lingo优化模型
集合

属性

Min ??400RP( I ) ? 450OP( I ) ? 20 INV ( I )?
I ?1

4

约束条件主要有两个:
(1)能力限制

RP(I)≤40,I=1,2,3,4
(2)产品数量的平衡方程
INV(I)=INV(I-1)+RP(I)+OP(I)-DEM(I)

I=1,2,3,4 INV(0)=10;

集合的属性相当于以集合的元素为下标的数组

Lingo模型的基本要素
(1)集合段(SETS) (2)目标与约束段 (3)数据段(DATA):作用在于对集合的属性(数组)
输入必要的常数数据。格式为: attribute(属性)=value _list(常数列表); 常数列表(value _list)中数据之间可以用逗号“,”分开, 也可以用空格分开(回车的作用也等价于一个空格) “变量名=?;” ——运行时赋值

(4)初始段(INIT)——赋初值 (5)计算段(CALC)——预处理

例5 使用LINGO软件计算6个生产点8个销售点的最 小费用运输问题。产销单位运价如下表。
单 位 运 销地 B1 B2
2 9

B3
6 5

B4
7 3

B5
4 8

B6
2 5

B7
5 8

B8
9 2

产 量
60 55

产地
A1 A2


6 4

A3
A4

5
7

2
6

1
7

9
3

7
9

4
2

3
7

3
1

51
43

A5
A6

2
5 35

3
5 37

9
2 22

5
2 32

7
8 41

2
1 32

6
4 43

5
3 38

41
52

销量

模型:

min z ? ?? cij xij
i ?1 j ?1

6

8

s.t.

?x
j ?1

8

ij

? ai

?x
i ?1

6

i ? 1, 2,
ij

,6 ,8
,8

? bj

j ? 1, 2,

xij ? 0 i ? 1, 2,

, 6; j ? 1, 2,

model: !6发点8收点运输问题; sets: warehouses/wh1..wh6/: capacity; vendors/v1..v8/: demand; links(warehouses,vendors): cost, volume; endsets !目标函数; min=@sum(links: cost*volume); !需求约束; @for(vendors(J): @sum(warehouses(I): volume(I,J))=demand(J)); !产量约束; @for(warehouses(I): @sum(vendors(J): volume(I,J))<=capacity(I)); !这里是数据; data: capacity=60 55 51 43 41 52; demand=35 37 22 32 41 32 43 38; cost=6 2 6 7 4 2 9 5 49538582 52197433 76739271 23957265 5 5 2 2 8 1 4 3; enddata end

MATLAB中有关求解线性规划问题的指令
?

X=linprog(c,A,b,Aeq,beq)
X=linprog(c,A,b,Aeq,beq,vlb,vub) X=linprog(c,A,b,Aeq,beq,vlb,vub,x0)

?

?

?

X=linprog(c,A,b,Aeq,beq,vlb,vub,x0,options)
[x,fval,exitflag,output]= linprog(…)

?

用MATLAB优化工具箱解线性规划
1、模型:

min z=cX
s.t. AX ? b

命令:x=linprog(c,A,b)

2、模型:min z=cX s.t. AX ? b Aeq ? X ? beq 命令:x=linprog(c,A,b,Aeq,beq)
AX ? b 存在,则令A=[ ],b=[ ]. 注意:若没有不等式:

3、模型:min z=cX s.t. AX ? b Aeq ? X ? beq VLB≤X≤VUB
命令:[1] x=linprog(c,A,b,Aeq,beq, VLB,VUB) [2] x=linprog(c,A,b,Aeq,beq, VLB,VUB, X0) 注意:[1] 若没有等式约束: Aeq ? X ? beq , 则令Aeq=[ ], beq=[ ]. [2]其中X0表示初始点 4、命令:[x,fval]=linprog(…) 返回最优解x及x处的目标函数值fval.

例6

max

s.t.

z ? 0.4x1 ? 0.28x2 ? 0.32x3 ? 0.72x4 ? 0.64x5 ? 0.6x6 0.01x1 ? 0.01x2 ? 0.01x3 ? 0.03x4 ? 0.03x5 ? 0.03x6 ? 850 0.02x1 ? 0.05x4 ? 700 0.02x2 ? 0.05x5 ? 100 0.03x3 ? 0.08x6 ? 900

xj ? 0

j ? 1,2,?6

解 编写M文件xxgh1.m如下: c=[-0.4 -0.28 -0.32 -0.72 -0.64 -0.6]; A=[0.01 0.01 0.01 0.03 0.03 0.03;0.02 0 0 0.05 0 0;0 0.02 0 0 0.05 0;0 0 0.03 0 0 0.08]; b=[850;700;100;900]; Aeq=[]; beq=[]; vlb=[0;0;0;0;0;0]; vub=[]; [x,fval]=linprog(c,A,b,Aeq,beq,vlb,vub)

To Matlab (xxgh1)

例7

min z ? 6x1 ? 3x2 ? 4x3 s.t. x1 ? x2 ? x3 ? 120 x1 ? 30 0 ? x2 ? 50 x3 ? 20

m in z ? (6

3

? x1 4)? ? x2 ? x3

? ? ? ?

s.t .

?1 ? ?0 ?

解: 编写M文件xxgh2.m如下: c=[6 3 4]; A=[0 1 0]; b=[50]; Aeq=[1 1 1]; beq=[120]; To Matlab (xxgh2) vlb=[30,0,20]; vub=[]; [x,fval]=linprog(c,A,b,Aeq,beq,vlb,vub)

? x1 1 ?? ?? x2 1 0? ?? x ? 3 ? x1 ? ? 3 0? ? 0 ? ? ?x ? ? 2 ? ? 2 0? ? ? ? x3 ? 1

? ? ?1 2 0? ??? ? 50 ? ? ? ? ? ?

例1的Matlab求解
改写为: S.t.

问题

min z ? ?13 9 10 11 12 8?X
0 0 ? ? 0.4 1.1 1 0 ? 800 ? ? ? ? X ?? ? 0 ? ? ? 0 0 0 . 5 1 . 2 1 . 3 900 ? ? ? ?
? x1 ? ? ? ? x2 ? ?x ? 3 ??0 ,X ?? ? x4 ? ?x ? ? 5? ?x ? ? 6?

?1 0 0 1 0 0? ? 400 ? ? ? ? ? ? 0 1 0 0 1 0 ? X ? ? 600 ? ?0 0 1 0 0 1? ? 500 ? ? ? ? ?

编写M文件xxgh3.m如下: f = [13 9 10 11 12 8]; A = [0.4 1.1 1 0 0 0 0 0 0 0.5 1.2 1.3]; b = [800; 900]; Aeq=[1 0 0 1 0 0 010010 0 0 1 0 0 1]; beq=[400 600 500]; vlb = zeros(6,1); vub=[]; [x,fval] = linprog(f,A,b,Aeq,beq,vlb,vub)

结果:
x= 0.0000 600.0000 0.0000 400.0000 0.0000 500.0000 fval =1.3800e+004 即在甲机床上加工600个工件2,在乙机床上加工400个工件1、500个 工件3,可在满足条件的情况下使总加工费最小为13800。 返回

例2的Matlab求解
改写为:
min z ? ?40
s.t.

? x1 ? 36 ?? ?x ? ? ? 2?

?? 5

? x1 ? ? 3?? ?x ? ? ? (?45) ? 2?

编写M文件xxgh4.m如下: c = [40;36]; A=[-5 -3]; b=[-45]; Aeq=[]; beq=[]; vlb = zeros(2,1); vub=[9;15]; %调用linprog函数: [x,fval] = linprog(c,A,b,Aeq,beq,vlb,vub)

结果为: x= 9.0000 0.0000 fval =360 即只需聘用9个一级检验员。

注:本问题应还有一个约束条件:x1、x2取整数。故它是一
个整数线性规划问题。这里把它当成一个线性规划来解,求得 其最优解刚好是整数:x1=9,x2=0,故它就是该整数规划的最 优解。若用线性规划解法求得的最优解不是整数,将其取整后 不一定是相应整数规划的最优解,这样的整数规划要用专门的 方法求解。 返回

例3的Matlab求解
编写M文件如下: c = [-72 -64]; A=[1 1;12 8; 3 0]; b=[50 480 100]; Aeq=[]; beq=[]; %调用linprog函数: [x,fval] = linprog(c,A,b,Aeq,beq)

问题
max=72*x1+64*x2; x1+x2<=50; 12*x1+8*x2<=480; 3*x1<=100; 结果为: x= 20.0000 30.0000 fval =-3.3600e+003 即用20桶牛奶生产X1,30桶牛奶生 产X2。

三、整数规划和01规划
min(or max)u ? f ( x) x ? ?

s. t. hi ( x) ? 0, i ? 1,2,...,m.
gi ( x) ? 0( gi ( x) ? 0),i ? 1,2,..., p.
其中决策变量为整数或者为01
? 整数约束:@gin(x);

0-1约束:@bin(x)

例6 混合泳接力队的选拔 (教材P108)
5名候选人的百米成绩
蝶泳 仰泳 蛙泳 自由泳 甲 1’06”8 1’15”6 1’27” 58”6 乙 57”2 1’06” 1’06”4 53” 丙 1’18” 1’07”8 1’24”6 59”4 丁 1’10” 1’14”2 1’09”6 57”2 戊 1’07”4 1’11” 1’23”8 1’02”4

如何选拔队员组成4?100米混合泳接力队?

穷举法:组成接力队的方案共有5!=120种。

0-1规划模型
cij j=1 j=2 j=3 j=4 i=1 66.8 75.6 87 58.6

cij(秒)~队员i 第j 种泳姿的百米成绩
i=2 57.2 66 66.4 53
4 5

i=3 78 67.8 84.6 59.4

i=4 70 74.2 69.6 57.2

i=5 67.4 71 83.8 62.4

若选择队员i参加泳姿j 的比赛,记xij=1, 否则记xij=0

目标 函数
约束 条件

Min

Z ? ?? cij xij
j ?1 i ?1

每人最多入选泳姿之一

每种泳姿有且只有1人

?x
j ?1

4

ij

? 1, i ? 1,?5

?x
i ?1

5

ij

? 1, j ? 1,? 4

模型求解

输入LINGO求解
min=@sum(link: c*x); @for(person(i): @sum(position(j):x(i,j))<=1;); @for(position(i): @sum(person(j):x(j,i))=1;); @for(link: @bin(x)); END

MODEL: sets: person/1..5/; position/1..4/; link(person,position): c, x; endsets data: c= 66.8, 75.6, 87, 58.6, 57.2, 66, 66.4, 53, 78, 67.8, 84.6, 59.4, 70, 74.2, 69.6, 57.2, 67.4, 71, 83.8, 62.4; enddata

01约束

四、经典的线性规划模型
问题1 运输问题(参见例5)

设某种物资共有 m 个产地 A1,A2,…,Am,各 产地的产量分别是a1,a2 ,…,am;有n 个销地 B1,

B2,…,Bn ,各销地的销量分别为b1,b2,…,bn .
假定从产地Ai(i =1,2,…,m)向销地Bj(j =1, 2,…,n)运输单位物资的运价是cij,问怎样调运才能 使总运费最小?

设 xij 表示产地 Ai 运往销地 Bj (i=1,2,…,m;

j=1,2,…,n) 的运量.
1、产销平衡问题
m


n i ?1 j ?1

? a ? ?b
i ?1 i j ?1

m

n

j

min z ? ?? cij xij
s.t.

?x
j ?1

n

ij

? ai

?x
i ?1

m

i ? 1, 2,
ij

,m ,n
, m; j ? 1, 2, ,n

? bj

j ? 1, 2,

xij ? 0 i ? 1, 2,

2、产销不平衡问题 当

? a ? ?b
i ?1 i j ?1

m

n

j



? a ? ?b
i ?1 i j ?1

m

n

j

min z ? ?? cij xij
i ?1 j ?1
ij

m

n

min z ? ?? cij xij
i ?1 j ?1
ij

m

n

s.t.

?x
j ?1

n

? ai

s.t.

?x
j ?1

n

? ai

i ? 1, 2,
ij

,m

i ? 1, 2,
ij

,m

?x
i ?1

m

? bj

?x
i ?1

m

? bj

j ? 1, 2,

,n

j ? 1, 2,

,n
,n

xij ? 0 i ? 1, 2,

, m; j ? 1, 2,

, n xij ? 0 i ? 1, 2,

, m; j ? 1, 2,

问题2

生产组织与计划问题

工厂用m 种设备 A 1 , A2 ,

, Am生产n种产品B1 , B2 ,

,

Bn .在一个生产周期内, 已知第i 台设备 Ai只能工作 ai 个
机时. 工厂必须完成产品 B j至少 b j 件. 设备A 生产B j 所
i

需要的机时和成本分别为tij , cij . 试建立相应的数学模型, 使设备能在计划周期内完成计划但又使成本达到最低.

模型为

min z ? ? cij xij ,
i, j

s.t.

? n ?? tij xij ? ai , i ? 1,2, , m, ? j ?1 ?m ? x ? b , j ? 1,2, , n, ? ij j ? ? i ?1

xij ? 0, xij ? I .

问题3

工厂选址问题

设有 n 个需求点(城市, 仓库, 商店等), 有m个可供 选择的建厂地址, 每个地址最多可建一个工厂. 在 i 地 间的固定成本为ai ,需求点 j的需求量为b j ,从厂址i 到 址建立工厂的生产能力为Di , 在i 地址经营工厂, 单位时

需求点 j的单位运费为cij ,问应如何选择厂址和安排运
输计划, 使相应的成本为最小.

模型为

min z ? ? cij xij ? ? ai yi
i, j i ?1

m

s.t.

? n ?? xij ? Di yi ? j ?1 ?m ? x ?b ? ij j ? ? i?1

i ? 1, 2, j ? 1, 2,

, m, , n.

xij ? 0, y j ? 0 ? 1.

上式中 yi 的意义是:

?1, 在地址i 建厂, yi ? ? ?0, 不在地址i 建厂.
这样的线性规划称为混合型的整数线性规划.

问题4

设备购置和安装问题

, Am ,设备Ai的单价为 pi ,工厂已有第i 种设备ai台,i ? 1, 2, , m. 今有资金 M
元, 可用于购置这些设备. 该厂有n 处可安装这些设备,

工厂需要 m 种设备A 1 , A2 ,

B j处最多可安装b j 台,

济效益为 ij 元, 问应如何购置和安装这些设备, 才能使 总的经济效益最高.


c

将一台设备 A 安装在B j 处, 经
i

xij表示设备 Ai 在 B j处安装的台数, yi表示购置 Ai

的台数, 则模型为

max z ? ? cij xij
? s.t. ?? xij ? yi ? ai ? j ?1 ?m ?? xij ? b j , ? i?1 ?m ?? pi yi ? M ? ? i?1
n

i, j

i ? 1, 2, j ? 1, 2,

, m, , n.

xij ? 0, xij ? I .

问题5

货郎问题(旅行商问题,Travel Salesman Problem)
i

的距离为d ij ,如何选择一条道路, 使得货郎每个地方走 一遍后回到起点, 且所走的路径最短.

货郎要到n 个地方去卖货. 已知两个地方 A 和 A j 之间

定义

?1, 货郎选择的路线包含从 Ai 到 Aj 的路径 xij ? ? ?0, 否则

则相应的模型为

min z ? ? dij xij
? i ? 1, 2, , n, s.t. ?? xij ? 1, ? j ?1 ? n j ? 1, 2, , n. ?? xij ? 1, ? i ?1 ? m ? ? xij ? S ? 1, 2 ? S ? n ? 1, S ? ?1, 2, ?i , j?S
n

i, j

, n?.

xij ??0,1? , i, j ? 1, 2,

, n, i ? j.

基于旅行商问题的中文规则碎纸拼接

完整文件原文

基于旅行商问题的中文规则碎纸拼接

只有纵切的规 则碎片

问题6

系统可靠性问题

的元件可从集合S i中挑选. 对元件j ? Si ,用cij 表示元 件 j在第 i个位置上的花费,

选择 n 个元件, 组成一个并联系统. 设第i 个位置所用

pij 表示其可靠性的概率,



应如何配置各位置上的元件, 使得系统的可靠性不小于

? ,且使总费用最小.
定义

j 用在位置 i上 , ?1, 若元件 j ? Si 且元件 xij ? ? j 不用在位置 i上 , ?0, 若元件 j ? Si 且元件

总费用为

z ,其可靠性为
n

? xij ? R ? 1 ? ? ?? ?1 ? pij ? ? ? ? . i ?1 ? j?Si ? 若记 aij ? ln ?1 ? pij ? , M ? ln ?1 ? ? ? , 则上式可写成

?? a x
i ?1 j?Si

n

ij ij

? M.

相应的模型转化为0 ? 1规划.

模型为

min z ? ?? cij xij
i ?1 j?Si

n

s.t.

? n n ??? aij xij ? M , ? i?1 j ?1 ? ? x ? 1, i ? 1, 2, ? ij ? ? j?Si

,n

xij ??0,1? ,

i ? 1, 2,

, n, j ? Si .

作业
练习1 铁路平板车装货问题(用Lingo求解) 有七种规格的包装箱要装到两节铁路平板车上去。 包装箱的宽和高是一样的,厚度(t,cm 计)及重量 (w,kg计)不同。表1给出了包装箱的厚度、重量以及 数量。每节平板车有10.2m 长的地方可装包装箱,载重 为40t。由于当地货运的限制,对于C5, C6, C7 类包装 箱的总数有一个特别限制:箱子所占的空间(厚度)不 能超过302.7cm。试把包装箱装到平板车上,使得浪费 空间最小。

种类
t/cm w/kg

C1 48.7 2000

C2 53.0 3000

C3 61.3 1000

C4 72.0 500

C5 48.7 4000

C6 52.0 2000

C7 64.0 1000

n/件

8

7

9

6

6

4

8

练习2 展厅监控问题 (试求出所有可能的解—用Lingo和matlab求解)
展厅保安监控问题——海湾艺术馆考虑安装一系列摄像安全系 统以减少其保安费用。下图是海湾艺术馆用于展览的8间展厅的示 意图。各展厅之间的通道显示为⑴ - ⒀。一家保安公司建议在一些 通道安装双向摄像机。每架摄象机都可以很好地监控通道两侧的展 厅。例如:在通道⑷处安装摄象机,则展厅 1 和 4 就可以完全被监 控到,等等。管理层用最少数量的双向摄像机覆盖所有的8间展厅。
展厅7 (2) 展厅3 (1) 展厅1 (5) (3) 展厅4 (4) (6) (7) (9) 展厅5 (8) 展厅2 (10) (11) 展厅8 (13) 展厅6 (12)


推荐相关:

2015数学建模提高班专题1规划专题_图文.ppt

2015数学建模提高班专题1规划专题 - 2015数学建模提高班 规划模

数学建模提高班专题一--规划模型、案例和软..._图文.ppt

数学建模提高班专题一--规划模型、案例和软..._数学_自然科学_专业资料。数学建模提高班专题一--规划模型、案例和软... 历届竞赛赛题基本解法赛题 93A非线性交...

数学建模提高班专题一--规划模型、案例及软件求解(2010....ppt

数学建模提高班专题一--规划模型、案例及软件求解(2010-4-10)final

数学建模提高班专题5时间序列建模_图文.ppt

建模提高班专题5时间序列建模 2015数学建模提高班 差分方程与时间序列模型

2016数学建模提高班专题六网络优化模及案例分析资料_图文.ppt

? ? ? ? ? 从农夫怎样过河谈起 图是种思考问题的 2016数学建模提高班网络优化模型及案例分析专题 赵承业 2016/5/7 内部资料,版权所有,请勿外传,侵权...

2017数学建模提高班专题5时间序列分析_图文.ppt

2017数学建模提高班专题5时间序列分析 - 2017数学建模提高班 专题五:时间序列分析 柴中林 2017/4/23 课件提纲 ?1时间序列的引例与概念 ?2时间序列中的趋势...

2017数学建模提高班专题2 统计回归方法及Matlab软....ppt

2017数学建模提高班 ---统计回归及软件实现专题 刘学艺 2017/03/1

2015年数学建模考试试卷0.doc

湖南第师范学院数学与计算科学学院 2015 年《线性规划数学建模》考查试题考

数学建模提高班专题一--规划模型、案例及软件求解(2010....ppt

数学建模提高班专题一--规划模型、案例及软件求解(2010-4-10)final

2015年数学建模作业题.doc

2015年数学建模作业_学科竞赛_初中教育_教育专区。...9,10 37、自行车生产规划家公司生产儿童自行车...2011数学建模提高班第四... 8页 免费 ...

2015深圳杯数学建模d题航班延误问题_图文.doc

2015深圳杯数学建模d题航班延误问题_数学_自然科学_专业资料。航班延误问题摘要...构造动态规划模 型,最后为航空公司提供种合理的管理措施,即延误时长在一定的...

2015年数学建模06_图文.ppt

11.04.24完成制作主讲教师:张卫§4雀巢等等巧妙建模之 607 授课对象:湖南师范大学2011年校选课数学建模班 时间:11.04.28 思考题6-1: 问题1中6改为7,或改为...

华农数模考试考试题.doc

华农数模考试考试_理学_高等教育_教育专区。华农数模考试考试题 2011 年数学建模提高班暨数学建模集训选拔试题姓名 学号 Email 注意事项 1.试卷答卷以电子版提交,...

数学建模考试题(开卷)].pdf

2014-2015 年第二学期 数学建模考试题 (开卷) (在如下问题中任选一题

《数学建模》选修课班第1-4次作业.doc

数学建模》选修课班第1-4次作业_理学_高等教育_...规划论模型 3.静态模型和动态模型 , 离散模型和...1.让读者尽快了解论文的主要内容,以补充题名的缺乏...

数学建模比赛的选拔问题(1)..doc

数学建模比赛的选拔问题卢艳阳 王伟 朱亮亮(黄河科技...然后利用 0-1 规划的 相关知识对这 9 人进行合理...而对于本题中,我们只需要考虑数学基础和计算机 编程...

2015南通大学数学建模竞赛A题.doc

2015南通大学数学建模竞赛A_理学_高等教育_教育专区。2015 年南通大学数学建模...“左转弯待转区”这一硬性条件下,通过线性规划和建立 函数关系式,合理分析出该...

农场规划问题数学建模.doc

数模方法及主要结果:在本题中,我们按照数学建模的...来解决这个线性规划问题,打开个新文件运 软件实现...来养殖些鸡、牛和种植些农作物来进一步提高家庭年净...

航班延误数学建模论文_图文.doc

2015 年吉林省大学生数学建模竞赛 承 诺 书 我们...构造动态规划模型,最后为航空公司提供了种合理的...班数 准点率 航空公司 原因 流量原因 天气原因 ...

数学建模培训_图文.ppt

欢迎参加 数学建模培训仰恩大学数学系 吴建国 开设数学建模培训班的目的 ? 是数学建模研究会的活动之一。 ? 是为参加今年9月19日举行的全国大学生数...

网站首页 | 网站地图
All rights reserved Powered by 学霸学习网 www.tceic.com
copyright ©right 2010-2021。
文档资料库内容来自网络,如有侵犯请联系客服。zhit325@126.com