《数学建模》实验指导_03_Lingo求解线性规划问题
- 格式:doc
- 大小:70.50 KB
- 文档页数:3
实验一:利用Lingo 软件求解线性规划问题实验一 利用Lingo 软件求解线性规划问题1、 实验目的和任务1.1. 进一步掌握Lingo 编程操作;1.2通过实验进一步掌握运筹学线性规划问题的建模以及求解过程,提高学生分析问题和解决问题能力。
2、 实验仪器、设备及材料计算机、Lingo3、 实验内容料场选址问题P10某公司有6个建筑工地要开工,每个工地的位置(用平面坐标a,b 表示,距离单位:km )及水泥日用量d(单位:t)由下表给出,目前有两个临时料场位于P (5,1),Q (2,7),日储量各有20t.请回答以下问题: 假设从料场到工地之间有直线道路相连,试制定每天的供应计划,即从P,Q 两料场分别向各工地运送多少吨水泥,使总的吨公量数最小。
工地的位置(a,b )及水泥日用量d建模 设工地的位置为(,)i i a b ,水泥日用量为i d ,i=1,2,…,6;料场位置为(,)j j x y ,日储量为j e ,j=1,2; 从料场j 向工地i 的运送量为ij c 。
决策变量:在问题(1)中,决策变量就是料场j 向工地i 的运送量为ij c ;在问题(2)中,决策变量除了料场j 向工地i 的运送量为ij c 外,新建料场位置(,)j j x y 也是决策变量。
目标函数:这个优化问题的目标函数f 是总砘公量数(运量乘以运输距离),所以优化目标可表为2611min j i f c ===∑∑约束条件:各工地的日用量必须满足,所以21,1,2, (6)ij ijc d i ===∑各料场的运送量不能超过日储量,所以61,1,2. ij jic e j =≤=∑求解过程编写模型程序:(介绍集合的定义及应用)model:sets:!确定变量a(1),a(2),a(3),a(4),a(5),a(6);demand/1..6/:a,b,d;supply/1..2/:x,y,e;link(demand,supply):c;endsetsdata:!分割数据的空格与逗号或回车的作用是等价的;a=1.25 8.75 0.5 5.75 3 7.25;b=1.25,0.75,4.75,5,6.5,7.75;d=3,5,4,7,6,11;e=20,20;!a=enddatainit:!lingo对数据是按列赋值的,而不是按行;x,y=5,1,2,7;endinit[OBJ] min=@sum(link(i,j):c(i,j)*((x(j)-a(i))^2+(y(j)-b(i))^2)^(1/2));@for(demand(i):[demand_con] @sum(supply(j):c(i,j))=d(i););@for(supply(i):[supply_con] @sum(demand(j):c(j,i))<=e(i););@for(supply(i):@bnd(0.5,x(i),8.75);@bnd(0.75,y(i),7.75););End计算结果:(如果你使用的是试用版软件,则可能不能用全局求解器求解本例,因为问题规模太大了,激活全局最优求解程序的方法,是用“lingo|Options”菜单命令打开选项对话框,在“Global Solver”选项卡上选择“Use Global Solver”)Local optimal solution found.Objective value: 85.26604Total solver iterations: 61Variable Value Reduced CostA( 1) 1.250000 0.000000A( 2) 8.750000 0.000000A( 3) 0.5000000 0.000000A( 4) 5.750000 0.000000A( 5) 3.000000 0.000000A( 6) 7.250000 0.000000B( 1) 1.250000 0.000000B( 2) 0.7500000 0.000000B( 3) 4.750000 0.000000B( 4) 5.000000 0.000000B( 5) 6.500000 0.000000B( 6) 7.750000 0.000000D( 1) 3.000000 0.000000D( 2) 5.000000 0.000000D( 3) 4.000000 0.000000D( 4) 7.000000 0.000000D( 5) 6.000000 0.000000D( 6) 11.00000 0.000000X( 1) 3.254883 0.000000X( 2) 7.250000 0.6335133E-06 Y( 1) 5.652332 0.000000Y( 2) 7.750000 0.5438639E-06 E( 1) 20.00000 0.000000E( 2) 20.00000 0.000000C( 1, 1) 3.000000 0.000000C( 1, 2) 0.000000 4.008540C( 2, 1) 0.000000 0.2051358C( 2, 2) 5.000000 0.000000C( 3, 1) 4.000000 0.000000C( 3, 2) 0.000000 4.487750C( 4, 1) 7.000000 0.000000C( 4, 2) 0.000000 0.5535090C( 5, 1) 6.000000 0.000000C( 5, 2) 0.000000 3.544853C( 6, 1) 0.000000 4.512336C( 6, 2) 11.00000 0.000000Row Slack or Surplus Dual PriceOBJ 85.26604 -1.000000DEMAND_CON( 1) 0.000000 -4.837363DEMAND_CON( 2) 0.000000 -7.158911DEMAND_CON( 3) 0.000000 -2.898893DEMAND_CON( 4) 0.000000 -2.578982DEMAND_CON( 5) 0.000000 -0.8851584DEMAND_CON( 6) 0.000000 0.000000SUPPLY_CON( 1) 0.000000 0.000000SUPPLY_CON( 2) 4.000000 0.000000如果把料厂P,Q的位置看成是已知并且固定的,这时是LP模型,只需把上面的程序中初始段的语句移到数据段就可以了。
实验报告课程名称:运筹学项目名称:线性规划问题的求解姓名:专业:班级:1班学号:同组成员:一、实验准备:1.线性规划(Linear programming,简称LP)是运筹学中研究较早、发展较快、应用广泛、方法较成熟的一个重要分支,它是辅助人们进行科学管理的一种数学方法。
研究线性约束条件下线性目标函数的极值问题的数学理论和方法。
英文缩写LP。
它是运筹学的一个重要分支,广泛应用于军事作战、经济分析、经营管理和工程技术等方面。
为合理地利用有限的人力、物力、财力等资源作出的最优决策,提供科学的依据。
从实际问题中建立数学模型一般有以下三个步骤;(1)根据影响所要达到目的的因素找到决策变量;(2)由决策变量和所在达到目的之间的函数关系确定目标函数;(3)由决策变量所受的限制条件确定决策变量所要满足的约束条件。
2.所建立的数学模型具有以下特点:(1)每个模型都有若干个决策变量(x1,x2,x3……,xn),其中n为决策变量个数。
决策变量的一组值表示一种方案,同时决策变量一般是非负的。
(2)目标函数是决策变量的线性函数,根据具体问题可以是最大化(max)或实际中,为保证完成100套工架,所使用原材料最省,可以混合使用各种下料方案。
设按方案A,B,C,D,E下料的原材料数分别为x1,x2,x3,x4,x5根据表可以得到下面的线性规划模型:解:虽然连续投资问题属于动态优化问题,但可以用静态优化的方法解决,用决策变量xi1,xi2,xi3,xi4(i=12…,5)分别表示第i年年初为项目A,B,C,D,的投资额,根据问题的要求各变量的对应关系如表,表中空白处表示当年不能为该项目投资,也可认为投资额为0.实验报告成绩(百分制)__________ 实验指导教师签字:__________。
实验课题:(一)线性规划问题1.用lingo求解下列线性规划问题:2. 某班男同学30人、女同学20人,植树。
工作效率(个/人、天)如下表。
如何安排,植树最多?3.某牧场饲养一批动物,平均每头动物至少需要 700g 蛋白质、30g 矿物质和100g 维生素。
现有A、B、C、D、E五种饲料可供选用,每千克饲料的营养成分(单位:g)与价格(单位:元/kg)如下表所示:试求能满足动物生长营养需求又最经济的选用饲料方案。
4.在以色列,为分享农业技术服务和协调农业生产,常常由几个农庄组成一个公共农业社区。
在本课题中的这个公共农业社区由三个农庄组成,我们称之为南方农庄联盟。
南方农庄联盟的全部种植计划都由技术协调办公室制订。
当前,该办公室正在制订来年的农业生产计划。
南方农庄联盟的农业收成受到两种资源的制约。
一是可灌溉土地的面积,二是灌溉用水量。
这些数据由下表给出。
注:英亩-英尺是水容积单位,1英亩-英尺就是面积为1英亩,深度为1英尺的体积;1英亩-英尺≈1233.48立方米。
南方农庄联盟种植的作物是甜菜、棉花和高粱,这三种作物的纯利润及耗水量不同。
农业管理部门根据本地区资源的具体情况,对本联盟农田种植规划制定的最高限额数据由下表给出。
三家农庄达成协议:各家农庄的播种面积与其可灌溉耕地面积之比相等;各家农庄种植何种作物并无限制。
所以,技术协调办公室面对的任务是:根据现有的条件,制定适当的种植计划帮助南方农庄联盟获得最大的总利润,现请你替技术协调办公室完成这一决策。
对于技术协调办公室的上述安排,你觉得有何缺陷,请提出建议并制定新的种植计划。
5.有一艘货轮,分前、中、后三个舱位,它们的容积与最大允许载重量如下表所示:前舱中舱后舱最大允许载重量(t)2000 3000 1000容积(m3)4000 5400 1000现有三种货物待运,已知有关数据如下表所示:商品数量(件)每件体积(m3/件)每件重量(t/件)运价(元/件)A 600 10 8 1000B 1000 5 6 700C 800 7 5 600又为了航运安全,要求前、中、后舱在实际载重量上大体保持各舱最大允许载重量的比例关系。
实验1 用LINGO求解线性规划问题LINGO使用简介LINGO软件是美国的LINDO系统公司(Lindo System Inc)开发的一套用于求解最优化问题的软件包.LINGO除了能用于求解线性规划和二次规划外,还可以用于非线性规划求解以及一些线性和非线性方程(组)的求解.LINGO软件的最大特色在于它允许优化模型中的决策变量为整数,而且执行速度快.LINGO内置了一种建立最优化模型的语言,可以简便地表达大规模问题,利用LINGO高效的求解器可快速求解并分析结果,这里简单介绍LINGO的使用方法.LINGO可以求解线性规划、二次规划、非线性规划、整数规划、图论及网络优化和排队论模型中的最优化问题等.一个LINGO程序一般会包含集合段、数据输入段、优化目标和约束段、初始段和数据预处理段等部分,每一部分有其独特的作用和语法规则,读者可以通过查阅相关的参考书或者LINGO的HELP文件详细了解,这里就不展开介绍了.LINGO的主要功能特色为:既能求解线性规划问题,也有较强的求解非线性规划问题的能力;输入模型简练直观;运算速度快、计算能力强;内置建模语言,提供几十个内部函数,从而能以较少语句,较直观的方式描述大规模的优化模型;将集合的概念引入编程语言,很容易将实际问题转换为LINGO模型;并且能方便地与Excel、数据库等其他软件交换数据.LINGO的语法规定:(1)求目标函数的最大值或最小值分别用MAX=…或MIN=…来表示;(2)每个语句必须以分号“;”结束,每行可以有许多语句,语句可以跨行;(3)变量名称必须以字母(A~Z)开头,由字母、数字(0~9)和下划线所组成,长度不超过32个字符,不区分大小写;(4)可以给语句加上标号,例如[OBJ] MAX=200*X1+300*X2;(5)以惊叹号“!”开头,以分号“;”结束的语句是注释语句;(6)如果对变量的取值范围没有作特殊说明,则默认所有决策变量都非负;(7)LINGO模型以语句“MODEL:”开头,以“END”结束,对于比较简单的模型,这两个语句可以省略.实验目的1.对于给定的实际应用问题,正确的建立线性规划问题数学模型,并用LINGO求解;2.掌握灵敏度分析以及资源的影子价格的相关分析方法.实验数据与内容问题1.1某工厂在计划期内要安排生产A、B两种产品,已知生产单位产品所需设备台时及对甲、乙两种原材料的消耗,有关数据如表1.1.问:应如何安排生产计划,使工厂获利最大?.问题1.2 某公司饲养实验用的动物以供出售,已知这些动物的生长对饲料中3种营养成分(蛋白质、矿物质和维生素)特别敏感,每个动物每周至少需要蛋白质60g ,矿物质3g ,维生素8mg ,该公司能买到5种不同的饲料,每种饲料1kg 所含各种营养成分和成本如表1.2所示,如果每个小动物每周食用饲料不超过52kg ,求既能满足动物生长需要,又使总成本最低的饲料配方.实验指导问题1.1设计划生产两种产品分别为,则建立线性规划问题数学模型B A ,21,x x ⎪⎪⎩⎪⎪⎨⎧≥≤≤≤++=0,12416482.32max 21212121x x x x x x t s x x S 在LINGO 的MODEL 窗口内输入如下模型:model :max =2*x1+3*x2;x1+2*x2<=8;4*x1<=16;4*x2<=12;end选菜单Lingo|Solve(或按Ctrl+S),或用鼠标点击“求解”按纽,如果模型有语法错误,则弹出一个标题为“LINGO Error Message ”(错误信息)的窗口,指出在哪一行有怎样的错误,每一种错误都有一个编号(具体含义可查阅相关文献或LINGO 的Help ).改正错误以后再求解,如果语法通过,LINGO 用内部所带的求解程序求出模型的解,然后弹出一个标题为“LINGO Solver Status ”(求解状态)的窗口,其内容为变量个数、约束条件个数、优化状态、耗费内存、所花时间等信息,点击Close 关闭窗口,屏幕上出现标题为“Solution Report ”(解的报告)的信息窗口,显示优化计算(线性规划中换基迭代)的步数、优化后的目标函数值、列出各变量的计算结果.求解结果:Global optimal solution found at iteration: 5Objective value: 14.00000Variable Value Reduced CostX1 4.000000 0.000000X2 2.000000 0.000000Row Slack or Surplus Dual Price1 14.00000 1.0000002 0.000000 1.5000003 0.000000 0.12500004 4.000000 0.000000该报告说明:运行5步找到全局最优解,目标函数值为14,变量值分别为.“Reduced Cost ”的含义是需缩减成本系数或需增加利润系数(最优解中取值非零的决策变量的Reduced Cost 值等于零).“Row ”是输入模型中的行号,目标函数是第一行;“Slack or Surplus ”的意思是松弛或剩余,即约束条件左边与右边的差值,对于“124,2==x x ≤”的不等式,右边减左边的差值为Slack (松弛),对于“”的不等式,左边减右边的差值为Surplus (剩余),当约束条件两边相等时,松弛或剩余的值等于零.“Dual Price ”的意思是对偶价格(或称为影子价格),上述报告中Row2的松弛值为0,表明生产甲产品4单位、乙产品2单位,所需设备8台时已经饱和,对偶价格1.5的含义是:如果设备增加1台时,能使目标函数值增加1.5.报告中Row4的松弛值为4,表明生产甲产品4单位、乙产品2单位,所需原材料乙8公斤还剩余4公斤,因此增加原材料乙不会使目标函数值增加,所以对偶价格为0.≥问题1.2设需要饲料分别为 kg ,则建立线性规划数学模型:54321,,,,A A A A A 54321,,,,x x x x x 123451234512345123451234512345min 0.20.70.40.30.50.320.6 1.8600.10.050.020.20.0530.050.10.020.20.088.52,,,,0S x x x x x x x x x x x x x x x x x x x x s t x x x x x x x x x x =++++++++≥⎧⎪++++⎪⎪≥++++⎨⎪++++≤⎪≥⎪⎩≥ 在LINGO 的MODEL 窗口内输入如下模型:Min=0.2*x1+0.7*x2+0.4*x3+0.3*x4+0.5*x5;0.3*x1+2*x2+x3+0.6*x4+1.8*x5>60;0.1*x1+0.05*x2+0.02*x3+0.2*x4+0.05*x5>3;0.05*x1+0.1*x2+0.02*x3+0.2*x4+0.08*x5>8;x1+x2+x3+x4+x5<52;求解输出结果如下:Global optimal solution found at iteration: 4Objective value: 22.40000Variable Value Reduced CostX1 0.000000 0.7000000X2 12.00000 0.000000X3 0.000000 0.6166667X4 30.00000 0.000000X5 10.00000 0.000000Row Slack or Surplus Dual Price1 22.40000 -1.0000002 0.000000 -0.58333333 4.100000 0.0000004 0.000000 -4.1666675 0.000000 0.8833333因此,每周每个动物的配料为饲料、、分别为12、30和10kg ,合计为52,可使得饲养成本达到最小,最小成本为22.4元;不选用饲料和的原因是因为这两种饲料的价格太高了,没有竞争力.“Reduced Cost ”分别等于0.7和0.617,说明当这两种饲料的价格分别降低0.7元和0.62元以上时,不仅选用这两种饲料而且使得饲养成本降低.从“Slack or Surplus”可以看出,蛋白质和维生素刚达到最低标准,矿物质超过最低标准4.12A 4A 5A kg kg kg 1A 3A g ;从“Dual Price”可以得到降低标准蛋白质1单位可使饲养成本降低0.583元,降低标准维生素1单位可使饲养成本降低4.167元,但降低矿物质的标准不会降低饲养成本,如果动物的进食量减少,就必须选取精一些的饲料但要增加成本,大约进食量降低1可使得饲养成本增加0.88元.kg 对于目标函数系数和约束条件右端常数项的灵敏度分析,可以通过LINGO 软件求解的灵敏度分析给出.如果要看灵敏度分析结果,必须激活灵敏度计算功能才会在求解时给出灵敏度分析结果,默认情况下这项功能是关闭的.想要激活它,必须运行LINGO|Options …命令,选择Gengral Solver ,在Dual Computation 列表框中,选择Prices and Ranges 选项并确定.对于例1.1问题进行灵敏度分析,结果如下:以下是灵敏度分析的结果Ranges in which the basis is unchanged:Objective Coefficient RangesCurrent Allowable AllowableVariable Coefficient Increase DecreaseX1 2.000000 INFINITY 0.5000000X2 3.000000 1.000000 3.000000Righthand Side RangesRow Current Allowable AllowableRHS Increase Decrease2 8.000000 2.000000 4.0000003 16.00000 16.00000 8.0000004 12.00000 INFINITY 4.000000对于例1.2问题进行灵敏度分析,结果如下:Ranges in which the basis is unchanged:Objective Coefficient RangesCurrent Allowable AllowableVariable Coefficient Increase DecreaseX1 0.2000000 INFINITY 0.7000000X2 0.7000000 INFINITY 0.1358974X3 0.4000000 INFINITY 0.6166667X4 0.3000000 1.400000 1.000000X5 0.5000000 0.1247059 INFINITYRighthand Side RangesRow Current Allowable AllowableRHS Increase Decrease2 60.00000 4.800000 4.8000003 3.000000 4.100000 INFINITY4 8.000000 0.3428571 0.48000005 52.00000 1.846154 1.411765思考题某投资公司拟制定今后5年的投资计划,初步考虑下面四个投资项目:项目A:从第1年到第4年每年年初可以投资,于次年年末收回成本,并可获利润15%;项目B:第3年年初可以投资,到第5年年末可以收回成本,并获得利润25%,但为了保证足够的资金流动,规定该项目的投资金额上限为不超过总金额的40%;项目C:第2年年初可以投资,到第5年年末可以收回成本,并获得利润40%,但公司规定该项目的最大投资金额不超过总金额的30%;项目D:5年内每年年初可以购买公债,于当年年末可以归还本金,并获利息6%.该公司现有投资金额100万元,请帮助该公司制定这些项目每年的投资计划,使公司到第5年年末核算这5年投资的收益率达到最大.建立线性规划问题的数学模型,并用LINGO求解.。
实验二:Lingo求解线性规划问题
学时:4学时
实验目的:掌握用Lingo求解线性规划问题的方法,能够阅读Lingo结果报告。
实验内容:
1、求解书本上P130的习题1:
某银行经理计划用一笔资金进行有价证券的投资,可供购进的证券以及其信用等级、到期年限、收益如下表1所示,按照规定,市政证券的收益可以免税,其他证券的收益需按50%的税率纳税,此外还有以下限制:
1)政府及代办机构的证券总共至少要购进400万元;
2)所购证券的平均信用等级不超过1.4(信用等级数字越小,信用程序越高);
3)所购证券的平均到期年限不超过5年。
表 1
(1)若该经理有1000万元资金,应如何投资?
(2)如果能够以2.75%的利率借到不超过100万元资金,该经理应如何操作?
(3)在1000万元资金情况下,若证券A的税前收益增加为4.5%,投资应否改变?若证券C的税前收益减少为4.8%,投资应否改变?
列出线性规划模型,然后用Lingo求解,根据结果报告得出解决方案。
2、指派问题:6个人计划做6项工作,其效益如下表(”-”表示某人无法完成某项工作),
3、有限制的运输问题:6个发点6个收点,其供应量、接收量和运费如下表1(”-”表示某个发电无法向某个收点运输货物),如果某个发点向某个收点运输货物,则运输量不得低
使用Lingo 的一些注意事项
1. “>”与“>=”功能相同。
2. 变量与系数间相乘必须用”*”号,每行用”;”结束。
3. 变量以字母开头,不能超过8个字符。
4. 变量名不区分大小写(包括关键字)。
5. 目标函数用min=3*x1+2*x2或max=3*x1+2*x2的格式表示。
6. “!”后为注释。
7. 变量界定函数实现对变量取值范围的附加限制,共4种:
@bin(x) 限制x 为0或1 @bnd(L,x,U) 限制L≤x≤U
@free(x) 取消对变量x 的默认下界为0的限制,即x 可以取任意实数 @gin(x) 限制x 为整数 其他可见“Lingo 教程.doc ”
如书上85页的Lindo 代码可改为如下Lingo 代码: max =72*x1+64*x2; x1+x2<50;
12*x1+8*x2<480; 3*x1<100;
例1.1 如何在LINGO 中求解如下的LP 问题:
,6002100
350.
.32min 21211
212
1≥≤+≥≥++x x x x x x x t s x x
在模型窗口中输入如下代码:
min =2*x1+3*x2; x1+x2>=350; x1>=100;
2*x1+x2<=600;
然后点击工具条上的按钮 即可。
例1.2 使用LINGO 软件计算6个发点8个收点的最小费用运输问题。
产销单位运价如
6
8
,,1
1
6
,18
,1
m in * 1,,8 1,,6
i j
i j
i j i j
j i i j
i j cost
volum e volum e
dem and j volum e
capacity i ========∑
∑∑∑ 使用LINGO 软件,编制程序如下:
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 4 9 5 3 8 5 8 2 5 2 1 9 7 4 3 3 7 6 7 3 9 2 7 1 2 3 9 5 7 2 6 5 5 5 2 2 8 1 4 3; enddata end。