用LINGO解线性规划和整数规划.docx
- 文档编号:11163042
- 上传时间:2023-05-29
- 格式:DOCX
- 页数:22
- 大小:78.38KB
用LINGO解线性规划和整数规划.docx
《用LINGO解线性规划和整数规划.docx》由会员分享,可在线阅读,更多相关《用LINGO解线性规划和整数规划.docx(22页珍藏版)》请在冰点文库上搜索。
用LINGO解线性规划和整数规划
用LINGO解线性规划和整数规划
在工程技术、经济管理、科学研究和日常生活等许多领域中,人们经常遇到的一类决策问题是:
在一系列客观或主观限制条件下,寻求使关注的某个或多个指标达到最大(或最小)的决策。
例如:
★结构设计要在满足强度要求条件下选择材料的尺寸,使其总重量最轻;
★资源分配要在有限资源约束下制定各用户的分配数量,使资源产生的总效益最大;
★运输方案要在满足物资需求和装载条件下安排从各供应点到各需求点的运量和路线,使运输总费用最低;
★生产计划要按照产品工艺流程和顾客需求,制定原料、零件、部件等订购、投产的日程和数量,尽量降低成本使利润最高。
上述这种决策问题通常称为优化问题。
人们解决这些优化问题的手段大致有以下几种:
1.依赖过去的经验判断面临的问题。
这似乎切实可行,并且没有太大的风险,但是其处理过程会融入决策者太多的主观因素,难以客观地加以描述,从而无法确认结果的最优性。
2.做大量的试验反复比较。
这固然比较真实可靠,但是常要花费太多的资金和人力,而且得到的最优结果基本上离不开开始设计的试验范围。
3.用数学建模的方法建立数学规划模型求解最优决策。
虽然由于建模时要作适当的简化,可能使得结果不一定完全可行或达到实际上的最优,但是它基于客观规律和数据,又不需要多大的费用,具有前两种手段无可比拟的优点。
如果在此基础上再辅之以适当的经验和试验,就可以期望得到实际问题的一个比较圆满的回答,是解决这种问题最有效、最常用的方法之一。
1.
1.1数学规划模型
数学规划模型一般有三个要素:
一是决策变量,通常是该问题要求解的那些未知量,不妨用n维向量
表示;二是目标函数,通常是该问题要优化(最小或最大)的那个目标的数学表达式,它是决策变量x的函数,这里抽象地记作f(x);三是约束条件,由该问题对决策变量的限制条件给出,即x允许取值的范围
称可行域,常用一组关于x的不等式(也可是等式)gi(x)≤0(I=1,2,…,m)来界定。
一般地,这类模型可表示成如下形式:
optz=f(x)
(1)
s.t.gi(x)≤0
(2)
这里opt(optimize)是最优化的意思,可以是求极小min(minimize)或求极大max(maximize);s.t.(subjectto)是“受约束于”的意思,满足
(2)式的解x称为可行解,同时满足
(1)式,
(2)式的解x*称为最优解。
模型
(1),
(2)中:
若决策变量x的所有分量xi(i=1,…n)均为实数,且f、gi(i=1,…m)都是线性函数时,称为线性规划;
若f、gi至少有一个非线性函数,则称为非线性规划;
若x至少有一个分量只取整数,则称为整数规划。
线性规划和非线性规划是连续规划,而整数规划是离散优化(组合优化),它们统称为数学规划。
我们简介用LINGO解线性规划和整数规划问题。
LINGO(LinearInteractiveandGeneraiOptimizer)是由美国芝加哥大学的LinusSchrage于1986年开发的优化计算软件包,LINGO可以用来求解线性规划、线性整数规划、二次规划和整数二次规划、非线性规划等问题。
LINDO公司的主页为:
。
1.2用LINGO求解线性规划问题
例1加工奶制品的生产计划。
(I)问题及建模:
一奶制品加工厂用牛奶生产A1、A2两种奶制品,1桶牛奶可以在设备甲上用12小时加工成3公斤A1,或者在设备乙上用8小时加工成4公斤A2。
根据市场需求,生产的A1、A2能全部售出,且每公斤A1获利24元,每公斤A2获利16元。
现在加工厂每天能得到50桶牛奶的供应,每天正式工人总的劳动时间为480小时,并且设备甲每天至多能加工100公斤A1,设备乙的加工能力没有限制。
试为该厂制定一个生产计划,使每天获利最大,并进一步讨论以下3个附加问题:
1)若用35元可以购买到1桶牛奶,应否作这项投资?
若投资,每天最多购买多少桶牛奶?
2)若可以聘用临时工人以增加劳动时间,付给临时工人的工资最多是每小时几元?
3)由于市场需求变化,每公斤A1的获利增加到30元,应否改变生产计划?
数学模型设每天用x1桶牛奶生产A1,用x2桶牛奶生产A2
解:
目标函数:
设每天获利为z元。
x1桶牛奶可生产3x1公斤A1,获利24*3x1,x2桶牛奶可生产4x2公斤A2,获利16*4x2,故z=72x1+64x2
约束条件:
①、原料供应生产A1、A2的原料(牛奶)总量不超过每天的供应50桶,即:
x1+x2≤50
②、劳动时间生产A1、A2的总加工时间不超过每天正式工人总的劳动时间480小时,即:
12x1+8x2≤480
③、设备能力A1的产量不得超过设备甲每天的加工能力100小时,即
3x1≤100
④、非负约束x1、x2均不能为负值,即:
x1≥0,x2≥0
综上所述可得:
Maxz=72x1+64x2
s.t.x1+x2≤50
12x1+8x2≤480
3x1≤100
x1≥0,x2≥0
因为,目标函数和约束条件都是线性的,所以这是一个线性规划问题(linearprogramming,LP),求出的最优解将给出使净利润最大的生产计划,要讨论的问题需要考虑参数的变化对最优解和影响,一般称为敏感性(或灵敏度)分析。
(II)用LINGO求解
在LINGO模型窗口输入:
max=72*x1+64*x2;
x1+x2<=50;
12*x1+8*x2<=480;
3*x1<=100;
注:
由于LINGO中已假设所有的变量都是非负的,所以非负约束条件不必输入;LINGO也不区分变量中的大小写字符(实际上任何小写字符将被转换为大写字符)。
然后,用鼠标单击菜单中的“求解”命令(SOLVE)或点击工具栏上的“
”就可以得到解答,结果窗口显示如下:
Globaloptimalsolutionfound.
Objectivevalue:
3360.000
Infeasibilities:
0.000000
Totalsolveriterations:
2
VariableValueReducedCost
X120.000000.000000
X230.000000.000000
RowSlackorSurplusDualPrice
13360.0001.000000
20.00000048.00000
30.0000002.000000
440.000000.000000
其中:
Value给出最优解中各变量(Variabl)的值:
x1=20.000000,x2=30.000000。
ReducedCost(缩减成本系数)的含义是(max型问题):
基变量的REDUCEDCOST值为0,对于非基变量,相应的REDUCEDCOST值表示当非基变量增加一个单位时(其它非基变量保持不变)目标函数减少的量。
本例中两个变量都是基变量。
SlackorSurplus给出松弛变量的值,表示约束是否取等式约束;第2、第3
行松弛变量均为0,说明对于最优解而言,两个约束均取等式约束;第4行松弛变量为40.000000,说明对于最优解而言,这个约束取不等式约束。
DualPrice给出约束的影子价格(也称为对偶价格)的值:
第2、第3、第4行(约束)对应的影子价格分别48.000000,2.000000,0.000000。
具体地,计算结果说明:
这个线性规划的最优解为x1=20,x2=30,最优值为z=3360,即用20桶牛奶生产A1,30桶牛奶生产A2,可获最大利润3360元。
输出中除了告诉我们问题的最优解和最优值以外,还有许多对分析结果有用的信息,下面结合题目中提出的3个附加问题给予说明。
3个约束条件的右端不妨看作3种“资源”:
原料、劳动时间、车间甲的加工能力。
SlackorSurplus给出这3种资源在最优解下是否有剩余:
原料、劳动时间的剩余均为零,车间甲尚余40(公斤)加工能力。
目标函数可以看作“效益”,成为紧约束的“资源”一旦增加,“效益”必然跟着增长。
DualPrice给出这3种资源在最优解下“资源”增加1个单位时“效益”的增量:
原料增加1个单位(1桶牛奶)时利润增长48(元),劳动时间增加1个单位(1小时)时利润增长2(元),而增加非紧约束车间甲的能力显然不会使利润增长。
这里,“效益”的增量可以看作“资源”的潜在价值,经济学上称为影子价格,即1桶牛奶的影子价格为48元,1小时劳动的影子价格为2元,车间甲的影子价格为零。
用影子价格的概念很容易回答附加问题1):
用35元可以买到1桶牛奶,低于1桶牛奶的影子价格48,当然应该作这项投资。
回答附加问题2):
聘用临时工人以增加劳动时间,付给的工资低于劳动时间的影子价格才可以增加利润,所以工资最多是每小时2元。
目标函数的系数发生变化时(假定约束条件不变),最优解和最优值会改变吗?
上面输出给出了最优基不变条件下目标函数系数的允许变化范围x1的系数为(72-8,72+24)=(64,96);x2的系数为(64-16,64+8)=(48,72)。
注意:
x1系数的允许范围需要x2系数64不变,反之亦然。
由于目标函数的费用系数变化并不影响约束条件,因此此时最优基不变可以保证最优解也不变,但最优值变化。
用这个结果很容易回答附加问题3):
若每公斤A1的获利增加到30元,则x1系数变为30×3=90,在允许范围内,所以不应改变生产计划,但最优值变为90×20+64×30=3720。
总之:
用LINGO求解加工奶制品的生产计划,结果如下:
20桶牛奶生产A1,30桶生产A2,利润3360元。
1)35元可买到1桶牛奶,要买吗?
由于原料的影子价格为48,35<48,应该买!
2)聘用临时工人付出的工资最多每小时几元?
由于工时的影子价格为2,聘用临时工人付出的工资最多每小时2元;
3)A1获利增加到30元/千克,应否改变生产计划
由于要使最优解保持不变,X1系数的允许变化范围为[64,96]。
x1系数由24*3=72增加为30*3=90,在允许范围内。
所以不改变生产计划。
1.3线性规划练习
实验目的:
练习建立实际问题的线性规划模型;掌握用LINDO软件求解线性规划问题。
实验内容:
1.用LINDO求解下列线性规划问题
1)minz=
+
+
st
2)maxz=5(2
)
st
2.某化工厂要用三种原材料C、P、H混合配出三种不同规格的产品A、B、D。
已知产品的规格要求,产品单价,每天能供应的原材料数量及原材料单价如表1所示,求最优生产计划。
表1产品的规格要求,产品单价、原材料数量及原材料单价
产品
原料
ABC
供应量(kg/天)
单价(元/kg)
C
P
H
100
100
60
65
25
35
单价(元/kg)
503525
3.连续投资问题。
某部门在今后五年内考虑给下列项目投资,已知:
项目A,从第一年到第四年年初需要投资,并于次年末回收本利110%;
项目B,第三年初需要投资,到第五年末能回收本利115%,但规定最大投资额不超过4万元;
项目C,第二年初需要投资,到第五年末能回收本利130%,但规定最大投资额不超过3万元;
项目D,五年内每年初可购买公债,于当年末归还,并加利息3%。
该部门现有资金10万元,问它应如何确定给这些项目每年的投资额,使到第五年末拥有资金的本利总额为最大?
4.某银行经理计划用一笔资金进行有价证券的投资,可供购进的证券以及信用等级、到期年限、收益如表2所示。
按照规定,市政证券的收益可以免税,其他证券的收益需按50%的税率纳税。
此外还有以下限制:
(1)政府及代办机构的证券总共至少要够进400万元;
(2)所购证券的平均信用等级不超过1.4(信用等级数字越小,信用程度越高);
(3)所购证券的平均年限不超过5年;
表2证券以及信用等级、到期年限、收益
证券名称
种类
信用等级
到期年限
到期收益%
A
市政
2
9
4.3
B
代办机构
2
15
5.4
C
政府
1
4
5.0
D
政府
1
3
4.4
E
市政
5
2
4.5
(1)若该经理拥有1000万元资金,应如何投资?
(2)如果能够以2.75%的利率借到不超过100万元资金,该经理应如何操作?
(3)在1000万元资金情况下,若证券A的税前收益增加为4.5%,投资应否改变?
若证券C的税前收益减少为4.8%,投资应否改变?
2用LINGO求解整数规划问题
2.1实例及数学模型
例1.钢管下料问题
问题某钢管零售商从钢管厂进货,将钢管按照顾客要求的长度进行切割,称为下料。
假定进货时得到的原料钢管长度都是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种,如表3所示:
于是问题化为在满足客户需要的条件下,按照哪几种合理的模式,每种模式切割多少根原料钢管最为节省。
而所谓节省,可以有两种标准,一是切割后剩余的总余料量最小,二是切割原料钢管的总根数最少。
下面将对这两个目标分别讨论。
模型
问题1)用xi表示按照表3第i种模式(i=1,2,…,7)切割的原料钢管的根数,若以切割后剩余的总余料量最小为目标,则按照表3最后一列可得
MinZ1=3x1+x2+3x3+3x4+x5+x6+3x7
(1)
若以切割原料钢管的总根数最少为目标,则有
表3钢管下料问题1)的合理切割模式
模式
4m钢管根数
6m钢管根数
8m钢管根数
余料/m
1
4
0
0
3
2
3
1
0
1
3
2
0
1
3
4
1
2
0
3
5
1
1
1
1
6
0
3
0
1
7
0
0
2
2
MinZ2=x1+x2+x3+x4+x5+x6+x7
(2)
约束条件为客户的需求,按照表3应有
4x1+3x2+2x3+x4+x5≥50(3)
x2+2x4+x5+3x6≥20(4)
x3+x5+2x7≥15(5)
最后,切割的原料钢管的根数xi显然应当是非负整数(用Z表示整数集合,Z+表示非负整数集合):
xi∈Z+,i=1,2,…,7(6)
于是,问题1)归结为在约束条件(3)~(6)下,使目标
(1)或目标
(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(7)
满足客户需求的约束条件为
r11x1+r12x2+r13x3≥50(8)
r21x1+r22x2+r23x3≥10(9)
r31x1+r32x2+r33x3≥20(10)
r41x1+r42x2+r43x3≥15(11)
每一种切割模式必须可行、合理,所以每根原料钢管的成品量不能超过19m,也不能少于16m(余料不能大于3m),于是
16≤4r11+5r21+6r31+8r41≤19(12)
16≤4r12+5r22+6r32+8r42≤19(13)
16≤4r13+5r23+6r33+8r43≤19(14)
最后,加上非负整数约束:
xi,rji∈Z+,i=1,2,3,j=1,2,3,4(16)
于是,问题2)归结为在在约束条件下,求xi和r1i,r2i,r3i,r4i(i=1,2,3)使目标(7)达到最小。
显然这是线性整数规划模型。
2.2用LINGO求解
问题
(1)的求解.将式
(1),式(3)~(6)构成的线性整数规划模型输入LINDO如下:
model:
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);
@gin(x4);@gin(x5);@gin(x6);
@gin(x7);
end
可以得到最优解如下:
Globaloptimalsolutionfound.
Objectivevalue:
27.00000
Objectivebound:
27.00000
Infeasibilities:
0.000000
Extendedsolversteps:
0
Totalsolveriterations:
3
VariableValueReducedCost
X10.0000003.000000
X212.000001.000000
X30.0000003.000000
X40.0000003.000000
X515.000001.000000
X60.0000001.000000
X70.0000003.000000
RowSlackorSurplusDualPrice
127.00000-1.000000
21.0000000.000000
37.0000000.000000
40.0000000.000000
即:
按照模式2切割12根原料钢管,按照模式5切割15根原料钢管,共27根,总余料量27m。
显然,在总余料量最小的目标下,最优解将是使用余料尽可能小的切割模式(模式2和模式5的余料为1m),这会导致切割原料钢管的总根数较多。
问题
(2)的求解
非线性整数规划模型(7)~(15)虽然用LINGO软件可以直接求解,但为了减少运行时间,可以增加一些显然的约束条件,从而缩小可行解的搜索范围。
例如,由于3种切割模式的排列顺序是无关要紧的,所以不妨增加以下约束:
x1≥x2≥x3(16)
又如,注意到所需原料钢管的总根数有明显的上界和下界。
首先,原料钢管的根数不可能少于
(根)。
其次,考虑一种非常特殊的生产计划:
第一种切割模式下只生产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(17)
将式(7)~(17)构成的模型输入LINGO如下:
model:
min=x1+x2+x3;
r11*x1+r12*x2+r13*x3>=50;
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<=19;
4*r13+5*r23+6*r33+8*r43<=19;
4*r11+5*r21+6*r31+8*r41>=16;
4*r12+5*r22+6*r32+8*r42>=16;
4*r13+5*r23+6*r33+8*r43>=16;
x1+x2+x3>=26;
x1+x2+x3<=31;
x1>=x2;
x2>=x3;
@gin(x1);@gin(x2);@gin(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);
end
得到结果如下:
Globaloptimalsolutionfound.
Objectivevalue:
28.00000
Objectivebound:
28.00000
Infeasibilities:
0.000000
Extendedsolversteps:
1
Totalsolveriterations:
129601
VariableValue
X110.00000
X210.00000
X38.000000
R112.000000
R123.000000
R130.000000
R211.000000
R220.000000
R230.000000
R311.000000
R321.000000
R330.000000
R410.000000
R420.000000
R432.000000
RowSlackorSurplus
128.00000
20.000000
30.000000
40.000000
51.000000
60.000000
71.000000
83.000000
93.000000
102.000000
110.00000
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- LINGO 线性规划 整数 规划