《数学建模数学规划ppt课件》由会员分享，可在线阅读，更多相关《数学建模数学规划ppt课件（67页珍藏版）》请在金锄头文库上搜索。
1、数学规划数学规划1内容安排数学规划线性规划线性规划的软件解法整数规划目标规划21.数学规划 数学规划论起始数学规划论起始2020世纪世纪3030年代末，年代末，5050年代与年代与6060年代发年代发展成为一个完整的分支并受到数学界和社会各界的重展成为一个完整的分支并受到数学界和社会各界的重视。视。七八十年代是数学规划飞速发展时期，无论是从理论七八十年代是数学规划飞速发展时期，无论是从理论上还是算法方面都得到了进一步完善。上还是算法方面都得到了进一步完善。时至今日数学规划仍然是运筹学领域中热点研究问题。时至今日数学规划仍然是运筹学领域中热点研究问题。从国内外的数学建模竞赛的试题中看，有近从国内
2、外的数学建模竞赛的试题中看，有近1/41/4的问题的问题可用数学规划进行求解。可用数学规划进行求解。3数学规划模型的一般表达式：数学规划模型的一般表达式： 为目标函数，为目标函数， 为约束函数，为约束函数， 为可控变量，为可控变量， 为已知参数，为已知参数， 为为随机参数。随机参数。 数学规划模型42. 线性规划线性规划模型是运筹学的重要分支，是线性规划模型是运筹学的重要分支，是2020世纪三四十年代世纪三四十年代初兴起的一门学科。初兴起的一门学科。19471947年美国数学家丹齐格年美国数学家丹齐格G.B.DantzigG.B.Dantzig及其同事提出的求及其同事提出的求解线性规划的单纯形
3、法及有关理论具有划时代的意义。他解线性规划的单纯形法及有关理论具有划时代的意义。他们的工作为线性规划这一学科的建立奠定了理论基础。们的工作为线性规划这一学科的建立奠定了理论基础。随着随着19791979年前苏联数学家哈奇扬的椭球算法和年前苏联数学家哈奇扬的椭球算法和19841984年美籍年美籍印度数学家卡玛卡尔印度数学家卡玛卡尔H.KarmarkarH.Karmarkar算法的相继问世，线性算法的相继问世，线性规划的理论更加完备成熟，实用领域更加宽广。规划的理论更加完备成熟，实用领域更加宽广。线性规划研究的实际问题多种多样，如生产计划问题、物线性规划研究的实际问题多种多样，如生产计划问题、物资
4、运输问题、合理下料问题、库存问题、劳动力问题、最资运输问题、合理下料问题、库存问题、劳动力问题、最优设计问题等。优设计问题等。5就模型而言，线形规划模型类似于高等数学中的条件极值就模型而言，线形规划模型类似于高等数学中的条件极值问题，只是其目标函数和约束条件都限定为线性函数。问题，只是其目标函数和约束条件都限定为线性函数。线性规划模型的求解方法目前仍以单纯形法为主要方法。线性规划模型的求解方法目前仍以单纯形法为主要方法。本节将介绍的主要内容本节将介绍的主要内容线性规划模型的建立及标准形式；线性规划模型的建立及标准形式；线性规划模型的解和单纯形法；线性规划模型的解和单纯形法；整数线性规划模型及建
5、模案例等。整数线性规划模型及建模案例等。6例2.1 生产组织与计划问题某工厂计划生产甲、乙两种产品，主要材料有钢材某工厂计划生产甲、乙两种产品，主要材料有钢材3600kg3600kg、专用设备能力专用设备能力30003000台时。材料与设备能力的消耗定额以及单台时。材料与设备能力的消耗定额以及单位产品所获利润如下表所示位产品所获利润如下表所示问如何安排生产，才能使该厂所获利润最大？问如何安排生产，才能使该厂所获利润最大？产产品品单位产品消单位产品消耗定额耗定额材料与设备材料与设备甲（件）甲（件）乙（件乙（件）现有材料与现有材料与设备能力设备能力钢材钢材（kg）铜材铜材（kg）设备能力（台时）设
6、备能力（台时）单位产品的利润（元）单位产品的利润（元）9436004520003103000701207设甲、乙两种产品计划生产量分别为设甲、乙两种产品计划生产量分别为x1x1和和x2x2件，总的利润为件，总的利润为Z Z元元那么那么, ,我们的任务就是：求变量的值为多少时，才能使总利润我们的任务就是：求变量的值为多少时，才能使总利润 最大最大? ?由已知条件，由已知条件， x1x1和和x2x2要受下列限制：要受下列限制：(1)(1)生产甲、乙两种产品所用钢材的总数不能超过现有钢材数，即生产甲、乙两种产品所用钢材的总数不能超过现有钢材数，即 (2)(2)生产甲、乙两种产品所用铜材的总数不能超过
7、现有铜材数，即生产甲、乙两种产品所用铜材的总数不能超过现有铜材数，即 (3)(3)生产两种产品所用的设备能力的总数不能超过现有设备能力的台时数，生产两种产品所用的设备能力的总数不能超过现有设备能力的台时数，即即建模过程8(4)甲、乙两种产品的计划生产量不能为负数，即甲、乙两种产品的计划生产量不能为负数，即问题转化为求解如下的条件极值（问题转化为求解如下的条件极值（数学模型数学模型）：）：建模过程9设有设有m m种物质，第种物质，第i i种物资的库存量为种物资的库存量为b bi i每种物资都可以生产每种物资都可以生产n n种产品种产品, ,第第i i种物资生产第种物资生产第j j种产品种产品时，
8、每生产单位产品所需物资量为时，每生产单位产品所需物资量为a aijij每种物资生产第每种物资生产第j j种产品时，每单位产品可获利润种产品时，每单位产品可获利润C Cj j（如下如下表表）问如何组织生产才能使利润最大？问如何组织生产才能使利润最大？ 例2.2 最大利润问题 1011用用x xj j表示生产第表示生产第j j种产品计划数，则问题归结为如下数学问题：种产品计划数，则问题归结为如下数学问题：约束条件的意义是：每种原料生产约束条件的意义是：每种原料生产n n种产品所需要的资源总量不能超种产品所需要的资源总量不能超过该种资源的库存量；每种产品的生产计划数不能为负。过该种资源的库存量；每种
9、产品的生产计划数不能为负。建模过程 12设某类物资有设某类物资有m m个产地，有个产地，有n n个销售地个销售地. . 第第i i个产地的产量为个产地的产量为a ai i, ,第第j j个销售地的需要量为个销售地的需要量为b bj j. .从产地从产地i i到销售地到销售地j j运输单位物资的运价（单价）为运输单位物资的运价（单价）为C Cijij. .今考虑在产销平衡的条件下，即今考虑在产销平衡的条件下，即应如何组织运输，才能使得即满足各地的需要，又使应如何组织运输，才能使得即满足各地的需要，又使总运总运费最小。费最小。例2.3 运输问题1314用用x xijij表示产地表示产地i i供给销
10、地供给销地j j的物资数量，则问题变成在产销平衡条件的物资数量，则问题变成在产销平衡条件下，求解以下数学问题：下，求解以下数学问题： 考察上述几个问题的数学模型，他们的目标函数及约束函数都是自变考察上述几个问题的数学模型，他们的目标函数及约束函数都是自变量的线性函数，故称这类数学问题为量的线性函数，故称这类数学问题为线性规划问题。线性规划问题。建模过程 15类似的问题很多类似的问题很多诸如下料问题、配料问题、分配问题、工厂选址问题等等。诸如下料问题、配料问题、分配问题、工厂选址问题等等。解决方法都归结为上述的线性规划问题，只是约束条件有的是等解决方法都归结为上述的线性规划问题，只是约束条件有的
11、是等式，有的是不等式。式，有的是不等式。 通过以上例子可以看出通过以上例子可以看出尽管所提问题的内容不同，但从构成数学问题的结构来看，却属尽管所提问题的内容不同，但从构成数学问题的结构来看，却属于同一类优化问题，其结构具有如下特征：于同一类优化问题，其结构具有如下特征： （1 1）目标函数是决策变量的线性函数。）目标函数是决策变量的线性函数。 （2 2）约束条件都是决策变量的线性等式或不等式。）约束条件都是决策变量的线性等式或不等式。总结 16称如下的称如下的条件极值问题条件极值问题 为为标准的线性规划问题标准的线性规划问题。线性规划的解法概述17若引进记号若引进记号 则（则（LPLP）可简单
12、地表示为）可简单地表示为 进一步，若令进一步，若令 则（则（LPLP）可表示为：）可表示为： 18对于非标准形式的线性规划，可通过下列办法化成标准形式。对于非标准形式的线性规划，可通过下列办法化成标准形式。若求若求 , ,可化为求可化为求 . .若约束条件中含有不等式若约束条件中含有不等式 或或 则可引进则可引进新变量新变量 （称为（称为松弛变量松弛变量），化为等式约束：），化为等式约束： 或或 今后总假定今后总假定 ，否则在等式两边乘以，否则在等式两边乘以-1-1即可。即可。若变量若变量 无非负限制，则引入两个非负变量无非负限制，则引入两个非负变量 与与 令令 ，便可化为标准形式。，便可化为
13、标准形式。19（1 1）单纯形法单纯形法19471947年由美国数学家年由美国数学家DantzigDantzig提出；提出； 虽然在特殊情况下可能出现循环，但这种方法仍是目前虽然在特殊情况下可能出现循环，但这种方法仍是目前求解线性规划问题最常用的方法；求解线性规划问题最常用的方法； 事实上在大量的实际问题计算中看出，循环情况从未出事实上在大量的实际问题计算中看出，循环情况从未出现过（仅在特意构造下才能出现）；现过（仅在特意构造下才能出现）； 是一种是一种迭代方法迭代方法。 （2 2）椭球法椭球法19771977年由前苏联数学家年由前苏联数学家khachiyankhachiyan提出的提出的多项
14、式时间算法；多项式时间算法；它在理论上保证了多项式时间算法的存在性；它在理论上保证了多项式时间算法的存在性； 但大量数值研究发现，对于大多数实际问题，椭球法在但大量数值研究发现，对于大多数实际问题，椭球法在计算上不如单纯形方法。计算上不如单纯形方法。解法概述20（3 3）KarmarkarKarmarkar内点法内点法19831983年由美籍印度数学家年由美籍印度数学家KarmarkarKarmarkar提出的；提出的； 也是一种也是一种多项式时间算法多项式时间算法，在大多数情况下比单纯形算法的计算，在大多数情况下比单纯形算法的计算速度要快。速度要快。（4 4）图上作业与表上作业法）图上作业与
15、表上作业法前一种是前一种是5050年代由我国数学工作者提出的，后者是年代由我国数学工作者提出的，后者是19501950年年DantzingDantzing提出的；提出的；这二种方法主要是为解决这二种方法主要是为解决运输问题运输问题（特殊的线性规划）而设计的。（特殊的线性规划）而设计的。 据统计在用线性规划解决的实际问题中，据统计在用线性规划解决的实际问题中，70%70%以上属于运输问题类以上属于运输问题类型。型。213. 线性规划问题的软件解法l求解线性规划的常用方法是求解线性规划的常用方法是19471947年年G.B.DantzigG.B.Dantzig提出的单纯提出的单纯形法。形法。l这种
16、方法是以寻找最优解的迭代过程为主线。基本思路是这种方法是以寻找最优解的迭代过程为主线。基本思路是给出一个基可行解（一个顶点）后，判断其是否为最优解；给出一个基可行解（一个顶点）后，判断其是否为最优解；若它不是最优解，可用迭代的方法转换到另一个基可行解（顶点），若它不是最优解，可用迭代的方法转换到另一个基可行解（顶点），最终找到使目标函数值更优的基可行解。最终找到使目标函数值更优的基可行解。经过有限次迭代后，这一迭代过程以找到最优解或判定问题无最优经过有限次迭代后，这一迭代过程以找到最优解或判定问题无最优解为目标。解为目标。求解线性规划的软件很多，下面介绍求解线性规划的软件很多，下面介绍Math
17、ematicaMathematica和和MATLABMATLAB软件。软件。22Mathematica和MATLAB求解MathematicaMathematica命令命令1.1.可用于求解各种形式的线性规划问题的命令，输入格式：可用于求解各种形式的线性规划问题的命令，输入格式：c=c1x1+c2x2+cnxn；m=a11x1+a12x2+a1nxn=b1，am1x1+am2x2+amnxn P Pi+1i+1，i = 1,2,i = 1,2,L-1,L-1. . 57目标规划模型 即在计算过程中即在计算过程中, , 首先保证首先保证P P1 1级目标的实现，这时可级目标的实现，这时可不考虑次
18、级目标；而不考虑次级目标；而P P2 2级目标是在实现级目标是在实现P P1 1级目标的基础上级目标的基础上考虑的，以此类推。考虑的，以此类推。当需要区别具有相同优先因子的若干个目标的差别时，当需要区别具有相同优先因子的若干个目标的差别时，可分别赋于它们不同的权系数可分别赋于它们不同的权系数w wj j 。优先因子及权系数的值，均由决策者按具体情况来确优先因子及权系数的值，均由决策者按具体情况来确定定 （4 4）目标规划的目标函效）目标规划的目标函效 目标规划的目标函数是通过各目标约束的正、目标规划的目标函数是通过各目标约束的正、负偏差变量和赋于相应的优先等级来构造的负偏差变量和赋于相应的优先
19、等级来构造的58目标规划模型决决策策者者的的要要求求是是尽尽可可能能从从某某个个方方向向缩缩小小偏偏离离目目标标的的数数值值。于是，目标规划的目标函数应该是求极小值于是，目标规划的目标函数应该是求极小值min min f f f f （d d + +，d d - -) ) 其基本形式有三种：其基本形式有三种： 要求恰好达到目标值，即使相应目标约束的正、负要求恰好达到目标值，即使相应目标约束的正、负偏差变量都要尽可能地小。偏差变量都要尽可能地小。这时取这时取 min min （d d + + + + d d - - ) )； 要求不超过目标值，即使相应目标约束的正偏差变要求不超过目标值，即使相应
20、目标约束的正偏差变量要尽可能地小。量要尽可能地小。这时取这时取 min min （d d + + ) )；59目标规划模型 要求不低于目标值，即使相应目标约束的负偏差变量要要求不低于目标值，即使相应目标约束的负偏差变量要尽可能地小。尽可能地小。这时取这时取 min min （d d - - ) )；对于上例对于上例, , 我们根据决策者的考虑可知我们根据决策者的考虑可知 第一优先级要求第一优先级要求 minmin（d d1 1+ + + + d d2 2+ + ) )； 第二优先级要求第二优先级要求 minmin（d d3 3+ + ) )； 第三优先级要求第三优先级要求 minmin（d d
21、4 4- - ) )； 第四优先级要求第四优先级要求 minmin（d d1 1- - + 2+ 2d d2 2- - ) )，这里，这里, , 当不能满足市当不能满足市场需求时场需求时, , 市场认为市场认为B B产品的重要性是产品的重要性是A A产品的产品的2 2倍即减少倍即减少B B产品的影响是产品的影响是A A产品的产品的2 2倍，因此引入了倍，因此引入了2:12:1的权系数。的权系数。 60目标规划模型综合上述分析，我们可得到下列目标规划模型综合上述分析，我们可得到下列目标规划模型 Minf = P1（d1+ + d2+ ) + P2 d3+ + P3 d4- + P4（d1- +
22、2d2- ) s.t.x1+d1-d1+=9 x2 +d2-d2+=8 4x1 + 6x2+d3-d3+=60(5) 12x1 + 18x2+d4-d4+=252 x1 , x2,di-,di+ 0,i =1,2,3,4.61目标规划模型根据上面讨论根据上面讨论, ,我们可以得到目标规划的一般形式如下我们可以得到目标规划的一般形式如下62作业1.加工奶制品的生产计划加工奶制品的生产计划1桶牛奶可以加工桶牛奶可以加工3公斤公斤A1，每公斤获利，每公斤获利24元，耗时元，耗时12小时；可以小时；可以加工加工4公斤公斤A2，每公斤获利，每公斤获利16元；耗时元；耗时8小时；小时；每天供应每天供应50
23、桶牛奶，总的加工时为桶牛奶，总的加工时为480小时，至多加工小时，至多加工100公斤的公斤的A1；制订生产计划，使每天获利最大制订生产计划，使每天获利最大35元可买到元可买到1桶牛奶，买吗？若买，每天最多买多少桶牛奶，买吗？若买，每天最多买多少?可聘用临时工人，付出的工资最多是每小时几元可聘用临时工人，付出的工资最多是每小时几元?A1的获利增加到的获利增加到30元元/公斤，应否改变生产计划？公斤，应否改变生产计划？63其他费用其他费用: :450元元/千吨千吨 应如何分配水库供水量，公司才能获利最多？应如何分配水库供水量，公司才能获利最多？ 若水库供水量都提高一倍，公司利润可增加到多少？若水库
24、供水量都提高一倍，公司利润可增加到多少？ 元元/千吨千吨甲甲乙乙丙丙丁丁A160130220170B140130190150C190200230/引水管理费引水管理费2 自来水输送自来水输送收入：收入：900元元/千吨千吨支出支出A：50B：60C：50甲：甲：30；50乙：乙：70；70丙：丙：10；20丁：丁：10；40水水库库供供水水量量(千千吨吨)小小区区基基本本用用水水量量(千千吨吨)小小区区额额外外用用水水量量(千千吨吨)（以天计）（以天计）64如何如何装运，装运，使本次飞行使本次飞行获利最大？获利最大？三个货舱三个货舱最大最大载载重重( (吨吨),),最大容积最大容积( (米米3
25、 3) )3货机装运货机装运重量（吨）重量（吨）空间空间(米米3/吨）吨）利润（元利润（元/吨）吨）货物货物1184803100货物货物2156503800货物货物3235803500货物货物4123902850三个货舱中实际载重必须与其最大三个货舱中实际载重必须与其最大载载重成比例重成比例前仓：前仓：10；6800中仓：中仓：16；8700后仓：后仓：8；5300飞机平衡飞机平衡654.纺织厂的生产规划纺织厂的生产规划某纺织厂生产窗帘布和衣料两种布料，该厂对这两种布料某纺织厂生产窗帘布和衣料两种布料，该厂对这两种布料的生产能力均是的生产能力均是1000m/h，工厂正常生产能力每周，工厂正常生
26、产能力每周80h，根据市场预测，下周最大销售量窗帘布，根据市场预测，下周最大销售量窗帘布70000m、衣料、衣料45000m，窗帘布每米获利，窗帘布每米获利2.50元，衣料每料获利元，衣料每料获利1.50元。元。该厂定出的经营目标是：该厂定出的经营目标是：P1：保证生产均衡稳定，避免开工不足；：保证生产均衡稳定，避免开工不足；P2：每周加班时间不超过：每周加班时间不超过10h；P3：努力实现最大销售量；：努力实现最大销售量；P4：尽可能减少加班时间。：尽可能减少加班时间。试制定下周的生产计划试制定下周的生产计划（生产不同布料的小时数）（生产不同布料的小时数）66TheEnd！AnyQuestion?http:/
