Lingo 模型.docx
《Lingo 模型.docx》由会员分享,可在线阅读,更多相关《Lingo 模型.docx(52页珍藏版)》请在冰点文库上搜索。
Lingo模型
Lingo模型
Lingo是较好的最优化建模工具(详细使用说明见Lingo模型参考),Lingo模型由两部分组成:
(一)目标(objective):
最优化目标。
(二)限制条件(constraint).(下载网址:
)
1.我的食谱由四种食品组成:
果仁巧克力,冰淇淋,可乐,奶酪.一块果仁巧克力价格为50美分,一杯冰淇淋价格为20美分,一瓶可乐价格为30美分,一快奶酪价格为80美分.我每天的营养最低需求:
500卡路里,6盎司巧克力,10盎司糖,8盎司脂肪.四种食品的营养成分如下表:
卡路里
巧克力(盎司)
糖(盎司)
脂肪(盎司)
果仁巧克力(块)
400
3
2
2
巧克力冰淇淋(杯)
200
2
2
4
可乐(瓶)
150
0
4
1
奶酪(块)
500
0
4
5
试列出一份最节俭的食谱
〔讲评〕
师:
该问题的目标是什么?
生:
食谱中饮食的成本最低
师:
限制条件?
生:
满足每天卡路里,巧克力,糖,脂肪的最低需求
师:
选择哪些变量?
生:
果仁巧克力,冰淇淋,可乐,奶酪的数量
(参考模型:
lingo-LP1.lg4)
讨论:
如果巧克力冰淇淋的价格变为原来的两倍,食谱将如何改动?
练习:
1.1.你决意生产两种糖果:
硬糖和软糖,糖果仅由糖,坚果,和巧克力制成.你现在有100盎司糖,20盎司坚果,30盎司巧克力.软糖须含有至少20%的坚果.硬糖须含有至少10%的坚果和10%的巧克力.一盎司的软糖售价为25美分,一盎司的硬糖售价为20美分.试安排生产计划
(参考模型:
lingo-LP1-1.lg4)
1.2.某公司生产A,B,C三种产品,售价分别为:
A,$10;B,$56;C,$100.生产一单位A,需1小时的劳力;生产一单位B,需2小时的劳力加上2单位的A;生产一单位C,需3小时的劳力加上1单位的B.现有40小时的劳力,试安排生产计划.
(参考模型:
lingo-LP1-2.lg4)
2.Donovan公司生产一种电子产品.已知明年四季度的需求(须按时交货):
季度1,4000件;季度2,2000件;季度3,3000件;季度4,10000件;公司员工每年有一个季度休假,每个员工年薪为$30,000,每季度最多可生产500件产品.每个季度末公司须为每件存货付存储费$30.公司现有600件产品,如何安排明年的生产?
〔讲评〕
师:
该问题的目标是什么?
生:
员工年薪与存储费总和最低
师:
限制条件?
生:
每季度初的库存与该季度生产量的和须满足该季度的需求
师:
如何表示员工总数?
生甲:
各季度上班的员工x
(1),x
(2),x(3),x(4)总和
生乙:
甲的总和是员工总数的3倍,因为每个员工工作3个季度。
师:
如何表示存储费?
生:
设计每季度末的库存变量
师:
如何表示每季度的产量?
生:
设计每季度每个员工的实际产量变量
(参考模型:
lingo-LP2.lg4)
讨论:
若每个季度上班员工数目相同,员工年薪与存储费总和将如何变化?
练习:
2.1.某公司须完成如下交货任务:
季度1,30件;季度2,20件;季度3,40件;每季度正常上班时间至多可生产27件,单位成本$40,加班时间的单位生产成本为$60.产品不合格率为20%,每季度剩下的合格产品(在存货时)中有10%被破坏,单位存货费为$15.已知现有20件合格产品,如何安排3季度的的生产?
(参考模型:
lingo-LP2-1.lg4)
3.某邮局每天需一定数量的全职员工:
星期一,17;星期二,13;星期三,15;星期四,19;星期五,14;星期六,16;星期日,11.全职员工连续工作5天后休息2天.
邮局须雇用多少全职员工?
〔讲评〕
师:
问题中如何设置变量?
生甲:
该问题跟模型2有点相似,将员工分为7种,分别为星期一开始上班(休假结束),星期二开始上班,...星期日上班,对应人数分别为x
(1),x
(2),…x(7),这样星期一来上班的人数为:
x
(1)+x(4)+x(5)+x(6)+x(7).
(参考模型:
lingo-LP3
(1).lg4)
讨论:
假设邮局可要求员工加一天班,已知员工正常工作日薪为$50,加班工作日薪为$62.试定一最省钱的人事安排计划.
(参考模型:
lingo-LP3
(2).lg4)
练习:
3.1.GothamCityNationalBank每周一至周五的9:
00—17:
00营业.银行对信贷员的需求量如下表:
时间段:
9-10
10-11
11-12
12-13
13-14
14-15
15-16
16-17
信贷员需求量
4
3
4
6
5
6
8
8
银行雇用两种信贷员:
全职信贷员(工作时间:
9:
00—17:
00,除去11:
00-12:
00或12:
00—13:
00的中餐时间),时薪为$8(含中餐时间);兼职信贷员,工作时间为连续3小时,时薪为$5.试定一最省钱的信贷员雇用计划.每天兼职信贷员总数不超过5个.
(参考模型:
lingo-LP3-1.lg4)
4.AlexisCornby靠买卖谷子为生.年初,他有50吨谷子和$10000,每月初他可以以下价格买进谷子:
一月,$300;二月,$350;三月,$400;四月,$500;每月末他可以以下价格卖出谷子:
一月,$350;二月,$450;三月,$350;四月,$550;Alexis的谷子存放于它的仓库内(仓库容量为100吨).他买谷子时须付现金.试设计买卖计划.
讨论:
若买谷子的钱可延期一个月付款,买卖计划将发生何种变化?
(参考模型:
lingo-LP4.lg4)
5.有一块长为120厘米,宽为90厘米的矩形薄铁皮材料,现要剪一个长方体的展开图,做一个长方体模型.求长方体体积的最大值.
〔讲评〕
师:
设a,b,c分别是长方体的长,宽,高,a,b,c须满足什么条件?
生甲:
2a+b<120及2a+2c<90
生乙:
也可以是2a+b<90及2a+2c<120。
师:
试试看哪种情况体积大?
讨论:
在体积最大的前提下,哪种情况铁皮利用率大?
(参考模型:
lingo-LP5.lg4)
练习
5.1.如图,P,Q到河岸的距离分别为10,8,试选一点R,使得R到河岸的距离及RP,RQ的和最小.
P
Q
R
6
(参考模型:
lingo-LP5-1.lg4)
6.某工厂在计划内拟生产I,II两种产品,已知生产单位产品所需的设备台时及A,B两种原材料的消耗如下表:
I
II
总量
设备(台时)
3
4
36
原材料A(kg)
0
2
12
原材料B(kg)
1
0
8
该工厂生产一件产品I可获利3百元,生产一件产品II可获利5百元,
(1)应如何安排生产?
(2)若该工厂决定不生产,而将上述资源出租,问总租金应为多少?
〔讲评〕
师:
问题
(2)是相对于问题
(1)的影子价格问题,运行lingo-LP6.lg4后,在solutionreport中的dualcost栏中显示。
我们不妨假设,原材料A的单价为a百元/公斤,原材料B的单价为b百元/公斤,设备费为c百元/台时。
因为3台时设备和1公斤原料B可生产一件产品I,等价于可获利3百元,所以,3*c+b>3,同理,4*c+2*a>5.但是作为承租方希望总租金最少:
min=36*c+12*a+8*b.
讨论:
若增加1公斤原材料A,总获利增加多少?
若市场上有x公斤的原材料出售,你愿以何种价格收购?
(参考模型:
lingo-LP6.lg4)
7.DocCouncilman正组建一支400米混合泳(自由泳,仰泳,蝶泳,蛙泳)接力队,有四位泳将,GARYHALL,MARKSPITZ,JIMMONTGOMERY,CHETJASTREMSKI,他们四项游泳项目成绩如下表,DocCouncilman应如何安排四位泳将的接力项目?
单位:
秒
自由泳
蛙泳
蝶泳
仰泳
GARYHALL
54
54
51
53
MARKSPITZ
51
57
52
52
JIMMONTGOMERY
50
53
54
56
CHETJASTREMSKI
56
54
55
53
〔讲评〕
师:
问题的目标是什么?
生甲:
接力赛成绩最好
师:
限制条件是什么?
生乙:
每人只能参加一项,每项都须有人参加。
师:
如何表示这种限制条件?
生甲:
设置一个4×4的选择矩阵(每个元素只能是1或0),矩阵每行每列的和均为1
师:
如何表示接力赛成绩?
生乙:
甲设的矩阵与成绩矩阵点乘(对应元素相乘)后对所有元素求和
(参考模型:
lingo-LP7.lg4)
8.四项工作指派给五个员工(每项工作只能由一人单独完成),每人完成各项工作耗时如下表,如何指派使得完成四项工作总耗时最少?
工作1
工作2
工作3
工作4
员工1
22
18
30
18
员工2
18
-
27
22
员工3
26
20
28
28
员工4
16
22
-
14
员工5
21
-
25
28
(注:
横线表该员工不宜完成该项工作)
〔讲评〕
师:
碰到横线怎么办?
生:
设成很大的数
师:
5个人4项工作如何表示?
生:
每列的和为1(工作须有人做),每行的和小于或等于1(有机会不做)
(参考模型:
lingo-LP8.lg4)
9.已知森林具有6年的生长期,我们把森林中的树木按照高度分为6类,第一类树木的高度为[0,h1],它是树木的幼苗,其经济价值为p1=0,第k类树木的高度为[h(k-1),h(k)],每一棵经济价值为p(k),第六类树木的高度为[h5,∞],经济价值为p6.设每年对森林砍伐一次,且为了维持每年都有稳定的收获,只能砍伐部分树木,留下的树木和补种的幼苗,经过一年的生长期后,应该与上一次砍伐前的高度状态一致.再假设在一年的生长期内树木最多只能生长一个高度级,即第k类的树木可能进入k+1类(比例为g(k)),也可能停留在k类中.设g1=0.28,g2=0.32,g3=0.25,g4=0.23,g5=0.37,p2=50元,p3=100元,p4=150元,p5=200元,p6=250元.求出对其进行最优采伐的策略.
〔讲评〕
师:
如何描述砍伐前后森林高度状态的变化?
生:
设森林的总面积为1,6类高度树木分别为x
(1),x
(2),x(3),x(4),x(5),x(6),被砍掉的面积分别为y
(1),y
(2),y(3),y(4),y(5),y(6).x
(1)先变为x
(1)-y
(1),由于补种树苗的原因,x
(1)变为x
(1)-y
(1)+(y
(1)+y
(2)+y(3)+y(4)+y(5)+y(6)),最后由于树木生长原因,
x
(1)变为(1-g1)×(x
(1)-y
(1)+(y
(1)+y
(2)+y(3)+y(4)+y(5)+y(6))).x
(2)先变为x
(2)-y
(2),后由于树木生长原因x
(2)变为(1-g2)×(x
(2)-y
(2))+g1×(x
(1)-y
(1)+(y
(1)+y
(2)+y(3)+y(4)+y(5)+y(6)))。
同理,x(3)=(1-g3)×(x(3)-y(3))+g2*(x
(2)-y
(2)),…x(6)=(x(6)-y(6))+g5*(x(5)-y(5))
讨论:
修改p2,p3,p4,p5,p6,g1,g2,g3,g4,g5的值,看看砍伐策略的变化情况.
(参考模型:
lingo-LP9.lg4)
10.Chicago教育委员会为该城市的四条学生公交线路招标.四家公司做出如下竟标:
线路1
线路2
线路3
线路4
公司1
4000
5000
-
-
公司2
-
4000
-
4000
公司3
3000
-
2000
-
公司4
-
-
4000
5000
(a)假设每位竟标者至多可分配到一条线路,问委员会将如何招标?
(参考模型:
lingo-LP10a.lg4)
(b)假设每位竟标者至多可分配到两条线路,问委员会将如何招标?
(参考模型:
lingo-LP10b.lg4)
11.福特在L.A.和Detroit生产汽车,在Atlanta有一仓库,供应点为Houston和Tampa;城市间每辆汽车运输费用见下表.L.A.的生产能力为1100辆,Detroit的生产能力为2900辆.Houston汽车需求量为2400辆,Tampa汽车需求量为1500辆,
L.A
DETROIT
ATLANTA
HOUSTON
TAMPA
L.A.
0
140
100
90
225
DETROIT
145
0
111
110
119
ATLANTA
105
115
0
113
78
HOUSTON
89
109
121
0
-
TAMPA
210
117
82
-
0
如何确定运输和生产方案,才能满足Houston和Tempa的需求且费用最低.
〔讲评〕
师:
这个问题是否很简单?
生甲:
这是一个从L.A.和Detroit到Houston和Tampa城市间的汽车运输问题,仓库Atlanta完全多余
生乙:
仓库Atlanta可降低运费,例如,从L.A.经过Atlanta到达Tampa比从L.A.直接到达Tampa便宜
师:
这是运输问题中的转运问题,任何一个地点都可以输入也可以输出。
生产点(L.A.和Detroit),仓库(Atlanta),需求点(Houston和Tampa)的输入和输出须满足什么条件?
生:
生产点,输入减输出等于产量;仓库,输入等于输出;需求点,输出减输入等于需求量。
(参考模型:
lingo-LP11.lg4)
12.设有三个化肥厂供应四个地区的农用化肥.假定等量的化肥在这些地区使用效果相同.各化肥厂年产量,各地区年需要量及从各化肥厂到各地区运送单位化肥的运价(万元/万吨)如下表所示.试求出总的运费最省的化肥调拨方案.
需求地区
化肥厂
I
II
III
IV
产量(万吨)
A
16
13
22
17
50
B
14
13
19
15
60
C
19
20
23
禁止
50
最低需求(万吨)
30
70
0
10
最高需求(万吨)
50
70
30
不限
〔讲评〕
师:
地区IV最高需求为不限,是不是无限大的意思?
生甲:
是的
生乙:
不是,地区IV最多可得到(50+50+60)(总产量)-(70+30)(其它地区最小需求)=60
(参考模型:
lingo-LP12.lg4)
13.某航运公司承担6个港口城市A,B,C,D,E,F的四条固定航线的物资运输任务.已知各条航线的起点,终点城市及每天航班数见下表:
航线
起点城市
终点城市
每天航班数
1
E
D
3
2
B
C
2
3
A
F
1
4
D
B
1
假定各条航线使用相同型号的船只,由各城市间的航程天数见下表:
到
从
A
B
C
D
E
F
A
0
1
2
14
7
7
B
1
0
3
13
8
8
C
2
3
0
15
5
5
D
14
13
15
0
17
20
E
7
8
5
17
0
3
F
7
8
5
20
3
0
又知每条船只每次装卸货物的时间各需1天,则该航运公司至少应配备多少条船,才能满足所有航线的运货要求.
〔讲评〕
师:
若城市x(起点),y(终点)间航程为4天,每条船只每次装卸货物的时间各需1天,空船从空船从y到x只需2天,每天航班数为5,应配备多少条船?
生甲:
5条
生乙:
若一天发出5条船,第二天便没船可发,应备5×(4+2)=30条
生丙:
6天过后,离开x的船还没回来,应备5×(4+2+2)=40条
师:
该题中4条航线需多少船?
生甲:
3×(17+2)+2×(3+2)+(7+2)+(13+2)=91
生乙:
91条不够,城市E处的船只够19天(51条),E,每天需3条空船。
同理,A和B每天均需1条船;而C,D,F处每天分别多出2,2,1条船。
生丙:
这这正好是一个C,D,F到E,A,B的运输问题。
(参考模型:
lingo-LP13.lg4)
14.Indianapolis航空公司计划每天从Indianapolis飞6个航班,计划目的地为:
NewYork,LosAngeles,或Miami.下表列出各航线的日收益与航班次数的关系.
航班次数
1
2
3
4
5
6
NEWYORK
$80
$150
$210
$250
$270
$280
LOSANGELES
$100
$195
$275
$325
$300
$250
MIAMI
$90
$180
$265
$310
$350
$320
试帮该公司确定航线和相应的航班次数.
[讲评]
师:
如果,NEWYORK飞3个航班,LOSANGELES飞2个航班,MIAMI只能飞1个航班了,如何用数据表示这种安排(有利于收益的计算,及限制条件的表示)
生:
上述安排对应于下表:
航班次数
1
2
3
4
5
6
NEWYORK
0
0
1
0
0
0
LOSANGELES
0
1
0
0
0
0
MIAMI
1
0
0
0
0
0
1表示选择,0表示不选.
正好可以设计一个选择矩阵(3行6列)
(参考模型:
lingo-LP14.lg4)
15.某种机器可在高低两种不同的负荷下进行生产,设机器在高负荷下生产的年产量函数为:
y=8x,(x:
投入生产的机器台数),年完好率为0.7;机器在低负荷下生产的年产量函数为:
y=5x,(x:
投入生产的机器台数),年完好率为0.9;假定开始生产时完好的机器数量为1000台,试问每年如何安排机器在高,低负荷下的生产,使在五年内生产的产品总产量最高.
讨论:
如果5年末完好机器数必为500台,又将如何?
(参考模型:
lingo-LP15.lg4)
16.某工厂要对一种产品制定今后四个时期的生产计划,据估计在今后四个时期内,市场对于
该产品的需求量如表所示,假定该厂生产每批产品的固定成本为3(千元),若不生产为0;
每单位产品成本为1(千元);每个时期生产能力所允许的最大生产批量为不超过6个单位;
每个时期末未售出的产品,每单位需存储费0.5(千元).还假定在第一个时期的初始储存
量为0,第四个时期之末的库存量也为0.试问如何安排各个时期的生产与库存,才能在满足
市场需要的条件下,使总成本最小.
时期
1
2
3
4
需求(单位)
2
3
2
4
[讲评]
师:
如何处理生产固定成本?
生:
设计一个生产判断变量数组x,若生产则x(i)为1,不生产则x(i)为0
师:
如何表示每个时期的产量?
生:
设计一个产量数组y,x(i)*y(i)则为第i时期的产量。
(参考模型:
lingo-LP16.lg4)
17.下图为一网络,节点1到节点2的宽带带宽为6兆,节点1到节点3的宽带带宽为2兆,节点2到节点4的宽带带宽为3兆,…节点4到节点6的宽带带宽为2兆,求节点1到节点6的最大网速。
3
2
6
3
7
1
7
2
[讲评]
师:
节点1到节点6的最大网速受什么限制?
生甲:
受节点1输出宽带带宽的限制。
生乙:
还受中间节点2,3,4,5输入和输出宽带带宽的限制。
生丙:
中间节点的输入等于输出。
师:
如何表示节点1到节点6的最大网速?
生:
节点1的输出或节点6的输入。
讨论:
若想提高节点1到节点6的最大网速x兆,如何实现?
(参考模型:
lingo-LP17.lg4)
18.在网络传输过程中有时得考虑费用问题,下表中的单位成本是指流经该宽带单位流量的费用,考虑从节点1到节点5的最小费用最大流。
宽带
(1,2)
(1,3)
(2,4)
(2,5)
(3,2)
(3,4)
(4,5)
带宽
10
8
2
7
5
10
4
单位成本
4
1
6
1
2
3
2
(参考模型:
lingo-LP18.lg4)
19.某项研制新产品的各个工序,工序所需时间及相应费用,工序极限时间及相应费用,以及工序之间的相互关系如表:
工序代号
正常情况
采取措施后
缩短一天工期代价
紧后工序
正常时间(天)
直接费用
极限时间(天)
直接费用
a
60
10000
60
10000
--
b,c,d,e
b
45
4500
30
6300
120
l
c
10
2800
5
4300
300
f
d
20
7000
10
11000
400
g,h
e
40
10000
35
12500
500
h
f
18
3600
10
5440
230
l
g
30
9000
20
12500
350
k
h
15
3750
10
5750
400
l
k
25
6250
15
9150
290
l
l
35
12000
35
12000
--
l
研制过程中每天间接费用为400元.
(1)试作出流程图,并求出正常情况最早完工时间
〔讲评〕
x
师:
我们通常用
来表示工序x.
0
f
h
l
k
g
c
b
e
d
a
工序(3,6)是虚拟工序,仅用来表示h须在d结束后才能开始。
我们通常在各节点处摆放一个记时器,定t
(1)=0,t
(2)为以节点2为起点的工序中最早开始动工的时刻,t(3)为以节点3为起点的工序中最早开始动工的时刻,…t(8)为完工时间。
请问,t(5),t(7)间需满足什么关系?
生:
t(5)-t(7)大于工序f所需时间。
师:
正常情况最早完工时间怎么表示?
生:
就是t(8)的最小值
(参考模型:
lingo-LP19
(1).lg4)
(2)求最短工期下的最低费用.(参考模型:
lingo-LP19
(2).lg4)
(3)求最低费用下的最短工期.(参考模型:
lingo-LP19(3).lg4)
20.如下图所示,节点间的线段表示某小区的弄堂,线段旁的数字表示弄堂的长度。
邮局在其中某个节点,请设计邮递员投递路线。
2
4
6
4
3
4
9
5
5
〔讲评〕
师:
问题的目标是什么?
生:
邮递员投递线路最短。
师:
邮递员投递线路的长度是否等于所有弄堂的长度和?
生:
不是,每条弄堂仅过一遍