线性规划问题的求解幻灯片.ppt

上传人:石*** 文档编号:48386616 上传时间:2022-10-06 格式:PPT 页数:68 大小:3.78MB
返回 下载 相关 举报
线性规划问题的求解幻灯片.ppt_第1页
第1页 / 共68页
线性规划问题的求解幻灯片.ppt_第2页
第2页 / 共68页
点击查看更多>>
资源描述

《线性规划问题的求解幻灯片.ppt》由会员分享,可在线阅读,更多相关《线性规划问题的求解幻灯片.ppt(68页珍藏版)》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、线性规划问题的求解第1页,共68页,编辑于2022年,星期一5.1一般线性规划模型的建立与求解5.1.1基本理论线性规划问题的标准形式是等约束的,用矩阵表示如下:一般线性规划问题都可以通过引入松弛变量松弛变量与剩余变量剩余变量的方法化成标准形式。线性规划模型的一般性质:(1)比例性比例性,每个决策变量对目标函数以及右端项的贡献与该决策变量的取值成正比。(2)可加性可加性,每个决策变量对目标函数以及右端项的贡献与其他决策变量的取值无关。(3)连续性连续性,每个决策变量的取值都是连续的。比例性和可加性保证了目标函数和约束条件对于决策变量的线性性质,连续性则允许得到决策变量的实数最优解。单纯形算法的

2、实质单纯形算法的实质:在保证可行(最小比值法则)的前提下,先在可行解上取一个顶点,判断是否达到最优解,如果没有,则通过一定的规则(入基,旋转等)到另一个更优第2页,共68页,编辑于2022年,星期一的顶点,如此迭代下去直到最优,或者判断不可行或者判断无界为止。5.1.2应用举例例5-1(运输问题运输问题)两个粮库A1,A2,向三个粮站B1,B2,B3调运大米,两个粮库现存大米分别为4t,8t,三个两站至少需要大米分别为2t,4t,5t,两个粮库到三个粮站的距离(km)如下表,求使运费最低。B1B2B3库存库存A1122484A23012248需求需求245解:(1)问题分析:总需求量为11t,

3、小于总库存量12t,所以问题可行。(2)从线性规划的三个要素出发,决策变量决策变量:问题是各个粮仓向粮站调运了多少大米,此调运量就是决策变量。目标函数目标函数:运费和运量和距离有关系,即t*km最小,所以要将运量与相应的距离相乘然后使总和最小。约束条件约束条件:两个粮库的库存量限制和三个粮站需求量的限制。第3页,共68页,编辑于2022年,星期一(3)建立模型,设A1,A2分别向B1,B2,B3运送大米x11,x12,x13,x21,x22,x23,则有:minf=12*x11+24*x12+8*x13+30*x21+12*x22+24*x23s.t.x11+x12+x13=4x21+x22+

4、x23=2x12+x22=4x13+x23=5x11,x12,x13,x21,x22,x23=0(4)转化成对应的Lingo建模语言程序1,求解模型,结果如下页图示:第4页,共68页,编辑于2022年,星期一第5页,共68页,编辑于2022年,星期一通过选择Lingo|Generate|Displaymodel将模型展开,方便查看求解报告的第三部分。相应的添加的剩余变量或者松弛变量。第6页,共68页,编辑于2022年,星期一程序改进一、上面解法是一种傻瓜式的直接输入法,适用于程序规模不大的问题,如果问题规模很大的话用这种方式很费力,可以使用矩阵生成器来编写程序2minf=12*x11+24*x

5、12+8*x13+30*x21+12*x22+24*x23s.t.x11+x12+x13+y1=4x21+x22+x23+y2=8x11+x21-y3=2x12+x22-y4=4x13+x23-y5=5x11,x12,x13,x21,x22,x23,y1,y2,y3,y4,y5=0转换成Lingo语言如下所示:第7页,共68页,编辑于2022年,星期一第8页,共68页,编辑于2022年,星期一注:1、写程序要习惯给程序用title命名2、为了方便查看报告,用行号区分约束3、此程序的格式可以固定为标准形式的求解模式。程序改进三:可以减少引入的变量个数,将模型修改为下面的形式minf=12*x11

6、+24*x12+8*x13+30*x21+12*x22+24*x23s.t.x11+x12+x13=4x21+x22+x23=8-x11-x21=-2-x12-x22=-4-x13-x23=0写成lingo语言如下所示:第9页,共68页,编辑于2022年,星期一第10页,共68页,编辑于2022年,星期一注:1、改程序把不等式约束全部转化为小于等于约束,是为了将约束可以写到是为了将约束可以写到一个循环语句中实现一个循环语句中实现,如果还有等是约束的话,则要在写一个循环语句来控制约束。2、当程序比较大的时候,一般将约束按性质约束按性质进行分类程序改进四:将约束进行分类,代码如下:第11页,共68

7、页,编辑于2022年,星期一注:1、在进行调试程序时,可以用!号某些语句屏蔽,缩小寻找出错的范围。2、可以编写程序边运行,保证每行书写都是正确的3、常见的出错情况有:(1)定义了多个长度一样的集合,而在使用中区分不明确;(2)定义了同名的属性;(3)漏掉了括号;(4)分号不是英文半角;(5)使用的字母没有定义;(6)循环语句中元素下标颠倒或者不明;(7)约束错误变成不可行或者无界;(8)关系运算符误用成逻辑运算符;(9)函数调用错误等等第12页,共68页,编辑于2022年,星期一例5-2(阶段生产问题阶段生产问题)某公司产品最大生产能力为10000单位,每单位存储费2元,预定的销售量与单位成本

8、如下表所示:月份月份单位成本单位成本销售量销售量17060002717000380120004766000求一生产计划,使(1)满足需求;(2)不超过生产能力;(3)成本(生产成本与存储费之和最低)问题分析:这是一个多阶段生产计划问题,设计多阶段存储,只需要制定14月份的生产计划,不妨假定1月初无库存,4月底卖完,当月生产的不作为当月的库存,库存量无限制。模型建立(1):设xi为第i月产量,di为销售量,ei为存储费,ci为单位成本,则目标生产成本为:第13页,共68页,编辑于2022年,星期一第j月到j+1月的库存量(记作第记作第j+1月的库存量月的库存量)应该是1月到j月的总产量减去1月到

9、j月的总销售量,即:总的库存费用为:总成本为:即求总成本的最小值。约束条件1:如果每个月都有非负的存储量,显然满足要求,可用约束:第14页,共68页,编辑于2022年,星期一约束条件3:产量限制,0=xi=10000。综上,建立如下数学模型:约束条件2:4个月的总产量等于总需求量即:转成相应的Lingo语言如下:第15页,共68页,编辑于2022年,星期一第16页,共68页,编辑于2022年,星期一模型改进(2):引入库存变量库存变量,再利用库存平衡方程使模型更加流畅简洁。设xi为第i个月的产量,di为销售量,ei为存储费,ci为单位成本,设第i个月的库存为si,则:程序编写如下:第17页,共

10、68页,编辑于2022年,星期一模型改进(3):将该模型转化成运输问题运输问题。设xij表示第i个月生产的产品在第j个月卖出去的数量,cij表示第i个月生产的产品在第j月卖出去时的生产成本与存储成本之和,第18页,共68页,编辑于2022年,星期一dj表示第j月的销售量,则生产月生产的产品在需求月卖出时单位总成本如下表所示:需求月需求月1需求月需求月2需求月需求月3需求月需求月4产量产量生产月17072747610000生产月271737510000生产月3808210000生产月47610000销量60007000120006000建立模型如下:第19页,共68页,编辑于2022年,星期一相

11、应的Lingo程序如下:第20页,共68页,编辑于2022年,星期一例5-3(连续投资问题连续投资问题)某部门在今后5年内考虑给下列项目投资,已知:(1)项目A,从第1年到第4年每年初要投资,次年末回收本利1.15;(2)项目B,第3年初投资,到第5年末回收本利1.25,最大投资4万元;(3)项目C,第2年初投资,到第5年末回收本利1.40,最大投资3万元;(4)项目D,每年初购买国债,当年末回收本利1.06;该部门现有资金10万元,问应如何投资到第5年末总资本最大。问题分析:将可能的投资情况设为变量,如下表所示第第1年年第第2年年第第3年年第第4年年第第5年年Ax1Ax2Ax3Ax4ABx3

12、BCx3CDx1Dx2Dx3Dx4Dx5D因为具有项目D,所以可以认为该部门每年都把自己全部投出去,而且年末的总资本等于第二年初的总投资额。由此可建立模型如下:第21页,共68页,编辑于2022年,星期一转换成Lingo程序如下所示:第22页,共68页,编辑于2022年,星期一第23页,共68页,编辑于2022年,星期一5.2灵敏性分析与影子价格5.2.1灵敏性分析例5-4(生产计划问题生产计划问题)某工厂计划安排生产III两种产品,已知每种单位产品的利润,生产单位产品所需设备台时及A,B两种原材料的消耗,现有原材料和设备台时的定额见下表所示:产品产品I产品产品II最大资源量最大资源量设备12

13、8台原材料A4016kg原材料B0412kg单位产品利润23求:(1)怎么样安排生产使得工厂利润最大?(2)产品I的单位利润降低到1.8万元,要不要改变生产计划,如果降低到1万元呢?(3)产品II的单位利润增大到5万元,要不要改变生产计划?(4)如果产品I,II的单位利润同时降低了1万元,要不要改变生产计划?第24页,共68页,编辑于2022年,星期一建立模型:用x1,x2分别表示计划生产产品III的数量,可建立如下模型编写lingo程序如下:第25页,共68页,编辑于2022年,星期一程序执行结果:通过执行结果对问题进行分析:问题1:安排生产产品I为4个单位,II为2个单位,最大利润为14万

14、元。灵敏性分析:打开LINGO中的灵敏性分析开关,LINGO|Options|GeneralSolver|DualComputations|PricesandRanges分析结果通过点击Lingo|Range命令获得第26页,共68页,编辑于2022年,星期一说明1、(1)红框内的部分是对目标函数进行的灵敏性分析,第一列是变量变量,第二列是对应的系数对应的系数,第三列是允许增加量允许增加量,第四列是允许减少量允许减少量,允许增加和允许减少都是在当前系数基础当前系数基础上改变的。在其他变量系数都不变的情况下有:在其他变量系数都不变的情况下有:当x1在(2-0.5,2+)=(1.5,)之间变化时,

15、最优解不变;当x2在(3-3,3+1)=(0,4)之间变化时,最优解不变。第27页,共68页,编辑于2022年,星期一问题2:产品I的单位利润降低到1.8万元,在(1.5,)之间,所以不改变生产计划;而降低到1万元,则需要重新制定生产计划;问题3:5万不在(0,4)范围内,故要重新制定生产计划。修改程序之后运行结果如下:问题4:因为两个系数同时发生变化,所以只能更改程序的数据,重新运行。运行结果和灵敏性分析结果如下:第28页,共68页,编辑于2022年,星期一第29页,共68页,编辑于2022年,星期一说明2、红框内所示为保持最优基不变的约束右端项的变化范围,即原材料A的量在(8-4,8+2)

16、=(4,10),原材料B的量在(16-8,16+16)=(8,32),设备台时在(12-4,12+)=(8,)内变化时,最优基保持不变。第30页,共68页,编辑于2022年,星期一5.2.2对偶问题两个线性规划问题:称为对称形式的对偶问题(dualproblem),互为对偶问题的(I)和(II)一个称为原问题,一个称为原问题的对偶问题。称对偶问题的最优解为原问题约束条件的影子价格(shadowprice)1、一对对称形式的对偶问题有如下的对应关系:(1)若一个模型为目标求极大,约束为小于等于的不等式,则它的对偶模型为目标求极小,约束为大于等于的不等式,即”max=”第31页,共68页,编辑于2

17、022年,星期一(2)从约束系数的矩阵看,一个模型为A,一个模型为AT,一个模型为m个约束,n个变量,另一个则为n个约束,m个变量。(3)从数据b和c的位置看,在两个规划模型中两者互换。(4)两个模型中的变量皆非负。2、非对称形式的对偶规划一般称不具有对称形式的一对线性规划为非对称形式的对偶规划。对于非对称形式的规划,可以按照下面的对应关系直接给出其对偶规划。(1)将模型统一为“max,”或“min,”的形式,对于其中的等式约束按下面(2)、(3)中的方法处理;(2)若原规划的某个约束条件为等式约束,则在对偶规划中与此约束对应的那个变量取值没有非负限制;(3)若原规划的某个变量的值没有非负限制

18、,则在对偶问题中与此变量对应的那个约束为等式。第32页,共68页,编辑于2022年,星期一下面对关系(2)作一说明。对于关系(3)可以给出类似的解释。设原规划中第一个约束为等式:a11x1+a1nxn=b1那么,这个等式与下面两个不等式等价:则原规划模型可以写成如下形式:第33页,共68页,编辑于2022年,星期一此时已转化为对称形式,可以直接写出其对偶问题:这里,把y1看作是y1=y1-y1,于是y1没有非负限制,关系(2)的说明完毕。对偶定理:对偶定理:若互为对偶问题的线性规划问题(I)和(II)中有一个最优解,则另一个必有最优解,且目标函数值相同。第34页,共68页,编辑于2022年,星

19、期一例5-5(生产决策问题)某工厂可以用A,B两种原料生产I,II,III三种产品,每种产品需要同时用两种原料,有关数据如下表(单位消耗与资源限制):产品产品I产品产品II产品产品III现有原料现有原料/t原料A2127原料B13211单位产品利润/万元231求:(1)若目前市场上原料A的实际价格为0.5万元/t,工厂应如何决策?(2)若目前市场上原料B的实际价格为0.8万元/t,工厂应如何决策?解:建立模型,设x1,x2,x3分别表示I,II,III的生产量,则模型如下:对偶问题第35页,共68页,编辑于2022年,星期一模型讨论:若把y1,y2当作原料A,B的定价,用两个单位的A,1个单位

20、的B,若生产产品I只能赚2万元,现在考虑把资源拿到市场上卖,定价y1,y2,使得2y1+y22,也就是一定比生产产品I赚得多。产品II,III同理。亦即对偶问题的约束条件保证了资源直接在市场上出售一定不会比生产产品获得的利润低,另一方面,为了增强出售资源的市场竞争力,定价希望低一些,定价的目标是在比生产产品获得更多利润的前提下的最小利润,这个定价模型就是对偶问题。如果把资源A的量由7增加到8,会导致什么结果呢?影子价格:在最有情况下,y1的值就是资源A的影子价格,所以要把影子价格与资源A的市场价格做比较,如果影子价格大于市场价格,考虑出售部分资源以获得更大利润,否则,则从市场买进该资源。第36

21、页,共68页,编辑于2022年,星期一影影子子价价格格的的经经济济意意义义:在资源得到最优配置,使总效益最大时,该资源投入量每增加一个单位所带来总收益的增加量。影子价格是一种静态的资源最优配置价格,不能表现资源在不同时期动态配置时的最优价格,只反映某种资源的稀缺程度和资源与总体积极效益之间的关系,不能代替资源本身的价值。程序编写:执行结果如下:第37页,共68页,编辑于2022年,星期一说明:从红框部分知道,A的影子的价格为0.6,B的影子价格为0.8,松弛变量的值都是0,说明约束是紧约束(约束取等号),即资源没有剩余,影子价格有意义必须是紧约束。影子价格是对应最优基来说的,如果约束的改变使得

22、最优基发生改变,当前的影子价格也就没有任何意义了。通过对右端项的灵敏性分析:第38页,共68页,编辑于2022年,星期一在最优基不变时,A,B的右端项变化范围分别为(4.67,22)和(3.5,21)对问题(1)0.50.6,应该售出部分原料将使利润更大,最大售出量为3.33t,利润将会增加(0.8-0.6)*3.33=0.66万元第39页,共68页,编辑于2022年,星期一例5-6(奶制品的加工问题)1桶牛奶3公斤A112小时8小时4公斤A2或获利24元/公斤获利16元/公斤50桶牛奶时间480小时至多加工100公斤A1制订生产计划,使每天获利最大(1)35元可买到1桶牛奶,买吗?若买,每天

23、最多买多少?(2)可聘用临时工人,付出的工资最多是每小时几元?(3)A1的获利增加到30元/公斤,应否改变生产计划?每天:第40页,共68页,编辑于2022年,星期一1桶牛奶3公斤A112小时8小时4公斤A2或获利24元/公斤获利16元/公斤x1桶牛奶生产A1x2桶牛奶生产A2获利243x1获利164 x2原料供应劳动时间加工能力决策变量 目标函数 每天获利约束条件非负约束线性规划模型(LP)时间480小时至多加工100公斤A150桶牛奶每天第41页,共68页,编辑于2022年,星期一max72x1+64x2st2)x1+x2503)12x1+8x24804)3x1100endOBJECTIV

24、EFUNCTIONVALUE1)3360.000VARIABLEVALUEREDUCEDCOSTX120.0000000.000000X230.0000000.000000ROWSLACKORSURPLUSDUALPRICES2)0.00000048.0000003)0.0000002.0000004)40.0000000.000000NO.ITERATIONS=220桶牛奶生产A1,30桶生产A2,利润3360元。模型求解 第42页,共68页,编辑于2022年,星期一模型求解 reducedcost值表示当该非基变量增加一个单位时(其他非基变量保持不变)目标函数减少的量(对max型问题)OB

25、JECTIVEFUNCTIONVALUE1)3360.000VARIABLEVALUEREDUCEDCOSTX120.0000000.000000X230.0000000.000000ROWSLACKORSURPLUSDUALPRICES2)0.00000048.0000003)0.0000002.0000004)40.0000000.000000NO.ITERATIONS=2也可理解为:为了使该非基变量变成基变量,目标函数中对应系数应增加的量第43页,共68页,编辑于2022年,星期一OBJECTIVEFUNCTIONVALUE1)3360.000VARIABLEVALUEREDUCEDCO

26、STX120.0000000.000000X230.0000000.000000ROWSLACKORSURPLUSDUALPRICES2)0.00000048.0000003)0.0000002.0000004)40.0000000.000000原料无剩余时间无剩余加工能力剩余40max72x1+64x2st2)x1+x2503)12x1+8x24804)3x1100end三种资源“资源”剩余为零的约束为紧约束(有效约束)结果解释 第44页,共68页,编辑于2022年,星期一OBJECTIVEFUNCTIONVALUE1)3360.000VARIABLEVALUEREDUCEDCOSTX120

27、.0000000.000000X230.0000000.000000ROWSLACKORSURPLUSDUALPRICES2)0.00000048.0000003)0.0000002.0000004)40.0000000.000000结果解释 最优解下“资源”增加1单位时“效益”的增量时间加1单位,利润增2影子价格35元可买到1桶牛奶,要买吗?3548,应该买!聘用临时工人付出的工资最多每小时几元?2元!第45页,共68页,编辑于2022年,星期一RANGESINWHICHTHEBASISISUNCHANGED:OBJCOEFFICIENTRANGESVARIABLECURRENTALLOWA

28、BLEALLOWABLECOEFINCREASEDECREASEX172.00000024.0000008.000000X264.0000008.00000016.000000RIGHTHANDSIDERANGESROWCURRENTALLOWABLEALLOWABLERHSINCREASEDECREASE250.00000010.0000006.6666673480.00000053.33333280.0000004100.000000INFINITY40.000000最优解不变时目标系数允许变化范围DORANGE(SENSITIVITY)ANALYSIS?Yesx1系数范围(64,96)x

29、2系数范围(48,72)A1获利增加到30元/千克,应否改变生产计划x1系数由243=72增加为303=90,在允许范围内不变!(约束条件不变)结果解释 第46页,共68页,编辑于2022年,星期一结果解释 RANGESINWHICHTHEBASISISUNCHANGED:OBJCOEFFICIENTRANGESVARIABLECURRENTALLOWABLEALLOWABLECOEFINCREASEDECREASEX172.00000024.0000008.000000X264.0000008.00000016.000000RIGHTHANDSIDERANGESROWCURRENTALLOW

30、ABLEALLOWABLERHSINCREASEDECREASE250.00000010.0000006.6666673480.00000053.33333280.0000004100.000000INFINITY40.000000影子价格有意义时约束右端的允许变化范围原料最多增加10时间最多增加5335元可买到1桶牛奶,每天最多买多少?最多买10桶?(目标函数不变)注意:充分但可能不必要第47页,共68页,编辑于2022年,星期一5.3整数线性规划例5-7(下料问题)做100套钢架,用长为2.9m,2.1m,1.5m的元钢各一根,已知原料长为7.4m,问如何下料,所用最省?问题分析:每一种下

31、料方式用了多少根钢材,合理的下料方式是剩余料头的长度不能超过最短原料需求(1.5m),可首先利用lingo搜索出全部的下料方式,然后从中筛选出符合条件的方式:模型建立:设xi为按第i种方式下料的根数,i=1,8,建立如下模型:x1x8第48页,共68页,编辑于2022年,星期一说明:(1)目标函数有两种取法,一是剩余的料最少,二是所用原料的根数最少。(2)决策变量限制取整数。(3)这种全方式设变量的模型只适合小型下料问题,大型下料问题或者对下料方式有限制的问题将不再合适。程序编写:第49页,共68页,编辑于2022年,星期一补充例5-7(下料问题2)问题1.如何下料最节省?问题2.客户增加需求

32、:原料钢管:每根19米 4米50根 6米20根 8米15根 客户需求节省的标准是什么?由于采用不同切割模式太多,会增加生产和管理成本,规定切割模式不能超过3种。如何下料最节省?5米10根 第50页,共68页,编辑于2022年,星期一按照客户需要在一根原料钢管上安排切割的一种组合。切割模式切割模式余料1米 4米1根 6米1根 8米1根余料3米4米1根6米1根6米1根合理切割模式的余料应小于客户需要钢管的最小尺寸余料3米8米1根8米1根下料问题 第51页,共68页,编辑于2022年,星期一为满足客户需要,按照哪些种合理模式,每种模式切割多少根原料钢管,最为节省?合理切割模式合理切割模式2.所用原料

33、钢管总根数最少模式4米钢管根数6米钢管根数8米钢管根数余料(米)14003231013201341203511116030170023下料问题1 两种标准1.原料钢管剩余总余量最小第52页,共68页,编辑于2022年,星期一xi 按第i 种模式切割的原料钢管根数(i=1,2,7)约束满足需求 决策变量 目标1(总余量)按模式2切割12根,按模式5切割15根,余料27米模式4米根数6米根数8米根数余料14003231013201341203511116030170023需求502015最优解:x2=12,x5=15,其余为0;最优值:27整数约束:xi 为整数第53页,共68页,编辑于2022年

34、,星期一当余料没有用处时,通常以总根数最少为目标 目标2(总根数)下料问题1 约束条件不变 最优解:x2=15,x5=5,x7=5,其余为0;最优值:25。xi 为整数按模式2切割15根,按模式5切割5根,按模式7切割5根,共25根,余料35米虽余料增加8米,但减少了2根与目标1的结果“共切割27根,余料27米”相比第54页,共68页,编辑于2022年,星期一下料问题2对大规模问题,用模型的约束条件界定合理模式增加一种需求:5米10根;切割模式不超过3种。现有4种需求:4米50根,5米10根,6米20根,8米15根,用枚举法确定合理切割模式,过于复杂。决策变量xi 按第i 种模式切割的原料钢管

35、根数(i=1,2,3)r1i,r2i,r3i,r4i 第i 种切割模式下,每根原料钢管生产4米、5米、6米和8米长的钢管的数量第55页,共68页,编辑于2022年,星期一满足需求模式合理:每根余料不超过3米整数非线性规划模型下料问题2目标函数(总根数)约束条件整数约束:xi,r1i,r2i,r3i,r4i(i=1,2,3)为整数第56页,共68页,编辑于2022年,星期一增加约束,缩小可行域,便于求解原料钢管总根数下界:特殊生产计划:对每根原料钢管模式1:切割成4根4米钢管,需13根;模式2:切割成1根5米和2根6米钢管,需10根;模式3:切割成2根8米钢管,需8根。原料钢管总根数上界:31模

36、式排列顺序可任定下料问题2需求:4米50根,5米10根,6米20根,8米15根每根原料钢管长19米第57页,共68页,编辑于2022年,星期一LINGO求解整数非线性规划模型Localoptimalsolutionfoundatiteration:12211Objectivevalue:28.00000VariableValueReducedCostX110.000000.000000X210.000002.000000X38.0000001.000000R113.0000000.000000R122.0000000.000000R130.0000000.000000R210.0000000.

37、000000R221.0000000.000000R230.0000000.000000R311.0000000.000000R321.0000000.000000R330.0000000.000000R410.0000000.000000R420.0000000.000000R432.0000000.000000模式1:每根原料钢管切割成3根4米和1根6米钢管,共10根;模式2:每根原料钢管切割成2根4米、1根5米和1根6米钢管,共10根;模式3:每根原料钢管切割成2根8米钢管,共8根。原料钢管总根数为28根。第58页,共68页,编辑于2022年,星期一例5-8(选址问题)A,B,C三个区,

38、7个位置M1,M7,约束:(1)在A区从M1,M2,M3中选择至多两个;(2)在B区从M4,M5中选择至少一个;(3)在C区,从M6,M7中选择至少一个。已知,M1.M7分别投资为200,300,350,250,350,200,400,预计每年获利50,80,12-,70,100,60,120,总资金1200,问如何建立?模型分析:典型的0-1规划问题,设选择M1,M7的投资分别为bi万元,每年获利ci万元,总资金b万元,设0-1变量xi(i=1,7)为:1(选择)或0(不选择)建立模型:第59页,共68页,编辑于2022年,星期一第60页,共68页,编辑于2022年,星期一例5-9(拍卖与投

39、标)5类艺术品拍卖,来自4个投标人的投标书,投标价格如下表,假定每个投标人对每类艺术品只能购买一件每类艺术品只能购买一件,每个投标人对每类艺术品最多只能购进一件,每个投标人竞购总数不能超过3件,则哪些艺术品能卖出去?卖给谁?每类物品的清算价格是多少?招标项目类型招标项目类型12345招标项目数量12334投标价格投标人192863投标人267915投标人378634投标人454321问题分析:供应能力与需求能力达到平衡时的产品的价格称为清算价格,清算价格pi满足如下条件:第61页,共68页,编辑于2022年,星期一(1)不超过物品数量的限制;(2)报价低于pj的将不能获得物品;(3)物品没有全

40、部卖出,可认为清算价格为0,除非拍卖方指定最低保护价;(4)报价高于pj的投标人有权获得物品,如果他有权获得的物品超过三件,假设他总是希望自己的满意度(报价与清算价之差来衡量)最大模型建立:设有N类物品要拍卖,第j类的物品数量Sj(j=1,N),有M个投标者,投标者i(i=1,M)对第j类物品的投标价格为bij,投标者购买点额总件数不能超过Tj,用0-1变量xij表示是否分配一件第j类物品给投标者i,xij=1(分配)或0(不分配)第62页,共68页,编辑于2022年,星期一程序编写:第63页,共68页,编辑于2022年,星期一说明:(1)从Excel中读取数据有两种方式,一种是根据Excel

41、表格中指定的名称与Lingo程序中设定的名称一致来读取,另一种是采用指定位置的读取数据。(2)Excel区域命名的方法(3)Excel文件的位置需要指定文件的具体路径求解结果为:第64页,共68页,编辑于2022年,星期一例5-10(面试顺序问题)4名同学到一家公司参加3个阶段的面试,要经过初试-复试-面试,不允许插队,面试时间如下表所示:姓名姓名初试初试复试复试面试面试131520乙102018丙201610丁810154名同学约定他们全部面试完以后一起离开公司,假定现在时间是早上8点,请问他们最早何时离开。模型建立:记tij为第i名同学参加第j阶段面试需要的时间,xij表示第i名同学参加第j阶段面试的开始时刻(为了方便,记早上8点为0时刻)(i=1,.,4,j=1,.,3),T为完成全部面试的最少时间,则优化目标为:第65页,共68页,编辑于2022年,星期一个人时间的先后次序约束:同阶段不同同学时间不相容(同阶段靠前同学的完成时间小于靠后同学的开始时间):不妨给定i,k的关系为ik。目标可写为如下线性优化:第66页,共68页,编辑于2022年,星期一程序编写:第67页,共68页,编辑于2022年,星期一计算结果:第68页,共68页,编辑于2022年,星期一

展开阅读全文
相关资源
相关搜索

当前位置:首页 > 教育专区 > 大学资料

本站为文档C TO C交易模式,本站只提供存储空间、用户上传的文档直接被用户下载,本站只是中间服务平台,本站所有文档下载所得的收益归上传人(含作者)所有。本站仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私,请立即通知淘文阁网,我们立即给予删除!客服QQ:136780468 微信:18945177775 电话:18904686070

工信部备案号:黑ICP备15003705号© 2020-2023 www.taowenge.com 淘文阁