《数学建模-优化》课件.ppt

1、-数学建模基地系列课件数学建模基地系列课件-数学建模数学建模 优化专题优化专题华中农业大学数学建模基地华中农业大学数学建模基地专题板块系列专题板块系列概率统计专题概率统计专题1优化专题优化专题2模糊方法及微分方程专题模糊方法及微分方程专题3图论方法专题图论方法专题华中农业大学数学建模基地华中农业大学数学建模基地优化专题线性规划模型线性规划模型非线性规划模型非线性规划模型动态规划动态规划华中农业大学数学建模基地华中农业大学数学建模基地?,./2,5,321可可使使利利润润最最大大问问如如何何安安排排计计划划吨吨万万元元的的利利润润分分别别为为且且下下表表原原材材料料（单单位位：吨吨）如如每每吨吨

2、所所需需原原材材料料及及现现有有，两两种种产产品品，已已知知生生产产，生生产产和和，料料某某工工厂厂计计划划用用三三种种原原材材 AAA生产计划问题生产计划问题线性规划模型线性规划模型华中农业大学数学建模基地华中农业大学数学建模基地 2x1+x2 8 s.t.x1 3 x2 4 x1，x2 0 max f=5x1+2x2,:21吨吨两两种种产产品品分分别别为为设设生生产产解解xx 求最大利润求最大利润三种三种材料量的限制材料量的限制生产量非负生产量非负线性规划模型线性规划模型华中农业大学数学建模基地华中农业大学数学建模基地。问问如如何何调调运运使使运运费费最最低低如如下下公公里里单单位位距距离

3、离两两个个粮粮库库到到三三个个粮粮站站的的吨吨大大米米分分别别为为三三个个粮粮站站至至少少需需要要吨吨吨吨为为两两个个粮粮库库现现存存大大米米分分别别调调运运大大米米向向三三个个粮粮站站有有两两个个粮粮库库,):(,5,4,2,8,4,32121BBBAA运输问题运输问题线性规划模型线性规划模型华中农业大学数学建模基地华中农业大学数学建模基地解：解：设设A A1,1,A A2 2调运到三个粮站的大米分别为调运到三个粮站的大米分别为x x1 1，x x2 2，x x3 3，x x4 4，x x5 5，x x6 6吨。吨。题设量可总到下表：题设量可总到下表：线性规划模型线性规划模型华中农业大学数学

4、建模基地华中农业大学数学建模基地结合存量限制和需量限制得数学模型结合存量限制和需量限制得数学模型：65432124123082412minxxxxxxf 0,54284.654321635241654321xxxxxxxxxxxxxxxxxxts线性规划模型线性规划模型华中农业大学数学建模基地华中农业大学数学建模基地 m个产地个产地A1,Am联合供应联合供应n个销地个销地B1,Bn,各产各产地至各销地单位运价地至各销地单位运价(单位单位:元元/吨吨)为为cij，问如何调运使，问如何调运使总运费最少总运费最少?一般运输问题一般运输问题.:ijjixBA的的运运输输量量为为到到销销地地设设从从产产

5、地地解解 njmixnjbxmiaxtsxcfijjmiijinjijminjijij,.,1;,.,10,.,1,.,1,.min1111总运价总运价产量限制产量限制需量限制需量限制运量非负运量非负线性规划模型线性规划模型华中农业大学数学建模基地华中农业大学数学建模基地 njmixnjbxmiaxtsxcfijjmiijinjijminjijij,.,1;,.,10,.,1,.,1,.min1111假设假设产销平衡产销平衡:在很多实际问题中在很多实际问题中,解题思想和运输问题同出一辙解题思想和运输问题同出一辙,也就是说我们可以用运输模型解决其他问题也就是说我们可以用运输模型解决其他问题.nj

6、jmiiba11线性规划模型线性规划模型华中农业大学数学建模基地华中农业大学数学建模基地 设有设有n件件工作工作B1,B2,Bn,分派给分派给n人人A1,A2,An去去做做,每人只做一件工作且每件工作只派一个人去做每人只做一件工作且每件工作只派一个人去做,设设Ai完成完成Bj的工时为的工时为cij,问应如何分派才能完成全部工作的问应如何分派才能完成全部工作的总工时最少总工时最少.否则否则去做去做分派给分派给工作工作设设解解01:ijijABx ninjijijxcf11min ）（或或）（）（njixnixnjxtsijnjijniij,.,2,1,10,.,2,11,.,2,11.11每件每

7、件工作只派工作只派1人人每个人只派做每个人只派做1件件变量变量xi只取只取0和和1,故建立故建立的模型也称的模型也称0-1规划规划.分派问题分派问题线性规划模型线性规划模型华中农业大学数学建模基地华中农业大学数学建模基地?,1,2:),(),(),(),(),(),(),(:7,7654321的的年年利利润润最最大大问问如如何何选选择择地地址址使使公公司司元元总总投投资资不不超超过过元元每每年年可可获获利利元元投投资资若若选选个个汉汉口口汉汉阳阳至至少少个个武武昌昌至至多多并并规规定定汉汉商商二二十十一一世世纪纪行行街街步步武武广广司司门门口口亚亚贸贸中中商商个个地地址址有有拟拟议议中中汉汉阳

8、阳建建立立专专卖卖店店汉汉口口某某公公司司拟拟定定在在在在武武昌昌bcbAAAAAAAAiii 否否则则选选择择解解,0,1:iiAx 71maxiiixcf 7,.,2,110112.765432171ixxxxxxxxbxbtsiiii或或选址问题选址问题线性规划模型线性规划模型华中农业大学数学建模基地华中农业大学数学建模基地 现要做现要做100套钢架套钢架,用长为用长为2.9m、2.1m和和1.5m的元的元钢各一根钢各一根,已知原料长已知原料长7.4m,问如何下料问如何下料,使用的原材料使用的原材料最省最省?分析分析:下料方式：下料方式：最省：最省：1.所用刚架根数最少；所用刚架根数最少

9、；2.余料最少余料最少下料问题下料问题线性规划模型线性规划模型华中农业大学数学建模基地华中农业大学数学建模基地原料截成所需长度的根数下料方法所需根长2.9m211100002.1m021032101.5m10130234剩余料头0.1 0.3 0.901.1 0.2 0.8 1.4:,为为则则问问题题的的线线性性规规划划模模型型根根数数种种办办法法下下料料的的原原材材料料的的表表示示按按第第设设ixi线性规划模型线性规划模型华中农业大学数学建模基地华中农业大学数学建模基地876543214.18.02.01.109.03.01.0minxxxxxxxxf 取取整整jjxjxxxxxxxxxxx

10、xxxxxts;8,7,6,5,4,3,2,1,0100432310023321002.876431765324321不同方不同方法截得法截得每每种根种根长的长的总总数至少数至少100例例3,4中的此例的变量中的此例的变量xi只取正整数只取正整数,故建立的模型也称故建立的模型也称整数规划整数规划.0-1规划是整数规划的特殊情形规划是整数规划的特殊情形.线性规划模型线性规划模型华中农业大学数学建模基地华中农业大学数学建模基地 某公司生产某产品某公司生产某产品,最大生产能力为最大生产能力为100单位单位,每单位每单位存储费存储费2元元,预定的销售量与单位成本如下预定的销售量与单位成本如下:月份单位

11、成本(元)销售量1234 70 60 72 70 80 120 76 60求求一生产计划一生产计划,使使 1)满足需求满足需求;2)不超过生产能力不超过生产能力;3)成本成本(生产成本与存储费之和生产成本与存储费之和)最低最低.阶段生产问题阶段生产问题线性规划模型线性规划模型华中农业大学数学建模基地华中农业大学数学建模基地 1 je 解解:假定假定1月初无库存月初无库存,4月底买完月底买完,当月生产的不库当月生产的不库存存,库存量无限制库存量无限制.为为单单位位成成本本，为为存存储储费费，为为销销售售量量，月月产产量量，为为第第：设设模模型型iiiicedix jiijiidx11 31j 4

12、1jjjxc fmin第j+1个月的库存量第j+1个月的库存费共共3个月的库存费个月的库存费 4,23,110003,2,1.414111ixdxjdxtsiiiiijijiii且且为为正正整整数数到本月总生产量到本月总生产量大于等于销售量大于等于销售量4个月总生产量等个月总生产量等于总销售量于总销售量4个月总个月总生产成本生产成本线性规划模型线性规划模型华中农业大学数学建模基地华中农业大学数学建模基地.iiiiisicedix月月初初的的库库存存量量为为为为单单位位成成本本，设设第第为为存存储储费费，为为销销售售量量，月月产产量量，为为第第：设设模模型型 4141miniiiiiisexcf

13、.ts 1is,iiidxs 4,3,2,1 i0051 ss4321043211000，且为整数且为整数，且为整数，且为整数，isixii线性规划模型线性规划模型华中农业大学数学建模基地华中农业大学数学建模基地.,月月的的销销售售量量第第表表示示的的费费之之和和出出时时的的生生产产成成本本与与存存储储月月卖卖月月生生产产的的产产品品在在第第表表示示第第数数量量月月卖卖出出的的月月生生产产的的产产品品在在第第表表示示第第设设化化为为运运输输问问题题解解法法jdjicjixjijij 月份单位成本(元)销售量1234 70 60 72 70 80 120 76 60线性规划模型线性规划模型华中农

14、业大学数学建模基地华中农业大学数学建模基地76827676-80-7472-747270生产月100100100100产量产量6041207060销量销量4321321需求月费用费用cij线性规划模型线性规划模型华中农业大学数学建模基地华中农业大学数学建模基地且且为为整整数数0100.min41,411 ijijijjijijjjiijijxxdxtsxcf4,3,2,1 j4,3,2,1 i4,3,2,1,ji本题本题3个模型为整数规划模型个模型为整数规划模型.线性规划模型线性规划模型华中农业大学数学建模基地华中农业大学数学建模基地线性规划模型特点线性规划模型特点v决策变量：向量决策变量：向

15、量(x1 xn)T,决策人要考虑和控制决策人要考虑和控制的因素非负；的因素非负；v约束条件：线性等式或不等式；约束条件：线性等式或不等式；v目标函数：目标函数：Z=(x1 xn)线性式，求线性式，求Z极大或极小；极大或极小；线性规划模型线性规划模型23一般形式一般形式 0,.minmax21221122222121112121112211nmnmnmmnnnnnnxxxbxaxaxabxaxaxabxaxaxatsxcxcxcf目标函数目标函数约约束束条条件件线性规划模型线性规划模型华中农业大学数学建模基地华中农业大学数学建模基地 矩阵形式为：矩阵形式为：记记,),(212121TnTnnmi

16、jnbbbbxxxxaAcccc 0.minxbAxtscxfL称为约束矩阵。称为约束矩阵。的每一分量的每一分量指指Axxxj,00 矩阵形式矩阵形式线性规划模型线性规划模型华中农业大学数学建模基地华中农业大学数学建模基地满足约束条件的变量的值称为满足约束条件的变量的值称为可行解可行解，可行解的集合称为可行解的集合称为可行域可行域。使目标函数达到最大（小）值的可行解使目标函数达到最大（小）值的可行解称为称为最优解最优解，相应的目标函数的值称为相应的目标函数的值称为最优值最优值。线性规划模型线性规划模型华中农业大学数学建模基地华中农业大学数学建模基地线性规划问题的性质线性规划问题的性质:v比例性

17、 每个决策变量对目标函数以及右端项的贡献与该决策变量的取值成正比.v可加性 每个决策变量对目标函数以及右端项的贡献与其他决策变量的取值无关.v连续性 每个决策变量的取值都是连续的.线性规划模型线性规划模型华中农业大学数学建模基地华中农业大学数学建模基地应应 用用v市场营销(广告预算和媒介选择，竞争性定价，新产品开发，制定销售计划)v生产计划制定(合理下料，配料，“生产计划、库存、劳力综合”)v库存管理(合理物资库存量，停车场大小，设备容量)v运输问题v财政、会计(预算，贷款，成本分析，投资，证券管理)v人事(人员分配，人才评价，工资和奖金的确定)v设备管理(维修计划，设备更新)v城市管理(供水

18、，污水管理，服务系统设计、运用)线性规划模型线性规划模型华中农业大学数学建模基地华中农业大学数学建模基地线性规划问题的基本理论线性规划问题的基本理论用图解法求解线性规划问题用图解法求解线性规划问题 0,4382.25max21212121xxxxxxtsxxf2125:xxc 目标函数目标函数12252xcx 变形为：变形为：是一簇斜率为是一簇斜率为-5/2的平的平行直线族行直线族斜率为斜率为-2C/2为直线与为直线与y轴的轴的交点交点华中农业大学数学建模基地华中农业大学数学建模基地x240 x18342,3 192235max23 f最最大大值值取取得得，所所以以目目标标函函数数在在2125

19、:xxc 目标函数目标函数12252xcx 变形为：变形为：如图所示如图所示:显然直线向右上移动时，显然直线向右上移动时，与与y轴交点越高，从而轴交点越高，从而c/2越越大，使得目标函数值大，使得目标函数值c 越大。越大。线性规划问题的基本理论线性规划问题的基本理论华中农业大学数学建模基地华中农业大学数学建模基地从从上述几何直观可看出：上述几何直观可看出：线性规划问题的任意两个可行解线性规划问题的任意两个可行解联线联线上的点上的点都是可行解都是可行解；线性规划问题的任意两个最优解线性规划问题的任意两个最优解联线联线上的点上的点都是最优解；都是最优解；线性规划问题的最优值若存在，则一线性规划问题

20、的最优值若存在，则一定定在某个顶点达到在某个顶点达到。线性规划问题的基本理论线性规划问题的基本理论华中农业大学数学建模基地华中农业大学数学建模基地0,.min21221122222121112121112211nmnmnmmnnnnnnxxxbxaxaxabxaxaxabxaxaxatsxcxcxcf任何一个线性规划问题都可以化为标准形式，任何一个线性规划问题都可以化为标准形式，我们的求解方法都是针对标准形式的。我们的求解方法都是针对标准形式的。线性规划问题的基本理论线性规划问题的基本理论标准形式标准形式:华中农业大学数学建模基地华中农业大学数学建模基地如果给定的如果给定的LP问题是极大化问题

21、问题是极大化问题,即即nnxcxcxcf 2211max可可化为极小化问题化为极小化问题nnxcxcxcf 2211min约束条件不变约束条件不变,其其最优解是最优解是一致一致的的,但目标函数值的符号但目标函数值的符号相反相反.则:结论结论:如果问题是求目标函数的最大值如果问题是求目标函数的最大值,则化为求则化为求 f 的最小值的最小值;1.关于目标函数线性规划问题的基本理论线性规划问题的基本理论华中农业大学数学建模基地华中农业大学数学建模基地2.关于约束条件(1)如果给定的如果给定的LP有约束不等式有约束不等式ininibxaxa 11而而化化为为约约束束等等式式量量则则可可在在左左边边添添

22、加加剩剩余余变变,0 iyiininibyxaxa 11线性规划问题的基本理论线性规划问题的基本理论华中农业大学数学建模基地华中农业大学数学建模基地注意注意:新引入的变量在目标函数和约束条件中的系新引入的变量在目标函数和约束条件中的系数均为数均为0.(2)如果给定的如果给定的LP有约束不等式有约束不等式jnjnjbxaxa 11而而化化为为约约束束等等式式量量则则可可在在左左边边添添加加松松弛弛变变,0 jyjjnjnjbyxaxa 11线性规划问题的基本理论线性规划问题的基本理论华中农业大学数学建模基地华中农业大学数学建模基地3.3.关于变量关于变量 在标准形式中在标准形式中,所有的变量都有

23、非负限制所有的变量都有非负限制,如果某些如果某些变量没有非负限制变量没有非负限制,则称这些变量为则称这些变量为自由的自由的.两种处理办法两种处理办法:自自由由的的变变量量设设给给定定ixLP .0,:1iiiiiixvuvux替替换换消消去去自自由由变变量量令令换换成成两两个个非非负负变变量量之之差差 的的那那个个方方程程。时时去去掉掉解解出出函函数数消消去去自自由由变变量量，同同数数与与目目标标，然然后后代代入入其其他他约约束束函函在在某某个个等等式式中中解解出出iixx2线性规划问题的基本理论线性规划问题的基本理论华中农业大学数学建模基地华中农业大学数学建模基地 无无非非负负限限制制式式将

24、将下下列列问问题题化化为为标标准准形形321321321321321,0,52327.32maxxxxxxxxxxxxxtsxxxf 0,522327.32min76543215421754216542132176354xxxxxxxxxxxxxxxxxxxxxtsxxxffxxxxx和剩余变量和剩余变量松弛变量松弛变量，引入，引入替换替换解：用解：用线性规划问题的基本理论线性规划问题的基本理论华中农业大学数学建模基地华中农业大学数学建模基地行解和基最优解。行解和基最优解。并指出基解是否为基可并指出基解是否为基可解、典式与单纯形表，解、典式与单纯形表，所有的基及其相应的基所有的基及其相应的基写

25、出线性规划问题写出线性规划问题 0,743532.23min321321321321xxxxxxxxxtsxxxf线性规划问题的基本理论线性规划问题的基本理论华中农业大学数学建模基地华中农业大学数学建模基地相应的典式如下相应的典式如下:327xf 323121xxxx ,0,2,1:Tx 基解为基解为.7的的值值为为这这时时 f但但不不是是基基最最优优解解。此此解解是是基基可可行行解解，223xf 232121xxxx 125xf 131211xxxx ,1,1,0:Tx 基解为基解为最优值为最优值为5.,2,0,1:Tx基解为基解为非基可行解非基可行解是最优解，是最优解，线性规划问题的基本理

26、论线性规划问题的基本理论华中农业大学数学建模基地华中农业大学数学建模基地 1 2 3 4 5 6 7 8 96 5 4 3 2 1（2.25，3.75）1 2 3 4 5 6 7 8 96 5 4 3 2 1分枝定界法分枝定界法线性规划问题的基本理论线性规划问题的基本理论华中农业大学数学建模基地华中农业大学数学建模基地隐枚举法过滤条件检验可行目标值可行检验过滤检验(0,0,0)0(0,0,1)55(0,1,0)-2(0,1,1)3(1,0,0)3(1,0,1)88（最优）(1,1,0)1(1,1,1)63523321xxx线性规划问题的基本理论线性规划问题的基本理论华中农业大学数学建模基地华中

27、农业大学数学建模基地连续投资连续投资10万元万元A：从第从第1年年 到第到第4年每年初要投资，次年末回收年每年初要投资，次年末回收本利本利1.15B：第第3年初投资，到第年初投资，到第5年末回收年末回收1.25，最大投资，最大投资4万元万元C：第第2年初投资，到第年初投资，到第5年末回收年末回收1.40，最大投资，最大投资3万元万元D：每年初投资，每年末回收每年初投资，每年末回收1.11。求：求：5年末总资本最大。年末总资本最大。练习1:连续投资华中农业大学数学建模基地华中农业大学数学建模基地练习练习2某服务部门一周中每天需要不同数目的雇员，某服务部门一周中每天需要不同数目的雇员，周一到周四每

28、天至少需要周一到周四每天至少需要50人，周五至少需要人，周五至少需要80人，人，周六和周日至少需要周六和周日至少需要90人，现规定应聘者需连续工人，现规定应聘者需连续工作作5天，试确定聘用方案。天，试确定聘用方案。华中农业大学数学建模基地华中农业大学数学建模基地练习练习3某班准备从某班准备从5名游泳员中选择人组成接力队，名游泳员中选择人组成接力队，藏家学校的藏家学校的4100m混合泳接力比赛，混合泳接力比赛，5名队员名队员4种泳种泳姿的百米平均成绩如表，问如何选拔队员。姿的百米平均成绩如表，问如何选拔队员。队员队员甲甲乙乙丙丙丁丁戊戊蝶泳蝶泳10685721181101074仰泳仰泳11561

29、0611421142111蛙泳蛙泳1271064109610961238自由泳自由泳华中农业大学数学建模基地华中农业大学数学建模基地 线性模型题目线性模型题目1 生产计划问题生产计划问题某工厂计划安排生产，两种产品，已知每种单位产品的利润，生产单位产品所需设备台时及A,B两种原材料的消耗，现有原材料和设备台时的定额如表所示，问：）怎么安排生产使得工厂获利最大？）产品的单位利润降低到1.8万元，要不要改变生产计划，如果降低到1万元呢？）产品的单位利润增大到5万元，要不要改变生产计划？）如果产品，的单位利润同时降低了1万元，要不要改变生产计划？产品产品产品产品最大资源量最大资源量设备设备128台时

30、台时原材料原材料A4016kg原材料原材料B0412kg单位产品利润单位产品利润华中农业大学数学建模基地华中农业大学数学建模基地 线性模型建立线性模型建立华中农业大学数学建模基地华中农业大学数学建模基地 线性模型求解线性模型求解程序编写程序编写model:title 生产计划问题;maxfmax=2*x1+3*x2;Ax1+2*x28;B4*x116;TIME4*x212;END华中农业大学数学建模基地华中农业大学数学建模基地 线性模型求解线性模型求解运行结果运行结果 Model Title:生产计划问题 Variable Value Reduced Cost X1 4.000000 0.00

31、0000 X2 2.000000 0.000000 Row Slack or Surplus Dual Price MAXF 14.00000 1.000000 A 0.000000 1.500000 B 0.000000 0.1250000 TIME 4.000000 0.000000 对问题1，安排是生产产品4单位，产品2单位，最大盈利为14万元。华中农业大学数学建模基地华中农业大学数学建模基地 线性模型敏感性理论线性模型敏感性理论1目标函数的系数变化的敏感性分析目标函数的系数变化的敏感性分析如果目标函数的系数发生变化，将会影响目标函数 f 斜率的变化，但是只要f 的斜率小于等于-1/2（

32、也就是直线l夹在l1与l2之间时），最优解都在(4,2)上取到，最优解不变，从而生产计划不会变华中农业大学数学建模基地华中农业大学数学建模基地 线性模型敏感性分析线性模型敏感性分析1要使用敏感性分析要使用敏感性分析必须要在这里选择必须要在这里选择Prices&Ranges然后然后保存保存退出退出路径：路径：LINGOOptionsGeneral Solver(通用求解程序通用求解程序)选项卡选项卡华中农业大学数学建模基地华中农业大学数学建模基地 线性模型敏感性分析线性模型敏感性分析1要调出敏感性分析的结果，要调出敏感性分析的结果，必须必须先求解先求解后再后再在程序窗在程序窗口下口下点击点击LI

33、NGORange，华中农业大学数学建模基地华中农业大学数学建模基地 线性模型敏感性分析线性模型敏感性分析1Ranges in which the basis is unchanged:Objective Coefficient Ranges Current Allowable Allowable Variable Coefficient Increase Decrease X1 2.000000 INFINITY 0.5000000 X2 3.000000 1.000000 3.000000 Righthand Side Ranges Row Current Allowable Allowab

34、le RHS Increase Decrease A 8.000000 2.000000 4.000000 B 16.00000 16.00000 8.000000 TIME 12.00000 INFINITY 4.000000 当前变量系数允许增加量允许减少量对问题对问题2，产品，产品的单位利润降低到的单位利润降低到1.8万元，在（万元，在（1.5，）之间，所以不）之间，所以不改变生产计划。如果降低到改变生产计划。如果降低到1万元，不在（万元，不在（1.5，）内，要改变生产计划。）内，要改变生产计划。在程序中将目标函数的系数在程序中将目标函数的系数“2”改为改为“1”，可得新的计划为，可得新

35、的计划为安排是生产产品安排是生产产品2单位，产品单位，产品3单位，最大盈利为单位，最大盈利为11万元万元.对问题对问题3，要改变生产计划，更改程序得新计划为生产产品，要改变生产计划，更改程序得新计划为生产产品2单位，产品单位，产品3单位，最大盈利为单位，最大盈利为19万元万元.对问题对问题4，因为两个系数同时改变了，所以只有更改程序的数据，重新运，因为两个系数同时改变了，所以只有更改程序的数据，重新运行得：不改变生产计划，但是最大利润降低到行得：不改变生产计划，但是最大利润降低到8万元万元华中农业大学数学建模基地华中农业大学数学建模基地 线性模型敏感性理论线性模型敏感性理论华中农业大学数学建模

36、基地华中农业大学数学建模基地 线性模型影子价格理论线性模型影子价格理论12121112max2328416.412,0fxxxxxstxx x0,34224.12168min3213221321yyyyyyyt syyyg把y1,y2,y3作为三种原料的定价，定价的目标是在比生产产品获得更多利润的前提下的最小利润.在最优情况下，在最优情况下，y的值就是资的值就是资源的源的影子价格，影子价格，影子价格有意影子价格有意义是有范围的义是有范围的。影子价格经济含义是：在资源得到最优配影子价格经济含义是：在资源得到最优配置，使总效益最大时，该资源投入量每增置，使总效益最大时，该资源投入量每增加一个单位所

37、带来总收益的增加量加一个单位所带来总收益的增加量 华中农业大学数学建模基地华中农业大学数学建模基地 线性模型综合讨论线性模型综合讨论Ranges in which the basis is unchanged:Objective Coefficient Ranges Current Allowable Allowable Variable Coefficient Increase Decrease X1 2.000000 INFINITY 0.5000000 X2 3.000000 1.000000 3.000000 Righthand Side Ranges Row Current Allo

38、wable Allowable RHS Increase Decrease A 8.000000 2.000000 4.000000 B 16.00000 16.00000 8.000000 TIME 12.00000 INFINITY 4.000000 运行结果运行结果 Model Title:生产计划问题 Variable Value Reduced Cost X1 4.000000 0.000000 X2 2.000000 0.000000 Row Slack or Surplus Dual Price MAXF 14.00000 1.000000 A 0.000000 1.500000

39、 B 0.000000 0.1250000 TIME 4.000000 0.000000 华中农业大学数学建模基地华中农业大学数学建模基地 线性模型题目线性模型题目21桶牛奶 3公斤A1 12小时 8小时 4公斤A2 或获利24元/公斤 获利16元/公斤 50桶牛奶桶牛奶 时间时间480小时小时 至多加工至多加工100公斤公斤A1 制订生产计划，使每天获利最大制订生产计划，使每天获利最大 35元可买到元可买到1桶牛奶，买吗？若买，每天最多买多少桶牛奶，买吗？若买，每天最多买多少?可聘用临时工人，付出的工资最多是每小时几元可聘用临时工人，付出的工资最多是每小时几元?A1的获利增加到的获利增加到

40、30元元/公斤，应否改变生产计划？公斤，应否改变生产计划？每天：每天：加工奶制品的生产计划加工奶制品的生产计划华中农业大学数学建模基地华中农业大学数学建模基地 线性模型建立线性模型建立x1桶牛奶生产桶牛奶生产A1 x2桶牛奶生产桶牛奶生产A2 获利获利 243x1 获利获利 164 x2 原料供应原料供应 5021 xx劳动时间劳动时间 48081221 xx加工能力加工能力 10031x决策变量决策变量 目标函数目标函数 216472xxzMax每天获利每天获利约束条件约束条件非负约束非负约束 0,21xx线性线性规划规划模型模型(LP)华中农业大学数学建模基地华中农业大学数学建模基地 线性

41、模型求解线性模型求解Max=72*x1+64*x2;x1+x250;12*x1+8*x2480;3*x1100;OBJECTIVE FUNCTION VALUE 1)3360.000 VARIABLE VALUE REDUCED COST X1 20.000000 0.000000 X2 30.000000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2)0.000000 48.000000 3)0.000000 2.000000 4)40.000000 0.000000 NO.ITERATIONS=220桶牛奶生产桶牛奶生产A1,30桶生产桶生产A2，

42、利润利润3360元。元。华中农业大学数学建模基地华中农业大学数学建模基地 线性模型影子价格线性模型影子价格 OBJECTIVE FUNCTION VALUE 1)3360.000 VARIABLE VALUE REDUCED COST X1 20.000000 0.000000 X2 30.000000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2)0.000000 48.000000 3)0.000000 2.000000 4)40.000000 0.000000 35元可买到元可买到1桶牛奶，要买吗？桶牛奶，要买吗？35 0，初始可行点，初始可行点

43、xk,初始步长初始步长k0,在在xk线性化得线性规划问题：线性化得线性规划问题：min .0,1,0,1,TkkkTikikkTjkjkkkkfxfxxxs txxxxikxxxxjkmxx 非线性规划有约束问题非线性规划有约束问题华中农业大学数学建模基地华中农业大学数学建模基地 求出此线性规划问题得最优解求出此线性规划问题得最优解xk1，检验，检验是否为原问题的的可行解，若是转，否则缩短是否为原问题的的可行解，若是转，否则缩短步长转；步长转；判断精度。判断精度。1,kkxx 若若则取则取最优解最优解x*=xk+1,停，否则令停，否则令k=k+1转。转。12211221 min .0 0fXx

44、xs tgxxxgxx 例例：非线性规划有约束问题非线性规划有约束问题华中农业大学数学建模基地华中农业大学数学建模基地（2）罚函数法）罚函数法转化为无约束最优化问题：转化为无约束最优化问题：22min,min 0,ijF x MfxMxMx M为足够大的正数。称为为足够大的正数。称为罚因子罚因子。算法分析：算法分析：设可行域为设可行域为S，构造函数：，构造函数：20 ,1iixSuximxxS 非线性规划有约束问题非线性规划有约束问题华中农业大学数学建模基地华中农业大学数学建模基地 iixux 令令 求无约束问题得最优解为求无约束问题得最优解为X(M),直观看出，直观看出，只有当只有当X(M)

45、S才可能真正取得极小值，若才可能真正取得极小值，若 ,X MS 就就加大加大罚因子罚因子M，使，使X(M)向向S逼近，逼近，当当M时，点列时，点列 。外外趋趋于于最最优优解解从从*XSMXK非线性规划有约束问题非线性规划有约束问题华中农业大学数学建模基地华中农业大学数学建模基地计算步骤计算步骤：（第：（第k次迭代）次迭代）。优优解解，求求解解无无约约束束问问题题得得最最取取kkXM01 .,*k121转转，否则取，否则取则则若若kkkkMMXXxM 12211221 min .0 0fXxxs tgxxxgxx 例例：2111,min,2124 1TXSX MMMM 非线性规划有约束问题非线性

46、规划有约束问题华中农业大学数学建模基地华中农业大学数学建模基地 露天矿里铲位已分成矿石和岩石露天矿里铲位已分成矿石和岩石:平均铁含量不低于平均铁含量不低于25%的的为矿石，否则为岩石。每个铲位的矿石、岩石数量，以及矿石的为矿石，否则为岩石。每个铲位的矿石、岩石数量，以及矿石的平均铁含量（称为品位）都是已知的。每个铲位至多安置一台电平均铁含量（称为品位）都是已知的。每个铲位至多安置一台电铲，电铲平均装车时间铲，电铲平均装车时间5分钟。分钟。卡车在等待时所耗费的能量也是相当可观的，原则上在安卡车在等待时所耗费的能量也是相当可观的，原则上在安排时排时不应发生卡车等待不应发生卡车等待的情况。的情况。矿

47、石卸点需要的铁含量要求都为矿石卸点需要的铁含量要求都为29.5%1%(品位限制），搭品位限制），搭配量在一个班次（配量在一个班次（8小时）内满足品位限制即可。卸点在一个班小时）内满足品位限制即可。卸点在一个班次内不变。卡车载重量为次内不变。卡车载重量为154吨，平均时速吨，平均时速28km,平均卸车时间平均卸车时间为为3分钟。分钟。问题：出动几台电铲，分别在哪些铲位上；出动几辆卡车，分问题：出动几台电铲，分别在哪些铲位上；出动几辆卡车，分别在哪些路线上各运输多少次别在哪些路线上各运输多少次?露天矿生产的车辆安排露天矿生产的车辆安排(CUMCM-2003B)华中农业大学数学建模基地华中农业大学数

48、学建模基地 露天矿生产的车辆安排露天矿生产的车辆安排(CUMCM-2003B)华中农业大学数学建模基地华中农业大学数学建模基地距离距离铲位铲位1铲位铲位2铲位铲位3铲位铲位4铲位铲位5铲位铲位6铲位铲位7铲位铲位8铲位铲位9铲位铲位10矿石漏矿石漏5.265.194.214.002.952.742.461.900.641.27倒装倒装1.900.991.901.131.272.251.482.043.093.51岩场岩场5.895.615.614.563.513.652.462.461.060.57岩石漏岩石漏0.641.761.271.832.742.604.213.725.056.10倒装

49、倒装4.423.863.723.162.252.810.781.621.270.50铲位铲位1铲位铲位2铲位铲位3铲位铲位4铲位铲位5铲位铲位6铲位铲位7铲位铲位8铲位铲位9铲位铲位10矿石量矿石量095105100105110125105130135125岩石量岩石量125110135105115135105115135125铁含量铁含量30%28%29%32%31%33%32%31%33%31%露天矿生产的车辆安排露天矿生产的车辆安排(CUMCM-2003B)华中农业大学数学建模基地华中农业大学数学建模基地与典型的运输问题明显有以下不同：与典型的运输问题明显有以下不同：1.这是运输矿石与岩

50、石两种物资的问题；这是运输矿石与岩石两种物资的问题；2.属于产量大于销量的不平衡运输问题；属于产量大于销量的不平衡运输问题；3.为了完成品位约束，矿石要搭配运输；为了完成品位约束，矿石要搭配运输；4.产地、销地均有单位时间的流量限制；产地、销地均有单位时间的流量限制；5.运输车辆只有一种，每次满载运输，运输车辆只有一种，每次满载运输，154吨吨/车次；车次；6.铲位数多于铲车数意味着要最优的选择不多于铲位数多于铲车数意味着要最优的选择不多于7个产地作个产地作为最后结果中的产地；为最后结果中的产地；7.最后求出各条路线上的派出车辆数及安排。最后求出各条路线上的派出车辆数及安排。近似处理：近似处理