规划建模培训2Word格式.docx
《规划建模培训2Word格式.docx》由会员分享,可在线阅读,更多相关《规划建模培训2Word格式.docx(17页珍藏版)》请在冰点文库上搜索。
![规划建模培训2Word格式.docx](https://file1.bingdoc.com/fileroot1/2023-5/1/21aa8557-1c54-4a38-b08a-97848279afbf/21aa8557-1c54-4a38-b08a-97848279afbf1.gif)
假定进货时得到的原料钢管长度都是19m。
1)现有一客户需要50根长4m、20根长6m和15根长8m的钢管。
应如何下料最节省?
2)零售商如果采用的不同切割模式太多,将会导致生产过程的复杂化,从而增加生产和管理成本。
所以该零售商规定采用的不同切割模式不能超过3种。
此外。
该客户除需要1)中的3种钢管外,还要10根长5m的钢管。
问题分析:
对于下料问题首先要确定采用哪些切割模式。
所谓切割模式,是指按照顾客要求的长度在原料钢管上安排切割的一种组合。
例如,我们可以将19m的钢管切割成3根长4m的钢管,余料为7m;
或者将长19m的钢管切割成长4m、6m和8m的钢管各1根,余料为1m。
显然,可行的切割模式是很多的。
其次,应当明确哪些切割模式是合理的。
合理的切割模式通常还假设余料不应大于或等于客户需要钢管的最小尺寸。
例如,可以将长19m的钢管切割成3根4m的钢管是可行的,但余料为7m,可进一步将7m的余料切割成4m钢管(余料为3m),或者将7m的余料切割成6m钢管(余料为1m)。
经过简单的计算可知,问题1)的合理切割模式一共有7种,如表1所示:
于是问题转化为在满足客户需要的条件下,按照哪几种合理的模式,每种模式切割多少根原料钢管最为节省。
而所谓节省,可以有两种标准,一是切割后剩余的总余料量最小,二是切割原料钢管的总根数最少。
下面将对这两个目标分别讨论。
问题1)用xi表示按照表1第i种模式(i=1,2,…,7)切割的原料钢管的根数,若以切割后剩余的总余料量最小为目标,则按照表1最后一列可得
minZ1=3x1+x2+3x3+3x4+x5+x6+3x7
若以切割原料钢管的总根数最少为目标,则有
表1钢管下料问题1)的合理切割模式
模式
4m钢管根数
6m钢管根数
8m钢管根数
余料/m
1
4
3
2
5
6
7
MinZ2=x1+x2+x3+x4+x5+x6+x7
约束条件为客户的需求,按照表1应有
4x1+3x2+2x3+x4+x5≥50
x2+2x4+x5+3x6≥20
x3+x5+2x7≥15
最后,切割的原料钢管的根数xi显然应当是非负整数(用Z表示整数集合,Z+表示非负整数集合):
xi∈Z+,i=1,2,…,7
于是,问题1)归结为在约束条件下,使目标达到最小。
显然这是线性整数规划模型。
钢管下料问题1)的求解
以切割后剩余的总余料量最小为目标,建立LINGO模型:
min=3*x1+x2+3*x3+3*x4+x5+x6+3*x7;
4*x1+3*x2+2*x3+x4+x5>
=50;
x2+2*x4+x5+3*x6>
=20;
x3+x5+2*x7>
=15;
@gin(x1);
@gin(x2);
@gin(x3);
求解可以得到最优解如下:
OBJECTIVEFUNCTIONVALUE
1)27.00000
VARIABLEVALUEREDUCEDCOST
X10.0000003.000000
X212.0000001.000000
X30.0000003.000000
X40.0000003.000000
X515.0000001.000000
X60.0000001.000000
X70.0000003.000000
即按照模式2切割12根原料钢管,按照模式5切割15根原料钢管,共27根,总余料量27m。
显然,在总余料量最小的目标下,最优解将是使用余料尽可能小的切割模式(模式2和模式5的余料为1m),这会导致切割原料钢管的总根数较多。
以切割原料钢管的总根数最少为目标,建立LINGO模型:
min=x1+x2+x3+x4+x5+x6+x7;
@gin(x4);
@gin(x5);
@gin(x6);
@gin(x7);
1)25.00000
X10.0000001.000000
X215.0000001.000000
X30.0000001.000000
X40.0000001.000000
X55.0000001.000000
X75.0000001.000000
即按照模式2切割15根原料钢管,按照模式5切割5根原料钢管,按照模式7切割5根原料钢管,共25根,总余料量35m。
与上面得到的结果相比,总余料量增加了8m,但是所用的原料钢管的总根数减少了2根,在余料没有什么用途的情况下,通常选择总根数最少为目标。
问题2)如果按照问题1)的办法处理,首先要通过枚举法确定哪些切割模式是合理的,并从中选出不超过3种模式。
而由于需求的钢管规格增加到4种,所以枚举法的工作量较大。
下面介绍一种带有普遍性的方法,可以同时确定切割模式和切割数量。
同问题1)一样,只使用合理的切割模式,其余料不应大于3m(因为客户需要的钢管最小尺寸为4m,而本题中参数都是整数)。
由于不同切割模式不能超过3种,可以用用xi表示按照第i种模式(i=1,2,3)切割的原料钢管的根数。
又设使用第i种切割模式下每根原料钢管生产长4m、5m、6m和8m的钢管数量分别为r1i,r2i,r3i,r4i。
仅以使用的原料总根数最少为目标,即
minx1+x2+x3
满足客户需求的约束条件为
r11x1+r12x2+r13x3≥50
r21x1+r22x2+r23x3≥10
r31x1+r32x2+r33x3≥20
r41x1+r42x2+r43x3≥15
每一种切割模式必须可行、合理,所以每根原料钢管的成品量不能超过19m,也不能少于16m(余料不能大于3m),于是
16≤4r11+5r21+6r31+8r41≤19
16≤4r12+5r22+6r32+8r42≤19
16≤4r13+5r23+6r33+8r43≤19
最后,加上非负整数约束:
xi,rji∈Z+,i=1,2,3,j=1,2,3,4
于是,问题2)归结为在在约束条件下,求xi和r1i,r2i,r3i,r4i(i=1,2,3)使目标达到最小。
当然,这是一个整数非线性规划模型。
钢管下料问题2)模型的进一步优化:
非线性整数规划模型虽然用LINGO软件可以直接求解,但为了减少运行时间,可以增加一些显然的约束条件,从而缩小可行解的搜索范围。
例如,由于3种切割模式的排列顺序是无关要紧的,所以不妨增加以下约束:
x1≥x2≥x3
又如,注意到所需原料钢管的总根数有明显的上界和下界。
首先,原料钢管的根数不可能少于
(根)。
其次,考虑一种非常特殊的生产计划:
第一种切割模式下只生产4m钢管,一根原料钢管切割成4根4m钢管,为满足50根4m钢管的需求,需要13根原料钢管;
第二种切割模式下只生产5m,6m钢管,一根原料钢管切割成1根5m钢管和2根6m钢管,为满足10根5m和20根6m钢管的需求,需要10根原料钢管;
第三种切割模式下只生产8m钢管,一根原料钢管切割成2根8m钢管,为满足15根8m钢管的需求,需要8根原料钢管。
于是满足要求的这种生产计划共需要13+10+8=31根原料钢管,这就得到了最优解的一个上界,所以可增加以下约束:
26≤x1+x2+x3≤31
LINGO模型为:
min=x1+x2+x3;
r11*x1+r12*x2+r13*x3>
r21*x1+r22*x2+r23*x3>
=10;
r31*x1+r32*x2+r33*x3>
=20;
r41*x1+r42*x2+r43*x3>
=15;
4*r11+5*r21+6*r31+8*r41<
=19;
4*r12+5*r22+6*r32+8*r42<
4*r13+5*r23+6*r33+8*r43<
4*r11+5*r21+6*r31+8*r41>
=16;
4*r12+5*r22+6*r32+8*r42>
4*r13+5*r23+6*r33+8*r43>
x1+x2+x3>
=26;
x1+x2+x3<
=31;
x1>
=x2;
x2>
=x3;
@gin(r11);
@gin(r12);
@gin(r13);
@gin(r21);
@gin(r22);
@gin(r23);
@gin(r31);
@gin(r32);
@gin(r33);
@gin(r41);
@gin(r42);
@gin(r43);
得到输出如下:
Localoptimalsolutionfoundatiteration:
12211
Objectivevalue:
28.00000
VariableValueReducedCost
X110.000000.000000
X210.000002.000000
X38.0000001.000000
r113.0000000.000000
r122.0000000.000000
r130.0000000.000000
r210.0000000.000000
r221.0000000.000000
r230.0000000.000000
r311.0000000.000000
r321.0000000.000000
r330.0000000.000000
r410.0000000.000000
r420.0000000.000000
r432.0000000.000000
即按照模式1,2,3分别切割10根,10根,8根原料钢管,使用原料钢管总根数为28根。
第一种切割模式下一根原料钢管切割成3根4m钢管和1根6m钢管;
第二种切割模式下一根原料钢管切割成2根4m钢管,1根5m钢管和1根6m钢管;
第三种切割模式下一根原料钢管切割成2根8m钢管。
例3、飞行计划问题
这个问题是以第二次世界大战中的一个实际问题为背景,经过简化而提出来的。
在甲、乙双方的一场战争中,一部分甲方部队被乙方部队包围长达4个月。
由于乙方封锁了所有水陆交通通道,被包围的甲方部队只能依靠空中交通维持供给。
运送4个月的供给分别需要2,3,3,4次飞行,每次飞行编队由50架飞机组成(每架飞机需要3名飞行员),可以运送10万t物质。
每架飞机每个月只能飞行一次,每名飞行员每个月也只能飞行一次。
在执行完运输任务后的返回途中有20%的飞机会被乙方部队击落,相应的飞行员也因此牺牲或失踪。
在第1个月开始时,甲方拥有110架飞机和330名熟练的飞行员。
在每个月开始时,甲方可以招聘新飞行员和购买新飞机。
新飞机必须经过一个月的检查后才可以投入使用,新飞行员必须在熟练飞行员的指导下经过一个月的训练才能投入飞行。
每名熟练飞行员可以作为教练每个月指导20名飞行员(包括他自己在内)进行训练。
每名飞行员在完成一个月的飞行任务后,必须有一个月的带薪假期,假期结束后才能再投入飞行。
已知各项费用(单位略去)如下表所示,请为甲方安排一个飞行计划。
第1个月
第2个月
第3个月
第4个月
新飞机价格
200.0
195.0
190.0
185.0
闲置的熟练飞行员报酬
7.0
6.9
6.8
6.7
教练和新飞行员报酬(包括培训费用)
10.0
9.9
9.8
9.7
执行飞行任务的熟练飞行员报酬
9.0
8.9
休假期间的熟练飞行员报酬
5.0
4.9
4.8
4.7
飞行计划的原始数据
如果每名熟练飞行员可以作为教练每个月指导不超过20名飞行员(包括他自己在内)进行训练,模型和结果有那些改变?
习题4-2
1.用机床A1、A2、A3加工零件B1和B2,零件数相等。
日产量(个/日)如下表,如何生产使总产量最多?
max=x11+x12+x21+x22+x31+x32;
x11<
=30;
x12<
x21<
x22<
=40;
x31<
=18;
x32<
x11+x21+x31=x12+x22+x32;
@gin(x11);
@gin(x12);
@gin(x21);
@gin(x22);
@gin(x31);
@gin(x32);
Globaloptimalsolutionfound.
126.0000
Extendedsolversteps:
0
Totalsolveriterations:
VariableValueReducedCost
X1130.00000-1.000000
X1220.00000-1.000000
X2115.00000-1.000000
X220.000000-1.000000
X3118.00000-1.000000
X3243.00000-1.000000
RowSlackorSurplusDualPrice
1126.00001.000000
20.0000000.000000
30.0000000.000000
40.0000000.000000
540.000000.000000
60.0000000.000000
77.0000000.000000
80.0000000.000000
2.一家24小时自助餐厅在24小时内需要的服务员人数如下表:
起止时间
2-6
6-10
10-14
14-18
18-22
22-2
最少人数
8
10
12
每个服务员每天连续工作8小时。
问:
(1)该餐厅最少需要招聘几个服务员?
(2)劳动法规定,每个工作人员每星期至少休息1天。
加上此限制,最少应该招聘几个服务员?
3.某军用与民用计算机硬件制造商目前正在生产民用器件E-1200、E-1500,每个纯利分别为$50、$40。
加工时间与日加工能力如下表:
车间
E-1200
E-1500
车间能力(每天小时数)
300
540
440
1.2
1.5
假设所有产品都能卖掉,制定最佳生产方案;
假设E-1200的纯利减少$10,制定最佳生产方案;
假设此公司获准生产军用产品Z-1800,其在四个车间的加工时间分别为0.1小时、3.6小时、2.2小时、1.2小时,每个纯利为$55,民用产品的纯利同
(1),制定最佳生产方案。
4.(总运力问题)某卡车公司拨款800万元用于购买新的运输工具,有3种运输工具可供选择:
A的载重量10吨,平均时速45千米,价格26万元;
B的载重量20吨,平均时速40千米,价格36万元;
C的载重量18吨,平均时速40千米,价格42万元。
其中,C是B的变种,新设了一个卧铺,所以载重降低了、价格上升了。
A需要1名司机,如果每天三班工作,每天可运行18小时.当地法律规定B和C均需要两名司机,如果三班工作,B每天可运行18小时,C可运行21小时.该公司目前每天有150名司机可用,短期内无法招募到其他训练有素的司机。
当地工会禁止司机每天工作超过一个班次。
此外,受维修保障能力的限制,公司最多能拥有30辆运输工具。
请你建立数学模型,确定A、B、C的数量使得公司的总运力最大。
5.(机票的销售策略)在四个城市A、B、C、H之间,有唯一一家航空公司提供三个航班,这三个航班的“出发地—目的地”分别为AH、HB、HC,可搭载旅客的最大数量分别为120人、100人、110人,机票的价格分头等舱和经济舱两类。
经过市场调查,公司销售部得到了每天旅客的相关信息,见下表。
该公司应该在每条航线上分别分配多少张头等舱和经济舱的机票?
出发地—目的地
头等舱需求/人
头等舱价格/人
经济舱需求/人
经济舱价格/人
AH
33
190
56
90
AB(经H转机)
24
244
43
193
AC(经H转机)
261
67
199
HB
44
140
69
80
HC
16
186
17
103
1、一汽车厂生产小.中.大三种类型的汽车,已知各类型每辆车对钢材.劳动时间的需求,利润以及每月工厂钢材.劳动时间的现有量如表2-3所示。
由于各种条件限制,如果生产某一类型汽车,则至少要生产80辆,试制定月生产计划,使工厂的利润最大。
5.两个汽车公司春运期间为三条线路增派汽车,甲公司可提供12辆,乙公司可提供20辆;
A线路需9辆,B线路需15辆,C线路需8辆。
已知甲公司运营A、B、C三线的距离依次为10公里、5公里、6公里;
乙公司运营A、B、C三线的距离依次为4公里、8公里、15公里。
若每辆每公里的运营费为常数a元,则甲公司供应给A、B、C三线各多少辆,使总运营费用最省?
6.某机车厂在A、B两处分厂分别有库存机车16台、12台,现要运往甲、乙两地,其中甲地15台,乙地13台。
已知从A地运一台机车到甲地的运费为5000元,到乙地的运费为4000元;
从B地运一台机车到甲地的运费为3000元,到乙地的运费为6000元。
问应设计怎样的调运方案,才能使这些机车的总运费最省?
此时总运费是多少?
7.A市、B市和C市分别有某种机器10台、10台和8台。
现在决定把这些机器支援给D市18台、E市10台。
已知从A市调运一台机器到D市、E市的运费分别为200元和800元;
从B市调运一台机器到D市、E市的运费分别为300元和700元;
从C市调运一台机器到D市、E市的运费分别为400元和500元。
⑴设从A市、B市各调x台机器到D市,当28台机器全部调运完毕后,求总运费W(元)关于x(台)的函数式,并求W的最小值和最大值;
⑵设从A市调x台到D市,B市调y台到D市,当28台机器全部调运完毕后,用x、y表示总运费W(元),并求W的最小值和最大值。
8.某运输公司有7辆载重量为6吨的A型卡车与4辆载重量为10吨的B型卡车,有9名驾驶员,在建筑某段高速公路中,此公司承包了每天至少搬运360吨沥青的任务,已知每辆卡车每天往返的次数为A型车8次,B型车6次,每辆卡车每天往返的成本费为A型车160元,B型车252元,每天派出A型车与B型车各多少辆,公司所花的成本费最低?
最低成本费是多少?
9.某厂生产甲、乙、丙三种产品,都分别经A、B两道工序。
设A工序可以分别在A1或A2上完成,B工序可以分别在B1、B2、B3上完成。
已知甲产品可在A、B任一设备上加工;
乙产品可在任一A设备上加工,但完成B工序时,只能在B1上加工;
丙产品只能在A2和B2上加工。
具体工序时间及其他数据如表所示,问如何安排生产计划,使得该厂获利最大。
设备
甲产品
乙产品
丙产品
设备有效台时
设备加工费(元/h)
A1
6000
0.05
A2
9
10000
0.03
B1
4000
0.06
B2
11
7000
0.11
B3
原料费(元/件)
0.25
0.35
0.50
售价
(元/件)
1.25
2.00
2.80