教案.docx
- 文档编号:3134077
- 上传时间:2023-05-05
- 格式:DOCX
- 页数:15
- 大小:230.17KB
教案.docx
《教案.docx》由会员分享,可在线阅读,更多相关《教案.docx(15页珍藏版)》请在冰点文库上搜索。
教案
B题钢管订购和运输
要铺设一条
的输送天然气的主管道,如图一所示(见下页)。
经筛选后可以生产这种主管道钢管的钢厂有
。
图中粗线表示铁路,单细线表示公路,双细线表示要铺设的管道(假设沿管道或者原来有公路,或者建有施工公路),圆圈表示火车站,每段铁路、公路和管道旁的阿拉伯数字表示里程(单位km)。
为方便计,1km主管道钢管称为1单位钢管。
一个钢厂如果承担制造这种钢管,至少需要生产500个单位。
钢厂
在指定期限内能生产该钢管的最大数量为
个单位,钢管出厂销价1单位钢管为
万元,如下表:
1
2
3
4
5
6
7
800
800
1000
2000
2000
2000
3000
160
155
155
160
155
150
160
1单位钢管的铁路运价如下表:
里程(km)
≤300
301~350
351~400
401~450
451~500
运价(万元)
20
23
26
29
32
里程(km)
501~600
601~700
701~800
801~900
901~1000
运价(万元)
37
44
50
55
60
1000km以上每增加1至100km运价增加5万元。
公路运输费用为1单位钢管每公里0.1万元(不足整公里部分按整公里计算)。
钢管可由铁路、公路运往铺设地点(不只是运到点
,而是管道全线)。
(1)请制定一个主管道钢管的订购和运输计划,使总费用最小(给出总费用)。
(2)请就
(1)的模型分析:
哪个钢厂钢管的销价的变化对购运计划和总费用影响最大,哪个钢厂钢管的产量的上限的变化对购运计划和总费用的影响最大,并给出相应的数字结果。
(3)如果要铺设的管道不是一条线,而是一个树形图,铁路、公路和管道构成网络,请就这种更一般的情形给出一种解决办法,并对图二按
(1)的要求给出模型和结果。
线性规划(LinearProgramming缩写为LP)是运筹学的重要分支之一,在实际中应用得较广泛,其方法也较成熟,借助计算机,使得计算更方便,应用领域更广泛和深入。
线性规划通常解决下列两类问题
(1)当任务或目标确定后,如何统筹兼顾,合理安排,用最少的资源(如资金、设备、原标材料、人工、时间等)去完成确定的任务或目标;
(2)在一定的资源条件限制下,如何组织安排生产获得最好的经济效益(如产品量最多、利润最大.
【例1.1】某企业计划生产甲、乙、丙三种产品。
这些产品分别要在A、B、C、D、四种不同的设备上加工。
按工艺资料规定,单件产品在不同设备上加工所需要的台时如表1-1所示,已知各设备在计划期内的能力分别为20、15、16、12小时;每生产一件甲、乙、丙三种产品,企业可获得利润分别为4、3、5元。
企业决策者应如何安排生产计划,使企业在计划期内总的利润收入最大?
产品
设备
甲乙丙
设备能力
(小时)
A
312
20
B
224
15
C
401
16
D
035
12
利润(元/件)
435
【解】设x1、x2、x3分别为甲、乙、丙三种产品的产量数学模型为:
线性规划的数学模型由
决策变量Decisionvariables
目标函数Objectivefunction
及约束条件Constraints
构成。
称为三个要素。
怎样辨别一个模型是线性规划模型?
⏹其特征是:
⏹1.解决问题的目标函数是多个决策变量的
线性函数,通常是求最大值或最小值;
⏹2.解决问题的约束条件是一组多个决策变量
的线性不等式或等式。
【例1.3】下料问题,某一机床需要用甲、乙、丙三种规格的轴各一根,这些轴的规格分别是2.9,2.1,1.5(m),这些轴需要用同一种圆钢来做,圆钢长度为7.4m。
现在要制造100台机床,最少要用多少圆钢.
第一步:
设一根圆钢切割成甲、乙、丙三种轴的根数分别为y1,y2,y3,则切割方式可用不等式2.9y1+2.1y2+1.5y3≤7.4表示,象这样的非负整数解共有8组,也就是有8种下料方式,如表1-2所示。
第二步:
建立线性规划数学模型。
设xj(j=1,2…,8)为第j种下料方案所用圆钢的根数。
则数学模型为
2.9y1+2.1y2+1.5y3≤7.4
方案
规格
1
2
3
4
5
6
7
8
需求量
y1(2.9m)
2
1
1
1
0
0
0
0
100
y2(2.1m)
0
2
1
0
3
2
1
0
100
y3(1.5m)
1
0
1
3
0
2
3
4
100
0.1
0.3
0.9
0
1.1
0.2
0.8
1.4
minz=x1+x2+x3+x4+x5+x6+x7+x8
•2x1+x2+x3+x4100
•2x2+x3+3x5+2x6+x7100
•x1+x3+3x4+2x6+3x7+4x8100
•xj0,j=1,2,…,8
求得最优解为x1=40,x2=20,x6=30,其余x为零,即第一种方案用料40根,第二种方案用20根,第六种方案用30根,共计用料90根。
minz=0.1x1+0.3x2+0.9x3+1.1x5+0.2x6+0.8x7+1.4x8
最优下料方案为:
第一种方案用料40根,第二种方案20根,第六种方案30根,总余料为16m。
【例1.4】配料问题。
某一合金公司同一科研单位签订一项包含有四种金属的合金订购单,要求的成分规格是:
金属A不少于23%,金属B不多于15%,金属C不多于4%,金属D要界于35%~65%之间,不允许有其他成分。
合金公司拟从六种不同级别的矿石中进行冶炼,每种矿物的成分含量和价格如表1-3所示。
矿石杂质在治炼过程中废弃,现要求也每吨合金成本最低的矿物数量。
假设矿石在冶炼过程中,金属含量没有发生变化。
金属
矿石
A%
B%
C%
D%
杂质%
费用
(元/t)
1
25
10
10
25
30
23
2
40
0
0
30
30
20
3
20
10
0
30
40
18
4
0
15
5
20
60
10
5
20
20
0
40
20
27
6
8
5
15
17
55
12
【解】设xj(j=1,2…,6)是第j种矿石数量,目标函数是总成本最少,得到下列线性规划模型
minZ=23x1+20x2+18x3+10x4+27x5+12x6
【例1.5】投资问题。
某投资公司在第一年有100万元资金,每年都有如下的投资方案可供考虑采纳:
“假使第一年投入一笔资金,第二年又继续投入此资金的50%,那么到第三年就可回收第一年投入资金的一倍金额。
”投资公司要设法决定最优的投资策略使第六年所掌握的资金最多。
解:
设x1为第一年的投资;x2为第一年的保留资金
x1+x2=100
第二年:
x3为第二年新的投资;x4:
第二年的保留资金;
第三年:
x5为新的投资;x6:
第三年的保留资
第四年:
新的投资x7;第四年的保留资金x8;
第五年:
x9为第五年的保留资金:
第五年不再进行新的投资,因为这笔投资要到第七年才能回收。
约束条件保证每年满足如下的关系:
追加投资金额+新投资金额+保留资金=可利用的资金总额
⏹到第六年实有资金总额为x9+2x7,整理后得到下列线性规划模型
maxZ=2x7+x9
用单纯形法解得:
X=(22.64,72.36,58.54,0,26.02,0,104.06,0,0)’。
Z=208.12。
即:
第一年投资22.64元;
第二年新投资58.54元;
第三年新投资26.02元;
第四年新投资104.06元;
第六年末有资金208.12万元。
一般地,假设线性规划数学模型中,有m个约束,有n个决策变量xj,j=1,2…,n,目标函数的变量系数用cj表示,cj称为价值系数。
约束条件的变量系数用aij表示,aij称为工艺系数。
约束条件右端的常数用bi表示,bi称为资源限量。
则线性规划数学模型的一般表达式可写成
运输问题
人们在从事生产活动中,不可避免地要进行物资调运工作。
如某时期内将生产基地的煤、钢铁、粮食等各类物资,分别运到需要这些物资的地区,根据各地的生产量和需要量及各地之间的运输费用,如何制定一个运输方案,使总的运输费用最小。
这样的问题称为运输问题。
运输问题的特征
每一个出发地都有一定的供应量(supply)配送到目的地,每一个目的地都有需要从一定的需求量(demand),接收从出发地发出的产品。
需求假设(TheRequirementsAssumption)
可行解特性(TheFeasibleSolutionsProperty)
成本假设(TheCostAssumption)
整数解性质(IntegerSolutionsProperty)
需求假设(TheRequirementsAssumption):
每一个出发地都有一个固定的供应量,所有的供应量都必须配送到目的地。
与之相类似,每一个目的地都有一个固定的需求量,整个需求量都必须由出发地满足,即
总供应量=总需求量
可行解特性(TheFeasibleSolutionsProperty):
当且仅当供应量的总和等于需求量的总和时,运输问题才有可行解
成本假设(TheCostAssumption):
从任何一个出发地到任何一个目的地的货物配送成本和所配送的数量成线性比例关系,因此这个成本就等于配送的单位成本乘以所配送的数量
整数解性质(IntegerSolutionsProperty):
只要它的供应量和需求量都是整数,任何有可行解的运输问题必然有所有决策变量都是整数的最优解。
因此,没有必要加上所有变量都是整数的约束条件
看一个例子:
【例2】有三台机床加工三种零件,计划第i台的生产任务为ai(i=1,2,3)个零件,第j种零件的需要量为bj(j=1,2,3),第i台机床加工第j种零件需要的时间为cij,如表3-2所示。
问如何安排生产任务使总的加工时间最少?
零件
机床
B1
B2
B3
生产任务
A1
5
2
3
50
A2
6
4
1
60
A3
7
3
4
40
需要量
70
30
50
150
【解】设xij(i=1,2,3;j=1,2,3,)为第i台机床加工第j种零件的数量,则此问题的数学模型为
运输问题的数学模型
设有m个产地(记作A1,A2,A3,…,Am),生产某种物资,其产量分别为a1,a2,…,am;有n个销地(记作B1,B2,…,Bn),其需要量分别为b1,b2,…,bn;且产销平衡,即。
从第i个产地到j个销地的单位运价为cij,在满足各地需要的前提下,求总运输费用最小的调运方案。
设xij(i=1,2,…,m;j=1,2,…,n)为第i个产地到第j个销地的运量,则数学模型为:
一个规划问题中要求部分或全部决策变量是整数,则这个规划称为整数规划。
当要求全部变量取整数值的,称为纯整数规划;只要求一部分变量取整数值的,称为混合整数规划。
如果模型是线性的,称为整数线性规划。
本章只讨论整数线性规划。
很多实际规划问题都属于整数规划问题.
例如
1.变量是人数、机器设备台数或产品件数等都要求是整数
2.对某一个项目要不要投资的决策问题,可选用个逻辑变量x当x=1表示投资,x=0表示不投资;
3.人员的合理安排问题,当变量xij=1表示安排第i人去做j工作,xij=0表示不安排第i人去做j工作。
逻辑变量也是只允许取整数值的一类变量。
【例5.2】在例5.1中,假设此人还有一只旅行箱,最大载重量为12公斤,其体积是0.02m3。
背包和旅行箱只能选择其一,建立下列几种情形的数学模型,使所装物品价值最大。
所装物品不变;
如果选择旅行箱,载重量和体积的约束为
解:
此问题可以建立两个整数规划模型,但用一个模型描述更简单
引入0-1变量(或称逻辑变量)yi,令
(1)由于所装物品不变,式(8.1)约束左边不变,整数规划数学模型为
(2) 由于不同载体所装物品不一样,数学模型为
【例5.3】企业计划生产2000件某种产品,该种产品可利用A、B、C设备中的任意一种加工。
已知每种设备的生产准备结束费用、生产该产品时的单件成本以及每种设备限定的最大加工数量(件)如下表所示,试建立总成本最小的数学模型。
设备生产准备结束费(元)生产成本(元/件)限定最大加工数(件)
A10010600
B3002800
C20051200
【解】设xj表示在第j(j=1,2,3)种设备上加工的产品数量,其生产费用为:
式中Kj是同产量无关的生产准备费用(即固定费用),cj是单位产品成本。
设0-1变量yj,令
目标函数为
式中
是一个特殊的约束条件,显然当xj>0时,yj=1,当xj=0时,为使Z极小化,只有yj=0才有意义。
用QSB软件求解得到:
X=(0,800,1200),Y=(0,1,1),Z=8100.
如果问题的所有变量取0或1,此问题称为0-1整数规划问题,简称0-1规划。
【例5.4】指派问题或分配问题。
人事部门欲安排四人到四个不同岗位工作,每个岗位一个人。
经考核四人在不同岗位的成绩(百分制)如表5-3所示,如何安排他们的工作使总成绩最好。
【解】此工作分配问题可以采用枚举法求解,即将所有分配方案求出,总分最大的方案就是最优解。
本例的方案有
4!
=4×3×2×1=24种,当人数和工作数较多时,方案数是人数的阶乘,计算量非常大。
用0-1规划模型求解此类分配问题显得非常简单。
数学模型如下:
目标函数为
要求每人做一项工作,约束条件为
每项工作只能安排一人,约束条件为
变量约束:
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 教案