数学规划概述PPT演示课件

数学规划模型概述,假期你想去旅游。假如你只去一个地方而且只有一条线路可走，反倒省心一些如果你要去许多地方，又有许多路线，许多交通工具，而你还想尽量节省路费，那么你就要考虑“最优决策”或“最优（方案）设计”的问题了最优化(optimization)是企业运作、科技研发和工程设计中常见的问题要表述一个最优化问题(即建立数学模型)，应明确三个基本要素： 决策变量（decision variables） 约束条件(constraints) 目标函数(objective function),决策变量(decision variables):它们是决策者所控制的那些数量，它们取什么数值需要决策者来决策，最优化问题的求解就是找出决策变量的最优取值约束条件(constraints)：它们是决策变量在现实世界中所受到的限制，或者说决策变量在这些限制范围之内取值才有实际意义目标函数(objective function):它代表决策者希望对其进行优化的那个指标。目标函数是决策变量的函数,如果一个最优化问题的决策变量不是时间的函数，则属于静态优化(static optimization)或有限维优化(finite dimensional optimization)的范畴按照静态优化问题的结构是否线性分为线性规划和非线性规划线性规划的特征是目标函数和约束条件中的函数都是决策变量的线性函数，并且约束是必不可少的（否则不存在有实际意义的解）,三要素：决策变量；目标函数；约束条件,数学规划模型的一般形式,规划问题：求目标函数在约束条件下的最值可行解（只满足约束）与最优解(取到最优值),数学规划模型的简单分类,线性规划(LP) 目标和约束均为线性函数 非线性规划(NLP) 目标或约束中存在非线性函数 二次规划(QP) 目标为二次函数、约束为线性 整数规划(IP) 决策变量(全部或部分)为整数 整数线性规划(ILP)，整数非线性规划(INLP) 纯整数规划(PIP), 混合整数规划(MIP) 一般整数规划，0-1（整数）规划,连续优化,离散优化,数学规划,MATLAB优化工具箱能求解的优化模型,优化工具箱3.0 (MATLAB 7.0 R14),连续优化,离散优化,无约束优化,非线性极小fminunc,非光滑(不可微)优化fminsearch,非线性方程(组)fzerofsolve,全局优化暂缺,非线性最小二乘lsqnonlinlsqcurvefit,线性规划linprog,纯0-1规划 bintprog一般IP(暂缺),非线性规划fminconfminimaxfgoalattainfseminf,上下界约束fminbndfminconlsqnonlinlsqcurvefit,约束线性最小二乘lsqnonneglsqlin,约束优化,二次规划quadprog,优化,线性规划,非线性规划,二次规划,连续优化,整数规划,LINDO,LINGO,LINDO/LINGO软件能求解的模型,LP QP NLP IP 全局优化(选) ILP IQP INLP,LINGO软件的求解过程,LINGO预处理程序,线性优化求解程序,非线性优化求解程序,分枝定界管理程序,1. 确定常数2. 识别类型,1. 单纯形算法2. 内点算法(选),1、顺序线性规划法(SLP) 2、广义既约梯度法(GRG) (选) 3、多点搜索(Multistart) (选),LINGO软件的功能与特点,LINGO模型的优点,集成了线性(非线性) / 连续(整数) 优化功能 具有多点搜索 / 全局优化功能 提供了灵活的编程语言(矩阵生成器)，可方便地输入模型 提供与其他数据文件的接口 提供与其他编程语言的接口 LINDO API 可用于自主开发 运行速度较快,LINDO 公司软件产品简要介绍,美国芝加哥(Chicago)大学的Linus Schrage教授于1980年前后开发, 后来成立 LINDO系统公司（LINDO Systems Inc.）， 网址：,LINDO: Linear INteractive and Discrete Optimizer (V6.1)LINDO API: LINDO Application Programming Interface (V4.1)LINGO: Linear INteractive General Optimizer (V10.0)Whats Best!: (SpreadSheet e.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等。,保罗-萨缪尔逊（PAUL A SAMUELSON ）, 他发展了数理和动态经济理论，将经济科学提高到新的水平。他的研究涉及经济学的全部领域。于1970年获得诺贝尔经济学奖。华西里列昂惕夫（WASSILY LEONTIEF） ，美国人，他发展了投入产出方法，该方法在许多重要的经济问题中得到运用。曾获1973年诺贝尔经济科学奖。肯尼斯-J-阿罗（KENNETH J. ARROW）,美国人，因与约翰-希克斯（JOHN R. HICKS）共同深入研究了经济均衡理论和福利理论获得1972年诺贝尔经济学奖。牟顿-米勒（MERTON M. MILLER）,1923-2000, 美国人,由于他在金融经济学方面做出了开创性工作，于1990年获得诺贝尔经济奖。,一个农场有50亩土地, 20个劳动力, 计划种蔬菜,棉花和水稻. 种植这三种农作物每亩地分别需要劳动力 1/2 1/3 1/4, 预计每亩产值分别为 110元, 75元, 60元. 如何规划经营使经济效益最大.,种植蔬菜 x1 亩, 棉花 x2 亩, 水稻 x3 亩(决策变量)以取得最高的产值的方式达到收益最大的目标. 求f=110x1+75x2+60x3的最大值(目标函数、优劣标准) 约束条件 x1+x2+x3 50 1/2x1+1/3x2+1/4x3 20,例1 农作物种植,max : Z =110x1+75x2+60x3 s.t. x1+x2+x3 50 1/2x1+1/3x2+1/4x3 20 x1，x2，x3 0,目标函数和约束条件是线性的，是线性规划,关于线性的界定,比例性：决策变量变化引起目标的改变量与决策变量改变量成正比；可加性：每个决策变量对目标和约束的影响独立于其它变量；连续性：每个决策变量取连续值；确定性：线性规划中的参数aij , bi , ci为确定值。,正则模型 决策变量: x1,x2,xn. 目标函数: Z=c1x1+c2x2+cnxn. 求目标函数的最小或最大 约束条件: a11x1+a1nxnb1, am1x1+amnxnbm,线性规划的数学模型及其标准化,标准化模型 决策变量 x1, x2, xn, max Z = c1x1+ cnxn, s. t. a11x1+ a1nxn= b1, am1x1+ amnxn= bm, x1 0, xn 0,模型的标准化 10. 引入松弛变量将不等式约束变为等式约束 若有 ai1x1+ainxnbi, 则引入xn+i 0, 使得 ai1x1+ainxn+ xn+i =bi 若有 aj1x1+ajnxnbj, 则引入xn+j 0, 使得 aj1x1+ajnxn- xn+j =bj. 且此时目标函数Z=c1x1+c2x2+cnxn+0xn+1+0xn+m. 20. 将目标函数的优化变为目标函数的极大化. 若求 min Z, 令 Z=Z, 则问题变为 max Z. 30. 引入人工变量,使得所有变量均为非负. 若xi没有非负的条件,则引入 xi 0和xi0, 令xi= xi xi,则可使得问题的全部变量均非负.,线性规划的对偶性和影子价格,农作物种植（续）：一个农场有50亩土地,20个劳动力, 计划种蔬菜,棉花和水稻. 种植这三种农作物每亩地分别需要劳动力1/2 1/3 1/4,预计每亩产值分别为110元,75元,60元. 如果出租土地和劳动力如何规划经营使经济效益最大.,决策变量: 对单位土地和单位劳力出租价格分别为 y1 y2,目标函数: g=50y1+20y2,优劣准则: 应求g的最小值.(因为要达到的要求已经通过约束条件满足，决策者关心的是在最低要求达到时出租价格的心理底线是多少？),约束条件: y1+1/2y2 110 y1+1/3y2 75 y1+1/4y2 60 (成本不小于产值)（我出租出去要比自己种植合适。出租底线）,对偶线性规划,原问题 max f=cTx s.t. Ax b xi 0,i=1,2,n.,对偶问题 min f=bTy s.t. ATy c yi 0, i=1,2,m.,max : Z =110x1+75x2+60x3 s.t. x1+x2+x3 50 1/2x1+1/3x2+1/4x3 20 x1，x2，x3 0,A 是m n 矩阵， c 是 n 1向量，b 是 m 1向量 x 是 n 1向量, y 是 m 1向量,min：g=50y1+20y2s.t. y1+1/2y2 110 y1+1/3y2 75 y1+1/4y2 60 y1，y2 0,对偶定理: 互为对偶的两个线性规划问题 若其中一个有有穷的最优解,则另一个也有有穷的最优解,且最优值相等. 若两者之一有无界的最优解,则另一个没有可行解。,模型II 给出了生产中资源的最低估价. 这种价格涉及到资源的有效利用,它不是市场价格,而是根据资源在生产中做出的贡献确定的估价,被称为“影子价格”。,模型I 给出了生产中的资源最优分配方案。,灵敏度分析主要包括下面几个内容：1：当约束条件的右边常数项变化的影响；2：约束条件的系数变化的影响；3：目标函数的系数变化的影响。 可能的影响结果：1：最优解保持不变；2：基变量保持不变，但值变了；3：基本解变化。,线性规划的灵敏度分析,例：简单的线性规划（LP）问题,在空白的模型窗口中输入这个LP模型：,max 2x+3yst 4x+3y=10 3x+5y12end,附录1：用Lindo(Lingo)解线性规划,如图：,模型求解,用鼠标点击工具栏中的图标 ，或从菜单中选择Solve|Solve（Ctrl+S）命令,LINDO首先开始编译这个模型，编译没有错误则开始求解；求解时会首先显示如右图所示的LINDO“求解器运行状态窗口 ”。,求解器运行状态窗口显示的相应信息及含义,紧接着弹出一对话框，询问你是否需要做灵敏性分析（DO RANGE (SENSITIVITY) ANALYSIS? ）先选择“否（N）”按钮，这个窗口就会关闭。然后，再把状态窗口也关闭。,报告窗口,用鼠标选择“Window | Reports Window”（报告窗口），就可以查看该窗口的内容,保存文件,选择File|Save（F5）命令把“结果报告”保存在一个文件中（缺省的后缀名为LTX,即LINDO文本文件）类似地，回到模型窗口，可以把输入的模型保存在一个文件中。保存的文件将来可以用File | Open（F3）和File | View（F4）重新打开，用前者打开的程序可以进行修改，而后者只能浏览。,如果模型有错误,运行时会弹出出错信息报告窗口(LINDO Error Message)，则需要修改模型。,例：某家具公司制造书桌、餐桌和椅子，所用的资源有三种：木料、木工和漆工。生产数据如下表所示。,若要求桌子的生产量不超过5件，如何安排三种产品的生产可使利润最大？,解：,用DESKS、TABLES和CHAIRS分别表示三种产品的生产量（决策变量），容易建立LP模型。,在LINDO模型窗口中输入模型：,MAX 60 DESKS + 30 TABLES + 20 CHAIRSSUBJECT TO 2) 8 DESKS + 6 TABLES + CHAIRS = 48 3) 4 DESKS + 2 TABLES + 1.5 CHAIRS = 20 4) DESKS + 1 5 TABLES + O 5 CHAIRS = 8 5) TABLES = 5END,解这个模型，并对弹出的对话框 “ DO RANGE (SENSITIVITY) ANALYSIS? ” 选择“是（Y）”按钮，这表示你需要做灵敏性分析。然后，查看输出结果。,LP OPTIMUM FOUND AT STEP 2 OBJECTIVE FUNCTION VALUE 1) 280.0000 VARIABLE VALUE REDUCED COST DESKS 2.000000 0.000000 TABLES 0.000000 5.000000 CHAIRS 8.000000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2) 24.000000 0.000000 3) 0.000000 10.000000 4) 0.000000 10.000000 5) 5.000000 0.000000 NO. ITERATIONS= 1,输出结果的前半部分：,前半部分的输出结果的解释:,“LP OPTIMUM FOUND AT STEP2”表示两次迭代（旋转变换）后得到最优解。,“OBJECTIVE FUNCTION VALUE 1）280.000000”表示最优目标值为280。,“VALUE”给出最优解中各变量的值：造2个书桌（desks）, 0个餐桌（tables）, 8个椅子（chairs）。所以desks、chairs是基变量（取值非0），tables是非基变量（取值为0）。,“SLACK OR SURPLUS”给出松驰变量的值。（在最优的情况下资源的剩余量） 第2行松驰变量 =24 （第1行表示目标函数，第2行对应第1个约束） 第3行松驰变量 =0 第4行松驰变量 =0 第5行松驰变量 =5,“REDUCED COST”列出最优单纯形表中判别数所在行的变量的系数，表示当变量有微小变动时, 目标函数的变化率. 其中 基变量的reduced cost值应为0; 非基变量 Xj，相应的 reduced cost值1）表示当非基变量Xj 增加一个单位时，目标函数相应减少的量( max型问题)。2）理解为：为了使该非基变量变成基变量，目标函数中该变量前对应系数应增加的量。,本例中：变量TABLES对应的reduced cost值为5。 1）表示当非基变量TABLES 的值从0变为1时（此时假定其它非基变量保持不变,但为了满足约束条件，基变量显然会发生变化），此时的最优的目标函数值为280 - 5=275。 2）理解为目前table的单价30元偏低，不值得生产，如果生产的话至少35元。,“DUAL PRICE” （对偶价格）表示当对应约束有微小变动时, 目标函数的变化率. 输出结果中对应于每一个约束有一个对偶价格. 若其数值为p, 表示对应约束中不等式右端项若增加1个单位, 目标函数将增加p个单位（max型问题)。也就是相应的一个单位的该资源在生产过程中产生的效益，即其价值。1）如果在最优解处约束正好取等号（也就是“紧约束”现有相应资源全部使用），该资源的对偶价格才可能不是0。例如本例中：第3行是紧约束，对应的是资源是漆工，其对偶价格值为10，表示当紧约束 4 DESKS + 2 TABLES + 1.5 CHAIRS = 20变为 4 DESKS + 2 TABLES + 1.5 CHAIRS = 50TUE) X1 + X2 + X5 + X6 + X7 = 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 = 90ENDGIN 7,其中“GIN 7”表示7个变量都是一般整数变量。 （仍然默认为取值是非负的）,求解后状态窗口中与整数相关的三个域有了相关结果:,“Best IP ：94”表示当前得到的最好的整数解的目标函数值为94（人）。“IP Bound ：93.5” 表示该整数规划目标值的下界为93.5 （人）。“Branches ：1”表示分枝数为1（即在第1个分枝中就找到了最优解）。我们前面说过，LINDO求解IP用的是分枝定界法。,显然，上面第二条“整数规划目标值的下界为93.5 （人）”表明至少要聘用93.5名员工，由于员工人数只能是整数，所以至少要聘用94（人）。而第一条说明目前得到的解就是聘用94（人），所以已经是最优的了。,LP OPTIMUM FOUND AT STEP 8 OBJECTIVE VALUE = 93.3333359 SET X2 TO = 4 AT 1, BND= -94.00 TWIN= -93.50 18 NEW INTEGER SOLUTION OF 94.0000000 AT BRANCH 1 PIVOT 18 BOUND ON OPTIMUM: 93.50000 DELETE X2 AT LEVEL 1 ENUMERATION COMPLETE. BRANCHES= 1 PIVOTS= 18 LAST INTEGER SOLUTION IS THE BEST FOUND RE-INSTALLING BEST SOLUTION.,求解结果的报告窗口如下：,（接下页）,OBJECTIVE FUNCTION VALUE 1) 94.00000 VARIABLE VALUE REDUCED COST X1 0.000000 1.000000 X2 4.000000 1.000000 X3 40.000000 1.000000 X4 2.000000 1.000000 X5 34.000000 1.000000 X6 10.000000 1.000000 X7 4.000000 1.000000 ROW SLACK OR SURPLUS DUAL PRICES MON) 0.000000 0.000000 TUE) 2.000000 0.000000 WED) 8.000000 0.000000 THU) 0.000000 0.000000 FRI) 0.000000 0.000000 SAT) 0.000000 0.000000 SUN) 0.000000 0.000000 NO. ITERATIONS= 18 BRANCHES= 1 DETERM.= 1.000E 0,报告窗口中前两行告诉我们：在8次迭代后找到对应的线性规划（LP）问题的最优解，最优值=93.3333359。 LINDO求解IP用的是分枝定界法，紧接着几行显示的是分枝定界的信息，在第1个分枝中设定x2=4,并在该分枝中找到了整数解，而且就是全局整数最优解，所以算法停止。旋转迭代（PIVOT）共18次。,后面显示的是最后的最优解：x=(0,4,40,2,34,10,4).松弛和剩余变量（SLACK OR SURPLUS）仍然可以表示约束的松紧程度，但目前IP尚无相应完善的敏感性分析理论，因此REDUCED COST和DUAL PRICES的结果在整数规划中意义不大。,聘用方案（续） 邮局一周中每天需要不同数目的雇员，设周一至少需要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),一个旅行者的背包最多只能装 6 kg 物品. 现有4 件物品 重量为 2 kg , 3 kg, 3 kg, 4 kg, 价值为 1 元, 1.2元, 0.9元, 1.1元. 应携带那些物品使得携带物品的价值最大?,0-1规划 背包问题,决策变量： xj 旅行者是否携带第 j 件物品, xj = 0, 1.约束条件 2x1+3x 2+3x 3+4x 4 6目标函数 f=x1+1.2x2+0.9x3+1.1x4 优劣标准： 最大.,用Lingo 软件求解0-1规划Linear Interactive and General OptimizerModel: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种产品，每种产品的利润已知。在各种工艺条件下每种产品所消耗的资源是确定的，并且，工厂的总资源有一定限制。问应选择哪种工艺，每种产品各生产多少，使总利润最大,混合0-1规划 生产工艺问题,分析有关参量：用A1,A2,Ak表示k种工艺；用B1,B2,Bn表示n种产品；单件Bi的利润pi；在工艺Aj下,资源限制Qj，单件Bi的资源消耗cij。,决策变量：一是Bi的产量xi；一是工艺的选择。,目标函数: max: Zp1*x1+p2*x2+ +pn*xn,资源限制约束： cij*xi=0 为保证yj1的工艺不被选择，资源限制条件改为 cij*xi=Qj +yjM j=1,2, ,k 其中M充分大的一个正数。 （当yj1时，此约束条件对任何决策变量xi都成立，所以在k个资源限制约束中只有yj0的有效。）,某厂生产两个牌号的同一种产品，如何确定产量使利润最大,二次规划模型产销计划问题,=（100-x1-0.1 x2-2）x1+（280-0.2x1-2x2-3）x2=98 x1 + 277 x2 x12 0.3 x1 x2 2x22,约束,x1 + x2 100 x1 2 x2x1 , x2 0,二次规划模型(QP),若还要求产量为整数，则是整数二次规划模型(IQP),非线性规