线性规划模型的应用

线性规划模型的应用线性规划模型的应用线性规划与运筹学线性规划与运筹学v线性规划属于最优化的一个分支，研究在线性目标线性规划属于最优化的一个分支，研究在线性目标函数和线性约束条件下的最优化问题函数和线性约束条件下的最优化问题v线性规划在实践中有非常多的应用。西方的所谓管线性规划在实践中有非常多的应用。西方的所谓管理科学其实主要是运筹学，而线性规划是运筹学的理科学其实主要是运筹学，而线性规划是运筹学的一个主要内容。一个主要内容。v下面先介绍什么是最优化问题下面先介绍什么是最优化问题什么是优化问题什么是优化问题v1.1 运筹学模型运筹学模型v假设有一项工作需要假设有一项工作需要5周完成，其间要往返于甲地与周完成，其间要往返于甲地与乙地之间。每周一要乘飞机从甲地出发，周三返回乙地之间。每周一要乘飞机从甲地出发，周三返回v普通往返机票价格为普通往返机票价格为400元元v如果往返时间跨越周末，则可享受如果往返时间跨越周末，则可享受20%的优惠的优惠v单程机票的价格是普通往返机票价格的单程机票的价格是普通往返机票价格的75%v如何安排购票策略，使得如何安排购票策略，使得总费用最小总费用最小？什么是优化问题什么是优化问题v做一件工作，有多种方法，哪种方法做好呢？做一件工作，有多种方法，哪种方法做好呢？列出所有可行方案，逐一评价列出所有可行方案，逐一评价什么样的方法是可行的？实际问题有哪些约束？什么样的方法是可行的？实际问题有哪些约束？如何评价解决方案？如何评价解决方案？v求解问题的求解问题的策略策略往往不能一步求到最优解往往不能一步求到最优解先找到一个可行的方案，再尝试改进它先找到一个可行的方案，再尝试改进它v问题可能是问题可能是离散型离散型的，也可能是的，也可能是连续型连续型的的机票购买的问题属于机票购买的问题属于.如何改进方案？如何如何改进方案？如何判断已达最优？判断已达最优？1.1 运筹学模型运筹学模型v对方案的限制：每周周一从甲至乙，周三返对方案的限制：每周周一从甲至乙，周三返v可能的方案可能的方案1、购买五张普通的甲、购买五张普通的甲-乙乙-甲往返票，每周一出发，甲往返票，每周一出发，周三返回周三返回2、购买一张甲、购买一张甲-乙的单程机票和乙的单程机票和4张跨周末的甲张跨周末的甲-乙乙-甲往返票，再买一张乙甲往返票，再买一张乙-甲单程票甲单程票3、先购买一张第一周周一出发、最后一周星期三、先购买一张第一周周一出发、最后一周星期三返程的甲返程的甲-乙乙-甲往返票，再购买甲往返票，再购买4张跨周末的乙张跨周末的乙-甲甲-乙往返票乙往返票1.1 运筹学模型运筹学模型v评价：以最小费用为标准评价：以最小费用为标准v方案方案1：5*400=2000v方案方案2：0.75*400+4*(0.8*400)+0.75*400=1880v方案方案3：5*(0.8*400)=16001.1 运筹学模型运筹学模型v考虑用一段长为考虑用一段长为L的电线来围成一个矩形，要让这个的电线来围成一个矩形，要让这个矩形的面积最大，其长和宽该取多少呢？矩形的面积最大，其长和宽该取多少呢？v与前面购买机票问题不同，这里的长和宽是与前面购买机票问题不同，这里的长和宽是连续变连续变化化的，可能方案的个数有无穷多种！的，可能方案的个数有无穷多种！v我们可以控制的因素是矩形的长与宽，记为我们可以控制的因素是矩形的长与宽，记为w和和hv可行方案要满足：可行方案要满足：w+h=L/2w=0,h=0v下面建立该问题的模型下面建立该问题的模型1.1 运筹学模型运筹学模型vmax z=whvs.t.2(w+h)=L,w,h=0v第一部分为第一部分为目标函数目标函数，这里是求，这里是求wh的最大值，目标的最大值，目标函数即为评价方案优劣的标准函数即为评价方案优劣的标准(指标指标)通常求效益、成绩、利润时求通常求效益、成绩、利润时求最大值最大值求费用、风险、代价时求求费用、风险、代价时求最小值最小值v第二部分为第二部分为约束条件约束条件，表明可行方案必须满足的条，表明可行方案必须满足的条件件基本概念基本概念v满足所有约束条件的解称为满足所有约束条件的解称为可行解可行解(feasible)v所有可行解构成问题的所有可行解构成问题的可行域可行域或或可行解集合可行解集合v所有可行解中取得最好目标值的解称为所有可行解中取得最好目标值的解称为最优解最优解(optimal)v如果在模型求解的过程中丢掉了部分可行解，则得如果在模型求解的过程中丢掉了部分可行解，则得到的最优解可能实际上只是局部最优解或次优解到的最优解可能实际上只是局部最优解或次优解除非明确的可排除部分区域除非明确的可排除部分区域(确定不可行或最优解确定不可行或最优解一定不在其中一定不在其中)，否则不要丢掉可能方案！，否则不要丢掉可能方案！可行解、最优解、次优解可行解、最优解、次优解v对于离散型的机票购买问题，可行方案是有限多的对于离散型的机票购买问题，可行方案是有限多的若问题的规模较小，总可以枚举出所有解，求得若问题的规模较小，总可以枚举出所有解，求得最优解最优解问题规模较大时，只能找到问题规模较大时，只能找到满意解满意解或或可行解可行解v对于连续型的问题，可行方案有无限多种对于连续型的问题，可行方案有无限多种不能采用枚举的方法，需要找到最优解所满足的不能采用枚举的方法，需要找到最优解所满足的充分性条件充分性条件最优性条件可能是局部的，也可能是全局的最优性条件可能是局部的，也可能是全局的最优解不仅与目标函数有关，还与可行域有关最优解不仅与目标函数有关，还与可行域有关1.2 运筹学模型的求解运筹学模型的求解v运筹学模型在数学上实际就是运筹学模型在数学上实际就是最优化模型最优化模型：在满足：在满足一定约束条件下一定约束条件下(也可能是没有约束的也可能是没有约束的)，求目标函，求目标函数的最小值数的最小值(或最大值或最大值)v运筹学问题通常是用某些算法求解出来的，往往要运筹学问题通常是用某些算法求解出来的，往往要借助于计算机借助于计算机v有时求出最优解非常困难，这时使用有时求出最优解非常困难，这时使用启发式方启发式方法转法转而求取较好的可行解而求取较好的可行解1.2 运筹学模型的求解运筹学模型的求解v困难困难实际运筹学问题的目标和约束可能很难用数学式实际运筹学问题的目标和约束可能很难用数学式来描述来描述不好的模型会加重求解的复杂度，所以要不断调不好的模型会加重求解的复杂度，所以要不断调整模型整模型化简问题，抓住关键因素：很多问题在数学上是化简问题，抓住关键因素：很多问题在数学上是非常困难的，但是加上实际背景的约束，往往可非常困难的，但是加上实际背景的约束，往往可得到简化得到简化仅有数学是不够的仅有数学是不够的v最忌讳的是最忌讳的是生搬硬套生搬硬套模型，一定要从问题的背景出模型，一定要从问题的背景出发仔细分析，这样才能发仔细分析，这样才能理解模型和改进模型理解模型和改进模型v产生一个问题的因素有很多，要分析出哪些是实际产生一个问题的因素有很多，要分析出哪些是实际可以操作的环节可以操作的环节v建模竞赛建模竞赛(尤其是美国赛尤其是美国赛)的题目往往从实践中来，的题目往往从实践中来，又要求返回到实际中去又要求返回到实际中去MCM 2007 The Airplane Seating ProblemvAirlines are free to seat passengers waiting to board an aircraft in any order whatsoever.It has become customary to seat passengers with special needs first,followed by first-class passengers(who sit at the front of the plane).vThen coach and business-class passengers are seated by groups of rows,beginning with the row at the back of the plane and proceeding forward.MCM 2007 The Airplane Seating ProblemvApart from consideration of the passengers wait time,from the airlines point of view,time is money,and boarding time is best minimized.The plane makes money for the airline only when it is in motion,and long boarding times limit the number of trips that a plane can make in a day.vThe development of larger planes,such as the Airbus A380(800 passengers),accentuate the problem of minimizing boarding(and deboarding)time.MCM 2007 The Airplane Seating ProblemvDevise and compare procedures for boarding and deboarding planes with varying numbers of passengers:small(85210),midsize(210330),and large(450800).vPrepare an executive summary,not to exceed two single-spaced pages,in which you set out your conclusions to an audience of airline executives,gate agents,and flight crews.MCM 2007 The Airplane Seating ProblemvAn article appeared in the NY Times Nov 14,2006 addressing procedures currently being followed and the importance to the airline of finding better solutions.vThe article can be seen at:http:/ MCM 2007 The Airplane Seating Problemv这道题目要用仿真算法来检验各种登机方案这道题目要用仿真算法来检验各种登机方案困难：不可能穷举所有可能的方案困难：不可能穷举所有可能的方案v问题：能否按照前面的图引导乘客？为什么？问题：能否按照前面的图引导乘客？为什么？1.6 运用运筹学的几个步骤运用运筹学的几个步骤v其实与数学建模的步骤非常类似其实与数学建模的步骤非常类似v问题定义问题定义目标、限制、假设目标、限制、假设v模型构造模型构造实际的问题往往不能使用标准模型而要加以改动实际的问题往往不能使用标准模型而要加以改动v模型求解模型求解有时很容易，有时很困难，尤其是数据量较大时有时很容易，有时很困难，尤其是数据量较大时可能需要返回去修改模型！可能需要返回去修改模型！注意注意灵敏度分析灵敏度分析！1.6 运用运筹学的几个步骤运用运筹学的几个步骤v模型验证模型验证模型是否正确模型是否正确(模型是在一定假设和简化下作出的模型是在一定假设和简化下作出的)？是否符合实际？是否符合实际？有时可以用仿真来检验有时可以用仿真来检验v实施实施针对实际操作的人，使用不那么数学的语言解释针对实际操作的人，使用不那么数学的语言解释方案方案线形规划模型线形规划模型v2.1 二维变量的线形规划模型二维变量的线形规划模型v例例2.1-1 某公司使用某公司使用M1和和M2两种原料生产内、外墙两种原料生产内、外墙涂料涂料v内墙涂料的日需量不超过外墙涂料的日需量加内墙涂料的日需量不超过外墙涂料的日需量加1吨，吨，内墙涂料的最大日需量是内墙涂料的最大日需量是2吨吨每吨产品使用原料的吨数每吨产品使用原料的吨数日最大可用日最大可用量量(吨吨)外墙涂料外墙涂料内墙涂料内墙涂料原料原料 M1原料原料 M26142246每吨利润每吨利润542.1 二维变量的线形规划模型二维变量的线形规划模型v下面建立下面建立求日总利润最大求日总利润最大的生产方案的线性规划模的生产方案的线性规划模型型v线形规划模型的构成线形规划模型的构成决策变量决策变量目标函数目标函数约束条件约束条件2.1 二维变量的线形规划模型二维变量的线形规划模型v例例2.1-1v很自然设内、外墙涂料的日产量为很自然设内、外墙涂料的日产量为x1和和x2v目标函数：利润目标函数：利润 Z=5*x1+4*x2v这里是求利润的最大值这里是求利润的最大值Max Z=5*x1+4*x2约束条件约束条件v原料数量的约束原料数量的约束M1只有只有24吨吨 6x1+4x2=24M2只有只有6吨吨 x1+2x2=6v市场需求量的约束市场需求量的约束x2-x1=1x2=0 2.1 二维变量的线形规划模型二维变量的线形规划模型v例例2.1-1Max Z=5*x1+4*x26x1+4x2=24x1+2x2=6x2-x1=1x2=0线性规划模型的性质线性规划模型的性质v线性体现在线性体现在目标函数目标函数和和约束条件都是决策变量的线约束条件都是决策变量的线性函数性函数v线性蕴含着线性规划必须满足的线性蕴含着线性规划必须满足的3条基本性质条基本性质v比例性比例性每个决策变量无论在目标函数中还是在约束条件每个决策变量无论在目标函数中还是在约束条件中其贡献与决策变量的值成比例。中其贡献与决策变量的值成比例。目标函数中决策变量的系数称为目标函数中决策变量的系数称为价值系数价值系数约束条件中决策变量的系数称为约束条件中决策变量的系数称为工艺系数工艺系数线性规划模型的性质线性规划模型的性质v线性蕴含着线性规划必须满足的线性蕴含着线性规划必须满足的3条基本性质条基本性质v可加性可加性所有变量在目标函数和约束中的总贡献等于每个所有变量在目标函数和约束中的总贡献等于每个变量各自贡献的直接和变量各自贡献的直接和NaCl=Na+Cl-?1+1=？v确定性确定性线性规划中的系数都是确定的线性规划中的系数都是确定的如果不是确定的，则可能要用如果不是确定的，则可能要用概率模型概率模型来描述来描述思考思考v假定涂料厂采用按量打折销售的方法，把它的外墙假定涂料厂采用按量打折销售的方法，把它的外墙涂料卖给某个批发商。如果批发商每日的购买量不涂料卖给某个批发商。如果批发商每日的购买量不超过超过2吨，则工厂每吨的利润是吨，则工厂每吨的利润是5000元，否则是元，否则是4500元。元。v给出目标函数的数学表达式，得到的函数还是线性给出目标函数的数学表达式，得到的函数还是线性的吗？的吗？2.2 线性规划的图解法线性规划的图解法v对只有两个决策变量的线型规划问题，可以通过图对只有两个决策变量的线型规划问题，可以通过图解法直观的求解解法直观的求解v图解法的步骤：图解法的步骤：v1.求可行解集合：求可行解集合：分别求出满足每个约束包括变量非分别求出满足每个约束包括变量非负要求的区域，其交集为负要求的区域，其交集为可行解集合可行解集合，或称或称可行域可行域v2.绘制目标函数图形。绘制目标函数图形。先过原点作一条矢量指向点先过原点作一条矢量指向点（c1,c2)，矢量的方向就是目标函数增加的方向，称，矢量的方向就是目标函数增加的方向，称为为梯度方向梯度方向，再作一条与矢量垂直的直线，这条直再作一条与矢量垂直的直线，这条直线就是线就是目标函数的等值线目标函数的等值线；2.2 线性规划的图解法线性规划的图解法v图解法的步骤：图解法的步骤：v3.求最优解。求最优解。依据目标函数求最大或最小移动目标函依据目标函数求最大或最小移动目标函数直线，直线与可行域相交的点对应的坐标就是数直线，直线与可行域相交的点对应的坐标就是最最优解。优解。v一般地，将目标函数直线放在可行域中一般地，将目标函数直线放在可行域中 求最大值时直线沿着矢量方向移动求最大值时直线沿着矢量方向移动 求最小值时沿着矢量的反方向移动求最小值时沿着矢量的反方向移动思考思考v1 已知已知x1,x2=0，确定下面每个独立约束的可行空间，确定下面每个独立约束的可行空间-3x1+x2=52x1-3x2=12x1-x2=0思考思考v2 确定下列情况中确定下列情况中Z的增加方向的增加方向max z=x1-x2max z=-5x1-6x2max z=-x1+2x2max z=-3x1+x2x1x2O1020304010203040(3,4)(15,10)最优解最优解X=(15,10)最优值最优值Z=85注意观察可行域的注意观察可行域的几何特征及最优解几何特征及最优解在可行域中的位置在可行域中的位置246x1x2246最优解最优解X=(3,1)最优值最优值Z=5(3,1)min Z=x1+2x2(1,2)可行域无界可行域无界注意观察可行域的注意观察可行域的几何特征及最优解几何特征及最优解在可行域中的位置在可行域中的位置246x1x2246X（2）（3,1）X（1）（1,3）(5,5)min Z=5x1+5x2有无穷多个最优解有无穷多个最优解即具有多重解即具有多重解,通解为通解为 01 当当=0.5时，时，=(x1,x2)=0.5(1,3)+0.5(3,1)=(2,2)注意观察可行域的注意观察可行域的几何特征及最优解几何特征及最优解在可行域中的位置在可行域中的位置246x1x2246(1,2)无界解无界解(无最优解无最优解)max Z=x1+2x2x1x2O10203040102030405050无无可行解可行解即无最优解即无最优解max Z=10 x1+4x2线性规划解的形式线性规划解的形式v由以上例题可知，线性规划的解有由以上例题可知，线性规划的解有4种形式：种形式：1.有唯一最优解有唯一最优解2.有多重解有多重解3.有无界解有无界解4.无可行解无可行解v1、2情形为有最优解情形为有最优解v3、4情形为无最优解情形为无最优解线性规划解的特点线性规划解的特点v由以上例题可知，两个变量的线性规划的可行域和由以上例题可知，两个变量的线性规划的可行域和最优解有如下特点：最优解有如下特点：v1.可行域为可行域为多边形多边形v2.若可行域有界，则必有最优解若可行域有界，则必有最优解v3.若存在最优解，则一定出现在若存在最优解，则一定出现在边界边界上上v4.最优值一定在边界的最优值一定在边界的顶点顶点取到取到2.3 线性规划应用选讲线性规划应用选讲v例例 2.3-1 城市更新模型城市更新模型v某市由于财政预算不足，决定征用一块市内的住宅某市由于财政预算不足，决定征用一块市内的住宅区域进行现代化开发，以增加税收来源。区域进行现代化开发，以增加税收来源。v改造工程包括：改造工程包括：拆除不符合标准的旧住宅以腾出空地拆除不符合标准的旧住宅以腾出空地新建住宅新建住宅2.3 线性规划应用选讲线性规划应用选讲v例例 2.3-1 城市更新模型城市更新模型v拆除大约拆除大约300套旧住宅，每套占地套旧住宅，每套占地0.25英亩。拆除成英亩。拆除成本为每套本为每套2000美元美元v新的单、双、三和四户住宅单元的土地面积分别为新的单、双、三和四户住宅单元的土地面积分别为0.18、0.28、0.4和和0.5英亩。英亩。v街道、开阔地和公共设施占可利用土地面积的街道、开阔地和公共设施占可利用土地面积的15%v三户与四户住宅单元的总和至少占总住宅单元的三户与四户住宅单元的总和至少占总住宅单元的25%。单户和双户住宅单元数分别至少占总单元数。单户和双户住宅单元数分别至少占总单元数的的20%和和10%2.3 线性规划应用选讲线性规划应用选讲v例例 2.3-1 城市更新模型城市更新模型v单、双、三和四户住宅每单元征税额分别为单、双、三和四户住宅每单元征税额分别为1000$、1900$、2700$和和3400$v单、双、三和四户住宅每单元的建筑成本分别是单、双、三和四户住宅每单元的建筑成本分别是50000$、70000$、130000$和和160000$。v通过当地银行最高可筹措到通过当地银行最高可筹措到15 000 000$v问题：应建多少单元各种类型的住宅使得税收总额问题：应建多少单元各种类型的住宅使得税收总额达到最大？达到最大？建立数学模型建立数学模型v要考虑的因素要考虑的因素如何评价一个决策方案的优劣？如何评价一个决策方案的优劣？从哪些方面进行优化，优化的目标是什么？从哪些方面进行优化，优化的目标是什么？这个目标如何用数学式表达？这个目标如何用数学式表达？v很自然首先要列出决策变量，也就是在这个问题中很自然首先要列出决策变量，也就是在这个问题中哪些因素是我们可以控制的。最终目标函数用决策哪些因素是我们可以控制的。最终目标函数用决策变量来表达。变量来表达。v决策变量及其范围在一定程度上给出了决策变量及其范围在一定程度上给出了系统的边界系统的边界超出边界的因素不是模型中要考虑的超出边界的因素不是模型中要考虑的建立数学模型建立数学模型v决策变量的设置有时相当简单，有时富于技巧性决策变量的设置有时相当简单，有时富于技巧性v原则原则 便于表述和理解，把内在联系或规律表示清楚便于表述和理解，把内在联系或规律表示清楚 便于求解便于求解v以上两个要求可能是矛盾的！以上两个要求可能是矛盾的！v在这个例子中，我们可以决定的量是要拆除的旧单在这个例子中，我们可以决定的量是要拆除的旧单元的数目和每种新单元建设的数目元的数目和每种新单元建设的数目v分别设分别设x1、x2、x3和和x4为单、双、三、四户住宅单为单、双、三、四户住宅单元的建造数；设元的建造数；设x5为拆除旧住宅单元的数目为拆除旧住宅单元的数目v下面就要用下面就要用xi来表示目标函数和约束来表示目标函数和约束v目标：目标：v约束约束v土地可用量：土地可用量：新建住宅面积新建住宅面积=净可用面积净可用面积0.18x1+0.28x2+0.4x3+0.5x4=0.85*(0.25x5)v被拆除的旧住宅数量不超过被拆除的旧住宅数量不超过300套套x5=0.25(x1+x2+x3+x4)v单户和双户住宅单元数分别至少占总单元数的单户和双户住宅单元数分别至少占总单元数的20%和和10%x10.2(x1+x2+x3+x4)x20.1(x1+x2+x3+x4)v总预算资金的限制总预算资金的限制v(50 x1+70 x2+130 x3+160 x4)+2x5=0,Ii=0vSi实际上是临时工人的变化数，可以是正实际上是临时工人的变化数，可以是正(人数增加，人数增加，新雇佣工人新雇佣工人)，也可以是负，也可以是负(人数减少，解雇工人人数减少，解雇工人)v目标是最小化总成本，包括雇佣与解雇成本和库存目标是最小化总成本，包括雇佣与解雇成本和库存成本成本v库存成本库存成本=50*(I1+I2+I3)为什么没有为什么没有I4?v雇佣与解雇成本雇佣与解雇成本=200*(3月、月、4月、月、5月和月和6月初雇佣月初雇佣临时工人的数量临时工人的数量)+400*(3月、月、4月、月、5月和月和6月初解雇月初解雇临时工人的数量临时工人的数量)例例2.3-6 多周期生产平滑模型多周期生产平滑模型v每个月库存量之间的约束每个月库存量之间的约束上月库存上月库存+当月产量当月产量=当月需求量当月需求量+当月库存当月库存v已知临时工人各月的产量为已知临时工人各月的产量为10 xi，则有，则有 10 x1=400+I1 3月月 I1+10 x2=600+I2 4月月 I2+10 x3=400+I35月月 I3+10 x4=5006月月 x1,x2,x3,x4=0,I1,I2,I3=0例例2.3-6 多周期生产平滑模型多周期生产平滑模型v雇佣和解雇量之间的约束雇佣和解雇量之间的约束当月零时工人人数当月零时工人人数=上月临时工人人数上月临时工人人数+变动量变动量Si=xi-xi-1v关键在于变动量即前面的关键在于变动量即前面的Si表示雇佣或解雇数量是可表示雇佣或解雇数量是可正可负的，为了建立线性规划模型，还需进一步处正可负的，为了建立线性规划模型，还需进一步处理理v令令Si=Si-Si+Si-是临时是临时(增加增加)雇佣工人的数量，雇佣工人的数量，Si-=0Si+是临时解雇是临时解雇(减少减少)工人的数量工人的数量,Si+=0如果这样表示会出如果这样表示会出现什么问题？现什么问题？例例2.3-6 多周期生产平滑模型多周期生产平滑模型vSi=Si-Si+上式对上式对Si-和和Si+有什么逻辑上的要求？有什么逻辑上的要求？v雇佣和解雇成本雇佣和解雇成本雇佣成本雇佣成本=200(S1-+S2-+S3-+S4-)解雇成本解雇成本=400(S1+S2+S3+S4+)例例2.3-6 多周期生产平滑模型多周期生产平滑模型例例2.3-6 多周期生产平滑模型多周期生产平滑模型v最优解最优解vz=19500$vx1=50,x2=50,x3=45,x4=45vS1-=50,S3+=5vI1=100,I3=50v思考：如果解雇费用和雇佣时间的长短有关系，每思考：如果解雇费用和雇佣时间的长短有关系，每月的生产成本和库存成本都不同，则该如何建模？月的生产成本和库存成本都不同，则该如何建模？vBob要接一个要接一个4个月的建设工程，需要雇佣卡车。他个月的建设工程，需要雇佣卡车。他现在手头上有现在手头上有20辆，但是从第一到第四个月这辆，但是从第一到第四个月这20辆辆车只有车只有1，2，3，1辆可以使用，其他的都有任务，辆可以使用，其他的都有任务，而最郁闷的是这个工程而最郁闷的是这个工程4个月里面分别需要个月里面分别需要10，12，14，8辆卡车。辆卡车。v卡车可以雇佣卡车可以雇佣1，2，3，4个月的，个月的，Bob要考虑分别要考虑分别雇佣时间长度为雇佣时间长度为14个月的卡车需要多少辆才能使自个月的卡车需要多少辆才能使自己的雇佣花费最少。己的雇佣花费最少。雇佣期限每月成本（美元）14000237003322543040例例 2.3-8 公交车调度安排公交车调度安排v某市正在研究寻求能满足运输需求的最少公交车数某市正在研究寻求能满足运输需求的最少公交车数v经研究发现，所需的最少公交车数随一天中的时间经研究发现，所需的最少公交车数随一天中的时间不同而变化，而且所需要的最少公交车数在若干连不同而变化，而且所需要的最少公交车数在若干连续的续的4小时间隔内可被近似为常数小时间隔内可被近似为常数v为了完成所需的日常维护，每辆公交车一天只能连为了完成所需的日常维护，每辆公交车一天只能连续运行续运行8小时小时v要求：确定每班运行公交车的数量，以满足最小需要求：确定每班运行公交车的数量，以满足最小需求，使所运行的公交车总数量最少求，使所运行的公交车总数量最少例例 2.3-8 公交车调度安排公交车调度安排0:0012848:0012:0016:0020:000:004:0081071244例例 2.3-8 公交车调度安排公交车调度安排x1x2x3x4x5x6定义变量定义变量例例 2.3-8 公交车调度安排公交车调度安排v目标：总的车辆最少目标：总的车辆最少min z=x1+x2+x3+x4+x5+x6v约束：满足各时段的需求约束：满足各时段的需求x1 +x6 =4x1+x2 =8 x2+x3 =10 x3+x4 =7 x4+x5 =12 x5+x6 =4为什么不用为什么不用等于号？等于号？线性规划模型的软件求解线性规划模型的软件求解vExcel：直观，但变量数和约束数有限制：直观，但变量数和约束数有限制vMatlab：常用，但是有的功能使用不方便：常用，但是有的功能使用不方便vLingo：专业，强大，：专业，强大，大家自学大家自学第第3章章 单纯形方法和灵敏度分析单纯形方法和灵敏度分析v本次讲座由于内容的限制不深入线性规划的求解方本次讲座由于内容的限制不深入线性规划的求解方法法单纯形法，虽然就方法本身而言是一个体现单纯形法，虽然就方法本身而言是一个体现优化思想的极好例子。优化思想的极好例子。v在日常学习、工作和比赛中可以方便的使用软件求在日常学习、工作和比赛中可以方便的使用软件求解模型，因而对于大家实际的重点在于如何构造线解模型，因而对于大家实际的重点在于如何构造线性规划模型。性规划模型。v这里只给出一些概念上的澄清这里只给出一些概念上的澄清3.1 等式形式的线性规划模型等式形式的线性规划模型v单纯形法要求线性规划模型具有下述的称为标准型单纯形法要求线性规划模型具有下述的称为标准型的形式：的形式：约束都是等式约束都是等式具有非负的右端项具有非负的右端项变量非负变量非负v这个要求只针对单纯性方法，很多软件并无此限制这个要求只针对单纯性方法，很多软件并无此限制3.1.1 将不等式转化为等式将不等式转化为等式v小于等于小于等于=的约束给出了某种资源的上限的约束给出了某种资源的上限6x1+4x2=24v由于上式中左端项小于等于右端项由于上式中左端项小于等于右端项 右端项减左右端项减左端项将大于等于端项将大于等于0 在左端加上左端比右端少的在左端加上左端比右端少的量则可转化为等式约束量则可转化为等式约束6x1+4x2+s1=24,s1=0s1称为松弛变量称为松弛变量3.1.1 将不等式转化为等式将不等式转化为等式v同理在大于等于约束式的左端减去一个大于等于同理在大于等于约束式的左端减去一个大于等于0的的量可使不等式变为等式量可使不等式变为等式x1+x2=800 x1+x2-S1=800S1称为剩余变量称为剩余变量v右端项为负值的处理右端项为负值的处理-x1+x2=-3-x1+x2+s1=-3x1-x2-s1=33.1.1 将不等式转化为等式将不等式转化为等式v不等式转化为等式的目的不等式转化为等式的目的v线性不等式组容易求解还是线性等式组容易求解？线性不等式组容易求解还是线性等式组容易求解？v化为等式后可用采用线性方程组的解法求解化为等式后可用采用线性方程组的解法求解3.1.2 处理无限制变量处理无限制变量v若若xi=0,xi=0从线性代数方程组的角度讨论从线性代数方程组的角度讨论v化为等式后，线性规划模型可表示如下化为等式后，线性规划模型可表示如下 Max Z=CX AX=b X=0v其中其中A属于属于Rm*n，通常而言，通常而言，mn时，称为超定方程组，往往是矛盾的时，称为超定方程组，往往是矛盾的无解无解转化为求解转化为求解最小二乘解最小二乘解v当当mn时，称为待定方程组，往往有时，称为待定方程组，往往有多解多解优化问题往往是允许多解的问题优化问题往往是允许多解的问题单纯形方法单纯形方法v细节不在课堂上解释细节不在课堂上解释v要求大家掌握软件求解要求大家掌握软件求解v单纯形方法的细节体现了优美的迭代过程的构造单纯形方法的细节体现了优美的迭代过程的构造3.6 灵敏度分析灵敏度分析v在线性规划模型或其他数学模型中，外部约束在线性规划模型或其他数学模型中，外部约束(表现表现为各种参数，如线性规划模型中的价值系数、工艺为各种参数，如线性规划模型中的价值系数、工艺系数和资源限量系数和资源限量)决定模型的解。决定模型的解。v这些参数有的是有客观取值的，有的则是主观估计这些参数有的是有客观取值的，有的则是主观估计的，可能跟准确值有较大出入的，可能跟准确值有较大出入v出于以上考虑，线性规划理论中专门讨论所谓的灵出于以上考虑，线性规划理论中专门讨论所谓的灵敏度分析，找出在不改变最优解敏度分析，找出在不改变最优解/最优基的情况下输最优基的情况下输入参数允许变化的范围入参数允许变化的范围3.6 灵敏度分析灵敏度分析v线性规划的灵敏度分析问题，更一般性地可对应到线性规划的灵敏度分析问题，更一般性地可对应到输入输入输出系统中的稳定性分析，即输出对输入的输出系统中的稳定性分析，即输出对输入的微小变化的敏感性。微小变化的敏感性。在数学模型中，这首先取决于实际系统的性态，在数学模型中，这首先取决于实际系统的性态，其次取决于所建立的数学模型其次取决于所建立的数学模型v在实际建模的例子中，通常数值算例是针对一组输在实际建模的例子中，通常数值算例是针对一组输入参数的。入参数的。v要注意我们的要注意我们的成果是一个模型成果是一个模型(一个方法一个方法)而不是一而不是一个简单的结果个简单的结果，所以通常要变化输入参数以给出在，所以通常要变化输入参数以给出在不同情况下对实际问题的建议。不同情况下对实际问题的建议。3.6 灵敏度分析灵敏度分析v见：见：灵敏性分析的意义灵敏性分析的意义.ppt