数学规划概述

数学规划模型概述,假期你想去旅游。假如你只去一个地方而且只有一条线路可走，反倒省心一些如果你要去许多地方，又有许多路线，许多交通工具，而你还想尽量节省路费，那么你就要考虑“最优决策”或“最优（方案）设计”的问题了最优化(optimization)是企业运作、科技研发和工程设计中常见的问题要表述一个最优化问题(即建立数学模型)，应明确三个基本要素：决策变量（decisionvariables）约束条件(constraints)目标函数(objectivefunction),决策变量(decisionvariables):它们是决策者所控制的那些数量，它们取什么数值需要决策者来决策，最优化问题的求解就是找出决策变量的最优取值约束条件(constraints)：它们是决策变量在现实世界中所受到的限制，或者说决策变量在这些限制范围之内取值才有实际意义目标函数(objectivefunction):它代表决策者希望对其进行优化的那个指标。目标函数是决策变量的函数,如果一个最优化问题的决策变量不是时间的函数，则属于静态优化(staticoptimization)或有限维优化(finitedimensionaloptimization)的范畴按照静态优化问题的结构是否线性分为线性规划和非线性规划线性规划的特征是目标函数和约束条件中的函数都是决策变量的线性函数，并且约束是必不可少的（否则不存在有实际意义的解）,三要素：决策变量；目标函数；约束条件,数学规划模型的一般形式,规划问题：求目标函数在约束条件下的最值可行解（只满足约束）与最优解(取到最优值),数学规划模型的简单分类,线性规划(LP)目标和约束均为线性函数非线性规划(NLP)目标或约束中存在非线性函数二次规划(QP)目标为二次函数、约束为线性整数规划(IP)决策变量(全部或部分)为整数整数线性规划(ILP)，整数非线性规划(INLP)纯整数规划(PIP),混合整数规划(MIP)一般整数规划，0-1（整数）规划,连续优化,离散优化,数学规划,MATLAB优化工具箱能求解的优化模型,优化工具箱3.0(MATLAB7.0R14),连续优化,离散优化,无约束优化,非线性极小fminunc,非光滑(不可微)优化fminsearch,非线性方程(组)fzerofsolve,全局优化暂缺,非线性最小二乘lsqnonlinlsqcurvefit,线性规划linprog,纯0-1规划bintprog一般IP(暂缺),非线性规划fminconfminimaxfgoalattainfseminf,上下界约束fminbndfminconlsqnonlinlsqcurvefit,约束线性最小二乘lsqnonneglsqlin,约束优化,二次规划quadprog,优化,线性规划,非线性规划,二次规划,连续优化,整数规划,LINDO,LINGO,LINDO/LINGO软件能求解的模型,LPQPNLPIP全局优化(选)ILPIQPINLP,LINGO软件的求解过程,LINGO预处理程序,线性优化求解程序,非线性优化求解程序,分枝定界管理程序,1.确定常数2.识别类型,1.单纯形算法2.内点算法(选),1、顺序线性规划法(SLP)2、广义既约梯度法(GRG)(选)3、多点搜索(Multistart)(选),LINGO软件的功能与特点,LINGO模型的优点,集成了线性(非线性)/连续(整数)优化功能具有多点搜索/全局优化功能提供了灵活的编程语言(矩阵生成器)，可方便地输入模型提供与其他数据文件的接口提供与其他编程语言的接口LINDOAPI可用于自主开发运行速度较快,LINDO公司软件产品简要介绍,美国芝加哥(Chicago)大学的LinusSchrage教授于1980年前后开发,后来成立LINDO系统公司（LINDOSystemsInc.），网址：,LINDO:LinearINteractiveandDiscreteOptimizer(V6.1)LINDOAPI:LINDOApplicationProgrammingInterface(V4.1)LINGO:LinearINteractiveGeneralOptimizer(V10.0)WhatsBest!:(SpreadSheete.g.EXCEL)(V8.0),演示(试用)版、高级版、超级版、工业版、扩展版（求解问题规模和选件不同）,历史悠久，理论成熟，应用广泛运筹学的最基本的方法之一，网络规划、整数规划、目标规划和多目标规划都是以线性规划为基础的。解决稀缺资源最优分配的有效方法，使付出的费用最小或获得的收益最大。,线性规划模型,1939年前苏联康托洛维奇（KOHTOPOBUZ）生产组织与计划中的数学方法提出“解乘数法”。,线性规划理论的发展,美国科学院院士DANTZIG（丹齐克），1948年在研究美国空军资源的优化配置时提出线性规划及其通用解法“单纯形法”。被称为线性规划之父。,线性规划之父的Dantzig(丹齐克)。据说，一次上课，Dantzig迟到了，仰头看去，黑板上留了几个题目，他就抄了一下，回家后埋头苦做。几个星期之后，疲惫的去找老师说，这件事情真的对不起，作业好像太难了，我所以现在才交，言下很是惭愧。几天之后，他的老师就把他召了过去，兴奋的告诉他说他太兴奋了。Dantzig很不解,后来才知道原来黑板上的题目根本就不是什么家庭作业，而是老师说的本领域的未解决的问题，他给出的那个解法也就是单纯形法。这个方法是上个世纪前十位的算法。,1960年，“最佳资源利用的经济计算”康托洛维奇和库伯曼斯(Koopmans)。两人因对资源最优分配理论的贡献而获1975年诺贝尔经济学奖,1961年，查恩斯与库伯提出了目标规划，艾吉利提出了用优先因子来处理多目标问题。20世纪70年代，斯姆李与杰斯开莱尼应用计算机处理目标规划问题,从1964年诺贝尔奖设经济学奖后，到1992年28年间的32名获奖者中有13人(40%)从事过与线性规划有关的研究工作，其中著名的有Simon，Samullson，Leontief，Arrow，Miller等。,保罗-萨缪尔逊（PAULASAMUELSON）,他发展了数理和动态经济理论，将经济科学提高到新的水平。他的研究涉及经济学的全部领域。于1970年获得诺贝尔经济学奖。华西里列昂惕夫（WASSILYLEONTIEF），美国人，他发展了投入产出方法，该方法在许多重要的经济问题中得到运用。曾获1973年诺贝尔经济科学奖。肯尼斯-J-阿罗（KENNETHJ.ARROW）,美国人，因与约翰-希克斯（JOHNR.HICKS）共同深入研究了经济均衡理论和福利理论获得1972年诺贝尔经济学奖。牟顿-米勒（MERTONM.MILLER）,1923-2000,美国人,由于他在金融经济学方面做出了开创性工作，于1990年获得诺贝尔经济奖。,一个农场有50亩土地,20个劳动力,计划种蔬菜,棉花和水稻.种植这三种农作物每亩地分别需要劳动力1/21/31/4,预计每亩产值分别为110元,75元,60元.如何规划经营使经济效益最大.,种植蔬菜x1亩,棉花x2亩,水稻x3亩(决策变量)以取得最高的产值的方式达到收益最大的目标.求f=110 x1+75x2+60 x3的最大值(目标函数、优劣标准)约束条件x1+x2+x3501/2x1+1/3x2+1/4x320 x1，x2，x30,例1农作物种植,max:Z=110 x1+75x2+60 x3s.t.x1+x2+x3501/2x1+1/3x2+1/4x320 x1，x2，x30,如果规划问题的数学模型中，决策变量的取值可以是连续的，目标函数是决策变量的线性函数，约束条件是含决策变量的线性等式或不等式，则该类规划问题的数学模型称为线性规划的数学模型。实际问题中线性的含义：一是严格的比例性二是可叠加性,关于线性的界定,比例性：决策变量变化引起目标的改变量与决策变量改变量成正比；可加性：每个决策变量对目标和约束的影响独立于其它变量；连续性：每个决策变量取连续值；确定性：线性规划中的参数aij,bi,ci为确定值。,正则模型决策变量:x1,x2,xn.目标函数:Z=c1x1+c2x2+cnxn.求目标函数的最小或最大约束条件:a11x1+a1nxnb1,am1x1+amnxnbm,线性规划的数学模型及其标准化,标准化模型决策变量x1,x2,xn,maxZ=c1x1+cnxn,s.t.a11x1+a1nxn=b1,am1x1+amnxn=bm,x10,xn0,模型的标准化10.引入松弛变量将不等式约束变为等式约束若有ai1x1+ainxnbi,则引入xn+i0,使得ai1x1+ainxn+xn+i=bi若有aj1x1+ajnxnbj,则引入xn+j0,使得aj1x1+ajnxn-xn+j=bj.且此时目标函数Z=c1x1+c2x2+cnxn+0 xn+1+0 xn+m.20.将目标函数的优化变为目标函数的极大化.若求minZ,令Z=Z,则问题变为maxZ.30.引入人工变量,使得所有变量均为非负.若xi没有非负的条件,则引入xi0和xi0,令xi=xixi,则可使得问题的全部变量均非负.,线性规划的对偶性和影子价格,农作物种植（续）：一个农场有50亩土地,20个劳动力,计划种蔬菜,棉花和水稻.种植这三种农作物每亩地分别需要劳动力1/21/31/4,预计每亩产值分别为110元,75元,60元.如果出租土地和劳动力如何规划经营使经济效益最大.,决策变量:单位土地和单位劳力出租价格分别为y1y2,目标函数:g=50y1+20y2,优劣准则:应求g的最小值.(因为要达到的要求已经通过约束条件满足，决策者关心的是在基本要求达到时出租价格的心理底线是多少？标底),约束条件:y1+1/2y2110y1+1/3y275y1+1/4y260(成本不小于产值)（我出租出去要比自己种植合适。出租底线）,对偶线性规划,原问题maxf=cTxs.t.Axbxi0,i=1,2,n.,对偶问题minf=bTys.t.ATycyi0,i=1,2,m.,max:Z=110 x1+75x2+60 x3s.t.x1+x2+x3501/2x1+1/3x2+1/4x320 x1，x2，x30,A是mn矩阵，c是n1向量，b是m1向量x是n1向量,y是m1向量,min：g=50y1+20y2s.t.y1+1/2y2110y1+1/3y275y1+1/4y260y1，y20,对偶定理:互为对偶的两个线性规划问题若其中一个有有穷的最优解,则另一个也有有穷的最优解,且最优值相等.若两者之一有无界的最优解,则另一个没有可行解。,模型II给出了生产中资源的最低估价.这种价格涉及到资源的有效利用,它不是市场价格,而是根据资源在生产中做出的贡献确定的估价,被称为“影子价格”。,模型I给出了生产中的资源最优分配方案。,灵敏度分析主要包括下面几个内容：1：当约束条件的右边常数项变化的影响；2：约束条件的系数变化的影响；3：目标函数的系数变化的影响。可能的影响结果：1：最优解保持不变；2：基变量保持不变，但值变了；3：基本解变化。,线性规划的灵敏度分析,例：简单的线性规划（LP）问题,在空白的模型窗口中输入这个LP模型：,max2x+3yst4x+3y=103x+5y12end,附录1：用Lindo解线性规划,如图：,程序以“MAX”（或“MIN”）开始，表示目标最大化（或最小化）问题，后面直接写出目标函数表达式和约束表达式；目标函数和约束之间用“ST”分开；（或用“s.t.”，“sunjectto”）程序以“END”结束（“END”也可以省略）。系数与变量之间的乘号必须省略。系统对目标函数所在行自动生成行名“1）”,对约束默认的行名分别是“2)”“3)”，用户也可以自己输入行名；行名放在对应的约束之前。书写相当灵活，不必对齐，不区分字符的大小写。默认所有的变量都是非负的,所以不必输入非负约束。约束条件中的“=”可分别用“”代替。一行中感叹号“！”后面的文字为是注释语句，可增强程序的可读性，不参与模型的建立。,LINDO程序有以下特点,模型求解,用鼠标点击工具栏中的图标，或从菜单中选择Solve|Solve（Ctrl+S）命令,LINDO首先开始编译这个模型，编译没有错误则开始求解；求解时会首先显示如右图所示的LINDO“求解器运行状态窗口”。,求解器运行状态窗口显示的相应信息及含义,紧接着弹出一对话框，询问你是否需要做灵敏性分析（DORANGE(SENSITIVITY)ANALYSIS?）先选择“否（N）”按钮，这个窗口就会关闭。然后，再把状态窗口也关闭。,报告窗口,用鼠标选择“Window|ReportsWindow”（报告窗口），就可以查看该窗口的内容,保存文件,选择File|Save（F5）命令把“结果报告”保存在一个文件中（缺省的后缀名为LTX,即LINDO文本文件）类似地，回到模型窗口，可以把输入的模型保存在一个文件中。保存的文件将来可以用File|Open（F3）和File|View（F4）重新打开，用前者打开的程序可以进行修改，而后者只能浏览。,如果模型有错误,运行时会弹出出错信息报告窗口(LINDOErrorMessage)，则需要修改模型。,例1：某家具公司制造书桌、餐桌和椅子，所用的资源有三种：木料、木工和漆工。生产数据如下表所示。,若要求桌子的生产量不超过5件，如何安排三种产品的生产可使利润最大？,解：,用DESKS、TABLES和CHAIRS分别表示三种产品的生产量（决策变量），容易建立LP模型。,在LINDO模型窗口中输入模型：,MAX60DESKS+30TABLES+20CHAIRSSUBJECTTO2)8DESKS+6TABLES+CHAIRS=483)4DESKS+2TABLES+1.5CHAIRS=204)DESKS+1.5TABLES+0.5CHAIRS=85)TABLES=5END,解这个模型，并对弹出的对话框“DORANGE(SENSITIVITY)ANALYSIS?”选择“是（Y）”按钮，这表示你需要做灵敏性分析。然后，查看输出结果。,LPOPTIMUMFOUNDATSTEP2OBJECTIVEFUNCTIONVALUE1)280.0000VARIABLEVALUEREDUCEDCOSTDESKS2.0000000.000000TABLES0.0000005.000000CHAIRS8.0000000.000000ROWSLACKORSURPLUSDUALPRICES2)24.0000000.0000003)0.00000010.0000004)0.00000010.0000005)5.0000000.000000NO.ITERATIONS=1,输出结果的前半部分：,前半部分的输出结果的解释:,“LPOPTIMUMFOUNDATSTEP2”表示两次迭代（旋转变换）后得到最优解。,“OBJECTIVEFUNCTIONVALUE1）280.000000”表示最优目标值为280。,“VALUE”给出最优解中各变量的值：造2个书桌（desks）,0个餐桌（tables）,8个椅子（chairs）。所以desks、chairs是基变量（取值非0），tables是非基变量（取值为0）。,“SLACKORSURPLUS”给出松驰变量的值。（在最优的情况下资源的剩余量）第2行松驰变量=24（第1行表示目标函数，第2行对应第1个约束）第3行松驰变量=0第4行松驰变量=0第5行松驰变量=5,“REDUCEDCOST”列出最优单纯形表中判别数所在行的变量的系数，表示当变量有微小变动时,目标函数的变化率.其中基变量的reducedcost值应为0;非基变量Xj，相应的reducedcost值1）表示当非基变量Xj增加一个单位时，目标函数相应减少的量(max型问题)。2）理解为：为了使该非基变量变成基变量，目标函数中该变量前对应系数应增加的量。,本例中：变量TABLES对应的reducedcost值为5。1）表示当非基变量TABLES的值从0变为1时（此时假定其它非基变量保持不变,但为了满足约束条件，基变量显然会发生变化），此时的最优的目标函数值为280-5=275。2）理解为目前table的单价30元偏低，不值得生产，如果生产的话至少35元。,“DUALPRICE”（对偶价格）表示当对应约束有微小变动时,目标函数的变化率.输出结果中对应于每一个约束有一个对偶价格.若其数值为p,表示对应约束中不等式右端项若增加1个单位,目标函数将增加p个单位（max型问题)。也就是相应的一个单位的该资源在生产过程中产生的效益，即其价值。1）如果在最优解处约束正好取等号（也就是“紧约束”现有相应资源全部使用），该资源的对偶价格才可能不是0。例如本例中：第3行是紧约束，对应的是资源是漆工，其对偶价格值为10，表示当紧约束4DESKS+2TABLES+1.5CHAIRS=50WED)X1+X2+X3+X6+X7=50THU)X1+X2+X3+X4+X7=50FRI)X1+X2+X3+X4-X5=80SAT)X2+X3+X4-X5+X6=90SUN)X3+X4-X5+X6+X7=90ENDGIN7,其中“GIN7”表示7个变量都是一般整数变量。（仍然默认为取值是非负的）,求解后状态窗口中与整数相关的三个域有了相关结果:,“BestIP：94”表示当前得到的最好的整数解的目标函数值为94（人）。“IPBound：93.5”表示该整数规划目标值的下界为93.5（人）。“Branches：1”表示分枝数为1（即在第1个分枝中就找到了最优解）。我们前面说过，LINDO求解IP用的是分枝定界法。,显然，上面第二条“整数规划目标值的下界为93.5（人）”表明至少要聘用93.5名员工，由于员工人数只能是整数，所以至少要聘用94（人）。而第一条说明目前得到的解就是聘用94（人），所以已经是最优的了。,LPOPTIMUMFOUNDATSTEP8OBJECTIVEVALUE=93.3333359SETX2TO=4AT1,BND=-94.00TWIN=-93.5018NEWINTEGERSOLUTIONOF94.0000000ATBRANCH1PIVOT18BOUNDONOPTIMUM:93.50000DELETEX2ATLEVEL1ENUMERATIONCOMPLETE.BRANCHES=1PIVOTS=18LASTINTEGERSOLUTIONISTHEBESTFOUNDRE-INSTALLINGBESTSOLUTION.,求解结果的报告窗口如下：,（接下页）,OBJECTIVEFUNCTIONVALUE1)94.00000VARIABLEVALUEREDUCEDCOSTX10.0000001.000000X24.0000001.000000X340.0000001.000000X42.0000001.000000X534.0000001.000000X610.0000001.000000X74.0000001.000000ROWSLACKORSURPLUSDUALPRICESMON)0.0000000.000000TUE)2.0000000.000000WED)8.0000000.000000THU)0.0000000.000000FRI)0.0000000.000000SAT)0.0000000.000000SUN)0.0000000.000000NO.ITERATIONS=18BRANCHES=1DETERM.=1.000E0,报告窗口中前两行告诉我们：在8次迭代后找到对应的线性规划（LP）问题的最优解，最优值=93.3333359。LINDO求解IP用的是分枝定界法，紧接着几行显示的是分枝定界的信息，在第1个分枝中设定x2=4,并在该分枝中找到了整数解，而且就是全局整数最优解，所以算法停止。旋转迭代（PIVOT）共18次。,后面显示的是最后的最优解：x=(0,4,40,2,34,10,4).松弛和剩余变量（SLACKORSURPLUS）仍然可以表示约束的松紧程度，但目前IP尚无相应完善的敏感性分析理论，因此REDUCEDCOST和DUALPRICES的结果在整数规划中意义不大。,聘用方案（续）邮局一周中每天需要不同数目的雇员，设周一至少需要a1人，周二至少需要a2人，周三至少需要a3人，等等。又规定应聘者需连续工作5天，问邮局每天聘多少雇员才能既满足需求，又使聘用总人数最少。进一步考虑，上述指全时雇员（每天工作8小时）。如果邮局也可聘用半天雇员（每天工作4小时，连续工作5天），设全时和半时雇员的工资每小时为3元和2元，并且限制半时雇员的工作量不应超过总工作量的四分之一，问邮局如何安排聘用方案，使所付工资总额最少？,分析此时决策变量由两部分构成：全时雇员x1,x2,x3,x4,x5,x6,x7;半时雇员y1,y2,y3,y4,y5,y6,y7.目标值应该是雇员的总工资，标准是最少：min:Z=385xi245yi约束条件：每天的工作量应该折合为小时工作量(以周一的工作量为例)8(x4x5x6x7x1)4(y4y5y6y7y1)=8a1半时雇员的限制45yi=0.258(ai),一个旅行者的背包最多只能装6kg物品.现有4件物品重量为2kg,3kg,3kg,4kg,价值为1元,1.2元,0.9元,1.1元.应携带那些物品使得携带物品的价值最大?,0-1规划背包问题,决策变量：xj旅行者是否携带第j件物品,xj=0,1.约束条件2x1+3x2+3x3+4x46目标函数f=x1+1.2x2+0.9x3+1.1x4优劣标准：最大.,用Lingo软件求解0-1规划LinearInteractiveandGeneralOptimizerModel:Max=x1+1.2*x2+0.9*x3+1.1*x4;2*x1+3*x2+3*x3+4*x4=6;bin(x1);bin(x2);bin(x3);bin(x4);end,工厂可用k种不同的工艺生产n种产品