线性规划模型的应用 (2).ppt
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_05.gif)
《线性规划模型的应用 (2).ppt》由会员分享,可在线阅读,更多相关《线性规划模型的应用 (2).ppt(89页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、线性规划模型的应用线性规划模型的应用线性规划与运筹学线性规划与运筹学v线性规划属于最优化的一个分支,研究在线性目标线性规划属于最优化的一个分支,研究在线性目标函数和线性约束条件下的最优化问题函数和线性约束条件下的最优化问题v线性规划在实践中有非常多的应用。西方的所谓管线性规划在实践中有非常多的应用。西方的所谓管理科学其实主要是运筹学,而线性规划是运筹学的理科学其实主要是运筹学,而线性规划是运筹学的一个主要内容。一个主要内容。v下面先介绍什么是最优化问题下面先介绍什么是最优化问题什么是优化问题什么是优化问题v1.1 运筹学模型运筹学模型v假设有一项工作需要假设有一项工作需要5周完成,其间要往返于
2、甲地与周完成,其间要往返于甲地与乙地之间。每周一要乘飞机从甲地出发,周三返回乙地之间。每周一要乘飞机从甲地出发,周三返回v普通往返机票价格为普通往返机票价格为400元元v如果往返时间跨越周末,则可享受如果往返时间跨越周末,则可享受20%的优惠的优惠v单程机票的价格是普通往返机票价格的单程机票的价格是普通往返机票价格的75%v如何安排购票策略,使得如何安排购票策略,使得总费用最小总费用最小?什么是优化问题什么是优化问题v做一件工作,有多种方法,哪种方法做好呢?做一件工作,有多种方法,哪种方法做好呢?列出所有可行方案,逐一评价列出所有可行方案,逐一评价什么样的方法是可行的?实际问题有哪些约束?什么
3、样的方法是可行的?实际问题有哪些约束?如何评价解决方案?如何评价解决方案?v求解问题的求解问题的策略策略往往不能一步求到最优解往往不能一步求到最优解先找到一个可行的方案,再尝试改进它先找到一个可行的方案,再尝试改进它v问题可能是问题可能是离散型离散型的,也可能是的,也可能是连续型连续型的的机票购买的问题属于机票购买的问题属于.如何改进方案?如何如何改进方案?如何判断已达最优?判断已达最优?1.1 运筹学模型运筹学模型v对方案的限制:每周周一从甲至乙,周三返对方案的限制:每周周一从甲至乙,周三返v可能的方案可能的方案1、购买五张普通的甲、购买五张普通的甲-乙乙-甲往返票,每周一出发,甲往返票,每
4、周一出发,周三返回周三返回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)=160
5、01.1 运筹学模型运筹学模型v考虑用一段长为考虑用一段长为L的电线来围成一个矩形,要让这个的电线来围成一个矩形,要让这个矩形的面积最大,其长和宽该取多少呢?矩形的面积最大,其长和宽该取多少呢?v与前面购买机票问题不同,这里的长和宽是与前面购买机票问题不同,这里的长和宽是连续变连续变化化的,可能方案的个数有无穷多种!的,可能方案的个数有无穷多种!v我们可以控制的因素是矩形的长与宽,记为我们可以控制的因素是矩形的长与宽,记为w和和hv可行方案要满足:可行方案要满足:w+h=L/2w=0,h=0v下面建立该问题的模型下面建立该问题的模型1.1 运筹学模型运筹学模型vmax z=whvs.t.2(w
6、+h)=L,w,h=0v第一部分为第一部分为目标函数目标函数,这里是求,这里是求wh的最大值,目标的最大值,目标函数即为评价方案优劣的标准函数即为评价方案优劣的标准(指标指标)通常求效益、成绩、利润时求通常求效益、成绩、利润时求最大值最大值求费用、风险、代价时求求费用、风险、代价时求最小值最小值v第二部分为第二部分为约束条件约束条件,表明可行方案必须满足的条,表明可行方案必须满足的条件件基本概念基本概念v满足所有约束条件的解称为满足所有约束条件的解称为可行解可行解(feasible)v所有可行解构成问题的所有可行解构成问题的可行域可行域或或可行解集合可行解集合v所有可行解中取得最好目标值的解称
7、为所有可行解中取得最好目标值的解称为最优解最优解(optimal)v如果在模型求解的过程中丢掉了部分可行解,则得如果在模型求解的过程中丢掉了部分可行解,则得到的最优解可能实际上只是局部最优解或次优解到的最优解可能实际上只是局部最优解或次优解除非明确的可排除部分区域除非明确的可排除部分区域(确定不可行或最优解确定不可行或最优解一定不在其中一定不在其中),否则不要丢掉可能方案!,否则不要丢掉可能方案!可行解、最优解、次优解可行解、最优解、次优解v对于离散型的机票购买问题,可行方案是有限多的对于离散型的机票购买问题,可行方案是有限多的若问题的规模较小,总可以枚举出所有解,求得若问题的规模较小,总可以
8、枚举出所有解,求得最优解最优解问题规模较大时,只能找到问题规模较大时,只能找到满意解满意解或或可行解可行解v对于连续型的问题,可行方案有无限多种对于连续型的问题,可行方案有无限多种不能采用枚举的方法,需要找到最优解所满足的不能采用枚举的方法,需要找到最优解所满足的充分性条件充分性条件最优性条件可能是局部的,也可能是全局的最优性条件可能是局部的,也可能是全局的最优解不仅与目标函数有关,还与可行域有关最优解不仅与目标函数有关,还与可行域有关1.2 运筹学模型的求解运筹学模型的求解v运筹学模型在数学上实际就是运筹学模型在数学上实际就是最优化模型最优化模型:在满足:在满足一定约束条件下一定约束条件下(
9、也可能是没有约束的也可能是没有约束的),求目标函,求目标函数的最小值数的最小值(或最大值或最大值)v运筹学问题通常是用某些算法求解出来的,往往要运筹学问题通常是用某些算法求解出来的,往往要借助于计算机借助于计算机v有时求出最优解非常困难,这时使用有时求出最优解非常困难,这时使用启发式方启发式方法转法转而求取较好的可行解而求取较好的可行解1.2 运筹学模型的求解运筹学模型的求解v困难困难实际运筹学问题的目标和约束可能很难用数学式实际运筹学问题的目标和约束可能很难用数学式来描述来描述不好的模型会加重求解的复杂度,所以要不断调不好的模型会加重求解的复杂度,所以要不断调整模型整模型化简问题,抓住关键因
10、素:很多问题在数学上是化简问题,抓住关键因素:很多问题在数学上是非常困难的,但是加上实际背景的约束,往往可非常困难的,但是加上实际背景的约束,往往可得到简化得到简化仅有数学是不够的仅有数学是不够的v最忌讳的是最忌讳的是生搬硬套生搬硬套模型,一定要从问题的背景出模型,一定要从问题的背景出发仔细分析,这样才能发仔细分析,这样才能理解模型和改进模型理解模型和改进模型v产生一个问题的因素有很多,要分析出哪些是实际产生一个问题的因素有很多,要分析出哪些是实际可以操作的环节可以操作的环节v建模竞赛建模竞赛(尤其是美国赛尤其是美国赛)的题目往往从实践中来,的题目往往从实践中来,又要求返回到实际中去又要求返回
11、到实际中去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-clas
12、s 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 make
13、s 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
14、 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,g
15、ate 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这道题目
16、要用仿真算法来检验各种登机方案这道题目要用仿真算法来检验各种登机方案困难:不可能穷举所有可能的方案困难:不可能穷举所有可能的方案v问题:能否按照前面的图引导乘客?为什么?问题:能否按照前面的图引导乘客?为什么?1.6 运用运筹学的几个步骤运用运筹学的几个步骤v其实与数学建模的步骤非常类似其实与数学建模的步骤非常类似v问题定义问题定义目标、限制、假设目标、限制、假设v模型构造模型构造实际的问题往往不能使用标准模型而要加以改动实际的问题往往不能使用标准模型而要加以改动v模型求解模型求解有时很容易,有时很困难,尤其是数据量较大时有时很容易,有时很困难,尤其是数据量较大时可能需要返回去修改模型!可能需
17、要返回去修改模型!注意注意灵敏度分析灵敏度分析!1.6 运用运筹学的几个步骤运用运筹学的几个步骤v模型验证模型验证模型是否正确模型是否正确(模型是在一定假设和简化下作出的模型是在一定假设和简化下作出的)?是否符合实际?是否符合实际?有时可以用仿真来检验有时可以用仿真来检验v实施实施针对实际操作的人,使用不那么数学的语言解释针对实际操作的人,使用不那么数学的语言解释方案方案线形规划模型线形规划模型v2.1 二维变量的线形规划模型二维变量的线形规划模型v例例2.1-1 某公司使用某公司使用M1和和M2两种原料生产内、外墙两种原料生产内、外墙涂料涂料v内墙涂料的日需量不超过外墙涂料的日需量加内墙涂料
18、的日需量不超过外墙涂料的日需量加1吨,吨,内墙涂料的最大日需量是内墙涂料的最大日需量是2吨吨每吨产品使用原料的吨数每吨产品使用原料的吨数日最大可用日最大可用量量(吨吨)外墙涂料外墙涂料内墙涂料内墙涂料原料原料 M1原料原料 M26142246每吨利润每吨利润542.1 二维变量的线形规划模型二维变量的线形规划模型v下面建立下面建立求日总利润最大求日总利润最大的生产方案的线性规划模的生产方案的线性规划模型型v线形规划模型的构成线形规划模型的构成决策变量决策变量目标函数目标函数约束条件约束条件2.1 二维变量的线形规划模型二维变量的线形规划模型v例例2.1-1v很自然设内、外墙涂料的日产量为很自然
19、设内、外墙涂料的日产量为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线性体现在线性体现在目标函数目标函数和和约束条件都是决策变量的
20、线约束条件都是决策变量的线性函数性函数v线性蕴含着线性规划必须满足的线性蕴含着线性规划必须满足的3条基本性质条基本性质v比例性比例性每个决策变量无论在目标函数中还是在约束条件每个决策变量无论在目标函数中还是在约束条件中其贡献与决策变量的值成比例。中其贡献与决策变量的值成比例。目标函数中决策变量的系数称为目标函数中决策变量的系数称为价值系数价值系数约束条件中决策变量的系数称为约束条件中决策变量的系数称为工艺系数工艺系数线性规划模型的性质线性规划模型的性质v线性蕴含着线性规划必须满足的线性蕴含着线性规划必须满足的3条基本性质条基本性质v可加性可加性所有变量在目标函数和约束中的总贡献等于每个所有变量
21、在目标函数和约束中的总贡献等于每个变量各自贡献的直接和变量各自贡献的直接和NaCl=Na+Cl-?1+1=?v确定性确定性线性规划中的系数都是确定的线性规划中的系数都是确定的如果不是确定的,则可能要用如果不是确定的,则可能要用概率模型概率模型来描述来描述思考思考v假定涂料厂采用按量打折销售的方法,把它的外墙假定涂料厂采用按量打折销售的方法,把它的外墙涂料卖给某个批发商。如果批发商每日的购买量不涂料卖给某个批发商。如果批发商每日的购买量不超过超过2吨,则工厂每吨的利润是吨,则工厂每吨的利润是5000元,否则是元,否则是4500元。元。v给出目标函数的数学表达式,得到的函数还是线性给出目标函数的数
22、学表达式,得到的函数还是线性的吗?的吗?2.2 线性规划的图解法线性规划的图解法v对只有两个决策变量的线型规划问题,可以通过图对只有两个决策变量的线型规划问题,可以通过图解法直观的求解解法直观的求解v图解法的步骤:图解法的步骤:v1.求可行解集合:求可行解集合:分别求出满足每个约束包括变量非分别求出满足每个约束包括变量非负要求的区域,其交集为负要求的区域,其交集为可行解集合可行解集合,或称或称可行域可行域v2.绘制目标函数图形。绘制目标函数图形。先过原点作一条矢量指向点先过原点作一条矢量指向点(c1,c2),矢量的方向就是目标函数增加的方向,称,矢量的方向就是目标函数增加的方向,称为为梯度方向
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 线性规划模型的应用 2 线性规划 模型 应用
![提示](https://www.taowenge.com/images/bang_tan.gif)
限制150内