数学规划模型课件.pptx

《数学规划模型课件.pptx》由会员分享，可在线阅读，更多相关《数学规划模型课件.pptx（240页珍藏版）》请在三一办公上搜索。

1、第四章 数学规划模型,1,感谢你的观看,2019年6月13,一、数学规划模型,1.模型的建立,问题1 某厂利用甲,乙,丙,丁四种设备生产A,B,C三种产品,相关数据如表所示.已知这三种产品的单件利润分别是4.5,5,7（百元）,试问该厂应如何安排生产可获得最大利润?,2,感谢你的观看,2019年6月13,3,感谢你的观看,2019年6月13,甲,乙,丙,丁,注意到变量 代表的是产品的产量,故有抽去所给问题的具体意义,我们得到原问题的数学关系为,4,感谢你的观看,2019年6月13,分析,该问题的关键所在是确定每种产品的产量,为此以 表示三种产品的产量,则目标为,在一个生产周期中,每种设备所提供

2、的工时为有限的,故对四种设备而言还应该满足下列条件:,5,感谢你的观看,2019年6月13,非负性,6,感谢你的观看,2019年6月13,用Lingo软件可以得到相应问题的解.启动Lingo,在窗口下中输入下列程序:,保存完之后执行Lingo菜单下的Solve命令,得到相应的解.,7,感谢你的观看,2019年6月13,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.0000

3、00 2 0.000000 1.357143 3 57.14286 0.000000 4 0.000000 0.2142857 5 0.000000 0.4642857,8,感谢你的观看,2019年6月13,问题2 某车间要制造100套钢筋架,每套需要长为2.9 2.1 1.5 的钢筋各一根.已知原料钢筋长度为7.4 问如何切割钢筋,使得钢筋的利用率为最高?,分析 该问题的要点是如何切割钢筋,使得每次切割之后,剩下的余料为最少?,假设在切割过程中,我们不考虑钢筋的损耗,并考虑各种切割方案:,9,感谢你的观看,2019年6月13,10,感谢你的观看,2019年6月13,非负性,11,感谢你的观看

4、,2019年6月13,从分析中可以看出,此问题的关键是确定每种方案下的余料数.,设 表示第 种方案中使用的原料钢筋数,则余料数为,而相应的限制条件为,12,感谢你的观看,2019年6月13,故原问题的数学关系式为,非负性,13,感谢你的观看,2019年6月13,在Lingo下得到该问题的解为,14,感谢你的观看,2019年6月13,运行后得到该问题的解为,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,15,感谢你的观看,2019年

5、6月13,线性规划的模型一般可表示为,非负性,16,感谢你的观看,2019年6月13,注 线性规划的目标函数还可以用min来表示,表示追求目标函数的最小值.而 表示约束条件:（Subject to）.,17,感谢你的观看,2019年6月13,问题3 要从甲地调出物质2000吨,从乙地调出物质1100吨,分别供给 地1700吨,地11吨,地200吨和 100吨,已知每吨运费如表所示,试建立一个使运费达到最小的调拨计划.,单位路程运费表,18,感谢你的观看,2019年6月13,分析 设从第 个产地到第 个销地的运输量为 运输成本为 则问题的目标函数为,由于从第一个产地调出的物质的总和为第一个产地的

6、产量,即有,同理,有,19,感谢你的观看,2019年6月13,对称地,对销地而言,有关系,由此得到该问题的数学模型,20,感谢你的观看,2019年6月13,21,感谢你的观看,2019年6月13,注 该问题又称为运输问题.运输问题的一般形式可写成,其中 是第 个产地的产量,是第 个销地的需求量.,22,感谢你的观看,2019年6月13,在上面的关系中,有,相应的运输问题称为产销平衡的运输问题.若产销不平衡,应该如何处理?为什么总是假定产销是平衡的.,23,感谢你的观看,2019年6月13,问题4 随机规划模型,决策者要建造一座水库,使水库的容量 在满足给定的限制条件下达到最小,以使其造价最小.

7、,分析 1.在一年中的第 个季节水库应留出一定的容量 以保证洪水的注入.由于洪水量是一个变数,故假定以较大的概率 使得,其中 为第 个季节的储水量.,24,感谢你的观看,2019年6月13,2.为保证灌溉,发电,航运等用水供应,水库在每个季节应能保证一定的放水量 考虑到这仍然是一随机因数,要求满足满足这一条件的概率不小于 即,其中 为第 个季节的可放水量.,3.为保证水库的安全和水生放养,水库还应有一定的储水量 即,25,感谢你的观看,2019年6月13,由此得到相应问题的数学模型为:,26,感谢你的观看,2019年6月13,问题5 某公司准备派 个工人 去完成项工作 已知第 个工人完成第 工

8、作的效率为 求如此的一个指派方案,使工人完成这些工作的效率为最大.,该问题可用一个网络图 来表示:其中 表示顶点集,是边集,是权集.该问题即是从 的每一个顶点,找出唯一的一条到 的某一个 的边,使得权之和为最大.,27,感谢你的观看,2019年6月13,模型建立,若以 表示在顶点 存在边,否则则目标函数可表示为,而从 的每一个顶点 只能作一条边等价于,同样,连 惟一的一条边等价于,28,感谢你的观看,2019年6月13,由此得到相应的数学模型为,29,感谢你的观看,2019年6月13,这样的规划又称为0-1规划.,注1 很多实际问题都可以转化成这样的模型.例如游泳接力队员的选拔.,注2 当人数

9、和工作数不相同时,这样的问题应该如何求解,又当 时,并且容许一个人能完成两件工作,又该如何解决?,30,感谢你的观看,2019年6月13,31,感谢你的观看,2019年6月13,32,感谢你的观看,2019年6月13,二、模型的求解,33,感谢你的观看,2019年6月13,例1 一奶制品加工厂用牛奶生产 两种奶制品,1桶牛奶可以在设备甲上用12小时加工生产3公斤 或则在设备乙上用8小时加工成4公斤 根据市场需要,生产的 全部能售出,且每公斤 获利24元,每公斤 可获利16元.现在加工厂每天能得到50桶牛奶的供应,每天工人总的劳动时间为480小时,并且设备甲每天至多能加工100公斤 设备乙的加工

10、能力没有限制.试为该厂制定一个生产计划,使每天获利最大,并进一步讨论以下3个附加问题:,34,感谢你的观看,2019年6月13,若用35元可以买到1桶牛奶,应否作这项投资?若投资,每天最多购买多少桶牛奶?,若可以聘用临时工人以增加劳动时间,付给临时工人的工资最多是每小时几元?,由于市场需求变化,每公斤 的利润增加到30元,应否改变生产计划?,35,感谢你的观看,2019年6月13,解 设 表示这两种产品每天所消耗牛奶的数量（单位：桶）.则用于生产 的牛奶可获利用于生产 的牛奶可获利 则目标函数为,限制条件分别为:,对原料的限制:,劳动力的限制,设备甲的开工限制,36,感谢你的观看,2019年6

11、月13,由此得到相应的规划模型,37,感谢你的观看,2019年6月13,对每一约束条件,在第一象限中确定坐标点的范围,最终确定解的范围可行域（多边形区域）;,模型求解,解法1（图解法）,确定等值线（图中用虚线），则最优解为可行域与等值线的最后交点（即图中点的 坐标）即为所求问题的最优解.,38,感谢你的观看,2019年6月13,39,感谢你的观看,2019年6月13,为此求解方程,容易得到该方程的解为,40,感谢你的观看,2019年6月13,解法2（单纯形方法）,原规划的标准型为,41,感谢你的观看,2019年6月13,42,感谢你的观看,2019年6月13,43,感谢你的观看,2019年6月

12、13,解法3（利用计算机软件）,在软件Lingo8下进行求解:,输入命令,44,感谢你的观看,2019年6月13,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,得到的解为,45,感谢你的观看,2019年6月13,结果分析,三个约束条件的右端视为“资源”:原料,劳动时间,设备甲的加工

13、能力.对当前解而言,前两种“消耗殆尽”，而设备甲尚余40公斤的加工能力.,目标函数可以看作为是“效益”.成为紧约束的资源一旦增加,则“效益”必然增加.解中列出的“对偶”价格表示紧约束“资源”每增加一个单位后相应“效益”的增加值.,46,感谢你的观看,2019年6月13,原料每增加一个单位,利润可增加48个单位;而劳动时间每增加一个单位,利润可增加2个单位.而非紧约束资源的增加,不会带来相应的收益.这种“资源”潜在价值被称为“影子”价格.,用“影子”价格即可回答附加问题.,用35元购买一桶牛奶,低于牛奶的影子价格,故可以做这项投资;临时工人每小时的工资不超过2元.而设 备甲尚有富裕能力,故增加工

14、时不会产生效益.,47,感谢你的观看,2019年6月13,目标函数的系数发生变化对最优解和最优值的影响.在图解法中可以看到，价值系数 对最优解会产生一定的影响.因为 确定了等值线的斜率,原问题等值线的斜率为,当斜率上升到 则最优解将会改变,此时最优解将在 点取得.,48,感谢你的观看,2019年6月13,灵敏度分析还给出了各个系数的范围:的上界为24,下界为8,即当 时,最优解不变;同样当 时,最优解不变.,从图中还可以看出,原料（牛奶）的增加,对应的是直线 的向右的平移,此时最优解仍为点 但当 与 重合时,最优解将不再改变,49,感谢你的观看,2019年6月13,此时,而由“影子”价格知:原

15、料每增加一个单位利润将增加48个单位.此时总利润为,同样,当劳动力资源增加时,即直线 向右移动时,最优解也将改变,但当 两点重合时,最优解将不再改变.由“影子”,50,感谢你的观看,2019年6月13,价格,劳动力每增加一个工时,效益增加2个单位.但劳动力最多增加53个单位.,因设备甲仍有富余工时,因而设备的加工能力无需再增加,其“影子”价格为零.,根据上面的分析,可以回答原问题中提出的相关问题.,可以批准用每桶35元的价格再购买部分牛奶,但最多再购买10桶;,可以以用低于每小时2元的工资聘用临时工人以增,51,感谢你的观看,2019年6月13,劳动时间,但最多不得超过53小时.,52,感谢你

16、的观看,2019年6月13,例2 奶制品的销售计划,例1给出的 两种奶制品的生产条件,利润及工厂的资源限制不变,为增加工厂的获利,开发了奶制品的深加工技术:用2小时和3元加工费,可将1公斤 加工成0.8高级奶制品 也可将一公斤 加工成0.75公斤高级奶制品 每公斤 能获利44元,每公斤 能获利32元,试为该厂制定一个生产销售计划,使获得的利润最大,并讨论以下问题:,53,感谢你的观看,2019年6月13,若投资32元可以增加供应一桶牛奶,投资3元可以增加一小时劳动时间,应否作这样的投资,若每天投资150元,可赚回多少?,每公斤高级奶制品 的获利经常有10%的波动,对指定计划有无影响,若每公斤

17、的获利下降10%,计划应该改变吗?,54,感谢你的观看,2019年6月13,问题分析,要求指定生产计划,关键是确定各产品的产量,而目标函数为销售这些产品之后可获得的利润.,55,感谢你的观看,2019年6月13,建立模型,设每天销售 公斤 公斤 公斤 公斤 用 公斤 加工 公斤 加工,目标函数,56,感谢你的观看,2019年6月13,约束条件,原料供应 每天生产 公斤,用牛奶 桶,每天生产 公斤,用牛奶 桶,两者之和不超过50桶;,劳动时间 每天生产 的时间分别为 加工 的时间分别为 两者之和不超过480小时;,设备能力 的产量 不得超过设备甲每天的,57,感谢你的观看,2019年6月13,加

18、工能力100公斤;,非负约束,附加约束 1公斤 加工成 公斤 即同样,由此得到模型,58,感谢你的观看,2019年6月13,59,感谢你的观看,2019年6月13,模型求解,用Lingo软件,进行求解,得,Variable Value Reduced Cost X1 0.000000 1.680000 X2 168.0000 0.000000 X3 19.20000 0.000000 X4 0.000000 0.000000 X5 24.00000 0.000000 X6 0.000000 1.520000,60,感谢你的观看,2019年6月13,Row Slack or Surplus Du

19、al 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 Coefficient Increase Decrease X1 24.00000 1.680000 INFINITY,61,感谢你的观看,2019年6月

20、13,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,62,感谢你的观看,2019年6月13,结果分析,由输出的结果知,约束2和3的“影子”价格分别是 和 即每增加一桶牛奶可使净利润增加,元,增加1小时劳动时间,可是利润增加 元,所以应该投资 元增加一桶牛奶或投资3元增加一小时劳动时间.若每天投资 元,增加供应5桶牛奶,可获利,元,63,感谢你的

21、观看,2019年6月13,但约束2的增加值最多不超过120,意味牛奶的桶数最多不超过10桶.,在灵敏度分析的报告中,目标函数系数的变化范围分别为,64,感谢你的观看,2019年6月13,由此可见,当 的价格向下波动 或 的价格向上波动 都会影响到最优解.,65,感谢你的观看,2019年6月13,问题的提出 钢铁、煤、水电等生产、生活物资从若干供应点运送到一些需求点，怎样安排运输，使运费为最小、或者利润为最大.某种类型的货物由于需要装箱,故要考虑如何搭配使利用率达到最高,诸如此类的问题都牵涉到一些具体的数学模型,这目讨论两个问题,并利用相应的数学规划模型加以解决.,三、应用举例,66,感谢你的观

22、看,2019年6月13,题1 自来水的输送问题,某市有甲、乙、丙、丁四个居民区,自来水由三个水库供应,四个区每天必须得到保证的基本用水量分别为 千吨,但由于水源紧张,三个水库每天最多只能分别供应 吨自来水,并由于地区位置的差别,自来水公司从各水库向各区送水所需付出的引水管理费不同（见表）,其它管理费用都是 千吨,根据公司规定,各区用户按统一标准 千吨收费,此外,四个区都向公司申请了额外用水量,分,67,感谢你的观看,2019年6月13,分别为每天 千吨,该公司应如何分配供水量,才能获利最多?,68,感谢你的观看,2019年6月13,为了增加供水量,自来水公司正在考虑进行水库改造,随三个水库的供

23、水量都提高一倍,问此时供水方案应如何改变?公司利润可增加多少?,69,感谢你的观看,2019年6月13,分析,问题的关键是如何安排从各个水库向四个居民区供水,使得引水管理费用达到最小,注意到其它费用与供水安排无关.,70,感谢你的观看,2019年6月13,模型建立,设决策变量为 三个水库 向甲、乙、丙、丁 四个区的供水量,设水库 向 区的日供水量为 并注意到 由条件得,由于需求量大于供水量,需求限制可表示为,71,感谢你的观看,2019年6月13,72,感谢你的观看,2019年6月13,在Lingo下得到问题的解.,Variable Value Reduced Cost X11 0.00000

24、0 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,73,感谢你的观看,2019年6月13,即:该问题的解为,此时引水管理费为 元,利润为,元.,74,感谢你的观看,2019年6月13,讨论

25、,如果 三个水库的每天最大供水量都增加一倍,则公司总供水能力为 千吨,水库供水量超过总需求量,故此时需要计算三个水库向甲、乙、丙、丁四个区供应每千吨水的净利润，即有表2,75,感谢你的观看,2019年6月13,从水库向各区送水的净利润,76,感谢你的观看,2019年6月13,由此得到目标函数为,约束条件为：,77,感谢你的观看,2019年6月13,78,感谢你的观看,2019年6月13,在Lingo下得到问题的解：,Variable Value Reduced Cost X11 0.000000 25.00000 X12 100.0000 0.000000 X13 0.000000 30.00

26、000 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,79,感谢你的观看,2019年6月13,Row Slack or Surplus Dual Price 1 93400.00 1.000000 2 0.000000 305.0000 3 0.000000 305.0000 4 0.0000

27、00 250.0000 5 0.000000 10.00000 6 0.000000 15.00000 7 0.000000-45.00000 8 0.000000-5.000000,80,感谢你的观看,2019年6月13,81,感谢你的观看,2019年6月13,题2 货机装运问题,问题 某种货机有三个货舱:前舱、中舱、后舱.三个货舱所能装载的货物的最大重量和体积都有限制,如表所示,并且为了保持飞机的平衡,三个货舱中实际装载货物的重量必须与其最大容许重量成正比.,82,感谢你的观看,2019年6月13,现有四种货物供该货机本次飞行装运,有关信息如表,最后一列表示装运后获得的利润.,83,感谢你

28、的观看,2019年6月13,假设,1.每种货物可以进行任意的分割;,2.每种货物可以在一个或多个货舱中任意分布;,3.每种货物可以混装,并保证不留空隙.,84,感谢你的观看,2019年6月13,应如何安排装运,使该货机本次装运的利润最大?,85,感谢你的观看,2019年6月13,模型建立,决策变量 表示第 种物资装入第 个货舱的重量,货舱 分别表示前、中、后舱.,目标函数表示一次运送后的总利润,即有,约束条件有如下的:,86,感谢你的观看,2019年6月13,总重量约束,三个货舱的重量限制,87,感谢你的观看,2019年6月13,三个货舱的空间限制,平衡限制,88,感谢你的观看,2019年6月

29、13,模型求解.,在Lingo下,可得到模型的解为:,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,89,感谢你的观看,2019年6月13,Variable Value Reduced Cost X32 12.94737 0.000000 X33 0.000000 0.000000

30、 X41 0.000000 650.0000 X42 3.052632 0.000000 X43 0.000000 650.0000,最大利润为,90,感谢你的观看,2019年6月13,题3 汽车生产问题,一汽车厂生产小、中、大三种类型的汽车,已知各类型每辆车对钢材、劳动时间的需求,利润以及每月工厂,劳动时间的现有量入表所示,试指定月生产计划,使工厂每月的利润最大.,91,感谢你的观看,2019年6月13,模型的建立,设每月生产小、中、大型汽车的数量分别为工厂的月利润为 假定在生产周期中,各项指标不变,则有相应的线性规划:,92,感谢你的观看,2019年6月13,模型求解,该问题的整数解为,9

31、3,感谢你的观看,2019年6月13,讨论,若增加附加条件:每种汽车如果生产的话,则至少生产80辆,则生产计划应该做如何修改?,分析:根据条件,对决策变量的限制改为如下几种:,94,感谢你的观看,2019年6月13,对得到的每一个解进行讨论,最后确定最大值解.,最优解为,95,感谢你的观看,2019年6月13,注 在Lingo下,求整数解的命令为 变量名,方法二 用 规划,在问题中,引入待定常数 其中 为任意的的正数,（在具体问题中可以确定）,96,感谢你的观看,2019年6月13,Global optimal solution found at iteration:31 Objective

32、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 Y2 1.000000 0.000000 Y3 0.000000 0.000000,97,感谢你的观看,2019年6月13,题4 原料采购与加工,问题 某公司用两种原油（和）混合加工成两种汽油（甲和乙）,甲、乙两种汽油含原油的最低比例分别为 每吨售价分别为 元和 元,该公司还有原油 和 的库存量分别为 吨和吨,另外还可以从市场上买到不超过 吨的

33、原油原油 的市场价为:购买不超过 吨时的单价为 吨,购买量超过 吨但不超过 吨时,超过部分 吨,超过 吨的部分,吨.该公,98,感谢你的观看,2019年6月13,司应如何安排原油的采购和加工?,99,感谢你的观看,2019年6月13,问题分析,公司安排原油的采购和加工,其目的是为了取得最大利润,但问题的困难之处在于原油 的采购价与采购量的关系比较复杂.,100,感谢你的观看,2019年6月13,模型建立,设原油的购买量为 则由题意,购买成本函数为,但这样的函数过于复杂,为了是问题尽可能简单,我们引入多个变量来刻画:,101,感谢你的观看,2019年6月13,分别以 表示以 吨,吨,吨采购得到的

34、原油 的采购量,则当以 吨的价格采购到原油时,总有 故相应的条件可表示为,同样,当以价格 吨的价格购买到了 吨原油 时,有,此外,变量 还应满足,102,感谢你的观看,2019年6月13,假设:用于生产甲、乙两种汽油的原油 的数量分别为 用于生产甲、乙两种汽油的原油 的数量分别为 则总收入为,而成本函数 可表达为,约束条件为,103,感谢你的观看,2019年6月13,以及非负限制,总结上面的分析,得到相应的模型为,104,感谢你的观看,2019年6月13,105,感谢你的观看,2019年6月13,模型求解,利用Lingo,得到问题的解为,Variable Value Reduced Cost

35、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,106,感谢你的观看,2019年6月13,解法二:采用 规划,令 分别表示以 吨、吨、吨,则约束条件可转化为,107,感谢你的观看,2019年6月13,用Lingo软件得到问题的解为,Variable Value Reduced Cost X11 0.000000 0.000000 X21 0

36、.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.000 Y3 1.000000 1000.000,108,感谢你的观看,2019年6月13,即问题的解为,109,感谢你的观看,2019年6月13,题5 接力队的选拔,问题的提出:在实际工作中,经常会遇到下面的问题:有若干项工作要分配给某些人去完成.在分配的过程中,要尽可能发

37、挥每个人的长处,以取得最大效益.这样的问题就称为指派问题.通过下面的例子我们来说明如何求解这样的指派问题.,110,感谢你的观看,2019年6月13,问题,某班准备从5名游泳队员中选拔4人组成一个接力队,参加学校的 混合泳接力赛.5名队员的4种泳姿的成绩如表所示,问应该如何选拔?,111,感谢你的观看,2019年6月13,5名队员4种泳姿的百米最好成绩,112,感谢你的观看,2019年6月13,问题分析,解决该问题的关键,是从5名队员中选出4名队员,组成接力队,每名队员完成一种泳姿,且4人的泳姿各不相同,但使总成绩为最好.一种方法是穷举法,但这种方法当 较大时是不可接受的.我们用 规划来解决这

38、个问题.,113,感谢你的观看,2019年6月13,以 表示5名队员,表示4种泳姿,以 表示第 名队员游第 种泳姿的最好成绩,则有,114,感谢你的观看,2019年6月13,115,感谢你的观看,2019年6月13,引入 变量 若选择队员 去参加泳姿 的比赛,则记 其它情况,记 且应该满足如下的约束条件:,1.每人最多只能入选4种泳姿之一，即,2.每种泳姿必须有一人也只能有一人入选，即,116,感谢你的观看,2019年6月13,当队员 选泳姿 时，相应的 表示他的成绩,否则 因此,即为所求求的目标函数.从而该问题的规划模型为,117,感谢你的观看,2019年6月13,118,感谢你的观看,20

39、19年6月13,用Lingo软件求解该问题.,该问题的解为,119,感谢你的观看,2019年6月13,120,感谢你的观看,2019年6月13,题6 选课策略,某学校规定，运筹学专业的学生毕业时至少学习过两门数学课，三门运筹学课和两门计算机课，这些课程的编号、名称、学分、所属类别和先修课要求如表所示，那么毕业时学生最少可以学习这些课程中的哪些课程？,如果某个学生既希望选修课程的数量少，又希望所获得的学分多，他可以选修哪些课程？,121,感谢你的观看,2019年6月13,122,感谢你的观看,2019年6月13,123,感谢你的观看,2019年6月13,模型建立,设 表示选修课表中按编号顺序的9

40、门课程（表示不选这门课程,）则问题的目标为选修课程为最少,即,约束条件有,1.至少选修两门数学课,三门运筹学课和两门计算机课,即,124,感谢你的观看,2019年6月13,此外,某些课程有先选的要求,例如对最优化方法而言,必须先选微积分和线性代数线性代数.即应该满足 从而得到约束条件关系,同样,对其它选修课程的先选关系也可得到相应的约束条件,整理后得到,125,感谢你的观看,2019年6月13,由此得到相应的规划为,126,感谢你的观看,2019年6月13,127,感谢你的观看,2019年6月13,在Lingo下面对问题进行求解,得到解为,若在考虑选修课时达到最小的同时,还希望所得到的学分达到

41、最大,则增加目标函数,128,感谢你的观看,2019年6月13,为此引入目标函数向量 最终得到目标函数,但是得到问题的解发现选修的课程门数多于6门而达到7门,如果所考虑的问题是优先门数的话,则再增加限制条件,129,感谢你的观看,2019年6月13,则得到问题的解为,而此时相应的学分为,130,感谢你的观看,2019年6月13,题7 销售代理的开发与中断,问题 某公司正在考虑在某城市开发一些销售代理业务.经过预测,该公司已经确定了该城市未来5年的业务量,分别为 该公司已经初步物色了4家销售公司作为其代理候选企业,下表给出了该公司与每个候选企业代理关系的一次性费用,以及每个应该与哪些候选企业建立

42、代理关系?,131,感谢你的观看,2019年6月13,132,感谢你的观看,2019年6月13,如果该公司目前已经和上述4个代理建立了代理关系,并且都处于运行状态,但每年初可以决定临时中断或重新恢复代理关系,每次临时中断或恢复代理关系的费用如下表所示,该公司应如何对这些代理进行业务调整?,133,感谢你的观看,2019年6月13,模型的建立,首先考虑问题的前半部分:以 表示公司在第年与公司 首次建立代理关系（则表示不建立代理关系）.,目标函数为这5年中的总费用,则总费用为建立代理关系的一次性费用及每年的运行费用,其中建立代理关系的一次性费用为,134,感谢你的观看,2019年6月13,由于第一

43、问中没有说明是否可以临时中断代理关系,故假定代理关系一旦建立,该关系将维持下去,因此对候选代理1而言,5年的总运行费用为,于是对所有的候选代理人而言,5年的总运行费用为,135,感谢你的观看,2019年6月13,由此得到问题的目标函数为,136,感谢你的观看,2019年6月13,约束条件为:公司的业务量必须由足够的代理承担,即有（第一年的业务量）,类似，对第二年的业务量，有,由此得到问题的数学模型为,137,感谢你的观看,2019年6月13,138,感谢你的观看,2019年6月13,139,感谢你的观看,2019年6月13,140,感谢你的观看,2019年6月13,得到问题的解为 其余的变量为

44、零,此意味 公司在第一年初与代理1,2建立代理关系,并在以后保持代理关系,第四年与代理4建立代理关系.最小费用为 元.,141,感谢你的观看,2019年6月13,进一步地,若建立关系之后可以中断关系,中断关系之后也可恢复关系,试在其它假设不变的情况下,求出问题的最优解.,142,感谢你的观看,2019年6月13,模型建立,仍然以 表示在第 年公司与候选代理人 在年初建立代理关系,但注意到在年初公式可以临时决定公司可以决定解除或恢复代理关系,故以 表示公司在第 年初公司与代理人 中断代理业务,而 则表示在第 年的年初公司与代理人 恢复代理人业务,则相应的目标函数为,143,感谢你的观看,2019

45、年6月13,144,感谢你的观看,2019年6月13,中断与恢复代理关系的约束表现为,注意到期初时,公司与所有代理人都有代理关系,即,又恢复关系可以表现为 即有,145,感谢你的观看,2019年6月13,146,感谢你的观看,2019年6月13,题8 饮料厂的生产与检修计划,问题 某饮料厂生产一种饮料以满足市场需要.该厂销售科根据市场预测,已经确定了未来四周该饮料厂的需求量,计划科根据本厂实际情况给出了未来四周的生产能力和生产成本,相应数据由下表所示,每周当饮料满足需求后有剩余时,要支出存储费,为每周每千箱饮料 千元,问应如何安排生产,在满足市场需要的前提下,使四周的总费用为最小.,147,感

46、谢你的观看,2019年6月13,148,感谢你的观看,2019年6月13,分析,从表中的数据中可以看出,除了第四周外,其余各周的生产能力都大于每周的需求量,即可以满足市场的需要.如果第一周,第二周按需生产,第三周多生产5千箱以弥补第四周的不足部分,可以使总的存储费用为最小,但注意到,生产成本逐月上升,因而从总成本最小的角度出发考虑问题,前几周多生产一些,可能是更好的方案.,149,感谢你的观看,2019年6月13,模型假设,设饮料厂在第一周开始时没有库存,并且假设在第四周的周末也没有库存,周末有库存时需支付一周的存储费.,150,感谢你的观看,2019年6月13,模型建立,以 表示四周的产量,

47、表示周末的库存量,则成本为,对第一周而言,产量减去库存,即为当月的需求量,即,平行的有其它的约束条件,由此得规划为,151,感谢你的观看,2019年6月13,152,感谢你的观看,2019年6月13,在Lingo下对该问题进行求解,容易得到该问题的解为:,最优解值为,153,感谢你的观看,2019年6月13,讨论,如果工厂要安排一次设备检修,检修将占用当周15千箱的生产能力,但会使检修以后每周的生产能力提高5千箱,试确定检修的时间安排.,154,感谢你的观看,2019年6月13,分析,问题的关键是确定检修的时间安排.为此引入 变量 若 则表示检修放在第 周进行,注意到此时该周的生产能力将减少1

48、5千箱,而以后各周的生产能力将增加5箱,因而要增加相应的约束条件:,155,感谢你的观看,2019年6月13,又检修只能进行一次,故还应该满足,156,感谢你的观看,2019年6月13,联合起来,得到原问题的数学规划为,157,感谢你的观看,2019年6月13,158,感谢你的观看,2019年6月13,在Lingo下,可以得到问题的解为,即检修安排在第一周,最优解值为,159,感谢你的观看,2019年6月13,题9 饮料的生产批量问题,问题 某饮料厂使用同一条生产线轮流生产多种饮料以满足市场需要.如果某周开工生产其中一种原料,就要清洗设备和更换部分部件,于是需支出生产准备费.现在只考虑一种饮料

49、的生产,假设其未来四周的需求量,生产能力,生产成本与存储费与上题相同,问如何安排这种饮料的生产,使该种饮料的总费用为最小?,160,感谢你的观看,2019年6月13,161,感谢你的观看,2019年6月13,分析,与上例相比,解决该问题的关键是要考虑与产品数量无关的生产准备费用.条件是:只要生产,就有该费用的产生.,162,感谢你的观看,2019年6月13,模型建立,首先我们对问题做一般的讨论:,将问题分为若干个阶段,用 来表示.对时段 以表示需求量,生产能力为 如果在时段 开工,则需支付准备费用 时段 末的库存为 单件存储费为 产量为 为成本,引入 变量表示该产品在该时段投入生产,否则不投入

50、生产,则目标函数为,163,感谢你的观看,2019年6月13,相应的关系为,164,感谢你的观看,2019年6月13,带回原来问题的值,得到问题的模型为,165,感谢你的观看,2019年6月13,166,感谢你的观看,2019年6月13,在Lingo下,得到问题的最优解为,167,感谢你的观看,2019年6月13,题10 钢管的下料问题,问题 某钢管零售商从钢管厂进货,将钢管按客户的要求进行切割后售出,从钢管厂进货时的长度都是19,现有一客户需要50根4 29根6 和15根8 的钢筋,应如何下料?,零售商如果采用不同的切割模式太多,将会导致生产过程的复杂化,从而增加生产和管理成本,所以该零售商