线性规划模型的应用

《线性规划模型的应用》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、线性规划模型的应用线性规划与运筹学线性规划属于最优化的一个分支，研究在线性目标函数和线性约束条件下的最优化问题线性规划在实践中有非常多的应用。西方的所谓管理科学其实主要是运筹学，而线性规划是运筹学的一个主要内容。下面先介绍什么是最优化问题什么是优化问题1.1运筹学模型假设有一项工作需要5周完成，其间要往返于甲地与乙地之间。每周一要乘飞机从甲地出发，周三返回普通往返机票价格为400元如果往返时间跨越周末，则可享受20%的优惠单程机票的价格是普通往返机票价格的75%如何安排购票策略，使得总费用最小？什么是优化问题做一件

2、工作，有多种方法，哪种方法做好呢？列出所有可行方案，逐一评价什么样的方法是可行的？实际问题有哪些约束？如何评价解决方案？求解问题的策略往往不能一步求到最优解先找到一个可行的方案，再尝试改进它问题可能是离散型的，也可能是连续型的机票购买的问题属于...如何改进方案？如何判断已达最优？1.1运筹学模型对方案的限制：每周周一从甲至乙，周三返可能的方案1、购买五张普通的甲-乙-甲往返票，每周一出发，周三返回2、购买一张甲-乙的单程机票和4张跨周末的甲-乙-甲往返票，再买一张乙-甲单程票3、先购买一张第一周周一出发、最后一周

3、星期三返程的甲-乙-甲往返票，再购买4张跨周末的乙-甲-乙往返票1.1运筹学模型评价：以最小费用为标准方案1：5*400=2000方案2：0.75*400+4*(0.8*400)+0.75*400=1880方案3：5*(0.8*400)=16001.1运筹学模型考虑用一段长为L的电线来围成一个矩形，要让这个矩形的面积最大，其长和宽该取多少呢？与前面购买机票问题不同，这里的长和宽是连续变化的，可能方案的个数有无穷多种！我们可以控制的因素是矩形的长与宽，记为w和h可行方案要满足：w+h=L/2w>=0,h>=0下面建立

4、该问题的模型1.1运筹学模型maxz=whs.t.2(w+h)=L,w,h>=0第一部分为目标函数，这里是求wh的最大值，目标函数即为评价方案优劣的标准(指标)通常求效益、成绩、利润时求最大值求费用、风险、代价时求最小值第二部分为约束条件，表明可行方案必须满足的条件基本概念满足所有约束条件的解称为可行解(feasible)所有可行解构成问题的可行域或可行解集合所有可行解中取得最好目标值的解称为最优解(optimal)如果在模型求解的过程中丢掉了部分可行解，则得到的最优解可能实际上只是局部最优解或次优解除非明确的可排

5、除部分区域(确定不可行或最优解一定不在其中)，否则不要丢掉可能方案！可行解、最优解、次优解对于离散型的机票购买问题，可行方案是有限多的若问题的规模较小，总可以枚举出所有解，求得最优解问题规模较大时，只能找到满意解或可行解对于连续型的问题，可行方案有无限多种不能采用枚举的方法，需要找到最优解所满足的充分性条件最优性条件可能是局部的，也可能是全局的最优解不仅与目标函数有关，还与可行域有关1.2运筹学模型的求解运筹学模型在数学上实际就是最优化模型：在满足一定约束条件下(也可能是没有约束的)，求目标函数的最小值(或最大值)

6、运筹学问题通常是用某些算法求解出来的，往往要借助于计算机有时求出最优解非常困难，这时使用启发式方法转而求取较好的可行解1.2运筹学模型的求解困难实际运筹学问题的目标和约束可能很难用数学式来描述不好的模型会加重求解的复杂度，所以要不断调整模型化简问题，抓住关键因素：很多问题在数学上是非常困难的，但是加上实际背景的约束，往往可得到简化仅有数学是不够的最忌讳的是生搬硬套模型，一定要从问题的背景出发仔细分析，这样才能理解模型和改进模型产生一个问题的因素有很多，要分析出哪些是实际可以操作的环节建模竞赛(尤其是美国赛)的题目往

7、往从实践中来，又要求返回到实际中去MCM2007TheAirplaneSeatingProblemAirlinesarefreetoseatpassengerswaitingtoboardanaircraftinanyorderwhatsoever.Ithasbecomecustomarytoseatpassengerswithspecialneedsfirst,followedbyfirst-classpassengers(whositatthefrontoftheplane).Thencoachandbusin

8、ess-classpassengersareseatedbygroupsofrows,beginningwiththerowatthebackoftheplaneandproceedingforward.MCM2007TheAirplaneSeatingProblemApartfromconsiderationofthepassengers’waittime