数学建模-数学规划

1、陈旺虎http:/ 数学规划 线性规划 线性规划的软件解法 整数规划 目标规划1.数学规划 数学规划论起始数学规划论起始2020世纪世纪3030年代末，年代末，5050年代与年代与6060年代发年代发展成为一个完整的分支并受到数学界和社会各界的重展成为一个完整的分支并受到数学界和社会各界的重视。视。 七八十年代是数学规划飞速发展时期，无论是从理论七八十年代是数学规划飞速发展时期，无论是从理论上还是算法方面都得到了进一步完善。上还是算法方面都得到了进一步完善。 时至今日数学规划仍然是运筹学领域中热点研究问题。时至今日数学规划仍然是运筹学领域中热点研究问题。 从国内外的数学建模竞赛的试题中看，有近

2、从国内外的数学建模竞赛的试题中看，有近1/41/4的问题的问题可用数学规划进行求解。可用数学规划进行求解。 数学规划模型的一般表达式：数学规划模型的一般表达式： 为目标函数，为目标函数， 为约束函数，为约束函数， 为可控变量，为可控变量， 为已知参数，为已知参数， 为随机参数。为随机参数。 min max, ,f x . .,0s t gxfgx数学规划模型2. 线性规划 线性规划模型是运筹学的重要分支，是线性规划模型是运筹学的重要分支，是2020世纪三四十年世纪三四十年代初兴起的一门学科。代初兴起的一门学科。 19471947年美国数学家丹齐格年美国数学家丹齐格G.B.DantzigG.B.

3、Dantzig及其同事提出的求及其同事提出的求解线性规划的单纯形法及有关理论具有划时代的意义。解线性规划的单纯形法及有关理论具有划时代的意义。他们的工作为线性规划这一学科的建立奠定了理论基础。他们的工作为线性规划这一学科的建立奠定了理论基础。 随着随着19791979年前苏联数学家哈奇扬的椭球算法和年前苏联数学家哈奇扬的椭球算法和19841984年美年美籍印度数学家卡玛卡尔籍印度数学家卡玛卡尔H.KarmarkarH.Karmarkar算法的相继问世，线算法的相继问世，线性规划的理论更加完备成熟，实用领域更加宽广。性规划的理论更加完备成熟，实用领域更加宽广。 线性规划研究的实际问题多种多样，如

4、生产计划问题、线性规划研究的实际问题多种多样，如生产计划问题、物资运输问题、合理下料问题、库存问题、劳动力问题、物资运输问题、合理下料问题、库存问题、劳动力问题、最优设计问题等。最优设计问题等。 就模型而言，线形规划模型类似于高等数学中的条件极就模型而言，线形规划模型类似于高等数学中的条件极值问题，只是其目标函数和约束条件都限定为线性函数。值问题，只是其目标函数和约束条件都限定为线性函数。 线性规划模型的求解方法目前仍以单纯形法为主要方法。线性规划模型的求解方法目前仍以单纯形法为主要方法。 本节将介绍的主要内容本节将介绍的主要内容线性规划模型的建立及标准形式；线性规划模型的建立及标准形式；线性

5、规划模型的解和单纯形法；线性规划模型的解和单纯形法；整数线性规划模型及建模案例等。整数线性规划模型及建模案例等。例2.1 生产组织与计划问题 某工厂计划生产甲、乙两种产品，主要材料有钢材某工厂计划生产甲、乙两种产品，主要材料有钢材3600kg3600kg、专用设备能力专用设备能力30003000台时。材料与设备能力的消耗定额以及单台时。材料与设备能力的消耗定额以及单位产品所获利润如下表所示位产品所获利润如下表所示问如何安排生产，才能使该厂所获利润最大？问如何安排生产，才能使该厂所获利润最大？产产品品单位产品消单位产品消 耗定额耗定额材料与设备材料与设备甲（件）甲（件）乙（件乙（件）现有材料与现

6、有材料与设备能力设备能力钢材钢材（kg）铜材铜材（kg）设备能力（台时）设备能力（台时）单位产品的利润（元）单位产品的利润（元）9 4 36004 5 20003 10 300070 120设甲、乙两种产品计划生产量分别为设甲、乙两种产品计划生产量分别为x1x1和和x2x2件，总的利润为件，总的利润为Z Z元元那么那么, ,我们的任务就是：求变量的值为多少时，才能使总利润我们的任务就是：求变量的值为多少时，才能使总利润 最大最大? ?由已知条件，由已知条件， x1x1和和x2x2要受下列限制：要受下列限制： (1)(1)生产甲、乙两种产品所用钢材的总数不能超过现有钢材数，即生产甲、乙两种产品所

7、用钢材的总数不能超过现有钢材数，即 (2)(2)生产甲、乙两种产品所用铜材的总数不能超过现有铜材数，即生产甲、乙两种产品所用铜材的总数不能超过现有铜材数，即 (3)(3)生产两种产品所用的设备能力的总数不能超过现有设备能力的台时数，生产两种产品所用的设备能力的总数不能超过现有设备能力的台时数，即即 1270120zxx12943600 xx12452000 xx123103000 xx建模过程(4)甲、乙两种产品的计划生产量不能为负数，即甲、乙两种产品的计划生产量不能为负数，即 问题转化为求解如下的条件极值（问题转化为求解如下的条件极值（数学模型数学模型）：）： 120,0 xx12max70

8、120zxx12121212943600452000. .31030000,0 xxxxstxxxx建模过程设有设有m m种物质，第种物质，第i i种物资的库存量为种物资的库存量为b bi i每种物资都可以生产每种物资都可以生产n n种产品种产品, ,第第i i种物资生产第种物资生产第j j种产品种产品时，每生产单位产品所需物资量为时，每生产单位产品所需物资量为a aijij每种物资生产第每种物资生产第j j种产品时，每单位产品可获利润种产品时，每单位产品可获利润C Cj j（如下如下表表）问如何组织生产才能使利润最大？问如何组织生产才能使利润最大？ 例2.2 最大利润问题 用用x xj j表

9、示生产第表示生产第j j种产品计划数，则问题归结为如下数学问题：种产品计划数，则问题归结为如下数学问题：约束条件的意义是：每种原料生产约束条件的意义是：每种原料生产n n种产品所需要的资源总量不能超种产品所需要的资源总量不能超过该种资源的库存量；每种产品的生产计划数不能为负。过该种资源的库存量；每种产品的生产计划数不能为负。njjjnxcxxxf1, 21).,(maxmibxaxxgtsinjjijni,.,1,),.,(. .11njxj,.,1, 0建模过程 设某类物资有设某类物资有m m个产地，有个产地，有n n个销售地个销售地. . 第第i i个产地的产量为个产地的产量为a ai i

10、, ,第第j j个销售地的需要量为个销售地的需要量为b bj j. . 从产地从产地i i到销售地到销售地j j运输单位物资的运价（单价）为运输单位物资的运价（单价）为C Cijij. . 今考虑在产销平衡的条件下，即今考虑在产销平衡的条件下，即 应如何组织运输，才能使得即满足各地的需要，又使应如何组织运输，才能使得即满足各地的需要，又使总运总运费最小。费最小。11mnijijab例2.3 运输问题用用x xijij表示产地表示产地i i供给销地供给销地j j的物资数量，则问题变成在产销平衡条件的物资数量，则问题变成在产销平衡条件下，求解以下数学问题：下，求解以下数学问题： 考察上述几个问题的

11、数学模型，他们的目标函数及约束函数都是自变考察上述几个问题的数学模型，他们的目标函数及约束函数都是自变量的线性函数，故称这类数学问题为量的线性函数，故称这类数学问题为线性规划问题。线性规划问题。1. .1,2,mijjistxbjn11,2,nijijxaim0ijx 11minmnijijijzc x建模过程 类似的问题很多类似的问题很多诸如下料问题、配料问题、分配问题、工厂选址问题等等。诸如下料问题、配料问题、分配问题、工厂选址问题等等。解决方法都归结为上述的线性规划问题，只是约束条件有的是等解决方法都归结为上述的线性规划问题，只是约束条件有的是等式，有的是不等式。式，有的是不等式。 通过

12、以上例子可以看出通过以上例子可以看出尽管所提问题的内容不同，但从构成数学问题的结构来看，却属尽管所提问题的内容不同，但从构成数学问题的结构来看，却属于同一类优化问题，其结构具有如下特征：于同一类优化问题，其结构具有如下特征： （1 1）目标函数是决策变量的线性函数。）目标函数是决策变量的线性函数。 （2 2）约束条件都是决策变量的线性等式或不等式。）约束条件都是决策变量的线性等式或不等式。总结 称如下的称如下的条件极值问题条件极值问题 为为标准的线性规划问题标准的线性规划问题。njxmibxaxxgtsxcxxfLPjnjijijnnjjjn,.,1, 0,.,1,),.,(. .),.,(m

13、in1111线性规划的解法概述 若引进记号若引进记号 则（则（LPLP）可简单地表示为）可简单地表示为 进一步，若令进一步，若令 则（则（LPLP）可表示为：）可表示为： 11,TTnncccbbb minTfxc x. .s t Axb0 x ,0nDxRA xb xxCxfTDx)(minnmijTnaAxxx)(,),.,(对于非标准形式的线性规划，可通过下列办法化成标准形式。对于非标准形式的线性规划，可通过下列办法化成标准形式。若求若求 , ,可化为求可化为求 . .若约束条件中含有不等式若约束条件中含有不等式 或或 则可引进则可引进新变量新变量 （称为（称为松弛变量松弛变量），化为等

14、式约束：），化为等式约束： 或或 今后总假定今后总假定 ，否则在等式两边乘以，否则在等式两边乘以-1-1即可。即可。若变量若变量 无非负限制，则引入两个非负变量无非负限制，则引入两个非负变量 与与 令令 ，便可化为标准形式。，便可化为标准形式。 max fxAxbAxb1nx1nAxxb1nAxxb0b jx)(min(xfjxjx jjjxxx （1 1）单纯形法单纯形法19471947年由美国数学家年由美国数学家DantzigDantzig提出；提出； 虽然在特殊情况下可能出现循环，但这种方法仍是目前虽然在特殊情况下可能出现循环，但这种方法仍是目前求解线性规划问题最常用的方法；求解线性规划

15、问题最常用的方法； 事实上在大量的实际问题计算中看出，循环情况从未出事实上在大量的实际问题计算中看出，循环情况从未出现过（仅在特意构造下才能出现）；现过（仅在特意构造下才能出现）； 是一种是一种迭代方法迭代方法。 （2 2）椭球法椭球法19771977年由前苏联数学家年由前苏联数学家khachiyankhachiyan提出的提出的多项式时间算法；多项式时间算法；它在理论上保证了多项式时间算法的存在性；它在理论上保证了多项式时间算法的存在性； 但大量数值研究发现，对于大多数实际问题，椭球法在但大量数值研究发现，对于大多数实际问题，椭球法在计算上不如单纯形方法。计算上不如单纯形方法。解法概述（3

16、3）KarmarkarKarmarkar内点法内点法19831983年由美籍印度数学家年由美籍印度数学家KarmarkarKarmarkar提出的；提出的； 也是一种也是一种多项式时间算法多项式时间算法，在大多数情况下比单纯形算法的计算，在大多数情况下比单纯形算法的计算速度要快。速度要快。（4 4）图上作业与表上作业法）图上作业与表上作业法前一种是前一种是5050年代由我国数学工作者提出的，后者是年代由我国数学工作者提出的，后者是19501950年年DantzingDantzing提出的；提出的；这二种方法主要是为解决这二种方法主要是为解决运输问题运输问题（特殊的线性规划）而设计的。（特殊的线

17、性规划）而设计的。 据统计在用线性规划解决的实际问题中，据统计在用线性规划解决的实际问题中，70%70%以上属于运输问题类以上属于运输问题类型。型。3. 线性规划问题的软件解法l 求解线性规划的常用方法是求解线性规划的常用方法是19471947年年G.B.DantzigG.B.Dantzig提出的单纯提出的单纯形法。形法。l 这种方法是以寻找最优解的迭代过程为主线。基本思路是这种方法是以寻找最优解的迭代过程为主线。基本思路是 给出一个基可行解（一个顶点）后，判断其是否为最优解；给出一个基可行解（一个顶点）后，判断其是否为最优解； 若它不是最优解，可用迭代的方法转换到另一个基可行解（顶点），若它

18、不是最优解，可用迭代的方法转换到另一个基可行解（顶点），最终找到使目标函数值更优的基可行解。最终找到使目标函数值更优的基可行解。 经过有限次迭代后，这一迭代过程以找到最优解或判定问题无最优经过有限次迭代后，这一迭代过程以找到最优解或判定问题无最优解为目标。解为目标。 求解线性规划的软件很多，下面介绍求解线性规划的软件很多，下面介绍MathematicaMathematica和和MATLABMATLAB软件。软件。Mathematica和MATLAB求解 MathematicaMathematica命令命令1.1.可用于求解各种形式的线性规划问题的命令，输入格式：可用于求解各种形式的线性规划问题

19、的命令，输入格式： 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. . 目标规划模型 即在计算过程中即在计算过程中, , 首先保证首先保证P P1 1级目标的实现，这时可级目标的实现，这时可不考虑次级目标；而不考虑次级目标；而P P2 2级目标是在实现级目标是在实现P P1 1级目标的基础上级目标的基础上考虑的，以此类推。考虑的，以此类推。当需要区别具有相同优先因子的若干个目标的差别当需要区别具有相同优先因子的若干个目标的差别时，可分别赋于它们不同的权系

20、数时，可分别赋于它们不同的权系数w wj j 。优先因子及权系数的值，均由决策者按具体情况来优先因子及权系数的值，均由决策者按具体情况来确定确定 （4 4）目标规划的目标函效）目标规划的目标函效 目标规划的目标函数是通过各目标约束的正、目标规划的目标函数是通过各目标约束的正、负偏差变量和赋于相应的优先等级来构造的负偏差变量和赋于相应的优先等级来构造的目标规划模型决策者的要求是尽可能从某个方向决策者的要求是尽可能从某个方向缩小偏离目标的数值缩小偏离目标的数值。于是，目标规划的目标函数应该是求极小值于是，目标规划的目标函数应该是求极小值min min f f f f （d d + +，d d -

21、-) ) 其基本形式有三种：其基本形式有三种： 要求恰好达到目标值，即使相应目标约束的正、负要求恰好达到目标值，即使相应目标约束的正、负偏差变量都要尽可能地小。偏差变量都要尽可能地小。这时取这时取 min min （d d + + + + d d - - ) )； 要求不超过目标值，即使相应目标约束的正偏差变要求不超过目标值，即使相应目标约束的正偏差变量要尽可能地小。量要尽可能地小。这时取这时取 min min （d d + + ) )；目标规划模型 要求不低于目标值，即使相应目标约束的负偏差变量要要求不低于目标值，即使相应目标约束的负偏差变量要尽可能地小。尽可能地小。这时取这时取 min m

22、in （d d - - ) )；对于上例对于上例, , 我们根据决策者的考虑可知我们根据决策者的考虑可知 第一优先级要求第一优先级要求 minmin（d d1 1+ + + + d d2 2+ + ) )； 第二优先级要求第二优先级要求 minmin（d d3 3+ + ) )； 第三优先级要求第三优先级要求 minmin（d d4 4- - ) )； 第四优先级要求第四优先级要求 minmin（d d1 1- - + 2+ 2d d2 2- - ) )，这里，这里, , 当不能满足市当不能满足市场需求时场需求时, , 市场认为市场认为B B产品的重要性是产品的重要性是A A产品的产品的2 2

23、倍即减少倍即减少B B产品的影响是产品的影响是A A产品的产品的2 2倍，因此引入了倍，因此引入了2:12:1的权系数。的权系数。 目标规划模型综合上述分析，我们可得到下列目标规划模型综合上述分析，我们可得到下列目标规划模型 Min f = P1（d1+ + d2+ ) + P2 d3+ + P3 d4- + P4（d1- + 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

24、,3,4. 目标规划模型根据上面讨论根据上面讨论, ,我们可以得到目标规划的一般形式如下我们可以得到目标规划的一般形式如下KknjddxmibxaKkgddxctsddPLGPkkjnjijijnjkkkjkjLlKkklkklkl, 2 , 1, 2 , 1, 0, 2 , 1,),(, 2 , 1,. . )(min)(1111作业 1. 加工奶制品的生产计划加工奶制品的生产计划 1桶牛奶可以加工桶牛奶可以加工3公斤公斤A1，每公斤获利，每公斤获利24元，耗时元，耗时12小时；可以小时；可以加工加工4公斤公斤A2 ，每公斤获利，每公斤获利16元；耗时元；耗时8小时；小时； 每天供应每天供应

25、50桶牛奶，总的加工时为桶牛奶，总的加工时为480小时，至多加工小时，至多加工100公斤的公斤的A1； 制订生产计划，使每天获利最大制订生产计划，使每天获利最大 35元可买到元可买到1桶牛奶，买吗？若买，每天最多买多少桶牛奶，买吗？若买，每天最多买多少? 可聘用临时工人，付出的工资最多是每小时几元可聘用临时工人，付出的工资最多是每小时几元? A1的获利增加到的获利增加到 30元元/公斤，应否改变生产计划？公斤，应否改变生产计划？其他费用其他费用: :450元元/千吨千吨 应如何分配水库供水量，公司才能获利最多？应如何分配水库供水量，公司才能获利最多？ 若水库供水量都提高一倍，公司利润可增加到多少？若水库供水量都提高一倍，公司利润可增加到多少？ 元元/千吨千吨甲甲乙乙丙丙丁丁A160130220170B140130190150C190200230/引水管理费引水管理