数学规划概述

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

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

3、间的函数，则属于数，则属于静态优化静态优化(static optimization)或有或有限维优化限维优化(finite dimensional optimization)的的范畴范畴按照静态优化问题的结构是否线性分为按照静态优化问题的结构是否线性分为线性规线性规划划和和非线性规划非线性规划线性规划的特征是目标函数线性规划的特征是目标函数和约束条件中的函数都是决策变量的线性函数，和约束条件中的函数都是决策变量的线性函数，并且约束是必不可少的（否则不存在有实际意并且约束是必不可少的（否则不存在有实际意义的解）义的解）三要素：三要素：决策变量决策变量；目标函数目标函数；约束条件约束条件约约束束条

4、条件件决策变量决策变量数学规划模型的一般形式数学规划模型的一般形式njiDxljxgmixhtsxf,.,1, 0)(,.,1, 0)(. .)(min规划问题：求目标函数在约束条件下的最值规划问题：求目标函数在约束条件下的最值可行解（只满足约束）与最优解可行解（只满足约束）与最优解(取到最优值取到最优值)目标函数目标函数数学规划模型的数学规划模型的简单分类简单分类 线性规划线性规划(LP) 目标和约束均为线性函数目标和约束均为线性函数 非线性规划非线性规划(NLP) 目标或约束中存在非线性函数目标或约束中存在非线性函数 二次规划二次规划(QP) 目标为二次函数、约束为线性目标为二次函数、约束

5、为线性 整数规划整数规划(IP) 决策变量决策变量(全部或部分全部或部分)为整数为整数 整数整数线性线性规划规划(ILP)，整数，整数非线性非线性规划规划(INLP) 纯整数规划纯整数规划(PIP), 混合整数规划混合整数规划(MIP) 一般整数规划，一般整数规划，0-1（整数）规划（整数）规划njiDxljxgmixhtsxf,.,1, 0)(,.,1, 0)(. .)(min连连续续优优化化离离散散优优化化数学规划数学规划MATLABMATLAB优化工具箱优化工具箱能求解的优化模型能求解的优化模型优化工具箱优化工具箱3.0 (MATLAB 7.0 R14)连续优化连续优化离散优化离散优化无

6、约束优化无约束优化非线性非线性极小极小fminunc非光滑非光滑(不可不可微微)优化优化fminsearch非线性非线性方程方程(组组)fzerofsolve全局全局优化优化暂缺暂缺非线性非线性最小二乘最小二乘lsqnonlinlsqcurvefit线性规划线性规划linprog纯纯0-1规划规划 bintprog一般一般IP(暂缺暂缺)非线性规划非线性规划fminconfminimaxfgoalattainfseminf上下界约束上下界约束fminbndfminconlsqnonlinlsqcurvefit约束线性约束线性最小二乘最小二乘lsqnonneglsqlin约束优化约束优化二次规划

7、二次规划quadprog优化优化线性规划线性规划非线性规划非线性规划二次规划二次规划连续优化连续优化整数规划整数规划 LINDOLINGOLINDO/LINGOLINDO/LINGO软件能求解的模型软件能求解的模型 LP QP NLP IP 全局优化全局优化(选选) ILP IQP INLP LINGOLINGO软件的求解过程软件的求解过程 LINGO预处理程序预处理程序线性优化求解程序线性优化求解程序非线性优化求解程序非线性优化求解程序分枝定界管理程序分枝定界管理程序1. 确定常数确定常数2. 识别类型识别类型1. 单纯形算法单纯形算法2. 内点算法内点算法(选选)1、顺序线性规划法、顺序线

8、性规划法(SLP) 2、广义既约梯度法、广义既约梯度法(GRG) (选选) 3、多点搜索、多点搜索(Multistart) (选选) LINGO软件的功能与特点软件的功能与特点LINGO模型的优点模型的优点 集成了线性集成了线性(非线性非线性) / 连续连续(整数整数) 优化功能优化功能 具有多点搜索具有多点搜索 / 全局优化功能全局优化功能 提供了灵活的编程语言提供了灵活的编程语言(矩阵生成器矩阵生成器)，可方便地，可方便地输入模型输入模型 提供与其他数据文件的接口提供与其他数据文件的接口 提供与其他编程语言的接口提供与其他编程语言的接口 LINDO API 可用于自主开发可用于自主开发 运

9、行速度较快运行速度较快LINDO LINDO 公司软件产品简要介绍公司软件产品简要介绍 美国芝加哥美国芝加哥(Chicago)大学的大学的Linus Schrage教授于教授于1980年前后开发年前后开发, 后来成立后来成立 LINDO系统公司（系统公司（LINDO Systems Inc.），）， 网址：网址：http:/ LINDO: Linear INteractive and Discrete Optimizer (V6.1)LINDO API: LINDO Application Programming Interface (V4.1)LINGO: Linear INteractiv

10、e General Optimizer (V10.0)Whats Best!: (SpreadSheet e.g. EXCEL) (V8.0)演示演示(试用试用)版、高级版、超级版、工业版、扩展版版、高级版、超级版、工业版、扩展版 （求解（求解问题规模问题规模和和选件选件不同）不同）历史悠久，理论成熟，应用广泛运筹学的最基本的方法之一，网络规划、整数规划、目标规划和多目标规划都是以线性规划为基础的。解决稀缺资源最优分配的有效方法，使付出的费用最小或获得的收益最大。 线性规划模型线性规划模型1939年前苏联康托洛维奇（年前苏联康托洛维奇（KOHTOPOBUZ） 生产组织与计划中的生产组织与计划中

11、的 数学方法数学方法提出提出 “解乘数法解乘数法”。列奥尼德列奥尼德康托罗维奇，前苏联人，由于在康托罗维奇，前苏联人，由于在1939年创立年创立了享誉全球的线性规划要点，对资源最优分配理论做了享誉全球的线性规划要点，对资源最优分配理论做出了贡献，而获得诺贝尔经济学奖。出了贡献，而获得诺贝尔经济学奖。 线性规划理论的发展线性规划理论的发展美国科学院院士美国科学院院士DANTZIG（丹齐克），（丹齐克），1948年在年在研究美国空军资源的优化配置时提出线性规划及其通用研究美国空军资源的优化配置时提出线性规划及其通用解法解法 “单纯形法单纯形法”。被称为线性规划之父。被称为线性规划之父。 线性规划之

12、父的线性规划之父的Dantzig (Dantzig (丹齐克丹齐克) )。据说，一次上课，。据说，一次上课，DantzigDantzig迟到迟到 了，仰头看去，黑板上留了几个题目，他就抄了一下，回家后埋头苦做。了，仰头看去，黑板上留了几个题目，他就抄了一下，回家后埋头苦做。几个星期之后，疲惫的去找老师说，这件事情真的对不起，作业好像太几个星期之后，疲惫的去找老师说，这件事情真的对不起，作业好像太难了，我所以现在才交，言下很是惭愧。几天之后，他的老师就把他召难了，我所以现在才交，言下很是惭愧。几天之后，他的老师就把他召了过去，兴奋的告诉他说他太兴奋了。了过去，兴奋的告诉他说他太兴奋了。Dantz

13、igDantzig很不解很不解, , 后来才知道原后来才知道原来黑板上的题目根本就不是什么家庭作业，而是老师说的本领域的未解来黑板上的题目根本就不是什么家庭作业，而是老师说的本领域的未解决的问题，他给出的那个解法也就是单纯形法。这个方法是上个世纪前决的问题，他给出的那个解法也就是单纯形法。这个方法是上个世纪前十位的算法。十位的算法。 19601960年，年，“最佳资源利用的经济计算最佳资源利用的经济计算” ” 康托洛维奇康托洛维奇和库伯曼斯和库伯曼斯(Koopmans) (Koopmans) 。两人。两人因对资源最优分配理论的因对资源最优分配理论的贡献而获贡献而获19751975年诺贝尔经济学

14、奖年诺贝尔经济学奖 佳林佳林库普曼斯，美国人，他将数理统计学成功运用库普曼斯，美国人，他将数理统计学成功运用于经济计量学，对资源最优分配理论做出了贡献。于经济计量学，对资源最优分配理论做出了贡献。1961年，查恩斯与库伯提出了目标规划，艾吉利提出了用优先因子来处理多目标问题。20世纪70年代，斯姆李与杰斯开莱尼应用计算机处理目标规划问题从1964年诺贝尔奖设经济学奖后，到1992年28年间的32名获奖者中有13人(40%)从事过与线性规划有关的研究工作，其中著名的有Simon，Samullson，Leontief，Arrow，Miller等。保罗-萨缪尔逊（PAUL A SAMUELSON ）

15、, 他发展了数理和动态经济理论，将经济科学提高到新的水平。他的研究涉及经济学的全部领域。于1970年获得诺贝尔经济学奖。华西里列昂惕夫（WASSILY LEONTIEF） ，美国人，他发展了投入产出方法，该方法在许多重要的经济问题中得到运用。曾获1973年诺贝尔经济科学奖。肯尼斯-J-阿罗（KENNETH J. ARROW）,美国人，因与约翰-希克斯（JOHN R. HICKS）共同深入研究了经济均衡理论和福利理论获得1972年诺贝尔经济学奖。牟顿-米勒（MERTON M. MILLER）,1923-2000, 美国人,由于他在金融经济学方面做出了开创性工作，于1990年获得诺贝尔经济奖。一个

16、农场有一个农场有50亩土地亩土地, 20个劳动力个劳动力, 计划种蔬菜计划种蔬菜,棉花和水棉花和水稻稻. 种植这三种农作物每亩地分别需要劳动力种植这三种农作物每亩地分别需要劳动力 1/2 1/3 1/4, 预计每亩产值分别为预计每亩产值分别为 110元元, 75元元, 60元元. 如何规划经营使如何规划经营使经济效益最大经济效益最大. 种植蔬菜 x1 亩, 棉花 x2 亩, 水稻 x3 亩(决策变量)以取得最高的产值的方式达到收益最大的目标. 求f=110 x1+75x2+60 x3的最大值(目标函数、优劣标准) 约束条件 x1+x2+x3 50 1/2x1+1/3x2+1/4x3 20 例例

17、1 1 农作物种植农作物种植 max : Z =110 x1+75x2+60 x3 s.t. x1+x2+x3 50 1/2x1+1/3x2+1/4x3 20 x1，x2，x3 0目标函数和约束条件是线性的，是线性规划目标函数和约束条件是线性的，是线性规划如果规划问题的数学模型中，决策变量的取值可以是连续的，目标函数是决策变量的线性函数，约束条件是含决策变量的线性等式或不等式，则该类规划问题的数学模型称为线性规划的数学模型线性规划的数学模型。 实际问题中线性的含义：一是严格的比例性二是可叠加性关于线性的界定关于线性的界定比例性：决策变量变化引起目标的改变量与决策变量改变量成正比；可加性：每个决

18、策变量对目标和约束的影响独立于其它变量；连续性：每个决策变量取连续值；确定性：线性规划中的参数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, 模型的标准化模型

19、的标准化 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+0 xn+1+0 xn+m. 20. 将目标函数的优化变为目标函数的极大化. 若求 min Z, 令 Z=Z, 则问题变为 max Z. 30. 引入人工变量,使得所有变量均为非负. 若xi没有非负的条件,则引入 xi 0和xi0, 令xi= xi xi,则可使得问题的全部变量

20、均非负. 线性规划的对偶性和影子价格线性规划的对偶性和影子价格农作物种植（续）：农作物种植（续）：一个农场有50亩土地,20个劳动力, 计划种蔬菜,棉花和水稻. 种植这三种农作物每亩地分别需要劳动力1/2 1/3 1/4,预计每亩产值分别为110元,75元,60元. 如果土地和劳动力如何规划经营使经济效益最大. 决策变量决策变量: 对单位土地和单位劳力出租价格分别为对单位土地和单位劳力出租价格分别为 y1 y2目标函数目标函数: g=50y1+20y2优劣准则优劣准则: 应求应求g的最小值的最小值. (因为要达到的要求已经通过因为要达到的要求已经通过约束条件满足，决策者关心的是在最低要求达到时

21、出租价约束条件满足，决策者关心的是在最低要求达到时出租价格的心理底线是多少？格的心理底线是多少？)约束条件约束条件: 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 =110 x1+75x2+60 x3 s.t. x1+x2+x3 50 1/2x1+1/3x2+1

22、/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 给出

23、了生产中的资源最优分配方案。 灵敏度分析主要包括下面几个内容：1：当约束条件的右边常数项变化的影响；2：约束条件的系数变化的影响；3：目标函数的系数变化的影响。 可能的影响结果：1：最优解保持不变；2：基变量保持不变，但值变了；3：基本解变化。线性规划的灵敏度分析线性规划的灵敏度分析例：简单的线性规划（例：简单的线性规划（LP）问题）问题 0,12531034.32 yxyxyxtsyxzMax在在空白的模型窗口中输入这个空白的模型窗口中输入这个LP模型模型：max 2x+3yst 4x+3y=10 3x+5y12end附录附录1：用：用Lindo(Lingo)解线性规划解线性规划如图：如图：

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

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

26、：“N/A” （No Answer或或Not Applicable）表示无答案或无意义，因）表示无答案或无意义，因为这个模型中没有整数变量，不是整数规划（为这个模型中没有整数变量，不是整数规划（IP）。）。 求解器运行状态窗口显示的相应信息及含义名称名称含义含义IP Bound（整数规划的界）显示整数规划的界（对最大化问题显示上界；对最小化显示整数规划的界（对最大化问题显示上界；对最小化问题，显示下界）：问题，显示下界）：“N/A”含义同上。含义同上。 Branches（分枝数）显示分枝定界算法已经计算的分枝数：显示分枝定界算法已经计算的分枝数： “N/A”含义同含义同上。上。Elapsed

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

28、序运行过程中用鼠标点击该按钮终止计算。求解结束后这个按钮程中用鼠标点击该按钮终止计算。求解结束后这个按钮变成了灰色，再点击就不起作用了。变成了灰色，再点击就不起作用了。Close（关闭）该按钮只是关闭状态窗口，并不终止计算。如果你关闭该按钮只是关闭状态窗口，并不终止计算。如果你关闭了状态窗口，将来随时可以选择了状态窗口，将来随时可以选择WINDOW | OPEN STATUS WINDOW 菜单命令来再次打开这个窗口。菜单命令来再次打开这个窗口。紧接着弹出一对话框，询问你是否需要做灵敏性分析紧接着弹出一对话框，询问你是否需要做灵敏性分析（DO RANGE (SENSITIVITY) ANALY

29、SIS? ）先选择）先选择“否（否（N）”按钮，这个窗口就会关闭。然后，再把状态按钮，这个窗口就会关闭。然后，再把状态窗口也关闭。窗口也关闭。 报告窗口 用鼠标选择用鼠标选择“Window | Reports Window”（报告窗口），（报告窗口），就可以查看该窗口的内容就可以查看该窗口的内容 保存文件选择选择File|Save（F5）命令把命令把“结果报告结果报告”保存在一个文件中保存在一个文件中（缺省的后缀名为（缺省的后缀名为LTX,即即LINDO文本文件）文本文件）类似地，回到模型窗口，可以把输入的模型保存在一个文件类似地，回到模型窗口，可以把输入的模型保存在一个文件中。保存的文件将来

30、可以用中。保存的文件将来可以用File | Open（F3）和）和File | View（F4）重新打开，用前者打开的程序可以进行修改，而后者）重新打开，用前者打开的程序可以进行修改，而后者只能浏览。只能浏览。如果模型有错误如果模型有错误,运行时会弹出出错信息报告窗口运行时会弹出出错信息报告窗口(LINDO Error Message)，则需要修改模型。，则需要修改模型。例：某家具公司制造书桌、餐桌和椅子，所用的资源有例：某家具公司制造书桌、餐桌和椅子，所用的资源有三种：木料、木工和漆工。生产数据如下表所示。三种：木料、木工和漆工。生产数据如下表所示。每个书桌每个餐桌每个椅子现有资源总数木料8

31、单位6单位1单位48单位漆工4单位2单位1.5单位20单位木工2单位1.5单位0.5单位8单位成品单价60单位30单位20单位 若要求桌子的生产量不超过若要求桌子的生产量不超过5件，如何安排三种产品件，如何安排三种产品的生产可使利润最大？的生产可使利润最大？解解：用用DESKS、TABLES和和CHAIRS分别表示三种产品的分别表示三种产品的生产量（决策变量），容易建立生产量（决策变量），容易建立LP模型。模型。在在LINDO模型窗口中输入模型：模型窗口中输入模型：MAX 60 DESKS + 30 TABLES + 20 CHAIRSSUBJECT TO 2) 8 DESKS + 6 TAB

32、LES + 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) 28

33、0.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 OPTIM

34、UM 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”给出松驰变量的值给出松驰

35、变量的值。（在最优的情况下资源的剩余量）。（在最优的情况下资源的剩余量） 第第2行松驰变量行松驰变量 =24 （第（第1行表示目标函数，第行表示目标函数，第2行对应第行对应第1个约束）个约束） 第第3行松驰变量行松驰变量 =0 第第4行松驰变量行松驰变量 =0 第第5行松驰变量行松驰变量 =5“REDUCED COST”列出最优单纯形表中判别数所在行的变量的系数，表示当变列出最优单纯形表中判别数所在行的变量的系数，表示当变量有微小变动时量有微小变动时, 目标函数的变化率目标函数的变化率. 其中其中 基变量的基变量的reduced cost值应为值应为0; 非基变量非基变量 Xj，相应的，相应的

36、 reduced cost值值1）表示当非基变量）表示当非基变量Xj 增加一个单位时，目标函数相应减少的增加一个单位时，目标函数相应减少的量量( max型问题型问题)。2）理解为：为了使该非基变量变成基变量，目标函数中该变）理解为：为了使该非基变量变成基变量，目标函数中该变量前对应系数应增加的量。量前对应系数应增加的量。本例中：变量TABLES对应的reduced cost值为5。 1）表示当非基变量TABLES 的值从0变为1时（此时假定其它非基变量保持不变,但为了满足约束条件，基变量显然会发生变化），此时的最优的目标函数值为280 - 5=275。 2）理解为目前table的单价30元偏低

37、，不值得生产，如果生产的话至少35元。“DUAL PRICE” （对偶价格）表示当对应约束有微小变动时（对偶价格）表示当对应约束有微小变动时, 目标函数的变化率目标函数的变化率. 输出结果中对应于每一个约束有一个对偶价输出结果中对应于每一个约束有一个对偶价格格. 若其数值为若其数值为p, 表示对应约束中不等式右端项若增加表示对应约束中不等式右端项若增加1个单位个单位, 目标函数将增加目标函数将增加p个单位（个单位（max型问题型问题)。也就是相应的一个单。也就是相应的一个单位的该资源在生产过程中产生的效益，即其价值。位的该资源在生产过程中产生的效益，即其价值。1）如果在最优解处约束正好取等号（

38、也就是）如果在最优解处约束正好取等号（也就是“紧约束紧约束”现有相现有相应资源全部使用），该资源的对偶价格才可能不是应资源全部使用），该资源的对偶价格才可能不是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 = 5

39、0THU) 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”表示当前表示当前得到的最好的整数解的目得到的最好的整数解的目标函数值为标函数

40、值为94（人）。（人）。“IP Bound ：93.5” 表示表示该整数规划目标值的下界该整数规划目标值的下界为为93.5 （人）。（人）。“Branches ：1”表示分表示分枝数为枝数为1（即在第（即在第1个分枝个分枝中就找到了最优解）。中就找到了最优解）。我们前面说过，我们前面说过，LINDO求解求解IP用的是分枝定界法。用的是分枝定界法。显然，上面第二条显然，上面第二条“整数规划目标值的下界为整数规划目标值的下界为93.5 （人）（人）”表明至少要表明至少要聘用聘用93.5名员工，由于员工人数只能是整数，所以至少要聘用名员工，由于员工人数只能是整数，所以至少要聘用94（人）。（人）。而

41、第一条说明目前得到的解就是聘用而第一条说明目前得到的解就是聘用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

42、= 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.00

43、0000 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报告窗口中前两行告诉我们：在报告窗口中前两行告

44、诉我们：在8次迭代后找到对应的线次迭代后找到对应的线性规划（性规划（LP）问题的最优解，最优值）问题的最优解，最优值=93.3333359。 LINDO求解求解IP用的是分枝定界法，紧接着几行显示的是分用的是分枝定界法，紧接着几行显示的是分枝定界的信息，在第枝定界的信息，在第1个分枝中设定个分枝中设定x2=4,并在该分枝中并在该分枝中找到了整数解，而且就是全局整数最优解，所以算法停止。找到了整数解，而且就是全局整数最优解，所以算法停止。旋转迭代（旋转迭代（PIVOT）共）共18次。次。 后面显示的是最后的最优解：后面显示的是最后的最优解：x=(0,4,40,2,34,10,4).松弛和剩余变量

45、（松弛和剩余变量（SLACK OR SURPLUS）仍然可以表示）仍然可以表示约束的松紧程度，但目前约束的松紧程度，但目前IP尚无相应完善的敏感性分析理尚无相应完善的敏感性分析理论，因此论，因此REDUCED COST和和DUAL PRICES的结果在整数的结果在整数规划中意义不大。规划中意义不大。 聘用方案（续）聘用方案（续） 邮局一周中每天需要不同数目的雇员，设周一至少需要a1人，周二至少需要a2人，周三至少需要a3人，等等。又规定应聘者需连续工作5天，问邮局每天聘多少雇员才能既满足需求，又使聘用总人数最少。 进一步考虑，上述指全时雇员（每天工作8小时）。如果邮局也可聘用半天雇员（每天工作

46、4小时，连续工作5天），设全时和半时雇员的工资每小时为3元和2元，并且限制半时雇员的工作量不应超过总工作量的四分之一，问邮局如何安排聘用方案，使所付工资总额最少？ 分析分析此时决策变量由两部分构成：此时决策变量由两部分构成： 全时雇员全时雇员x1,x2, x3,x4,x5,x6,x7; 半时雇员半时雇员y1,y2, y3,y4,y5,y6,y7.目标值应该是雇员的总工资，标准是最少：目标值应该是雇员的总工资，标准是最少： min : Z=385xi245yi约束条件：约束条件： 每天的工作量应该折合为小时工作量每天的工作量应该折合为小时工作量(以周一的工作量为例以周一的工作量为例) 8(x4x

47、5x6x7x1)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

48、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种产品；单件

49、种产品；单件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都都成立，所以在成立

50、，所以在k个资源限制约束中只有个资源限制约束中只有yj0的有的有效。）效。）牌牌号号产量成本价格甲甲x1q1p1乙乙x2q2p2假设假设A产销平衡产销平衡假设假设Bp随随x (两种牌号两种牌号)增加而减小，呈线性关系增加而减小，呈线性关系12111211121211111, 0,aaaabxaxabp某厂生产两个牌号的同一种产品，如何确定产量使利润最大某厂生产两个牌号的同一种产品，如何确定产量使利润最大21222221222212122, 0,aaaabxaxabp二次规划模型产销计划问题二次规划模型产销计划问题22211121,)()(),(max21xqpxqpxxzxx目标目标利润最大利润最大=（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 二次规划模型二次