数学规划模型参考培训课件.ppt

1、第四章第四章 数学规划模型数学规划模型一、数学规划模型一、数学规划模型 1.模型的建立模型的建立 问题问题1 某厂利用甲某厂利用甲,乙乙,丙丙,丁四种设备生产丁四种设备生产A,B,C三种三种产品产品,相关数据如表所示相关数据如表所示.已知这三种产品的单件利润已知这三种产品的单件利润分别是分别是4.5,5,7（百元）（百元）,试问该厂应如何安排生产可获试问该厂应如何安排生产可获得最大利润得最大利润?ABC总工时总工时甲甲224800乙乙123650丙丙423850丁丁242700甲甲123224800.xxx乙乙12323650.xxx丙丙123423850.xxx丁丁123242700.xxx

2、注意到变量注意到变量 代表的是产品的产量代表的是产品的产量,故有故有抽去所给问题的具体意义抽去所给问题的具体意义,我们得到原问题的数学关系我们得到原问题的数学关系为为123,x xx0.ix 分析分析 该问题的关键所在是确定每种产品的产量该问题的关键所在是确定每种产品的产量,为此以为此以 表示三种产品的产量表示三种产品的产量,则目标为则目标为1,x23,xx123Max 4.557.zxxx 在一个生产周期中在一个生产周期中,每种设备所提供的工时为有限的每种设备所提供的工时为有限的,故对四种设备而言还应该满足下列条件故对四种设备而言还应该满足下列条件:123Max 4.557.zxxx1231

3、23123123224800,23650,423850,242700.xxxxxxxxxxxx.st非负性非负性0,1,2,3.ixi用用Lingo软件可以得到相应问题的解软件可以得到相应问题的解.启动启动Lingo,在窗在窗口下中输入下列程序口下中输入下列程序:max4.5*1 5*27*3;2*12*24 3800;1*12*23 3650;4*12*24 3850;2*14*22 3700;Endxxxxxxxxxxxxxxx保存完之后执行保存完之后执行Lingo菜单下的菜单下的Solve命令命令,得到相应的解得到相应的解.Variable Value Reduced Cost X1 8

4、5.71429 0.000000 X2 71.42857 0.000000 X3 121.4286 0.000000 Row Slack or Surplus Dual Price 1 1592.857 1.000000 2 0.000000 1.357143 3 57.14286 0.000000 4 0.000000 0.2142857 5 0.000000 0.4642857 问题问题2 某车间要制造某车间要制造100套钢筋架套钢筋架,每套需要长为每套需要长为2.9 2.1 1.5 的钢筋各一根的钢筋各一根.已知原料钢筋长度为已知原料钢筋长度为7.4 问如何切割钢筋问如何切割钢筋,使得钢

5、筋的利用率为最高使得钢筋的利用率为最高?,mm.m分析分析 该问题的要点是如何切割钢筋该问题的要点是如何切割钢筋,使得每次切割之使得每次切割之后后,剩下的余料为最少剩下的余料为最少?假设在切割过程中假设在切割过程中,我们不考虑钢筋的损耗我们不考虑钢筋的损耗,并考虑各并考虑各种切割方案种切割方案:方案方案2.92.11.5余料余料1103022010.130220.241200.350130.812434512352100,22100,323100.xxxxxxxxxx.st非负性非负性0,1,2,5.ixi 从分析中可以看出从分析中可以看出,此问题的关键是确定每种方案下此问题的关键是确定每种方

6、案下的余料数的余料数.设设 表示第表示第 种方案中使用的原料钢种方案中使用的原料钢筋数筋数,则余料数为则余料数为1,2,5ix i i23450.10.20.30.8.zxxxx而相应的限制条件为而相应的限制条件为 故原问题的数学关系式为故原问题的数学关系式为2345min 0.10.20.30.8.zxxxx12434512352100,22100,323100.xxxxxxxxxx.st非负性非负性0,1,2,5.ixi在在Lingo下得到该问题的解为下得到该问题的解为min 0.1*20.2*30.3*40.8*5;12*24100;2*32*45100;3*122*33*5100;En

7、dxxxxxxxxxxxxxx运行后得到该问题的解为运行后得到该问题的解为 X2 25.00000 0.000000 X3 0.000000 0.3666667 X4 25.00000 0.000000 X5 0.000000 1.283333 X1 25.00000 0.000000 线性规划的模型一般可表示为线性规划的模型一般可表示为1 122max .nnzc xc xc x11 11221121 1222221 122,.nnnnmmmnnma xa xa xba xa xa xba xaxaxb.st非负性非负性0,1,2,.ixin 注注 线性规划的目标函数还可以用线性规划的目标函

8、数还可以用min来表示来表示,表示表示追求目标函数的最小值追求目标函数的最小值.而而 表示约束条件表示约束条件:（Subject to）.st 问题问题3 要从甲地调出物质要从甲地调出物质2000吨吨,从乙地调出物质从乙地调出物质1100吨吨,分别供给分别供给 地地1700吨吨,地地11吨吨,地地200吨和吨和 100吨吨,已知每吨运费如表所示已知每吨运费如表所示,试建立一个使运费达到试建立一个使运费达到最小的调拨计划最小的调拨计划.ABCD单位路程运费表单位路程运费表销地销地15375151乙乙1572521甲甲DCBA产地产地 分析分析 设从第设从第 个产地到第个产地到第 个销地的运输量为

9、个销地的运输量为 运运输成本为输成本为 则问题的目标函数为则问题的目标函数为ij,ijx,ijc111213142125715zxxxx2122232451513715,xxxx由于从第一个产地调出的物质的总和为第一个产地的产由于从第一个产地调出的物质的总和为第一个产地的产量量,即有即有111213142000,xxxx同理同理,有有212223241100.xxxx对称地对称地,对销地而言对销地而言,有关系有关系11211700,xx12221100,xx1323200,xx1441100.xx由此得到该问题的数学模型由此得到该问题的数学模型11121314min 2125715zxxxx2

10、122232451513715,xxxx111213142122232411211222132314412000,1100.1700,1100,200,100.xxxxxxxxxxxxxxxx.st0.ijx 注注 该问题又称为运输问题该问题又称为运输问题.运输问题的一般形式可写运输问题的一般形式可写成成min ,ijijzc x11,mijiinijjjxaxb.st0.ijx 其中其中 是第是第 个产地的产量个产地的产量,是第是第 个销地的需求量个销地的需求量.iaijbj在上面的关系中在上面的关系中,有有11.mnijijab相应的运输问题称为产销平衡的运输问题相应的运输问题称为产销平衡

11、的运输问题.若产销不平若产销不平衡衡,应该如何处理应该如何处理?为什么总是假定产销是平衡的为什么总是假定产销是平衡的.问题问题4 随机规划模型随机规划模型 决策者要建造一座水库决策者要建造一座水库,使水库的容量使水库的容量 在满足给定在满足给定的限制条件下达到最小的限制条件下达到最小,以使其造价最小以使其造价最小.C 分析分析 1.在一年中的第在一年中的第 个季节水库应留出一定的容量个季节水库应留出一定的容量 以保证洪水的注入以保证洪水的注入.由于洪水量是一个变数由于洪水量是一个变数,故假定故假定以较大的概率以较大的概率 使得使得i,iv,i1,1,2,3,4.iiP Csvi其中其中 为第为

12、第 个季节的储水量个季节的储水量.isi 2.为保证灌溉为保证灌溉,发电发电,航运等用水供应航运等用水供应,水库在每个季水库在每个季节应能保证一定的放水量节应能保证一定的放水量 考虑到这仍然是一随机因考虑到这仍然是一随机因数数,要求满足满足这一条件的概率不小于要求满足满足这一条件的概率不小于 即即,iq2,2,1,2,3,4.iiP xqi其中其中 为第为第 个季节的可放水量个季节的可放水量.ixi3,1,2,3,4.imP xxi 3.为保证水库的安全和水生放养为保证水库的安全和水生放养,水库还应有一定的水库还应有一定的储水量储水量 即即,mx由此得到相应问题的数学模型为由此得到相应问题的数

13、学模型为:min C123,0,1,2,3,4.iiiiimiiP CsvP xqP xxx si.st 问题问题5 某公司准备派某公司准备派 个工人个工人 去完成去完成项工作项工作 已知第已知第 个工人完成第个工人完成第 工作的效工作的效率为率为 求如此的一个指派方案求如此的一个指派方案,使工人完成这些工作使工人完成这些工作的效率为最大的效率为最大.n12,nx xxn12,.ny yyij,ijwxy11w12wnnw 该问题可用一个网络图该问题可用一个网络图 来表示来表示:其中其中 表表示顶点集示顶点集,是边集是边集,是权集是权集.该问题即是从该问题即是从 的每一个顶点的每一个顶点,找出

14、唯一的一条到找出唯一的一条到 的某一个的某一个 的边的边,使得权之和为最大使得权之和为最大.,x y e w,x yewxy 模型建立模型建立 若以若以 表示在顶点表示在顶点 存在边存在边,否则否则则目标函数可表示为则目标函数可表示为 1ijz,ijx y0.ijz,1,nijiji jzw z而从而从 的每一个顶点的每一个顶点 只能作一条边等价于只能作一条边等价于xix11.nijjz同样同样,连连 惟一的一条边等价于惟一的一条边等价于jy11.nijiz由此得到相应的数学模型为由此得到相应的数学模型为,1max ,nijiji jzw z111,1,2,1.1,2,.01.nijjniji

15、ijijzinzjnzz.st这样的规划又称为这样的规划又称为0-1规划规划.注注1 很多实际问题都可以转化成这样的模型很多实际问题都可以转化成这样的模型.例如游泳例如游泳接力队员的选拔接力队员的选拔.注注2 当人数和工作数不相同时当人数和工作数不相同时,这样的问题应该如何求这样的问题应该如何求解解,又当又当 时时,并且容许一个人能完成两件工作并且容许一个人能完成两件工作,又该如何解决又该如何解决?1nm二、模型的求解二、模型的求解例例1 一奶制品加工厂用牛奶生产一奶制品加工厂用牛奶生产 两种奶制品两种奶制品,1桶牛奶可以在设备甲上用桶牛奶可以在设备甲上用12小时加工生产小时加工生产3公斤公斤

16、 或或则在设备乙上用则在设备乙上用8小时加工成小时加工成4公斤公斤 根据市场需要根据市场需要,生产的生产的 全部能售出全部能售出,且每公斤且每公斤 获利获利24元元,每公每公斤斤 可获利可获利16元元.现在加工厂每天能得到现在加工厂每天能得到50桶牛奶的供桶牛奶的供应应,每天工人总的劳动时间为每天工人总的劳动时间为480小时小时,并且设备甲每天并且设备甲每天至多能加工至多能加工100公斤公斤 设备乙的加工能力没有限制设备乙的加工能力没有限制.试试为该厂制定一个生产计划为该厂制定一个生产计划,使每天获利最大使每天获利最大,并进一步并进一步讨论以下讨论以下3个附加问题个附加问题:12,A A1,A

17、2.A12,A A1A2A1,A 若用若用35元可以买到元可以买到1桶牛奶桶牛奶,应否作这项投资应否作这项投资?若投若投资资,每天最多购买多少桶牛奶每天最多购买多少桶牛奶?若可以聘用临时工人以增加劳动时间若可以聘用临时工人以增加劳动时间,付给临时工付给临时工人的工资最多是每小时几元人的工资最多是每小时几元?由于市场需求变化由于市场需求变化,每公斤每公斤 的利润增加到的利润增加到30元元,应否改变生产计划应否改变生产计划?1A解解 设设 表示这两种产品每天所消耗牛奶的数量表示这两种产品每天所消耗牛奶的数量（单位：桶）（单位：桶）.则用于生产则用于生产 的牛奶可获利的牛奶可获利用于生产用于生产 的

18、牛奶可获利的牛奶可获利 则目标函数为则目标函数为12,x x1A13 24,x2A24 16,x127264.zxx限制条件分别为限制条件分别为:对原料的限制对原料的限制:1250,xx劳动力的限制劳动力的限制12128480,xx设备甲的开工限制设备甲的开工限制13100.x 由此得到相应的规划模型由此得到相应的规划模型12max 7264zxx1212150,128480,3100,xxxxx.st12,0.x x 对每一约束条件对每一约束条件,在第一象限中确定坐标点的范围在第一象限中确定坐标点的范围,最最终确定解的范围终确定解的范围可行域（多边形区域）可行域（多边形区域）;模型求解模型求

19、解 解法解法1 （图解法）（图解法）确定等值线（图中用虚线），则最优解为可行域与确定等值线（图中用虚线），则最优解为可行域与等值线的最后交点（即图中点的等值线的最后交点（即图中点的 坐标）即为所求问坐标）即为所求问题的最优解题的最优解.B112:50Lxx31:3100Lx 2020404060601x2x212:128480LxxABCD1272641440 xx 为此求解方程为此求解方程121250,128480.xxxx容易得到该方程的解为容易得到该方程的解为20,30.TX 解法解法2 （单纯形方法）（单纯形方法）原规划的标准型为原规划的标准型为12max 7264zxx1231241

20、550,128480,3100.xxxxxxxx.st0,1,2,5.ixi 12345345341726400001110050128010480300011007264000001101/350/3080148010001/3100/306400242400 xxxxxxcxxxxxx3215210011/81/320/30101/81/21010001/3100/30008830400063/41400131/40301021/40200048203360 xxxxxx 解法解法3 （利用计算机软件）（利用计算机软件）在软件在软件Lingo8下进行求解下进行求解:输入命令输入命令MODE

21、L:MAX72*164*2;1250;12*18*2480;3*1100;ENDxxxxxxx Variable Value Reduced Cost X1 20.00000 0.000000 X2 30.00000 0.000000 Row Slack or Surplus Dual Price 1 3360.000 1.000000 2 0.000000 48.00000 3 0.000000 2.000000 4 40.00000 0.000000得到的解为得到的解为 结果分析结果分析 三个约束条件的右端视为三个约束条件的右端视为“资源资源”:原料原料,劳动时间劳动时间,设备甲的加工能力

22、设备甲的加工能力.对当前解而言对当前解而言,前两种前两种“消耗殆尽消耗殆尽”，而设备甲尚余而设备甲尚余40公斤的加工能力公斤的加工能力.目标函数可以看作为是目标函数可以看作为是“效益效益”.成为紧约束的资成为紧约束的资源源一旦增加一旦增加,则则“效益效益”必然增加必然增加.解中列出的解中列出的“对偶对偶”价价格表格表示紧约束示紧约束“资源资源”每增加一个单位后相应每增加一个单位后相应“效益效益”的增的增加值加值.原料每增加一个单位原料每增加一个单位,利润可增加利润可增加48个单位个单位;而劳动时间而劳动时间每增加一个单位每增加一个单位,利润可增加利润可增加2个单位个单位.而非紧约束资源而非紧约

23、束资源的增加的增加,不会带来相应的收益不会带来相应的收益.这种这种“资源资源”潜在价值潜在价值被被称为称为“影子影子”价格价格.用用“影子影子”价格即可回答附加问题价格即可回答附加问题.用用35元购买一桶牛奶元购买一桶牛奶,低于牛奶的影子价格低于牛奶的影子价格,故可以故可以做这项投资做这项投资;临时工人每小时的工资不超过临时工人每小时的工资不超过2元元.而设而设 备甲尚有富裕能力备甲尚有富裕能力,故增加工时不会产生效益故增加工时不会产生效益.112:50Lxx31:3100Lx 2020404060601x2x212:128480LxxABCD1272641440 xx198k 234k 目标

24、函数的系数发生变化对最优解和最优值的影响目标函数的系数发生变化对最优解和最优值的影响.在图解法中可以看到，价值系数在图解法中可以看到，价值系数 对最优解会产对最优解会产生一定的影响生一定的影响.因为因为 确定了等值线的斜率确定了等值线的斜率,原问题原问题等值线的斜率为等值线的斜率为 ,当斜率上升到当斜率上升到 则则最优解将会改变最优解将会改变,此时最优解将在此时最优解将在 点取得点取得.12,c c12,c c19,8k 23,4k C 灵敏度分析还给出了各个系数的范围灵敏度分析还给出了各个系数的范围:的上界为的上界为24,下界为下界为8,即当即当 时时,最优最优解不变解不变;同样当同样当 时

25、时,最优解不变最优解不变.1c1728,722464,96c 248,72c 112:50Lxx31:3100Lx 2020404060601x2x212:128480LxxABCD1272641440 xx198k 234k 从图中还可以看出从图中还可以看出,原原料（牛奶）的增加料（牛奶）的增加,对应对应的是直线的是直线 的向右的的向右的平移平移,此时最优解仍此时最优解仍为点为点 但当但当 与与 重合重合时时,最优解将不再改变最优解将不再改变,1L,BBA112:50Lxx31:3100Lx 2020404060601x2x212:128480LxxABCD1272641440 xx此时此时

26、,而由而由“影子影子”价格知价格知:原料每增加一原料每增加一个个单位利润将增加单位利润将增加48个单位个单位.此时总利润为此时总利润为 1260.xx33604803840.同样同样,当劳动力资源当劳动力资源增加时增加时,即直线即直线 向向右移动时右移动时,最优解也最优解也将改变将改变,但当但当 两两点重合时点重合时,最优解将最优解将不再改变不再改变.由由“影子影子”2L,B C价格价格,劳动力每增加一个工时劳动力每增加一个工时,效益增加效益增加2个单位个单位.但劳但劳动力最多增加动力最多增加53个单位个单位.因设备甲仍有富余工时因设备甲仍有富余工时,因而设备的加工能力无需再因而设备的加工能力

27、无需再增加增加,其其“影子影子”价格为零价格为零.根据上面的分析根据上面的分析,可以回答原问题中提出的相关问题可以回答原问题中提出的相关问题.可以批准用每桶可以批准用每桶35元的价格再购买部分牛奶元的价格再购买部分牛奶,但最但最多再购买多再购买10桶桶;可以以用低于每小时可以以用低于每小时2元的工资聘用临时工人以增元的工资聘用临时工人以增劳动时间劳动时间,但最多不得超过但最多不得超过53小时小时.例例2 奶制品的销售计划奶制品的销售计划 例例1给出的给出的 两种奶制品的生产条件两种奶制品的生产条件,利润及工厂利润及工厂的资源限制不变的资源限制不变,为增加工厂的获利为增加工厂的获利,开发了奶制品

28、的深开发了奶制品的深加工技术加工技术:用用2小时和小时和3元加工费元加工费,可将可将1公斤公斤 加工成加工成0.8高级奶制品高级奶制品 也可将一公斤也可将一公斤 加工成加工成0.75公斤高级公斤高级奶制品奶制品 每公斤每公斤 能获利能获利44元元,每公斤每公斤 能获利能获利32元元,试为该厂制定一个生产销售计划试为该厂制定一个生产销售计划,使获得的利润最大使获得的利润最大,并讨论以下问题并讨论以下问题:12,A A1A1,B2A2,B1B2B 若投资若投资32元可以增加供应一桶牛奶元可以增加供应一桶牛奶,投资投资3元可以增元可以增加一小时劳动时间加一小时劳动时间,应否作这样的投资应否作这样的投

29、资,若每天投资若每天投资150元元,可赚回多少可赚回多少?每公斤高级奶制品每公斤高级奶制品 的获利经常有的获利经常有10%的波动的波动,对指定计划有无影响对指定计划有无影响,若每公斤若每公斤 的获利下降的获利下降10%,计计划应该改变吗划应该改变吗?12,B B1B 问题分析问题分析 要求指定生产计划要求指定生产计划,关键是确定各产品的产量关键是确定各产品的产量,而目而目标函数为销售这些产品之后可获得的利润标函数为销售这些产品之后可获得的利润.建立模型建立模型 设每天销售设每天销售 公斤公斤 公斤公斤 公斤公斤 公斤公斤 用用 公斤公斤 加工加工 公斤公斤 加工加工1x2x1,A2,A3x2A

30、14,B x2,B5x16,B x1A2.B 目标函数目标函数123456max 2416443233,zxxxxxx 约束条件约束条件 原料供应原料供应 每天生产每天生产 公斤公斤,用牛奶用牛奶 桶桶,每天生产每天生产 公斤公斤,用牛奶用牛奶 桶桶,两者之和不超过两者之和不超过50桶桶;1A15xx15/3xx2A26xx26/4xx 劳动时间劳动时间 每天生产每天生产 的时间分别为的时间分别为 加工加工 的时间分别为的时间分别为 两两者之和不超过者之和不超过480小时小时;12,A A154,xx262,xx12BB562,2,xx 设备能力设备能力 的产量的产量 不得超过设备甲每天的不得

31、超过设备甲每天的 1A15xx加工能力加工能力100公斤公斤;非负约束非负约束 126,0;x xx 附加约束附加约束 1公斤公斤 加工成加工成 公斤公斤 即即同样同样1A1,B350.8,xx460.75.xx0.8 由此得到模型由此得到模型123456max 2416443233zxxxxxx1526152656153546503442224801000.80.75xxxxxxxxxxxxxxxx.st126,0;x xx 模型求解模型求解 用用Lingo软件软件,进行求解进行求解,得得 Variable Value Reduced Cost X1 0.000000 1.680000 X2

32、 168.0000 0.000000 X3 19.20000 0.000000 X4 0.000000 0.000000 X5 24.00000 0.000000 X6 0.000000 1.520000 Row Slack or Surplus Dual Price 1 3460.800 1.000000 2 0.000000 3.160000 3 0.000000 3.260000 4 76.00000 0.000000 5 0.000000 44.00000 6 0.000000 32.00000Ranges in which the basis is unchanged:Objecti

33、ve Coefficient Ranges Current Allowable Variable Coefficient Increase Decrease X1 24.00000 1.680000 INFINITY X2 16.00000 8.150000 2.100000 X3 44.00000 19.75000 3.166667 X4 32.00000 2.026667 INFINITY X5 -3.000000 15.80000 2.533333 X6 -3.000000 1.520000 INFINITY 结果分析结果分析 由输出的结果知由输出的结果知,约束约束2和和3的的“影子影子

34、”价格分别是价格分别是 和和 即每增加一桶牛奶可使净利润增加即每增加一桶牛奶可使净利润增加 3.163.26,3.16 1237.92 .元元增加增加1小时劳动时间小时劳动时间,可是利润增加可是利润增加 元元,所以应该所以应该投资投资 元增加一桶牛奶或投资元增加一桶牛奶或投资3元增加一小时劳动时元增加一小时劳动时间间.若每天投资若每天投资 元元,增加供应增加供应5桶牛奶桶牛奶,可获利可获利3.2613015037.925189.6 .元元但约束但约束2的增加值最多不超过的增加值最多不超过120,意味牛奶的桶数最多意味牛奶的桶数最多不超过不超过10桶桶.在灵敏度分析的报告中在灵敏度分析的报告中,

35、目标函数系数的变化范围分目标函数系数的变化范围分别为别为1234,25.68,13.9,24.15,443.17,63.75,322.03.xxxx 由此可见由此可见,当当 的价格向下波动的价格向下波动 或或 的价格向的价格向上波动上波动 都会影响到最优解都会影响到最优解.1B10%2B10%,问题的提出问题的提出 钢铁、煤、水电等生产、生活物资从钢铁、煤、水电等生产、生活物资从若干供应点运送到一些需求点，怎样安排运输，使运费若干供应点运送到一些需求点，怎样安排运输，使运费为最小、或者利润为最大为最小、或者利润为最大.某种类型的货物由于需要装某种类型的货物由于需要装箱箱,故要考虑如何搭配使利用

36、率达到最高故要考虑如何搭配使利用率达到最高,诸如此类的诸如此类的问题都牵涉到一些具体的数学模型问题都牵涉到一些具体的数学模型,这目讨论两个问题这目讨论两个问题,并利用相应的数学规划模型加以解决并利用相应的数学规划模型加以解决.三、应用举例三、应用举例 题题1 自来水的输送问题自来水的输送问题 某市有甲、乙、丙、丁四个居民区某市有甲、乙、丙、丁四个居民区,自来水由自来水由三个水库供应三个水库供应,四个区每天必须得到保证的基本用水量四个区每天必须得到保证的基本用水量分别为分别为 千吨千吨,但由于水源紧张但由于水源紧张,三个水库三个水库每天最多只能分别供应每天最多只能分别供应 吨自来水吨自来水,并由

37、于地并由于地区位置的差别区位置的差别,自来水公司从各水库向各区送水所需付自来水公司从各水库向各区送水所需付出的引水管理费不同（见表）出的引水管理费不同（见表）,其它管理费用都是其它管理费用都是 千吨千吨,根据公司规定根据公司规定,各区用户按统一标准各区用户按统一标准 千吨千吨收费收费,此外此外,四个区都向公司申请了额外用水量四个区都向公司申请了额外用水量,分分,A B C30,70,10,1050,60,50450/900/分别为每天分别为每天 千吨千吨,该公司应如何分配供该公司应如何分配供水量水量,才能获利最多才能获利最多?50,70,20,40/管理费管理费甲甲乙乙丙丙丁丁A1601302

38、20170B140130190150C190200230/为了增加供水量为了增加供水量,自来水公司正在考虑进行水库改造自来水公司正在考虑进行水库改造,随三个水库的供水量都提高一倍随三个水库的供水量都提高一倍,问此时供水方案应如问此时供水方案应如何改变何改变?公司利润可增加多少公司利润可增加多少?分析分析 问题的关键是如何安排从各个水库向四个居民区供水问题的关键是如何安排从各个水库向四个居民区供水,使得引水管理费用达到最小使得引水管理费用达到最小,注意到其它费用与供水安注意到其它费用与供水安排无关排无关.模型建立模型建立 设决策变量为设决策变量为 三个水库三个水库 向甲、乙、向甲、乙、丙、丁丙、

39、丁 四个区的供水量四个区的供水量,设水库设水库 向向 区的区的日供水量为日供水量为 并注意到并注意到 由条件得由条件得,A B C1,2,3i 1,2,3,4j ij,ijx340.x1112131421222324313233min 160130220170140130190150190200230.Zxxxxxxxxxxx 由于需求量大于供水量由于需求量大于供水量,需求限制可表示为需求限制可表示为1112131421222324313233112131122232132333142450605030807014010301050.xxxxxxxxxxxxxxxxxxxxxx.st0.ijx

40、 在在Lingo下得到问题的解下得到问题的解.Variable Value Reduced Cost X11 0.000000 30.00000 X12 50.00000 0.000000 X13 0.000000 50.00000 X14 0.000000 20.00000 X21 0.000000 10.00000 X22 50.00000 0.000000 X23 0.000000 20.00000 X24 10.00000 0.000000 X31 40.00000 0.000000 X32 0.000000 10.00000 X33 10.00000 0.000000即即:该问题的解

41、为该问题的解为122224313350,50,10,40,10,xxxxx此时引水管理费为此时引水管理费为 元元,利润为利润为24400144000720002440047600元元.讨论讨论 如果如果 三个水库的每天最大供水量都增加一倍三个水库的每天最大供水量都增加一倍,则公司总供水能力为则公司总供水能力为 千吨千吨,水库供水量超过总需求水库供水量超过总需求量量,故此时需要计算三个水库向甲、乙、丙、丁四个区故此时需要计算三个水库向甲、乙、丙、丁四个区供应每千吨水的净利润，供应每千吨水的净利润，即有表即有表2 ,A B C320净利润净利润甲甲乙乙丙丙丁丁A290320230280B31032

42、0260300C260250220/从水库向各区送水的净利润从水库向各区送水的净利润 由此得到目标函数为由此得到目标函数为1112131421222324313233max 290330230280310320260300260250220.Zxxxxxxxxxxx约束条件为：约束条件为：11121314212223243132331121311222321323331424100120100030807014010301050.xxxxxxxxxxxxxxxxxxxxxx.st0.ijx 在在Lingo下得到问题的解：下得到问题的解：Variable Value Reduced Cost X

43、11 0.000000 25.00000 X12 100.0000 0.000000 X13 0.000000 30.00000 X14 0.000000 20.00000 X21 0.000000 5.000000 X22 40.00000 0.000000 X23 30.00000 0.000000 X24 50.00000 0.000000 X31 80.00000 0.000000 X32 20.00000 0.000000 X33 0.000000 0.000000 Row Slack or Surplus Dual Price 1 93400.00 1.000000 2 0.000

44、000 305.0000 3 0.000000 305.0000 4 0.000000 250.0000 5 0.000000 10.00000 6 0.000000 15.00000 7 0.000000 -45.00000 8 0.000000 -5.000000 题题2 货机装运问题货机装运问题 问题问题 某种货机有三个货舱某种货机有三个货舱:前舱、中舱、后舱前舱、中舱、后舱.三三个货舱所能装载的货物的最大重量和体积都有限制个货舱所能装载的货物的最大重量和体积都有限制,如如表所示表所示,并且为了保持飞机的平衡并且为了保持飞机的平衡,三个货舱中实际装载三个货舱中实际装载货物的重量必须与其最

45、大容许重量成正比货物的重量必须与其最大容许重量成正比.前舱前舱中舱中舱后舱后舱重量限制重量限制10168体积体积680087005300 现有四种货物供该货机本次飞行装运现有四种货物供该货机本次飞行装运,有关信息如表有关信息如表,最后一列表示装运后获得的利润最后一列表示装运后获得的利润.重量重量体积体积利润利润货物货物1184803100货物货物2156503800货物货物3235803500货物货物123902850 假设假设 1.每种货物可以进行任意的分割每种货物可以进行任意的分割;2.每种货物可以在一个或多个货舱中任意分布每种货物可以在一个或多个货舱中任意分布;3.每种货物可以混装每种货

46、物可以混装,并保证不留空隙并保证不留空隙.应如何安排装运应如何安排装运,使该货机本次装运的利润最大使该货机本次装运的利润最大?模型建立模型建立 决策变量决策变量 表示第表示第 种物资装入第种物资装入第 个货舱的重量个货舱的重量,货货舱舱 分别表示前、中、后舱分别表示前、中、后舱.ijxij1,2,3j 目标函数表示一次运送后的总利润目标函数表示一次运送后的总利润,即有即有111213212223313233414243max 3100380035002850.Zxxxxxxxxxxxx 约束条件有如下的约束条件有如下的:总重量约束总重量约束11121321222311121341424318,

47、15,23,12.xxxxxxxxxxxx三个货舱的重量限制三个货舱的重量限制11213141122232421323334310,16,8.xxxxxxxxxxxx三个货舱的空间限制三个货舱的空间限制1121314112223242313233434806505803906800,4806505803908700,4806505803905300.xxxxxxxxxxxx平衡限制平衡限制1121314121223242313233431016.8xxxxxxxxxxxx 模型求解模型求解.在在Lingo下下,可得到模型的解为可得到模型的解为:Variable Value Reduced Co

48、st X11 0.000000 400.0000 X12 0.000000 57.89474 X13 0.000000 400.0000 X21 7.000000 0.000000 X22 0.000000 239.4737 X23 8.000000 0.000000 X31 3.000000 0.000000 Variable Value Reduced Cost X32 12.94737 0.000000 X33 0.000000 0.000000 X41 0.000000 650.0000 X42 3.052632 0.000000 X43 0.000000 650.0000最大利润为最

49、大利润为121515.8z 题题3 汽车生产问题汽车生产问题 一汽车厂生产小、中、大三种类型的汽车一汽车厂生产小、中、大三种类型的汽车,已知各类已知各类型每辆车对钢材、劳动时间的需求型每辆车对钢材、劳动时间的需求,利润以及每月工厂利润以及每月工厂,劳动时间的现有量入表所示劳动时间的现有量入表所示,试指定月生产计划试指定月生产计划,使工使工厂每月的利润最大厂每月的利润最大.小型小型中型中型大型大型现有量现有量钢材钢材1.535600劳动时间劳动时间28025040060000利润利润234 模型的建立模型的建立 设每月生产小、中、大型汽车的数量分别为设每月生产小、中、大型汽车的数量分别为工厂的月

50、利润为工厂的月利润为 假定在生产周期中假定在生产周期中,各项指标不变各项指标不变,则有相应的线性规划则有相应的线性规划:123,x xx,z123max z234,xxx1231231.535600,28025040060000,xxxxxx.st123,0.x xx 模型求解模型求解 该问题的整数解为该问题的整数解为12364,168,0.630 xxxz 讨论讨论 若增加附加条件若增加附加条件:每种汽车如果生产的话每种汽车如果生产的话,则至少生产则至少生产80辆辆,则生产计划应该做如何修改则生产计划应该做如何修改?分析分析:根据条件根据条件,对决策变量的限制改为如下几种对决策变量的限制改为