数学规划模型

《数学规划模型》由会员分享，可在线阅读，更多相关《数学规划模型（240页珍藏版）》请在金锄头文库上搜索。

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

2、去所给问题的具体意义, 我们得到原问题的数学关系我们得到原问题的数学关系为为 分析分析 该问题的关键所在是确定每种产品的产量该问题的关键所在是确定每种产品的产量, 为此以为此以 表示三种产品的产量表示三种产品的产量, 则目标为则目标为 在一个生产周期中在一个生产周期中, 每种设备所提供的工时为有限的每种设备所提供的工时为有限的,故对四种设备而言还应该满足下列条件故对四种设备而言还应该满足下列条件:非负性非负性用用Lingo软件可以得到相应问题的解软件可以得到相应问题的解. 启动启动Lingo, 在窗在窗口下中输入下列程序口下中输入下列程序:保存完之后执行保存完之后执行Lingo菜单下的菜单下的

3、Solve命令命令,得到相应的解得到相应的解. Variable Value Reduced Cost X1 85.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

4、1.5 的钢筋各一根的钢筋各一根. 已知原料钢筋长度为已知原料钢筋长度为7.4 问如何切割钢筋问如何切割钢筋, 使得钢筋的利用率为最高使得钢筋的利用率为最高?分析分析 该问题的要点是如何切割钢筋该问题的要点是如何切割钢筋, 使得每次切割之使得每次切割之后后, 剩下的余料为最少剩下的余料为最少? 假设在切割过程中假设在切割过程中, 我们不考虑钢筋的损耗我们不考虑钢筋的损耗, 并考虑并考虑各各种切割方案种切割方案:方案方案2.92.11.5余料余料1103022010.130220.241200.350130.8非负性非负性 从分析中可以看出从分析中可以看出, 此问题的关键是确定每种方案下此问题的

5、关键是确定每种方案下的余料数的余料数. 设设 表示第表示第 种方案中使用的原料钢种方案中使用的原料钢筋数筋数, 则余料数为则余料数为而相应的限制条件为而相应的限制条件为 故原问题的数学关系式为故原问题的数学关系式为非负性非负性在在Lingo下得到该问题的解为下得到该问题的解为运行后得到该问题的解为运行后得到该问题的解为 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 线性规划的模型一般可表示为线性规划的模型一般可表示为非负性非负性

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

7、 设从第设从第 个产地到第个产地到第 个销地的运输量为个销地的运输量为 运运输成本为输成本为 则问题的目标函数为则问题的目标函数为由于从第一个产地调出的物质的总和为第一个产地的产由于从第一个产地调出的物质的总和为第一个产地的产量量, 即有即有同理同理, 有有对称地对称地, 对销地而言对销地而言, 有关系有关系由此得到该问题的数学模型由此得到该问题的数学模型注注 该问题又称为运输问题该问题又称为运输问题. 运输问题的一般形式可写运输问题的一般形式可写成成其中其中 是第是第 个产地的产量个产地的产量, 是第是第 个销地的需求量个销地的需求量. 在上面的关系中在上面的关系中, 有有相应的运输问题称为

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

9、中 为第为第 个季节的储水量个季节的储水量. 2.为保证灌溉为保证灌溉, 发电发电, 航运等用水供应航运等用水供应, 水库在每个水库在每个季季节应能保证一定的放水量节应能保证一定的放水量 考虑到这仍然是一随机因考虑到这仍然是一随机因数数, 要求满足满足这一条件的概率不小于要求满足满足这一条件的概率不小于 即即其中其中 为第为第 个季节的可放水量个季节的可放水量. 3.为保证水库的安全和水生放养为保证水库的安全和水生放养, 水库还应有一定的水库还应有一定的储水量储水量 即即由此得到相应问题的数学模型为由此得到相应问题的数学模型为: 问题问题5 某公司准备派某公司准备派 个工人个工人 去完成去完成

10、项工作项工作 已知第已知第 个工人完成第个工人完成第 工作的效工作的效率为率为 求如此的一个指派方案求如此的一个指派方案, 使工人完成这些工作使工人完成这些工作的效率为最大的效率为最大. 该问题可用一个网络图该问题可用一个网络图 来表示来表示: 其中其中 表表示顶点集示顶点集, 是边集是边集, 是权集是权集. 该问题即是从该问题即是从 的每一个顶点的每一个顶点,找出唯一的一条到找出唯一的一条到 的某一个的某一个 的边的边, 使得权之和为最大使得权之和为最大. 模型建立模型建立 若以若以 表示在顶点表示在顶点 存在边存在边, 否则否则则目标函数可表示为则目标函数可表示为 而从而从 的每一个顶点的

11、每一个顶点 只能作一条边等价于只能作一条边等价于同样同样, 连连 惟一的一条边等价于惟一的一条边等价于由此得到相应的数学模型为由此得到相应的数学模型为这样的规划又称为这样的规划又称为0-1规划规划.注注1 很多实际问题都可以转化成这样的模型很多实际问题都可以转化成这样的模型. 例如游例如游泳泳接力队员的选拔接力队员的选拔.注注2 当人数和工作数不相同时当人数和工作数不相同时, 这样的问题应该如何求这样的问题应该如何求解解, 又当又当 时时, 并且容许一个人能完成两件工作并且容许一个人能完成两件工作, 又该如何解决又该如何解决?二、模型的求解二、模型的求解例例1 一奶制品加工厂用牛奶生产一奶制品

12、加工厂用牛奶生产 两种奶制品两种奶制品,1桶牛奶可以在设备甲上用桶牛奶可以在设备甲上用12小时加工生产小时加工生产3公斤公斤 或或则在设备乙上用则在设备乙上用8小时加工成小时加工成4公斤公斤 根据市场需要根据市场需要, 生产的生产的 全部能售出全部能售出, 且每公斤且每公斤 获利获利24元元, 每公每公斤斤 可获利可获利16元元. 现在加工厂每天能得到现在加工厂每天能得到50桶牛奶的供桶牛奶的供应应, 每天工人总的劳动时间为每天工人总的劳动时间为480小时小时, 并且设备甲每并且设备甲每天天至多能加工至多能加工100公斤公斤 设备乙的加工能力没有限制设备乙的加工能力没有限制. 试试为该厂制定一

13、个生产计划为该厂制定一个生产计划, 使每天获利最大使每天获利最大, 并进一步并进一步讨论以下讨论以下3个附加问题个附加问题: 若用若用35元可以买到元可以买到1桶牛奶桶牛奶, 应否作这项投资应否作这项投资? 若投若投资资, 每天最多购买多少桶牛奶每天最多购买多少桶牛奶? 若可以聘用临时工人以增加劳动时间若可以聘用临时工人以增加劳动时间, 付给临时工付给临时工人的工资最多是每小时几元人的工资最多是每小时几元? 由于市场需求变化由于市场需求变化, 每公斤每公斤 的利润增加到的利润增加到30元元,应否改变生产计划应否改变生产计划?解解 设设 表示这两种产品每天所消耗牛奶的数量表示这两种产品每天所消耗

14、牛奶的数量（单位：桶）（单位：桶）. 则用于生产则用于生产 的牛奶可获利的牛奶可获利用于生产用于生产 的牛奶可获利的牛奶可获利 则目标函数为则目标函数为限制条件分别为限制条件分别为:对原料的限制对原料的限制:劳动力的限制劳动力的限制设备甲的开工限制设备甲的开工限制 由此得到相应的规划模型由此得到相应的规划模型 对每一约束条件对每一约束条件,在第一象限中确定坐标点的范围在第一象限中确定坐标点的范围, 最最终确定解的范围终确定解的范围可行域（多边形区域）可行域（多边形区域）; 模型求解模型求解 解法解法1 （图解法）（图解法） 确定等值线（图中用虚线），则最优解为可行域与确定等值线（图中用虚线），

15、则最优解为可行域与等值线的最后交点（即图中点的等值线的最后交点（即图中点的 坐标）即为所求问坐标）即为所求问题的最优解题的最优解. 为此求解方程为此求解方程容易得到该方程的解为容易得到该方程的解为 解法解法2 （单纯形方法）（单纯形方法） 原规划的标准型为原规划的标准型为 解法解法3 （利用计算机软件）（利用计算机软件） 在软件在软件Lingo8下进行求解下进行求解: 输入命令输入命令 Variable Value Reduced Cost X1 20.00000 0.000000 X2 30.00000 0.000000 Row Slack or Surplus Dual Price 1 3

16、360.000 1.000000 2 0.000000 48.00000 3 0.000000 2.000000 4 40.00000 0.000000得到的解为得到的解为 结果分析结果分析 三个约束条件的右端视为三个约束条件的右端视为“资源资源”: 原料原料, 劳动时劳动时间间,设备甲的加工能力设备甲的加工能力. 对当前解而言对当前解而言, 前两种前两种“消耗殆尽消耗殆尽”，而设备甲尚余而设备甲尚余40公斤的加工能力公斤的加工能力. 目标函数可以看作为是目标函数可以看作为是“效益效益”. 成为紧约束的资成为紧约束的资源源一旦增加一旦增加,则则“效益效益”必然增加必然增加. 解中列出的解中列出

17、的“对偶对偶”价价格表格表示紧约束示紧约束“资源资源”每增加一个单位后相应每增加一个单位后相应“效益效益”的增的增加值加值.原料每增加一个单位原料每增加一个单位, 利润可增加利润可增加48个单位个单位; 而劳动时而劳动时间间每增加一个单位每增加一个单位, 利润可增加利润可增加2个单位个单位. 而非紧约束资源而非紧约束资源的增加的增加, 不会带来相应的收益不会带来相应的收益. 这种这种“资源资源”潜在价值潜在价值被被称为称为 “影子影子”价格价格. 用用“影子影子”价格即可回答附加问题价格即可回答附加问题. 用用35元购买一桶牛奶元购买一桶牛奶, 低于牛奶的影子价格低于牛奶的影子价格, 故可故可

18、以以做这项投资做这项投资; 临时工人每小时的工资不超过临时工人每小时的工资不超过2元元. 而设而设 备甲尚有富裕能力备甲尚有富裕能力, 故增加工时不会产生效益故增加工时不会产生效益. 目标函数的系数发生变化对最优解和最优值的影响目标函数的系数发生变化对最优解和最优值的影响. 在图解法中可以看到，价值系数在图解法中可以看到，价值系数 对最优解会产对最优解会产生一定的影响生一定的影响. 因为因为 确定了等值线的斜率确定了等值线的斜率, 原问题原问题等值线的斜率为等值线的斜率为 , 当斜率上升到当斜率上升到 则则最优解将会改变最优解将会改变, 此时最优解将在此时最优解将在 点取得点取得. 灵敏度分析

19、还给出了各个系数的范围灵敏度分析还给出了各个系数的范围: 的上界为的上界为24,下界为下界为8, 即当即当 时时, 最优最优解不变解不变; 同样当同样当 时时,最优解不变最优解不变. 从图中还可以看出从图中还可以看出, 原原料（牛奶）的增加料（牛奶）的增加, 对应对应的是直线的是直线 的向右的的向右的平移平移, 此时最优解仍此时最优解仍为点为点 但当但当 与与 重合重合时时, 最优解将不再改变最优解将不再改变,此时此时, 而由而由“影子影子”价格知价格知: 原料每增加原料每增加一个一个单位利润将增加单位利润将增加48个单位个单位. 此时总利润为此时总利润为 同样同样, 当劳动力资源当劳动力资源

20、增加时增加时, 即直线即直线 向向右移动时右移动时, 最优解也最优解也将改变将改变, 但当但当 两两点重合时点重合时, 最优解将最优解将不再改变不再改变. 由由“影子影子”价格价格, 劳动力每增加一个工时劳动力每增加一个工时, 效益增加效益增加2个单位个单位.但劳但劳动力最多增加动力最多增加53个单位个单位. 因设备甲仍有富余工时因设备甲仍有富余工时, 因而设备的加工能力无需因而设备的加工能力无需再再增加增加, 其其“影子影子”价格为零价格为零. 根据上面的分析根据上面的分析,可以回答原问题中提出的相关问题可以回答原问题中提出的相关问题. 可以批准用每桶可以批准用每桶35元的价格再购买部分牛奶

21、元的价格再购买部分牛奶, 但最但最多再购买多再购买10桶桶; 可以以用低于每小时可以以用低于每小时2元的工资聘用临时工人以增元的工资聘用临时工人以增劳动时间劳动时间, 但最多不得超过但最多不得超过53小时小时. 例例2 奶制品的销售计划奶制品的销售计划 例例1给出的给出的 两种奶制品的生产条件两种奶制品的生产条件, 利润及工厂利润及工厂的资源限制不变的资源限制不变, 为增加工厂的获利为增加工厂的获利, 开发了奶制品的深开发了奶制品的深加工技术加工技术: 用用2小时和小时和3元加工费元加工费, 可将可将1公斤公斤 加工成加工成0.8高级奶制品高级奶制品 也可将一公斤也可将一公斤 加工成加工成0.

22、75公斤高级公斤高级奶制品奶制品 每公斤每公斤 能获利能获利44元元, 每公斤每公斤 能获利能获利32元元,试为该厂制定一个生产销售计划试为该厂制定一个生产销售计划, 使获得的利润最大使获得的利润最大,并讨论以下问题并讨论以下问题: 若投资若投资32元可以增加供应一桶牛奶元可以增加供应一桶牛奶, 投资投资3元可以增元可以增加一小时劳动时间加一小时劳动时间, 应否作这样的投资应否作这样的投资, 若每天投资若每天投资150元元, 可赚回多少可赚回多少? 每公斤高级奶制品每公斤高级奶制品 的获利经常有的获利经常有10%的波动的波动,对指定计划有无影响对指定计划有无影响, 若每公斤若每公斤 的获利下降

23、的获利下降10%, 计计划应该改变吗划应该改变吗? 问题分析问题分析 要求指定生产计划要求指定生产计划, 关键是确定各产品的产量关键是确定各产品的产量, 而目而目标函数为销售这些产品之后可获得的利润标函数为销售这些产品之后可获得的利润. 建立模型建立模型 设每天销售设每天销售 公斤公斤 公斤公斤 公斤公斤 公斤公斤 用用 公斤公斤 加工加工 公斤公斤 加工加工 目标函数目标函数 约束条件约束条件 原料供应原料供应 每天生产每天生产 公斤公斤, 用牛奶用牛奶 桶桶, 每天生产每天生产 公斤公斤,用牛奶用牛奶 桶桶, 两者之和不超过两者之和不超过50桶桶; 劳动时间劳动时间 每天生产每天生产 的时

24、间分别为的时间分别为 加工加工 的时间分别为的时间分别为 两两者之和不超过者之和不超过480小时小时; 设备能力设备能力 的产量的产量 不得超过设备甲每天的不得超过设备甲每天的 加工能力加工能力100公斤公斤; 非负约束非负约束 附加约束附加约束 1公斤公斤 加工成加工成 公斤公斤 即即同样同样 由此得到模型由此得到模型 模型求解模型求解 用用Lingo软件软件, 进行求解进行求解, 得得 Variable Value Reduced Cost X1 0.000000 1.680000 X2 168.0000 0.000000 X3 19.20000 0.000000 X4 0.000000

25、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: Objective Coefficient Ranges Current Allowable Variable Co

26、efficient 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的的“影子影子”价格分别是价格分别是 和和 即每增加一桶牛奶可使净利润增加即每增加一桶牛奶可使净利润增加 元元增加

27、增加1小时劳动时间小时劳动时间, 可是利润增加可是利润增加 元元, 所以应该所以应该投资投资 元增加一桶牛奶或投资元增加一桶牛奶或投资3元增加一小时劳动时元增加一小时劳动时间间. 若每天投资若每天投资 元元, 增加供应增加供应5桶牛奶桶牛奶, 可获利可获利元元但约束但约束2的增加值最多不超过的增加值最多不超过120, 意味牛奶的桶数最多意味牛奶的桶数最多不超过不超过10桶桶. 在灵敏度分析的报告中在灵敏度分析的报告中, 目标函数系数的变化范围分目标函数系数的变化范围分别为别为 由此可见由此可见, 当当 的价格向下波动的价格向下波动 或或 的价格向的价格向上波动上波动 都会影响到最优解都会影响到

28、最优解. 问题的提出问题的提出 钢铁、煤、水电等生产、生活物资从钢铁、煤、水电等生产、生活物资从若干供应点运送到一些需求点，怎样安排运输，使运费若干供应点运送到一些需求点，怎样安排运输，使运费为最小、或者利润为最大为最小、或者利润为最大. 某种类型的货物由于需要装某种类型的货物由于需要装箱箱, 故要考虑如何搭配使利用率达到最高故要考虑如何搭配使利用率达到最高, 诸如此类的诸如此类的问题都牵涉到一些具体的数学模型问题都牵涉到一些具体的数学模型, 这目讨论两个问题这目讨论两个问题,并利用相应的数学规划模型加以解决并利用相应的数学规划模型加以解决.三、应用举例三、应用举例 题题1 自来水的输送问题自

29、来水的输送问题 某市有甲、乙、丙、丁四个居民区某市有甲、乙、丙、丁四个居民区, 自来水由自来水由三个水库供应三个水库供应, 四个区每天必须得到保证的基本用水四个区每天必须得到保证的基本用水量量分别为分别为 千吨千吨, 但由于水源紧张但由于水源紧张, 三个水库三个水库每天最多只能分别供应每天最多只能分别供应 吨自来水吨自来水, 并由于地并由于地区位置的差别区位置的差别, 自来水公司从各水库向各区送水所需自来水公司从各水库向各区送水所需付付出的引水管理费不同（见表）出的引水管理费不同（见表）, 其它管理费用都是其它管理费用都是 千吨千吨, 根据公司规定根据公司规定, 各区用户按统一标准各区用户按统

30、一标准 千吨千吨收费收费, 此外此外, 四个区都向公司申请了额外用水量四个区都向公司申请了额外用水量, 分分分别为每天分别为每天 千吨千吨, 该公司应如何分配供该公司应如何分配供水量水量, 才能获利最多才能获利最多?管理费管理费甲甲乙乙丙丙丁丁A160130220170B140130190150C190200230/ 为了增加供水量为了增加供水量, 自来水公司正在考虑进行水库改自来水公司正在考虑进行水库改造造,随三个水库的供水量都提高一倍随三个水库的供水量都提高一倍, 问此时供水方案应问此时供水方案应如如何改变何改变?公司利润可增加多少公司利润可增加多少? 分析分析 问题的关键是如何安排从各个

31、水库向四个居民区供水问题的关键是如何安排从各个水库向四个居民区供水,使得引水管理费用达到最小使得引水管理费用达到最小, 注意到其它费用与供水安注意到其它费用与供水安排无关排无关. 模型建立模型建立 设决策变量为设决策变量为 三个水库三个水库 向甲、乙、向甲、乙、丙、丁丙、丁 四个区的供水量四个区的供水量, 设水库设水库 向向 区的区的日供水量为日供水量为 并注意到并注意到 由条件得由条件得 由于需求量大于供水量由于需求量大于供水量, 需求限制可表示为需求限制可表示为 在在Lingo下得到问题的解下得到问题的解. Variable Value Reduced Cost X11 0.000000

32、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即即:该问题的解为该问题的解为此时引水管理费为此时引水管理费为 元元, 利润为利润为元元. 讨论讨论 如果如果 三个水库的每天最大供水量都增加一

33、倍三个水库的每天最大供水量都增加一倍,则公司总供水能力为则公司总供水能力为 千吨千吨, 水库供水量超过总需求水库供水量超过总需求量量, 故此时需要计算三个水库向甲、乙、丙、丁四个区故此时需要计算三个水库向甲、乙、丙、丁四个区供应每千吨水的净利润，供应每千吨水的净利润， 即有表即有表2 净利润净利润甲甲乙乙丙丙丁丁A290320230280B310320260300C260250220/从水库向各区送水的净利润从水库向各区送水的净利润 由此得到目标函数为由此得到目标函数为约束条件为：约束条件为：在在Lingo下得到问题的解：下得到问题的解： Variable Value Reduced Cost

34、 X11 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.0

35、00000 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 货机装运问题货机装运问题 问题问题 某种货机有三个货舱某种货机有三个货舱: 前舱、中舱、后舱前舱、中舱、后舱. 三三个货舱所能装载的货物的最大重量和体积都有限制个货舱所能装载的货物的最大重量和体积都有限制, 如如表所示表所示, 并且为了保持飞机的平衡并且为了保持飞机的平衡,三个货舱中实际装三个货舱中实际装载载货物的重

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

37、货物可以混装每种货物可以混装, 并保证不留空隙并保证不留空隙.应如何安排装运应如何安排装运, 使该货机本次装运的利润最大使该货机本次装运的利润最大? 模型建立模型建立 决策变量决策变量 表示第表示第 种物资装入第种物资装入第 个货舱的重量个货舱的重量, 货货舱舱 分别表示前、中、后舱分别表示前、中、后舱. 目标函数表示一次运送后的总利润目标函数表示一次运送后的总利润, 即有即有 约束条件有如下的约束条件有如下的:总重量约束总重量约束三个货舱的重量限制三个货舱的重量限制三个货舱的空间限制三个货舱的空间限制平衡限制平衡限制 模型求解模型求解. 在在Lingo下下,可得到模型的解为可得到模型的解为:

38、 Variable Value Reduced Cost 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 X

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

40、月生产小、中、大型汽车的数量分别为工厂的月利润为工厂的月利润为 假定在生产周期中假定在生产周期中, 各项指标不变各项指标不变, 则有相应的线性规划则有相应的线性规划: 模型求解模型求解 该问题的整数解为该问题的整数解为 讨论讨论 若增加附加条件若增加附加条件: 每种汽车如果生产的话每种汽车如果生产的话,则至少生产则至少生产80辆辆, 则生产计划应该做如何修改则生产计划应该做如何修改? 分析分析: 根据条件根据条件, 对决策变量的限制改为如下几种对决策变量的限制改为如下几种: 对得到的每一个解进行讨论对得到的每一个解进行讨论, 最后确定最大值解最后确定最大值解. 最优解为最优解为 注注 在在Li

41、ngo下下, 求整数解的命令为求整数解的命令为 变量名变量名 方法二方法二 用用 规划规划 在问题中在问题中,引入待定常数引入待定常数 其中其中 为任意的的正数为任意的的正数,（在具体问题中可以确定）（在具体问题中可以确定）,Global optimal solution found at iteration: 31 Objective value: 610.0000 Variable Value Reduced Cost X1 80.00000 -2.000000 X2 150.0000 -3.000000 X3 0.000000 -4.000000 Y1 1.000000 0.000000

42、 Y2 1.000000 0.000000 Y3 0.000000 0.000000 题题4 原料采购与加工原料采购与加工 问题问题 某公司用两种原油（某公司用两种原油（ 和和 ）混合加工成两种）混合加工成两种汽油（甲和乙）汽油（甲和乙）, 甲、乙两种汽油含原油的最低比例分甲、乙两种汽油含原油的最低比例分别为别为 每吨售价分别为每吨售价分别为 元和元和 元元,该公司还有原油该公司还有原油 和和 的库存量分别为的库存量分别为 吨和吨和吨吨, 另外还可以从市场上买到不超过另外还可以从市场上买到不超过 吨的原油吨的原油原油原油 的市场价为的市场价为: 购买不超过购买不超过 吨时的单价为吨时的单价为

43、吨吨, 购买量超过购买量超过 吨但不超过吨但不超过 吨时吨时, 超超过部分过部分 吨吨, 超过超过 吨的部分吨的部分, 吨吨. 该该公公司应如何安排原油的采购和加工司应如何安排原油的采购和加工? 问题分析问题分析 公司安排原油的采购和加工公司安排原油的采购和加工, 其目的是为了取得最大其目的是为了取得最大利润利润, 但问题的困难之处在于原油但问题的困难之处在于原油 的采购价与采购量的采购价与采购量的关系比较复杂的关系比较复杂. 模型建立模型建立 设原油的购买量为设原油的购买量为 则由题意则由题意, 购买成本函数为购买成本函数为 但这样的函数过于复杂但这样的函数过于复杂, 为了是问题尽可能简单为

44、了是问题尽可能简单, 我我们引入多个变量来刻画们引入多个变量来刻画: 分别以分别以 表示以表示以 吨吨, 吨吨, 吨采购得到吨采购得到的原油的原油 的采购量的采购量, 则当以则当以 吨的价格采购到原油吨的价格采购到原油时时, 总有总有 故相应的条件可表示为故相应的条件可表示为同样同样, 当以价格当以价格 吨的价格购买到了吨的价格购买到了 吨原油吨原油 时时, 有有此外此外,变量变量 还应满足还应满足 假设假设: 用于生产甲、乙两种汽油的原油用于生产甲、乙两种汽油的原油 的数量分别的数量分别为为 用于生产甲、乙两种汽油的原油用于生产甲、乙两种汽油的原油 的数量分的数量分别为别为 则总收入为则总收

45、入为而成本函数而成本函数 可表达为可表达为约束条件为约束条件为以及非负限制以及非负限制总结上面的分析总结上面的分析, 得到相应的模型为得到相应的模型为 模型求解模型求解 利用利用Lingo, 得到问题的解为得到问题的解为 Variable Value Reduced Cost X11 500.0000 0.000000 X21 500.0000 0.000000 X12 0.000000 0.2666667 X22 0.000000 0.000000 X1 0.000000 0.4000000 X2 0.000000 0.000000 X3 0.000000 0.000000 解法二解法二:

46、采用采用 规划规划 令令 分别表示以分别表示以 吨、吨、 吨、吨、 吨吨, 则约束条件可转化为则约束条件可转化为用用Lingo软件得到问题的解为软件得到问题的解为 Variable Value Reduced Cost X11 0.000000 0.000000 X21 0.000000 1.400000 X12 1500.000 0.000000 X22 1000.000 0.000000 X1 500.0000 0.000000 X2 500.0000 0.000000 X3 0.000000 0.000000 Y1 1.000000 0.000000 Y2 1.000000 2000.0

47、00 Y3 1.000000 1000.000即问题的解为即问题的解为 题题5 接力队的选拔接力队的选拔 问题的提出问题的提出: 在实际工作中在实际工作中,经常会遇到下面的问题经常会遇到下面的问题:有若干项工作要分配给某些人去完成有若干项工作要分配给某些人去完成. 在分配的过程在分配的过程中中, 要尽可能发挥每个人的长处要尽可能发挥每个人的长处, 以取得最大效益以取得最大效益. 这这样的问题就称为指派问题样的问题就称为指派问题. 通过下面的例子我们来说通过下面的例子我们来说明如何求解这样的指派问题明如何求解这样的指派问题. 问题问题 某班准备从某班准备从5名游泳队员中选拔名游泳队员中选拔4人组

48、成一个接力队人组成一个接力队,参加学校的参加学校的 混合泳接力赛混合泳接力赛. 5名队员的名队员的4种泳姿种泳姿的成绩如表所示的成绩如表所示, 问应该如何选拔问应该如何选拔? 甲甲乙乙丙丙丁丁戊戊蝶泳蝶泳仰泳仰泳蛙泳蛙泳自由泳自由泳5名队员名队员4种泳姿的百米最好成绩种泳姿的百米最好成绩 问题分析问题分析 解决该问题的关键解决该问题的关键, 是从是从5名队员中选出名队员中选出4名队员名队员, 组组成接力队成接力队, 每名队员完成一种泳姿每名队员完成一种泳姿, 且且4人的泳姿各不相人的泳姿各不相同同, 但使总成绩为最好但使总成绩为最好. 一种方法是穷举法一种方法是穷举法, 但这种方但这种方法当法

49、当 较大时是不可接受的较大时是不可接受的. 我们用我们用 规划来解规划来解决这个问题决这个问题. 以以 表示表示5名队员名队员, 表示表示4种种泳姿泳姿, 以以 表示第表示第 名队员游第名队员游第 种泳姿的最好成种泳姿的最好成绩绩, 则有则有66.857.2787067.475.66667.874.2718766.484.669.683.858.65359.457.262.4 引入引入 变量变量 若选择队员若选择队员 去参加泳姿去参加泳姿 的比赛的比赛, 则记则记 其它情况其它情况, 记记 且应该满足如下的约且应该满足如下的约束条件束条件:1.每人最多只能入选每人最多只能入选4种泳姿之一，即种

50、泳姿之一，即2.每种泳姿必须有一人也只能有一人入选，即每种泳姿必须有一人也只能有一人入选，即 当队员当队员 选泳姿选泳姿 时，时， 相应的相应的 表示他的成绩表示他的成绩, 否则否则 因此因此即为所求求的目标函数即为所求求的目标函数. 从而该问题的规划模型为从而该问题的规划模型为 用用Lingo软件求解该问题软件求解该问题. 该问题的解为该问题的解为 题题6 选课策略选课策略 某学校规定，运筹学专业的学生毕业时至少学习过两某学校规定，运筹学专业的学生毕业时至少学习过两门数学课，三门运筹学课和两门计算机课，这些课程的门数学课，三门运筹学课和两门计算机课，这些课程的编号、名称、学分、所属类别和先修

51、课要求如表所示，编号、名称、学分、所属类别和先修课要求如表所示，那么毕业时学生最少可以学习这些课程中的哪些课程？那么毕业时学生最少可以学习这些课程中的哪些课程？ 如果某个学生既希望选修课程的数量少，又希望所获如果某个学生既希望选修课程的数量少，又希望所获得的学分多，他可以选修哪些课程？得的学分多，他可以选修哪些课程？编号编号名称名称学分学分类别类别先修课程号先修课程号1微积分微积分5数学数学2线性代数线性代数4数学数学3最优化方法最优化方法4数学数学,运筹学运筹学1,24数据结构数据结构3数学数学,计算机计算机75应用统计应用统计4数学数学,运筹学运筹学1,26计算机模拟计算机模拟3计算机计算

52、机,运筹运筹学学77计算机编程计算机编程2计算机计算机编号编号名称名称学分学分类别类别先修课程号先修课程号8预测理论预测理论2运筹学运筹学59数学实验数学实验3运筹学运筹学,计算计算机机1,2 模型建立模型建立 设设 表示选修课表中按编号顺序的表示选修课表中按编号顺序的9门课程（门课程（ 表示不选这门课程表示不选这门课程, ） 则问题的目标为选修则问题的目标为选修课程为最少课程为最少, 即即约束条件有约束条件有1.至少选修两门数学课至少选修两门数学课, 三门运筹学课和两门计算机课三门运筹学课和两门计算机课, 即即 此外此外, 某些课程有先选的要求某些课程有先选的要求, 例如对例如对最优化方法最

53、优化方法而言而言, 必须先选必须先选微积分微积分和线性代数和线性代数线性代数线性代数.即即应该满足应该满足 从而得到约束条件关系从而得到约束条件关系同样同样, 对其它选修课程的先选关系也可得到相应的约束对其它选修课程的先选关系也可得到相应的约束条件条件, 整理后得到整理后得到由此得到相应的规划为由此得到相应的规划为在在Lingo下面对问题进行求解下面对问题进行求解, 得到解为得到解为 若在考虑选修课时达到最小的同时若在考虑选修课时达到最小的同时, 还希望所得到的还希望所得到的学分达到最大学分达到最大, 则增加目标函数则增加目标函数为此引入目标函数向量为此引入目标函数向量 最终得到目标函最终得到

54、目标函数数 但是得到问题的解发现选修的课程门数多于但是得到问题的解发现选修的课程门数多于6门而达门而达到到7门门,如果所考虑的问题是优先门数的话如果所考虑的问题是优先门数的话, 则再增加限则再增加限制条件制条件则得到问题的解为则得到问题的解为而此时相应的学分为而此时相应的学分为 题题7 销售代理的开发与中断销售代理的开发与中断 问题问题 某公司正在考虑在某城市开发一些销售代理业某公司正在考虑在某城市开发一些销售代理业务务. 经过预测经过预测, 该公司已经确定了该城市未来该公司已经确定了该城市未来5年的业务年的业务量量, 分别为分别为 该公司已经初步该公司已经初步物色了物色了4家销售公司作为其代

55、理候选企业家销售公司作为其代理候选企业, 下表给出了该下表给出了该公司与每个候选企业代理关系的一次性费用公司与每个候选企业代理关系的一次性费用, 以及每个以及每个应该与哪些候选企业建立代理关系应该与哪些候选企业建立代理关系?代理代理1代理代理2代理代理3代理代理4最大业务量最大业务量350250300200一次性费用一次性费用100809070年运行费用年运行费用7 .54.06.53.0 如果该公司目前已经和上述如果该公司目前已经和上述4个代理建立了代理关系个代理建立了代理关系,并且都处于运行状态并且都处于运行状态, 但每年初可以决定临时中断或重但每年初可以决定临时中断或重新恢复代理关系新恢

56、复代理关系, 每次临时中断或恢复代理关系的费用每次临时中断或恢复代理关系的费用如下表所示如下表所示, 该公司应如何对这些代理进行业务调整该公司应如何对这些代理进行业务调整?代理代理1代理代理2代理代理3代理代理4中断费用中断费用5342恢复费用恢复费用5419 模型的建立模型的建立 首先考虑问题的前半部分首先考虑问题的前半部分: 以以 表示公司在第表示公司在第年与公司年与公司 首次建立代理关系（首次建立代理关系（ 则表示不建立代理关则表示不建立代理关系）系）. 目标函数为这目标函数为这5年中的总费用年中的总费用, 则总费用为建立代理则总费用为建立代理关系的一次性费用及每年的运行费用关系的一次性

57、费用及每年的运行费用, 其中建立代理关其中建立代理关系的一次性费用为系的一次性费用为由于第一问中没有说明是否可以临时中断代理关系由于第一问中没有说明是否可以临时中断代理关系, 故故假定代理关系一旦建立假定代理关系一旦建立, 该关系将维持下去该关系将维持下去, 因此对候因此对候选选代理代理1而言而言, 5年的总运行费用为年的总运行费用为于是对所有的候选代理人而言于是对所有的候选代理人而言, 5年的总运行费用为年的总运行费用为由此得到问题的目标函数为由此得到问题的目标函数为约束条件为约束条件为: 公司的业务量必须由足够的代理承担公司的业务量必须由足够的代理承担, 即即有有（第一年的业务量）（第一年

58、的业务量）类似，对第二年的业务量，有类似，对第二年的业务量，有由此得到问题的数学模型为由此得到问题的数学模型为得到问题的解为得到问题的解为 其余的变量为零其余的变量为零, 此此意味意味 公司在第一年初与代理公司在第一年初与代理1,2建立代理关系建立代理关系, 并在以后并在以后保持代理关系保持代理关系, 第四年与代理第四年与代理4建立代理关系建立代理关系. 最小费用最小费用为为 元元. 进一步地进一步地, 若建立关系之后可以中断关系若建立关系之后可以中断关系, 中断关中断关系系之后也可恢复关系之后也可恢复关系, 试在其它假设不变的情况下试在其它假设不变的情况下, 求出求出问题的最优解问题的最优解

59、. 模型建立模型建立 仍然以仍然以 表示在第表示在第 年公司与候选代理人年公司与候选代理人 在年在年初建立代理关系初建立代理关系, 但注意到在年初公式可以临时决定公但注意到在年初公式可以临时决定公司可以决定解除或恢复代理关系司可以决定解除或恢复代理关系, 故以故以 表示公司表示公司在第在第 年初公司与代理人年初公司与代理人 中断代理业务中断代理业务, 而而 则表则表示在第示在第 年的年初公司与代理人年的年初公司与代理人 恢复代理人业务恢复代理人业务, 则则相应的目标函数为相应的目标函数为中断与恢复代理关系的约束表现为中断与恢复代理关系的约束表现为注意到期初时注意到期初时, 公司与所有代理人都有

60、代理关系公司与所有代理人都有代理关系, 即即又恢复关系可以表现为又恢复关系可以表现为 即即有有 题题8 饮料厂的生产与检修计划饮料厂的生产与检修计划 问题问题 某饮料厂生产一种饮料以满足市场需要某饮料厂生产一种饮料以满足市场需要. 该厂该厂销售科根据市场预测销售科根据市场预测, 已经确定了未来四周该饮料厂的已经确定了未来四周该饮料厂的需求量需求量, 计划科根据本厂实际情况给出了未来四周的生计划科根据本厂实际情况给出了未来四周的生产能力和生产成本产能力和生产成本, 相应数据由下表所示相应数据由下表所示, 每周当饮料每周当饮料满足需求后有剩余时满足需求后有剩余时, 要支出存储费要支出存储费, 为每

61、周每千箱饮为每周每千箱饮料料 千元千元, 问应如何安排生产问应如何安排生产, 在满足市场需要的前在满足市场需要的前提下提下, 使四周的总费用为最小使四周的总费用为最小.周次周次需求量需求量生产能力生产能力成本成本115305225405.1335455.4425205.5合计合计100135 分析分析 从表中的数据中可以看出从表中的数据中可以看出, 除了第四周外除了第四周外, 其余各周其余各周的生产能力都大于每周的需求量的生产能力都大于每周的需求量, 即可以满足市场的需即可以满足市场的需要要. 如果第一周如果第一周, 第二周按需生产第二周按需生产, 第三周多生产第三周多生产5千千箱箱以弥补第四

62、周的不足部分以弥补第四周的不足部分, 可以使总的存储费用为最小可以使总的存储费用为最小,但注意到但注意到,生产成本逐月上升生产成本逐月上升, 因而从总成本最小的角因而从总成本最小的角度度出发考虑问题出发考虑问题, 前几周多生产一些前几周多生产一些, 可能是更好的方案可能是更好的方案. 模型假设模型假设 设饮料厂在第一周开始时没有库存设饮料厂在第一周开始时没有库存, 并且假设在第四并且假设在第四周的周末也没有库存周的周末也没有库存, 周末有库存时需支付一周的存储周末有库存时需支付一周的存储费费. 模型建立模型建立 以以 表示四周的产量表示四周的产量, 表示表示周末的库存量周末的库存量, 则成本为

63、则成本为 对第一周而言对第一周而言, 产量减去库存产量减去库存, 即为当月的需求量即为当月的需求量, 即即平行的有其它的约束条件平行的有其它的约束条件,由此得规划为由此得规划为 在在Lingo下对该问题进行求解下对该问题进行求解, 容易得到该问题的解容易得到该问题的解为为:最优解值为最优解值为 讨论讨论 如果工厂要安排一次设备检修如果工厂要安排一次设备检修, 检修将占用当周检修将占用当周15千千箱的生产能力箱的生产能力, 但会使检修以后每周的生产能力提高但会使检修以后每周的生产能力提高5千箱千箱, 试确定检修的时间安排试确定检修的时间安排. 分析分析 问题的关键是确定检修的时间安排问题的关键是

64、确定检修的时间安排. 为此引入为此引入 变变量量 若若 则表示检修则表示检修放在第放在第 周进行周进行, 注意到此时该周的生产能力将减少注意到此时该周的生产能力将减少15千箱千箱, 而以后各周的生产能力将增加而以后各周的生产能力将增加5箱箱, 因而要增加因而要增加相相应的约束条件应的约束条件:又检修只能进行一次又检修只能进行一次, 故还应该满足故还应该满足联合起来联合起来, 得到原问题的数学规划为得到原问题的数学规划为在在Lingo下下, 可以得到问题的解为可以得到问题的解为即检修安排在第一周即检修安排在第一周, 最优解值为最优解值为 题题9 饮料的生产批量问题饮料的生产批量问题 问题问题 某

65、饮料厂使用同一条生产线轮流生产多种饮料某饮料厂使用同一条生产线轮流生产多种饮料以满足市场需要以满足市场需要. 如果某周开工生产其中一种原料如果某周开工生产其中一种原料, 就就要清洗设备和更换部分部件要清洗设备和更换部分部件, 于是需支出生产准备费于是需支出生产准备费. 现在只考虑一种饮料的生产现在只考虑一种饮料的生产, 假设其未来四周的需求量假设其未来四周的需求量,生产能力生产能力, 生产成本与存储费与上题相同生产成本与存储费与上题相同, 问如何安排问如何安排这种饮料的生产这种饮料的生产, 使该种饮料的总费用为最小使该种饮料的总费用为最小?周次周次需求量需求量生产能力生产能力成本成本11530

66、5225405.1335455.4425205.5合计合计100135 分析分析 与上例相比与上例相比, 解决该问题的关键是要考虑与产品数量解决该问题的关键是要考虑与产品数量无关的生产准备费用无关的生产准备费用.条件是条件是:只要生产只要生产, 就有该费用的就有该费用的产产生生. 模型建立模型建立 首先我们对问题做一般的讨论首先我们对问题做一般的讨论: 将问题分为若干个阶段将问题分为若干个阶段, 用用 来表示来表示. 对时段对时段 以以表示需求量表示需求量, 生产能力为生产能力为 如果在时段如果在时段 开工开工, 则需则需支支付准备费用付准备费用 时段时段 末的库存为末的库存为 单件存储费为单

67、件存储费为 产量为产量为 为成本为成本, 引入引入 变量变量表示该产品在该时段投入生产表示该产品在该时段投入生产, 否则不投入生产否则不投入生产, 则目则目标函数为标函数为相应的关系为相应的关系为带回原来问题的值带回原来问题的值, 得到问题的模型为得到问题的模型为在在Lingo下下,得到问题的最优解为得到问题的最优解为 题题10 钢管的下料问题钢管的下料问题 问题问题 某钢管零售商从钢管厂进货某钢管零售商从钢管厂进货, 将钢管按客户的将钢管按客户的要求进行切割后售出要求进行切割后售出, 从钢管厂进货时的长度都是从钢管厂进货时的长度都是19 现有一客户需要现有一客户需要50根根4 29根根6 和

68、和15根根8 的钢筋的钢筋, 应如何下料应如何下料? 零售商如果采用不同的切割模式太多零售商如果采用不同的切割模式太多, 将会导致生产将会导致生产过程的复杂化过程的复杂化, 从而增加生产和管理成本从而增加生产和管理成本, 所以该零售所以该零售商商规定采用的不同切割模式不能超过规定采用的不同切割模式不能超过3种种, 此外此外, 该客户除该客户除需要上面的三种钢管外需要上面的三种钢管外, 还需要还需要10根根5 长的钢筋长的钢筋, 应应如如何下料何下料? 分析分析 首先确定哪些方案是可行的首先确定哪些方案是可行的, 为此讨论以下方为此讨论以下方案案方案方案4m6m8m余料余料14003231013

69、201341203方案方案4m6m8m余料余料511116030170023 所谓一个合适的切割方案所谓一个合适的切割方案, 应当满足两点应当满足两点: 第一方案第一方案可行可行, 第二切割后剩下的余料应当小于最小用料单位第二切割后剩下的余料应当小于最小用料单位4因此合适的切割方案只有这上述因此合适的切割方案只有这上述7种种. 模型建立模型建立 由前面的分析由前面的分析,不难得到相应的模型为不难得到相应的模型为在在Lingo下下, 得到问题的解为得到问题的解为其余其余此时用料此时用料27根根, 余料余料27 如果余料无用如果余料无用,我们可以考虑另外一种模式我们可以考虑另外一种模式, 即要求即

70、要求用用料最少料最少, 此时模型为此时模型为此时的最优解为此时的最优解为其余其余此时余料为此时余料为35 现在来看第二个问题现在来看第二个问题, 在增加一个品种的条件下在增加一个品种的条件下, 要要求切割方案总数不超过求切割方案总数不超过3种种, 今用整数非线性规划方法今用整数非线性规划方法加加以求解以求解. 设设 为第为第 种方案下使用的原料数种方案下使用的原料数, 第第 种方案下产生种方案下产生4 5 6 8 的钢管数分别为的钢管数分别为则问题的模型为则问题的模型为得到问题的最优解为得到问题的最优解为 题题11 某储蓄所每天的营业时间为上午某储蓄所每天的营业时间为上午9点到下午点到下午5点

71、点. 根据根据经验经验, 每天不同时间所需要的服务员数量为每天不同时间所需要的服务员数量为:时间段时间段91010111112121数量数量4346时间段时间段12233445数量数量5688储蓄所可以雇佣全时和半时两类服务员储蓄所可以雇佣全时和半时两类服务员. 全时服务员全时服务员每每天报酬天报酬100元元, 从上午从上午9点到下午点到下午5点工作点工作, 但中午但中午12点点到到下午下午2点之间必须安排点之间必须安排1小时的午餐时间小时的午餐时间.储蓄所每天可储蓄所每天可以不超过以不超过3名的半时服务员名的半时服务员, 每个半时服务员必须连续每个半时服务员必须连续工作工作4小时小时, 报酬

72、报酬40元元, 问该储蓄所该如何雇佣全时和问该储蓄所该如何雇佣全时和半半时服务员时服务员? 如果不能雇佣半时服务员如果不能雇佣半时服务员, 每天至少增加多每天至少增加多少费用少费用,如果雇佣半时服务员的数量没有限制如果雇佣半时服务员的数量没有限制, 每天可每天可以以减少多少费用减少多少费用? 分析分析 解决此问题的关键是确定聘用全时服务员及半时服务解决此问题的关键是确定聘用全时服务员及半时服务员的人数员的人数, 但还要考虑全时服务员有吃午餐的时间但还要考虑全时服务员有吃午餐的时间, 故故把把全时服务员分为两类全时服务员分为两类: 午餐时间为午餐时间为12时至下午时至下午1时的及下时的及下午午1

73、时至下午时至下午2时的时的; 而半时服务员按上班时间进行划分而半时服务员按上班时间进行划分. 模型建立模型建立 设设 为午餐时间为下午为午餐时间为下午12时的全时服务员的人数时的全时服务员的人数, 为午餐时间为下午为午餐时间为下午1时的全时服务员的人数时的全时服务员的人数, 而而 分别分别表示从表示从9点点, 10点点, 11点点, , 1点开始上班的半时服务点开始上班的半时服务员员人数人数, 则目标函数为则目标函数为约束条件按各个小时需要的服务员人数确定约束条件按各个小时需要的服务员人数确定, 则有则有此外此外, 对半时服务员人数的限制对半时服务员人数的限制对决策变量的限制为对决策变量的限制

74、为为整数为整数.由上述分析由上述分析, 得到相应的数学模型为得到相应的数学模型为为整数为整数. 模型求解模型求解 在在Lingo下得到问题的解下得到问题的解:若不能雇佣半时服务员若不能雇佣半时服务员,则最优解为则最优解为因而多支出因而多支出 元元.若对半时服务员人数没有限制若对半时服务员人数没有限制, 则最优解为则最优解为节省开支节省开支 元元.四、几种常用的线性规划介绍四、几种常用的线性规划介绍 问题问题1 生产组织与计划问题生产组织与计划问题 工厂用工厂用 种设备种设备 生产生产 种产品种产品 在一个生产周期内在一个生产周期内, 已知第已知第 台设备台设备 只能工作只能工作 个个机时机时.

75、 工厂必须完成产品工厂必须完成产品 至少至少 件件. 设备设备 生产生产 所所需要的机时和成本分别为需要的机时和成本分别为 试建立相应的数学模型试建立相应的数学模型,使设备能在计划周期内完成计划但又使成本达到最低使设备能在计划周期内完成计划但又使成本达到最低. 模型为模型为 问题问题2 工厂选址问题工厂选址问题 设有设有 个需求点（城市个需求点（城市, 仓库仓库, 商店等）商店等）, 有有 个可个可供供选择的建厂地址选择的建厂地址, 每个地址最多可建一个工厂每个地址最多可建一个工厂. 在在 地地址建立工厂的生产能力为址建立工厂的生产能力为 在在 地址经营工厂地址经营工厂, 单位时单位时间的固定

76、成本为间的固定成本为 需求点需求点 的需求量为的需求量为 从厂址从厂址 到到需求点需求点 的单位运费为的单位运费为 问应如何选择厂址和安排运问应如何选择厂址和安排运输计划输计划, 使相应的成本为最小使相应的成本为最小. 模型为模型为上式中上式中 的意义是的意义是:在地址在地址 建厂建厂,不在地址不在地址 建厂建厂.这样的线性规划称为混合型的整数线性规划这样的线性规划称为混合型的整数线性规划. 问题问题3 设备购置和安装问题设备购置和安装问题 工厂需要工厂需要 种设备种设备 设备设备 的单价为的单价为 工厂已有第工厂已有第 种设备种设备 台台, 今有资金今有资金元元, 可用于购置这些设备可用于购

77、置这些设备. 该厂有该厂有 处可安装这些设备处可安装这些设备, 处最多可安装处最多可安装 台台, 将一台设备将一台设备 安装在安装在 处处, 经经济效益为济效益为 元元, 问应如何购置和安装这些设备问应如何购置和安装这些设备, 才能使才能使总的经济效益最高总的经济效益最高. 以以 表示设备表示设备 在在 处安装的台数处安装的台数, 表示购置表示购置 的台数的台数, 则模型为则模型为 问题问题4 货郎问题货郎问题 货郎要到货郎要到 个地方去卖货个地方去卖货. 已知两个地方已知两个地方 和和 之间之间的距离为的距离为 如何选择一条道路如何选择一条道路, 使得货郎每个地方走使得货郎每个地方走一遍后回

78、到起点一遍后回到起点, 且所走的路径最短且所走的路径最短. 定义定义货郎选择的路线包含从货郎选择的路线包含从 到到 的路径的路径否则否则则相应的模型为则相应的模型为 问题问题5 系统可靠性问题系统可靠性问题 选择选择 个元件个元件, 组成一个并联系统组成一个并联系统. 设第设第 个位置所个位置所用用的元件可从集合的元件可从集合 中挑选中挑选. 对元件对元件 用用 表示元表示元件件 在第在第 个位置上的花费个位置上的花费, 表示其可靠性的概率表示其可靠性的概率, 问问应如何配置各位置上的元件应如何配置各位置上的元件, 使得系统的可靠性不小于使得系统的可靠性不小于 且使总费用最小且使总费用最小.

79、定义定义若元件若元件 且元件且元件 用在位置用在位置 上上若元件若元件 且元件且元件 不用在位置不用在位置 上上总费用为总费用为 其可靠性为其可靠性为若记若记 则上式可写成则上式可写成相应的模型转化为相应的模型转化为 规划规划. 模型为模型为五、非线性规划简介五、非线性规划简介 前面的问题中前面的问题中, 所建立的数学模型中的表达式的各个所建立的数学模型中的表达式的各个部分都是线性函数部分都是线性函数, 因而我们把这样的规划称为线性规因而我们把这样的规划称为线性规划划, 但在许多实际问题中但在许多实际问题中, 目标函数和约束条件表达式目标函数和约束条件表达式可能是非线性函数可能是非线性函数.这

80、样的规划就称为非线性规划这样的规划就称为非线性规划. 问题问题1 抽水费用最小问题抽水费用最小问题 某地区有某地区有3个泵站个泵站: 第第 个泵站的抽水费用为个泵站的抽水费用为 其中其中 为抽水流量为抽水流量. 泵站与各灌溉地块泵站与各灌溉地块用渠道连接用渠道连接. 在一个灌溉周期中在一个灌溉周期中, 地块地块 需流量需流量 立方立方米米/小时小时. 泵站泵站 的最大抽水能力为的最大抽水能力为 由于渗透和蒸发由于渗透和蒸发,从从 泵站到泵站到 地块的水量要打一折扣地块的水量要打一折扣, 即乘上系数即乘上系数 称称为水的实用系数为水的实用系数. 问应如何确定每一泵站的输水量问应如何确定每一泵站的

81、输水量, 才才能使总的抽水费用为最小能使总的抽水费用为最小? 试建立相应的数学模型试建立相应的数学模型. 分析分析 问题的关键是确立决策变量和目标函数问题的关键是确立决策变量和目标函数. 设从泵站设从泵站 到地块到地块 的输水量为的输水量为注注: 在上面的问题中在上面的问题中, 输水费用函数输水费用函数 一般不是一般不是的线性函数的线性函数. 因而相应的规划不是线性规划因而相应的规划不是线性规划. 问题问题2 砂石运输问题砂石运输问题 设有设有 立方米的砂立方米的砂, 石要由甲地运到乙地石要由甲地运到乙地, 运输前需运输前需先装入一个有底无盖并在底部装有滑行器的木箱中先装入一个有底无盖并在底部

82、装有滑行器的木箱中. 砂砂石运到乙地后石运到乙地后, 从箱中倒出从箱中倒出,在继续用空箱装运在继续用空箱装运. 不论不论箱箱子大小子大小, 每装运一箱每装运一箱, 需需0.1元元, 箱底和两端的材料费为箱底和两端的材料费为20元元/米米2, 箱子两侧的材料费为箱子两侧的材料费为5元元/米米2, 箱底的两个箱底的两个滑滑行器与箱子同长行器与箱子同长, 材料费为材料费为2.5元元/米米. 问木箱的长宽高问木箱的长宽高各各为多少米为多少米,才能使运费与箱子的成本费的总和为最小才能使运费与箱子的成本费的总和为最小. 建模建模 设木箱的长宽高分别为设木箱的长宽高分别为 运费与成本费的总运费与成本费的总和

83、为和为 则目标函数为则目标函数为 若在上述问题中若在上述问题中, 箱子的底与两侧使用废料来做箱子的底与两侧使用废料来做, 而而废料只有废料只有4平方米平方米, 则问题为则问题为:在上面问题中在上面问题中, 目标函数与约束条件中的每一项可表达目标函数与约束条件中的每一项可表达成成 的形式（其中的的形式（其中的 为整数）为整数） , 数学上将其成为广义多项式数学上将其成为广义多项式, 相应的规划称为几何规划相应的规划称为几何规划.当系数为正数时当系数为正数时, 规划称为正项几何规划规划称为正项几何规划. 非线性规划解法非线性规划解法例例1 求解非线性规划求解非线性规划解解1 图解法图解法解解2 用

84、用Lingo软件求解软件求解 无约束非线性规划解法简介无约束非线性规划解法简介 无约束非线性规划一般可写成无约束非线性规划一般可写成其中其中 解法解法 1.求求 的梯度的梯度 2.令梯度令梯度 解出解出 的驻点的驻点3.验证验证 在该点的在该点的Hessian矩阵是否为正（负）定的矩阵是否为正（负）定的, 若成立若成立, 则该点为函数的极小（大）值点则该点为函数的极小（大）值点.例例 求函数求函数 的极小点的极小点.解解 的梯度为的梯度为令令 则驻点为则驻点为 函数的函数的Hessian阵为阵为注意到该矩阵为正定阵注意到该矩阵为正定阵, 因而该点为极小值点因而该点为极小值点. 注意到此方法只有

85、对一些特殊的函数才有效注意到此方法只有对一些特殊的函数才有效. 一般情一般情况下况下, 要求出函数的驻点是比较困难的要求出函数的驻点是比较困难的. 下面我们简单下面我们简单介绍求解该类问题的数值解法介绍求解该类问题的数值解法.1.给出给出 的极小点的极小点 的一个初始估计值的一个初始估计值 称为初称为初始点始点;2.如果如果 已求得已求得, 并且不是极小点并且不是极小点, 设法选取一个方设法选取一个方向向 （该方向称为搜索方向）（该方向称为搜索方向）, 使目标函数使目标函数 沿该方沿该方向是下降的（一般取梯度方向）向是下降的（一般取梯度方向）;3.在射线在射线 取适当的步长取适当的步长, 书记

86、书记 由此确定点由此确定点 其中的其中的 一般取使得一般取使得上式取到极小值的值上式取到极小值的值.4.检验检验 是否为函数是否为函数 的极小值的极小值, 或者满或者满足足精度的要求精度的要求, 若不是若不是, 再回到第二步再回到第二步.六、应用六、应用 某大医院向社会提供各种不同的医疗服务某大医院向社会提供各种不同的医疗服务, 为获得为获得最最好的社会效益和经济效益好的社会效益和经济效益, 医院必须优化其资源配置医院必须优化其资源配置.如果资源配置不是最好的如果资源配置不是最好的, 则可能存在有的资源使用则可能存在有的资源使用率率低低, 而有的资源使用过度的情况而有的资源使用过度的情况. 以

87、下面提供的外科以下面提供的外科手手术数据为例术数据为例, 试建立一个能够帮助医院改善其资源配试建立一个能够帮助医院改善其资源配置置,提高效益的的数学模型提高效益的的数学模型. 题题1 医院开刀问题医院开刀问题手术类型分为三类手术类型分为三类: 简称为大手术（例如心脏搭桥手简称为大手术（例如心脏搭桥手术）术）, 中手术（例如胃切除手术）和小手术（例如阑中手术（例如胃切除手术）和小手术（例如阑尾手术）尾手术）. 每种手术所需的人数和费用如下表每种手术所需的人数和费用如下表:手术手术主刀医师主刀医师麻醉师麻醉师配合医师配合医师器械护士器械护士大大3112中中2111小小1101手术手术巡回护士巡回护

88、士所需时间所需时间平均费用平均费用大大21天天3万万中中2半天半天1.6万万小小15个个/天天3千千资源数据表资源数据表 现在医院的人员基本情况如下现在医院的人员基本情况如下: 高级医师高级医师21人人, 普通医师普通医师44人人. 只有高级医师才可以只有高级医师才可以充人大充人大, 中手术的主刀医师中手术的主刀医师. 护士护士100人人, 其中只有其中只有60人人可以充当器械护士可以充当器械护士, 麻醉师麻醉师30人人.1.假定各种外科手术的病人足够多假定各种外科手术的病人足够多, 如何安排每天的日如何安排每天的日常手术使得其经济效益最高常手术使得其经济效益最高?2.若做手术的病人分布不均若

89、做手术的病人分布不均, 如大手术并不常见如大手术并不常见, 而小而小手手术则可能较多术则可能较多, 要求做小手术的病人在手术完成之前一要求做小手术的病人在手术完成之前一直占据着医院的床位直占据着医院的床位, 如若床位有限如若床位有限, 小手术要求一周小手术要求一周内完成内完成, 否则病人要求转院否则病人要求转院. 问如何制定一个医院的每问如何制定一个医院的每周手术安排计划周手术安排计划?3.充分考虑社会效益和经济效益充分考虑社会效益和经济效益, 如何在原来的计划上如何在原来的计划上作尽可能小的调整作尽可能小的调整, 满足急症病人的需要满足急症病人的需要. 问题分析问题分析 在第一种情况下在第一

90、种情况下, 需要确定各种手术方案需要确定各种手术方案, 目标是使目标是使得相应的收益达到最大得相应的收益达到最大, 而并不考虑实际情况而并不考虑实际情况. 因问题因问题假设是有足够多的病人可供选择假设是有足够多的病人可供选择. 设设 是每天进行的大手术的人数是每天进行的大手术的人数, 是每天进行的中是每天进行的中手术的人数手术的人数, （为使问题简单（为使问题简单, 是实际进是实际进行中手术的人数行中手术的人数, ） 是进行小手术的人数是进行小手术的人数. 则目标函则目标函数为数为 再考虑资源的要求再考虑资源的要求:高级医师高级医师: 假设小手术中由高级医师主刀的有假设小手术中由高级医师主刀的

91、有 个个, 而有普通医师而有普通医师主刀的有主刀的有 个个, 普通医师普通医师: 麻醉师麻醉师: 器械护士器械护士: 护士总需要护士总需要:另外另外,所有的所有的 都必须取正整数都必须取正整数. 由此得到相应的数由此得到相应的数学学模型为模型为为正整数为正整数.由由Lingo程序程序, 得到该问题的解得到该问题的解总收益为总收益为 单位单位: 万元万元.结果分析结果分析: 在这样的安排下在这样的安排下, 大手术没有安排（想一大手术没有安排（想一下下原因是什么原因是什么?） 高级医师进行的都是中手术高级医师进行的都是中手术. 中手术一中手术一个完成了个完成了20个个. 小手术安排了小手术安排了1

92、00个个, 均是由普通医师均是由普通医师主主刀的刀的. 此时医师的使用情况是此时医师的使用情况是: 高级医师高级医师20, 普通医师普通医师30, 麻醉师麻醉师30. 器械护士器械护士30, 巡回护士巡回护士40. 2.在第种情况下在第种情况下, 没有安排大手术没有安排大手术, 这显然不合理这显然不合理. 由由于大手术并不多见于大手术并不多见, 故可以考虑在周末安排一到两个大故可以考虑在周末安排一到两个大手术手术. 如果尽安排一个大手术的情况下如果尽安排一个大手术的情况下, 相应问题的解相应问题的解为为:总收益为总收益为 单位单位: 万元万元. 对小手术的安排对小手术的安排, 不妨可以规定不妨

93、可以规定: 在需要进行小手术在需要进行小手术的病人住院后的病人住院后, 5天内一定要安排手术天内一定要安排手术. 对结果的分析对结果的分析, 可以发现可以发现, 开刀医生资源并没有充分开刀医生资源并没有充分利用利用. 造成这一现象的关键原因是麻醉师不够（当然还造成这一现象的关键原因是麻醉师不够（当然还得考虑病区内有值班医师和护士的存在）得考虑病区内有值班医师和护士的存在）. 但如果从增但如果从增加效益的角度来说加效益的角度来说, 提高社会效益和医院效益的一个方提高社会效益和医院效益的一个方法是增加麻醉师法是增加麻醉师.例如当把麻醉师的数量从例如当把麻醉师的数量从30增加到增加到35人时人时,

94、相应问题的解为相应问题的解为总收益为总收益为 单位单位: 万元万元.不断改变麻醉师的数量不断改变麻醉师的数量, 可以发现当麻醉师数量上升到可以发现当麻醉师数量上升到45人时人时, 解不再变化解不再变化. 问题的解为问题的解为总收益为总收益为 单位单位: 万元万元.六、练习六、练习 1.用长度为用长度为500厘米的条材厘米的条材, 分别截成长度为分别截成长度为98厘米与厘米与78厘米的两种毛坯厘米的两种毛坯, 前者需要前者需要1000根根, 后者需要后者需要2000根根.问因如何截取问因如何截取, 才能使才能使余料最少余料最少?使用的原料最少使用的原料最少?试建立相应的模型试建立相应的模型, 并

95、用并用Lingo软件求解软件求解.2.某商店拟制定某种商品某商店拟制定某种商品712月的进货、销售计划月的进货、销售计划.已已知商店最大库存量为知商店最大库存量为1500件件, 6月底已有存货月底已有存货300件件, 年年底的库存以不少于底的库存以不少于300件为宜件为宜. 以后每月进货一次以后每月进货一次, 假假设各月份该商品买进设各月份该商品买进, 售出单价如下表售出单价如下表, 若每件每月的若每件每月的库存费为库存费为0.5元元, 问各月进货问各月进货,售货多少件售货多少件, 才能使净收益才能使净收益最大最大,试建立数学模型试建立数学模型, 并求解并求解.月月789101112买进买进(

96、元元/件件)282625272423.5卖出卖出(元元/件件)2927262825253.某货船的载重量为某货船的载重量为12000吨吨, 总容积为总容积为45000 冷藏冷藏容积为容积为3000 可燃性指数的总和不得超过可燃性指数的总和不得超过7500, 准备准备装装6种货物种货物, 每种货物的单价每种货物的单价, 重量重量, 体积和可燃性指数体积和可燃性指数如下表如下表, 试确立相应的装货方案试确立相应的装货方案, 使价值最高使价值最高.货物货物重量重量体积体积可燃性可燃性是否冷藏是否冷藏单价单价0.21.21是是500.52.32否否1000.53.04否否1500.124.51是是10

97、00.255.23否否2500.56.49否否200 4.城市消防站的选址问题城市消防站的选址问题 设设 城市人口分布在城市人口分布在 个区中个区中, 第第 区的人口为区的人口为 要要建若干个消防站建若干个消防站, 它们的位置只能从它们的位置只能从 个位置中选定个位置中选定, 令令 表示从第表示从第 区的中心到第区的中心到第 个位置的距离个位置的距离. 要要求每个区由一个消防站管辖求每个区由一个消防站管辖, 同时不容许某个区被分配同时不容许某个区被分配给一个不设消防站的点管辖给一个不设消防站的点管辖. 用用 表示第表示第 区（中心）区（中心）到分配管辖它的消防站的距离到分配管辖它的消防站的距离, 表示第表示第 个服务点的个服务点的总人口数总人口数, 在第在第 点建立一个服务于人口总数为点建立一个服务于人口总数为 的消的消防站所虚费用为防站所虚费用为 可用于建消防站的总费用不得可用于建消防站的总费用不得超过超过 万元万元,若要求各区中心离可分配管辖该区的消防站若要求各区中心离可分配管辖该区的消防站最远的距离为最小最远的距离为最小, 试建立相应的数学模型试建立相应的数学模型. 对此问题对此问题, 拟定一组数据拟定一组数据, 并根据该数据并根据该数据, 验证你所建立的模型的验证你所建立的模型的合理性合理性.5.求函数求函数的梯度的梯度, Hessian阵和极小点阵和极小点.