数学规划概述幻灯片.ppt

《数学规划概述幻灯片.ppt》由会员分享，可在线阅读，更多相关《数学规划概述幻灯片.ppt（91页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数学规划概述第1页，共91页，编辑于2022年，星期六 假期你想去旅游。假如你只去一个地方而且只有一条线路可走，反倒省心一些如果你要去许多地方，又有许多路线，许多交通工具，而你还想尽量节省路费，那么你就要考虑“最优决策”或“最优（方案）设计”的问题了最优化(optimization)是企业运作、科技研发和工程设计中常见的问题要表述一个最优化问题(即建立数学模型)，应明确三个基本要素：决策变量（decision variables）约束条件(constraints)目标函数(objective function)第2页，共91页，编辑于2022年，星期六决决策策变变量量(decision var

2、iables):它它们们是是决决策策者者所所控控制制的的那那些些数数量量，它它们们取取什什么么数数值值需需要要决决策策者者来来决决策策，最最优优化化问问题的求解就是找出决策变量的最优取值题的求解就是找出决策变量的最优取值约约束束条条件件(constraints)：它它们们是是决决策策变变量量在在现现实实世世界界中中所所受受到到的的限限制制，或或者者说说决决策策变变量量在在这这些些限限制制范范围围之内取值才有实际意义之内取值才有实际意义目目标标函函数数(objective function):它它代代表表决决策策者者希希望望对对其其进进行优化的那个指标。行优化的那个指标。目标函数是决策变量的函数

3、目标函数是决策变量的函数目标函数是决策变量的函数目标函数是决策变量的函数第3页，共91页，编辑于2022年，星期六如如果果一一个个最最优优化化问问题题的的决决策策变变量量不不是是时时间间的的函函数数，则则属属于于静静态态优优化化(static optimization)或或有有限限维维优优化化(finite dimensional optimization)的范畴的范畴按按照照静静态态优优化化问问题题的的结结构构是是否否线线性性分分为为线线性性规规划划和和非非线线性性规规划划线线性性规规划划的的特特征征是是目目标标函函数数和和约约束束条条件件中中的的函函数数都都是是决决策策变变量量的的线线性性

4、函函数数，并并且且约约束是必不可少的（否则不存在有实际意义的解）束是必不可少的（否则不存在有实际意义的解）第4页，共91页，编辑于2022年，星期六三要素：三要素：决策变量决策变量；目标函数目标函数；约束条件约束条件约约束束条条件件决策变量决策变量数学规划模型的一般形式数学规划模型的一般形式规划问题：求目标函数在约束条件下的最值规划问题：求目标函数在约束条件下的最值可行解（只满足约束）与最优解可行解（只满足约束）与最优解(取到最优值取到最优值)目标函数目标函数第5页，共91页，编辑于2022年，星期六数学规划模型的数学规划模型的简单分类简单分类线性规划线性规划(LP)目标和约束均为线性函数目标

5、和约束均为线性函数非线性规划非线性规划(NLP)目标或约束中存在非线性函数目标或约束中存在非线性函数二次规划二次规划(QP)目标为二次函数、约束为线性目标为二次函数、约束为线性整数规划整数规划(IP)决策变量决策变量(全部或部分全部或部分)为整数为整数整数整数线性线性规划规划(ILP)，整数，整数非线性非线性规划规划(INLP)纯整数规划纯整数规划(PIP),混合整数规划混合整数规划(MIP)一般整数规划，一般整数规划，0-1（整数）规划（整数）规划连连续续优优化化离离散散优优化化数学规划数学规划第6页，共91页，编辑于2022年，星期六MATLABMATLAB优化工具箱优化工具箱能求解的优化

6、模型能求解的优化模型优化工具箱优化工具箱3.0(MATLAB7.0R14)连续优化连续优化离散优化离散优化无约束优化无约束优化非线性非线性极小极小fminunc非光滑非光滑(不可不可微微)优化优化fminsearch非线性非线性方方程程(组组)fzerofsolve全局全局优化优化暂缺暂缺非线性非线性最小二乘最小二乘lsqnonlinlsqcurvefit线性规划线性规划linprog纯纯0-1规划规划bintprog一般一般IP(暂缺暂缺)非线性规划非线性规划fminconfminimaxfgoalattainfseminf上下界约束上下界约束fminbndfminconlsqnonlinl

7、sqcurvefit约束线性约束线性最小二乘最小二乘lsqnonneglsqlin约束优化约束优化二次规划二次规划quadprog第7页，共91页，编辑于2022年，星期六优化优化线性规划线性规划非线性规划非线性规划二次规划二次规划连续优化连续优化整数规划整数规划LINDOLINGOLINDO/LINGOLINDO/LINGO软件能求解的模型软件能求解的模型第8页，共91页，编辑于2022年，星期六LPQPNLPIP全局优化全局优化(选选)ILPIQPINLPLINGOLINGO软件的求解过程软件的求解过程 LINGO预处理程序预处理程序线性优化求解程序线性优化求解程序非线性优化求解程序非线性

8、优化求解程序分枝定界管理程序分枝定界管理程序1.确定常数确定常数2.识别类型识别类型1.单纯形算法单纯形算法2.内点算法内点算法(选选)1、顺序线性规划法、顺序线性规划法(SLP)2、广义既约梯度法、广义既约梯度法(GRG)(选选)3、多点搜索、多点搜索(Multistart)(选选)第9页，共91页，编辑于2022年，星期六LINGO软件的功能与特点软件的功能与特点LINGO模型的优点模型的优点集成了线性集成了线性(非线性非线性)/连续连续(整数整数)优化功能优化功能具有多点搜索具有多点搜索/全局优化功能全局优化功能提供了灵活的编程语言提供了灵活的编程语言(矩阵生成器矩阵生成器)，可方便地输

9、入，可方便地输入模型模型提供与其他数据文件的接口提供与其他数据文件的接口提供与其他编程语言的接口提供与其他编程语言的接口LINDOAPI可用于自主开发可用于自主开发运行速度较快运行速度较快第10页，共91页，编辑于2022年，星期六LINDO LINDO 公司软件产品简要介绍公司软件产品简要介绍美国芝加哥美国芝加哥(Chicago)大学的大学的LinusSchrage教授于教授于1980年年前后开发前后开发,后来成立后来成立LINDO系统公司（系统公司（LINDOSystemsInc.），），网址：网址：http:/LINDO:LinearINteractiveandDiscreteOptim

10、izer(V6.1)LINDOAPI:LINDOApplicationProgrammingInterface(V4.1)LINGO:LinearINteractiveGeneralOptimizer(V10.0)WhatsBest!:(SpreadSheete.g.EXCEL)(V8.0)演示演示(试用试用)版、高级版、超级版、工业版、扩展版版、高级版、超级版、工业版、扩展版（求（求解解问题规模问题规模和和选件选件不同）不同）第11页，共91页，编辑于2022年，星期六历史悠久，理论成熟，应用广泛运筹学的最基本的方法之一，网络规划、整数规划、目标规划和多目标规划都是以线性规划为基础的。解决稀

11、缺资源最优分配的有效方法，使付出的费用最小或获得的收益最大。线性规划模型线性规划模型第12页，共91页，编辑于2022年，星期六1939年前苏联康托洛维奇（年前苏联康托洛维奇（KOHTOPOBUZ）生生产组织与计划中的产组织与计划中的数学方法提出数学方法提出“解乘数法解乘数法”。列奥尼德列奥尼德康托罗维奇，前苏联人，由于在康托罗维奇，前苏联人，由于在1939年创年创立了享誉全球的线性规划要点，对资源最优分配理论立了享誉全球的线性规划要点，对资源最优分配理论做出了贡献，而获得诺贝尔经济学奖。做出了贡献，而获得诺贝尔经济学奖。线性规划理论的发展线性规划理论的发展第13页，共91页，编辑于2022年

12、，星期六美国科学院院士美国科学院院士DANTZIG（丹齐克），（丹齐克），1948年在研究美年在研究美国空军资源的优化配置时提出线性规划及其通用解法国空军资源的优化配置时提出线性规划及其通用解法“单纯形单纯形法法”。被称为线性规划之父。被称为线性规划之父。线线性性规规划划之之父父的的Dantzig Dantzig(丹丹齐齐克克)。据据说说，一一次次上上课课，DantzigDantzig迟迟到到 了了，仰仰头头看看去去，黑黑板板上上留留了了几几个个题题目目，他他就就抄抄了了一一下下，回回家家后后埋埋头头苦苦做做。几几个个星星期期之之后后，疲疲惫惫的的去去找找老老师师说说，这这件件事事情情真真的的

13、对对不不起起，作作业业好好像像太太难难了了，我我所所以以现现在在才才交交，言言下下很很是是惭惭愧愧。几几天天之之后后，他他的的老老师师就就把把他他召召了了过过去去，兴兴奋奋的的告告诉诉他他说说他他太太兴兴奋奋了了。DantzigDantzig很很不不解解,后后来来才才知知道道原原来来黑黑板板上上的的题题目目根根本本就就不不是是什什么么家家庭庭作作业业，而而是是老老师师说说的的本本领领域域的的未未解解决决的的问问题题，他给出的那个解法也就是单纯形法。这个方法是上个世纪前十位的算法。他给出的那个解法也就是单纯形法。这个方法是上个世纪前十位的算法。第14页，共91页，编辑于2022年，星期六 196

14、01960年，年，“最佳资源利用的经济计算最佳资源利用的经济计算”康托洛维奇和库康托洛维奇和库伯曼斯伯曼斯(Koopmans)(Koopmans)。两人因对资源最优分配理论的贡献而获。两人因对资源最优分配理论的贡献而获19751975年诺贝尔经济学奖年诺贝尔经济学奖 佳林佳林库普曼斯，美国人，他将数理统计学成功运用库普曼斯，美国人，他将数理统计学成功运用于经济计量学，对资源最优分配理论做出了贡献。于经济计量学，对资源最优分配理论做出了贡献。第15页，共91页，编辑于2022年，星期六1961年，查恩斯与库伯提出了目标规划，艾吉利提出了用优先因子来处理多目标问题。20世纪70年代，斯姆李与杰斯开

15、莱尼应用计算机处理目标规划问题从1964年诺贝尔奖设经济学奖后，到1992年28年间的32名获奖者中有13人(40%)从事过与线性规划有关的研究工作，其中著名的有Simon，Samullson，Leontief，Arrow，Miller等。保罗-萨缪尔逊（PAUL A SAMUELSON）,他发展了数理和动态经济理论，将经济科学提高到新的水平。他的研究涉及经济学的全部领域。于1970年获得诺贝尔经济学奖。华西里列昂惕夫（WASSILY LEONTIEF），美国人，他发展了投入产出方法，该方法在许多重要的经济问题中得到运用。曾获1973年诺贝尔经济科学奖。肯尼斯-J-阿罗（KENNETH J.A

16、RROW）,美国人，因与约翰-希克斯（JOHN R.HICKS）共同深入研究了经济均衡理论和福利理论获得1972年诺贝尔经济学奖。牟顿-米勒（MERTON M.MILLER）,1923-2000,美国人,由于他在金融经济学方面做出了开创性工作，于1990年获得诺贝尔经济奖。第16页，共91页，编辑于2022年，星期六一一个个农农场场有有50亩亩土土地地,20个个劳劳动动力力,计计划划种种蔬蔬菜菜,棉棉花花和和水水稻稻.种种植植这这三三种种农农作作物物每每亩亩地地分分别别需需要要劳劳动动力力1/21/31/4,预预计计每每亩亩产产值值分分别别为为110元元,75元元,60元元.如如何何规规划划经

17、经营营使使经经济济效益最大效益最大.种植蔬菜 x1 亩,棉花 x2 亩,水稻 x3 亩(决策变量)以取得最高的产值的方式达到收益最大的目标.求f=110 x1+75x2+60 x3的最大值(目标函数、优劣标准)约束条件 x1+x2+x3 50 1/2x1+1/3x2+1/4x3 20例例1 1 农作物种植农作物种植max:Z=110 x1+75x2+60 x3s.t.x1+x2+x3 501/2x1+1/3x2+1/4x3 20 x1，x2，x30目标函数和约束条件是线性的，是线性规划目标函数和约束条件是线性的，是线性规划第17页，共91页，编辑于2022年，星期六如果规划问题的数学模型中，决

18、策变量的取值可以是连续的，目标函数是决策变量的线性函数，约束条件是含决策变量的线性等式或不等式，则该类规划问题的数学模型称为线性线性规划的数学模型规划的数学模型。实际问题中线性的含义：一是严格的比例性二是可叠加性关于线性的界定关于线性的界定第18页，共91页，编辑于2022年，星期六比例性：决策变量变化引起目标的改变量与决策变量改变量成正比；可加性：每个决策变量对目标和约束的影响独立于其它变量；连续性：每个决策变量取连续值；确定性：线性规划中的参数aij,bi,ci为确定值。第19页，共91页，编辑于2022年，星期六 正则模型正则模型 决策变量:x1,x2,xn.目标函数:Z=c1x1+c2

19、x2+cnxn.求目标函数的最小或最大 约束条件:a11x1+a1nxnb1,am1x1+amnxnbm线性规划的数学模型及其标准化线性规划的数学模型及其标准化第20页，共91页，编辑于2022年，星期六 标准化模型标准化模型 决策变量 x1,x2,xn,max Z=c1x1+cnxn,s.t.a11x1+a1nxn=b1,am1x1+amnxn=bm,x1 0,xn 0,第21页，共91页，编辑于2022年，星期六 模型的标准化模型的标准化 10.引入松弛变量将不等式约束变为等式约束 若有 ai1x1+ainxnbi,则引入xn+i 0,使得 ai1x1+ainxn+xn+i=bi 若有 a

20、j1x1+ajnxnbj,则引入xn+j 0,使得 aj1x1+ajnxn-xn+j=bj.且此时目标函数Z=c1x1+c2x2+cnxn+0 xn+1+0 xn+m.20.将目标函数的优化变为目标函数的极大化.若求 min Z,令 Z=Z,则问题变为 max Z.30.引入人工变量,使得所有变量均为非负.若xi没有非负的条件,则引入 xi 0和xi0,令xi=xi xi,则可使得问题的全部变量均非负.第22页，共91页，编辑于2022年，星期六线性规划的对偶性和影子价格线性规划的对偶性和影子价格农农作作物物种种植植（续续）：一个农场有50亩土地,20个劳动力,计划种蔬菜,棉花和水稻.种植这三

21、种农作物每亩地分别需要劳动力1/2 1/3 1/4,预计每亩产值分别为110元,75元,60元.如果出出出出租租租租土地和劳动力如何规划经营使经济效益最大.决策变量决策变量:对单位土地和单位劳力出租价格分别为对单位土地和单位劳力出租价格分别为y1y2目标函数目标函数:g=50y1+20y2优优劣劣准准则则:应应求求g的的最最小小值值.(因因为为要要达达到到的的要要求求已已经经通通过过约约束束条条件件满满足足，决决策策者者关关心心的的是是在在最最低低要要求求达达到到时时出出租租价价格格的的心心理理底底线线是是多多少？少？)约束条件约束条件:y1+1/2y2 110y1+1/3y2 75y1+1/

22、4y2 60(成本不小于成本不小于产值产值)（我出租出去要比自己种植合适。出租底线）（我出租出去要比自己种植合适。出租底线）第23页，共91页，编辑于2022年，星期六对偶线性规划对偶线性规划 原问题 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=110 x1+75x2+60 x3s.t.x1+x2+x3 501/2x1+1/3x2+1/4x3 20 x1，x2，x30 A 是m n 矩阵，c 是 n 1向量，b 是 m 1向量 x 是 n 1向量,y 是 m 1向量min：g=50y1+

23、20y2s.t.y1+1/2y2 110y1+1/3y2 75y1+1/4y2 60y1，y20第24页，共91页，编辑于2022年，星期六对偶定理对偶定理:互为对偶的两个线性规划问题 若其中一个有有穷的最优解,则另一个也有有穷的最优解,且最优值相等.若两者之一有无界的最优解,则另一个没有可行解。模型II 给出了生产中资源的最低估价.这种价格涉及到资源的有效利用,它不是市场价格,而是根据资源在生产中做出的贡献确定的估价,被称为“影子价格影子价格”。模型I 给出了生产中的资源最优分配方案。第25页，共91页，编辑于2022年，星期六 灵敏度分析主要包括下面几个内容：1：当约束条件的右边常数项变化

24、的影响；2：约束条件的系数变化的影响；3：目标函数的系数变化的影响。可能的影响结果：1：最优解保持不变；2：基变量保持不变，但值变了；3：基本解变化。线性规划的灵敏度分析线性规划的灵敏度分析第26页，共91页，编辑于2022年，星期六例：简单的线性规划（例：简单的线性规划（LP）问题）问题 在空白的模型窗口中输入这个在空白的模型窗口中输入这个LP模型：模型：max 2x+3yst 4x+3y=10 3x+5y12end附录附录1：用：用Lindo(Lingo)解线性规划解线性规划第27页，共91页，编辑于2022年，星期六如图：如图：第28页，共91页，编辑于2022年，星期六模型求解用鼠标点

25、击工具栏中的图标用鼠标点击工具栏中的图标 ，或从菜单中选择或从菜单中选择Solve|Solve（Ctrl+S）命令命令LINDO首先开始编译这个模首先开始编译这个模型，编译没有错误则开始求型，编译没有错误则开始求解；解；求解时会首先显示如右图所求解时会首先显示如右图所示的示的LINDO“求解器运行状态窗口求解器运行状态窗口”。第29页，共91页，编辑于2022年，星期六名称名称含含义义Status（当前状态）显显示当前求解状示当前求解状态态：“Optimal”表示已表示已经经达到最达到最优优解；解；其他可能的其他可能的显显示示还还有三个：有三个：Feasible(可行解可行解),Infeasi

26、ble(不可行不可行),Unbounded(最最优值优值无界无界)。Iterations（迭代次数）显显示迭代次数：示迭代次数：“2”表示表示经过经过了了2次迭代。次迭代。Infeasibility（不可行性）约约束不束不满满足的量足的量(即各个即各个约约束条件不束条件不满满足的足的“数量数量”的和；的和；特特别别注意不是注意不是“不不满满足的足的约约束个数束个数”)：“0”表示表示这这个解是个解是可行的。可行的。Objective（当前的目标值）显显示目示目标标函数当前的函数当前的值值：7.45455。BestIP（整数规划当前的最佳目标值）显显示整数示整数规规划当前的最佳目划当前的最佳目标

27、值标值：“N/A”（NoAnswer或或NotApplicable）表示无答案或无意）表示无答案或无意义义，因，因为这为这个模型个模型中没有整数中没有整数变变量，不是整数量，不是整数规规划（划（IP）。）。求解器运行状态窗口显示的相应信息及含义第30页，共91页，编辑于2022年，星期六名称名称含含义义IP Bound（整数规划的界）显显示整数示整数规规划的界（划的界（对对最大化最大化问题显问题显示上界；示上界；对对最小化最小化问问题题，显显示下界）：示下界）：“N/A”含含义义同上。同上。Branches（分枝数）显显示分枝定界算法已示分枝定界算法已经计经计算的分枝数：算的分枝数：“N/A”

28、含含义义同上。同上。Elapsed Time（所用时间）显显示示计计算所用算所用时间时间（秒）：（秒）：“0.00”说说明明计计算太快了，用算太快了，用时时还还不到不到0.005秒。秒。Update Interval（刷新本界面的时间间隔）显显示和控制刷新本界面的示和控制刷新本界面的时间间时间间隔：隔：“1”表示表示1秒；用秒；用户户可可以直接在界面上修改以直接在界面上修改这这个个时间间时间间隔。隔。Interrupt Solver（中断求解程序）当模型当模型规规模比模比较较大大时时（尤其（尤其对对整数整数规规划），可能求解划），可能求解时间时间会很会很长长，如果不想再等待下去，如果不想再等待

29、下去时时，可以在程序运行，可以在程序运行过过程中程中用鼠用鼠标标点点击该击该按按钮终钮终止止计计算。求解算。求解结结束后束后这这个按个按钮变钮变成了成了灰色，再点灰色，再点击击就不起作用了。就不起作用了。Close（关闭）该该按按钮钮只是关只是关闭闭状状态态窗口，并不窗口，并不终终止止计计算。如果你关算。如果你关闭闭了了状状态态窗口，将来随窗口，将来随时时可以可以选择选择WINDOW|OPEN STATUS WINDOW 菜菜单单命令来再次打开命令来再次打开这这个窗口。个窗口。第31页，共91页，编辑于2022年，星期六紧紧接接着着弹弹出出一一对对话话框框，询询问问你你是是否否需需要要做做灵灵

30、敏敏性性分分析析（DO RANGE(SENSITIVITY)ANALYSIS?）先先选选择择“否否（N）”按按钮钮，这个窗口就会关闭。然后，再把状态窗口也关闭。这个窗口就会关闭。然后，再把状态窗口也关闭。第32页，共91页，编辑于2022年，星期六报告窗口 用鼠标选择用鼠标选择“Window|Reports Window”（报告窗口），（报告窗口），就可以查看该窗口的内容就可以查看该窗口的内容 第33页，共91页，编辑于2022年，星期六保存文件选择选择File|Save（F5）命令把命令把“结果报告结果报告”保存在一个文件中（缺省的保存在一个文件中（缺省的后缀名为后缀名为LTX,即即LIND

31、O文本文件）文本文件）类似地，回到模型窗口，可以把输入的模型保存在一个文件中。保存的类似地，回到模型窗口，可以把输入的模型保存在一个文件中。保存的文件将来可以用文件将来可以用File|Open（F3）和）和File|View（F4）重新打开，用前）重新打开，用前者打开的程序可以进行修改，而后者只能浏览。者打开的程序可以进行修改，而后者只能浏览。如果模型有错误如果模型有错误,运行时会弹出出错信息报告窗口运行时会弹出出错信息报告窗口(LINDO Error Message)，则需要修改模型。，则需要修改模型。第34页，共91页，编辑于2022年，星期六例例：某某家家具具公公司司制制造造书书桌桌、餐

32、餐桌桌和和椅椅子子，所所用用的的资资源源有有三三种种：木木料、木工和漆工。生产数据如下表所示。料、木工和漆工。生产数据如下表所示。每个书桌每个餐桌每个椅子现有资源总数木料8单位6单位1单位48单位漆工4单位2单位1.5单位20单位木工2单位1.5单位0.5单位8单位成品单价60单位30单位20单位 若若要要求求桌桌子子的的生生产产量量不不超超过过5件件，如如何何安安排排三三种种产产品品的的生生产产可使利润最大？可使利润最大？第35页，共91页，编辑于2022年，星期六解解：用用DESKS、TABLES和和CHAIRS分别表示三种产品的生分别表示三种产品的生产量（决策变量），容易建立产量（决策变

33、量），容易建立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）”按钮，这表示你需要做灵敏性分析。然后，查按钮，这表示你需要做灵敏性分析

34、。然后，查看输出结果。看输出结果。第36页，共91页，编辑于2022年，星期六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

35、5)5.000000 0.000000 NO.ITERATIONS=1输出结果的前半部分：输出结果的前半部分：第37页，共91页，编辑于2022年，星期六前半部分的输出结果的解释前半部分的输出结果的解释:“LP OPTIMUM FOUND AT STEP2”表示两次迭代（旋转变换）后得到最优解。表示两次迭代（旋转变换）后得到最优解。“OBJECTIVE FUNCTION VALUE 1）280.000000”表示最优目标值为表示最优目标值为280。“VALUE”给出最优解中各变量的值：造给出最优解中各变量的值：造2个书桌（个书桌（desks）,0个餐桌（个餐桌（tables）,8个椅个椅子（子

36、（chairs）。所以）。所以desks、chairs是基变量（取值非是基变量（取值非0），），tables是非基变量是非基变量（取值为（取值为0）。）。“SLACK OR SURPLUS”给出松驰变量的值给出松驰变量的值。（在最优的情况下资源的剩余量）。（在最优的情况下资源的剩余量）第第2行松驰变量行松驰变量=24 （第（第1行表示目标函数，第行表示目标函数，第2行对应第行对应第1个约束）个约束）第第3行松驰变量行松驰变量=0 第第4行松驰变量行松驰变量=0 第第5行松驰变量行松驰变量=5第38页，共91页，编辑于2022年，星期六“REDUCED COST”列出最优单纯形表中判别数所在行的

37、变量的系数，表示当变量有微小变动列出最优单纯形表中判别数所在行的变量的系数，表示当变量有微小变动时时,目标函数的变化率目标函数的变化率.其中其中 基变量的基变量的reduced cost值应为值应为0;非基变量非基变量 Xj，相应的，相应的 reduced cost值值1）表示当非基变量）表示当非基变量Xj 增加一个单位时，目标函数相应减少的量增加一个单位时，目标函数相应减少的量(max型问题型问题)。2）理解为：为了使该非基变量变成基变量，目标函数中该变量前对应）理解为：为了使该非基变量变成基变量，目标函数中该变量前对应系数应增加的量。系数应增加的量。本例中：变量TABLES对应的reduc

38、ed cost值为5。1）表示当非基变量TABLES 的值从0变为1时（此时假定其它非基变量保持不变,但为了满足约束条件，基变量显然会发生变化），此时的最优的目标函数值为280-5=275。2）理解为目前table的单价30元偏低，不值得生产，如果生产的话至少35元。第39页，共91页，编辑于2022年，星期六“DUAL PRICE”（对对偶偶价价格格）表表示示当当对对应应约约束束有有微微小小变变动动时时,目目标标函函数数的的变变化化率率.输输出出结结果果中中对对应应于于每每一一个个约约束束有有一一个个对对偶偶价价格格.若若其其数数值值为为p,表表示示对对应应约约束束中中不不等等式式右右端端项

39、项若若增增加加1个个单单位位,目目标标函函数数将将增增加加p个个单单位位（max型型问问题题)。也也就就是是相相应应的的一一个个单单位位的的该该资资源在生产过程中产生的效益，即其价值。源在生产过程中产生的效益，即其价值。1）如如果果在在最最优优解解处处约约束束正正好好取取等等号号（也也就就是是“紧紧约约束束”现现有有相相应应资资源源全全部部使使用用），该该资资源源的的对对偶偶价价格格才才可可能能不不是是0。例例如如本本例例中中：第第3行行是是紧紧约约束束，对对应应的的是是资资源源是是漆漆工工，其其对对偶偶价价格格值值为为10，表表示示当当紧紧约约束束 4 DESKS+2 TABLES+1.5

40、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个变量都是一般整数变量。个变量都是一般整数变量。（仍然默认为取值是非负的）（仍然默认为取值是非负的）第69页，共91页，编辑于2022年，星期六求解后状态窗口中与整数相关的三个域有了相关结果求解后状态窗

41、口中与整数相关的三个域有了相关结果:“Best IP：94”表示当前得表示当前得到的最好的整数解的目标函到的最好的整数解的目标函数值为数值为94（人）。（人）。“IP Bound：93.5”表示该表示该整数规划目标值的下界为整数规划目标值的下界为93.5（人）。（人）。“Branches：1”表示分枝表示分枝数为数为1（即在第（即在第1个分枝中就个分枝中就找到了最优解）。找到了最优解）。我们前面说过，我们前面说过，LINDO求解求解IP用的是用的是分枝定界法。分枝定界法。显然，上面第二条显然，上面第二条“整数规划目标值的下界为整数规划目标值的下界为93.5（人）（人）”表明至少要聘用表明至少要

42、聘用93.5名名员工，由于员工人数只能是整数，所以至少要聘用员工，由于员工人数只能是整数，所以至少要聘用94（人）。而第一条说明目前得（人）。而第一条说明目前得到的解就是聘用到的解就是聘用94（人），所以已经是最优的了。（人），所以已经是最优的了。第70页，共91页，编辑于2022年，星期六 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

43、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.求解结果的报告窗口如下：求解结果的报告窗口如下：（接下页）（接下页）第71页，共91页，编辑于2022年，星期六 OBJECTIVE FUNCTION VALUE 1)94.00000 VARIABLE VALUE REDUCED COST X1 0.000000 1.000000 X

44、2 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.0

45、00000 0.000000 NO.ITERATIONS=18 BRANCHES=1 DETERM.=1.000E 0第72页，共91页，编辑于2022年，星期六报告窗口中前两行告诉我们：在报告窗口中前两行告诉我们：在8次迭代后找到对应的线性规次迭代后找到对应的线性规划（划（LP）问题的最优解，最优值）问题的最优解，最优值=93.3333359。LINDO求解求解IP用的是分枝定界法，紧接着几行显示的是分枝定用的是分枝定界法，紧接着几行显示的是分枝定界的信息，在第界的信息，在第1个分枝中设定个分枝中设定x2=4,并在该分枝中找到了整数并在该分枝中找到了整数解，而且就是全局整数最优解，所以算法停

46、止。旋转迭代解，而且就是全局整数最优解，所以算法停止。旋转迭代（PIVOT）共）共18次。次。后面显示的是最后的最优解：后面显示的是最后的最优解：x=(0,4,40,2,34,10,4).松弛和剩余变量（松弛和剩余变量（SLACK OR SURPLUS）仍然可以表示约束）仍然可以表示约束的松紧程度，但目前的松紧程度，但目前IP尚无相应完善的敏感性分析理论，因此尚无相应完善的敏感性分析理论，因此REDUCED COST和和DUAL PRICES的结果在整数规划中意义不的结果在整数规划中意义不大。大。第73页，共91页，编辑于2022年，星期六 聘用方案（续）聘用方案（续）邮局一周中每天需要不同数

47、目的雇员，设周一至少需要a1人，周二至少需要a2人，周三至少需要a3人，等等。又规定应聘者需连续工作5天，问邮局每天聘多少雇员才能既满足需求，又使聘用总人数最少。进一步考虑，上述指全时雇员（每天工作8小时）。如果邮局也可聘用半天雇员（每天工作4小时，连续工作5天），设全时和半时雇员的工资每小时为3元和2元，并且限制半时雇员的工作量不应超过总工作量的四分之一，问邮局如何安排聘用方案，使所付工资总额最少？第74页，共91页，编辑于2022年，星期六分析分析此时决策变量由两部分构成：此时决策变量由两部分构成：全时雇员全时雇员x1,x2,x3,x4,x5,x6,x7;半时雇员半时雇员y1,y2,y3,

48、y4,y5,y6,y7.目标值应该是雇员的总工资，标准是最少：目标值应该是雇员的总工资，标准是最少：min:Z=385xi245yi约束条件：约束条件：每天的工作量应该折合为小时工作量每天的工作量应该折合为小时工作量(以周一的工作量为例以周一的工作量为例)8(x4x5x6x7x1)4(y4y5y6y7y1)=8a1半时雇员的限制半时雇员的限制45yi=0.258(ai)第75页，共91页，编辑于2022年，星期六一个旅行者的背包最多只能装 6 kg 物品.现有4 件物品 重量为 2 kg,3 kg,3 kg,4 kg,价值为 1 元,1.2元,0.9元,1.1元.应携带那些物品使得携带物品的价

49、值最大?0-1规划规划背包问题背包问题决策变量：xj 旅行者是否携带第 j 件物品,xj=0,1.约束条件 2x1+3x 2+3x 3+4x 4 6目标函数 f=x1+1.2x2+0.9x3+1.1x4 优劣标准：最大.第76页，共91页，编辑于2022年，星期六用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第77页，共91页，编辑于2022年，星期

50、六 工厂可用k种不同的工艺生产n种产品，每种产品的利润已知。在各种工艺条件下每种产品所消耗的资源是确定的，并且，工厂的总资源有一定限制。问应选择哪种工艺，每种产品各生产多少，使总利润最大 混合混合0-1规划规划生产工艺问题生产工艺问题第78页，共91页，编辑于2022年，星期六分析分析有有 关关 参参 量量：用用 A1,A2,Ak表表 示示 k种种 工工 艺艺；用用B1,B2,Bn表表示示n种种产产品品；单单件件Bi的的利利润润pi；在在工工艺艺Aj下下,资源限制资源限制Qj，单件，单件Bi的资源消耗的资源消耗cij。决策变量：一是决策变量：一是Bi的产量的产量xi；一是工艺的选择。；一是工艺