数学建模案例之线性规划

.,数学建模案例之线性规划奶制品的生产与销售,.,优化问题及其一般模型：,引言,优化问题是人们在工程技术、经济管理和科学研究等领域中最常遇到的问题之一。例如：设计师要在满足强度要求等条件下选择材料的尺寸，使结构总重量最轻；公司经理要根据生产成本和市场需求确定产品价格，使所获利润最高；调度人员要在满足物质需求和装载条件下安排从各供应点到需求点的运量和路线，使运输总费用最低；投资者要选择一些股票,债券下注,使收益最大,而风险最小,.,一般地，优化模型可以表述如下：,这是一个多元函数的条件极值问题，其中x=x1,x2,xn。,许多实际问题归结出的这种优化模型，但是其决策变量个数n和约束条件个数m一般较大，并且最优解往往在可行域的边界上取得，这样就不能简单地用微分法求解，数学规划就是解决这类问题的有效方法。,引言,.,数学规划模型分类:,“数学规划是运筹学和管理科学中应用及其广泛的分支。在许多情况下，应用数学规划取得的如此成功，以致它的用途已超出了运筹学的范畴，成为人们日常的规划工具。”H.P.Williams.数学规划模型的建立。,数学规划包括线性规划、非线性规划、整数规划、几何规划、多目标规划等，用数学规划方法解决实际问题，就要将实际问题经过抽象、简化、假设，确定变量与参数，建立适当层次上的数学模型，并求解。,引言,.,建立数学规划模型的步骤:,当你打算用数学建模的方法来处理一个优化问题的时候，首先要确定寻求的决策是什么，优化的目标是什么，决策受到那些条件的限制（如果有限制的话），然后用数学工具（变量、常数、函数等）表示它们，最后用合适的方法求解它们并对结果作出一些定性、定量的分析和必要的检验。,引言,.,引言,Step1.寻求决策，即回答什么？必须清楚，无歧义。阅读完题目的第一步不是寻找答案或者解法，而是Step2.确定决策变量第一来源：Step1的结果，用变量固定需要回答的决策第二来源：由决策导出的变量（具有派生结构）其它来源：辅助变量（联合完成更清楚的回答）Step3.确定优化目标用决策变量表示的利润、成本等。Step4.寻找约束条件决策变量之间、决策变量与常量之间的联系。第一来源：需求；第二来源：供给；其它来源：辅助以及常识。Step5.构成数学模型将目标以及约束放在一起，写成数学表达式。,.,内容：如何建立线性规划模型举例线性规划模型的求解方法要求：掌握线性规划模型的建立方法掌握利用数学软件LINDO、Matlab等求解线性规划模型的方法理解单纯形法的计算步骤重点、难点：重点：线性规划模型的建立与软件求解难点：线性规划问题的理论求解方法单纯形法,.,简介,线性规划是最简单、应用最广泛的一种数学规划方法，也是应用最早的一种最优化方法；线性规划的数学模型是目标函数和全部约束式都是变量的线性函数；线性规划是学习运筹学的首要课程之一；1947年，丹茨格（Dantzig）提出了单纯形法，使线性规划的算法趋于成熟；在数学上讲，线性规划问题就是研究一类条件极值问题，即在一组线性约束条件（包括等式及不等式约束）下，找出一个线性函数的最大值或最小值。,.,例1：加工奶制品的生产计划,一奶制品加工厂用牛奶生产A1，A2两种奶制品，一桶牛奶可以在设备甲上用12小时加工成3公斤A1，或者在设备乙上用8小时加工成4公斤A2。根据市场需求，生产的A1、A2全部能够售出，且每公斤A1获利24元，每公斤A2获利16元。现在加工厂每天能够得到50桶牛奶的供应，每天正式工人总的劳动时间为480小时，并且设备甲每天至多能加工100公斤A1，设备乙的加工能力没有限制。试为该厂制定一个生产计划，使每天获利最大?并进一步讨论以下三个附加问题：1）若用35元可以买到一桶牛奶，应否作这项投资？若投资，每天最多购买多少桶牛奶？2）若可以聘用临时工人以增加劳动时间，付给临时工人的工资最多是每小时多少元？3）由于市场需求变化，每公斤A1的获利增加到30元，应否改变生产计划？,.,问题分析,企业内部的生产计划有各种不同的情况。空间层次工厂级：根据外部需求和内部设备、人力、原料等条件，以最大利润为目标制订产品生产计划车间级：根据生产计划、工艺流程、资源约束及费用参数等，以最小成本为目标制订生产批量计划时间层次若短时间内外部需求和内部资源等不随时间变化，可制订单阶段生产计划，否则应制订多阶段生产计划,.,问题分析,每天,50桶牛奶,时间480小时,至多加工100公斤A1,制订生产计划，使每天获利最大,35元可买到1桶牛奶，买吗？若买，每天最多买多少?,可聘用临时工人，付出的工资最多是每小时几元?,A1的获利增加到30元/公斤，应否改变生产计划?,.,模型构成,引入决策变量x1桶牛奶生产A1，x2桶牛奶生产A2（每天）目标函数（每天获利）生产A1获利：243x1生产A2获利：164x2每天获利总额：z=72x1+64x2约束条件原料供应：x1+x250劳动时间：12x1+8x2480加工能力：3x1100非负约束：x1,x20,.,模型构成,数学模型：,LP模型,.,线性规划模型具有的三条性质,比例性,可加性,连续性,xi对目标函数的“贡献”与xi取值成正比,xi对约束条件的“贡献”与xi取值成正比,xi对目标函数的“贡献”与xj取值无关,xi对约束条件的“贡献”与xj取值无关,A1,A2每公斤的获利是与各自产量无关的常数,每桶牛奶加工出A1,A2的数量和时间是与各自产量无关的常数,A1,A2每公斤的获利是与相互产量无关的常数,每桶牛奶加工出A1,A2的数量和时间是与相互产量无关的常数,加工A1,A2的牛奶桶数是实数,xi取值连续,.,LP问题的一般概念,1.LP模型的一般形式求一组决策变量x1,x2,xn的值，使其满足约束条件：并使目标函数取得最大（或最小)值，其中aij,bi,cj为已知量。,.,LP问题的一般概念,2.标准形式其中,.,LP问题的一般概念,3.将一般线性规划模型转化为标准形例题：将下述LP模型转化成标准形式解：转化分为目标函数、大于等于约束、小于等于约束和自由约束变量几个不同部分。,.,LP问题的一般概念,目标函数maxz=4x1+5x2+7x3-x4minz1=-4x1-5x2-7x3+x4约束条件大于等于约束x1+x2+2x3-x41添加剩余变量x50x1+x2+2x3-x4-x5=1小于等于约束2x1-6x2+3x3+x4-3添加松弛变量x60-2x1+6x2-3x3-x4-x6=3自由变量（无）,.,LP问题的一般概念,化成标准型为：,.,LP问题的一般概念,4.单纯形法G.B.Dantzig的单纯形法（Simplexmethod）是一个顶点迭代算法，即从一个顶点出发，沿着凸多面体的棱迭代到另一个顶点，使目标函数值下降（至少不升），由顶点个数的有限性，可以证明经过有限次迭代一定可以求得最优解或者判定该问题无最优解，这就是单纯形法的基本思想。而几何上一个的顶点对应在代数上的一个基可行解，因此，单纯形法求解线性规划问题只需要关心基可行解。,.,LP问题的一般概念,基本理论参见任何一本运筹学教材上的相关内容，下面仅以一个例子说明单纯形法的步骤。利用单纯形法求解下述LP问题。,.,LP问题的一般概念,Step1.将一般的LP问题划成标准形式引入松弛变量x3，x4，x5将原问题化成标准形式,.,LP问题的一般概念,Step2.建立初始单纯形表，求出初始的基本可行解x(0)及对应的目标函数值z0建立初始单纯形表求出基本可行解x(0)=(0,0,350,200,150)T，求出目标函数值z0=0,.,LP问题的一般概念,Step3.判断现行解是否是最优解。若是，计算结束；否则转第4步。判断方法：计算检验数rj=cj-zj，其中zj=cBTaij，j=1,2,n.若所有的rj0，j=1,2,n，则现行解为最优解。检验数中r10，r20，上面的结果x(0)不是最优解。,.,LP问题的一般概念,Step4.确定进基向量计算minrj|rj0=rk，则xk进基；因minrj|rj0=bl/ark，此时主元素为ark，xl应离基。因为150/50=b3/a32=3，主元素为a32=5，原来的基变量x5离基.,.,LP问题的一般概念,Step6.以ark为主元素，进行换基计算，即进行一次Gauss消元计算，求得一个新的基本可行解，然后返回Step3。将xk所对应的列向量化为单位向量，使主元素处为1，其余元素均为0.新的基本可行解为x(0)=(0,30,200,50,0)T最优值为-45000.由于r1=-4000，所以还没有达到最优解。,.,LP问题的一般概念,重复Step4Step6x1进基,x4离基,a21=2为主元素,作Gauss消去法后得到:,.,LP问题的一般概念,重复Step3，判断是否为最优解因为所有的检验数rj0,所以现行解为最优解，即最优解为x(0)=(25,20,25,0,0)T，最优值为w=-z0=55000.,.,模型求解,1.图解法,目标函数,z=c(常数)等值线,在B(20,30)点得到最优解,目标函数和约束条件是线性函数,可行域为直线段围成的凸多边形,目标函数的等值线为直线,最优解一定在凸多边形的某个顶点取得。,.,2.单纯形法Step1.将一般的LP问题划成标准形式引入松弛变量x3，x4，x5将原问题化成标准形式,.,Step2.建立初始单纯形表，求出初始的基本可行解x(0)及对应的目标函数值w0建立初始单纯形表求出基本可行解x(0)=(0,0,50,480,100)T，求出目标函数值w0=0,.,Step3.判断现行解是否是最优解。若是，计算结束；否则转第4步。判断方法：计算检验数rj=cj-zj，其中zj=cBTaij，j=1,2,n.若所有的rj0，j=1,2,n，则现行解为最优解。检验数中r10，r20，上面的结果x(0)不是最优解。,.,Step4.确定进基向量计算minrj|rj480/12100/3，所以minbi/ai1|ai10=b3/a31=100/3，主元素为a31=3，原来的基向量x5离基.,.,Step6.以ark为主元素，进行换基计算，即进行一次Gauss消元计算，求得一个新的基本可行解，然后返回Step3。将xk所对应的列向量化为单位向量，使主元素处为1，其余元素均为0.新的基本可行解为x(0)=(100/3,0,50/3,80,0)T最优值为-2400.由于r2=-640，所以还没有达到最优解。,.,重复Step4Step6x2进基,x4离基,a22=8为主元素,作Gauss消去法后得到:,.,重复Step3，判断是否为最优解新的基本可行解为x(0)=(100/3,10,20/3,0,0)T最优值为-3040.由于r5=-80，所以还没有达到最优解。,.,重复Step4Step6x5进基,x3离基,a15=1/6为主元素,作Gauss消去法后得到:,.,重复Step3，判断是否为最优解因为所有的检验数rj0,所以现行解为最优解，即最优解为x(0)=(20,30,0,0,40)T，最优值为z=-w0=3360.,.,3.Mathematica软件求解,方法一：Mathematica软件所采用的线性规划模型是：式中：X是n维列向量，即X=(x1,x2,xn)T,为未知向量；CT是n维行向量，称为目标函数f的系数向量；b是m维列向量，称为约束函数右端向量；A是mn维矩阵，称为约束函数系数矩阵；符号minf表示对函数f(x)求局部极小。,.,3.Mathematica软件求解,方法二：Mathematica软件中的NMaximize和NMinimize函数可以解线性规划问题,还能解非线性规划问题。其使用格式如下：,.,4.Matlab软件求解,线性规划问题的数学模型：式中f,x,b,beq,lb,ub为向量A和Aeq为矩阵.Linprog函数的调用格式如下：x=linprog(f,A,b)x=linprog(f,A,b,Aeq,beq)x=linprog(f,A,b,Aeq,beq,lb,ub)x=linprog(f,A,b,Aeq,beq,lb,ub,x0)x,fval=linprog()x,fval,exitflag=linprog(),.,5.Lindo软件求解,5.1软件介绍LINDO是Linear,INteractive,andDiscreteOptimizer的缩写可求解问题线性规划：LinearProgramming(LP)整数规划：IntegerProgramming(IP)二次规划：QuadraticProgramming(QP),.,5.2求解线性规划问题举例利用Lindo软件求解例题1：奶制品的生产软件操作演示用户输入程序max72x1+64x2st2）x1+x2503）12x1+8x24804）3x1100end运行程序,.,输出结果（不进行灵敏度分析）解释1,OBJECTIVEFUNCTIONVALUE1)3360.000VARIABLEVALUEREDUCEDCOSTX120.0000000.000000X230.0000000.000000ROWSLACKORSURPLUSDUALPRICES2)0.00000048.0000003)0.0000002.0000004)40.0000000.000000NO.ITERATIONS=2,20桶牛奶生产A1,30桶生产A2，利润3360元。,.,输出结果（不进行灵敏度分析）解释2,OBJECTIVEFUNCTIONVALUE1)3360.000VARIABLEVALUEREDUCEDCOSTX120.0000000.000000X230.0000000.000000ROWSLACKORSURPLUSDUALPRICES2)0.00000048.0000003)0.0000002.0000004)40.0000000.000000NO.ITERATIONS=2,“资源”剩余为零的约束为紧约束（有效约束）,max72x1+64x2st2）x1+x2503）12x1+8x24804）3x1100end,.,输出结果（不进行灵敏度分析）解释3,OBJECTIVEFUNCTIONVALUE1)3360.000VARIABLEVALUEREDUCEDCOSTX120.0000000.000000X230.0000000.000000ROWSLACKORSURPLUSDUALPRICES2)0.00000048.0000003)0.0000002.0000004)40.0000000.000000NO.ITERATIONS=2,最优解下“资源”增加1单位时“效益”的增量,原料增加1单位,利润增长48,时间增加1单位,利润增长2,加工能力增长不影响利润,影子价格,35元可买到1桶牛奶，要买吗？,3548,应该买！,聘用临时工人付出的工资最多每小时几元？,2元！,.,输出结果（有灵敏度分析）解释4,RANGESINWHICHTHEBASISISUNCHANGED:OBJCOEFFICIENTRANGESVARIABLECURRENTALLOWABLEALLOWABLECOEFINCREASEDECREASEX172.00000024.0000008.000000X264.0000008.00000016.000000RIGHTHANDSIDERANGESROWCURRENTALLOWABLEALLOWABLERHSINCREASEDECREASE250.00000010.0000006.6666673480.00000053.33333280.0000004100.000000INFINITY40.000000,最优解不变时目标函数系数允许变化范围,(约束条件不变),x1系数范围(64,96),x2系数范围(48,72),A1获利增加到30元/千克，应否改变生产计划？,不变！,x1系数由243=72增加为303=90，在允许范围内,.,输出结果（有灵敏度分析）解释5,RANGESINWHICHTHEBASISISUNCHANGED:OBJCOEFFICIENTRANGESVARIABLECURRENTALLOWABLEALLOWABLECOEFINCREASEDECREASEX172.00000024.0000008.000000X264.0000008.00000016.000000RIGHTHANDSIDERANGESROWCURRENTALLOWABLEALLOWABLERHSINCREASEDECREASE250.00000010.0000006.6666673480.00000053.33333280.0000004100.000000INFINITY40.000000,影子价格有意义时右端约束的允许变化范围,(目标函数不变),原料最多增加10,时间最多增加53,35元可买到1桶牛奶，每天最多买多少？,最多买10桶!,.,例2：奶制品的生产销售计划,例1给出了A1，A2两种奶制品的生产条件,利润及工厂的“资源”限制全都不变。为增加工厂的获利，开发了奶制品的深加工技术:用2小时和3元的加工费，可将1公斤A1加工成0.8公斤高级奶制品B1,也可将1公斤A2加工成0.75公斤高级奶制品B2,每公斤B1能获利44元，每公斤B2能获利32元。试为该厂制订一个生产销售计划，使每天的净利润最大，并讨论以下问题：1）若投资30元可以增加供应1桶牛奶，投资3元可以增加1小时劳动时间，应否作这些投资？若每天投资150元，可赚回多少？2）每公斤高级奶制品B1,B2的获利经常有10%的波动，对制订的生产销售计划有无影响？若每公斤B1的获利下降10%，计划应该变化吗？,.,例2奶制品的生产销售计划,在例1基础上深加工,制订生产计划，使每天净利润最大,30元可增加1桶牛奶，3元可增加1小时时间，应否投资？现投资150元，可赚回多少？,50桶牛奶,480小时,至多100公斤A1,B1，B2的获利经常有10%的波动，对计划有无影响？,.,销售x1千克A1,x2千克A2，,x3千克B1,x4千克B2,原料供应,劳动时间,加工能力,决策变量,目标函数,利润,约束条件,非负约束,x5千克A1加工B1，x6千克A2加工B2,附加约束,.,模型求解,软件实现,LINDO6.1,OBJECTIVEFUNCTIONVALUE1)3460.800VARIABLEVALUEREDUCEDCOSTX10.0000001.680000X2168.0000000.000000X319.2000010.000000X40.0000000.000000X524.0000000.000000X60.0000001.520000ROWSLACKORSURPLUSDUALPRICES2)0.0000003.1600003)0.0000003.2600004)76.0000000.0000005)0.00000044.0000006)0.00000032.000000NO.ITERATIONS=2,.,OBJECTIVEFUNCTIONVALUE1)3460.800VARIABLEVALUEREDUCEDCOSTX10.0000001.680000X2168.0000000.000000X319.2000010.000000X40.0000000.000000X524.0000000.000000X60.0000001.520000ROWSLACKORSURPLUSDUALPRICES2)0.0000003.1600003)0.0000003.2600004)76.0000000.0000005)0.00000044.0000006)0.00000032.000000NO